Примеры. Функция длвычисления длины списка

Функция дл вычисления длины списка

дл(х) º if(x) = nil then 0 else дл(cdr(x)) + 1

Вычислим функцию для конкретного списка.

дл(A, B, C) = дл(B, C) + 1

дл(B, C) = дл(C) + 1

дл(C) = дл(nil) + 1

дл (nil) = 0

"Пройдя" в обратном направлении можно получить числовое значение.

Обращение списка обр, то есть список A, B, C обратится в список C, B, A

обр(x, y) º if x = nil then y else обр(cdr(x), cons(car(x), y))

Вычислим функцию для конкретного списка

обр(A, B, C, nil) = обр((B, C), (A))

обр((B, C), (A)) = обр((C), (B, A))

обр((C), (B, A)) = обр((nil), C, B, A)

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

Функциональный язык Бэкуса.

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

Интересный функциональный язык РЕФАЛ был разработан в 70-х годах нашим соотечественником Турчиным и исподльзовал математическую модель нормальных алгорифмов Маркова.

Но, пожалуй, наибольший резонанс у теоретиков программирования имел функциональный язык, предложенный Дж. Бэкусом 1979 году. Он был создан, одним из "отцов" фортрана не только как альтернатива Фортрану и всем прочим процедурным языкам, но в известной мере и как альтернатива LISP, синтаксис которого ориентировался на устаревшее представление об архитестуре компьютера, да и в области математической логики за тот период произошли заметные подвижки.

Следуя за Дж. Бэкусом сравним процедурный и функциональные стили программирования.

Пусть у нас есть фрагмент процедурной программы:

с:= 0

for i:= 1 to N do c:= c + a[i] * b[j]

Беспристрастный, но строгий анализ показывает очевидные недостатки процедурного программирования:

1. Операторы работают с невидимыми значениями переменных.

2. Программа неиерархична (операторы одного уровня).

3. Программа динамична (чтобы её понять необходимо её выполнить).

4. Последовательно выполняются операции с отдельными элементами массива.

5. Часть данных находится в программе.

6. Программа называет свои операнды, предварительно их записав.

7. Отсутствует механизм сбора мусора - ненужные части программы продолжают находиться в памяти.

На языке, предложенном Бэкусом, та же самая задача решается проще:

(/+) ° (a*) ° T:

где

Т – транспозиция (проектирование),

° - композиция,

/ - вставка,

a - применить ко всем (applay to all)

это функциональные формы, они оперируют функциями

+ и * - традиционные функции.

Приведем пример выполнения этой программы:

(/+)°(a*)°T:<<1,2,3>,<6,5,4>>

кортеж из двух кортежей

(/+)°(a*): <<1,6>,<2,5>,<3,4>>

(/+): <6,10,12>

:28

Достоинства метода:

1. Нет невидимых данных.

2. Программа иерархична, т.к. есть не только функции, но и функциональные формы.

3. Статическое описание программы. Программа читается «за один проход».

4. Работаем сразу со всеми данными, а не с отдельными элементами.

5. В теле программы нет никаких данных.

6.В программе нет названий операндов.

7. Сбор мусора - программы и данные эволюционируют в процессе вычислений.

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