## Eighth assignment now available

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

### Eighth assignment now available

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.)

m1c3
Neuling
Beiträge: 9
Registriert: 7. Okt 2009 17:36

### Re: Eighth assignment now available

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))]
;...


Weishaupt
Windoof-User
Beiträge: 37
Registriert: 7. Okt 2009 20:20

### Re: Eighth assignment now available

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!

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

### Re: Eighth assignment now available

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

Wambolo
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

### Re: Eighth assignment now available

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.

AlexanderF
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

### Re: Eighth assignment now available

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

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

### Re: Eighth assignment now available

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.

sewe
Sonntagsinformatiker
Beiträge: 295
Registriert: 16. Jan 2009 14:53
Kontaktdaten:

### Re: Eighth assignment now available

Finally caught up with things.

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