PoPL 1

What does an if need?

A true/false condition, and both choices (then and else) must give the same kind of value

What does e1 && e2 do if e1 is false?

It stops and never looks at e2. The answer is false

What does e1 || e2 do if e1 is true?

It stops and never looks at e2. The answer is true

Can you add an int and a float, like 3 + 2.5?

No. Ints use + - * /. Floats use +. -. *. /.

Does let x = 4 in let x = x + 1 in x change the first x?

No. The new x hides the old one. The old one is unchanged

What is a type error?

A mistake OCaml finds before the program runs, like 1 + "hi"

What is a runtime exception?

A crash while the program runs, like List.hd []

When do you need the word rec?

When a function calls itself

How do you separate items in a list?

With a semicolon: [1; 2; 3]

What does a comma make?

A tuple (a pair), not a list. [1, 2] is a list holding one pair

What is the head of [4; 5; 6]?

4 (the first item)

What is the tail of [4; 5; 6]?

[5; 6] (everything after the first item)

What does x :: rest mean in a pattern?

x is the first item, rest is the list of everything else

What does _ mean in a pattern?

Something is here, but I don't need it, so I won't name it

In a match, which branch runs?

The first one that fits

What is an unreachable branch?

A branch that can never run because an earlier branch already catches everything it would

Where should the _ catch-all go?

Last

Is Some 4 the same as 4?

No. Some 4 is an option (a box with 4 inside). 4 is just a number

What does None mean?

There is no answer

What is a tail call?

A call where nothing is done to its answer afterward. The answer is just passed back

Is 1 + f x a tail call?

No. The + still has to happen after f finishes

Is x :: f rest a tail call?

No. The :: still has to happen after f finishes

Is loop rest (total + x) a tail call?

Yes. The adding happens before the call, so nothing is left to do after

Which uses less memory, tail or non-tail recursion?

Tail recursion. It uses the same small space (O(1)). Non-tail grows with the list (O(n))

What is an accumulator?

An extra input that carries the answer so far

What should the accumulator start at?

The answer for an empty list (0 for sum or length, [] for building a list)

Why does building a list with an accumulator come out backwards?

:: adds each new item to the front, so the last item ends up first. Use List.rev at the end to fix it

Why is it hard to make tree functions tail recursive?

A node has two children, so there are two calls and only one can be last

What is the difference between an exception and an option?

An option shows "maybe no answer" in the type (None). An exception does not

What does try … with do?

Tries something. If it crashes with a matching error, it uses the backup answer instead

What does List.map do?

Does a function to every item. The new list is the same length

What does List.filter do?

Keeps only the items that pass a true/false test. The new list can be shorter

What does List.fold_left (fun acc x -> acc + x) 0 [1; 2; 3] give?

6 (it adds everything up, starting at 0)

What does fold_left with x :: acc and [] do to [1; 2; 3]?

It reverses it: [3; 2; 1]

What does fold_right with x :: acc and [] do to [1; 2; 3]?

It keeps the order: [1; 2; 3]

What is List.fold_left (-) 0 [1; 2; 3]?

-6

What is List.fold_right (-) [1; 2; 3] 0?

2

What type does a fold give back?

The same type as its starting value

What is currying?

A function with two inputs is really a function that takes one input and gives back another function

If add is int -> int -> int, what is add 5?

A function: int -> int. It still waits for one more number

What is the type of add x y = x + y?

int -> int -> int (two inputs, one after another)

What is the type of add (x, y) = x + y?

int * int -> int (one input that is a pair)

What does compose f g x equal?

f (g x). The second function g runs first

What is lexical scope?

A function uses the names from where it was written, not from where it is called

What is a closure?

A function plus the names it remembers from where it was written

Does a later let x = 100 change a function already written?

No. The function keeps the old x

What is the type of let id x = x?

'a -> 'a (any type in, the same type out)

What is the type of let pair x = (x, x)?

'a -> 'a * 'a

What is the type of let apply f x = f x?

('a -> 'b) -> 'a -> 'b

What is the type of let choose b x y = if b then x else y?

bool -> 'a -> 'a -> 'a

Why is let bad x = (x + 1, not x) an error?

x would have to be an int and a bool at the same time

In a type, what does the same letter twice mean?

Those spots must be the same type

What is a signature?

A list of the names and types a module shows to the outside

What is an abstract type?

A type whose inside is hidden. type t with no = in a signature

Why is B.get 3 an error if B.t is int inside?

The outside cannot see that t is an int, so 3 does not count as a B.t

Are B.t and C.t the same type if both modules look alike?

No. Each module makes its own separate type

Can a module have extra functions the signature does not list?

Yes. They are just hidden. A module can have more, never less

What is a representation invariant?

A rule that must always be true about the hidden data, like n = List.length xs

Why does hiding the type protect the rule?

Outsiders can only make values with the module's own functions, and those keep the rule true