4. Expression Evaluation, Laziness & More About Functions

Written by Massimo Carli

In the previous chapters, you learned that you can define a function as “a bunch of code that might be executed later”. You also learned several interesting points:

• As a software engineer, you write code and, more specifically, you write functions.
• If the functions you write are pure, their bodies are referentially transparent expressions.
• Executing a function means evaluating the expression in its body.
• “Executed later” means the expression of a function is evaluated at a time that isn’t related to the position of the expression itself.
• It’s possible that a function is never executed and the expression never evaluated.

Evaluation strategy is the relationship between the position where you define the expression in your code and the point when the expression is actually evaluated. In this chapter, you’ll learn about two different evaluation strategies:

• Applicative-order evaluation
• Normal-order evaluation

These two evaluation strategies will lead you to other very important concepts in this chapter:

• The evaluation strategy for Kotlin.

• What strictness and laziness mean.

• How lambda expressions allow you to execute your code later.

• The Kotlin lazy function and how to use it to improve performance.

• How to implement memoization for pure functions in Kotlin.

• How to implement infinite Streams of data using lazy functions.

Again, all this uses Kotlin and many engaging exercises and challenges. Open up the starter project for this chapter to begin!

Expression evaluation order

As you know, you can write a pure function and execute it much later. Here’s an example to help you understand how the position of an expression relates to the time it’s evaluated.

Suppose you want to evaluate the following expression that calculates triple the average of two values:

3 * avg(x, y)

To represent this expression as a function, write the following code in the initially empty Evaluation.kt file in this chapter’s material:

fun add(x: Int, y: Int): Int { // 1
  val result = x + y
  println("add") // 5
  return result
}

fun triple(x: Int): Int { // 2
  val result = add(add(x, x), x)
  println("triple") // 5
  return result
}

fun divide(x: Int, y: Int): Int { // 3
  val result = x / y
  println("divide") // 5
  return result
}

fun average(x: Int, y: Int): Int { // 4
  val result = divide(add(x, y), 2)
  println("average") // 5
  return result
}

In this code, you:

1. Create add, which returns the sum of the two input values.
2. Define triple, which uses add twice. This is possible because addition is associative, as are pure functions. You also know that pure functions and types create a category, which has associativity by definition.
3. Implement divide, which returns the division between the two input values. This is a division of Ints, so the result will always round down to a whole number. In this context, the precision of the function doesn’t really matter, so that’s OK. :]
4. Create average, which uses divide and add.
5. All these functions would be pure, but you added some println just to understand how and, more importantly, when they’re evaluated. It’s important to note how println follows the evaluation of the expression, giving evidence of the actual execution.

Now, write and run the following:

fun main() {
  triple(average(2, 4))
}

You get the output:

add
divide
average
add
add
triple

At first glance, you see that triple is the function evaluated last.

To understand why, apply the substitution model like this:

triple(average(2, 4)) // 1
triple(divide(add(2, 4), 2)) // 2
triple(divide(2+4, 2))
triple(divide(6, 2)) // 3
triple(6/2)
triple(3)
add(add(3,3), 3) // 4
add(3+3, 3)
add(6, 3) // 5
6+3
9

In the previous representation, you see that you always reduce the expression that allows you to give the leftmost function all the value it needs. In particular:

1. To resolve triple, Kotlin needs to resolve the expression you pass as an input parameter: average.
2. Next, you need to evaluate and give divide the value it needs as input: the sum of 2 and 4. This is why Kotlin evaluates add(2, 4) first.
3. At this point, divide has all the values it needs, and Kotlin starts the divide evaluation.
4. It’s now time to evaluate triple, which needs to evaluate the add you have as the first input parameter.
5. Finally, you reduce everything to the value 9, which you can see by printing the result of the expression using this code:

fun main() {
  val result = triple(average(2, 4))
  println(result)
}

The previous example proves that in Kotlin, a function’s arguments are evaluated before the function is applied, which is the definition of applicative-order evaluation. With applicative-order evaluation, a function executes only when all the expressions you pass as input parameters are evaluated, starting from the leftmost parameter.

