On 23/07/2015 08:25 AM, scott wrote:
>> 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.

Indeed. The simpler the language, the more complex the programs.

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

Hehe, we'll see. ;-)

You may remember many years ago I built a self-decompressing SDL program 
based on Huffman codes. Oh, the compressor was written in Smalltalk, but 
the decompressor was SDL. It decompresses itself and then runs the 
result. Curiously, when I posted it somebody instantly recognised the 
decompression algorithm, despite the set of people who know 3D and the 
set of people who know data compression being completely disjoint...

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

In other news: I often wonder just how hard it "really" is to 
reverse-engineer compiled Haskell code. Supposedly it's intractably 
hard, since GHC aggressively optimises your Haskell code, and the result 
is statically linked against a non-trivial run-time system, and it does 
things like store the call stack on the heap and other strangeness... 
OTOH, game studios deliberately obfuscate stuff all the time, and this 
stops approximately 0% of all cracking attempts.

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

Which would mean, for an int variable, unless b=0 you are now accessing 
undefined memory locations. That's UB. At this point you have to *guess* 
what appears next in memory (which is compiler-dependent).

> If L=1 then a[b] == b[a].

Uh, how do you figure? The memory locations of the two variables might 
be in no way related.

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

That seems clear enough.

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

I don't have it with me, but I did manage to come up with a recursive 
algorithm for generating prime numbers. It's based on the fact that the 
prime numbers repeat, until multiples of the next prime come into play. 
The algorithm is tricky as hell to get right, but it's quite nice when 
it works. Does require O(N!) RAM though...

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

What, you can't compute the square root of 5 in your head? ;-)

No, seriously - humans have shallow stacks.

Post a reply to this message