Введение в теорию программирования. Функциональный подход



             

Категориальная абстрактная машина - часть 3


Первый этап процедуры трансляции, а именно, преобразование текста программы на языке функционального программирования в соответствующее выражение ламбда-исчисления, был достаточно подробно рассмотрен нами ранее, в ходе изучения синтаксиса языка программирования SML в сопоставлении с синтаксисом ламбда-исчисления.

Рассмотрим более подробно второй этап процедуры трансляции, который состоит в преобразовании полученного выражения ламбда-исчисления в так называемый (промежуточный) код де Брейна, названный так по имени его создателя. Смысл перехода к коду де Брейна состоит в унификации записи и ликвидации коллизии обозначений переменных в ламбда-термах.

Числом де Брейна называется глубина связывания переменной (которое понимается как количество ламбда-абстракций, находящихся в ламбда-терме до данной переменной) без единицы.

При трансляции текста программы на языке функционального программирования в код де Брейна производятся следующие преобразования:

  1. числа де Брейна, замещающие переменные ламбда-термов, заменяются соответствующими комбинаторами n, рассмотренными в ходе предыдущей лекции;
  2. операция аппликации заменяется комбинатором S;

  3. операция абстракции заменяется комбинатором ? = ?x.(?z.x[y,z]);
  4. операция цитирования (в случае наличия в ламбда-терме констант) заменяется комбинатором цитирования ‘ = K = ?x.(?y.x).

Проиллюстрируем кодирование ламбда-терма по де Брейну следующим примером. Пусть требуется закодировать ламбда-терм следующего вида:

?x.?y.((+x)y).

В результате получаем код де Брейна следующего вида:

?(?(S(S(‘+1),0))).

В наших рассуждениях неоднократно использовалось понятие среды вычислений. Среда имеет важнейшее значение в теории и практике языков программирования, поскольку она определяет условия для выполнения той или иной программы в зависимости от характеристик компьютера, операционной системы, транслятора и другого окружения, в котором программа функционирует. Из истории языков программирования естественным образом следует, что в ходе эволюции программных систем среда изменялась в сторону повышения адаптивности и универсальности.


Содержание  Назад  Вперед