Prolog: три портрета через 50 лет

Давайте вернёмся в историческое прошлое и посмотрим на события периода с 1970 по 1976 годы глазами создателей языка логического программирования Prolog: Алана Колмероэ, Роберта Ковальски и Дэвида Уоррена.

Алан

Алан Колмероэ (Alain Colmerauer) окончил Гренобльский политехнический институт (Grenoble Institute of Technology). Там же, в Гренобле в 1967 году он защитил докторскую диссертацию на тему синтаксического анализа текстов на естественном языке. Именно интерес Алана к синтаксическому анализу в конце концов привел как к разработке метода логического программирования, так и реализации этого метода — языка программирования Prolog.

Монреальский университет

В период с 1967 по 1970 годы Алан Колмероэ работал ассистентом профессора информатики Монреальского университета (University of Montreal). Он руководил проектом TAUM‑METEO (Traduction Automatique de l’Université de Montréal), предназначенным для автоматического перевода прогнозов погоды с английского на французский языки (напомним, что Канада англоязычная и франкофонная страна). Для структуризации данных Алан создал метод направленных преобразований графов по заданным правилам грамматики, а также формальный язык Q‑Systems, Программную реализацию формализмов Q‑Systems Алан написал на языке программирования Algol. Q‑systems ввели в эксплуатацию к октябрю 1969 года.

Приложение Q‑systems бурно развивалось. Выпускники Монреальского университета Мишель ван Канегем (Michel van Caneghem) и Франсуа Стеллин (Franqois Stellin) переписали Q‑systems на языке программирования Fortran. Дело в том, что именно язык Fortran в то время присутствовал почта на каждом крупном вычислительном комплексе. В свою очередь Жиль Стюард (Gilles Steward) версию на Fortran адаптировал для суперкомпьютера Control Data Corporation CDC 6400 и дополнил модулем фазы перевода. Брайан Харрис (Brian Harris) дополнил формализмы Q‑systems морфологическим анализом английского языка. Ричард Киттредж (Richard Kittredge) написал содержательную грамматику для анализа английского языка, а Жюль Дансеро (Jules Danserau) — грамматику для синтеза французского языка. Мишель ван Канегем (Michel van Caneghem) разработал полную морфологию французского языка.

В 1970 году Жан Трудель (Jean Trudel) — аспирант Алана Колмероэ, — писал диссертацию на тему автоматического доказательства теорем. Изучая литературу он натолкнулся на публикацию Алана Робинсона (Alan Robinson) о принципе резолюции при доказательстве теорем. Статья оказалась сложна для понимания Жана и он обратился за разъяснениями к Алану. Алан объяснил Жану теоретическую основу статьи. Но самого Алана заинтересовало практическое применение этой теории в его исследованиях. Алан узнал, что Мартину Дэвису (Martin Davis) разработал полный инструментарий доказательств теорем с унификацией, написанный в современном стиле программирования: все вычисления заключались в модицификации указателей. Алан договорился с Мартином о том, что тот прочитает курс лекций Жану. Мартин Дэвис не колеблясь согласился и Жан Трудель поехал в Нью‑Йорк добывать новые практические знания для исследований Алана.

Университет Экс-Марсель

В 1970 году университет Экс‑Марсель (Aix‑Marseille University) сформировал новый факультет информатики в Люмини — пригороде Марселя, — и подбирал молодых амбициозных сотрудников. Одними из первых преподавателей информатики стали Роберт Пасеро (Robert Pasero) и Филипп Руссель (Philippe Roussel). Обоим исполнилось по 25 лет. Оба выпускники университета Экс‑Марсель 1970 года.

В целях повышения квалификации новых преподавателей информатики руководство университета Экс‑Марсель попросило своих коллег из Монреальского университета устроить им стажировку. Те, естественно, не возражали и выслали приглашение. В июле 1970 года в Монреаль приехали Роберт Пасеро и Филипп Руссель. Их познакомили с Аланом Колмероэ и поручили ему познакомить коллег со своими исследованиями. Кстати, Алан оказался не намного старше их, ему исполнилось 29 лет. За два месяца стажировки Алан познакомил их с методами синтаксического анализа естественного языка. Молодые преподаватели поработали на приложении Q‑System с генератором фраз на французском языке. Для приобретения опыта написали несколько синтаксических анализаторов на языке программирования Algol 60.

К осени 1970 года перед Аланом Колмероэ возникла дилемма: перейти работать на факультет информатики Стэнфордского университета (Stanford University) или принять приглашение университета Экс‑Марсель (Aix‑Marseille University). Алан принимает решение перейти на должность декана нового факультета информатики именно в университет Экс‑Марсель. Очень типичное решение его стиля жизни: искать новые направления, начинать с самого начала и доводить дело до конца.

