В информатике future , promise , delay и deferred относятся к конструкциям, используемым для синхронизации выполнения программ в некоторых языках параллельного программирования . Они описывают объект, который действует как прокси для результата, который изначально неизвестен, обычно потому, что вычисление его значения еще не завершено.
Термин «обещание» был предложен в 1976 году Дэниелом П. Фридманом и Дэвидом Уайзом [1] , а Питер Хиббард назвал его «возможным» [2] . Несколько схожая концепция «будущее» была введена в 1977 году в статье Генри Бейкера и Карла Хьюитта [3] .
Термины future , promise , delay и deferred часто используются взаимозаменяемо, хотя некоторые различия в использовании между future и promise рассматриваются ниже. В частности, когда использование различается, future является представлением переменной только для чтения , в то время как promise является записываемым контейнером с одним назначением , который устанавливает значение future. В частности, future может быть определен без указания того, какое конкретное promise установит его значение, и различные возможные promise могут устанавливать значение данного future, хотя это можно сделать только один раз для данного future. В других случаях future и promise создаются вместе и связываются друг с другом: future является значением, promise является функцией, которая устанавливает значение – по сути, возвращаемым значением (future) асинхронной функции (promise). Установка значения future также называется разрешением , выполнением или связыванием его.
Futures и promises возникли в функциональном программировании и связанных с ним парадигмах (таких как логическое программирование ) для отделения значения (future) от того, как оно вычисляется (promise), что позволяет выполнять вычисления более гибко, в частности, путем их распараллеливания. Позже они нашли применение в распределенных вычислениях , для сокращения задержек от круговых передач связи. Еще позже они стали более распространенными, позволяя писать асинхронные программы в прямом стиле , а не в стиле продолжения-передачи .
Использование futures может быть неявным (любое использование future автоматически получает его значение, как если бы это была обычная ссылка ) или явным (пользователь должен вызвать функцию, чтобы получить значение, например, getметод java.util.concurrent.Futureв Java ). Получение значения явного future можно назвать stinging или forcing . Явные futures могут быть реализованы как библиотека, тогда как неявные futures обычно реализуются как часть языка.
В оригинальной статье Бейкера и Хьюитта описывались неявные будущие, которые естественным образом поддерживаются в модели акторов вычислений и чистых объектно-ориентированных языках программирования, таких как Smalltalk . В статье Фридмана и Уайза описывались только явные будущие, что, вероятно, отражало сложность эффективной реализации неявных будущих на стандартном оборудовании. Сложность заключается в том, что стандартное оборудование не имеет дела с будущими для примитивных типов данных, таких как целые числа. Например, инструкция add не знает, как обращаться с . В чистых языках акторов или объектов эта проблема может быть решена путем отправки сообщения , которое просит будущее сложить с собой и вернуть результат. Обратите внимание, что подход с передачей сообщений работает независимо от того, когда завершается вычисление, и что не требуется никаких стигментаций/форсинга.3 + future factorial(100000)future factorial(100000)+[3]3factorial(100000)
Использование фьючерсов может значительно сократить задержку в распределенных системах . Например, фьючерсы позволяют реализовать конвейеризацию обещаний [4] [5] , как это реализовано в языках E и Joule , который также назывался call-stream [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()xt3xyt1t2t3t1 <- c(t2)t1t2xy
Конвейеризацию обещаний следует отличать от параллельной асинхронной передачи сообщений. В системе, поддерживающей параллельную передачу сообщений, но не конвейерную, отправка сообщений x <- a()и y <- b()в приведенном выше примере может выполняться параллельно, но отправка t1 <- c(t2)должна будет ждать, пока оба t1и t2не будут получены, даже если x, y, t1, и t2находятся на одной и той же удаленной машине. Относительное преимущество конвейерной обработки в задержке становится еще больше в более сложных ситуациях, включающих много сообщений.
Конвейерную обработку обещаний также не следует путать с конвейерной обработкой сообщений в акторных системах, где актор может указать и начать выполнение поведения для следующего сообщения до завершения обработки текущего сообщения.
В некоторых языках программирования, таких как Oz , E и AmbientTalk , можно получить представление future, доступное только для чтения , что позволяет читать его значение при разрешении, но не позволяет разрешать его:
!!оператор используется для получения представления, доступного только для чтения.std::futureпредоставляет вид только для чтения. Значение устанавливается напрямую с помощью a std::promiseили устанавливается в результате вызова функции с помощью std::packaged_taskили std::async.System.Threading.Tasks.Task<T> представляет собой вид только для чтения. Разрешение значения может быть выполнено через System.Threading.Tasks.TaskCompletionSource<T>.Поддержка представлений только для чтения соответствует принципу наименьших привилегий , поскольку он позволяет ограничить возможность установки значения субъектами , которым необходимо его установить. В системе, которая также поддерживает конвейеризацию, отправитель асинхронного сообщения (с результатом) получает обещание только для чтения для результата, а цель сообщения получает распознаватель.
Некоторые языки, такие как Alice ML , определяют будущие события, которые связаны с определенным потоком, который вычисляет значение будущего. [9] Это вычисление может начинаться либо активно, когда будущее создается, либо лениво , когда его значение впервые требуется. Ленивое будущее похоже на thunk в смысле отложенного вычисления.
Alice ML также поддерживает будущие события, которые могут быть разрешены любым потоком, и называет их promises . [8] Такое использование promise отличается от его использования в E, как описано выше. В Alice promise не является представлением только для чтения, и конвейеризация promise не поддерживается. Вместо этого конвейеризация естественным образом происходит для будущих событий, включая те, которые связаны с promises.
Если доступ к значению будущего осуществляется асинхронно, например, путем отправки ему сообщения или явного ожидания с использованием конструкции, такой как whenв E, то нет никаких трудностей в задержке, пока будущее не будет разрешено, прежде чем сообщение может быть получено или ожидание завершится. Это единственный случай, который следует рассматривать в чисто асинхронных системах, таких как чистые языки акторов.
Однако в некоторых системах также может быть возможно попытаться немедленно или синхронно получить доступ к значению будущего. Тогда необходимо сделать выбор дизайна:
В качестве примера первой возможности в C++11 поток, которому необходимо значение future, может блокироваться до тех пор, пока оно не станет доступно, вызывая функции-члены wait()или get(). Тайм-аут также может быть указан для ожидания с помощью функций- членов wait_for()или wait_until(), чтобы избежать неопределенной блокировки. Если future возник из вызова , std::asyncто блокирующее ожидание (без тайм-аута) может привести к синхронному вызову функции для вычисления результата в ожидающем потоке.
Будущие события являются частным случаем примитива синхронизации " события ", который может быть завершен только один раз. В общем случае события могут быть сброшены в начальное пустое состояние и, таким образом, завершены столько раз, сколько необходимо. [11]
I -var (как в языке Id ) — это future с блокирующей семантикой, как определено выше. I-structure — это структура данных , содержащая I-var. Связанная конструкция синхронизации, которая может быть установлена несколько раз с разными значениями, называется M-var . M-var поддерживают атомарные операции для взятия или помещения текущего значения, где взятие значения также возвращает M-var в его первоначальное пустое состояние. [12]
Параллельная логическая переменная [ требуется ссылка ] похожа на будущее, но обновляется унификацией , так же, как и логические переменные в логическом программировании . Таким образом, она может быть связана более одного раза с унифицируемыми значениями, но не может быть возвращена в пустое или неразрешенное состояние. Переменные потока данных Oz действуют как параллельные логические переменные, а также имеют блокирующую семантику, как упоминалось выше.
Конкурентная переменная ограничения — это обобщение конкуренциональных логических переменных для поддержки программирования логики ограничений : ограничение может быть сужено несколько раз, указывая на меньшие наборы возможных значений. Обычно есть способ указать thunk, который должен запускаться всякий раз, когда ограничение сужается еще больше; это необходимо для поддержки распространения ограничений .
Eager thread-specific futures можно напрямую реализовать в неспецифичных для потока futures, создав поток для вычисления значения одновременно с созданием future. В этом случае желательно вернуть клиенту только для чтения представление, чтобы только вновь созданный поток мог разрешить этот future.
Для реализации неявных ленивых потокоспецифичных будущих событий (например, как в Alice ML) в терминах не потокоспецифичных будущих событий необходим механизм для определения того, когда значение будущего события необходимо в первую очередь (например, конструкция WaitNeededв Oz [13] ). Если все значения являются объектами, то достаточно реализовать прозрачные объекты пересылки, поскольку первое сообщение, отправленное пересылателю, указывает на необходимость значения будущего события.
Неспецифичные для потока фьючерсы могут быть реализованы в специфичных для потока фьючерсах, предполагая, что система поддерживает передачу сообщений, заставляя разрешающий поток отправлять сообщение собственному потоку фьючерса. Однако это можно рассматривать как ненужную сложность. В языках программирования, основанных на потоках, наиболее выразительным подходом, по-видимому, является предоставление смеси неспецифичных для потока фьючерсов, представлений только для чтения и либо конструкции WaitNeeded , либо поддержки прозрачной пересылки.
Стратегия оценки фьючерсов, которую можно назвать вызовом по фьючерсу , недетерминирована: значение фьючерса будет оценено в какой-то момент между моментом создания фьючерса и моментом использования его значения, но точное время заранее не определено и может меняться от запуска к запуску. Вычисление может начаться сразу после создания фьючерса ( eagy evaluation ) или только тогда, когда значение действительно необходимо ( lazy evaluation ), и может быть приостановлено на полпути или выполнено за один запуск. После того, как значение фьючерса назначено, оно не пересчитывается при будущих обращениях; это похоже на мемоизацию, используемую в call by need .
АЛенивый будущий — это будущий, который детерминированно имеет ленивую семантику вычисления: вычисление значения будущего начинается, когда значение впервые требуется, как в вызове по потребности. Ленивые будущие используются в языках, стратегия вычисления которых по умолчанию не является ленивой. Например, вC++11такие ленивые будущие могут быть созданы путем передачиstd::launch::deferredполитики запуска вstd::async, вместе с функцией для вычисления значения.
В модели актора выражение формы future <Expression>определяется тем, как оно реагирует на Evalсообщение со средой E и клиентом C следующим образом: Будущее выражение отвечает на Evalсообщение, отправляя клиенту C вновь созданный актор F (прокси для ответа evaluating <Expression>) в качестве возвращаемого значения одновременно с отправкой <Expression>сообщения Evalсо средой E и клиентом C. Поведение F по умолчанию следующее:
<Expression>следующим образом:<Expression>, то V сохраняется в F иОднако некоторые фьючерсы могут обрабатывать запросы особым образом, чтобы обеспечить большую параллельность. Например, выражение 1 + future factorial(n)может создать новый фьючерс, который будет вести себя как число 1+factorial(n). Этот трюк не всегда работает. Например, следующее условное выражение:
if m>future factorial(n) then print("bigger") else print("smaller")приостанавливается до тех пор, пока будущее factorial(n)не ответит на запрос, mбольше ли оно само.
Конструкции future и/или promise были впервые реализованы в таких языках программирования, как MultiLisp и Act 1. Использование логических переменных для связи в языках программирования concurrent logic было довольно похоже на futures. Они начались в Prolog с Freeze и IC Prolog и стали настоящим примитивом concurrency с Relational Language, Concurrent Prolog , guarded Horn clauses (GHC), Parlog , Strand , Vulcan , Janus , Oz-Mozart , Flow Java и Alice ML . I-var с одним присваиванием из языков программирования dataflow , происходящая из Id и включенная в Reppy's Concurrent ML , очень похожа на переменную 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 года произошло значительное возрождение интереса к futures и promises из-за их использования в отзывчивости пользовательских интерфейсов и в веб-разработке из-за модели передачи сообщений « запрос-ответ»FutureTask . Несколько основных языков теперь имеют языковую поддержку futures и promises, наиболее заметно популяризированную в 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++ (2011).
Некоторые языки программирования поддерживают будущие объекты, обещания, параллельные логические переменные, переменные потока данных или I-vars либо посредством прямой языковой поддержки, либо в стандартной библиотеке.
java.util.concurrent.Futureилиjava.util.concurrent.CompletableFutureasyncи awaitначиная с ECMAScript 2017 [33]asyncи await[23]kotlin.native.concurrent.Future обычно используется только при написании кода на Kotlin, предназначенного для изначального запуска [35].await) [41]Языки, также поддерживающие конвейеризацию обещаний, включают:
async/неблокируемость await[95]Будущие события могут быть реализованы в сопрограммах [27] или генераторах [103] , что приводит к той же стратегии оценки (например, кооперативная многозадачность или ленивая оценка).
Futures можно легко реализовать в каналах : future — это одноэлементный канал, а promise — это процесс, который отправляет данные в канал, выполняя future. [104] [105] Это позволяет реализовывать futures в параллельных языках программирования с поддержкой каналов, таких как CSP и Go . Получающиеся futures являются явными, поскольку доступ к ним должен осуществляться путем чтения из канала, а не только путем оценки.