🌱Ian's Digital Garden

💾
Midnight System


From Cons to Cursor

A magical property of computers is the ability to "change the airplane engines mid-flight." You can start with Linux, GCC and Vim and-- given enough time-- rewrite them into whatever software you'd like.

Some people are interested in the smallest systems that provide this ability. For instance Hundred Rabbits has their 💾uxn virtual computer. These minimal systems aren't nearly as useful as Linux, but they're fun in their own way. For one thing you can experiment with them easily. For another you can understand everything about them, which a refreshing experience coming from modern software environments.

Midnight's also a minimalist self-modifying system, though with a Lisp basis instead of an assembly one. It's designed to answer the question: if we start from primitives like car, cdr, and cons, what's the smallest amount of stuff we need to add to get a self-modifying system without code golfing? Are there any special characteristics of lisp that make this easier?

Result

A miniature, Scheme-like language (💾Midnight Lisp) and a computing environment based on it (the Midnight System).

Live: midnightsystem.com

Code: github.com/seagreen/midnight

Steps

1. "Machine" Language

The primitives are inspired by the original Lisp paper, 📜Recursive Functions of Symbolic Expressions and Their Computation by Machine.

lambda, let, quote, eval, if, car, cdr, cons, pair?, list-empty?, symbol? symbol-eq?, codepoints->symbol, symbol->codepoints, int?, +, -, *, /, %, <, =, >

See more: 💾Midnight Lisp.

2. Macro System

Midnight is a nice base language, but we want a higher-level language to write the rest of the system in.

In a traditional system we'd write a compiler and have separate source code files for both languages.

In Midnight, taking advantage of quote, we write a macro system. Using it we incrementally build the higher level langauge. This all happens in a single expression:

(let
  ((midnight-plus-macros
    '(
; definitions here must start with `define` or `define-macro`
))
  (macroexpand ...)) ; implement the macro system

(eval (macroexpand (midnight-plus-macros))))

Using define-macro we write the following:

  • Short circuiting and and or
  • cond
  • Pattern matching with case
  • quasiquote
  • define-struct

3. Stdlib

List functions, association list based dictionaries, etc.

4. Input, Output, Store, and Ephem

These aren't part of the source code, but rather properties of the system itself.

Input: keypresses.

Output: a 80x30 fixed text display and a cursor.

Store ("hard drive"): an S-expression. It's passed into each step of the program along with a keypress and an Ephem. If a running program had a type signature it would be:

step :: Store -> Ephem -> Keypress -> (Store, Ephem)

The store must be an association list with a display key. The system reads off the display key after each input to know what to display.

Ephem ("RAM"-- except tree-shaped so TM?): A Midnight expression. Unlike the Store this can contain closures.

5. Text Editor

Back to the source code.

The two simplest programs I could think of to give self-modifying behavior are a text editor and a REPL. I'm still thinking about which is the best choice for this project, but it's a text editor for now.

6. Self-Modifying Machinery

To get self-modifying behavior the source code stores the actual action to be taken on each keypress as a closure in the Ephem. The source feeds each input into the Ephem closure instead of processing it itself. Thus the system can change its own behavior by replacing the closure stored there.

Currently the user requests such a reload with a ctrl-ENTER keypress. This triggers a parse of the editor's current contents, using a parser for Midnight written in Midnight. This is then eval'd. The result replaces the old Ephem closure.

Reflections

How'd we do? Our original question was if we start from Lisp primitives like cons, car, and cdr, what's the smallest amount of stuff we need to add to get a self-modifying system without code golfing? Are there any special characteristics of lisp that make this easier?

The answer to the first part is about ~3,000 lines of code when done this way.

And does lisp make this easier? Definitely. Somewhat.

  • The minimal lisp syntax makes parse easy to write. parse is needed to convert the text editor contents from a string into a Midnight S-expression, so that it can be passed to eval.
  • quote means that it's easy to extend our base language with a macro system. This makes writing parse and the editor significantly more pleasant.
    • Note that there is a non-quote based alternative to this strategy: we could have implemented a second language using plain Midnight. So what quote actually gives us is this: given that at least some code has to be in plain Midnight, we gain the option for it to be a macro system instead of a parser for a second language.

Bonus: Copy-Paste Your Computer

Midnight supports system images (Wikipedia link).

Steps:

  1. From within a running system, click the "Store" button at the top alongside "Live", "Display", etc.
  2. Copy the text there
  3. Paste it into the "Store" button text box in another tab
  4. Press ctrl-ENTER

The system will take up from exactly where it left off.

How Paste Works

The difficulty in starting from a pasted system is rebuilding the Ephem, since it can contain closures and thus can't be guaranteed to be serializable.

To get around this applications are required to keep another special key on the Store in addition to display called main-sexp. main-sexp must contain an S-expression that, when evaluated, produces a function that can rebuild the appropriate Ephem.

Related Work

📎self-contained computing environments

📎minimalist lisp-family programming languages

Backlinks