Sample Exam 2011

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Sample Exam 2011

Beitrag von Kineese »

The sample exam can be found in public respository.

I tried to solve the tasks to check my skills in COPL.
My solutions are truly not correct but I hope that someone else got other (better) solutions. Just post them, I try to update this post to correct answers.

Task 1.1

Code: Alles auswählen

Interpreter: Takes the interpreted language and returns a evaluation of the expression

Compiler: Takes Src-Code and returns Object-Code

Preprocessor: Takes code in language A and returns a tranfomated code of A
Task 1.2

Code: Alles auswählen

def subst( expr: Exrp, substId: Symbol, value: Value){
  ...
  case With(id, idExpr, bodyExpr) => {
    if(substId == id){
      With(id,subst(idExpr,substId,val),bodyExpr)
    }else{
      With(id,subst(idExpr,substId,val),subst(bodyExpr,substId,val))
  }
}
Task 1.3
With(x, 1, With(f, Fun(y, Add(x,x)), f 2) --> App(Fun(x,App(Fun(f,f2),Fun(y, Add(x, y))), 1 )

Task 2.1
a )
It flats a given list. E.g. f(List("a","b",List("c","d"),"e")) --> List("a","b","c","d","e")

b )
No idea how to do it :(

Task 2.2
Use foldr because the constructor of list is right-associative

Task 3.2
That Tasks makes me headaches... see here
With static scoping: the result will be 5. Cause g(f(x)) is called with x=2 so g(f(2)) = g(y=4):= y + x. Here x is bound to the value 1 in the upper With-Expression
With dynamic scoping: Well... I guess it is 3.

Task 4.1
Lazy with call-by-value: 5 times
Lazy with call-by-name: 3 times
Eager with memorization: 3 times

Task 4.2
The lists elements are the result of the multiplication of 2 with the prior element.
First 6 Elements: [1,2,4,8,16,32]

Task 4.3
ys is a list of sums where the operands are the tails of the list itself and the given list
First 6 Elements:[0,1,3,7,15]

Whole Task 5 is skipped, because its not relevant for the exam

Task 6.1
Environment: Stores the location in the Store
Store: Stores a Value or a location in the store

Task 6.2
Scope of a variable: I don't know this by heart :(

Extend of a variable: As explained here the identifier that points to the value in the environment may be not available, but it is possible that another identifier points to the value.

Task 6.3
The result must be 3. The Value 1 is stored in the Store, that will be open increased by 1 and placed back in the store. The last expression in the sequence will open the box (with value 2) and add this with openbox(x) = 1, because it don't have recognition about the changes done in the sequence.

Task 6.4
Have to be done

Whole Task 7 will be skipped, because its not a topic in the exam

Task 8.1
With the usage of tailrec-annotation

Code: Alles auswählen

import scala.annotation.tailrec
object CPS extends App {
def cpsRemove[A](a:A,list:List[A]): List[A]={
  @tailrec def innerRemove(a:A,list:List[A],currList:List[A]) : List[A] = {
    if(list.isEmpty){
      currList
    }else{
       if(a == list.head){
    	   innerRemove(a,list.tail,currList)
       }else{
         innerRemove(a,list.tail, currList++List(list.head))
       }
     }
   }
   innerRemove(a,list,List())
 }
}
Task 8.2
To be done

Task 9
Not done

Task 10
I guess its out of scope!

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Sample Exam 2011

Beitrag von Seldon »

Task 2.1 a): Can you give a hint on how to solve such tasks? I never understand a function's intent just by looking at it... :|

Task 3.2
Dynamic: I think it's 6:
f(2) = 2 + 2 = 4
g(4) = 4 + current(x) = 4 + 2 = 6

Task 6.1
Store stores only values, not locations (though a location can be inside of a box, which is a value)

Task 6.2
The scope of a variable with identifier x is the code's area where all identifiers x refer to this variable. Therefore "dynamic" means the scope widens and narrows during execution.

Task 6.3
The result is 4. The last openbox(x) equals to 2. The fact that the change is visible is the main feature of a box, otherwise Set(x) could have been used. Here's what the environment and store look like after the first line:

Code: Alles auswählen

Env         Store
---         -----
x -> 2      1 -> NumV(1)
            2 -> Box(1)
And after line 3:

Code: Alles auswählen

Env         Store
---         -----
x -> 2      1 -> NumV(2)
            2 -> Box(1)
Task 8.1
That's not CPS, but a nice demonstration of tail recursion ;) The signature expects a continuation as the last argument:

Code: Alles auswählen

import scala.annotation.tailrec
@tailrec
def cpsRemove[A](item: A, l: List[A], k: (List[A]) => List[A]): List[A] = l match {
  case Nil => k(Nil)
  case x :: xs if x == item => cpsRemove(item, xs, k)
  case x :: xs => cpsRemove(item, xs, (res: List[A]) => k(x :: res))
}
Example of usage:

Code: Alles auswählen

scala> cpsRemove(5, List(1, 2, 3, 5, 4, 5, 6), identity[List[Int]])
res4: List[Int] = List(1, 2, 3, 4, 6)
I couldn't find answers for the tasks you skipped. Most of them seem to cover topics we haven't discussed.

--
Some "Bonus questions" as there were many tasks with topics out of scope (if you don't mind :mrgreen:) :
1. Immediate Substitution handles static scope quite nicely. For example, we didn't need function closures for first class functions. However, there was one concept that is impossible with immediate substitution. Which is it?

2. These are the current contents of the environment and the store:

Code: Alles auswählen

Env:          Store:
------        ------
              1 -> NumV(8)
v -> 2        2 -> Box(1)
w -> 3        3 -> Object('Foo, List(Box(4), 12))
              4 -> NumV(10)
              5 -> NumV(9)
z -> 6        6 -> Box(5)
Perform moving garbage collection. Assume that the stack contains [w, z].

3.

Code: Alles auswählen

magic :: [Integer] -> Integer
magic [] = 0
magic (-1 : xs) = sum xs
magic (x : y : xs) = y

countFromTwo = 2 : [x + 1 | x <- countFromTwo]
a) What is the result of evaluating "magic countFromTwo"? Why does it work/fail?
b) Which elements of the list parameter will be looked at when evaluating "magic [2, 3, 4, 42 `div` 0]" ?

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Re: Sample Exam 2011

Beitrag von Kineese »

Hi, thanks for your submission.
Seldon hat geschrieben:Task 2.1 a): Can you give a hint on how to solve such tasks? I never understand a function's intent just by looking at it... :|
Well I guess you just have to look at the keywords^^ In the Sample Exam, the Language Scheme doesn't give any hints about types in the functions signature so its really hard to know what input comes. But just reading line 2 it indicates that a list must be an input. Line three says that the result of the function is a list as well.
Line 4 to 6 finally tell what's exactly happening. If list.head is a List (don't know if something like that exist in Scala, maybe pattern matching) then append the result of function call f with the head of the list as argument with the result of function call f giving the tail of the list. Otherwise (it must be an element) make list.head:f(list.tail).

