Почему мы стремимся к вычислительной полноте
Вот снова ОО-предписание 3 в своей исходной формулировке:
D должен быть вычислительно полным. Это значит, что в D может поддерживаться механизм вызовов из так называемых основных (host) программ, написанных на языках, отличных от D (но эта поддержка не является обязательной). Аналогично, в D может поддерживаться использование других языков для реализации операций, определяемых пользователями (но эта поддержка не является обязательной).
В [1] это предписание комментируется следующим образом:
Я не понимаю текст, начинающийся с «Это значит», – он не является определением того, что означает вычислительная полнота языка. Наличие программ, написанных на других языках, которые можно вызывать из конструкций данного языка или из которых можно вызвать программы, написанные на данном языке, не делает этот язык вычислительно полным.
Конечно, я согласен с тем, что текст, начинающийся с «Это значит», не является определением вычислительной полноты; он для этого и не предназначался, и может быть желательна некоторая переформулировка. Скорее, этот текст предназначался для разъяснения некоторых последствий вычислительной полноты языка D – другими словами, он предназначался для разъяснения того, почему мы считаем вычислительную полноту хорошей идеей. В своей части [1] Хью писал следующее:
Я надеюсь, что обоснование нашего включения требования вычислительной полноты является очевидным. Частично оно состоит в том, что тогда приложения могут писаться на языке D, что позволяет избежать проблем, связанных с потребностью писать их на другом языке, а частично в том, что обеспечивается возможность использования языка D для кодирования реализаций операций, определяемых пользователями.
В ходе дальнейшей переписки в ответ на уже обсуждавшиеся мной критические замечания Хью сказал следующее:
Возможно, нам следовало сказать что-нибудь, подобное следующему: Язык D должен включать полный набор возможностей для реализации приложений баз данных и операций, определяемых пользователями. Для достижения целей было бы достаточно наличия вычислительно полного языка, но от D не требуется вычислительная полнота; не требуется и наличие возможности написания на языке D приложений и операций, определяемых пользователями.
Но если мы соглашается отступить от вычислительной полноты, то как далеко мы можешь отойти? – т.е. где мы проведем границу? Насколько много вычислительных действий можем мы поддерживать безопасно? Если верно то, что вычислительная полнота означает всего лишь возможность вычислять все вычислимые функции, а вычислимая функция означает всего лишь функцию, которую можно закодировать с использованием циклов WHILE, то следует ли нам запретить циклы WHILE? Если да, то с чем мы останемся? Замечание: Конечно, эти вопросы являются теоретическими. Моя позиция достаточно очевидна: я не думаю, что мы можем отойти от вычислительной полноты. Более того, Хью согласен со мной; его намек на то, что от D может не требоваться вычислительная полнота, не был серьезным.
Но имеется еще одна проблема, которую я должен затронуть при обсуждении нашего стремления к вычислительной полноте языка D. Среди прочего, вычислительная полнота означает возможность включения в реляционные выражения вызовов определяемых пользователями операций только чтения, возвращающих значения-отношения, – операций, реализация которых может быть закодирована на самом языке D, возможно, с использованием циклов и других процедурных конструкций, – и некоторые критики могут счесть эту возможность противоречащей исходной цели Кодда относительно того, что все запросы и пр. должны представляться декларативно. Однако мы утверждаем, что вызовы операций только чтения являются в равной степени декларативными, независимо от того, где, как, кем и на каком языке эти операции реализованы (и независимо от того, являются ли они возвращающими значения-отношения). Для иллюстрации рассмотрим следующий пример:
OPERATOR TABLE_NUM ( K INTEGER )
RETURNS RELATION { N INTEGER } ;
... implementation code ...
END OPERATOR ;
При вызове эта операция возвращает отношение, представляющее предикат «N является целым числом в диапазоне от 1 до K» (полезность такой операции демонстрируется в [6]). Тогда, конечно, вызов, например, TABLE_NUM (3149) является в равной степени «декларативным» вне зависимости от того, (a) написан ли код реализации на языке D тем же пользователем, который производит вызов, или (b) он написан некоторым другим пользователем на некотором другом языке, или (c) он предоставляется в составе СУБД.
