I remember the day I got the mind shift about functional programming. I switched from being a fervent defender of Java and C# to a passionate of LISP dialects. At the time I was convinced that there were nothing better than OOP and curly bracket syntaxes. I was then fighting for conventions and simplicity rather than language expressivity.
As a good ignorant I thought that languages evolved with the time, and that these problems were not addressed because nobody thought about them before. And I discovered LISP the second oldest programming language with none of these problems and even powerful features other languages don’t have such as macros or continuation capture. I got interested in functional programming languages and I learned Haskell, CAML, and finally F#.
I don’t know why but the concept of sequences in functional programming languages amazed me.
How do you perceive infinity?
“How do we perceive infinity?” This is the way Gerald Jay Sussman and Guy L. Steele introduced their presentation about sequences (streams in LISP).
I never thought about it before, since resources on a computer are finite. But interesting question, let say I want to represent the infinite sequence of numbers, what characterizes this infinity and makes it exist? Is it the fact that these numbers are all present in the computer memory at the same time (which is impossible) or the fact that I can get one of them when needed.
How could we possibly define the infinite sequence of natural integers?
Starting from 0 we can recursively define these numbers just by adding one, however this recursion shouldn’t take place until needed, so that the whole number sequence is never in memory. There is no choice that to delay the evaluation of the recursion building the sequence. We could take advantage of the fact that list are pairs, the car of the pair would be a value and the cdr of the pair a delayed evaluation leading to a pair. Delaying a computation, it’s when laziness comes into play.
What is laziness?
Wikipedia: “Laziness (also called indolence) is a disinclination to activity or exertion despite having the ability to do so. It is often used as a pejorative; related terms for a person seen to be lazy include couch potato, slacker, and bludger.”
We are close to what we need !
Although very useful to deal with infinity, as for human laziness is unfortunately not well considered by programming languages. Indeed most programming languages favor eager evaluation over lazy evaluation.
“Never put off until tomorrow what you can do the day after tomorrow.”
Eager evaluation consists in evaluating as soon as possible expressions whereas lazy evaluations consists in evaluating an expression only when it is actually needed.
Below is an example:
In a language like C# this program does nothing valuable except crashing (by exploding the stack). In a language using lazy evaluation this program does nothing. Why? Because DoNothing does nothing with its argument x, so why computing it? However with eager evaluation we start computing immediately the value of x although we don’t need it!
If you think about it you already know some cases of laziness:
Indeed in all languages conditional expressions are lazy. Why? Because if they weren’t, both the consequence and the alternative branches of the condition would be evaluated! However what is expected from a conditional expression is to first evaluate its condition and then depending on the result either evaluate the consequence or the alternative branch. In the same way the and and or short-circuit operators are lazy.
An other way of achieving laziness is to capture expressions into functions. By doing so we are capturing the future of an expression, the value in becoming of this expression, also called its continuation. The problem in languages which doesn’t favor laziness is that you would have to build all these continuations by hand and call them at the right place when needed.
In F# you can get laziness using the lazy keyword or by building sequences. This will ensure you that this expression will be evaluated only when needed.
Let’s do it
Ok we know that we need to build an infinite sequence using laziness. F# has its own sequence type that I am going to present you later, now I want you to look at a simple implementation of infinite sequences (which is really inefficient due to boxing and unboxing needed to escape static typing), the only purpose is to show you how it works:
Here is the result:
Look the infinite integers sequence is a list which starts by 0 and whose next value is not computed yet: “Value is not created”.
With lazyMap, lazyFilter you can operate on integers to create new infinite lists ! If you look at the lazyMap and lazyFilter function definitions you won’t find any break condition, these functions don’t need to stop, since they are working on data with infinite length !
Why do we need lazy sequences?
What are F# sequences?
F# sequences are created using the seq computation expression (cf. my article to come on Workflows). They are represented by the generic type seq<’a> with ‘a being the type of the elements in the sequence. Under the hood they map the well known .NET type IEnumerable<T>. The Seq module provides for use with sequences most of the functions working with lists. Finally F# arrays and lists are instance of seq<’a>.