PAKCS
Exported names: Imported modules:

Module Heap

This module defines a heap structure, containing bindings from variables to markers for free variables or black holes, or the expressions.

Author: Björn Peemöller

Version: May 2015

Summary of exported operations:

ppBinding :: Binding -> Doc   
Pretty printing of a heap binding
ppHeap :: [(Int,Binding)] -> Doc   
Show the heap in a human readable fashion.
emptyHeap :: [(Int,Binding)]   
Create an empty heap.
isEmptyHeap :: [(Int,Binding)] -> Bool   
Is the given heap empty?
elemHeap :: Int -> [(Int,Binding)] -> Bool   
Check if a binding exists for a variable in the given heap.
getHeap :: Int -> [(Int,Binding)] -> Binding   
Get the binding for a variable in the given heap or throw an error in case of a missing binding.
lookupHeap :: Int -> [(Int,Binding)] -> Maybe Binding   
Lookup a binding for a variable in the given heap.
bindHole :: Int -> [(Int,Binding)] -> [(Int,Binding)]   
Bind a variable as "baclk hole" to the given expression in the given heap.
bindExpr :: Int -> Expr -> [(Int,Binding)] -> [(Int,Binding)]   
Bind a variable to the given expression in the given heap.
bindFree :: Int -> [(Int,Binding)] -> [(Int,Binding)]   
Bind a variable as "free" in the given heap.
bindParam :: Int -> [(Int,Binding)] -> [(Int,Binding)]   
Bind a variable as an unbound parameter in the given heap.
bindLazyExpr :: Int -> Expr -> [(Int,Binding)] -> [(Int,Binding)]   
Bind a variable lazily to the given expression in the given heap.
bindLazyFree :: Int -> [(Int,Binding)] -> [(Int,Binding)]   
Bind a variable lazily as "free" in the given heap.
bindLazyParam :: Int -> [(Int,Binding)] -> [(Int,Binding)]   
Bind a variable lazily as an unbound parameter in the given heap.
unbind :: Int -> [(Int,Binding)] -> [(Int,Binding)]   
Remove any binding for the given variable in the given heap.
dereference :: [(Int,Binding)] -> Expr -> Expr   
Derefence any bindings in the given heap referred to by the given expression.
without :: [(Int,Binding)] -> [(Int,Binding)] -> [(Int,Binding)]   
Difference on heaps.

Exported datatypes:

Binding

A Binding represents the value of a variable bound in the heap.

Constructors:

  • BlackHole :: Binding : the variable is a black hole, such as in let x = x in x
  • BoundVar :: Expr -> Binding : the variable is bound to an expression e
  • LazyBound :: Expr -> Binding : the variable is bound to an expression e
  • FreeVar :: Binding : the variable is a logic (free) variable
  • LazyFree :: Binding : the variable is a lazily bound logic (free) variable
  • Param :: Binding : the variable is an unbound parameter variable
  • LazyParam :: Binding : the variable is a lazily bound parameter variable
Heap

A Heap is an association from a VarIndex to a binding (see below).

Type synonym: Heap = [(VarIndex,Binding)]

Exported operations:

ppBinding :: Binding -> Doc   

Pretty printing of a heap binding

ppHeap :: [(Int,Binding)] -> Doc   

Show the heap in a human readable fashion.

emptyHeap :: [(Int,Binding)]   

Create an empty heap.

Further infos:
  • solution complete, i.e., able to compute all solutions

isEmptyHeap :: [(Int,Binding)] -> Bool   

Is the given heap empty?

Further infos:
  • solution complete, i.e., able to compute all solutions

elemHeap :: Int -> [(Int,Binding)] -> Bool   

Check if a binding exists for a variable in the given heap.

getHeap :: Int -> [(Int,Binding)] -> Binding   

Get the binding for a variable in the given heap or throw an error in case of a missing binding.

lookupHeap :: Int -> [(Int,Binding)] -> Maybe Binding   

Lookup a binding for a variable in the given heap.

bindHole :: Int -> [(Int,Binding)] -> [(Int,Binding)]   

Bind a variable as "baclk hole" to the given expression in the given heap.

bindExpr :: Int -> Expr -> [(Int,Binding)] -> [(Int,Binding)]   

Bind a variable to the given expression in the given heap.

bindFree :: Int -> [(Int,Binding)] -> [(Int,Binding)]   

Bind a variable as "free" in the given heap.

bindParam :: Int -> [(Int,Binding)] -> [(Int,Binding)]   

Bind a variable as an unbound parameter in the given heap.

bindLazyExpr :: Int -> Expr -> [(Int,Binding)] -> [(Int,Binding)]   

Bind a variable lazily to the given expression in the given heap.

bindLazyFree :: Int -> [(Int,Binding)] -> [(Int,Binding)]   

Bind a variable lazily as "free" in the given heap.

bindLazyParam :: Int -> [(Int,Binding)] -> [(Int,Binding)]   

Bind a variable lazily as an unbound parameter in the given heap.

unbind :: Int -> [(Int,Binding)] -> [(Int,Binding)]   

Remove any binding for the given variable in the given heap.

dereference :: [(Int,Binding)] -> Expr -> Expr   

Derefence any bindings in the given heap referred to by the given expression. That is, the bindings of all variables in the expression are extracted from the heap and inserted into the heap as recursive let expressions. This operation preserves sharing by determining the smallest sub-expression which contains all references to a specific variable.

For example, consider the heap @h = [x -> 1, y -> free]@.

For this heap, the following equations hold:

without :: [(Int,Binding)] -> [(Int,Binding)] -> [(Int,Binding)]   

Difference on heaps.