Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

A.6. РЕКУРСИИ

855

Дадим точное определение рекурсии.

Прежде всего,рекурсия определяет частичные функции.Частичные функ-

ции могут быть частично упорядочены. При стандартном теоретико-множе-

ственном представлении функций такое упорядочение может быть описано

следующим образом. Функция f 4 g, если G{f} ⊆ G{g}, где G — график

функции f. Содержательно это означает, что g доопределяет f. Естественно,

что две функции, противоречащие друг другу (дающие разные значения для

одного и того же x

) просто несравнимы.

Нигде не определенная функция, функция ошибки ⊥ является наимень-

шим элементом в получившемся чуме.

Во всяком чуме можно определить естественную топологию. Окрестно-

стями функции f считаются все множества функций, замкнутые вверх (как

говорят, верхние конусы), содержащие f. Таким образом, любая окрестность

f содержит вместе с нею и все ее пополнения. Функция над функциями (фун-

кционал, как обычно ее называют) Φ непрерывна, если для каждой окрест-

ности ее результата O

Φ(f)

можно найти окрестность ее аргумента R

, такую,

что если g ∈ R

, то Φ(g) ∈ O

Φ(f)

. Это — стандартное топологическое опре-

деление непрерывности, копирующее и обобщающее определение для дей-

ствительных чисел.

Там, где появляется топология, появляются и пределы. В частности, пре-

дел возрастающей последовательности функций f

— наименьшая функция

lim

n→∞

, принадлежащая всем окрестностям f

Лемма A.6.1. Любая возрастающая последовательность функций имеет

предел.

Непрерывный функционал перерабатывает предел последовательности в

предел своих значений на этой последовательности

Φ( lim

n→∞

Предложение A.6.2. Любой непрерывный функционал имеет неподвижную

точку.

Следствие A.6.3. Всякий непрерывный функционал имеет наименьшую не-

подвижную точку.

Теперь заметим,что,если условный терм t,содержащий свободную функ-

циональную переменную f, рассматривать как функционал λf. t(f ), то он

856

ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

является непрерывным. Соответственно, он имеет наименьшую неподвиж-

ную точку.

Определение A.6.9. Рекурсивная функция f, определяемая схемой

f ← t(f)

это наименьшая неподвижная точка функционала λf. t(f ).

Конец определения A.6.9.

Такое определение позволяет, в частности, поставить вопрос о том, какие

стратегии вычисления рекурсивных функций корректны, а какие нет. Из не-

го, в частности, получается, что вычислять нужно всегда прежде всего са-

мую внешнюю функцию, если терм не условный, и условие терма, если терм

условный, заменяя эту функцию на ее определение. Если внешняя функция

уже является исходной либо импортированной, то вычисляется самая внеш-

няя рекурсивная функция в одном из ее аргументов, и так далее. В любом

случае заменяться на свое определение должна рекурсивная функция ли-

бо рекурсивный предикат, у которого нет объемлющих вызовов рекурсивно

определенных функций.

Если же мы попытаемся заменять внутреннее определение, то мы можем

выдать ошибку в том случае, если внутренняя функция не определена, но

она не вызывается из-за того, что ее вызов в определении внешней функции

оказывается в невыполненной альтернативе условного терма.

Другое содержательное истолкование такого абстрактного определения

касается уже самого графика рекурсивно определенной функции. Вначале

мы определяем значения t(f), подставляя вместо f функцию ошибки ⊥, и

тем самым задается базис рекурсии, когда значение t(f) определяется без

всякого обращения к f . Затем мы подставляем в t получившуюся функцию

, определяя f

= λx. t(f

), и так далее.

Пример A.6.10. Рассмотрим определение сложения (??). Тогда Add

опре-

делено лишь для y = 0 и всегда дает x. Add

определено уже и для y = 1 и

для него выдает x + 1 и так далее. Объединением всех этих ограниченных

рекурсий и является Add.

Конец примера A.6.10.

Построенное нами определение естественно обобщается на тот случай, ко-

гда несколько функций одновременно задаются рекурсивной схемой общего

A.6. РЕКУРСИИ

857

вида. Во-первых, топология на кортежах функций [f

, . . . , f

] является пря-

мым произведением топологий на соответствующих пространствах функ-

ций. Если расшифровать это предельно точное, но абстрактное, выражение,

получается, что кортеж

, . . . , f

] 4 [g

, . . . , g

]

тогда, когда для всех i f

4 g

