;;;; INTRODUCTION
;;; Why Scheme?
;;; Because it allows us to deal with:
;;; 1. Data Abstraction - it allows us to implement ADT (abstact data types)
;;; in a very special way. The issue of data abstraction is addressed in other
;;; languages: clusters in CLU, modules in MODULA, generics in ADA. But only
;;; SCHEME allows us to treat ADT as "first class objects." It allows us
;;; to pass them as parameters, return them as values, store them in data
;;; structures. We can deal with abstract objects in the same way we deal
;;; with integers.
;;; 2. Procedural Abstraction - the notion of procedural abstraction
;;; (functional form) is overlooked in most conventional languages.
;;; And those languages which utilize functional forms do not treat them
;;; as first class objects. For example, APL restricts us to about five
;;; functional forms introduced by Iverson in 1961. And a
;;; major goal of this course is to show that procedural abstaraction
;;; is the main tool for design of algorithms.
;;; Aplicative order
((lambda (x y) (* x (+ y 2))) 5 0)
;;; How does SCHEME evaluates an expression?
;;; 1. it checks whether a first element of an expression is a "special form"
;;; ("magic word").
;;; 2. if it is not (and in our case it isn't - our first element is not a
;;; word at all - it is an expression) all elements of the expression are
;;; evaluated in some unspecified order (could be in parallel).
;;; (2.1) If it is a special form, then SCHEME does a special thing.
;;; 3. Result of the evaluation of the first element (which better be a
;;; procedural object) is "applied" to the results of evalution of the rest
;;; of the elements.
;;; in our case 5 evaluates to 5, 0 evaluates to 0 (numbers are
;;; "self-evaluating" objects, actually, all atomic object, with the
;;; exeption of symbols, are self-evaluating), but how does
;;; SCHEME evaluate (lambda (x y) (* x (+ y 2)))?
;;; It looks at its first elmenent and finds that it is a special form
;;; "lambda". This special form creates a procedure with formal arguments
;;; x and y and procedure body (* x (+ y 2)).
;;; How does SCHEME applies a procedure?
;;; 1. Current "environment" is extended by "binding" formal arguments
;;; to actual arguments (in our case ((x 5) (y 0)))
;;; (in TI SCHEME we can actually see how it is done by changing our
;;; expression to
((lambda (x y)
(display (environment-bindings (the-environment)))
(* x (+ y 2)))
5
0)
;;; )
;;; 2. Evaluating the body of the procedure in the extended environment
;;; ...
;;; Global environment
;;; Global environment is an environment which containes all initial bindings
;;; (in TI SCHEME system bindings are in user-global-environment which is a
;;; parent of user-initial-environment in which user's global bindings are)
;;; define
;;; we can extend our global environment by typing
(define foo 88)
;;; which would add to it a binding (foo 88)
;;; is "define" a procedure or a special form?
;;; if it were a procedure it would get a value of "foo" and not "foo"
;;; and it would be impossible for it to create a binding (foo 88)
;;; define does not evaluate its first argument, but does evaluate
;;; its second argument.
;;; if we say
foo
;;; system will evaluate it and return the result
;;; now say
bar
;;; see what happens!
;;; now let us define a global function
(define square (lambda (x) (* x x)))
;;; there is a short hand for such defines; we can say
(define (square x) (* x x))
;;; (there is a subtle difference, however, which we shall see later)
;;; now, do
(square 2)
;;; now, we can do the following
(define bar square)
(bar 2)
;;; explain ...
;;; now we can define the most useful function which is going to be used
;;; throughout and which is not a part of standard SCHEME
(define (identity x) x)
;;; Free variables
;;; a variable in the body of a procedure is called "free" if it is not bound
;;; in this procedure
(lambda (x y) ((lambda (x y z) (+ x (* y z))) x y a))
;;; a is a free variable
;;; Lexical scoping
;;; Free variables are associated to a lexically apparent binding
;;; (to a binding which "textually" encloses the body)
;;Try the following
(define b 1)
((lambda (a b) (a 5)) (lambda (x) (+ x b)) 2)
;;; the second lambda has a free variable b which is associated with
;;; the global binding (b 1) even when it is called within the first
;;; lambda where b is bound to 2
;;; Indefinite (unlimited) extent
;;; all the objects in SCHEME, environment bindings including, live
;;; forever.
;;; It means that in some cases a binding in the environment of a procedure
;;; can be used after the procedure terminated
(define (make-add-a-constant c)
(lambda (x) (+ x c)))
(define one-plus (make-add-a-constant 1))
(define two-plus (make-add-a-constant 2))
(define seven-plus (make-add-a-constant 7))
;;; So we can define functions which make functions
;;; Actually, make-add-a-constant is just an instant of more general
;;; and more useful functions:
(define (bind-1-of-2 function constant)
(lambda (x) (function constant x)))
(define (bind-2-of-2 function constant)
(lambda (x) (function x constant)))
;;; that make a function of one variable out of a function of two
;;; Problem:
(define foo (bind-1-of-2 / 1))
;;; what does foo do?
;;; square can be defined with the help of a following function
(define (D-combinator function)
(lambda (x) (function x x)))
;;; (it was introduced by M. Schoenfinkel in 1924, 50 years before SCHEME)
(define square (D-combinator *))
;;; we also can make a function that composes two functions:
(define (compose f g)
(lambda (x) (f (g x))))
;;; and a function that takes two functions and returns a function that
;;; applies them to an argument sequentially
(define (S-combinator f g)
(lambda (x) (f x) (g x)))
;;; Problem 1.1:
;;; Define a function FUNCTIONAL-DIFFERENCE that takes two functions F(x)
;;; and G(x) as and returns a function W(x)=F(x)-G(x)
(define ((functional-difference f g) x)
(- (f x) (g x)))
;;; Problem 1.2:
;;; Define a function T-combinator that takes a function f(x y) and returns
;;; a function g(x y)=f(y x)
(define ((t-combinator f) x y)
(f y x))
;;; What is ((T-combinator -) 5 2)?
;;; Problem 1.3:
;;; What does the following function do:
(define foobar
((t-combinator functional-difference)
identity
(d-combinator *)))
;;; Conditonal
;;; The primitive conditional construct in Scheme is
;;; (if condition consequent alternative)
;;; the condition is evaluated and if it returns a true value (anything,
;;; but #!false or #!null) the consequent is evaluated and its value is
;;; returned, otherwise the alternative is evaluated and its value is
;;; returned
;;; if "if" does not have an alternative then the if expression is
;;; evaluated only for its effect and the result is not specified
;;; and we can define if-combinator
(define (if-combinator predicate f g)
(lambda (x) (if (predicate x) (f x) (g x))))
;;; Problem:
(define foo (if-combinator odd? 1+ identity))
;;; what does foo do?
;;; actually, it is also useful to have another combinator
(define (when-combinator predicate function)
(lambda (x) (if (predicate x) (function x))))
;;; it has two arguments: predicate P and function F, it returns a function
;;; that applies F only to those arguments that satisfy P.
;;; factorial example
;;; now we can implement factorial in a traditional recursive way
(define factorial
(lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
;;; while the program does work it is not quite "first class".
;;; its correctness depends on the global binding of "factorial"
;;; so if we do something like
(define new-factorial factorial)
(define factorial *)
;;; (new-factorial 5) is going to return 20 in stead of 120
;;; so what we want is to make a recursive functional object to be
;;; independant of its global name
;;; namely, we want to bind name factorial to the procedural object
;;; in the environment of this procedural object
;;; there is a special form "named-lambda"
;;; (named-lambda (name var1 ...) body)
;;; which does just that.
;;; it works just as lambda, but also binds a procedural object
;;; it returns to name in the environment of the procedural object
;;;and we can define factorial as:
(define factorial
(named-lambda (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
;;; now, the self-recursive reference is done through the local binding
;;; which cannot be affected by changing the global binding of factorial
;;; actually, if we defined factorial as
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
;;; it would have expanded into
(define factorial
(named-lambda (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
;;; Tail Recursion
;;; our definition of factorial has one problem:
;;; it pushes the stack
;;; the reason for that is that multiplication in the first call cannot
;;; be evaluated until the result of second call is returned and so on.
;;; but if we change our definition into
(define (factorial-loop i result n)
(if (> i n)
result
(factorial-loop (+ i 1) (* result i) n)))
;;; and
(define (factorial n)
(factorial-loop 1 1 n))
;;; SCHEME is not going to push the stack because there is no need
;;; to keep the environment ...
;;; actually, the better way to do this is by making factorial-loop
;;; local procedure in factorial:
(define (factorial n)
(define (factorial-loop i result)
(if (> i n)
result
(factorial-loop (+ i 1) (* result i))))
(factorial-loop 1 1))
;;; this kind of recursion is called tail-recursion and systems that
;;; do not push the stack for tail-recursive calls are called
;;; "properly tail recursive"
;;; SCHEME is properly tail recursive
;;; we can ask what are the conditions that allow us to find a
;;; tail recursive representation of a recursive function
;;; it is possible to prove that any primitive-recursive function
;;; has a tail recursive form
;;; in SCHEME we can construct the best possible proof of them all
;;; we can implement a function which does the transformation of
;;; a primitive-recursive function into a tail recursive form
;;; (we shall restrict ourselves to functions of one variable)
;;; first, we shall make a function that makes a primitive recursive
;;; function given a transformation and an initial value
(define (make-primitive-recursive transformation initial-value)
(named-lambda (function n)
(if (= n 0)
initial-value
(transformation n (function (- n 1))))))
;;; PROBLEM:
;;; define FACTORIAL with the help of MAKE-PRIMITIVE-RECURSIVE
;;; we can produce an equivalent iterative function with:
(define ((make-primitive-iterative transformation initial-value) n)
(define (loop variable result)
(if (= n variable)
result
(loop (+ variable 1) (transformation (+ variable 1) result))))
(loop 0 initial-value))
;;; in TI SCHEME not just functions, but environments are first class objects
;;; and we can extract transformation and initial value out of a functional
;;; object created with the help of make-primitive-recursive.
;;; That allows us to define a function:
(define (recursive->iterative function)
((lambda (environment)
(make-primitive-iterative
(access transformation environment)
(access initial-value environment)))
(procedure-environment function)))
;;; PROBLEM:
;;; with the help of MAKE-PRIMITIVE-RECURSIVE and MAKE-PRIMITIVE-ITERATIVE
;;; implement functions MAKE-ADD-SELECT(PREDICATE) and
;;; MAKE-ADD-SELECT-ITERATIVE(PREDICATE) so that they return a function
;;; defined on non-negative integers such that for any integer N it returns
;;; the sum of those integers less-or-equal to N that satisfy PREDICATE
;;; define ADD-ODD as (make-add-select odd?) and ADD-ODD-ITERATIVE
;;; as (make-add-select-iterative odd?);
;;; what is the smallest integer i on your system such that
;;; (add-odd i) bombs and (add-odd-iterative i) does not?
;;; Now, what if the value of a function on N depends not just on the value on
;;; F(N-1), but on F(N-1) and F(N-2)?
(define (make-two-recursive transformation value-0 value-1)
(named-lambda (function n)
(if (= n 0)
value-0
(if (= n 1)
value-1
(transformation n (function (- n 1)) (function (- n 2)))))))
;;; and the equivalent iterative function can be obtained with:
(define ((make-two-iterative transformation value-0 value-1) n)
(define (loop variable first second)
(if (= n variable)
first
(loop (1+ variable)
(transformation (1+ variable) first second)
first)))
(if (= n 0) value-0
(loop 1 value-1 value-0)))
(define (two-recursive->iterative function)
((lambda (environment)
(make-two-iterative
(access transformation environment)
(access value-0 environment)
(access value-1 environment)))
(procedure-environment function)))
;;; PROBLEM:
;;; define a function FIB(n) which returns n-th fibonacci number
;;; with the help of TWO-RECURSIVE.
;;; time (fib 20)
;;; transform fib into an iterative function with the help of
;;; TWO-RECURSIVE->ITERATIVE
;;; time (fib 20)