Будущее и обещания - Futures and promises

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

Период, термин обещать был предложен в 1976 г. Дэниел П. Фридман и Дэвид Уайз,^[1]и Питер Хиббард назвал это возможный.^[2]Несколько похожая концепция будущее был представлен в 1977 году в статье Генри Бейкер и Карл Хьюитт.^[3]

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

Приложения

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

Неявное и явное

Использование фьючерсов может быть скрытый (любое использование будущего автоматически приобретает свою ценность, как если бы оно было обычным ссылка ) или же явный (пользователь должен вызвать функцию для получения значения, например получать метод java.util.concurrent.Futureв Ява ). Получение ценности явного будущего можно назвать жалящий или же принуждение. Явные фьючерсы могут быть реализованы как библиотека, тогда как неявные фьючерсы обычно реализуются как часть языка.

В исходной статье Бейкера и Хьюитта описывались неявные фьючерсы, которые, естественно, поддерживаются в актерская модель вычислений и чистых объектно-ориентированного программирования языки как Болтовня. В статье Фридмана и Уайза описываются только явные фьючерсы, что, вероятно, отражает сложность эффективной реализации неявных фьючерсов на стандартном оборудовании. Сложность в том, что стандартное оборудование не работает с фьючерсами для примитивных типов данных, таких как целые числа. Например, инструкция добавления не знает, что делать с 3 + будущее факториал (100000). В чистых акторных или объектных языках эту проблему можно решить, отправив будущее факториал (100000) сообщение +[3], который просит будущее добавить 3 себе и вернуть результат. Обратите внимание, что подход к передаче сообщений работает независимо от того, когда факториал (100000) завершает вычисление, и никаких укусов / принуждения не требуется.

Обещание конвейерной обработки

Использование фьючерсов может резко сократить задержка в распределенные системы. Например, фьючерсы позволяют конвейерная обработка обещаний,^[4][5] как реализовано на языках E и Джоуль, который также назывался звонок-поток^[6] на языке Аргус.

Рассмотрим выражение, включающее обычные вызовы удаленных процедур, Такие как:

 t3: = (x.a ()) .c (y.b ())

который может быть расширен до

 t1: = x.a (); t2: = y.b (); t3: = t1.c (t2);

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

Используя фьючерсы, приведенное выше выражение можно было бы записать

 t3: = (x <- a ()) <- c (y <- b ())

который может быть расширен до

 t1: = x <- a (); t2: = y <- b (); t3: = t1 <- c (t2);

Здесь используется синтаксис языка E, где х <- а () означает отправить сообщение а () асинхронно к Икс. Всем трем переменным немедленно назначаются фьючерсы на их результаты, и выполнение переходит к последующим операторам. Более поздние попытки разрешить значение t3 может вызвать задержку; однако конвейерная обработка может сократить количество необходимых циклов. Если, как в предыдущем примере, Икс, у, t1, и t2 все расположены на одном удаленном компьютере, конвейерная реализация может вычислять t3 с одной поездкой в ​​оба конца вместо трех. Поскольку все три сообщения предназначены для объектов, находящихся на одной и той же удаленной машине, необходимо отправить только один запрос и получить только один ответ, содержащий результат. Отправить t1 <- c (t2) не будет блокировать, даже если t1 и t2 находились на разных машинах друг к другу или Икс или же у.

Конвейеризацию обещаний следует отличать от параллельной асинхронной передачи сообщений. В системе, поддерживающей параллельную передачу сообщений, но не конвейерную, сообщение отправляет х <- а () и у <- Ь () в приведенном выше примере может происходить параллельно, но отправка t1 <- c (t2) придется подождать, пока оба t1 и t2 был получен, даже когда Икс, у, t1, и t2 находятся на одной удаленной машине. Преимущество конвейерной обработки в относительной задержке становится еще больше в более сложных ситуациях, связанных с большим количеством сообщений.

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

Представления только для чтения

В некоторых языках программирования, таких как Унция, E, и AmbientTalk, можно получить просмотр только для чтения будущего, что позволяет читать его значение при разрешении, но не позволяет его разрешить:

