Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,263
    • Issues 4,263
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 416
    • Merge Requests 416
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Security & Compliance
    • Security & Compliance
    • Dependency List
    • License Compliance
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Collapse sidebar
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
  • Glasgow Haskell Compiler
  • GHCGHC
  • Wiki
    • Rewrite rules
  • worker wrapper

Last edited by AndyGill Jan 05, 2009
Page history New page

worker wrapper

Worker/Wrapper PRAGMA

This is a sketch of a design for a PRAGMA to support the wider use of the worker/wrapper idiom.

The basic idea

  1. Write basic function
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
  1. Write non-rec worker function using the original function.
worker :: [a] -> [a] -> [a]
worker xs = rep (reverse xs)
  1. Finally, the pragma (or alt syntax, for discussion).
{-# WRAPPER reverse xs = abs (worker xs) #-}
{-# RULE "reverse" [WRAPPER] reverse xs = abs (worker xs) #-}

The design here intentionally works if the PRAGMA is ignored: the original reverse is used by everyone, and worker gets removed as dead code.

You also may need to provide the coercion functions that go with the above definition.


rep :: [a] -> [a] -> [a]
rep xs ys = xs ++ ys

abs :: ([a] -> [a]) -> [a]
abs f = f []

How does this work?

We look for the edge between the worker and reverse, and rename it, as well as promoting the wrapper rule into a definition. So early in compilation, the AST will look like:

{-# INLINE reverse' #-}
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse xs ++ [x]

worker :: [a] -> [a] -> [a]
worker xs = rep (reverse' xs)

{-# INLINE reverse #-}
reverse xs = abs (worker xs)

Now we can let the optimizer do its job, as before. reverse' (which is no longer recursive) will be inlined inside worker. Anyone using reverse will call worker.

The key thing is identifying the worker in general. It is anything that

  • Is mentioned in the right hand side of the WRAPPER rule, and
  • Calls the original function (reverse).

After prototyping, we will explore generalizations.

Discuss

I've come to the conclusion that this is not possible to implement directly inside the current rules as provided, and needs a small extension.

  • What is a good syntax for the WRAPPER PRAGMA?
  • What is the best place to put this in GHC? Do we extend Activation with a Wrapper constructor? Do we extend the HsDecls AST?
Clone repository

GHC Home
GHC User's Guide

Joining In

Newcomers info
Mailing Lists & IRC
The GHC Team

Documentation

GHC Status Info
Working conventions
Building Guide
Debugging
Commentary

Wiki

Title Index
Recent Changes