. Точно так же доказывается, что любая воз-

растающая последовательность кортежей функций имеет предел, и функция,

определяемая рекурсивной схемой общего вида — наименьшая неподвижная

точка функционала, перерабатывающего вектор функций

f в вектор функций

f), или, другими словами, функционала λ

f).

Упражнения к § A.6

A.6.1. Постройте деревья, соответствующие спискам из примера A.6.2.

A.6.2. Постройте индуктивные определения длины и высоты списка.

A.6.3. Является ли nilэлементом списка (())?А списка ((()))?А списка ((), ())?

A.6.4. Можно ли в определении списка заменить второй пункт на следую-

щий: конечное множество атомов и списков — список?

A.6.5. Пусть L есть (A, ((D, E), C), B), a есть (D, E). Постройте L[a | nil],

L[a | true], L[a | (F, F, F )].

A.6.6. Пусть L есть (A, ((D, E), C), B, (D, E)), a есть (D, E).Постройте L[aknil],

L[aktrue], L[ak(F, F, F )].

A.6.7. Имеет ли смысл выражение nil[nil|A]? Если да, то чему оно равно?

A.6.8. Дайте индуктивное определение L[a | M].

A.6.9. (Для тех, кто знаком с элементарными понятиями топологии). Пусть

на импортированной алгебраической структуре задана некоторая то-

пология и все импортированные функции непрерывны. Все остальные

атомы считаются изолированными точками.Если уже определены окрест-

ности l

, ..., l

, то окрестностями (l

, . . . , l

) являются прямые произ-

ведения окрестностей l

Верно ли,что простейшая композиция также непрерывна на своей обла-

сти определения?

858

ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

A.6.10. Какие функции действительных чисел будут простейшими компози-

циями, если импортировать поле действительных чисел?

A.6.11. А если импортировать кольцо действительных чисел?

A.6.12. Функция f инвариантна относительно данного элемента a списка

L, если для любого M f(L[a|M]) = f(L)[akM]. Всегда ли можно по

простейшей композиции f определить такие n и m, что f инвариантна

относительно всех вершин, стоящих не ранее чем на n-том месте либо

на глубине не менее чем m?

A.6.13. Переносятся ли результаты упражнения A.6.12 на условные термы?

A.6.14. Определите предикат, проверяющий, является ли его аргумент спис-

ком.

A.6.15. Определите предикат, проверяющий, является ли его аргумент одно-

элементным списком.

Постройте функции, вычисляющие:

A.6.16. Весь кортеж кроме последнего элемента

HEAD*

A.6.17. Добавление элемента в качестве последнего члена списка

ADD*

A.6.18. Перестановка членов кортежа в обратном порядке

INV

A.6.19. Вытягивание списка в линейный

LINE

, то есть построить список из

всех атомов, находящихся в данном списке, в списках, являющихся его

членами, и т. д.

A.6.20. Применение функции f(x) ко всем членам списка.

A.6.21. Проверка предиката P (x) для всех членов списка (вычисление логи-

ческой формулы ∀x ∈ L P (x)).

A.6.22. Постройте алгоритм

CONCAT

,вычисляющий соединение списков как

кортежей.

A.6.23. Постройте алгоритм, проверяющий, выполнен ли предикат P(x) хо-

тя бы для одного члена списка, т.е. вычисляющий логическую формулу

∃x ∈ L P (x).

A.6. РЕКУРСИИ

859

A.6.24. Постройте всюду определенный предикат,проверяющий является ли

его элемент одноэлементным списком.

A.6.25. То же самое для списка из двух элементов.

A.6.26. Список назовем чистым, если он удовлетворяет следующему индук-

тивному определению.

1. nil, true, false — чистые списки.

2. Если все элементы списка чистые, то и список чистый.

Постройте предикат, проверяющий,является ли список чистым.

A.6.27. Постройте предикат, проверяющий равенство двух чистых списков.

Предикат должен быть всюду определенным.

A.6.28. Пусть задан предикат EQ(x, y), проверяющий равенство произволь-

ных атомов. Построить предикат, проверяющий равенство произволь-

ных списков.

A.6.29. Есть ли в чуме функций наибольший элемент? Если его нет, есть ли

максимальные и чем они являются?

A.6.30. Есть ли у функции минимальная окрестность, если есть. из чего она

состоит?

A.6.31. Что является окрестностями ошибки ⊥?

A.6.32. Перепишите понятие предела возрастающей последовательности в