В начале 1971 года Алан Колмероэ переехал из Монреаля в Марсель. Он получил должность декана (maitre de conference) нового факультета информатики университета Экс‑Марсель. Аспирант Жан Трудель последовал за Аланом, не желая менять научного руководителя диссертации. Более того, уезжая Жан Трудель выбил небольшой грант у компании Hydro Quebec. Проект предусматривал дедуктивный разбор текстов, написанных на французском языке. Для работы над проектом Алан создал исследовательскую группа. В неё вошли и уже знакомые Алану преподаватели Роберт Пасеро и Филипп Руссель. Работу над проектом распределили следующим образом. Жан Трудель и Филипп Руссель занялись дедуктивной частью — автоматизацией рассуждений при получении ответов на вопросы. А Роберт Пасеро и Алан Колмероэ — обработкой фраз естественного языка.

По меркам Франции Марсельский университет предоставлил факультету информатики прекрасные условия. В вычислительном центре установили вычислительный комплекс IBM System 360–44. Дух захватывало: 900 Кб внутренней памяти! С небольшим недостатком — в операционном системе отсутствовала поддержка виртуальных машин, — справились самостоятельно. Жан Трудель разработал консоль для интерактивного общения между оператором и программой. Каждую ночь Жан блаженствовал, имея возможность использовать полный объём оперативной памяти для запуска «огромных» программ, размером почти в 1 Мб.

Навыки Жана Труделя улучшались не по дням, а по часам. В начале мая он написал на Algol‑W программу для доказательства теорем. Логический интерфейс формулирования французских фраз с помощью формализмов Q‑System, содержал 50 правил ввода и 17 правил вывода. Одно из правил представляло собой модуль доказательства.

Жан Трудель продолжал поиск более продуктивных методов доказательства теорем. Его заинтересовал метод SLD разрешений (SLD resolution). Жан Трудель попросил Алана организовать встречу с автором метода — Робертом Ковальски. Через пару недель, в июне в Марсель по приглашению Алана приехал Роберт Ковальски. Встеча оказалась незабываемой. Для начала организовали разговор со специалистами по автоматизации доказательства теорем, которые смогли обсудить с Робертом принципы резолюций, варианты и направления совершенствования. В ходе обсуждения Роберту самому стало интересно как его теоретический метод можно было бы применить в практике обработки естественного языка.

За первым знакомством Алана Колмероэ с Робертом Ковальски последовала целая череда встреч, которая завершилась крепкой дружбой не только между исследователями, но и их семьями.

Во второй раз Алан и Роберт встретились в сентябре 1971 года на конференции. Оба посетили сначала лекцию Терри Винограда (Terry Winograd) об обработке фраз естественного языка, а затем доклад Карла Хьюита (Carl Hewitt) на котором он представил язык программирования Planner. В докладах Терри Винограда и Карла Хьюита отсутствовал формализм унификации и шла острая критика логического подхода.

Приложение, которое создало язык

Год 1972 оказался финансово щедрым — исследовательской группе Алана Колмероэ выделили три гранта. В феврале 1972 года грант в размере 122 тыс. французских франков предоставил Институт исследований информации и автоматизации (Institut de Recherche d’Infomatique et d’Futomatique), связанный с Министерством промышленности Франции. Этот грант позволил группе приобрести телетайпный терминал, способный передавать данные между Марселем и Греноблем на сумасшедшей скорости в 300 бит в секунду. Терминал подключили к вычислительной машине IBM System 360–67 c операционной системой CP‑CMS (Control Program/Cambridge Monitor System), поддерживающей архитектуру виртуальных машин. В течение трёх лет команда Алана Колмероэ использовала весь этот мощный компьютерный комплекс. Следующий грант привлёк аспирант Генри Кануи (Henry Kanoui), который занимался исследованиями морфологии французского языка. Последний грант получил Роберт Ковальски от штаб‑квартиры НАТО, которая стремилась поддерживать научный обмен между Эдинбургом и Марселем.

Апрель и май 1972 года Роберт Ковальски провёл в Марселе. За прошедший год команда исследователей приобрела значительные знания о компьютерных методах доказательства теорем — о том, как аксиоматизировать проблемы, как осуществлять конкатенацию и изменение списков. Камнем преткновения оставался поиск формализмов для отображения фраз естественного языка. В то время о парадигме суждений Хорна (хорновских дизъюнктах) они ещё не знали. Приходилось использовать разработанный Аланом ещё в Монреале язык Q‑System.

