pairs

• Constructor: \(\qty(e,e’)\)
• Destructor: \(p.l, p.r\) or \(fst\ p\), \(snd\ p\)
• Type: \(A * B\)

currying

Consider a function from pairs to a thing: \(A * B \to C\)

We can instead construct a function: \(A \to B \to C: \lambda a . \lambda b. f(a,b)\)

state and exception

Both state and exceptions create “side information”—-the side information is threaded through computation in a specific order; we create new primitives for manipulating side information.

Object

The functional core still stays:

\begin{equation} e \to x | \lambda x. e | e e \end{equation}

Records

Named fields with values:

\begin{equation} [flag = False, value = 42] \end{equation}

“each element of the tuple has a name, and order is unimportant”

If the fields are fixed, they are basically just ADTs.

Record Type

All functions are types, and so are the methods; so we can just add more types for the methods as well. So here’s two properties and a method:

Problem: because Object Calculus and Lambda Calculus really can’t be resolved in into one system, we have to decide either extending objects with lambda (Java, C++), or extend lambda with objects (OCaml, Haskell).

memory safety

This is a problem introduced during manual memory management: pointers or references needs to be checked whether they point to a thing of the correct type — key problem in C/C++ (double free, wild pointer, out of bounds accesses).

“the ways in which one can dividing the original program together depends on the way people can glue problems together. one must provide new kinds of glue in teh programming language”

Goals of PL

balancing between:

• productivity—Python
• safety—Coq, Lean
• performance—C,

Edges:

• safety+performance—Rust (not really productive)
• productivity+safety—ML, Maskell (not very performant)
• productivity+performance—Matlab (not very safe)

Java and C++ tries to do all three, but makes them more contradictory systems because you can’t get optimality on all three

MAIN IDEA: Combinator Calculus

primitive recursion vs general recursion

primitive recursion is a form of recursion whereby you don’t get to modify the amount of recursion after the loop is defined. general recursion have control flow.

non-termination

all forms of general recursion either

rewrite system

• \(\to\) is a single rewrite
• \(\to^{*}\) stands for the reflexive, transitive closure of \(\to\) (i.e. zero or more rewrites—“we skipped the middle”)