• В Озе !! Оператор используется для получения представления только для чтения.
• В E и AmbientTalk будущее представлено парой значений, называемой пара обещание / преобразователь. Обещание представляет собой представление, доступное только для чтения, и преобразователь необходим для установки будущего значения.
• В C ++ 11 а std :: future обеспечивает просмотр только для чтения. Значение устанавливается напрямую с помощью std :: обещаниеили установить результат вызова функции с помощью std :: packaged_task или же std :: async.
• в Набор инструментов Dojo отложенный API версии 1.5, объект обещания только для потребителей представляет собой представление только для чтения.^[7]
• В Алиса М.Л., фьючерсы обеспечивают просмотр только для чтения, в то время как обещание содержит как будущее, так и способность решить будущее^[8][9]
• В .NET 4.0 System.Threading.Tasks.Task представляет собой представление только для чтения. Разрешить значение можно с помощью System.Threading.Tasks.TaskCompletionSource .

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

Зависящие от потока фьючерсы

Некоторые языки, например Алиса М.Л., определить фьючерсы, связанные с конкретным потоком, который вычисляет будущее значение.^[9] Это вычисление может начинаться либо с нетерпением когда создается будущее, или лениво когда его значение необходимо в первую очередь. Ленивое будущее похоже на thunk, в смысле отложенного вычисления.

Алиса ML также поддерживает фьючерсы, которые могут быть решены любым потоком, и называет их обещания.^[8] Это использование обещать отличается от его использования в E, как описано над. В Алисе промис - это не доступное только для чтения представление, и конвейерная обработка обещаний не поддерживается. Вместо этого конвейерная обработка, естественно, происходит для фьючерсов, в том числе связанных с обещаниями.

Блокирующая и неблокирующая семантика

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

Однако в некоторых системах также можно попытаться немедленно или же синхронно получить доступ к будущим ценностям. Затем следует сделать выбор дизайна:

• доступ может заблокировать текущий поток или процесс до разрешения будущего (возможно, с таймаутом). Это семантика переменные потока данных на языке Унция.
• попытка синхронного доступа всегда могла сигнализировать об ошибке, например, бросая исключение. Это семантика удаленных обещаний в E.^[10]
• потенциально доступ может быть успешным, если будущее уже решено, но сигнализировать об ошибке, если это не так. Это имело бы недостаток, заключающийся в недетерминировании и потенциальную возможность условия гонки, и кажется необычным выбором дизайна.

В качестве примера первой возможности в C ++ 11, поток, которому нужно значение future, может заблокироваться, пока он не станет доступен, вызвав ждать() или же получать() функции-члены. Вы также можете указать тайм-аут ожидания, используя ждать() или же Подожди до() функции-члены, чтобы избежать неопределенной блокировки. Если будущее возникло из звонка std :: async тогда блокирующее ожидание (без тайм-аута) может вызвать синхронный вызов функции для вычисления результата в ожидающем потоке.

Связанные конструкции

Будущее частный случай Событие (примитив синхронизации), который можно выполнить только один раз. В общем, события могут быть сброшены в исходное пустое состояние и, таким образом, завершены сколько угодно раз.^[11]

An И-вар (как на языке Идентификатор ) - это будущее с семантикой блокировки, как определено выше. An I-структура это структура данных содержащие I-вары. Связанная конструкция синхронизации, которая может быть установлена ​​несколько раз с разными значениями, называется М-вар. M-vars поддерживают атомарные операции для брать или же положить текущее значение, где взятие значения также возвращает M-var к исходному пустой государственный.^[12]

А параллельная логическая переменная^{[нужна цитата ]} похоже на будущее, но обновляется объединение, так же, как логические переменные в логическое программирование. Таким образом, его можно связать более одного раза с унифицируемыми значениями, но нельзя вернуть в пустое или неразрешенное состояние. Переменные потока данных Oz действуют как параллельные логические переменные, а также имеют семантику блокировки, как упомянуто выше.

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

Отношения между выразительностью разных форм будущего

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

Чтобы реализовать неявные ленивые фьючерсы, зависящие от потока (например, предоставленные Alice ML) в терминах фьючерсов, не зависящих от потока, необходим механизм для определения того, когда значение будущего необходимо в первую очередь (например, Подождите построить в Оз^[13]). Если все значения являются объектами, тогда достаточно возможности реализовать прозрачные объекты пересылки, поскольку первое сообщение, отправленное на сервер пересылки, указывает, что необходимо значение будущего.

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

