Key ideas

• appreciating PL as a techincal field
  • OS people cares only about dynamic system—build a good runtime/OS, etc.
  • PL people cares only about static system—build a compiler, etc.
• think systematically about PL tools
• what we can do, what we can’t do, what will be able to do
• basics of active research in PL

equal in expressive power

• SKI calculus
• Lambda calculus
• Turing machines

Lectures

• SU-CS242 SEP242024

Combinator Calculus

• SU-CS242 SEP262024
• SU-CS242 OCT012024

Lambda Calculus

• SU-CS242 OCT032024
• SU-CS242 OCT102024
• SU-CS242 OCT152024
• SU-CS242 OCT172024

Objects

• SU-CS242 OCT242024

Programming Abstractions and Logic Programming

• SU-CS242 OCT312024
• SU-CS242 NOV072024
• SU-CS242 NOV142024
• SU-CS242 NOV192024

Contravariance

• SU-CS242 NOV212024
• SU-CS242 DEC032024

A decision making method using search on a model of the problem to be able tom make decisions.

1. create a (usually deterministic, but for CS238 we care only about non-deterministic cases) model of the problem or a good approximation thereof
2. use the model to plan for possible next actions to yield for a good solution

contrast v. explicit programming

explicit programming requires you to plan for the action

1. we start at an initial belief point
2. we do a random Rollout to get to the next belief

then collect

we keep track of a bunch of alpha vectors and belief samples (which we get from point selection):

\begin{equation} \Gamma = \{\alpha_{1}, \dots, \alpha_{m}\} \end{equation}

and

\begin{equation} B = \{b_1, \dots, b_{m}\} \end{equation}

To preserve the lower-boundedness of these alpha vectors, one should seed the alpha vectors via something like blind lower bound

We can estimate our utility function at any belief by looking in the set for the most optimal:

\begin{equation} U^{\Gamma}(b) = \max_{\alpha \in \Gamma} \alpha^{\top}b \end{equation}