Recover Your Boilerplate (RYB)

Optimizing SYB by Recovering Handwritten Traversals

Report Bug · Request Feature

Table of Contents

1. About
2. Getting Started
   • Prerequisites
   • Installing and Building
3. Usage
   • Basic Usage
   • Exposing Unfoldings
   • Plugin Options
4. Roadmap
5. Contributing
6. License
7. Contact

About

2024-09-13.14-36-03.mp4

Recover Your Boilerplate (RYB) is a GHC plugin for optimizing Scrap Your Boilerplate (SYB)-style traversals via specialization, thereby recovering all handwritten boilerplate code. With this plugin, virtually all runtime/space costs associated with using SYB constructs are eliminated by rebuilding handwritten "boilerplate" traversals from SYB-style traversals.

Currently, this plugin supports optimizations for mkT, mkQ, mkM aliases (along with their ext variants), and the traversal schemes everywhere, everywhere', everything and everywhereM. Support for other aliases and schemes are in progress.

This plugin has been tested on GHC version 9.4.8. Support for more GHC versions is in progress.

(back to top)

Getting Started

This is an example of how you may give instructions on setting up your project locally. To get a local copy up and running follow these simple example steps.

Prerequisites

• GHC v9.4.8 (base v4.17.2.1)
• Cabal v3.10.3.0
• git

Installing and Building

• Clone this repository

  git clone https://github.com/yonggqiii/optimizing-syb.git
  cd optimizing-syb/

• Building

  cabal build

You're all set!

(back to top)

Usage

Basic Usage

This plugin can be used when compiling any source file containing SYB functions. For example:

import Data.Company -- A 'Company' datatype that derives Data
import Data.Generics ( everywhere, mkT ) -- SYB functions

incS :: Float -> Salary -> Salary
incS k (S s) = S $ s * (1 + k)

increase :: Data a => Float -> a -> a
increase k = everywhere $ mkT (incS k)

To compile with this plugin, specify the -O2 optimization and the OptimizingSYB plugin, like so:

{-# OPTIONS_GHC -O2 -fplugin OptimizingSYB #-}
import Data.Company -- A 'Company' datatype that derives Data
import Data.Generics ( everywhere, mkT ) -- SYB functions

incS :: Float -> Salary -> Salary
incS k (S s) = S $ s * (1 + k)

increase :: Data a => Float -> a -> a
increase k = everywhere $ mkT (incS k)

However, this plugin will not do anything to this program because no information on the type to specialize increase over is provided. Therefore, either specify the exact type that increase operates over, such as

-- ...
increase :: Float -> Company -> Company -- Specific type for increase
increase k = everywhere $ mkT (incS k)

Or write a SPECIALIZE pragma:

-- ...
increase :: Data a => Float -> a -> a
increase k = everywhere $ mkT (incS k)
{-# SPECIALIZE increase :: Float -> Company -> Company #-}

Include the plugin project directory in your cabal.project file:

packages: .
          -- ...
          /path/to/optimizing-syb

Include optimizing-syb in your build dependencies in your my-project.cabal file:

-- ...
executable MyProject
  -- ...
  build-depends:   -- ...
                 , optimizing-syb
                   -- ... 

Now you can build your project with cabal build and this plugin will optimize your traversals!

Exposing Unfoldings

An important caveat when using this plugin is that all unfoldings of any used Data instances must be included. That is, in the file containing the instance declarations, provide an -fexpose-all-unfoldings GHC option:

{-# OPTIONS_GHC -fexpose-all-unfoldings #-}

import Data.Generics

data Company = C [Dept] deriving (Show, Data)
data Dept = D Name Manager [SubUnit] deriving (Show, Data)
-- ...

Otherwise, the plugin may not be able to inline occurrences of gmapT, gmapQ etc., especially when your datatypes are recursive (GHC does not expose these unfoldings when that is the case):

{-# OPTIONS_GHC -fexpose-all-unfoldings #-}
data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Show, Data) -- unfoldings for Data (Tree a) are not exposed without
                                                                     -- -fexpose-all-unfoldings option

Note: this requirement affects any data type where [] occurs, because GHC does not expose the unfoldings for Data [a]. In our testing, re-compiling GHC with the -fexpose-all-unfoldings option included in the Data.Data source file removes this issue.

Plugin Options

This plugin does not have customizations, since virtually all passes included are required for optimizing SYB-style traversals. However, this plugin exposes verbosity options to track the transformations applied to the program.

This plugin runs several transformations:

1. Simple optimizations (--show-simple): runs a simple preprocessor to inline and simplify invocations of ($) to reveal applications of SYB schemes
2. Function map extraction (--show-function-map): groups SPECIALIZE'd functions together for traversal extraction
3. Traversal extraction (--show-traversal-extraction): extracts SYB-style traversals as standalone least function for specialization
4. Scheme elimination (--show-scheme-elim): eliminates schemes like everywhere by turning traversals into recursive functions
5. Traversal specialization (--show-spec): specializes traversals
6. Combinator elimination (--show-gmap-elim): eliminates calls to combinators like gmapT by inlining
7. Type-level evaluation (--show-type-eval): eliminates calls to aliases like mkT by compile-time type-level evaluation

To see the result of running each phase, provide these flags as options to the OptimizingSYB plugin. For example, to show the scheme elimination and combinator elimination passes, you may do something like

{-# OPTIONS_GHC -O2 -fplugin OptimizingSYB #-}
{-# OPTIONS_GHC -fplugin-opt OptimizingSYB:--show-scheme-elim #-}
{-# OPTIONS_GHC -fplugin-opt OptimizingSYB:--show-gmap-elim #-}

import Data.Company -- A 'Company' datatype that derives Data
import Data.Generics ( everywhere, mkT ) -- SYB functions

incS :: Float -> Salary -> Salary
incS k (S s) = S $ s * (1 + k)

increase :: Float -> Company -> Company
increase k = everywhere $ mkT (incS k)

(back to top)

Roadmap

• Support for all SYB features
• Support for GHC > 9.4.8
• Support for GHC < 9.4.8

See the open issues for a full list of proposed features (and known issues).

(back to top)

Contributing

Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!

1. Fork the Project
2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
3. Commit your Changes (git commit -m 'Add some AmazingFeature')
4. Push to the Branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

(back to top)

Top contributors:

License

Distributed under the MIT License. See LICENSE.txt for more information.

(back to top)

Contact

Foo Yong Qi - [email protected]

Project Link: https://github.com/yonggqiii/optimizing-syb

(back to top)