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

PM>> Технически, в Питоне и C# попросту нет нужных операторов и эмулировать их никак нельзя.

VD>А чего нехватает. Я что-то с ходу не уловил.

Ну как чего не хватает? Именно операторов shift/reset, на которых построено все изложение, нет.
Re[9]: Монады и delimited continuations
От: BulatZiganshin  
Дата: 22.11.07 13:56
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Уверяю тебя, что читатель заинтересован. Вот только если он увидит примеры толко на Схеме, то многие скажут "игрушки". Не будем спорить о их правоте. Они просто это скажут. А если там будут примеры на более, скажем так, приземленных языках, то они с огромной вероятностью прочтут такую статью.


я уже рассказывал, что проищоло когда один товарищ написал на C++ с лямбдами и lazy streams. товарищи его покрутили у виска рукой и переделали "по-человечески". я видел тот код — хотя там было что-то типа простой list comprehesion, читать его было совершенно невозможно
Люди, я люблю вас! Будьте бдительны!!!
Re[10]: Монады и delimited continuations
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.11.07 15:30
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>Ну как чего не хватает? Именно операторов shift/reset, на которых построено все изложение, нет.


Можно в двух словах их смысл? Это не тоже самое что клонирование итератора?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Монады и delimited continuations
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.11.07 15:30
Оценка:
Здравствуйте, BulatZiganshin, Вы писали:

BZ>я уже рассказывал, что проищоло когда один товарищ написал на C++ с лямбдами и lazy streams. товарищи его покрутили у виска рукой и переделали "по-человечески". я видел тот код — хотя там было что-то типа простой list comprehesion, читать его было совершенно невозможно


Кому?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: Монады и delimited continuations
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 22.11.07 15:45
Оценка: +1
Здравствуйте, VladD2, Вы писали:

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


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

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


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

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


Почему?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[11]: Монады и delimited continuations
От: BulatZiganshin  
Дата: 22.11.07 15:50
Оценка:
Здравствуйте, VladD2, Вы писали:

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


BZ>>я уже рассказывал, что проищоло когда один товарищ написал на C++ с лямбдами и lazy streams. товарищи его покрутили у виска рукой и переделали "по-человечески". я видел тот код — хотя там было что-то типа простой list comprehesion, читать его было совершенно невозможно


VD>Кому?


мне. никогда не видел boost::lambda in action?
Люди, я люблю вас! Будьте бдительны!!!
Re[11]: Монады и delimited continuations
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 22.11.07 16:19
Оценка: 1 (1)
Здравствуйте, VladD2, Вы писали:

VD>Можно в двух словах их смысл? Это не тоже самое что клонирование итератора?


У palm_mute есть замечательная статья shift/reset для самых маленьких, часть 1.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[12]: Монады и delimited continuations
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.11.07 16:32
Оценка:
Здравствуйте, BulatZiganshin, Вы писали:

BZ>мне. никогда не видел boost::lambda in action?


А... Вот тут
Автор: vdimas
Дата: 22.11.07
в соседнем форуме товарищь считает, что небольшие приседения в больших объемах тлоько на пользу для ягодичных мышц.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: Монады и delimited continuations
От: palm mute  
Дата: 22.11.07 16:46
Оценка: 10 (1)
Здравствуйте, VladD2, Вы писали:

PM>>Ну как чего не хватает? Именно операторов shift/reset, на которых построено все изложение, нет.

VD>Можно в двух словах их смысл? Это не тоже самое что клонирование итератора?

В двух словах? Это кажется мне затруднительным, я не так давно худо-бедно, в меру своих ограниченных литературных способностей, 19 кб текста написал, понятнее у меня сейчас вряд ли получится. Но я попробую еще раз.
reset — обозначает границу, до которой можно резать; shift — захватывает фрагмент call-стека до обозначенной границы.
Самое простое, что можно сделать с захваченным контекстом — это просто его вернуть вызывающему коду с помощью выражения (shift k k); получаем эффект, аналогичный точке останова (прямо как вызов int 3; аналогия принадлежит Олегу Киселеву).

Вот минимальный пример, без монад:
(define (break) (shift k k))

(define (forrest)
  (reset
   (begin
     (display "before breakpoint 1")
     (newline)

     (display (format "value returned from breakpoint 1: ~a" (break)))
     (newline)

     (display "before breakpoints 2 & 3")
     (newline)

     (display (format "result of complex expression with breaks inside: ~a"
                      (+ 10 (* (break) 2) (break))))
     (newline)
     "final value")))

(define (run-forrest-run)
  (let* ((snapshot1 (forrest))
         (snapshot2 (snapshot1 "eat this"))
         (alternative-snapshot2 (snapshot1 "now eat that"))
         (snapshot3 (snapshot2 10))
         (alternative-snapshot3 (alternative-snapshot2 20))         
         (final-value (snapshot3 20))
         (alternative-final-value (alternative-snapshot3 40)))
    (begin
      (display (format "final value is: ~a" final-value))
      (newline)
      (display (format "alternative final value is also: ~a" final-value))
      (newline))))


Если запустить run-forrest-run, получим следующий вывод:
before breakpoint 1
value returned from breakpoint 1: eat this
before breakpoints 2 & 3
value returned from breakpoint 1: now eat that
before breakpoints 2 & 3
result of complex expression with breaks inside: 50
result of complex expression with breaks inside: 90
final value is: final value
alternative final value is also: final value


Все переменные snapshotX, alternative-snapshotX отражают состояние процедуры forrest на какой-то из точек останова, причем запускать каждую из них можно неограниченное количество раз и притом с разными аргументами. C# так не умеет, т.к. iterator.MoveNext() не принимает никаких аргументов. Питон так умеет, но у него тоже есть ограничения. Главное ограничение — yield нельзя передать в качестве callback-функции. Код ниже совершенно бессмысленный:
def foo(f):
    items = getSomeItems()
    for item in items:
        f(item)
...
foo(yield)


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

О возможности клонирования шарповских итераторов я никогда не слышал.
Re[12]: Монады и delimited continuations
От: palm mute  
Дата: 22.11.07 16:52
Оценка:
Здравствуйте, lomeo, Вы писали:

L>У palm_mute есть замечательная статья shift/reset для самых маленьких, часть 1.


Кстати, мне интересно, неужто до конца никто не осилил? В исходном-то посте, с которого началось обсуждение, в конце, я ссылку на свой опус давал.
Re[13]: Монады и delimited continuations
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 22.11.07 17:30
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>Кстати, мне интересно, неужто до конца никто не осилил? В исходном-то посте, с которого началось обсуждение, в конце, я ссылку на свой опус давал.


Не знаю, после того как ты в ЖЖ про shift/reset рассказал, то что ты здесь написал я понял прекрасно. Ну, я надеюсь, что прекрасно

А по ссылкам не ходил. Не до того пока.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[13]: Монады и delimited continuations
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.11.07 10:04
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>Кстати, мне интересно, неужто до конца никто не осилил? В исходном-то посте, с которого началось обсуждение, в конце, я ссылку на свой опус давал.


Скажу честно поглядев ее (скролингом) и увидив кучу кода на Лиспе я решил отложить ее чтение до лучших времен, так как воспринимаю Лисп с большим трудом.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Покритикуйте калькулятор на Haskell
От: Кодт Россия  
Дата: 23.11.07 12:00
Оценка:
Здравствуйте, lomeo, Вы писали:

L>Например,

L>data CalcS a = StateT Env (ErrorT String IO) a

L>Из-за лифтинга сможешь явно звать методы и MonadState и MonadError в одном do-блоке:
L>if param < 0
L>    then throwError "Negative" -- тут мы зовём метод MonadError
L>    else modify (param:)       -- тут мы зовём метод MonadState

А можешь пояснить, каким образом здесь throwError и modify оказались одного типа — судя по всему, ()->CalcS() ?
Или имелось в виду всё-таки liftM.throwError ?
if param < 0
    then liftM $ throwError "Negative"
    else modify (param:)
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[5]: Покритикуйте калькулятор на Haskell
От: palm mute  
Дата: 23.11.07 12:07
Оценка: 1 (1) +1
Здравствуйте, Кодт, Вы писали:

К>А можешь пояснить, каким образом здесь throwError и modify оказались одного типа — судя по всему, ()->CalcS() ?

К>Или имелось в виду всё-таки liftM.throwError ?
К>
К>if param < 0
К>    then liftM $ throwError "Negative"
К>    else modify (param:)
К>


Библиотечные трансформеры монад знают друг о друге и лифтят автоматически. Некрасиво, но удобно.
Re[6]: Покритикуйте калькулятор на Haskell
От: palm mute  
Дата: 23.11.07 12:23
Оценка: 27 (1)
Здравствуйте, palm mute, Вы писали:

PM>Здравствуйте, Кодт, Вы писали:


К>>А можешь пояснить, каким образом здесь throwError и modify оказались одного типа — судя по всему, ()->CalcS() ?

К>>Или имелось в виду всё-таки liftM.throwError ?
К>>
К>>if param < 0
К>>    then liftM $ throwError "Negative"
К>>    else modify (param:)
К>>


PM>Библиотечные трансформеры монад знают друг о друге и лифтят автоматически. Некрасиво, но удобно.


