The Plan Assembler

(Under construction, all docs in a pre-alpha state).

In most software ecosystems, the compiler is self-hosting, which means that you need an existing compiler binary in order to build the compiler. This has significant implications, since it is not practically possible to audit these binaries. Plunder solves this problem at it's root by having an extremely tiny bootstrapping language built directly into the virtual machine, and then defining everything else in terms of that.

This bootstrapping language is The Plan Assembler (pet-named Wisp), which is tiny enough to be written by hand in less than a thousand lines of assembly. And because PLAN itself is also such a tiny formal system, the VM kernel needed to boot a PLAN ecosystem from scratch, can realistically be written entirely in assembly code. The result is that a Plunder has zero software supply-chain dependencies.

The Plan Assembler is basically just a notation for constructing PLAN values, and binding values to names. But because of it's novel and expressive syntax system, it's powerful macro system, and the general expressive power of PLAN itself, Wisp can extended itself into a fairly powerful language, and then more complex languages can be implemented in Wisp.

Wisp Syntax

Wisp Syntax Introduction

Wisp uses a Lisp-like syntax with some modifications which make it even more expressive, while also making it able to be parsed with far less code. This borrows some of the ideas from Rex Rex, but with much less features, making it extremely easy to parse.

Despite significant conceptual differences, most Wisp code strongly resembles Scheme. Here's a quick example.

(define (isJunk token)
  (define tt (Tag tok))
  (or (= tt TT_SPACE)
      (= tt TT_CLOSE)
      (= tt TT_ERROR)))

(define (mapLoop f x n i acc)
  (if (>= i n) acc
    (mapLoop f x n (inc i)
      (Up i (f (Ix i x)) acc))))

(define (map f x)
  (define n (Sz x))
  (map-loop f x n 0
    (Rep 0 0 n)))

Compared to Lisp expectations, Wisp syntax has a number of unusual properties.

Wisp syntax is total and permissive, with no error states.
Wisp syntax is not homoiconic: the data model is not a subset of PLAN.
Wisp string literals do not support escaping.
Wisp draws no distinction between strings and numbers.
Wisp supports (parenthesis), [square braces], and {curly braces}.
Wisp forms can be juxta(posed).
Wisp does not have any special forms, like Lisp's 'quoting, and `(quasi ,quoting).
Wisp makes a hard distinction between words (fooBar) and operators (-=).

Wisp Syntax Design

Total Parsing and Minimality

Because Wisp is designed to be implemented in assembly, and because every implementation of PLAN must include an implementation of Wisp, Wisp goes to extreme lengths to minimize implementation footprint, and to minimize the number of edge cases which are likely to diverge between implementations.

One of the ways that Wisp achives this is by eliminating error cases. Error cases require a lot of code, and they are a significant source of divergence between implementations since they are hard to test. For example, Wisp does not require strings to be terminated at the end of a file, and nesting characters do not need to be matching: (foo] is accepted. A separate tool can be used to validate these cases.

Another example of this is the lack of escape sequences in string literals. Almost all languages support something like "Say \"Hello World\", now\n".. The rules for this tend to be complicated, and the specifics vary dramatically between languages. Wisp eliminates all of this complexity by simply having strings read until the next double-quote (or end-of-file). Support for escaping can be implemented in user code via a macro, for example: (putStr "Say \qHello World\q, now\n").

Wisp also eliminates all of the special notations that are usually baked into Lisp systems. Almost all lisps usually have '(q u o t e s), and `(q u a s i ,q u o t e s). #(vector literals), :keywords, conditional compilation, and the like. Wisp eliminates such forms from the base language, but the juxtaposition system and the rune system make it possible to define all of these features in user code by defining macros.

While these design choices are extreme and unconventional, the result is an absurdly small system that is still very expressive and erognomic. Without these simplifications, a zero dependency, purely assembly implementation of Wisp would not be pragmatically feasible.

Macro Hygiene

Macro hygiene is one really tricky corner case for Lisp metaprogramming, but Wisp manages to avoid all of these problems by reframing the foundations in a way that avoids the problem.

Macro hygiene can be broken down into three problems (TODO: am I missing one?):

If a macro expands to a reference to a global value that is in scope in the macro definition (Like the add function), what happens if the call-site happens to have shaddowed that name? Without hygiene, the result will accidentally refer to the local binding (For example, a local variable named add).
If a macro wishes to expand to an expression which references another macro which is in scope at macro-definition time, what happens if this name is shaddowed at the expansion site?
If a macro needs to generate local bindings, how can those bindings be guarenteed to not accidentally shaddow any user bindings, and not be shaddowed by any user bindings?

Scheme implementations include a lot of machinery to enable hygeneric metaprogramming. Some basic mechanisms are in the Scheme standard, and implementations generally include their own more complex mechanisms in addition to that.

Common Lisp does not solve this problem. A couple of other mis-features (separate namespace for functions and values) result in the problem comming up less often, and in the other cases macro authors are just forced to program in an extremely defensive style.

Wisp simply eliminates the first two problems by construction, and the third problem is solved by threading a macro-expansion count through all macro-expansions within a file, and then macros use that to generate unique symbols. This combination of features is sufficient to implement Scheme-style hygenic macro systems as a normal macro, without any special baked in constructions.

data Wisp
    = Expression [Wisp]
    | Expand Plan [Wisp]
    | Symbol Nat
    | Constant Plan

First, note that this is not homoiconic. You can embed arbitrary PLAN values, but the notation is not a subset of PLAN.

Second, remember that PLAN is a hermetic system with no opaque or privalidged values, so there is no distinction between runtime and compile time. In particular, code truely is data: functions are just normal transparent data structures, just like everything else.

Third, remember that PLAN itself is a purely functional model, and that it doesn't not have any built-in concept of a symbol or namespace. Wisp itself has a symbol table, but it is only used to lookup symbols when reading forms, functions refer to each other by value, not by name.

The result of all of these unique features is that the hard problems of hygenic macros just go away.

In Lisp, a macro that wants to expand to a reference to a function needs to somehow output a symbol which contains a stable (unshadowable, unredefinable) name for that function. In Wisp, you just expand to a Constant reference to the function value itself. Similarly, if you want to expand to an expression which references a specific macro, instead of expanding to an s-expression, you expand to a (Expand macro exprs..) form, where macro is not a name, but a literal reference to a macro function.

Wisp Syntax Specification

Lexing Wisp

Parsing Wisp

Desugaring Wisp

Encoding Wisp in PLAN

Wisp Macros

The Wisp macro system is extremely simple, but it is able to support fully hygenic macros by changing how the problem is looked at, and taking advantage of some of the unique capabilities of PLAN.

(TODO: document the system here)