Tony Garnock-Jones 238e58cebf | ||
---|---|---|
bin | ||
src | ||
.gitignore | ||
README.md | ||
SNORTH.md | ||
lib.px | ||
model.rkt | ||
package.json | ||
tests.px | ||
tsconfig.json | ||
yarn.lock |
README.md
Syndicate-lang 3bis "ICON4th"
Inspired by Emery Hemingway's lang_3
and earlier work on syndicate-lang
etc., and
incorporating ideas loosely inspired by ICON4 and Haskell's non-determinism (list) monad.
> yarn
...
> ./bin/3bis.js '1 2 3 + + wr nl'
6
> ./bin/3bis.js '[1 2 3] :vs [vs / 1 +] wr nl'
[2 3 4]
Starting the interpreter without command-line arguments (or with a --repl
flag) starts a
read-eval-print loop.
Test suite. Run it with yarn test
or with ./bin/3bis.js -l
tests.px
.
Overview
A stack-oriented (but not strictly concatenative) language intended for high-concurrency, interactive environments (e.g. the Syndicated Actor Model!).
The data model is Preserves, plus embedded applicable values such as closures and delimited continuations.
Syntax
P-expressions. Non-symbol atoms are interpreted as literals, pushed immediately on the stack.
Symbols are interpreted as words. A word is looked up in the current environment and
immediately executed. New variables are bound through pattern matching (see below). As an
exception to normal symbol handling, a symbol beginning with an equals sign causes the same
symbol but with the leading equals sign removed to be pushed immediately on the stack. For
example, if
would trigger the if
word, but =if
would push the symbol if
onto the stack.
P-expression groups (round parentheses) construct closures. A closure is a bundle of a program and an environment.
#t (1 2 +) (3 4 +) if
# has effect () --> (3)
#t (1 2 +) when
# has effect () --> (3)
#f (3 4 +) unless
# has effect () --> (7)
P-expression sequences, records, blocks and sets construct Preserves data. At
the start of each compound term, the current stack is remembered and emptied. A comma (,
)
transfers the contents of the stack into the compound value under construction, leaving the
stack empty again. At the end of each compound term, any remaining elements are also added to
the compound value, even if no comma is present. Then, the remembered stack is restored and the
finished compound value is pushed on top.
[1 2 +, 3 4 +, 5 6 +, 7 8 +]
# has effect () --> ([3 7 11 15])
10 [dup 1 +, dup 2 +, dup 3 +]
# is an error, because the stack is empty when dup runs
10 [10 1 + dup 2 + dup 3 +]
# has effect () --> (10 [11 13 16])
[1 1 1, 2 2 2, 3 3 3]
# has effect () --> ([1 1 1 2 2 2 3 3 3])
10 [_, _, _]
# is an error, because the stack is empty when _ runs
10 []
# has effect () --> (10 [])
10 [,,,]
# has effect () --> (10 [])
#{ 1 2 +, 3 4 +, 3 }
# has effect () --> (#{3 7})
#{ 1 2 + 3 4 + 3 }
# also has effect () --> (#{3 7})
Records are unusual in that the record label is taken literally, and may not be computed.
2024 :year 5 :month 3 :day
"Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec" " " split month 1 - ? :monthName
<date year monthName day>
# has effect () --> (<date 2024 "May" 3>), and introduces four new bindings
Blocks are unusual in that they construct Preserves dictionaries, and so require both keys and
values. The double-colon (::
) operator pops the top of the stack into a temporary "key"
register. If the "key" register was empty, it does nothing further; otherwise, it pops a single
value, and stores it along with the previous contents of the "key" register as a key-value pair
in the dictionary under construction. At the end of a block, the same thing happens if the
"key" register is nonempty. Comma may be used within a block, with the same effect as for other
compound terms, accumulating any pending key-value pair and clearing the stack. In addition,
the comma operator clears the "key" register.
{
=a :: 1 2 +
=b :: 3 4 +
"c" :: 5 6 +
9 2 * :: 3 3 3 * *
}
# has effect () --> ({a: 3, b: 7, "c": 11, 18: 27})
10 { =a :: 10 1 +, =b :: 10 2 +, =c :: 10 3 + }
# has effect () --> (10 {a: 11, b: 12, c: 13})
Standard words
c !
-- read as "apply" or "call" -- evaluates the applicable c on the top of the stack.
If the top of the stack is not an applicable, it is left in place.
(1 2 +) ! # --> 3
"non-closure" ! # --> "non-closure"
v tc fc if
-- evaluates fc if v is #f
; otherwise, evaluates tc.
(:fc :tc (:#f \ fc, _ tc) !) :if
v c when
-- evaluates c if v is not #f
.
(:tc (:#f, _ tc) !) :when
v c unless
-- evaluates c if v is #f
.
(:fc (:#f \ fc, _) !) :unless
v _
-- discards v from the top of the stack.
(:_) :drop
v dup
-- leaves v in place on the stack, and pushes another v on top of it.
(:v (v) (v)) :dup
- Notice that the references to
v
are quoted within closures. This is becausedup
, if asked to copy a closure, should not invoke that closure even once, let alone twice. Quoting works because for allv
,(v)
pushes a value that, when applied, has the same effect asv
.1
w v nip
-- removes w from the stack, leaving v in its place.
(:top _ (top)) :nip
- Notice the quoting of
top
again.
The word clear
empties the stack.
1 2 3 clear # nothing remains on the stack; anything
# pushed previously is also removed
Arithmetic words +
, -
, *
, div
, rem
, fld
, and mod
take two values from the stack,
leaving one in their place.
3 4 + # --> 7
3 4 - # --> -1
3 4 * # --> 12
The words div
and rem
perform truncating integer division (like Java, JavaScript,
C, Erlang and many others do), while the words fld
and mod
perform flooring integer
division.
8 3 div # --> 2
-8 3 div # --> -2
8 -3 div # --> -2
-8 -3 div # --> 2
8 3 rem # --> 2
-8 3 rem # --> -2
8 -3 rem # --> 2
-8 -3 rem # --> -2
8 3 fld # --> 2
-8 3 fld # --> -3
8 -3 fld # --> -3
-8 -3 fld # --> 2
8 3 mod # --> 2
-8 3 mod # --> 1
8 -3 mod # --> -1
-8 -3 mod # --> -2
Comparison words eq
, ne
, lt
, le
, gt
and ge
compare the penultimate value with the top
value from the stack. If the asked-for relationship holds, the top value is discarded (and the
former penultimate value becomes the top of stack) and execution continues. However, if the
relationship does not hold, execution fail
s (see below). Comparison follows Preserves
ordering and equivalence.
2 4 lt # --> 2
4 2 lt # fails
4 4 lt # fails
"a" "b" lt # --> "a"
"b" "a" lt # fails
3 "a" lt # --> 3, because in Preserves order, integers precede strings
"a" 3 lt # fails, because in Preserves order, integers precede strings
v error
-- crash the current actor with v as the crash detail and user-error
as the
error tag.
"An example error" error # crashes
v size
-- pops v and pushes its size. For sequences and sets, this is the number of
elements; for dictionaries, the number of keys; for strings and symbols, the number of Unicode
scalars; and for byte-strings, the number of bytes. Execution fail
s if v is any other kind
of value.
#t size # fails
3.4 size # fails
40 size # fails
"hello" size # --> 5
#"hello" size # --> 5
=hello size # --> 5
<ok 1 2> size # --> 2
[1 2] size # --> 2
#{1 2} size # --> 2
{=a::=b} size # --> 1
v k .
-- retrieves the element labelled with key k from value v. For sequences,
records, strings, symbols, and byte-strings, k must be a non-negative integer. For
dictionaries, k can be an arbitrary value. For other types of value, or if the element is not
present, execution fail
s.
"hello" 4 . # --> 111, the Unicode scalar for the character `o`
=hello 4 . # --> 111
=hello 9 . # fails, no such position
"" 4 . # fails, no such position
#"hello" 4 . # --> 111
#[aGVsbG8] 4 . # --> 111 (base-64 representation of #"hello")
<ok 1 2> 1 . # --> 2
[1 2] 1 . # --> 2
[1 2] 3 . # fails, no such position
{=a::1} =a . # --> 1
{=a::1} =x . # fails, no such key
Output words pr
and wr
take a single value and display it to stdout
. The word wr
writes
its argument using Preserves text syntax. The word pr
is just the same, but does not quote
strings. Output may be buffered until nl
is executed. The word nl
flushes the buffer and
also prints a newline. Variants which print to stderr
instead of stdout
also exist, with a
_e
suffix: pr_e
, wr_e
and nl_e
.
"Hello\n" wr # empty stack; prints `"Hello\n"`, with quotes and escaping
=hello wr # empty stack; prints `hello`
["quote \"quote\""] wr # empty stack; prints `["quote \"quote\""]`
"Hello\n" pr # empty stack; prints `Hello`, without quotes, followed by newline
=hello pr # empty stack; prints `hello`
["quote \"quote\""] pr # empty stack; prints `["quote \"quote\""]`
(If you try the above examples interactively, don't forget to use nl
to flush the buffer.)
Branching and failure
A primitive word, fail
, causes the current program to fail. Failures by default propagate to
surrounding contexts.
Two special contexts allow failure handling: the first is the presence of multiple alternatives in a closure, and the second is the treatment of failure in branches.
Failures are not errors or exceptions: they are used for non-exceptional control flow purposes,
and are less like exceptions and more like []
in Haskell's non-determinism (list) monad.
Alternatives in a closure
If a closure's program contains one or more comma operators, those operators split the program into multiple smaller subprograms.
When the closure is called, the first such subprogram is executed. If it runs to completion
(i.e. up to the comma following it), the closure returns as usual. However, if it fail
s, the
stack and environment are reset to their states at the time the closure was called and
execution proceeds with a subsequent subprogram. Successive failures invoke successive
subprograms until no more exist, at which point the failure propagates outside the call of the
closure to the surrounding context.
3 =plus (:=plus \ 1 +, :=minus \ 1 -) ! # --> 4
3 =minus (:=plus \ 1 +, :=minus \ 1 -) ! # --> 2
3 =bogus (:=plus \ 1 +, :=minus \ 1 -) ! # fails, no matching branch
Patterns interact with branching, alternatives and failure:
(:3 =is-3, :_ =not-3) # a closure that yields is-3 or not-3, depending on the top of stack
(:=inc 1 +, :=dec 1 -) # a kind of object that understands inc and dec "messages"
The primitive word \
, read "cut", commits to the current branch in a closure with multiple
alternatives, ruling out backtracking for this closure.
=ok 4 3 (:3 :4) ! # --> ok
=ok 4 3 (:3 :5 ,) !) # --> ok 4 3, 3 matched, but 4 =/= 5, so backtracked to `,`
=ok 4 3 (:3 \ :5,) !) # fails, the 3 matched and commited, but then 4 =/= 5,
# and backtracking was disabled by the commit
=ok 4 3 (:3 \ (:5, :4)! ,) !) # --> ok, 3 matched and commited, 4 =/= 5 but 4 === 4
=ok 4 3 (:3 \ (:5, :6)! ,) !) # fails, 3 matched and commited, 4 =/= 5 and 4 =/= 6
=ok 4 3 (:3 (:5, :6)! ,) !) # --> ok 4 3, 3 matched but did not commit,
# subsequent fail backtracked
Branching and collection
3bis uses delimited continuations plus some unusual effects to implement a form of generators.
The continuation capture operator, shift
, captures a continuation delimited by the
dynamically innermost compound value building context (the "delimiting frame"): that is, the
innermost [
...]
or <
...>
or #{
...}
or {
...}
.2 (There is also an
implicit delimiter at the top of the continuation stack.) A captured continuation can be used
to perform "the rest of the computation" many times, once for each generated element.
A primitive word, schedule!
, stores an applicable value for later evaluation in the
delimiting frame. Combining schedule!
with shift
allows operators like iota
to be
constructed:
(
:limit
shift :k
(
limit lt :n \
(n 1 + loop) schedule!
(k n, clear) !
,
clear
) :loop
0 loop
) :iota
[5 iota] # --> [0 1 2 3 4]
[5 iota 1 +] # --> [1 2 3 4 5]
[1 5 iota +] # --> [1 2 3 4 5]
-
Notice careful use of comma (
,
) forfail
-handling. -
Each time round the loop, the next iteration is
schedule!
d, and the captured contextk
is invoked with the current value of the iteration countern
.
If code inside a delimiting frame executes to completion, all its values are accumulated into
the compound value under construction. If it fails, however, the stack is discarded and the
failure is ignored. In each case, execution continues with the next schedule!
d applicable
value. If no more schedule!
d values are waiting, the compound value is finished.
More interesting generators can be built atop primitive generators like iota
, such as /
,
which generates every element of its argument:
(children dup size iota .) :/
[5 iota] :vs
[vs /] # --> [0 1 2 3 4]
[vs / 1 +] # --> [1 2 3 4 5]
[1 vs / +] # --> [1 2 3 4 5]
{vs / :: =x} # --> {0: x, 1: x, 2: x, 3: x, 4: x}
{vs / :n n 1 + :: n} # --> {1:0 2:1 3:2 4:3 5:4}
and //
which recursively generates the given value itself plus //
applied to all its
elements:
(:v [(v) ((v) / //)] / !) ://
[{ =a:: [1 2], =b:: [3 4] } //] # --> [ {a: [1 2] b: [3 4]}
[1 2]
1
2
[3 4]
3
4 ]
-
Notice the use of quotation,
(v)
, just in casev
is bound to an applicable value. -
Notice the use of
/
to generate closure elements(v)
and((v) / //)
, followed immediately by!
to invoke these closures. This pattern allows branching continuations, encoded as branching data.
Generators combine nicely with fail
- and pattern-matching-based predicates:
(dup 2 mod :1) :?odd
[vs / 1 + ?odd] # --> [1 3 5]
The scope of a delimited continuation extends only as far as the next comma-separated segment in the delimiting frame:
[[3 4] /, [5 6] /] # --> [3 4 5 6]
[[3 4] / [5 6] /] # --> [3 5 3 6 4 5 4 6]
Failures within a generator simply yield no values:
[[3 4] / fail, [5 6] /] # --> [5 6]
However, failures outside a generator but within a delimiting frame cause failure to propagate:
[fail] # fails
[fail, [5 6] /] # fails
[[3 4] /, fail] # fails
[[3 4] / fail, fail] # fails
Pattern matching
The :
operator precedes a pattern, to be matched against the top of the stack. If no value
is on the stack, an error is signalled. If the pattern fails to match the top of stack,
execution fails as if the fail
word were executed. Otherwise, new bindings are introduced to
the environment and execution continues.
Patterns follow a grammar:
- the literal symbol
_
is a discard-pattern, a wildcard. - a
symbol
not prefixed with=
(and not literally_
) is a binding. - a
symbol
(other than_
) followed by&
and another pattern is a binding with a nested pattern. - a
=symbol
prefixed with=
only matches a corresponding literalsymbol
. - other atoms are self-matching.
- a group
(
expr ...)
may contain program expressions; during pattern construction, the program (if any) is evaluated, and a single value is popped from the stack and placed in the pattern as an expected literal value.3 - a record
<
label pattern ...>
must have a label that is a literal Preserves value, not containing any groups ((
...)
), with symbols not prefixed with=
, and so on. The subpatterns match record fields. - sequences
[
pattern ...]
contain subpatterns, and act as prefix-matchers. - sets are not allowed.
- dictionaries
{
key:
pattern,
...}
have keys that are literal Preserves values, just the same as labels on record patterns. Each key is associated with a subpattern. - commas are ignored (except in groups (
(
...)
), where they denote alternatives as usual).
Examples:
3 :3 # no net stack change
3 :x # no net stack change; places x ⟼ 3 in the environment
3 :4 # fails
[1 2] :[x y] # no net stack change; places x ⟼ 1 and y ⟼ 2 in the environment
Macros
Attributes @
mark macro invocations. For example,
@foo bar
invokes the macro foo
on the syntax bar
. There is, as yet, no facility for user-defined
macros.
-
You might be concerned that, say, in a loop, repeated quoting might ensue. However, because
(v)
≡((v))
≡ ..., the interpreter notices this pattern and treats it specially, avoiding trivial nesting of quotations. ↩︎ -
These compound value building contexts are the only form of
reset
operator in the language at present. ↩︎ -
There is a complication with compound literals in patterns: all pattern matching over compound terms will accept larger compound values. So a pattern
[1 2]
will match[1 2 3]
, but not[1]
. ↩︎