Левин Д.Я. Сетл: Реализация и применение теоретико-множественного языка программирования

Появление Сетла

Язык Сетл был предложен и разработан в начале 70-х годов профессором Нью-Йоркского университета Джекобом Шварцем (Jacob Schwartz). Это стало выдающимся событием: математик с мировым именем смело вошел в область программирования с радикальным практическим предложением. Оно состояло в том, чтобы, базируясь на множествах как основных типах данных, писать программы в терминах высокоуровневых непроцедурных алгоритмов, широко использующих логико-предикатные средства.

Вот два характерных примера записи на Сетле исполняемых алгоритмов.

Напечатать простые числа, меньшие N:
Print {n < N | not exist k, 1 < k < n | div (n, k)}

Выборка из базы данных:
Print { rec in DB | rec.age < 30 & rec.salary > good_salary}

В 1972 году Дж. Шварц по пути из Китая сделал короткую остановку в Новосибирске и рассказал о Сетле на семинаре в Вычислительном Центре. Организация этого выступления и последующего проекта Сетл в Новосибирске стали еще одним подтверждением выдающейся чуткости А.П. Ершова к фундаментальным тенденциям в программировании.

Формирование Сибирского проекта

Новосибирская Сетл-команда сформировалась естественным образом. Л.В. Городняя и Л.В. Черноброд к этому времени уже обладали огромным опытом работы с языком Лисп и его реализацией. Вкус к языку повышенного уровня, динамике данных, знание фундаментальных принципов и тонкостей этой области позволили им быстро оценить новый проект и энергично приступить к его реализации. Применение Лиспа для моделирования семантики Сетла имело свои преимущества и недостатки. С одной стороны, операции с подвижными и иерархическими множествами, включая необходимую для них сборку мусора (garbage collection), хорошо поддерживались базовыми механизмами Лиспа. С другой стороны, поскольку множества — это далеко не списки, то реализация ассоциативных выборок, построение теоретико-множественных объединений, пересечений, дополнений и др. в принципе не могли быть эффективно реализованы на Лиспе. В целом реализация на Лиспе сыграла ключевую роль прототипа, позволившего практически войти в проблематику Сетла.

В начале 70-х гг. А.А. Ляпунов неоднозначно относился к тенденциям программирования в целом, считая, что близорукая прагматическая составляющая оставляет слишком мало места для развития совершенно необходимой программированию подлинно системно-кибернетической и математической основы. Появление Сетла обрадовало и заинтересовало Ляпунова, известного своими фундаментальными результатами в теории множеств, до такой степени, что он откомандировал меня, своего бывшего дипломника, только что вернувшегося из армии сотрудника его лаборатории, "заниматься Сетлом к Ершову".

Высокий профессионализм, творческий энтузиазм, прекрасная атмосфера интеллигентного коллектива, занятого в востребованной обществом сфере деятельности, интересная задача — все это, увиденное в Отделении Ершова, помогло мне быстро и практически включиться в проект Сетл. Опыт Лисп-реализации и полученные к тому времени результаты группы Дж. Шварца (BALM-SETL) показали, что продвижение к эффективной реализации нового языка лежит через построение специальной виртуальной машины, прицельно поддерживающей принципиальные элементы теоретико-множественного программирования. Создание такой машины, версии входного языка, компилятора и окружения — это стало моей задачей в 1973-75 гг.

Первые результаты

Сравнительно быстрому получению практических результатов способствовал выбор в качестве средства реализации Сетла системы ЭПСИЛОН-БЭСМ-6. Ее автор — А.Е. Хоперсков — отнесся к моей работе весьма неравнодушно, давая многочисленные тонкие советы и не жалея времени на разбор ошибок. Роль ЭПСИЛОНа оказалась тем более важна, что почти в то же самое время в группе Шварца началось применение вполне аналогичного средства — языка LITTLE. Сегодня, в эпоху сугубо интерактивной работы с компьютером, полезно вспомнить колоды с тысячами перфокарт, напряженное внимание к их прохождению через службу приема задач и машинный зал БЭСМ-6. Впрочем, это уже были далеко не те легендарные и по-настоящему героические времена 60-х годов: в 1973 году мне удавалось в пакетном режиме совершить до 20-25 запусков в день...

