Seite 1 von 1

Eighth assignment now available

Verfasst: 8. Jun 2012 10:51
von sewe
The eighth assignment (6 Tasks, 10 points overall) is now available: https://cage.st.informatik.tu-darmstadt ... 012-06-08/. Please note: This assignment consists of two parts/files.

Despite there being no exercise class next week, this assignment is already due on Thursday, 14 June 2012, 23:59. (Several tasks require written answers, which I would like to have time to review before the next exercise class on 22 June.)

Re: Eighth assignment now available

Verfasst: 9. Jun 2012 11:01
von m1c3
I think there is a bug in the interpreter of the first assignment. The problem occurs with nested closures.

To reproduce the bug you can define these simple functions in 'funs:

Code: Alles auswählen

(fundef 'inc 'n (parse '{+ n 1}))
(fundef 'dec 'n (parse '{- n 1}))
(fundef 'incDec 'n (parse '{dec {inc n}}))
Now evaluating for example (evaluate '{incDec 2} funs) throws this exception:
numb-n: contract violation, expected: numb?, given: (eclosure (num 2) (list (fundef 'square 'n (mult (id 'n) (id 'n))) (fundef 'inc 'n (add (id 'n) (num 1))) (fundef 'dec 'n (sub (id 'n) (num 1))) (fundef 'incDec 'n (app 'dec (app 'inc (id 'n))))) (emptyEnv) '#&#f)
contract from: numb-n, blaming: use
contract: (-> numb? number?)
You can see, that numb-n expects a numb, but gets an eclosure.

I fixed this issue for me by applying strict recursive to closures:

Code: Alles auswählen

;in define (strict val)
;...
[eclosure (expr funs env cache)
                       (if (boolean? (unbox cache))
                           (begin
                             (set-box! cache (strict (interp expr funs env))) ; recursive call added
                             (unbox cache))
                           (unbox cache))]
;...

Re: Eighth assignment now available

Verfasst: 10. Jun 2012 13:35
von Weishaupt
The fibonacci numbers are once again defined incorrect.

For the next time you do something with fibonnacci numbers, you could actually use the right definition of them. fib(0) = 0! ;)

Re: Eighth assignment now available

Verfasst: 11. Jun 2012 07:50
von sewe
m1c3 hat geschrieben:I think there is a bug in the interpreter of the first assignment. The problem occurs with nested closures.

To reproduce the bug you can define these simple functions in 'funs:

Code: Alles auswählen

(fundef 'inc 'n (parse '{+ n 1}))
(fundef 'dec 'n (parse '{- n 1}))
(fundef 'incDec 'n (parse '{dec {inc n}}))
You are right. This is indeed a bug.
m1c3 hat geschrieben:I fixed this issue for me by applying strict recursive to closures:

Code: Alles auswählen

;in define (strict val)
;...
[eclosure (expr funs env cache)
                       (if (boolean? (unbox cache))
                           (begin
                             (set-box! cache (strict (interp expr funs env))) ; recursive call added
                             (unbox cache))
                           (unbox cache))]
;...
This is exactly the right fix. Thanks. I have already committed it to the SVN.

Greetings from Beijing.

Andreas

Re: Eighth assignment now available

Verfasst: 13. Jun 2012 01:53
von Wambolo
I have a question regarding memoization in case of recursive calls:
Should every result of every recursive call be memoized or just the final result?
In case of fac 10 I could memoize the results of fac 10, fac 9 ... or just the result of fac 10

In addition should we erase the memory when calling evaluate? I think we should not but I'm not sure.

Re: Eighth assignment now available

Verfasst: 13. Jun 2012 14:57
von AlexanderF
hello Wambolo
Wambolo hat geschrieben:Should every result of every recursive call be memoized or just the final result?
In case of fac 10 I could memoize the results of fac 10, fac 9 ... or just the result of fac 10
I think the memory of a function should save each calculated result, i.e. the result for each argument, that was calculated
And because fac n is expressed in terms of fac n-1 ... after calculating fac 10, in the memory of fac should be saved the results for 0,1, ...,10
Wambolo hat geschrieben:In addition should we erase the memory when calling evaluate?
I guess it should be sufficient when you restart your program before you take a second measurement,
because the erasure of the memory was not mentioned in the task.

I'm sorry if I'm wrong with this answer.

regards,
Alexander

Re: Eighth assignment now available

Verfasst: 13. Jun 2012 15:30
von sewe
AlexanderF hat geschrieben:
Wambolo hat geschrieben:Should every result of every recursive call be memoized or just the final result?
In case of fac 10 I could memoize the results of fac 10, fac 9 ... or just the result of fac 10
I think the memory of a function should save each calculated result, i.e. the result for each argument, that was calculated
And because fac n is expressed in terms of fac n-1 ... after calculating fac 10, in the memory of fac should be saved the results for 0,1, ...,10
Exactly; each call to fac should, upon returning, add an entry to the cache.
AlexanderF hat geschrieben:
Wambolo hat geschrieben:In addition should we erase the memory when calling evaluate?
I guess it should be sufficient when you restart your program before you take a second measurement,
because the erasure of the memory was not mentioned in the task.
No, you don't need to reset the memory. It's still a good exercise to think about what this would do to your measurements, though.

Re: Eighth assignment now available

Verfasst: 20. Jun 2012 13:05
von sewe
Finally caught up with things. :-)

The assignment has been marked; points.txts and the model solution are now in the SVN.