Infinite Functions

A cool recent development in Scotch: functions that never end, which can be used in combinination with take to get a specific number of results and stop evaluating.

There are a few functions now that use "filter" on an infinite list, i.e.

evens = filter(even, [1..])

which returns all even numbers, which there are infinitely many of. If you try to evaluate "evens" the interpreter will hang, trying to call the "even" function on an infinite list.

Unfortunately, it's impossible for Scotch to figure out that this is an infinite list; that would be equivalent to solving the halting problem, an undecidable problem in computer science. It's impossible to even tell that the evaluation of [1..] does not terminate. Why? Well, for starters, how can we tell that [1..] is not just [1..1000]? We can only tell when the evaluation of [1..] reaches 1001. But then we don't know that it's not just [1..1002]. Basically, you can't predict future behavior of the list; you can only know that it has terminated. If it never terminates, you have no way of knowing it never will. So, Scotch will happily try to evaluate this infinite function.

In practice, infinite functions can be used like this:

take 100 from evens

or

take 1000 from primes

to get a set number of results from a function that never terminates.

I also tweaked things so that using take with the sum of a list and something else will evaluate to just take from the list if it's long enough. So infinite functions that involve addition, like this,

infinite_range(n) = [n] + infinite_range(n + 1)

can be used in combination with take to get a set number of results:

>> take 10 from infinite_range(1)
[1,2,3,4,5,6,7,8,9,10]

This type of expression required a different approach to be evaluable. The function, when called, would evaluate like this:

• [1] + infinite_range(2)
• [1] + ([2] + infinite_range(3))
• [1] + ([2] + ([3] + infinite_range(4)))
• ...

The problem here is that the never terminating (and therefore never fully evaluable) function infinite_range is always trapped inside parentheses with the elements that need to be added to the list, so this function could never be evaluated.

The solution was to automatically rewrite addition expressions associatively: a + (b + c) should always be rewritten as (a + b) + c. This allows infinite sums like infinite_range to evaluate to [n, n+1, n+2 ... n+m] + infinite_range(n+m+1) which can be used in combination with "take m" to get the list of m elements.