
Program Transformation and Optimization in Calculational Form 
Selected Papers 
Software
Correctnesspreserving program transformation plays an important role
in compiler optimization in functional programming, and it calls for
a more systematic study. We have demonstrated that many
important program transformations
such as deforestation (or fusion),
tupling, accumulation, and
IO swapping calculation, can be effectively
and elegantly formalized in calculational form. In general,
program transformation in calculational form enjoys the nice
properties of modularity and cheap implementation, which can be
embedded in compilers of functional languages.
In addition, program calculation is very helpful in developing efficient algorithms. We
have developed some systematic derivation strategies with which we
derived several new algorithms: a new divideandconquer
algorithms for solving twodimensional version of maximal segment sum
problem, a novel efficient parallel program for bracket
matching, a completely new algorithm for computing frequent
sets in data mining. In particular, we proposed a
generic algorithm for solving the maximum marking problems,
a class of useful optimization problems.
Selected Papers

Akimasa Morihata,
Kazuhiko Kakehi,
Zhenjiang Hu,
Masato Takeichi,
Manipulating Accumulative Functions by Swapping Calltime and Returntime Computations,
Journal of Functional Programming, accepted, 2012.

Julien Tesson,
Hideki Hashimoto,
Zhenjiang Hu,
Frederic Loulergue,
Masato Takeichi,
Prorgam Calculation in Coq,
Thirteenth International Conference on Algebraic Methodology And Software Technology
(AMAST 2010),
Quebec City, Canada, 2326 June 2010.

Akimasa Morihata,
Kiminori Matsuzaki,
Zhenjiang Hu,
Masato Takeichi,
The Third Homomorphism Theorem on Trees: Downward & Upward
Lead to DivideandConquer,
The 36th Annual ACM SIGPLAN  SIGACT Symposium on
Principles of Programming Languages
(POPL 2009),
Savannah, Georgia, USA, January 2123, 2009. pp.177185.

Zhenjiang Hu,
Tetsuo Yokoyama,
Masato Takeichi,
Program Optimizations and Transformations in
Calculational Form,
Summer School on Generative and Transformational Techniques
in Software Engineering
(GTTSE 2005),
Braga, Portugal, 47 July, 2005. (Slides),
LNCS 4143, 2006. Springer. pp.139164.

Akimasa Morihata
Kazuhiko Kakehi,
Zhenjiang Hu,
Masato Takeichi,
Swapping Arguments and Results of Recursive Functions,
8th International Conference on Mathematics of Program Construction
(MPC 2006),
Kuressaare, Estonia, 35 July 2006. LNCS 4014, Springer. pp.379396.

Tetsuo Yokoyama,
Zhenjiang Hu,
Masato Takeichi,
Deterministic Secondorder Patterns,
Information Processing Letters,
Vol. 89, No.6,
Elsevier,
2004. pp. 309314.

Mizuhito
Ogawa,
Zhenjiang Hu,
Isao Sasano,
Iterativefree Program Analysis,
8th ACM SIGPLAN International Conference on Functional
Programming,
(ICFP 2003),
Uppsala, Sweden: 2529 August 2003. ACM Press. pp.111123.

Tetsuo Yokoyama,
Zhenjiang Hu,
Masato Takeichi,
Deterministic Secondorder Patterns and Its Application to Program Transformation,
International Symposium on Logicbased Program Synthesis and Transformation
(LOPSTR 2003)
Uppsala, Sweden: 2527 August 2003. pp.165178.
Revised version appears in LNCS 3018, 2004. Springer Verlag. pp. 128142.

WeiNgan Chin,
Zhenjiang Hu,
Towards a Modular Program Derivation via Fusion and
Tupling,
The First ACM SIGPLAN Conference on Generators and
Components
(GCSE/SAIG
2002), Pittsburgh, PA, USA, October 68, 2002. pp.140155.
Affiliated with
(PLI
2002). Lecture Notes in Computer Science 2487, Springer
Verlag. pp.140155.

Zhenjiang Hu,
WeiNgan Chin,
Masato Takeichi,
Calculating a New Data Mining Algorithm for Market Basket
Analysis, (Revised version of the paper presented at PADL'00.)
Journal of Functional and Logic Programming, October 2001.

Isao Sasano,
Zhenjiang Hu,
Masato Takeichi,
Mizuhito Ogawa,
Make it Practical: A Generic Linear Time Algorithm for Solving
Maximum Weightsum Problems ,
The 2000 ACM SIGPLAN International Conference on Functional
Programming,
(ICFP 2000),
Montreal, Canada, 1820 September 2000. ACM Press. pp. 137149.

Zhenjiang Hu , Hideya Iwasaki ,
Masato Takeichi,
Calculating Accumulations,
New Generation Computing, Vol. 17, No. 2, 1999, pp.153173.

Zhenjiang Hu ,
Masato Takeichi,
WeiNgan Chin,
Parallelization in Calculational Forms
,
25th ACM SIGPLANSIGACT Symposium on
Principles of Programming Languages
(POPL'98),
San Diego, California, USA, January 1998, pp. 316328. ACM Press.

Akihiko Takano,
Zhenjiang Hu,
Masato Takeichi,
Program Transformation in Calculational Form,
ACM Computing Surveys, Vol. 30, No.3, 1998.
A special issue for 1998 Symposium on Partial Evaluation
(SOPE'98).

Zhenjiang Hu ,
Hideya Iwasaki,
Masato Takeichi,
Akihiko Takano,
Tupling Calculation Eliminates Multiple Data Traversals ,
2nd ACM SIGPLAN International Conference on
Functional Programming
(ICFP'97),
Amsterdam, The Netherlands, June 1997, pp.164175. ACM Press.

Yoshiyuki Onoue,
Zhenjiang Hu,
Hideya Iwasaki,
Masato Takeichi,
A Calculational Fusion System HYLO ,
IFIP TC 2 Working Conference on Algorithmic Languages and
Calculi.
Le Bischenberg, France, February 1997, pp.76106. Chapman&Hall.

Zhenjiang Hu,
Hideya Iwasaki,
Masato Takeichi,
Deriving Structural Hylomorphisms from Recursive Definitions,
ACM SIGPLAN International Conference on Functional Programming
(ICFP'96),
Philadelphia, May 1996, pp.7382. ACM Press.
More papers are available here.
Software
 Yicho: A
Combinator Library for Supporting Calculational Programming.
 HYLO: An automatic fusion calculation system (implemented in the old GHC).
Maintained by Zhenjiang Hu. Last modified in 2006.