How do I write Push and Pop in Scheme?

Question

Right now I have

(define (push x a-list)
  (set! a-list (cons a-list x)))

(define (pop a-list)
  (let ((result (first a-list)))
    (set! a-list  (rest a-list))
    result))

But I get this result:

Welcome to DrScheme, version 4.2 [3m].
Language: Module; memory limit: 256 megabytes.
> (define my-list (list 1 2 3))
> (push 4 my-list)
> my-list
(1 2 3)
> (pop my-list)
1
> my-list
(1 2 3)

What am I doing wrong? Is there a better way to write push so that the element is added at the end and pop so that the element gets deleted from the first?

Answer 1

What you're doing there is modifying the "queue" locally only, and so the result is not available outside of the definition's scope. This is resulted because, in scheme, everything is passed by value, not by reference. And Scheme structures are immutable.

(define queue '()) ;; globally set

(define (push item)
  (set! queue (append queue (list item))))

(define (pop)
  (if (null? queue)
      '()
      (let ((pop (car queue)))
        (set! queue (cdr queue))
        pop)))

;; some testing
(push 1)
queue
(push 2)
queue
(push 3)
queue
(pop)
queue
(pop)
queue
(pop)

The problem relies on the matter that, in Scheme, data and manipulation of it follows the no side-effect rule

So for a true queue, we would want the mutability, which we don't have. So we must try and circumvent it.

Since everything is passed by value in scheme, as opposed to by reference, things remain local and remain unchanged, no side-effects. Therefore, I chose to create a global queue, which is a way to circumvent this, by applying our changes to the structure globally, rather than pass anything in.

In any case, if you just need 1 queue, this method will work fine, although it's memory intensive, as you're creating a new object each time you modify the structure.

For better results, we can use a macro to automate the creation of the queue's.

Answer 2

1. You are just setting what is bound to the lexical variable a-list. This variable doesn't exist anymore after the function exits.

2. cons makes a new cons cell. A cons cell consists of two parts, which are called car and cdr. A list is a series of cons cells where each car holds some value, and each cdr points to the respective next cell, the last cdr pointing to nil. When you write (cons a-list x), this creates a new cons cell with a reference to a-list in the car, and x in the cdr, which is most likely not what you want.

3. push and pop are normally understood as symmetric operations. When you push something onto a list (functioning as a stack), then you expect to get it back when you pop this list directly afterwards. Since a list is always referenced to at its beginning, you want to push there, by doing (cons x a-list).

4. IANAS (I am not a Schemer), but I think that the easiest way to get what you want is to make push a macro (using define-syntax) that expands to (set! <lst> (cons <obj> <lst>)). Otherwise, you need to pass a reference to your list to the push function. Similar holds for pop. Passing a reference can be done by wrapping into another list.

Answer 3

Svante is correct, using macros is the idiomatic method.

Here is a method with no macros, but on the down side you can not use normal lists as queues. Works with R5RS at least, should work in R6RS after importing correct libraries.

(define (push x queue)
  (let loop ((l (car queue)))
    (if (null? (cdr l))
      (set-cdr! l (list x))
      (loop (cdr l)))))

 (define (pop queue)
   (let ((tmp (car (car queue))))
     (set-car! queue (cdr (car queue)))
     tmp))

(define make-queue (lambda args (list args)))

(define q (make-queue 1 2 3))

(push 4 q)
q
; ((1 2 3 4))
(pop a)
; ((2 3 4))
q

Answer 4

I suppose you are trying to implement a queue. This can be done in several ways, but if you want both the insert and the remove operation to be performed in constant time, O(1), you must keep a reference to the front and the back of the queue.

You can keep these references in a cons cell or as in my example, wrapped in a closure.

The terminology push and pop are usually used when dealing with stacks, so I have changed these to enqueue and dequeue in the code below.

(define (make-queue)
  (let ((front '())
        (back '()))
    (lambda (msg . obj)
      (cond ((eq? msg 'empty?) (null? front))
            ((eq? msg 'enqueue!) 
             (if (null? front)
                 (begin 
                   (set! front obj)
                   (set! back obj))
                 (begin
                   (set-cdr! back obj)
                   (set! back obj))))
            ((eq? msg 'dequeue!) 
             (begin
               (let ((val (car front)))
                 (set! front (cdr front))
                 val)))
            ((eq? msg 'queue->list) front)))))

make-queue returns a procedure which wraps the state of the queue in the variables front and back. This procedure accepts different messages which will perform the procedures of the queue data structure.

This procedure can be used like this:

> (define q (make-queue))
> (q 'empty?)
#t
> (q 'enqueue! 4)
> (q 'empty?)
#f
> (q 'enqueue! 9)
> (q 'queue->list)
(4 9)
> (q 'dequeue!)
4
> (q 'queue->list)
(9)

This is almost object oriented programming in Scheme! You can think of front and back as private members of a queue class and the messages as methods.

The calling conventions is a bit backward but it is easy to wrap the queue in a nicer API:

(define (enqueue! queue x)
   (queue 'enqueue! x))

(define (dequeue! queue)
  (queue 'dequeue!))

(define (empty-queue? queue)
  (queue 'empty?))

(define (queue->list queue)
  (queue 'queue->list))

Edit:

As Eli points out, pairs are immutable by default in PLT Scheme, which means that there is no set-car! and set-cdr!. For the code to work in PLT Scheme you must use mutable pairs instead. In standard scheme (R4RS, R5RS or R6RS) the code should work unmodified.

Answer 5

This is a point about using mutation in your code: there is no need to jump to macros for that. I'll assume the stack operations for now: to get a simple value that you can pass around and mutate, all you need is a wrapper around the list and the rest of your code stays the same (well, with the minor change that makes it do stack operations properly). In PLT Scheme this is exactly what boxes are for:

(define (push x a-list)
  (set-box! a-list (cons x (unbox a-list))))

(define (pop a-list)
  (let ((result (first (unbox a-list))))
    (set-box! a-list (rest (unbox a-list)))
    result))

Note also that you can use begin0 instead of the let:

(define (pop a-list)
  (begin0 (first (unbox a-list))
    (set-box! a-list (rest (unbox a-list)))))

As for turning it into a queue, you can use one of the above methods, but except for the last version that Jonas wrote, the solutions are very inefficient. For example, if you do what Sev suggests:

(set-box! queue (append (unbox queue) (list x)))

then this copies the whole queue -- which means that a loop that adds items to your queue will copy it all on each addition, generating a lot of garbage for the GC (think about appending a character to the end of a string in a loop). The "unknown (google)" solution modifies the list and adds a pointer at its end, so it avoids generating garbage to collect, but it's still inefficient.

The solution that Jonas wrote is the common way to do this -- keeping a pointer to the end of the list. However, if you want to do it in PLT Scheme, you will need to use mutable pairs: mcons, mcar, mcdr, set-mcar!, set-mcdr!. The usual pairs in PLT are immutable since version 4.0 came out.