Tips

Of course I’m not committing my midterm.

array programing

“collection-oriented programming”—

1. precise programs with bulk operations over the whole collection—the iteration structures/accesses are spelt out much more explicitly (i.e. not to use general structures like for loops as a crutch): iteration patterns are baked into the language
2. performance: leaving the details of parallelism to your hardware

array programmings are easy to optimize

Lifting for loops is hard; but: \(\qty(\text{map } f) \cdot \qty(\text{map } g) = \text{map } \qty(f \cdot g)\). This is, notably, not true if your functions \(f\) and \(g\) are not pure (i.e. they have state or can throw exceptions); for instance, \(f\) crashes up front and \(g\) crashes in the end, then, the crashed error is different between the first and second method of evaluation.

Building a programing language, step by step:

Lambda Calculus

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

and you can add types

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

\begin{equation} t \to \alpha | t \to t | \text{int} \end{equation}

Adding ADT

Algebraic Data Type—

\begin{equation} \lambda a_1 . \lambda a_2 \dots \lambda a_{k}. \lambda f_1 . \lambda f_2 \dots \lambda f_{n} f_i a_1 a_2 \dots a_{k} \end{equation}

Logic Programming

Logic is the study of correct arguments. For instance, for some predicate \(P\); for instance:

\begin{equation} \forall x .\exists y. P(x,y) \end{equation}

• we can “prove” this by doing the thing
• we can also do that by contradiction (but that won’t create a witness \(y\) of the statement)

PROLOG

PROgramming LOgic - PROLOG; not general, but good in specific cases (databases, scheduling outputs, etc.)

pros and cons

pros

• very declarative
• easy to write some backtracking search approaches

worst

• “algorithm” / “complexity” obscured because you only have one algorithm
• because you get performance only by wrangling goal ordering

PROLOG time

So, every predicate returns true/false.