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


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


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

Еще в 1924 г. М. Шейнфинкель (Moses Schonfinkel) разработал простую (simple) теорию функций, которая фактически являлась исчислением объектов-функций и предвосхитила появление ламбда-исчисления – математической формализации, поддерживающей языки функционального программирования (т.е. программирования в терминах функций).

Затем в 1934 г. А. Черч (Alonso Church) предложил собственно исчисление ламбда-конверсий (или ламбда-исчисление) и применил его для исследования теории множеств. Вклад ученого был фундаментальным, так что теория до сих пор называется ламбда-исчислением и часто именуется в литературе ламбда-исчислением Черча.

Позднее, в 1940 г., Х. Карри (Haskell Curry) создал теорию функций без переменных (иначе называемых комбинаторами), известную в настоящее время как комбинаторная логика. Эта теория является развитием ламбда-исчисления и представляет собой формальный язык, подобный языку функционального программирования.

В 60-х годах Х. Барендрегтом (H. Barendregt) были детально описаны синтаксис (т.е. форма конструкций) и семантика (т.е. значение конструкций) ламбда-исчисления.

Именно синтаксис и семантика являются наиболее существенными понятиями, фактически определяющими произвольный язык программирования.

В 60-х годах Дж. Бэкусом (John Backus) были созданы основы формализации синтаксиса языков программирования посредством специального математического языка. Позднее П. Науром (Peter Naur) этот язык (а с точки зрения целевого языка программирования — метаязык) был доработан, в результате чего возникла математическая нотация, известная и сегодня под названием "форм Бэкуса-Наура", или, сокращенно, БНФ.

Данная нотация была специально разработана с целью формализации синтаксиса языка программирования (в то время это был весьма популярный, прежде всего в математической среде, язык программирования ALGOL 60 с ясным, но довольно пространным синтаксисом).


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



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