High order programming in extended FP. (English) Zbl 0574.68013

Functional programming languages and computer architecture, 2nd Conf., Nancy/France 1985, Lect. Notes Comput. Sci. 201, 65-80 (1985).
[For the entire collection see Zbl 0566.00026.]
This article is concerned with functional programming without variables. The new language JYM is presented. This language is a programming oriented version of FP systems of J. W. Backus.
First, it is shown that JYM can be used for high level programming since it allows functionals, dynamic computations and definitions of functional forms.
Then an extensional fixed-point operator is constructed using the tools added to FP in order to define JYM. The main theorem shows that the three following functions are extensionally equal: a recursive function ordinarily defined and computed by the interpreter, the fixed-point obtained by applying the previously defined fixed-point operator to the functional associated to the recursive definition, the least fixed-point of this functional.
This result allows the semantics of JYM to be defined inside JYM. That is: JYM is his own metalanguage. More than this, the semantics of JYM can be defined without the use of an environment. So that JYM is an efficient and well-founded functional programming language without variables.


68Q60 Specification and verification (program logics, model checking, etc.)
68N01 General topics in the theory of software


Zbl 0566.00026