Вот пример, как это выглядит, именно для класса MonadError:
instance (MonadError e m) => MonadError e (StateT s m) where
    throwError       = lift . throwError
    m `catchError` h = StateT $ \s -> runStateT m s
        `catchError` \e -> runStateT (h e) s


И, кстати, твой код неверный — там должен быть lift, liftM — это урезанная версия fmap для монад.
Re[12]: Монады и delimited continuations
От: Tonal- Россия www.promsoft.ru
Дата: 25.11.07 12:58
Оценка: 13 (2)
Здравствуйте, palm mute, Вы писали:
PM>Все переменные snapshotX, alternative-snapshotX отражают состояние процедуры forrest на какой-то из точек останова, причем запускать каждую из них можно неограниченное количество раз и притом с разными аргументами. C# так не умеет, т.к. iterator.MoveNext() не принимает никаких аргументов. Питон так умеет, но у него тоже есть ограничения. Главное ограничение — yield нельзя передать в качестве callback-функции. Код ниже совершенно бессмысленный:
PM>
PM>def foo(f):
PM>    items = getSomeItems()
PM>    for item in items:
PM>        f(item)
PM>...
PM>foo(yield)
PM>

PM>А с настоящими continuations — это не проблема. Они позволяют вгрызаться в произвольный код.
Помедитировал тут на досуге над эти, и накатал такой вот классик:
class shift(object):
  def __init__(self, func):
    def wrapper(*args, **kw):
      gen = func(*args, **kw)
      gen.next()
      return gen
    self.cons = wrapper()

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

Теперь сипользование:
def for_each(it, func):
  "Итеративная функция"
  for item in it:
    func(item)

def test():
  "Наши вычисления над итемами"
  while True:
    item = (yield)
    print item

#Запускаем "продолжения"
for_each(xrange(10), shift(test))

Можно попробывать ещё и (yield) завернуть в итератор...
Оно конечно не настоящие "продолжения" но вроде где-то рядом.

PM>О возможности клонирования шарповских итераторов я никогда не слышал.

В python-е это itertools.tee
... << RSDN@Home 1.2.0 alpha rev. 784>>
Re[13]: Монады и delimited continuations
От: palm mute  
Дата: 25.11.07 13:29
Оценка:
Здравствуйте, Tonal-, Вы писали:

PM>>А с настоящими continuations — это не проблема. Они позволяют вгрызаться в произвольный код.

T>Помедитировал тут на досуге над эти, и накатал такой вот классик: [skip]
T>def test():
T>  "Наши вычисления над итемами"
T>  while True:
T>    item = (yield)
T>    print item
T>

T>Оно конечно не настоящие "продолжения" но вроде где-то рядом.
Это не то. У тебя test — сопрограмма (coroutine, не путать с копрограммой), т.к. добровольно делает паузы с помощью оператора yield. Я задачу формулировал по-другому — превратить произвольную функцию в сопрограмму, передав ей соответствующий callback. Твоя функция for_each, как и моя foo, будучи запущенной, выполняется до конца.

PM>>О возможности клонирования шарповских итераторов я никогда не слышал.

T>В python-е это itertools.tee
За это спасибо.
Re[14]: Монады и delimited continuations
От: Tonal- Россия www.promsoft.ru
Дата: 25.11.07 15:35
Оценка:
Здравствуйте, palm mute, Вы писали:
PM>Это не то. У тебя test — сопрограмма (coroutine, не путать с копрограммой), т.к. добровольно делает паузы с помощью оператора yield. Я задачу формулировал по-другому — превратить произвольную функцию в сопрограмму, передав ей соответствующий callback. Твоя функция for_each, как и моя foo, будучи запущенной, выполняется до конца.
Вот я и пытаюсь понять можно ли обернуть конструкцию
...
  while True:
    item = (yield)
...
[py]
в итератор.
Тогда бы test мог выглядеть совершенно невинно:
[py]
def test(it):
  for item in it:
    print item

Только пока никак не могу сообразить как это сделать.

Кстати вот наткнулся на интересные ссылки:
Continuations and Stackless Python, Stackless Python
... << RSDN@Home 1.2.0 alpha rev. 784>>
Re[15]: Монады и delimited continuations
От: palm mute  
Дата: 25.11.07 16:15
Оценка:
Здравствуйте, Tonal-, Вы писали:

T>Вот я и пытаюсь понять можно ли обернуть конструкцию

T>[py]
T>...
T> while True:
T> item = (yield)
T>...
T>[py]
...
T>Только пока никак не могу сообразить как это сделать.
Думаю, это невозможно.

T>Кстати вот наткнулся на интересные ссылки:

