Hostname: page-component-7c8c6479df-7qhmt Total loading time: 0 Render date: 2024-03-28T06:32:00.498Z Has data issue: false hasContentIssue false

More haste, less speed: lazy versus eager evaluation

Published online by Cambridge University Press:  01 September 1997

RICHARD BIRD
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
GERAINT JONES
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
OEGE DE MOOR
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Nicholas Pippenger has recently given a problem that, under two simple restrictions, can be solved in linear time by an impure Lisp program, but requires Ω(n log n) steps to be solved by any eager pure Lisp program. By showing how to solve the problem in linear time with a lazy functional program, we demonstrate that – for some problems at least – lazy evaluators are strictly more powerful than eager ones.

Type
Research Article
Copyright
© 1997 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.