Evaluation Strategies: Scheme vs. Haskell

Hello! Welcome to the third lesson in our module on Evaluation Strategies.

In our previous lessons, we distinguished between call-by-value, call-by-name, and call-by-need (lazy evaluation). We saw that most languages, like Python, are eager (call-by-value), while others, like Haskell, are lazy by default. We explored how Python uses generators for optional laziness and how Haskell's default laziness enables powerful abstractions like infinite data structures.

Today, we move from definitions to consequences. The choice of an evaluation strategy is not merely an implementation detail; it fundamentally alters what a program means and how it behaves. This brings us to our learning outcome:

Analyze how evaluation strategies affect program behavior, termination, and side effects using comparative examples from Scheme and Haskell.

To do this, we will:

1. Establish Scheme as our example of a strict (eager) language and Haskell as our lazy one.
2. Analyze how this difference impacts program results, especially when errors or side effects are involved.
3. Investigate how evaluation strategy determines whether a program will even terminate.

1. The Stage: Scheme (Strict) vs. Haskell (Lazy)

To explore these differences, we'll focus on two languages that are pillars of the functional programming world but sit on opposite sides of the evaluation spectrum.

• Scheme, a dialect of Lisp, is a strict (or eager) language. Like Python, it evaluates function arguments completely before the function body is executed.
• Haskell is a lazy (or non-strict) language. It evaluates expressions only when their results are demanded by another computation.

This core difference has profound implications, particularly concerning side effects and purity.

As the reading highlights, strict languages like Scheme can interleave side effects (like printing to the screen or modifying variables) with pure computations because the order of execution is predictable. In contrast, lazy languages like Haskell make the order of execution unpredictable, which forces the language design to enforce purity—the separation of functions that perform calculations from actions that have side effects.

Now, let's see what this means in practice.

2. Impact on Program Behavior and Side Effects

The most immediate consequence of the evaluation strategy is that the same piece of code can produce different results, or even crash in one language and not the other.

Example 1: Avoiding Errors with Laziness

Consider a simple boolean or operation. In a lazy language, if the first argument is True, the second argument is never evaluated. A strict language, however, might evaluate both arguments before computing the result.

This video demonstrates the concept perfectly using Haskell.

In Scheme, the or form is a special syntactic form that does short-circuit, just like in Python. However, if we define our own function, the underlying strictness of the language becomes apparent:

; Define a function that behaves like 'or'
(define (my-or x y)
  (if x #t y))

; This will cause an error in Scheme because (/ 5 0) is evaluated
; before the function 'my-or' is called.
(my-or #t (/ 5 0)) 

In Haskell, any function behaves this way naturally. The short-circuiting isn't a special feature of ||; it's a direct result of lazy evaluation.

Example 2: The Unpredictability of Side Effects

What happens when a delayed expression involves a side effect, like getting the current time? The following video uses Scala's call-by-name to demonstrate.

Note: Call-by-name is slightly different from Haskell's call-by-need (lazy evaluation). Call-by-name re-evaluates the expression every time it's used, while call-by-need evaluates it once and caches the result. However, both delay the initial evaluation, which is the key point for this example.

Let's break down how Scheme and Haskell would handle the nanoTime scenario:

• Scheme (Strict): (print-twice (get-current-time)) would call get-current-time once, then pass the resulting value to print-twice. It would print the same time twice.
• Haskell (Lazy/Call-by-need): printTwice getTime would pass an unevaluated getTime action to the function. The first time it's needed (for the first print), getTime is executed. The same resulting value is then cached and reused for the second print. It would also print the same time twice, but the evaluation happens later than in Scheme.
• Scala (Call-by-name): As the video showed, the expression is re-evaluated on each use, printing two different times.

This highlights a subtle but critical point: lazy evaluation's unpredictability of when side effects run is precisely why Haskell's type system strictly separates pure code from impure IO actions. You are forced to be explicit about sequencing operations whose timing matters.

3. Impact on Program Termination

Perhaps the most mind-bending difference between strict and lazy evaluation is its effect on whether a program finishes. A program that runs forever in a strict language can terminate instantly in a lazy one.

The const function example

Imagine a function const that takes two arguments and always returns the first one.

• Haskell: const x y = x
• Scheme: (define (const x y) x)

Now, what happens if we call it with a second argument that is an infinite loop?

• In Scheme (Strict):

  (define (loop) (loop))
  (const 1 (loop)) ; This program NEVER terminates.
  

  Scheme must evaluate all arguments before calling const. It first evaluates 1, which is just 1. Then it tries to evaluate (loop), which never returns a value. The program is stuck.

• In Haskell (Lazy):

  loop = loop
  const 1 loop -- This program immediately returns 1.
  

  Haskell calls const with two unevaluated expressions (thunks). The body of const only requires the value of the first argument, x. It returns x without ever needing to evaluate the second argument, y. The loop is never executed.

This property is what allows Haskell to work with conceptually infinite data structures. You can define the list of all natural numbers, [1, 2, 3, ...], because the tail of the list is just a "promise" to compute more numbers. An operation like take 5 [1..] terminates because it only forces the evaluation of the first five elements. In contrast, an operation like sum [1..] would, correctly, never terminate.

Summary: A Tale of Two Strategies

The choice between a strict and lazy evaluation strategy represents a fundamental design trade-off.

Aspect	Scheme (Strict / Eager)	Haskell (Lazy / Non-Strict)
Behavior	Predictable. Evaluation order follows code order.	Unpredictable. Evaluation order is driven by data dependencies ("pull" model).
Side Effects	Manageable. The sequence of effects is explicit and easy to reason about.	Difficult to reason about. The timing of effects is not obvious, necessitating a strong separation of pure and impure code (e.g., IO monad).
Termination	A function call will not terminate if any of its arguments do not terminate.	A function call can terminate even if some arguments are non-terminating, as long as their values are not needed.
Data Structures	Works with finite data structures by default. Laziness must be simulated (e.g., with delay/force).	Natively supports infinite data structures, enabling a declarative style where you define "what" a sequence is, not "how" to generate it step-by-step.
Error Handling	An error in an argument will crash the program before the function call, unless handled by a special syntactic form.	An error in an unused argument is never triggered. This allows for more flexible composition.

Conclusion

Today we've seen how the abstract concept of evaluation strategy has concrete and far-reaching consequences. It's not just about performance; it dictates program semantics, termination behavior, and even forces major language design decisions like purity.

Key Takeaways:

• Strict evaluation (Scheme): Offers predictability in execution order, making it easier to reason about performance and side effects. However, it can perform unnecessary work and will fail to terminate if an argument (even an unused one) enters an infinite loop.
• Lazy evaluation (Haskell): Avoids unnecessary computations and enables powerful idioms like infinite data structures. It can terminate where a strict program would not. This flexibility comes at the cost of predictable performance and requires a strong discipline (enforced by the type system) to manage side effects.
• The behavior of a program—its result, its side effects, and whether it even finishes—can change dramatically based on the language's evaluation strategy.

Preview of the Next Lesson:

We've established that lazy evaluation is the key to working with infinite data structures. In our next lesson, we will dive deeper into this topic: "Implement and process infinite data structures (streams) using lazy evaluation, comparing Haskell's native support with Python's generators." We will see how to build and manipulate these powerful abstractions in both a lazy-by-default and an eager-by-default language.