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.