|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |