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

В функциональных языках могут использоваться разные элементарные и составные типы данных: списки, кортежи, векторы и типы данных, определяемые программистом (см. дополнительный материал для языка Scheme и Kotlin). Рассмотрим упрощенный набор типов данных, характерный для большинства функциональных языков и обеспечивающий строгую функциональность.

Областью определения и областью значений для функций в таком строго функциональном языке являются S-выражения. Элементарными S-выражениями являются атомы (числовые, символьные и булевы константы). Из них строятся списки – последовательности S-выражений, заключенных в скобки, например, ((имя Джон Смит) (возраст 99) (женат #T) (дети (Том Мэри))). Особым S-выражением является пустой список (), который считается атомом. Списки легко реализовать с помощью структуры из двух указателей (рис. 2).

Рис. 2. Представление списка (дети (Том Мэри)) в памяти компьютера

В виде S-выражений можно представить любые структуры данных. Трудности при чтении S-выражений компенсируются легкостью их обработки. В виде S-выражения можно представить и любые формулы, при этом операции переводятся из инфиксной формы в префиксную. Например, `2*x+5` записывается как (+ (* 2 x) 5). Чтобы отличать константные S-выражения от вычисляемых выражений, перед константой будем ставить апостроф. Например, 'x – символьная константа, a x – переменная.

Для обработки S-выражений достаточно пяти функций: `"car"`, `"cdr"`, `"cons"`, `"atom"` и `"eq"`.

Функция car возвращает первый элемент списка.

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

Имена функций `"car"` и `"cdr"` происходят от имен регистров компьютера, на котором был реализован первый компилятор языка LISP. Эти имена сохранились, так как по-зволяют использовать вместо `"car"("cdr"("cdr"(x)))` сокращенную запись `"caddr"(x)` (третий элемент списка `x`).

Функция `"cons"` соединяет два S-выражения в единое S-выражение, таким образом, что первым элементом результата является первый аргумент функции, а хвостом – второй аргумент. При сцеплении двух атомов `"cons"(`'A,'B`)` получается S-выражение, которое не является списком. Будем его записывать как точечную пару (A . B). Результат `"cons"(`'A,()`)` можно также записать либо как список (A) либо как точечную пару (A . ()). S-выражение (A . (B . (C . D))) можно записывать в более простой форме (A B C . D).

Функция-предикат `"atom"` позволяет распознавать, является ли S-выражение списком или атомом.

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

Функции `"car"`, `"cdr"`, `"eq"` являются частичными. Можно определить и общие функции: