μετα 2010

Second International Workshop on Metacomputation in Russia
 

July 1-5, 2010, Pereslavl-Zalessky (120 km to the north-east from Moscow), Russia

Home
Call For Papers
News
Submissions
Invited Speakers
Accepted Papers
Program
Photos
Important Dates
Registration
Visa Support
Place
Contacts
History
Posters
Sponsors

 

 

 

 

 

A Graph-Based Definition of Distillation

Geoff Hamilton and Gavin Mendel-Gleason,
School of Computing Dublin City University, Ireland

 

Abstract

Full text pdf 439 KB

In this paper, we give a graph-based definition of the distillation transformation algorithm. This definition is made within a similar framework to the positive supercompilation algorithm, thus allowing for a more in-depth comparison of the two algorithms. We find that the main distinguishing characteristic between the two algorithms is that in positive supercompilation, generalization and folding are performed with respect to expressions, while in distillation they are performed with respect to graphs. We also find that while only linear improvements in performance are possible using positive supercompilation, super-linear improvements are possible using distillation. This is because computationally expensive terms can only be extracted from within loops when generalizing graphs rather than expressions.



Presentation pdf 1 MB