程序代写代做代考 chain Java database flex jvm compiler ocaml c++ Control in Sequential Languages

Control in Sequential Languages
Mitchell Chapter 8

Topics
– “structured” jumps that may return a value
• Exceptions
– dynamic scoping of exception handler
• Continuations
– Function representing the rest of the program – Generalized form of tail recursion
• Control of evaluation order (force and delay) – Can increase efficiency
– Call-by-need parameter passing.
2

Exceptions: Structured Exit
• Historically, goto statements were used, which can jump out of anywhere or into anywhere
• Some languages have break statements
• Exceptions provide a clean way to jump out of or abort a
function call.
– Their effects would not be easy to achieve with other forms of controlled jumps.
• Main language constructs:
– Statement or expression to raise or throw exception
– Statement or expression to handle or catch exceptions, called a handler
3

Exceptions: Structured Exit
Terminate part of computation, achieving the following effects:
• Jump out of construct
• Pass data as part of jump
– This data can be used, for example, to recover from an error.
• Return to most recent site set up to handle exception
– The correct handler is determined according to dynamic
scoping rules
• Unnecessary activation records may be deallocated
– May need to free heap space, other resources
4

C++ vs ML Exceptions – Can throw any type
– Stroustrup: “I prefer to define types with no other purpose than exception handling. This minimizes confusion about their purpose. In particular, I never use a built-in type, such as int, as an exception.” – – The C++ Programming Language, 3rd ed.
• ML exceptions
– Exceptions are a different kind of entity than types.
– Declare exceptions before use
Similar, but ML requires the recommended C++ style.
• C++ exceptions
5

OCaml Exceptions exception ánameñ of átypeñ
• Declaration
– gives name of exception and type of data passed when raised
• Raise
raise (ánameñ áparametersñ)
– expression form to raise an exception and pass data
• Handler
try áexp1ñ with | ápatternñ -> áexp2ñ
– Evaluate first expression.
– If exception that matches pattern is raised, then evaluate second expression instead.
– General form allows multiple patterns.
6

Examples
exception Ovflw raise Ovflw exception Signal of int raise (Signal (x+4))
let f x = if x 0) / (try f 0 with | Ovflw -> 1)
let g x = if x=0 then raise (Signal 0)
else if x=1 then raise (Signal 1)
else if x=10 then raise (Signal (x-8))
else (x-2) mod 4 try g 10 with | Signal 0 -> 0 | Signal 1 -> 1
| Signal x -> x+8
7

Which Handler is Used?
let f x = if x 0) / (try f 0 with | Ovflw -> 1)
• Dynamic scoping of handlers
– First call handles exception one way
– Second call handles exception another
– General dynamic scoping rule
Jump to most recently established handler on run-time stack
• Dynamic scoping is not an accident – User knows how to handler error – Author of library function does not
8

General Form of Handler Expressions
try with
| -> | -> …
| ->
• First, is evaluated.
• If the evaluation terminates normally, the value of the whole try expression is the value of this expression; the handler is never invoked.
• If the evaluation raises an exception that matches (and there is no matching handler declared in ), then the corresponding handler is invoked.
• Pattern matching works just as in ordinary OCaml.
9

Exception for Error Condition
type ‘a tree = Leaf of ‘a | Node of ‘a tree * ‘a tree exception No_Subtree
let lsub (t:’a tree) =
match t with
| Leaf x -> raise No_Subtree | Node (x,y) -> x
• This function raises an exception when there is no reasonable value to return
• We’ll look at typing later.
10

Exception for Efficiency
• Function to multiply values of tree leaves let rec prod (t:int tree) : int =
match t with
| Leaf x -> x
| Node (x,y) -> (prod x) * (prod y)
• Optimize using exception let exception Zero in
let rec prod (t:int tree) : int =
match t with
| Leaf x -> if x=0 then (raise Zero) else x | Node (x,y) -> (prod x) * (prod y)
in
try (prod t) with Zero -> 0
11

scope
Dynamic Scope of Handler
exception X
try (let f y = raise X in
let g h = try h 1 with X -> 2 in
try g f with X -> 4)
with X -> 6
handler
Which handler is used?
12

