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 -ltests.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 because dup, if asked to copy a closure, should not invoke that closure even once, let alone twice. Quoting works because for all v, (v) pushes a value that, when applied, has the same effect as v.¹

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 fails (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 fails 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 fails.

"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 fails, 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 {...}.² (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 (,) for fail-handling.

• Each time round the loop, the next iteration is schedule!d, and the captured context k is invoked with the current value of the iteration counter n.

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 case v 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 literal symbol.
• 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.³
• 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.

---

1. 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. ↩︎

2. These compound value building contexts are the only form of reset operator in the language at present. ↩︎

3. 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]. ↩︎