Подтвердить что ты не робот

Недетерминированные языки программирования

Я знаю, в Прологе вы можете сделать что-то вроде

someFunction(List) :- 
    someOtherFunction(X, List)
    doSomethingWith(X)
    % and so on

Это не будет повторять каждый элемент в списке; вместо этого он будет разветвляться на разные "машины" (с помощью нескольких потоков, обратного отслеживания в одном потоке, создания параллельных юниверсов или чего-либо еще) с отдельным выполнением для каждого возможного значения X, которое вызывает someOtherFunction(X, List) вернуть истину!
(Понятия не имею, как это происходит, но это не важно для вопроса)

Мой вопрос: какие еще существуют недетерминированные языки программирования? Кажется, что недетерминизм - это самый простой и логичный способ реализации многопоточности в языке с неизменяемыми переменными, но я никогда раньше не видел, чтобы это было сделано. Почему этот метод не более популярен?

4b9b3361

ОТВЕТЫ

Ответ 1

Пролог на самом деле детерминистский, порядок оценки предписан, и порядок имеет значение.

Почему популярность не недетерминированна?

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

Единственные недетерминированные языки, о которых я знаю,

  • Исчисление Дейкстры охраняемых команд, которое он хотел никогда не реализовывать

  • Параллельный ML, в котором связь может быть синхронизирована недетерминированно

  • Жерар Хольцманн язык Promela, который является языком проверки модели SPIN

SPIN действительно использует недетерминизм и исследует все пространство состояний, когда это возможно.

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

Кстати, если вы хотите достичь parallelism, вы можете достичь того же самого элемента простой функцией map на чистом функциональном языке, таком как Haskell. Там причина Google MapReduce основана на функциональных языках.

Ответ 2

Статья в Википедии указывает на Amb, которая является Схема производная с возможностями для недетерминированного программирования.

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

Такая же проблема влияет на Prolog. Любое эффективное или, по крайней мере, не очень-неэффективное приложение Prolog должно использовать оператор "cut", чтобы не исследовать экспоненциальное число путей. Этот оператор работает только до тех пор, пока у программиста есть хороший ментальный взгляд на то, как интерпретатор Prolog будет исследовать возможные пути, детерминированным и очень процедурным способом. Вещи, которые очень процедурные, не очень хорошо сочетаются с функциональным программированием, поскольку последнее - это, в основном, попытка не думать о процедуре вообще.

В качестве побочного примечания, между детерминированными и недетерминированными машинами Тьюринга существует модель "квантовых вычислений". Квантовый компьютер, предполагая, что он существует, не делает все, что может сделать недетерминированная машина Тьюринга, но может делать больше, чем детерминированная машина Тьюринга. Есть люди, которые в настоящее время разрабатывают языки программирования для квантового компьютера (предполагая, что в конечном итоге будет построен квантовый компьютер). Некоторые из этих новых языков являются функциональными. Вы можете найти множество полезных ссылок на этой странице Wikipedia. По-видимому, проектирование языка квантового программирования, функционального или нет, и использование его, нелегко и, конечно, не "просто".

Ответ 3

Одним из примеров недетерминированного языка является Occam, основанный на теории CSP. Сочетание конструкций PAR и ALT может привести к недетерминированному поведению в многопроцессорных системах, реализующих мелкозернистые параллельные программы.

При использовании мягких каналов, то есть каналов между процессами на одном процессоре, реализация ALT сделает поведение близким к детерминированному † но как только вы начнете использовать жесткие каналы (физические непроцессорные каналы связи), любая иллюзия детерминизма исчезнет. Не предполагается, что разные удаленные процессоры будут синхронизированы каким-либо образом, и они могут даже не иметь одинаковое ядро или тактовую частоту.

†Конструкция ALT часто реализуется с помощью PRI ALT, поэтому вы должны явным образом кодировать, если вам нужно, чтобы она была честной.

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

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

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

Ответ 4

В Прологе вы можете иметь как недетерминизм, так и параллелизм. Недетерминизм - это то, что вы описали в своем вопросе относительно кода примера. Вы можете представить, что предложение Prolog полно неявных выражений amb. Менее известно, что параллелизм также поддерживается логикой программирования.

История говорит:

Первым параллельным языком логического программирования был реляционный язык Кларка и Грегори, который был ответвлением IC-Prolog. Более поздние версии параллельного логического программирования включают GHC языка Concurrent Prolog и Ueda Guarded Horn Clause. https://en.wikipedia.org/wiki/Concurrent_logic_programming

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

Ответ 5

Я считаю, что у Haskell есть возможность построить и недетерминированную машину. Сначала Хаскелл может показаться слишком сложным и абстрактным для практического использования, но на самом деле он очень силен.

Ответ 6

Java 2K

Примечание. Прежде чем нажимать на ссылку и быть разочарованным: это esoteric язык и не имеет ничего общего с parallelism.

Ответ 7

Существует язык программирования для недетерминированных проблем, который называется "программирование управления сетью". Если вы хотите получить дополнительную информацию, перейдите в http://controlnetworkprogramming.com. Этот сайт все еще продолжается, но вы можете прочитать некоторую информацию об этом.

Ответ 8

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