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.