Note: Another name for Kotlin’s applicative-order evaluation is eager evaluation.

But is this evaluation strategy good or bad? How would the same expression be evaluated in the case of normal-order evaluation, and what would the advantages be? Before exploring that, it’s important to see some more examples.

Applicative-order evaluation examples

You just learned what applicative-order evaluation is, resolving a simple expression in Kotlin. To better understand what the consequences are, open the initially empty ApplicativeOrder.kt and write the following code:

fun greaterThan10(x: Int): Boolean { // 1
  println("greaterThan10") // 2
  return x > 10
}

fun main() {
  val inputValue = 3
  if (inputValue > 4 && greaterThan10(inputValue * 2)) { // 3
    println("OK") // 4
  } else {
    println("KO") // 4
  }
}

In this code, you:

1. Define greaterThan10 as a simple function returning a Boolean stating whether the input value is greater than 10.
2. Use println to give some evidence of the invocation of greaterThan10.
3. Define a simple test to check if the value of a local inputValue variable is greater than 4 and whether the result of greaterThan10 passing inputValue * 2 as input is true.
4. Print OK or KO if the test is true or false, respectively.

Run the previous code, and you’ll get:

KO

This is because inputValue isn’t greater than 4. The interesting part is that greaterThan10 wasn’t even invoked. The reason is the use of &&, which is a short circuit operator. When you resolve A && B, a false value of A makes the whole expression false and the evaluation of B would be irrelevant.

Note: The same is true with the || operator. In the case of A || B, a true value for A would make the whole expression true. The evaluation of B would then be irrelevant.

Now, change the previous example like the following, assigning 30 to inputValue and passing it to greaterThan10:

fun main() {
  val inputValue = 30 // HERE
  if (inputValue > 4 && greaterThan10(inputValue)) {
    println("OK")
  } else {
    println("KO")
  }
}

Run the code and find:

greaterThan10
OK

In this case, inputValue > 4 evaluates to true and && requires the evaluation of greaterThan10(inputValue). This is why you see greaterThan10 as part of the output.

So far, so good. This is how && works. Now, change the previous code like this:

fun main() {
  val inputValue = 3 // 1
  val greater10 = greaterThan10(inputValue) // 2
  if (inputValue > 4 && greater10) { // 3
    println("OK")
  } else {
    println("KO")
  }
}

In this case, you:

1. Use 3 as the initial value for inputValue.
2. Invoke greaterThan10, passing inputValue as input.
3. Use greater10 in the condition for if.

This is equivalent to the very first example but, when you run the code, you get the following output:

greaterThan10
KO

The output contains KO, but greaterThan10 has been invoked anyway. This might look obvious because you evaluate greaterThan10 before the test, and you don’t know yet if the if condition would require it or not.

However, is it possible to define the invocation of greaterThan10 in the same position as the last example but then execute it when you actually need it? The answer is yes, using lazy evaluation with lambda expressions.

Understanding lambda expressions

A lambda expression is simply an anonymous function you can use as a value. This basically means that:

• You can define a lambda expression on the fly, assigning it to a variable.
• As you’ll see in detail in Chapter 5, “Higher-Order Functions”, you can use a lambda expression as an input parameter or the result value of another function.

You define a lambda expression by adding a normal expression in a code block. The following is a perfectly valid lambda expression you can find in Lambdas.kt in this chapter’s material.

val empty = {}

In the case of an input parameter, you define a lambda expression like the following:

{ a: Int, b: Int -> a + b }

In this case, you create an anonymous function that returns the sum of two input parameters of type Int. The result of evaluating a lambda expression is the value of the last expression in its body, in this case, the sum of a and b. You separate the input parameters list and the result expression with ->. It’s important to note that both the input parameter and the result expression are optional, as you saw in the first example.

Exercise 4.1: Can you write a lambda expression that calculates the distance between two points given their coordinates, x1, y1 and x2, y2? The formula for the distance between two points is distance = √(x2−x1)²+(y2−y1)².

Give it a try, and afterward, check the solution in Appendix D or this chapter’s challenge project.

Lambda type inference

Type inference is the mechanism a compiler uses to understand the element types involved in an expression.

