СЕТЛ: РЕАЛИЗАЦИЯ И ПРИМЕНЕНИЕ ТЕОРЕТИКО-МНОЖЕСТВЕННОГО ЯЗЫКА ПРОГРАММИРОВАНИЯ
Д. Я. Левин
Язык Сетл был предложен и разработан в начале 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 году в проекте ВЕТЕ в Нью-Йорке участвовало не менее десяти прекрасно подготовленных сотрудников и аспирантов. Благодаря глобальному пониманию этого проекта Ершовым и поддержке Г. И. Марчука, было подписано межправительственное соглашение о нашем сотрудничестве в области реализации Сетл. Ярким и содержательным событием программы сотрудничества был Советско-Американский Сетл-семинар, состоявшийся ранней осенью 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 …
Из сборника »Становление Новосибирской школы программирования. Мозаика воспоминаний«. Новосибирск, 2001 г.
Перепечатываются с разрешения редакции.