I guess there is some practice needed to figure out what exactly a function does. For me it took to much time to solve this task, because I'm not familiar with Scheme.

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Re: Sample Exam 2011

Beitrag von Kineese »

Seldon hat geschrieben:
Task 6.3
The result is 4. The last openbox(x) equals to 2. The fact that the change is visible is the main feature of a box, otherwise Set(x) could have been used. Here's what the environment and store look like after the first line:

Code: Alles auswählen

Env         Store
---         -----
x -> 2      1 -> NumV(1)
            2 -> Box(1)
And after line 3:

Code: Alles auswählen

Env         Store
---         -----
x -> 2      1 -> NumV(2)
            2 -> Box(1)
Yeah you must be right. I guess the functionality setBox indicates that the content of the box is mutable :D
Seldon hat geschrieben: Task 8.1
That's not CPS, but a nice demonstration of tail recursion ;) The signature expects a continuation as the last argument:

Code: Alles auswählen

import scala.annotation.tailrec
@tailrec
def cpsRemove[A](item: A, l: List[A], k: (List[A]) => List[A]): List[A] = l match {
  case Nil => k(Nil)
  case x :: xs if x == item => cpsRemove(item, xs, k)
  case x :: xs => cpsRemove(item, xs, (res: List[A]) => k(x :: res))
}
Example of usage:

Code: Alles auswählen

scala> cpsRemove(5, List(1, 2, 3, 5, 4, 5, 6), identity[List[Int]])
res4: List[Int] = List(1, 2, 3, 4, 6)
I couldn't find answers for the tasks you skipped. Most of them seem to cover topics we haven't discussed.
Damn you are right :D

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Re: Sample Exam 2011

Beitrag von Kineese »

Thx for your bonus questions :D
Seldon hat geschrieben: 1. Immediate Substitution handles static scope quite nicely. For example, we didn't need function closures for first class functions. However, there was one concept that is impossible with immediate substitution. Which is it?
Recursion?!
Seldon hat geschrieben: 2. These are the current contents of the environment and the store:

Code: Alles auswählen

Env:          Store:
------        ------
              1 -> NumV(8)
