Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 2 down vote accepted

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).
share|improve this answer
    
add1 and sub1: that's what I was looking for! I kept trying inc and dec to no avail. Thank you :) – Xophmeister Jan 19 at 21:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.