Repository logo
 

Generating mutually recursive definitions

Accepted version
Peer-reviewed

Type

Conference Object

Change log

Authors

Yallop, J 
Kiselyov, O 

Abstract

Many functional programs — state machines [Krishnamurthi 2006], top-down and bottom-up parsers [Hinze and Paterson 2003; Hutton and Meijer 1996], evaluators [Abelson et al. 1984], GUI initialization graphs [Syme 2006], &c. — are conveniently expressed as groups of mutually recursive bindings. One therefore expects program generators, such as those written in MetaOCaml, to be able to build programs with mutual recursion.

Unfortunately, currently MetaOCaml can only build recursive groups whose size is hard-coded in the generating program. The general case requires something other than quotation, and seemingly weakens static guarantees on the resulting code. We describe the challenges and propose a new language construct for assuredly generating binding groups of arbitrary size – illustrating with a collection of examples for mutual, n-ary, heterogeneous, value and polymorphic recursion.

Description

Keywords

Recursion, fixed points, multi-stage programming, metaprogramming

Journal Title

PEPM 2019 - Proceedings of the 2019 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, Co-located with POPL 2019

Conference Name

POPL '19: 46th Annual ACM SIGPLAN Symposium on Principles of Programming Languages

Journal ISSN

Volume Title

Publisher

ACM