When the compiler can’t get all the information it needs about types, you’re supposed to help. You can give the compiler the information it needs in different ways. In the previous code, you helped the Kotlin compiler by adding explicit type information for a and b. The Kotlin compiler then understands that a and b are Ints, and the result of the lambda expression will also be Int because of the type of the result of a + b.

The following code would give a compilation error because the Kotlin compiler wouldn’t know the types for a and b.

val lambda = { a, b -> a + b }

You can use a lambda expression as a normal value. This means you can assign it to a variable, like in the following example:

var operation = { a: Int, b: Int -> a + b }

In this case, you assign a lambda expression to a variable operation. The compiler infers for operation the type (Int, Int) -> Int, which is the type of any function with two input parameters of type Int returning another Int. Another way to give the compiler the information it needs is:

var operation: (Int, Int) -> Int = { a, b -> a + b }

By defining operation of type (Int, Int) -> Int, you’re telling the Kotlin compiler the type of values you can assign to it. Because { a, b -> a + b } is compatible with the type of operation, the compiler infers an Int type for a and b and also verifies the return type. In this case, the Kotlin compiler inferred the type of the input parameters a and b from the type of operation you defined explicitly.

Exercise 4.2: What’s the type for the lambda expression you wrote in Exercise 4.1?

Again, give it a try and check the solution in Appendix D or the challenge project.

The type of a lambda expression is then a function type, meaning the following code is perfectly legal:

typealias Fun<A, B> = (A) -> B

val multiplyBy2: Fun<Int, Int> = { x -> 2 * x }

Exercise 4.3: What are the types of the following lambda expressions?

  val emptyLambda = {} // 1
  val helloWorldLambda = { "Hello World!" } // 2
  val helloLambda = { name: String -> "Hello $name!" } // 3
  val nothingLambda = { TODO("Do exercise 4.3!") } // 4

Can you write an example of a lambda expression of the following type?

typealias AbsurdType = (Nothing) -> Nothing

In this case, can you show how to invoke it?

Try to answer without the support of IntelliJ, and check your solutions in Appendix D or the challenge project.

Lambda expression evaluation

A lambda expression allows you to define an expression without actually resolving it. Consider the following definition:

var operation = { a: Int, b: Int -> a + b }

Here, you’re defining a lambda expression that describes how to calculate the addition of two Ints, but you’re not actually running it. This is the beauty of lambda expressions: They allow you to describe code you’ll execute later with the advantage that you can treat them as data. You can handle the value 2 and the lambda operation as values exactly the same way. You can treat them as input parameters and return values of functions.

Eventually, you might need to execute or resolve the lambda expression. How can you do that? And, in that case, what would the final result be?

As mentioned earlier, a lambda expression is a function type. This means you can execute it like any other function. For instance, in the previous example, add the following to Lambdas.kt:

fun main() {
  val result = operation(3, 4)
  println(result)
}

Running this code, you get:

7

You can achieve the same thing using invoke like this:

fun main() {
  val result = operation.invoke(3, 4)
  println(result)
}

The value you get resolving a lambda expression is the value of the last expression in its body. Consider the following code:

val testLambda = { a: Int ->
  val doubleA = a * 2
  if (doubleA > 10) "$doubleA is Greater than 10"
  else "$doubleA is Smaller or Equal to 10"
}

In this example, the if expression is the last in the body of testLambda.

Note: You’ll see much more about this in Chapter 5, “Higher-Order Functions”.

More about lambda expressions

You’ll see much more about lambda expressions in the following chapters of this book. Here, it’s helpful to provide some useful and interesting information about:

• Lambda type inheritance
• Generic lambda expressions

Lambda type inheritance

In the previous paragraphs, you learned that the type of a lambda expression is a function type. In Chapter 2, “Function Fundamentals”, you learned that a type is a way to represent the set of all possible values. For instance, with Int, you represent the set of all the possible integer values — or, at least, the ones you can represent in Kotlin. When you define operation like this:

var operation: (Int, Int) -> Int = { a, b -> a + b }

