Ex06: Wrong reference counting

Jannis
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Ex06: Wrong reference counting

Hello!

I think that the reference counting in Ex06 and the RefCount_SRCFLAEInterp interpreter could be wrong. When we evaluate the following expression:

Code: Alles auswählen

Seqn(Let('box, NewBox(Num(0)), SetBox(Id('box), Num(1))), Num(2))

then we end up with one reference to Box(0) ('box) and one reference to Num(1). Both values should have been deleted when we do reference counting because we cannot reach them in the second expression inside Seqn.

How the interpreter counts the references:

Code: Alles auswählen

Seqn(
Let('box, NewBox(Num(0)),           ('box: 1, NumV(0): 1)
SetBox(Id('box), Num(1))),      ('box: 2 ~ Id('box) increments the 'box reference count,
NumV(1): 2 ~ because of enref in SetBox,
NumV(0): 0 ~ destroyed)
Num(2)                              ('box: 1 ~ because of the Let deref,
NumV(1): 1 ~ because SetBox returns NumV(1) -> deref in Seqn,
NumV(2): 1)
)

I think one of the problems here is that we do increment the reference count on each call of Id('x). But I was not able to completely fix the reference counting yet.

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

Re: Ex06: Wrong reference counting

Hi,

does ex06 even do any reference counting? That seems to be mostly about the qualitative properties of RC.

Anyway, what I would like to discuss a bit is the implementation of the reference counting interpreter.
The short version is … the implementation of that interpreter is not very good.
This goes beyond your example (which I did not check btw.) and more than specific bugs, I think the whole concept of RC is not very clear in the interpreter. The first problem is, that each Value has a mutable field for the reference count. Disregarding the fact, that mutable state in an interpreter is always a code smell, it also makes very little sense to store the count together with the value. How many pointers exist to a particular location in the store is a property of either those pointers, or the store itself, not of the stored value.
The second problem (maybe as a result of the first), is that even values that are not stored in the store have a reference count. The way the interpreter works, is that each time a value is produces you increase the refcount of the produced value by one. E.g., Num(2) produces a new value so the value has a ref count of 1, and Id('x) produces the value bound to 'x, so you increase the refcount of that value by one. And each time a value is consumed, the refcount is decreased by one, i.e., Add(Num(1), Num(2)) consumes the two numbers, reducing their value by 1. Note that the store is not involved in any of these operations.

Going by the second point, the bug you mentioned is very likely related to SetBox consuming the value of Id('box) but not decreasing the count of the consumed value. But I would recommend not using this particular interpreter as an example of good craftsmanship.

Now, if someone wants to improve the quality of the interpreters as part of an extended tutor position, a Praktikum in der Lehre, or a small lab project, please come talk to us

Jannis
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Re: Ex06: Wrong reference counting

Well, ex06 does not explicitly do reference counting. But in task 1.3 one has to reason why the calls of enref/deref in the given code examples are necessary. My point was that it is hard to give an appropriate answer because the interpreter itself does not correctly count the references.

I guess tracking the number of references for each object should work too (otherwise there would be no reason why it is introduced in the lecture), but you are right that this introduces some problems regarding the semantics of the reference counter.

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

Re: Ex06: Wrong reference counting

The main problem with the tracking on the value is that doing it this way is only simpler if because of the mutable field. Which is plain bad style. Encoding the counters as part of the store for example would allow us to continue using store passing style and keep the interpreter pure.

Did you try adding a deref call to the SetBox case? Because I suspect that may fix the bug you observed.

Jannis
Mausschubser
Beiträge: 63
Registriert: 15. Apr 2015 17:10

Re: Ex06: Wrong reference counting

Ragnar hat geschrieben:
1. Mär 2018 22:07
Did you try adding a deref call to the SetBox case? Because I suspect that may fix the bug you observed.
Yes, this fixes the bug in the expression from the first post.