[plt-scheme] Lexical Scoping, References and Side Effects

From: tbourdon (tbourdon at gmail.com)
Date: Sun Aug 30 19:42:02 EDT 2009

Hello -

I'm currently teaching myself  Scheme by working through "Teach
Yourself Scheme in Fixnum Days" and "The Little Schemer". As I was
working through the sources I decided to break off and implement some
stack data structures. So far I've implemented the stack functions
three different ways and I've noticed that I really can't (or haven't
found a way) to create a reference to a stack and pass it around to be
operated on.

For example; I can't come up with an implementation for a stack-push
function where the following works:

(define stack ())
(stack-push stack 1)
(stack-top stack) => 1

I have been able to come up with the following implementation (1):

(define-struct list-pointer (value))
(define stack (make-list-pointer ()))
(stack-push stack 1)
(stack-top stack) => 1

I've also been able to implement the following (2):

(define stack ())
(set! stack (stack-push stack 1))
(stack-top stack) => 1

I also have a more traditional implementation (3) where I've defined
two structures (stack and stack-item) where a stack-item has a value
and reference to a next-stack-item. Because this implementation used
structures I was able to make my stack, pass it to the various stack
functions and have the caller's reference of stack changed in the

Now I've read in some places that side effects are avoided in Scheme.
But the idea of passing references down call stacks and changing the
values they point to is so pervasive in other languages that its
something I do as second nature. Is there really no way in Scheme to
create a reference to a value, pass it to a function and have it's
value changed in the caller's scope? My second implementation which
used the (define-struct list-pointer (value)) was my hack for this
behavior but I'm wondering if there's just something I'm missing.

For my second implementation I had the stack-push function just return
the updated stack but as you can see this leads to successive set!
calls in order to update the stack. While the stack-push function
seems more "Schemey" by not relying on side effects, it sure is a
paradigm shift from other languages.

Any insights on this topic would be appreciated.

Posted on the users mailing list.