Re[15]: Монады и delimited continuations
От: palm mute  
Дата: 27.11.07 13:26
Оценка:
Здравствуйте, lomeo, Вы писали:


L>Кстати, забавно. Gaperton спрашивал про язык "со скобочной записью вызовов", я так понял, противопоставляя его Haskell. Поэтому я подумал, что он говорит о foo(x,y), а palm_mute о (foo x y )

L>

Я просто проигнорировал замечание о синтаксисе, т.к. оно не относится к делу; Схему было удобно использовать для примера. Если есть continuations, не нужен специальный синтаксис — мы используем стандартный, меняя его семантику.
Re[10]: Монады и delimited continuations
От: VladD2 Российская Империя www.nemerle.org
Дата: 29.11.07 12:21
Оценка:
Здравствуйте, lomeo, Вы писали:

L>Здравствуйте, VladD2, Вы писали:


VD>>Ну, для того чтобы повторить Хаскелевский Парсек их за глаза хватает. Вот.


L>Угу, читал эту статью. Только не понял при чём тут парсек?


Ну, да причем? Повторили его идею комбинаторного парсера. Вместо монад использовали итераторы и объекты.

VD>> Сдается мне для данного примера C# за глаза должно хваоить.


L>Вряд ли. Ты в примере разобрался? По большому счёту там строится один большой reset с кучей shift внутри, за счёт чего мы получаем серию из этих delimited continuations. Как такое сделать на C# я не представляю, yield слишком маленький для этого.


Видимо плохо я в нем разобрался. Времени нет. Можно описание на пальцах (самой задачи) без примеров на Лиспе и т.п.?

VD>>А так... как я понял эти shift/reset тоже не 100%-ное решение.


L>Почему?


Вы же сами тут говорите, что полноценные континюэшоны вроде как круче. Или я не так вас понял?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Монады и delimited continuations
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 29.11.07 13:40
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Ну, да причем? Повторили его идею комбинаторного парсера. Вместо монад использовали итераторы и объекты.


Ну так, LINQ — это и есть монада, from..in — это <-, select — это return. Да и вообще, понятно, что парсек можно повторить на других языках, вопрос в выразительности/удобстве использования.

Только при чём тут continuations, мы же вроде о них говорили в сравнении с yield? Или это была аналогия?

VD>Видимо плохо я в нем разобрался. Времени нет. Можно описание на пальцах (самой задачи) без примеров на Лиспе и т.п.?


Конкретно эта задача показывает, что монады отражаются на continuations.
shift/reset позволяют выразить это отражение элегантным образом (на чистом call/cc reflect и runState будут выглядеть похуже).

Тут просто интересно то, как это делается — связка shift-ов это по сути связка bind-ов, а т.к. shift можно писать отдельно, то мы получаем аналог do-синтаксиса в Haskell.

VD>Вы же сами тут говорите, что полноценные континюэшоны вроде как круче. Или я не так вас понял?


Они (shift/reset) тоже полноценные, просто они чуть эффективнее, т.к. позволяют руками определять границу стека, по которой резать. Ну, и в ряде случаев, более выразительнее.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[12]: Монады и delimited continuations
От: VladD2 Российская Империя www.nemerle.org
Дата: 29.11.07 16:03
Оценка:
Здравствуйте, lomeo, Вы писали:

L>Здравствуйте, VladD2, Вы писали:


VD>>Ну, да причем? Повторили его идею комбинаторного парсера. Вместо монад использовали итераторы и объекты.


L>Ну так, LINQ — это и есть монада,


Ну, это для тех кто их там очень хочет угядеть. Монады официально (штатно) есть только в Хаскеле. В C# их слава богу нет (иначе бы этот язык тоже половина народа понять не могла бы).

L> from..in — это <-, select — это return.


from, in и select всего лишь синтаксический сахар к нбору (почти стандартному) ФВП. Точнее from..in переписывается в банальное задание имени для элементов коллкций, а select так вообще чистый Map().

L>Да и вообще, понятно, что парсек можно повторить на других языках, вопрос в выразительности/удобстве использования.


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