T>Continuations and Stackless Python, Stackless Python
Я внимательно не читал, только просмотрел. Похоже, авторы добавили поддержку call/cc в Питон.
Re[14]: Монады и delimited continuations
От: lomeo Россия http://lomeo.livejournal.com/
Дата: 27.11.07 12:45
Оценка: 31 (2)
Здравствуйте, VladD2, Вы писали:

VD>Скажу честно поглядев ее (скролингом) и увидив кучу кода на Лиспе я решил отложить ее чтение до лучших времен, так как воспринимаю Лисп с большим трудом.


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



Что касается кода на Лисп, то переписать это на руби (или stackless питон) трудновато без подходящих примитивов.
Вот тут есть статья, как реализовать shift/reset на руби с помощью callcc. Это один-в-один переложение реализации shift/reset на схеме (http://mumble.net/~campbell/scheme/shift-reset.scm).

@@metacont = lambda { |x|
    raise RuntimeError, "You forgot the top-level reset..."
}

def reset(&block)
    mc = @@metacont
    callcc { |k|
        @@metacont = lambda { |v|
            @@metacont = mc
            k.call v
        }
        x = block.call
        @@metacont.call x
    }
end

def shift(&block)
    callcc { |k|
        @@metacont.call block.call(lambda { |*v| reset { k.call *v } })
    }
end


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

Лучше всего, наверное, это показать на примере. Вот код из статьи:

def each_to_stream(collection)
  reset {
    collection.each { |v|
      shift { |k|
        lambda { |&block|
          block.call v
          k.call
        }
      }
    }
    nil
  }
end


Заменим shift/reset на callcc, бета-редуцируем, уберём кое-где всякие @@metacont и вообще сократим.
Получим таким образом (псевдокод)

def each_to_stream(collection)
        callcc { |k1|
                k3({
                        collection.each(lambda { |v|
                                callcc { |k2|
                                        {k3|k1}(lambda { |b|
                                                b(v)
                                                callcc { |k3|
                                                        k3(k2([]))
                                                }
                                        })
                                }
                        })
                        nil
                })
        }
end


Здесь foo({x;y}) — это вызов с параметром, являющимся результатом выполнения блока, а не самим блоком. Также b.call(v) заменены просто на b(v). Конструкция {k3|k1} возвращает k3, если уже он был определён (во внутреннем callcc) либо k1. Плюс нам по большому счёту не важно, что вернёт k2, он тут играет роль goto.

Итак! iter = each_to_stream [1,2,3,4,5,6] нам вернёт lambda {|b| b(v); callcc {|k3| k3(k2([]))}} с контекстом k1. При вызове iter.call {|v| p v} значение будет напечатано (b(v)), дальше k2 выходит из лямбды (k2([]), реализация collection.each выбирает следующий элемент, для него делается callcc {|k2|...} и возвращается опять та же lambda {|b| b(v); callcc {|k3| k3(k2([]))}} но уже с контекстом k3, который знает о состоянии collection.each, и следовательно, который можно скопировать. Ну и дальше то же самое — печать и возврат лямбды с контекстом k3 до тех пор пока перебор не закончится, тогда возвращается nil.

Погляди на исходный код — там это записано более явно, чем через callcc — shift там сращу возвращает нужную нам лямбду, или если перебор окончен, то nil. Поэтому я говорил о выворачивании кода наизнанку, у нас получается как будто внутренний блок (в shift) зовёт внешний внутри себя. Именно благодаря этому приёму palm_mute завернул прямые вызовы в bind монады. Вот один в один код palm_mute, переложенный на ruby (я руби знаю очень плохо, поэтому поправьте меня, если что то можно сделать проще)

#
# Вот этот код "вывернется" наружу, обернув примитивы State в bind.
#
def reflect(&m)
    shift { | k | bindM(m, k) }
end

#
# Следующие две функции - это реализация монады State.
#
def returnM(x)
    lambda { |s| [x,s] }
end

def bindM(m, f)
    lambda do |s|
        as1 = m.call s
        a  = as1[0]
        s1 = as1[1]
        f.call(a).call(s1)
    end
end

#
# Следующие две функции - простые примитивы для работы с монадой State.
#
def put(s)
    reflect { |_| [[], s] }
end

def get
    reflect { |s| [s,s] }
end

#
# Вот так мы разворачиваем состояние.
#
def run_state(s0, &m)
    (reset { returnM(m.call) }).call(s0)
end

#
# Пример использования
#
def testMe
    state = run_state(10) do
        x = get
        put(x + 5)
        put(get + get)
        0
    end

    print state[1]
end

testMe


Хотя сомневаюсь, что так понятнее, чем на Схеме, но чем на callcc должно быть понятнее, это точно
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.