Class PLDI

insertion_sort (A)
    for i in len(A) -2 down to 0
        v = A[i]
        for j in i+1 to len(A) -1
            // A[j..len(A) - 1] is sorted
            if A[j] > v break
            A[j-1] = a[j]
        A[j-1] = v

sort(A):

if len(A) < 2 return A;
else

    let v be A[0] + R be A[1..]
    return insert (v, sort (R))

where insert (v, S):
    if len(S) == 0 return {v}
    else
        let w be S[0] + T be S[1..]
        if v <w  return v, S
        else return w.insert(v,T)
    

Stephen Kleene; U of Wisc; Mathcn; Recursion theory;
Kleene star (Kleene closure).

Church-Turning Theory: computability.

1   program       ->  stmt_list $$
2   stmt_list     ->  stmt_list stmt | E
3   stmt          ->  ID := expr | READ ID | WRITE expr
4   expr          ->  term | expr add_op term
5   term          ->  factor | term mult_op factor
6   factor        ->  ( expr ) | ID | LITERAL
7   add_op        ->  + | -
8   mult_op       ->  * | /

AST_node expr()
   case input_token of 
    id, literal, (:
        T := term()
        return term_tail(T)
    else: error

AST_node term_tail(T1)
   case input_token of
    +,-: 
        op:=addop()
        T2:= term()
        N := new node(op, T1, T2)
        return term_tail(N)
    ), id, read, write, $$:
        return T1
    else error

E => E + T          E1.n = new bin_op(+, E2.n, T.n) // .n -> .node
E => E - T          E1.n = new bin_op(-, E2.n, T.n)
E => T              E.n  = T.n
T => T * F          T1.n = new bin_op(*, T2.n, F.n)
T => T / F          T1.n = new bin_op(/, T2.n, F.n)
T => F              T.n  = F.n
F => - F            F1.n = new un_op(-, F2.n)
F => (E)            F.n  = E.n
F => const          F.n  = new num(const.val)
F => id             F.n  = new ident(id.name)

E  => T TT          E.n = TT.n
                    TT.st = T.n
TT1 => + T TT2      TT1.n = TT2.n
                    TT2.st = new bin_op(+, TT1.st, T.n)
TT => - T TT        TT1.n = TT2.n
                    TT2.st = new bin_op(-, TT1.st, T.n)
TT =>               TT.n = TT.st
T  => F FT          T.n = FT.n
                    FT.st = F.n
FT => * F FT        FT1.n = FT2.n
                    FT2.st = new bin_op(*, FT1.st, F.n)
FT => / F FT        FT1.n = FT2.n
                    FT2.st = new bin_op(/, FT1.st, F.n)
FT =>               FT.n = FT.st
F  => - F           F1.n = new un_op(-, F2.n)
F  => ( E )         F.n = E.n
F  => const         F.n = new num(const.val)
F  => id            F.n = new ident(id.name)

P -> I 
int dec: I
real dec: I
read: I
write: I
assign: I -> id E I
'+': E -> E E

      -- Euclid algorithm.

let rec gcd a b =
  if a = b then a
  else if a > b
    then gcd (a-b) b
    else gcd a (b-a)

 gcd(a, b) {
    top:
        if a == b return a
        elsif a > b
            a := a - b
            goto top
        else
            b := b - a
            goto top
    }

let rec sum1 f low high =
      if low = high then f low
      else (f low) + (sum1 f (low + 1) high);;

// changed to 

let rec sum2 f low high st =
      if low = high then st + (f low)
      else sum2 f (low + 1) high (st + (f low));;

    let sum3 f low high =
      let rec helper low st =
        let new_st = st + (f low) in
        if low = high then new_st
        else helper (low + 1) new_st in
      helper low 0;;

    let rec f = .. g .. 
    and rec g = .. f ..
    in expr

let rec fib n = 
   match n with
    | 0 -> 1
    | 1 -> 1
    | _ -> fib (n-1) + fib(n-2)

