Purely functional stack implementation with scheme

Question

I would like to implement a functional stack in scheme. This is my attempt:

(define make-stack
  (letrec ((do-op
            (lambda (stack op . val)
              (cond ((eq? op 'push)
                     (lambda (op . v)
                       (do-op (cons (car val) stack) op v)))
                    ((eq? op 'pop)
                     (lambda (op . v)
                       (do-op (cdr stack) op v)))
                    ((eq? op 'print)
                     (begin (display stack)
                            (newline)
                            (lambda (op . v)
                              (do-op stack op v))))))))
    (lambda (op . val)
      (do-op '() op val))))

The stack can be used as in this example:

(define s make-stack)
((((((s 'push 1) 'push 2) 'push 3) 'print) 'pop) 'print)

The output of this example is:

((3) (2) (1))
((2) (1))

Not exactly what I wanted, but not too bad. I wanted to ask the experienced schemers here if there is a way to make the stack behave more naturally, for example like this:

(define s make-stack)
(s 'push 1)
(s 'push 2)
(s 'pop)
...

while keeping it functional (so no mutability, no set!).

The first thing I thought was to keep returning a function with no arguments, but changing every lambda (op . v) with:

(lambda ()
  (lambda (op . v)
    ...

but this does not work as we still need to capture the returned function:

> (define s make-stack)
> ((s) 'push 1)
#<procedure>

Answer 1

Your goals are contradictory. If s is a stack, and your operations purely functional, then (s 'push 1) must return the same thing every time it is called. To capture the notion of change, you must use a different s each time. That's how your functional stack works: it gives you back a new stack, and you must compose function calls with it.