RUS  ENG
Full version
JOURNALS // Proceedings of the Yerevan State University, series Physical and Mathematical Sciences // Archive

Proceedings of the YSU, Physical and Mathematical Sciences, 2018 Volume 52, Issue 2, Pages 109–118 (Mi uzeru466)

Informatics

On incomparability of interpretation algorithms of typed functional programs with respect to undefined value

D. A. Grigoryan

Chair of Programming and Information Technologies YSU, Armenia

Abstract: In the paper the interpretation algorithms of typed functional programs are considered. The interpretation algorithm is based on substitution, $\beta$-reduction and canonical $\delta$-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 ($\bot$-incomparable).

Keywords: typed functional program, canonical $\delta$-reduction, interpretation algorithm, $\bot$-incomparability.

MSC: 68N18

Received: 07.05.2018
Accepted: 30.05.2018

Language: English



© Steklov Math. Inst. of RAS, 2024