LINUX.ORG.RU

Promises в Scheme и других ЯП

 , ,


0

4

Добрый день!

Пишу сейчас на коленке имплементацию Scheme (r5rs) на Java (да, полностью r5rs на джаве не получится реализовать, но это и не планируется).
Немного запутался в delayed evaluation'ах и в promises.

Если открыть, например:
http://community.schemewiki.org/?delayed-computation

то там пишут:


A promise is, quite simply, the promise to evaluate an expression later.
It is not evaluated until explicitly requested, although R5RS permits promises to be evaluated implicitly when passed to primitive operations and their result be used instead.


Тоже самое пишут и на:
https://docs.racket-lang.org/reference/Delayed_Evaluation.html


A promise encapsulates an expression to be evaluated on demand via force.
After a promise has been forced, every later force of the promise produces the same result.



Т.е. promise - это просто выражение, которое мы вычислим когда-нибудь потом, либо явно через force, либо неявно.
Результат запоминается после вычисления и повтороное вычисление promise'а всегда возвращает сохраненный результат.

API для promise'в довольно простой: delay, да force.
И разные вспомогательные promise?, promise-forced?, promise-running?

Если же посмотреть promises в JavaScript или Java:
https://www.promisejs.org/implementing
https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/CompletableFut...

То, как я понимаю, речь немного о другом.
Future - read-only 'контейнер' для результата будущих вычислений
Promise - writable 'контейнер' для результата будущих вычислений

Т.е. допустим, мы создаем Promise и передаем его куда-нибудь, обещая положить туда результат неких вычислений когда-то в будущем.
На той стороне (обычно, в другом треде) получают созданный нами promise и в нужный момент пытаются получить его результат (блокирующий вызов).
API намного сложнее.

Как я это вижу:
в Java/JS/... - это concurrency примитив, 'контейнер' для результатов (часть методов которого - блокирующие)
в Scheme promise - это control feature, которая просто позволяет делать delayed evaluation

Так ли это?

Второй вопрос:
Будет ли в Scheme какая-то принципиальная разница (кроме memoization) между promise и обычным s-expr?

(force (delay (+ 1 2))) ; => 3
(eval  (quote (+ 1 2))) ; => 3

Т.е. должен ли я использовать Java'вский CompletableFuture (aka Promise) для реализации Scheme Promise
или достаточно будет создать обычный класс Promise, который просто хранит тело выражения (s-exp) и результат (если есть), а force просто берет тело и выполняет его (передает хранящийся в promise s-exp evaluator'у)?

★★★★★

Интересный вопрос, тож погуглил, на вики вроде самое понятное описание:

The terms future, promise, delay, and deferred are often used interchangeably, although some differences in usage between future and promise are treated below. Specifically, when usage is distinguished, a future is a read-only placeholder view of a variable, while a promise is a writable, single assignment container which sets the value of the future.[4] Notably, a future may be defined without specifying which specific promise will set its value, and different possible promises may set the value of a given future, though this can be done only once for a given future. In other cases a future and a promise are created together and associated with each other: the future is the value, the promise is the function that sets the value – essentially the return value (future) of an asynchronous function (promise). Setting the value of a future is also called resolving, fulfilling, or binding it.

loz ★★★★★ ()

после 30 лет преподавания в MIT отказались от лиспа (и схемы) в пользу питона, поскольку воспитывалась склонность к созданию велосипедов у студентов

anonymous ()

Как я это вижу:

в Java/JS/... - это concurrency примитив, 'контейнер' для результатов (часть методов которого - блокирующие)
в Scheme promise - это control feature, которая просто позволяет делать delayed evaluation

Так ли это?

Всё правильно. Это просто штука для отложенных вычислений. R5RS не специфицирует многопоточность и всё такое.

Будет ли в Scheme какая-то принципиальная разница (кроме memoization) между promise и обычным s-expr?

Почти нет. Важно только чтобы force не вычисляла значение ещё раз. Флажка вполне достаточно. Вообще там обычно флажок и замыкание (а не тупо s-expr) внутри, чтобы можно было делать так:

(force (let ((x 5)) (delay x))

Там в самом R5RS есть пример реализации. Он даже не требует, чтобы promises были отдельным типом.

ilammy ★★★ ()
Ответ на: комментарий от loz

Не знаю насчет понятности, но самое точное описание следует искать у Карла Хьюитта, это он автор концепции. Он изобрел transparent futures, а все остальные промисы — это неполноценные суррогаты данной концепции, но по назначению близки, их цель — синхронизация конкурентных вычислений.

filequest ()

мда... прочитал сейчас, вроде так и есть, в схеме, свои, особенные промисы, отличные от того, что под этим имеется в виду в CS.

filequest ()

Собственно, там нечего вообще реализовывать, это у этих клоунов всего лишь сахар над

(define foo (lambda(proc) (proc)))

filequest ()
Ответ на: комментарий от anonymous

после 30 лет преподавания в MIT отказались от лиспа (и схемы) в пользу питона, поскольку воспитывалась склонность к созданию велосипедов у студентов

следовало бы не только от scheme, но и от самого sicp, отказаться, эта книженция учит говнопаттернам, авторы не умеют в полноценное проектирование.

filequest ()
Ответ на: комментарий от anonymous

после 30 лет преподавания в MIT отказались от лиспа (и схемы) в пользу питона, поскольку воспитывалась склонность к созданию велосипедов у студентов

Не устал ещё играть на толстенном и заезженном баяне всякий раз, когда слышится «лисп»? :-) Попей водички, если икается :-)

