Функциональное программирование

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

В l-исчислении любой объект является функцией, при этом основное правило преобразования сводится к обычному вызову функции с заменой её параметра на конкретное значение. В выражении f(x), которое используется обычно для представления функции, не ясно: то ли оно означает функцию f, то ли ее значение при заданном значении параметра х. Поэтому для четкого описания функции f вводится выражение λx.f(x). To есть, когда выражение М хотят рассматривать как функцию от х, используют запись λх.М. Таким образом, выражение λx.(x+y) является функцией от х, а не от у. При этом х называется связанной переменной, а у – свободной переменной. Если f= λх.М, то подстановка выражения А в х внутри М называется применением А к f и записывается как fA.

l-выражения определяются рекурсивно при помощи следующих правил:

· если x является именем переменной, то x является l-выражением;

· если М является l-выражением, то λх.М является l-выражением;

· если F и A являются l-выражениями, то (FA) также l-выражение, где F – оператор, а A – операнд.

Для l-выражений определена только одна операция – операция редукции. Если (FA) – l-выражение и F= λх.М, то во всех случаях, где в М встречается свободная переменная x, вместо неё можно подставить A (то есть λх.М A Þ М’). Эта операция аналогична подстановке фактического параметра вместо формального параметра при вызове функции.

Когда к l-выражению применяется операция редукции, оно сводится либо к некоторым константам, либо к другим l-выражениям. Таким образом, все l-выражения являются решением следующего функционального уравнения:

l-выражение = константа + (l-выражение Þ l-выражение).

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

Такой подход предполагает вместо присваивания значений переменным вызов функций с измененными значениями их параметров, однако в традиционных вычислительных машинах с фон-неймановской архитектурой компилятор переводит рекурсию в итерацию и присваивание, так как вызов функции (процедуры) в таких машинах оказывается медленнее, чем повторение тела цикла.

Известным примером языка программирования, реализующего вычисления на основе функциональной модели, является язык обработки списков – Lisp, который был разработан в 1959 году Джоном МакКарти (John McCarthy) и использовался в конце 70-х годов в американской программе по искусственному интеллекту SCI (Strategic Computer Initiative).

4 Лекция №3

Дата добавления: 2014-11-24; просмотров: 282; Нарушение авторских прав

Мы поможем в написании ваших работ!