CS217 Day 1 Monday, March 27, 2000

We will be studying programming languages using the programming language Scheme as a tool. Issues include

• Data types supported by a language.
• Declaration and scope of variables.
• Declaration and scope of procedures.
• Procedure application
• Control structures
• Syntax for programs, expressions, data
• Object oriented languages (OOL)
• Type systems

Scheme is a dialect of Lisp, but it's block structure and lexical scope make it a descendent of Algol, along with Pascal and Ada.

We will use Scheme to study the meaning of programming language constructs by building interpreters to implement them.
We will be writing Scheme programs that operate on defined programs.

The meaning of programs in a defined language will be defined relative to the meaning of programs in Scheme.

Therefore we need to learn the syntax and semantics of Scheme and become proficient in its use.

Data types in Scheme include

• Numbers (integer, rational, floating point, both real and complex)
• Strings, e.g. "Hi"
• Symbols, e.g. 'hi
• Characters, e.g. #\h, #\i
• Boolean -- #t, #f
• Empty list -- ()
• Pairs -- (a . b), where a, b are Scheme data
• Lists -- (a0 ...) where a0, ... are Scheme data
  Lists are represented in terms of pairs and the empty list
  

      (a0 a1 ...) = (a0 . (a1 ...))
  

• Vectors -- #(a0 ...) where a0, ... are Scheme data

BNF (Backus-Naur Form) specification of Scheme data:

