Comparing objects by memory location in Haskell

Recently I needed to compare two objects for memory equivalence in Haskell. That is, I was looking for a function like:

isMemoryEquivalent :: a -> a -> Bool

The first thing you might ask is: “why the hell are you doing this in Haskell?”. And your surprise is understandable. However, once in a while a project requires you lower the level and go dirty =P.

I was writing a Scheme interpreter (which will be the subject of a post soon) and this need came out in the equal? built-in procedure implementation. This procedure checks if two Scheme objects can be regarded as the same, i.e., if they are equivalent. It’s not difficult to see that this is extremely difficult for procedures (in fact, it’s impossible in the general case).

For example, try to think about an efficient algorithm to compare the following procedures:

(define (succ1 x)
  (+ x 1))

(define (succ2 x)
  (- (+ x 2) 1))

One possibility is to check if the domains of succ1 and succ2 are the same. If this was the case, you could evaluate succ1 and succ2 over the domain and compare the results. But this is a naïve approach seldom possible in practice. It assumes the domains can be known (in dynamic typed languages such as Scheme this is impossible). And even if the domains can be known, it should be finite (or practically finite), which is almost always not true. Think about float numbers, arbitrary precision integers, tree-like data structures, etc. Not to mention the efficiency problems that arise when the procedures are costly, e.g., a factorial procedure. Well, this is not exactly new if you know a bit about theory of computation, but think about it concretely makes it clear.

The alternative is relax the definition of the equal? procedure: two procedures are said to be equal if they are stored in the same memory location (their memory pointers are equal). That is, (equal? (lambda (x) x) (lambda (x) x)) must return #f.

But there isn’t native pointers in Haskell. To implement this behavior in the interpreter I need to use the extension infrastructure of the Haskell environment. In my case, the Haskell environment is the excellent GHC compiler and the suitable infrastructure is the Foreign module. Using it, I can implement isMemoryEquivalent as follows:

import Foreign

isMemoryEquivalent :: a -> a -> IO Bool
isMemoryEquivalent obj1 obj2 = do
    obj1Ptr <- newStablePtr obj1
    obj2Ptr <- newStablePtr obj2
    let result = obj1Ptr == obj2Ptr
    freeStablePtr obj1Ptr
    freeStablePtr obj2Ptr
    return result

It’s quite easy to understand this code snippet. It acquires the pointers to the objects, compares, and releases them. This acquire/release process is needed because the garbage collector is free to move objects through memory, invalidating pointers. So, first the object of interest must be locked in a safe memory location before going any further and released at the end. This is accomplished by the Foreign module functions newStablePtr and freeStablePtr, respectively. Another important point to note is the use of the IO monad since pointer operations can be viewed as a kind of IO.

This is quite a specific topic, but it’s instructive about how you can lower the level with Haskell. One interesting thing is that a low level in Haskell is indeed very high =P. Anyway… kids, don’t try this without adult supervision, ok? =P