ON INTERPRETATION OF TYPED AND UNTYPED FUNCTIONAL PROGRAMS

Authors

  • S.A. Nigiyan Chair of Programming and Information Technologies, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2018.52.2.119

Keywords:

typed functional program, untyped functional program, basic semantics, interpretation algorithm, completeness, comparability, translation

Abstract

In this paper the interpretation algorithms for typed and untyped functional programs are considered. Typed functional programs use variables of any order and constants of order $ \leq 1 $, where constants of order 1 are strongly computable, monotonic functions with indeterminate values of arguments. The basic semantics of the typed functional program is a function with indeterminate values of arguments, which is the main component of its least solution. The interpretation algorithms of typed functional programs are based on substitutions, $ \beta $-reduction and canonical $ \delta $-reduction. The basic semantics of the untyped functional program is the untyped $ \lambda $-term, which is defined by means of the fixed point combinator. The interpretation algorithms of untyped functional programs are based on substitutions and $ \beta $-reduction. Interpretation algorithms are examined for completeness and comparability. It is investigated how the “behavior” of the interpretation algorithm changes after translation of typed functional program into untyped functional program.

Downloads

Published

2018-08-15

How to Cite

Nigiyan, S. (2018). ON INTERPRETATION OF TYPED AND UNTYPED FUNCTIONAL PROGRAMS. Proceedings of the YSU A: Physical and Mathematical Sciences, 52(2 (246), 119–133. https://doi.org/10.46991/PYSU:A/2018.52.2.119

Issue

Section

Informatics