A General Method for Defining Objects by Recursion over Syntax

Simon Thompson (University of Kent, United Kingdom)

Abstract: In this paper we look back to work done in the late 1980s, and that looked at links between grammars, data types and recursion principles, and illustrating it with examples that include enumerations of types and developing a structure editor. The work is introduced by a historical foreword, and closes with an afterword that discusses some of the subsequent developments of these ideas.

Keywords: Miranda, algebraic data type, coinduction, generic programming, grammar, higherorder function, recursor, syntax, verification

Categories: D.1.1, D.2.4, D.3.3