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
Аннотация:
В данной работе рассматриваются интерпретаторы типизированных функциональных программ. Алгоритм интерпретации основан на подстановках,
$\beta$-редукции и канонической
$\delta$-редукции. Основная семантика типизированных функциональных программ есть функция с неопределенными значениями аргументов, которая является главной компонентой ее наименьшего решения. Если значение основной семантики для некоторых значений аргументов есть неопределенность, то алгоритм интерпретации либо останавливается со значением
$\bot$, либо работает бесконечно. Показано, что семь известных алгоритмов интерпретации являются попарно несравнимыми относительно неопределенного значения. Это следующие алгоритмы: FS (полной подстановки), PES (параллельной внешней подстановки), LES (левой внешней подстановки), PIS (параллельной внутренней подстановки), LIS (левой внутренней подстановки), ACT (активный алгоритм), PAS (пассивный алгоритм).
Ключевые слова:
typed functional program, canonical
$\delta$-reduction, interpretation algorithm,
$\bot$-incomparability.
MSC: 68N18 Поступила в редакцию: 07.05.2018
Принята в печать: 30.05.2018
Язык публикации: английский