Alternative xreal Implementation: Binary Rational Intervals:

      - As mentioned in a previous lecture, the implementations of exact
        reals use so far are inefficient in the following ways:

	- Inefficiencies in precfunc:

	1) The generation of rational interval values that have very
	   large numerator and denominator, when there is a much simpler
           rational in the interval to use.

	2) Repeated computation of the same operation.


        - Inefficiencies in wordstream:

	1) (for small bases) full-word machine operation used to
           determine only a couple bits.  (This should be a pretty huge
           time waster.)

        2) (for large bases) a very high granularity of precision

      - An alternative is found in the use of binary rational intervals,
        which are treated in both papers on exact real arithmetic handed
        out.  Such an interval is

	[(m-1)2^n, (m+1)2^n]

	This interval can be represented by the pair (m,n).  It has
	width 2^(n+1) and midpoint m*2^n.  

	If we fix n, we get the following midpoints/intervals:

	Intervals__[        ] [         ] [         ] [        ] ... m = odd
		 \_     [         ] [         ] [         ]      ... m = even
	Midpoints	     *     *     *     *     *   ....
			    2^n  2*2^n 3*2^n 4*2^n 5*2^n ....

	An xreal implemented with a binary rational interval, then, is a
	function from n to m such that x is in [(m-1)2^n,(m+1)2^n].

The Frame/State/Environment Model:

      - Consider the following model to represent an environment:

	    / symbols        environment/state
	X = | names        -------------------->  values
	    | variables
	    \ parameters

	The environment here is a function that maps things in X to
	their associated values.  However, once you start using things
	like set!, set-cdr! etc. in this model, things break down, since
	you can't guarantee proper binding between names and variables
	has been done.

      - To solve the problem, we adopt a refined model:

		 environment		       state
        symbols ------------->  l-values   ------------->  values
	names      (bind)	variables      assign
				addresses/
				pointers
				locations

				
	For example, in (lambda (x) (lambda (y) ..., we have the symbol
	lambda twice, but it can be bound differently in each instance
	since we isolate that step in the environment part.  The first
	model above, then, is a composition of the new environment and
	state, but, in doing so we lose intermediate information, which
	is vital to proper bookkeeping.

	Binding is associating symbol -> variable.
	Assigning is associating variable -> value.

	The environment (binding) step is the place of most activity in
	functional programming languages, while the state (assign) step
	is the main realm of activity for procedural languages.

      - To understand environments with nested scopes (such as the
        nested lambda example), we need to understand the environment
        step's structure a little better.  An environment is given by a
        sequence of frames.

	A FRAME is a finite fragment of the environment plus a pointer
	to a parent environment.  

	A sequence of frames, then, represents the environment by
	mapping the name x according to the first appearance of x in a
	frame that is part of the sequence.

	Frames can only be added or removed, not edited.  Also the
	sequence is stored in a stack structure (LIFO).

	Environment schematic:

	   TOP
	|Frame n|        |Frame n-1|        
	|	|	 |	   |
	|x: ...	|------->|x: ...   |-------> ...  BOTTOM
	|y: ...	|	 |w: ...   |
	|z: ... |        |         |

	Multiple stacks are also possible.  In Scheme, a new stack can
	be started off from a certain point in an already existing
	stack, which proves to be a useful optimization.

      - The following are examples of how the frame structure is put into
        action:

	(lambda (x) body)  - builds a procedure encoding the body in an
			     environment that includes a frame for 'x


	(fn a1 ... an)     - creates a new frame that binds names involved
			     in function to new variables
			   - assigns values of a1 ... an to new
			     variables
			   - evaluates function body in environment with
			     our new frame of the top of the stack and
			     the current environment frames below
			   - After evaluation, throw away new frame to
			     get back the previous environment stack.

      - Now consider the following set actions under this system:

	(set! name value) 

	If name is not bound, then it is an error..
	Assign a value to the variable that is already bound to name.


	(define name value)

	If name is not bound, add it to the current LOCAL frame with binding
	to the new variable, then assign value to it.