Programming Languages Recitation Links
Grammars, Parsing, and Formal Languages
- Everything2: Formal grammar: What's a formal language? How do we generate strings from a grammar?
- BNF and EBNF: What are they and how do they work?
- Python Grammar: Impressively short grammar for the syntax of the Python programming language.
Simple Models of ComputationNo programming language is more "powerful" than any other. Anything that can be written in one language can be encoded in another. That encoding may not necessarily be pleasant or compact, but it is possible. Most languages are hard to reason about in our heads, they have complicated semantics with lots of edge cases. For this reason, people concerned with proving properties of computational systems often instead use simpler (but equally powerful!) computational models like the Lambda Calculus and the Universal Turing Machine.
- What does it mean to compute?
- Compiling to lambda-calculus: Turtles all the way down
- Church Encoding: This is how you do arithmetic when your only data type is a function.
- Universal Turing Machine encoded within the Game of Life: Conway's Game of Life is an extremely simple rule system for turning on and off the elements of a grid. It is (strangely) possible to translate any program into a particular configuration of grid cells, run the simulation, and get back the result of your computation.
- A Turing Machine: In The Classic Style: A physical Turing Machine. Insane and awesome.
- Why do programming languages use type systems?
- What to Know Before Debating Type Systems
- Type System Quadrant: Splits languages along the weak/strong and safe/unsafe axes.
- Types and Programming Languages: The Bible of type system theory.
- The choices, tradeoffs, and implementations of dynamic allocation
- Why is Garbage Collection a Good Thing?
- An Introduction to Garbage Collection: A Look Under the Hood
- Back To Basics: Mark and Sweep Garbage Collection
- How does garbage collection work in the JVM?
Function Values and ClosuresProgramming languages like C treat functions essentially as dumb labels. You can't bottle up a function into a runtime value and pass it around. To make functions into first-class values in a language we need closures, which are often implemented as the function's code pointer paired with an environment record.
Higher Order ProgrammingFirst order functions take just data as their arguments. Higher order functions have at least some arguments which are themselves functions.
- Can Your Programming Language Do This?
- Higher Order Programming is Easy
- Implementing 'map' and 'reduce' operators in PHP
Translation, Compilation, Bytecode, and Virtual Machines
- Registers vs. Stacks for Interpreter Design
- Stack machines: Sketch of how virtual machines like the JVM work.
- Bytecode Basics: Overview of the JVM bytecode.
- Serp: A library for creating/manipulating JVM bytecode on the fly.
Lisp and Scheme
ML and the Hindley-Milner type system
- Standard ML and OCaml Overview of the two languages and more detailed links.
- Caml Trading Video of Yaron Minsky from Jane Street talking about how his company uses ML.
- What is Hindley-Milner? (and why is it cool?)