Логічне програмування

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Логі́чне програмува́ння — парадигма програмування, а також розділ дискретної математики, що вивчає методи і можливості цієї парадигми, засновані на виведенні нових фактів з даних фактів згідно із заданими логічними правилами. Логічне програмування засноване на теорії математичної логіки. Найвідомішою мовою логічного програмування є Prolog, що є за своєю суттю універсальною машиною виводу, що працює в припущенні замкнутості системи фактів.

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

Від мови Planner також відбулися логічні мови програмування QA-4, Popler, Conniver, і QLISP. Мови програмування Mercury, Visual Prolog, Oz і Fril будувалися вже від мови Prolog. На базі мови Planner було розроблене також декілька альтернативних мов логічного програмування, не заснованих на методі backtracking, наприклад, Ether (див. огляд Шапіро [1989]).

Суть логічних мов програмування[ред.ред. код]

Логічні мови, як передбачається їх назвою, для цілей передачі змісту програм використовують засоби математичної логіки. Сама по собі логіка була винайдена як інструмент людської думки, що дозволяє впорядкувати знання і отримати з них відповідні висновки. Тому здається досить природним вдатися до логіки і для програмування комп'ютерів.

На ділі застосовується апарат не всієї математичної логіки, а тільки її розділ, що відноситься до обчислення предикатів першого порядку. Правду кажучи, він використовується частково. Точніше кажучи, на обчислення в загальному вигляді накладено ряд досить сильних обмежень. На щастя, щоб скористатися мовою логічного програмування, зовсім не потрібно знати логіку предикатів: вона вже вбудована в мову. Досить вивчити саму мову і звикнути до її виразних засобів.

Формальна логіка як основа логічного програмування. Метод резолюцій[ред.ред. код]

Для будь-якої системи логічного програмування характерним є те, що для виконання програми (побудови виведення результату) використовується вмонтована система автоматичного пошуку. Механізм пошуку логічного висновку Prolog-у бере свій початок від методу резолюцій Робінсона. Правило резолюції виведення логічного висновку працює наступним чином: дві фрази можуть резольвувати між собою, коли одна з них має позитивний, а друга — негативний літерал з одним і тим самим позначенням предикату та однаковою кількістю аргументів і в разі, якщо аргументи обох літералів можуть бути уніфіковані (погоджені). Наприклад, фраза P(a, b) o Q(c, d) і фраза Q(c, d) o R(b, c) дають резольвенту P(a, b) o R(b, c). Якщо ж аргументом відношення є змінна, то вона уніфікується з константою, а резольвента буде мати дану константу на місцях попереднього розташування змінної. Розглянемо дві фрази спеціального вигляду: Р(а) — висловлювання без умови і oP(а) — умова без висловлювання. Наявність цих двох фраз в одній теорії є протиріччям. Якщо вони резольвуються між собою, тоді отримана резольвента називається порожньою фразою. Якщо при резолюції двох фраз, що входять до складу теорії, отримується порожня фраза, то теорія буде непослідовною.

Використання логічного програмування[ред.ред. код]

Логічне програмування в першу чергу асоціюється з мовою Prolog. Prolog набагато менш поширена і відома мова, ніж COBOL, Fortran або С. Відразу виникає питання: навіщо він може знадобитися практикуючому програмісту?

Було б невірним вважати логічне програмування в цілому і Prolog зокрема виключно інструментом штучного інтелекту. Prolog знайшов застосування в ряді областей, наприклад, при вирішенні завдань складання складних розкладів, пошуку інформації та аналізу баз даних.

Інше вражаюче використання логічні мови знайшли завдяки своїй націленості на маніпуляцію і трансформацію математичних об'єктів. Щоб повною мірою зрозуміти наслідок цієї їх особливості, потрібно згадати, що сама програма на декларативній мові також є математичним об'єктом. Піддавши вихідний текст програми інваріантним щодо семантики коду перетворенням, можна отримати програму, що служить тим же цілям, але працюючу набагато ефективніше.

Намагаючись усвідомити цю можливість, мимоволі приходиш до моторошної думки про теоретичну можливість створення програм, що самомодифікуються та саморозвиваються. Так, в науці про штучний інтелект є і такий напрямок. Нарешті, ведуться роботи, в яких робиться спроба створення систем, що грунтуються на цьому принципі, які за вихідними формальними специфікаціями могли б генерувати готові прикладні програми. І все це тільки завдяки наявності у декларативних мовах абстрактних семантичних систем.

