Skip to main content

Introduction

  • Avoids doing unnecessary evaluation
  • Ensures termination whenever possible
  • Supports programming with infinite lists
  • Allows programs to be more modular

Evaluation Strategies

Two main strategies for deciding which reducible expression (redex) to consider next:

  • Choose a redex that is innermost, does not contain another redex
  • Chose a redex that is outermost, not contained in another redux

Termination​

infinity = 1 + infinity fst (0, infinity -> results in 0

  • Outermost evaluation may give a result when innermost evaluation fails to terminate
  • If any evaluation sequence terminates, then so does outermost, with the same result
  • Outermost evaluation may require more steps that innermost. However this can easily be avoided by using pointers to indicate sharing of arguments

Lazy evaluation = outermost evaluation + sharing of arguments

  • Lazy evaluation ensures termination whenever possible, but never requires more steps than innermost evaluation and sometimes fewer

Infinite lists

  • In general, lazy evaluation expressions are only evaluated as much as required by the context in which they are used
  • Hence, ones is really a potentially infinite list

Modular Programming

Lazy evaluation allows us to make programs more modular by separating control from data Without using lazy evaluation the control and data parts would need to be combined into one

Generating Primes

To generate the infinite sequence of primes:

  1. Write down the infinite sequence 2,3,4...,
  2. Mark the first number p as being prime
  3. Delete all multiple of p from the sequence
  4. Return to the second step