HYLO fusion in GHC
History
| Until |
Target to embed our algorithm |
| Autumn '97: |
Prototype system based on gofer2.30a. |
| Autumn '98: |
Optimisation path in ghc-2.10, |
| Summer '99: |
Applied for nofib benchmarks(spectral). |
| Now: |
Optimisation path in ghc-5.04.3. |
Features
- No need to prepare some fusable functions (eg. foldr/build).
- User defined datatype can be fused.
- And more...
Example
CGI interface to hylo-fusion It's out of order, sorry.
- Original Haskell Program
- Optimised Core Program
Add '-fprint-core' option at last optimisation paths.
You will find an new fused function named 'fun1.fun2'.
- Executed Result
'a.out' was compiled by original GHC.
'b.out' was compiled by our modified GHC.
Please compare two heap comsumption.
Next time, we will apply our method to larger programs.
Current Limitations
- No mutual recursion
- And more...
References
- A. Takano, E. Meijer.
Shortcut Deforestation in Calculational Form,
Proc. Conf. on Functional Programming Languages and Computer Architecture,
La Jolla, California, June 1995, pp.306-313.
- Z. Hu, H. Iwasaki, M. Takeichi.
Deriving Structural Hylomorphisms from Recursive Definitions,
ACM SIGPLAN International Conference on Functional Programming
(ICFP'96),
Philadelphia, pp.73-82. May 1996. ACM Press.
- Y. Onoue, Z. Hu, H. Iwasaki, M. Takeichi.
A Calculational Fusion System HYLO,
IFIP TC2 Working Conference on Algorithmic Languages and Calculi.
Le Bischenberg, France. pp.76-106. February 1997. Chapman & Hall.
- Y. Onoue, Z. Hu, M. Takeichi.
Implementation of Program Fusion by HYLO System.
Computer Software, Vol.15, No.6, pp.52-56, 1998. (Japanese)
- Y. Onoue, Z. Hu, H. Iwasaki, M. Takeichi.
Verification for Practical Effectiveness of Program Fusion.
Computer Software, Vol.17, No.3, pp.81-85, 2000. (Japanese)
Back to Onoue's Home Page