Unrestricted pure call-by-value recursion

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Unrestricted pure call-by-value recursion

Full text

Pdf (278 KB)

Source

International Conference on Functional Programming archive
Proceedings of the 2008 ACM SIGPLAN workshop on ML table of contents

Victoria, BC, Canada

SESSION: Session 1 table of contents

Pages 23-34

Year of Publication: 2008

ISBN:978-1-60558-062-3

Authors

Johan Nordlander	Lulea University of Technology, Luleå, Sweden
Magnus Carlsson	Galois, Inc., Portland, OR, USA
Andy J. Gill	The University of Kansas, Lawrence, KS, USA

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 38, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/1411304.1411309 What is a DOI?

ABSTRACT

Call-by-value languages commonly restrict recursive definitions by only allowing functions and syntactically explicit values in the right-hand sides. As a consequence, some very appealing programming patterns that work well in lazy functional languages are hard to apply in a call-by-value setting, even though they might not be using laziness for any other purpose than to enable the desired form of recursion.

In this paper we present an operational semantics as well as a straightforward implementation technique for unrestricted recursion under pure call-by-value. On that basis we are able to demonstrate that highly recursive programming idioms such as combinator-based parsing are indeed compatible with call-by-value evaluation.

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.

	1	Z. M. Ariola and S. Blom. Skew conïfluence and the lambda calculus with letrec. Annals of pure and applied logic, 117 ((1-3)): 95-178, 2002.
	2	Gérard Boudol and Pascal Zimmer. Recursion in the call-by-value λ-calculus. In Fixed Points in Computer Science, FICS 2002, Copenhagen, Denmark, July 2002.
	3	Luca Cardelli, Compiling a functional language, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.208-217, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802037]
	4	Derek Dreyer, A type system for well-founded recursion, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-305, January 14-16, 2004, Venice, Italy
	5	Conal Elliott , Paul Hudak, Functional reactive animation, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.263-273, June 09-11, 1997, Amsterdam, The Netherlands
	6	Manuel Fahndrich , Songtao Xia, Establishing object invariants with delayed types, Proceedings of the 22nd annual ACM SIGPLAN conference on Object oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
	7	Tom Hirschowitz , Xavier Leroy , J. B. Wells, Compilation of extended recursion in call-by-value functional languages, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.160-171, August 27-29, 2003, Uppsala, Sweden [doi>10.1145/888251.888267]
	8	Tom Hirschowitz , Xavier Leroy, Mixin Modules in a Call-by-Value Setting, Proceedings of the 11th European Symposium on Programming Languages and Systems, p.6-20, April 08-12, 2002
	9	N. I. Adams, IV , D. H. Bartley , G. Brooks , R. K. Dybvig , D. P. Friedman , R. Halstead , C. Hanson , C. T. Haynes , E. Kohlbecker , D. Oxley , K. M. Pitman , G. J. Rozas , G. L. Steele, Jr. , G. J. Sussman , M. Wand , H. Abelson, Revised5 report on the algorithmic language scheme, ACM SIGPLAN Notices, v.33 n.9, p.26-76, Sept. 1, 1998 [doi>10.1145/290229.290234]
	10	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]
	11	Conor Mcbride , Ross Paterson, Applicative programming with effects, Journal of Functional Programming, v.18 n.1, p.1-13, January 2008 [doi>10.1017/S0956796807006326]
	12	Johan Nordlander, Magnus Carlsson, Andy Gill, Per Lindgren, and Björn von Sydow. The Timber home page, 2008. URL http://timber-lang.org.
	13	OCaml. Objective Caml. http://caml.inria.fr/ocaml/.
	14	S. Doaitse Swierstra , Luc Duponcheel, Deterministic, Error-Correcting Combinator Parsers, Advanced Functional Programming, Second International School-Tutorial Text, p.184-207, August 26-30, 1996
	15	Don Syme. Initializing mutually referential abstract objects: The value recursion challenge. Electr. Notes Theor. Comput. Sci., 148 (2): 3--25, 2006.