Last year's exam available

[sewe]

You can find the exam of last year in the SVN: https://cage.st.informatik.tu-darmstadt ... m-2011.pdf. I hope you find this useful.

Unfortunately, last year's exam was in German. I hope this is not a problem for anyone. (Of course, this year's exam will be - like the lecture - in English).

Please also note that this year we haven't covered the topics of type systems, formal semantics and function-reactive programming (well, we will cover FRP next week, but it won't be part of the 2012 exam).

[FeG]

Hi,

I first thought of posting halfway complete solutions for the exam, but as I also want to go through the second half of the exam check-list (whose questions, at least for me, are notably more difficult as the questions in the exam), I'll only post some questions on the parts of the exam where I have the most uncertainties.


3.1 Name four approaches to implement recursion (with short description).

Are they:

• fundef-lists separately passed to the interpreter. As used as external look-up reference, function calls can be recursive.
• cyclic environments: cyclically close function closure environments over themselfves, using mutable data structures.
• functional environments that way, one can use the recursion property of the underlying scheme functions (-> meta-interpreter).
• Y / fixpoint combinator: use of Y-combinator (like for "define" with lambda calculus) allows recursive functions by its specific fixpoint property.

?

3.2

Is it

• x@2 : static = 2, dynamic = 2
• x@3 : static = 1, dynamic = 4
• y@3 : static = 3, dynamic = 3
• x@5 : static = 4, dynamic = 4

?

4.1 Is it 7, 5, and 4 ?

5.1 instance for []:

Code: Alles auswählen

instance Monad [] where
  (>>=)  :: [a] -> (a -> [b]) -> [b]
  return :: a -> [a]
  fail   :: String -> [a]

?

5.3 Discuss existence of "unsafePerformIO :: IO a -> a".

As this was never mentioned in the lecture or exercise and so I have to look it up online (which is no option on Friday ), I'm very uncertain about my following solution:

• the operation is not type-safe
• I/O operation enclosed should be free of side effects
• if I/O operation enclosed has side effects, then the relative order of the I/O operations to the remaining program is undefined

That's mostly copied from here, and I think I at most got a little idea what the operation does and where the problems lie. Maybe someone could explain this a bit...

6.3 That's just "4 (with left-to-right processing)"?

8.2 Again, the answer (for after all 4 points) is just "1"?

9.3 Is it sufficient to write "Fixpoint op. not needed, as no recursive call is made in 9.1."?



So far, thanks in advance for any responses on that.

Best,
Felix

[sewe]

5.3 Discuss existence of "unsafePerformIO :: IO a -> a".

As this was never mentioned in the lecture or exercise and so I have to look it up online (which is no option on Friday ), I'm very uncertain about my following solution:

• the operation is not type-safe
• I/O operation enclosed should be free of side effects
• if I/O operation enclosed has side effects, then the relative order of the I/O operations to the remaining program is undefined

That's mostly copied from here, and I think I at most got a little idea what the operation does and where the problems lie. Maybe someone could explain this a bit...

Hey, this was mentioned (albeit briefly) in the exercise!

Anyway, the important thing to think about is that the Monad type class alone does not offer you any way to convert a m a to a plain a. In other words, once some expression is "tainted" by the IO monad, any expression that uses this as a subexpression also has to have a type IO ... - unless you use unsafePerformIO. (In a sense, unsafePerformIO assumes the same role as fromMaybe for the Maybe monad or runIdentity for the Identity monad or pattern matching on : for the list monad or ...)

Now, within the IO parts of the program, Haskell (or rather the IO monads >>= operator) give you some guarantees about the evaluation order. But outside of the IO monad, this is not the case (or rather, the order is deterministic but - due to laziness - often unpredictable for mere humans). This is the reason for the two recommendations on the website you found:

• I/O operation enclosed should be free of side effects
• if I/O operation enclosed has side effects, then the relative order of the I/O operations to the remaining program is undefined

Hope this explains things a bit.

[FeG]

