Class 05: Hoare's Examples

Held: Wednesday, February 1, 2006

Summary: Today we continue to consider the code examples from Hoare and the points he intended to make with them.

Related Pages:

• EBoard.

Assignments

• Read John McCarthy's Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (due Fri.).
• Read Paul Graham's The Roots of Lisp (due Fri.).

Notes:

• The next two readings are somewhat harder. The Graham paper will help you understand the McCarthy paper, but I'd like you to read the McCarthy paper first.

Overview:

• More examples from Hoare.
• Why recurse?

Examples from Hoare, Continued

• What's wrong with multiply(A,A,A) (assume C)?
• What point does he make in comparing x := y and x := y+1, where x is a reference variable?

Beyond Hoare: Recursion

• Why is recursion so important?
  • Hoare discusses it as a key aspect of Algol.
  • McCarthy and Graham consider it a central aspect of Lisp.
• Consider Quicksort. How do you write it w/o recursion?
• Consider the efficient exponentiation algorithm. How do you phrase it iteratively?