[FoRK] The World's Smallest Programming Language

Dave Long < dave.long at bluewin.ch > on > Mon Sep 11 08:03:42 PDT 2006

> Seems to me there's probably some interesting intersection there with
> algorithmic information theory, Chaitin incompleteness / Kolmogorov
> complexity.

If these are the iota and jot I'm thinking of, see also "zot":
     http://ling.ucsd.edu/~barker/Iota/zot.html
where he mentions Tromp's influence.
     http://homepages.cwi.nl/%7Etromp/cl/lazy-k.html

One very practical issue with combinator reduction is that it can be 
not only exponentially larger, but also slower, than lambda or graph 
evaluation.

Maybe I just need to read the speed prior stuff more closely, but it 
seems that if algorithms jump drastically between big-O classes 
depending upon whether they're expressed with naming/sharing or not, it 
would affect which programs were chosen by a speed prior.  Or does time 
expand pretty uniformly across codes?

Depending upon how much you care, this might be a question for kc-list.

-Dave


More information about the FoRK mailing list