LiquidHaskell Documentation

The verification process follows a specific lifecycle to transform source code into verified specifications:

1. Inputs: The process takes CoreBinds, BareSpecs, and LiftedDeps (dependencies of the module including their LiftedSpecs).
2. Transformation:
   • A TargetSpec is produced, which generates Verification Constraints.
   • These constraints are checked by liquid-fixpoint.
3. Outputs:
   • If verified, a LiftedSpec is produced and serialized into the module's interface file (.hi).

A [zipper][wiki-zipper] is an aggregate data structure used to traverse and update a structure arbitrarily. It consists of three parts:

1. focus: The element currently being used.
2. up: A list of elements located before the current focus (to the left).
3. down: A list of elements located after the current focus (to the right).

In applications like the XMonad tiling window manager, a zipper can represent a set of windows where the focus is the active window, and up/down represent the preceding and succeeding windows. A common invariant for such structures is uniqueness: every element in the zipper must appear exactly once.

A standard implementation of quickSort may fail LiquidHaskell verification if the ++ (append) operator is typed as a simple IncrList a -> IncrList a -> IncrList a, because appending two sorted lists does not necessarily result in a sorted list (e.g., [1, 2, 4] ++ [3, 5, 6] is not increasing).

To fix this, you cannot use the standard ++ operator. Instead, you must implement a specialized 'pivot-append' function. This function leverages the extra information available during Quick Sort: the existence of a pivot element x such that all elements in the first list are less than x, and all elements in the second list are greater than or equal to x. This specialized function allows LiquidHaskell to verify that the resulting concatenated list remains an IncrList.

Liquid Haskell uses a mechanism called reflection to provide logic meaning to Haskell functions used within formal specifications. When you write a specification in a comment {-@ ... @-}, Liquid Haskell must resolve the names in the predicate to their logic equivalents.

For example, in the specification {-@ filter :: p:(a -> Bool) -> xs:[a] -> {v:[a] | all p v } @-}, Liquid Haskell identifies p and v from the function parameters, but it must use reflection to understand what all means by looking it up in the Prelude.

LiquidHaskell can automatically infer refinement types for local helper functions (like go in a recursive loop) to establish safety properties.

In the context of vector processing, LiquidHaskell uses the relationship between the loop index i, the termination condition n, and the vector length vlen vec to prove that an index is always valid. If you modify the logic—for example, by removing a check like 0 < n or changing a guard to i <= n—LiquidHaskell will flag the program as unsafe because it can no longer guarantee that the index remains within the valid bounds of the vector.

The project uses the following directory structure:

• css/: Core styles required for the project to function.
• js/: Core JavaScript files.
• plugin/: Extensions and components developed for reveal.js.
• lib/: Third-party assets including JavaScript, CSS, and fonts.

Measures

Measures define auxiliary or ghost properties of data values. They are used for specification and verification but do not exist at runtime. They appear only inside type refinements. You can use helper functions like length to "materialize" these ghost values into the actual code world.

Assumes

The assume keyword is used when you are not verifying the implementation of a library (like Data.Vector) but are instead using its properties to verify your own client code. If you were verifying the library itself, you would ascribe these types directly to the library's source code instead of using assume.

Fragments allow you to step through individual elements on a slide. Any element with the class fragment will be hidden initially and revealed sequentially.

Fragment Styles

Append a class to fragment to change its behavior:

• fragment grow: Grows the element.
• fragment shrink: Shrinks the element.
• fragment roll-in: Rolls the element in.
• fragment fade-out: Fades the element out.
• fragment visible: Shows the element only once.
• fragment highlight-red / highlight-blue / highlight-green: Highlights the element in a specific color.

Controlling Order

Use data-fragment-index="N" to specify the exact order in which fragments appear.

<section>
	<p class="fragment" data-fragment-index="3">Appears last</p>
	<p class="fragment" data-fragment-index="1">Appears first</p>
	<p class="fragment" data-fragment-index="2">Appears second</p>
</section>

When writing LiquidHaskell specifications, complex logical constraints (like checking if an index is within the bounds of a vector) can become verbose and difficult to read. You can use predicate aliases to create reusable, named abstractions for these logical patterns.

To define a predicate alias, use the predicate keyword within a LiquidHaskell comment block ({-@ ... @-}). This allows you to compose complex logic into a single, readable name that can then be used in refinement types.

For example, instead of manually conjoining lower and upper bound checks every time you access a vector, you can define an InBounds predicate.

Dependent Pairs are expressed by binding the initial elements of the tuple. This allows the type of the second element to depend on the value of the first. Internally, these desugar to abstract refinement types.

{-@ incrPair :: Int -> (x::Int, {v:Int | x <= v}) @-}
incrPair i = (i, i+1)