cdiggins.com

My friend Frank said he found it hard to wrap his head around Cat infinite lists. The “n” operation, for example, returns a list of all the number from 0 to some upper bound (it is implemented using range_gen). However, an implementation of Cat  is free to implement the list in any way as long as all the list operations are available. It doesn’t even have to allocate a block of memory.

So the creation of the list, mapping the list, getting the size of the list, and getting the nth item can all potentially run in constant time regardless of the size of the list. The following is purely interpreted code without any optimizations:

>> 1000000000 n [2 * 1 +] map count 2 / nth
Time elapsed : 0.00 msec
stack: ( 1, 3, 5, 7, …) 1000000001

Yes that is 0.00 msec (give or take 0.15 msec which is the resolution of the internal timer) .

The next logical question would probably be: what if someone writes code which doesn’t use “n” or “range_gen”. For example:

nil 0 [[cons] keep inc] [dup billion <] while pop

Doesn’t that create a list of a billion cons cells? Well only if you don’t have a optimizer, which the current Cat implementation unfortunately doesn’t. :-(

But since I love theory, lets talk about how an optimizer could identify the pattern as being an opportunity to use a generator instead of the loop. The algorithm is pretty simple (with a fair amount of hand-waving):

1. Establish that there are no side-effects
2. Get the initial values: $a=nil and $b=0
3. Check that $a is a list, and $b is an integer, if not abandon hope.
4. Compute the relation between iterations of the loop ($a:list $b:int -> (cons($a, $b), inc($b)))
5. Use that to establish the relation beween consecutive list items: $c = [inc]
6. Compute the terminating relation in terms of $b if it can (otherwise exit): $d = [1000000000 <]
7. Rewrite the algorithm as: $b $c $d gen

Now you have 

0 [inc] [billion <] gen

This isn’t quite as efficient though as a “range_gen” function. To go from a “gen” to a “range_gen”, you need to notice that inc is the same as [x +] where x=1. You also note that the terminating condition is a simple comparison: [y <]. Therefore you can easily rewrite a “gen” function with those properties as:

0 y range_gen [x *] map

or in terms of the example: 

0 billion range_gen [1 *] map

which is easily identified as beign the same as:

billion n [1 *] map

and finally it is a trivial observation that [1 *] map is superflous:

billion n

 And that’s that.