Алан после отъезда Роберта в конечном счёте нашёл способ разработки анализатора. Он связал двоичный предикат N(x,y) с каждым нетерминальным символом грамматики N, означающим, что x и y служат терминальными строками, для которых существует строка u, определённая через x=uy и полученная из N. Представляя x и y списками, каждое грамматическое правило кодировали высказыванием, имеющим точно такое же количество литералов, как и вхождения нетерминальных символов. Таким образом удалось обойтись без объединения списков (в настоящее время это метод разностных списков). Для вычислений в каждый нетерминал Алан ввёл дополнительные параметры. Аналогично анализатору Q‑System новый анализатор Алана не только проверял правильность высказывания (синтаксис), но и извлекал значение формальной части (семантику).

Филипп Руссель завершил написание диссертации. Основной темой которой стал метод SLD‑разрешений оперирования формальными равенствами при автоматическом доказательстве теорем. Формальное равенство, конечно, менее выразительно, чем математическое равенство, но его легче автоматизировать. В SLD‑разрешении режим работы стекового типа оказался похож на управление вызовами процедур в императивных языках программирования и хорошо подходил для обработки недетерминированности путём обратного отслеживания, а не путём копирования и сохранения разрешающих элементов.

Споры о формализмах отображения высказываний продолжались до конца лета. В конце концов исследовательская группа Алана приняла драконовское решение — проводить унификацию только головы высказывания, пустьи ценой потери полноты. Сами того не подозревая они переизобрели метод подобный высказываниям Хорна. Через несколько лет Роберт Ковальски и Мартен ван Эмден (Maarten Herman van Emden) довели эту идею до совершенства, определив семантику фиксированной точки программирования использованием хорновских дизъюнктов.

Принятие решения об унификации позволила ускорить написание программной части приложения для обработки текста на естественном языке. Программирование осуществили на языке Fortran, использовали линейную резолюцию (вывод) и дизъюнкты с описанием фактов. Для выполнения программы Алан предложил процедурную интерпретацию, преобразующую процесс доказательства в традиционный пошаговый вызов процедур.

Во второй версии приложения разработчики сфокусировали внимание не на дедуктивной части анализа французского языка, а на программной. Осенью 1972 года Филипп переписал программный код Fortran на язык программирования Algol‑W, предложенного Никлаусом Виртом (Niklaus Wirth), для вычислительного комплекса IBM 360–67 под управлением операционной системы CP‑CMS. Алан Колмероэ и Роберт Пасеро создали человеко‑машинный интерфейс приложения. Интерфейс содержал 610 клауз (высказываний). Из них 334 аналитических правила написал Алан, 162 дедуктивных правила написал Роберт Пасеро, 104 правила французской морфологии написал Генри Кануи.

Несмотря на появление второй версии приложения продолжала действовать и первая версия. Роберт Пасеро завершил с её помощью все эксперименты с французской семантикой и результаты включил в свою диссертацию.

Оставалось придумать название приложению. Как‑то вечером дома Филипп Руссель рассказал жене о завершённом программном приложении и полном тупике с названием.

— Наговори мне ключевых слов, — попросила жена Филиппа.

— Эээ… текст, синтаксис, логика, вычисления, программа…, — начал перечислять Филипп.

— Да что тут думать?! ПроЛог (PROgrammation en LOGique), — почти не задумываясь ответила жена.

Так в 1972 году у приложения, предназначенного для интерактивного общения человека и компьютера на французском языке, появилось название Prolog. Да‑да, вы верно прочитали — «приложение Prolog»! В 1972 году не существовало ни методологии логического программирования, ни языка Prolog. Всё это появится гораздо позже.

В апреле 1973 года коллектив Алана Колмероэ получил официальный статус в Национа́льном центре нау́чных иссле́дований Франции (Centre National de la Recherche Scientifique, CNRS). Их зарегистрировали как ассоциированную исследовательскую группу исследователей человеко‑машинного диалога на естественном языке и выделили финансирование в размере 39 тыс. французских франков в год.

Алан и Роберт

Роберт Ковальски (Robert Anthony Kowalski) — ровесник Алана Колмероэ, оба родились в 1941 году, — поступил в 1967 году в аспирантуру Эдинбургского университета (University of Edinburgh) на факультет математики. Возглавлял факультет в то время Бернард Мельцер (Bernard Meltzer). В качестве темы диссертации Роберт выбрал автоматизированное доказательство теорем. Прежде он уже изучал математическую логику в аспирантуре Стэнфордского университета (Stanford University), но не проявлял никакого интереса к исследованиям в области информатики.