// tail rec version:

let fib2 n = 
  let rec helper f1 f2 i =
    if i = n then f2
    else helper f2 (f1 + f2) (i + 1) in
    helper 0 1 0;;

F(n) = nearest whole number to ($\phi ^ n$)/(\squa {5}), where $\phi = (1 + \squa{5})/(2)$

let rec len l = 
    match l with 
    | [] -> 0
    | [_] -> 1
    | hd::tl -> 1 + len tl;;

> _: len = `a list -> int <func>

      ==> [15;]

int -> (int -> int): given one int, it returns a function that is (int -> int)

----------------------------------------
 ||             ||  |      |   ||
 ||             ||  |      |   ||
----------------------------------------

 let foo l k =
      let rec helper l f i b =
        match l with
        | [] -> raise (Failure "list too short")
        | h :: t ->
            if i = k then f h
            else if (b && h < 0) then helper t (( + ) h) (i + 1) false
                 else helper t f (i + 1) b in
      helper l (fun x -> x) 0 true;;

This captures the "right" h in foo [1; -3; 2; -4; 5] 4;;

------------
f  -----> ? h
helper
...
helper
helper
foo
------------

let g p = p 2;

let d() = 
  let x = 3 in ( + ) x;;

g (d());; ==> 5

// where to find x?

int a

proc first:
    a = 1

proc second:
    int a
    first()

a := 2; second(); write(a)

def plus x = fun y -> x + y;;

def plus3 = plusx 3;; // subroutine closure = |plusx | 3 |;

// plus3 5;; 
// ==> 8

auto plusx (int x) {
    return [x](int y){return x + y;}; // lambda expression, a function with no name; a body of func; a capture list [x]
    //return [&x](int y){return x + y;}; // &x here is not safe.
}

//...
auto plus3 = plusx(3);
count << plus3(5); // ==> 8

int x;
void foo(int &y){
    count << x << y << x + y ;
}
foo (&x);

let len l = match l with
 | [] -> 0
 | h::t -> 1 + len t;;

len: `a list -> int

$_ = "-3.14e5"

if (/^[+-]?((\d+)\.|(\d*))\.(\d+))(e([+-]?\d+))?$){
    1      2 3      4       5     6 7
}

// ? means optional; [] one char; \d digits; 
// use $1, $2, $3, ... for the matching parts

if c1
  then if c2
       then 
else ... (which if is this else belongs to)

// solution

- match the closest ones;

- use terminators: end

// bad decision to have break in switch stmts in C;
// most other language don't have notion of fall through

switch (x) {
    3:
    5:
    7:
    9:
}

// characteristic array: array[0, max-value], each element is empty (if no such case) or stores a pointer (code pointer for that case)

// hash table: compiler knows all the possible hash values --> can pick (a perfect) hash func with no collisions.

// linear search array: arrary of <case, code-ptr>


For cases with ranges:

case expr of 
1 .. 48:
97 .. 283:
900 .. 1024:
1234 .. 2302:
esac

// decision tree O(log(n)), no insert/deletion, can do redistribution if not even tree;
// or binary search O(log(n)), 

top: 
    r1:=condition // >=1 inst
    if !r1 goto continue
      <body>
    goto top
continue:


// improve 01

   r1:=condition
   if r1 goto continue
top:
      <body>
   r1:=condition
   if r1 goto top
skip:

// improve 02
 
goto test
top:
      <body>
test:
   r1:=condition
   if !r1 goto top

for (i = first; i<= last; i++){
    // body
}

==>

i = first
while (i <= last){
    // body
    ++i;
}

// but got complicated in newer C, where for (int i=first;...), the i is local to body.

open Printf;;
let show n = printf "%d\n" n;;

let upto lo hi =
    fun f -> let rec helper i =
                if i > hi then ()
                else (f i ; helper (i + 1)) in
    helper lo;;

upto 1 10 show;; =>
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    - : unit = ()