Реализация СЕТЛ-ЭПСИЛОН имела свои плюсы и минусы. С одной стороны, экспериментальная реализация так и не была доведена до профессионально сделанной системной программы, содержала много трюков, ошибок и др. С другой стороны, эта быстрая, прагматичная, иногда с изощренными алгоритмами, реализация позволила почти сразу начать довольно широкое программирование на Сетле. Это привело к появлению эффектных примеров, практической пропаганде средства "very high level" (русский перевод всегда выглядел нескромно), стимулированию дальнейших работ и пр.

Это было прекрасное время безоглядной игры мускулами - возможностями очень быстро написать почти неалгоритмическую программу и наслаждаться ее работоспособностью. Было, например, проведено моделирование весьма модной в те годы fuzzy logic. Сделано это было на примере системы, которая по фразе типа "Нарисуй небольшой круг в правом нижнем углу экрана, а над ним - маленький квадрат" действительно печатала звездочками на АЦПУ довольно адекватную конфигурацию. Это была лишь игрушечная иллюстрация фундаментальной лингвистической модели "Смысл-Текст", восходящей к известному советскому лингвисту И.А. Мельчуку, а также глубокого проекта "Рисунок-Информация-Текст", выполнявшегося под руководством А.С. Нариньяни. Как раз в то время в Отделе Ершова находился некий докторант самого Заде: мне и сегодня приятно вспомнить, как был поражен иностранный гость, когда увидел, как вся основа fuzzy logic практически в том же синтаксисе записывается на Сетле и ... работает.

Примерно в 1975 году мне довелось провести несколько ознакомительных занятий по Сетлу для группы математических лингвистов НГУ. Умные и симпатичные студентки без затруднений писали короткие абстрактные алгоритмы в форме теоретико-множественных выражений, но не хотели верить в то, что "программы", в которых отсутствовали изнурительные атрибуты "настоящего" языка программирования, могут непосредственно исполняться на ЭВМ. "Язык программирования - это ФОРТРАН", — говорили опытные лингвистки.

В это время появились первые отечественные публикации о Сетле. Наряду со статьями о СЕТЛ-ЛИСП и СЕТЛ-ЭПСИЛОН большое значение имела работа В.Н. Касьянова, посвященная оптимизации. Действительно, "повышенный" уровень языка Сетл, новые типы данных, операции и языковые конструкции могли стать серьезным вызовом для развития и применения оптимизационной техники.

Поддержка и влияние корифеев

В 1974 году на Всесоюзной конференции в Бакуриани, при первом выходе в свет с Сетлом, я столкнулся с явным и глубоким интересом профессионалов к этому проекту. Этому способствовало и выступление В.М. Брябрина, который незадолго до этого провел несколько недель в Нью-Йоркском университете, и смог ярко рассказать об американском проекте. Вообще, отношение к Сетлу было всегда заинтересованное и благожелательное. Наряду с А.П. Ершовым — Берс, Брябрин, Котов, Лавров, Любимский, Тыугу, Поттосин, Фуксман и другие классики отечественного программирования сразу оценили стратегическую перспективу вклада, сделанного Джекобом Шварцем, и постоянно проявляли практический интерес к отечественному проекту.

