Логическое и функциональное программирование (стр. 10 из 16)
f(…f(…f…)…).
3.2.1Компьютерное задание
Дана последовательность символов a1, a2, …, an. С применением рекурсии реализовать процедуру инверсии данной последовательности, то есть процедуру получения последовательности b1, b2, …, bnтакой, что b1 = an, b2 = an-1, …, bn-1 = a2, bn = a1.
3.3l-исчисление
В алгебре приводится четкое различие между связанными и свободными переменными в контексте некоторых конструкций. Внутри этих конструкций свободные переменные имеют тот же смысл, что и вне них. Связанные же переменные полностью принадлежат самим конструкциям и вне них пусты, то есть могут быть заменены любыми буквами (за исключением тех, которые используются в данной конструкции).
В выражении
буква x может быть заменена любой другой буквой (за исключением tили f) и смысл выражения от этого не изменится в любом контексте, где это выражение может быть использовано.
В определении функции вида:
… гдеg(x) = a sin(px + q)
буква x также пуста.
С точки зрения вычислительной математики возникает проблема, является ли x именем объекта (областью рабочей памяти) или нет; или x– это объект, значением которого является другое имя. Этот вариант может иметь дальнейшее развитие, когда фактический параметр в g(x) является выражением отличным от простой переменной, например, как в записи g(t2 + 2).
Очевидно, что в основе лежит вопрос определения функций. Для этих целей в 1941 году Черчем было введено l -исчисление. Задать функцию – это означает указать закон соответствия, приписывающий значение функции каждому допустимому значению аргумента. Пусть M– некоторая формула, содержащая x в качестве свободной переменной. Тогда lx.[M] есть функция, значение которой для любого аргумента получается подстановкой этого аргумента в M вместо x. Операцию образования выражения lx.[M] из M и x называют l - операцией или функциональной абстракцией.
В l - исчислении исследуются такие классы формальных систем, в которых используются общие способы применения одних функции к другим.
Основным понятием является понятие функции f, которая сопоставляет по крайней мере один объект f(x1, …, xn) (ее значение) с каждой n – кой объектов x1, …, xn (ее аргументов, которые сами могут рассматриваться как функции). l - исчисление позволяет учитывать специфику вычисления функции в зависимости от используемых аргументов, то есть от того какой из аргументов рассматривается как связанная переменная.
Например, в дифференциальном исчислении выражение x-yможет рассматриваться как функция f от x, либо как функция g от y. Для того, чтобы их различать будем записывать:
f = lx.[x-y], g = ly.[x-y].
Говорят, что префикс lxабстрагирует функцию lx.[x-y] от выражения x-y.
Аналогичные обозначения применяются для функций от многих переменных. Например, x-yотвечает функциям от двух переменных hи k: h(x, y) = x-y, k(y, x) = -y+x. Это можно записать:
h = lxy.[x-y], k = lyx.[x-y].
Однако, можно избежать использования функций от нескольких переменных, если использовать функции, значениями которых являются функции.
Например, определим функцию:
s= lx.[ly.[x-y]],
которая для каждого числа a превращается в
s(a) = lx.[ly.[x-y]](a) = ly.[a-y],
а для каждой пары a, bв
s(a (b)) = s(a, b) = lx.[ly.[x-y]](a, b) = a-b.
Предположим, что имеется бесконечная последовательность переменных и конечная или бесконечная последовательность констант. Атом определяется как переменная или константа. Множество l - термов определяется индуктивно:
1. Каждый атом есть l - терм.
2. Если Xи Y - l - термы, то (XY) - l - терм.
3. Если Y- l - терм, а x – переменная, то lx.[Y] - l - терм.
Приведенное выше определение функции g(x) в этом исчислении записывается следующим образом:
g = l(x).[a* sin(p * x + q)],
а вместо g(t2 + 2) можно записать:
l(x).[a* sin(p * x + q)] (t2 + 2).
За символом l следует еще несколько синтаксических конструкций: вначале идет список связанных переменных, затем выражение, в которое входят эти переменные (тело l - выражения). Если остановиться здесь, то будем иметь функцию без операндов, такую как sin (заголовок функции). Но далее может следовать список фактических операндов. В этом случае имеем результат: взятие функции от этих операндов.
Важное значение приобретает сочетание l - исчисления и рекурсии. Предположим, что существует функция «следующий» - назовем ее next(x) – для каждого целого положительного числа и нуля. На самом деле – это функция x + 1, но будем считать, что + пока не определен.
Используя next, можем задать функцию «предыдущий» - prior(x) (после определения – эта функция будет иметь вид x –1). Определим эту функцию следующим образом:
prior(x) = previous(x, 0) Where previous(y, z) = iif(next(z) = y, z, previous(y, next(z))).
Процесс вычисления prior(x) начинается при z = 0, далее последовательно вычисляются последовательно функции nextдо тех пор, пока следующий для z не будет равен x. Это значение z и является ответом. Теперь можем определить сумму и разность двух чисел.
Sum(x, y) = iif(y = 0, x, Sum(next(x), prior(y))),
Diff(x, y) = iif(y = 0, x, Diff(prior(x), prior(y))).
Обратим внимание, что если y>x, то при вычислении Diff настанет такой момент, когда потребуется вычисление prior(0), а среди положительных чисел нет предшественника нуля. Поэтому говорят, что Diff вычислимо только частично для положительных чисел.
Теперь представим Sum в l - исчислении:
Sum = l(x, y).[iif(y = 0, x, Sum(next(x), prior(y)))]
Можно выполнить дальнейшее преобразование этой функции с помощью l - исчисления. Введя еще одно l - обозначение, убираются все рекурсивные ссылки из тела l - определения:
Sum =lf.l(x, y).[iif(y = 0, x, Sum(next(x), prior(y)))](Sum),
а затем можно совсем убрать объект определения из правой части за счет введения оператора Y такого, что если F – функция, то YF – решение уравнения y = F(x).
Sum = Ylf.l(x, y).[iif(y = 0, x, f(next(x), prior(y)))].
В этом определенииf– связанная переменная, которая при разрешении уравнения может быть заменена на что-либо другое. Следовательно, при замене на Sumполучим:
Sum = YlSum.l(x, y).[iif(y = 0, x,.Sum(next(x), prior(y)))].
В результате введенных обозначений функции принимают форму оператора присваивания (= является приказом), и, как следствие, понятия переменной, константы, литерала могут применяться к функциям также, как и к другим видам значений.
Говорят, что l - исчисление используется для того, чтобы выполнить операцию l - редукции и упростить выражение.
Учитывая, что выражение lx.[Px](a) может быть редуцировано к Pa, выражение:
lf.ly.lx.[f(x, y)],
сформулированное:
lf.ly.lx.[f(x, y)](подсистема)
сводится к
ly.lx.[подсистема(x, y)],
ly.lx.[подсистема(x, y)](ЭВМ)®lx.[подсистема(x, ЭВМ)], а
lx.[подсистема(x, ЭВМ)](процессор)®подсистема(процессор, ЭВМ).
Таким образом, l - редукция осуществляется слева направо, и поэтому lf.ly.lx.[f(x, y)], сформулированное в виде lf.ly.lx.[f(x, y)](любит, Мария, Иван), дает любит(Иван, Мария).
3.3.1Практические задания
1.Определить функцию f(x, y) = iif(x>y, sin(x), cos(x)) в l - исчислении. Дать ее запись для x=t и y=p/2. Осуществить редукцию.
2.Осуществить редукцию следующих l - выражений:
lf.[lg.[lt.[f(g(x)+t(y)]]](sin, cos, tg),
lg.[lt.[lf.[f(g(x)+t(y)]]](sin, cos, tg),
lf.[lt.[lg.[f(g(x)+t(y)]]](sin, cos, tg),
3.4Использование списков
Введем некоторые определения. Символ - это набор букв, цифр и специальных знаков. Кроме символов будем использовать: числа, Т – истина, Nil – ложь или пустой список. Будем понимать под константами – числа, Т, Nil. Будем понимать под атомами символы и числа. Назовем списком упорядоченную последовательность, элементами которой являются атомы или другие списки (подсписки). Будем заключать списки в круглые скобки, а элементы списка разделять пробелами.
Формально список можно определить следующим образом:
Список :- Nil / (голова Ç хвост)
[Список либо пуст, либо это пара голова и хвост]
голова :- атом / список
[рекурсия в глубину]
хвост :- список
[рекурсия в ширину]
Другой вариант определения:
Список :- Nil / (элемент элемент … )
Элемент :- атом / список
[рекурсия]
Обратим внимание, что атом это не список, хотя символ может идентифицировать список. Каждый символ имеет значение. Им может быть список, в том числе и пустой, константа, функция, которую рассматривают как специальный символ. Для записи функций будем использовать префиксную нотацию, т.е. x + y будем записывать, как (+ xy).