Pull to refresh

Фатальный выбор

Reading time8 min
Views2.4K
Original author: Maarten van Emden
В своей предыдущей статье (en), я рассказывал об истории японского проекта вычислительных систем пятого поколения, запущенного под звон фанфар в 1982 и почившего в 1992, прихватив с собой логическое программирование. В этой я расскажу о том, как в качестве языка для систем пятого поколения был выбран Пролог, вместо более очевидного Лиспа. Мне интересен феномен людей, способных формировать приверженцев того или иного языка. Надеюсь, в этой статье я смогу объяснить его.

О терминологии. Логическое программирование — это метод, использующий логические предложения в представление процедур и данных, и производящий вычисления на базе полученных утверждений. Пролог — язык программирования, основанный на этих двух идеях. И язык, и метод играли главную роль в системах пятого поколения.

На конференции, открывавшей проект, в 1981 Фучи назвал логическое программирование основной его программной методологией. На завершающей в 1992 Фурукава припомнил, что команда Электротехнической Лаборатории (ЭТЛ) из Токио (в которой позже и стартовал проект систем пятого поколения) в 1976 имела большой опыт в Лиспе, а Пролог был ей совершенно не знаком. В 1976 так было со всеми: за пределами Марселя о Прологе знали всего в паре институтов.

Фучи заинтересовался логическим программированием[1] после прочтения статьи Кавасаки[7] в 1974. Наверное, это и заставило Фурукаву поискать Пролог во время своего визита в Исследовательский Институт Стэндфорда в 1976. Он и правда нашел исходник на Фортране первой версии интерпретатора Пролога, распространяемой за пределами Марселя. В 1974 Дээвид Х.Д. Варрен взял себе в Эдинбург копию. А в 1976 Гарри Бэрроу привез копию из Эдинбурга в Исследовательский Институт Стэндфорда. Варрен[1] рассказывал: «Гарри не мог запустить систему сам и дал ее копию Фурукаве». В 1976 в Токийской ЭТЛ Фурукава и еще несколько исследователей начали экспериментировать с Прологом. США выступили в роли переносчика вируса Пролога, сами избежав инфекции.

Как результаты своей работы в ЭТЛ Фурукава продемонстрировал несколько программ индексирования баз данных на прологе. Видимо, позитивные результаты и позволили ЭТЛ получить реализацию пролога для DEC-10 от Дээвида Х.Д. Варрена. Фурукава писал[2]:
Я написал программу сборки кубика Рубика на Прологе DEC-10.она была эффективной и решала задачу за относительно короткое время (около 20 секунд). В таком типе экспертных систем механизм принятия решений эффективно реализуется с помощью хвостовой рекурсии на Прологе. После этого эксперимента я убедился, что пролог — это язык обработки знаний.

За информацией по истории пролога я обратился к книге Алана Колмероера и Филиппа Россела «Рождение Пролога»[3]. Первые шаги были сделаны в 1971 группой, возглавляемой Колмероером в университете Аикс-Марсель. После создания нескольких предварительных версий, служащих исключительно для обработки естественных языков, в 1973 была создана «финальная версия». Под влиянием Кавасаки логика предложений стала языком, а определенная форма утверждений служила механизмом вызова процедур. Эта версия стала первой, получившей название «Пролог» и использовавшейся для задач отличных от обработки естественных языков. В начале 1974 после визита Варрена в Марсель, копия Пролога попала в Эдинбург; а из Эдинбурга быстро распространилась по несколько европейским институтам (Будапешт, Лювен, Лиссабон) и в Канаду.

С 1974 по 1977 была проведена масса увлекательных экспериментов, продолжавших начатые в Марселе. Хелдер Коэльо из Лиссабона начал собирать программы для книги «Как сделать на Прологе». В 1975 Варрен начал писать компилятор Пролога на Прологе DEC-10. Когда он был завершен в 1977 выяснилось, что получилось серьезное улучшение марсельского интерпретатора 1973 года. Варрен и его коллеги осмелились сравнить его с компилятором Лиспа, который был совершенен как произведение искусства, и получили занимательные результаты. Реверсирование списков выполнялось на 30-50% быстрее чем на Лиспе. Результат был удивителен, т.к. списки транслируются в логические термы и обрабатываются унифицировано, как любой другой терм. Символическое дифференцирование (в зависимости от данных) выполнялось от 1.1 до 2.6 раз быстрее чем на Лиспе. В 1977 Лиспу было 18 лет, а Прологу — 6, и только горстка людей работала над его развитием в период с 1971 по 1977.

Следующие примеры, по большому счету, бесполезны. Они выбраны для демонстрации притягательной природы Пролога.

Предположим программу для предиката «move» означающего при записи move(X1,Y1,X2,Y2), что конь может перейти с клетки (X1,Y1) на клетку (X2,Y2).
Имея соответствующую программу, можно спросить
?- move (U,U,V,V).

