> Although, Wikipedia does mutter something about people making silicon
> that runs SKI commands directly. (Not exactly sure how that would work,
> but you can imagine a CPU with only 3 possible opcodes would be quite
> simple to implement... Certainly a damned site easier than trying to
> implement the full lambda calculus!)

As I found with my OISC interpreter though, you just shift the 
complexity away from the CPU/interpreter and into the program itself. In 
a real system you'd probably end up with a "core" library to do things 
like add, subtract etc, and then because every single program uses those 
library calls, you might as well implement them in hardware...

> I actually started thinking about a POV-Ray SDL program that's actually
> a self-decompressing program that then executes SKI code to build a
> scene description. But maybe that's just crazy...

Yes that's crazy, but so long as the output was half-decent I'm sure it 
would generate a lot of interest after someone asked to see the source 
code :-)

> Either way, I figured nobody would ever figure out WTF it actually does.
> I would think the set of people who know how to unravel obfuscated shell
> code and the set of people who know about theoretical models of
> computation are totally disjoint.

I wouldn't say *totally*.

> Uh... I don't even... How can you index an integer as if it's an array?
> If my understanding is not wildly broken, that's Undefined Behaviour...

I think that was one of the first things I learned from the IOCCC! a[b] 
means read the value at memory address a+b*L, where L is the length of 
each array element in bytes. If L=1 then a[b] == b[a]. Also if you then 
use that value to index into another array: c[ a[b] ], by the same rule 
that is equivalent to a[b][c] or any other combination you can come up with.

> Division is fairly hard to implement in the lambda calculus. (Depending
> on which way you encode integers.) The Fibonacci numbers should be
> comparatively easy to compute, however.

In my OISC code I used a prime sieve to avoid having to do any 
multiplications or divides. The only tricky bit was having to use 
self-modifying code to write the results to the correct place in the 
output array.

> [In fact, I managed to write a working implementation for that in my
> lunch break. But it uses Church numerals, whereas the SKI interpreter I
> wrote expects the output to be a linked list of Church Bools. It
> shouldn't be too hard to convert, but I haven't done it yet...]

I tried figuring out Fibonacci numbers in my head the other day (it was 
a game-show question on TV) - I got lost pretty quickly, it's a lot 
harder than you think without any pen and paper.

Post a reply to this message