Языки Prolog и Lisp: как устроены и как написать первую программу

Prolog и Lisp появились больше полувека назад, и оба учат думать о программе иначе, чем Python или Java. На Prolog вы описываете факты и правила, а ответ на вопрос система ищет сама. В Lisp программа записывается теми же списками в скобках, что и данные, поэтому код может строить и менять другой код.

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

CheckroiПодборка курсов по алгоритмам43 курса • 20 школСравните цены, школы, программу и найдите выгодные предложения по обучениюСравнить→

Что такое Prolog и Lisp

Слово «пролог» в литературе означает вступление к произведению. Здесь речь о языке программирования Prolog: его название придумали в Марселе в 1972 году как сокращение от французского «PROgrammation en LOGique». Об этом пишут сами авторы, Ален Кольмероэ и Филипп Руссель, в статье «The birth of Prolog». Язык вырос из проекта по разбору французского: авторы учили машину отвечать на вопросы по тексту, а язык программирования получился побочным результатом.

Lisp старше. Джон Маккарти описал его в статье «Recursive Functions of Symbolic Expressions and Their Computation by Machine», вышедшей в Communications of the ACM в апреле 1960 года. Сегодня Lisp означает целое семейство: Common Lisp, Scheme, Racket, Clojure, Emacs Lisp. Общее у них одно: скобки и списки везде.

Чтобы почувствовать разницу, сравните их с привычным языком Python:

Если коротко, в Prolog вы говорите, «что» нужно найти, а в Python расписываете «как». Lisp стоит посередине. Он вычисляет выражения, как обычный язык, но даёт работать с самим кодом как с данными.

Как установить Prolog и Lisp

Для примеров в этой статье мы взяли две свободные реализации: SWI-Prolog и SBCL (Steel Bank Common Lisp). Обе бесплатные и работают на Windows, macOS и Linux. Весь код ниже запущен в SWI-Prolog 10.0.2 и SBCL 2.6.9, вывод скопирован из терминала.

1. SWI-Prolog. Скачайте установщик со страницы стабильных версий: для Windows там 64-битный exe, для macOS образ dmg (macOS 10.15 и новее, Intel и Apple Silicon). В Linux пакет обычно есть в репозитории дистрибутива: sudo apt install swi-prolog. На Mac можно поставить через Homebrew: brew install swi-prolog.
2. SBCL. Сборки лежат на сайте проекта. В Linux поставьте пакет командой sudo apt install sbcl, на Mac командой brew install sbcl.
3. Проверка. Наберите в терминале swipl --version и sbcl --version. Если в ответ пришёл номер версии, всё готово.

Ставить ничего не хочется? Prolog можно попробовать в браузере, в песочнице SWISH от тех же разработчиков. Код пишется слева, запросы задаются справа внизу.

Совет: файлы Prolog сохраняйте с расширением .pl, файлы Common Lisp с расширением .lisp. Редактор подойдёт любой, включая VS Code.

Prolog с нуля: факты, правила и запросы

Программа на Prolog состоит из трёх вещей. Факты описывают то, что известно. Правила говорят, как вывести новое из известного. Запросы задают вопрос, и система ищет все ответы сама.

Факты и правила

Возьмём классический пример, семейное дерево. Сохраните код в файл family.pl:

% Факты: кто чей родитель
parent(anna, boris).
parent(anna, vera).
parent(boris, gleb).
parent(vera, dina).

% Правило: X — бабушка или дедушка Z
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

% Правило: X и Y — брат и сестра (у них общий родитель)
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.

Разберём синтаксис:

• слова с маленькой буквы (anna, parent) обозначают константы и имена отношений;
• слова с большой буквы (X, Y) это переменные, их значения Prolog подбирает сам;
• :- читается как «если», запятая как «и», а каждое утверждение заканчивается точкой;
• \= означает «не совпадает», без этого условия человек оказался бы братом самому себе.

Мы описали граф: люди в нём вершины, а связи «родитель» рёбра. Правило grandparent ищет путь длиной в два ребра.

Запросы

Запустите swipl family.pl и задавайте вопросы после приглашения ?-. Чтобы получить следующий ответ, нажмите ;:

?- parent(anna, X).
X = boris ;
X = vera.

?- grandparent(anna, W).
W = gleb ;
W = dina.

