====================== 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 , 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 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 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 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 Kernel_0. ====================== Kernel_0/Changes.txt ====================== This machine inherits Base_3. ---------------------------------------------------------- 1. This machine is cross system to the next. Now i start works for spliting the current SECD model into 2 parts: - hard machine SECK: single task, strict and asynch I/O low level machine with only 4 registers S E C and K (kernel). It will be used for implementing more komplex soft machine. - soft machine SEC: it will be similar to the machine from Base_3, but all multitasking and I/O actions will be interpreted by some strict_LISP kernel on SECK machine. 2. strict_LISP low level compiler is defined with only purpouse to compile the future kernel. 3. #rtn code of SECD machine is simplified. (this is possible due to current nil representation of #rtn) New #rtn may be executed in more than 1 SECD loop, but not contains internal loop. 4. New codes are added: - more simple and low-level file handling for SECK model. - special control codes for user-kernel swap. - other kernel codes (setcar, setcdr ...). All new codes except #int_n are usable only in kernel mode. These codes are explained in secd.html page. 5. kernel.sys is the source of the kernel. First version only reads some user code and start it in user mode. 6. Interrupt system is defined. Interrupts from 64 to 127 are for primitive-like codes, interpreted by kernel. 7. The primitive code #fopen is changed with #intr_64 and tested. All seems to be OK. 8. make_all script is changed to start kernel.sec. 9. kernel.sys is completely writen to implement all multitascking and IO handling functions. It is compiled, but tested only for primitive-like interrupts. ---------------------------------------------------------- Next machine is Kernel_1. ====================== Kernel_1/Changes.txt ====================== This machine inherits Kernel_0. ---------------------------------------------------------- 1. All changes in SECK machine are made and tested. r0, r1 and io registers are erased. Now all multitasking and IO actions are handled by the strict_LISP kernel. 2. Current model is strictly equivalent to Base_3 in high-level aspects (pure_LISP language semantics), but implementation differ - in Base_3 multitascing and asynchronous IO are integrated into SEC model, while current SECK is single-task machine with interrupt system, allowing old SEC semi-interpretation by the kernel. 3. Current model is 2-3 times slower than Base_3 for some programs like selfcompilation. I started some analysis how to speed up the kernel: - Task sheduling consumes many resources if the Shedule_Limit is low (127 in Base_3). I changed it to 511 and losses decreased under 10%. This is tested in massive evaluation example prmember. - For queens Base_3 is about 50% faster than SECK. - IO operation may be interpreted faster, but now there is a good isolation of all IO handling in kernel and i will not change this (selfcompilation is 2.3 slower than Base_3). 4. I found s serious bug in Lazy_Ref_Count Garbage Collector and i think that i fixed it. Don't use previous versions !!! ---------------------------------------------------------- Next machine is Cache_3. ====================== Cache_3/Changes.txt ====================== This machine inherits Kernel_1. ---------------------------------------------------------- 1. Reorganization of pascal sources: - sec_codes.pp defines the SECK machine. - sec_lists.pp defines the list space meta functions and garbage collectors. - sec_atoms.pp defines the atom space meta functions. - sec_drivers.pp defines all meta IO functions. 2. Cache for register E is implemented: The cache consist of one new register - L (local vars) and flag CacheE. CacheE saves the cache state - active (L holds local vars) and passive (L is not used). Register L cached the first element of E register. SECK without SECK with E cache (old) E cache (new) CacheE=false E <=====> E CacheE=true E=(l e) <=====> L=l; E=e 3. The cache for E is coded in implementation part of the program sec_codes.pp. Noting changes in other Pascal and Lisp programs. 4. Cache for S is rewriten to allow k-level cache (in current version cache use 12 registers). New cache implementation is tested. It decrease the meta_cons usage with 10-20% (compared with Kernel_1), but the real speed of my SECK machine is not changed significantly. This is due to many pascal calls. To increase the speed, some small and widely used pascal procedures/functions must be replaced by macros. I made some of macros, needed to speed up the SECD machine. After the changes it works about 20% faster. New subdirectory test is created and some shell scripts in it for speed tests. 5. secd.html is updated. ---------------------------------------------------------- Next machine is Base_4. ====================== Base_4/Changes.txt ====================== This machine inherits Cache_3. ---------------------------------------------------------- 1. New code is added to allow parameter passing during the kernel start. 89 #parstr (n.s) e c --> (paramstr(n).s) e c Kernel is changed to use this code. 2. ---------------------------------------------------------- Next machine is ????.