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


Вступительная лекция - часть 2


БНФ и сегодня являются теоретически адекватным и практически применимым средством формализации синтаксиса языков программирования.

В 90-х годах синтаксис современного языка программирования SML был сформулирован Р. Милнером (Robin Milner). В работах, описывающих синтаксис SML, и по сей день широко используются формы Бэкуса-Наура.

Что касается теоретических основ семантики вычислений, то в конце 60-х годов Д. Скотт (Dana S. Scott) предложил применить для формализации семантики математических теорий так называемые домены (пока будем неформально понимать их как особый вид множеств). При этом на основе доменов Д. Скоттом был предложен так называемый денотационный подход к семантике. Такой подход предполагает анализ синтаксически корректных конструкций языка (или, иначе, денотатов) с точки зрения возможности вычисления их значений посредством специализированных функций.

Далее, в 70-х годах, М. Гордон (Michael J.C. Gordon) исследовал аппарат денотационной семантики применительно к языкам функционального программирования и сделал вывод об адекватности и практической эффективности использования этого подхода для решения поставленной задачи.

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

Одним из практических результатов исследований в этом направлении стала разработка П. Лендином (Peter J. Landin) семантики модели языка программирования в форме абстрактной машины (т.е. модели компьютера), использовавшей понятие состояния.

Альтернативный подход к формализации семантики (который был осуществлен в рамках исследования так называемой операционной семантики языков программирования) привел к созданию Ч. Хоаром (Charles A.R. Hoare) аксиоматического метода, моделирующего отношения и причинно-следственные связи, возникающие между операторами языка программирования.

Развитие операционной семантики языков программирования привело Р. Флойда (Robert W.


Начало  Назад  Вперед



Книжный магазин