pLISP
© '98 Thomas Mahler

SECD Compiler for LISPKIT Lisp

Preliminaries

Copyright: Copyright © 1998 ICS Institut fuer Cybernetic und Systemtheorie, Bochum, Germany. All rights reserved.
Copyright © 1997,98 Thomas Mahler
This is copyrighted software. By using the software, you agree to the following terms and conditions.
1. License for personal non-commercial use.: You may use the software only for your personal, noncommercial use.
2. No redistribution.: You may not distribute copies of the software to others. You may not place the software on any web site, Internet server, electronic bulletin board, or other information retrieval systems.
3. No warranty.: THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT WARRANTY OF ANY KIND. TO THE MAXIMUM EXTENT PERMITTED BY LAW, THE AUTHOR DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
4. Disclaimer.: IN NO EVENT WILL THE AUTHOR BE LIABLE TO YOU FOR ANY DAMAGES, INCLUDING ANY LOST PROFITS, LOST SAVINGS, OR OTHER INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE.
5. Notice of experimental software.: THIS SOFTWARE CONTAINS PROGRAMS OF AN EXPERIMENTAL NATURE, INCLUDING PROGRAMS THAT HAVE NOT BEEN FULLY TESTED. YOU AGREE TO ASSUME ALL RISKS INVOLVED IN THE USE OF EXPERIMENTAL AND UNTESTED SOFTWARE.
6. General.: For commercial use or if you intend to modify the code and to distribute modified code please contact the author:
mailto:thomas.mahler@essen.netsurf.de
http://www.techno.net/pcl/tm

Bootstrapping the SECD Compiler