что будет означать «может ли конь перейти на одну из клеток по диагонали за один ход» и получить ответ «Нет».

При вопросе
?- move(U,U,X,Y),move(X,Y,V,V).

значащий «может ли конь перейти на клетку по диагонали за два хода» получим ответ «Да», со всеми вариантами ходов при необходимости. Программа будет следующей
move(X1,Y1,X2,Y2) :- diff1(X1,X2),diff2(Y1,Y2).
move(X1,Y1,X2,Y2) :- diff2(X1,X2),diff1(Y1,Y2).

% diff1(X,Y): координаты X и Y отличаются на 1.
diff1(X,Y) :- succ(X,Y).
diff1(X,Y) :- succ(Y,X).

% diff2(X,Z): координаты X и Z отличаются на 2.
diff2(X,Z) :- succ(X,Y),succ(Y,Z).
diff2(X,Z) :- succ(Z,Y),succ(Y,X).

% succ(X,Y): Y подходящая координата для координаты X.
succ(1,2). succ(2,3). succ(3,4). succ(4,5). succ(5,6). succ(6,7). succ(7,8).


Ещё пример. Допустим, у нас есть наборы из двадцати семи цифр, содержащиеся в следующих списках
[1,9,1,6,1,8,2,5,7,2,6,9,2,5,8,4,7,6,3,5,4,9,3,8,7,4,3]
[1,9,1,2,1,8,2,4,6,2,7,9,4,5,8,6,3,4,7,5,3,9,6,8,3,5,7]
[1,8,1,9,1,5,2,6,7,2,8,5,2,9,6,4,7,5,3,8,4,6,3,9,7,4,3]
[3,4,7,9,3,6,4,8,3,5,7,4,6,9,2,5,8,2,7,6,2,5,1,9,1,8,1]
[7,5,3,8,6,9,3,5,7,4,3,6,8,5,4,9,7,2,6,4,2,8,1,2,1,9,1]
[3,4,7,8,3,9,4,5,3,6,7,4,8,5,2,9,6,2,7,5,2,8,1,6,1,9,1]

с условием, что каждой из цифр d=1,..,9 найдется три вхождения d, где d отстоят друг от друга на d позиций. Для решения нам потребуется довольно сложный запрос
?-equals(List,
[_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_]),
sublist([9,_,_,_,_,_,_,_,_,_,9,_,_,_,_,_,_,_,_,_,9],List),
sublist([8,_,_,_,_,_,_,_,_,8,_,_,_,_,_,_,_,_,8],List),
sublist([7,_,_,_,_,_,_,_,7,_,_,_,_,_,_,_,7],List),
sublist([6,_,_,_,_,_,_,6,_,_,_,_,_,_,6],List),
sublist([5,_,_,_,_,_,5,_,_,_,_,_,5],List),
sublist([4,_,_,_,_,4,_,_,_,_,4],List),
sublist([3,_,_,_,3,_,_,_,3],List),
sublist([2,_,_,2,_,_,2],List),
sublist([1,_,1,_,1],List).

но сама программа очень маленькая и содержит только предикаты общего назначения:
% sublist(X,Y) если все элементы X встречаются в Y в том же порядке как и в Х

sublist([],List).
sublist([X|Xs],[X|Ys]) :- append(Xs,_,Ys).
sublist(List,[Y|Ys]) :- sublist(List,Ys).

append([],Y,Y).
append([U|X],Y,[U|Z]) :- append(X,Y,Z).

equals(X,X).

Ранняя история пролога мне кажется очень интересной: всего несколько человек за шесть лет с нуля развили его в элегантный, мощный и эффективный язык, входящий в Большую Четверку до сих пор. Ранняя история Лисп не менее занимательная. В 1950-ых МакКарти выбирал язык для своего проекта «Советник». Кандидатами были IPL-V Ньювела и Симона и компилятор Фортрана, разрабатываемы группой Бакуса в IBM. У IPL было преимущество в виде гибких структур данных, представленных списками. С другой стороны МакКарти нравился Фортран из-за его механизма итераций. Потому он начал эксперимент по созданию FLPL (Fortran List Processing Language – Язык Обработки Списков на Фортране), версии компилятора Фортрана с поддержкой работы со списками. Напомню, что в то время поддержка пользовательских функций в Фортране была недокументированным свойством с дальним сроком реализации, а тело функции было ограничено одной строкой. Неудивительно, что МакКарти начал работу над собственным языком обработки списков. В ноябре 1958 интерпретатор уже работал в MIT. Вскоре он эволюционировал в язык, известный нам сейчас как Лисп, который был побочным эффектом от работы над описанием проекта.