L>Только при чём тут continuations, мы же вроде о них говорили в сравнении с yield? Или это была аналогия?


Дык в ном примере как раз все кишки на yield и реализованы.

L>Тут просто интересно то, как это делается — связка shift-ов это по сути связка bind-ов, а т.к. shift можно писать отдельно, то мы получаем аналог do-синтаксиса в Haskell.


Не. Это объяснение мне не понять. Да и я вообще-то просил объяснить суть примера, а не что им пытались обосновать (описать).
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[13]: Монады и delimited continuations
От: VoidEx  
Дата: 29.11.07 20:02
Оценка:
Здравствуйте, VladD2, Вы писали:


div (x : int, y : int) : int
{
  call/cc (fun (return)
    {
      when (y = 0)
        return 0;
      x / y
    }
  )
}


call/cc принимает лямбду. Лямбда принимает текущий контекст, и если происходит
"вызов" этого контекста, то управление сразу переходит к этому контексту, и все значение
calc/cc становится равным аргументов, переданных контектсу.
Т.е. в данном примере, return — это что-то типа

fun (a) {
  ...
  div (x : int, y : int) : int
  {
    a
  }
  ...
}

Когда внутри лямбды, переданной внутрь calc/cc мы пишем return 0, в контекст сразу "возвращается" 0, если return не используется, то возвращается просто результат выполнения это лямбды.

Теперь reset и shift
reset обозначает границу, докуда этот контекст захватывать, а shift захватывает позволяет
его использовать, как функцию
Например
reset (10 + (shift (foo => 1 + 2 + 3 + (foo 3))))

Т.е. в данном случае foo будет равен (10 + _) и результатом всего reset-а будет
1 + 2 + 3 + (10 + 3)

Тут, конечно, псевдно-код, но, может, понятнее стало
Re[13]: Монады и delimited continuations
От: _nn_ www.nemerleweb.com
Дата: 29.11.07 20:09
Оценка: +1
Здравствуйте, Tonal-, Вы писали:

T>
T>class shift(object):
T>  def __init__(self, func):
T>    def wrapper(*args, **kw):
T>      gen = func(*args, **kw)
T>      gen.next()
T>      return gen
T>    self.cons = wrapper()

T>  def __call__(self, item):
T>    self.cons.send(item)
T>


Какой смысл wrapper-а ?
Можно и так:
def shift(func):
    cons = func()
    cons.next()
    return cons.send()
http://rsdn.nemerleweb.com
http://nemerleweb.com
Re[13]: Монады и delimited continuations
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 29.11.07 23:54
Оценка: 7 (1) +1
Здравствуйте, VladD2, Вы писали:

L>>Ну так, LINQ — это и есть монада,


VD>Ну, это для тех кто их там очень хочет угядеть.


bind есть, return есть, монадическим правилам подчиняется, значит монада, т.к. отвечает её определению.

L>> from..in — это <-, select — это return.


VD>from, in и select всего лишь синтаксический сахар к нбору (почти стандартному) ФВП. Точнее from..in переписывается в банальное задание имени для элементов коллкций, а select так вообще чистый Map().


Вот именно Ты сказал то же самое, что и я, но другими словами.

Кстати, под select я имел в виду не метод Select, а конструкцию select x, которая принимая тип элемента возвращает IEnumerable над ним. Это так, к вопросу о том, что select — это map.

VD>Тогда что понимать по повторить. Боюсь, что повтор на С, да и на С++ могут оказаться настолько "выразительным", что все кто это увидит будут долго и нецензурно выражаться .


Кроме как развести руками, ничего не остаётся.
С другой стороны не будь LINQ-а, на C# это можно было бы описать с помощью лямбд, хотя и не так красиво.

VD>Дык в ном примере как раз все кишки на yield и реализованы.


Э-э-э, не заметил

L>>Тут просто интересно то, как это делается — связка shift-ов это по сути связка bind-ов, а т.к. shift можно писать отдельно, то мы получаем аналог do-синтаксиса в Haskell.


VD>Не. Это объяснение мне не понять. Да и я вообще-то просил объяснить суть примера, а не что им пытались обосновать (описать).


