CS 280 Lab Combinators and Graph Reduction Rhys Price Jones Fritz Ruehr Richard Salter Alexei Barchenkov, Dan Hutchings, Michael Klingbeil © February, 1996

Contents

• Introduction
• Functional programming without lambdas
  • Function definition by partial application
    • Exercise 1
  • Currying and uncurrying
    • Exercise 2
  • Composition, diagonalization and other fun tricks
    • Exercise 3
    • Exercise 4
    • Exercise 5
  • An iteration combinator for lists
    • Exercise 6
    • Exercise 7
• Combinators and graph reduction
  • The syntax of combinatory logic
    • Exercise 8
  • Reduction and normal forms
  • The combinator reduction machine
  • An animated companion to the reduction machine
• Implementing functional languages via combinators
  • The "bracket" abstraction algorithm
  • Experimenting with abstraction
    • Exercise 9
• Combinatory encodings
  • Encoding booleans and conditionals
    • Exercise 10
    • Exercise 11
  • Encoding numbers and arithmetic
  • Encoding recursion