Building abstractions in Scheme 

(Spark, an implementation of Scheme was used to run the sample code).

Lambda Calculus 

Invented in the 1930s by Alonzo Church.

A form of mathematical logic dealing primarly with functions and the application of functions to their arguments. 

In pure lambda calculus, there are only lambda abstractions (which are simply specifications of functions), variables, and applications of functions to functions. 

A lambda abstraction is typically specified using a lambda expression, which might look like the following.

     λ x . x

The above specifies a function of one argument, that can be reduced by applying the function to its argument (function application is left-associative by default, and parentheses can be used to specify associativity).

A function with more that one argument is represented by:

       λ x .  λ y . x + y

It is often abreviated as:

       λ x y . x + y

Arguments can be the function itself. This gives rise to recursion:

       λ f . f

We can specify the Church integer 0 in lambda calculus as:

      0  =  λ z . z

and 3 as:

      3 =   λ f x . f ( f (f x) )

Suppose we have a function inc, which when given a string representing an integer, returns a new string representing the number following that integer. Then:

    3 inc 0 = 3

Addition of Church integers in lambda-calculus is:

add =  λ x y . ( λ f z . x f (y f z) )
add 2 3 =  λ f z . 2 f (3 f z)
        =  λ f z . 2 f ( f ( f (f z) ) )
        =  λ f z . f ( f ( f ( f (f z) ) ) )
        = 5

Truth values and conditionals:

    true =  λ x: y: x
    false =  λ x: y: y
    not =  λ t: t false true

It is easy to use the rules of -conversion to show that these de nitions have the
desired properties. For example:
                        not true = ( λ t: t false true) true
                                  = true false true               
                                  = ( λ x: y: x) false true    
                                  = ( λ y: false) true              
                                  = false                         
Similarly not false = true.

Pairs and tuples:

    fst =   λ p: p true
    snd =    λ p: p false
    (E1  E2 ) =  λ f: f E1 E2

fst (E1 E2) = ( λ p: p true) (E1 E2)
            = (E1 E2 ) true
            = ( λ f: f E1 E2 ) true
            = true E1 E2
            = ( λ x y: x) E1 E2
            = E1 

Lisp

Designed in the late 1950s by John McCarthy. 

Based on Lambda Calculus.

A family of languages.

Most popular of these are Common Lisp and Scheme.

Spark is an implementation of Scheme based on MzScheme.

Procedures 

e.g: (+ 3 4 5 6)

Expressions such as these, formed by delimiting a list of expressions within parentheses in order to denote procedure application, are called ''combinations''. 

The leftmost element in the list is called the ''operator'', and the other elements are called ''operands''. 

The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.

The convention of placing the operator to the left of the operands is known as ''prefix'' notation.  

Prefix notation has several advantages. One of them is that it can accommodate procedures that may take an arbitrary number of arguments.

''define'' is the simplest means of abstraction provided by Scheme. 

It allows us to name objects as well as complex computations using them.

Keep in mind that the usual evaluation rules does not apply to ''define''. It is a ''special form''.

Scheme has few such special forms, each with its own evaluation rules.

e.g: 

(define a 10)

(define (add a b) (+ a b))

Note the special form used for defining procedures.

They are called ''compound procedures''. 

A compound procedure can be invoked just the way you invoke a primitive procedure. 

They can also be used in defining other compound procedures.

It should be clear that the possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the ''environment'' (more precisely the ''global environment'').

 
A formal parameter of a procedure has a very special role in the procedure definition, in that it doesn't matter what name the formal parameter has. 

Such a name is called a bound variable, and we say that the procedure definition binds its formal parameters. 

The meaning of a procedure definition is unchanged if a bound variable is consistently renamed throughout the definition.

If a variable is not bound, we say that it is free.

The set of expressions for which a binding defines a name is called the scope of that name. In a procedure definition, the bound variables declared as the formal parameters of the procedure have the body of the procedure as their scope. 

This discipline is called ''Lexical Scoping''.

Recursion and Iteration.

In this section we will examine some common ``shapes'' for processes generated by simple procedures.

We will also investigate the rates at which these processes consume the important computational resources of time and space. 

Look at this procedure:

(define (factorial n)
   (if (= n 1)

      1
      (* n (factorial (- n 1)))))


Now will look at a different way to compute factorials:

(define (factorial n)
   (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (* counter product)
                   (+ counter 1)
                   max-count)))

Consider the first process. The substitution model reveals a shape of expansion followed by contraction.
The expansion occurs as the process builds up a chain of deferred operations (in this case, a chain of multiplications). 

The contraction occurs as the operations are actually performed.
This type of process, characterized by a chain of deferred operations, is called a recursive process.
Carrying out this process requires that the interpreter keep track of the operations to be performed later on.
In the computation of n!, the length of the chain of deferred multiplications,
and hence the amount of information needed to keep track of it, grows linearly with n (is proportional to n),
just like the number of steps. Such a process is called a ''linear recursive process''.

