Improvement in a lazy context

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improvement in a lazy context: an operational theory for call-by-need

Full text

Pdf (1.61 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

San Antonio, Texas, United States

Pages: 43 - 56

Year of Publication: 1999

ISBN:1-58113-095-3

Authors

Andrew Moran	Department of Computing Science, Chalmers University of Technology and the University of Göteborg, S-412 96 Göteborg, Sweden
David Sands	Department of Computing Science, Chalmers University of Technology and the University of Göteborg, S-412 96 Göteborg, Sweden

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 18, Citation Count: 12

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/292540.292547 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AB97	Zena M. Ariola , Stefan Blom, Cyclic Lambda Calculi, Proceedings of the Third International Symposium on Theoretical Aspects of Computer Software, p.77-106, September 23-26, 1997
	AB98	Z.M. Ariola and S. Blom, Lambda calculi plus letrec, Tech. report, Dept. of Computer Science, University of Oregon, 1998, Extended version of {AB97}; submitted for publication.
	AF97	Zena M. Ariola , Matthias Felleisen, The call-by-need lambda calculus, Journal of Functional Programming, v.7 n.3, p.265-301, May 1997 [doi>10.1017/S0956796897002724]
	AFM+95	Zena M. Ariola , John Maraist , Martin Odersky , Matthias Felleisen , Philip Wadler, A call-by-need lambda calculus, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.233-246, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199507]
	AK97	Zena M. Ariola , Jan Willem Klop, Lambda calculus with explicit recursion, Information and Computation, v.139 n.2, p.154-233, Dec. 15, 1997 [doi>10.1006/inco.1997.2651 ]
	AO93	Samson Abramsky , C.-H. Luke Ong, Full abstraction in the lazy lambda calculus, Information and Computation, v.105 n.2, p.159-267, Aug. 1993 [doi>10.1006/inco.1993.1044 ]
	BLR96	Zine-El-Abidine Benaissa , Pierre Lescanne , Kristoffer Høgsbro Rose, Modeling Sharing and Recursion for Weak Reduction Strategies Using Explicit Substitution, Proceedings of the 8th International Symposium on Programming Languages: Implementations, Logics, and Programs, p.393-407, September 24-27, 1996
	Cur91	P.-L. Curien, An abstract frame work for environment machines, Theoretical Computer Science, v.82 n.2, p.389-402, May 31, 1991 [doi>10.1016/0304-3975(91)90230-Y ]
	Fie90	John Field, On laziness and optimality in lambda interpreters: tools for specification and analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, December 1989, San Francisco, California, United States [doi>10.1145/96709.96710]
	GP98	Andrew D. Gordon , Andrew M. Pitts, Higher order operational techniques in semantics, Cambridge University Press, New York, NY, 1999
	Gus98	Jörgen Gustavsson, A type based sharing analysis for update avoidance and optimisation, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.39-50, September 26-29, 1998, Baltimore, Maryland, United States
	HM95	John Hughes , Andrew Moran, Making choices lazily, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.108-119, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224191]
	Jef93	A. Jeffrey, A fully abstract semantics for concurrent graph reduction, Tech. Report 93:12, School of Cognitive and Computing Sciences, University of Sussex, 1993.
	Jef94	A. Jeffrey, A fully abstract semantics for concurrent graph reduction, Proc. LICS'94, the 9th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, July 1994, pp. 82-91.
	Jos89	M. B. Josephs, The semantics of lazy functional languages, Theoretical Computer Science, v.68 n.1, p.105-111, Oct. 16, 1989 [doi>10.1016/0304-3975(89)90122-9 ]
	Las98	S.B. Lassen, Relational reasoning about func. tions and nondeterminism, Ph.D. thesis, Department of Computer Science, University of Aarhus, May 1998.
	Lau93	John Launchbury, A natural semantics for lazy evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.144-154, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158618]
	Mar91	Luc Maranget, Optimal derivations in weak lambda-calculi and in orthogonal term rewriting systems, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.255-269, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99618]
	MFP91	Erik Meijer , Maarten Fokkinga , Ross Paterson, Functional programming with bananas, lenses, envelopes and barbed wire, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.124-144, June 1991, Cambridge, Massachusetts, United States
	Mil77	R. Milner, Fully abstract models of the typed A-calculus, Theoretical Computer Science 4 (1977), 1-22.
	MOW98	John Maraist , Martin Odersky , Philip Wadler, The call-by-need lambda calculus, Journal of Functional Programming, v.8 n.3, p.275-317, May 1998 [doi>10.1017/S0956796898003037]
	MST96	Ian A. Mason , Scott F. Smith , Carolyn L. Talcott, From operational semantics to domain theory, Information and Computation, v.128 n.1, p.26-47, July 10, 1996 [doi>10.1006/inco.1996.0061 ]
	Nie96	Joachim Niehren, Functional computation as concurrent computation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-343, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237801]
	Pit97a	A. M. Pitts, Operational semantics for program equivalence, March 1997, Invited talk at MFPS XIII, the 13th Conference on Mathematical Foundations of Programming Semantics, slides available at http://www.cl.cam.ac.uk/users/ap/talks/ mfpsg7.ps.gz.
	Pit97b	A.M. Pitts, Operationally-based theories of program equivalence, Semantics and Logics of Computation (P. Dybjer and A. M. Pitts, eds.), Publications of the Newton Institute, Cambridge University Press, 1997, pp. 241- 298.
	PJPS96	Simon Peyton Jones , Will Partain , André Santos, Let-floating: moving bindings to give faster programs, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.1-12, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	PJS98	Simon L. Peyton Jones , André L. M. Santos, A transformation-based optimiser for Haskell, Science of Computer Programming, v.32 n.1-3, p.3-47, Sept. 1998 [doi>10.1016/S0167-6423(97)00029-4 ]
	Ros96	K.H. Rose, Operational reduction models for functional programming languages, Ph.D. thesis, DIKU, University of Copenhagen, Denmark, February 1996, available as DIKU report 96/1.
	San91	David Sands, Operational Theories of Improvement in Functional Languages (Extended Abstract), Proceedings of the 1991 Glasgow Workshop on Functional Programming, p.298-311, August 12-14, 1991
	San95	D. Sands, A halve time analysis and its theory of cost equivalence, Journal of Logic and Computation 5 (1995), no. 4, 495-541.
	San96	David Sands, Total correctness by local improvement in the transformation of functional programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.2, p.175-234, March 1996 [doi>10.1145/227699.227716]
	San97	David Sands, From SOS rules to proof principles: an operational metatheory for functional languages, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.428-441, January 15-17, 1997, Paris, France [doi>10.1145/263699.263760]
	San98	D. Sands, Improvement theory and its applications, Higher order operational techniques in semantics, Cambridge University Press, New York, NY, 1999
	Ses97	Peter Sestoft, Deriving a lazy abstract machine, Journal of Functional Programming, v.7 n.3, p.231-264, May 1997 [doi>10.1017/S0956796897002712]
	Smi91	Scott F. Smith, From Operational to Denotational Semantics, Proceedings of the 7th International Conference on Mathematical Foundations of Programming Semantics, p.54-76, March 25-28, 1991
	SPI96	Jill Seaman , S. Purushothaman Iyer, An operational semantics of sharing in lazy evaluation, Science of Computer Programming, v.27 n.3, p.289-322, Nov. 1996 [doi>10.1016/0167-6423(96)00012-3 ]
	SPJ97	Patrick M. Sansom , Simon L. Peyton Jones, Formally based profiling for higher-order functional languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.2, p.334-385, March 1997 [doi>10.1145/244795.244802]
	TH98	M. Tullsen and P. Hudak, An intermediate meta-language /or program transformation, YALEU/DCS/RR 1154, Yale University, June 1998.
	TWM95	David N. Turner , Philip Wadler , Christian Mossin, Once upon a type, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.1-11, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224168]
	Wad88	P. Wadler, The concatenate vanishes, Tech. report, University of Glasgow (UK), 1988, appeared as a note on an FP electronic mailing list, December 1987.
	Wad90	Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990
	Yos93	Nobuko Yoshida, Optimal reduction in weak-&lgr;-calculus with shared environments, Proceedings of the conference on Functional programming languages and computer architecture, p.243-252, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165217]

