On 20/07/2015 10:03 PM, Orchid Win7 v1 wrote:

> Rule #5: "G" - Read one bit of input. Delete the G and replace it with:
>
> + S(K(S(SI(K (KI) )))G if the bit read was 0
> + S(K(S(SI(K (K ) )))G if the bit read was 1

Alternatively, if reading the input reached EOF, replace G with K.

> Rule #7: "P" - Delete the P, keep the next item, insert O, Z after it.

I haven't looked into it properly yet, but it ought to be possible to 
dispense with this rule.

> The first 4 rules constitute the entire SKI calculus. The 5 subsequent
> rules specify how to perform I/O.

Overall, I'm a little disappointed with how "complicated" this stuff 
looks. It's meant to be like "wow, this is so simple, yet you can write 
entire programs with it? No way!" But it comes across as maybe too 
complicated for that.

> My initial thought was that certainly the first 4 rules ought to be
> pretty simple to implement using sed (the Unix Stream EDitor). However,
> sed only understands regular expressions, and such a construct cannot
> handle *nested* brackets. For that, you need a context-sensitive grammar.
>
> After many experiments, I hit upon a single idea: represent
> single-letter items as themselves, and represent compound items by ID
> numbers.

It's really not hard to write a Bash script that linearly scans the 
input, keeping a count of how many brackets it's seen, and handle items 
that way. Trouble is, I anticipate "real" SKI programs being very large 
indeed, and this method requires copying potentially huge blocks of text 
around. OK, you can copy one character at a time, but Bash isn't noted 
for being a high-performance I/O engine.

By contrast, by working with item IDs, each individual item is actually 
tiny. We also get "full sharing" (i.e., if a sub-expression gets 
duplicated [as the S command happens to do], then it still only gets 
"executed" once).

Hypothetically, it could do with some kind of "garbage collector", which 
removes item files that are no longer reachable. In practice, I doubt 
you're going to run out of disk space. And it's not like we can reuse 
item IDs (unless you start also renumbering items!)

> Assumptions / limitations:

> * There is minimal error-checking. It isn't hard to add this, but it
> makes the shell script longer than 99 lines. I wanted to show how
> "simple" the job is, without a lot of error-handling clutter.
>
> * In particular, mismatched brackets or incorrect SKI programs will
> probably provoke utterly baffling failures.

Also, illegal characters in the input (e.g., J) will get silently 
ignored, rather than reported as an error. Also note that SKI programs 
are case-sensitive.

Post a reply to this message