By contrast, the second process does not grow and shrink.
At each step, all we need to keep track of, for any n, are the current values of the variables product, counter, and max-count.
We call this an iterative process.
In general, an iterative process is one whose state can be summarized by a fixed number of state variables,
together with a fixed rule that describes how the state variables should be updated as the process moves
from state to state and an (optional) end test that specifies conditions under which the process should terminate.
In computing n!, the number of steps required grows linearly with n. Such a process is called a ''linear iterative process''.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages
(including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure
consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative.
As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs''
such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect.
It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure.
An implementation with this property is called ''tail recursive''.With a tail-recursive implementation,
iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.
To make your life a little bit easier, Spark does give you such syntact extentions.

Higher-Order procedures

Consider the following three procedures. The first computes the sum of the integers from a through b:

(define (sum-integers a b)
    (if (> a b)
       0
       (+ a (sum-integers (+ a 1) b))))

The second computes the sum of the cubes of the integers in the given range:

(define (sum-cubes a b)
    (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))

These two procedures clearly share a common underlying pattern. 

They are for the most part identical, differing only in the name of the procedure, the function of a used to compute the term to be added,
and the function that provides the next value of a.
We could generate each of the procedures by filling in slots in the same template:

(define (<name> a b)
    (if (> a b)
      0
      (+ (<term> a)
         (<name> (<next> a) b))))

The presence of such a common pattern is strong evidence that there is a useful abstraction waiting to be brought to the surface.
 We can do so readily in our procedural language by taking the common template shown above and transforming the ``slots'' into formal parameters:

(define (sum term a next b)
    (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

Notice that sum takes as its arguments the lower and upper bounds a and b together with the procedures term and next.
We can use sum just as we would any procedure.
For example, we can use it (along with a procedure inc that increments its argument by 1) to define sum-cubes:

(define (sum-cubes a b)
    (sum cube a add1 b))

Using this, we can compute the sum of the cubes of the integers from 1 to 10:

(sum-cubes 1 10)
3025

With the aid of an identity procedure to compute the term, we can define sum-integers in terms of
sum:

(define (identity x) x)

(define (sum-integers a b)

(sum identity a inc b))

Then we can add up the integers from 1 to 10:

(sum-integers 1 10)
55


lambda

It seems terribly awkward to have to define trivial procedures such as identity just so we can use them as arguments to our higher-order procedure.
It would be more convenient to have a way to directly specify ``the procedure that returns its input''.
We can do this by introducing the special form lambda, which creates procedures.

Using lambda we can describe what we want as

(lambda (x) x)

In general, lambda is used to create procedures in the same way as define, except that no name is
specified for the procedure:

(lambda (<formal-parameters>) <body>)

The resulting procedure is just as much a procedure as one that is created using define.
The only difference is that it has not been associated with any name in the environment. In fact,

(define (plus4 x) (+ x 4))

is equivalent to

(define plus4 (lambda (x) (+ x 4)))

We can read a lambda expression as follows:
(lambda (x) (+ x 4))

the procedure of an argument x that adds x and 4
Like any expression that has a procedure as its value, a lambda expression can be used as the operator in a combination such as

((lambda (x y z) (+ x y (square z))) 1 2 3)
12

or, more generally, in any context where we would normally use a procedure name.

Another use of lambda is in creating local variables. We often need local variables in our procedures other than those that have been bound as formal parameters. In writing a procedure to compute f, we would like to include as local variables not only x and y but also the names of intermediate quantities like a and b. One way to accomplish this is to use an auxiliary procedure to bind the local variables:

(define (f x y)
    (define (f-helper a b)
       (+ (* x (square a))
       (* y b)
(* a b)))
(f-helper (+ 1 (* x y))
(- 1 y)))
Of course, we could use a lambda expression to specify an anonymous procedure for binding our local variables. The body of f then becomes a single call to that procedure:

(define (f x y)
    ((lambda (a b)
      (+ (* x (square a))
      (* y b)
      (* a b)))
      (+ 1 (* x y))
      (- 1 y)))

This construct is so useful that there is a special form called ''let'' to make its use more convenient. Using ''let'', the f procedure could be written as

(define (f x y)
    (let ((a (+ 1 (* x y)))
     (b (- 1 y)))
     (+ (* x (square a))
     (* y b)
     (* a b))))

Data abstractions

Scheme provides certain primitive procedures that enable us to "glue" together values to create compound data.

cons is used to create a pair:

(define point (cons 10 20))

car and cdr are used to extract the first and second values from the pair:

(car point) -> 10

(cdr point) -> 20

Lists can be created by embedding pairs:

(cons 1 (cons 2 (cons 3 null))) -> (1 2 3)

This can be shortened using the list procedure:

(list 1 2 3) -> (1 2 3) 

Closures

A procedure is evaluated in a new environment.

It's arguments and all local variables are temporarily bound in this environment.

This environment holds a pointer to the global environment.

The environment created by any embedded procedure in-turn holds a pointer back to the parent procedure's environment.

This prevents the environment from being garbage collected, and creates state for the procedure.

e.g:

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
    ((= m 1) y)
    (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)

(define (car z) (z 0))

(define (cdr z) (z 1))

Using symbols the above example can be refactored to make use of messages:

(define (cons x y)
  (define (dispatch m)
    (case m

    ((first) x)
    ((second) y)
    (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)

(define point (cons 10 20))

(point 'first) -> 10
(point 'second) ->20

Closures, higher-order functions and extreme late binding render polymorphism and most of the popular OOP patterns strainghforward and simple in Scheme:

(define (cat-speak)
(printf "Meow!~n"))

(define (dog-speak)
(printf "Woof!~n"))

(define pets (list cat-speak dog-speak))
(for-each (lambda (p) (p)) pets)