Transcript My Python-oriented slides

CSC 310 – Theory of Programming
Languages, Spring, 2009
Chapter 6: Control Flow
Control flow = sequence of execution of
instructions / data access
• Sequence – use order of appearance or precedence.
• Selection – alternation and short-circuited evaluation
• Iteration – Repetition determined at compile time
(loop control constants) or run time (variables).
• Procedural abstraction, a.k.a. functions or methods.
• Recursion – tail calls, direct & indirect recursion.
• Concurrency – multithreading and distributed
procedures.
• Nondeterminacy – partially ordered sequences.
Operator precedence and associativity
• Precedence and associativity in algebraic expressions
determines order of evaluation, and therefore
instruction sequence.
•
•
•
•
•
•
>>> 3 + 4 ** 2 * 5
83
>>> (3 + 4) ** (2 * 5)
282475249
>>> (3 + 4) ** 2 * 5
245
• Parent-child node relationships in a syntax tree can
reflect precedence and associativity.
Assignments, Values and References
• An l-value corresponds to a symbol appearing in the
left-hand-side of an assignment. An l-value is a
reference for the target of the assignment.
• An r-value corresponds to a symbol appearing in the
right-hand-side of an assignment or expression. An rvalue is a value of the symbol binding.
• Syntax for the two may be identical or different.
• d=a;
• a=b+c
Value versus reference model.
• In a value model language, every data object is a value. Value
semantics typically apply to primitive data types, e.g., ints and
floats in C/C++ and Java.
• A reference model implicitly treats every variable binding as a
pointer. Java uses a reference model for class objects. Python
uses a reference model for all data objects.
• Because C/C++ uses a value model, pointers are treated as
explicit pointer values. The distinction between an object and
a pointer to an object leads to added syntax and programming
complexity, the benefit being efficiency in avoiding
unnecessary pointer dereferencing and heap-based object
allocation and recovery.
• C++ has also added reference variables and parameters to the
value model of C.
Boxing
• Compiler automatically places a primitive
datum into an object when needed.
• Old Java.
• void f(char key, int value, java.util.Map map)
– map.put(new Character(char), new Integer(value))
• Newer Java.
• void f(char key, int value, java.util.Map map)
– map.put(char, value)
Short circuited and lazy evaluation
• condition1 or condition2 or condition3
• Stop evaluation on the first true result.
• Python equates 0 with False, non-0 with True.
– >>> 0 or 0 or 7 or 5
–7
• condition1 and condition2 and condition3
• Stop evaluation on the first false result.
–
–
–
–
>>> 1 and 5 and 7 and 9
9
>>> 1 and 5 and 0 and 9
0
Short circuiting for safety
• Short circuiting supports writing safe conditional
tests.
•
•
•
•
•
•
•
•
•
•
>>> mylist = [1, 2, 3, 4, 5]
>>> i = 17
>>> if (i < len(mylist) and mylist[i] <= 3):
... print mylist[i]
...
>>> i = 2
>>> if (i < len(mylist) and mylist[i] <= 3):
... print mylist[i]
...
3
Alternation (selection) is short
circuited in programming languages.
• In an if-else construct, code in the branch not taken is never evaluated.
• The code in the branch not taken can include value errors (divide by 0,
invalid array indices, etc.), and in Python, invalid types.
–
–
–
–
–
–
–
–
–
–
–
–
–
–
>>> i = 3
>>> if (type(i) == int):
... print i + 7
... else:
... print str(i) + " stringy"
...
10
>>> i = 'a string'
>>> if (type(i) == int):
... print i + 7
... else:
... print str(i) + " stringy"
...
a string stringy
• Boolean expression short circuiting is a similar case.
• Switch / case statements select 1 alternative from many, compile into
jump tables for contiguous cases.
Normal order (lazy) evaluation
generalizes this approach.
• Evaluate expressions only if / when you need them,
and in a functional language, evaluate them only
once. Applicative evaluation evaluates expressions
and parameters immediately.
•
•
•
•
•
•
•
•
•
fun returndiv(quotient, divisor)
= if divisor <> 0 then quotient else ~1000 ;
(* Like a C conditional statement. *)
returndiv(8 div 2, 2);
returndiv(8 div 0, 0); // applicative evaluation in ML
-bash-3.00$ sml mldemo.sml
val it = 4 : int
uncaught exception Div [divide by zero]
raised at: mldemo.sml:113.13-113.16
Normal-order evaluation in Haskell
• returndiv quotient divisor
•
= if (divisor /= 0) then quotient else -1000
• -- returndiv (div 8 2) 2
• -- returndiv (div 8 0) 0
• Main> returndiv (div 8 2) 2
• 4
• Main> returndiv (div 8 0) 0
• -1000
Normal order is a generalization of the short-circuited boolean
tests and alternation constructs in other languages.
Iteration
• While and for loops test at the top.
• For loops build loop control variables into the syntax.
• >>> for x in range(1,5): sys.stdout.write(str(x) + " ")
• ...
• 1 2 3 4 >>>
• Until loops run the loop once and test at the bottom.
• Selection and iteration compile to jumps and
conditional jumps in machine code.
Recursion
• Direct recursion -- a function invokes itself.
• Indirect recursion – a function invokes another function that, directly or
indirectly, invokes the first function.
• Tail recursion – a direct recursive call that returns immediately.
• The compiler can compile tail calls to jumps back to the start of the
function after re-binding the parameters.
• Optimizing tail calls is important in functional languages that discourage
or disallow iteration and re-assignment of variable- value bindings.
•
•
•
•
•
•
•
•
•
>>> def sum(l, cursum=0):
... if (len(l)):
...
tmpsum = cursum + l[0]
...
return sum(l[1:], tmpsum)
... else:
...
return cursum
...
>>> sum([1, 2, 3, 4, 5])
15
Continuations support coroutines –
multiple activation stacks
•
(define buffer '()) ;the shared resource
•
•
•
•
•
•
•
•
(define producer
(lambda (consumer-continuation count)
(set! buffer (list "tuna sandwich #" count))
(display "producer making ")
(display buffer)
(newline)
(sleep 1) ;slowing things down a bit
(producer (call/cc consumer-continuation) (+
count 1))))
•
•
•
•
•
•
•
•
(define consumer
(lambda (producer-continuation)
(display "consumer eating ")
(display buffer)
(newline)
(set! buffer '()) ;accessing the shared resource
(sleep 1) ;slowing things down a bit
(consumer (call/cc producer-continuation))))
•
;(trace producer consumer)
•
(producer consumer 0) ;getting the ball rolling
•
•
•
•
•
•
producer making (tuna sandwich # 0)
consumer eating (tuna sandwich # 0)
producer making (tuna sandwich # 1)
consumer eating (tuna sandwich # 1)
producer making (tuna sandwich # 2)
consumer eating (tuna sandwich # 2)
•
Code by Liz Kalter, CSC 580