Стратегия оценки

В стратегия оценки фьючерсов, которые можно назвать позвонить будущим, является недетерминированным: значение будущего будет оцениваться в какой-то момент между тем, когда будущее будет создано, и тем, когда его значение будет использовано, но точное время не определяется заранее и может меняться от запуска к запуску. Вычисление может начаться, как только будет создано будущее (жадная оценка ) или только тогда, когда значение действительно необходимо (ленивая оценка ), и может быть приостановлено на полпути или выполнено за один проход. Как только значение future назначено, оно не пересчитывается при будущих доступах; это похоже на мемоизация используется в позвонить по необходимости.

А ленивое будущее - это будущее, которое детерминированно имеет семантику ленивого вычисления: вычисление будущего значения начинается, когда значение требуется в первую очередь, как при вызове по необходимости. Ленивые фьючерсы используются в языках, в которых стратегия оценки по умолчанию не является ленивой. Например, в C ++ 11 такие ленивые фьючерсы можно создать, передав std :: launch :: отложенный запустить политику std :: asyncвместе с функцией для вычисления значения.

Семантика фьючерсов в актерской модели

В модели актера выражение формы будущее <Expression> определяется тем, как он реагирует на Eval сообщение с окружающей средой E и клиент C следующим образом: Будущее выражение отвечает на Eval сообщение, отправив клиенту C недавно созданный актер F (прокси для ответа на оценку <Expression>) как возвращаемое значение одновременно с отправкой <Expression> ан Eval сообщение с окружающей средой E и клиент C. Поведение по умолчанию F как следует:

• Когда F получает запрос р, затем он проверяет, получил ли он уже ответ (который может быть либо возвращаемым значением, либо выданным исключением) от оценки <Expression> действуя следующим образом:
  1. Если уже есть ответ V, тогда
     • Если V является возвращаемым значением, тогда ему отправляется запрос р.
     • Если V является исключением, затем он передается заказчику запроса р.
  2. Если ответа еще нет, то р хранится в очереди запросов внутри F.
• Когда F получает ответ V от оценки <Expression>, тогда V хранится в F и
  • Если V является возвращаемым значением, тогда все запросы в очереди отправляются в V.
  • Если V является исключением, то оно передается заказчику каждого из запросов в очереди.

Однако некоторые фьючерсы могут обрабатывать запросы особым образом, чтобы обеспечить больший параллелизм. Например, выражение 1 + будущий факториал (n) может создать новое будущее, которое будет вести себя как число 1 + факториал (n). Этот прием не всегда срабатывает. Например, следующее условное выражение:

если m> будущий факториал (n) тогда печать ("больше") еще печать («меньше»)

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

История

В будущее и / или обещать конструкции были впервые реализованы на языках программирования, таких как MultiLisp и Акт 1. Использование логических переменных для связи в одновременный логическое программирование языки были очень похожи на фьючерсы. Это началось в Пролог с замораживанием и IC Prolog, и стал настоящим примитивом параллелизма с реляционным языком Concurrent Пролог, охраняемый Роговые оговорки (GHC), Парлог, Strand, Вулкан, Янус, Оз-Моцарт, Поток Java, и Алиса М.Л.. Однократное назначение И-вар из программирование потока данных языки, происходящие из Идентификатор и включен в Reppy's Параллельный ML, очень похожа на переменную параллельной логики.

Техника конвейерной обработки обещаний (с использованием фьючерсов для преодоления задержки) была изобретена Барбара Лисков и Люба Шрира в 1988 г.^[6] и независимо Марк С. Миллер, Дин Триббл и Роб Джеллингхаус в контексте Проект Ксанаду около 1989 года.^[14]

Период, термин обещать был придуман Лисковым и Шрирой, хотя они называли конвейерный механизм именем звонок-поток, который сейчас используется редко.

