Hi Ramana, The reason for only allowing a weak reference to point to a reference has to do with the notion of equality in ML and the way the Poly/ML system and the garbage collector in particular deal with that. A reference has an identity and so it is possible to say whether a particular reference is pointed at from anywhere else. Equality for references is defined as pointer equality and Poly/ML respects that.
Equality for immutable data is by value and in the absence of PolyML.pointerEq it is not possible to distinguish two pointers to the same immutable data structure from two pointers to different structures with the same contents. The garbage collector exploits this both by allowing some duplication and also by compacting equal data structures when memory is short. All this means that if a weak pointer could point to an immutable data structure it would not be possible to give any assurance as to when the weak pointer would be modified by the garbage collector. That may not matter if the object is to implement some sort of speed-up but it wouldn't be acceptable if the idea was to discover whether some other entity was reachable or not.
I have to ask what your motivation behind implementing hash-consing is. The garbage collector already implements a "sharing" phase if memory is really short and this will effectively hash-cons all the shareable data.
Regards, David
On 04/10/2015 09:27, Ramana Kumar wrote:
Hello,
I am interested in using Poly/ML's Weak structure ( http://polyml.org/documentation/Reference/Weak.html) for hash-consing. The documentation would perhaps suggest that this is not an intended use of Weak, so I'd like to ask the list whether it is suitable and, if not, whether there are alternatives.
An abstract of the problem is as follows. For a certain datatype, t, we want there to be at most one copy of any value of type t created by applying a constructor to unique arguments. To achieve this, we implement "hash-consing" constructors for t, which check whether the desired value exists already and return it if so, and only otherwise create a new value. To be able to check which values exist already, we maintain a hash table of all existing values. To allow values to be garbage collected when they are no longer needed, we make the hash table store only weak references to the values.
The Weak structure allows weak references to be made to other references, but not to other non-reference values. Thus, the values in the hash table can be of type (t ref option ref), as produced by Weak.weak, but not of type (t option ref). Thus, on the face of it, it seems like using Poly/ML's Weak implementation will require unnecessary references and indirections. Is that indeed the case, or is Poly/ML smart about avoiding unnecessary indirections somehow?
For hash-consing, we are not using Weak in the way described in its documentation, wherein the contents of the reference don't matter and the reference itself is only used as a token to track an external resource. Is there, perhaps, an alternative interface to Poly/ML's garbage collector more suitable for hash-consing?
Cheers, Ramana
polyml mailing list polyml at inf.ed.ac.uk http://lists.inf.ed.ac.uk/mailman/listinfo/polyml