Chapter 2: Getting Started

 

 

 

Expression is Basic Syntax Structure

 

  1. Constant data object (the value is the object)
    - Numbers, strings, symbols, lists

    2.  

  2. Procedure applications
    - procedure name followed by args e.g.     ( proc arg1 arg2 . . .)

    3.  

  3. Quote expressions
    - Prevents data list from being interpreted as procedure application
    - Example:     ( quote ( + 1 2 ) ) has value (+ 1 2), not value 3.
    - Shorten by using apostrophe:     '(+ 1 2 )
    - Prevents symbol from being interpreted as variable
    - Example:     ( quote ( hi ) ) has value hi

 

 

 

List: zero or more items enclosed in parentheses

  1. Items separated by white space; list enclosed in ( ) or [ ]
  2. Basic list procedures: car, cdr, cons, list
  3. car : Contents of Address Register (IBM 704)
    - Result is first list value
    - Example:     ( car '( 1 2 3 ) ) is 1
  4. cdr: Contents of Data Register (IBM 704)
    - Result is list* with first value removed
    - Example:     ( cdr '( 1 2 3 ) ) is ( 2 3 )
    - * not always a list. See "improper list", "dotted pair"
  5. cons: CONStruct
    - Takes two args, a value followed by a list*
    - Result is list having first arg as head
    - Example:     ( cons 1 '( 2 3 ) ) is ( 1 2 3 )
  6. list
    - Takes zero or more args, all values
    - Result is list consisting of those values
    - Example:     ( list 1 2 3 ) is ( 1 2 3 )

    7.  

  7. Proper and Improper lists
    - Proper list defined recursively, consists of pairs
    - Each pair consists of car (a value) and cdr (the next pair)
    - Think binary tree: each node has car as left child, cdr as right child
    - Proper list has list as right child; leaf right child is empty list ( )
    - Improper list has value rather than list as right child (cdr).
    - Example:     ( cons '1 '( 2 ) ) builds a proper list ( 1 2 )
    - Example: ( cons '1 '2 ) builds an improper list ( 1 . 2 )
    - Improper list printed as dotted pair. (last element preceded by dot)
    - Proper lists can be specified in dotted-pair notation.
    - Example:     ' ( 1 . ( 2 . ( ) ) ) is equivalent to ' ( 1 2 )

 

 

 

let-expressions and let-variables

 

  1. binds value to variable for remainder of expression (body)
    - example:     ( let ( ( x 3 ) ) ( + x x ) )
    - binding is: let ( ( x 3 ) )
    - body is: ( + x x )

    2.  

  2. body can itself contain a let expression (nested)

    3.  

  3. scoping/visibility rules apply if nested variable has same name

    4.  

  4. let-variable can be procedure name!
    - Example:     ( let ( ( opr * ) ) ( opr 3 4 ) )
    - What is its value?

    5.  

  5. Multiple let-variables in a let list
    - Example:     ( let ( (x 3) (y 4) (opr *) ) ( opr x y ) )
    - What is its value?

    6.  

  6. Let-variable can have complex expression as value
    - Example: 
    7. ( let ( ( x 3 ) ( y 4 ) )
   ( let ( ( z ( + y ( * x 2 ) ) ) )
      ( + ( * 10 z ) z )
   )
)

     

    result is 110.
    Explanation: Substituting     (+ y (* x 2)) for z,
    the body becomes:     (+ (* 10 (+ y (* x 2))) (+ y (* x 2)))
    which becomes: (+ (* 10 (+ 4 (* 3 2))) (+ 4 (* 3 2)))
    The equivalent infix is: (10 * (4 + (3 * 2))) + (4 + (3 * 2))

     

  7. Suppose you want binding to change?
    - Example: evaluate the above expression for x = 1, x = 2, x = 3
    - Cut and Paste let-expression, then edit to change binding

    OR

    - Define a procedure!

 

 

Lambda Expressions

 

  1. Expression that defines a procedure

    2.  

  2. General format: ( lambda ( var . . .) exp1 exp2 . . .)
    - List of variables is formal parameters
    - List of expressions is procedure body

    3.  

  3. A procedure is thus an object

    4.  

  4. Example: ( lambda (x) ( * x x ) )
    - What does it do?
    - What is its value? #<procedure>
    - How can we use it?

    5.  

  5. Example: ( ( lambda (x) ( * x x ) ) 5 )
    - What is its value?
    - This is a procedure application
    - An anonymous single-parameter procedure is defined then applied.
    - Actual parameter 5 is bound to formal parameter x.

    6.  

  6. Example: ( ( lambda (x y) ( * x y ) ) 5 6 )
    - What is its value?
    - Extends the previous example to two parameters

    7.  

  7. Example: (let ((square (lambda (x) ( * x x )))) ( square 5 ))
    - What is its value?
    - Binds procedure to let-variable     square, then applies it.

    8.  

  8. Example: 
    9. ( let ( ( square ( lambda (x) ( * x x ) ) ) ) 
   ( list ( square 4 ) ( square 5 ) )
)

     

  9. Consider scope of procedure and binding in Examples
    - limited to expression in which it is defined (nested)
    - use     define to make it global: top-level definition

    10.  

  10. Example: ( define square-all ( lambda (x) ( * x x ) ) )
    - can be shadowed (hidden) in inner scopes
    - can be applied anywhere that it is not shadowed
    - is retained by command interpreter so you can use it any time

 

 

 

; example to demonstrate Scheme binding in specific situation.
;
; Pete Sanderson 13 Oct 1997
;
; Situation is: Binding for x at procedure application differs
; from binding for x at procedure definition.
; Question is: Which one prevails?
 
( let ((x 2)) 
   ( let ((fun (lambda (y) (* x y)))) 
      ( let ((x 3)) 
         (fun 5)        ; apply procedure; which x?
      )
   )
)

 

 

Lambda expression formal parameters

 

  1. Proper list of variables
    - Value of argument bound to corresponding formal param.
    - Number of arguments must match number of formals
    - Example:     ( lambda (x y) . . .)

    2.  

  2. Single variable
    - Any/all arguments evaluated and values placed in list
    - List is bound to single formal parameter
    - Example:     ( lambda x . . .) ; provide 0 or more arguments

    3.  

  3. Improper (dotted) list of variables
    - Combination of the above
    - All variables except last: each argument matched to corresponding formal
    - Last variable: any/all remaining arg values put in list, bind list to formal
    - Example:     ( lambda (x y . z) . . .) ; provide 2 or more arguments

 

 

 

Conditional Expressions

 

  1. The if-then-else construct
  2. General form: ( if condition then-part else-part )
    -     if is keyword
    - condition is boolean expression
    - then-part is expression
    - else-part is expression

    3.  

  3. Analogous to C/C++ conditional expression
    - Example of the C long way:
    if (a > b)
    z = a;
    else
    z = b;
    - Equivalent C conditional expression: z = (a > b) ? a : b ;
    - Example:
    ( let ((x 4)) ( if ( < x 8 ) 1 0 ) )
    - What is its value?

    4.  

  4. Is if a procedure?
    - Note:     car, cdr, cons, list, +, -, *, / are all procedures
    - If so, its use represents procedure application
    - In a procedure     application, all arguments are evaluated prior to application.
    - Consider
    ( define safe-div
    (lambda (x y)
    (if (= y 0) "zero divide" (/ x y) ) ) )
    -     If a procedure, then all three args, (= y 0), "zero divide" and (/ x y), will be evaluated before procedure is applied! The if construct is a syntactic form.
  5. Consider: and, or, not -- procedures or syntactic forms?
    -     not is a procedure.
    -     And and or are syntactic forms,
    - Allows short-circuit evaluation
    - Any number of operands allowed (including none)
    - Final value is value of last expression evaluated!
    - Every object except     #f , and ( ) (non-ANSI), is considered true.
    - Example:     (and 1 0 2)
    - Example: (and (< 4 8))
    - Example: (and (< 4 8) (> 4 8) (= 3 3))
    - Example: (or (> 4 8) 6)
    - Example: (or (< 4 8) (> 4 8) 3)

    6.  

  6. Elsif capability using cond instead of if
    - Format is: ( cond (test then-part) (test elsif-part) . . . (else else-part) )

 

 

Recursion

 

  1. Direct and indirect recursion supported
  2. Recursion used for iteration
  3. Tail recursion compiled as iteration for runtime performance
  4. Use if to test for base case; recursion step is in then-part or else-part.
  5. Example: factorial, defined recursively: n! = n * (n-1)!
( define fact 
   (lambda (n) 
      (if (> n 0) (* n (fact (- n 1) ) ) 1 ) ) )

 

 

Begin expressions

 

  1. General Form: (begin expr1 expr2 . . .)
  2. Evaluates expressions from left to right in sequence
  3. Final value is value of last expression
  4. Is begin a procedure or a syntactic form?
  5. Forces sequential evaluation
  6. Example:
(begin (display "howdy") 
       (newline) 
       (display "doody") )

 

 

Assignment

 

  1. Rarely necessary
  2. Causes side effect
  3. Changes binding of existing variable (original binding from let or lambda)
  4. Format: (set! variable expression)

Example of acceptable use: 

; Count of procedure applications.
; Be aware that count initialized only once.
(define count 0)
 (define sigma
   (lambda (n)
      (set! count (+ count 1))
      (if (> n 0)
         (+ n (sigma (- n 1)))
         0)))

Example of acceptable use: 

; Maintenance of local state. 
; Note binding of next in procedure definition.
(define take_a_number
   (let ((next 0))
        (lambda ()
           (set! next (if (= next 99) 1 (+ next 1)))
           next
        )))