anonymous ()
Ответ на: комментарий от filequest

авторы не умеют в полноценное проектирование.

Ну так умеют ведь, зато, авторы Io или Smalltalk :-) Эти очень быстрые и нужные всему миру языки являются как эталоном всей CS, так и прекрасными средствами для создания любых программ :-) Именно поэтому создано так много систем на этих полноценно спроектированных системах :-)

anonymous ()
Ответ на: комментарий от anonymous

Я не про язык говорю, а про проектирование. Как могут студентов чему-то научить люди, которые делают такие ошибки? Научить то научат, но не тому, чему следует.

filequest ()
Ответ на: комментарий от anonymous

Вот пример детской ошибки

http://s8.hostingkartinok.com/uploads/images/2016/05/0ae72f92dfa75c54272ffa2f...

У них там баланс меняют клиенты, а это должен делать банк. Они, вместо построения правильной архитектуры, списывают свою ошибку на «плохое» поведение set!

Я чуть со стула не упал, когда до меня это дошло. Вот такой вот эталон хваленого митовского обучения.

filequest ()
Ответ на: комментарий от filequest

Я не про язык говорю, а про проектирование.

А, теоретик теории полнейшей инкапсуляции проектирования, т.е. когда проектировщик не знает языка для выражения его проекта, а кодировщик не знает фантазии проектировщика до того момента, по ему не принесут лист с заданием для кодирования? :-) Такой же мечтатель, как и все MVC-ориентированные адепты? :-) Язык отделять от проектирования - это всё равно, что думать про себя молча :-) Лол :-)

anonymous ()
Ответ на: комментарий от filequest

У тих там клиенты отдают распоряжение на изменение баланса. Баланс меняет банк. Так работает любая СУБД с многопользовательским доступом.

winlook38 ★★ ()

в Java/JS/... - это concurrency примитив, 'контейнер' для результатов (часть методов которого - блокирующие)
в Scheme promise - это control feature, которая просто позволяет делать delayed evaluation
Так ли это?

Да. Можешь считать это аналогом lazy evaluation. Название одинаковое, а смысл разный.

