Programming Languages: Fall 2005

From SubfireWiki

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:

S[[â�?��?ifâ�?��?� E â�?��?thenâ�?��?� L1 â�?��?elseâ�?��?� L2]](Env) =
   if E[[E]](Env)>0 then L[[L1]](Env)
                       else L[[L2]](Env)

- 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:

S[[ â�?��?whileâ�?��?� E â�?��?doâ�?��?� L]](Env) =
  if E[[E]](Env)<0 then Env else
      S[[ â�?��?whileâ�?��?� E â�?��?doâ�?��?� L]](L[[L]](Env))

- 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 $P$ , work backwards through the code (as we have done), make sure that $P\wedge B$ can derive what we find after all the substitutions. As a second step, you must also prove that $P \wedge \neg B$ derives the end result: $x = = g d c (x 0, y 0)$

$x 0$ is initialize value of x, $y 0$ is initial value of y

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

postcondition = preconditions $\wedge (y==0)$

Taking the whole post condition:

$(gcd(x,y) == gcd(x_0,y_0)) \wedge (x \geq 0) \wedge (y \geq 0) \wedge (x+y > 0) \wedge y==0$

x=temp $\implies (gcd(temp,y) == gcd(x_0,y_0)) \wedge (temp \geq 0) \wedge (y \geq 0) \wedge (temp+y > 0) \wedge y==0$

y=x%y $\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$

int temp=y $\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$

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

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

note: $g c d (x, y % x) = g c d (x, y)$

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

Programming Languages: Fall 2005

From SubfireWiki

Contents

Question 1: haskell

Question 2: prolog

Question 3 : semantics

(a) Denotational semantics

(b) Axiomatic semantics

This is wrong:

Question 4: Reference model vs. value model

Question 5: non-determinism

Views

Personal tools

Navigation

Search

Toolbox