Особое влияние на судьбу новосибирского проекта СЕТЛ оказал А.С. Нариньяни, когда эти работы стали вестись в рамках возглавляемой им Лаборатории Искусственного Интеллекта (ИИ). Главное состояло в том, что Александр Семенович предложил широко использовать Сетл для экспериментального программирования задач ИИ. Это был по-настоящему смелый и мудрый поступок: респектабельность в области ИИ предписывала пользоваться Прологом, а профессиональное программирование подразумевало безнадежную неэффективность языков высокого уровня. Позиция Нариньяни была свободна от консерватизма: Пролог намертво фиксировал как раз то, что должно было составлять суть экспериментов в ИИ, а "неэффективность" давно следовало трезво оценивать с позиций требований конкретных приложений. Вероятно, без определенного давления Нариньяни траектория Сибирского Сетла была бы гораздо более аккуратной и академичной. С сегодняшних позиций я без оговорок рад, что все произошло именно так, как произошло.

Советско-Американский Проект

Мне кажется, Джекоб Шварц оценивал неэффективность созданного им языка лишь в целом, равномерно и, как мне кажется, переоценил ее, чем надолго задержал крупные эксперименты по прототипированию и, тем более, построению приложений. Впрочем, свою миссию профессор Шварц выполнял и выполнил блестяще: она состояла, видимо, не в том, чтобы построить с помощью Сетла какие-то интересные прототипы, а в том, чтобы предложить в чистом виде новую фундаментальную парадигму программирования и в чистом же виде максимально полно показать ее проблемы.

К 1976 году в проекте SETL в Нью-Йорке участвовало не менее десяти прекрасно подготовленных сотрудников и аспирантов. Благодаря глобальному пониманию этого проекта Ершовым и поддержке Г.И. Марчука было подписано межправительственное соглашение о нашем сотрудничестве в области реализации Сетл. Ярким и содержательным событием программы сотрудничества был Советско-Американский Сетл-семинар, состоявшийся ранней осенью 1976 года. Сначала была собственно формальная часть, проходившая в Москве, а затем большая часть американской делегации провела неделю в Новосибирске. На московском семинаре гости представили полную картину своих работ, сделав десять докладов; мы рассказали о своей реализации, а также об истории программирования в СССР; надолго запомнились ужины в ресторанах "Пекин" и "Славянский Базар", а также выступление Э. Дейкстры, почти случайно заехавшего на наш семинар во время своего турне по СССР... В Новосибирске состоялись интенсивные сопоставления реализаций, оценка возможных приложений, обсуждение проблем.

Применение Сетла в Сибири

Первым заметным сибирским применением Сетла была реализация с его помощью прототипа системы общения с базой данных на естественном языке, выполненная в 1976 году. Прототип состоял из словаря, лингвистического процессора, переводящего естественно-языковые запросы к базе данных в некоторый стандартизованный язык СУБД, а также из собственно макета СУБД, включая и наборы демонстрационных данных. Лингвистический процессор был построен как компилятор, осуществляющий несколько проходов и основанный на продукционных правилах, которые принимали во внимание главным образом несинтаксическую информацию. Макет СУБД хорошо подтверждал исходное предположение Шварца о естественности применения Сетла для работы с базами данных. У этой Сетл-программы, занимавшей не более двухсот строк и за 1-2 секунды отвечавшей на вопросы типа "Кто завлаб в лаборатории, где средняя зарплата не меньше 150 рублей?", оказалась хорошая история. Во-первых, ее многочисленные варианты эффектно демонстрировались затем лет десять, применительно к дюжине языков и нескольким предметным областям. Во-вторых, она послужила зерном, из которого выросли развитые обстановки для создания процессоров естественного языка. В-третьих, из нее выросла система СТЕНД — интегрированный инструментальный комплекс программирования.

В те годы мы в Лаборатории ИИ пропагандировали принцип оптимистического программирования: решать программистскую задачу на самом высоком языковом уровне, который допускают реальные требования данного приложения. Именно Сетл в то время дал фактическую возможность выбора между оптимистической и прочими позициями. СТЕНД — это была наивная, но благородная попытка построить "полную" инструментальную среду, в которой программист не должен был опускаться ниже уровня Сетла. Выше Сетла были продукционные системы, СУБД, а самое главное — конструктор виртуальных процессоров. Наш аспирант, а впоследствии ведущий сотрудник, И.Е.Швецов прекрасно и чисто реализовал механизм универсального интерпретатора УНИК, который должен был работать в сочетании со специальными процессорами. В идеале программы виделись как суперпозиции троек процессоров: данных, вычислений и интерфейсов.