В 1968 году, совершенно случайно, Роберт Ковальски встретил Алана Робинсона (John Alan Robinson) — автора опубликованного в 1965 году алгоритма унификации и принципа резолюций при доказательстве теорем (статья «Nondeterministic Algorithms»). Тот в выходной день заглянул на кафедру Бернарда Мельцера. Там их и познакомили. После общения с Аланом Робинсоном научное направление искусственного интеллекта заинтересовало Роберта Ковальски.

В то время в Великобритании и США спонтанно возникли семинары по проблеме искусственного интеллекта. В них участвовал широкий круг исследователей по совершенно различным, и казалось совершенно несвязанным друг с другом темам. Самым ярким оказался 4-й семинар, проведённый в 1969 году. На нём выступили Алан Робинсон, Даг Правиц (Dag Prawitz), Ларри Вос (Larry Wos). Соавторы Джон Маккарти (John McCarthy) и Пэт Хейс (Pat Hayes) представили знаменитый доклад, посвящённый ситуационному анализу. Корделл Грин (Cordell Green) — аспирант Джона Маккарти, — рассказал о своей работе над использованием метода резолюций для получения ответов на вопросы. Фостер (J.M. Foster) и Элкок (E.W. Elcock) представили язык ассертивного программирования Absys (Aberdeen System), разработанный в Абердинском университете. Пэт Хейз (Pat Hayes) и Роберт Ковальски рассказали о применении семантических деревьев как методе нахождения результативных правил автоматического доказательства теорем. Позже Пэт Хейз продолжил развивать тему семантических деревьев и защитил на эту тему диссертацию.

Большой интерес исследователей искусственного интеллекта к публикациям об автоматизации доказательства теорем вызвал сильное противодействие со стороны научных кругов Массачусетского технологического института, которые продвигали идею процедурного, а не декларативного представления знаний. Оппозицию возглавил Сеймур Паперт (Seymour Papert) — разработчик языка программирования Logo, — и Марвин Мински (Marvin Minsky) — директор лаборатории искусственного интеллекта Массачусетского технологического института. Карл Хьюитт (Carl Hewitt) — аспирант Марвина Мински, — разработал язык программирования Planner для процедурного представления знаний.

Язык программирования Planner приобрёл большое влияние благодаря Терри Винограду (Terry Winograd) — аспиранту Массачусетского технологического института, — который создал программу понимания естественного языка SHRDLU и реализовал сочетание программы SHRDLU с языками Planner, Lisp и Programmer. После появления системы синтаксического анализа Programmer, которая интерпретировала грамматики, написанные в терминах программ, исследования по доказательству теорем, основанных на разрешении, резко сократилось во всём мире.

Активность сотрудников Массачусетского технологического института Марвина Мински, Карла Хьюитта, Терри Винограда оказала сильное влияние на Пэта Хейза. Пэт, после посещения Джона Маккарти в Стэнфорде, вернулся сильно разочарованным и отказался от дальнейших исследований совместно с Робертом Ковальски. Пэт хотел написать большую статью с критикой методов доказательства теорем. Но после долгих споров с Робертом они согласились не публиковать результаты совместных исследований. Пэт Хейз ограничился тем, что совместно с Брюсом Андерсоном (Bruce Anderson) написал статью «Безумие логиков», направленную против парадигмы процедуры доказательства теорем.

В 1970 году Роберт Ковальски защитил докторскую диссертацию. Несмотря на скептицизм окружающих он продолжил исследования в области методов доказательства теорем. В 1971 году совместно с Дональдом Кюнером (Donald Kuehner) они опубликовали статью о применимости SLD разрешений (SLD resolution) в эвристических методах. Роберт Ковальски оставался убеждён, что SLD подход ориентированный на цели, может обеспечить поведение, аналогичное процедурным подходам. Роберт изо всех сил старался найти способ конкурировать с процедурными подходами синтаксического анализа и понимания естественного языка. В результате он начал исследовать возможность представления грамматик в логической форме и использовать SLD разрешения для синтаксического анализа.

