pLISP
© '98 Thomas Mahler

pLisp to Combinatory Logics Compiler

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:[email protected]
http://www.techno.net/pcl/tm

About the Compiler

The following defines a compiler from lisp to combinatory logics.
The combinator objects (binary trees) can be reduced very efficiently.
Generally a compiled function is smaller in size than the uncompiled version
and computing is about 10-20 times faster.

If a function takes more than 2 or 3 arguments, the size of the compiled code will grow and the computation will be slower than for a unary or binary function.

There has been lots of research on variable abstraction algorithms that don't produce output growing with the number of args.
Our System provides support for several well known algorithms but is ready for experimentation with different algorithms, as the abstraction and optimization algorithms are passed as higher order function parameter. (see definition of cf for details) My own research showed that the smallest Code must not be also the fastest: The algorithm babstr is suboptimal regarding output size, but the object code is much faster than that of Cabstr.
Thus the main compile function cf assumes babstr as default.

Algorithms are taken from 'A. Diller, Compiling functional languages' and 'S.L. Peyton Jones, The Implementation of Functional Programming Languages' exact references are given in comments at the respective algorithms below.

see the Combinator Lisp homepage for details on the concepts: http://www.techno.net/pcl/tm/plisp

usage: (cf 'my-fun) compiles lambda body to combinator machine code.
note: function must be quoted: 'my-fun !
uncompile: (uncompile 'my-fun) restores original definition of my-fun

You can play with compiling, uncompiling and executing some simple functions in the file basics.html

Commented Source code

 // define some minor functions used within the compiler
 (define or
  (lambda (x y) 
     (if x 
          1 
          (if y 1 0))))
 (define and
    (lambda (x y)