5. Behind the Scenes: Architecture of the stepper
Architectural Overview
The Substitution Stepper takes the user’s input as a file and passes it to the Glasgow Haskell Compiler to convert the Haskell Source file into the Haskell Core data type.
The stepper then produces the step by step reduction for the input expressions. Finally, the reduction result is printed to the output.
Some Words about the Glasgow Haskell Compiler and Haskell Core
Haskell code is often compiled with the Glasgow Haskell Compiler (GHC). The GHC does not directly convert Haskell Source Code into machine code but instead uses different intermediate formats: Haskell Code is first converted into Haskell Core, then into STG and then into machine code. Here is a visualization of those stages:
(Source: https://www.haskell.org/ghc/)
This Core data type is impressive as it contains only 10 constructors that can represent every Haskell program:
(Source: https://gitlab.haskell.org/ghc/ghc/blob/master/compiler/GHC/Core.hs)
The Haskell Substitution Stepper works with the code on a Core Level. It uses the GHC in the background to retrieve Core code from the input. However, if the verbosity levels 1 or 2 for the output are chosen, the output is printed in a format that looks like original Haskell code. The goal is to make the output easier to read for programmers who know Haskell Code but do not know Haskell Core code.
The main stepper loop
The heart of the Haskell Substitution Stepper is the function applyStep, defined in the stepper’s backend. It takes a single Core expression and a list of bindings, selects an applicable reduction rule and returns a reduced expression. This function is called repeatedly until the expression reaches head normal form.
The reduction rules
Because the GHC itself does the reduction of Haskell expressions on an STG-Level, the reduction rules for Haskell Core code are not standardized. Whenever possible, the stepper adheres to the rules of lazy evaluation and non-strict evaluation. With those limitations, a set of reduction rules was derived. Here is the list of reduction rules that the stepper has implemented.
Resolving functions
There are different ways how functions and types are defined in the stepper:
When the Haskell Substitution Stepper tries to resolve a function or type, it first checks if the user has provided an implementation for it in the input file.
If this is not the case, the stepper checks if the function or type is defined in the built-in Steppable Prelude. However, not every part of the original Haskell Prelude can be represented in Haskell code itself. (Imagine functions like sin or the type class Num for the type Int). Support for such „unsteppable“ functions is built into the backend of the stepper. If the stepper sees such a function which is not defined by the user itself and not part of the prelude, it uses an evaluate function which is defined in the backend. This evaluate function only supports a set of predefined functions and does not use dynamic loading of code which means it is safe to use.