Futures and promises

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

Терминология

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

Термины future, promise и delay довольно часто взаимозаменяемы, однако далее описана разница между future и promise. Под future обычно имеется в виду представление переменной, доступное только для чтения, а под promise — изменяемый контейнер с одиночным присваиванием, который передаёт значение future.^[4] Future может быть определён без указания того, из какого promise будет получено значение. Также с одним future может быть связано несколько promise, однако присвоить значение future сможет только один promise. В остальных случаях future и promise создаются вместе и привязываются друг к другу: future — это значение, а promise — это функция, которая присваивает значение. На практике future — возвращаемое значение асинхронной функции promise. Процесс присваивания значения future называют resolving, fulfilling или binding.

В некоторых источниках на русском используются следующие переводы терминов: для future — будущие результаты^[5], фьючерс^[6][7][8]; для promise — обещание^[9][5]; для delay — задержка.

Следует отметить, что неисчислимый («будущее») и двусловный («будущее значение») варианты перевода имеют очень ограниченную применимость (см. обсуждение). В частности, язык Alice ML наделяет futures первоклассными свойствами, в том числе, предоставляя futures первого класса уровня ML-модулей — future modules и future type modules^[10] — и все эти термины оказываются непереводимы с использованием этих вариантов. Возможным вариантом перевода термина в этом случае оказывается «будущность» — соответственно, давая группу терминов «первоклассные будущности», «будущности уровня модулей», «будущные структуры» и «будущные сигнатуры». Возможен вольный перевод «перспектива», с соответствующим терминологическим рядом.

Неявное и явное использование future

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

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

Конвейер из promise

При использовании future значительно сокращаются задержки в распределённых системах. К примеру, при помощи future можно создать конвейер из promise^[11][12], который реализован в таких языках, как E и Joule, а также в Argus под названием call-stream.

Рассмотрим выражение, использующее традиционные удалённые вызовы процедур:

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

которое можно раскрыть как

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

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

Данное выражение может быть переписано с использованием future

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

и раскрыто как

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

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

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

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

Неизменяемые представления

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

• В Oz для получения неизменяемого представления используется оператор !!.
• В E и AmbientTalk future представляет собой пару значений promise/resolver. Promise представляет собой неизменяемое представление, а resolver необходим для присваивания значения future.
• В C++11 std::future представляет собой неизменяемое представление. Значение присваивается напрямую при помощи std::promise или получается из результата выполнения функции std::packaged_task или std::async.
• В Dojo Toolkit Deferred API 1.5 consumer-only promise object представляет собой неизменяемое представление.^[13]
• В Alice ML future предоставляют только неизменяемое представление, а promise содержит возможности future и способность сделать resolve^[14][15]
• В .NET 4.0 и выше System.Threading.Tasks.Task<T> представляет собой неизменяемое представление. Resolve значения может быть выполнен при помощи System.Threading.Tasks.TaskCompletionSource<T>.

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

Future, привязанные к потокам

В некоторых языках, таких как Alice ML, future привязываются к определенному потоку, который вычисляет значение. Вычисление может начаться сразу при создании future или лениво, то есть при первой необходимости. «Ленивый» future напоминает thunk^[en](в плане отложенного вычисления).

Alice ML также поддерживает future, которые могут быть разрешены любым потоком, и там это тоже называется promise.^[14] Стоит заметить, что в данном контексте promise означает не то, что в примере на языке E, рассмотренном выше: promise в Alice не является неизменяемым представлением, и в Alice не поддерживается создание конвейеров из promise. Зато конвейеры естественным образом работают с future (включая те, которые привязаны к promise).

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

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

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

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

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

Похожие конструкции

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

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

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

Выразительность различных форм future

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

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

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

Стратегия вычисления

Стратегия вычисления «вызов по преднамеченности» (англ. call by future) является недетерминированной: значение future будет вычислено в какой-то момент времени после создания, но перед использованием. Вычисление может быть начато непосредственно после создания future («энергичные вычисления» — eager evaluation), или лишь в момент, когда потребуется значение (ленивые вычисления, отложенные вычисления). После того, как результат future вычислен, при последующих обращениях не происходит повторного вычисления. Таким образом future обеспечивают и Вызов по необходимости (call by need), и мемоизацию.

Концепция lazy future ("ленивый" future) предоставляет детерминированную семантику ленивого вычисления: вычисление значения future начинается при первом использовании значения, как в методе "call by need". Lazy future полезны в языках программирования, не предоставляющих ленивых вычислений. Например, в C++11 подобная конструкция может быть создана указанием политики запуска std::launch::sync для std::async с передачей функции, вычисляющей значение.

Семантика future в модели акторов

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

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

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

История

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

Техника конвейера из promise, использующая futures для преодоления задержек, была предложена Барбарой Лисков и Liuba Shrira в 1988 году^[19], и, независимо от них, Mark S. Miller, Dean Tribble и Rob Jellinghaus в рамках Project Xanadu около 1989^[20].

Термин promise был предложен Лисков и Shrira, хотя они назвали механизм конвейеризации call-stream (сейчас это название используется редко).

В обоих работах и в реализации конвейера promise в Xanadu, значения promise не являлись объектом первого класса: аргументы функций и возвращаемые значения не могли являться непосредственно promise (что усложняет реализацию конвейера, например в Xanadu). promise и call-stream не были реализованы в публичных версиях Argus^[21] (языка программирования, использованных в работах Лисков и Shrira); Argus прекратил развитие в 1988 году.^[22] Реализация конвейера в Xanadu стала доступна только с выходом Udanax Gold^[23] в 1999, и не объяснялась в опубликованной документации.^[24]

Реализации promise в Joule и E поддерживают их в качестве объектов первого класса.

Несколько ранних Actor-языков, в том числе языки Act,^[25][26] поддерживали параллельную передачу сообщений и конвейерную обработку сообщений, но не конвейер promise. (Несмотря на возможность реализации конвейера promise через поддерживаемые конструкции, нет свидетельств подобных реализаций в языках Act.)

Каналы

Концепция Future может быть реализована в терминах каналов: future является одноэлементным каналом, а promise является процессом, посылающим значение в канал, выполняя future^[27]. Таким образом реализуются future в таких конкурентных языках с поддержкой каналов как CSP и Go. Реализуемые в них future являются явными, поскольку доступ к ним производится через чтение из канала, а не в рамках обычного вычисления выражений.

Примечания

Ссылки

• Future Value и Promise Pipelining в энциклопедии C2 (Portland Pattern Repository)  (англ.)
• Easy Threading with Futures в языке программирования Python  (англ.)
• http://scrutator.me/post/2012/06/03/parallel-world-p2.aspx

Эта страница в последний раз была отредактирована 23 января 2024 в 14:23.