I. Relational Programming (Ch 9) A. Motivation ------------------------------------------ MOTIVATIONS FOR RELATIONAL PROGRAMMING ------------------------------------------ 1. programming is difficult, expensive Why is programming so hard? What approaches might solve this problem? What are the steps in building a computer system to do some job? Can we separate them? Which could we automate? 2. rapid prototyping How do we know if we're building the right system? What would help us do that better? What are the costs we care about in rapid prototyping? B. Goals So what should our goals for declarative programming be, to solve the problems that motivate the paradigm? ------------------------------------------ GOALS OF RELATIONAL PROGRAMMING ------------------------------------------ C. relational (logic) programming 1. idea ------------------------------------------ RELATIONAL PROGRAMMING (CH. 9) idea: procedures are relations - zero results, one result, or more - arguments can be both inputs and outputs varies with different calls Example (from section 9.3.3) \insert 'SolveFirst.oz' \insert 'SolveAll.oz' declare proc {RAppend ?A ?B ?C} choice A=nil B=C [] local As Cs X in A=X|As C=X|Cs {RAppend As B Cs} end end end % Forward use {Browse {SolveFirst proc {$ S} Z=S in {RAppend [3 4] [5 6] Z} end}} % Backward use {Browse {SolveFirst proc {$ S} X=S in {RAppend X [2 3] [1 2 3]} end}} {Browse {SolveFirst proc {$ S} Y=S in {RAppend [3 4] Y [3 4 5 6]} end}} % Determine combinations of arguments {Browse {SolveAll proc {$ S} X#Y=S in {RAppend X Y [1 2 3]} end}} {Browse {SolveFirst proc {$ S} Y#Z=S in {RAppend [1 2] Y Z} end}} {Browse {List.take {Solve proc {$ S} X#Z=S in {RAppend X [3 4] Z} end} 3}} % Check if all arguments fit together {Browse {SolveFirst proc {$ S} {RAppend [1 2] [3 4] [1 2 3 4]} S=unit end}} ------------------------------------------ So what's a "result" of a procedure? 2. uses ------------------------------------------ WHEN TO USE RELATIONAL PROGRAMMING - For specifications - as an exploratory tool - when the search space is small ------------------------------------------ Why is this good for specifications? Why is this good for exploratory programming? Why is this good when the search space is small? II. The relational computation model (9.1) A. syntax ------------------------------------------ SYNTAX ::= ... | choice [] ... [] end | fail | {Solve } Expression sugars R = choice E1 [] ... [] En end ==> choice R=E1 [] ... [] R=En end L = {Solve E} ==> {Solve E L} ------------------------------------------ Can "fail" be used as an expression? Would you use a choice expression or statement in a fun? B. semantics 1. semantics by example ------------------------------------------ SEMANTICS BY EXAMPLE \insert 'SolveFirst.oz' declare proc {Vowel ?R} choice R=a [] R=e [] R=i [] R=o [] R=u end end % Solve returns a lazy List L = {Solve Vowel} {Browse L} {Delay 5000} _={List.take L 2} % A choice suspends if used directly % {Browse {Vowel $}} % But can be used in a search with Solve {Browse {List.take {Solve Vowel} 4}} % fail continues with next alternative of most recent choice declare proc {Distinct ?Res} V1 V2 in {Vowel V1} {Vowel V2} if V1 == V2 then fail end Res=V1#V2 end {Browse {List.take {Solve Distinct} 7}} {Browse {List.take {Solve proc {$ ?Z} {Distinct Z} end} 15}} {Browse {List.take {Solve Distinct} 21}} ------------------------------------------ In what order are choices used? Does a fail statement have to occur nested within the execution of a choice statement? What happens when there are no more choices and a fail occurs? ------------------------------------------ FAILURE BY UNIFICATION FAILURE % Unification failures are also failures declare V3=3 {Browse V3} fun {Example} choice V3=3 a [] V3=0 b [] fail c end end {Browse example#{List.take {Solve Example} 3}} ------------------------------------------ Is there a difference between unification failure and fail? Do we need fail as a primitive then? ------------------------------------------ % Unification failures are also failures declare V3=3 {Browse V3} proc {Example ?R} choice V3=3 R=a [] V3=0 R=b [] fail R=c end end {Browse example#{List.take {Solve Example} 3}} % Solve encapsulates search. % Can only read variables declared before solving declare V4 {Browse V4} fun {Example2 ?R} choice V4=1 R=a [] V4=2 R=b [] V4=3 R=c end end {Browse example2#{List.take {Solve Example2} 3}} % suspends % feeding this makes it go... % V4=2 ------------------------------------------ 2. Search tree (9.1.2) ------------------------------------------ SEARCH TREE (9.1.2) ------------------------------------------ What happens to variable bindings after a failure? ------------------------------------------ FOR YOU TO DO Given proc {Vowel ?R} choice R=a [] R=e [] R=i [] R=o [] R=u end end Draw a search tree for the query: {Solve proc {$ ?V} V={Vowel} V=i end} ------------------------------------------ 3. summary ------------------------------------------ SEMANTICS SUMMARY choice S1 [] ... [] Sn end - pushes a new choice point choice point = case choosing between S1 ... Sn in a suspended thread + CCC (choice case counter) The CCC is 1 initially (will do S1) - when demanded if CCC <= n then make a new compuation space execute CCC'th statement in new space advance CCC by 1 else pop stack of choice points demand the choice point at the top fail - demand execution of top of choice point stack {Solve F} - A lazy list is produced by: - Call F to set up a choice point (suspends) - When the first element is needed: - demand execution of top of choice point stack - unify the result with the first element of the result list - Repeat for other elements when needed ------------------------------------------ C. Encapsulated search ------------------------------------------ ENCAPSULATED SEARCH (9.1.3) Solve encapsulates a search - runs in own computation space - treats existing variables as read-only except for result of the function argument - new bindings created for each path in the tree - keeps track of its own choice point stack This is: modular: concurrent threads can search without affecting each other compositional: Solve can be used inside Solve ------------------------------------------ III. examples of relational programming (9.2) A. List examples 1. AddToEnd ------------------------------------------ LIST EXAMPLES {AddToEnd L X R} % R is the list with % the elements of L followed by X Examples: {AddToEnd nil 5 5|nil} {AddToEnd 6|nil 5 6|5|nil} {AddToEnd 2|9|6|nil 5 2|9|6|5|nil} ------------------------------------------ What are some facts about the relation between inputs and outputs? What's true about the base case? What's a recursive case? A related simpler case? How are they related? 2. Reverse ------------------------------------------ FOR YOU TO DO {Reverse L1 L2} % L2 is the reverse of L1 Examples: {Reverse nil nil} {Reverse [1 2 3 4] [4 3 2 1]} ------------------------------------------ What are some facts about the relation between inputs and outputs? What's true about the base case? What's a recursive case? A related simpler case? How are they related? How do these differ from procedures in the declarative model? 3. More examples B. Unary number examples ------------------------------------------ NATURAL NUMBERS (UNARY) ::= z "zero" | s() "successor" Code the following as relations: Count Examples: {List.take {Solve Count} 3} == [z s(z) s(s(z))] LT (less than) Examples: {LT z s(z)} {LT z s(s(s(z)))} {LT s(s(z)) s(s(s(z)))} LE (less than or equal to) GT (greater than) GE (greater than or equal to) Plus Diff (subtraction) Times ToInt ToNat ------------------------------------------ C. Generate and Test ------------------------------------------ GENERATE AND TEST Architecture: 1. generate all possibilities 2. test to find correct answers Example: declare proc {GenFromTo I N ?R} (I =< N) = true % i.e., fail if I > N choice R=I [] {GenFromTo I+1 N R} end end proc {AtLeast50 ?Sol} {GenFromTo 0 60 Sol} % Generate (Sol >= 50) = true % Test end {Test {List.take {Solve proc {$ Z} {GenFromTo 1 5 Z} end} 5} '==' [1 2 3 4 5]} {Test {SolveAll AtLeast50} '==' [50 51 52 53 54 55 56 57 58 59 60]} ------------------------------------------ ------------------------------------------ VIDEO TIMES EXAMPLE Example: - A VCR has SP and EP speeds, with SP 3 times faster than EP. - A tape is 2*60 min at SP speed, and 6*60 min at EP speed. - SP is better quality - How to tape a N minute show to use the most SP speed? Generate: tuples of form time(ep: MinutesEP sp: MinutesSP) where 3*MinutesSP + MinutesEP = 6*60 Test: find which ones have length N min total ------------------------------------------ IV. Relation to logic programming (9.3) A. What is logic programming ------------------------------------------ SPECIFICATION OF SORTED Specification: OutList = {Sorted InList} if {Permutation InList OutList} and {Ordered OutList} corresponds to formula: exists OutList . OutList = {Sorted InList} How could you prove this? ------------------------------------------ How could you prove this? ------------------------------------------ ABSTRACTING FROM THE EXAMPLE So programs are modeled as Specification: a problem to be solved is Answer to a problem: ------------------------------------------ B. Constructive logic (cf. 9.3.1) ------------------------------------------ CONSTRUCTIVE LOGIC def: constructive logic is a variant of logic which requires evidence Example: Theorem/Query: exists Out . {Sorted [3 1 2] Out} Constructive proof: Out = [1 2 3] Theorem/Query: exists I . {Prime I} % and (I>6) = true Constructive proof: I = 7 ------------------------------------------ Does constructive logic allow "proof by contradiction"? C. Operational and logical semantics (9.3.2) ------------------------------------------ CORRESPONDENCE (T) BETWEEN STATEMENTS IN OZ LOGICAL FORMULA (Operational Semantics) (Logical Semantics) ================================================== T(skip) = true T(fail) = false T(S1 S2) = T(choice S1 = [] ... [] Sn end) T(local X in S end) = exists X . T(S) T(X=Y) = X=Y T(X=f(l1:X1 ... ln:Xn)) = X=f(l1:X1, ... ln:Xn) T(if X then S1 else S2) = (X=true /\ T(S1)) \/ (X=false /\ T(S2)) T(case X of = (exists X1, ..., Xn . f(l1:X1 ... ln:Xn) X=f(l1:X1, ... ln:Xn) then S1 /\ T(S1)) else S2) \/ (not(exists X1, ..., Xn . f(l1:X1 ... ln:Xn) X=f(l1:X1, ... ln:Xn)) /\ T(S2)) T(P = proc {$ X1 ... Xn} = all X1, ..., Xn . S p(X1, ..., Xn) <== T(S) end) {P Y1 ... Yn} = p(Y1, ..., Yn) ------------------------------------------ Given these translations, what's another way to write if Z then A=nil else A=3|nil end in Oz (to produce the same logic)? What's translation of (X > Y)=true ? So if we want to prove that a relation p(Y1, ..., Yn) holds, what do we do (operationally)? 1. Practice with the translation ------------------------------------------ FOR YOU TO DO What's the logical semantics of: % (d) case Ls of nil then skip [] _|nil then skip [] X|Y|Zs then (X =< Y)=true {Ordered Y|Zs} end % (nd) choice Ls=nil [] Ls=_|nil [] local X Y Zs in X|Y|Zs=Ls (X =< Y)=true {Ordered Y|Zs} end end ------------------------------------------ What's the operational difference between these? 2. Using the translation to do programming a. axioms (database facts) ------------------------------------------ GROUND DATABASES AND GROUND QUERIES (WITH FACTS WITHOUT VARIABLES) declare % a database of capitals proc {Capitals ?State ?City} choice State=florida City=tallahassee [] State=iowa City=desMoines [] State=kansas City=topeka [] State=virginia City=richmond [] State=michigan City=lansing [] State=newYork City=albany [] State=california City=sacremento end end \insert 'SolveOne.oz' fun {QueryCapitals State City} Ans = {SolveOne proc {$ Ok} {Capitals State City} Ok=yes end} in if Ans \= nil then yes else no end end {Test {QueryCapitals florida tallahassee} '==' yes} {Test {QueryCapitals newYork albany} '==' yes} logical rule: axiom (or fact) _______ p(a,b) ------------------------------------------ What does QueryCapitals do? What does the identity rule mean? What's the operational semantics of such a query? b. closed world assumption (finite failures) ------------------------------------------ CLOSED WORLD ASSUMPTION {Test {QueryCapitals georgia atlanta} '==' no} ------------------------------------------ Is atlanta the capital of Georgia? Why doesn't the program agree? c. generalization (existential queries) ------------------------------------------ ANSWERING QUERIES WITH UNBOUND VARIABLES (ON GROUND DATABASES) % What is the capital of iowa? {Test {SolveFirst proc {$ What} {Capitals iowa What} end} '==' desMoines} Logical translation of query: logical rule: generalization _____________________________ exists X1...Xn . p(X1,...,Xn) ------------------------------------------ d. conjunction ------------------------------------------ CONJUNCTIVE QUERIES declare proc {Agriculture ?State ?Product} choice State=florida Product=oranges [] State=iowa Product=pork [] State=kansas Product=sunflowers [] State=virginia Product=ham [] State=michigan Product=cherries [] State=newYork Product=dairy [] State=california Product=wine end end \insert 'Capitals.oz' % What is the capital and chief agricultural product of florida? {Test {SolveFirst proc {$ Ans} Town#Farmed = Ans in {Capitals florida Town} %% and {Agriculture florida Farmed} end} '==' tallahassee#oranges} % What is the capital and chief agricultural product of iowa? {Test {SolveFirst proc {$ Ans} Town#Farmed=Ans in {Capitals iowa Town} {Agriculture iowa Farmed} end} '==' desMoines#pork} Logical translation of (2nd) query: exists Town, Farmed . capitals(iowa, Town) /\ agriculture(iowa, Farmed) logical rule: conjunction exists X1,...,Xn . s[[p1(X1,...,Xn)]], exists X1,...,Xn . s[[p2(X1,...,Xn)]] _____________________________________ exists X1,...,Xn . p1(X1,...,Xn) /\ p2(X1,...,Xn) where s is a substitution, and Xi in dom(s), and ------------------------------------------ What syntax is used to represent conjunction? What's the operational semantics? How would you ask what state has capital sacremento and produces wine? e. universal modus ponens (rules) ------------------------------------------ AN EXAMPLE TO BUILD RULES ON % file 'FamilyExample.oz' declare proc {Dad ?Father ?Kid} choice Father=pop Kid=sarah [] Father=pop Kid=john [] Father=pop Kid=robert [] Father=pop Kid=jill end end proc {Mom ?Mother ?Kid} {Dad _ Kid} Mother=mom end proc {Male ?Person} choice Person=pop [] Person=robert [] Person=john end end proc {Female ?Person} choice Person=mom [] Person=sarah [] Person=jill end end ------------------------------------------ ------------------------------------------ LOGICAL MEANING OF RULES \insert 'FamilyExample.oz' declare proc {Son ?X ?Y} {Parent Y X} {Male X} end proc {Daughter ?X ?Y} {Parent Y X} {Female X} end proc {Parent ?Y ?X} choice {Dad Y X} [] {Mom Y X} end end Logical translation of rules: all X, Y . son(X, Y) <== parent(Y, X) /\ male(X) all X, Y . daughter(X, Y) <== parent(Y, X) /\ female(X) all X, Y . parent(Y, X) <== dad(Y, X) \/ mom(Y, X) ------------------------------------------ ------------------------------------------ ANSWERING QUERIES USING RULES \insert 'FamilyRules.oz' \insert 'SolveAll.oz' % What children are sons of what adults? {Test {SolveAll proc {$ Ans} Child#Adult=Ans in {Son Child Adult} end} '==' [john#pop robert#pop john#mom robert#mom]} logical rule: universal modus ponens: where (all Y1,...,Yn . p(Y1,...,Yn) <== S) is a rule, s is a substitution, exists X1,...,Xn . S' p(X1,...,Xn) = s[[p(Y1,...,Yn)]], ________________________________ S' = s[[S]] exists X1,...,Xn . p(X1,...,Xn) ------------------------------------------ Why does that make sense? What does it mean computationally? f. exercise ------------------------------------------ FOR YOU TO DO Write Oz rules that encode your class schedule. Write a query to ask if you are in class Monday at 11:45. Write a query to find all the classes you are taking. ------------------------------------------ D. Logic programming in other models Can we do logic programming in the declarative model? What happens if we add concurrency to the relational model? Can we use logic programming ideas in the stateful models? V. Natural Language Parsing and Grammars (9.4 and 9.5) A. flexible parsing of ambiguous grammars 1. encoding of grammars as relations ------------------------------------------ PARSING PROTOCOL For each nonterminal NT: write a procedure {NT Input ?Unparsed} that takes input list and bind unparsed part Example: ::= lives becomes proc {IntransVerb Input ?Unparsed} Input=lives|Unparsed end Parsing the whole thing: {SolveAll proc {$ Rest} {Sentence [mary lives] Rest} Rest=nil end ------------------------------------------ How would you write a parser for ::= ? ------------------------------------------ PARSING CHOICES ::= man | woman becomes proc {Noun Input ?Unparsed} choice Input=man|Unparsed [] Input=woman|Unparsed end end ------------------------------------------ How would you write a parser for ::= | ? 2. creating parse trees ------------------------------------------ MAKING PARSE TREES Besides checking for validity, return parse tree (data structure). Parsers for nonterminals are now functions that - takes subtrees (or placeholders) - takes input list - bind unparsed part - returns new parse tree ------------------------------------------ ------------------------------------------ EXAMPLE WITH PARSE TREES % An grammar for simple expressions. % The parsers return parse trees. Compare figures 9.5 and 9.6 of CTM. % ::= % | % | 'if' 'then' 'else' % | 'if' 'then' % ::= '+' | '*' | '-' | '>' % ::= | declare fun {Expression I ?U} choice {BasicExp I U} [] local R1 R2 LeftTree OpTree RightTree in LeftTree={BasicExp I R1} OpTree={Operator LeftTree RightTree R1 R2} RightTree={Expression R2 U} OpTree end [] local K1 K2 K3 R1 R2 TestTree ThenTree ElseTree in {Check 'if' I K1} TestTree={Expression K1 R1} {Check 'then' R1 K2} ThenTree={Expression K2 R2} {Check 'else' R2 K3} ElseTree={Expression K3 U} ifExp(TestTree ThenTree ElseTree) end [] local K1 K2 R TestTree ThenTree in {Check 'if' I K1} TestTree={Expression K1 R} {Check 'then' R K2} ThenTree={Expression K2 U} ifExp(TestTree ThenTree numExp(0)) end end end fun {Operator LeftTree RightTree I ?U} choice {Check '+' I U} plusExp(LeftTree RightTree) [] {Check '*' I U} timesExp(LeftTree RightTree) [] {Check '-' I U} subExp(LeftTree RightTree) [] {Check '>' I U} gtExp(LeftTree RightTree) end end fun {BasicExp I ?U} What in I=What|U choice {IsAtom What}=true idExp(What) [] {IsNumber What}=true numExp(What) end end % A helping procedure to check for reserved words proc {Check KW I ?U} I=KW|U end ------------------------------------------ ------------------------------------------ SOME TESTS SHOWING AMBIGUITY \insert 'ExpressionParser.oz' \insert 'SolveAll.oz' \insert 'TestingNoStop.oz' % A helper function for tests fun {Parses LoA} {SolveAll proc {$ PTree} PTree={Expression LoA nil} end} end {Test {Parses [3]} '==' [numExp(3)]} {Test {Parses [foo]} '==' [idExp(foo)]} {Test {Parses [foo '+' 3]} '==' [plusExp(idExp(foo) numExp(3))]} {Test {Parses [7 '*' foo '+' 3]} '==' [timesExp(numExp(7) plusExp(idExp(foo) numExp(3)))]} {Test {Parses ['if' 6 '>' 7 '*' foo 'then' 3 'else' bar]} '==' [ifExp(gtExp(numExp(6) timesExp(numExp(7) idExp(foo))) numExp(3) idExp(bar))]} {Test {Parses ['if' baz 'then' 4 'else' bar]} '==' [ifExp(idExp(baz) numExp(4) idExp(bar))]} % The classic dangling-else ambiguity {Test {Parses ['if' 6 '>' 7 '*' foo 'then' 'if' baz 'then' 4 'else' bar]} '==' [ifExp(gtExp(numExp(6) timesExp(numExp(7) idExp(foo))) ifExp(idExp(baz) numExp(4) numExp(0)) idExp(bar)) ifExp(gtExp(numExp(6) timesExp(numExp(7) idExp(foo))) ifExp(idExp(baz) numExp(4) idExp(bar)) numExp(0))]} ------------------------------------------ B. grammar interpreter (9.5) Can we make a generic parser that takes the grammar as data? VI. databases (9.6) ------------------------------------------ DATABASES (9.6) Relational Database = set of relations Relation = set of tuples The Relational DB ADT Rel = {New RelationClass init} {Rel assertall(Ts)} -- puts all tuples in Ts in the DB {Rel assert(T)} -- puts the tuple T in the DB {Rel query(X)} -- looks up X (unifies with DB) Advantages of using logic programs for queries: - queries can use logical operations - rules can deduce consequences of data ------------------------------------------ How would you implement the Relation ADT? What if the database was in XML format? A. example ------------------------------------------ EXAMPLE \insert 'RelationClass.oz' declare ClassRel = {New RelationClass init} {ClassRel assertall([name(cop3223 'C prog') name(cot3100 'intro to discrete') name(cop3502 'CS I') name(cop3330 'OOP and UML') name(cda3103 'comp. org.') name(cot3960 'foundation exam') name(cop3503 'CS II') name(cop3402 'systems software') name(cop4020 'prog lang I')])} Prereqs = {New RelationClass init} {Prereqs assertall([prereq(cop3502 cop3223) prereq(cop3330 cop3223) prereq(cda3103 cop3223) prereq(cop3960 cop3502) prereq(cop3960 cot3100) prereq(cop3503 cop3502) prereq(cop3503 cop3330) prereq(cop3503 cot3100) prereq(cop3402 cop3502) prereq(cop4020 cot3960) prereq(cop4020 cot3503)])} % What are the prerequisites of cop4020? {Test {SolveAll proc {$ ?Pre} {PrereQ cop4020 Pre} end} '==' [cot3960 cot3503]} FOR YOU TO DO % What are the names of the classes that precede 'prog lang I'? ------------------------------------------ How would you ask: What classes have the most prerequisites? How would you ask: What are all the classes you take before cop4020? B. implementation ------------------------------------------ %% Figure 9.11 in CTM declare % A choice between all elements in a list (the second argument) proc {Choose ?X Ys} choice Ys=X|_ [] Yr in Ys=_|Yr {Choose X Yr} end end class RelationClass attr d meth init d:={NewDictionary} end meth assertall(Is) for I in Is do {self assert(I)} end end meth assert(I) if {IsDet I.1} then Is={Dictionary.condGet @d I.1 nil} in {Dictionary.put @d I.1 {Append Is [I]}} else raise databaseError(nonground(I)) end end end meth query(I) if {IsDet I} andthen {IsDet I.1} then {Choose I {Dictionary.condGet @d I.1 nil}} else {Choose I {Flatten {Dictionary.items @d}}} end end end ------------------------------------------ Why is IsDet being called? VII. summary When is the relational model most useful? What are some typical problems the relational model is good for? What kind of modularity properties does the relational model have? Is the relational model declarative? Referentially transparent? Can we mix the relational model with state?