v -> 2        2 -> Box(1)
w -> 3        3 -> Object('Foo, List(Box(4), 12))
              4 -> NumV(10)
              5 -> NumV(9)
z -> 6        6 -> Box(5)
Perform moving garbage collection. Assume that the stack contains [w, z].
I guess the type of garbage collection is irrelevant. So here is just the result:

Code: Alles auswählen

Env:          Store:
------        ------
w -> 3        3 -> Object('Foo, List(Box(4), 12))
              4 -> NumV(10)
              5 -> NumV(9)
z -> 6        6 -> Box(5)
Seldon hat geschrieben: 3.

Code: Alles auswählen

magic :: [Integer] -> Integer
magic [] = 0
magic (-1 : xs) = sum xs
magic (x : y : xs) = y

countFromTwo = 2 : [x + 1 | x <- countFromTwo]
a) What is the result of evaluating "magic countFromTwo"? Why does it work/fail?
b) Which elements of the list parameter will be looked at when evaluating "magic [2, 3, 4, 42 `div` 0]" ?
Haha :D thats a good Task for learning how to read code ;)
Well magic just picks the 2nd element of a List[Int], countFromTwo is a infinite list that starts from two, like [2..].
a) The result is 3
b) I don't know if I understood you question.. But my answer is the whole list..
We insert the list into the magic-function: pattern 1 fails; pattern 2 fails; and pattern 3 watches the first, the second and the tail of the list, so all elements

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Sample Exam 2011

Beitrag von Seldon »

1. We implemented recursion for immediate substitution in WebLab exercise 5.1 ;) The impossible concept is state.

2. Moving garbage collection closes any gaps inside the store by moving the remaining values. This means that also references (in the env and boxes) have to be updated:

Code: Alles auswählen

Env:          Store:
------        ------
w -> 1        1 -> Object('Foo, List(Box(2), 12))
              2 -> NumV(10)
              3 -> NumV(9)
z -> 4        4 -> Box(3)
I admit that the example was not well chosen, as there was only one gap. See group exercise 08 for a similar task, also including copying garbage collection.

3. I should have written "evaluated". As you said correctly, only the first (2nd pattern) and second element (3rd pattern) is evaluated. "magic [-1, 2, 42 `div` 0]" would fail. There is a more verbose example in the slides for lazy evaluation.

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Re: Sample Exam 2011

Beitrag von Kineese »

Seldon hat geschrieben: 3. I should have written "evaluated". As you said correctly, only the first (2nd pattern) and second element (3rd pattern) is evaluated. "magic [-1, 2, 42 `div` 0]" would fail. There is a more verbose example in the slides for lazy evaluation.
How would the call "magic [-1, 2, 42 `div` 0]" fail? On GHCI it works perfectly

Code: Alles auswählen

*Main> magic [2,3,4,42 `div` 0]
3
EDIT:: Argh nevermind :D Thought you would disagree with my solution ;)

Kineese
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 14. Feb 2008 18:33

Re: Sample Exam 2011

Beitrag von Kineese »

Seldon hat geschrieben: Task 8.1
That's not CPS, but a nice demonstration of tail recursion ;) The signature expects a continuation as the last argument:

Code: Alles auswählen

import scala.annotation.tailrec
@tailrec
def cpsRemove[A](item: A, l: List[A], k: (List[A]) => List[A]): List[A] = l match {
  case Nil => k(Nil)
  case x :: xs if x == item => cpsRemove(item, xs, k)
  case x :: xs => cpsRemove(item, xs, (res: List[A]) => k(x :: res))
}
Well yeah I see what the problem is. I didn't do the home-assignment 9 so I', trying to solve these. But I have hard problems with transferring your code into the assignments task.
Home Assignment 9 - CPS hat geschrieben: // Reimplement the `sumList` function below as `sumListCPS` in continuation-
// passing style. This implies that every call has to be a tail-call.
def sumList(list: List[Int]): Int ={
if (list.isEmpty)
0
else
list.head + sumList(list.tail)
}
My current implementations looks like

Code: Alles auswählen

def sumListCPS(list: List[Int], k: Int => Int): Int ={
  @tailrec def innerCPS(acc:Int, l:List[Int],func:Int=>Int): Int = {
    if(l.isEmpty){
      k(acc)
    }else{
      innerCPS(acc+l.head,l.tail, (res: Int)=>k(res))
    }
  }
  innerCPS(0,list,k)
}
The tests works fine, but I'm not sure if this is the correct way of implementing CPS-Style

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Sample Exam 2011

Beitrag von Seldon »

Kineese hat geschrieben: My current implementations looks like

Code: Alles auswählen

def sumListCPS(list: List[Int], k: Int => Int): Int ={
  @tailrec def innerCPS(acc:Int, l:List[Int],func:Int=>Int): Int = {
    if(l.isEmpty){
      k(acc)
    }else{
      innerCPS(acc+l.head,l.tail, (res: Int)=>k(res))
    }
  }
  innerCPS(0,list,k)
}
The tests works fine, but I'm not sure if this is the correct way of implementing CPS-Style
It looks good, however I'm not entirely sure if an accumulator is valid in CPS. Here's a version more faithful to the original:

Code: Alles auswählen