Летом 1971 года Роберта Ковальски познакомился с Аланом Колмероэ. Алан знал о публикациях Корделла Грина о методе резолюций для получения ответов на вопросы, а также о статьях Роберта Ковальски с Дональдом Кюнером о SLD разрешении. Алан после личного общения с Робертом решил изучить применение этих методов как основы логического компонента автоматизированной системы ответов на вопросы, которой занималась созданная им группа. В конце лета Алан Колмероэ прислал в Эдинбург приглашения Роберту Ковальски с предложением погостить у него в Марселе. Роберт с огромным удовольствием принял приглашение и поехал в Марсель на своём небольшом Austin mini. Жёны Роберта и Алана быстро нашли общий язык. И пока они общались Роберт и Алан обменивались идеями о доказательстве теорем и синтаксическом анализе формальных языков. Роберт Ковальски полагал, что как исследователь много знает о методе доказательства теорем. Однако в ходе общения с Аланом Колмероэ к своему удивлению Роберт обнаружил, что тот знает больше не только о методе, но и его применимости к синтаксическому анализу формальных языков.

В ходе активного обмена идеями Роберт и Алан обнаружили удивительные параллели между грамматиками доказательства теорем и синтаксического анализа. Оба метода использовали: декларативное представление знаний, а также решение в прямом или обратном направлении. Ещё больше их удивило то, что формальная грамматика представленная в синтаксисе формальной логики ведёт себя как восходящий синтаксический анализатор, а метод SLD резолюций ведёт себя как нисходящий синтаксический анализатор. Это открытие, сделанное летом 1971 года, стало первым шагом к созданию языка логического программирования Prolog.

В 1972 году Роберт Ковальски представил свои открытия на конференции «Математические основы информатики». Встреча Роберта и Алана придала исследованиям новый импульс. Роберт Ковальски, вернувшийся в Эдинбург, работал над представлениями грамматик с явными аксиомами ассоциативности. Его вдохновляла математическая идея создать свою алгебру. Алан же понял бесперспективность использования ассоциативности для обоснования конкатенаций. Вместо этого он попытался формализовать графическое представление строк, аналогично Q‑Systems — методу направленного преобразования графа по заданным правилам грамматики.

Следующим летом 1972 года Алан пригласил Роберта приехать в Марсель с семьёй на 2 месяца. Он организовал детский сад для дочерей Роберта и снял для него квартиру в деревушке Кассис, расположенной недалеко от университетского кампуса в Люмини. Всё свободное от преподавательской деятельности время Алан проводил с Робертом, обсуждая идею использования логики в качестве языка программирования компьютеров.

Осенью 1972 года Роберт Ковальски вернулся в Эдинбург после своего двухмесячного пребывания в Марселе. Он с энтузиазмом рассказывал коллегам по университету о логическом программировании. Одни воспринимали восторженно, другие, такие как Пэт Хейс, оказались очень недовольны. Он с завистью высказывался о том, что Роберт Ковальски присвоил себе заслугу о том, что вычисления — это управляемая дедукция. Пэту в принципе не нравился подход языка Prolog — достижения цели путём выбора подходящего логического представления проблемы.. Вместо этого он отстаивал противоположный подход, который заключался в выборе фиксированной логической спецификации и достижении желаемой цели путём изменения команд управления поведением при доказательстве теоремы.

Дональд Мичи (Donald Michie) — директор департамента машинного интеллекта Эдинбургского университета, — и Бернард Мельцер — декан факультета математики Эдинбургского университета, — оказались среди тех, кто с энтузиазмом воспринял идеи логического программирования. Дональд пригласил аспиранта Дэвида Уоррена (David H. D. Warren) и научного сотрудника Мартена ван Эмдена (Maarten van Emden) поработать с Робертом Ковальски над новой темой. Дэвида Уоррена в первую очередь интересовала марсельская реализация Prolog и возможность её дальнейшего развития. А Мартен сосредоточил усилия на исследовании теоретических основ логического программирования и языка Prolog в частности.

Всего год назад в 1971 году Мартен ван Эмден защитил докторскую диссертацию по информатике в Амстердамском университете. После защиты он год прорабобтал научным сотрудником в Исследовательском центре IBM имени Томаса Дж. Уотсона, а затем присоединился к группе Дональда Мичи в Эдинбургском университете. Мартен в сотрудничестве с Робертом Ковальски разработал семантику фиксированных точек для дизъюнктов Хорна. Эта работа легла в основу семантики логического программирования. А далее Мартен занялся исследованиями в области верификации и корректности программного обеспечения.

В том же 1972 году Алан Колмероэ попросил Роберта Ковальски выступить в качестве внешнего эксперта для защиты диссертации докторской диссертации Филиппа Русселя — аспиранта Алан и исследователя по теме автоматизации рассуждений.

В 1973 году Алан и Филипп посетили Роберта в Эдинбурге. Рассказали об очередной реализации программы, в которую к высказываниям добавили управляющие аннотации. Реакция Роберта окзалась очень прохладной. По его мнению подобный подход не соответствовал логической методологии.

