A magical property of computers is the ability to "change the airplane engines mid-flight." You can start with Linux, GCC, Git 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 are less useful than Linux, but they're easier to understand. That makes them handy for studying this self-modifying behavior of computers.
Midnight's also a minimal self-modifying computing system. However it comes at the problem from a Lisp perspective insted of an assembly one. It's designed to answer the question: 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?
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? Yes!
quote
means we can store the logic of the whole program, including
multiple "languages", in a single file, in fact a
single expression. You wouldn't want to do this for a
big system but it works here.
parse
easy to write.
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.