Фьючерсы и обещания

Не путать с теорией обещаний .

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

Термин « обещание» был предложен в 1976 году Дэниелом П. Фридманом и Дэвидом Уайзом. и Питер Хиббард назвал это возможным . Несколько похожая концепция будущего была представлена ​​в 1977 году в статье Генри Бейкера и Карла Хьюитта .

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

Приложения

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

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

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

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

Конвейеризация обещаний

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

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

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

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

т1 := ха();
  т2 := yb();
  т3 := 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 , можно получить доступное только для чтения представление будущего, которое позволяет читать его значение при разрешении, но не позволяет его разрешить:

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

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

Специфические фьючерсы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для реализации неявных ленивых фьючерсов, специфичных для потока (как, например, предоставлено Алисой ML) в терминах фьючерсов, не специфичных для потока, необходим механизм, определяющий, когда значение фьючерса требуется в первую очередь (например, WaitNeeded построить в стране Оз ). Если все значения являются объектами, то возможности реализовать прозрачные объекты пересылки достаточно, поскольку первое сообщение, отправленное в пересылку, указывает на то, что требуется будущее значение.

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

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

Дополнительная информация: Звонок в будущее.

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

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

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

В модели актера выражение вида future <Expression> определяется тем, как он реагирует на Eval сообщение со средой E и клиентом C следующим образом: Выражение будущего отвечает на Eval сообщение, отправив клиенту C вновь созданный актер F (прокси для ответа на оценку <Expression>) в качестве возвращаемого значения одновременно с отправкой <Expression> а Evalсообщение со средой E и 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")

приостанавливает до будущего для factorial(n) ответил на запрос, спрашивающий, если m больше, чем он сам.

История

Конструкции будущего были впервые реализованы в таких языках программирования , и/или обещания как MultiLisp и Act 1 . Использование логических переменных для связи в параллельной языках программирования логики очень похоже на фьючерсы. Они начались в Прологе с Freeze и IC Prolog и стали настоящим примитивом параллелизма с Relational Language, Concurrent Prolog , защищенными предложениями Horn (GHC), Parlog , Strand , Vulcan , Janus , Oz-Mozart , Flow Java и Alice ML . с одним присвоением I-var из языков программирования потоков данных , происходящий из Id Reppy и включенный в Concurrent ML , во многом похож на переменную параллельной логики.

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

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

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

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

После 2000 года произошло значительное возрождение интереса к фьючерсам и обещаниям из-за их использования в отзывчивости пользовательских интерфейсов, а также в веб-разработке из-за «запрос-ответ» модели передачи сообщений . В нескольких основных языках теперь есть языковая поддержка фьючерсов и обещаний, наиболее популяризированная FutureTask в Java 5 (анонсировано в 2004 г.) и конструкции async/await в .NET 4.5 (анонсировано в 2010 г., выпущено в 2012 г.) во многом вдохновлен асинхронными рабочими процессами F#, который датируется 2007 годом. Впоследствии это было принято другими языками, в частности Dart (2014), Питон (2015), Hack (HHVM) и черновики ECMAScript 7 (JavaScript), Scala и C++ (2011 г.).

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

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

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

• АБКЛ/ф
• Элис МЛ
• AmbientTalk (включая первоклассные преобразователи и обещания только для чтения)
• C++ , начиная с C++11 : std::future и std::promise.
  • Композиционный C++
• Кристалл (язык программирования)
• Дарт (с Future / Completer классами и ключевые слова await и async )
• Elm (язык программирования) через Task модуль
• Глазго Haskell (только I-вары и M-вары)
• Идентификатор (только I-вары и M-вары)
• Этот
• Java через java.util.concurrent.Future или java.util.concurrent.CompletableFuture
• JavaScript согласно ECMAScript 2015, и через ключевые слова async и await начиная с ECMAScript 2017
• Lucid (только поток данных)
• Некоторые Липсы
  • Кложур
  • МультиЛисп
• .NET через Task s
  • C# , начиная с .NET Framework 4.5, через ключевые слова async и await
