jart/sectorlisp

Bootstrapping LISP in a Boot Sector

sectorlisp

sectorlisp is a 512-byte implementation of LISP that's able to bootstrap John McCarthy's meta-circular evaluator on bare metal.

Overview

LISP has been described as the Maxwell's equations of software. Yet there's been very little focus to date on reducing these equations to their simplest possible form. Even the original LISP paper from the 1960's defines LISP with nonessential elements, e.g. LABEL.

This project aims to solve that by doing three things:

1. We provide a LISP implementation that's written in LISP, as a single pure expression, using only the essential functions of the language. See lisp.lisp. It's the same meta-circular evaluator in John McCarthy's paper from the 1960's, except with its bugs fixed, dependencies included, and syntactic sugar removed.

2. We provide a readable portable C reference implementation to show how the meta-circular evaluator can be natively bootstrapped on POSIX conforming platforms, with a pleasant readline-like interface. See lisp.c.

3. We provide a 512-byte i8086 implementation of LISP that boots from BIOS on personal computers. See sectorlisp.S. To the best of our knowledge, this is the tiniest true LISP implementation to date.

Getting Started

See lisp.lisp for code examples that you can copy and paste into your LISP REPL.

You can run the C implementation as follows:

$ make
$ ./lisp

After running make you should see a sectorlisp.bin file, which is a master boot record you can put on a flopy disk and boot from BIOS. If you would prefer to run it in an emulator, we recommend using Das Blinkenlights.

curl --compressed https://justine.lol/blinkenlights/blinkenlights-latest.com >blinkenlights.com
chmod +x blinkenlights.com
./blinkenlights.com -rt sectorlisp.bin

Alternatively you may use QEMU as follows:

qemu-system-i386 -nographic -fda sectorlisp.bin

Further information may be found on our wiki.

Demo

The video above demonstrates how to boot sectorlisp in the blinkenlights emulator, to bootstrap the meta-circular evaluator, which evaluates a program for finding the first element in a tree.

You can watch the full demo on YouTube.

sectorlisp's Issues

Code reduction suggestion

Are you accepting improvements? I have found your project on HN in the comments to miniforth, where I helped reduce the size.

I think that "Intern" can take less bytes (about 10):

Intern:	mov	bx, di
	mov	si, $STR
0:	mov	di, bx
	push	si
	lodsb
	test	al, al
	jne	2f
	pop	di
	push	di
	mov	si, bx
4:	lodsb
	stosb
	test	al, al
	jnz	4b
6:	pop	ax
	sub	ax, $STR
	shl	ax
	ret

1:	lodsb
2:	scasb
	jne	5f
	test	al, al
	jne	1b
	jmp	6b

5:	pop	di
3:	test	al, al
	jz	0b
	lodsb
	jmp	3b

Sorry for using Intel syntax, I found it much easier to read because I have been writing with this syntax for years.
Also I haven't tested this code (except inside of my mind).

Is there a function reference or any help at all?

Hi :)

This project is great BUT I cannot figure out how lambda works, I understand C but cannot find lambda in lisp.c so that didn't help..

the lisp.lisp file is the only example i can find on the internet, but it's complex and I cant understand it. I thought there would be some simple examples in rossetta code but there wasn't ..

All I'm asking is a simple documentation that lists all the functions within SectorLisp, and explains them in a few sentences.

By the way, since I cant read assembly, are the core functions these (CONS CAR CDR QUOTE ATOM EQ LAMBDA COND) or there are more builtin?

And sometimes (when using ./lisp) the interpreter stops outputting stuff, I have to restart it.. what causes those? I cant seem to figure when it's happening (EDIT: it happens when the previous lines don't have matching braces)

Thanks for reading :)

`(EQ (QUOTE A) (QUOTE A))` evaluates to a null string

Evaluating (EQ (QUOTE A) (QUOTE A)) produces the following output:

(EQ (QUOTE A) (QUOTE A))

Where nothing is printed.

I confirmed this by running the test in ./test as follows:

git clone https://github.com/jart/sectorlisp && cd sectorlisp
make
cd bin && mv sectorlisp.bin sectorlisp.bin.old && mv ../sectorlisp.bin .
cd ../test
make

I found out that ./bin/sectorlisp.bin has a longer byte length from what is built by make, and seems to be an older version. When I ran the test with the old version ./bin/sectorlisp.bin, the expression properly evaluated to T. However, in the new binary built with make, the interpreter showed a null string as I mentioned above.

Referencing bound variables in lambdas crashes the interpreter in QEMU

Evaluating the following expression in QEMU using make test1 crashes the interpreter:

((LAMBDA (B) B)(QUOTE C))

When this expression starts being evaluated, the interpreter stops running and no output or input prompts occur afterwards.

The following expressions do work:

((LAMBDA () (QUOTE A)))
((LAMBDA (B) (QUOTE A))(QUOTE C))

The difference here is whether the bounded variables are referenced or not, so it seems that referencing bounded variables in lambdas are currently failing.

Since variable bindings do not work, the metacircular evaluator in ./test/eval10.lisp and eval15.lisp doesn't work as well.

This issue does not happen at all in Blinkenlights, so it may be an x86 forward compatibility issue.

Embedding (QUOTE (A . B)) in the metacircular evaluator is causing a segfault

