Control flow mechanisms and their implementation (23 and 25 Oct. 2012) T4 due today A4 due 11:59pm Wed. 7 Nov. ---------------------------------------- Midterms: possible: 72 high: 67 low: 24 median: 51 mean: 49 Comments: generally pretty happy with the exam; this is, on the whole, a strong class people had the most difficulty with the AG problem It's about as simple as I could make it: S-attributed I was looking for initialize to 0 at leaves pass upward add 1 in primary -> ( expr ) max in expr -> primary expr_tail and args_list -> expr args_tail the scoping question also gave some people trouble, though less than in past years. Haskell was clearly an obstacle for some. and in the storage allocation question, I was surprised that some people seemed to think type was the determining factor (as in, say, scalars are global, arrays go in the stack, pointers go in the heap). Type is immaterial. What matters is lifetime. ============================================================== [ Expression-oriented v. statement-oriented languages [ Expressions generate a value; statements just have side effects [ expression-oriented: [ functional languages (Lisp, Scheme, ML) [ Algol-68 [ statement-oriented: [ most imperative languages [ C kinda halfway in-between [ [ Orthogonality [ [ if (if b != 0 then a/b == c else false) then ... [ if (if f then true else messy()) then ... [ [ initialization, aggregates [ Essential for functional programming; very handy for imperative [ programming. [ Standard Pascal has no initialization -- major omission [ C has aggregates only for initialization -- major [ non-orthogonality ORDER of execution matters for statements, and for expressions with side effects. Ordering for statements is CONTROL FLOW. Principal paradigms for control flow: sequencing selection iteration subroutines, recursion (and related control abstractions, e.g. iterators) nondeterminacy concurrency ---------------------------- Expression evaluation infix, prefix operators precedence and associativity C has 15 levels -- too many to remember Pascal has 3 levels -- too few for good semantics Fortran has 8; Ada has 6 I don't like the rules in *any* of these (Fortran probably closest) Ada puts and, or at same level Pascal if a = b or c = d then Lesson: when unsure, use parentheses! << consider f(a+b, c, d(e, h), h) Why might order of evaluation of arguments matter? Why might implementation choose a particular order? Should the language say? >> ordering of operand evaluation (generally none) application of arithmetic identities distinguish between commutativity (assumed to be safe) and associativity (known to be dangerous) (a + b) + c works if a ~= minint and b ~= maxint and c is small a + (b + c) may not (esp. in FP) inviolability of parentheses short-circuiting if (b != 0 && a/b == c) ... if (*p && p->foo) ... if (f || messy()) ... connection to lazy evaluation of arguments [ and to the distinction between functions (define, let) and [ special forms (define-syntax, let-syntax) in Scheme. Variables as values v. variables as references value-oriented languages C, Pascal, Ada reference-oriented languages most functional languages (Lisp, Scheme, ML, Haskell) Clu Smalltalk Algol-68 kinda halfway in-between Java deliberately in-between built-in types are values user-defined types are objects -- references C# similar, though user can choose which object variables are values ("expanded", in Eiffel terminolody) and which are references [ Assignment [ statement (or expression) executed for its side effect(s) [ [ assignment operators (+=, -=, etc) [ handy [ avoid redundant work (or need for optimization) [ perform side effects exactly once [ [ C --, ++ [ prefix v. postfix semantics [ postfix more than syntactic sugar Initialization v. assignment esp. important in OO languages foo b; // calls no-arg constructor foo::foo() foo f = b; // calls one-arg "copy constructor" foo::foo(&foo) // This is syntactic sugar for // foo f(b); foo b, f; // calls no-arg constructor f = b; // calls foo::operator=(&foo) Side Effects often discussed in the context of functions a side effect is some permanent state change caused by execution of function -- some noticable effect of call other than return value. in a more general sense, assignment statements provide the ultimate example of side effects. They change the value of a variable. SIDE EFFECTS ARE FUNDAMENTAL TO THE WHOLE VON NEUMANN MODEL OF COMPUTING In (pure) functional, logic, and dataflow languages, there are no such changes. These languages are called SINGLE-ASSIGNMENT languages. They might better be called "simple definition" languages. [ several langauges outlaw side effects for functions [ easier to prove things about programs [ closer to Mathematical intuition [ easier to optimize [ (often) easier to understand [ [ but side effects can be nice [ consider rand() [ [ side effects are a particular problem if they affect state used in [ other parts of the expression in which a function call appears, [ because many languages don't specify an evaluation order for [ components of an expression. It's nice not to specify an [ order, because it makes it easier to optimize. Fortran says [ it's ok to have side effects, but they aren't allowed to change [ other parts of the expression containing the function call. [ Unfortunately, compilers can't check this completely without [ language restrictions, and most don't try to do so. [ [ BTW, note the difference between [ errors (forbidden by language definition) [ "erroneous" (term introduced by Ada) -- forbidden, but [ compiler not required to catch [ implementation-defined behavior [ and undefined behavior ---------------------------------------- sequencing specifies a linear ordering on statements very imperative, Von-Neumann selection sequential if statements if ... then ... else if ... then ... elsif ... else (cond (C1) (E1) (C2) (E2) ... (Cn) (En) (T) (Et) ) value of explicit terminators or begin/end (or {}) brackets need for elsif (elif) jump code For selection and logically-controlled loops. No point in computing a Boolean value into a register, then testing it. Instead of passing register containing Boolean out of expression as a synthesized attribute, pass inherited attributes INTO expression, indicating where to jump to if true, and where to jump to if false. Especially useful in the presence of short-circuiting. Example (section 6.4.1 of book): if ((A > B) and (C > D)) or (E <> F) then then_clause else else_clause w/out short-circuiting (as in, e.g., Pascal): r1 := A -- load r2 := B r1 := r1 > r2 r2 := C r3 := D r2 := r2 > r3 r1 := r1 & r2 r2 := E r3 := F r2 := r2 <> r3 r1 := r1 | r2 if r1 = 0 goto L2 L1: then_clause -- label not actually used goto L3 L2: else_clause L3: with short-circuiting (as in, e.g., C): r1 := A r2 := B if r1 <= r2 goto L4 r1 := C r2 := D if r1 > r2 goto L1 L4: r1 := E r2 := F if r1 = r2 goto L2 L1: then_clause goto L3 L2: else_clause L3: guarded commands example of non-determinacy if cond1 -> stmt1 [] cond2 -> stmt2 ... [] condN -> stmtN fi similar version for loops fortran computed gotos case/switch (introduced in Algol-W) nobody lets labels overlap << what should happen if there isn't a matching label for value? >> suppose no label for value? Ada: forbid at compile time C: no-op Pascal: dynamic semantic error << what implementation should we use for 3: 1: 1: 1..48: 5: 2: 59: 97..283: 7: 3: 187: 900..1024: 9: ... ... ... 1000: 1000000: 12345..67890: >> case implementation sequential testing small number of choices, non-dense range jump table dense range search table (hashing, binary search, search tree) non-dense range hash table not an option when some labels are themselves big ranges should ranges be allowed in the label list? they make it easy to state things for which a jump table or hash table is awful: can be done efficiently with binary search ======================================== iteration logically-controlled pre-test (while) post-test (repeat) one-and-a-half loops (loop with exit) labels for non-closest exit? implementation options: top: r1 := condition if !r1 goto continue < loop body > goto top continue: That has two branches in every iteration. r1 := condition if !r1 goto skip top: < loop body > r1 := condition if r1 goto top skip: That evaluates the condition twice. Not a big deal if it doesn't bloat code size. If it's complicated we can do this instead: goto test top: < loop body > test: r1 := condition if r1 goto top That has one extra jump, but only one copy of the test. C-style for loop semantically clean, but NOT really a for loop hard to apply the various optimizations possible for "real" for loops for (i = first; i <= last; i+= step) { ... } ~= i = first; while (i <= last) { ... i += step; } enumeration-controlled Pascal or Fortran-style for loops /* Modula-2 syntax */ i : integer; ... for i := first to last by step do ... end << How might we implement this? Consider i := first goto test top: ... i += step test: if i <= last goto top What can go wrong? >> Problems -- generally fixed in Ada and Fortran 90, to some extent in Modula-2. empty bounds shouldn't execute (did in Fortran I) changes to bounds or stepsize within loop calculated up front in modern languages direction of step constant stepsize "downto" (Pascal) "in reverse" (Ada) changes to loop variable within loop not generally allowed in modern langauges value after the loop especially at end-of-legal range for type (overflow?) if local to loop, can't even name afterward, so it's just an implementation issue, not a semantic one iteration count translation technique needed in Fortran, which has run-time step helpful any time the end value may be the last valid one gotos in and out modern langauges allow only out, and structure as exit/break/return (or exception) ------------ iterators supply a for loop with the members of a set abstraction/generalization of the 'from A to B by C' sorts of stuff you see built-in in older languages pioneered by Clu: for i in iterator do ... end built-in iterators for from_to, from_to_by, etc. wonderful for iterating over arbitrary user-defined sets very good for abstraction; for loop doesn't have to know whether set is a linked list, hash table, dense array, etc. may be true iterators (as in Clu, C#, Icon, Python, Ruby) or interface-based approximation ("iterator objects", as in Euclid, Java 5, and C++) iterator objects (Euclid, C++, Java 5) Standard interface for abstraction to drive for loops. Supported in Euclid and Java 5 with special loop syntax, and in C++ through clever use of standard constructor and operator overload mechanisms. In Java 5: List myList = ...; for (Object o : myList) { // use object o } requires that the to-be-iterated class (here, List) implements the Iterable interface, which exports a method public Iterator iterator() where Iterator is an interface exporting methods public boolean hasNext() and public Object next() The for loop is syntactic sugar for for (Iterator i = myList.iterator(); i.hasNext();) { Object o = i.next(); // use object o } C++ version looks like list my_list; ... for (list::const_iterator i = my_list.begin(); i != my_list.end(); i++) { // make use of *i or i->field_name } Don't have to have an equivalent of the Iterator interface (it's just a convention), because C++ individually type-checks every use of a generic (template). All the standard library collection/container classes support iterators, in both languages. ------------ true iterators (Clu, Icon, C#, Python) iterator itself looks like a procedure, except it can include "yield" statements that produce intermediate values. when the iterator returns, the loop terminates C# for loop resembles that of Java: foreach (object o in myList) { // use object o } This is syntactic sugar for for (IEnumerator i = myList.GetEnumerator(); i.MoveNext()) { object o = i.Current; // use object o } Current is an *accessor* -- a special method supporting field-like access: public object Current { get { return ...; } put { ... = value; } } In contrast to Java, you don't need to hand-create the hasNext() [MoveNext()] and next() [Current] methods. The compiler does this automatically when your class implements the IEnumerable interface and has an iterator -- a method containing yield statements and "returning" an IEnumerator: class List : IEnumerable { ... public IEnumerator GetEnumerator() { node n = head; while (n != null) { yield return n.content; n = n.next; } // NB: no return stmt } } If you want to be able to have multiple iteration orders, your class can have multiple methods that each return an IEnumerator. Then you can say, e.g. foreach (object o in myTree.InPreOrder) { ... foreach (object o in myTree.InPostOrder) { ... detail: IEnumerator implements MoveNext and Current (also Reset) IEnumerable implements GetEnumerator, which returns an IEnumerator ------------ loop body as lambda (Ruby, ML, Scheme, ...) Ruby: (1..10).each {|i| print i, "\n";} Scheme: (map show (upto 1 10)) ; where (define show (lambda (i) (begin (display i) (newline)))) (define upto (lambda (a b) (letrec ((f (lambda (a b L) (if (> a b) L (f a (- b 1)(cons b L)))))) (f a b '())))) ------------ implementation of true iterators (section 8.6.3-CD) coroutines or threads overkill single-stack used in Clu works, but would confuse a standard debugger, and not compatible with some conventions for argument passing implicit iterator object kinda cool; used in C# and Python block as lambda expression (Ruby, functional languages) ---------------------------- recursion equally powerful to iteration mechanical transformations back and forth often more intuitive (sometimes less) *naive* implementation less efficient no special syntax required fundamental to functional languages like Scheme tail recursion [ (define gcd (lambda (a b) [ (cond ((= a b) a) [ ((< a b) (gcd a (- b a))) [ ((> a b) (gcd (- a b) b))))) gcd :: (Integral a) => a -> a -> a gcd b c | b == c = b | b < c = gcd b (c - b) | c < b = gcd (b - c) c implemented as gcd (b c) start: if b = c return b if b < c c := c - b goto start if b > c b := b - c goto start changes to create tail recursion (e.g. pass along an accumulator) [ (define summation (lambda (f low high) [ (if (= low high) [ (f low) ; then part [ (+ (f low) (summation f (+ low 1) high))))) ; else part summation :: (Integral a) => (a -> a) -> a -> a -> a summation f low high | low == high = f low | otherwise = f low + summation f (low+1) high becomes [ (define summation (lambda (f low high subtotal) [ (if (= low high) [ (+ subtotal (f low)) [ (summation f (+ low 1) high (+ subtotal (f low)))))) summation2 :: (Integral a) => (a -> a) -> a -> a -> a -> a summation2 f low high st | low == high = st + f low | otherwise = summation2 f (low+1) high (st + f low) and then [ (define summation (lambda (f low high) [ (letrec ((sum-helper (lambda (low subtotal) [ (let ((new_subtotal (+ subtotal (f low)))) [ (if (= low high) [ new_subtotal [ (sum-helper (+ low 1) new_subtotal)))))) [ (sum-helper low 0)))) summation3 :: (Integral a) => (a -> a) -> a -> a -> a summation3 f low high = helper low 0 where helper low st | low == high = new_st | otherwise = helper (low+1) new_st where new_st = st + f low More generally (absent an associative operator), pass along a *continuation*. This is perfectly natural to someone used to programming in a functional language. Note that the summation example depends for correctness on the associativity of addition. To sum the elements in the *same* order we could have counted down from high instead of up from low, but that makes a more drastic change to the structure of the recursive calls. There is no perfectly general algorithm to discover tail-recursive versions of functions, but compilers for functional languages recognize all sorts of common cases. Sisal and pH have "iterative" syntax for tail recursion: function sum (f : function (n : integer returns integer), low : integer, high : integer returns integer) for initial st := f (low); while low <= high low := old low + 1 st := old st + f (low) returns value of st end for end function Sisal compiler was *really* good at finding tail recursive forms. concurrency specifies that statements are to occur (at least logically) concurrently concurrency is fundamental to probably half the research in computer science today subject of chapter 15 nondeterminacy choice "doesn't matter" periodically popular, promoted by Dijkstra for use with selection can apply to execution order as well useful for certain kinds of concurrency process server do receive read request -> reply with data [] receive write request -> update data and reply od also nice for certain axiomatic proof schemes raises issues of "randomness", "fairness", "liveness", etc.