Lecture 6: The Full Language, Nothing but the Full Language, and Only the Full Language

###
Lecture 6: The Full Language, Nothing but the Full Language, and Only the Full Language

1. We emersed you in some fragment of the Scheme programming language. If your goal is to get through this course or to find out what computing is about but nothing else, this fragment will serve you just fine. If, however, you find it fun to get things done easily on a computer (say CGI scripting, Web-paged building, systems admin, ...), you might wish to find out more about the language. (All of the Web pages are generated with MzScheme scripts, plus some borrowed software.)

2. A language consists of three pieces:
   - vocabulary : all the words
   - grammar : how to form sentences
   - meaning : how to determine the meaning of sentences
     and to distinguish meaningful sentences from meaningless ones
3. The vocabulary of Scheme:

        (
        )
        i-am-a-name
        i-am!
        define cond
        ! @ % ^ & * +
        888

4. The grammar of Scheme:

       program =
         (define (function-name variable-name ...) expression)
         ...
         (define variable-name expression)
         ...
         expression

       expression =
         |  variable-name
         |  constants
         |  (primitive-operation expression ... )
         |  (function-name expression ... )
         |  (cond
       	(expression expression)
       	...
               (expression expression))
         |  (cond
       	(expression expression)
       	...
               (else expression))

       constants =
         | 0 | +1 | -1 | ...
         | #t | #f
         | 'hello | 'world
         | empty

       variable-name = name
       function-name = name
       name = x | f | ! | @ | ...

   All red things are what we write down. Let's practice with this grammar. It's an extremely simple game -- match patterns.

       !
       (! 10)
       (define (! n) n)
       (cond (test 'hello))
       (cond (else 10))

   Grammatical mistakes:

       (define (f x) + x y z)

       (cond)

       (define (f test)
         (cond
           ((test) 10)
           (else 0)))

   Why are these grammatical mistakes? Computing scientists call them syntactic mistakes.

   names for pieces of "sentences"

5. The Meaning of Scheme: the goal is to produce a program whose expression we can reduce (equate to, calculate to) a value.

   In Scheme without lists, we can safely say numbers and symbols are values. Right?

   the "grade school" laws:

       (+ 1 1) = 2
       (/ 4 2) = 2
       (* 2 1) = 2
       (- 4 2) = 2

       (eq? 'x 'x) = #t
       (not #f) = #t

   the "middle school" laws:

       (define (f x)
         expression)

       ...

       (f V) =  expression with all x replaced by V

   An example with two variables ...

   And now to the algebra of information:

       for any value I and list L,
         (first (cons I L)) = I
         (rest (cons I L)) = L

   But what are values:

       value =
           0 | +1 | -1 | ...
         | #t | #f
         | 'hello | 'world
         | empty
         | list

       list =
           empty
         | (cons value list)

   All constants are values. And lists are values.

   Some strange examples

       (cons (cons 1 (cons 2 empty)) empty)

   How many items are in this list?

Matthias Felleisen | This page was generated on Fri Mar 5 09:04:41 CST 1999.