терминах лишь частичного порядка. Чем является предел последова-

тельности для множества ее членов с точки зрения частичного поряд-

ка?

A.6.33. Мы воспользовались неубыванием непрерывного функционала

∀f, g(f 4 g ⇒ Φ(f) 4 Φ(g)).

Докажите это утверждение.

A.6.34. Если у функций f и g есть верхняя грань, то каким свойством эти

функции обладают и чем является эта грань?

860

ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

A.6.35. Если у функций f и g есть нижняя грань, то каким свойством эти

функции обладают и чем является эта грань?

A.6.36. Разберитесь, что вычисляет функция

f(x) ← if x > 100 then x − 11 else f(f(x + 10)) ﬁ.

A.6.37. Верно ли, что совокупность функций, определяемая схемой







, . . . , x

) ← t

, . . . , x

)

···

, . . . , x

) ← t

, . . . , x

)

является наименьшей совместной неподвижной точкой всех функцио-

налов λf

. t

, . . . , f

§ A.7. СОВМЕСТНОСТЬ И ПАРАЛЛЕЛИЗМ

Совместное и параллельное исполнение характеризуются с точки зрения

математических моделей тем, что время, в котором происходит исполнение

программы, рассматривается как частично-упорядоченное множество. Если

два момента времени несравнимы, то соответствующие действия могут ис-

полняться в любом порядке.Но заметим,что совместность и параллелизм да-

ют существенно разные вычислительные модели. Лучше всего рассмотреть

это на элементарном примере.

Пример A.7.1. Сильная трехзначная логика Клини.

В программировании мы все время должны принимать во внимание эф-

фект неудачи либо провала. Клини предложил следующее расширение клас-

сической логики на случай вычислений, не всегда приводящих к результату.

В приведенных таблицах u означает, что аргумент зациклился либо выдал

ошибку (распознать и разделить заранее два этих случая в принципе невоз-

можно).

& t f u

t t f u

f f f f

u u f u

∨ t f u

t t t t

f t f u

u t u u

⇒ t f u

t t f u

f t t t

u t u u

t f

f t

u u

A.7. СОВМЕСТНОСТЬ И ПАРАЛЛЕЛИЗМ

861

Таким образом, если один из аргументов гарантирует значение связки не-

зависимо от значения другого аргумента, это значение выдается. В програм-

мировании часто говорят (используя теорию как заклинание), что пользуют-

ся этой логикой. Но последовательными программами она реализована быть

не может. Чтобы вычислить значение связки в логике Клини, нужно запу-

стить два процесса вычисления аргументов параллельно, и завершить вычи-

сление, если хоть один из них выдал ответ, гарантирующий значение связки.

Если один из процессов выдал ошибку, второй должен, не обращая на это

внимание, продолжать вычисления.

Если аргументы вычисляются совместно, то может выполняться (даже

если совместность перенесена на уровень элементарных действий, реализу-

ющих вычисления аргументов) один из них, а про второй можно забыть и не

получить результата.

Если же совместность дополнить предписанием переходить к следую-

щим элементарным действиям каждого процесса лишь после того, как будут

закончены оба действия либо одно закончится, а другой процесс завершится

ошибкой, то опять можно вычислить значения в логике Клини.

Конец примера A.7.1.

Данный пример иллюстрирует два из трех базовых случаев параллелизма,

выделенных в теории программирования.

1. &-параллелизм. Процессы идут независимо друг от друга, пока все они

не завершатся. Результат суммирует в себе результаты всех процессов.

Нужно ли останавливать все вычисление при ошибке одного из про-

цессов, определяется характером решаемой задачи.

2. ∨-параллелизм. Процессы идут независимо друг от друга, пока один из

них не завершится успехом (как говорят, они соревнуются). Вычисле-

ние должно продолжаться, невзирая на ошибки и неудачи отдельных

процессов. Лишь неудача всех процессов служит причиной остановки

вычисления.

3. Конвейерный параллелизм.Выполняется по одному элементарному дей-

ствию из каждого процесса, затем они обмениваются данными, и вы-

числение продолжается.

Этот вариант параллелизма был исторически первым разработанным и внедренным в

практику вычислений. Во время Великой французской революции потребовалось срочно

пересчитать все артиллерийские, геодезические и навигационные таблицы в связи с перехо-

862

ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

4. Общий параллелизм. Процессы выполняются независимо, пока не вой-

дут в критический интервал. В критическом интервале каждый про-

цесс может быть задержан внешней управляющей программой, пока не

