Задачи для самостоятельного решения

Задача 11.4. Задана таблица примитивных бинарных операций над целыми, в которой идентификатору операции сопоставлена двуместная функция. Например, такая таблица может иметь следующее содержание:

type Table = [(String, Integer -> Integer -> Integer)]

opTable: Table.

opTable = [(«+ «, (+)),(«-», ,(«/», div),(«%», mod)].

Требуется написать функцию, которая преобразует заданное выражение, представленное типом данных Ехрг из задачи 11.3, вычисляя в выражении константные выражения, использующие указанные в таблице функции, и подставляя вместо таких выражений результат вычисления. Например, выражение, которое в расширенном лямбда-исчислении имело вид Ах. х+ (2*2), должно быть преобразовано в выражение Ах. х+4. Функция должна иметь тип.

evaluate:: Table -> Ехрг -> Ехрг После преобразования в выражении не должно остаться ни одного применения примитивной функции из заданной таблицы к двум целочисленным константам.

Задача 11.5. Напишите функцию, которая проверяет, находится ли выражение, представленное значением типа Ехрг, описанного в задаче 11.3, в нормальной форме. Выражение находится в нормальной форме, если оно не содержит ни одного рили 5-редекса. Заметим, что выражение может находиться в слабой заголовочной нормальной форме, не находясь при этом в нормальной форме.

Задача 11.6. Расширьте eval/apply-интерпретатор, приведенный в листинге 11.1, таким образом, чтобы он приводил заданное выражение не к слабой заголовочной нормальной форме, а к нормальной форме. Заметим, что такое приведение к нормальной форме может не сводиться к чисто формальным преобразованиям выражения из-за возможного конфликта имен переменных. Ваша программа должна обнаруживать и разрешать такие конфликты. Конечно, как и в случае версии интерпретатора в листинге 11.1, программа может никогда не закончить работу для заданного исходного выражения, если нормальной формы для него не существует.