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

а именно, преобразование текста программы


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

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

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

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

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


  2. операция аппликации заменяется комбинатором S;
  3. операция абстракции заменяется комбинатором ? = ?x.(?z.x[y,z]);


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


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

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

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

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

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

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






Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий