content: {-# LANGUAGE TypeSynonymInstances #-}
  
  -----------------------------------------------------------------------------
  -- |
  -- Module      : Berp.Base.Identity
  -- Copyright   : (c) 2010 Bernie Pope
  -- License     : BSD-style
  -- Maintainer  : florbitous@gmail.com
  -- Stability   : experimental
  -- Portability : ghc
  --
  -- A unique identity. All Python objects have a unique identity. In CPython
  -- the identity is the machine address of the object. That relies on the 
  -- object being kept at a fixed virtual address in memory. We can't do the
  -- same thing in Haskell because the garbage collector can move data around.
  --
  -- TODO: consider lazy identities, which are only constructed on demand.
  --
  -----------------------------------------------------------------------------
  
  module Berp.Base.Identity (Identity, newIdentity) where
  
  import Berp.Base.Unique
  import Berp.Base.Hash (Hash (..))
  import Berp.Base.LiftedIO (MonadIO, liftIO)
  
  type Identity = Unique
  
  newIdentity :: MonadIO m => m Unique
  newIdentity = liftIO newUnique
  
  instance Hash Identity where
     hash = hashUnique
  
  {- 
  
  Some comments on this important module.
  
  All Python objects have an identity which is unique to the object.
  The identity of an object can be obtained by the primitive function id().
  
  id is a "built in type or function". 
  
  It returns an integer (class 'int'). According to the __doc__ for id
  in Python 3.0 it says:
  
     id(...)
         id(object) -> integer
      
         Return the identity of an object.  This is guaranteed to be unique among
         simultaneously existing objects.  (Hint: it's the object's memory address.)
  
  There's probably Python code out there which depends on the result being
  an actual integer. But it would be nicer if it returned an abstract type.
  
  There's also a builtin called hash():
  
     hash(...)
         hash(object) -> integer
      
         Return a hash value for the object.  Two objects with the same value have
         the same hash value.  The reverse is not necessarily true, but likely.
   
  In some cases the hash function uses the identity of the object to obtain the hash
  value.
  
  The hash is quite useful, particularly because it is used to allow an object to be
  a key in a dictionary. 
  
  CPython's garbage collector does not move objects allocated on the heap.
  This means it can use the address of the object as its
  identity. Obviously this is problematic if we want to use GHC's collector which
  does move objects.
  
  Thus we must generate a unique identity for all objects when they are constructed.
  
  A couple of important considerations:
     a) The scheme must scale. We should not have any limit on the number of
        identities that we can generate. 
     b) As computation time goes on we'd like to keep
        a handle on the size of individual identities. A constant size would be
        ideal, but we might allow for growth in the size of the identity value
        if it has reasonable asymptotic behaviour.
     c) It should work well with threads. Global counters must be atomically
        updated. 
     d) It is better if the scheme is portable (does not rely on deep GHC magic). 
     e) Should be fast.
  
  A couple of options for implementation:
  
     1) A global mutable Integer counter protected by an MVar.
           - Satisfies a).
           - Size of counter grows logaithmically, but very slowly, so may be
             practical for the vast majority of applications. So probably 
             satisfies b).
           - Will work with threads, but at what cost? Each time an object
             is constructed the running thread must take the lock on the MVar,
             increment the counter, and release the lock. Incrementing an 
             Integer is not trivial, so there may be lock contention. 
             Probably satisfies c), but the significance of the time costs
             are unknown. 
           - MVars are not too magical, so probably satisfies d).
  
     2) A Stable Name.
           - Satisfies a). The number of stable names is only limited to the
             number of objects in memory (I think).
           - Satisfies b). The size of a stable name is constant. (good).
           - Satisfies c). I don't think there is any issue with thread 
             contention.
           - I think stable names are part of the FFI, so should be portable.
             Better check this. However, I don't think they work with parallel
             Haskell at present. Is this important? Hard to say.
  
     Regarding the speed of each method: it is hard to say without measuring
     them on real programs. My intution is that Stable Names have some advantage
     in multi-threaded programs because they don't go via MVars (or maybe they
     do, if the stable name table is locked in the runtime - better check this).
     I'm also a bit concerned that Stable Names were not designed to support a very
     large number of objects, and so may perform badly on Python programs which
     allocate many objects. 
  -}
  