или достаточно будет создать обычный класс Promise, который просто хранит тело выражения (s-exp) и результат (если есть), а force просто берет тело и выполняет его (передает хранящийся в promise s-exp evaluator'у)?

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

Legioner ★★★★★ ()
Последнее исправление: Legioner (всего исправлений: 1)
Ответ на: комментарий от anonymous

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

filequest ()
Ответ на: комментарий от filequest

Scheme это гениальный язык, один из лучших языков в CS. Например JavaScript это Scheme с фигурными скобками, на нём сейчас пишет весь мир.

Legioner ★★★★★ ()
Последнее исправление: Legioner (всего исправлений: 2)
Ответ на: комментарий от anonymous

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

filequest ()
Ответ на: комментарий от Legioner

Во первых, JS — это не «Scheme со скобками», а self со схемой внутри.

Во вторых, ты тут выкрикиваешь фанбойские лозунги, а я опираюсь на факты.

filequest ()
Ответ на: комментарий от filequest

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

Legioner ★★★★★ ()
Последнее исправление: Legioner (всего исправлений: 1)
Ответ на: комментарий от Legioner

Вот краткое резюме предмета:

In the 1960’s at the MIT AI Lab a remarkable culture grew up around “hacking” that concentrated on remarkable feats of rogramming.54 Growing out of this tradition, Gerry Sussman and Guy Steele decided to try to understand Actors by reducing them to machine code that they could understand and so developed a “Lisp-like language, Scheme, based on the lambda calculus, but extended for side effects, multiprocessing, and process synchronization.” [Sussman and Steele 1975].

Their reductionist approach included primitives like the following:

 START!PROCESS  STOP!PROCESS  EVALUATE!UNINTERRUPTIBLEYii that had the following explanation: Of course, the above reductionist approach is very unsatisfactory because it missed a crucial aspect of the Actor Model: the reception ordering of messages

подробней http://arxiv.org/pdf/1008.1459.pdf со стр 43

filequest ()
Ответ на: комментарий от Legioner

Это легенды про белого бычка. Никто изначально не собирался совать схему в браузер. У Айка изначально была задача создать язык с си-подобным синтаксисом, семантически он его сделал как кастрированную реализацию self, только позже он добавил туда семантику scheme.

filequest ()
Ответ на: комментарий от Legioner

Можешь считать это аналогом lazy evaluation

не может он это считать. Явная задержка вычисления никакого отношения к лени не имеет. Таким макаром любое квотирование или передачу функций и строк в качестве параметров можно считать «аналогом lazy-evaluation». Это просто неуклюжая, и не особо нужная конструкция, которая даже особой роли не играет.

filequest ()
Ответ на: комментарий от filequest

А сам язык scheme, кстати, появился как результат некорректной реализации модели Акторов.

Прям с большой буквы, модель «Акторов» :-)

anonymous ()
Ответ на: комментарий от Legioner

Например JavaScript это Scheme с фигурными скобками, на нём сейчас пишет весь мир.

Да? :-) А где же макросы тогда? :-)

anonymous ()
Ответ на: комментарий от anonymous

Опять ты за свое пустое. В прошлых тредах разоблачили вроде макросы, а ты так и не понял? Макросы «есть» в любом языке, пиши препроцессор и будут тебе макросы. Вот fexpr's — это уже органичная часть семантики, их так просто не добавишь, не прибьешь сверху.

filequest ()
Ответ на: комментарий от winlook38

У тих там клиенты отдают распоряжение на изменение баланса. Баланс меняет банк

Так должно быть, но в их схеме не так. Если это так, откуда же тогда получается несответствие в балансе?

filequest ()
Ответ на: комментарий от winlook38

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

filequest ()
Ответ на: комментарий от filequest

Макросы «есть» в любом языке, пиши препроцессор и будут тебе макросы.

Нет, в JavaScript их нет :-) Зачем мне писать препроцессор, если в CL или в Scheme или даже в C есть макросы? Пиши препроцессор ты, а у меня макры есть :-)

anonymous ()
Ответ на: комментарий от filequest

Это всего лишь иллюстрация lost update problem. И варианты ее решения уже придуманы. Читай дальше там, где ты эту иллюстрацию нашел.

winlook38 ★★ ()
Ответ на: комментарий от winlook38

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

filequest ()
Ответ на: комментарий от filequest

Я говорю, нет там никакой проблемы

Мне насрать, что говорит человек, который ни разу с практическими задачами не работал. Ты хоть гуглить пробовал?

Подозреваю, твое решение заключается в том, чтобы предоставить клиентам возможность увеличения/уменьшения баланса мне прямой записи значения.

winlook38 ★★ ()
Ответ на: комментарий от anonymous

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

filequest ()
Ответ на: комментарий от filequest