exception X
try (let f y = raise X in
let g h = try (h 1) with X -> 2 in
try (g f) with X -> 4)
with X -> 6
• When a handler is in a nested block, the handler expression goes on the stack first and is treated like a declaration.
• A handler in a function definition is treated like a local variable.
Dynamic Scope of Handler
13

Dynamic Scope of Handler
exception X
try (let f y = raise X in
let g h = try (h 1) with X -> 2 in
try (g f) with X -> 4)
with X -> 6
handler X
6
14

Dynamic Scope of Handler
exception X
try (let f y = raise X in
let g h = try (h 1) with X -> 2 in
try (g f) with X -> 4)
with X -> 6
Note: pointers in closures left out of diagram, but can be deduced.
handler X
6
access link
fun f
15

Dynamic Scope of Handler
exception X
try (let f y = raise X in
let g h = try (h 1) with X -> 2 in
try (g f) with X -> 4)
handler X
6
access link
fun f
access link
fun g
with X -> 6
access link
handler X
4
access link
formal h
handler X
2
(g f)
18

Dynamic Scope of Handler
exception X
try (let f y = raise X in
let g h = try (h 1) with X -> 2 in
try (g f) with X -> 4)
with X -> 6
handler X
6
access link
fun f
access link
fun g
access link
handler X
4
• Dynamic scope: find first X handler, going up the dynamic call chain at the point raise X is executed.
• Result is 2.
(g f)
access link
formal h
handler X
2
access link
formal y
1
(h 1) activation blocks are popped.
• After the handler returns 2, the computation is done, so all
20

Comparison to Static Scope of Variables
exception X
try let f y = raise X in
let g h = try h 1 with X -> 2 in
try g f with X -> 4
with X -> 6
let x = 6 in
let f y = x in
let g h = let x = 2 in
h1 in
let x = 4 in gf
21

Static Scope of Declarations
var x
6
let x = 6 in
let f y = x in
let g h = let x = 2 in
h1 in
let x = 4 in gf
Static scope: find first x, following access links from the reference to x.
(g f)
(h 1)
access link
fun f
access link
fun g
access link
var x
4
access link
formal h
var x
2
access link
formal y
1
22

Typing of Exceptions
• Typing of raise áexnñ
– Recall definition of typing
• Expression e has type t if (normal termination of) e produces value of type t
– Raising exception is not normal termination • Example: 1 + raise X
• Typing of with | áexnñ -> ávalueñ
– Converts exception to normal termination – Need type agreement
– Examples
• 1+(tryraiseXwithX->e) Typeofemustbeint
• 1+(trye1 withX->e2) Typeofe1,e2mustbeint
23

Exceptions and Resource Allocation
exception X try
(let x = ref [1,2,3] in
let y = ref [4,5,6] in
… raise X
) with X -> …
• Resources may be allocated between handler and raise
• May be “garbage” after exception
• Examples – Memory
– Lock on database – Threads
–…
General problem: no obvious solution
24

Comparison: ML Example
• Exception used to handle a condition that makes it impossible to continue the computation
exception Determinant; (* declare exception name *) let invert M = (* function to invert matrix *)
…
if …
then raise Determinant
else … …
(* exit if Det=0 *)
in
try invert myMatrix with | Determinant -> …
Value for expression if determinant of myMatrix is 0
25

