Japan Advanced Institute of Science and Technology

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

Masayoshi Saga

Scho ol of Information Science,

Japan Advanced Institute of Science and Technology

February 13, 1998

Keywords: program transformation, functionalprogram, deforestation.

In functional programming, each program is composed of small and basic functions.

These module-oriented programs are easy for us to read and understand. However this

function composition makes many intermediatedata structures suchas tree and list, be-

causethoseintermediatedatastructuresareusedtopassandreceiveinformationbetween

functions. Thisintermediatedatastructuredoesnotdirectlyapp earasapartoftheresult

of the whole program and causes loss ofeciency.

In order to eliminate intermediate data structures, deforestation was proposed by

Wadler(1990). In his deforestation procedure, 7 rules are applied to a given program

repetitively and the program is transformed into ecient one. It is a simple procedure,

but it requires complicatedmemorization to guarantee termination of the procedure.

Gill, etc(1993) capture the structure of program by fol dr, a list op erating function.

They apply transformations only to programs written in terms of the fol dr function.

Their technique do esnot require memorization for termination.

Deforestationwithoutmemorization,likefol drtechnique,hasadvantageinapractical

use but their technique is limited to lists and programs have to be abstracted by fol dr.

In addition, the well-known ecientfunction for reversalof listcan not betransformed.

Inthis study,weproposepartialevaluativedeforestation,whichdo esnotrequirecom-

plicatedmemorizationandprogramabstractionbyfol dr. Partialevaluativedeforestation

works on a call-by-value language. Furthermore, a function likethe ecientlist reversal

function can be transformed bythis technique.

Thepro cedureofpartialevaluativedeforestationhastwophases,classicationoffunc-

tions and rewriting a program to adeforested program with anewly denedfunction.

Functionsareclassiedtothreegroups,successivefunction(Su),packedfunction(Pa)

andothers. Afunctioninformertwofunctiongroupsisarecursivefunctionandabsolutely

produces a part of the result of the whole program wheneverit is called. The dierence

between Suand Pais asfollows.

Copyrightc 1998byMasayoshiSaga

Su

…

Pa

…

of the whole program is accumulatedinan extraargument.

Partial evaluative deforestation mainly applies transformation to these two kinds of

functions. 7 transformation rules are made by the structure of a term. Especially, a

functionisnewlydened infourrules. Thesefourrulesfollowallthepatternsoffunction

compositionof Su and Pa. Basicstrategies for deriving a new functionare asfollows.

Unfold aninner function andapply a outerfunction to eachrightside of branch.

Reduce if possible.

Rewrite a function composition matching an input to a new term using a newly

denedfunction.

In addition to these basic strategies, terms are recursively transformed by extracting an

operation for the elements of data and adopting the extracted operation as a part of a

newly dened functionor asa part of a new term.

Equivalenceof values of terms between beforeand aftertransformation and termina-

tionoftheprocedureareprovedbystructural inductiononterms. Implementationofthis

method showsus raisingan eciencyof aprogram b ecause ofdecrease inthe numb erof

referring todata.

In spiteof eciency,terminationand equivalence,partialevaluativedeforestation has

three major limitations. One is that types of input and output data for two kinds of

function groups haveto be the same. The secondproblem isthat twokinds of functions

absolutely produce a part of the result of the whole program whenever they are called.

The last limitation is allthe elementsof input data are equallyoperated.

In order to extend partial evaluative deforestation, there is a serious problem. Ex-

tension of our method causes diculty of extracting an operation for the elements of

data. Oneofthe solutionsof thisproblem isintro ductionof anotherclassicationmecha-

nism and new transformationrules based onits classiedfunctioncomposition. Another

classication mechanism classies functions by whether functions absolutely produce a

part of the result of the whole program every time called and whether all the elements

of input data are equally op erated. This classication mechanism is considered to be so

complicated withoriginal classication.

As describ ed above, partial evaluative deforestation without memorization and pro-

gram abstracting by fol dr is proposed. Partial evaluative deforestation is for call-by-

value languages. Furthermore, its eectiveness, problems and solutions are discussed.

As a future work, studies oncharacters of functions,higer-order functions and reduction

strategies remain tobedone.