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?
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
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.
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:
and
and
or
cond
case
quasiquote
define-struct
List functions, association list based dictionaries, etc.
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.
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.
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.
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.
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.
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.
Midnight supports system images (Wikipedia link).
Steps:
ctrl-ENTER
The system will take up from exactly where it left off.
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.