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

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

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

За исключением одного класса задач. Задач, решение которых нельзя описать в виде алгоритма. Но можно указать некие критерии, которым должно удовлетворять искомое решение. Я имею ввиду логические языки программирования и Пролог, как самый яркий представитель этого класса.

Еще помню воспоминание из юности, когда удалось достать дискету с этим языком. Ух, с каким задором горели мои глаза, когда мне казалось, ну вот, еще чуть-чуть и будет создана система с базой знаний, у которой и можно будет получить заветный ответ 42 на любой вопрос.

Так почему этого так и не случилось? В чем проблема Пролога, да и любой системы / языка программирования, назначение которых анализировать факты и искать ответы на вопросы?

Эта проблема называется «Комбинаторный взрыв» — экспоненциальная зависимость времени работы алгоритма от количества входных данных. И есть как минимум два решения этой проблемы.

Подходы к написанию программ

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

Императивный — это классический вариант написания программы, при котором программист сам задает шаги алгоритма для получения конечного результата. А сам текст программы состоит из последовательности команд, которые читают, сохраняют и обрабатывают данные или вызывают другие команды.

Декларативный — в этом стиле программист описывает условия задачи и правила для получения требуемого результата, но не требуется детально описывать все шаги работы алгоритма, оставляя их на усмотрения компьютера.

Именно к декларативному стилю относится язык Пролог, да и все остальные логические языки программирования. К декларативному стилю написания программ следует относить и язык структурированных запросов (SQL).

И проблема под называнием «Комбинаторный взрыв» сильнее всего оказывает негативное влияние как раз на подобные языки. Ведь в императивном подходе программист сам отвечает за последовательность выполняемых команд, и если он запрограммировал алгоритм полного перебора всех возможных вариантов решений, то он сам себе злобный Буратино.

Другое дело, программирование в декларативном стиле. Разработчик хоть и может указать ограничения, которые следует применять при поиске решения, но это возможно только в том случае, когда известен алгоритм решения задачи. Но если алгоритм решения известен, то проще использовать императивный стиль, как раз и реализуя этот алгоритм!

Поэтому основное применения языков программирования в декларативном стиле — отказаться от необходимости описания четкого алгоритма поиска решения, отдав это компьютеру на откуп. Для которого самое простое решение «в лоб» — полный перебор возможных вариантов.

Именно в этом случае и начинается экспоненциальный рост времени выполнения алгоритма. И начиная с определенного порога, время ожидания ответа становится неприемлемым для реального использования. Это и означает «Комбинаторный взрыв», резкий («взрывной») рост времени выполнения алгоритма при увеличении размера входных данных.

Проблема поиска решений

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

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

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

Масштабирование производительности

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

Другое дело горизонтальное масштабирование, при котором выполнение алгоритма запускается на отдельных узлах, которые параллельно решают одну и ту же задачу. Такой способ масштабирования позволяет уже значительно сократить время получения итогового результата для сложных вычислительных задач. И хотя это способ является решением «в лоб», но успехи в области data science доказывают успешность такого подхода.

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

Тут частично может помочь парадигма функционального программирования, которая ограничивает результат вычисления функций только входными параметрами и результатом выполнения других функций, но сам результат не зависит от состояния системы или иных внешних данных.

Поиск обобщенного решения

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

Я имею ввиду возможность поиска самого алгоритма решения. Точнее не совсем алгоритма, а возможность применения к входным данным различные методы отбора, чтобы исключить необходимость их полного перебора. По сути, это сводится к применению различных методов и механизмов обработки входных данных с учетом различных закономерностей.

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

Естественно, такой способ подходит не для всех классов задач. Он не подходит для выявления ВСЕХ возможных решений. Но там где это не требуется, подобные способы уменьшения вычислительной сложности имею право на существование.

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

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

Область не решаемых задач

Как вы считает, а реально ли создать язык логического программирования, который бы сам умел автоматизировать поиск решений для задач подобных классов? Или хотя бы имел в своем арсенале встроенные механизмы для автоматизации подобной деятельности?