Ще одне застосування мов логічного програмування, лежить в області паралельних обчислень. Знаменитий Prolog на ділі був адаптований до виконання на послідовних машинах. У своїй чистій формі логічне програмування має ряд властивостей, які дозволяють говорити про логічні мови, як про паралельні. Одним із прикладів є мова Parlog, розроблена Стівом Грегорі в середині 80-х в Імперському коледжі в Лондоні. Ця паралельна мова широко поширена в британській вищій школі.

Основні парадигми програмування[ред.ред. код]

Див. також[ред.ред. код]

Джерела[ред.ред. код]

Бібліографія[ред.ред. код]

  • Иван Братко. Алгоритмы искусственного интеллекта на языке PROLOG (Оригінал Prolog Programming For Artificial Intelligence)
  • John McCarthy. Programs with common sense Symposium on Mechanization of Thought Processes. National Physical Laboratory. Teddington, England. 1958.
  • Fisher Black. A deductive question answering system Harvard University. Thesis. 1964.
  • James Slagle. Experiments with a Deductive Question-Answering Program CACM. December, 1965.
  • Cordell Green. Application of Theorem Proving to Problem Solving IJCAI 1969.
  • Carl Hewitt. Planner: A Language for Proving Theorems in Robots IJCAI 1969.
  • Gerry Sussman and Terry Winograd. Micro-planner Reference Manual AI Memo No, 203, MIT Project MAC, July 1970.
  • Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
  • Terry Winograd. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language MIT AI TR-235. January 1971.
  • Bruce Anderson. Documentation for LIB PICO-PLANNER School of Artificial Intelligence, Edinburgh University. 1972
  • Bruce Baumgart. Micro-Planner Alternate Reference Manual Stanford AI Lab Operating Note No. 67, April 1972.
  • Julian Davies. Popler 1.6 Reference Manual University of Edinburgh, TPU Report No. 1, May 1973.
  • Jeff Rulifson, Jan Derksen, and Richard Waldinger. QA4, A Procedural Calculus for Intuitive Reasoning SRI AI Center Technical Note 73, November 1973.
  • Robert Kowalski Predicate Logic as Programming Language Memo 70, Department of Artificial Intelligence, Edinburgh University. 1973.
  • Drew McDermott and Gerry Sussman. The Conniver Reference Manual MIT AI Memo 259A. January 1974.
  • Earl Sacerdoti, et al. QLISP: A Language for the Interactive Development of Complex Systems AFIPS National Computer Conference. 1976.
  • Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
  • Bill Kornfeld. The Use of Parallelism to Implement a Heuristic Search IJCAI 1981.
  • Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981.
  • Bill Kornfeld. Combinatorially Implosive Algorithms CACM. 1982
  • Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985.
  • Robert Kowalski. The limitation of logic Proceedings of the 1986 ACM fourteenth annual conference on Computer science.
  • Ehud Shapiro (Editor). Concurrent Prolog MIT Press. 1987.
  • Robert Kowalski. The Early Years of Logic Programming CACM. January 1988.
  • Ehud Shapiro. The family of concurrent logic programming languages ACM Computing Surveys. September 1989.
  • Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
  • Shunichi Uchida and Kazuhiro Fuchi Proceedings of the FGCS Project Evaluation Workshop Institute for New Generation Computer Technology (ICOT). 1992.
  • Зубенко В. В. Програмування : навчальний посібник (гриф МОН України) / В. В. Зубенко, Л. Л. Омельчук. — К. : ВПЦ «Київський університет», 2011. — 623 c.
  • Нікітченко М. С. Теоретичні основи програмування : навчальний посібник / М.С Нікітченко — Ніжин : Видавництво НДУ імені Миколи Гоголя, 2010. — 121с.
  • Лавров С. С. Програмирование. Математические основи, средства, теория / С. С. Лавров. — СПб. : БХВ-Петербург,2001. — 251с.
  • Непейвода Н. Н. Основания програмирования : учеб. пособие / Н. Н. Непейвода, И. Н. Скопин. — Ижевск, 2003.
  • Pratt T.W., Zelkovitz M.V. Programming languages, design and implementation (4th ed.). Prentice Hall, 2000 (англ.) (Пратт Т., Зелкович М., Языки программирования: разработка и реализация.- Спб.: Питер, 2002.-688 с.)(рос.)
  • Gabbrielli, Maurizio (2010). Programming languages principles and paradigms. London, New York: Springer,. ISBN 9781848829145. 
  • Robert W. Sebesta: Concepts of Programming Languages, 9th ed., Addison Wesley 2009.

Посилання[ред.ред. код]