?- sibling(boris, vera).
true.

?- grandparent(gleb, _).
false.

Цикла по списку родителей мы нигде не писали. Перебор вариантов и откат назад (по-английски backtracking) Prolog делает сам. Подчёркивание _ в последнем запросе означает «любое значение, нам не важно какое».

Списки и рекурсия

Циклов в Prolog нет, их заменяет рекурсия. Список записывается в квадратных скобках, а шаблон [Голова|Хвост] отделяет первый элемент от остальных. Вот своя версия длины списка:

my_length([], 0).
my_length([_|T], N) :- my_length(T, N0), N is N0 + 1.

Первая строка задаёт базовый случай: у пустого списка длина 0. Вторая говорит: длина списка на единицу больше длины его хвоста. Если вы раньше писали цикл while в Python, сравните: здесь нет счётчика, который меняется на каждом шаге.

?- my_length([a, b, c], N).
N = 3.

Теперь пример, ради которого Prolog и стоит попробовать. Встроенный предикат append склеивает списки, но его можно спросить и наоборот: «какие два списка дают [1, 2, 3]?»

?- append(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3] ;
X = [1, 2],
Y = [3] ;
X = [1, 2, 3],
Y = [].

Одно и то же отношение работает в обе стороны. Это и есть логическое программирование: вы описали связь между тремя списками, а что из них известно и что надо найти, решает запрос.

Ребус SEND + MORE = MONEY

Сильнее всего Prolog в задачах с ограничениями: расписания, раскраска карт, ребусы. Знаменитый ребус SEND + MORE = MONEY требует подобрать каждой букве свою цифру. С библиотекой clpfd, которая входит в SWI-Prolog, решение выглядит как условие задачи:

:- use_module(library(clpfd)).

% SEND + MORE = MONEY: каждой букве своя цифра
puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-
    Vars = [S,E,N,D,M,O,R,Y],
    Vars ins 0..9,
    all_different(Vars),
    S #\= 0, M #\= 0,
              1000*S + 100*E + 10*N + D
            + 1000*M + 100*O + 10*R + E
    #= 10000*M + 1000*O + 100*N + 10*E + Y,
    label(Vars).

?- puzzle(P).
P = ([9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2]).

То есть 9567 + 1085 = 10652. Решение единственное, у нас поиск занял меньше десятой доли секунды. Вложенных циклов по цифрам здесь нет, мы только перечислили условия.

Lisp с нуля: скобки, списки и функции

В Lisp всё записывается как список в круглых скобках. Первый элемент списка означает функцию, остальные элементы её аргументы. Такая запись называется префиксной: вместо 1 + 2 + 3, как в Python или Паскале, пишут (+ 1 2 3).

Примеры ниже написаны на Common Lisp, их можно сохранить в файл demo.lisp и запустить командой sbcl --script demo.lisp.

Выражения и списки

(print (+ 1 2 3))          ; 6
(print (* 2 (+ 3 4)))      ; 14