Одной из особенностей языка была его универсальность: можно ли на нём рассчитать всё то, что в принципе рассчитывается? В качестве демонстрации использовалась программа универсальной машины Тьюринга. Многим нравится то, что МакКарти предпочитал универсальную функцию из теории рекурсивных функций. До того времени эта теория использовалась только в пределах множества натуральных чисел. МакКарти заметил, что натуральность множества не является ограничением, и что она будет работать с любым перечисляемым множеством. Всё это привело к универсальной функции для функций над символическими выражениями (S-выражения).

Универсальная функция принимала в качестве аргумента описание любой функции и описание её аргументов. В качестве результата она выдавала результат выполнения функции над аргументами. Для написания такой функции необходимо было изменить синтаксис определения функции. Её было необходимо описывать с помощью данных, и вот оно – S-выражение.
… После описания EVAL и публикации о ней Стив Рассел спросил, почему я не запрограммирую EVAL и не сделаю интерпретатор; я ответил, ну-ну, не путай теорию с практикой, EVAL служит для чтения, а не для вычислений. Но он продолжил и сделал интерпретатор. Он скомпилировал EVAL из моей статьи в 704 строки машинного кода, исправил баги и рассказал всем об интерпретаторе Лиспа, чем собственно оно и являлось; в целом с того момента Лисп приобрел форму, в какой мы его знаем и сегодня, форму S-выражений (выделено Стояном[5] в транскрипте к «Истории Лиспа», разговор с МакКарти в 1974)

В своей статье МакКарти описал небольшой набор операций над S-выражениями: ATOM, EQ, CONS, CAR, CDR. К ним он добавил QUOTE и COND в качестве логических функций. Статус LABEL и LAMBDA довольно интригующий: EVAL переписывает списки так, что они в них встречаются в качестве атомов, таким образом LABEL и LAMBDA используются в процессе.

Мы можем рассматривать универсальную функцию МакКарти как элегантную аксиоматизацию подхода к вычислениям[8]. Но то, что было теоретическим изысканием, стало Лиспом. Универсальная функция изменило язык так, что не только данные, но и функции стали списками. Благодаря вдохновению Русселя и его способностям как программиста, универсальная функция стала интерпретатором.

Для ответа на вопрос, почему люди влюбляются в Пролог, я не придумал ничего лучше, чем привести несколько примеров. Для Лиспа есть способ еще лучше: ознакомьтесь с универсальной функцию EVAL и неразлучной с ней APPLY. Они встречаются в самом начале описания Лиспа. Тут и находится pons asinorum[9]: мне кажется, бросившие изучение, забросили его именно в этом месте. После пересечения моста, новичок продолжает путешествие до конца и становится приверженцем Лиспа.

Схожесть достоинств Лиспа и Пролога являются, и всегда являлись, предметом бесконечных дебатов. Проигнорируем творения людей, пишущих фортрановые программы на Лиспе, и людей, использующих пролог как Паскаль с поддержкой шаблонов. Короче говоря, следует игнорировать все, что МакКарти назвал «порнографическим программированием»[4]. В этих дебатах стоит рассматривать только код написанный со знанием «дзена языка». Описание дзена Пролога оставим на другой раз. Для Лиспа оно будет следующим.

С современной точки зрения главное, что сделал МакКарти, — это определение виртуальной машины. Вообще он определил ее во время мысленного эксперимента исключительно для описательных целей. Потому он мог себе позволить сделать ее максимально простой с логической точки зрения: из семи примитивов работающих со списками (проигнорируем отличия между списками и S-выражениями), состоящими только из головы и хвоста. Удивительно, что все это переросло в язык, который можно было реализовать в то время. А еще более интригующим является то, что предельно простая виртуальная машина осталась в живых за десятилетия роста объемов памяти и скоростей процессоров. На основе этой виртуальной машины построены все интерпретаторы EVAL/APPLY, которые можно найти в любом вводном курсе Лиспа.

Как только новичок постигает дзен Лиспа, для него становится естественным писать любую программу, как расширение ограниченных возможностей базового интерпретатора. И эти семь примитивов не хоронятся и не убираются с глаз долой, как только закончен интерпретатор. Напротив, они очень часто встречаются в пользовательском коде. Гилберт сказал противникам теории множеств: «Никто не заставит нас покинуть рай, созданный для нас Кантором». Тоже самое испытывают лисперы по отношению к раю, созданному МакКарти.

Проект пятого поколения был запущен людьми, знающими Лисп и воспринимающими Пролог, как интригующую новинку. Виденье (или мираж) нового поколения компьютеров базировалось на логических вычисления и параллелизме, что сместило баланс мнений в пользу Пролога. Случись по-другому, судьба систем пятого поколения никак бы не повлияла на Лисп: он уже был широко распространён. Но исторически случилось так, что хрупкие и ранние надежды на Пролог разрушились вместе с крахом систем пятого поколения, не достигших своих целей.
Tags:
Hubs:
Total votes 58: ↑53 and ↓5+48
Comments24

Articles