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

From: Will M Farr (farr at MIT.EDU)
Date: Wed Sep 2 17:31:18 EDT 2009

There's no way to make this work if you use a bare list as your stack  
data structure.  However, if you make your own stack data structure  
which stores a list of the elements on the stack, then you can store a  
new list in the structure for every stack-push!/pop!.  (By the way,  
it's customary in Scheme to name procedures that mutate their  
arguments with trailing "!".)  Something like the following sounds  
like what you want:

#lang scheme

;; A stack stores a list of the elements it contains
;; #:mutable needed to change the stored list on pop/push
;; #:transparent for easy printing and inspection.
(define-struct stack (elements) #:mutable #:transparent)

;; Push obj onto the top of the stack. Return value is void
(define (stack-push! stack obj)
   (set-stack-elements! stack (cons obj (stack-elements stack))))

;; Pop the top object off the stack and return it
(define (stack-pop! stack)
   (when (null? (stack-elements stack))
     (error 'stack-pop! "empty stack: ~a" stack))
   (let* ((elements (stack-elements stack))
          (top (car elements)))
     (set-stack-elements! stack (cdr elements))

;; Look at the top element without changing it
(define (stack-peek stack)
   (when (null? (stack-elements stack))
     (error 'stack-peek "empty stack: ~a" stack))
   (car (stack-elements stack)))

;; Tests.

(define the-stack (make-stack '()))

(stack-push! the-stack 1)
(stack-push! the-stack 2)
(stack-push! the-stack 3)

(equal? (stack-peek the-stack) 3)
;; #t

(equal? (stack-pop! the-stack) 3)
;; #t

(equal? (stack-peek the-stack) 2)
;; #t

(stack-push! the-stack 'a)

(equal? (stack-pop! the-stack) 'a)
;; #t

(equal? (stack-pop! the-stack) 2)
;; #t

(equal? (stack-pop! the-stack) 1)
;; #t

(stack-pop! the-stack)
;; Error!




On Sep 2, 2009, at 10:42 AM, tbourdon wrote:

> As I said, "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" and that's the whole point. I don't want stack-
> push to return anything. I want it to change the state of the stack
> that's passed in so the caller can reference that stack's changed
> state later. In other words, is there a way for the following to work?
> (define stack ()) ; stack is defined as empty list.
> (stack-push stack 1) ; stack-push pushes 1 onto stack.
> (stack-top stack) => 1 ; stack-top returns 1.
> On Sep 2, 12:30 am, Matthias Felleisen <matth... at ccs.neu.edu> wrote:
>> On Aug 30, 2009, at 7:42 PM, tbourdon wrote:
>>> 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
>> You omitted the most important part of your quasi-spec? What should
>> stack-push return?
>> _________________________________________________
>>   For list-related administrative tasks:
>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 203 bytes
Desc: This is a digitally signed message part
URL: <http://lists.racket-lang.org/users/archive/attachments/20090902/250cce47/attachment.sig>

Posted on the users mailing list.