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.