LISPy things you can do in 64K bytes of core

System Initialization and First Steps

The core of the Kilo LISP system compiles to a PCDOS .COM file of 12.6K bytes using Turbo C 2.0. It can probably be compiled to a smaller binary using a compiler that is optimizing more aggressively. For example, the Mark Williams C compiler on the Coherent 3.2 operating system for 80286-based PCs gets the size down to 10.1K bytes. The DOS version will be used below.

The first step after compilation of the core system is system initialization, i.e. the creation of an image file containing the parts of the system that are written in LISP. Image files were part of LISP from the beginning [1], and when using Kilo LISP on a 4.77MHz IBM PC it becomes clear why this is a good idea.

The LISP part of the Kilo LISP source code has a size of less than 5000 bytes, but it takes 18 seconds to load. The image file that is created during system initialization contains the entire cons pool of the system plus some additional variables that are necessary to restore the state of the system from the file. Once the system can be loaded from the image file, start-up time decreases from 18 to 0.5 seconds.

C:\KLISP> ls -l klsrc
-rw-  03-05-119  13:48      4644  klsrc

C:\KLISP> kl
* (load 'klsrc)  ; load the LISP part of the system
t

* (suspend 'klisp)
t

* ^Z             ; goodbye!

C:\KLISP> kl
* (gc)
6812             ; nodes left for programs

* ^Z

C:\KLISP> ls -l kl.com klisp
-rw-  03-27-119  21:01     12912  kl.com
-rw-  03-27-119  21:02     40973  klisp

C:\KLISP> _

Once the system is ready, there are still 6812 out of 8192 nodes (or cons cells) left to LISP programs. Plenty of space to try some fun things. First a few obvious expressions:

* (cons (quote a) (quote b))
(a . b)

* (car '(1 2 3))
1

* (atom 'foo)
t

* (+ 1 1)
? syntax            ; special characters are not allowed

* (plus 1 2)
? undefined: plus   ; PLUS is undefined

* 1
? undefined: 1      ; so is 1

* _

Very early LISP (and this means early LISP 1.0) did not have any concept of numbers. There were only atoms (symbols) and lists. This is how things are in Kilo LISP, too. The token 1 is just a single-character atom and when it is not bound to any value, it is undefined.

There are still some interesting things you can do with such a system, though! Here is a function that creates a binary tree of a given depth, where the depth is specified as the number of elements in the argument N:

* (setq tree
    (lambda (n)
      (cond ((null n) (quote x))
            (else
              (list (tree (cdr n))
                    (tree (cdr n)))))))
tree

* (tree '(1 1 1))
(((x x) (x x)) ((x x) (x x)))

* _

Here is a naive function for flattening a tree (converting it to a flat list). It can be used to create some arguments for the CONC function, which concatenates lists:

* (setq flat
    (lambda (x)
      (cond ((null x) nil)
            ((atom x) (list x))
            (else (conc (flat (car x)) 
                        (flat (cdr x)))))))
flat

* (setq list16 (flat (tree '(1 1 1 1))))
list16

* list16
(x x x x x x x x x x x x x x x x)

* (conc list16 list16 list16)
(x x x x x x x x x x x x x x x x
 x x x x x x x x x x x x x x x x
 x x x x x x x x x x x x x x x x)

* _

Here is a puzzle that even ancient LISP systems can solve easily on ancient hardware: the Towers of Hanoi. There are three poles and N disks of different diameters, each with a hole in its center. All disks are located on the left pole so that smaller disks are always on top of larger disks. To solve the puzzle, move the disks to the middle pole, by moving one disk at a time from one pole to another and never placing a larger disk on top of a smaller one. Here is an illustration:

      |            |            |
     ###           |            |
   #######         |            |
 ###########       |            |
=======================================
      L            M            R

The following program creates a solution using a simple recursive algorithm: to solve the puzzle for N disks from L to M via R, solve it for N-1 disks from L to R via M, then move one disk from L to M, and then solve for N-1 disks from R to M via L.

* (setq hanoi
    (lambda (n x y z)
      (cond ((null n) nil)
            (else (conc (hanoi (cdr n) x z y)
                        (list (list x y))
                        (hanoi (cdr n) z y x))))))
hanoi

* (hanoi '(1 1 1) 'l 'm 'r)
((l m) (l r) (m r) (l m) (r l) (r m) (l m))

* (hanoi '(1 1 1 i i) 'l 'm 'r)
((l m) (l r) (m r) (l m) (r l) (r m) (l m) (l r)
 (m r) (m l) (r l) (m r) (l m) (l r) (m r) (l m)
 (r l) (r m) (l m) (r l) (m r) (m l) (r l) (r m)
 (l m) (l r) (m r) (l m) (r l) (r m) (l m))

* _

Solving puzzles is fun, but are the any more serious things you can do in 64K bytes of core?

contact  |  privacy