Thank you very much, Andreas, this gave me a little context.

Hey, this was mentioned (albeit briefly) in the exercise!

I assume you mean the exercise class (as in the exercise/solution files, I must have missed it several times by now.. ) -- that might be the case, but due to a parallel lecture I wasn't able to attend the classes on Friday

So thanks again for the explanations here...

Best,
Felix

[aloifolia]

Here is an example of how unsafePerformIO could be used in an evil manner:

Code: Alles auswählen

aString = unsafePerformIO $ getLine :: String

From the type signature you would not assume that this aString has side effects. You would guess that aString would always yield the same String value. But this is not the case as the output depends on the user's input...

One question though: The following expression is erroneous (as the interpreter says) - how comes?

Code: Alles auswählen

let foo = unsafePerformIO . getLine

[sqrtsben]

Hi guys,

just wanted to touch base on the CPS task 8.1. Does this make sense?

Code: Alles auswählen

(define (remove/k item l k)
  (cond [(empty? l) (k empty)]
        [(not (list? l)) (k empty)]
        [else
         (if (equal? item (first l))
             (remove/k item (rest l) (lambda(list-rest)
                                       (k list-rest)))
             (remove/k item (rest l) (lambda(list-rest)
                                       (k (cons (first l) list-rest))))
             )]))          

As for 3.2, I get the same.

For 4.1, the question is how the memoization works exactly. Does the interpreter cache the result of the "function call" to + - that would mean for the two {f {+ 1 1}}, it would only run the calculation once. Same holds true for the two calls to f(2). That would mean, at this point the interpreter would only have done two additions, now followed by the third one, as it doesn't yet "know" what (+ 4 4) is. In total, that would result in 3 additions.

For call-by-name, I agree with you. For call-by-need, the question is whether (+1 1) is an "argument" or not. If it is, (+ 1 1) would have to be calculated just once. From there one, we need to run f(2) twice as we only cache arguments, not function values for certain arguments. Finally, the outer addition leads to 4 additions.

[sqrtsben]

btw - anyone willing to provide a solution to 9.1. I'm completely stuck on that one

[FeG]

Hi,

just wanted to touch base on the CPS task 8.1. Does this make sense?

Code: Alles auswählen

(define (remove/k item l k)
  (cond [(empty? l) (k empty)]
        [(not (list? l)) (k empty)]
        [else
         (if (equal? item (first l))
             (remove/k item (rest l) (lambda(list-rest)
                                       (k list-rest)))
             (remove/k item (rest l) (lambda(list-rest)
                                       (k (cons (first l) list-rest))))
             )]))          

I think it's correct, although on equal you could just use (remove/k item (rest l) k). (And, besides, the [(not (list? l)) (k empty)] check deviates from the original function, this wasn't checked at all there...)

For 4.1, the question is how the memoization works exactly. Does the interpreter cache the result of the "function call" to + - that would mean for the two {f {+ 1 1}}, it would only run the calculation once. Same holds true for the two calls to f(2). That would mean, at this point the interpreter would only have done two additions, now followed by the third one, as it doesn't yet "know" what (+ 4 4) is. In total, that would result in 3 additions.

Good point; I assumed that only user-defined functions use memoization and that + does not.

For call-by-name, I agree with you. For call-by-need, the question is whether (+1 1) is an "argument" or not. If it is, (+ 1 1) would have to be calculated just once. From there one, we need to run f(2) twice as we only cache arguments, not function values for certain arguments. Finally, the outer addition leads to 4 additions.

I don't get this, what do you mean by "is (+ 1 1) an 'argument'"? ... It's an argument to f (in both calls), so it gets only evaluated once in each f call (= 2 times overall). Then each f does an addition (= 2), finall the results are added (= 1), in sum: 5. The only thing, along with your first comment, would be, whether "(f (+ 1 1))" is seen as an argument to + and thus only one f is called... but again, I though built-in functions were left out in this consideration.

btw - anyone willing to provide a solution to 9.1. I'm completely stuck on that one