CITED BY 12

	David Sands , Jörgen Gustavsson , Andrew Moran, Lambda calculi and linear speedups, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
	Dana N. Xu, Extended static checking for haskell, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA
	Nils Anders Danielsson, Lightweight semiformal time complexity analysis for purely functional data structures, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Janis Voigtländer, Concatenate, reverse and map vanish for free, ACM SIGPLAN Notices, v.37 n.9, p.14-25, September 2002
	Jörgen Gustavsson , David Sands, Possibilities and limitations of call-by-need space improvement, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Dan R. Ghica, Slot games: a quantitative model of computation, ACM SIGPLAN Notices, v.40 n.1, p.85-97, January 2005
	Clem Baker-Finch , David J. King , Phil Trinder, An operational semantics for parallel lazy evaluation, ACM SIGPLAN Notices, v.35 n.9, p.162-173, Sept. 2000
	Joachim Niehren, Uniform confluence in concurrent computation, Journal of Functional Programming, v.10 n.5, p.453-499, September 2000
	Steven E. Ganz , Amr Sabry , Walid Taha, Macros as multi-stage computations: type-safe, generative, binding macros in MacroML, ACM SIGPLAN Notices, v.36 n.10, October 2001
	Geoff W. Hamilton, Higher Order Deforestation, Fundamenta Informaticae, v.69 n.1-2, p.39-61, January 2006
	Andrew Moran , David Sands , Magnus Carlsson, Erratic fudgets: a semantic theory for an embedded coordination language, Science of Computer Programming, v.46 n.1-2, p.99-135, January/February 2003
	Andrew Moran , David Sands , Magnus Carlsson, Erratic fudgets: a semantic theory for an embedded coordination language, Science of Computer Programming, v.46 n.1-2, p.99-135, January/February 2003

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
F.4.1 Mathematical Logic
Subjects: Lambda calculus and related systems

Additional Classification:
F. Theory of Computation
F.3 LOGICS AND MEANINGS OF PROGRAMS
F.3.2 Semantics of Programming Languages
Subjects: Operational semantics

General Terms:
Languages

Collaborative Colleagues:

Andrew Moran: colleagues

David Sands: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

Adobe Acrobat

QuickTime

Windows Media Player

Real Player