% Implementing Pointer Algorithms in Haskell
% Péter Diviánszky
% CEFP, Budapest & Komárno, 25-30 May 2009
#
The code and the slides can be found as
`linear-maps` on
[http://hackage.haskell.org](http://hackage.haskell.org/packages/archive/pkg-list.html).
# Pointers
- Pointers are well known.
- They are called mutable variables in functional languages.
- Some algorithms use them heavily.
- Pointers can be modeled with a global store (heap).
- Efficient implementation on CPU and memory.
- Hard to find a stateless / modular model for them.
- This would be the functional way.
# Pointers in C
~~~~~~~~~~~~~~~~~ {.c}
void swap(int *x, int *y) {
int xv = *x; // read
int yv = *y;
*x = yv; // write
*y = xv;
}
int main() {
int a = 13;
int b = 14;
swap(&a, &b); // references
printf("%d, %d", a, b);
return 0;
}
~~~~~~~~~~~~~~~~~
# Pointers in OCAML
~~~~~~~~~~~~~~~~~ {.ocaml}
let swap x y =
let vx = !x (* read *)
and vy = !y in
x := vy; (* write *)
y := vx;;
let a = ref 13;; (* reference *)
let b = ref 14;;
swap a b;;
~~~~~~~~~~~~~~~~~
Primitives:
~~~~~~~~~~~~~~~~~ {.ocaml}
ref : 'a -> 'a ref
(!) : 'a ref -> 'a
(:=) : 'a ref -> a -> unit
~~~~~~~~~~~~~~~~~
# Pointers in Haskell
~~~~~~~~~~~~~~~~~ {.haskell}
swap :: IORef a -> IORef a -> IO ()
swap x y = do
vx <- readIORef x
vy <- readIORef y
writeIORef x vy
writeIORef y vx
~~~~~~~~~~~~~~~~~
Primitives:
~~~~~~~~~~~~~~~~~ {.haskell}
newIORef :: a -> IO (IORef a)
readIORef :: IORef a -> IO a
writeIORef :: IORef a -> a -> IO ()
~~~~~~~~~~~~~~~~~
Side effects are properly indicated with `IO` in types.
# ST Pointers in Haskell
`STRef`s are more safe than `IORef`s because they need less privileges.
~~~~~~~~~~~~~~~~~ {.haskell}
swap :: STRef s a -> STRef s a -> ST s ()
swap x y = do
vx <- readSTRef x
vy <- readSTRef y
writeSTRef x vy
writeSTRef y vx
~~~~~~~~~~~~~~~~~
Primitives:
~~~~~~~~~~~~~~~~~ {.haskell}
newSTRef :: a -> ST s (STRef s a)
readSTRef :: STRef s a -> ST s a
writeSTRef :: STRef s a -> a -> ST s ()
~~~~~~~~~~~~~~~~~
# ST Pointers in Haskell (continued)
Imperative style Fibonacci function:
~~~~~~~~~~~~~~~~~ {.haskell}
fib :: Integer -> ST s Integer
fib n = do
a <- newSTRef 0
b <- newSTRef 1
replicateM_ n $ do
av <- readSTRef a
bv <- readSTRef b
writeSTRef a bv
writeSTRef b (av + bv)
readSTRef a
~~~~~~~~~~~~~~~~~
# ST Pointers in Haskell (continued)
Note that the return type of the `ST` computation does not depend on `s`:
~~~~~~~~~~~~~~~~~ {.haskell}
fib :: Integer -> ST s Integer
~~~~~~~~~~~~~~~~~
In this case the `ST` computation can be turned into a pure value:
~~~~~~~~~~~~~~~~~ {.haskell}
runST :: (forall s. ST s a) -> a
~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~ {.haskell}
fib' :: Integer -> Integer
fib' n = runST (fib n)
~~~~~~~~~~~~~~~~~
In that way pointers can be used in a pure function.
Still, we need a strictly scheduled computation inside.
# Other Direction: Pointers in Clean
~~~~~~~~~~~~~~~~~ {.clean}
swap :: (Ptr a) (Ptr a) *Heap -> *Heap
swap x y h1 = h5
where
(vx, h2) = readPtr x h1
(vy, h3) = readPtr y h2
h4 = writePtr x vy h3
h5 = writePtr y vx h4
~~~~~~~~~~~~~~~~~
Primitives:
~~~~~~~~~~~~~~~~~ {.clean}
newPtr :: a *Heap -> (Ptr a, *Heap)
readPtr :: (Ptr a) *Heap -> (a, *Heap)
writePtr :: (Ptr a) a *Heap -> *Heap
~~~~~~~~~~~~~~~~~
# Problems with Explicit Heap
The previous pointer interface is
- Typed.
- Functional.
However, an explicit heap value should be carried through the program
which determines the evaluation order overly.
The result is an imperative program in a functional guise.
# Improvement: Interchangeable Pointer Reads
Reading a pointer does not alter the heap but it have to be done in time:
~~~~~~~~~~~~~~~~~ {.clean}
swap :: (Ptr a) (Ptr a) *Heap -> *Heap
swap x y h
#! vx = sreadPtr x h
vy = sreadPtr y h
= writePtr y vx (writePtr x vy h)
~~~~~~~~~~~~~~~~~
New primitive:
~~~~~~~~~~~~~~~~~ {.clean}
sreadPtr :: (Ptr a) Heap -> a
~~~~~~~~~~~~~~~~~
Note that `Heap` is a subtype of `*Heap`.
# Improvement: Typed Heaps
An `Int`-pointer read and a `Char`-pointer write may be interchanged safely.
This is modeled with typed heaps.
Primitives (as used in the Clean compiler sources):
~~~~~~~~~~~~~~~~~ {.clean}
newHeap :: .(Heap a)
newPtr :: a *(Heap a) -> (Ptr a, *(Heap a))
readPtr :: (Ptr a) *(Heap a) -> (a, *(Heap a))
sreadPtr :: (Ptr a) (Heap a) -> a
writePtr :: (Ptr a) a *(Heap a) -> *(Heap a)
~~~~~~~~~~~~~~~~~
Still a problem: Reading a `Ptr Char` in a `Heap Char` fails if the pointer was constructed in another `Heap Char`.
# Improvement: Use the ST Pointer Trick
We distinguish between different `Heap Char` values by adding a phantom type variable: `Heap k Char`.
~~~~~~~~~~~~~~~~~ {.haskell}
newPtr :: a -> Heap k a -> (Ptr k, Heap k a)
sreadPtr :: Ptr k -> Heap k a -> a
writePtr :: Ptr k -> a -> Heap k a -> Heap k a
~~~~~~~~~~~~~~~~~
Note that the interface use `Ptr k` instead of `Ptr k a` because `a` is not needed.
If the result of a heap-consuming computation does not contain the phantom typevar then we get a heap for free:
~~~~~~~~~~~~~~~~~ {.haskell}
runHCC :: (forall k. Heap k a -> b) -> b
~~~~~~~~~~~~~~~~~
# Coming from Another Direction: Finite Maps
Finite maps are functions with finite domain.
Related phrases: dictionary (Python), hash (Perl), association list.
~~~~~~~~~~~~~~~~~ {.haskell}
empty :: Map k a
lookup :: Ord k => k -> Map k a -> Maybe a
insert :: Ord k => k -> a -> Map k a -> Map k a
delete :: Ord k => k -> Map k a -> Map k a
~~~~~~~~~~~~~~~~~
We will need an additional function:
~~~~~~~~~~~~~~~~~ {.haskell}
modify :: Ord k => k -> Maybe a -> Map k a -> Map k a
modify k Nothing m = delete k m
modify k (Just a) m = insert k a m
~~~~~~~~~~~~~~~~~
# Finite Maps vs Heaps
`Heap k (Maybe a)` ~ `Map (Id k) a`
~~~~~~~~~~~~~~~~~ {.haskell}
newtype Id k = Id Int deriving (Eq, Ord)
~~~~~~~~~~~~~~~~~
We allow only `Maybe`-typed heaps, so we can use an interface similar to finite maps.
# Pointers with Finite Map Interface
`Map` here is the abstract heap (not a finite map):
~~~~~~~~~~~~~~~~~ {.haskell}
lookup :: Id k -> Map k a -> Maybe a
insert :: Id k -> a -> Map k a -> Map k a
delete :: Id k -> Map k a -> Map k a
~~~~~~~~~~~~~~~~~
Instead of including `newPtr`, pointers are created with the map (this decison pays back later):
~~~~~~~~~~~~~~~~~ {.haskell}
runICC :: (forall k. Map k a -> [Id k] -> b) -> b
~~~~~~~~~~~~~~~~~
`runICC` runs an identifier consuming computation, which receives a map (heap) and an infinite list of identifiers (pointers)
allowed to be used with that map.
# Use Case: Doubly Linked Lists
~~~~~~~~~~~~~~~~~ {.haskell}
data DList k a
= Empty
| NonEmpty
{ first :: Id k
, last :: Id k
, nodes :: Map k (DListNode k a)
}
data DListNode k a =
{ previous :: Maybe (Id k)
, next :: Maybe (Id k)
, value :: a
}
(<|) :: a -> DList k a -> Id k -> DList k a
(|>) :: DList k a -> a -> Id k -> DList k a
~~~~~~~~~~~~~~~~~
# Use Case: Doubly Linked Lists (v2)
It is a problem that at insertions free `Id`s are needed.
This new version solves that problem:
~~~~~~~~~~~~~~~~~ {.haskell}
data DList k a
= Empty
| NonEmpty
{ first :: Id k
, last :: Id k
, nodes :: Map k (DListNode k a)
, freeIds :: [Id k] -- stored free Ids
}
(<|) :: a -> DList k a -> DList k a
(|>) :: DList k a -> a -> DList k a
~~~~~~~~~~~~~~~~~
# Use Case: Doubly Linked Lists (v3)
This version simplifies the creation of `DList`s:
~~~~~~~~~~~~~~~~~ {.haskell}
data DList a
= Empty
| forall k . NonEmpty -- encapsulated heap
{ first :: Id k
, last :: Id k
, nodes :: Map k (DListNode k a)
, freeIds :: [Id k]
}
singleton :: a -> DList a
(<|) :: a -> DList a -> DList a
(|>) :: DList a -> a -> DList a
~~~~~~~~~~~~~~~~~
# Use Case: Doubly Linked Lists (v3, continued)
Code for `singleton`:
~~~~~~~~~~~~~~~~~ {.haskell}
singleton :: a -> DList a
singleton x = runICC $ \emptyMap (firstId: otherIds) ->
NonEmpty
{ first = firstId
, last = firstId
, nodes = insert firstId x emptyMap
, freeIds = otherIds
}
~~~~~~~~~~~~~~~~~
But `DList`s can not be joined because if we open two `NonEmpty` values, the phantom variables can not be unified by the type system (which is right).
# Improvement: Identifier Subtyping
If `k1` ≠ `k2` then `Id k1` can not be used instead of `Id k2`.
This is right, because this type variables marks "different regions of memory".
But sometimes memory regions should be joined.
`Id (k1 :|: k2)` is the joined set of `Id k1` and `Id k2`.
`:|:` is an infix type constructor with kind `* -> * -> *`:
~~~~~~~~~~~~~~~~~ {.haskell}
data (a :|: b)
-- no constructors
~~~~~~~~~~~~~~~~~
# Identifier Subtyping (continued)
`Id (k1 :|: k2)` is the joined set of `Id k1` and `Id k2`.
A value with type `Id k1` is acceptable when a value with type `Id (k1 :|: k2)` is needed.
In other words, `Id k1` is a subtype of `Id (k1 :|: k2)`.
There is no subtyping in Haskell so we use explicit conversion functions:
~~~~~~~~~~~~~~~~~ {.haskell}
left :: Id k1 -> Id (k1 :|: k2)
right :: Id k2 -> Id (k1 :|: k2)
~~~~~~~~~~~~~~~~~
One can join two maps (two heaps or two "memory regions") with `union`:
~~~~~~~~~~~~~~~~~ {.haskell}
union :: Map k1 a -> Map k2 a -> Map (k1 :|: k2) a
~~~~~~~~~~~~~~~~~
# Use Case: Doubly Linked Lists (v4)
A simplification first: the `freeIds` field is not needed because any number of
free `Id`s can be obtained by joining a new "memory region":
~~~~~~~~~~~~~~~~~ {.haskell}
data DList a
= Empty
| forall k . NonEmpty
{ first :: Id k
, last :: Id k
, nodes :: Map k (DListNode k a)
-- , freeIds :: [Id k] -- not needed
}
~~~~~~~~~~~~~~~~~
# Use Case: Doubly Linked Lists (v4, continued)
~~~~~~~~~~~~~~~~~ {.haskell}
(><) :: DList a -> DList a -> DList a
Empty >< y = y
x >< Empty = x
x >< y = NonEmpty
{ first = left (first x)
, last = right (last y)
, nodes = ... (fmap left (nodes x)
`union` fmap right (nodes y))
}
~~~~~~~~~~~~~~~~~
`...` contains code which redirects
`next (last x)` to `first y` and
`previous (first y)` to `(last x)`.
# Improvement: Split Maps
Redirecting `next (last x)` to `first y` is complicated because a `DListNode` record have to be updated.
This could be improved if three different maps were used for `previous`, `next` and `value` values.
But a pointer can only point to one object.
Solution: Maps are tagged with type-level integers.
A pointer can be a key in several maps with different integers.
We will use `(Map I0 k a, Map I1 k b, Map I2 k c)`
instead of `Map k (a, b, c)`.
# Improvement: Split Maps (continued)
To understand the implementation:
The finite map `Map i k a` represents a scattered memory fragment with the following properties:
- The memory fragment contains an `a`-typed values.
- The pieces of the memory fragment are some record's `i`th field.
- `i` is a type-level integer (`I0`, `I1`, `I2`, ... in the implementation).
- The records need not have the same type.
- `k` is an additional tag (for example, to separate two doubly linked lists)
# Use Case: Doubly Linked Lists (v5)
~~~~~~~~~~~~~~~~~ {.haskell}
data DList a
= Empty
| forall k . NonEmpty
{ first :: Id k
, last :: Id k
, previous :: Map I0 k (Id k)
, next :: Map I1 k (Id k)
, value :: Map I2 k a
}
~~~~~~~~~~~~~~~~~
# Creation of Split Maps
Basic solution: There are a family of functions
~~~~~~~~~~~~~~~~~ {.haskell}
runICC1 :: (forall k. Map I0 k a -> [Id k] -> b) -> b
runICC2 :: (forall k. Map I0 k a -> Map I1 k a -> [Id k] -> b) -> b
runICC3 :: (forall k. Map I0 k a -> Map I1 k a -> Map I2 k a -> [Id k] -> b) -> b
...
~~~~~~~~~~~~~~~~~
Instead of that, the current implementation use a variant of the function
~~~~~~~~~~~~~~~~~ {.haskell}
runICC :: (forall k. Maps i k -> [Id k] -> b) -> b
~~~~~~~~~~~~~~~~~
where `Maps` is a GADT which can be unfolded into `i` maps.
# Conclusion / Efficiency
The implementation is as efficient as if mutable references were used:
- `Map`s are not present in the generated code (for example, `NonEmpty` has two fields).
- `Id`s are replaced by pointers to records (arrays actually).
TODOs:
- The implementation has to be reviewed.
- The `Maybe`s still cause some performance loss.
# Conclusion / Safety
Guarantees by the type system:
- Pointers are typed (by the type of the pointed value).
- Pointers can not escape their scope.
- Pointer in "different regions" can not be exchanged by accident.
TODOs:
- Linear use is checked *only in runtime*.
- This is a big disadvantage.
- Should be checked statically, which needs at least annotated types and a strictness analyzer.
# Conclusion / Usability
Pros:
- Highly functional interface (similar to finite maps).
- Less strict evaluation order (more possibility to parallel execution).
- One can virtually join `i`th fields of different records (if the `i`th fields has the same type).
Cons:
- Linear use should be obeyed.
- Creation of maps is a bit uncomfortable (maps has to be carried).
# Conclusion / Semantics
The library has a simple semantics.
This is demonstrated by a small pure functional implementation of the interface functions.
# Further Extensions
Sets can be modeled as maps to unit values.
- The current implementation is more efficient than that: 32 sets are packed into 1 integer map.
- The interface of sets and maps are unified.
Identifiers can refer to static data.
For example, if a sequence is implemented by a doubly linked map,
`previous` and `next` are mutable but `value` is static. So two maps are sufficient.
# Related Work
- [DDC](http://www.haskell.org/haskellwiki/DDC), The Disciplined Disciple Compiler
- An explicitly lazy dialect of Haskell.
- Supports destructive update, computational effects, type directed field projections.
- [Monadic Regions](http://okmij.org/ftp/Haskell/regions.html)
- A technique for managing resources (memory areas, file handles, database connections).
# Forthcoming Use Cases
- Graph walks.
- with tagging
- with pointer reversal
- Strongly connected components computation.
- Linear time type inference algorithm with pointers.
# Thanks
Thanks for your attention!