В своей предыдущей статье (en), я рассказывал об истории японского проекта вычислительных систем пятого поколения, запущенного под звон фанфар в 1982 и почившего в 1992, прихватив с собой логическое программирование. В этой я расскажу о том, как в качестве языка для систем пятого поколения был выбран Пролог, вместо более очевидного Лиспа. Мне интересен феномен людей, способных формировать приверженцев того или иного языка. Надеюсь, в этой статье я смогу объяснить его.
О терминологии. Логическое программирование — это метод, использующий логические предложения в представление процедур и данных, и производящий вычисления на базе полученных утверждений. Пролог — язык программирования, основанный на этих двух идеях. И язык, и метод играли главную роль в системах пятого поколения.
На конференции, открывавшей проект, в 1981 Фучи назвал логическое программирование основной его программной методологией. На завершающей в 1992 Фурукава припомнил, что команда Электротехнической Лаборатории (ЭТЛ) из Токио (в которой позже и стартовал проект систем пятого поколения) в 1976 имела большой опыт в Лиспе, а Пролог был ей совершенно не знаком. В 1976 так было со всеми: за пределами Марселя о Прологе знали всего в паре институтов.
Фучи заинтересовался логическим программированием[1] после прочтения статьи Кавасаки[7] в 1974. Наверное, это и заставило Фурукаву поискать Пролог во время своего визита в Исследовательский Институт Стэндфорда в 1976. Он и правда нашел исходник на Фортране первой версии интерпретатора Пролога, распространяемой за пределами Марселя. В 1974 Дээвид Х.Д. Варрен взял себе в Эдинбург копию. А в 1976 Гарри Бэрроу привез копию из Эдинбурга в Исследовательский Институт Стэндфорда. Варрен[1] рассказывал: «Гарри не мог запустить систему сам и дал ее копию Фурукаве». В 1976 в Токийской ЭТЛ Фурукава и еще несколько исследователей начали экспериментировать с Прологом. США выступили в роли переносчика вируса Пролога, сами избежав инфекции.
Как результаты своей работы в ЭТЛ Фурукава продемонстрировал несколько программ индексирования баз данных на прологе. Видимо, позитивные результаты и позволили ЭТЛ получить реализацию пролога для DEC-10 от Дээвида Х.Д. Варрена. Фурукава писал[2]:
За информацией по истории пролога я обратился к книге Алана Колмероера и Филиппа Россела «Рождение Пролога»[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).
Имея соответствующую программу, можно спросить
что будет означать «может ли конь перейти на одну из клеток по диагонали за один ход» и получить ответ «Нет».
При вопросе
значащий «может ли конь перейти на клетку по диагонали за два хода» получим ответ «Да», со всеми вариантами ходов при необходимости. Программа будет следующей
Ещё пример. Допустим, у нас есть наборы из двадцати семи цифр, содержащиеся в следующих списках
с условием, что каждой из цифр d=1,..,9 найдется три вхождения d, где d отстоят друг от друга на d позиций. Для решения нам потребуется довольно сложный запрос
но сама программа очень маленькая и содержит только предикаты общего назначения:
Ранняя история пролога мне кажется очень интересной: всего несколько человек за шесть лет с нуля развили его в элегантный, мощный и эффективный язык, входящий в Большую Четверку до сих пор. Ранняя история Лисп не менее занимательная. В 1950-ых МакКарти выбирал язык для своего проекта «Советник». Кандидатами были IPL-V Ньювела и Симона и компилятор Фортрана, разрабатываемы группой Бакуса в IBM. У IPL было преимущество в виде гибких структур данных, представленных списками. С другой стороны МакКарти нравился Фортран из-за его механизма итераций. Потому он начал эксперимент по созданию FLPL (Fortran List Processing Language – Язык Обработки Списков на Фортране), версии компилятора Фортрана с поддержкой работы со списками. Напомню, что в то время поддержка пользовательских функций в Фортране была недокументированным свойством с дальним сроком реализации, а тело функции было ограничено одной строкой. Неудивительно, что МакКарти начал работу над собственным языком обработки списков. В ноябре 1958 интерпретатор уже работал в MIT. Вскоре он эволюционировал в язык, известный нам сейчас как Лисп, который был побочным эффектом от работы над описанием проекта.
Одной из особенностей языка была его универсальность: можно ли на нём рассчитать всё то, что в принципе рассчитывается? В качестве демонстрации использовалась программа универсальной машины Тьюринга. Многим нравится то, что МакКарти предпочитал универсальную функцию из теории рекурсивных функций. До того времени эта теория использовалась только в пределах множества натуральных чисел. МакКарти заметил, что натуральность множества не является ограничением, и что она будет работать с любым перечисляемым множеством. Всё это привело к универсальной функции для функций над символическими выражениями (S-выражения).
Универсальная функция принимала в качестве аргумента описание любой функции и описание её аргументов. В качестве результата она выдавала результат выполнения функции над аргументами. Для написания такой функции необходимо было изменить синтаксис определения функции. Её было необходимо описывать с помощью данных, и вот оно – S-выражение.
В своей статье МакКарти описал небольшой набор операций над S-выражениями: ATOM, EQ, CONS, CAR, CDR. К ним он добавил QUOTE и COND в качестве логических функций. Статус LABEL и LAMBDA довольно интригующий: EVAL переписывает списки так, что они в них встречаются в качестве атомов, таким образом LABEL и LAMBDA используются в процессе.
Мы можем рассматривать универсальную функцию МакКарти как элегантную аксиоматизацию подхода к вычислениям[8]. Но то, что было теоретическим изысканием, стало Лиспом. Универсальная функция изменило язык так, что не только данные, но и функции стали списками. Благодаря вдохновению Русселя и его способностям как программиста, универсальная функция стала интерпретатором.
Для ответа на вопрос, почему люди влюбляются в Пролог, я не придумал ничего лучше, чем привести несколько примеров. Для Лиспа есть способ еще лучше: ознакомьтесь с универсальной функцию EVAL и неразлучной с ней APPLY. Они встречаются в самом начале описания Лиспа. Тут и находится pons asinorum[9]: мне кажется, бросившие изучение, забросили его именно в этом месте. После пересечения моста, новичок продолжает путешествие до конца и становится приверженцем Лиспа.
Схожесть достоинств Лиспа и Пролога являются, и всегда являлись, предметом бесконечных дебатов. Проигнорируем творения людей, пишущих фортрановые программы на Лиспе, и людей, использующих пролог как Паскаль с поддержкой шаблонов. Короче говоря, следует игнорировать все, что МакКарти назвал «порнографическим программированием»[4]. В этих дебатах стоит рассматривать только код написанный со знанием «дзена языка». Описание дзена Пролога оставим на другой раз. Для Лиспа оно будет следующим.
С современной точки зрения главное, что сделал МакКарти, — это определение виртуальной машины. Вообще он определил ее во время мысленного эксперимента исключительно для описательных целей. Потому он мог себе позволить сделать ее максимально простой с логической точки зрения: из семи примитивов работающих со списками (проигнорируем отличия между списками и S-выражениями), состоящими только из головы и хвоста. Удивительно, что все это переросло в язык, который можно было реализовать в то время. А еще более интригующим является то, что предельно простая виртуальная машина осталась в живых за десятилетия роста объемов памяти и скоростей процессоров. На основе этой виртуальной машины построены все интерпретаторы EVAL/APPLY, которые можно найти в любом вводном курсе Лиспа.
Как только новичок постигает дзен Лиспа, для него становится естественным писать любую программу, как расширение ограниченных возможностей базового интерпретатора. И эти семь примитивов не хоронятся и не убираются с глаз долой, как только закончен интерпретатор. Напротив, они очень часто встречаются в пользовательском коде. Гилберт сказал противникам теории множеств: «Никто не заставит нас покинуть рай, созданный для нас Кантором». Тоже самое испытывают лисперы по отношению к раю, созданному МакКарти.
Проект пятого поколения был запущен людьми, знающими Лисп и воспринимающими Пролог, как интригующую новинку. Виденье (или мираж) нового поколения компьютеров базировалось на логических вычисления и параллелизме, что сместило баланс мнений в пользу Пролога. Случись по-другому, судьба систем пятого поколения никак бы не повлияла на Лисп: он уже был широко распространён. Но исторически случилось так, что хрупкие и ранние надежды на Пролог разрушились вместе с крахом систем пятого поколения, не достигших своих целей.
О терминологии. Логическое программирование — это метод, использующий логические предложения в представление процедур и данных, и производящий вычисления на базе полученных утверждений. Пролог — язык программирования, основанный на этих двух идеях. И язык, и метод играли главную роль в системах пятого поколения.
На конференции, открывавшей проект, в 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, которые можно найти в любом вводном курсе Лиспа.
Как только новичок постигает дзен Лиспа, для него становится естественным писать любую программу, как расширение ограниченных возможностей базового интерпретатора. И эти семь примитивов не хоронятся и не убираются с глаз долой, как только закончен интерпретатор. Напротив, они очень часто встречаются в пользовательском коде. Гилберт сказал противникам теории множеств: «Никто не заставит нас покинуть рай, созданный для нас Кантором». Тоже самое испытывают лисперы по отношению к раю, созданному МакКарти.
Проект пятого поколения был запущен людьми, знающими Лисп и воспринимающими Пролог, как интригующую новинку. Виденье (или мираж) нового поколения компьютеров базировалось на логических вычисления и параллелизме, что сместило баланс мнений в пользу Пролога. Случись по-другому, судьба систем пятого поколения никак бы не повлияла на Лисп: он уже был широко распространён. Но исторически случилось так, что хрупкие и ранние надежды на Пролог разрушились вместе с крахом систем пятого поколения, не достигших своих целей.