И дизайн, описанный в статье Лискова и Шриры, и реализация конвейерной обработки обещаний в Xanadu, имели предел, при котором значения обещаний не были первый класс: аргумент для или значение, возвращаемое вызовом или отправкой, не может напрямую быть обещанием (поэтому приведенный ранее пример конвейерной обработки обещаний, который использует обещание для результата одной отправки в качестве аргумента для другого, не был бы напрямую выражается в дизайне потока вызовов или в реализации Xanadu). Похоже, что обещания и потоки вызовов никогда не были реализованы ни в одном публичном выпуске Argus,^[15] язык программирования, использованный в статье Лискова и Шриры. Разработка Argus остановилась примерно в 1988 году.^[16] Реализация конвейерной обработки обещаний в Xanadu стала общедоступной только после выпуска исходного кода для Udanax Gold.^[17] в 1999 году, и ни в одном опубликованном документе не было объяснений.^[18] Более поздние реализации в Joule и E полностью поддерживают первоклассные обещания и преобразователи.

Несколько ранних актерских языков, включая сериал Act,^[19][20] поддерживает как параллельную передачу сообщений, так и конвейерную обработку сообщений, но не поддерживает конвейерную обработку сообщений. (Хотя технически возможно реализовать последнюю из этих функций в первых двух, нет никаких доказательств того, что языки Act сделали это.)

После 2000 г. произошло серьезное возрождение интереса к фьючерсам и обещаниям из-за их использования в ответная реакция пользовательских интерфейсов, а в Веб-разработка, из-за ответ на запрос модель передачи сообщений. Несколько основных языков теперь имеют языковую поддержку для фьючерсов и обещаний, в первую очередь популяризированных FutureTask в Java 5 (объявлено в 2004 г.)^[21] и асинхронный и Ждите конструкции в .NET 4.5 (объявлено в 2010 г., выпущено в 2012 г.)^[22][23] во многом вдохновленный асинхронные рабочие процессы выключенный#,^[24] который датируется 2007 годом.^[25] Впоследствии это было принято другими языками, в частности, Dart (2014),^[26] Python (2015),^[27] Взломать (HHVM) и черновики ECMAScript 7 (JavaScript), Scala и C ++.

Список реализаций

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

Список понятий, связанных с фьючерсами и обещаниями в языке программирования

• ABCL / f^[28]
• Алиса М.Л.
• AmbientTalk (включая первоклассные преобразователи и обещания только для чтения)
• C ++, начиная с C ++ 11: std :: future и std :: обещание
  • мкС ++
  • Композиционный C ++
• Кристалл (язык программирования)
• Дротик (с Будущее/Завершитель классы^[29] и ключевые слова Ждите и асинхронный^[26])
• Вяз (язык программирования) через Задача модуль^[30]
• Глазго Haskell (Только I-вары и M-вары)
• Идентификатор (Только I-вары и M-вары)
• Ио^[31]
• Ява через java.util.concurrent.Future или же java.util.concurrent.CompletableFuture
  • Поток Java
• JavaScript (ограничено, с ECMAScript 6)
• Lucid (только поток данных)
• Немного Лиспы
  • Clojure^[32]
  • MultiLisp
• .СЕТЬ через Задачаs
  • C #, начиная с .NET Framework 4.5,^[22] через ключевые слова асинхронный и Ждите^[23]
• Ним
• Кислород
• Унция версия 3^[33]
• Python concurrent.futures, начиная с 3.2,^[34] как было предложено PEP 3148, а в Python 3.5 добавлены async и await^[35]
• р (обещает ленивую оценку, по-прежнему однопоточную)
• Ракетка^[36]
• Раку^[37]
• Scala через scala.concurrent пакет
• Схема
• Писк Болтовня
• Strand
• Быстрый (только через сторонние библиотеки)
• Visual Basic^{[требуется разъяснение ]} 11 (по ключевым словам Асинхронный и Ждите)^[23]

Языки, также поддерживающие конвейерную обработку обещаний, включают:

• E
• Джоуль

Список нестандартных реализаций фьючерсов на основе библиотек

• За Common Lisp:
  • Blackbird^[38]
  • Нетерпеливое будущее2^[39]
  • lпараллельный^[40]
  • PCall^[41]
