I. Computation models and Programming Models (Preface) A. Why study computation models and programming models? How would we pick what to study? B. What is a paradigm or programming model? ------------------------------------------ PROGRAMMING MODEL (OR PARAGIDM) def: a *programming model* (or *paradigm*) is ------------------------------------------ How is a paradigm different from a pattern? C. What is a computational model? (Preface) ------------------------------------------ COMPUTATION MODEL def: a *computation model* is ------------------------------------------ 1. parts 2. presentation D. overview 1. differences How are programming and computation models different? How are programming languages different from programming models? 2. traditional view of programming paradigms ------------------------------------------ PROGRAMMING PARADIGMS !--------------------------------------! ! DECLARATIVE ! ! ! ! Logic Constraint ! ! ! ! CL ! ! ! !--------------------------------------! !--------------------------------------! ! ALGORITHMIC ! ! ! ! Imperative Higher-Order ! ! ! ! mostly- ! ! functional ! ! ! ! ! ! ! ! Object-based ! ! Applicative ! ! ! ! Object-oriented ! ! ! ! ! ! Aspect-oriented ! ! ! !--------------------------------------! ------------------------------------------ what problem motivates each style? what languages are examples of each style? Where do languages like Python and Perl fit in? How does concurrency fit in? 3. relationships between computation models (Appendix D) ------------------------------------------ GENERAL COMPUTATION MODEL (APPENDIX D) ______________________________________ |____________________________________| ||__________________________________|| ||| _______________________________||| ||||______________________________|||| |||||Declarative ||||| ||||| sequence, local, ||||| ||||| variable creation/binding||||| ||||| value creation ||||| ||||| procedures, if, case ||||| |||||____________________________||||| |||| |||| |||| Declarative concurrent |||| |||| thread |||| |||| by-need synchronization |||| ||||______________________________|||| ||| ||| ||| Security ||| ||| name creation, ||| ||| read-only views ||| |||________________________________||| || || || Exceptions || || try/catch, raise, || || failed values || ||__________________________________|| | | | Explicit state | | cell creation, cell exchange,| | boundness test | |____________________________________| ------------------------------------------ E. book's goals (skip if already covered) II. Introduction to Programming Concepts (Chapter 1) A. Working with Mozart/Oz (1.1, Appendix A) 1. Show where the documentation is 2. Browse ------------------------------------------ BROWSE AND SHOW {Browse 3} {Show 3} {Browse true} {Browse fiddle} ------------------------------------------ 3. declare a. dataflow variables ------------------------------------------ DATAFLOW VARIABLES declare X X=20 {Browse (X + X)*100+X} declare Y=25 {Show Y} declare Sum = X+Y {Browse Sum} ------------------------------------------ What's the difference between a variable in Oz and one in Java? b. functions ------------------------------------------ FUNCTION DECLARATIONS declare fun {Inc N} N+1 end declare fun {Fact N} if N==0 then 1 else N*{Fact N-1} end end FOR YOU TO DO Code the Fibonacci function defined by: Fib(0) = 1 Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2), if n >= 2 ------------------------------------------ What's the complexity of your solution? B. Data (Appendix B, quickly if did designing a language) ------------------------------------------ ATOMIC DATA (APPENDIX B) Ints 3 ~5 is negative 5 Floats 3.14 7.2e~3 == 0.0072 Character Literals &c is the literal for 'c' == 99 &\n is newline &\012 is also a newline Atoms (like Lisp symbols) an_atom anotherOne ':=' 'if' ------------------------------------------ ------------------------------------------ STRUCTURED DATA (RECORDS) Records tree(key:I value:Y left:LT right:RT) labeled "tree" with 4 features, whose values are the values of the dataflow variables I, Y, LT, RT truck(maker:gm weight:4020 doors:4) person(name:joe weight:179) message(contents: type(3)) signal() atom Special cases: Tuples (numbered features = no names) triple(1:a 2:b 3:c) == triple(a b c) pair(1:a 2:b) == pair(a b) '#'(a b c) == a#b#c Lists (either nil or tuple with label '|' and 2 features) nil '|'(1:a 2:'|'(1:b 2:nil)) == '|'(a '|'(b nil)) == a|b|nil == [a b] picture of the above: .1 .2 .1 .2 -->[ * | * | *-]-->[ * | * | *-]-->(nil) | | | | v v v v (|) (a) (|) (b) Strings (lists of characters) nil == "" '|'(1:&c 2:'|'(1:&h 2:'|'(1:&a 2:'|'(1:&r 2:'|'(1:&s 2:nil))))) == '|'(&c '|'(&h '|'(&a '|'(&r '|'(&s nil)))) == &c|&h|&a|&r|&s|nil == [&c &h &a &r &s] == "chars" "strings are lists of characters" ------------------------------------------ What does the result of {Browse song(artist: beatles name:"all you need is love") == song(name:"all you need is love" artist: beatles) } tell you? Does order matter in records? In tuples? How would you define a list recursively? C. Pattern Matching ------------------------------------------ PATTERN MATCHING Syntax: is a record expression with variable identifiers Variable identifiers in patterns - are declared there - match any data there (wildcards) case of then [] then ... [] then else end Example: Write Assoc that takes a list of #-pairs of keys and values and a key, and returns the associated value for that key, or nil if there is none. {Assoc [c#3] c} = 3 {Assoc [a#1 b#2 c#3] b} = 2 {Assoc nil z} = nil {Assoc [a#1 b#2 c#3] z} = nil ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write ListLength that returns the number of (top level) elements in a list: {ListLength nil} == 0 {ListLength a|(b|(c|(d|nil)))} == 4 {ListLength [s a m e]} == 4 {ListLength [nil [a b] [[c]]]} == 3 ------------------------------------------ What is the induction over? What's a related simpler example to the second one? D. Higher Order Functions ------------------------------------------ HIGHER-ORDER FUNCTIONS Def: a *higher-order function* Example: Write a function Map that takes a list Lst and a function F and returns the list of the results of applying F to each element of Lst, in order. {Map nil Add2} == nil {Map [1 2 3] Add1} == [2 3 4] {Map [[a] [b] [c d]] fun {$ E} [res E] end} == [[res [a]] [res [b]] [res [c d]]] ------------------------------------------ E. threads and dataflow execution 1. threads (1.10) ------------------------------------------ THREADS (1.10) Models concurrency in "real world" declare proc {GeneKelly} thread {Dance} end thread {Sing} end end proc {Dance} {Browse im_dancing} {Delay 3} {Browse im_dancing} end proc {Sing} {Browse and_singing} {Delay 3} {Browse in_the_rain} end {GeneKelly} ------------------------------------------ ------------------------------------------ THREAD SCHEDULING 1. A thread is runnable if it is not finished and not suspended. 2. The scheduler can execute the next primitive statement from any runnable thread. 3. A thread suspends if it tries: to read from an undetermined dataflow variable 4. A suspended thread becomes runnable if the dataflow variable it suspended on becomes determined 5. Threads are treated fairly CONSEQUENCES ------------------------------------------ 2. dataflow execution (1.11) ------------------------------------------ DATAFLOW EXECUTION What should happen if we do: declare A B C C = A+B {Browse C} Waits (suspends) % then later feeding... A=10 B=20 Makes the browser show it ------------------------------------------ ------------------------------------------ DATAFLOW AND THREADS % The following suspends, % if fed all at once declare L1 {Browse {ListLength L1}} L1 = [a b] % But with threads this works... declare L2 thread {Browse {ListLength L2}} end L2 = [a b c d e] % What's going on here? declare L3 thread {Browse {ListLength L3}} end thread L3 = a|b|c|L4 end L4 = d|nil ------------------------------------------ F. Explicit State (1.12) Why have explicit state? How does the book model state? ------------------------------------------ CELLS declare Toggle = {NewCell true} Toggle := {Not @Toggle} {Browse @Toggle} ------------------------------------------ G. Objects and Classes (skip if low on time) 1. Objects (1.13) ------------------------------------------ OBJECTS Object = functions + shared state declare local V in V = {NewCell true} fun {Flip} V := {Not @V} @V end fun {Value} @V end end {Browse {Value}} {Browse {Flip}} {Browse {Value}} ------------------------------------------ Is the state necessarily encapsulated? 2. Classes (1.14) ------------------------------------------ CLASSES Classes are factories that make objects declare fun {NewToggle} V Flip Value in V = {NewCell true} fun {Flip} V := {Not @V} @V end fun {Value} @V end toggle(flip:Flip value:Value) end declare T1 = {NewToggle} T2 = {NewToggle} _ = if {T1.value} then {T2.flip} else {T1.flip} end {Browse {T2.value}} {Browse {T1.value}} ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write a class Point that implements 2D points with operations Move, GetX, GetY. ------------------------------------------ This is object-based programming. What other feature(s) is needed for OOP? H. Concurrency Problems 1. Nondeterminism and time (1.15) What happens if you combine concurrency and state? ------------------------------------------ RACE CONDITIONS declare fun {NewMovingAverage} local Old = {NewCell 0.0} New = {NewCell 0.0} Avg = {NewCell 0.0} proc {Put X} {Delay ({OS.rand} mod 30)} Old := @New New := X Avg := (@Old + @New) / 2.0 end fun {Average} {Delay ({OS.rand} mod 30)} @Avg end in movingAvg(put: Put average: Average) end end MA = {NewMovingAverage} thread {MA.put 10.0} end thread {MA.put 20.0} end {Delay ({OS.rand} mod 5)} {Browse {MA.average}} ------------------------------------------ 2. Atomicity (1.16) How can we prevent these problems? Why is that good? Bad? I. Relational Model (preview of chapter 9) ------------------------------------------ RELATIONAL EXAMPLE declare fun {Keyword} choice "java" [] "modeling" [] "language" [] "verification" [] "environment" [] "tool" [] "system" [] "project" [] "extensible" [] "advanced" end end fun {Acronym N} if N =< 0 then nil else local First={Keyword}.1 Rest={Acronym N-1} in if {Member First Rest} then fail else First|Rest end end end end fun {FourLetter} {Acronym 4} end {Browse starting} {Browse {List.take {Solve Keyword} 5}} {Browse {List.take {Solve FourLetter} 5}} ------------------------------------------