Будущее и обещания

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

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

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

Приложения [ править ]

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

Неявное и явное [ править ]

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

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

Конвейерная обработка обещаний [ править ]

Использование фьючерсов может значительно сократить время ожидания в распределенных системах . Так , например, фьючерсы позволяют обещание конвейерную , ^{[4] [5]} как это реализовано на языках Е и Джоуля , который также называют колл-поток ^[6] на языке Argus .

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

 t3: = (xa ()) .c (yb ())

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

 t1: = xa (); t2: = yb (); t3: = t1.c (t2);

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

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

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

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

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

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

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

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

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

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

• В Oz !!оператор используется для получения представления только для чтения.
• В E и AmbientTalk будущее представлено парой значений, называемой парой обещание / преобразователь . Обещание представляет собой представление, доступное только для чтения, и преобразователь необходим для установки будущего значения.
• В C ++ 11 a std::futureпредоставляет представление только для чтения. Значение устанавливается напрямую с помощью a std::promiseили устанавливается равным результату вызова функции с помощью std::packaged_taskили std::async.
• В Deferred API Dojo Toolkit версии 1.5 объект обещания только для потребителя представляет собой представление, доступное только для чтения. ^[7]
• В Alice ML , фьючерсы предоставляют представление только для чтения , тогда как обещание содержит как будущее, так и возможность разрешить будущее ^{[8] [9]}
• В .NET Framework 4.0 System.Threading.Tasks.Task<T> представляет собой представление только для чтения. Разрешить значение можно с помощью System.Threading.Tasks.TaskCompletionSource<T>.

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

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

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

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

Блокирующая и неблокирующая семантика [ править ]

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

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

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

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

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

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

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

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

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

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

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

Для реализации неявных ленивых фьючерсов, зависящих от потока (например, предоставленных Alice ML) в терминах фьючерсов, не зависящих от потока, необходим механизм, определяющий, когда значение future необходимо в первую очередь (например, WaitNeededконструкция в Oz ^{[13 ]} ). Если все значения являются объектами, то возможности реализовать прозрачные объекты пересылки достаточно, поскольку первое сообщение, отправленное на сервер пересылки, указывает, что необходимо будущее значение.

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

Стратегия оценки [ править ]

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

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

Семантика будущего в модели акторов [ править ]

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

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

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

if m>future factorial(n) then print("bigger") else print("smaller")

приостанавливается до тех пор, пока future for factorial(n)не ответит на запрос, спрашивая, mбольше ли оно, чем оно.

История [ править ]

Конструкции future и / или prom были впервые реализованы в языках программирования, таких как MultiLisp и Act 1 . Использование логических переменных для связи в языках программирования параллельной логики было очень похоже на Futures. Они начались в Прологе с замораживанию и IC Прологом , и стали истинным параллелизмом примитива с реляционным языком, Concurrent Prolog , охранявшими положениями Хорн (GHC), Parlog , Strand , Vulcan , Янусом , Ог Моцартом , Flow Java, и Алиса ML . I-var с одним присваиванием из языков программирования потоков данных , происходящий из Id и включенный в Concurrent ML Reppy , очень похож на переменную concurrent logic.

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

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

И дизайн, описанный в статье Лискова и Шриры, и реализация конвейерной обработки обещаний в 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] и конструкциями async / await в .NET 4.5 (объявлено в 2010 г., выпущено в 2012 г.) ^{[22] [23] в} значительной степени вдохновлены асинхронными рабочими процессами F # ^[24], датируемыми 2007 годом. ^[25]Впоследствии это было принято другими языками, в частности, Dart (2014), ^[26] Python (2015), ^[27] Hack (HHVM) и проектами ECMAScript 7 (JavaScript), Scala и C ++.

Список реализаций [ править ]

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

Список понятий, относящихся к Futures и Promises в языке программирования [ править ]

• ABCL / f ^[28]
• Алиса М.Л.
• AmbientTalk (включая первоклассные преобразователи и обещания только для чтения)
• C ++ , начиная с C ++ 11 : std :: future и std :: prom
  • Композиционный C ++
• Кристалл (язык программирования)
• Dart (с классами Future / Completer ^[29] и ключевыми словами await и async ^[26] )
• Elm (язык программирования) через модуль Task ^[30]
• Glasgow Haskell (только I-vars и M-vars)
• Id (только I-vars и M-vars)
• Ио ^[31]
• Java через java.util.concurrent.Futureилиjava.util.concurrent.CompletableFuture
  • Поток Java
• JavaScript с ECMAScript 2015, ^[32] и с помощью ключевых слов, asyncа awaitс ECMAScript 2017 ^[33]
• Lucid (только поток данных)
• Некоторые лиспы
  • Clojure ^[34]
  • MultiLisp
• .NET через Task s
  • C # , начиная с .NET Framework 4.5, ^[22] через ключевые слова asyncи await^[23]
• Ним
• Кислород
• Оз, версия 3 ^[35]
• Python concurrent.futures , начиная с версии 3.2, ^[36], как было предложено PEP 3148 , и Python 3.5 добавил async и await ^[37]
• R (обещает ленивую оценку, по-прежнему однопоточную)
• Ракетка ^[38]
• Раку ^[39]
• Scala через пакет scala.concurrent
• Схема
• Писк Smalltalk
• Strand
• Swift (только через сторонние библиотеки)
• Visual Basic ^{[ требуется пояснение ]} 11 (через ключевые слова Async и Await ) ^[23]

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

• E
• Джоуль

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

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

Сопрограммы [ править ]

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

Каналы [ править ]

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

См. Также [ править ]

• Волокно (информатика)
• Фьютекс
• Пирамида гибели (программирование) , дизайнерский антипаттерн, которого избегают обещания

Ссылки [ править ]

Внешние ссылки [ править ]

• Презентация шаблонов параллелизма на scaleconf
• Конвейерная обработка будущих ценностей и перспектив в портлендском репозитории паттернов
• Простая многопоточность с Futures в Python