how to simulate the concept of object identity in Haskell

Question

I am considering the design of an interpreter for Python like object oriented language in Haskell. One particular problem I am facing is related to the concept of object identity. If we consider Python's id(object) function, the definition suggests that it returns the "identity" of an object. This is an integer (or long integer) which is guaranteed to be unique and constant for this object during its lifetime. Two objects with non-overlapping lifetimes may have the same id() value. (Implementation note: this is the address of the object.)

What is the general approach to implement a concept like this in Haskell?

Answer 1

I assume that your interpreter will work within the State monad. Probably the state will consist of a collection of live objects and whatnot. What you can do, is keep track of a list of available (non-used) ids (represented as Ints) and annotate every Object with an Int, namely its id. This id was taken from the list of available ids and assigned to it at creation time. Thus it cannot be that two Object instances have the same id.

Observe that I talked about Ints. You could go for Integers, but that may eventually become less efficient. Going with Ints does mean that you'll have to add the id of destroyed objects back to the pool (list) of available ids (for otherwise you'd run out, eventually). Thus I envision something like this:

data Object a = Obj Int a

instance Eq (Object a) where
  Obj i _ == Obj j _ = i == j

type InterpreterState a = State [Int] a

createObject :: a -> InterpreterState (Object a)
createObject a = do
  (i:is) <- get 
  put is
  return $ Obj i a 

destroyObject :: Object a -> InterpreterState ()
destroyObject (Obj i a) = do
  modify (i:)

(Note that InterpreterState will be much more complex in your case, and createObject and destroyObject should have the object added to/removed from the state. But that's beside the point here.)

Answer 2

The answer to this question depends on how you are going to implement these objects you want to get id's from. How is it going to look if two variables contain the same object? You basically need to store references to "mutable" objects in the variables, the question is how exactly you do this. If you would just associate simple values to variable names changes in one variable would never be reflected in another variable, and there would be no such thing as object identity.

So the variables need to hold references to the actual current values of the objects. This could look like this:

data VariableContent = Int | String | ObjRef Int | ...
data ObjStore = ObjStore [(Int, Object)]
data ProgramState = ProgramState ObjStore VariableStore ...

Here each ObjRef refers to a value in ObjStore that can be accessed by the Int id stored in ObjRef. And this Int would be the right thing to be returned by the id(object) function.

In general the id function strongly depends on how you actually implement object references.