CSC 324 Tutorial Week 5
=======================

stack objects
=============

To further illustrate the use of set!, let's consider the
implementation of stack objects whose internal workings are not
visible on the outside. A stack object accepts one of four messages:
 - empty?, which returns #t if the stack is empty; 
 - push!, which adds an object to the top of the stack; 
 - top, which returns the object on the top of the stack; and
 - pop!, which removes the object on top of the stack. 
The procedure make-stack given below creates a new stack each time it
is called in a manner similar to make-counter.

Question
--------

Define make-stack that returns such an object.

Example
-------

(define stack1 (make-stack))
(define stack2 (make-stack))

(stack1 'empty?) => #t
(stack1 'push! 'a)
(stack1 'empty?) => #f
(stack2 'empty?) => #t
(stack1 'push! 'b)
(stack1 'top) => b
(stack1 'pop!)
(stack1 'top) => a
... and so on

Answer
------

(define make-stack
  (lambda ()
    (let ((ls '()))
      (lambda arglist   
	(let ((msg (car arglist))   
	      (args (cdr arglist)))
	  (cond
	   ((eqv? msg 'empty?) (null? ls))
	   ((eqv? msg 'push!)
	    (set! ls (cons (car args) ls)))
	   ((eqv? msg 'top) (car ls))
	   ((eqv? msg 'pop!)
	    (set! ls (cdr ls)))
	   (else "oops")))))) 

Each stack is stored as a list bound to the variable ls; 
set! is used to change this binding for push! and pop!. 



set-car! and set-cdr!
=====================

In addition to changing the values of variables, we can also change
the values of the car and cdr fields of a pair, using the procedures
set-car! and set-cdr!.

(define p (list 1 2 3))
(set-car! (cdr p) 'two)
p => (1 two 3)
(set-cdr! p '())
p => (1) 

Exercise: extend this stack to a queue object. (We need to use a
header to keep track of the front and end of the list.)

(if you have time, you can go through setting up the queue, but I'd
prefer if you made sure they knew define-syntax)


define-syntax
=============

Recall: define-syntax is similar to define, except that define-syntax
associates a syntactic transformation procedure, or transformer, with
a keyword (such as let), rather than associating a value with a
variable. 

Recall that we saw that 

  (let ((var1 val1) ...) e1 e2 ...)

was equivalent to the following lambda expression

  ((lambda (var1 ...) e1 e2 ...) val1)


Question
--------

Define let.

Answer
------

(define-syntax let
  (syntax-rules ()
    ((_ ((x v) ...) e1 e2 ...)
     ((lambda (x ...) e1 e2 ...) v ...))))

Carefully walk through translation. syntax-rules specifies a list of
additional keywords, then a number of syntax rules.
A rule specifies a pattern to match, and how it should be transformed.


Question
--------

Recall that and is a special form.
Define and.

Observation
-----------

and takes an arbitrary number of arguments. So we must design this recursively!


Sub-Questions
-------------
What is/are the base case(s)? What is/are the recursive case(s)?

Answer
------
Base cases: zero or 1 argument
Recursive cases: at _least_ two arguments


What should be returned in base cases?
 - zero args => #t
 - one arg => value of argument

Thus, we have so far:

(define-syntax and
  (syntax-rules ()
    ((_) #t)
    ((_ e) e)
     ------

How do we specify the recursive case?
Answer: (_ e1 e2 e3 ...)
Why? Because we want to be sure there are at least 2 arguments!
Remember that form "e ..." matches zero or more expressions, so we
must write "e2 e3 ..." to match one or more expressions.

The rest should be easy, giving us the final answer:

(define-syntax and
  (syntax-rules ()
    ((_) #t)
    ((_ e) e)
    ((_ e1 e2 e3 ...)
     (if e1 (and e2 e3 ...) #f)))) 



Question 
--------
(good to leave this for them to work out themselves, then mention the subtlety)

Define or.

Answer
------

Watch out for this subtlety! We don't want to reevaluate expressions twice!
(especially if there are side-effects)

A temporary variable must be introduced for each intermediate value so
that we can both test the value and return it if it is a true
value. (A similar temporary is not needed for and since there is only
one false value, #f.)

Here's the answer:

(define-syntax or
  (syntax-rules ()
    ((_) #f)
    ((_ e) e)
    ((_ e1 e2 e3 ...)
     (let ((t e1))
       (if t t (or e2 e3 ...))))))


when and unless
===============

Question
--------

Define when. when has format:

  (when test e1 e2 ... eN)

The first argument to when should be tested. If true, evaluate e1 ... eN
in order from left to right. If false, undefined.
Must be at least one expression after test.

Answer
------

Procedure or macro?  - macro
How to evaluate expressions left to right?  - begin

What should when expand to?  - something like

  (if test (begin e1 e2 ... eN))

Do it:

(define-syntax when
  (syntax-rules ()
    ((when test e1 e2 ...)
     (if test (begin e1 e2 ...)))
    ))


Question
--------

Define unless. unless is similar, except doesn't evaluate expressions 
if the test is true.

  (until test e1 e2 ...)

Answer
------

Two ways to do it. Add a not call:

(define-syntax unless
  (syntax-rules ()
    ((_ test e1 e2 ...)
     (if (not test) (begin e1 e2 ...)))
    ))

Or use the else part of the if (i.e., don't use not).
  - But what to do in then part of if?? use void.

(define-syntax unless
  (syntax-rules ()
    ((_ test e1 e2 ...)
     (if test
	 (void)
	 (begin e1 e2 ...)))
    ))

mzscheme includes void as a built-in function that returns nothing.
Can write as:
(define void (if #f 1))


More Recursion (if extra time)
==============

All of the recursive procedures shown so far have been directly
recursive. That is, each procedure directly applies itself to a new
argument. It is also possible to write two procedures that use each
other, resulting in indirect (mutual) recursion.

Question:

  Define the procedures odd? and even?, each in terms of the other. 
  [Hint: What should each return when its argument is 0?]

  (even? 17) => #f
  (odd? 17) => #t 

Answer:

  (define even?
    (lambda (x)
      (or (= x 0)
	  (odd? (- x 1)))))
  (define odd?
    (lambda (x)
      (and (not (= x 0))
	   (even? (- x 1)))))

  Why does it work?
    - even? and odd? get bound when the procedures are called. define
    creates the names in the top-level scope, so they'll be available
    when we need to call them.

Question:

  Would it work if we defined even? and odd? inside a let?
    ... inside a let*?
    ... inside a letrec?

  i.e.,

    (let ((myeven?
	   (lambda (x)
	     (or (= x 0)
		 (myodd? (- x 1)))))
	  (myodd?
	   (lambda (x)
	     (and (not (= x 0))
		  (myeven? (- x 1))))))
      (list (myeven? 20) (myodd? 20)))

Answer:

  No for let and let*: 
     myodd? isn't visible in the scope that lambda is being evaluated.

  Yes for letrec:
     This is the whole point of why we need letrec.