zbMATH — the first resource for mathematics

Compiling a functional logic language: The Fair Scheme. (English) Zbl 1453.68039
Gupta, Gopal (ed.) et al., Logic-based program synthesis and transformation. 23rd international symposium, LOPSTR 2013, Madrid, Spain, September 18–19, 2013. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8901, 202-219 (2014).
Summary: We present a compilation scheme for a functional logic programming language. The input program to our compiler is a constructor-based graph rewriting system in a non-confluent, but well-behaved class. This input is an intermediate representation of a functional logic program in a language such as Curry or \(\mathcal{TOY}\). The output program from our compiler consists of three procedures that make recursive calls and execute both rewrite and pull-tab steps. This output is an intermediate representation that is easy to encode in any number of programming languages. We formally and tersely define the compilation scheme from input to output programs. This compilation scheme is the only one to date that implements a deterministic strategy for non-deterministic computations with a proof of optimality and correctness.
For the entire collection see [Zbl 1320.68017].
68N20 Theory of compilers and interpreters
68N15 Theory of programming languages
68N17 Logic programming
68N18 Functional programming and lambda calculus
68Q42 Grammars and rewriting systems
Curry; KiCS2; PAKCS; TOY
Full Text: DOI