Functional Programming
3. A Simple Subset of Scheme

3.1 Scheme

Scheme is a language developed by Guy L. Steele and Gerald Jay Sussman of MIT over the (1975-1980) period (See History of the Scheme programming language). It was influenced by Lisp, the premier AI language of the time.

The standard text for Scheme is The Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman. For years it was the introductory programming text for MIT and many other top CS schools.

Scheme has evolved into the Racket family of languages, which is what we are using for this course.

3.2 Restricted Scheme

We now define a restricted subset of Scheme that is a rough analog of the untyped lambda calculus (to be discussed later). The reason for doing this is that we want to force ourselves to understand the low-level nature of the language, and then implement the features that are used in regular programming. We will use the full Scheme/Racket language later.

Restricted Scheme consists of exactly the following permitted terms. In the definitons below, In restricted Scheme you have only the following programming constructs:

3.3 Some Illustrative Examples

Try these inside the Scheme environment, observe what happens, and make sure you understand why. It cannot be stressed too much: it is important to actually sit down and experiment with the language. code/LambdaScheme/LambdaScheme01.rkt

    #lang racket
    ; Integers:
    (quotient 9 4)
    (remainder 9 4)
    (modulo 9 5)
    (modulo 9 -4)
    (modulo -9 5)
    (modulo -9 -4)
    (= 2 3)
    (not (= 2 3))
    (< 3 4)
    ; Lists:
    (define L '(1 2 3))
    (first L)
    (car L)
    (rest L)
    (cdr L)
    (first (rest L))
    (car (cdr L))
    (cadr L)
    (cons (first L) (rest L))
    (cons 42 L)
    (cons L L)
    (cons 1 1)
    (cons 1 (cons 2 (cons 3 '())))
    (cons (cons (cons (cons 1 '()) '()) '()) '())
    (list? L)
    (null? L)
    (null? (rest '(2)))
    (list? 1)
    (null? 1)
    (define LL '( (1 2 3) (4 5 6 (7 8) )))
    (car (car LL))
    (caar LL)
    (car (cdr LL))
    (cadr LL)
    (car (cdr (cdr LL)))
    (caddr LL)
    (cdr (cdr (car (cdr LL))))
    (cddadr LL)
    (car (cdr (cdr (car (cdr LL)))))
    (caddadr LL)
    ; If you want the list consisting of the value of a and the value of b, then you
    ; need to assemble it.  So you start with the empty list 
    ; (this is a constant, so has a quote).  Then you use the inductive definition 
    ; of list, and build the list containing b, by doing 
    (cons b '()) 
    ; finally you add a to the front, by doing 
    (cons a (cons b '()))
    ; Definition and Quotation:
    (quote 1)
    (quote ())
    (define X (+ 1 2))
    (define Y '(+ 1 2))
    (eval Y)
    ; Abstraction:
    ; the constant function of no arguments
    (define f1 (lambda () 42))
    ; the unary function that doubles its argument
    (define f2 (lambda (x) (+ x x)))
    (f2 3)
    ; the identity function
    (define ident (lambda (x) x))
    (ident 42)
    ; the function that builds a list around its argument
    (define list1 (lambda (x) (cons x '()) ) )
    (list1 3)
    ; a binary function that does addition
    (define add (lambda (x y) (+ x y)))
    (add 40 2)
    ; Scheme doesn't do Currying automatically
    (add 40)
    ; (addn n) builds a function that adds n to it's argument
    (define addn (lambda (n) (lambda (x) (+ x n))))
    (addn 3)
    (define plus3 (addn 3))
    (plus3 40)
    ; Conditionals and Recursion:
    ; in an imperative language, we would do something like this to
    ; find the min of a list
    ; def lmin(L):
    ;   min_val = None
    ;   for x in L:
    ;       if min_val is None or x < min_val:
    ;           min_val = x
    ;   return min_val
    ; functionally, we do it like this
    ; try tracing it in DrRacket
    (define lmin (lambda (L) 
        (if (null? (rest L)) 
            (first L) 
            (min (first L) (lmin (rest L)))
    (lmin '(1 -3 4))
    ; sum over a list: note the base case, and induction/recursion
    (define lsum (lambda (L)
        (if (null? L)
            (+ (first L) (lsum (rest L)))
    (lsum '(1 -3 4))
    ; Evaluation
    (quote (+ 3 4))
    (eval (quote (+ 3 4))
    (define exp (cons (lambda (x) (+ x x)) '(3)))
    (eval exp)

3.4 Scheme Naming Conventions

Every language has it's conventions for naming. The Scheme ones are a bit richer since identifiers can contain special characters. These conventions are taken from the Scheme r6rs document (part of the plt DrScheme distribution).

By convention, the names of procedures that store values into previously allocated locations end in ! (bang or exclamation). For example, update-previous!. Note, we do not permit this operation in our restricted Scheme subset.

Procedures that convert between types usually contain -> in their name, separating the source and destinations. For example list->string and char->integer.

The names of predicates that always return a boolean value end in ? when the name contains any letters (such as converged?). If no letters, then the predicate looks more like a standard comparison operation (like <=) and no question mark is necessary.

By convention, the components of compound names are separated by dashes - (not underscore _). In particular, prefixes that are actual words or can be pronounced as though they were actual words are followed by a hyphen, except when the first character following the hyphen would be something other than a letter, in which case the hyphen is omitted. Short, unpronounceable prefixes (like fn, fop) are not followed by a hyphen.

3.5 Iterated Function Composition

Here is an example of a function composition operator that takes a function and applies it a specified number of times to the input argument. Functions that take other functions as arguments are often called operators.

Aside from the obvious use of doing compositions like repeated squarings, the compose operator can be used to implement any iteration one generally associates with a for loop. One can think of the loop body as a state transition function that is applied to the current state of the loop and delivers the next state of the loop. You start the loop with an initial state, and each iteration is a composition.

Important Note: Converting a loop into an iterated composition is a last-resort technique. There is almost always a "better, more functional" way to construct your solution. an equivalent

The function sum-of-n below implements a "loop" that sums up the first n integers.


    #lang racket
    ; suppose that we want to compose a function fn with itself n times
    ; applying it to argument x.  
    ; For example, function g composed 3 times on argument y is 
    ; g(g(g(y))) (in normal math notation), or
    ; (g (g (g y))) as a Scheme expression
    ; Function g composed 0 times on y is just y.
    (define fcompose (lambda (fn n x) 
        (if (<= n 0) 
            ; base case, the identity function, just return x
            ; recursion, compute one application and then send it
            ; to n-1 applications
            ; note that fcompose is in tail-recursive position, so 
            ; this code is run as a loop with constant stack space
            ; watch how the stack grows if instead this non-tail recursive
            ; formulation is used: (fn (fcompose fn (-n 1) x))
            (fcompose fn (- n 1) (fn x))
    ; compute powers of two
    (define times2 (lambda (x) (* 2 x)))
    (fcompose times2 5 1)
    (fcompose times2 0 1)
    (define power2 (lambda (x) (fcompose times2 x 1)))
    (power2 4)
    (power2 0)
    ; compute y ^ n
    (define yexpn (lambda (y n) 
        (fcompose (lambda (p) (* y p)) n 1)
    (yexpn 2 5)
    (yexpn 5 3)
    ; sum up the first n integers 1, 2, ..., n
    ; we keep a state consisting of a list (sum i) of two elements
    ; where sum is the sum so far, and i is the next element of the 
    ; sequence.
    ; This corresponds to a loop body that looks something like this:
    ;     sum = sum + i
    ;     i = i + 1
    ; making lists with cons car and cdr is really annoying to read
    (define loop-body-ugly (lambda (state) 
        ; new state is updated sum and next i.  Create a 2 element list
        (cons (+ (car state) (cadr state))
            (cons (+ 1 (cadr state)) '() ))
    ; which is why first, second, third, fourth are defined
    ; and there is a list function which takes an arbitrary number of 
    ; arguments and wraps them into a list
    (define loop-body (lambda (state) 
        ; new state is updated sum and next i.  Create a 2 element list
              (+ (first state) (second state))
              (+ 1 (second state)))
    ; run the loop 10 times, starting with initial state sum=0 i=1
    (fcompose loop-body 10 '(0 1))
    ; a function to run the loop n times, starting with initial state sum=0 i=1
    ; this is exactly the loop
    ; sum = 0
    ; i = 1
    ; for (index = 0; index < n; index++) {
    ;     sum = sum + i
    ;     i = i + 1
    ;     }
    (define sum-of-n (lambda (n)
        (first (fcompose loop-body n '(0 1)))
    (sum-of-n 10)
    (sum-of-n 0)
    (sum-of-n 3)

3. A Simple Subset of Scheme
Notes on Functional Programming / Version 2.10 2014-02-24