Show HN: Extending SectorLISP to Implement Basic REPLs and Games

SectorLISP is an amazing project where a fully functional Lisp interpreter is fit into the 512 bytes of the boot sector of a floppy disk. Since it works as a boot sector program, the binary can be written to a disk to be used as a boot drive, where the computer presents an interface for…

2
Show HN: Extending SectorLISP to Implement Basic REPLs and Games

A screenshot of a BASIC interpreter written for SectorLISP.

SectorLISP is an amazing project
where a fully functional Lisp interpreter is fit into the 512 bytes of the boot sector of a floppy disk.
Since it works as a boot sector program, the binary can be written to a disk to be used as a boot drive,
where the computer presents an interface for writing and evaluating Lisp programs,
all running in the booting phase of bare metal on the 436-byte program.
As it hosts the Turing-Complete language of Lisp,
I was in fact able to write a BASIC interpreter
in 120 lines of SectorLISP code, which evaluates BASIC programs embedded as an expression within the Lisp code,
shown in the screenshot above.

When I first saw SectorLISP and got it to actually run on my machine,
I was struck with awe by how such a minimal amount of machine code could be used to open up the vast ability to
host an entire programming language.
You can write clearly readable programs which the interpreter will accurately evaluate to the correct result.
I find it beautiful how such a small program is capable of interpreting a form of human thought
and generating a sensible response that contains the meaning encapsulated in the inquired statement.

The Issue – Designing Interactions

After writing various programs for SectorLISP, there was a particular thought that came into my mind.
Even after writing the BASIC interpreter, I felt that there was one very important feature that could significantly enhance the capabilities of SectorLISP –
that is, the ability to accept feedback from the user depending on the program’s output,
by designing the interaction between the user and the computer.

The prime example of this is games.
Games are possible to be played on a computer since the player can react depending on the output of the computer.
Of course, even with pure functions as in SectorLISP,
it’s still possible to create a game if we make the user of the program run the same program again
every time the program demands a new input.
The entire history of user inputs can be expressed as a certain list in the program,
and the input and output states can be passed through the course of the entire program,
and the program can stop whenever a required input is not apparent, also showing its accumulated outputs.
However, such an interface that requires repeated inputs is rather inconvenient for the user,
inconvenient in the same sense that IF is inconvenient than COND,
and how lambdas that can take only one argument are inconvenient than lambdas that can take any number of arguments,
both being used to make the experience of the humans interacting with SectorLISP as simple and natural as possible.

When you think about it, the reason why computers are such a powerful device
used almost everywhere in our lives today,
is because they can be redesigned into an entirely different tool for an arbitrary purpose.
The computer is then no longer a tool that is used only by the programmer,
but can be used by anybody to run its applications.
The transition from ENIAC to the dawn of the personal computing era
was possible since computers became capable of general tasks other than computing equations,
such as writing and saving documents for a business.
Today, computers are being used for creating artwork,
for playing games, for communicating with others, to only give a few examples.
The entire history of computers is shaped by what new tasks computers became capable of,
which is inseparable from the means of interaction between the human and the computer.

At the heart of the diverse applications for computers is the language used to program them.
This is why programming languages capable of designing interactions are special –
once a computer is programmed, it can leave the hands of the programmer
and lie in the hands of the user, who interacts with it in a newly designed way.

As a matter of fact, all of the other languages mentioned in the SectorLISP blog post support an I/O functionality.
SectorFORTH has the key and emit instructions which reads a keystroke from the user and prints a character to the console.
BootBasic has the instructions input and print where input stores a user input to a variable.
Even BF has the instructions , and . capable of designing arbitrary user text input and output.
@rdebath has in fact made a text adventure game written entirely in BF.

Although the goal of SectorLISP is set in the realm of pure functions,
I thought that it would be a massive gain if it were able to handle I/O and still have a smaller program size
than the other languages mentioned in the SectorLISP blog post.
In the context of comparing the binary footprint of programs,
it would be a better comparison if all of the programs under discussion had even more functionalities in common.
All of this could be achieved if we could construct a version of SectorLISP that is capable of handling user input and outputs
that still has a small program size.

