:::warning
Announcements
- Quiz 2 grades back
- Help hours today 3:45-5:15pm, L043
:::

:::success
Agenda for today
- More imp. interp, tips for A7
- Parallelism/Concurrency
- Goals/non-goals
- Parallelism vs Concurrency, vocab
- Summary of landscape
- Promises
- Parallelism with `domainslib`
:::

# More imperative interpretation

It may help to think of the next statement just with your intuition about programming: in the existing branch of test, if the test succeeds, we just do what's up next but don't add anything new to do later (represented by making a recursive call with Pass in the new next position). This pattern should hold true for other cases that do not modify the control flow. But think about cases that _do_ modify the control flow, like if.
If I have some code like:

if x then {
  y;
} else {
  z;
};
w

Then when we get if as the current statement, w would be the next statement. But for the recursion, we want to instead say that (if x is true) y becomes the current statement - and then instead of Pass, what should the next statement be for the recursive call? Well, after we complete `y`, the code should jump to w. So in the case of if, we put `w` as next for the recursive call.

## End of the recursion (return type of `interp_stmt`)

Unlike our function interpreters, where cases of `if` statements were leaves in the recursion, in the above example, every non-`Pass` statement still makes a recursive call. This means two things:

### Return type
:::success
What should the return type be?
:::

Answer: `interp_stmt` interprets statements for their side effects, so the return type should be `unit`.

### Base case

The "base case" should be when we have no work left to do: when both `curr` and `next` are `Pass`.

  | (e, Pass, Pass, conts) ->
    ()

# Parallelism/Concurrency

For the next topic, we'll do a brief introduction to parallelism and concurrency and how they impact programming language implementation.

## Goals

- Familiarity with high-level ideas
- essence, key concerns
- non-sequential thinking
- some high-level models
- some mid-to-high-level mechanisms

## Non-goals

- performance engineering / measurement
- deep programming proficiency
- exhaustive survey of models and mechanisms
- ... see CS240 and CS343!

# Parallelism vs. concurrency

Both eliminate 1 big assumption: "evaluation happens as a sequence of ordered steps".

There are many use cases where we want a computer to do more than one thing at once!

For example:
- When you want to do Control-C in the terminal on a program that's already running.

:::success
Other examples?
:::

- When you are taking notes on a tablet, but also want to receive push notifications.
- When you are listening to music and writing code.
- When you want to scroll on a website or app, while it also receives data from the server over the network.
- Multiple users should be able to like an Instagram photo at once.

People use both "concurrency" and "parallelism" to refer to these ideas, but there are subtle differences between the two.

**Concurrency:** Coordinate access to shared resources.

For example: one CPU core can only perform one instruction at a time. Example: Spotify and VSCode could need to coordinate access to one shared core.

