Haskell Interop

Fixen generates Haskell source code, which means it lives in the Haskell ecosystem. You can define types, type classes, and functions in Haskell and use them directly in your Fixen programs. This chapter covers how to embed Haskell in Fixen, how the generated module works, and how to integrate Fixen-generated code into your projects.

Figure 1 shows the overall workflow of developing Haskell projects with Fixen. We have been following this process in the complete examples shown previously:

1. Write a Fixen program, declaring sorts (lat and/or partial ord), relations, rules, priorities, phases, potentially include-ing other Fixen programs.
2. Compile the Fixen program into a Haskell module using the Fixen compiler, fixen.
3. Write the surrounding Haskell application code that makes use of the generated module. The generated module can be a small part of the overall program, just like how a compiler may use a happy-generated parser as part of a complete compiler.
4. Compile the overall Haskell project using your favourite Haskell compiler, e.g., GHC.
5. Win!

Figure 1. Developing with Fixen.

Using Haskell Definitions in Fixen Programs

Wrap Haskell code in triple backticks with the hs language annotation:

```hs
type Vertex = String
distMlbs :: Natural -> Natural -> [Natural]
distMlbs x y = if x <= y then [y] else [x]
```

The contents of Haskell blocks are included verbatim in the generated Haskell module.

You can import Haskell modules using the import keyword:

import Numeric.Natural
import Data.HashMap.Strict

These imports are included at the top of the generated Haskell module, making the imported symbols available in your Fixen program.

The Generated Module

The Fixen compiler generates a self-contained Haskell module. Understanding its structure helps you integrate Fixen into your projects.

Figure 2 illustrates the workflow of application code working with Fixen-generated modules:

1. The generated module consists of a Fact datatype which allows application code and the fixed-point solver to instantiate facts. Application code starts by initializing the solver with initial facts, treated as premiseless (phase ) rules, i.e., an initial fact F is treated as a rule rule: |- F in the program.
2. The generated module consists of two functions: solve and reSolve. These functions perform the actual fixed-point computation based on the specification defined in the Fixen program. solve performs fixed-point computation with initial facts and the empty database.
3. The result of solve (and reSolve) is a database (for single-phase programs) or an interpretation (an tuple of fact databases, where is the number of phases in the program).
4. Application code performs queries (generated from query declarations) on the solved fact database, obtaining facts.
5. Given an interpretation/database, we can add more facts and perform further fixed-point computation with reSolve, from which we can perform more queries and more reSolves as desired.

Figure 2. How application code can use Fixen-generated modules.

Data Types

The compiler generates these primary data types:

• Fact — a sum type with one constructor per relation. Each constructor’s arguments use the underlying Haskell types of the relation’s sorts.
• Database — a record type with one field per relation. Fields are nested HashMaps optimized for the relation’s usage patterns (discrete matched arguments serve as primary keys).
• Interpretation — a type alias representing a tuple of Databases. These are generated only for multi-phase Fixen programs.
• Phase — a data type representing the possible phases of a program, used for queries.

For instance, the generated data types for facts, databases and interpretations and phase selectors for the reduced product of the interval and parity analyses are as follows:

data Fact = Assign Label String Expr
          | Branch Label Expr Label Label
          | Seq Label Label
          | StateBeforeI Label (HashMap String Interval)
          | StateBeforeP Label (HashMap String Parity)
          | Var Label String
  deriving (Show, Eq)

data Database = Database
  { _factsAssign :: HashMap Label (HashMap String (HashSet Expr))
  , _factsBranch :: HashMap Label (HashMap Expr (HashMap Label (HashSet Label)))
  , _factsSeq :: HashMap Label (HashSet Label)
  , _factsStateBeforeI :: HashMap Label (HashMap String Interval)
  , _factsStateBeforeP :: HashMap Label (HashMap String Parity)
  , _factsVar :: HashMap Label (HashSet String)
  } deriving Eq

type Interpretation = (Database, Database)

data Phase = Phase0 | Phase1 deriving (Eq, Show, Ord)

Note that the Database type may re-order relation sorts for performance purposes.

Core Functions

Function	Signature	Purpose
solve	[Fact] -> Database	Compute the fixed point from initial facts
reSolve	Database -> [Fact] -> Database	Resume computation with additional facts

solve takes a list of initial facts (treated as body-less rules) and returns the solved database. reSolve resumes fixed-point computation from an already-solved database with new facts, enabling incremental updates.

These functions for the reduced product of the interval and parity analyses are as follows. Note that the conclusion of premiseless rules declared in the Fixen program are also included in the reSolve queue.

solve :: [Fact] -> Interpretation
solve = reSolve emptyInterpretation

reSolve :: Interpretation -> [Fact] -> Interpretation
reSolve i f =
  let q = Q.fromList $ concat [
            (,Phase1) . Init <$> f
          ]
   in loop q i

Query Functions

For each query declaration, the compiler generates a Haskell function. The function’s parameters correspond to the input-mode arguments of the query, and the return type contains the output-mode facts.

stateBeforeP :: Label -> Interpretation -> Phase -> [Fact]
stateBeforeP _v0_0 i p = do
  let db = selectDb i p
  step0 <- maybeToList (_factsStateBeforeP db HashMap.!? _v0_0)
  let _v1_0 = step0
  return $ StateBeforeP _v0_0 _v1_0

stateBeforeI :: Label -> Interpretation -> Phase -> [Fact]
stateBeforeI _v0_0 i p = do
  let db = selectDb i p
  step0 <- maybeToList (_factsStateBeforeI db HashMap.!? _v0_0)
  let _v1_0 = step0
  return $ StateBeforeI _v0_0 _v1_0

Module Declarations

Every Fixen program starts with a Haskell module declaration:

module MyProject.ShortestPath where

This determines the name of the generated Haskell module. The module name must be a valid Haskell module path (dot-separated identifiers).

Including Other Fixen Files

The include statement imports another Fixen program, bringing in all its relations, rules, Haskell blocks, and imports, sort declarations and queries:

include "Common"
include "../Analysis/Interval"

Included files are processed recursively. Note that priorities and phases are not inherited from included files—each program defines its own. This is because priorities and phase assignments are specific to the local program, and is likely overridden when more rules are added in the including program.

Summary

• Haskell blocks (```hs) embed arbitrary Haskell code in Fixen programs.
• Imports make external Haskell modules available to the generated code.
• The generated module primarily exports Fact, Phase, solve, reSolve, and query functions.
• Include statements compose Fixen programs from multiple files.
• The generated code is a self-contained Haskell module that can be integrated into larger projects.