def sumListCPS(list: List[Int], k: Int => Int): Int = {
  if (list isEmpty)
    k(0)
  else
    sumListCPS(list.tail, (res: Int) => k(res + list.head))
}
The transformation follows simple rules:
  • Whenever you return something, call k with the result.
  • If you have to work with the result of a function, call the function with a lambda that does the computation.

gismo
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 10. Jan 2007 17:06
Wohnort: Darmstadt
Kontaktdaten:

Re: Sample Exam 2011

Beitrag von gismo »

Kineese hat geschrieben: Task 2.1
b )
No idea how to do it :(
I think this could be solved by the following code:

Code: Alles auswählen

var testList = List(List("a", "b"), List("b", "c"), List("d", "e"))
                                                  
def f[T](xs: List[T]): List[T] = xs match{
  	case Nil => Nil
  	case x :: xs1 => x match{
  		case x: List[T] => (x :\ f(xs1)) (_ :: _) 
  		case x => List(x) ++ f(xs1)
  	}
}                                               
  	
f(testList) 
Btw.: ":\" = foldRight

dummdidumm
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 28. Apr 2010 18:49

Re: Sample Exam 2011

Beitrag von dummdidumm »

Regarding Task 2.1

converting the function to scala is

def flatten(l: List[Any]): List[Any] = {
l.head match {
case List() => List()
case d: List[Any] => d.head :: flatten(d.tail :: l.tail)
case d: Any => d :: flatten(l.tail)
}
}

in my opinion
using fold is then somehow like this

def flattenF(l: List[Any]): List[Nothing] = {
l.foldRight(List())({(x,y) => x match {
case a : List[Any] => flattenF(a) ::: y
case _ => x :: y
}
})}

note that this gives syntax errors, I just dont know how write this properly with generic types. Any ideas?


Regarding Task 4.1
call-by-name: 7 . he has to inserts (+ 1 1) into both x of the function and has to evaluate them both times. makes 3 additions for one function application, we have two of them so 3*2, and then the final addition in the end -> 3*2+1=7. correct?
call-by-need: 5 . just like call-by-name, he inserts (+ 1 1) into both x, but remembers that the result is 2, so for the second x he does not have to do an addition. however this information is not known for the second f(+ 1 1) so he has to do that again -> 2*2+1=5. correct?
eager with memo: 4. he does (+ 1 1) immediatley, has to do one more inside f -> 2. he remembers the result of f(2). he does (+1 1) again in the second f, sees that he knows f(2). one more addition surrounding both the f-applications -> 2+1+1 = 4. correct?

JanPM
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25
Wohnort: Darmstadt

Re: Sample Exam 2011

Beitrag von JanPM »

Hi, I get different values in 4.1

Task 4.1
Lazy with call-by-name: 7 times
Lazy with call-by-need: 5 times
Eager with memorization: 4 times

does anybody get the same values?

Seldon
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 19. Apr 2012 18:12

Re: Sample Exam 2011

Beitrag von Seldon »

The person above your post does ;) I found the explanation reasonable and agree with the result.

JanPM
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 105
Registriert: 20. Mär 2009 14:25
Wohnort: Darmstadt

Re: Sample Exam 2011

Beitrag von JanPM »

oh right :)

Lemurhummel438
Erstie
Erstie
Beiträge: 15
Registriert: 21. Sep 2011 22:17

Re: Sample Exam 2011

Beitrag von Lemurhummel438 »

Here's my answer to task 2.1

Code: Alles auswählen

object Test extends App {

  var testList = List(List("a", "b"), List("b", "c"), List("d", "e"))

  def f2[T](l: List[Any]): List[Any] =
    l.foldRight(
      List[Any]())(
        { (el, acc) =>
          if (el.isInstanceOf[List[Any]])
            f2(el.asInstanceOf[List[Any]]) ++ acc
          else
            el :: acc
        })

  println(f2(testList))

}
The casting is a bit ugly, but when I try to use pattern matching like this:

Code: Alles auswählen

case el2@List[Any] => f2(el2) ++ acc
It says that List[Any] is an unsupported pattern.



Regarding task 4.1:
@dummdidumm: I agree with you on the results for call-by-name and eager eval. with memo.
(Even though I found the term memoization rather ambiguous since the script says that call-by-need is a memoized version of call-by-name. It then goes on to mention that this means that an argument is evaluated at most once. But with the eager eval. with memo. it seems that memoization means caching the result of the function application)

About call-by-need:
I, however, don't understand why you're saying:
however this information is not known for the second f(+ 1 1) so he has to do that again
Isn't the idea of call-by-need to store the result once an expression has been evaluated? (Then the number of additions would be 4. [This also would make the second function application of f basically copy-by-value.]) Or does the interpreter really throw away the cached value once the function has been applied? Both approaches seem sensible. Am I missing some information that could clear this up?

Antworten

Zurück zu „Archiv“