What are the actual lambdas you can assign to it? Only the ones of type (Int, Int) -> Int? In this case, the answer is yes. You can only assign functions of that type to operation because Int is final, but this isn’t always the case.

Note: Saying that Int is final means the Int class can’t be extended.

Suppose you have the following types:

class A
class B

Now, suppose you define the following function type:

typealias LambdaType = (A) -> B

LambdaType is the type of generic function from A to B. This means you can write the following code, which is perfectly legal:

var lambda: LambdaType = { a -> B() }

Now, suppose you have the following new types:

class C
class D

What relation do these new types need to have with the previous A and B to make the following definition valid?

lambda = { c: C -> D() }

At the moment, the compiler is complaining because C isn’t an A and D isn’t a B. You basically need to make the function type (C) -> D a subtype of (A) -> B.

To fix this, you need to create the following relations you can visualize in Figure 4.1:

class A : C()
open class C
class D : B()
open class B

This means LambdaType is contravariant for the input type and covariant for the output type.

Note: Variance is a crucial concept when working with generic types. Given a hierarchy relation between two types, A and B, it describes the relation between F<A> and F<B>. Here, F is a data type you represent using generic types like List<T>, Set<T> and others. Using this terminology:

You have covariance when given B IS-A A entails that F<B> IS-A F<A>.
When given B IS-A A entails that F<A> IS-A F<B>, you have contravariance.
When given B IS-A A entails nothing about F<A> and F<B>, you have invariance.\

To give a quick example, if Triangle IS-A Shape entails that List<Triangle> IS-A List<Shape>, you say that List<T> is covariant.

Generic lambda expressions

You might be wondering about the difference between a normal function and a lambda expression. For instance, what’s the difference between the function:

fun add(a: Int, b: Int): Int = a + b

And the following lambda expression?

val sum = { a: Int, b: Int -> a + b }

Well, in this specific example, there’s no difference — but consider the following case instead:

interface Combinable<A> { // 1
  fun combine(rh: A): A
}

fun <A : Combinable<A>> combine(lh: A, rh: A): A = lh.combine(rh) // 2

In this case, you define:

1. The Combinable<A> interface, which defines combine. combine returns the combination of two objects of the same type A.
2. The combine function, which appends two input Combinable<A> objects into another Combinable<A>. This is a generic function in the type A with the constraint of considering only Combinable<A> objects.

How would you represent combine(lh: A, rh: A) using a lambda expression? Unfortunately, the following definition wouldn’t work:

val combineLambda = { lh: A, rh: A -> lh.combine(rh) } // ERROR

You can’t define a generic lambda expression the same way you do for a normal generic function. You might try to solve this problem with the following code:

typealias CombineLambdaType<A> =
  (Combinable<A>, Combinable<A>) -> Combinable<A> // 1

val combineLambda: CombineLambdaType<A> =  // 2
  { lh: A, rh: A -> lh.combine(rh) } // ERROR

In this case, you:

1. Define the typealias CombineLambdaType<A> as a function from two Combinable<A> to a single Combinable<A>.
2. Use CombineLambdaType<A>, trying to infer the parameter type to the lambda.

This doesn’t work because you wouldn’t be able to set the constraint on the type A.

In short, you can’t define a lambda expression on a generic type. This is why expressing combine(lh: A, rh: A) using a lambda expression won’t work. It’s the consequence of the fact that lambda expressions are like values, and you can’t define a value of a generic type A.

Lazy evaluation

Now that you know almost everything about lambda expressions in Kotlin, you can return to the following example you already wrote in ApplicativeOrder.kt. Next, copy it into LazyEvaluation.kt, using the same greaterThan10:

fun main() {
  val inputValue = 3
  val greater10 = greaterThan10(inputValue)
  if (inputValue > 4 && greater10) {
    println("OK")
  } else {
    println("KO")
  }
}

As you remember, if you run the code, you get:

greaterThan10
KO

How can you keep the same layout and evaluate greaterThan10 only when you really need to? Now you know the answer: Use a lambda expression. Just replace the previous code with the following:

