S₀ is the lowest level “machine language” that Swanson hosts execute. It is primarily intended as a translation target, and not meant to be written directly. It doesn’t even have a textual language for writing it! It only has a binary format, SBL.
S₁, on the other hand, is Swanson’s “assembly language”. It’s still quite low-level, mapping very closely to S₀ and the Swanson execution model. It adds several convenience instructions, most of which desugar directly into one or more S₀ instructions.
Other than that, S₁ purposefully does not provide very many other higher level affordances, so that it is simple to write a bootstrap translator from S₁ to S₀.
S₁ source files contain UTF-8-encoded Unicode.
Whitespace separates tokens but is otherwise ignored. A comment starts with
# and continues through the end of the line. Throughout most of the grammar
below, whitespace is allowed, but not required, between any two tokens. The
special SPACE and NO_SPACE “tokens” indicate places where whitespace is
required or prohibited.
name ::=bare_name|backtick_name|hex_name
Swanson names contain arbitrary binary data.
bare_name ::= (<Unicode category L, N, or M> | "." | "_")+
A bare S₁ name can contain any Unicode letter, number, or mark (as identified by
the L, N, and M Unicode categories), as well as period (.) and
underscore (_). (Unlike many other languages, there is no requirement that a
bare name start with a non-digit.)
backtick_name ::= "`" <any Unicode scalar value except U+0060>* "`"
If a name contains other characters besides “identifier” characters, you can enclose an arbitrary sequence of Unicode characters in backticks. This syntax does not support any escape sequences, and therefore cannot be used for a name that contains a backtick. (S₁ files are encoded in UTF-8, so whatever bytes are present in the source file are copied through verbatim to the name. Unicode normalization is not performed.)
hex_name ::= "!["hex_octet* "]" hex_octet ::=hex_nybbleNO_SPACEhex_nybblehex_nybble ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "A" | "B" | "C" | "D" | "E" | "F" | "a" | "b" | "c" | "d" | "e" | "f"
As a last resort, you can provide the contents of the name by explicitly listing
each octet in hexadecimal. (Note that you must use exactly two hexadecimal
digits for each octet. ![0] is not a valid hexadecimal name.)
The name hello can be rendered in each of these three syntaxes as follows:
hello
`hello`
![68 65 6c 6c 6f]
module ::= "module" SPACEmodule_name";"blockmodule_name ::=name
An S₁ source file defines one module. It consists of the module keyword, the
module’s name, and a single block of S₁ code:
module example;
@quote <example>
&drop {
κ:
};
loader:loaded
(This example contains some other S₁ constructs that we haven’t described yet; it will make more sense after we get through the following sections.)
An S₁ module is a valid Swanson unit. When loaded, the
module’s branch will be executed with a loader on the loader stack. The
module can use the loader to load other Swanson units that it depends on. It
should leave a single value on the default stack, and return control by invoking
the loaded branch of the loader. That value is what represents the loaded
module to other Swanson units.
block ::=instructionSPACEblock|call
An S₁ block is a sequence of zero or more instructions followed by exactly one call.
instruction ::=basic_instruction|quotation
The instructions in a block manipulate values on the stack in preparation for the call at the end of the block.
basic_instruction ::= "@newtag" |
"@droptag" |
"@lock" |
"@unlock" |
"@nil" |
"@dropnil" |
"@cons" |
"@uncons" |
move_instruction |
pack_instruction |
unpack_instruction
A “basic” instruction is any instruction that is not a quotation. (Quotations are rather complex, as we’ll see below, so they are not allowed in a parameter list.)
Each S₀ operation has a corresponding S₁ basic instruction. Each one operates on the default unnamed stack.
stack_name ::=namemove_instruction ::=move_targetNO_SPACE "←" NO_SPACEmove_source| "←" NO_SPACEmove_source|move_targetNO_SPACE "←" |move_sourceNO_SPACE "→" NO_SPACEmove_target| "→" NO_SPACEmove_target|move_sourceNO_SPACE "→" move_source ::=stack_name|literalmove_target ::=stack_name
You can use a “move” instruction to move values between stacks, or to push a
literal onto a stack. You can provide the source and target in either order; the
direction of the arrow indicates the direction of the move. Whitespace is not
allowed around the ← or →. If the source or target is not present, the
default unnamed stack is used.
literal ::=quoted_literal|hex_literal
A literal represents immutable binary content.
quoted_literal ::= '"' <any Unicode scalar value except U+0022>* '"'
Most literals can be encoded by enclosing their content in double quotes. This syntax does not support any escape sequences, and therefore cannot be used for a literal that contains a double quote. (S₁ files are encoded in UTF-8, so whatever bytes are present in the source file are copied through verbatim to the literal. Unicode normalization is not performed.)
hex_literal ::= "[" hex_octet* "]"
You can also provide the contents of the literal by explicitly listing each
octet in hexadecimal. (Note that you must use exactly two hexadecimal digits for
each octet. [0] is not a valid hexadecimal literal.)
pack_instruction ::= "@pack" "["stack_names"]" unpack_instruction ::= "@unpack" "["stack_names"]" stack_names ::= ε |stack_name|stack_nameSPACEstack_names
The @pack instruction creates a new list on the default
unnamed stack. The contents of the list are popped from the named stacks that
you provide. You cannot pack from the default unnamed stack. The list elements
are consumed in left-to-right order.
The @unpack instruction consumes a list from the default unnamed stack. The
contents of the list are pushed onto the named stacks that you provide. You
cannot unpack onto the default unnamed stack. The stack names are processed in
right-to-left order, so that packing and then unpacking with the same stack
names restores the original values. An unpack instruction halts and
catches fire if the list does not contain exactly the requested number
of values.
Packing or unpacking zero values creates or consumes an empty list, respectively.
quotation ::= ("@quote" | "@enclose") (quotation_body | upquote)
The @quote instruction constructs an invokable whose body is implemented in
S₁. This invokable is pushed onto the default unnamed stack.
The @enclose instruction constructs a closure. This instruction pops
a value from the default unnamed stack and “bundles” it with the quotation. The
closure is pushed onto the default unnamed stack. The closed-over value will be
pushed back onto the default unnamed stack when the quotation is invoked
(regardless of which branch is selected).
quotation_body ::= ("<" quotation_name ">")? named_branch+ ";"
quotation_name ::= name
named_branch ::= ("&" branch_name)? "{" block "}"
branch_name ::= name
The body of the quotation or closure will typically consist of one or more branches of S₁ code. Each branch can optionally be given a name. If no name is given, the branch has the default empty name. It is an error to give the same name (including the default empty name) to more than one branch.
The quotation itself can also have a name. This is purely decorative; many Swanson hosts will include this in debug or tracing output.
upquote ::= "(" "upquote" (SPACE upquote_depth)? ")"
upquote_depth ::= digit+
digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
To support recursion, you can also create a new quotation from within its body
via an upquote. You provide an optional lexical depth; 0 (the default)
selects the immediately enclosing quotation. (Note that this depth counts S₁
scopes. Certain continuations expand an S₁ scope into
multiple nested S₀ blocks. This implicit nesting is not counted when
calculating an upquote depth.)
call ::=plain_call|returned_receiver_callplain_call ::= (stack_nameNO_SPACE)? ":" (NO_SPACEbranch_name)?optional_parameterscontinuation
Each S₁ block must end with exactly one call. An S₁ call is translated into an S₀ invocation. You provide an optional stack name, which must have an invokable at top of stack. (If the stack name is not provided, the invokable must be at the top of the default unnamed stack.) You also provide an optional branch name (which defaults to the empty name), which must be the name of one of the invokable’s branches.
The call also optionally includes parameters and a continuation, which allow you to push any final inputs onto the execution stacks before performing the invocation. (The continuation is processed first; then the parameters, if any; then the invocation is performed.)
optional_parameters ::= ε | "(" parameters ")"
parameters ::= ε | parameter | parameter SPACE parameters
parameter ::= basic_instruction
Invokables typically use named stacks to name and document their inputs. The parameters in an S₁ call let you use basic instructions to put actual input values on the correct stacks. The end result looks similar to keyword arguments in other languages. For instance,
seven:add(rhs←five)
invokes the add branch of the invokable at the top of the stack named
seven. Before invoking, it moves a value from the stack named five to
the stack named rhs, signifying that the invokable’s rhs input should
come from the “local variable” stack we have named five.
continuation ::= ε |nonempty_continuationnonempty_continuation ::=simple_continuation|hybrid_continuation|join_continuation
The Swanson execution model is inherently based on continuations: to invoke an
invokable and then do something else after it’s done, you have to wrap the
“after” logic in a continuation, which you pass in as an input. S₁ provides an
ergonomic syntax for defining the continuation of a call. By convention,
continuations are placed on the stack named κ (or ![ce ba]).
simple_continuation ::= SPACE block
The most common form of continuation is the simple continuation. In this
case, it looks like there are additional instructions following the call.
Under the covers, all instructions following the call are wrapped in a single
branch with the default empty name, which is pushed as an additional input onto
κ stack.
hybrid_continuation ::=named_branch*continuation_branchcontinuation_branch ::= ("&"branch_name)? "…"block
A hybrid continuation also looks like there are additional instructions
following the call. You use a hybrid continuation when you want the continuation
input to have additional branches, or if you want to give the “inline” branch
a non-default name. Under the covers, we create an invokable with all of the
named branches, and with the instructions following the call wrapped into an
additional named branch. This invokable is pushed as an additional input onto
κ stack.
join_continuation ::=named_branch+ ";"continuation
A join continuation lets you define branching control flow that must join
back together. The named branches before the semicolon (;) define the
branching logic. You then place any other continuation (including another join
continuation, if needed) after the semicolon. The continuations are processed in
“reverse order”: the continuation after the semicolon is processed first,
pushing its value(s) onto κ stack. Then the join continuation is processed.
The end result is that the named branches will execute with the “following”
continuation immediately available at the top of κ stack. (Note that we do
not add any implicit instruction to invoke that following continuation; your
join continuation branches must do so explicitly.)
returned_receiver_call ::= (stack_nameNO_SPACE)? "::" (NO_SPACEbranch_name)?optional_parametersnonempty_continuation
The Swanson execution model is inherently linear: invoking a
value consumes it. Nevertheless, many invokables will end up pushing themselves
back onto a stack so that they can be used again. This stack is typically called
ρ (or ![cf 81]), for receiver.
This pattern — a returned receiver call — is common enough that S₁ has
special syntax for it. If you use a double-colon (::) to separate the stack
and branch names of the invokable, we will prepend a ρ→[stack name] move
instruction to every branch of the call’s first continuation. This has the
effect of moving the returned receiver back onto the stack that you originally
called it from. For instance,
loader::load(name←"module1") →module1
loader::load(name←"module2") →module2
desugars into
loader:load(name←"module1") ρ→loader →module1
loader:load(name←"module2") ρ→loader →module2