;;;; 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)