Планировщик (язык программирования) - Planner (programming language) - Wikipedia

Планировщик
Разработано	Карл Хьюитт
Впервые появился	1969; 51 год назад

Планировщик (часто обозначаемый в публикациях как «ПЛАНИРОВЩИК», хотя это не акроним) - язык программирования разработано Карл Хьюитт в Массачусетский технологический институт, и впервые опубликовано в 1969 году. Сначала были реализованы подмножества, такие как Micro-Planner и Pico-Planner, а затем, по сути, весь язык был реализован как Поплер Джулианом Дэвисом из Эдинбургского университета в ПОП-2 язык программирования.^[1] Производные, такие как QA4, Conniver, QLISP и Ether (см. метафора научного сообщества ) были важными инструментами в искусственный интеллект исследования 1970-х годов, которые повлияли на коммерческие разработки, такие как Инженерная среда знаний (KEE) и Инструмент автоматического мышления (ИЗОБРАЗИТЕЛЬНОЕ ИСКУССТВО).

Процедурный подход против логического подхода

Две основные парадигмы построения семантических программных систем были процедурной и логической. Процедурная парадигма была воплощена Лисп [Маккарти и другие. 1962], в котором использовались рекурсивные процедуры, работающие со структурами списков.

Логическая парадигма была воплощена в единой процедуре доказательства. средства доказательства теорем разрешения [Робинсон 1965]. Согласно логической парадигме, включение процедурных знаний было «обманом» [Green 1969].

Процедурное вложение знаний

Планировщик был изобретен с целью процедурного внедрения знаний [Hewitt 1971] и являлся отказом от разрешающая способность единая парадигма процедуры доказательства [Robinson 1965], которая

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

Planner был своего рода гибридом процедурной и логической парадигм, потому что он сочетал в себе программируемость с логическими рассуждениями. В планировщике использовалась процедурная интерпретация логических предложений, в которой подразумевается форма (P означает Q) можно процедурно интерпретировать следующими способами, используя вызов, управляемый шаблоном:

Прямая цепочка (ранее):

Если утверждать П, утверждать Q
Если утверждать не Q, утверждать не п

Обратная цепочка (как следствие)

Если цель Q, Цель п
Если цель не П, цель не Q

В этом отношении на разработку Planner повлияли естественный дедуктивный логические системы (особенно один Фредерик Фитч [1952]).

Внедрение микропланировщика

Подмножество под названием Micro-Planner было реализовано Джерри Сассман, Евгений Чарняк и Терри Виноград [Sussman, Charniak, and Winograd 1971] и использовался в программе Винограда для понимания естественного языка. ШРДЛУ, Работа Юджина Чарняка по пониманию историй, работа Торна Маккарти по юридической аргументации и некоторые другие проекты. Это вызвало большой ажиотаж в области ИИ. Он также вызвал споры, поскольку предлагал альтернативу логическому подходу, который был одной из основных парадигм ИИ.

В SRI International, Джефф Рулифсон, Ян Дерксен и Ричард Уолдингер развитый QA4 который основан на конструкциях в Planner и представил механизм контекста для обеспечения модульности выражений в базе данных. Эрл Сакердоти и Рене Ребо разработали QLISP, расширение QA4, встроенное в ИНТЕРЛИСП, предоставляя рассуждения, подобные Planner, встроенные в процедурный язык и разработанные в его богатой среде программирования. QLISP использовался Ричард Уолдингер и Карла Левитта за верификацию программ, Эрл Сакердоти за планирование и мониторинг исполнения, Жан-Клод Латомб для автоматизированного проектирования, Ричардом Файксом для дедуктивного поиска и Стивеном Коулсом для ранней экспертной системы, которая руководила использованием эконометрической модели.

Компьютеры были дорогими. У них был только один медленный процессор, и их память была очень маленькой по сравнению с сегодняшней. Поэтому Planner принял некоторые меры по повышению эффективности, в том числе следующие:

Отслеживание с возвратом [Golomb and Baumert 1965] было принято, чтобы сэкономить время и память, работая и сохраняя только одну возможность за раз при исследовании альтернатив.
Предположение об уникальном имени было принято для экономии места и времени, предполагая, что разные имена относятся к разным объектам. Например, предполагалось, что такие имена, как Пекин (предыдущее название столицы КНР) и Пекин (текущая транслитерация столицы КНР), относятся к разным объектам.
А предположение о замкнутом мире может быть реализован путем условной проверки того, полностью ли провалилась попытка доказать цель. Позже эта возможность получила вводящее в заблуждение название "отрицание как неудача "потому что для цели грамм можно было сказать: «если пытаешься добиться грамм полностью терпит неудачу, затем утверждать (Не G)."

Происхождение Пролога

Джерри Сассман, Евгений Чарняк, Сеймур Паперт и Терри Виноград посетил университет Эдинбург в 1971 году, распространяя новости о Micro-Planner и ШРДЛУ и ставить под сомнение подход к единой процедуре доказательства разрешения, который был опорой Edinburgh Logicists. В Эдинбургском университете Брюс Андерсон реализовал подмножество Micro-Planner под названием PICO-PLANNER (Андерсон, 1972), а Джулиан Дэвис (1973) реализовал практически весь Planner.

