Подразделы

Другие разделы

Дата и время

30/03/2025 23:40:19

Авторизация

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

Функции и программирование Списки. Функции для работы со списками Определение новых функций Функции высших порядков и /\-выражения Представление и выполнение функциональных программ Виды вычислений. Карринг. Конвейеры. Запоминание. Монады Интерпретация и компиляция функциональных программ Функции высших порядков. Обозначение типа Чистое /\-исчисление. Комбинаторная логика

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

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

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

Таблица 1

Группа	Абстрактная форма	Представление на языке Scheme	Представление на языке Kotlin
Переменные	$x$	`x`	`x`
Константы Числовые Булевы	'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})

Дополнение:
Управляющие конструкции в языке Scheme и Kotlin
Обработка списков в языке Scheme и Kotlin

Чтобы понять, как выполняется функциональная программа, введем понятие контекста. Контекст – это соответствие между переменными и их значениями, которые являются 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]}$ . Таким образом, контекст рекурсивного блока определений содержит сам себя в качестве составной части.

Упражнения