Табличное логическое программирование
Таблизация — это метод, впервые разработанный для обработки естественного языка и получивший название синтаксического анализа Эрли . Он заключается в сохранении в таблице (или диаграмме в контексте синтаксического анализа) частичных успешных анализов, которые могут пригодиться для повторного использования в будущем.
Составление таблиц состоит из ведения таблицы целей, вызываемых во время выполнения, вместе с ответами на них, а затем непосредственного использования ответов при последующем вызове той же цели. Составление таблиц дает гарантию полной корректности любой (чистой) программы на Прологе без функциональных символов. [1]
Таблицы можно расширять в различных направлениях. Он может поддерживать рекурсивные предикаты посредством разрешения SLG или линейного табличного представления. В многопоточной системе Пролога результаты табличного представления могут оставаться конфиденциальными для потока или совместно использоваться всеми потоками. А при поэтапном составлении таблиц, составление таблиц может реагировать на изменения. [2] [3]
История
[ редактировать ]Адаптация таблицы в процедуру доказательства логического программирования под названием дедукция Эрли восходит к неопубликованной заметке Дэвида Уоррена 1975 года . [4] Метод интерпретации, основанный на составлении таблиц, был позже разработан Тамаки и Сато и смоделирован как усовершенствование SLD-разрешения. [5]
Дэвид С. Уоррен и его ученики приняли эту технику с целью изменить семантику Пролога с семантики завершения на семантику минимальной модели.Табличный Пролог был впервые представлен в XSB . [6] Это привело к полной реализации хорошо обоснованной семантики , трехзначной семантики, которая представляет значения true, false и неизвестное. [7]
Ссылки
[ редактировать ]- ^ Кернер, Филипп; Леушель, Майкл; Барбоза, Жуан; Коста, Витор Сантос; Даль, Вероника; Эрменгильдо, Мануэль В.; Моралес, Хосе Ф.; Вилемакер, Ян; Диас, Дэниел; Абреу, Сальвадор; Чатто, Джованни (17 мая 2022 г.). «Пятьдесят лет Пролога и не только» . Теория и практика логического программирования . 22 (6): 776–858. дои : 10.1017/s1471068422000102 . hdl : 10174/33387 . ISSN 1471-0684 .
- ^ Свифт, Т. (1999). «Таблицы для немонотонного программирования». Анналы математики и искусственного интеллекта . 25 (3/4): 201–240. дои : 10.1023/A:1018990308362 . S2CID 16695800 .
- ^ Чжоу, Нэн-Фа; Сато, Тайсуке (2003). «Эффективное вычисление фиксированных точек в линейных таблицах» (PDF) . Материалы 5-й Международной конференции ACM SIGPLAN по принципам и практике декларативного программирования : 275–283.
- ^ Перейра, Фернандо CN; Шибер, Стюарт М. (1987). Пролог и анализ естественного языка . Стэнфорд: Центр изучения языка и информации . стр. 185–210.
- ^ Тамаки, Хисао; Сато, Тайсуке (1986), «СТАРАЯ резолюция с таблицами» , Конспекты лекций по информатике , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 84–98, ISBN 978-3-540-16492-0 , получено 27 октября 2023 г.
- ^ Сагонас, Константинос; Свифт, Терренс; Уоррен, Дэвид С. (24 мая 1994 г.). «XSB как эффективный дедуктивный механизм базы данных» . Запись ACM SIGMOD . 23 (2): 442–453. дои : 10.1145/191843.191927 . ISSN 0163-5808 .
- ^ Рао, Прасад; Сагонас, Константинос; Свифт, Терренс; Уоррен, Дэвид С.; Фрейре, Юлиана (1997), «XSB: система для эффективного вычисления обоснованной семантики» , Логическое программирование и немонотонное рассуждение , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 430–440, ISBN 978-3-540-63255-9 , получено 27 октября 2023 г.
По состоянию на 27 октября 2023 г. эта статья полностью или частично взята из книги « Пятьдесят лет Пролога и за его пределами» , автором которой является Филипп Кёрнер. Майкл Лешель,Жоао Барбоза,Витор Сантос Коста,Вероника Даль,Мануэль В. Эрменегильдо,Хосе Ф. Моралес,Ян Вилемакер,Дэниел Диас,Сальвадор Абреу,Джованни Чиатто. Владелец авторских прав лицензировал контент таким образом, чтобы его можно было повторно использовать в соответствии с CC BY-SA 3.0 и GFDL . Все соответствующие условия должны быть соблюдены.