В 1974 году возобновились двухмесячные поездки Филиппа Русселя в Эдинбург, а Дэвида Уоррена в Марсель. Филипп познакомился с теорией совместного использования структур в методе резолюций, разработанной в Эдинбурге Робертом Бойером (Robert S. Boyer) и Джей Муром (J Strother Moore). Вернувшись в Марсель Филипп внедрил метод совместного использования структур в очередную версию приложения Prolog.

Дуэт Алана Колмероэ и Роберта Ковальски оказался очень плодотворным. Роберт Ковальски фокусировал внимание на философии и теории логики, а Алана интересовали практические результаты реализации теоретических принципов.

Алан, Роберт и Дэвид

Дэвид Уоррен (David H. D. Warren) выпускник Эдинбургского университета. В 1972 году он стал аспирантом и поступил на работу на факультет машинного интеллекта, который возглавлял Дональд Мичи (Donald Michie). Дэвид стоял перед выбором темы исследований, которая стала бы темой его диссертации. Дональд Мичи как научный руководитель посоветовал Дэвиду поработать с Робертом Ковальски. Вот как впоследствии вспоминал Дэвид начало своего разговора с Робертом Ковальски. «Одним пасмурным октябрьским утром Роберт пригласил меня к себе и усадил на кожаный диван в своей гостинной.

— Я покажу вам кое‑что интересное, — мрачным тоном начал он. — мы называем это логическим программированием…».

Далее из разговора стало ясно, что Дэвид далеко не первый с кем Роберт обсуждал тему логического программирования. На кожаном диване в гостинной уже побывали научный сотрудник Мартен ван Эмден и студент Остин Тейт. Пропустив мимо ушей теоретические рассуждения Роберта, Дэвид согласился исследовать возможность дальнейшего развития марсельской реализации приложения Prolog.

В период с 1972 по 1974 годы Дэвид неоднократно посещал Марсель и общался с командой Алана Колмероэ. Дэвид быстро совершенствовал знания теории логического программирования. Совместно с Аланом Колмероэ и Фернандо Перейрой (Fernando Pereira) он переработал теорию метаморфозных грамматик. Метаморфозная грамматика позволяла применять параметризованные правила грамматики. В своих публикациях они переименовали её в DC грамматику. В конце 1974 года Дэивид добавил DC грамматику в эдинбургскую версию компилятора языка Prolog.

В период с февраля по апрель 1973 года Филипп Руссель по приглашению Роберта Ковальски вновь посетил Эдинбургский университет. Последовали долгие научные обсуждения проблем с Дэвидом Уорреном, Роджером Бойером, Джеем Муром после которых Филипп создал алгоритм резолюций. Он использовал метод совместного использования структур для преставления логических формул, генерируемых во время дедуктивного вывода. Но главным результатом коммандировки Филиппа в Эдинбург стало понимание — нужен отдельный язык программирования, который вобрал бы в себя все новые найденные решения.

В период с мая по июнь 1973 года команда Алана формулировала основые концепции языка: выбирали синтаксис, базовые примитивы, метод компьютерной интерпретации. Начиная с июня и до конца 1973 года аспиранты Жерар Баттани, Генри Мелони, Рене Баццоли (Rene Bazzoli) писали на языке Fortran интерпретатор языка Prolog. Однако, Алану не понравилось то, что разные части языка написаны на различных языках программирования. В период с июня по октябрь 1973 года Жерар Баттани и Генри Мелони под руководством Алана Колмероэ переписали интерпретатор Prolog, ранее написанный на Fortran. Теперь супервайзер интерпретатора полностью написали на самом языке Prolog. Программа содержала примерно 2000 инструкций и имела такой же размер, как и версия интерпретатора, написанная на Algol‑W.

В декабре 1973 года в Гренобле Жерар Баттани и Генри Мелони портировали Prolog, полностью написанный на языке Prolog, на вычислительный комплекс IBM System 360–67.

Дэвид Уоррен активно помогал команде Алана дописывать очередную версию приложения Prolog. В феврале 1974 года после посещения Марселя Дэвид привёз в Эдинбург две вещи: одну страничку кода компьютерной программы Warplan и коробку длиной в фут с карточками, содержащими вторую версию Prolog. Эту версию писали Жерар Баттени (Gerard Battani) и Генри Мелони (Henry Meloni). Программный код наполовину состоял из модулей на языке Fortran, наполовину из модулей на языке Prolog. Вторая версия Prolog произвела на Дэвида положительное впечатление. Возможность запускать программу на вычислительной машине DEC PDP-10 имела огромное практическое значение. Ведь подобных вычислительных комплексов в мире становилось всё больше и больше. Из кода программы Prolog исчезли аннотации к клаузам, которые ранее очень не нравились Роберту Ковальски. Из заменили случайные сокращения, которые выглядели менее навязчивыми.

