Ex06 Task 2

Fabian U.
Neuling
Neuling
Beiträge: 4
Registriert: 1. Mär 2017 12:48

Ex06 Task 2

Beitrag von Fabian U. » 1. Mär 2017 12:51

Hi,

when re-doing the exercises as an exam preparation we came across a problem in Ex06 Task 2.
We do not understand how the Initial Store is built in the solution, we would have built it differently (all the arrows to that point/zero thingy make no sense to us).
Some explanation would be great here.

Regards

Ragnar
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

Re: Ex06 Task 2

Beitrag von Ragnar » 1. Mär 2017 18:37

Hi,

the "arrows to that point/zero thingy" are meant to symbolize a scala level reference, so basically the scala object at store location 1 is copied (by reference) to store location 2. I wanted to make this explicit, to be pedantic about how it works.
The concrete implementation used is GC_SRCFWAEInterp (who came up with those names :lol:)
In particular the Let case and the NewBox case:

Code: Alles auswählen

    case Let(boundId, namedExpr, boundBody) => {
      val (namedVal, s1) = interp(namedExpr, stack, store)
      val (newLoc, s2) = s1.malloc(stack, namedVal)
      interp(boundBody, stack.head + (boundId -> newLoc) :: stack.tail, s2)
    }
    
    case NewBox(boxExpr) => {
      val (boxV, boxStore) = interp(boxExpr, stack, store)
      val (newLoc, resStore) = boxStore.malloc(stack, boxV)
      (Box(newLoc), resStore)
    }
Based on this code, the store given in the solution should be correct, but depending on the implementation of the interpreter, the store layout may indeed be different. What assumptions did you use, and what result did they produce?


Now, on a related note, the actual implementation of the GC algorithm is incorrect, because we implemented GC with a mutable "marked" flag, and do this referencing I tried to explain in the exercise. Which results in things beeing GCed which should not be. I already noticed the use of mutable state when preparing for the exercise, however, I did believe it would only cause too many locations to be marked, not too little. Another example that mutable state is very hard to reason about :/
I will upload a fixed version of the interpreter tomorrow.

The Solution for the exercise is, however, correct.

Fabian U.
Neuling
Neuling
Beiträge: 4
Registriert: 1. Mär 2017 12:48

Re: Ex06 Task 2

Beitrag von Fabian U. » 2. Mär 2017 11:33

the "arrows to that point/zero thingy" are meant to symbolize a scala level reference, so basically the scala object at store location 1 is copied (by reference) to store location 2.
We thought it is meant like this, but for the Box at store postion 5 (pointing to store postion 4) suddenly has its real scala object on store position 14. Why is that? How can we know that?

Additionally, the Box at store position 13 doesn't even have a real scala object?

This would only make sense, if you only create a real scala object if the Box is referenced elsewhere. But why would that be?

pschulz
Neuling
Neuling
Beiträge: 9
Registriert: 7. Nov 2016 18:15

Re: Ex06 Task 2

Beitrag von pschulz » 2. Mär 2017 19:00

also the box at store loc. 15 has no "real object" it just points to the one at loc. 14

Ragnar
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 21. Okt 2009 19:15

Re: Ex06 Task 2

Beitrag von Ragnar » 3. Mär 2017 19:11

Okay, I get that the notation was very unfortunate. I am sorry. But I did explain this in a lot of detail during the exercise session.

There is no “real object and false object“ the arrow to little dot notation just says, that an alias is created to the Box object, basically what happens at, i.e., location 2 is something like:

Code: Alles auswählen

store.set(location2) = store.get(location1) 
so you get the object out of location1 and put it into location2. This results in both locations containing the same Scala object. Please, for your sanity and mine, just read all of these as copies, so location2 will also just contain Box(0).

This distinction between making a copy, or just using the same reference is one of the reasons that makes it so hard to reason about Programs with mutable state. If we assume the Box(0) to be immutable, then there is no distinction any more. I fixed the interpreter, so that this is the case.

RamSch
Neuling
Neuling
Beiträge: 4
Registriert: 18. Nov 2015 20:25

Re: Ex06 Task 2

Beitrag von RamSch » 5. Mär 2017 14:08

Hi there,

i have a further question about the behaviour of the non-moving and moving gc.
The solution for non-moving (red marked as collected garbage) seems to not delete line 5 of the heap (Box(4)).
I guess that is because we need the reference of x3 or is this a mistake?

But why do we forget this line 5 in the moving gc? Shouldn't line 5 be changed to line 3 with content of Box(2) etc?

Antworten

Zurück zu „Archiv“