Mutable stack in Racket

Question

I'm learning Racket and have implemented a mutable stack, which is just a bunch of wrappers around an underlying struct containing a size and buffer list (so it's not optimal, in terms of computational complexity). After consulting #racket and reading the first half of Greg Hendershott's Fear of Macros, I was able to write the syntax transformations I wanted for my implementation.

(module stack racket
  (module stack-implementation racket
    (struct stack (size buffer) #:mutable)

    ;; size :: stack -> integer
    (define (size stack) (stack-size stack))

    ;; non-empty-stack? :: stack -> boolean
    (define (non-empty-stack? stack)
      (and
        (stack? stack)
        (positive? (stack-size stack))))

    ;; push! :: stack -> any (new item) -> integer (size)
    (define (push! stack item)
      (set-stack-buffer! stack
        (append (list item) (stack-buffer stack)))

      (set-stack-size! stack (+ (stack-size stack) 1))

      (stack-size stack))

    ;; pop! :: (non-empty) stack -> any (head)
    (define (pop! stack)
      (let ([head (car (stack-buffer stack))]
            [tail (cdr (stack-buffer stack))])

        (set-stack-buffer! stack tail)
        (set-stack-size! stack (- (stack-size stack) 1))

        head))

    ;; make
    (define-syntax-rule (make name)
      (define name (stack 0 '())))

    (provide make
             stack?
             (contract-out
               [size  (-> stack?            integer?)]
               [push! (-> stack? any/c      integer?)]
               [pop!  (-> non-empty-stack?  any)])))

  (require 'stack-implementation
           (for-syntax racket/syntax))

  ;; make-stack
  ;  Defines a stack under the specified symbol <name>
  ;  Plus defines <name>-size, <name>-empty?, <name>-push! and <name>-pop!
  (define-syntax (make-stack stx)
    (syntax-case stx ()
      [(_ name)
        (with-syntax ([(size-fn empty-fn push-fn pop-fn)
                       (map (lambda (fn) (format-id stx "~a-~a" #'name fn))
                            '("size" "empty?" "push!" "pop!"))])
          #'(begin
              (make name)
              (define (size-fn)      (size name))
              (define (empty-fn)     (zero? (size-fn)))
              (define (push-fn item) (push! name item))
              (define (pop-fn)       (pop!  name))))]))

  (provide make-stack
           stack?))

I'm completely new to Racket and Lisp, so I'm guessing there are many improvements I can make here (e.g., the duplication in the macro where I define the helper function IDs), besides using a better underlying data structure.

Answer 1

Many Lisp programs use cons cells quite liberally instead of adding a separate stack structure, in that sense your concerns about complexity are probably a bit less critical. Since the stack is also carrying the length of the list it actually supports at least the additional size operator quite well. Of course writing more code for an underlying (resizable) vector could make sense, but again I wouldn't count on that being necessary.

For the code I only have minor suggestions, as it's pretty well written and clear what each part means; while I'm not that familiar with Racket it's easily readable to me.

• For the pattern (+/- x 1) there are also the functions add1 and sub1 which could be used.
• The non-empty-stack? could just check whether the buffer is null? or empty? instead. positive? sounds like there's some risk that the stack size might get negative for some reason. For the same reason the contract can probably also be tightened to check for non-negative integers.
• (append (list x) y) is a bit shorter as (cons x y).