======================  Henderson/Changes.txt  ======================



This is the starting point of this package. 

First SECD machine is called "Henderson" 

It is an implementation of the original SECD machine from
the excellent book of P. Henderson "Functional Programming: 
Application and Implementation", 1980, Prentice Hall. 


No Garbage Collector, only selfcompiler works.

Machine is implemented in FreePascal (www.freepascal.org).

Root program   : self.pp

Compiler source: compiler.lisp
Compiler code  : compiler.secd 

------------------------------------------------------------

Next machine is Mini_0


======================  Mini_0/Changes.txt  ======================



This machine inherits Henderson.


-------------------------------------------

Original Henderson compiler uses only one
arithmetic construction - (ADD (QUOTE 1) x).

1. All arithemtic codes are removed from SECD,
   INC code is added:

   INC

   (x s) e c d  --> (x+1 s) e c d

2. INTEGER predicate is added.

3. Compiler is chaged to understand expressions like this:

   7     instead of    (quote 7)
   nil   instead of    (quote nil)

4. All text of compiler.lisp and compiler.secd are changed
   from uppercase to lowercase leters.

-------------------------------------------

The next machine is Mini_1.


======================  Mini_1/Changes.txt  ======================

This Machine inherits Mini_0.

---------------------------------

Changes:

1. AP, RAP and RTN are simplified - they don't touch S register.

2. SEL is modified to push E register (partial unification with AP/RAP).

3. JOIN is modified to restore E register (unification with RTN).

4. In the compiler.lisp JOIN codes are changed with RTN.

5. JOIN is removed from the SECD. 

6. SECD command codes are rearanged for TailRecursion purposes.
   Corresponding changes in compiler are done.

   INC from 16 to  9.
   APP from  4 to 15.
   SEL from  8 to 19.
   INT from 17 to  8.
   RAP from  7 to 17.

----------------------------------

The next machine is TR_SECD.



======================  TR_SECD/Changes.txt  ======================

This Machine inherits Mini_1.

----------------------------

1. TailRecursion variants of AP, RAP and SEL are added -
   TR_AP, TR_RAP and TR_SEL
   They don't push nothig into D register.
   They codes are codes of originals + 1.

2. Compiler changed to generate proper TailRecursive programs:

   Secuences ... AP RET)  are changed to ... TR_AP)
   Secuences ... RAP RET) are changed to ... TR_RAP)
   Secuences ... SEL c1 c2 RET) are changed to ... TR_SEL c1 c2)


----------------------------

The next machine is Unify_0


======================  Unify_0/Changes.txt  ======================

This Machine inherits TR_SECD.

--------------------------------------------------

1. New command DEC is added (code 7).

2. Compiler changes (unify compilation of standart primitives).

The result is slower, but shorter compiler.

3. Many versions of this compiler (1..9) do the same.
   In final versions command DEC is not used.

---------------------------------------------------

Next Mashine is Shell_0



======================  Shell_0/Changes.txt  ======================

This Machine inherits Unify_0.

Changes:

1. Old meta_program named self.pp compiles compiler itself.

   Now it is forks into 3 meta_programs with the semantics:

   self       - compiles compiler.lisp into compiler.secd.new
   comp fname - compiles file fname.lisp
   secd fname - executes file fname.secd

2. The mapcar demo is writen and tested.
   Note that the 'map' funcion is operator,
   it gets as parameter one parameter function and
   returns function on lists. 

   The type of map is: X->X -> L->L

   The whell cnown mapcar function hase type : <X->X , L> -> L 

   
3. First versions of some shell program are writen:

   shell_0 defines function (shell lambda(limit)).
   Important is second if in the body of this function:

   (if (eq (shell_step limit) nil)
       (shell (dec limit))
       (shell (dec limit)))

   This expresion ensure that first will be evaluated 
   shell_step function and then (shell (dec limit)).

   This function provides circle loop (loop will
   be executed while limit>0).

   ----

   shell_1 is a demonstration how to compile and execute expresions
   while the shell program is running (online compilation).

   I think that this is imposible with standard SECD instructions.
   In stack S must be pushed redundancy NIL to simulate parameter
   list for APP command.
   I solve this problem, i added new command EXEC (cod 4) with
   following rule:

   (c'.e' s)  e  c  d  --> s e' c' d

   This command is last command of online compiled null
   parameter functions, allowing online compilation.

   Key part of this mechanism are 2 functions:

   (eval lambda(expr)
     (let ((cons (compile fun) nil))
        (fun cons (quote lambda) (cons nil (cons expr nil)))))

   (compile lambda (e)
     (comp e nil (quote (4))))
                      

---------------------------------------------------

Next Mashine is RC_GC



======================  RC_GC/Changes.txt  ======================

This Machine inherits Shell_0.

Changes:

All changes in this section affects only meta_machine
(pascal implementation of the SECD mashine) !

1. Some more efective commands are defined in meta_machine
   to optimise furter implementation of Reference Count
   Garbage Collector and some SECD commands (LD x.y).

   car(x,x)    -> CarSelf(x)
   cdr(x,x)    -> CdrSelf(x)
   cons(x,y,y) -> Push(x,y)
   cons(y,x,y) -> PushR(x,y)
   New meta_command GetNth(s,d,i) for LD acceleration.

   cons(x,y,z) is not used, but not removed.

2. Into all list-oriented meta_commands are inserted
   calls to RC_inc and RC_dec functions - they change
   reference counts in list space. If some node counter
   decrese to 0, procedure RC_Collect is called to release
   this node.

3. Reference Count Garbage Collector V.1 is ready !

   Advantages:

   a) This is more real-time collector.
   b) It seems that this collector is slower, but 
      realy it is faster than standart mark/release
      collectors. Efficiency of standart collector
      depends on ratio free_heap/used_heap, until
      the efficiency of RefCount collector is
      constant. If ratio free/used < 50% then 
      RefCount collector must be faster.

   Disadvantages:

   a) This collector don't release all unused nodes.
      It can't free circular lists. In SECD model such
      lists occurs as result of RAPP command. To avoid
      this problem, standart collector must be added as
      additional collector when the heap is spent.

---------------------------------------------------

Next Mashine is LRC_GC



======================  LRC_GC/Changes.txt  ======================

This Machine inherits RC_GC.

Changes:

All changes in this section affects only meta_machine
(pascal implementation of the SECD mashine) !

1. In previous machine RC_Collect go around all subtree
   of released node. This may be very big tree and if
   this is the case, the machine will sleep for a long
   time (like in standart mark/release collector). 

2. In this machine RC_Collect release immadiately
   only the left branch of the tree. Other parts of 
   this tree are pushed onto GC internal stack and delayed
   for later release.
   Procedure GetNewNode starts with attempt to release
   node of the top of the GC internal stack.

   This version of Reference Count Collector may be named
   Lazy Reference Count Garbage Collector (LRC_GC).

   It provides real-time behavior of the SECD machine !

   The complexity of each LRC_GC step is limited by O(L), 
   where L is the length of the longest list in memory.

   This complexity is same as the complexity of GetNth meta_call,
   used by LD SECD command.

   Thus way there is no need to develop more nimble Garbage
   Collector.

   
---------------------------------------------------

Next Mashine is Unify_1



======================  Unify_1/Changes.txt  ======================

This Machine inherits LRC_GC.

Changes:

1. Changes in compiler.lisp

2. Cros_compilation for next machine Fast_0 

---------------------------------------------------

Next Mashine is Fast_0



======================  Fast_0/Changes.txt  ======================

This Machine inherits Unify_1.

Changes:

Previous machines used very slow mechanism to 
evaluate actual parameter list for user defined functions.
Each parameter is put in v by SECD command CONS, wich 
consumes 2 meta_cons.

This machine use different model of evaluations:

1. APP and similar commands are changed:
   15 APP
     (c'.e' s) e c d --> s s.e' c' (e c d)
   16 TR_APP
     (c'.e' s) e c d --> s s.e' c' d
   17 RAP
     (c'.e' s) nil.e c d --> s SetCar(e',s) c' (e c d)
   18 TR_RAP
     (c'.e' s) nil.e c d --> s SetCar(e',s) c' d

2. EXEC is removed

3. RTN is changed to have integer n as a parameter:

   5 RTN n
     (x x1 x2 ... xn s) e c (e1 c1 d) --> (x s) e1 c1 d
            
4. Compiler is adapted for this model of evaluations.


---------------------------------------------------

Next Mashine is Fast_1



======================  Fast_1/Changes.txt  ======================

This Machine inherits Fast_0.

In previous machine some case of TR behavior can't be
solved.

1. TR_APP and TR_RAP are changed to have parameter n:
   16 TR_APP n
     (c'.e' s) e c d --> cdrself(s,n) s.e' c' d
   18 TR_RAP n
     (c'.e' s) nil.e c d --> cdrself(s,n) SetCar(e',s) c' d

2. Compiler is adopted for this model of evaluations.
   Now Tail Recursion is fuly functional, but RET n
   make 1 additional meta_cons (if n>0), so TR_SEL is changed:

   20 TR_SEL n
     (x x1 x2 ... xn s) e (c1 c2 c) d --> s e cx d
  
3. Changes are made in compiler to use TR_xxx n whenever is
   possible.

4. The small program test.lisp is created an test with
   some of my SECD models. See the results:

   SECD machine     Loops      Cons          Cons
                               (eval)        (load & eval)

   Cache_0          202        143           307 
   Squeeze_1        202        240           404
   
   Fast_1           202	       240           496
   Fast_0           209        268           522
   Unify_1          261        321           620
   Shell_0,RC_GC,   
   Unify_0,LRC_GC,     The same as Unify_1
   TR_SECD
   Mini_1           282        363           676
   Mini_0           282        405           718

   The Mini_0 is the same as the original SECD machine from
   Henderson book.

   May be for other programs the results will differ, but
   i think that creation of model such as Fast_1 is resonable.

   The model Fast_x has one disatvantage - if you call function
   with differ count of actual and formal parameters, the stack S
   will be destroied. Henderson model allow to call function with
   count of actual parameters bigger than formal parameters list.

   Finding different lengths of formal/actual parameter me
   be solved in compilation time (some cases) or
   in execution time by some expanded SECD machine.
   
---------------------------------------------------

Next Mashine is Squeeze_0




======================  Squeeze_0/Changes.txt  ======================

This Machine inherits Fast_1.

---------------------------------------------

1. New syntax is defined for integers bigger than 2^24.
   Thes integers are represented in I/O streams in form:

   #ccc_n

   where ccc is some mnemonic for SECD command code and
   n is integer parameter.

   if SECD code is byte c and parameter n,
   the value of the corresponding big integer is c*2^24+n.

   This value will be used later to encode 
   SECD command + integer parameter to a 32-bit integer.

   Examples: #rtn_7    is same as  5*2^24+7
             #sel      is same as  19*2^24
             #trsel_3  is same as  20*2^24+3

2. Arithmetic binary commands are added to SECD mashine:

   ADD with code 22:
      (x y s) e c d --> (x+y s) e c d
   SUB with code 23:
      (x y s) e c d --> (x-y s) e c d
   MUL with code 24:
      (x y s) e c d --> (x*y s) e c d
   DIV with code 25:
      (x y s) e c d --> ((x div y) s) e c d
   REM with code 26:
      (x y s) e c d --> ((x mod y) s) e c d
   LEQ with code 27:
      (x y s) e c d --> ((x <= y) s) e c d

3. Compiler is changed to understand these commands.

4. New compiler comp_mnem.lisp is prepared for encoded
   SECD commands.

---------------------------------------------

Next Mashine is Squeeze_1.



======================  Squeeze_1/Changes.txt  ======================

This Machine inherits Squeeze_0.

---------------------------------------------

1. SECD machine is changed to use encoded commands:

   LD (x.y)  --> #ld_x_y  =  1*2^24+256*x+y
   RTN n     --> #rtn_n   =  5*2^24+n
   TR_APP n  --> #trapp_n = 16*2^24+n
   TR_RAP n  --> #trrap_n = 18*2^24+n
   TR_SEL n  --> #trsel_n = 20*2^24+n

2. Compiler is addopted to these changes.

3. The number of SECD loops and meta_cons is not changed
   in this machine, but the size of code is reduced by
   around 40%, decresing the number of car/cdr meta commands
   during execution of the SECD program.

---------------------------------------------

Next Mashine is Cache_0.



======================  Cache_0/Changes.txt  ======================

This Machine inherits Squeeze_1.

------------------------------------------------------

1. Processor cache for SECD machine is developed.
   It is very simple:

   The cache consist of one new register - A (accumulator)
   and flag CacheON. CacheON saves the cache state - 
   active (A holds info) and passive (A is not used).
   Register A cached the first element of S register.

                    SECD without         SECD with
                    cache (old)          cache (new)
              
CacheON=false       S        <=====>     S

CacheON=true       S=(x s)   <=====>     A=x;  S=s


2. The cache is coded in implementation part of the program
   secd_cod.pp. Noting changes in other Pascal and SECD/Lisp programs.
   
3. Results of this simple change in SECD implementation is 
   smart - number of meta_cons operations during execution
   decrease with 40-50% (40% for test, 50% for self-compilation). 
 
4. The program test.lisp now gives the following results for
   the following SECD models: 

   SECD machine     Loops      Cons          Cons
                               (eval)        (load & eval)

   Unify_2          225        141           321
   Cache_0          202        143           307 
   Squeeze_1        202        240           404
   Fast_1           202	       240           496
   Fast_0           209        268           522
   TR_SECD          261        321           620
   Mini_1           282        363           676
   Mini_0           282        405           718

---------------------------------------------------

Next Mashines are Unify_2 and Fast_2.




======================  Fast_2/Changes.txt  ======================

This Machine inherits Cache_0.

------------------------------------------------------

1. Some new control commands are introduced (let/trlet, letrec/trletr),
   other are removed (rap/trrap), and the rest changes its codes: 

 32 LET
    s e (c' c) d    --> s         (s e)       c' (e c d)
 33 TRLET n
    s e (c' c) d    --> Drop(s,n) (s e)       c' d
 34 LETREC
    s e (c' c) d    --> s         Setcar(e,s) c' ((cdr e) c d)
 35 TRLETR n
    s e (c' c) d    --> Drop(s,n) Setcar(e,s) c' d
 36 APP   
    (c'.e' s) e c d --> s         (s e')      c' (e c d)
 37 TR_APP n
    (c'.e' s) e c d --> Drop(s,n) (s e')      c' d
 38 SEL
    (x s) e (c1 c2 c) d --> s e cx (e c d)
 39 TR_SEL n
    (x s) e (c1 c2 c) d --> Drop(s,n) e cx d

2. Compiler is modified. Now some space and meta_conses are saved
   during execution of let/letrec blocks.

3. The program test.lisp now gives the following results for
   some of the SECD models: 

   SECD machine     Loops      Cons          Cons
                               (eval)        (load & eval)

   Fast_2           200        141           301
   Cache_0          202        143           307 
   Squeeze_1        202        240           404
   Fast_1           202	       240           496
   Fast_0           209        268           522
   TR_SECD          261        321           620
   Mini_1           282        363           676
   Mini_0           282        405           718

   Unify_2          225        141           321
   
---------------------------------------------------

Next Mashine is Fast_3.




======================  Fast_3/Changes.txt  ======================

This Machine inherits Fast_2.

------------------------------------------------------

1. Into 3 of TR commands (TRLET, TRLETR and TRSEL) is a redundancy:
   They accept in C register (... c), but the tail c is not
   accesible later, so it is removed:

 33 TRLET n
    s e c d           --> Drop(s,n) (s e)       c d
 35 TRLETR n
    s e c d           --> Drop(s,n) Setcar(e,s) c d
 39 TRSEL n
    (x s) e (c1 c2) d --> Drop(s,n) e cx d

2. Compiler is modified and cros-compiled in Fast_2. 
   Another space and meta_conses are saved, because
   the SECD programs are shorter. 

3. The program test.lisp now gives the following results for
   some of the SECD models: 

   SECD machine     Loops      Cons          Cons
                               (eval)        (load & eval)

   Fast_3           200        141           293
   Fast_2           200        141           301
   Cache_0          202        143           307 
   Squeeze_1        202        240           404
   Fast_1           202	       240           496
   Fast_0           209        268           522
   TR_SECD          261        321           620
   Mini_1           282        363           676
   Mini_0           282        405           718
-----------------------

Optionals:
   Unify_2          225        141           321
   
---------------------------------------------------

Next Mashine is Cros_0.




======================  Cros_0/Changes.txt  ======================

This Machine inherits Fast_2.

------------------------------------------------------

1. This is cros-machine to SEC_0

---------------------------------------------------

Next Mashine is SEC_0.




======================  SEC_0/Changes.txt  ======================

This Machine inherits Cros_0.

------------------------------------------------------

1. The register D is removed from SECD machine.
   S is used to save E and C in control commands.
   Now Tail Recursion requires more sincronised actions,
   so RTN and APP/TRAPP-like commands are changed.

2. Compiler is modified and cros-compiled in Cros_0. 

3. Minor changes in secd_str.pp

4. The speed and memory usage are not changed during the last
   changes. The behavior of SECD programs is the same as in 
   Fast_3
   

  FULL list of SECD commands:
  ---------------------------

  1 LD x y       s  e c           --> ((GetNth(GetNth(e,x),y) s) e c  
  2 LDC          s  e (x c)       --> (x s)   e      c 
  3 LDF          s  e (f c)       --> (x.e s) e      c 
  5 RTN          (x e' c' s) e c  --> (x s)   e'     c'
  6 DUM          s           e c  --> s      (nil e) c 
  
  7 DEC     (x s) e c  --> (x-1 s)      e c    
  8 INT     (x s) e c  --> (int?(x) s)  e c
  9 INC     (x s) e c  --> (x+1 s)      e c 
 10 CAR     (x s) e c  --> (car(x) s)   e c
 11 CDR     (x s) e c  --> (cdr(x) s)   e c
 12 ATOM    (x s) e c  --> (atom?(x) s) e c
 
 13 CONS    (x y s) e c  --> (cons(x,y) s) e c  
 14 EQ      (x y s) e c  --> (eq(x,y)   s) e c
 21 STOP
 22 ADD     (x y s) e c  --> (x+y s)       e c 
 23 SUB     (x y s) e c  --> (x-y s)       e c 
 24 MUL     (x y s) e c  --> (x*y s)       e c 
 25 DIV     (x y s) e c  --> ((x div y) s) e c 
 26 REM     (x y s) e c  --> ((x mod y) s) e c 
 27 LEQ     (x y s) e c  --> ((x <= y) s)  e c 

 32 LET n        s    e     (c' c)    --> (e c Drop(s,n))       (s e)       c' 
 33 TRLET n      s    e     c         --> Drop(s,n)             (s e)       c  
 34 LETREC n     s    e     (c' c)    --> ((cdr e) c Drop(s,n)) Setcar(e,s) c' 
 35 TRLETR n     s    e     c         --> Drop(s,n)             Setcar(e,s) c  
 36 APP n        (c'.e' s) e c        --> (e c Drop(s,n))       (s e')      c' 
 37 TR_APP n     (c'.e' s) e c        --> Drop(s,n)             (s e')      c' 
 38 SEL          (x s) e    (c1 c2 c) --> (e c s)               e           cx 
 39 TR_SEL       (x s) e    (c1 c2)   --> s                     e           cx 


---------------------------------------------------

Next Mashine is CacheL2.



======================  CacheL2/Changes.txt  ======================

This Machine inherits SEC_0.

------------------------------------------------------

1. Processor cache for SECD machine is expanded.
   Now it consist of 2 registers A and B and counter
   ChCnt with posible values 0,1 and 2:

   ChCnt = 0 if cache is not used
   ChCnt = 1 if only A register is used
   ChCnt = 2 if all cache is used

   Registers A and B caches the first two elements of S:

                    SECD without         SECD with
                    any cache            L2 cache (new)
              
ChCnt=0             S         <=====>     S

ChCnt=1             S=(x s)   <=====>     A=x;  S=s

ChCnt=2             S=(x y s) <=====>     A=x; B=y; S=s


2. The L2 cache is coded in implementation part of the program
   secd_cod.pp. Noting changes in other Pascal and SECD/Lisp programs.
   
3. Results of the changes in SECD implementation is good:
   The program test.lisp now gives the following results for
   some of the SECD models: 

   SECD machine     Loops      Cons          Cons
                               (eval)        (load & eval)

   CacheL2          200        113           265
   Fast_3           200        141           293
   Fast_2           200        141           301
   Cache_0          202        143           307 
   Squeeze_1        202        240           404
   Fast_1           202	       240           496
   Fast_0           209        268           522
   TR_SECD          261        321           620
   Mini_1           282        363           676
   Mini_0           282        405           718

4. Let assume that number of SECD loops is good approcsimation 
   for meta_car, meta_cdr and similar meta_commands costs in 
   execution time. 

   Then total execution costs will be the sum of loops and
   meta_conses.

   Let see the table for total costs for test.lisp example:
   
   SECD machine     Loops      Cons          Total Costs
                               (eval)        Loops + Cons

   CacheL2          200        113           313
   Fast_2           200        141           341
   Cache_0          202        143           345 
   Squeeze_1        202        240           442
   Fast_1           202	       240           442
   Fast_0           209        268           477
   TR_SECD          261        321           582
   Mini_1           282        363           645
   Mini_0           282        405           687

   The same test is made with program compiler.lisp 
   from Mini_0 to compile itself:

   Mini_0           43724      51670         95394
   CacheL2          31942      10441         42383


   For test.lisp acceleration is 687/313     = 219.5 %
   For mini.lisp acceleration is 95394/42383 = 225.1 %


---------------------------------------------------

Next Mashine is Base_0.




======================  Base_0/Changes.txt  ======================

This Machine inherits CacheL2.

------------------------------------------------------

1. New command LEXLEQ is added to SECD machine with code 28.
   It compares atom names for lexical less or equal relation.
   
2. New lisp function is added to compiler - (lexleq x y)

3. Old compiler is renamed to compiler.lisp.linear
   (it searches lineary into the list of system names)

4. New function lexleq is used to search in system names
   list like in binary tree.
   Compiler derives into two versions:

   ) compiler.lisp.btree1 makes only one lexleq and thus 
      splits the list into 2 sublists.

   b) compiler.lisp.btree2 makes 2 lexleq-s and thus 
      splits the list into 4 sublists.

   First compiler is faster now, but if system functions count
   grows, the second will stay faster.

5. Into these 2 compilers are added as macros 2 new lisp functions -
   (or x y) and (and x y), with compilation rules:

   (or x y)    <==>  (if x (quote T) y)
   (and x y)   <==>  (if x y (quote F))

6. File sysfun.txt contains current list of system functions in
   alfabetical order.

---------------------------------------------------

Next Mashine is Lazy_0.




======================  Lazy_0/Changes.txt  ======================

This machine inherits Base_0.

------------------------------------------------------

1. New subtype of node data type is added to meta_machine - 
   recipe.
   It is very similar to node and will be used for 
   lazy evaluations. Thes changes affects only secd_mem.pp

   For recipes i will use the syntax [x.y] and the 
   following semantic:

   [c.e]    represents delayed expression (c <> nil)
   [nil.x]  represents recovered expression with x as a
            terminal value (integer/atom/nil) 
   Recovered expressions with node values will
   be puted at the same place where the original delayed
   recipe was placed.


2. Following recomendations in part 8.2 of the Henderson book
   and exercise 8.7, new commands are planned to add to SECD machine:

   DELAY  s e (c c')  --> ([c.e] s) e c'

   This command delay the evaluation of expression, 
   represented by command list c in C register.


   RECOVER identifies many cases: 
   (x s) e c       --> (x s) e c       if x is not a recipe
   ([nil.x] s) e c --> (x s) e c       if x is a int/atom/nil 
   ([nil.x] s) e c --> (x s) e (REC c) if x is a recipe 
   ([nil.x] s) e c --> (x s) e c       if x is a node
         [nil.x] is replaced with x    (by-pass_B)
   ([c.e] s) e' c' --> ([c.e] e' (REC c') s) e c

   The RECOVER command starts evaluation of delayed expression.
   It will be repeated until the normal evaluated value
   occures on top of S.


   SUBST 
   (x [c.e] e' c' s) e nil --> (x s) e' c'
   [c.e] is replaced with [nil.x]   if x is not a node
   [c.e] is replaced with x         if x is a node (by-pass_A)

   This command is similar to RTN and is used to finish
   the evaluation of a delayed expression.

   The codes are:
    4 for DELAY 
    

3. But let me think befoure programming! 
   SUBST and RTN will be different form of restoration
   of E and C registers, and TailRecursion mechanism will
   be broken. To have full TR behaviour, we must have unified
   restoration of E and C regs !

   RTN expects to find in S list (x e' c' s), while
   SUBST expects (x [c.e] e' c' s)

   e' is always non-recipe and we may use this fact.

   If we plan to use TR, we must have TR variant fo RECOVER:

   TRREC (only last case differ from RECOVER):
   ([c.e] s) e' c' --> ([c.e] s) e c

   After executing a sequence of APP-like command, followed
   by sequence of TR-APP-like commands (RECOVER is APP-like,
   while TRREC is TR-APP-like) into the stack befoure RTN-like
   command will be the sequence:

   (x r1 r2 .... rk e' c' s)

   where all r1..rk are recipes and e' is not recipe, so we may
   define unified RTN command.

   if k=0 we are shure that all APP/TR-APP commands sequence
   not contains RECOVER/TRREC, and RTM may return delayed value

   if k>0 at least 1 RECOVER-like command was executed.
   In this case RTN must return non-delayed value, and we must
   include RECOVER loop in RTN behavior (because this loop can't
   be inplemented in TRREC).

4. Following the resoning given upper let define new RTN behavior
   and new SECD commands RECOVER/TRREC:

   RTN 
   if S has the form ([c.e] [c1.e1] s) 
    then TRREC { x is delayed value ! }
    else begin
      while S has the form (x [c.e] s) do begin
        { x must be now non-delayed value ! }
        if x is node
         then replace [c.e] with x 
         else replace [c.e] with [nil.x];
        (x [?.?] s) e nil --> (x s) e nil 
      end;
      { now S has the content (x e' c' s) }
      (x e' c' s) e nil  --> (x s) e' c'
    end;
   
   TRREC 
   (x s) e c         --> (x s) e c       if x is not a recipe
   ([nil.x] s) e  c  --> (x s) e c        
   ([c.e] s)   e' c' --> ([c.e] s) e c
   
   RECOVER  
   (x s) e c         --> (x s) e c       if x is not a recipe
   ([nil.x] s) e  c  --> (x s) e c        
   ([c.e]   s) e' c' --> ([c.e] e' c' s) e c

5. The last definitions are more short and clean than these
   in 2., and if i don't make errors, this mechanism must work.

   The more proper definitions for the new commands are:

   CleanX (common procedure for all):
    repeat
      ([nil.x] s) e c --> (x s) e c
    until S is ([nil.x] s)

   RTN
    CleanX;
    if S is ([c.e] [c1.e1] s)
     then ([c.e] s) e' c' --> ([c.e] s) e c 
     else begin
       while S is (x [c.e] s) do begin
         if x is node
           then replace [c.e] with x 
           else replace [c.e] with [nil.x];
         (x y s) e nil --> (x s) e nil 
       end;
       (x e' c' s) e nil  --> (x s) e' c'
     end;

   TREC
    CleanX;
    if S is ([c.e] s)
     then ([c.e] s) e' c' --> ([c.e] s) e c 

   RECOVER
    CleanX;
    if S is ([c.e] s)
     then ([c.e] s) e' c' --> ([c.e] e' c' s) e c 

6. The last definitions are implemented and tests begin.
   First all current lisp programs are tested - they work.
   
7. 2 new lisp functions are defined in compiler:
   (delay exp) - delays the evaluation of expression
   (recover exp) - recovers delayed expression 

   Small program demo.lisp defines infinite list of 
   natural numbers - (Nfrom 0) is such a list.

   Then demo evaluates first 8 elements of the list.

   This evaluation is correct !

---------------------------------------------------

Next machine is Lazy_1.




======================  Lazy_1/Changes.txt  ======================

This machine inherits Lazy_0.

------------------------------------------------------

1. Lazy compiler is defined, following chapter 8.3 
   recomendations of Henderson book.

   This compiler is named complazy.lisp.
   Meta program lcomp.pp is introduced to support
   compilation of lazy lisp programs.

   demo.lisp is modified (apparent use of delay and 
   recover is removed).

2. The compiler produce proper code, but the result of
   evaluation conatins many receipes, so it can't be
   displayed. To avoid this, i wrote the non-lasy program
   show.lisp (see file show.lisp.2) and then modify handly
   the code show.secd (result is show1.secd). Meta 
   program lazy.pp executes lazy lisp program, then 
   executes show1.secd and produce fully evaluated 
   result into top of the S register.

3. New command added to SECD for complete test of data type:

   15 NULL    (x s) e c  --> ((x=nil?) s) e c
   16 NODE    (x s) e c  --> (node?(x) s) e c
  
   Two new lisp functions are added to both compiler.lisp and
   complazy.lisp:

   (null x) tests if the argument is a nil
   (node x) tests if the argument is a node 

4. show.lisp is rewriten with new lisp function node, to be shorter,
   then the code is handly modified and tested (show2.secd).
   complazy.lisp is saved as comlazy.lisp.2  

5. The evaluation forcing code show2.secd is added at the tail of 
   each lazy compilation. Now the complasy produce programs
   with final result not containing recipes. They must be 
   executed with standart secd.pp meta_program.

6. I try to comile complazy itself, but the resulting code
   don't work properly. This is because the tail of compiled
   functions not started with #rec. This is changed and all
   is OK. Now the complazy compiles itself !

7. The mata_programs lcomp.pp and lazy.pp not needed, they 
   will be erased from the next machine.


------------------------------------------------------

Next machine is Lazy_2.




======================  Lazy_2/Changes.txt  ======================

This machine inherits Lazy_1.

------------------------------------------------------

1. compiler.* inherits complazy.* from previous machine,
   selfcompilation is tested. 

2. New lazy compiler is very slower. 
   Comparison for selfcompilation:

                          Loops           Conses

   NonLazyCompiler         68147           28308
   LazyCompiler           178914           93437
   
   I am starting to think about optimisations.

3. The or/and macros are not needed - the lazy user
   functions

   (or  lambda(e1 e2) (if e1 (quote T) e2))
   (and lambda(e1 e2) (if e1 e2 (quote F)))

   will do the same as previous nonlazy defined macroses.
   The or/and are removed from the compiler and user
   definitions for and/or are tested.

   This compiler version is saved as compiler.*.0

4. Some unifications in compiler saved as compiler.*.1

5. There is many redundant code pices in *.secd files.
   Some reductions may be done: 

   #delay (#ld_m_n #rtn)  ==> #ld_m_n
   #delay (#ldc X #rtn)   ==> #ldc X
   #delay (#ldf F #rtn)   ==> #ldf F

   The compiler is changed to do such reductions.
   The result is shorter and faster compiler.*.2

6. Reductions for #rec:

   #ldf F #rec   ==> #ldf F
   #ldc X #rec   ==> #ldc X
   
   Resulting compiler is compiler.*.3

7. Reductions for #rec:

   cmd #rec   ==>  cmd

   for all primitive commands excluding car & cdr

   Resulting compiler is compiler.lisp / compiler.secd
   It is bigger than previous models, but it seems that
   generated code don't contains obvious redundances.
   
   
------------------------------------------------------

Next machine is TR_Lazy.




======================  TR_Lazy/Changes.txt  ======================

This machine inherits Lazy_2.

------------------------------------------------------

0. The TR form of #rec is never used in Lazy_2 machine.
   This is because #rec is always followed by other 
   evaluation command. Many of cases are:

   (... #rec primitive_code #rtn)

   Others are:

   (... #rec #trapp_n)

   All these pieces of code may be treated as Tail Recursive
   calls, but the model of my SECD machine must be little changed.

   The change consist of implanting the primitive_code into the
   non-evaluated recipe.

   The recipe subtype is extended to contains a byte value p.
   I will mark this new form of recipe as [p|c.e]
   p will be used to represent primitive_code (p<128) which must be
   executed after the recipe evaluation is done or the n parameter
   ot #trapp_n code, following #rec command (p=128+n in the case).

   The behavior of #trrec_p and #rtn is changed in secd_cod.pp
   Now #trrec implants the pcod/trapp_n into p value of recipe.
   After the recipe is evaluated, #rtn code first replaces
   evaluated result into recipe, then executes command, represented
   by p.

   See the pascal implementation of RTN and TRREC for more details.
   

1. TailRecursive reduction:

   #rec pcod #rtn  ==> #trrec_pcod


2. Some changes in secd_mem.pp:
   CdrSelf(s) replaced with Drop(s,1)
   Car(s,d)   replaced with GetNth(s,d,0)
   Push, PushR optimised
   MoveReg replaced with CopyReg/MoveReg.


3. TailRecursive reduction:

   #rec #trapp_n   ==> #trrec_(128+n)

   
4. Other changes in secd_mem.pp (Roll optimised). 
   Minor changes in tail code (show2.secd) for
   compiled functions in compiler.lisp.

5. Appropriate changes are made into the compiler.lisp.
   Now it creates fully TailRecursive code for lazy 
   evaluations !

6. The effect of new changes is not big. Some statistics 
   is made for use of #rec and #trrec calls during the 
   evaluations:

   program          #rec calls         #trrec calls

   selfcompilation  7086               490
   primes           6065               140
   test               21                 5

   Each #trrec call saves 2 meta_conses, but the table 
   above shows that real #trrec calls are seldom used.

   In the compiled code the number of #trrec-s is bigger than
   #rec instructions tipicaly 2-3 times.

   May be this paradox represents the nature of the lazy evaluations.

7. Comparison for selfcompilation:
   (note that the compiler for nonLazy functions is 
   simpler than Lazy compiler, which is simpler than
   TR_Lazy compiler).

                          Loops           Conses

   NonLazyCompiler         68147           28308
   LazyCompiler           178914           93437
   TR_LasyCompiler        153298           77469 


   
------------------------------------------------------

Next machine is MR_GC.




======================  MR_GC/Changes.txt  ======================

This machine inherits TR_Lazy.

------------------------------------------------------

1. Some minor changes in compiler.lisp - delay and
   recover functions are removed (i think that in
   lazy programs they are unusable).

2. I wrote two more lazy variants of the compiler.
   They are in Compilers subdirectory, but tests
   below shows that they are slower than the nonlazy
   stile compiler. The big heap usage is a result of 
   inset use of letrec in new compilers. 

3. Comparisons for compilation of mini.lisp with 
   different compilers:

                         Loops      Conses     HeapUse

   Base_1 compiler.1     86350      45425      12228
   Base_1 compiler.2     83041      46051      12282
   TR_Lazy compiler      82326      42963       4733
   Base_1 compiler       81902      42567       4688
   CacheL2 compiler      59022      21031       1826 

4. Lazy-stile compiler are saved if you decide to use
   them as more readable. 

5. It is time to include in my meta_machine the standart 
   Mark/Release Garbage Collector.  

6. First Mark/Release Collector is saved in secd_mem.pp.1
   MarkReg uses Pascal stack for recursion calls.

7. Final MR version uses array GCStack for MarkReg loops.    
   Pascal recursion not used for Garbage Collectors.

8. The tests show the following:

   If some lisp program contains only one letrec block,
   Mark/Release collector can't free any node.
   
   The inset letrec constructions of the form:
   (letrec (letrec ... (letrec e ...) ...) ...)
   must be counted as 1 big letrec block.

   The constructions of the form:
   (letrec e ... (f1 lambda(x) (letrec ...) ...)
   must be counted as 2 letrec blocks.

   If the program contains more than one letrec block,
   MR collector succeeds to free some unused circular list space.

   My MR collector has not real_time behavior.
   If you want to develop real_time system, and if you 
   use programs with more than 1 letrec blocks, you must
   develop some real_time MarkRelease collector.

   One possible idea for such collector: divide the node
   space into 2 equal blocks - A and B. In each moment
   one block is used for new conses (active), 
   other (passive) is marked/released lazy while SECD 
   machine is working. When passive block is fully released,
   it stand up active, and lazy mark/release circle begins
   for the other block.

   
------------------------------------------------------

Next machine is Base_1.




======================  Base_1/Changes.txt  ======================

This machine inherits MR_GC.

------------------------------------------------------

1. This is final machine in Lazy line. Properties:

   - SECD & lisp compiler mechanisms for lazy evaluation
   - fully TailRecursion handling.
   - Reference Count as root garbage collector
   - Mark/Release as additional garbage collector
   - SECD command + parameters encoding into a 32-bit word.
   - Internal cache
   

------------------------------------------------------

Next machine is Files_0.


======================  Files_0/Changes.txt  ======================

This machine inherits Base_1.

------------------------------------------------------

1. SECD codes are rearanged:

   01..15 Special codes (LDx, RTN, DUM, STOP)
   16..31 Binary primitives (cons, eq, add ...)
   32..47 Calls (app,trapp, ...)
   48..63 Unary primitives (car,cdr, ...)

2. Using some ideas from Haskell 98 language, i'm 
   starting implementation of the I/O system.

   There must be a possibility to organise the
   sequence of actions to implement I/O and 
   communication with the outside world.

   The special lisp primitive is implemented:

   (do V e1 e2)

   with behavior:

   a) e1 is evaluated and recovered.
   b) result is binded to variable V.
   c) e2 is evaluated into the environment ((V) e).

   The behaviour of do is similar to

   (let e2 (V e1))

   except the following: in let e1 is delayed, while in do
   evaluation of e1 is forced.
   
   The semantics of do may be explained in this way:

   Organise the sequence of actions: first evaluate e1
   and store the result in V, then evaluate e2. You may
   use the result of e1 as variable named V. 

3. New SECD commands are defined:

   CHR n   creates atom from one character with ASCII code n
   PUTLEX  writes to stdout the non-node data from top of S
   GETLEX  reads from stdin a lexeme. lexeme is converted to
           nil/integer/atom. GETLEX has fictive parameter n
           to look like unary primitive.

   GETLEX and PUTLEX codes differ from other SECD codes: they
   communicate with the outside world, so they are not 
   functional (each time we execute GETLEX, the state of the
   machine depends from stdin content) !

4. The corresponding new lisp functions are defined into the
   compiler: (chr n), (putlex x) and (getlex n).

   I began to write analogs for the meta functions 
   ReadSFrom and WriteSTo (for reading/writing S-expresions). 

   These IO utilities are defined in file system.lisp.

5. New SECD command is defined:

   FLINK n fname
    n=0/1 <==> stdin/stdout
    fname is atom ==> file fname is used as stdin/stdout
    fname is nil  ==> keyboard/display is used as stdin/stdout

   New lisp function (flink n fname) is defined.

6. functions in system.lisp are expanded to allow reading/
   writing of S-exp. from/to selected file. 

   It seems they work properly.

7. The ReadSFrom lisp definition is used to go round usage
   of meta_function ReadSFrom in boot process. This is done
   in boot subdirectory and is explained in boot/README file.

8. New SECD command is defined:

   CONCAT a b
   (a b s) e c  ==> (a||b s) e c    concatenates atom names
   
   Appropriate lisp function (concat a b) is defined.

------------------------------------------------------

Next machine is Libs_0.

======================  Libs_0/Changes.txt  ======================

This machine inherits Files_0.

------------------------------------------------------

Static libraries are implemented in my lisp language: 

1. The function ReadSFrom from system.lisp program is
   placed into compiler.lisp.

   New function libSubst is added to compiler.lisp:

   (libSubst e lib)
   
   It replaces some ocurence of the string 'user_program'
   into lib with e.

   New system function is defined for my version of lisp: 

   (inLib library_name expression)

   The libraries have the form:

   (letrec user_program f1 f2 ... fn)

   If compiler encounters expression like this:

   (InLib myLib exp)

   it will replace exp into myLib.lib file and then
   will compile the resulting file:

   (letrec exp f1 f2 ... fn)

2. These news are tested with infinite numeric sequences
   from Base_1/Examples. The new programs for prime and 
   Fibonachy numbers are placed into subdirectory Numbers.

3. compiler.lib and system.lib are created and tested.  

------------------------------------------------------

Next machine is Shell_1.

======================  Shell_1/Changes.txt  ======================

This machine inherits Libs_0.

------------------------------------------------------

1. print function from system.lisp is expanded to allow
   different styles:

   (print expression style)

   style = (quote secd) --> for *.secd codes (object files)
           (quote lisp) --> for lisp sorce files (*.lib *.lisp)
           other        --> no style

2. New version of print is added to system.lib

3. Now implementation of shell.lisp program is very easy.
   The only problem is how to force the evaluation of
   compiled expression, but i get this from allready
   existing misc/show.lisp program.

   My shell.lisp is only 553 bytes long (but shell.secd is 13K !).
   Here is a typical session:

./comp shell
./secd shell

SEC>8
8
SEC>(add 6 7)
13
SEC>(inLib numbers (First 10 (Fib 1 1)))
(1 1 2 3 5 8 13 21 34 55)
SEC>(inLib numbers (First 20 (p (N 2))))
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
SEC>(let (add a b) (a quote 7) (b add 3 4))
14
SEC>...

4. system.lisp is not needed and it is moved to misc subdir.


------------------------------------------------------

Next machine is Pipes_0.

======================  Pipes_0/Changes.txt  ======================

This machine inherits Shell_1.

------------------------------------------------------

1. Multitasking and interprocess communications are 
   implemented for SECD machine here:

   Tho new registers are defined - r0 and r1 to save
   the pending processes. Each new pending process is 
   pushed onto r0, and if new running process is needed
   it is poped from r1. When r1 becoms nil, r0 is reverced 
   to r1.

   Interproces communication is implemented as message 
   passing mechanism between processes.

   To send and receive messages, the processes uses pipe.
   Each pipe have 2 states - 0 (passive) and 1 (wait).
   pipe is represented as node and additional byte value p of
   node is used (the same p i used before in recipe representation).

   pipes have 2 forms:

   <0|q0.q1>   - passive pipe, q0.q1 represents message queue 
   <1|s.(e.c)> - waiting pipe, (s e c) represents message handler

   2 new commands for SECD machine are defined - SEND and RECV
   in unit secd_msg.pp. See the sources for details of these
   commands.

   SEND starts from the state:
   
   (P msg s) e c

   where P is some pipe and msg is some data passed to P. If the 
   pipe is in waiting state, current process is saved and message
   handler is started to proceed the message. Else msg is saved
   for later handling into q0 part of the queue and current process 
   is supplied with some of the pending processes.
   
   RECV starts from the state:

   (P s) e c

   where P is a pipe from where data must be received. If the pipe
   is in waiting state the error occures - somebody else is 
   waiting for message. Else if there is some ready data, the
   first message is proceed, else current process stay the
   message handler for this pipe and some pending process is
   started.

2. FORK/TRFORK commands are defined (very similar to SEL/TRSEL):

   FORK:   s e (c1 c2 c)  --> (e c s) e c1 
                              r0 --> (((e c s) e c2) r0)

   TRFORK: s e (c1 c2)    --> s e c1 
                              r0 --> ((s e c2) r0)

   Any of these commands creates a new process and put it as
   pending process into r0.

   FAIL is added:

   FAIL   s e c               --> s1 e1 c1
          r1: ((s1 e1 c1) r1)     r1

3. Corresponding lisp functions are defined into compiler.lib:

   (send msg pipe)
   (recv pipe)
   (fork exp1 exp2)
   (fail x)

4. STOP command changes his behavior - the state of finished 
   process is printed to stdout and some pending process is 
   started (STOP <==> FAIL, exept that our FAIL does not
   print anything).

5. Tests for fork/fail:    
    
   queens.lisp from Henderson book (part 7.3) is implemented, 
   but it does not work properly. 
   Lazy evaluation of (choise n) cause the problem.
   This version of queens is saved as queens_bad.lisp.
   If let block in newqueen function is changed with do sequence, 
   all seems to be OK. 

   But this is an important problem -
   lazy evaluations and non-deterministic evaluations (fork)
   are not compatible and we must protect forks into
   some non-lazy construction to avoid collisions.

   May be constructions of the form:

   (do x (fork e1 e2) e3)

   will work properly, but i can't fully understand this 
   problem yet. If you can, please explain me the solution !

6. Test for send/recv:

   previous programs are saved as secd_cod.pp.1 and queens.lisp.1
   The FAIL command is changed to be purely the same as STOP.
   queens.lisp is modified to return final positions as BAD/GOOD.

   Now you may get good solutions in this way:

   ./secd queens | grep GOOD

   and bad solutions in this way:

   ./secd queens | grep BAD

   Problem is that the meta_machine is used to show the results.
   These versions are saved as secd_cod.pp.2 and queens.lisp.2.
   
   secd_cod is modified to kill silently stoped/failed processes.
   Special server-like process named 'spooler' is added to queens.

   The last version of queens do the following:

   - Root expression (fork (addqueen 1 8 nil) (spooler))
     starts 2 processes - one will generate all queens solutions,
     the other (spooler) will print to console these solutions.

   - When a proper solution is found, the expression:
     (send (cons (quote GOOD) newpos) pipe) creates some result
     like (GOOD (8.4) (7.7) (6.5) (5.2) (4.6) (3.1) (2.3) (1.8))
     and then send it as a message to pipe.

   - Spooler do an infinite loop:
     (do x (print (recv pipe) nil) (spooler)))
     First it try to receive a message from pipe. Received message
     is printed to stdout and the loop is closed.

   - The behavior of new program is very interesting:
     First, as expected, all proper solutions are found, send to
     spooler, then printed to console.
     Then my SECD machine unexpectedly stop (note that the spooler try to
     do an infinite loop !). The explanation is that spooler try the
     expression (recv pipe). If there is no arriving messages, spooler
     is saved as message handler into the pipe, but it is not
     member of the queue of pending processes. So the root loop of
     the SECD machine can't find any pending process and stops.
     This is the proper behavior - there may exists some waiting for
     messages process like spooler, but if there is nobody who can
     send new messages, the system can't do anything, so must 
     be stopped.
     
     The processes into r0/r1 registers may be called 'active' -
     they have some uncompleted works to do, while the processes 
     saved into pipes as message handlers may be called 'sleeping'
     - they wait for new messages.

7. New example is added in 2 forms:

   pitagor.lisp finds pitagorean triples in non-deterministic
   stile (pitagorean triples <x y z> are natural numbers following 
   the condition x*x+y*y=z*z).

   in Numbers subdirectory pitlazy.lisp do the same in lazy stile. 


----------------------------------------------------------

Next machine is TimeSh_0.

======================  TimeSh_0/Changes.txt  ======================

This machine inherits Pipes_0.

------------------------------------------------------

---------- WARNING ------------

   There ia an serious bug in this machine !
   The bug occures when #trrec_car/#trrec_cdr
   evaluates working recipe and is demonstarted by
   pr_bad.lisp example !
   It is solved in next machine Files_1,
   but i'm tired to do backtrack changes !
   Don't use this machine !

------- end of WARNING --------   

1. FAIL command is changed with STOP into compiler.lib
   and then is removed from the SECD machine.

2. New counters are added for statistics:

   - PendingCnt to count the number of pending processes. 
   Main loop of the SECD machine is little changed to be
   more readable.

   - RefCntMax shows the max reference counter value.
   - GCSPMax shows the max Garbage Collector stack pointer.
   - SwapCnt shows how many times the controll is swaped
     from one process to another.
   - PendMax is the maximum length of pending processes queue.
   - ShdMaxCnt is the maximum SECD loops between process swap
     if there is more than 0 pending process.

3. TimeSharing is implemented, but it conflicts with lazy
   evaluations. To solve this problem, the lazy mechanism is 
   changed as follows:

   Old recipes have 2 states - delayed and ready. 
   New recipes have 3 states - delayed, working and ready.
   Table below shows the differences:

   State	Old release         New release

   delayed      [c.e]	            [c.e]
   working      [p|c.e]             [p.q] 
   ready        [nil.x] or node     [nil.x] or node

   In working state p is a integer, representing #trrec
   parameter, while q is a queue of processes, waiting 
   the recipe evaluation.

   Note that the additional node field for p is not used
   in new release.

   First process trying to recover some recipe changes it
   state from delayed to [p.nil] and starts the recovering
   actions. If this process is interrupted by the timesharing
   mechanism and some new process try to recover the same 
   recipe, it identifies that the recipe is in working state,
   testing the car(recipe) for integer. If this is the case,
   this process push self into the recipe queue and control is
   send to another pending process:

   [p.q]  --> [p.((s e c) q)]

   When recipe is recovered, the replacement algorithm is:

   SECD contains: (x [P.q] s) e c 

   if x is a node
      then [p.q] is replaced with x
      else [p.q] is replaced with [nil.x];
      
   q is reverced into r1 (all processes witing the recovering
   are ready to be continued);

   (x [P.q] s) e c  --> (P(x s) s') e c

4. Pipe mechanism is changed to use some new subnode type in
   place of the node field p. This field is removed.

5. All these changes are made in meta_machine. 

6. As a result the node internal structure is simplified, but
   the main loop of SECD machine stay more complex - now there 
   is some commands (rtn, rec, trrec) with special behavior.
   Both they start without clearing the command code from C.
   If these command can't finish (the case where waiting recipe is
   on the top of S), they push the current process into the
   recipe queue. In other cases the command clear it's code from C
   and is executed as normal code (Phase1).

   This complex main loop must be changed with some kernel program,
   writen in Lisp, but i will do this later.

7. All meta_machine massages are changed to write on stderr.
   stderr is redirected to file secd.log. If you want to see
   wath happens while the machine is working, open some new
   console and type:

   tail -f secd.log

   
----------------------------------------------------------

Next machine is Files_1.

======================  Files_1/Changes.txt  ======================

This machine inherits TimeSh_0.

----------------------------------------------------------

1. More advanced file handling mechanism is defined in   
   this machine:

   - new subtype of node is introduced - stream
     [stream: f.x ]

     where f represents stream-like file meta_handler and 
     x is nil or send/recv handler.

2. New commands are added to SECD machine:

   18 FOPEN  (m fn s) e c  --> ([stream:f.nil] s) e c  

   opens file fn with mode m
   m=0 - input stream
   m=1 - output stream
   if fn=nil 
    then open stdin/stdout
    else open disk file named fn;

   54 FCLOSE  (f s) e c  --> (close(f) s) e c   close file stream    

3. SEND and RECV are expanded to work with streams.

4. Appropriate lisp functions are added to compiler:

   (fopen mode file_name)
   (fclose stream)

5. system.lib is changed:

   stdin and stdout streams are defined.
   print is changed to use only send function in place of putlex.
   printf is defined:
   (printf SExp Stream style)

   While these news are tested, (send l stdout) fails for delayed
   l, so in compiler.lib definition of send function is changed
   to recover all its arguments.

   read is changed to use recv in place of getlex.

   shell is modified also to use only recv and send only.

   Now getlex, putlex and flink are no more used, so they are 
   removed from SECD machine and from compiler.

6. All *.pp files are adopted to use new in/out procedures.   

7. Serious bug is found in timesharing/lazy mechanism.
   This bug is demonstrated by pr_bad.lisp example.
   It occures when command #trrec_car or #trrec_cdr is
   executed and result is an working recipe. In this case
   #rtn is started, but C register contains (#trrec_cXr).
   This #rtn delay the process, but later recovered process
   contains bad C content.

   To clear this bug, (#rtn) and () content of C are treated 
   as equivalent cases and #trrec is little changed. The main
   loop of SECD machine is changed too.  
   
8. #rtn code in this new implementation is not needed (it is
   represented by null C content).
   Compiler is changed to use nil in place of (#rtn).
   #rtn is removed as mnemonick code from the meta_machine.


----------------------------------------------------------

Next machine is Files_2.

======================  Files_2/Changes.txt  ======================

This machine inherits Files_1.

----------------------------------------------------------

1. SEND and RECV to/from streams in previous machine waits
   the i/o to finish. This brokes timesharing behaviour of
   the machine. In this section SEND and RECV are changed to work 
   asyncronously with streams.

2. New register is defined - io. It represents the sequence
   of Input/Output streams, waiting for data to be send/received.

   If RECV command can't get some ready lexeme, the current
   process is saved to stream, and stream is saved to io register.

   RECV

   (x s) e c          x = [stream:infile.nil]

   [stream:infile.nil] --> [stream:infile.(s e c)]
   io                  --> (x io)

   Then some pending process is loaded.

   If there is an ready lexeme RECV read it from the file:

   (x s) e c           --> ((getlex infile) s) e c

3. SEND to stream is changed in similar way:

   SEND

   (x msg s) e c      x = [stream:infile.nil]

   if msg can't be writen immediately:
   
   [stream:outfile.nil] --> [stream:outfile.(s e c)]
   io                   --> (x io)

   Then some pending process is loaded.

   If msg is writen immediately:

   (x msg s) e c        --> (T s) e c


4. Special example is provided to test if this mechanism works
   properly. The program sh_pr.lisp demonstrates paralel 
   evaluation of shell and prime number list computing.
   While the list of first 3000 prime numbers is evaluated
   and writen into file pr_3000, the shell is working, reading
   and executing the user expressions.
   
5. Some changes are made in secd_msg.pp and secd_cod.pp to 
   simplify the main loop of the machine.

6. All previous machines depends only from pure FreePascal 
   language. The current machine is OS dependant - it uses 
   the Linux unit to check the state of the file operation.
   If you plane to use this machine under other OS, you must 
   use some OS dependant FreePascal library to implement
   FGetLex/FPutLex/FOpen/FClose/FPutStr primitives in secd_str.pp 
   unit of the meta_machine.

7. Test examle don't tests assynronous SEND (lexemes are 
   immediately writen in Linux output buffers). These test
   will be done after the TCP socket implementation. 

----------------------------------------------------------

Next machine is Socket_0.

======================  Socket_0/Changes.txt  ======================

This machine inherits Files_2.

----------------------------------------------------------

1. TCP socket implementation:

   connected TCP socket is represented by node:

   <[stream:infile.nil].[stream:outfile.nil]>

   nonconnected TCP socket may arise in 2 ways: 

   a) from the server side of the connection. In this case
      new SECD command LISTEN creates the TCP listener:

    19 LISTEN  (P M s) e c   --> ([connwait:socket.nil] s) e c
    Start tcp listener on port P, allowing maximum M connections
                              
   b) from the client side of the connection. New command
      CONNECT try to establish connection:      
   
    20 CONNECT (P H s) e c   --> ([connwait:socket.nil] s) e c
    Try tcp connection to host with ip address H on port P
            
   These new commands creates new IO object (connwait).
   They are implemented in secd_tcp.pp unit.
   
   RECV is changed to work with this new type:

    9 RECV  
    (Connwait s) e c --> ((socket(Connwait) s) e c)
    Receive tcp connection from listener or connection try

2. Appropriate lisp commands are defined:

   (listen maxconn port) returns new TCP listener.
   (connect host_ip port) returns new connection_try to host_ip.

3. New examples server.lisp and client.lisp are defined for
   tests. client.lisp is placed in new subdirectory client
   to allow proper writing to file secd.log by SECD meta_machine.
   (now i am starting more than 1 copy of the secd machine).
   The proper usage is:

   in main directory (server): ./secd server

   In new console (client):    cd client
                               ../secd client

   
4. Some changes are made in GetLex meta_procedure to work 
   properly. Tests works fine, but getlex mechanism hides
   some characters (CR, LF, space). My current IO commands
   SEND and RECV uses only lexemes. 

5. New IO commands are defined:

   SENDC and RECVC are same as SEND/RECV but they transfers
   a simple character to/from stream.

6. Lisp functions sendc/recvc are defined and client.lisp
   is changed to use these new functions.

7. force function is moved from shell.lisp to system.lib.

8. shell.lisp is integrated with server.lisp into new
   program shelld.lisp

9. Now you may start 

   ./secd shelld 

   and then start different number of clients (i have 2
   subdirectories - client and cli_1). Any started client
   creates new connection to shelld and starts standart
   lisp read-eval-print loop.

   The problem is that there is now any error handling in the
   current system. If some of the clients is canceled, all
   the shelld and other clients hang up. Now i have no any idea
   how to implement clean and pure error handling mechanism.

10. Some primitive error handling is started for function
   read in system.lib. After this shelld kills properly
   processes trying to read from broken connections.

11. Old subdirectory misc is renamed to System and here are
   placed lisp programs with system programming behavior:
   shell.lisp, sh_pr.lisp, server.lisp, client.lisp ...
   
----------------------------------------------------------

Next machine is RTL_0.

======================  RTL_0/Changes.txt  ======================

This machine inherits Socket_0.

----------------------------------------------------------


   Implementation of the Run Time Library (RTL):


1. New lisp function is defined into compiler.lib:

   (env) - returns the node <lexical_scope.environment>.
   
   lexical_scope is the lexical environment into the
   moment of the evaluation (this scope is the value of the
   variable n into the main compilation function comp).
   
   environment is the content of the E register into the 
   moment of the evaluation.

   The result of this new function is not printable - the
   environment may contain closures (as a result of letrec),
   which are circular lists.

   The (env) function is defined to allow implementation of
   dynamic libraries. In this machine it is used for 
   implementation of the RTL.

2. First test rtl.lib is defined - it is copy of numbers.lib
   with some minor changes. The syntax of the rtl.lib must be:

   (letrec (letrec ... (letrec 
      (env)
      .... 
   ))...)   

3. New program complib.lisp is writen. It reads the file 'rtl.lib',
   compiles it withowt any tail actions and then write the result
   into file 'rtl.sec'.

4. shelld.lisp is changed - it starts with reading the file 'rtl.sec',
   evaluate it and store the result in local variable rtl.
   eval function is changed to compile the expressions into the rtl
   environment (old version of eval compiles expressions into nil 
   environment). Now we may use the functions, defined into rtl.lib
   in the same maner as system functions, defined in compiler.
   shelld also prints into the server console the secd code of the
   online compiled expression.

   If you start 2 consoles - one with the shelld, other with client,
   the following session is possible:

   On server console:

./secd shelld
Reading code shelld.secd  ...
Executing code ...
 (#ldc 3)

 (#ldc 3 #ldc 4 #add)

 (#delay
   (#ld_1_3 #trrec_app_0)
  #ldc 10 #ld_1_1 #trrec_app_2)

 (#delay
   (#ld_1_3 #trrec_app_0)
  #ldc 12 #ld_1_0 #trrec_app_2)



   On client console:

../secd client
Reading code client.secd  ...
Executing code ...
conn_established
SEC>3
3
SEC>(add 3 4)
7
SEC>(GetNth 10 (Primes))
31
SEC>(First 12 (Primes))
(2 3 5 7 11 13 17 19 23 29 31 37)
SEC>


5. These versions of rtl.lib and shelld.lisp are saved in 
   subdirectory rtl_numb.

6. More complex rtl is started. In subdirectories from rtl_0
   to rtl_5 is defined RTL for system usage - it contains old
   system.lib, compiler.lib and new functions for file compilation
   and self_compilation, and also a mini OS definition. The self-
   compilation of new versions of RTL is complex and i will not 
   explain it here (i have a full copy of development files).

   The last version of the RTL - rtl_5 will be used in next machines 
   in place of the old meta_programs 'self' and 'comp'.

   RTL is more complex from previous rtl_numb in two directions:

   - it includes special variable 'self' at top level of the
     lexical scope. This variable is a node <lex_scope.closure> where
     lex_scope represents the lexical scope of the rtl itself and 
     closure is the register E (closure at the moment of evaluation
     of (env) function from rtl.lsp). 'self' is used from rtl functions
     such as 'eval' and 'comp_lsp'.

   - RTL is defined as (lambda (input output) ...). The variables
     input and output are binded into the lowel level of the
     lexical scope of the RTL and are accesible for all it functions.
     This allow to link RTL with different paralel proceses and each
     process may link itself with specific input/output actual values. 
     The list of these variables (input output) may be treated as 
     environment for processes, accesible from the linked with it 
     thread of the RTL.

   The relations into the mini OS are defined in program init.lsp:

   - rtl_cod contains the code of the RTL
   - sh_loop contains the shell loop code definition.
   - first the listen socked is created, then 2 processes are 
     started - listener for arriving connections 'accept' and
     console shell loop 'syscon'.
   - for each new connection new thread of RTL is started and binded
     with its i/o streams, then the shell loop is started into this
     new environment. These thinks are done by 'handle' function.

7. New secd code STAT and lisp function (stat x) are defined for
   statistics. The STAT prints into file secd.log the current state
   of the SECD machine and do nothing with SECD registers.

8. All intermediate files are removed (incl. subdir rtl_0 .. rtl_4)
   to save space.  

----------------------------------------------------------

Next machine is Base_2.


======================  Base_2/Changes.txt  ======================

This machine inherits RTL_0.

----------------------------------------------------------

1. Many changes in package usage, with minor changes
   into different programs:

   - pascal meta programs are moved into 'meta' subdirectory
   - old metaprograms self.pp and comp.pp are removed. 
     The same functionality you may get from shell functions:
     
     (comp_self) - selfcompilation of the miniOS. It is good to
                   have a backup copy for the main fail in miniOS:
                   
                   client.sec   init.sec     rtl.sec    shell.sec
                   client.lsp   init.lsp     rtl.lsp    shell.lsp
                   compiler.lib sysboot.lib  system.lib

     (comp_lsp fn) - compiles file fn.lsp to code fn.sec in 
                   RTL environment. The file suffices are changed 
                   to remind for some minor differences with
                   previous model - now the programs are compiled
                   as expressions not as a functions ((#app #stop) 
                   code is not placed at the end of the program).
                   --------
                   Example: (comp_lsp (quote fac))

     (comp_lex fn scope) - compiles fn.lsp to fn.sec in specified
                   lexical scope (nil if no initial scope).

     (exec fn) -   executes code fn.sec
                   --------
                   Example: (exec (quote fac))  

   - make_all script is changed to start './secd init' after 
     compilation of the self.pp. Thus, the miniOS is started.
     If you want to start more client consoles to miniOS, open
     new console, go to subdirectory cli_0 or cli_1 and type:

     ../secd client

   - many of previous *.lisp programs are removed.  


2. I started changes in all examples. The goal is to make them
   compatible with miniOS. Examples from subdirectory Numbers
   works with minor changes, but non-deterministic examples 
   from subdirectory Examples causes problems. 

   pitagor.lisp is changed to pitagor.lsp with some tricks - the
   spooler function counts the number of paralell process to 
   understand when they are all finished to stop itself. This 
   technique depends on implementation of internal pipes and is not
   good.

   The examples such as pitagor.lsp or pitlazy.lsp are implemented for
   tests only. If you want to evaluate fast the pitagorean triples,
   use the program pitfast.lsp from Numbers subdirectory. It uses
   23 century old idea (known from Euclid's Elements) how to construct 
   these triples.

3. My old pipes implementation is not completely lazy, and now it is 
   changed to be. In old machines, process who send the massage to
   passive pipe is placed in pending queue. Now such process is 
   placed itself into pipe queue, so it sleeps until the pipe handler
   receives the message. 

4. There is an error in my secd_mem.pp unit, but i can't fix it.
   Where some big lazy program provokes the mark/release collector,
   sometimes it happens that C register contains noncorect program
   after some SECD steps. If you lokate small example with this
   bug, send me a message.

5. Old doc files are changed and new are writen (all in HTML format).
   These docs are placed in subdirectory 'html'.

----------------------------------------------------------

Next machine is Error_0.

======================  Error_0/Changes.txt  ======================

This machine inherits Base_2.

----------------------------------------------------------

1. Error handling is started. In this machine goal is to
   check for compilation errors. Special mechanism is 
   implemented to allow breaking compilation. This mechanism 
   is defined in function sys_comp - compilation is started 
   in paralel with some waiting process. If the compilation is
   succesful, it sends the result to syspipe, else the error
   message is printed and some standard code is send to syspipe.
   In all cases after sending the code to syspipe, compilation
   process is killed.
   Thus, the compiler work in breaking mode.

2. Some errors are handled:

   - binding error: when variable is not found in lexical
     scope, it can't be bound with value. This error is 
     handled in compiler function 'location'.

   - primitive functions are tested for correct number of
     actual arguments in function 'test_cnt'.

   - it is difficult to test special functions for correct
     number of parameters in a flexible way, so i started implementation
     of 'case' selector and other thinks:

3. Some changes are started in all parts of the package to
   allow more flexible compilation:

   a) constants, representing true and false are changed from
      atoms T / F to integers 0 / 1.

   b) new SECD codes are defined:

    5 CASE_k       if i in [0..k-1] then c_i:=ci else c_i:=ck
                   (i s) e (c0 ... ck c) --> (c_i s)  e c
                   
    8 CALL  if c=nil
             then   (c' s) e nil     --> s       e c'
             else   (c' s) e c       --> (e c s) e c'
                               
   c) compilation of 'if' function is changed to use sequence:
      ... rec_exp0 #case_1 then_exp else_exp #call ...
      new compilation must produce a little longer code, but 
      with the same meta_cons complexity.

   d) codes SEL and TR_SEL are removed from the SECD machine. 


   e) new LISP function (case i e0 ... ek eF) is defined.
      It returns ei if i is in [0..k] and eF otherwise.
      
   f) new SECD code is defined (more simple fork):

   13 FORK0 s e (c1 c2 c)  --> (c1 s) e c
                               r0 --> (((c2 s) e c) r0)
                                      
   g) LISP compilation of fork is changed to use sequence
      ... #fork0 exp1 exp2 #call ...
      new compilation produce a little longer code and
      make 1 additional meta_cons, but it simplifies the
      SECD machine definition.

   h) old codes FORK and TR_FORK are removed.  
      FORK0 is renamed to FORK.

   i) new function (seq e1 e2) is defined. It force 
      evaluation of e1, then ignore the result and
      evaluates e2. This function is used to replace
      (do X e1 e2) in places, where X is not used in e2.


   j) in most of the programs (do x e1 e2) is replaced
      with (seq e1 e2) if possible. New programs saves meta_conses,
      but are longer -current implementation of seq is the same as
      (case e1 e2). 

   k) new code POP is defined for SECD machine:   

   14 POP  (x s) e c  --> s e c

      and 'seq' is compiled using POP to produce shorter code. 

4. Info about new functions 'case' and 'seq' is added in
   pure_LISP reference.


----------------------------------------------------------

Next machine is Error_1.

======================  Error_1/Changes.txt  ======================

This machine inherits Error_0.

----------------------------------------------------------

1. Main compiler functions are completely rewriten to use
   binary tree structure, containing info about the compiler
   functions. This tree is created from file 'sysfun.lst'.

   Each sublist in the tree (called c_tree) has the form:

   (name type pcnt code ctype) where:

   - name is the name of the function
   - type is 0 for primitives and 1 for special functions
   - pcnt is nil if function has variable count of args,
          or is the number of its formal parameters.
   - code is SECD code for primitive functions or
          compiler index for special functions.
   - ctype is 0 if the function is realy primitive or
          nil for pseudoprimitives like send/recv.

2. New compiler is tested. It is faster and smaller than
   previous version and checking for correct count of
   parameters is very easy.

3. Most of the syntax errors are checked during the compilation.


----------------------------------------------------------

Next machine is Shell_2.

======================  Shell_2/Changes.txt  ======================

This machine inherits Error_1.

----------------------------------------------------------

1. rtl.lsp and init.lsp are simplified. Now shell.lsp is 
   not needed as part of the miniOS and is removed.

2. rtl.lsp and init.lsp are replaced with miniOS.lsp -
   more simple program. sysboot.lib is not needed and is 
   removed.

3. Minor change in implementation for replace of the
   evaluated recipe in RTN code - if the result is a node,
   the replaced recipe is returned as value. Thus the   
   returned lazy result is unified, allowing IO objects
   to be generated in more lazy way.

4. Some runtime error handling is started:

   - err_handler function is defined in miniOS. It must be
     the last element of the last level of E register.

----------------------------------------------------------

Next machine is Error_2.

======================  Error_2/Changes.txt  ======================

This machine inherits Shell_2.

----------------------------------------------------------

1. RunTime error handling in SECD machine:

   - when some runtime error ocures, the current state of the
     process is saved in list (#err_num S E C). This list
     is passed as only parameter of the function err_handler.

   - function err_handler must be the last element of the last 
     sublist of E regitser. It starts a new shell for the
     same user, passing to this shell the error state - nSEC. 
     If new shell receives non-nil nSEC it prints the info 
     about the error and then starts normal shell loop.

   - more runtime errors are handled by this mechanism but 
     some are not handled - like 'node heap overflow',
     'garbage collector stack overflow' and other errors,
     consuming some important resource. After such errors
     continuation of the evaluations is very difficult.

   - after each runtime error the meta_machine stack 
     (Pascal internal stack) must grow by little. This is a 
     result of current implementation of the pascal procedure
     RTError. It calls recursively secd_loop, leaving some
     unused control info into the stack. May be it is possible
     more clear implementation, but some break point (or
     exception handling) in pascal must be used. I'm not
     familiar with such things.

2. File errors.lst contains some messages about handled
   runtime errors. It is is used in miniOS.

3. The resulting error handling is not very good - 
   it is not flexible, but i can't invent someting beter now.
   The mechanism in miniOS for run time error handling is
   similar to compiler error handling and the corresponding 
   changes are made in miniOS.lsp.

4. New SECD code EOF test for end_of_file or broken/closed connection:

   59 EOF  (f s) e c  --> (eof?(f) s)  e c  

   This code tests if the stream (file or TCP connection) is 
   closed.

5. New lisp function (eof stream) is added and used in miniOS.lsp
   and client.lsp to check for closed connections.

----------------------------------------------------------

Next machine is Base_3.

======================  Base_3/Changes.txt  ======================

This machine inherits Error_2.

----------------------------------------------------------

1. SECD code FCLOSE is expanded to close properly TCP
   connections. It also sets stream pointer to nil.  

2. (fclose stream) function is used in miniOS to leave
   meta_system resources when TCP connection is broken.

3. All stream meta functions are changed to produce runtime
   error if their argument is a nil stream pointer.

4. html documentaion is changed to be adequate to current
   pure_LISP version.     

----------------------------------------------------------

Next machine is ?????.

