Аппликативный компьютинг: попытки установить природу вычислений

ВЕСТНИК УДМУРТСКОГО УНИВЕРСИТЕТА


КОМПЬЮТЕРНЫЕ НАУКИ                              2009. Вып. 2



УДК 004.07(063)

© В. Э. Вольфенгаген, Л. Ю. Исмаилова, С. В. Косиков, А. Д. Лаптев,
В. И. Назаров, В. В. Рословцев, И. С. Сафаров, А. Л. Степанов

АППЛИКАТИВНЫЙ КОМПЬЮТИНГ:




                ПОПЫТКИ УСТАНОВИТЬ ПРИРОДУ ВЫЧИСЛЕНИЙ




В настоящей работе отражены результаты, полученные при выполнении проектов 93-01-00943-а (ЛАМБДА), 96-01-01923-а (КООАМ), 05-01-00736-а, 06-07-99005-с, 05-07-90236-в, 07-07-00298-а, 07-07-00355-а, 07-07-12098-офи, поддержанных грантами РФФИ. Если на ранних стадиях программирование представляло собой вид искусства, когда программист писал программу для решения определенной задачи и сопровождал ее более или менее подробно составленной документацией, то теперь создана мощная индустрия программирования с сопутствующей ей инженерией программирования. В настоящее время в исследованиях по программированию или в сфере компьютерных наук, как правило, поддерживаются работы, в которых вносится некоторое небольшое улучшение в решение уже хорошо известной проблемы. Вместе с тем из виду упускаются действительно важные и фундаментальные исследования, ведущие к поиску новых концепций вычислений на компьютере и недостаточное внимание уделяется накоплению знаний в области программирования.
   В настоящей работе основное внимание уделено вычислениям с объектами, удельный вес и роль которых в данной области все более возрастает, превращаясь в доминирующую тенденцию.

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




                Введение




   Для компьютинга центральным вопросом является установление того, что и как может быть эффективно автоматизировано. Это нередко связывают в применением компьютеров, осуществляющих те или иные вычисления. Термин «вычисление» предполагает, что речь пойдет об использовании чисел, об оперировании числами, получении числовых результатов.
   В случае же аппликативных систем применим термин «компьютинг», поскольку в них среди исходных понятий нет чисел. Для них самое общее толкование компьютинга, по-видимому, все еще работает, хотя в этом и нет абсолютной уверенности. Выражаясь более точно, с появлением аппликативных систем вопрос о границах представления о компьютинге требует нового изучения. Как оказывается, причин тому имеется несколько.
   Если все же соглашаемся говорить о вычислениях, то нужно отдавать себе отчет в том, что аппликативное вычисление не похоже на обычное. Оно выполняется на переплетении цепочек возможных путей вычислений, которые представляют собой связи конвертируемости, отражающие трансформации объектов. При этом одни объекты могут редуцироваться к другим, либо подвергаться экспансии до других объектов.
   Рассматриваемые объекты не похожи на те сущности, которыми оперируют в объектноориентированном подходе (см. [4]). В процессе конверсии участвует па,ра, объектов, первый из которых играет роль редекса, а второй — контракта. Процесс конверсии является двунаправленным, представляя собой редукцию в одном направлении и экспансию в другом. Таким образом, пара объектов ‘редекс-контракт’ участвует в процессе ‘редукции-экспансии’, обеспечивающем взаимные переходы между редексами и соответствующими им контрактами. Ком-плексирование редекс-контракт подчиняется законам аппликативных вычислений.
   Объекты, участвующие в вычислении, не обязательно находятся в нормальной форме. Они могут иметь вид редекса, который может быть заменен на соответствующий контракт, т. е. участвовать в процессе редукции. В то же время каждый контракт может быть заменен на

Аппликативный компьютинг

119

КОМПЬЮТЕРНЫЕ НАУКИ                                                    2009. Вып. 2

его редекс, участвуя в процессе экспансии. Представлением для этих объектов может быть сам двунаправленный процесс редукции-экспансии, причем равновесие этого процесса при необходимости может быть смещено в ту или иную сторону. Таким образом, для этих объектов, участвующих в процессе конверсии, имеются представления сущностями об-систем, а последние обладают необходимыми математическим свойствами.
   Шаг «вычисления» состоит в следующем.
   Выбирается пара объектов, один из которых определяется как соответствующий виртуальной функции, порожденной процессом конверсии, а второй — как соответствующий виртуальному аргументу, который также порожден конвертированием. Затем первый объект апплици-руется, или применяется к другому. Результат апплицирования рассматривается как представляющий значение, полученное на шаге вычисления. В результате этого процесса возникают пары объектов, первым в которых является ‘аппликация’, а вторым — ‘результат апплицирования’, то есть это пары аппликация-означивание.
   Цепочки конверсий, в которых участвуют компонентные объекты, сплетаются. Вычисления, в общем случае, могут оказаться бесконечными и никогда не завершаться. В этом случае ответ на вопрос о получении значения оказывается непростым.
   В этой общей ситуации лучшим терминологическим решением будет говорить об ‘ап-плицировании’ вместо ‘вычисления’, а когда речь заходит о результате апплицирования, то есть о ‘значении вычисления’, то здесь можно воспользоваться термином ‘означивание’. Пара ‘апплицирование-означивание’ точнее отражает суть процессов, происходящих в аппликатив-ных системах.




                § 1. Осуществление аппликативного компьютинга




   Обсуждение осуществления компьютинга можно вести двояких образом. Во-первых, можно исходить от обычного компьютера, основанного на арифметике, а тогда отправным пунктом является система вычислений, в которой можно реализовать погружение аппликативной вычислительной системы. Во-вторых, располагая системой аппликативного компьютинга, в ней можно сформировать погруженную, или встроенную числовую систему, скажем, арифметику, для которой напрямую и подходит термин ‘вычисление’.




                1.1. Обычные системы вычислений




   Многие из этих систем вычислений уже осуществлены, а их возможности в большей или меньшей степени освоены на практике, другие находятся в стадии разработки. Для них характерно то, что они находятся в процессе постоянных доработок и усовершенствований, в погоне за дополнительными возможностями. В ряде систем возникает переизбыток возможностей, освоить которые на практике за разумный период времени не представляется возможным.
   В результате обычные системы вычислений и соответствующие им языки программирования постоянно разрастаются в объеме, но их выразительные возможности при этом не изменяются. В их основе лежат модели не только далекие от совершенства, но содержащие изъяны, а попытки их преодоления дают нагромождение деталей, усложняя восприятие вычислительных идей, затрудняя реализацию и снижая ее эффективность. Наиболее распространенный стиль вычислений состоит в обработке одного слова в данный момент, разворачивание последовательности моментов приводит к последовательной обработке «слово за словом». Семантика таких вычислений опирается на переходы состояний, что приводит к разделению вычисляемых конструкций на два класса: выражения и команды, или операторы. Это само по себе не дает возможности развивать мощные приемы комбинирования имеющихся «вычислительных блоков» для формирования из них более крупных новых блоков. Кроме того, обычные системы вычислений основываются на достаточно сложной и запутанной математической основе, которой не только не достает концептуальной ясности (см. [1]), но и относительно которой никак не возникает согласия в среде специалистов. Их разногласия выражаются в многочисленных публикациях в виде статей, написанных специальным языком, доступным немногим