(defvar *langs* '(lisp prolog python))
(print (car *langs*))              ; LISP
(print (cdr *langs*))              ; (PROLOG PYTHON)
(print (cons 'scheme *langs*))     ; (SCHEME LISP PROLOG PYTHON)

Три базовые операции со списками пришли из 1960 года и живы до сих пор:

• car возвращает первый элемент;
• cdr возвращает всё, кроме первого;
• cons добавляет элемент в начало.

Апостроф перед списком ('(lisp prolog python)) говорит: «это данные, не вычисляй». Без него Lisp попытается вызвать функцию lisp. К этой ошибке мы ещё вернёмся.

Функции и рекурсия

Функция объявляется через defun. Факториал на Lisp выглядит почти как математическое определение:

(defun fact (n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

(print (fact 5))    ; 120
(print (fact 30))   ; 265252859812191058636308480000000

Посмотрите на второй результат. Целые числа в Common Lisp не переполняются: 30! состоит из 33 цифр, и SBCL посчитал его точно, без дополнительных библиотек.

Функции высшего порядка

Функцию можно передать другой функции как аргумент. Безымянная функция записывается через lambda:

(print (mapcar (lambda (x) (* x x)) '(1 2 3 4)))   ; (1 4 9 16)
(print (remove-if-not #'evenp '(1 2 3 4 5 6)))     ; (2 4 6)
(print (reduce #'+ '(1 2 3 4 5)))                  ; 15

Если вы видели map, filter и reduce в Python или JavaScript, то знаете, откуда они пришли. В Lisp этот стиль был с самого начала.

Код как данные и макросы

Самое необычное в Lisp называют гомоиконностью: программа записана той же структурой, что и данные. Список (+ 10 20) можно хранить в переменной, разбирать по элементам и выполнить:

(defvar *code* '(+ 10 20))
(print (first *code*))   ; +
(print (eval *code*))    ; 30

На этом построены макросы, то есть функции, которые получают код и возвращают новый код до выполнения программы. Например, так можно добавить в язык свою конструкцию «если не»:

(defmacro unless* (condition &body body)
  `(if ,condition nil (progn ,@body)))

(print (macroexpand-1 '(unless* (> 1 2) (print "ok"))))
; (IF (> 1 2)
;     NIL
;     (PROGN (PRINT "ok")))

macroexpand-1 показывает, во что макрос развернётся. В других языках новую конструкцию добавляют авторы компилятора, в Lisp это может сделать любой программист.

И последняя полезная мелочь, список свойств. В нём ключи и значения идут парами, а getf достаёт значение по ключу:

(defvar *course* '(:title "Common Lisp" :hours 40))
(print (getf *course* :hours))   ; 40
(print (getf *course* :price))   ; NIL — такого ключа нет

Частые ошибки новичка

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

В Prolog

• Имя отношения с большой буквы. Строка Parent(boris, gleb). даёт Syntax error: Operator expected: с большой буквы начинаются переменные, а переменная не может быть именем отношения. Решение: имена фактов и правил пишите с маленькой буквы.
• Забытая точка. Без неё Prolog считает, что утверждение продолжается на следующей строке, и выдаёт ту же синтаксическую ошибку уже ниже. Ищите место ошибки на строку выше той, что указана.
• = вместо is. Запрос X = 2 + 3 вернёт X = 2+3: знак = сопоставляет шаблоны и ничего не считает. Для арифметики нужен is: X is 2 + 3 даёт 5.
• Arguments are not sufficiently instantiated. Так Prolog отвечает, если в сравнение N > 0 попала переменная без значения. Например, факториал на Prolog, записанный через условие N > 0, на запросе «у какого числа факториал 120» падает именно с этой ошибкой. Арифметика в Prolog работает только в одну сторону, в отличие от append.
• Бесконечный поиск. Запрос my_length(L, 2) сначала честно отвечает L = [_, _], но если попросить ещё ответ через ;, программа уйдёт в бесконечный перебор. Остановить её можно сочетанием Ctrl+C, а вот встроенный length/2 на тот же вопрос отвечает один раз и завершается.

В Lisp

• Забытый апостроф. (car (lisp prolog)) вместо (car '(lisp prolog)) даёт undefined function: COMMON-LISP-USER::LISP. Lisp принял список за вызов функции.
• Непарная скобка. SBCL сообщит READ error during LOAD: end of file: файл кончился, а выражение не закрыто. Редактор с подсветкой парных скобок экономит здесь часы.
• Неожиданные дроби. (/ 1 3) возвращает 1/3. Это точное рациональное число вместо 0,333, для десятичной дроби напишите (/ 1.0 3).

Где Prolog и Lisp используют сегодня

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

• IBM Watson. Система, которая в 2011 году обыграла людей в викторине Jeopardy!, разбирала вопросы правилами на Prolog. Подробности есть в статье разработчиков «Natural Language Processing With Prolog in the IBM Watson System».
• Clojure в банке. Бразильский Nubank пишет бэкенд на Clojure, диалекте Lisp для JVM. В 2020 году банк сообщил о примерно 2,7 млн строк кода на Clojure и 600 инженерах. Цифры приведены в блоге Nubank по случаю покупки Cognitect, компании, которая развивает язык.
• Редактор Emacs. Его расширения и большая часть самого редактора написаны на Emacs Lisp, у языка есть собственное руководство на сайте GNU. Настраивая Emacs, программист пишет код на Lisp, даже если не думает об этом.
• САПР. AutoLISP исторически появился в AutoCAD, но Autodesk приостановил работу в России в марте 2022 года. Российский nanoCAD загружает LISP-приложения (файлы .lsp), об этом написан раздел «Работа с LISP-приложениями» в справке платформы. Такими скриптами обычно автоматизируют повторяющиеся построения на чертеже, которые иначе делают мышью десятки раз.
• Вузы. Логическое программирование входит в курсы по интеллектуальным системам, и в российских методичках часто встречается диалект Visual Prolog: например, в методических рекомендациях «Логическое программирование», где лабораторный практикум идёт в средах Visual Prolog и DrRacket. Racket тоже диалект Lisp, так что студенты проходят оба языка в одном курсе.

Если вам ближе работа с данными, обратите внимание на родство Prolog с языком SQL. Запрос SELECT тоже описывает, какие строки нужны, а способ поиска выбирает сама база данных. Человек, который понял Prolog, рекурсивные запросы в SQL читает заметно легче.

Канал основателя Checkroi Вани БуявцаЗабирайте промпты и обучение по нейросетям в моём Телеграм-каналеБольше 3 700 человек уже применяют Claude Code, ChatGPT и другие нейросети в работе, учёбе, бизнесе и жизниПерейти в канал→

Стоит ли учить Prolog и Lisp

Первым языком ни один из них брать не стоит. Если вы хотите найти работу, начните с Python, JavaScript или Java, а к Prolog и Lisp возвращайтесь, когда уверенно пишете на первом. Как выстроить этот путь, мы разобрали в статье как стать программистом с нуля.

А вот кому эти языки дадут больше всего:

План на первую неделю, если хотите попробовать сами:

1. День 1–2. Поставить SWI-Prolog, повторить семейное дерево, дописать правила «дядя», «кузен», «предок» (последнее через рекурсию).
2. День 3. Списки: свои версии member, append и разворота списка.
3. День 4. Решить через clpfd мини-судоку 4×4 или свой ребус.
4. День 5–6. Поставить SBCL, повторить примеры из раздела про Lisp, написать функцию, которая считает слова в строке.
5. День 7. Написать один макрос и посмотреть его развёртку через macroexpand-1.

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

Где освоить логику и алгоритмы системно

Отдельных курсов по Prolog и Lisp среди онлайн-школ почти нет: эти языки учат в вузах и по книгам. Зато рекурсию, работу со списками и деревьями и умение описать задачу через условия тренируют курсы по алгоритмам. А если нужен язык для работы, присмотритесь к программам по Python: ниже подборка курсов, которые можно сравнить по цене и длительности.

Курс	Школа	Стоимость со скидкой	В рассрочку	Длитель­ность	Обзор курса от Checkroi
Профессия «Python-разработчик» Перейти на сайт курса	Skillbox	157 335 ₽	5987 ₽/мес.	10 месяцев	Обзор курса
Fullstack-разработчик на Python Перейти на сайт курса	Нетология	161 200 ₽	7125 ₽/мес.	21 месяц	Обзор курса
ДО Профессия Python-разработчик Перейти на сайт курса	GeekBrains	149 001 ₽	3167 ₽/мес.	10 месяцев	Обзор курса
Автоматизированное тестирование на Python Перейти на сайт курса	Skillbox	118 666 ₽	4108 ₽/мес.	9 месяцев	Обзор курса
Программирование на Python ПРО Перейти на сайт курса	Skillbox	119 600 ₽	-	17 месяцев	Обзор курса

• 

  Профессия «Python-разработчик»

  Skillbox157 335 ₽5987 ₽/мес10 месяцев
  Перейти на сайт курсаОбзор
• 

  Fullstack-разработчик на Python

  Нетология161 200 ₽7125 ₽/мес21 месяц
  Перейти на сайт курсаОбзор
• 

  ДО Профессия Python-разработчик

  GeekBrains149 001 ₽3167 ₽/мес10 месяцев
  Перейти на сайт курсаОбзор
• 

  Автоматизированное тестирование на Python

  Skillbox118 666 ₽4108 ₽/мес9 месяцев
  Перейти на сайт курсаОбзор
• 

  Программирование на Python ПРО

  Skillbox119 600 ₽17 месяцев
  Перейти на сайт курсаОбзор

Больше программ — в полном каталоге курсов по Python