• Для C ++:
  • Библиотека Boost^[42]
  • Длиб^[43]
  • Qt^[44]
  • Морская звезда^[45]
  • Глупость^[46]
  • Библиотеки POCO C ++ (Активные результаты)^[47]
  • HPX ^[48]
• За C # и другие .СЕТЬ языки: Параллельные расширения библиотека
• За Groovy: GPars^[49]
• За JavaScript:
  • Cujo.js '^[50] when.js^[51] предоставляет обещания, соответствующие обещаниям / A +^[52] 1.1 спецификация
  • В Набор инструментов Dojo поставляет обещания^[53] и Скрученный отложенный стиль
  • MochiKit^[54] вдохновлен Отложенные Twisted
  • jQuery's Отложенный объект основан на CommonJS Promises / A дизайн.
  • AngularJS^[55]
  • узел -обещать^[56]
  • Q, созданный Крисом Ковалом, соответствует требованиям Promises / A + 1.1.^[57]
  • RSVP.js, соответствует Promises / A + 1.1^[58]
  • ЮИ^[59] класс обещания^[60] соответствует спецификации Promises / A + 1.0.
  • Синяя птица, Петька Антонов^[61]
  • В Библиотека закрытия с обещать пакет соответствует спецификации Promises / A +.
  • Видеть Обещание / A + list для дополнительных реализаций на основе дизайна Promise / A +.
• За Ява:
  • JDeferred, предоставляет API отложенного обещания и поведение, подобное JQuery.Отложенный объект^[62]
  • ParSeq^[63] предоставляет API обещания задач, идеально подходящий для асинхронной конвейерной обработки и ветвления, поддерживаемый LinkedIn
• За Lua:
  • Cqueues [1] модуль содержит Promise API.
• За Цель-C: MAFuture,^[64][65] RXPromise,^[66] ObjC-CollapsingFutures,^[67] PromiseKit,^[68] objc-обещание,^[69] О.А. Обещание,^[70]
• За OCaml: Lazy модуль реализует ленивые явные фьючерсы^[71]
• За Perl: Будущее,^[72] Обещания,^[73] Рефлекс,^[74] и обещание :: ES6^[75]
• За PHP: React / Promise^[76]
• За Python:
  • Встроенная реализация^[77]
  • pythonfutures^[78]
  • Twisted's Отложенные^[79]
• За р:
  • future, реализует расширяемый будущий API с ленивым и нетерпеливым синхронным и (многоядерным или распределенным) асинхронным будущим^[80][81]
• За Рубин:
  • Обещание драгоценного камня^[82]
  • libuv gem, реализует обещания^[83]
  • Целлулоидный камень, реализует фьючерсы^[84]
  • ресурс будущего^[85]
• За Ржавчина:
  • Futures-RS^[86]
• За Scala:
  • Библиотека утилит Twitter^[87]
• За Быстрый:
  • Фреймворк Async, реализует стиль C # асинхронный/ неблокирующий Ждите^[88]
  • FutureKit,^[89] реализует версию для Apple GCD^[90]
  • FutureLib, чистая библиотека Swift 2, реализующая фьючерсы и обещания в стиле Scala с отменой в стиле TPL^[91]
  • Отложенная, чистая библиотека Swift, вдохновленная OCaml Deferred^[92]
  • BrightFutures^[93]
• За Tcl: tcl-обещание^[94]

Сопрограммы

Фьючерсы могут быть реализованы в сопрограммы^[27] или же генераторы,^[95] что приводит к той же стратегии оценки (например, совместная многозадачность или ленивая оценка).

каналы

Фьючерсы могут быть легко реализованы в каналы: будущее - это одноэлементный канал, а обещание - это процесс, который отправляется в канал, выполняя будущее.^[96][97] Это позволяет реализовать фьючерсы на языках параллельного программирования с поддержкой каналов, таких как CSP и Идти. Результирующие фьючерсы являются явными, поскольку доступ к ним должен осуществляться путем чтения из канала, а не только оценки.

Смотрите также

• Волокно (информатика)
• Фьютекс

Рекомендации

внешняя ссылка

• Представление шаблонов параллелизма данный в scaleconf
• Будущая стоимость и Promise Pipelining на Репозиторий портлендских паттернов
• Простая многопоточность с фьючерсами в Python