On 22/07/2015 08:32 AM, scott wrote:
> An interesting read... What are the uses of SKI then, apart from just
> making simple algorithms take up a million characters to encode?

Erm... that's pretty much the only use.

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!)

>> Still, this whole idea came about as I was thinking about a Bash script
>> that contains a tarball that it then unzips, which mostly contains a
>> giant SKI program and the SKI interpreter. Good luck to anybody trying
>> to reverse-engineer that! ;-)
>
> Sounds like the start of an IOCCC entry to me

That's pretty much what I was channelling, yeah.

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...

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.

> although it seems the
> recent entries are just ridiculous (like PC emulators, ray tracers and
> realtime CFD solvers in a few lines of gibberish C code with lots of
> commas).

Ah, C. The entire language is specifically designed for crazy.

> I once wrote an interpreter for a one instruction set computer (that's a
> lot easier than what you did!) and even wrote the code to generate prime
> numbers using it, but it got complicated and boring very quickly to do
> anything useful.

Quitter. ;-)

My dream is to build non-trivial programs, encode them to SKI, and then 
marvel at how huge they are. A bit like compiling Hello World in Eiffel 
and then looking at the 25MB executable it produces.

> OK I found it on my old HD, see attached, it should(!)
> compile and output all the prime numbers up to 1000. I wouldn't attempt
> to try and figure out how it's doing it though :-)

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 have a feeling though, writing a prime number generator in SKI might
> be a tad longer...

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 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...]

Post a reply to this message