The functional language LispKit, the SECD VM and the Liskit-to-SECD Compiler have been impressively described by P. Henderson in his classic "Functional Programming: Application and Implementation", 1980, Prentice Hall.
The Compiler for P. Hendersons LISPKIT to SECD Code has been included into this package as an example how to use PLISP to perform some more complex tasks. The compiled code CANNOT be used with the PLISP VM!
To see this Code working experiment with Chris Waltons webbased SECD implementation at: http://www.dcs.ed.ac.uk/home/cdw/MyProjects/SECD/Applet/lispkit.html.
In this example file you find an example how the SECD compiler can be utilized for bootstrapping new versions of the SECD Compiler itself:
COMPILE is called with the source code of the original SECD Compiler in LISPKIT syntax.
After executing this file (press Ctrl-R) you can find the result of compiling the Compiler in the global variable LISPKIT-OBJECT-CODE
The generated Objectcode (LOB in Henderon's terminology) can be executed on a SECD VM to compile any new LispKit Sources (LSO acc. to Henderson).
Obviously it is then possible to compile the original LISPKIT compiler (or modified versions) on the SECD VM itself. (See Hendersons book on further details of this bootstrapping concept)

Let's try to trap the boots...


 // load the secd compiler, defines toplevel function COMPILE 
   (load "secd-compiler.html")

 // set printing flags to allow complete output 
   (printdepth 500) 
   (printlength 500)

 // Assign Source Code of LISPKIT Compiler to Variable LISPKIT-SOURCE 
 (setq LISPKIT-SOURCE
 '(LETREC COMPILE
  (COMPILE LAMBDA (E)
    (COMP E (QUOTE NIL) (QUOTE (4 21))))
  (COMP LAMBDA (E N C)
    (IF (ATOM E)
        (CONS (QUOTE 1) (CONS (LOCATION E N) C))
    (IF (EQ (CAR E) (QUOTE QUOTE))
        (CONS (QUOTE 2) (CONS (CAR (CDR E)) C))
    (IF (EQ (CAR E) (QUOTE ADD))
        (COMP (CAR (CDR E)) N (COMP (CAR (CDR (CDR E))) N (CONS (QUOTE 15) C)))
    (IF (EQ (CAR E) (QUOTE SUB))
        (COMP (CAR (CDR E)) N (COMP (CAR (CDR (CDR E))) N (CONS (QUOTE 16) C)))
    (IF (EQ (CAR E) (QUOTE MUL))
        (COMP (CAR (CDR E)) N (COMP (CAR (CDR (CDR E))) N (CONS (QUOTE 17) C)))
    (IF (EQ (CAR E) (QUOTE DIV))
        (COMP (CAR (CDR E)) N (COMP (CAR (CDR (CDR E))) N (CONS (QUOTE 18) C)))
    (IF (EQ (CAR E) (QUOTE REM))
        (COMP (CAR (CDR E)) N (COMP (CAR (CDR (CDR E))) N (CONS (QUOTE 19) C)))
    (IF (EQ (CAR E) (QUOTE LEQ))
        (COMP (CAR (CDR E)) N (COMP (CAR (CDR (CDR E))) N (CONS (QUOTE 20) C)))
    (IF (EQ (CAR E) (QUOTE EQ))
        (COMP (CAR (CDR E)) N (COMP (CAR (CDR (CDR E))) N (CONS (QUOTE 14) C)))
    (IF (EQ (CAR E) (QUOTE CAR))
        (COMP (CAR (CDR E)) N (CONS (QUOTE 10) C))
    (IF (EQ (CAR E) (QUOTE CDR))
        (COMP (CAR (CDR E)) N (CONS (QUOTE 11) C))
    (IF (EQ (CAR E) (QUOTE ATOM))
        (COMP (CAR (CDR E)) N (CONS (QUOTE 12) C))
    (IF (EQ (CAR E) (QUOTE CONS))
        (COMP (CAR (CDR (CDR E))) N (COMP (CAR (CDR E)) N (CONS (QUOTE 13) C)))
    (IF (EQ (CAR E) (QUOTE IF))
        (LET (COMP (CAR (CDR E)) N (CONS (QUOTE 8)
                                    (CONS THENPT (CONS ELSEPT C))))
          (THENPT COMP (CAR (CDR (CDR E))) N (QUOTE (9)))
          (ELSEPT COMP (CAR (CDR (CDR (CDR E)))) N (QUOTE (9))) )
    (IF (EQ (CAR E) (QUOTE LAMBDA))
        (LET (CONS (QUOTE 3) (CONS BODY C))
          (BODY COMP (CAR (CDR (CDR E))) (CONS (CAR (CDR E)) N)
                                    (QUOTE (5))) )
    (IF (EQ (CAR E) (QUOTE LET))
        (LET (LET (COMPLIS ARGS N (CONS (QUOTE 3)
                           (CONS BODY (CONS (QUOTE 4) C))))
               (BODY COMP (CAR (CDR E)) M (QUOTE (5))))
           (M CONS (VARS (CDR (CDR E))) N)
           (ARGS EXPRS (CDR (CDR E))))
    (IF (EQ (CAR E) (QUOTE LETREC))
        (LET (LET (CONS (QUOTE 6) (COMPLIS ARGS M
                         (CONS (QUOTE 3) (CONS BODY (CONS (QUOTE 7) C)))))
               (BODY COMP (CAR (CDR E)) M (QUOTE (5))))
          (M CONS (VARS (CDR (CDR E))) N)
          (ARGS EXPRS (CDR (CDR E))))
    (COMPLIS (CDR E) N (COMP (CAR E) N (CONS (QUOTE 4) C)))))))))))))))))))))
  (COMPLIS LAMBDA (E N C)
    (IF (EQ E (QUOTE NIL)) (CONS (QUOTE 2) (CONS (QUOTE NIL) C))
        (COMPLIS (CDR E) N (COMP (CAR E) N (CONS (QUOTE 13) C)))))
  (LOCATION LAMBDA (E N)
    (LETREC
      (IF (MEMBER E (CAR N)) (CONS (QUOTE 0) (POSN E (CAR N)))
          (INCAR (LOCATION E (CDR N))))
    (MEMBER LAMBDA (E N)
          (IF (EQ N (QUOTE NIL)) (QUOTE F)
          (IF (EQ E (CAR N)) (QUOTE T) (MEMBER E (CDR N)))))
    (POSN LAMBDA (E N)
      (IF (EQ E (CAR N)) (QUOTE 0) (ADD (QUOTE 1) (POSN E (CDR N)))))
    (INCAR LAMBDA (L) (CONS (ADD (QUOTE 1) (CAR L)) (CDR L)))))
  (VARS LAMBDA (D)
    (IF (EQ D (QUOTE NIL)) (QUOTE NIL)
        (CONS (CAR (CAR D)) (VARS (CDR D)))))
  (EXPRS (LAMBDA (D)
    (IF (EQ D (QUOTE NIL)) (QUOTE NIL)
        (CONS (CDR (CAR D)) (EXPRS (CDR D))))))

 ))

 // Compile Source Code and assign result to variable LISPKIT-OBJECT-CODE
 (setq LISPKIT-OBJECT-CODE  (COMPILE LISPKIT-SOURCE))

 // Output Result
 (print (pp LISPKIT-OBJECT-CODE))