I'm getting segfaults when trying to run the following simple program embedded in the metacircular evaluator as run by lisp.c. I've tried on a Raspberry Pi and Mac OS X. It works if I remove the dot. So (A . B) segfaults, but (A B) works as expected. Typing it into the REPL works:

• (QUOTE (A . B))
  (A∙B)

I'm not sure if it's legal or not but the C eval is working differently than the metacircular eval for this case.

Here's the head of the embedded version:

((LAMBDA (ASSOC EVCON PAIRLIS EVLIS APPLY EVAL)
(EVAL (QUOTE (QUOTE (A . B))) ())
)

(QUOTE (LAMBDA (X Y)
(COND ((EQ Y ()) ())
((EQ X (CAR (CAR Y)))
...

Fails to build with GNU as from binutils 2.35.1

cc    -c -o start.o start.S
cc  -g -fno-pie -Os -D__REAL_MODE__ -wrapper ./realify.sh -ffixed-r8 -ffixed-r9 -ffixed-r10 -ffixed-r11 -ffixed-r12 -ffixed-r13 -ffixed-r14 -ffixed-r15 -mno-red-zone -fcall-used-rbx -fno-jump-tables -fno-shrink-wrap -fno-schedule-insns2 -flive-range-shrinkage -fno-omit-frame-pointer -momit-leaf-frame-pointer -mpreferred-stack-boundary=3 -fno-delete-null-pointer-checks -c -o lisp.real.o lisp.c
/tmp/ccy4ZtIH.s: Assembler messages:
/tmp/ccy4ZtIH.s:189: Error: incorrect register `%dx' used with `l' suffix
/tmp/ccy4ZtIH.s:275: Error: incorrect register `%bx' used with `l' suffix
/tmp/ccy4ZtIH.s:355: Error: incorrect register `%bx' used with `l' suffix
/tmp/ccy4ZtIH.s:393: Error: incorrect register `%dx' used with `l' suffix
/tmp/ccy4ZtIH.s:979: Error: incorrect register `%ax' used with `l' suffix
/tmp/ccy4ZtIH.s:1080: Error: incorrect register `%ax' used with `l' suffix
make: *** [Makefile:60: lisp.real.o] Error 1
$ cc --version
cc (Ubuntu 10.2.0-13ubuntu1) 10.2.0
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ file (which cc)
/usr/bin/cc: symbolic link to /etc/alternatives/cc
$ file /etc/alternatives/cc
/etc/alternatives/cc: symbolic link to /usr/bin/gcc

What compiler & version are you using?

Fails to build with GCC on CentOS 7

On a fresh clone of the main branch as of today:

% make
cc -w -Os   -c -o lisp.o lisp.c
cc -w -Os   -c -o bestline.o bestline.c
In file included from /usr/include/sys/stat.h:106:0,
                 from bestline.c:146:
/usr/include/bits/stat.h:91:21: error: field ‘st_atim’ has incomplete type
     struct timespec st_atim;  /* Time of last access.  */
                     ^
/usr/include/bits/stat.h:92:21: error: field ‘st_mtim’ has incomplete type
     struct timespec st_mtim;  /* Time of last modification.  */
                     ^
/usr/include/bits/stat.h:93:21: error: field ‘st_ctim’ has incomplete type
     struct timespec st_ctim;  /* Time of last status change.  */
                     ^
In file included from bestline.c:146:0:
/usr/include/sys/stat.h:373:54: error: array type has incomplete element type
 extern int futimens (int __fd, const struct timespec __times[2]) __THROW;
                                                      ^
make: *** [bestline.o] Error 1

I think it can be fixed just by adding #include <sys/time.h> before #include <sys/stat.h> on bestline.c?

Inconsistency between lisp and sectorlisp.bin quote

The program "lisp" behaves differently from sectorlisp.bin which, I believe, is unintended.
Output of lisp:

THE LISP CHALLENGE V1
VISIT GITHUB.COM/JART
(QUOTE (1 1))
(1)
(QUOTE (1 1))
(1 1∙NIL)

Output of sectorlisp.bin when run with qemu-system-x86_64 -nographic -fda sectorlisp.bin:

SeaBIOS (version d55cb5a)


iPXE (http://ipxe.org) 00:03.0 CA00 PCI2.10 PnP PMM+07F91660+07EF1660 CA00
                                                                               


Booting from Hard Disk...
Boot failed: could not read the boot disk

Booting from Floppy...
(QUOTE (1 1))
(1 1)
(QUOTE (1 1))
(1 1)
QEMU: Terminated

What's the runtime memory footprint of SectorLisp?

Hi @jart , jaw-dropping work!

What's the typical runtime memory footprint when it is loaded?

Recursion in EVLIS has an extra A parameter

I was taking a close look at this file to understand the implementation, and noticed this minor typo. It doesn't seem to have an impact on the execution, but it would be nice to fix if I'm right.

Currently the recursion looks like this:
(EVLIS (CDR M) A A)

I believe that the 2nd A parameter is extraneous:
(EVLIS (CDR M) A)

Also time permitting it would be nice to elaborate on the two "NOTE:" items labeled "IS NICE" and "CAN HELP" at the top of the file. Are these checks which can be added to the first COND in EVAL? Are they not in the code because of size of performance reasons? Or because they weren't in McCarthy's paper?