David Stone's Blog

Another Quarter Done

Whew. Crazy quarter. Glad that's over. I just found out that I got an A in my programming languages course. That's really good, because the final was killer. It had a bunch of "what's the value of this ML/Python/Prolog program" questions and some scoping stuff, and the real fun part: write an algorithm in prolog to type check ML programs. (Everybody was thinking they failed the class.) The professor used the "I don't like failing people" grading curve...where everybody above a 50% in the class at least passed.

My compiler construction final was significantly different than I thought it would be. The True/False questions Kube always puts on his tests didn't seem to be too bad. And a fair amount of them were either totally obvious (T/F: A Text Node in the XML DOM can never have child objects.)  or things that I had on my cheat sheet. There was a whole section on "Give the value of this XQuery program" (that's what we were doing all quarter, after all), and since I've been staring at XQuery these last two weeks, that wasn't that hard. The hardest parts were generating an SLR(1) parse table, using an SLR(1) parse table to parse a simple string (and giving the steps that it parsed), and generating first- and follow-sets from CFGs. Crazy stuff. Those were hard, but I had them on my cheat sheet as well. So I think I pretty much rocked the final. We'll see though. I hear we'll get grades by Monday.

Math 109 is something I at least passed. I had a 140% on the first midterm, a 50% on the second, (worth a sum total of 50% of my grade), I only turned in about half of the homework (~15%), and then there was the final (which I think I did really well on), which was 35% of my grade. I'm hoping for a B. It'd be pretty hard for me to totally not pass the class.

Today's agenda: Help out a friend with studying for her math placement exam. Get a haircut. Maybe fix up some stuff in CPHog that I've been meaning to look at. About a month ago, Firefox trunk builds were changed so that child nodes created in different documents must be imported into the document you want to use them in. This is valid, according to the spec, but a lot of Javascript totally ignores it because, up till now, Firefox has let you just use them together. Well not anymore. It's broken a few things in CPhog for me.

CSE 130 Sample Final Answers

1. Ocaml Types
   1. ans:int = 804
   2. type error
   3. ans:int = 100
   4. ans:int = 20
2. Function Type / Write reverse
1. 'a -> 'a * 'a -> bool * 'a -> 'a
2. let reverse l =
1. let f (c,b) = match c with [] -> ([], b) | h::t -> (t, h::b) in
2. let g (l, acc) = match l with [] -> false | h::t -> true in
3. let base = (l, []) in
3. Semantic Equivalence
1. Semantically Equivalent because addition is transitive
2. Not Semantically Equivalent because g is not defined in e2
3. Semantically Equivalent because multiplication is transitive
4. OCaml Module
1. Part A
1. Signature B
2. Stack.top [];;
3. Because signature A says that 'a stack = 'a list, you can call any function on 'a stack on an 'a list instead. This allows Stack.top to be called on [], which will throw the EmptyStack exception. When using signature B, you must call Stack.make, and it will never give you back an empty list.
2. Part B
1. Signature A
2. Inferred Type: 'a stk -> 'a list
3. Part C
1. Doesn't work
5. Boolean Formulas
1. type boolexp = Var of int | Not of boolexp | Or of boolexp * boolexp | And of boolexp * boolexp
   And(Or(Var(0), Not(Var(1))), Or(Var(1), Not(Var(2))))
2. let rec eval(list, expr) =
       let rec find (list, index) =
           if(index = 0) then List.hd(list)
           else find(List.tl list, index - 1) in
       match expr with
           Var(i) -> find(list, i)
           |Not(v) -> !eval(list, v)
           |And(a1,a2) -> eval(list, a1) && eval(list, a2)
           |Or(a1,a2) -> eval(list,a1) || eval(list,a2)