Осенью 1974 года Мартен ван Эмден в очередной раз посетил Марсель. Алан рассказывал Мартену о своём приложении Prolog, предназначенном для ответов на естественном языке. В теоретической основе лежала логика первого порядка. До этого в своей исследовательской деятельности Алан никогда не ставил своей целью создать теорию логического программирования. Его интересовал сугубо практический интерес — создать синтаксический анализатор естественного языка. Но с годами Алан убедился, что решения проблемы ему необходим особый язык программирования. При этом, ни один из существующих языков Алану не подходил. Во время обсуждения Алан показал Мартену побочные модули, в том числе простой компилятор вымышленного языка программирования, похожего на Algol. Для написания компилятора Алан использовал язык Prolog.

Вернувшись в Эдинбург Мартен в разговоре показал Дэвиду компилятор, который написал Алан. Дэвид с огромным интересом изучил эту программу, а затем начал писать свои варианты. Он присылал Мартену на обсуждение всё новые и новые версии компилятора Prolog.

К концу 1974 года Дэвид Уоррен совместно с Фернандо Перейрой создали продуктивный компилятор Prolog для DEC PDP-10, в котором большую часть кода удалось написать на самом языке Prolog. И код, и компилятор стали убедительным доказательством возможности использования языка логического программирования Prolog на практике. Более того, именно этот диалект логического программирования получил название Edinburgh Prolog и на долгие годы стал фактическим стандартом языка. Даже сегодня, когда существуют стандарты ISO Prolog многие разработчики продолжают использовать эдинбургский диалект.

10 декабря 1974 года на Эдинбургской конференции Дэвид Уоррен представил первое руководство пользователя языка Prolog для мейнфреймов DEC PDP-10. В руководстве появилось упоминание о супервайзере, написанном Дэвидом для эдинбургского диалекта, несколько отличного от марсельского синтаксиса. Своё руководство Дэвид шуточно назвал Epilog.

Наконец, 13 сентября 1975 года Дэвид Уоррен написал компилятор марсельской версии Prolog для DEC PDP-10. Он взял исходный код компилятора, который написал Алан, а затем занёс в файлы Macro-10 объявления к внешним предикатам. В среде окружения операционной системы он связал файлы Macro-10 с модулями Prolog, скомпилированными интерпретатором. Получил интерактивный Prolog в котором скомпилированный код Prolog стал доступен для комбинирования с интерпретируемым кодом Prolog.

Позже Дэвид придумал новую схему, в которой расположил компилятор внутри интерпретатора. Компилятор генерировал машинный код, который компьютер DEC PDP-10 немедленно выполнял. Подобное решение представляло собой сложную схему перехода между интерпретируемым и скомпилированным кодом, а также сложную загрузку.

Несмотря на появление эдинбургского диалекта языка Prolog Алан Колмероэ продолжал развивать свой, марсельский диалект Prolog. Команда проекта полностью переписала супервайзер (в современной инженерии употребляют термин «ядро»), но оставила возможность инфиксных операторов деклариования. В компилятор добавили метаморфозную грамматику. Рене Баццоли использовал анализатор для чтения правил Prolog сверху‑вниз.

В течение 1975 года целая команда занималась портированием интерпретатора Prolog на 16-битный миникомпьютер Telemecanique T1600. Компьютер имел целых 64 Кб оперативной памяти, а систему управления виртуальной памятью для него писали специально.

В 1977 году Дэвид Уоррен в Эдинбургском университете защитил докторскую диссертацию в области искусственного интеллекта. Научными руководителями значились Роберт Ковальски и Дональд Мичи.

Prolog и все, все, все

Интерес разработчиков программного обеспечения к логическому программированию непостоянен, как в семидесятые годы прошлого столетия, так и в настоящее время. Научные публикации повышают интерес и крайне завышенные ожидания о том, что вот теперь получится решить все проблемы. А затем наступает разочарование, как и после всех завышенных ожиданий и шумихи.

