CSC302 2006S, Class 11: The Scheme Report

Admin:
* Read R5RS 7.1 (Syntax)
* Missing: Dimitar, Alex
* Questions on the homework?
  Old strategy
	typedef struct node {
	  char data[STRING_MAX];
	  struct node *next;
	  struct node *last;
	  int val;
	}
  New strategy:
  * Simplest version of S expressions:
    S expression is: 
    * symbol
    * pair of s-expression and s-expression
  * So, let's think about each
  typedef struct sexp {
    int type;  // 0 for symbol, 1 for cons cell
    (void *)contents;  // Either (char *) or (struct node *)
  } 
  typedef struct node {
    struct sexp *car;
    struct sexp *cdr;
  }
Implementation of cons
  * allocate a new node.
  * fill in the car and cdr pointers.
  * allocate an sexp
  * fill in the type and the pointer to the node you just allocated.
* Why not use malloc for allocating a new node?
  * It wastes memory.  Malloc traditionally allocates much more than you asked for.
  * Solution?  Malloc large amounts and then manually manage that memory.

Overview:
* Why read R5RS?
* Particular questions.
* Looking ahead

/Why Read R5RS?/

* Observe a direction in which Lisp evolved.
* Read a real language standard that is not too large.
* Read the formal defintiion of a language (in denotational semantics)

/Some Questions/

* The report claims that (and) is true and (or) is false.  Why?
  * One way to think of and is "and is false when at least one of its parameters is false"  There are no false parameters when there are no parameters, so the answer cannot be false.  It must be true.
  * A practical reason
    (and false ...) => false
    (and true ...) => (and ...)
    * For the base case to work correctly, we need true
  * For or
    (or false ...) => (or ...)
    (or true ...) => true

* Tell me more about force and delay
  * Two perspectives on "apply function to arguments"
    * Eager: Evaluate arguments and then substitute evaluated acftuals for formals
    * Lazy: Substitute the (encapsulated) code of the actuals for the formals in the procedure
    * Advantages to lazy evaluation:
        (define constant-one (lambda (x) 1))
        (constant-one (sqrt 7))
    * Lazy evaluation is necessary in some cases
    (define fact
      (lambda (n)
        (if (= n 0)
            1
            (* n (fact (- n 1))))))
  (fact 0) 
   => (if (= 0 0) 1 (* 0 (fact (- 0 1))))
   => (if true 1 (* 0 (fact (- 0 1))))
   => (if true 1 (* 0 (fact -1)))
   => (if true 1 (* 0 (if (= -1 0) 1 (* -1 (fact (- -1 1))))))

Delay and force permit programmers to choose when to be eager
and when to be lazy.

Favorite example of the power of delayed evaluation:
* The Sieve of Eratosthenes

Theoretical reason: Church-Rosser Thm.
* In the lambda calculus, any result obtainable by any order of evaluation (including mixed) is obtainable by lazy evaluation.

//Why are there a dozen or so versions of equality testing?//

* Programmers get some control over efficiency and meaning
  eqv? only checks memory location
  equal? checks deep structure

  (eqv? (cons 'a 'b) (cons 'a 'b)) => #f

/Reading Section 7/

* Need to describe what the legal utterences are and what they mean
  * Syntax and Semantics
* Syntax (7.1) described in BNF
  <syntactic-unit> => how to build that syntactic unit
  In English
  <sentence> => <subject> <intransitive-verb>.
  <sentence> => <subject> <transitive-verb> <direct-object>.
  <subject> => <noun>
  <subject> => <adjective> <noun>
  <noun> => dog
  <noun> => frog
  <adjective> => green
* Semantics are denotational:
  * Define the meaning of each utterence using the lambda calculus
  * This lambda calculus is typed (ooh!) and uses an extended syntax