Download Presentation
## CS 60

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Mutual Recursion, Prolog, & Unicalc**CS 60 2014-09-24 Wednesday – Week 3 Lecture 07**Lecture 07 – Learning Goals**• Understand the output provided by prolog’s trace. • Write recursive prolog queries. • Reason about how prolog executes negation. • Describe mutual recursion. • Remember that you should read (multiple times) and take notes on provided code and assignment descriptions.**What sub-queries get executed if I write:**?- happy(lewis)**trace.**Starts tracing Type C or hit return to go step-by-step**trace.**Starts tracing Type C or hit return to go step-by-step notrace. Stops tracing**trace with Variables**notrace. Stops tracing nodebug. Stops debug**File simpsons.pl**/* * the age predicate */ age(helga, 97). age(olf, 99). age(uggette, 93). age(ug, 92). age(matilda, 65). age(homericus, 76). age(skugerina, 101). age(skug, 78). age(esmerelda, 55). age(gemini, 54). age(klotho, 20). age(atropos, 19). age(lachesis, 18). age(marge, 35). age(homer, 38). age(lisa, 8). age(maggie, 1). age(bart, 10). age(gomer, 41). age(john, 62). age(jackie, 59). age(patty, 38). age(selma, 38). age(glum, 27). age(cher, 44). age(millhouse, 8). age(terpsichore, 8). /* * the parent predicate */ parent(olf, skug). parent(helga, skug). parent(skug, esmerelda). parent(skugerina, esmerelda). parent(esmerelda, klotho). parent(gemini, klotho). parent(esmerelda, atropos). parent(gemini, atropos). parent(esmerelda, lachesis). parent(gemini, lachesis). parent(olf, homericus). parent(helga, homericus). parent(ug, matilda). parent(uggette, matilda). parent(homericus, homer). parent(matilda, homer). parent(homericus, gomer). parent(matilda, gomer). parent(homer, bart). parent(marge, bart). parent(homer, lisa). parent(marge, lisa). parent(homer, maggie). parent(marge, maggie). parent(john, marge). parent(jackie, marge). parent(john, selma). parent(jackie, selma). parent(john, patty). parent(jackie, patty). parent(john, glum). parent(jackie, glum). parent(glum, millhouse). parent(cher, millhouse). parent(glum, terpsichore). parent(cher, terpsichore). /* * the male predicate */ male(olf). male(skug). male(homericus). male(ug). male(homer). male(gomer). male(gemini). male(john). male(glum). male(bart). male(millhouse). /* * the female predicate */ female(helga). female(esmerelda). female(skugerina). female(uggette). female(matilda). female(marge). female(jackie). female(selma). female(patty). female(cher). female(lisa). female(maggie). female(klotho). female(atropos). female(lachesis). female(terpsichore).**simpsonSmall.pl**• parent(homer, bart). • parent(homer, lisa). • parent(marge, bart). • parent(marge, lisa). • parent(homer, maggie). • parent(marge, maggie). • age(lisa, 8). • age(maggie, 1). • age(bart, 10). • age(marge, 35). • age(homer, 38). • person(marge). • person(homer). • person(lisa). • person(bart). • person(maggie).**Homework Prep**Write these three predicates in prolog: True if MomOrDad is the parent of Kid child(Kid, MomOrDad) :- True if Mom is the parent of Kid and Mom is female mother(Mom,Kid) :- True if X is the parent of Y or if X is an ancestor of Y’s parent anc(X,Y) :- anc(X,Y) :- X is the sibling of Y if they have the same parent (The point of this one -- We need NOT!!!) sibling(X,Y) :-**Solutions**/* * Here are three rules about families */ Child(Kid, Adult) :- parent(Adult, Kid). mother(Mom, Kid) :- female(Mom), parent(Mom, Kid). anc(Old, Young) :- parent(Old, Young). Anc(Old, Young) :- parent(Middle, Young), anc(Old, Middle).**Negation (Summary)**“Unified” means a variable binding is created X = Y • X = Y succeeds if X can be unified with Y. X \= Y • X \= Y succeeds if X cannot be unified with Y. X == Y • X == Y succeeds if X and Y are identical, i.e., they unify with no variable bindings occurring. X \== Y • X \== Y succeeds if X and Y are not identical. http://www.amzi.com/manuals/amzi/pro/ref_manipulating_terms.htm#EqualityofTerms**Equality and Negation (DEMO)**= succeeds if they CAN be unified \= succeeds if they CANNOT be unified == succeeds if they are ALREADY the same \== succeeds if they are NOT ALREADY the same**Equality and Negation (SOLUTION)**= succeeds if they CAN be unified \= succeeds if they CANNOT be unified == succeeds if they are ALREADY the same \== succeeds if they are NOT ALREADY the same**simpsonSmall.pl**• parent(homer, bart). • parent(homer, lisa). • parent(marge, bart). • parent(marge, lisa). • parent(homer, maggie). • parent(marge, maggie). • age(lisa, 8). • age(maggie, 1). • age(bart, 10). • age(marge, 35). • age(homer, 38). • person(marge). • person(homer). • person(lisa). • person(bart). • person(maggie).**sib Demo (Big idea: Negation)**This says that bart is his own sibling!**If X and Y are unbound, X \= Y is false**sib Demo (Big idea: Negation) Works for specific cases.**sib Demo (Big idea: Negation)**REMEMBER: Put negation as late as possible so that variables already have known values! Why are there all of these duplicates?**setof(format,query,Var).**setof allows you to see only non-duplicates [X, Y] gives the format we want our answer in (as a list)**Write query to return the setof marge’s children**• setof is the only time I’ll nest anything in Prolog • I’ll do what I want! Humph!**Don’t worry about this!**Focus on the right hand side of the test!!!**notAparent Demo (Intro: \+ )**\+ means not Singleton variables: [Y]. _ is a variable that doesn’t need to match anything else. I don’t care As is: Doesn’t work with variables!**How can I give Prolog enough information to make this**inference?**How can I give Prolog enough information to make this**inference?**Mutual Recursion Example(Two functions that call each other)**WARNING: This is ridiculous code that no one should ever write!!!! But is a simple to understand example of mutual recursion!!! How many times is odd? called in: (even? 7) a)0 b)1 c)2 d)3 e)> 3**Mutual Recursion Solution**Here I used (trace even?) and (trace odd?) So I could see what calls were made! (Debugging tip!)**What you should understand right now:Mutual recursion is**when two functions call each other!**You always read the book before writing the essay:**• In CS you should: • Read the description of the problem • Read the provided code Unicalc(Hw3 Unicalc) • The goals of this assignment: • Use mutual recursion • Make something that works • Figure out how pieces fit together • Practice reading!**Quantity Lists (Represented as Lists – HW3)**'(9.8 (meter) (second second) 0.01) • multiply, divide, add, power • Simplify units • Handle uncertainty • “Normalize” units Quantity Numerator (units) Denominator (units) Uncertainty**Database (assoclist) of conversions**Base units (e.g. seconds, meters) don’t have an entry in the DB All non-base units have a quantity-list conversion listed**Mutual Recursion Example 1(norm-unit & norm-QL)**From DB (list 'joule (make-QL 1.0 '(kg meter meter) '(second second) 0.0)) (norm-unit 'joule) Calls: (norm-QL '(1.0 (kg meter meter) (second second) 0.0)) Which calls: > (norm-unit 'kg) > (norm-unit 'meter) > (norm-unit 'meter) > (norm-unit 'second) > (norm-unit 'second) If there is assoc-list entry (i.e. not a base unit) norm-unitcalls norm-QL once These are all base units so they don’t call norm-QL norm-QL calls norm-unit once for EACH unit**Mutual Recursion Example**(norm-unit 'day) (norm-QL '(24.0 (hour) () 0.0)) (norm-unit 'hour) (norm-QL '(60.0 (minute) () 0.0)) (norm-unit 'minute) (norm-QL '(60.0 (second) () 0.0)) (norm-unit 'second) Base units (e.g. seconds, meters) don’t have an entry in the DB**Write notes to yourself about what you understand about**unicalc at this point**What you should understand right now:**• I will need to spend time reading the unicalc assignment • Unicalc uses mutual recursion • norm-unit calls norm-QL • norm-QL calls norm-unit • “Base units” don’t need to be normalized and therefore there is no entry for them in the unicalc database!**Graphs can be stored as ListsEdge List**This vocab is important (define unicycleGraph'( ("A" "B") ("A" "D") ("B" "D") ("C" "B") ("C" "D") ("D" "E") ("E" "F") ("F" "G") ("G" "H") ("H" "E") )) I can think of other ways to represent this graph!**Graph-reachability: can you get from s to d?**is there some path from s to d in G? s == source d == dest. (define (reach? s d G) ? s d … ? ? a b I know I can get from a to b. If I can get from S to A and from B to D… (define unicycleGraph '(("A" "B") ("A" "D") ("B" "D") ("C" "B") ("C" "D") ("D" "E") ("E" "F") ("F" "G") ("G" "H") ("H" "E") ))**Graph-reachability: can you get from s to d?**is there some path from s to d in G? s == source d == dest. (define (reach? s d G) Consider the algorithm first, then the code...**Graph-reachability: can you get from s to d?**(define (reach? s d G) (cond ( ( ( else (let* ([EDGE [a [b [R [loseit**(nodes unicycleGraph)→'("A" "B" "D" "C" "E" "F" "G" "H")**(define (nodes graph) Hint: how could we use remove-duplicates (kids "A"unicycleGraph) →'("B" "D")(kids "B"unicycleGraph) → '("D") (define unicycleGraph '(("A" "B") ("A" "D") ("B" "D") ("C" "B") ("C" "D") ("D" "E") ("E" "F") ("F" "G") ("G" "H") ("H" "E") )) (define (kids n graph) big-O( ) ~ edges or nodes? parents? Hint: could we use filter?**Feel free to use available functions: remove-duplicates,**nodes, kids, parents, and higher-order functions... Write these functions for directed graphs. (define (leaf? n G) (leaf? n G) should return #t if n is a leaf in G and #f otherwise. ( (leaf? "E" unicycleGraph)→ #f Hint: call (kids n G) (define (gkids n G) (gkids n G) should compute the list of grandchildren of n in G: all nodes two edges away. ( (gkids "E" unicycleGraph)→ '("G") (gkids "A" unicycleGraph)→ '("D" "E") Hint: use kids and map - It's a bit tricky... (define (reach? a b G) (reach? a b G) should return #t if there is some path from a to b in G and #f otherwise. ( (reach? "B" "E" unicycleGraph)→ #t there is definitely not enough room here – plus, we’ll talk about a solution in the next lecture... (reach? "E" "B" unicycleGraph)→ #f**Graph-reachability: can you get from s to d?**is there some path from s to d in G? s == source d == dest. (define (reach? s d G) Consider the algorithm first, then the code...