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

printПредставление и выполнение функциональных программ

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

Числовые
Булевы
'x
'(1 2 3), '()
10, 1.25
#T, #F
'x или (quote x)
'(1 2 3), '()
10, 1.25
#t или #T, #f или #F
"x"
listOf(1,2,3), listOf<T>()
10, 1.25
true, false
Арифметические операции`x+y`, `x–y`, `x*y`, `x//y`,
`–x`, `x^y`, `x\ mod\ y`
(+ x y), (– x y), (* x y), (/ x y),
(– x), (expt x y), (remainder x y)
x+y, x-y, x*y, x/y,
–x, x.pow(y), x%y
Сравнения`x\ =\ y`, `x\ ≠\ y`,
`x\ <\ y`, `x\ >\ y`,
`x\ ≤\ y`, `x\ ≥\ y`
(= x y), (not (= x y)),
(< x y), (> x y),
(<= x y), (>= x y)
x==y, x!=y,
x<y, x>y,
x<=y, x>=y
Логические операции`bb"не"\ x`, `x\ и\ y`, `x\ bb"или"\ y`(not x), (and x y), (or x y)!x, x && y, x || y
Обработка списков`"car"(x)`, `"cdr"(x)`, `"cons"(x,y)`,
`"atom"(x)`, `"eq"(x,y)`,
`"null"(x)`, `"number"(x)`
(car x), (cdr x), (cons x y),
(not (pair? x)), (eqv? x y),
(null? x), (number? x)
x.first() или x[0], x.drop(1), listOf(x)+y,
x !is List<*>, x===y,
x.isEmpty(), x is Int, x is Double
Вызов функции`f(x_1,x_2,…,x_n)`(f x1 x2 … xn)f(x1,x2,...,xn)
Условное предложение`bb"если"\ e_1\ bb"то"\ e_2\ bb"иначе"\ e_3`(if e1 e2 e3)if (e1) e2 else e3
Блоки локальных определений`{e\ bb"где"\ x_1=e_1;\ …;\ x_k=e_k}`
`{bb"пусть"\ x_1=e_1;\ …;\ x_k=e_k\ в\ e}`
`{e\ bb"гдерек"\ x_1=e_1;\ …;\ x_k=e_k}`
`{bb"пустьрек"\ x_1=e_1;\ …;\ x_k=e_k\ в\ e}`
(let ((x1 e1) … (xk ek)) e)

(letrec ((x1 e1) … (xk ek)) e)
{val x1=e1;...; val xk=ek
  e} нужно добавить () после } если не часть if/while

через использование lateinit var
`λ`-выражения`lambda(x_1,x_2,…,x_n)e`(lambda (x1 x2 … xn) e){x1,x2,...,xn -> e}
или просто {e} для одного аргумента с именем it
Определения`f(x1,x2,…,"xn")=e`
`g=e`
(define (f x1 x2 … xn) e)
(define g e)
fun f(x1:T1,...,xn:Tn):T = e
val g=e (с явным указанием типа val g:T=e)
Отложенные вычисления`bb"задержать"\ e`
`bb"возобновить"\ e`
(delay e)
(force e)
lazy {e}
e.value
Многие функции в языке 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.
loading