CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Possibilities and Limitations of Call-by-Need Space Improvement

Jörgen Gustavsson ; David Sands (Institutionen för datavetenskap, ProSec ; Institutionen för datavetenskap)
Proceeding of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP'01) p. 265-276. (2001)
[Konferensbidrag, refereegranskat]

Innocent-looking program transformations can easily change the space complexity of lazy functional programs. The theory of space improvement seeks to characterise those local program transformations which are guaranteed never to worsen asymptotic space complexity of any program. Previous work by the authors introduced the space improvement relation and showed that a number of simple local transformation laws are indeed space improvements. This paper seeks an answer to the following questions: is the improvement relation inhabited by interesting program transformations, and, if so, how might they be established? We show that the asymptotic space improvement relation is semantically badly behaved, but that the theory of strong space improvement possesses a fixed-point induction theorem which permits the derivation of improvement properties for recursive definitions. With the help of this tool we explore the landscape of space improvement by considering a range of classical program transformations.

Denna post skapades 2006-09-28.
CPL Pubid: 18063


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, ProSec (2002-2004)
Institutionen för datavetenskap (1993-2001)


Datavetenskap (datalogi)

Chalmers infrastruktur