The Solution

What could we do to empower SectorLISP with the puzzle piece of interaction?
What is a natural way of implementing I/O?
To answer this, I created a fork of SectorLISP that supports two new special forms,
READ and PRINT. These two special forms are the counterparts for the , and . instructions in BF.
READ accepts an arbitrary S-Expression from the user, and PRINT prints the value of the evaluated argument to the console.
PRINT also prints a newline when called with no arguments as (PRINT).

The fork is available here: https://github.com/woodrush/sectorlisp/tree/io

Adding all of these features only amounted to an extra 35 bytes of the binary,
with a total of 469 bytes, or 471 bytes including the boot signature.
This is still 22 bytes or more smaller than the two former champions of minimal languages that fit in a boot sector mentioned in the SectorLISP blog post,
which are SectorFORTH (491 bytes) and BootBasic (510 bytes).
The rather minimal increase was achievable since most of the code for handling input and output were already available from the REPL’s functionality.
This fork successfully shows that adding an I/O feature to SectorLISP
will still allow it to have a smaller binary footprint than the two former champions.

Update: Thanks to a pull request by @jart,
the author of the original SectorLISP, we’re down to 465 bytes or 467 bytes including the boot signature.
Thank you @jart for your contribution!
The details of the assembly optimizations including the one used in this pull request are discussed in the
Assembly Optimizations section.

Usage

To run the SectorLISP fork, first git clone and make SectorLISP’s binary, sectorlisp.bin:

git clone https://github.com/woodrush/sectorlisp
cd sectorlisp
git checkout io
make

This will generate sectorlisp.bin under ./sectorlisp.

To run SectorLISP on the i8086 emulator Blinkenlights,
first follow the instructions on its download page
and get the latest version:

curl https://justine.lol/blinkenlights/blinkenlights-latest.com >blinkenlights.com
chmod +x blinkenlights.com

You can then run SectorLISP by running:

./blinkenlights.com -rt sectorlisp.bin

In some cases, there might be a graphics-related error showing and the emulator may not start.
In that case, run the following command first available on the download page:

sudo sh -c "echo ':APE:M::MZqFpD::/bin/sh:' >/proc/sys/fs/binfmt_misc/register"

Running this command should allow you to run Blinkenlights on your terminal.

After starting Blinkenlights,
expand the size of your terminal large enough so that the TELETYPEWRITER region shows up
at the center of the screen.
This region is the console used for input and output.
Then, press c to run the emulator in continuous mode.
The cursor in the TELETYPEWRITER region should move one line down.
You can then start typing in text or paste a long code from your terminal into Blinkenlight’s console
to run your Lisp program.

Running on Physical Hardware

You can also run SectorLISP on an actual physical machine if you have a PC with an Intel CPU that boots with a BIOS,
and a drive such as a USB drive or a floppy disk that can be used as a boot drive.
First, mount your drive to the PC you’ve built sectorlisp.bin on, and check:

lsblk -o KNAME,TYPE,SIZE,MODEL

Among the list of the hardware, check for the device name for your drive you want to write SectorLISP onto.
After making sure of the device name, run the following command, replacing [devicename] with your device name.
[devicename] should be values such as sda or sdb, depending on your setup.

Caution: The following command used for writing to the drive
will overwrite anything that exists in the target drive’s boot sector,
so it’s important to make sure which drive you’re writing into.
If the command or the device name is wrong,
it may overwrite the entire content of your drive or other drives mounted in your PC,
probably causing your computer to be unbootable.
Please perform these steps with extra care, and at your own risk.

sudo dd if=sectorlisp.bin of=/dev/[devicename] bs=512 count=1

