3bis/SNORTH.md

6.9 KiB

SNORTH

2024-05-06 tonyg

SNObol + fORTH ??

(Update 2024-05-07: actually it turns out I was thinking more of some hybrid of ICON4 and Haskell's non-determinism list monad than SNOBOL...)

Core idea

Stacky, but evaluation can succeed, yielding an altered stack, or fail, causing rewind to the nearest backtracking point.

/, from preserves-path, acts like I imagined ... might:

[1 2 3] :vs
[vs / 1 +]             # --> [2 3 4]
[vs / dup even? !!]    # --> [2]; note that `!!` means "fail-if-false", "(fail) unless"
[vs / even?]           # --> [#f #t #f]
#{vs / even?}          # --> #{#f #t}

Interestingly, [] / ... succeeds but does not invoke the ... part at all (because we keep all the values from the (zero) true branches, and ignore all the false branches). That is, / never fails on its own: code to its right has to fail explicitly. (Corollary: we now overapproximate the set of bindings introduced as part of a closure's execution! But this was always true in the presence of exceptions and/or other early returns.)

Perhaps (... ; ...) defaults to alternation? If the last branch fails, the whole call fails.

Then v (even? !! T; F)! acts like v even? (T) (F) if, when T has no ; in it

/ --> one continuation (to its right), multiple values (from the top-of-stack exploded); but par (... ; ... ; ...) --> one value (top-of-stack), multiple ;-separated continuations

I think par means something like "collect" (perhaps that's a better name for it): each of the branches explored, if it succeeds, contributes to the output, just the same as , accumulates into a collection.

Now, what would [vs / dup 10 +, 20 +] and [vs / dup 10 +; 20 +] mean?

What about mixed , and ;?

... actually, then, could we just make , be the branch separator? And then compound-value accumulations "finish a branch" on ,, while closures introduce backtracking points on ,?

So you'd write v (even? !! T, F)!.

Perhaps accessors and predicates should succeed/fail rather than answering, respectively, some kind of option-type or a boolean. Again like preserves-path. They would not consume their argument. You can always convert a faily predicate to a boolish one: (pred? #t, #f)! nip. Maybe with ?? yields bool, with ? yields a filter.

Then you'd have v (even? drop T, drop F)!.

(! drop #t; drop #f) :boolean

[vs / even?]              # --> [2]
#{vs / even?}             # --> #{2}
[vs / (even?) boolean]    # --> [#f #t #f]
#{vs / (even?) boolean}   # --> #{#f #t}

Preserves-path

You could recast preserves-path in this system:

/            # Moves into immediate children (values / fields)
//           # Flattens children recursively
key .        # Moves into named child
.^           # Moves into record label
.keys        # Moves into *keys* rather than values
.length      # Moves into the number of keys
.annotations # Moves into any annotations that might be present
.embedded    # Moves into the representation of an embedded value

                 # Accepts all
fail             # Rejects all

literal eq       # Matches values (equal to/less than/greater than/etc.) the literal
literal =
literal ne
literal !=
literal lt
literal gt
literal le
literal ge

regex re          # Matches strings and symbols by POSIX extended regular expression
regex =r

pred              # Applies predicate to each input; keeps inputs yielding success

literal ^         # Matches a record having a the literal as its label -- equivalent to dup .^ literal =

~real             # Promotes int to double, passes on double unchanged, rejects others
                  # Out-of-range ints (too big or too small) become various double infinities
                  # Converting high-magnitude ints causes loss of precision

~int              # Converts double to closest integer, where possible
                  # NaN and infinities are rejected

bool?             # Type filters
double?
int?
string?
bytes?
symbol?
rec?
seq?
set?
dict?
embedded?

Existing preserves-path has <count selector>, "Counts number of results of selector":

(:filter [filter] length) :count

or

([over over !] length nip nip) :count

which you might use as in [1 2 3 4 5 6] (/ even?) count. (This suggests reframing accumulation to be more general, to admit aggregate operators like count and group-by as well as push-onto-sequence etc.)

(Hmm: expanding count, we have [1 2 3 4 5 6] [/ even?] length nip. Hmm.)

The examples become:

  • .annotations =Documentation ^ 0 . /
  • // dup .^ (:=Test, :=NondeterministicTest)! dup 1 . rec?

Figuring out what / means

Clearly / is just one operator for introducing branches; // is another example.

So let's imagine a word branch that splits execution into two, with #f and #t pushed in each of the new branches.

(:n :c n 0 gt (c (c) n 1 - times) when) :times
(:n :c n 0 gt (((c) n 1 - timesK) c) when) :timesK
(:vs 0 (:k :n branch (vs n .) (n 1 + k) if) vs length timesK) :/

A branch succeeds if either or both its branches succeed, failing only if both branches fail.

A branch always succeeds, even if both its branches fail. This is because we want to use failure to e.g. filter lists, like this:

[vs / string?]

and such filtering should be able to easily yield an empty list if there are no elements in the input matching the filter.

The positive stack effects of the (non-failing) branches are pushed as the unified effect of the branch itself.

We can construct par/collect in terms of / (if we forgo syntax for it, which is probably the right thing to do):

[(A) (B) (C)] / !      =~=       par (A ; B ; C)

Still need to come back to examples like [vs / dup 10 +, 5] and [branch (3) (4) if, 5], to figure out the interaction between branch and ,.

My initial instinct is that , should end a branch, so that would yield

[vs / dup 10 +, 5]       # --> [1 11 2 12 3 13 5]
[vs / dup 10 + 5]        # --> [1 11 5 2 12 5 3 13 5]
[branch (3) (4) if, 5]   # --> [3 4 5]
[branch (3) (4) if 5]    # --> [3 5 4 5]

Simpler branch

Let's imagine a word catch that takes the closure on the top of stack and executes it in a special context such that failure causes a stack reset. Can we build branch from catch?

One downside to catch is the closure: the nice thing about branch is that it works with a kind of continuation, rather than a closure.

So we can't build a continuationish branch, but if the goal is to build a closureish branch, then we kind of can, so long as we have a "flatten this sequence onto the stack" operator:

(:k [(#t k) catch] sequence-to-stack [(#f k) catch] sequence-to-stack) :branch

Sadly a continuationish catch doesn't make sense absent continuation-capture operators, since there's no reified object which can be invoked multiple times.