Scheme stack-like object

Question

Trying to build a very simple stack structure :

(define (make-stack lst)
 (lambda message
 (case (car message)
 ((see) (newline) (write lst))
 ((empty?) (null? lst))
 ((push) (begin
 (set-cdr! lst (list (car lst) (cdr lst)))
 (set-car! lst (cadr message))))
 ((pop) (let ((elt (car lst)))
 (set-car! lst (cadr lst))
 (set-cdr! lst (cddr lst))
 elt)))))

I can use it with:

(define L (make-stack (list 0)))
(L 'push 1)
(L 'push 2)
(L 'see)
(newline)
(write (L' pop))
(L 'see)

But I can't init it using an empty list, that's why I init my instantiation using (list 0). How to modify make-stack procedure for it to accept initialization with an empty list?

Edit: When I pass an empty list:

;The object (), passed as the first argument to `cdr`, is not the correct type.

• Sylwester: So what error do you get when doing (make-pile (list))?
• molbdnilo: Open your REPL and compare (list 1 (list 2 3)) to (cons 1 (list 2 3)). And think about what you get when you add the head of a list to the tail of the same list.

Answer 1

Your error is caused by calling car / cdr on empty list. You can use set!:

(define (make-stack lst)
 (lambda message
 (case (car message)
 ((see) (newline) (write lst))
 ((empty?) (null? lst))
 ((push) (set! lst (cons (cadr message) lst)))
 ((pop) (let ((elt (car lst)))
 (set! lst (cdr lst))
 elt)))))

You should also decide what will happen when you pop from empty stack.

Test:

(define L (make-stack (list)))
(L 'see)
(L 'push 1)
(L 'see)
(L 'push 2)
(L 'see)
(newline)
(write (L' pop))
(L 'see)

=>

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

• Barmar: If lst is null, (list (cadr message)) is the same as (cons (cadr message) lst)
• Barmar: So you don't need the if call unless you want to keep the mutating behavior when the list is not null.

Answer 2

I think you're making the structure of your stack too complicated. Just treat it as a simple list, with the first element being the top of the stack, with no messing with set-car! or set-cdr! (Which are what's stopping you from having an empty stack and which cause the bottom of the stack to be a weird nested list construct after the first push). Your methods should look like

(define (make-stack lst)
 (lambda message
 (case (car message)
 ((see) (newline) (write lst))
 ((empty?) (null? lst))
 ((push) (set! lst (cons (cadr message) lst)))
 ((pop)
 (let ((elt (car lst)))
 (set! lst (cdr lst))
 elt)))))

Then you can actually have an empty stack:

(define L (make-stack '()))
(L 'push 1)
(L 'push 2)
(L 'see) ; (2 1), compared to your current (2 1 (0 ()))

• Will Ness: they might have that structure as a requirement, in preparation for implementing a queue or a deque. I'm just guessing. :)

Answer 3

Just don't initialize it with an empty list. Always store one extra element in your stack.

This will simplify things greatly. Change your empty? predicate accordingly.