Separating Program Evaluation From Description

Stream, Lazy, Map, Filter, EVAL

Guowei Lv

4 minute read

5.3 Separating program evaluation from description

This is the title of Chapter 5.3 from the book Functional Programming in Kotlin.

Everyone knows that a program is a list of instructions that will be executed/evaluated in the order they are written in.

fun exec() {
  doThis()
  doThat()
  doMore()
}

So the description decides the evaluation. What does it mean to separate them? I mean, can they be different?

Let’s define a lazy Stream:

sealed class Stream<out A>

data class Cons<out A>(
    val head: () -> A,
    val tail: () -> Stream<A>
) : Stream<A>()

object Empty : Stream<Nothing>()

Here are some helper functions:

// Memoized constructor
fun <A> cons(hd: () -> A, tl: () -> Stream<A>): Stream<A> {
    val head: A by lazy(hd)
    val tail: Stream<A> by lazy(tl)
    return Cons({ head }, { tail })
}

// Convinient empty constructor
fun <A> empty(): Stream<A> = Empty

// Helper function to create a Stream
fun <A> streamOf(vararg xs: A): Stream<A> =
    if (xs.isEmpty()) empty()
    else cons({ xs[0] }, { streamOf(*xs.sliceArray(1 until xs.size)) })

Next, let’s define map and filter for it.

fun <A, B> Stream<A>.map(f: (A) -> B): Stream<B> {
    return when (this) {
        is Cons -> {
            cons(
                { f(head()) },
                { tail().map(f) })
        }
        is Empty -> {
            empty()
        }
    }
}

fun <A> Stream<A>.filter(p: (A) -> Boolean): Stream<A> {
    return when (this) {
        is Cons -> {
            if (p(head())) {
                cons(head) { tail().filter(p) }
            } else {
                tail().filter(p)
            }
        }
        is Empty -> {
            empty()
        }
    }
}

What actually will happen if we do this?

streamOf(1, 2, 3, 4)
        .map { it + 10 }
        .filter { it % 2 == 0 }
        .map { it * 3 }

There is a trace analysis in the book, but it is rather abstract. I sort of get the idea, but not a very solid one. So I think I can break down the steps by hand, to get a better mental model of how to think of such operations.

Here we go:

streamOf(1, 2, 3, 4)
    .map { it + 10 }
    .filter { it % 2 == 0 }
    .map { it * 3 }
cons({ 1 }, { streamOf(2, 3, 4) })
    .map { it + 10 }
    .filter { it % 2 == 0 }
    .map { it * 3 }
cons({ 11 }, { streamOf(2, 3, 4)
                   .map { it + 10 } })
    .filter { it % 2 == 0 }
    .map { it * 3 }
streamOf(2, 3, 4)
    .map { it + 10 }
    .filter { it % 2 == 0 }
    .map { it * 3 }
cons({ 2 }, { streamOf(3, 4) })
    .map { it + 10 }
    .filter { it % 2 == 0 }
    .map { it * 3 }
cons({ 12 }, { streamOf(3, 4)
                    .map { it + 10 }})
    .filter { it % 2 == 0 }
    .map { it * 3 }
cons({ 12 }, { streamOf(3, 4)
                   .map { it + 10 }
                   .filter { it % 2 == 0}})
    .map { it * 3 }
cons({ 36 }, { streamOf(3, 4)
                   .map { it + 10 }
                   .filter { it % 2 == 0 }
                   .map { it * 3 }})

The pattern here is that the first value is always prepared, and the rest is wrapped for later.

If we just write: 

streamOf(1, 2, 3, 4)

Then it will be evaluated as: 

cons({ 1 }, { streamOf(2, 3, 4) })

Notice that the first value 1 is prepared, and the rest is wrapped in a function.

Now how about we add a map to it: 

streamOf(1, 2, 3, 4)
    .map { it + 10 }

This will be evaluated as:

cons({ 11 }, { streamOf(2, 3, 4)
                   .map { it + 10 } })

Again, notice that the first value 11 is already prepared, and the rest is in a function.

Let’s add the filter now:

streamOf(1, 2, 3, 4)
        .map { it + 10 }
        .filter { it % 2 == 0 }

This will be evaluated as:

cons({ 12 }, { streamOf(3, 4)
                   .map { it + 10 }
                   .filter { it % 2 == 0}})

The filter is more interesting, cause it will keep evaluating until it finds the first item that will not be filted out. Thus there are a few more steps to get the first value 12 there.

I think you get it now, the pattern is quite obvious.

So back to the question from the beginning of this article.

What is the description?

In this case the description is:

streamOf(1, 2, 3, 4)
        .map { it + 10 }
        .filter { it % 2 == 0 }
        .map { it * 3 }

We would expect something like this:

(1, 2, 3, 4) ->
(11, 12, 13, 14) ->
(12, 14) ->
(36, 48)

But in reality, the evalutaion order is:

1 ->
11 ->
2 ->
12 ->
36 ->
...

Thus the separation from description from evalutaion.

comments powered by Disqus