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

Ранее было сказано, что любую формулу можно представить в виде S-выражения. Одним из способов такого представления является язык программирования Scheme, развившийся из языка LISP. В языке Scheme различаются строчные и прописные буквы (в LISP и ранних версиях Scheme – не различаются), идентификатором является любая последовательность букв, цифр и спецсимволов, не начинающаяся с цифры. Способ перевода легко понять из таблицы 1.

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

Таблица 1

Многие функции в языке Scheme можно вызывать с более чем двумя аргументами, например, (+ 1 2 3 4) (сумма аргументов) или (< 1 2 3 4) (список аргументов упорядочен по возрастанию?).

Функция `"отобр"` после перевода на язык Scheme будет выглядеть следующим образом:

(define (отобр x f) 
   (if (null? x) '()
       (cons (f (car x)) (отобр (cdr x) f))))

(отобр '(1 2 3) (lambda (x) (* x x)))

А на языке Kotlin для списка значений типа X так:

fun<X,Y> отобр(x:List<X>, f:(X)->Y):List<Y> =
  if(x.isEmpty()) listOf() else listOf(f(x.first()))+отобр(x.drop(1),f)

отобр(listOf(1,2,3),{it*it})

Чтобы понять, как выполняется функциональная программа, введем понятие контекста. Контекст – это соответствие между переменными и их значениями, которые являются S-выражениями. Каждое выражение в функциональной программе вычисляется в некотором контексте. Например, в контексте `{x\ ->\ (A\ .\ B),\ y\ ->\ (C\ D),\ z\ ->\ 127}` выражение `"cons"(z+1,\ "cdr"(x))` имеет значение (128 . B).

Блоки "пусть" и "где" используются, чтобы установить новые связи. Выражение для значения новой локальной переменной вычисляется в некотором внешнем контексте. Определяемое блоком выражение вычисляется в новом контексте, полученном изменением внешнего контекста за счет добавления новых связей или вытеснения старых связей новыми в случае совпадения имен локальной переменной и переменной в контексте. Например, если выражение `{bb"пусть"\ u="cdr"(x);\ z=z+1\ в\ "cons"(z,"cons"(u,y))}` вычисляется в контексте `{x\ ->\ (A\ .\ B),\ y\ ->\ (C\ D),\ z\ ->\ 127}`, то для вычисления определяемого выражения используется контекст `{u\ ->\ B,\ x\ ->\ (A\ .\ B),\ y\ ->\ (C\ D),\ z\ ->\ 128}` и получается (128 B C D).

Рассмотрим выполнение функции на примере выражения `{bb"пусть"\ f=λ\ (x,y)\ 2*x+y\ в\ f(2,3)+f(3,2)}`. Аргументы функции `f` вычисляются в момент ее вызова, и каждое значение связывается с соответствующим формальным параметром. Таким образом, тело функции вычисляется в контексте, включающим связи каждого из параметров с фактическими значениями. В примере тело функции вычисляется дважды, сначала в контексте `{x\ ->\ 2,\ y\ ->\ 3}`, затем в контексте `{x\ ->\ 3,\ y\ ->\ 2}`. Первый вызов функции `f` дает результат 7, второй – 8, а вычисление всего выражения – 15.

Если `λ`-выражение содержит свободные переменные, то для корректного вычисления функции необходимо знать значения, с которыми были связаны свободные переменные при определении функции. Это делается с помощью замыкания, которое состоит из `λ`-выражения и контекста, определяющего значения свободных переменных. Например, в выражении `{bb"пусть"\ y=3\ в\ {bb"пусть"\ f=λ(x)2*x+y\ в\ {bb"пусть"\ y=4\ в\ f(2)}}}` вычисление выражения `f(2)` идет в контексте `{f\ ->\ [λ(x)2*x+y,\ {y\ ->\ 3}],\ y\ ->\ 4}`.

Можно отметить эквивалентность блока "пусть" и `lambda`-выражения: `{bb"пусть"\ x_1=e_1;\ …;\ x_k=e_k\ в\ e}` `≡` `(lambda(x_1,\ …,\ x_k)\ e)(e_1,\ …,\ e_k)`.

Теперь рассмотрим блоки "пустьрек" и "гдерек", в которых определения взаимно рекурсивны. Если все выражения `e_1,\ e_2,\ …,\ e_k` являются `lambda`-выражениями, то значением для каждого из `x_i` является замыкание `[e_i,\ alpha]`, где `alpha` – это контекст `{x_1\ ->\ [e_1,\ alpha],\ x_2\ ->\ [e_2,\ alpha],\ …,\ x_k\ ->\ [e_k,\ alpha]}`. Таким образом, контекст рекурсивного блока определений содержит сам себя в качестве составной части.

Переведите несколько программ из предыдущих упражнений на язык Scheme и Kotlin.