J. Nordlander, M. Carlsson, and A. J. Gill, “Unrestricted pure call-by-value recursion,” in Proceedings of the 2008 ACM SIGPLAN workshop on ML, ML ’08, pp. 23–34, ACM, 2008.

Links

• http://doi.acm.org/10.1145/1411304.1411309

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.

BibTeX

@inproceedings{Nordlander:2008:RecBinds08,
  author = {Nordlander, Johan and Carlsson, Magnus and Gill, Andy J.},
  title = {Unrestricted pure call-by-value recursion},
  booktitle = {Proceedings of the 2008 ACM SIGPLAN workshop on ML},
  series = {ML '08},
  year = {2008},
  isbn = {978-1-60558-062-3},
  location = {Victoria, BC, Canada},
  pages = {23--34},
  numpages = {12},
  doi = {10.1145/1411304.1411309},
  acmid = {1411309},
  publisher = {ACM},
  keywords = {call-by-value, combinator libraries, implementation, semantics, value recursion},
}