Lecture overview -- Keyboard shortcut: 'u'  Previous page: Rewrite rules, reduction, and normal forms [Section] -- Keyboard shortcut: 'p'  Next page: The alpha rewrite rule -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Help page about these notes  Alphabetic index  Course home  Lecture 4 - Page 9 : 27
Programming Paradigms
Evaluation Order and Infinite Lists
Rewrite rules

The rewrite rules define semantics preserving transformations of expressions

The goal of applying the rewrite rules is normally to reduce an expression to the simplest possible form, called a normal form

  • Overview of rewrite rules

    • Alpha conversion: rewrites a lambda expression

    • Beta conversion: rewrites function calls

      • Expresses the idea of substitution, as described by the substitution model

    • Eta conversion: rewrites certain lambda expressions to a simpler form