Уф, ну постараюсь.

Давай для начала обзовём лямбды внутри get и set именами get' и set'.
Тогда

get = reflect(get')
set = reflect(set')


Дальше

reflect(m) = shift (f => m >>= f)


(здесь я вместо bind буду для удобства писать >>=)
Нам надо вычислить

(А) runState { x = get; put(x + 5); put(get + get) }

т.к. runState(m, s0) = (reset { return m })(s0) то (А) аналогично

(B) (reset { return {
    x  = shift(f => (s => (s,s)) >>= f)
        shift(f => (_ => ((), x + 5)) >>= f)
        $1 = shift(f => (s => (s,s)) >>= f)
        $2 = shift(f => (s => (s,s)) >>= f)
        shift(f => (_ => ((), $1 + $2)) >>= f)
    }})


Вот и всё! Дальше зная, что этот код вывернется, начиная с первого shift, получаем

(C) (s => (s,s)) >>=
(x => (_ => ((), x + 5)) >>=
(_ => (s => (s,s)) >>=
($1 => (s => (s,s)) >>=
($2 => (_ => ((),$1 + $2))))))
[code]

Это ключевое место, обрати внимание как (B) преобразуется в (C).
Мы просто везде вместо f подставляем готовый контекст - как будто, мы выдернули первый shift, и вместо f подставили всё что осталось в reset-блоке, дальше в нём выдернули следующий shift и т.д. пока у нас не осталось ни одного shift-а.

Т.е

[code]
reset { q; shift(k => m(k)); shift(k => n(k)); p}

эквивалентно
m(n({q;p}))


Вооот... Дальше!
Если ты посмотришь как реализован bind, то увидишь, что (С) это функция, которая протаскивает параметр через тапл, что то вроде

s0 => let (x, _) = get'(s0)      // (s0,s0)
          (_,s1) = put'(x+5)     // ((), s0+5)
                    ($1,_) = get'(s1)      // (s0+5,s0+5)
                    ($2,_) = get'(s1)      // (s0+5,s0+5)
             in ((), $1 + $2)          // ((), (s0+5)+(s0+5))


Разумеется, передав ей 10 мы получим ((), 30).
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[9]: Монады и delimited continuations
От: SmbdRsdn  
Дата: 24.04.08 21:39
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Ну, для того чтобы повторить Хаскелевский Парсек их за глаза хватает. Вот. Сдается мне для данного примера C# за глаза должно хваоить.


А где замечание, что в статье используется сжатие C# кода до безобразия? В статье присутствует строка в 181 символ длиной.

То есть 2+ получается после ужатия C#-ного кода до безоразия (объявления и выражения на одной строке, 150-символьные строки).


отсюда
Автор: VladD2
Дата: 21.05.07
Re[13]: Монады и delimited continuations
От: Alexey Romanov  
Дата: 25.04.08 14:02
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, lomeo, Вы писали:


L>>Здравствуйте, VladD2, Вы писали:


VD>>>Ну, да причем? Повторили его идею комбинаторного парсера. Вместо монад использовали итераторы и объекты.


L>>Ну так, LINQ — это и есть монада,


VD>Ну, это для тех кто их там очень хочет угядеть. Монады официально (штатно) есть только в Хаскеле. В C# их слава богу нет (иначе бы этот язык тоже половина народа понять не могла бы).


Есть. LINQ to Objects -- это одна конкретная монада (List в Haskell), но поскольку есть ещё Query Pattern (в силу недостаточной выразительноси системы типов), то можно свободно писать любые другие монады (см. примеры здесь). Хотя, конечно, на F# оно выглядит получше.
Но когда где-нибудь появляется очередной ???LINQ (SyncLINQ, DLINQ, Push LINQ) -- это именно новая монада.

L>> from..in — это <-, select — это return.


VD>from, in и select всего лишь синтаксический сахар к нбору (почти стандартному) ФВП. Точнее from..in переписывается в банальное задание имени для элементов коллкций, а select так вообще чистый Map().


Ну да, именно так List и работает.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.