論文

査読有り
2008年9月

Algebraic fusion of functions with an accumulating parameter and its improvement

JOURNAL OF FUNCTIONAL PROGRAMMING
  • Shin-Ya Katsumata
  • ,
  • Susumu Nishimura

18
開始ページ
781
終了ページ
819
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1017/S095679680800693X
出版者・発行元
CAMBRIDGE UNIV PRESS

This paper develops a new framework for fusion that is designed for eliminating the intermediate data structures involved in the composition of functions that have one accumulating parameter. The new fusion framework comprises two steps: algebraic fusion and its Subsequent improvement process. The key idea in our development is to regard functions with an accumulating parameter as function:; that operate over the monoid of data contexts:is. Algebraic fusion composes each such function with a monoid homomorphism that is derived from the definition Of the Consumer function to obtain a higher-order function that Computes over the monoid of endofunctions net ions. The transformation result may be further refilled by an improvement process, which replaces the operation over the monoid of endofunctions (i.e., function Closures) with another monoid operation over a monoid Structure other than function Closures.
Using our framework, one can formulate a particular Solution to the fusion problem by devising appropriate monoids and monoid homomorphisms. This provides a unified exposition of a variety of fusion methods that have been developed so far in different formalisms. Furthermore, the cleaner formulation makes it possible to argue about some delicate issues on a firm mathematical basis. We demonstrate that algebraic fusion and improvement in the world of complete pointed partial orders (CPOs) and continuous functions can correctly fuse functions that operate on partial and infinite data structures. We also show that subtle differences in termination behaviours of transformed programmes caused by certain different fusion methods can be cleanly explained by corresponding improvement processes that have different underlying monoid structures.

Web of Science ® 被引用回数 : 4

リンク情報
DOI
https://doi.org/10.1017/S095679680800693X
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902233782375322
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000261111700006&DestApp=WOS_CPL
ID情報
  • DOI : 10.1017/S095679680800693X
  • ISSN : 0956-7968
  • J-Global ID : 200902233782375322
  • Web of Science ID : WOS:000261111700006

エクスポート
BibTeX RIS