Sure. The idea is to use that a list of length l calls the "c" function (in l-cons) l times before returning the "n" value. So one can pass a function for c which just ignores the actual list element "e" and simply calls a provided function f on the rest. Now if one pass the parameter x of the church number function as the n, the result is that f is applied l-times to x, i.e., you get the function representing the number l.

Now the code:

Code: Alles auswählen

(define (l-length l)
  (lambda (f)
    (lambda (x)
      (l (lambda (e r) (f r)) x))))

Best,
Felix

[sqrtsben]

I think it's correct, although on equal you could just use (remove/k item (rest l) k). (And, besides, the [(not (list? l)) (k empty)] check deviates from the original function, this wasn't checked at all there...)

That came from an earlier test of mine. Removed it now, thanks

For call-by-name, I agree with you. For call-by-need, the question is whether (+1 1) is an "argument" or not. If it is, (+ 1 1) would have to be calculated just once. From there one, we need to run f(2) twice as we only cache arguments, not function values for certain arguments. Finally, the outer addition leads to 4 additions.

I don't get this, what do you mean by "is (+ 1 1) an 'argument'"? ... It's an argument to f (in both calls), so it gets only evaluated once in each f call (= 2 times overall). Then each f does an addition (= 2), finall the results are added (= 1), in sum: 5. The only thing, along with your first comment, would be, whether "(f (+ 1 1))" is seen as an argument to + and thus only one f is called... but again, I though built-in functions were left out in this consideration.

I was thinking about that yesterday as well. Call-by-need (according to the slides) means that an argument to a single function call is evaluated at most once. Thus, I agree with you - ( + 1 1 ) is evaluated once for the first call to f and once more for the second call, as they are separate calls. In total, that means 5 calls.

The question remains, whether or not built-in functions are considered or not. Andreas, can you shed some light on that?

Regards,
Ben

[sewe]

One question though: The following expression is erroneous (as the interpreter says) - how comes?

Code: Alles auswählen

let foo = unsafePerformIO . getLine

Well, what are the types involved?

Code: Alles auswählen

getLIne :: IO String
unsafePerformIO :: IO a -> a
(.) :: (b -> c) -> (a -> b) -> (a -> c)

So, the problem is simply that getLine is not a function.

[sewe]

For call-by-name, I agree with you. For call-by-need, the question is whether (+1 1) is an "argument" or not. If it is, (+ 1 1) would have to be calculated just once. From there one, we need to run f(2) twice as we only cache arguments, not function values for certain arguments. Finally, the outer addition leads to 4 additions.

I don't get this, what do you mean by "is (+ 1 1) an 'argument'"? ... It's an argument to f (in both calls), so it gets only evaluated once in each f call (= 2 times overall). Then each f does an addition (= 2), finall the results are added (= 1), in sum: 5. The only thing, along with your first comment, would be, whether "(f (+ 1 1))" is seen as an argument to + and thus only one f is called... but again, I though built-in functions were left out in this consideration.

I was thinking about that yesterday as well. Call-by-need (according to the slides) means that an argument to a single function call is evaluated at most once. Thus, I agree with you - ( + 1 1 ) is evaluated once for the first call to f and once more for the second call, as they are separate calls. In total, that means 5 calls.

The question remains, whether or not built-in functions are considered or not. Andreas, can you shed some light on that?

OK, in all our implementations so far, + and - where built-in primitives rather than identifiers returning a closure of a (binary!) function upon evaluation. So, there's no function closure to attach a memoization "cache" (for lack of a better word) to. There is, however, in a lazy interpreter an expression closure for (+ 1 1), which can contain a (single-value) cache.

That being said, different expressions evaluate to different expression closures, which do not share their caches. This, the correct answers for task 4.1 are as follows:

• Interpreter mit call-by-name: 7
• Interpreter mit call-by-need: 5 (within f, the two summands x share the same cache/point to the same expression closure)
• Interpreter mit call-by-name: 4 (the value of (f 2) is cached)