I. Computation models (Preface) A. How to study programming languages? How many languages are there? How would we pick what to study? B. What is a paradigm or programming model? ------------------------------------------ PARAGIDM OR PROGRAMMING MODEL def: a *paradigm* or *programming model* 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 competition models different? How are programming languages different from programming models? 2. tradtional 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 languges 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 ||||| |||||____________________________||||| |||| |||| |||| Declarative concurrent |||| |||| procedures, if, case, |||| |||| 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. goal II. Introduction to Programming Concepts (Chapter 1) ------------------------------------------ QUIZ FOR CHAPTER 1 [system] What are the important points for working with the Mozart/Oz system? [variable] What does a "variable" mean in Oz? [function defs, recursion] The Fibonacci function is defined by Fib(0) = 1 Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2), if n >= 2 Write this in Oz. [correctness] Prove that your Fib function is correct. [Lazy evaluation] Make Fib run in time O(n). [lists, pattern matching] Write a function Assoc that takes a list of key-value pairs and a key K, and returns the element in the list associated with K, if any. [higher-order functions] Write a function Map that takes a function F and a list Lst and returns the list of the results of applying F to each element of Lst, in order. [threads] How are threads created? Give an example. [Dataflow] What is a dataflow variable and how is it used? Give an example. [Cells] How are memory cells created and used? Give an example. [Objects] How are objects related to functions? [Classes] Write a class for 2-dimensional points. [Nondeterminism and time] Give an example of a race condition. Does this example need to use cells? [Atomicity] How are locks used to avoid the problems with concurrency and state? Give an example. ------------------------------------------ III. Introduction to Programming Concepts (Chapter 1) A. Working with Mozart/Oz (1.1, Appendix A) 1. Browse 2. declare a. variables b. functions ------------------------------------------ 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) ------------------------------------------ ATOMIC DATA Numbers: ~5 is minus 5 Character Literals &c is the literal for 'c' == 99 &\n is newline &\012 is also a newline Atoms (like Lisp symbols) an_atom anotherOne ':=' ------------------------------------------ ------------------------------------------ STRUCTURED DATA Records tree(key:I value:Y left:LT right:RT) labeled "tree" with 4 features, whose values are the values of the variables I, Y, LT, and RT Tuples pair(3 4) '#'(a b c) a#b#c Lists nil a|b|nil == '|'(a '|'(b nil)) == [a b] Strings "strings are lists of characters" ------------------------------------------ Does order matter in records? In tuples? How would you define a list recursively? C. Pattern Matching ------------------------------------------ PATTERN MATCHING Syntax: case of then else end Example: Write ListLength, so that {ListLength nil} = 0 {ListLength [a b c d]} = 4 ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write a function Assoc that takes a list of key-value pairs and a key K, and returns the element in the list associated with K, if any. Examples {Assoc [c#3] c} = 3 {Assoc [a#1 b#2 c#3] b} = 2 {Assoc [] z} = nil {Assoc [a#1 b#2 c#3] z} = nil ------------------------------------------ What is the induction over? What's a related simplier example to the second one? D. Higher Order Functions ------------------------------------------ HIGHER-ORDER FUNCTIONS Take functions as arguments, or return them. declare Add1 Add2 fun {Add1 X} X+1 end fun {Add2 X} X+2 end declare CAdd fun {CAdd N} fun {$ M} N+M end end {Browse {{CAdd 3} 4}} ------------------------------------------ ------------------------------------------ FOR YOU TO DO Define the function Compose, such that: {{Compose Add1 Add2} 10} = 13 {{Compose {CAdd 100} Add2} 10} = 112 ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write a function Map that takes a function F and a list Lst and returns the list of the results of applying F to each element of Lst, in order. {Map Add2 nil} = nil {Map Add1 [1 2 3]} = [2 3 4] ------------------------------------------ E. threads and dataflow execution 1. threads (1.10) ------------------------------------------ THREADS (1.10) Models concurrency in "real world" % thread 1 thread P in P = {Pascal 30} {Browse P} end % thread 2 {Browse 99*99} ------------------------------------------ 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 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 ------------------------------------------ Is the state necessarily encapsulated? 2. Classes (1.14) ------------------------------------------ CLASSES Classes are factories that make objects declare fun {NewToggle} V Flip Value in ------------------------------------------ ------------------------------------------ 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 C = {NewCell 0} thread C := 1 end thread C := 2 end What happens? ------------------------------------------ 2. Atomicity (1.16) How can we prevent these problems?