• Котлин , однако kotlin.native.concurrent.Future обычно используется только при написании Kotlin, предназначенного для запуска в исходном виде.
• Nim
• Кислород
• Оз версия 3
• Python concurrent.futures , начиная с версии 3.2, как предложено PEP 3148 , а в Python 3.5 добавлены асинхронность и ожидание
• R (обещания для ленивых вычислений, все еще однопоточные)
• Ракетка
• Раку
• Ржавчина (обычно достигается с помощью .await)
• Scala через пакет scala.concurrent
• Схема
• Писк ​
• Стрэнд
• Swift (только через сторонние библиотеки)
• Visual Basic 11 (через ключевые слова Async и Await )

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

• И
• Джоуль

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

• Для Common Lisp :
  • Блэкберд
  • Стремление к будущему2
  • параллельно
  • ПКзвонок
• Для С++:
  • Библиотека повышения
  • Длиб
  • глупость
  • HPX
  • Библиотеки POCO C++ (активные результаты)
  • Qt
  • Сетар
  • плита
• Для C# и других .NET языков параллельных расширений . : библиотека
• Для Groovy : GPars
• Для JavaScript :
  • Cujo.js' когда.js предоставляет обещания, соответствующие Promises/A+ 1.1 спецификация
  • Dojo Toolkit дает обещания и Twisted отсрочки в стиле
  • МочиКит вдохновлен альбомом Deferreds Twisted
  • jQuery Отложенный объект основан на дизайне CommonJS Promises/A .
  • AngularJS
  • узел -обещание
  • Q, автор Крис Коваль, соответствует Promises/A+ 1.1.
  • RSVP.js соответствует Promises/A+ 1.1.
  • ЮИ класс обещаний соответствует спецификации Promises/A+ 1.0.
  • Синяя птица, автор Петька Антонов
  • соответствует замыканий библиотеки Пакет обещаний спецификации Promises/A+.
  • См. список Promise/A+ для получения дополнительных реализаций, основанных на дизайне Promise/A+.
• Для Явы :
  • JDeferred предоставляет API отложенного обещания и поведение, аналогичное JQuery .Deferred. объекту
  • ПарСек предоставляет API-интерфейс Task Promise, идеально подходящий для асинхронной конвейерной обработки и ветвления, поддерживаемый LinkedIn.
• Для Луа :
  • Модуль cqueues [1] содержит Promise API.
• Для Objective-C : MAFuture, RXPromise, ObjC-CollapsingFutures, ОбещаниеКит, объект-обещание, ОАОбещание,
• Для OCaml : модуль Lazy реализует ленивые явные фьючерсы.
• Для Perl : будущее, Обещания, Рефлекс, Обещание::ES6, и обещание::XS
• Для PHP : Реагировать/Обещать
• Для Питона :
  • Встроенная реализация
  • Pythonfutures
  • Twisted Отсрочки
• Для Р :
  • будущее, реализует расширяемый API будущего с ленивыми и энергичными синхронными и (многоядерными или распределенными) асинхронными фьючерсами.
• Для Руби :
  • Параллельный Рубин
  • Обещанный драгоценный камень
  • libuv gem, реализует обещания
  • Целлулоидный драгоценный камень, реализует фьючерсы
  • будущий ресурс
• Для ржавчины :
  • фьючерсы-rs
• Для Скалы :
  • Утилитная библиотека Twitter
• Для Свифта :
  • Async-фреймворк, реализует стиль C#. async/неблокирующий await
  • БудущийКит, реализует версию для Apple GCD
  • FutureLib, чистая библиотека Swift 2, реализующая фьючерсы и обещания в стиле Scala с отменой в стиле TPL.
  • Deferred, чистая библиотека Swift, вдохновленная Deferred из OCaml.
  • BrightFutures
  • SwiftCoroutine
• Для Tcl : tcl-обещание

Сопрограммы

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

Каналы

Основная статья: Канал (программирование)

Фьючерсы легко реализовать в каналах : фьючерс — это одноэлементный канал, а обещание — это процесс, который отправляет в канал, исполняя будущее. Это позволяет реализовывать фьючерсы на параллельных языках программирования с поддержкой каналов, таких как CSP и Go . Получающиеся в результате фьючерсы являются явными, поскольку доступ к ним должен осуществляться путем чтения из канала, а не только путем оценки.

См. также

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

Внешние ссылки

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