не может он это считать. Явная задержка вычисления никакого отношения к лени не имеет. Таким макаром любое квотирование или передачу функций и строк в качестве параметров можно считать «аналогом lazy-evaluation». Это просто неуклюжая, и не особо нужная конструкция, которая даже особой роли не играет.

Функцию или строку тебе надо вручную вызвать/вычислить. А promise не надо, он для пользователя выглядит как обычное значение. А так да, если поддержки промисов в языке нет, придётся передавать функциональный объект и это будет lazy evaluation. Что тебя тут удивляет, я не знаю. lazy evaluation это такой паттерн, а не что-то волшебное.

Legioner ★★★★★ ()
Ответ на: комментарий от anonymous

Да? :-) А где же макросы тогда? :-)

Ну через eval можно поизвращаться. Вообще макросы, eval — практика показала, что это всё не нужно. В современных промышленных языках это не используется.

Legioner ★★★★★ ()
Ответ на: комментарий от winlook38

А мне насрать, что говорит человек, который рассуждает о «проблеме» даже не понимая смысла обсуждаемого.

Подозреваю, твое решение заключается

никакого решения нет, так как нет проблемы. Проблема в мозгах авторов SICP, в том что они не умеют проектировать приложения

filequest ()
Ответ на: комментарий от Legioner

надо вручную вызвать/вычислить

там то же самое, надо вызывать force

filequest ()
Ответ на: комментарий от filequest

Короче, смысл там такой, что клиенты имеют самостоятельный доступ к изменению баланса

Ты бредишь. Там банк предоставляет API из трёх запросов «Положить деньги», «снять деньги» и «узнать баланс». Как ты эими запросам произвольный баланс установишь?

monk ★★★★★ ()
Ответ на: комментарий от filequest

смысла обсуждаемого

О, ну ты-то уже постиг? Расскажешь?

в мозгах авторов SICP

Как я уже сказал, данную проблему решают, например, СУБД. man mvcc. SICP тут ни при чем.

winlook38 ★★ ()
Ответ на: комментарий от filequest

там то же самое, надо вызывать force

R5RS permits promises to be evaluated implicitly when passed to primitive operations and their result be used instead

Legioner ★★★★★ ()
Ответ на: комментарий от winlook38

ты у меня в бане, я на секунду подумал, что ты поумнел, но оказалось что нет. Оставайся там дальше.

filequest ()
Ответ на: комментарий от filequest

Проблема в мозгах авторов SICP, в том что они не умеют проектировать приложения

Скорее в твоих: ты понимать прочитанное не можешь. Там как раз вполне логично описано, как правильно спроектировать снятие денег в банке. К слову, в учебниках по СУБД для объяснения транзакций именно этот пример.

monk ★★★★★ ()
Ответ на: комментарий от filequest

откуда появляется несоответствие баланса

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

1. проверить достаточно ли остатках
2. установить остаток новый остаток

Но если процедура запущена дважды (многопоточность же), то может оказаться, что остаток изменится между действиями 1 и 2

monk ★★★★★ ()
Ответ на: комментарий от monk

Я повторяю, у них там детская ошибка. На этапе второго шага, «новое значение» клиент пересчитывает САМ значение нового баланса, на основании данных, которые он получил до этого, и которые не являются актуальными, затем сетит его.

filequest ()
Ответ на: комментарий от monk

не может этого быть. Эти две процедуры выполняются в одном потоке(при правильном проектировании) — в потоке банка.

filequest ()
Ответ на: комментарий от monk

остальные потоки всего лишь делают запросы, они ничего не решают и не запускают. (опять же — в правильном случае)

filequest ()
Ответ на: комментарий от filequest

Эти две процедуры выполняются в одном потоке(при правильном проектировании) — в потоке банка.

То есть твой банк может обслуживать клиентов (позволять им снимать деньги) только по очереди? Ну-ну... расскажи ещё про правильное проектирование.

monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от filequest

На этапе второго шага, «новое значение» клиент пересчитывает САМ значение нового баланса

С чего это? Оба шага внутри одной функции (withdraw). Клиент её только вызывает.

monk ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.