1、S. Haridi and P. Van Roy,1,Introduction to Programming,Seif Haridi KTHPeter Van Roy UCL,S. Haridi and P. Van Roy,2,Introduction,An introduction to programming concepts Simple calculator Declarative variables Functions Structured data (example: lists) Functions over lists Correctness and complexity L
2、azy functions Concurrency and dataflow State, objects, and classes Nondeterminism and atomicity,S. Haridi and P. Van Roy,3,A calculator,Use the system as a calculator Oz Browse 9999*9999,S. Haridi and P. Van Roy,4,Variables,Variables are short-cuts for values, they cannot be assigned more than onced
3、eclareV = 9999*9999Browse V*VVariable identifiers: is what you type Store variable: is part of the memory system The declare statement creates a store variable and assigns its memory address to the identifier V in the environment,S. Haridi and P. Van Roy,5,Functions,Compute the factorial function: S
4、tart with the mathematical definitiondeclarefun Fact Nif N=0 then 1 else N*Fact N-1 endend Fact is declared in the environment Try large factorial Browse Fact 100,S. Haridi and P. Van Roy,6,Composing functions,Combinations of r items taken from n. The number of subsets of size r taken from a set of
5、size n,declarefun Comb N RFact N div (Fact R*Fact N-R)end,Example of functional abstraction,Comb,Fact,Fact,Fact,S. Haridi and P. Van Roy,7,Structured data (lists),Calculate Pascal triangle Write a function that calculates the nth row as one structured value A list is a sequence of elements:1 4 6 4 1
6、 The empty list is written nil Lists are created by means of ”|” (cons)declareH=1T = 2 3 4 5Browse H|T % This will show 1 2 3 4 5,S. Haridi and P. Van Roy,8,Lists (2),Taking lists apart (selecting components) A cons has two components a head, and taildeclare L = 5 6 7 8L.1 gives 5L.2 give 6 7 8,|,|,
7、|,6,7,8,nil,S. Haridi and P. Van Roy,9,Pattern matching,Another way to take a list apart is by use of pattern matching with a case instruction case L of H|T then Browse H Browse T end,S. Haridi and P. Van Roy,10,Functions over lists,Compute the function Pascal N Takes an integer N, and returns the N
8、th row of a Pascal triangle as a list For row 1, the result is 1 For row N, shift to left row N-1 and shift to the right row N-1 Align and add the shifted rows element-wise to get row N,1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,(0),(0),0 1 3 3 11 3 3 1 0,Shift right,Shift left,S. Haridi and P. Van Roy,11,Functi
9、ons over lists (2),declare fun Pascal Nif N=1 then 1elseAddListShiftLeft Pascal N-1ShiftRight Pascal N-1end end,AddList,ShiftLeft,ShiftRight,Pascal N-1,Pascal N-1,Pascal N,S. Haridi and P. Van Roy,12,Functions over lists (3),fun ShiftLeft Lcase L of H|T thenH|ShiftLeft Telse 0end endfun ShiftRight L
10、 0|L end,fun AddList L1 L2case L1 of H1|T1 thencase L2 of H2|T2 thenH1+H2|AddList T1 T2endelse nil end end,S. Haridi and P. Van Roy,13,Top-down program development,Understand how to solve the problem by hand Try to solve the task by decomposing it to simpler tasks Devise the main function (main task
11、) in terms of suitable auxiliary functions (subtasks) that simplifies the solution (ShiftLeft, ShiftRight and AddList) Complete the solution by writing the auxiliary functions,S. Haridi and P. Van Roy,14,Is your program correct?,”A program is correct when it does what we would like it to do” In gene
12、ral we need to reason about the program: Semantics for the language: a precise model of the operations of the programming language Program specification: a definition of the output in terms of the input (usually a mathematical function or relation) Use mathematical techniques to reason about the pro
13、gram, using programming language semantics,S. Haridi and P. Van Roy,15,Mathematical induction,Select one or more input to the function Show the program is correct for the simple cases (base case) Show that if the program is correct for a given case, it is then correct for the next case. For integers
14、 base case is either 0 or 1, and for any integer n the next case is n+1 For lists the base case is nil, or a list with one or few elements, and for any list T the next case H|T,S. Haridi and P. Van Roy,16,Correctness of factorial,fun Fact Nif N=0 then 1 else N*Fact N-1 end endBase Case: Fact 0 retur
15、ns 1 (N1), N*Fact N-1 assume Fact N-1 is correct, from the spec we see the Fact N is N*Fact N-1 More techniques to come !,S. Haridi and P. Van Roy,17,Complexity,Pascal runs very slow, try Pascal 24 Pascal 20 calls: Pascal 19 twice, Pascal 18 four times, Pascal 17 eight times, ., Pascal 1 219 times E
16、xecution time of a program up to a constant factor is called programs time complexity. Time complexity of Pascal N is proportional to 2N (exponential) Programs with exponential time complexity are impractical,declare fun Pascal Nif N=1 then 1elseAddListShiftLeft Pascal N-1ShiftRight Pascal N-1end en
17、d,S. Haridi and P. Van Roy,18,fun FastPascal Nif N=1 then 1elselocal L inL=FastPascal N-1AddList ShiftLeft L ShiftRight Lendend end,Faster Pascal,Introduce a local variable L Compute FastPascal N-1 only once Try with 30 rows. FastPascal is called N times, each time a list on the average of size N/2
18、is processed The time complexity is proportional to N2 (polynomial) Low order polynomial programs are practical.,S. Haridi and P. Van Roy,19,Lazy evaluation,The functions written so far are evaluated eagerly (as soon as they are called) Another way is lazy evaluation where a computation is done only
19、 when the results is needed,declare fun lazy Ints NN|Ints N+1 end,Calculates the infinite list: 0 | 1 | 2 | 3 | .,S. Haridi and P. Van Roy,20,Lazy evaluation (2),Write a function that computes as many rows of Pascals triangle as needed We do not know how many beforehand A function is lazy if it is e
20、valuated only when its result is needed The function PascalList is evaluated when needed,fun lazy PascalList RowRow | PascalList AddList ShiftLeft RowShiftRight Row end,S. Haridi and P. Van Roy,21,Lazy evaluation (3),Lazy evaluation will avoid redoing work if you decide first you need the 10th row a
21、nd later the 11th row The function continues where it left off,declare L = PascalList 1 Browse L Browse L.1 Browse L.2.1,L 1 1 1,S. Haridi and P. Van Roy,22,Higher-order programming,Assume we want to write another Pascal function which instead of adding numbers performs exclusive-or on them It calcu
22、lates for each number whether it is odd or even (parity) Either write a new function each time we need a new operation, or write one generic function that takes an operation (another function) as argument The ability to pass functions as argument, or return a function as result is called higher-orde
23、r programming Higher-order programming is an aid to build generic abstractions,S. Haridi and P. Van Roy,23,Variations of Pascal,Compute the parity Pascal triangle,1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,1,1,1,1,0,1,1,1,1,1,1,0,0,0,1,fun Xor X Y if X=Y then 0 else 1 end end,S. Haridi and P. Van Roy,24,Higher-o
24、rder programming,fun GenericPascal Op Nif N=1 then 1else L in L = GenericPascal Op N-1OpList Op ShiftLeft L ShiftRight Lend end fun OpList Op L1 L2 case L1 of H1|T1 thencase L2 of H2|T2 thenOp H1 H2|OpList Op T1 T2endendelse nil end end,fun Add N1 N2 N1+N2 end fun Xor N1 N2 if N1=N2 then 0 else 1 en
25、d endfun Pascal N GenericPascal Add N end fun ParityPascal N GenericPascal Xor N end,S. Haridi and P. Van Roy,25,Concurrency,How to do several things at once Concurrency: running several activities each running at its own pace A thread is an executing sequential program A program can have multiple t
26、hreads by using the thread instruction Browse 99*99 can immediately respond while Pascal is computing,threadP inP = Pascal 21Browse P end Browse 99*99,S. Haridi and P. Van Roy,26,Dataflow,What happens when multiple threads try to communicate? A simple way is to make communicating threads synchronize
27、 on the availability of data (data-driven execution) If an operation tries to use a variable that is not yet bound it will wait The variable is called a dataflow variable,+,*,*,X,Y,Z,U,S. Haridi and P. Van Roy,27,Dataflow (II),Two important properties of dataflow Calculations work correctly independ
28、ent of how they are partitioned between threads (concurrent activities) Calculations are patient, they do not signal error; they wait for data availability The dataflow property of variables makes sense when programs are composed of multiple threads,declare X threadDelay 5000 X=99 end Browse Start B
29、rowse X*X,declare X threadBrowse Start Browse X*X end Delay 5000 X=99,S. Haridi and P. Van Roy,28,State,How to make a function learn from its past? We would like to add memory to a function to remember past results Adding memory as well as concurrency is an essential aspect of modeling the real worl
30、d Consider FastPascal N: we would like it to remember the previous rows it calculated in order to avoid recalculating them We need a concept (memory cell) to store, change and retrieve a value The simplest concept is a (memory) cell which is a container of a value One can create a cell, assign a val
31、ue to a cell, and access the current value of the cell Cells are not variables,declare C = NewCell 0 Assign C Access C+1 Browse Access C,S. Haridi and P. Van Roy,29,Example,Add memory to Pascal to remember how many times it is called The memory (state) is global here Memory that is local to a functi
32、on is called encapsulated state,declare C = NewCell 0 fun FastPascal NAssign C Access C+1GenericPascal Add N end,S. Haridi and P. Van Roy,30,Objects,Functions with internal memory are called objects The cell is invisible outside of the definition,declare local C inC = NewCell 0fun BumpAssign C Acces
33、s C+1Access Cend end,declare fun FastPascal NBrowse BumpGenericPascal Add N end,S. Haridi and P. Van Roy,31,Classes,A class is a factory of objects where each object has its own internal state Let us create many independent counter objects with the same behavior,fun NewCounterlocal C Bump inC = NewC
34、ell 0fun BumpAssign C Access C+1Access CendBumpend end,S. Haridi and P. Van Roy,32,Classes (2),Here is a class with two operations: Bump and Read,fun NewCounterlocal C Bump inC = NewCell 0fun BumpAssign C Access C+1Access Cendfun ReadAccess CendBump Readend end,S. Haridi and P. Van Roy,33,Object-ori
35、ented programming,In object-oriented programming the idea of objects and classes is pushed farther Classes keep the basic properties of: State encapsulation Object factories Classes are extended with more sophisticated properties: They have multiple operations (called methods) They can be defined by
36、 taking another class and extending it slightly (inheritance),S. Haridi and P. Van Roy,34,Nondeterminism,What happens if a program has both concurrency and state together? This is very tricky The same program can give different results from one execution to the next This variability is called nondet
37、erminism Internal nondeterminism is not a problem if it is not observable from outside,S. Haridi and P. Van Roy,35,Nondeterminism (2),declare C = NewCell 0thread Assign C 1 end thread Assign C 2 end,time,C = NewCell 0 cell C contains 0,Assign C 1 cell C contains 1,Assign C 2 cell C contains 2 (final
38、 value),t0,t1,t2,S. Haridi and P. Van Roy,36,Nondeterminism (3),declare C = NewCell 0thread Assign C 1 end thread Assign C 2 end,time,C = NewCell 0 cell C contains 0,Assign C 2 cell C contains 2,Assign C 1 cell C contains 1 (final value),t0,t1,t2,S. Haridi and P. Van Roy,37,Nondeterminism (4),declar
39、e C = NewCell 0thread I inI = Access CAssign C I+1 end thread J inJ = Access CAssign C J+1 end,What are the possible results? Both threads increment the cell C by 1 Expected final result of C is 2 Is that all?,S. Haridi and P. Van Roy,38,Nondeterminism (5),Another possible final result is the cell C
40、 containing the value 1,declare C = NewCell 0 thread I inI = Access CAssign C I+1 end thread J inJ = Access CAssign C J+1 end,time,C = NewCell 0,I = Access C I equal 0,t0,t1,t2,J = Access C J equal 0,Assign C J+1 C contains 1,Assign C I+1 C contains 1,t3,t4,S. Haridi and P. Van Roy,39,Lessons learne
41、d,Combining concurrency and state is tricky Complex programs have many possible interleavings Programming is a question of mastering the interleavings Famous bugs in the history of computer technology are due to designers overlooking an interleaving (e.g., the Therac-25 radiation therapy machine giv
42、ing doses 1000s of times too high, resulting in death or injury) If possible try to avoid concurrency and state together Encapsulate state and communicate between threads using dataflow Try to master interleavings by using atomic operations,S. Haridi and P. Van Roy,40,Atomicity,How can we master the
43、 interleavings? One idea is to reduce the number of interleavings by programming with coarse-grained atomic operations An operation is atomic if it is performed as a whole or nothing No intermediate (partial) results can be observed by any other concurrent activity In simple cases we can use a lock
44、to ensure atomicity of a sequence of operations For this we need a new entity (a lock),S. Haridi and P. Van Roy,41,Atomicity (2),declare L = NewLocklock L thensequence of ops 1 end,Thread 1,lock L thensequence of ops 2 end,Thread 2,S. Haridi and P. Van Roy,42,The program,declare C = NewCell 0 L = Ne
45、wLockthreadlock L then I inI = Access CAssign C I+1end end thread lock L then J inJ = Access CAssign C J+1end end,The final result of C is always 2,S. Haridi and P. Van Roy,43,Additional exercises,Write the memorizing Pascal function using the store abstraction (available at http:/www.sics.se/seif/D
46、atalogiII/Examples/Store.oz) Reason about the correctness of AddList and ShiftLeft using induction,S. Haridi and P. Van Roy,44,Memoizing FastPascal,FastPascal N New Version Make a store S available to FastPascal Let K be the number of the rows stored in S (i.e. max row is the Kth row) if N is less or equal K retrieve the Nth row from S Otherwise, compute the rows numbered K+1 to N, and store them in S Return the Nth row from S Viewed from outside (as a black box), this version behaves like the earlier one but faster,declare S = NewStore Put S 2 1 1 Browse Get S 2 Browse Size S,
