View source

== Question 1: haskell ==

Here's a (perhaps overly complex) solution:
 (\l -> map (\i -> snd i) (filter (\i -> fst i) (zip (foldl (\a b -> a ++ [b == 7])  [] l) (drop 1 l) )))



 > follow7::[Float] -> [Float]
 > follow7 [] = []
 > follow7 [a] = []
 > follow7 (a:b:x) 
 >		|  a == 7.0 = b:follow7 (b:x)
 >		| otherwise = follow7 (b:x)

== Question 2: prolog  ==

 permute([ ], [ ]).
 permute(L, [X | Y] ):- select(L, X, T),
                          permute(T, Y). 
 select([X | Y], X, Y).
 select([X | Y], Z, [X | T]):- select(Y, Z, T).

permute([1,2,3], X) will follow a depth-first search tree which builds a new list by selecting the first element (1), and permuting the rest of the list [2,3]. 
The recursive call to permute([2,3], X) then selects the first element (2) and permutes the rest of the list [3], which ends up just being [3].
The rest of the list is effectively patched together putting together the (1), (2), and (3) above, resulting in [1,2,3]

If a semicolon is pressed, then the prolog engine backtracks up to the last select call that had a "choice", which selects (3) instead of (2), which results in a final list of [1,3,2].

Next time a semicolon is pressed, the engine backtracks up one more level to match (2) as the first element, which will end up resuling in a final list of [2,1,3]

== Question 3 : semantics ==

=== (a) Denotational semantics ===

* Branching (if statements)
** We are adding a statement like {"if" E "then" L1 "else" L2} in our language. Goal is to explain precisely what it does "denotationally".
** Write this:
 <nowiki>S[[â�?��?ifâ�?��?� E â�?��?thenâ�?��?� L1 â�?��?elseâ�?��?� L2]](Env) =</nowiki>
 <nowiki>   if E[[E]](Env)>0 then L[[L1]](Env)</nowiki>
 <nowiki>                       else L[[L2]](Env)</nowiki>
** then explain what this means 
*** we're defining a new statement, 
*** a statement takes an environment and gives back a new environment (for the rest of the statements to use). 
*** The if statement will evaluate the expression in the current environment
**** if the expression 'E' evaluates to greater than zero, execute the first list of statements (which will consequently modify the environment in one way)
**** if the expression evaluates to less or equal to zero, evaluate the second list of statements with the environment given, which will modify the env in a different way.
(resulting in a new enviornment that is the composition of the modifications of each statement in the list)

* Looping (while statements)
** We are adding a statement like {"while" E "do" L}
** Wriet this:
 <u>S</u><nowiki>[[ â�?��?whileâ�?��?� E â�?��?doâ�?��?� L]](Env) =</nowiki>
   if <u>E</u><nowiki>[[E]](Env)<0 then Env else</nowiki>
       <u>S</u><nowiki>[[ â�?��?whileâ�?��?� E â�?��?doâ�?��?� L]](</nowiki><u>L</u><nowiki>[[L]](Env))</nowiki>
** then explain what it means
*** First evaluate E in the given environment
**** If it's less than zero, return the current environment
**** Otherwise get the new environment by evaluating the statement list in the given environment. Pass that to a new do/while instance. (thus checking the expression in the new environment ...)


=== (b) Axiomatic semantics ===

==== This is wrong: ==== 

* Actually, you need to start with the <math>P</math>, work backwards through the code (as we have done), make sure that <math>P\wedge B</math> can derive what we find after all the substitutions. As a second step, you must also prove that <math>P \wedge \neg B</math> derives the end result: <math>x == gdc(x_0,y_0)</math>

<math>x_0</math> is initialize value of x, <math>y_0</math> is initial value of y

precondition/loop invariant = <math>\{(gcd(x,y) == gcd(x_0,y_0)) \wedge (x \geq 0) \wedge (y \geq 0) \wedge (x+y > 0) \}</math>

postcondition = preconditions<math> \wedge (y==0)</math>

Taking the whole post condition:

<math>(gcd(x,y) == gcd(x_0,y_0))  \wedge (x \geq 0) \wedge (y \geq 0) \wedge (x+y > 0) \wedge y==0</math>

<code>x=temp</code> <math>\implies (gcd(temp,y) == gcd(x_0,y_0)) \wedge (temp \geq 0) \wedge (y \geq 0) \wedge (temp+y > 0) \wedge y==0</math>

<code>y=x%y</code> <math>\implies (gcd(temp,x%y) == gcd(x_0,y_0)) \wedge (temp \geq 0) \wedge (x%y \geq 0) \wedge (temp+x%y > 0) \wedge x%y==0</math>

<code>int temp=y</code> <math>\implies (gcd(y,x%y) == gcd(x_0,y_0)) \wedge (y \geq 0) \wedge (x%y \geq 0) \wedge (y+x%y > 0) \wedge x%y==0</math>

<math>\implies (gcd(y,x) == gcd(x_0,y_0)) \wedge (y \geq 0) \wedge (x \geq 0) \wedge (y+x > 0)</math>

Given the post conditions, we have found that the loop invariant and pre conditions hold. Because we find that <math>y==0</math> and we know that <math>gcd(x,0) == gcd(x_0,y_0) \wedge gcd(x>0) </math> which <math>\implies</math> therefore, <math>x = gcd(x_0,y_0)</math>

'''note:''' <math>gcd(x,y%x) = gcd(x,y)</math>

== Question 4: Reference model vs. value model ==

* Differences
** Stack allocation vs. heap allocation
** dynamic dispatching vs. static
* Similarities
** Because value parameters are passed by reference, the objects are not copied in either case, just the reference/pointer is passed.

* templates:
** add generic types/code without dynamic dispatching, but it's only at compile time

* in the value model, objects are copied on the stack so functions are dispatched statically. You need to pass the object by reference to get functions to be dispatched dynamically.

== Question 5: non-determinism ==

* compiler writer can focus on ''fairness''
** Programmer can focus on ''service''
* unpredictable
* execution can be overlapped