Comparison: C++ Example
Matrix invert(Matrix m) { if … throw Determinant; …
};
try { … invert(myMatrix); … }
catch (Determinant) { …
// recover from error }
• Note:
– raise instead of throw – catch instead of with – tryasinML
• A more significant difference:
– exceptions are types
26

Continuations
– Stop execution, and then later continue
• Themainidea: • Moreprecisely:
– The continuation of an expression in a program is the remaining actions to perform after evaluating the expression
• Important:
– does not depend on the expression, only the program that contains it.
27

Continuations
• Idea:
– The continuation of an expression is “the remaining work to be
done after evaluating the expression”
– Continuation of e is a function applied to e
• General programming technique
– Capture the continuation at some point in a program
– Use it later: “jump” or “exit” by function call
– A continuation with only a unit argument is like a simple jump. – A continuation with arguments is like a jump or exit with data.
• Useful in
– Compiler optimization: make control flow explicit – Operating system scheduling, multiprogramming – Web site design
28

Example of Continuation Concept
• Expression
– 2*x+3*y+1/x+2/y
• Whatiscontinuationof1/x?
– Remaining computation after division:
let before = 2*x + 3*y in
let continue d = before + d + 2/y in
continue (1/x)
– before is not essential, alternative is: let continue d = 2*x + 3*y + d + 2/y
in
continue (1/x)
29

Example: Error-Avoiding Division using Continuations
let divide (numer:float) (denom:float) (normal_cont: float -> float)
(error_cont: unit -> float) = if denom > 0.0001
then normal_cont (numer /. denom) else error_cont ()
let f (x:float) (y:float) =
let before = 2.0 *. x +. 3.0 *. y in let continue (quotient: float) =
before +. quotient +. 2.0 /. y in
let error_continue () = before /. 5.2 in divide 1.0 x continue error_continue
30

Example: Error-Avoiding Division using Exceptions
exception Div
let f (x:float) (y:float) =
try (2.0 *. x +. 3.0 *. y +. 1.0 /. (if x > 0.0001
then x
else raise Div) +. 2.0 /. y)
with Div ->
(2.0 *. x +. 3.0 *. y) /. 5.2
• Samebehaviour,simplerwithexceptions
• Ingeneral,continuationsaremoreflexiblethan
exceptions, but may require more programming effort.
31

Continuation-Passing Form and Tail Recursion
• continuation-passingform(CPS):eachfunctionor operation is passed a continuation
– Functions terminate by calling a continuation
– Thus, no function needs to return to the point from where
it was called.
– Like tail calls…
– There are systematic rules for transforming an expression or program to CPS.
32

Example: Tail Recursive Factorial
• Standardrecursivefunction fact(n) = if n=0 then 1 else n*fact(n-1)
• Tailrecursive
f(n,k) = if n=0 then k else f(n-1, n*k) fact(n) = f(n,1)
• Howcouldwederivethis?
– Transform to continuation-passing form
– Optimize continuation functions to single integer
33

Continuation View of Factorial
fact(n) = if n=0 then 1 else n*fact(n-1)
fact(9)
fact(8)
fact(7)
return
n
9
…
• This invocation multiplies by 9 and returns
• Continuation of fact(8) is lx. 9*x
return
n
8
…
• Multiplies by 8 and returns • Continuation of fact(7) is
ly. (lx. 9*x) (8*y)
return
n
7
…
• Multiplies by 7 and returns • Continuation of fact(6) is
lz. (ly. (lx. 9*x) (8*y)) (7*z)
34

Derivation of Tail Recursive Form
• Standardfunction
fact(n) = if n=0 then 1 else n*fact(n-1)
• Continuationform fact(n, k) = if n=0 then k(1)
else fact(n-1, lx.k (n*x) ) fact(n, lx.x) computes n!
• Examplecomputation
fact(3,lx.x) = fact(2, ly.((lx.x) (3*y)))
= fact(1, lx.((ly.3*y)(2*x)))
= fact(0, ly.((lx.3*(2*x))(1*y))) = ly.(3*(2*(1*y))) 1 = 6
35

Derivation of Tail Recursive Form
• Continuation-passingform
fact(n, k) = if n=0 then k(1) else fact(n-1, lx.k (n*x) )
• TailRecursiveFormasOptimizationofCPS fact(n,a) = if n=0 then a else fact(n-1, n*a )
Each continuation is effectively lx.(a*x) for some a • Examplecomputation
fact(3,1) = fact(2, 3) was fact(2, ly.3*y) = fact(1, 6) was fact(1, lx.6*x)
= fact(0, 6) = 6
36

Summary and Other Uses for Continuations
• DerivationofTailRecursiveForm(Optimization)
• ExplicitControl
– Normal termination — call continuation
– Abnormal termination — do something else
• CompilationTechniques
– Call to continuation is functional form of goto
– Continuation-passing style makes control flow explicit • WebApplicationsandServices(nextpage)
37

Web Applications and Services
• WebApplications,WebServices,Message-Oriented Middleware (MOM) and Service-Oriented Architecture (SOA) services
– Handle long running workflows
– Workflow may take 1 year to complete – Progress of subtasks is asynchronous
• Sequentialprogrammingissimplerthan asynchronous
• Continuationsprovide
– An easy way to suspend workflow execution at a wait state
– Thread of control can be resumed when the next message/event occurs, maybe some long time ahead
Continuations supported in some versions of Java JVM
38

Control of Evaluation Order (Force and Delay)
Example: controlling the order for efficiency
•
• •
•
let f x y = … x … y … in
f e1 e2
Suppose the value of y is needed only if the value of x has
some property.
Suppose the evaluation of e2 is expensive. We would like:
let f x y = … x … Force y … in
f e1 (Delay e2)
where Delay e2 causes the evaluation of e to be delayed until we call Force (Delay e2)
39

Control of Evaluation Order (Force and Delay)
• Delay and Force are explicit program constructs in Scheme
• They can be “programmed” in ML.
• Delay e is an abbreviation for (fun () -> e)
– Example: Delay (3+4) is (fun () -> 3+4)
• Force e is an abbreviation for e()
– Force (Delay (3+4)) is ((fun () -> 3+4) ()) = 7
40

Example
let time_consuming (n:int) = let rec tak x y z =
if x <= y then y else tak (tak (x-1) y z) (tak (y-1) z x) (tak (z-1) x y) in tak (3*n) (2*n) n let rec fib (n:int) = if n=0 || n=1 then 1 else fib (n-1) + fib (n-2) let odd (n:int) = (n mod 2) = 1 let f (x:int) (y:int) = if (odd x) then 1 else (fib y) in f (fib 9) (time_consuming 9) • tak runs for a very long time (and is used by time_consuming) • Function f has 2 arguments and the second is used only if the first is not odd. 41 • • Example (Continued) let f (x:int) (y:int) = if (odd x) then 1 else (fib y) in f (fib 9) (time_consuming 9) f (fib 9) (time_consuming 9) runs for a very long time A version that uses Delay and Force to only evaluate the second argument if needed. let lazy_f (x:int) (y:unit -> int) = if odd x then 1 else fib (y())
in
lazy_f (fib 9) (fun () -> time_consuming 9)
Because (fib 9) is odd, this expression terminates much more quickly than the one without Delay
•
42

Using a Delayed Value More than Once
• TheversionofDelayandForcedescribedsofar:
– Requires static scoping
– Saves time only if the delayed argument is used at most once.
• Aversionthatworkswhenthedelayedargumentis used more than once can also be programmed in ML.
• Mainidea:storeaflagthatindicateswhetherthe expression has been evaluated once or not.
– If not, then evaluate when needed and store the result. – If so, retrieve the stored result.
– This is call-by-need parameter passing.
43

type ‘a delay =
| EV of ‘a
| UN of (unit -> ‘a)
let ev (d:’a delay) = match d with
| EV x -> x
| UN f -> f()
let force (d:’a delay ref) = let v = ev !d in
(d := EV v; v)
•
A delayed value is a reference cell containing an “unevaluated delay”
let d = ref (UN (fun () -> fib 9) let d’ =
ref (UN (fun () -> time_consuming 9))
Forcing evaluation evaluates and stores
force d = 55
After the call to force:
d = ref (EV 55)
Implementation and Example
• •
44

Summary
– “structured” jumps that may return a value
• Exceptions
– dynamic scoping of exception handler
• Continuations
– Function representing the rest of the program
– Generalized form of tail recursion
– Used in Lisp and ML compilation, some OS projects, web application development, …
• Delay and Force
– For controlling evaluation order
– Can be used to (greatly) improve efficiency
– Can be used to implement call-by-need parameter passing
45

Related Posts