2 Постановка задачи: о связном предъявлении теории информатики и практики программирования в теме исполнения для теоретического мышления. 13 (стр. 6 из 25)
Хочется отметить преимущества бестиповости лямбда-исчисления (и Лиспа также, так как он основан на этой теории). Продемонстрируем это на примере, показывающем, что аргумент одной и той же функции может выступать в роли как функции, так и данного (в нашем случае целого числа). Здесь также используется карринговость l-исчисления.
Рассмотрим функционал Ф2 = lf. lx. f (f x) композиции функции. Так, применение этого функционала к функции g и числу 3 дает нам Ф2 g 3 ® g(g 3).
Посмотрим вычисление выражения (Ф2Ф2) g 3.
(Ф2Ф2) g 3 ® (lx. Ф2 (Ф2 x) g 3 ® Ф2 (Ф2 g) 3.
Далее вычисления могут идти двумя путями. Могут использоваться ленивые вычисления (вычисления параметров откладывается до их использования) или энергичные вычисления (сначала вычисляются все параметры, затем только - применение функции).
Итак, при ленивых вычислениях:
® (Ф2 g) (Ф2 g 3) ® (lx. g (g x)) (g (g 3)) ® (g (g (g (g 3)))) = g4 3;
при энергичных:
® Ф2 (lx. g (g x)) 3 ® (lx. g2 (g2 x)) 3 = g4 3.
Первоначально при описании функционала предполагалось применение его к двум аргументам: функции и объекту. Но при вычислениях в качестве x выступает также функция g. Бестиповость языка позволяет нам сделать это.
Отметим, что все объекты Лиспа - это S-выражения. Более того, программа на Лиспе сама является S-выражением, то есть не существует явных ключевых слов. Это приводит к одинаковому представлению программ и данных.
Язык FP.
Во всех языках, рассмотренных выше, определение функции дает имена объектам, передаваемым этой функции, и описывает затем, что делать с этими переданными аргументами. Поначалу этот подход кажется самым простым для понимания: определение функций принимает вид набора уравнений. Однако одной из наиболее сильных сторон функциональных языков является то, что они поддаются формальным преобразованиям. Одной из форм преобразования - “заменить равное равным”. В языке FP каждая функция выражается именно таким образом.
Отличительной особенностью FP является то, что в нем нельзя выражать функции высшего порядка, определенные пользователем. Все функции высшего порядка являются встроенными - это комбинирующие формы “применить-ко-всем”, левая вставка и правая вставка. Так, в FP существует аналог функции map, работающей со списками: a f обозначает функцию, которая применяет f к каждому элементу в заданной последовательности аргументов.
(a f) : <x1,¼,xn>=<f : x1,¼, f : xn>
Например, a tl применяет функция выделения хвоста последовательности к заданной последовательности последовательностей (tl - примитив языка):
(a tl) : <<1 2 3>,<4 5 6>>=<tl : <1 2 3>, tl : <4 5 6>>=<<2 3><5 6>>.
Функционалы правая и левая вставка определяются следующим образом:
(/f) : <x> = x базовый случай
(/f) : <x1,¼,xn> = f : <x1, /f : <x2,¼,xn>> - правая
и
(\f) : <x> = x базовый случай
(\f) : <x1,¼,xn> = f : <\f : <x1,¼,x-1>, xn> - левая.
Существуют также варианты вставок, имеющие связанные с ними базовые случаи. Они указываются индексами у символов \ и /.
С помощью этих встроенных функционалов мы можем записать нерекурсивный вариант такой функции как n!. Мы увидим, как FP хорошо иллюстрирует мощность функциональной нотации, и в особенности выразительную силу функций высшего порядка.
Рекурсивный вариант:
def fac = eq 0®1; *·[id, fac·(-·[id, 1])]
где · - композиция функций,
id - тождественная функция (id : x = x),
1 - константа 1,
[] - “конструкция”: [f1,¼,fn] : x = <f1 : x,¼,fn : x>.
Заметим, что в этом определении нет ссылок на объекты, и поэтому нет символов применения функции. Тело состоит целиком из функций и функционалов. При применении fac к конкретному числу выражения становятся более привычным:
fac : 3 º eq 0 : 3 ® 1; * : <3, fac : (- : <3, 1>)> = * : <3, fac : (- : <3, 1>)>.
Нерекурсивный эквивалент:
def fac = /1 * · i,
где /1 - функция вставки (со значением в базовом случае, равном 1),
i - примитив, при применении к n этот генератор дает последовательность целых от 1 до n.
Тогда fac : 3 = /1 * : <1, 2, 3> = * : <1, /1* : <2, 3>> =
= * : <1, * : <2, </1* : 3>>> = * : <1, * : <2, * : <1, 3>>>> =
= * : <1, * : <2, 3>>> = * : <1, 6> = 6.
3.1.2 Неподвижная точка как подходящее обобщение проблемной ориентированности.
Термин "неподвижная точка" встречается в различных разделах математики: в теории рекурсивных функций и алгоритмов, теории множеств, логике, теории автоматов, математическом анализе. Главный теоретический инструмент, использующий данное понятие - это теорема о неподвижной точке (или "теорема Клини").
В языках программирования высокого уровня необходимо иметь возможность записывать определение рекурсивных функций. Мы можем это сделать, так как имеем возможность дать имя любой функции f, а затем ссылаться на это имя где угодно в программе (при определённых ограничениях, обусловленных языком), даже в теле функции, названной этим именем, например, f(f(x)). Однако в l-исчислении функции не имеют имён. Они представляются l-выражениями (впрочем, это единственный объект l-теории). Поэтому для представления рекурсии необходимо придумать какой-то метод, который позволит функциям вызывать себя не по имени, а каким-то другим образом. Этим способом может быть механизм копирования аппликаций: то есть вид l-выражения остаётся неизменным, а рекурсия будет осуществляться уже при выполнении, посредством копирования тела функции. Для этого и используется неподвижная точка.
· Неподвижная точка в лямбда-теории.
Перейдём непосредственно к решению проблемы рекурсии в l-исчислении. Для этого представим рекурсивную функцию как функцию, имеющую себя в качестве аргумента. Таким образом, она будет содержать в своём теле ссылки на себя. Рассмотрим данный метод на примере функции факториал:
Обобщим выражение E(F) посредством l-абстракции
lf. lx. (x=0 | 1 | * x (f (- x 1))).
Обозначим эту абстракцию через G. Возникает уравнение для оператора G: z=Gy.
Чтобы смоделировать рекурсию, необходимо иметь оператор Y со следующим свойством
YG = G(YG) = lx. (x=0 | 1 | * x (YG (x-1))).
Тогда оператор Y для операторного уравнения z=Gy отыскивает неподвижную точку
YG = G(YG).
Тогда рекурсивная функция F с телом Е(F) записывается в l-исчислении в виде:
Y (lF. E(F)).
Осталось определить оператор неподвижной точки Y. Нам необходимо записать Y в виде l-выражения, так как чистое l-исчисление не имеет встроенных функций. Вид Y встречается при доказательстве теоремы о неподвижной точке в l-исчислении:
Теорема. " f $ x (f x = x).
Доказательство:
Возьмём w = l x. f(xx). Тогда искомым x является ww. Проверим утверждение теоремы: x = ww= (l x.f(xx)) w=f(ww)=f x.
■
Как видно из доказательства оператором Y является:
Y = l h. (l x. h(xx))(l x. h(xx)).
Убедимся, что именно это выражение и есть оператор неподвижной точки Y. Применим его к произвольной функции f:
Y f = (l h. (l x. h(xx))(l x. h(xx))) f =
= (l x.f(x x)) (l x.f(x x)) = f ((l x.f(x x)) (l x.f(x x))) = f (Yf)
Однако данный способ работает только в случае использования так называемого ленивого вычислителя, который “не делает ничего, пока это не потребуется“. В терминах традиционного программирования ленивое вычисление можно соотнести с вызовом по необходимости, в котором все аргументы передаются функции в невычисленном виде и вычисляются только тогда, когда в них возникает необходимость внутри тела функции. Если же использовать аппликативный порядок вычислений или энергичный вычислитель, который соответствует вызову функции по значению (при применении функции к аргументу последний сначала вычисляется, а затем уже передается функции) то самоприменение приводит к зацикливанию:
Y f ® f(Y f) ® f(f(Y f)) ® ¼
Однако можно модифицировать определение Y так, чтобы обойти эту проблему, определив альтернативный Y-комбинатор как:
Y1 = lh. (lx. h(ly. xxy))(lx. h(ly. xxy))
Y и Y1 h-эквивалентны, поскольку один можно получить из другого с помощью h-преобразования (ly. xxy =h xx[1]). Если теперь вместо Y использовать Y1, самоприменение вычисляется, только когда оно применяется к аргументу, соответствующему переменной y, например, к целому аргументу функции факториал F.
Пример энергичного(по значению) вычисления F=lf. lx. (x=0|1|*x(f(- x 1))).
Y1F 3 ® (lx. F (ly. xxy))(lx. F (ly. xxy)) 3 ®
®F (lz. (lx. F (ly. xxy))(lx. F (ly. xxy)) z ) 3 ®
® (* 3 ((lz. (lx. F (ly. xxy))(lx. F (ly. xxy)) z ) 2)) ®
® (* 3 ((lx. F (ly. xxy))(lx. F (ly. xxy)) 2)) ® /* (* 3 (Y1 F 2)) */
® ¼ ® (* 3 (* 2 (* 1 (lx. F (ly. xxy))(lx. F (ly. xxy)) 0)))®
®(* 3 (* 2 (* 1 1)))®6.
Так как w1w10 ® F (ly. w1w1y) 0 ® 1, где w1=(lx. F (ly. xxy)).
Таким образом, с помощью комбинаторов механизм рекурсии заменяется механизмом подстановки и эквивалентных преобразований.
Реализовать комбинатор Y можно двумя способами: в виде лямбда-выражения или, если все лямбда-выражения представлены в графовой форме, Y просто реализуется установкой циклического указателя (см. п. редукционные реализации).