fun main() {
  val inputValue = 3
  val greater10 = { greaterThan10(inputValue) } // 1
  if (inputValue > 4 && greater10()) { // 2
    println("OK")
  } else {
    println("KO")
  }
}

In this code, you:

1. Replace greaterThan10 with a lambda expression you saved in greater10.
2. Invoke greater10 only if necessary.

Run the code, and you get:

KO

Running the same code after changing inputValue’s value to 30, you get:

greaterThan10
OK

What you implemented using a lambda expression is called lazy evaluation. Lazy evaluation means resolving an expression only when you actually need it.

Exercise 4.4: Can you implement a function simulating the short-circuit and operator with the following signature without using &&? In other words, can you replicate the short-circuiting behavior of left && right:

fun shortCircuitAnd(left: () -> Boolean, right: () -> Boolean): Boolean

Can you also write a test to prove that right evaluates only if left is false?

Try to answer without the support of IntelliJ, and check your solutions in Appendix D or the challenge project.

Kotlin lazy delegate

Kotlin allows you to implement lazy evaluation using the… lazy delegate. :] Before understanding how lazy works, it’s useful to look at the by keyword. The Kotlin keyword by allows you to control the access to a variable, delegating getters and setters to the object you use as the target of the delegation: the delegatee. You call this property delegation.

To understand how it works, write the following code in Lazy.kt:

fun testDelegate() {
  var variable by object { // 1

    var localInt: Int? = null

    operator fun getValue( // 2
      thisRef: Any?,
      property: KProperty<*>
    ): Int? {
      println("Getter Invoked returning $localInt")
      return localInt
    }

    operator fun setValue( // 3
      thisRef: Any?,
      property: KProperty<*>,
      value: Int?
    ) {
      println("Setter Invoked with value $value")
      localInt = value
    }
  }
  variable = 10 // 4
  println("Reading $variable") // 5
}

In this code, you:

1. Use by to delegate variable’s access to a generic object.
2. Implement getValue, which is invoked every time you access variable.
3. Implement setValue, which is invoked every time you set a value to variable.
4. Assign the 10 value to variable.
5. Access variable and print its value.

This is why, running testDelegate(), you get the following output:

Setter Invoked with value 10
Getter Invoked returning 10
Reading 10

Now that you know how by works, just write the following code:

fun main() {
  val inputValue = 30
  val greater10 by lazy { greaterThan10(inputValue) } // 1
  if (inputValue > 4 && greater10) { // 2
    println("OK")
  } else {
    println("KO")
  }
}

In this code, note that you:

1. Use the Kotlin keyword by to delegate the access to the greater10 variable to the object you get by invoking lazy. You pass to lazy the lambda function you want to eventually execute for greater10 initialization.
2. Just access greater10 in the if condition.

Running the previous main, you get:

greaterThan10
OK

Change the inputValue to 3, and you get:

KO

This is what you’re expecting, but lazy gives you something more. Add the following code to Lazy.kt:

fun multiLazy() {
  val multiLambda by lazy { println("I'm MultiLambda") }
  multiLambda
  multiLambda
  multiLambda
  multiLambda
}

In this code, you:

1. Use lazy with a lambda expression containing the println of a message.
2. Access multiLambda multiple times.

When you run multiLazy, you get:

I'm MultiLambda

This is cool! The lambda expression you pass as a parameter to lazy is evaluated just once, and its result is reused when accessed again.

Of course, in this example, you use a println to prove that behavior, but if it doesn’t have any side effects or the expression takes some time, lazy is very useful. In this way, you achieved memoization, which you’ll learn about next.

Exercise 4.5: Can you implement the function myLazy with the following signature, which allows you to pass in a lambda expression and execute it just once?

 fun <A: Any> myLazy(fn: () -> A): () -> A // ???

Try to answer without the support of IntelliJ, and check your solutions in Appendix D or the challenge project.

Memoization

In the previous chapter, you learned that a pure function always produces the same result for the same input values, a concept known as referential transparency. A pure function also doesn’t have any side effects, and this makes it idempotent. Because of this, you don’t need to run the same pure function multiple times! You simply run it once and store the result for later invocations, saving time at the cost of some memory. Of course, the advantage is bigger if the computation takes some time.