After you have written your boot drive, insert the drive to the PC you want to boot it from.
You may have to change the boot priority settings from the BIOS to make sure the PC boots from the target drive.
When the drive boots successfully, you should see a cursor blinking in a blank screen,
which indicates that you’re ready to type your Lisp code into bare metal.

Applications

Here we present examples to showcase the capabilities of READ and PRINT.

Games

A major example of interactive programs is games.
I created a simple number guessing game that works on the fork of SectorLISP.

Here is a screenshot of the game in action, run in Blinkenlights:

A screenshot of SectorLISP running a number guessing game

Here is the text shown in the console:

(LET ' S PLAY A NUMBER GUESSING GAME. I ' M THINKING OF A CERTAIN NUMBER BETWEEN
 1 AND 10. SAY A NUMBER, AND I ' LL TELL YOU IF IT ' S LESS THAN, GREATER THAN,
OR EQUAL TO MY NUMBER. CAN YOU GUESS WHICH NUMBER I ' M THINKING OF?)
(PLEASE INPUT YOUR NUMBER IN UNARY. FOR EXAMPLE, 1 IS (*) , 3 IS (* * *) , ETC.)
NUMBER>(* * *)
(YOUR GUESS IS LESS THAN MY NUMBER.)
NUMBER>*
(PLEASE INPUT YOUR NUMBER IN UNARY. FOR EXAMPLE, 1 IS (*) , 3 IS (* * *) , ETC.)
NUMBER>(* * * * * * * *)
(YOUR GUESS IS GREATER THAN MY NUMBER.)
NUMBER>

We can see that the game is able to produce interactive outputs based on the feedback from the user,
which is an essential feature for creating games.
Note that there is also robust input handling in action,
where in the second input NUMBER>*, the user writes an invalid input *, which is not a list.
The game can handle such inputs without crashing.

The code is available at https://github.com/woodrush/sectorlisp-examples/blob/main/lisp/number-guessing-game.lisp.

Extended Lisp REPL – Transforming the Language Itself

The I/O feature can be used to transform the SectorLISP language itself as well.
As an example, I made an extended Lisp REPL where macro, define, progn,
as well as print and read are all implemented as new special forms.

Here is an example session of the program:

REPL>(define defmacro (quote (macro (name vars body)
       (` (define (~ name) (quote (macro (~ vars) (~ body))))))))
=>(macro (name vars body) (` (define (~ name) (quote (macro (~ vars) (~ body))))
))

REPL>(defmacro repquote (x)
       (` (quote ((~ x) (~ x)))))
=>(macro (x) (` (quote ((~ x) (~ x)))))

REPL>(repquote (1 2 3))
=>((1 2 3) (1 2 3))

REPL>

The code is available at https://github.com/woodrush/sectorlisp-examples/blob/main/lisp/repl-macro-define.lisp.

In the example above, the user first uses the backquote macro ` to define defmacro as a new macro,
then uses defmacro to define a new macro repquote.
These newly added features allow an interaction that is much more closer to those in modern Lisp dialects.

In the code,
these additional user inputs are included at the end of the code which could be directly pasted in the console.
However, we could look at this in another way – by writing the REPL code as the header,
we have effectively transformed the syntax of the language itself, by introducing new special forms
which were not present in the original interface.
The DEFINE special form is also introduced in SectorLISP’s friendly branch,
which adds some extra bytes.
With READ and PRINT, we can instead build these new features on top of the interface as software,
allowing us to save a lot of the program size.

Interactive BASIC REPL

As a final example for drastically modifying the means of user interactions,
I made an interactive BASIC interpreter written in the I/O SectorLISP.
It runs a subset of BASIC with the instructions LET, IF, GOTO, PRINT, REM, and the infix operators +, -, %, and <=.
Integers are expressed in unary as a list of atoms, such as (1 1 1)

NOW WITH OVER +8500 USERS. people can Join Knowasiak for free. Sign up on Knowasiak.com
Read More

Charlie
WRITEN BY

Charlie

Fill your life with experiences so you always have a great story to tell

Leave a Reply