sum = 0                                 # => 0
[ 1, 2, 3 ].each { |i| sum += i }       # => [1, 2, 3]  # array itself
sum                                     # => 6

# or

sum = 0
for i in [1, 2, 3] do       # 'do' is optional
    sum += i
end
sum

def uptoby(lo, hi, step):
    while True:
        if (step > 0 and lo > hi) or (step < 0 and lo < hi): return
        yield lo
        lo += step  # ignore overflow


# call it

for i in uptoby(1,10,2):
  # body

List<foo> myList= ...;

for (foo o: mylist){
    // use o
}

==> a syntax sugar of underlying:

for (Iterator<foo> i = myList.iterator(); i.hasNext()){
    foo o = i.next();
    // use o
}

==> for a iterator, must have three functions: iterator(), hasNext(), next();

list<foo> my_list;
...

for (list<foo>:: const_iterator i = my_list, begin(); i != my_list.end(); i++){
    // use i
}

// iterator =~ (smart) pointer
// .end() is a pointer that has just passed the last element.

foreach(foo o in myList){
    // use o 
}

==>

for (IEnumerator<foo>i = myList.GetEnumerator(); i.moveNext();){
    foo o = i.Current; // accessor
    // use o
}

// The interface implemented as

class List : IEnumerable {
    ...
    public IEnumerator GetEnumerator() {
        node n = head;
        while (n != null) {
            yield return n.content;
            n = n.next;
        }                   // NB: no return stmt
    }
}

// ==> the compiler define IEnumerator class as a special calss; in facing of this and `yield return` statement inside; the compiler will automatically create 
// - the new version of .GetEnumerator()
// - the .MoveNext();
// - the .Current
// 
// iterator stored on heap? implicit iterator object.

if x then e1 else e2

e1: 'a * int
e2: char list * b

==> expression inferred as <char, int>

    class stack {
        void*[100] contents;
        int tos = 0;
    public:
        void* pop();
        void push(void *);
        ...
    }

public static <T implements Comparable<T>> void sort(T A[]) {
        ...
        if (A[i].compareTo(A[j]) >= 0) ...
        ...
    }
    ...
    Integer[] myArray = new Integer[50];
    ...
    sort(myArray);

interface Comparator<T> {
    public Boolean ordered(T a, T b);
}

class Sorter<T> {
    Comparator<T> comp;

    public Sorter(Comparator<T> c) {    // constructor
        comp = c;
    }

    public void sort(T A[]) {
        ...
        if (comp.ordered(A[i], A[j])) ...
        ...
    }
}

class IntComp implements Comparator<Integer> {
    public Boolean ordered(Integer a, Integer b) {
        return a < b;
    }
}

Sorter<Integer> s = new Sorter<Integer>(new IntComp());
s.sort(myArray);

          atomic          condition

// define it

f(){
    ...
    reply();
    ...
}

// call it

f();

// ready == false

p = new foo(args)
ready = true                while (!ready) {}
                            // use *p

memory
----------------------------