Первая волна интереса к методологии логического программирования поднялась в 1972 году после ряда научных публикаций Роберта Ковальски, Дональда Кюнера, Алана Колмероэ других. Жак Коэн (Jacques Cohen) пригласил представителей команды Алана Колмероэ в Бостон и представил учёным из Массачусетского политехнического института (MIT). Тёплый приём исследователям из Марселя оказали Марвин Мински (Marvin Minsky), (Eugene Charniak), Карл Хьюитт (Carl Eddie Hewitt) и Терри Виноград (Terry Winograd). Затем разработчики посетили Стэнфорд. Побывали в лаборатории искусственного интеллекта Джона Маккарти (John McCarthy), встретили там Кордела Грина (Cordell Green) и пообщались с Робертом Флойдом (Robert Floyd).

Однако, как это часто бывает в научном мире, после бурного восхищения новым направлением в программной инженерии в период с 1972 по 1974 годы наступил спад. С одной стороны, крайне активно и агрессивно вели себя противники логического программирования. С другой стороны, сторонние разработчики не видели дял себя практической пользы приложения синтаксического анализа Prolog.

Вторая волна интереса уже не столько к логическому программированию, сколько к практической реализации этой теории, поднялась в 1974–1975 годах. Разработка Дэвидом Уорреном эдинбургского диалекта языка Prolog всколыхнула угасший интерес исследователей. В Эдинбурге к разработке подключились Алан Банди (Alan Bundy), Род Бёрстолл (Rod Burstall), Майкл Гордон (Michael J. C. Gordon), Робин Милнер (Robin Milner) и Гордон Плоткин (Gordon Plotkin). Теорию логического программирования развивали Аарон Сломан (Aaron Sloman), Дэнни Боброу (Daniel G. Bobrow) и даже Карл Хьюитт (Carl Hewitt). Идея логического программирования на языке Prolog проникла во многие европейские университеты. Среди первооткрывателей следует назвать Луиса Перейра (Luis Pereira) из Лиссабона, Стена Аке Тарнлунда (Sten Ake Tarnlund) из Стокгольма, Петера Середи из Будапешта (Peter Szeredi) и Мориса Брюноге (Maurice Bruynooghe) из Лёвена (Бельгия).

В 1974 году после создания отдельного интерпретатора и компилятора язык Prolog начал существовать вне пределов приложения Prolog. Всё больше программистов проявляли неподдельный интерес к языку Prolog: Кит Кларк (Keith Clark) из колледжа Королевы Марии (Queen Mary College), Луис Перейра (Luís Pereira) из Лиссабона, Томаш Пьетшиковски (Tomasz Pietrzykowski) из Университета Ватерлоо (University of Waterloo, Канада).

Генри Кануи и Марк Бергман (Marc Bergman) использовали Prolog для разработки приложения Sycophante, предназначенное для оперирования символами. Жерар Баттани и Генри Мелони для университета в Гренобле разработали приложение распознавания речи, способное отвечать на вопросы. Приложение работало на операционной системе IBM CP‑CMS, а вычислительный комплекс IBM System 360–67 выдавал примерно 200 унификаций в секунду.

Дэвид Уоррен, Жерар Баттани, Генри Мелони не успевали выполнять запросы о поставках из Венгрии, Польши, Канады, Бельгии и устанавливать язык Prolog на компьютеры DEC PDP-10. В то время не существовало понятия «дистрибутив языка Prolog». Файлы Prolog мультиплицировали, проще говоря, размножали копированием.

В установке языка Prolog отличилась выпускница Монреальского университета Элен Ле Глоан (Hélène Le Gloan). Свою первую установку марсельской версии языка Prolog она выполнила в 1974 году в родном университете Монтеаля. Затем, в том же 1974 году, последовала установка языка Prolog на суперкомпьютер Control Data 6000 в Варшаве (Польша). Предварительно Элен адаптировала интерпретатор Prolog под возможности суперкомпьютера Control Data 6000. Объём доступных адресов в структуре данных оказался в три раза больше, чем это предусматривала марсельная версия Prolog. Элен заменила все обращения к массиву вызовами процедур упаковки и распаковки.

В 1975 году Роберт Ковальски стал доцентом в Имперском колледже (Imperial College) в Лондоне. Первое, что он сделал — создал исследовательскую группу логического программирования, следуя примеру Алана Колмероэ. Расположение Лондона как одной из мировых столиц внесло огромный вклад в распространение языка Prolog в мировом масштабе.

В 1976 году для популяризации языка Prolog Роберт Ковальски организовал при Имперском колледже семинары, используя для описания темы семинара словосочетание «логическое программирование». В семинарах принимали участие такие знаменитости как Алан Робинсон, Алан Колмероэ, Филипп Руссель.

Заключение

Вот так приложение Prolog, созданное в 1972 году в Марселе для перевода текста с английского на французский язык, превратилось в язык логического программирования Prolog, который увидел свет в 1974 году в Эдинбурге!