You already learned how to implement memoization with Kotlin using the lazy function. It would be a good exercise to implement memoization for any function of type Fun<A, B>. How would you implement it?

Note: You can try to solve this problem on your own as a fun exercise before looking at the proposed solution. :]

Open the initially empty Memoization.kt file and write the following code:

fun <A, B> Fun<A, B>.memo(): Fun<A, B> { // 1
  val cache by lazy { mutableMapOf<A, B>() } // 2
  return { a: A ->  // 3
    val cached = cache[a] // 4
    if (cached == null) {
      cache[a] = this(a)
    }
    cache[a]!! // 5
  }
}

In this code, you:

1. Define memo as an extension function for Fun<A, B>. The return type is still Fun<A, B>. Remember Fun<A, B> is an alias of the type (A) -> B.
2. Use lazy to define MutableMap<A, B>, which will store the values to cache. In this case, lazy allows you to create just one instance of the cache in a lazy way.
3. Return a lambda accepting a parameter of type A. This is a lambda of type Fun<A, B>.
4. Check in the cache to see if you already have a result for the given input a. If not, you invoke the function and store the result.
5. Now you have the result, cached or not, to return.

To test this function, write this simple code:

fun main() {
  val testFunction = { a: Int -> println("Evaluating... $a"); a * 2 } // 1
  println("Running testFunction 4 times")
  testFunction(2) // 2
  testFunction(2)
  testFunction(2)
  testFunction(3)
  val memoTestingFunction = testFunction.memo() // 3
  println("Running memoTestingFunction 4 times")
  memoTestingFunction(2) // 4
  memoTestingFunction(2)
  memoTestingFunction(2)
  memoTestingFunction(3)
}

In this code, you:

1. Define a simple testFunction that returns double the input Int, printing a message to give evidence of the actual invocation.
2. Invoke testFunction four times. The first three times, you use the input 2, passing 3 instead in the last invocation.
3. Use memo to get the memoized version of testFunction you save in memoTestingFunction.
4. Invoke memoTestingFunction four times using the same parameters you used earlier for testFunction.

Run the code, and you get:

Running testFunction 4 times
Evaluating... 2
Evaluating... 2
Evaluating... 2
Evaluating... 3
Running memoTestingFunction 4 times
Evaluating... 2
Evaluating... 3

As you see, you have an output message every time you invoke testFunction. When you invoke memoTestingFunction, you have a message only the first time you pass a specific input value. This is exactly what you expect from memo.

Create a lazy stream with Kotlin

You learned that a lambda expression allows you to run some code — or evaluate some expression — later. This makes lambda expressions perfect for generating some sequences of values. Suppose you want to create a function returning the first N even numbers. A first, eager solution is the following. Add this to Stream.kt:

fun eagerEvenSequence(n: Int): List<Int> = List(n) { i -> i * 2 }

In this simple function, you create a List<Int> using the constructor List provides. It requires the size of the List and a lambda expression invoked for each element, which returns the value given its index. So far, so good. This solution has some problems, though:

1. The eagerEvenSequence function returns a List with all the values you might need. Here, the “might” is important because you might not need all of them.
2. If you just need the last value, you have to get the complete List first anyway.
3. If you need more values, you must invoke eagerEvenSequence with a new input value.

You can see all this by running the following code:

fun main() {
  println(eagerEvenSequence(5))
}

The output is:

[0, 2, 4, 6, 8]

In this case, the example is very simple, but in other cases, it might be useful to get a value of the sequence only if you really need it and when you really need it.

Next, add the following code to the same Stream.kt file:

fun evenPositiveStream(): () -> Int { // 1
  var count = -2 // 2
  return { count += 2; count } // 3
}

In this code, you:

1. Define evenPositiveStream as a function returning another function of type () -> Int, which provides an even Int value every time you invoke it.
2. Initialize count to -2. This weird initial value allows you to make the following line shorter and still return 0 as the first value after you add 2.
3. You return a lambda expression that adds 2 to count and returns the new value.

You can test the previous code by adding this to the same file:

fun main() {
  val evenSequence = evenPositiveStream() // 1
  5.times { // 2
    println(evenSequence())
  }
}

In main, you:

1. Create evenSequence, invoking evenPositiveStream.
2. Use the times utility function you find in Utils.kt to invoke evenSequence five times.

The output you get is:

0
2
4
6
8

More importantly:

1. You can persist the values of the sequence only if you really need them.
2. If you need more values, just invoke evenSequence more times.

Note: You might argue that in the case of eagerEvenSequence, you could just return double the input parameter. This is true, but, as the next exercise proves, you’re not always so lucky. :]

This is a very simple example of how lazy evaluation with lambda expressions allows you to create sequences in an optimal way.

Exercise 4.6: Can you create a function fibo returning the values of a Fibonacci sequence? Remember, every value in a Fibonacci sequence is the sum of the previous two elements. The first two elements are 0 and 1. The first values are, then:

0  1  1  2  3  5  8  13  21 ...

Try to answer without the support of IntelliJ, and check your solutions in Appendix D or the challenge project.

Normal-order evaluation

Note: The following two sections are optional. They give you some information about the normal-order evaluation used by languages like Haskell, in case you’re curious to know more. If you’re not curious, you can skip right to the challenges.

At the beginning of the chapter, you learned that Kotlin evaluates all expressions using applicative-order evaluation. This means it evaluates the expressions you pass as input parameters of a function before the function itself. After that, you also learned that Kotlin allows you to implement lazy evaluation using lambda expressions. Some other languages, like Haskell, use normal-order evaluation instead. But what does that mean, and is it possible to simulate normal-order evaluation with Kotlin?

Normal-order evaluation always reduces the leftmost, outermost reducible function expression. This means you evaluate the function before the expression you pass as a parameter to the same function. Kotlin doesn’t have applicative-order evaluation like Haskell, but with lazy evaluation, you can achieve something similar. Suppose you want to reduce the same function you saw at the beginning of the chapter:

3 * avg(x, y)

You want to evaluate the function before the expression you pass as a parameter. Open NormalOrder.kt and add the following:

fun addL(x: () -> Int, y: () -> Int): () -> Int {
  return { println("addL"); x() + y() }
}

addL has some interesting things to note:

• The input parameters are not executed expressions but lazily executable lambda expressions.
• You don’t evaluate the expression you use as the input parameter before the evaluation of addL but as part of it.
• You use println to have evidence of addL.
• The function returns a lambda expression.

You can now apply the same logic to the following functions. Add these to the same NormalOrder.kt file:

fun tripleL(x: () -> Int): () -> Int {
  return { println("tripleL"); addL(addL(x, x), x)() }
}

fun divideL(x: () -> Int, y: () -> Int): () -> Int {
  return { println("divideL"); x() / y() }
}

fun averageL(x: () -> Int, y: () -> Int): () -> Int {
  return { println("averageL"); divideL(addL(x, y), { 2 })() }
}

For testing its behavior, add the following main:

fun main() {
  tripleL(averageL({ 2 }, { 4 }))()
}

When you run the previous code, you get:

tripleL
addL
addL
averageL
divideL
addL
averageL
divideL
addL
averageL
divideL
addL

Try to mimic this by applying the substitution model. In this case, you have a longer sequence than you did earlier in this chapter because you evaluate the external function on the left first.

tripleL(averageL({2},{4}))()
addL(addL(averageL({2},{4})),averageL({2},{4}))),averageL({2},{4})))()
addL({averageL({2},{4})()+averageL({2},{4})()}(),averageL({2},{4}))()
{{averageL({2},{4})()+averageL({2},{4})()}()+averageL({2},{4})()}()
{{{divideL(addL({2},{4}),2)}()+averageL({2},{4})()}()+averageL({2},{4})()}()
{{addL({2},{4})()/2}()+averageL({2},{4})()}()+averageL({2},{4})()}()
{{addL({2},{4})()/2}()+averageL({2},{4})()}()+averageL({2},{4})()}()
{{(2+4)/2}()+averageL({2},{4})()}()+averageL({2},{4})()}()
{{(2+4)/2}()+{{divideL(addL({2},{4}),2)}()+averageL({2},{4})()}()
{{(2+4)/2}()+{addL({2},{4})()/2}()+averageL({2},{4})()}()
{{(2+4)/2}()+{(2+4)/2}()+averageL({2},{4})()}()
{{(2+4)/2}()+{(2+4)/2}()+{{divideL(addL({2},{4}),2)}()}()
{{(2+4)/2}()+{(2+4)/2}()+{addL({2},{4})()/2}() }()
{{(2+4)/2}()+{(2+4)/2}()+{(2+4)/2}()}()
{3+3+3}()
{9}()

As you can see, the leftmost function is the one you’re evaluating in each step.

Applicative-order vs. normal-order evaluations

Looking at the previous examples and considering how Kotlin works, you understand how lazy evaluation is a balanced compromise between applicative-order and normal-order evaluation strategies. It allows you to control where to define your expression and when to evaluate it. If you use the Kotlin lazy function, you also get the benefit of memoization, which is very good in the case of expensive — and pure — functions.

In particular, using the Kotlin lazy function, you get three different synchronization modes for free through the LazyThreadSafetyMode enum class. With this, you can decide how a lazy instance synchronizes initialization among multiple threads. Possible values are:

• SYNCHRONIZED: The initialization is safe because only a single thread at a time can access the lambda expression you pass as a parameter. This is the default mode.
• PUBLICATION: The lambda expression you pass as a parameter can be evaluated several times on concurrent access to an uninitialized lazy instance value. However, only the first returned value will be used as the actual value.
• NONE: The lambda expression can be evaluated multiple times from different threads, and its behavior is undefined.

In the last example, you might have the impression that normal-order evaluates the same expressions multiple times, which is a problem that lazy evaluation solves elegantly. On the other hand, applicative-order evaluation doesn’t always work well with recursion. If the function you pass as a parameter is recursive, it might not end. Or the expression could never return, like in this example you can write in EvalExamples.kt:

fun neverEnding(): Int { // 1
  while (true){}
}

fun double(x: Int): Int = x + x // 2

fun main() {
  double(neverEnding()) // 3
}

In this code, you:

1. Define neverEnding using an infinite loop as a function that never returns.
2. Create double as a simple function returning the double of its input parameter.
3. Define main, which simply uses neverEnding invocation as an input parameter of double.

Run this code, and the program will never complete.

Challenges

In this chapter, you learned many important concepts about expression evaluation, lambda functions and lazy evaluation. You’ve already done some interesting exercises, but here you have some additional challenges. Have fun! :]

Challenge 1: Handling nullability

In Exercise 4.5, you created myLazy, which allowed you to implement memoization for a generic lambda expression of type () -> A. Can you now create myNullableLazy, supporting optional types with the following signature?

fun <A> myNullableLazy(fn: () -> A?): () -> A? // ...

Challenge 2: Functions and set again

You might be aware of Euler’s number e. It’s a mathematical constant of huge importance that you can calculate in very different ways. It’s an irrational number like pi that can’t be represented in the form n/m. Here, you’re not required to know what it is, but you can use the following formula:

Can you create a sequence that provides the sum of the n terms of the given formula?

Key points

• You define evaluation strategy as the relationship between the point in your code where you define your expression and the point when the expression is actually evaluated.
• With applicative-order evaluation, a function is executed only when all the expressions you pass as input parameters are evaluated, starting from the leftmost parameter.
• A lambda expression is an anonymous function you can use as a value.
• Type inference is the mechanism a compiler uses to understand the element types involved in an expression.
• The type of lambda expression is a function type.
• A lambda expression is contravariant for the input type and covariant for the output type.
• Memoization is the process that allows you to save the result of a function in memory to reuse it more efficiently.
• Pure functions can always be memoized.
• Pure evaluation allows you to easily implement infinite sequences of values in a very efficient way.

Where to go from here?

Congratulations! You’ve completed another challenging chapter about expression evaluation and lambda functions. You had the chance to solve some fun exercises, and you’ve already started implementing some higher-order functions — which is the topic of the next chapter. See you there. :]