Кульминация и развязка

Примерно в 1977 году созрела идея сравнительно крупного международного эксперимента: в Национальном Центре Здоровья в Вашингтоне силами двух Сетл-групп построить высокоуровневую систему управления данными. В те годы такая идея требовала длительной бюрократической подготовки, которая при солидной поддержке Государственного Комитета по Науке и Технике (ГКНТ) была завершена к осени 1979 года. Нужно не по литературе знать тогдашние реалии, чтобы оценить и здесь проявившуюся раскованность А.С. Нариньяни, который сам предложил перенести нашу с ним двухмесячную поездку на последующую весну, ибо, по его мнению, зимняя одежда членов Советской делегации была на постыдном уровне самых низов американского народа.

Пожалуй, это была кульминация Сетл-проекта как в Новосибирске, так и в Нью-Йорке. В декабре 1979 случился "Афганистан", после чего года три-четыре чиновник из ГКНТ, лелея мечту о действительно интересном международном проекте, безнадежно справлялся у нас, не могут ли наши американские коллеги нажать на Госдепартамент...

В дальнейшем наша работа с Сетлом была в основном связана с развитием вышеупомянутых прототипов, а также с серией переносов системы с БЭСМ-6 на другие машины (Burroughs 6700, ЕС ЭВМ, НОРД), совместными экспериментами с чехословацкими коллегами, некоторыми контактами с возникшим на короткое время проектом в Ростовском университете. Заметное оживление Сетл-деятельности наблюдалось в ходе легендарного проекта СТАРТ (1985-88).

Послесловие

А.П. Ершов никогда не менял своей точки зрения на Сетл как фундаментальное явление программирования. Важно, что он способствовал появлению черт Сетла в языковых средствах "детской информатики", хорошо понимая их роль в освоении базовых понятий программирования.

Дж. Шварц, достаточно долго поддерживая интерес к своему детищу, затем все-таки перенес свой основной творческий интерес на другие области: сначала на робототехнику, а затем — на мультимедийные средства. ("Jack's style has been to enter a new field, master quickly the existing research literature, add the stamp of his own forceful vision in a series of research contributions, and finally, leave behind an active research group that continues fruitful research for many years along the lines he has laid down." — Martin Davis, Professor of Computer Science and Mathematics at NYU).

Хорошо понимаю, как мне повезло с Сетлом: интереснейшая задача, возможности карьеры, а самое главное — контакты с замечательными людьми.

Что я думаю про Сетл сегодня? Ценность теоретико-множественных и логико-предикатных элементов лексикона общения с ЭВМ не может устареть по определению. Другое дело, в какой контекст будут практически погружены эти элементы и какова будет архитектура их реализации.

Здесь необходимо вспомнить, что исходной идеей Шварца был язык абстрактных алгоритмов. С одной стороны абстрактные алгоритмы должны были реально исполняться и давать полноценную возможность прототипирования. С другой стороны абстрактность алгоритмов подразумевала возможность их регулярной конкретизации. Уже в 1976 году в наших проектах появились библиотеки представлений множеств и методов работы с ними. В чем-то тот подход даже опережал время, но в нем был и принципиальный источник трудностей: отсутствие индустриальной базовой системы программирования и закрытость набора методов. Сегодня теоретико-множественная оболочка могла бы вполне продуктивно работать на основе C++ или Java...




Вы обнаружили ошибку в следующем тексте:
Просто нажмите кнопку "Отправить сообщение об ошибке" для завершения. Вы можете также ввести комментарий (желательно).