По словам Дональда Маккензи, Пэт Хейс напомнил о влиянии визита Паперта в Эдинбург, который стал "сердцем" искусственный интеллект 's Logicland ", согласно коллеге Паперта из Массачусетского технологического института, Карлу Хьюитту. Паперт красноречиво выразил свою критику подхода к разрешению проблем, преобладающего в Эдинбурге," ... и по крайней мере один человек поднял палки и ушел из-за Паперта "[MacKenzie 2001 p 82.]

Вышеупомянутые события вызвали напряженность среди логиков в Эдинбурге. Эта напряженность обострилась, когда Совет научных исследований Великобритании поручил сэру Джеймсу Лайтхиллу написать отчет о ситуации с исследованиями ИИ в Великобритании. В итоговый отчет [Лайтхилл 1973; Маккарти 1973] был очень критичным, хотя ШРДЛУ был положительно упомянут.

Пэт Хейс посетил Стэнфорд, где узнал о Planner. Вернувшись в Эдинбург, он попытался убедить своего друга Боба Ковальски принять во внимание Planner в их совместной работе по автоматическому доказательству теорем. «Доказательство разрешающих теорем превратилось из горячей темы в пережиток ошибочного прошлого. Боб Ковальски упорно придерживался своей веры в потенциал теоремы разрешения прувинга. Он внимательно изучил Planner ». согласно Bruynooghe, Pereira, Siekmann, and van Emden [2004]. Ковальски [1988] заявляет: «Я могу вспомнить, как пытался убедить Хьюитта, что Planner похож на SL-разрешение. »Но Planner был изобретен для целей процедурного встраивания знаний и был отказом от парадигмы процедуры единого доказательства разрешения. Колмерауэр и Руссель вспомнили свою реакцию на изучение Planner следующим образом:

"На съезде IJCAI в сентябре 1971 года с Жаном Трюделем мы встретились Роберт Ковальски снова и услышал лекцию Терри Винограда об обработке естественного языка. Тот факт, что он не использовал единый формализм, вызвал у нас недоумение. Именно в это время мы узнали о существовании языка программирования Карла Хьюитта, Planner [Hewitt, 1969]. Отсутствие формализации этого языка, наше незнание Лиспа и, прежде всего, тот факт, что мы были абсолютно преданы логике, означало, что эта работа мало повлияла на наши последующие исследования ". [Colmerauer and Roussel 1996]

Осенью 1972 г. Филипп Руссель реализовал язык под названием Пролог (сокращение от PROграмматика ru БРЕВНОique - по-французски «программирование в логике»). Программы Prolog обычно имеют следующую форму (которая является частным случаем обратной цепочки в Planner):

Когда цель Q, Цель п₁ и ... и цель п_п

Пролог продублировал следующие аспекты Micro-Planner:

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

Prolog также продублировал следующие возможности Micro-Planner, которые были прагматически полезны для компьютеров той эпохи, потому что они экономили пространство и время:

Структура управления возвратом
Допущение уникального имени, согласно которому предполагается, что разные имена относятся к разным объектам, например, Пекин и Пекин считаются разными.
Оживление неудач. Способ, которым Planner установил доказуемость чего-либо, заключался в том, чтобы успешно попытаться это сделать как цель, а способ, которым он установил недоказуемость, заключался в попытке сделать это как цель и явно потерпеть неудачу. Конечно, другая возможность состоит в том, что попытка доказать цель будет бесконечной и никогда не вернет никакого значения. Планировщик также имел (не выражение) конструкция, которая преуспела, если выражение не удалось, что привело к появлению «Отрицание как неудача »Терминология в Planner.

Использование допущения и отрицания уникального имени в качестве ошибки стало более сомнительным, когда внимание обратилось на открытые системы [Hewitt and de Jong 1983, Hewitt 1985, Hewitt and Inman 1991].

Следующие возможности Micro-Planner были исключены из Prolog:

Вызов процедурных планов по шаблону из утверждений (т.е.., прямая цепочка )
Логическое отрицание, например, (не (человеческий Сократ)).

Пролог не включал отрицание отчасти потому, что это вызывает проблемы с реализацией. Рассмотрим, например, включение отрицания в следующую программу на Прологе:

нет В.

В: - П.

Вышеупомянутая программа не сможет доказать нет п хотя это следует по правилам математической логики. Это иллюстрация того факта, что Prolog (как и Planner) задуман как язык программирования и поэтому (сам по себе) не доказывает многие из логические следствия которые следуют из декларативного прочтения его программ.

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

Смотрите также

внешняя ссылка

Отчет Алена Колмерауэра и Филиппа Русселя о рождении Пролога в 1992 году на Wayback Machine (Архивировано 27 июля 2003 г.)

[1] Карл Хьюитт Средняя история логического программирования: разрешение, планировщик, пролог и японский проект пятого поколения ArXiv 2009. arXiv:0904.3036

[1]