cash cash cash cash cash (privilage cache; a write will kick out any other's cache)

p    p    p     p    p 

yield:
    disable_signals()
    enqueue(ready_list, current)
    reschedule
    re-enable_signals()

yield:
    disable_signals()
    acquire(scheduler_lock)        // spin lock
    enqueue(ready_list, current)
    reschedule
    release(scheduler_lock)
    re-enable_signals()

disable_signals()
acquire(scheduler_lock)        // spin lock
if not <desired condition>
    sleep_on <condition queue>
release(scheduler_lock)
re-enable_signals()

type semaphore = record
    N : integer     -- initialized to something non-negative, the counter.
    Q : queue of threads

procedure P(ref S : semaphore) :  // reduce counter
    disable_signals()
    acquire(scheduler_lock)
    if S.N > 0
        S.N -:= 1
    else
        sleep_on(S.Q)  -- give processor to others
    release(scheduler_lock)
    re-enable_signals()

procedure V(ref S : semaphore) : // add counter
    disable_signals()
    acquire(scheduler_lock)
    if S.Q is nonempty
        enqueue(ready_list, dequeue(S.Q)) // wake up one thread in the queue.
    else
        S.N +:= 1
    release(scheduler_lock)
    re-enable_signals()

shared buf : array [1..SIZE] of data
shared next_full, next_empty : integer := 1
shared mutex : semaphore := 1
shared empty_slots, full_slots : semaphore := SIZE, 0

procedure insert(d : data) :
    P(empty_slots)
    P(mutex)
    buf[next_empty] := d
    next_empty := next_empty mod SIZE + 1
    V(mutex)
    V(full_slots)

function remove returns data :
    P(full_slots)
    P(mutex)
    d : data := buf[next_full]
    next_full := next_full mod SIZE + 1
    V(mutex)
    V(empty_slots)
    return d

                    |

// LLM: how the monitor implemented?
// 

class BB {
    final private int SIZE = 10;
    private Object[] buf = new Object[SIZE];

    private int nextEmpty = 0;
    private int nextFull = 0;
    private int fullSlots = 0;

    synchronized public void insert(Object d) throws InterruptedException {
        while (fullSlots == SIZE) {
            wait();
        }
        buf[nextEmpty] = d;
        nextEmpty = (nextEmpty + 1) % SIZE;
        ++fullSlots;
        notifyAll();            // explain why!
    }

    synchronized public Object remove() throws InterruptedException {
        while (fullSlots == 0) {
            wait();
        }
        Object d = buf[nextFull];
        nextFull = (nextFull + 1) % SIZE;
        --fullSlots;
        notifyAll();            // explain why!
        return d;
    }
}

BB solution in Java 2 without using notifyAll is quite a bit harder:

class BB {
    final private int SIZE = 10;
    private Object[] buf = new Object[SIZE];

    private Object producerMutex = new Object();
    // waited upon only by producers
    // protects the following:
        private int nextEmpty = 0;
        private int emptySlots = SIZE;

    private Object consumerMutex = new Object();
    // waited upon only by consumers
    // protects the following:
        private int nextFull = 0;
        private int fullSlots = 0;

    public void insert(Object d) throws InterruptedException {
        synchronized (producerMutex) {
            while (emptySlots == 0) {
                producerMutex.wait();
            }
            --emptySlots;
            buf[nextEmpty] = d;
            nextEmpty = (nextEmpty + 1) % SIZE;
        }
        synchronized (consumerMutex) {
            ++fullSlots;
            consumerMutex.notify();
        }
    }

    public Object remove() throws InterruptedException {
        Object d;
        synchronized (consumerMutex) {
            while (fullSlots < 0) {
                consumerMutex.wait();
            }
            --fullSlots;
            d = buf[nextFull];
            nextFull = (nextFull + 1) % SIZE;
        }
        synchronized (producerMutex) {
            ++emptySlots;
            producerMutex.notify();
        }
        return d;
    }
}

class BB {
    final private int SIZE = 10;
    private Object[] buf = new Object[SIZE];

    private int nextEmpty = 0;
    private int nextFull = 0;
    private int fullSlots = 0;

    Lock l = new ReentrantLock();        // new
    final Condition emptySlot  = l.newCondition();         // new
    final Condition fullSlot = l.newCondition();           // new

    public void insert(Object d) throws InterruptedException {
        l.lock();                // new
        try {                    // new
            while (fullSlots == SIZE) {
                emptySlot.await();
            }
            buf[nextEmpty] = d;
            nextEmpty = (nextEmpty + 1) % SIZE;
            ++fullSlots;
            fullSlot.signal();
        } finally {              // new
            l.unlock();          // new
        }
    }

    public Object remove() throws InterruptedException {
        l.lock();
        try {
            while (fullSlots == 0) {
                fullSlot.await();
            }
            Object d = buf[nextFull];
            nextFull = (nextFull + 1) % SIZE;
            --fullSlots;
            emptySlot.signal();
            return d;
        } finally {
            l.unlock();
        }
    }
}

try{

} catch (exception_type1 ex1){

} catch (exception_type2 ex2){

}

trampoline

    main program
        |
        '-----------------------------------------> kernel
                                                      |
                    event       signal  <-------------'
                    handler     trampoline         rti
                                   |
                        <----------'
                        |
                        '--------->,
                                   |
         ,<------------------------'
         |

// may cause deadlock (priority invertion: handler>main but main holds lock)

// Java
Parent p ;
Child c = new Child();
P = c;

p.f(); // which version do we get? dynamic binding: child methods.

// C++
Parent *p;
Child c;
p = &c;

p -> f(); // which version? virtual vs non-virtual ==> abstract vs concrete type.

std::mutex my_lock
{
    std::lock_guard _(&my_lock);

    break;
    return;
    thrown;
    // can break out anywhere but the desctructor always be called thanks to my_lock; 

}

member1 = a; // assignment operator got called;

------- a vtable for each class ---> Vtable: 
------- parent methods
------- parent methods
------- parent methods
------- child methods
------- child methods
------- child methods
------- child methods

VTable:

------- virtual method
------- virtual method

// Example in text book


Class widget{
    interface sortable {

    }

    interface graphable{

    }
}

Class named_widget extends widget implement sortable {

}

Class augmented_widget extends named_widget implements graphable {

}


// augmented_widget

--------- a pointer --> augmented/widget/vtable
---------
---------
---------
// sortable, at distance 'offset' from augmented_widget
--------- a pointer --> sortable  
---------                   --------- (=offset)
---------
---------


// graphable
--------- a pointer --> graphable
---------
---------
---------

Foo f; // f() // 

class{
    foo() = delete; // if you do not want default constructor, do this. compiler will check all declarations are not using default constructor.
}

foo f = g;  // f(g); f g same type; copy constructor.??

gg = my_func(f);  
fun(my_func(f));

void my_func(foo x){   //==> copy constructor is called when passing f by value.
   foo t; 
   return t; //==> copy constructor can be called during return;
   a,b,c = ...;
   return foo(a,b,c); //==> this is an object somewhere; manual says this object should be created where this parent func is being called, to avoid a call to copy constructor; impl: a callback pointer to the caller i.e. in `gg=my_func(f)` or in `fun(my_func(f)) ; side effects. 
}

x = y; 
// l/r value: l value has a location in memory; r value might not have location in memory;

p = &4; // 4 is not an l-value, but an r-value, and it does not have an address so invalid stmt;

std::move<T>()

foo f = ....;

A.insert(f); // a copy constructor, f still valid after this line;
A.insert(move(f)); // a move constructor, f will be 'moved' and passed to A.insert; and f will not be valid after this line;

class widget{
    interface sortable{
    interface graphable{

    class named_widget implements sortable{   // xyz(sortable s) { s.compare(T); }
    class augmented_widget implements graphable{   


aug/named widget view
                +++++++++ --> vtable --- widget
                --plain--            -------------
                ---------            -------------
                ---------
                ---------
                +++++++++ --> vtable --- sortable for named_widget
                - named -            -- offset to named_widget, a
                ---------            -------------
                ---------                    
                +++++++++ --> vtable --- graphable
                - augm -             -------------
                ---------            -------------
                ---------                    


named_widget w;

xyz(w); // passed in the sortable view of the object w; i.e. srtable = w + a; inside xyz, will get back to w by srtable - a;


xyz(sortable s){

    s.compare(T);

// assembly translation:
    r1 = this; // this of sortable;
    r2 = *r1 ; // get the vtable;
    r1 -= *r2 ; // get the this of named_widget; the concrete obj.this
    r2 += 3 * wordsize ; // get the method of third 
    r2 = *r2; 
    call(r2)
}

class X: public P;
class Y: public P;

class Z: public X, public Y{
}

  X 
P    Z
  Y 

=> P X Y Z or P Y X Z

or 

P X 
    Z
P Y