ON INCOMPARABILITY OF INTERPRETATION ALGORITHMS OF TYPED FUNCTIONAL PROGRAMS WITH RESPECT TO UNDEFINED VALUE

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Submitted: 2025-02-04; Published: 2025-02-04

This work is licensed under Creative Commons Attribution–NonCommercial International License (CC BY-NC 4.0).

Abstract

In the paper the interpretation algorithms of typed functional programs are considered. The interpretation algorithm is based on substitution, β-reduction and canonical δ-reduction. It is shown that seven known interpretation algorithms (FS (of full substitution), PES (of parallel external substitution), LES (of left external substitution), PIS (of parallel inner substitution), LIS (of left inner substitution), ACT (active algorithm), PAS (passive algorithm)) are pairwise incomparable with respect to undefined value (⊥-incomparable).