Enrichment & Ancillary

Ancillary/Supplementary Videos

• Micinski on cons/improper lists/diagrams
• Continuations: the Swiss Army Knife of Flow Control
• Byrd’s Tutorial on the CPS Transformation

Enrichment

• More on the Ackermann Function + History

• The first recursive but not primitive-recursive function

• Pattern matching coming to Python

• Hutton’s Tutorial on fold operators

• On Barron & Strachey’s Cartesian product function

• The feeling you should get looking at our interpreter

• Reynold’s “Definitional Interpreters for Higher-order Programming Languages” (Updated Notes)

• Norman on “Denotational Design” (sort of our style of writing interpreters)

• Danvy & Nielsen’s “Defunctionalization at Work”

• Essay: “What does valof defunctionalize?”

• Vanier’s blogpost on the Y combinator
• Yin Wang’s slide deck on (re-)deriving the Y combinator
• The smallest (in AIT) fix-point combinator

• Poly-variadic fixpoint combinators for mutual recursion

• Hunting the history of Moses Schönfinkel

• Kleene’s “Church predecessor” via a trip to the dentist

• Someone else’s explanation of the CPS transformation§4.2
• A first-order one-pass CPS transformation
• Why continuations are coming to Java

• No-brainer CPS Conversion

• Lambda: the Ultimate GOTO

• CONS should not cons its arguments pt II: Cheney on the MTA

• (An operational investigation of) the CPS Hierarchy

• Church encoding is the vistor pattern

• Bohm-Berarducci encoding–an extension of Church encoding

• An agda based introduction to PL

• A Profile of Mathematical Logic (A fun, quick-ish read on the story of modern logic)
• The Search for Mathematical Roots, 1870-1940: Logics, Set Theories and the Foundations of Mathematics from Cantor through Russell to Gödel (A grown-up text on much of the same.)
• Philosophy of Computer Science (Draft text)

• Logicomix (It’s a comic about Russell and early 20th century mathematical logic. ᕕ( ᐛ )ᕗ)

• History of Lambda Calculus and Combinatory Logic
• SKI Combinator Tetris
• Care for your pet combinator

• Why concatenative programming matters

• van Emden on relational programming, logic beyond prolog
• Purity and programming purely in Prolog

• Paulson on logic programs as inductive definitions

• Chiang’s short story “Seventy-two Letters” (Audio version)

Additional online textbooks with relevant sections/explanations.

• PPL Notes
• Krishnamurthi’s PLAI
• Barzilay’s PL class notes

“All language designers are arrogant. Goes with the territory…” – Larry Wall