**Parallelism:** Use more resources to complete work faster. Example: divide-and-conquer on homework problems (but don't do that for CS251!). Other example: High-performance computer chips that parallelize machine learning applications.

How are these different?

Often, concurrency is implemented via _interleaving_, or the operating system rapidly switching between computations. This is likely what's happening when you are scrolling on a webpage while data also loads. There might be only one CPU actually doing the computation to scroll and to load, but the OS (for example, iOS) switches back and forth so rapidly that you don't notice.

True *parallelism* is when the underlying system is capable of performing multiple actions literally simultaneously (for example, by having multiple CPU cores, as most modern laptops have). Most processors today are _multicore_. In distributed systems, computations are shared across servers that may not even be in the same location.

### Analogy

CS111 idea: A program is like a recipe for a cook. One cook does one thing at a time! (Sequential)

#### Concurrency:
- Lots of cooks making different things, but only 4 stove burners.
- Want to allow access to all 4 burners, but not cause spills or incorrect burner settings.

#### Parallelism:
- Have lots of potatoes to slice?
- Hire helpers, hand out potatoes and knives.
- But too many chefs and you spend all your time coordinating

# Common parallel/concurrent abstractions

Computer scientists have many shared abstractions that transcend individual programming languages. We'll start with _threads_.

## Threads

A _thread_ is a single sequential stream of computation. Multiple threads can run at once, either via interleaving or parallel CPUs. A *scheduler* (often, the operating system) handles scheduling across multiple threads.

Programs have a *main thread*, which is the thread that executes the main function/runs by default. The main thread can create new threads, which appear to run simultaneously with the main thread.

## Processes

Processes are independent program executions, which may contain multiple threads. Processes run individual program executables: in our example, Spotify and VSCode must be running in different processes. But, for example, the Spotify process may contain multiple threads running at once (most desktop applications do).

By default, all threads within a process share one heap, whereas processes do not share heaps.

We'll leave the details of processes CS240 and later classes.

# Promises

While threads and processes are the core concepts at the operating system level, most modern programming languages introduce higher-level abstractions on top of the OS level.

In both functional programming languages and popular imperative languages such as Javascript, a popular higher-level abstraction is a **promise** (also called a "future"). A promise/future is a type of computation that may not have finished yet: it *promises* to eventually produce a value of a specified type in the *future*, but the computation may not be complete yet.

We can think of a promise as similar to a `ref` cell that can be mutated at most once. When a promise is created, it's like an empty cell that does not yet contain a value. Creating a promise creates the empty cell and kicks off the computation that will eventually fill the cell, but the sequential stream of execution continues even if the computation itself is not done. Eventually, at some point in the future, the promise can be *fulfilled* when the computation completes and places a value in the cell. Alternatively, if an error happens during the promise fulfillment, the cell could be filled with an exception instead of a normal value (which the OCaml book calls "rejected"). The book uses "resolved" for when the promise is either fulfilled or rejected. In either case, though, once the promise cell is filled, its contents cannot change (which is why we think of it as being mutated at most once).

What ties promises to parallel/concurrent computation is that a single program can have multiple promises being fulfilled at once. Once a promise resolves, the code may kick off additional sequential or concurrent computations that depend on its value.

This is the same core idea used by the popular `async`/`await` in modern Javascript! In Javascript, the `async` keyword causes a function to return a promise, and the `await` keyword that waits for a promise to finish computing before proceeding with execution. OCaml uses these same names for a similar effect.

# Concurrency in OCaml

The ideas above are shared across programming languages, but we can now also dig into the OCaml specifics.

OCaml has several different libraries that provide concurrency/parallelism. Prior to OCaml 5, OCaml did not support true multicore parallelism.

- The OCaml standard library provides the [`Threads` library](https://ocaml.org/manual/5.1/libthreads.html#:~:text=Only%20one%20thread%20at%20a,programs%20as%20several%20communicating%20processes.), which is quite low-level.
- The [OCaml Programming: Correct + Efficient + Beautiful book](https://cs3110.github.io/textbook/chapters/ds/promises.html) uses the `lwt` library for promises and concurrency.
- We'll use the new [`domainslib` library](https://ocaml.org/manual/5.3/parallelism.html), which is now recommended by the OCaml manual for higher-level parallelism.

:::success
Install `domainslib` with the following:

opam install domainslib

:::

# Parallelism with Domains

A domain is an OCaml unit of parallelism that maps 1-to-1 with an operating system thread. The OCaml manual recommends that programs do not spawn more domains than the number of available cores.

:::info
Next class, we'll show how to see how many cores a computer has.
:::

We can spawn a new domain, and code called within that domain will be run _in parallel_ with the main domain.

To use domains,

#require "domainslib";;
open Domain;;
open Domainslib;;

To create a new domain, we use `Domain.spawn`.

# Domain.spawn ;;
- : (unit -> 'a) -> 'a t = <fun>

What is type `t`? A promise! A domain of type `'a t` eventually produces either a result of type `'a` (is fulfilled) or an exception (is rejected).

Let's show this with some printlines:

If we run just:

Domain.spawn (fun () -> print_endline "printed from parallel domain") ;

:::success
Why do we need to write `fun () ->` before the print line?
:::

Answer: because otherwise, OCaml's eager evaluation would evaluate the function argument to a value before every passing it to the concurrent library call! We need to wrap the print in a *thunk* to delay its evaluation (that is, to let the library call handle executing the print on a separate domain/thread).

When we run with two prints:

Domain.spawn (fun _ -> print_endline "printed from parallel domain") ;
print_endline "printed from main domain" ;;

We see that despite the order in the code, the main message sometimes prints first!

This is because the main domain/thread by default **does not wait** for the spawned domain to resolve. The ordering of operations between concurrent domains/threads is **not specified** unless we explicitly force it to be: operations may be interleaved in any order (as long as sequential order **within** each domain/thread is respected).

We can force a specific ordering, in this case, by adding a `join`.

let task = Domain.spawn (fun _ -> print_endline "printed from parallel thread") in 
let _ = Domain.join task in 
print_endline "printed from main thread" ;;

`join` forces the promise to resolve before it continues with sequential execution. Here, because we call `join` on the `task` promise before the second printline, this now forces the following order of prints:

printed from parallel thread
printed from main thread

Because the main domain cannot hit its `print_endline` until the task domain has resolved!

:::success
Question: does this mean the code is no longer concurrent?
:::

Answer: Not quite. These is still concurrency between the spawned domain code and whatever code happens in the main domain between line 1 and the `join` call being made. In this case, that is nothing observable, but there are still briefly two parallel domains running simultaneously.

Next class, we'll see how to use promises to parallelize computations.