My lambda interpretter is comming along nicely. Already it is able to 
perform any computation in the pure lambda calculus, and can do a number 
of other things besides.

(Before I go any further, let me just say... RECURSIVE LET-BINDS! 
GAAAH!!! >_< Who'd have thought that such a simple feature could be so 
mind-blowingly complicated to get right?)

Anyway, the lambda calculus is a truly inefficient language. I'd like to 
share with you just *how* in efficient it is. I did this by asking it to 
compute a few factorials.

1! took 80 interpretter steps.

2! took 200 interpretter steps. The generated HTML trace was 2.5 MB in size.

3! took... well actually, I don't even know how many steps it was. It 
took my humble Sempron something like 20 seconds to perform the 
operation, and the generated HTML trace was 20.5 MB in size. (!!!) When 
I asked Firefox to display this, it started to eat RAM like it was 
candy. I was quickly forced to terminate Firefox before it broke my VM 
system.

Note that the program did in fact produce the correct answer in each 
case. It was just very inefficient. ;-)

But then, what do you expect from a programming language where you have 
to "define" what arithmetic *is* before you can do any calculations?

Anyway, the lambda calculus is fairly slow. But there _is_ a language 
which is significantly less efficient again: The SKI combinator 
calculus. Guess where I'm going next?

I can't wait to see how many million steps it takes to compute 5! in the 
SKI calculus!



The command to compute the factorial is of course quite simple:

let pred = \n f x -> n (\g h -> h (g f)) (\a -> x) (\b -> b); is_zero = 
\n -> n (\x -> False) True; prod = \n m f x -> n (m f) x; y = \f -> (\a 
-> f (a a)) (\b -> f (b b)); fac = \f -> \n -> is_zero n 1 (prod n (f 
(pred n))) in y fac 1

This is "quite simple" in the style of Bash.org quote number #464385:

<@insomnia> it only takes three commands to install Gentoo
<@insomnia> cfdisk /dev/hda && mkfs.xfs /dev/hda1 && mount /dev/hda1 
/mnt/gentoo/ && chroot /mnt/gentoo/ && env-update && . /etc/profile && 
emerge sync && cd /usr/portage && scripts/bootsrap.sh && emerge system 
&& emerge vim && vi /etc/fstab && emerge gentoo-dev-sources && cd 
/usr/src/linux && make menuconfig && make install modules_install && 
emerge gnome mozilla-firefox openoffice && emerge grub && cp 
/boot/grub/grub.conf.sample /boot/grub/grub.conf && vi 
/boot/grub/grub.conf && grub && init 6
<@insomnia> that's the first one

(Bash.org appears to be down at present.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message