[really string rewriting, but I trust
the parallels are obvious...]
While playing with sed guarded commands:
<http://www.ai.mit.edu/~gregs/ll1-discuss-archive-html/msg02007.html>
I wound up making some progress on the
plausibility of linda-sed:
<http://lists.canonical.org/pipermail/kragen-discuss/2002-July/000848.html>
The first step was to write in a sort of
"ratsed", which consists of sequences of
substitutions, choices [ this :: that ],
and loops { every :: this :: that }.
It makes the logic somewhat clearer (but
leaves the implementation sadly opaque).
> # main: bracket qsort unbracket
> # qsort: { zero :: one :: init-part { partition } fini-part }
>
> /[^0-9]*\([0-9]*\).*/{\1}/ # ...xs... -> {xs}
> { /[ ]*{} \([^ ]*\)/ {\1}/ # {} xs -> {xs}
> :: /[ ]*{\(.\)} \([^ ]*\)/\1 {\2}/ # as {a} xs -> as/a {xs}
> :: # {x/xs} -> {xs x <table> }
> /{\(.\)\([^ ]*\)}/{\2 \1 9876543210 }/
> { # {y/as x <table> zs}
> # -> {as x <table> y/zs},
> # when y before x in <table>
> /{\([^ ]*\)\(.\)\([^ ]*\) \(.\) \([^ ]*\2[^ ]*\4[^ ]*\) /{\1\3 \4 \5
>\2/ } # {as x <table> zs}
> # -> {as} x zs
> /{\([^ ]*\) \(.\) \([^ ]*\) \([^}]*\)}/{\1} \2 \4/ }
> /{}// # as {} $ -> as
What surprised me is that my buggy ratsed
preprocessor (with sequences unimplemented)
still produced a working script.
> #!/bin/sed -f
> s/[^0-9]*\([0-9]*\).*/{\1}/;:0
> s/[ ]*{} \([^ ]*\)/ {\1}/;t0
> s/[ ]*{\(.\)} \([^ ]*\)/\1 {\2}/;t0
> s/{\(.\)\([^ ]*\)}/{\2 \1 9876543210 }/;:1
> s/{\([^ ]*\)\(.\)\([^ ]*\) \(.\) \([^ ]*\2[^ ]*\4[^ ]*\) /{\1\3 \4 \5 \2/;t1
> s/{\([^ ]*\) \(.\) \([^ ]*\) \([^}]*\)}/{\1} \2 \4/;t0
> s/{}//
This is because the representation during
the partition and sort phases is distinct,
so partitioning still happens atomically
despite being inlined in the sort loop.
How much of the control flow is required?
Using the same trick as in the outer loop,
walking a cursor along the input, leaves
the inner loop redundant.
After tightening up the logic* (which ewd
says we should do anyway) what remains is
a system of substitions which will finish
the computation with very few restrictions
on the order in which they operate, and
could even sort several different strings
in parallel in a linda system.
> #!/bin/sed -f
> s/[^0-9]*\([0-9]*\).*/{\1}/
> #### start vat
> t0;:0;l
> s/{}$//;t
> s/{\(.*\)| \(.\) \([^ ]*\) \([^}]*\)}/{\1} \2 \4/
> s/{\(.*\)|\([^ ]\)\([^ ]*\) \(\2\) /{\1\2|\3 \4 /
> s/{\(.*\)|\([^ ]\)\([^ ]*\) \(.\) \([^ ]*\4[^ ]*\2[^ ]*\) /{\1\2|\3 \4 \5 /
> s/{\(.*\)|\([^ ]\)\([^ ]*\) \(.\) \([^ ]*\2[^ ]*\4[^ ]*\) /{\1|\3 \4 \5 \2/
> s/{\(.\)\(.[^ ]*\)}/{|\2 \1 9876543210 }/
> s/[ ]*{\(.\)} \([^ ]*\)/\1 {\2}/
> s/[ ]*{} \([^ ]*\)/ {\1}/
> t0
> #### end vat
Perhaps it would be better to leave the final
undecoration (/{}$//) up to consumers of the
vat -- they could then randomly read strings
from the vat, and return the ones which were
still being sorted.
-Dave
* there is an interesting parallel with the
excluded middle here: with a control flow,
after { A :: B } we know ~A and ~B; without
control flow, negative cases must be written
explicitly as positive patterns.