[x] -- the syntactic category x. (Angle brackets don't show in HTML.)
| -- alternative
::= -- can be
{...}^* -- zero or more of ...
{...}⁺ -- one or more of ...
Other symbols are terminal symbols

    [list]         ::=  () | ([datum] . [list])
    [dotted-datum] ::= ([datum] . [datum])
or
    [list]         ::= ({[datum]}*)
    [dotted-datum] ::= ({[datum]}+ . [datum])

    [vector]       ::= #({[datum]}*)
    [datum]        ::= [number] | [symbol] | [boolean] | [string]
                     | [list] | [dotted-datum] | [vector]

There are many procedures for manipulating, constructing, recognizing, converting Scheme data.
E.g.

    (+ e0 ...) => the sum of the (numerical) values of e0, ...
    (* e0 ...) => the product of the values of e0, ...

    (number? e0) => #t if e0 evaluates to a number, otherwise #f
    (symbol? e0) => #t if e0 evaluates to a symbol, otherwise #f

    (car '(a . b)) => a
    (cdr '(a . b)) => b
    (cons e f) => (a . b), where e => a and f => b

    (caar '((a . b) . c)) => a
    (cdar '((a . b) . c)) => b
    (cadr '(a . (b . c))) => b
    (cddr '(a . (b . c))) => c

    (list e0 ...) => (a0 ...), where ei => ai
    (vector e0 ...) => #(a0 ...), where ei => ai

    (list->vector '(a0 ...)) => #(a0 ...)
    (vector->list #(a0 ...)) => (a0 ...)

    (list-ref '(a0 ...) i) => ai
    (vector-ref #(a0 ...) i) => ai

    (set-car! '(a . b) e) replaces a with the value of e
    (set-cdr! '(a . b) e) replaces b with the value of e
    (vector-set! #(a0 ...) i e) replaces ai with the value of e

Expressions in Scheme include

• literals -- numbers, strings, characters, booleans

• variable references -- symbols with defined values
  E.g., + => #[procedure +]

• applications
  (a0 a1 ...) => the (procedure) value of a0 applied to the values of a1, ...., where a0 is not a special form.
  a0, a1, ..., are first (recursively) evaluated in some order, and then the procedure call is evaluated.
  E.g., (exp (* 4 (atan 1) 0+i)) => -1.0+1.2246063538223773e-16i .
  Note: e^{pi i} = -1.
  

  Special forms include: lambda, quote, define, if, let, letrec, cond, case, begin, and, or, set!

• lambda expressions, whose values are procedures
  (lambda (var1 ...) exp) => a procedure with parameters var1 ...

      ((lambda (var1 ...) exp) e1 ..)
  =>
      the value of exp with free occurrences of var0, ... replaced
      by the values of e1, ...
  

  (lambda vars exp) => procedure with 0 or more parameters

      ((lambda vars exp) a0 ...)
  =>
      the value of exp with free occurrences of vars replaced by
      a list of the values of a0, ...
  

• quoted expressions
  (quote exp) => exp (itself, unevaluated)
  Also written, for short, 'exp
  E.g.,

  (quote x) => x
  (quote (a 2 c)) => (a b c)
  '() => ()
  

  Enables symbols and lists to be regarded as data, rather than expressions to be evaluated.

• define
  (define var exp) causes the value of exp to be bound to var.
  Adds definitions of variables to the global environment.
  Any symbol can be redefined! E.g.

  (define old+ +)
  (define old* *)
  (define + old*)
  (define * old+)
  (+ (* 2 3) (* 4 5)) => 49
  

• if expressions
  

      (if e0 e1 e2)
  =>
      the value of e1 if the value of e0 is not #f,
      or the value of e2 if the value of e0 is #f
  

• let expressions can declare and use local variables
  

      (let ((v1 e1) ...) exp)
  =>
      the value of exp with free occurences of v1, ... in exp
      replaced by the values of e1, ...  Previous values are shadowed.
  
      -- the same as the value of ((lambda (v1 ...) exp) e0 ...)
  

  v1, ... are local variables in the evaluation of exp.

• letrec expressions can declare and use local recursive procedures
  

      (letrec ((v1 e1) ...) exp)
  =>
      like let, except occurrences of v1, ...in e1, ...
      are bound to the values of e1, ..., making v1, ... recursive.
      e1, ... are ordinarily lambda expressions
  

• cond expressions
  

      (cond (b1 e1) (b2 e2) ... (else e))
  =>
      the value of ei if bi is the first of b1, b2 ... with value #t
      or the value of e of all of b1, b2, ... evaluate to #f
  

• case expressions
  

      (case exp
        ((v11 v12 ...) e1)
        ((v21 v22 ...) e2)
        ...
        (else e))
  =>
      the value of ei if the value of exp is an integer or symbol
      among vi1, vi2, ..., otherwise the value of e.
  

• begin expressions
  

    (begin e1 e2 ...) => the value of the last ei
                         after evaluating e1, e2,... in order,
  
                         ignoring all values except the last
  
  

  All but the last are evaluated only for side effect.

• and expressions

    (and) => #f
    (and a1) => a1
    (and a1 a2 ...) => (if a1
                           (and a2 ...)
                           #f)
  

  Returns the value of the last arg or #f if some arg evaluates to #f.

• or expressions

    (or) => #f
    (or a1 a2 ...) => (let ((v a1))
                        (if (not (eqv v) #f)
                            a1
                            (or a2 ...)))
  

  Returns the value of the first arg whose value is not #f, or #f.

• -- to change the value of a variable

    (set! var exp) => no value, but replaces the value of var
                      with the value of exp
  

Two expecially expecially useful procedures: map and apply.

    (map p (e1 ...))
=>
    (list (p e1) ...)
    a list of the values of p applied to e1, ...


    (map p (e1 ...) (f1 ...))
=>
    (list (p e1 f1) ...)
    a list of the values of a two arg procedure p

    (apply p (a1 ...))
=>
    (p a1 ...)
    the value of p applied to a1, ...

E.g.

    (map (lambda (x) (* x x)) '(1 2 3)) => (1 3 9)
    (map + '(1 2 3) '(10 20 30) '(100 200 300)) => (111 222 333)

    (map car '((a 1) (b 2) (c 3))) => (a b c)
    (map cdr '((a 1) (b 2) (c 3))) => ((1) (2) (3))
    (map cadr '((a 1) (b 2) (c 3))) => (1 2 3)
    (map cons '(a b c) '(1 2 3)) => ((a 1) (b 2) (c 3))

    (apply + '(1 2 3) => 6
    (apply (lambda (x y z) (cons z (list y x))) '(1 2 3) => (3 2 1)

    (apply + (map + '(1 2 3) '(10 20 30))) => 66

    (apply car '(a b c)) => a
    (apply cdr '(a b c)) => (b c)
    (apply cons '(a b)) => (a . b)

Example definitions

-- A procedure that appends two lists

    (define append
      (lambda (lst1 lst2)
        (if (null? lst1)
            lst2
            (cons (car lst1) (append (cdr lst1) lst2)))))

-- Procedures that reverse the members of a list.

    (define reverse1
      (lambda (lst)
        (if (null? lst)
            '()
            (append (reverse1 (cdr lst)) (list (car lst))))))

    (define reverse2
      (lambda (lst)
        (letrec ((rev-helper (lambda (lst1 lst2)
                               (if (null? lst1)
                                   lst2
                                   (rev-helper
                                     (cdr lst1)
                                     (cons (car lst1) lst2))))))
          (rev-helper lst '()))))

Running Scheme within Emacs

• Start emacs
• ESC x run-scheme
• C-x 2
• C-x C-f myfile.scm
• Write definitions
• Evaluate one at a time with C-c C-e
  or all at once with C-x h C-c C-r (or use Scheme menu)
• C-x o switches visible buffers or click in buffer
• Evaluate expressions directly in *scheme* buffer or from myfile.scm

Read TSPL Ch2 and EOPL 1.1. Start work on Assignment 1.