1CMSC 330: Organization of Programming LanguagesFinal Exam ReviewReview Choices•OCaml– closures, currying, etc• Threads– data races, synchronization, classic probs• Java Generics• Topics– garbage collection, exceptions, parameters• Semantics and Lambda Calculus2Environments and Closures•An environment is a mapping from variable names to values– Just like a stack frame•A closure is a pair (f, e) consisting of function code f and an environment e• When you invoke a closure, f is evaluated using e to look up variable bindingsExamplelet add x = (fun y -> x + y)(add 3) 4 <closure> 4 3+4 73Curried Functions in OCaml• OCaml has a really simple syntax for currying– This is identical to all of the following:• Thus:– add has type int -> (int -> int)– add 3has type int -> int• The return of add x evaluated with x = 3• add 3is a function that adds 3 to its argument– (add 3)4=7• This works for any number of argumentslet add x y = x + ylet add = (fun x -> (fun y -> x + y))letadd=(funxy->x+y)let add x = (fun y -> x+y)Curried Functions in OCaml(cont’d)• Because currying is so common, OCamluses the following conventions:– -> associates to the right•Thus int -> int -> int is the same as• int -> (int -> int)– function application associates to the left•Thus add34is the same as• (add 3) 44Another Example of Currying• A curried add function with three arguments:–The same as• Then...– add_th has type int -> (int -> (int -> int))– add_th 4has type int -> (int -> int)– add_th 4 5has type int -> int– add_th456is 15let add_th x y z = x + y + zlet add_th x = (fun y -> (fun z -> x+y+z))Data Types• Rect and Circle are type constructors- here a shape is either a Rect or a Circle• Use pattern matching to deconstruct values, and do different things depending on constructortype shape =Rect of float * float (* width * length *)| Circle of float (* radius *)let area s =match s withRect(w,l)->w*.l| Circle r -> r *. r *. 3.14area (Rect (3.0, 4.0))area (Circle 3.0)5Data Types, con't.type shape =Rect of float * float (* width * length *)| Circle of floatlet l = [Rect (3.0, 4.0) ; Circle 3.0; Rect (10.0,22.5)]• What's the type of l?• What's the type of l's first element?l : shape listshapePolymorphic Data Types• This option type can work with any kind of data– In fact, this option type is built-in to OCamltype 'a option =None| Some of 'alet add_with_default a = functionNone->a+42|Somen->a+nadd_with_default 3 None (* 45 *)add_with_default 3 (Some 4) (* 7 *)6Recursive Data Types• Do you get the feeling we can build up lists this way?– Note: Don’t have nice [1; 2; 3] syntax for this kind of listtype 'a list =Nil| Cons of 'a * 'a listlet rec length l = functionNil -> 0| Cons (_, t) -> 1 + (length t)length (Cons (10, Cons (20, Cons (30, Nil))))Creating a Modulemodule Shapes =structtype shape =Rect of float * float (* width * length *)| Circle of float (* radius *)let area = functionRect (w, l) -> w *. l| Circle r -> r *. r *. 3.14let unit_circle = Circle 1.0end;;unit_circle;; (* not defined *)Shapes.unit_circle;;Shapes.area (Shapes.Rect (3.0, 4.0));;open Shapes;; (* import all names into current scope *)unit_circle;; (* now defined *)7Module Signaturesmodule type FOO =sigval add : int -> int -> intend;;module Foo : FOO =structlet add x y = x + ylet mult x y = x * yend;;Foo.add 3 4;; (* OK *)Foo.mult 3 4;; (* not accessible *)Entry in signatureSupply function typesGive type to moduleAbstract Types in Signatures• Now definition of shape is hiddenmodule type SHAPES =sigtype shapeval area : shape -> floatval unit_circle : shapeval make_circle : float -> shapeval make_rect : float -> float -> shapeend;;module Shapes : SHAPES =struct...let make_circle r = Circle rlet make_rect x y = Rect (x, y)end8Imperative OCaml• There are three basic operations on memory:– ref:'a->'aref• Allocate an updatable reference– ! : 'a ref -> 'a• Read the value stored in reference– := : 'a ref -> 'a -> unit• Write to a referencelet x = ref 3 (* x : int ref *)let y = !xx:=4Semicolon Revisited; Side Effects• Now that we can update memory, we have a real use for ; and () : unit– e1; e2 means evaluate e1, throw away the result, and then evaluate e2, and return the value of e2–()means “no interesting result here”– It’s only interesting to throw away values or use () if computation does something besides return a result•A side effect is a visible state change– Modifying memory– Printing to output– Writing to disk9Exceptionsexception My_exception of intletfn=if n > 0 thenraise (My_exception n)elseraise (Failure "foo")let bar n =tryfnwith My_exception n ->Printf.printf "Caught %d\n" n| Failure s ->Printf.printf "Caught %s\n" sThreads10Thread Creation in Java• To explicitly create a thread:– Instantiate a Thread object• An object of class Thread or a subclass of Thread– Invoke the object’s start() method• This will start executing the Thread’s run()method concurrently with the current thread – Thread terminates when its run() method returnsData Race Examplepublic class Example extends Thread {private static int cnt = 0; // shared statepublic void run() {int y = cnt;cnt=y+1;}public static void main(String args[]) {Thread t1 = new Example();Thread t2 = new Example();t1.start();t2.start();}}11Locks (Java 1.5)• Only one thread can hold a lock at once– Other threads that try to acquire it block (or become suspended) until the lock becomes available• Reentrant lock can be reacquired by same thread– As many times as desired– No other thread may acquire a lock until has been released same number of times it has been acquiredinterface Lock {void lock();void unlock();... /* Some more stuff, also */}class ReentrantLock implements Lock { ... }Avoiding Interference: Synchronizationpublic class Example extends Thread {private static int cnt = 0;static Lock lock = new ReentrantLock();public void run() {lock.lock();int y = cnt;cnt=y+1;lock.unlock();}}…}Lock, for protecting the shared stateAcquires the lock;Only succeeds if notheld by anotherthreadReleases the lock12Deadlock• Deadlock occurs when no thread can run because all threads are waiting for a lock– No thread running, so no thread can ever release a lock to enable another thread to runThread 1l.lock();m.lock();...m.unlock();l.unlock();Lock l = new ReentrantLock();Lock m = new ReentrantLock();Thread
View Full Document
Unlocking...