освободится общий ресурс, либо может подождать сам, пока не будут

готовы данные от другого процесса, либо, наоборот, первые из процес-

сов, вошедшие в критический интервал, могут быть объявлены непри-

косновенными, пока его не покинут.

Все эти случаи детально рассмотрены в программистской литературе.

дом на метрическую систему. Было усажено несколько десятков грамотных солдат, которые

выполняли сложение либо вычитание результатов, полученных ими от заранее установлен-

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

кому следует. В итоге мало того, что таблицы были пересчитаны в рекордно малое время и с

низкими затратами, они еще и стали самыми лучшими в мире (пока русские артиллеристы

под руководством гр. Аракчеева не составили свои таблицы).

Приложение B

Методологические результаты

В данной главе собраны в виде краткого обзора (или, скорее, конспекта)

результаты теории и анализа, которые:

• не столь прямо применимы, как собранные в предыдущей;

• как правило, большей частью опускаются в современных вузовских

курсах, делающих упор на ‘позитивном’ знании;

• полностью перевернули за XX век истинно научное мировоззрение.

Желающим подробнее ознакомиться с данными результатами рекомен-

дуем изучать фундаментальную теорию (стандартный совет литредакторов

советского времени плохим писателям был «Читайте классиков!»). Настоя-

щего образования никогда ничто не заменит. Другое дело, что чаще всего оно

большей частью результат самообразования (и порою попадания в удачную

неформальную группу).

Внимание! Мировоззрение позитивизма (в широком смысле, включая

сюда структурализм и фаллабилизм) или «квазирелигию прогресса» мы не

считаем по-настоящему научным мировоззрением. Их адепты предпочита-

ют закрывать глаза на существующие трудности и увлекаться слишком упро-

щенными моделями.Тем самым, на словах декларируя прогресс, на деле они,

путем замалчивания недостатков и отсутствия серьезного анализа ошибок,

способствуют тупиковому развитию либо застою.

§ B.1. ЛОГИЧЕСКИЕ ПАРАДОКСЫ

Парадокс — рассуждение либо высказывание, в котором, пользуясь сред-

863

864

ПРИЛОЖЕНИЕ B. МЕТОДОЛОГИЧЕСКИЕ РЕЗУЛЬТАТЫ

ствами, не выходящими (по видимости) за рамки логики, приходят к заведо-

мо неприемлемому результату. Ввиду того, что парадоксы обнажают скры-

тые концептуальные противоречия и переводят их в прямые и открытые,

они, согласно законам творческого мышления, помогают при развитии но-

вых идей и концепций.

Первым примером логического парадокса явился парадокс лжеца, припи-

сываемый Эпимениду. Простейшей формой его является следующее рассу-

ждение:

Если некто произнес лишь одно предложение:

«Я лгу,»

— сказал

ли он правду? Если предположить, что он сказал правду, то он

солгал, а если он солгал, то он сказал правду.

Заметим, что это рассуждение никак не зависит от закона исключенного тре-

тьего, оно доказывает утверждение формы A ≡

A. Более того, оно не за-

висит от семантики утверждений, и поэтому может считаться чисто синтак-

сическим парадоксом, который показывает, что утверждение, ссылающееся

само на себя, часто просто не может быть корректно проинтерпретировано.

Многие известные парадоксы восходят к парадоксу лжеца. Рассмотрим, на-

пример, парадокс Рассела:

Пусть

— множество всех множеств, не являющихся собствен-

ными элементами, т.е.

R = {x | x /∈ x}

. Тогда

Z ∈ Z

означает,

что

Z /∈ Z

Более тонко обыграна крайняя опасность автореференции (предложений,

ссылающихся на самих себя) в парадоксе Карри.

Пусть

— некоторое высказывание. Пусть

— высказывание

“

Если

, то

.” Допустим

. Тогда

B ⊃ A

. Значит, из

следует

, и

доказано. Но тогда доказано и

Таким образом, Карри показал, что обычная импликация в любой системе с

автореференцией позволяет вывести любое предложение, что является гру-

бой формой противоречия (противоречивость по Карри.)

Новый класс логических парадоксов был открыт Берри, который ввел в

рассмотрение сложность объекта.

Предложений, содержащих менее ста букв, конечное число. По-

этому с их помощью можно определить лишь конечное число на-

туральных чисел. Поэтому есть наименьшее число

, не опре-

делимое таким способом. Но тогда фраза “Наименьшее число, не