Control flow mechanisms and their implementation (25 and 27 Oct. 2011) T4 due today A4 due 11:59pm Wed. 9 Nov. ---------------------------------------- Midterms: possible: high: low: median: mean: Comments: ============================================================== 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! 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 ~= maxint and b ~= minint and c is small a + (b + c) does not 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 (introduced in Algol-W) nobody lets labels overlap suppose no label for value? Ada: forbid at compile time C: no-op Pascal: dynamic semantic error 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 */ for i := first to last by step do ... end 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#, Ruby, 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 ------------ 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 ---------------------------- The goto controversy assertion: gotos are needed almost exclusively to cope with lack of one-and-a-half loops early return from procedure exceptions in 25 years of programming, I can't remember using one for any other purpose, except maybe complicated conditions that can't be separated into a single if-then-else because of the need for short-circuiting ---------------------------- 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))))) | implemented as | gcd (a b) | start: | if a = b | return a | if a < b | b := b - a | goto start | if a > b | a := a - b | 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 | becomes | (define summation (lambda (f low high subtotal) | (if (= low high) | (+ subtotal (f low)) | (summation f (+ low 1) high (+ subtotal (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)))) | 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 is *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.