Optimizing bracket abstraction for Combinator Reduction

Abstract

In this post I will show how to significantly improve the performance of combinator based reducers by using a alternative abstraction algorithms. These algorithms are based on the paper λ to SKI, Semantically by Oleg Kiselyov and closely follow Ben Lynn’s implementation of Kiselyov’s ideas.

I will also give detailed comparisons of the different approaches regarding the size of the emitted code and execution performance on different reducers.

Introduction

In previous blog posts I have shown how functional languages can be implemented using a small set of combinators.

The first post, Implementing a functional language with Graph Reduction described an approach that sets up three major components:

• A parser for a tiny functional language based on the untyped λ-calculus.

• A compiler from λ-calculus to a fixed set of combinatory logic combinators (S,K,I,B,C and Y (aka. SICKBY)). This compiler uses traditional bracket abstraction algorithms to encode λ-terms as combinators.

• A graph-reduction engine which implements the combinator rewrite rules as an efficient graph reduction

In the second post, Evaluating SKI combinators as native Haskell functions, I showed how the combinators can be implemented as native Haskell functions. This allows to evaluate the combinators directly in Haskell without the need for a graph reduction engine.

The parser and the compiler of the first post could be reused without any changes. I just had to plug in a different execution engine. This time based on native Haskell functions instead of graph reduction.

I also did some performance measurements and found that the version using native Haskell functions is about 10-100 times faster than the graph reduction engine.

Another significant finding was that the performance of functions with two or more arguments was significantly worse than the performance of functions with one argument.

This is caused by the inefficient code generation of the classic bracket abstraction: The output size grows quadratic with internal complexity and number of variables. As each additional combinator or application will require additional execution time it’s easy to see why a quadratic growth in combinator code size will drastically decrease performance. There have been many attempts to optimize bracket abstraction by introducing additional combinators and by applying additional optimization rules.

In the present post I will show how to significantly improve the performnce by using an alternative abstraction algorithm. This algorithm is based on the paper Optimizing bracket abstraction by Oleg Kiselyov.

My implementation closely follows Ben Lynn’s implementation of Kiselyov’s algorithm in his blog post. I have made only minor changes to make the code more readable and to make it work with the parser and compiler of the first post.

From λ-calculus to combinators

My parser can parse programs of a very rudimentary language that is basically just pure λ-calculus plus integers. Here is an example:

sqr  = λx. * x x
main = sqr 3

The parser will produce an environment of top-level definitions from this program:

[("sqr",Lam "x" (App (App (Var "*") (Var "x")) (Var "x"))), 
 ("main",App (Var "sqr") (Int 3))]

Data types for λ-expressions and the environment are defined as follows:

data Expr
  = App Expr Expr
  | Var String
  | Int Integer
  | Lam String Expr
  deriving (Eq, Show)

type Environment = [(String, Expr)]

Now we can define a compiler that translates such λ-expressions to combinator terms. (You will find the complete code in Kiselyov.hs

Our journey begins by translating λ-expressions to a data type DB which is quite similar to the λ-calculus terms but uses indices instead of variable names. This is done by the function deBruijn:

data Peano = Succ Peano | Zero deriving Show
data DB = N Peano | L DB | A DB DB | Free String | IN Integer deriving Show

deBruijn :: Expr -> DB
deBruijn = go [] where
  go binds = \case
    Var x -> maybe (Free x) N $ index x binds
    Lam x t -> L $ go (x:binds) t
    App t u -> A (go binds t) (go binds u)
    Int i -> IN i  

index :: Eq a => a -> [a] -> Maybe Peano
index x xs = lookup x $ zip xs $ iterate Succ Zero    

Lets see how this works on a simple main functions:

  let source = "main = λx y. * x y"
  let env = parseEnvironment source
  putStrLn "The parsed environment of named lambda expressions:"
  mapM_ print env
  putStrLn ""
  putStrLn "The main expression in de Bruijn notation:"
  mapM_ (print . Data.Bifunctor.second deBruijn) env

This will produce the following output:

The parsed environment of named lambda expressions:
("main",Lam "x" (Lam "y" (App (App (Var "*") (Var "x")) (Var "y"))))

The main expression in de Bruijn notation:
("main",L (L (A (A (Free "*") (N (Succ Zero))) (N Zero))))

It’s easy to see that the de Bruijn notation is just a different representation of the λ-term. The only difference is that the variable names are replaced by indices. The innermost lambda-abstraction binds the variable y which is represented by the index Zero. The next lambda-abstraction binds the variable x which is represented by the index Succ Zero. This notation is quite helpful as it allows to systematically adress variables by their respective position in a complex term.

But why are we using Peano numbers for the indices? Why not just use integers? Well it’s definitely possible to use integers as indices. But there is a good reason to use Peano numbers in our case: In the subsequent compilation steps we want to be able to do pattern matching on the indices. This is possible with Peano numbers, because they are defined as an algebraic data type:

data Peano = Succ Peano | Zero

Starting with the de Bruijn notation Ben Lynn’s implementation of Kiselyov’s algorithm builds up a series of six increasingly optimized compilers that translate λ-expressions to combinator terms:

• a plain compiler without any optimizations (compilePlain)
• a compiler that implements K-optimization (compileK)
• a compiler that implements K- and Eta-optimization (compileEta)
• a compiler that generates code with Bulk Combinators (compileBulk)
• a compiler that eliminates Bulk Combinators with linear size(compileBulkLinear)
• a compiler that eliminates Bulk Combinators with logarithmic size(compileBulkLog)

I’ll don’t want to go into all the details of the algorithms. Ben’s blog post is a great resource for this. I’ll just give a brief overview of the compilation outputs of the different compilers. And then I’ll focus on performance comparisons between the different approaches. I will use my original compiler compileBracket based on the classic (recursively optimized) bracket abstraction as a baseline for the performance comparisons.

The simple main example

main = λx y. * x y

From this simple example it’s obvious that compilePlain and compileK generate a lot of redundant code. All the other compilers generate the same output as the baseline.

In order to have a simple metric for quality of the code generation I am showing the code size of the generated code for each compiler. The code size is measured in the number of emitted combinators. The codeSize function is defined as follows:

codeSize :: CL -> Int
codeSize (Com _) = 1
codeSize (INT _) = 0
codeSize (t :@ u) = codeSize t + codeSize u

Please also note that the Kiselyov algorithms may emit code for an additional R combinator with the following reduction rule:

R f g x = g x f  

The factorial function

fact = y(λf n. if (is0 n) 1 (* n (f (sub1 n))))
main = fact 100

-- in de Bruijn Notation
("fact", A (Free "y") (L (L (A (A (A (Free "if") (A (Free "is0") (N Zero))) (IN 1)) (A (A (Free "*") (N Zero)) (A (N (Succ Zero)) (A (Free "sub1") (N Zero))))))))
("main", A (Free "fact") (IN 100))

What’s interesting here is that only compileEta produces code of the same size as the baseline. All others produce code that uses at least one more combinator. Again compilePlain and compileK generate the largest code sizes.

The fibonacci function

fib  = y(λf n. if (is0 n) 1 (if (eql n 1) 1 (+ (f (sub1 n)) (f (sub n 2)))))
main = fib 10

-- in de Bruijn notation
("fib", A (Free "y") (L (L (A (A (A (Free "if") (A (Free "is0") (N Zero))) (IN 1)) (A (A (A (Free "if") (A (A (Free "eql") (N Zero)) (IN 1))) (IN 1)) (A (A (Free "+") (A (N (Succ Zero)) (A (Free "sub1") (N Zero)))) (A (N (Succ Zero)) (A (A (Free "sub") (N Zero)) (IN 2)))))))))
("main", A (Free "fib") (IN 10))

Here we see that compileEta produce code of the same size as the baseline. compileBulk generates code with one less combinator.

Please also note that compileBulk now emits code for additional bulk combinators S2 and B2. I’ll come back to the semantics of these later.

The ackermann function

ack  = y(λf n m. if (is0 n) (+ m 1) (if (is0 m) (f (sub1 n) 1) (f (sub1 n) (f n (sub1 m)))))
main = ack 2 2

-- in de Bruijn notation
("ack", A (Free "y") (L (L (L (A (A (A (Free "if") (A (Free "is0") (N (Succ Zero)))) (A (A (Free "+") (N Zero)) (IN 1))) (A (A (A (Free "if") (A (Free "is0") (N Zero))) (A (A (N (Succ (Succ Zero))) (A (Free "sub1") (N (Succ Zero)))) (IN 1))) (A (A (N (Succ (Succ Zero))) (A (Free "sub1") (N (Succ Zero)))) (A (A (N (Succ (Succ Zero))) (N (Succ Zero))) (A (Free "sub1") (N Zero))))))))))
("main", A (A (Free "ack") (IN 2)) (IN 2))

As mentioned in my last post the output size of braxcket abstraction grows quadratic with the number of variables. In this case with three variables the output size for the bracket abstraction is already significantly larger than for the previous example with two variables.

Now the Kiselyov algorithms really start to shine. compileEta produces code is significantly smaller as the baseline. And compileBulk output is even smaller.

The tak function

tak  = y(λf x y z. (if (geq y x) z (f (f (sub1 x) y z) (f (sub1 y) z x) (f (sub1 z) x y ))))
main = tak 7 4 2

-- in de Bruijn notation
("tak",A (Free "y") (L (L (L (L (A (A (A (Free "if") (A (A (Free "geq") (N (Succ Zero))) (N (Succ (Succ Zero))))) (N Zero)) (A (A (A (N (Succ (Succ (Succ Zero)))) (A (A (A (N (Succ (Succ (Succ Zero)))) (A (Free "sub1") (N (Succ (Succ Zero))))) (N (Succ Zero))) (N Zero))) (A (A (A (N (Succ (Succ (Succ Zero)))) (A (Free "sub1") (N (Succ Zero)))) (N Zero)) (N (Succ (Succ Zero))))) (A (A (A (N (Succ (Succ (Succ Zero)))) (A (Free "sub1") (N Zero))) (N (Succ (Succ Zero)))) (N (Succ Zero))))))))))
("main",A (A (A (Free "tak") (IN 7)) (IN 4)) (IN 2))

In this example with four variables the trend continues. compileEta produces code is significantly smaller as the baseline. And compileBulk output now is only about 1/3 of the baseline.

Executing Bulk Combinators

We have seen that Kisekyov’s algorithms produce code that makes use of Bulk Combinators like S4, B3 or C2. Ben Lynn defines the semantics of these combinators as follows:

where B', C' and S' defined as follows:

Ben also defines the following function that converts a combinator term with Bulk Combinators to a combinator term with only standard combinators:

breakBulkLinear :: Combinator -> Int -> CL
breakBulkLinear B n = iterate (comB' :@) (Com B) !! (n - 1)
breakBulkLinear C n = iterate (comC' :@) (Com C) !! (n - 1)
breakBulkLinear S n = iterate (comS' :@) (Com S) !! (n - 1)

comB' :: CL
comB' = Com B:@ Com B
comC' :: CL
comC' = Com B :@ (Com B :@ Com C) :@ Com B
comS' :: CL
comS' = Com B :@ (Com B :@ Com S) :@ Com B

As we have seen in the output of the compileBulkLinear this conversion expands the code size. To avoid this expansion of the combinator code I have implemented a solution to directly execute Bulk Combinators without any prior code expansion.

At the moment I have only implemented this idea in the Haskell-In-Haskell inspired HHI-Reducer. Implementing it for the Graph Reduction Engine is left as an exercise for the reader ;-).

In order to understand the solution we’ll have a short recap of the HHI-Reducer core ideas as described in my last post:

The core idea is to take a combinator term and compile it into a set of Haskell functions. This is done in a function link as follows:

1. All combinators of the form (CComb comb) are mapped to haskell functions implementing the respective combinator reduction rule. For example the combinator I is mapped to CFun id and the combinator K is mapped to CFun (CFun . const).

2. All applications (CApp fun arg) have to be replaced by actual function application. In our case we want apply functions of type CExpr -> CExpr that are wrapped by a CFun constructor. For this particular case we define an application operator (!) as follows:

infixl 0 !
(!) :: CExpr -> CExpr -> CExpr
(CFun f) ! x = f x

Thus:

(Cfun id) ! 14 = id 14 
         id 14 = 14

The mapping of Combinators to Haskell functions in step 1. is done by looking up a map of combinator definitions. This map contains definitions for all standard combinators and numeric operations. The Bulk combinators are not defined in this map. Instead they are resolved by the function resolveBulk:

resolveBulk :: Combinator -> CExpr
resolveBulk (BulkCom "B" n) = iterate (comB' !) comB !! (n-1)
resolveBulk (BulkCom "C" n) = iterate (comC' !) comC !! (n-1)
resolveBulk (BulkCom "S" n) = iterate (comS' !) comS !! (n-1)

It’s interesting to note how this functions resembles the breakBulkLinear function. The only difference is that we are using the function application operator (!) instead of the data constructor (:@). The function link is now defined as follows:

-- | "link" a compiled expression into Haskell native functions.
--   application terms will be transformed into real (!) applications
--   combinator symbols will be replaced by their actual function definition
link :: CombinatorDefinitions -> CExpr -> CExpr
link definitions (CApp fun arg) = link definitions fun ! link definitions arg
link definitions (CComb comb)   = case lookup comb definitions of
                                    Nothing -> resolveBulk comb
                                    Just e  -> e
link _definitions expr          = expr

In the same way I have re-implemented Ben’s function breakBulkLog as resolveBulkLog.

Performance Comparison

So far we have seen that for functions with more than two variables the Kiselyov algorithms generate code that is significantly smaller than optimized versions of classic bracket abstraction. But what about performance? Is the code generated by the Kiselyov algorithms also faster?

To answer this question I have set up a benchmarking suite based on the micro-benchmarking framework Criterion.

In my suite I am testing the performance of combinations of the following components:

• the compilers compileBracket, compileEta, compileBulk, compileBulkLinear and compileBulkLog from the previous section
• the function factorial, fibonacci, ackermann and tak from the previous section
• the execution backenda Graph Reduction Engine and the HHI-reducer implementaion from my previous post. I have not implemented the Bulk combinators in the graph reduction engine. So I am not testing this backend with the compileBulk compiler.
• the HHI-Reducer with both resolveBulkLinear and resolveBulkLog

So lets start with an overview of the results for the Graph Reduction Backend.

Performance figures for the Graph Reduction Engine

As already mentioned compileBulk is not implemented in the graph reduction engine. I am also not considering the compilePlain and compileK compilers as they generate code that is significantly larger than the baseline. All durations are given in μs.

Let’s put these figures into perspective by comparing them to the emitted code size (in number of combinators):

For factorial and fibonacci the code size is very similar for all compilers. And the performance figures are also very similar.

But for ackermann and tak the code size for compileEta is significantly smaller than for the other compilers. An interesting finding here is, that the performance of the compileEta code is significantly better than for the compileBracket code. But the performance of the compileBulkLinear and compileBulkLog code is faster per instruction than the compileBracketand compileEta code.

Overall compileEta gives the best result for the Graph Reduction Engine.

Performance figures for the HHI-Reducer

first all figures without the Bulk Combinators execution

The absolute execeution times are significantly smaller than for the Graph Reduction Engine. But the relative performance figures are very similar. Again compileEta gives the best result for the HHI-Reducer. In particular for ackermann and tak the performance of compileEta code is significantly better than for the other compilers.

Performance figures with Bulk Combinators execution

Now we want to see whether the native implementation of Bulk Combinators in the HHI-Reducer - as outlined in the previous section - can beat the performance of the compileEta compilation.

I see two main findings here:

1. For factorial, fibonacci and ackermann the performance of linear and logarithmic execution of Bulk Combinators is not better than the performance of compileEta code.

   But for tak the performance of both linear and logarithmic execution of Bulk Combinators is significantly better than the performance of compileEta code. The linear exceution of Bulk Combinators is slightly faster than the logarithmic execution.

2. The native implementation of Bulk Combinators is significantly faster than the resolveBulkLinear and resolveBulkLog for ackermann and tak.

Let’s put these results into perspective by comparing them to the emitted code size (in number of combinators):

1. For factorial and fibonacci the code size is very similar for all compilers. And the performance figures also don’t vary much.

   For ackermann the code size for compileBulk is about 82% of the code size for compileEta. But the execution time is not faster. This is due to the fact that the Bulk Combinator are more complex than the standard combinators. So the execution time per combinator is higher.

   For tak the code size for compileBulk is only 50% of the code size for compileEta. The execution time is now 84% of the execution time for compileEta. So even if the execution time per combinator is higher the overall execution time is now lower as the code size is significantly smaller.

2. Looking at the code sizes of the compileBulkLinear and compileBulkLog compilers we see that the code size is signifantly larger than for the compileEta and compileBulk compilers for ackermann and tak. So it is now wonder that the execution time is slower than for the `compileEta and compileBulk compilers.

Comparison to native Haskell code

As a final comparison I have also implemented the factorial, fibonacci, ackermann and tak functions as native Haskell functions. To make the comparison fair I have used a notation using the fix function to implement the Y-Combinator. See for example the implementation of the factorial function:

fact :: Integer -> Integer
fact = fix (\f n -> if n == 0 then 1 else n * f (n-1))

For Graph Reduction Engine I am using the compileEta compiler and for the HHI-Reducer I am using the compileBulk compiler with linear execution of Bulk combinators. The results are as follows:

In the following table I’m computing ratios to get simpler comparison metrics:

Conclusion

In this post I have shown that the Kiselyov algorithms for compiling SKI combinators to lambda calculus can be used to generate code that is significantly smaller than optimized versions of classic bracket abstraction.

In particular for functions with more than two variables the generation of Bulk-Combinator code avoids the quadratic growth of the code size that is typical for bracket abstraction.

The reduced code size also leads to better performance. In particular for functions with more than two variables the Kiselyov algorithms generate code that is significantly faster than optimized versions of classic bracket abstraction.

I have also shown that the native implementation of Bulk Combinators in the HHI-Reducer can beat the performance of the compileEta compilation. In particular for functions with more than two variables the native implementation of Bulk Combinators is significantly faster.