Здравствуйте, dsorokin, Вы писали:
D>В основе лежит монада списка (сюрприз!).
В основе чего? Какую роль она выполняет в языке неленивым исполнением?
D>Но как я понял, можно определять в linq и свои монады. Только непонятно, насколько эквивалентно получается тем же вычислительным выражениям.
Я одного не понимаю... неужели нельзя верить свои глазам?
Я понимаю зачем нужны монады в ComputationExpressions. Более того монады тут видны не вооруженным взглядом. Есть те самые бинд, ретон и т.п.
А зачем нужны монады в банальной библиотеке ФВП? И где те самые бинд, ретон и т.п.?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>В основе чего? Какую роль она выполняет в языке неленивым исполнением?
Неленивость (энергичность) тут ни причем.
VD>Я одного не понимаю... неужели нельзя верить свои глазам?
VD>Я понимаю зачем нужны монады в ComputationExpressions. Более того монады тут видны не вооруженным взглядом. Есть те самые бинд, ретон и т.п.
VD>А зачем нужны монады в банальной библиотеке ФВП? И где те самые бинд, ретон и т.п.?
Ну, выше же была ссылка. Там определялась монада Maybe через linq. Где-то я видел определение на linq чего то типа парсека. Да, и вообще, устал я уже от этой темы. Ты лучше enumerable comprehension зацени вместе со всеми плюшками
Например, в обычной ситуации у меня компилятор обламывался на yield, использованном внутри try-catch-finally. В enumerable comprehension это все должно работать! Using должен работать, даже с секцией catch! Foreach практически такой же как и стандартный. Загляденье.
Здравствуйте, dsorokin, Вы писали:
D>Я не понял, что с этим делать.
Это возможность другим макросам сгенерировать код обработчиков исключений. В общем случае нужно просто давать сгенерировать код и потом обрабатывать сгенерированный код.
D>В общем, я сделал все, что хотел. Можно назвать готовой бетой. Теперь исправления ошибок, если таковые будут.
Будут, не сомневайся . Если программа запустилась с первого раза, ищите ошибку в компиляторе (с)
D>Остается только неясность с FakeVoid (в F# для инстанцирования генериков по как бы void используется класс Unit, поддерживаемый на уровне компилятора).
Можно внести в стандартную библиотеку:
public struct unit { }
может быть еще попытаться добавить неявные приведения типов от void к unit и обратно.
D>Плюс нужно написать документацию. Но теперь темп будет уже не таким.
Вот как документацию писать, так...
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, dsorokin, Вы писали:
D>Неленивость (энергичность) тут ни причем.
А что здесь причем?
D>Ну, выше же была ссылка. Там определялась монада Maybe через linq. Где-то я видел определение на linq чего то типа парсека.
У тебя нарушена причино-следственная связь.
Конечно, используя linq без проблем можно описать что-то типа монады, так как SelectMeny имеет ту же сигнатуру, что и бинд. Но вот обратное не верно! Линк это библиотека ФВП. Мало чем отличающаяся от прелюда хаскеля. И это вся правда!
D>Да, и вообще, устал я уже от этой темы. Ты лучше enumerable comprehension зацени вместе со всеми плюшками
Заценю конечно. Просто я привык на практике заценивать, а задачи пока под это дело особо нет.
У меня сейчас вообще задачи — баги в компиляторе и интеграции править. Вот за вчера два поправил.
D>Например, в обычной ситуации у меня компилятор обламывался на yield, использованном внутри try-catch-finally. В enumerable comprehension это все должно работать! Using должен работать, даже с секцией catch! Foreach практически такой же как и стандартный. Загляденье.
Да, не плохо! Но и у ComputationExpressions тоже своих ограничений хватает. Главное из которых — это замкнутый подъязык. Те же макросы в нем не будут работать.
Кстати, хорошо бы понятные и простые тесты написать. Так бы можно было просто запустить тестовый проект под отладкой и поглядеть.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, dsorokin, Вы писали:
D>2) установленный run-time для F# (идет вместе с .NET v4).
4.0 вряд ли запустится под 3.5. Кроме того не ясно что с лицензией.
По идее раньше F# был в двух версиях, в том числе и в версии для 3.5. Не знаю выходила ли версия для 3.5 после выхода четвертого фрэймворка. Если выходила, то можно ею воспользоваться.
А что там в этой поддержке async-а такого есть?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[17]: Ликбез по ComputationExpressions
От:
Аноним
Дата:
25.04.10 20:37
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>А если скажем без IEnumerable? Или без SelectMany?
Без IEnumerable будет другая монада Без SelectMany будет моноид какой-нибудь или функтор. Наверное. Я не спец в теории категорий
VD>Ну, да. Ну, да. Это все я видел. Я же говорю... В прочем не буду повторяться (см. выше).
Я только хотел сказать, что и в программировании один и тот же феномен можно описывать разными способами. linq можно рассматривать как набор extension-методов, как mixin к коллекциям, как введение синтаксиса SQL в си-шарп и vb, как библиотеку комбинаторов, как порт хаскеллового прелюда, как обобщенный механизм запросов к источникам данных или вот как специальную нотацию для монад.
Никто, конечно же, не заставляет считать linq монадой, но это утверждение намного обоснованней, чем названия созвездий (имхо).
Монады, они ведь везде. Даже nullable можно считать монадой, если очень захотеть.
Вместо этих двух уродств. Нужно сделать ExecutionContext который может быть одним из нескольких пулов потоков, очередью разбора собщений WindowsForms или чемто еще.
Тогда можно будет делать так:
def poolContext = ThreadPoolExecutionContext(10);
def guiContext = WindowsFormsExecutionContext(form);
def worker()
{
comp async
{
callcomp Async.SwitchTo(poolContext);
//делаем что-то тяжолое в контексте пула.
callcomp Async.SwitchTo(guiContext);
//а тут спокойно ковыряемся в gui.
returncomp worker();
}
}
poolContext.Start(worker());
3)Async.Sleep использование int когда есть TimeSpan диверсия.
4)Агенты слишком куцое решение.
По хорошему нужно сделать каналы.
А на каналах агенты делаются одной левой.
Причем можно сделать весьма навороченные как в сингулярити.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>4)Агенты слишком куцое решение. WH>По хорошему нужно сделать каналы. WH>А на каналах агенты делаются одной левой. WH>Причем можно сделать весьма навороченные как в сингулярити.
Всегда надо знать кода нужно остановиться. А то нафантазировать можно столько, что за всю жизнь не разгребешь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Я добавил в сниппеты FSharpAsync. Там билдер fsasync для Nemerle, написанный на F#. Это обертка вокруг тамошнего async workflow. Накладной расход в том, что постоянно вызывается метод Delay самого первоначального async. Чтобы полноценно использовать fsasync, нужны асинхронные extensions для типов вроде FileStream.
Здравствуйте, VladD2, Вы писали:
VD>Это возможность другим макросам сгенерировать код обработчиков исключений. В общем случае нужно просто давать сгенерировать код и потом обрабатывать сгенерированный код.
Увы, это входит в противоречие с идеологией однопроходного и достаточно примитивного макроса comp. Хотя есть одно решение. Можно волюнтаристски трактовать такие обработчики try как монадические. Тогда можно сделать через отложенный макрос. Оборотная сторона в том, что может потребоваться метод Zero у билдера там, где можно было бы обойтись и без него.
D>>Остается только неясность с FakeVoid (в F# для инстанцирования генериков по как бы void используется класс Unit, поддерживаемый на уровне компилятора).
VD>Можно внести в стандартную библиотеку: VD>
VD>public struct unit { }
VD>
VD>может быть еще попытаться добавить неявные приведения типов от void к unit и обратно.
Вообще-то, такие приведения должен отрабатывать сам компилятор. Пока неясно, можно ли ограничиться одной перегрузкой. Но получается не так красиво, потому что при создании билдера нужно учитывать тип FakeVoid. И сейчас нельзя писать return (), нужно — return FakeVoid.Value. Но по идее в обычном коде такие выражения не должны встречаться.
Здравствуйте, VladD2, Вы писали:
VD>Да, не плохо! Но и у ComputationExpressions тоже своих ограничений хватает. Главное из которых — это замкнутый подъязык. Те же макросы в нем не будут работать.
Если внутри макросов не используются defcomp, return, returncomp, call и callcomp, то легко! Макросы будут оставлены как есть.
Здравствуйте, VladD2, Вы писали:
VD>Как я понимаю, монады по своей сути — это CPS-продолжения.
Я заранее извиняюсь за оффтоп, но это действительно удивительный факт — такая простая вещь оказывается настолько непонятой. Да, я опять о монадах.
Вопрос, ты знаешь, что такое моноид (ассоциативная операция)? На всякий случай напомню. Это операция, для которой верно следующее
(a + b) + c = a + (b + c)
Что такое функтор тебе известно. Я о преобразовании Fun<A,B> в Fun<T<A>, T<B>>, сохраняющем структуру. Пример — дерево в точно такое же дерево, но значения каким-то образом преобразованы (возведены в квадрат, сериализованы в строку, выплачена премия).
Так вот, монада — это моноид над функторами. Всё. Моноид над функторами.
Есть ассоциативная операция над списками (конкатенация), значит список — монада. Есть ассоциативная операция над императивом (точка с запятой из сишных языков) — значит императив — монада. Есть ассоциативная операция над продолжением (последующий вызов), значит продолжения — монада. Т.к. функторов везде полно (большинство типов T<A> являются функторами — как контейнеры, так и оболочки над функциями) и т.к. ассоциативных операций ещё больше, то неудивительно, что мы постоянно натыкаемся на монады.
Вопрос, в тех реализациях интерфейса linq, с которыми ты знаком результат
x.SelectMany(y => f(y).SelectMany(g)
эквивалентен
x.SelectMany(f).SelectMany(g)
?
Если да, то это тоже монада. Можно её видеть, можно не видеть, от этого она монадой быть не перестанет.
Здравствуйте, lomeo, Вы писали:
L>Я заранее извиняюсь за оффтоп, но это действительно удивительный факт — такая простая вещь оказывается настолько непонятой. Да, я опять о монадах.
Какие люди в нашей деревне!
Привет!
L>...Так вот, монада — это моноид над функторами. Всё. Моноид над функторами.
Проблема в том, что в языках которые мы тут обсуждаем (Немерле и возможно Шарп) просто нет понятий "функтор". Так что их пользователям твои рассказы просто разрывают мозг. Пусть те кто считает себя C#-программистом и кому эти рассказы не рвут мозг кинет в меня камень (путем установки минуса, плиз, а не явно).
L>Есть ассоциативная операция над списками (конкатенация), значит список — монада.
Значит если мы не добавим с наш список SelectMany, то мы имеем дел с простым списком?
L>Есть ассоциативная операция над императивом (точка с запятой из сишных языков) — значит императив — монада.
А если язык не ленивый по умолчанию, и точка запятой и так позволяет выполнить два выражения последовательно?
L> Есть ассоциативная операция над продолжением (последующий вызов), значит продолжения — монада.
А можно так: Есть передача в качестве параметра функции которая продолжит вычисление, значит монада — это продолжение?
Или тут важна ассоциативность?
L>Т.к. функторов везде полно (большинство типов T<A> являются функторами — как контейнеры, так и оболочки над функциями) и т.к. ассоциативных операций ещё больше, то неудивительно, что мы постоянно натыкаемся на монады.
Давай уточним кто такие "мы". А то аналогия со звездочетами становится зловеще правдоподобной.
Мне кажется, что монады есть только там где а) есть факт связи двух вычислений по средствам функций, б) человек использующий это дело понимает что пользуется именно этим инструментом, а не отталкивается от какой-то другой теории (например, что он тупо выпрямляет дерево или вложенные списки в плоский список). Согласен?
L>Вопрос, в тех реализациях интерфейса linq, с которыми ты знаком результат L>
L>x.SelectMany(y => f(y).SelectMany(g)
L>
L>эквивалентен L>
L>x.SelectMany(f).SelectMany(g)
L>
L>?
L>Если да, то это тоже монада. Можно её видеть, можно не видеть, от этого она монадой быть не перестанет.
L>Попытка удалась?
Ну, как сказать. Разглядеть монаду (при желании) в SelectMany я мог и раньше. Точнее разглядеть я мог сигнатуру бинда. Но вот убей меня я не могу понять зачем приплетать монады туда где от их (логического) использования нет никакого смысла.
В прочем, с философской точки зрения попытка хорошая. Просто мы совершенно разные люди. Тебе видимо чужд не научный метод определения пола кошаков (бросил... побежала — кошка, побежал — кот) .
ЗЫ
Кстати, ты как специаилст в области монад и другой нечисти, не мог бы нам объяснить, что "мощнее" полноценное (не ограниченное) продолжение или монада.
Ну, в смысле отвата на два вопроса:
1. Можно ли выразить любую монаду продолжением?
2. Можно ли выразить любое продолжение монадой?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Да... и за одно ответь, плиз, на вопрос. Что проще (и вообще реалистично ли это?) сделать сериализуемое ComputationExpressions или реализовать продолжение (ограниченное рамками одного класса) путем переписывания кода таким образом, чтобы он складывал параметры вызовов в списки, а не в стек?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Сорри за неоперативность, времени не было ответить! И ещё раз сорри — получилось длинно.
VD>Какие люди в нашей деревне! VD>Привет!
Я иногда читаю этот форум, тут пишут много интересного
L>>...Так вот, монада — это моноид над функторами. Всё. Моноид над функторами. VD>Проблема в том, что в языках которые мы тут обсуждаем (Немерле и возможно Шарп) просто нет понятий "функтор". Так что их пользователям твои рассказы просто разрывают мозг. Пусть те кто считает себя C#-программистом и кому эти рассказы не рвут мозг кинет в меня камень (путем установки минуса, плиз, а не явно).
Упс. Я действительно думал, что функтор (он же отображение — map) — вещь, хорошо знакомая.
L>>Есть ассоциативная операция над списками (конкатенация), значит список — монада. VD>Значит если мы не добавим с наш список SelectMany, то мы имеем дел с простым списком?
Если у этого списка нет операций map и concat, то да. Тут прикол в чём. Монада — это не тип данных, это операции над типом данных. Проще объяснить, наверное на моноиде (ассоциативная операция). Вот есть тип "целое число". Моноидом над ним будет операция сложения. Или операция умножения. Или сумма по модулю N. Т.е. тип не определяет какие операции будут над ним производиться. Это операции могут быть ассоциативными или нет.
L>>Есть ассоциативная операция над императивом (точка с запятой из сишных языков) — значит императив — монада. VD>А если язык не ленивый по умолчанию, и точка запятой и так позволяет выполнить два выражения последовательно?
К сожалению, как только мы начинаем говорить о таких языках, то видим, что действия (statements) у него не first-class values. А значит смысла говорить о (a;b);c ~ a;(b;c) нет, т.к. скобки определены только над выражениями (expressions). Во-вторых, действия в таких языках не есть функтор. Мы не можем взять какое-то действие и отобразить его в другое. Т.е. дело тут не в ленивости. В конце-концов делают же монады на неленивых языках.
L>> Есть ассоциативная операция над продолжением (последующий вызов), значит продолжения — монада. VD>А можно так: Есть передача в качестве параметра функции которая продолжит вычисление, значит монада — это продолжение?
Да. Но тут такой момент. bind — сложная операция для понимания. Гораздо проще грокнуть именно join — это и есть ассоциативная операция. А уж одно через другое выражается легко.
Вот, что такое продолжение? По сути, это функция, которая принимает функцию (функция-параметр) и ей передаёт некий результат своего вычисления, а возвращает уже результат применения этой функции-параметра. И вот тут важно увидеть, что продолжение оборачивает то по сути своё возвращаемое значение, а не результат функции-параметра.
Fun<A,R> — это функция с параметром типа A и результатом типа R.
Можем мы над ней определить отображение (Map, функтор)? Во-первых, что на что мы будем отображать? Т.к. мы выяснили, что продолжение оборачивает своё возвращаемое значение, значит сигнатура будет такой
class Cont[R,A] {
Map[B](fun: Fun[A,B]): Cont[R,B] { ... }
}
Вывести его тело легко (оно выводится автоматически, на самом деле — Carry-Howard в действии)
class Cont[R,A] {
Map[B](fun: Fun[A,B]): Cont[R,B] {
return new Cont(k => this.cont(x => k(fun(x))));
}
}
Итак! Мы поимели функтор! Теперь нам надо определить ассоциативную операцию, для связывания продолжений в цепочку (иначе нафиг они нам сдались!). Не зная о монадах сделать это как минимум тяжело. Зная — тоже тяжело Но нам поможет знание одной очень полезной штуки.
Оказывается, что над монадами проще определять не Bind, а Join, а уже через него Bind выражается очень легко. Join — это операция с типом
Join(m: Cont[Cont[A]]): Cont[A]
т.е. уплощяем (flat) некий функтор. Bind через Join определяется так:
cont.Bind(f) == Join(cont.Map(f))
Немного математики (нет необходимости читать): Join как раз и выражает моноид над функтором, который мы определили выше. Вспоминаем: моноид — это ассоциативная операция. функтор — (утрировано) тип, оборачивающий некий тип. Моноид над функторами будет операцией над типами. Т.е. есть функтор SomeFunctor[T], есть операция TypeMonoid[F] ~ F[F[T]]. Тут можно увидеть, что Join и представляет такую операцию.
Вернёмся к продолжениям. Join должен брать продолжение, определённое над продолжением (!) над неким значением и возвращать продолжение над этим значением. Я сразу напишу тип и реализацию. Могу где и налажать, особенно с синтаксисом. т.к. не знаком.
class Cont[R,A] {
static Join[R,A](c: Cont[R,Cont[R,A]]): Cont[R,A] {
return new Cont(x => c.cont(k => k.cont(x)));
}
}
Ну тут из типа видно, что мы хотим сделать. Смысл простой, мы flat-им продолжение, превращая его в понятное. Вот так, лёгким движением руки, зная о монадах и выведя тип самого Cont, мы получили продолжения, с которыми можем работать в общем для монад стиле — связывая их в цепочку.
VD>Или тут важна ассоциативность?
Да. Ассоциативность над функторами. Т.е. определяем две операции (на самом деле три, но третья — return уж очень простая) — отображение (функтор) и какую-нибудь ассоциативную операцию над этим функтором — это и есть монада, а не сам тип.
L>>Т.к. функторов везде полно (большинство типов T<A> являются функторами — как контейнеры, так и оболочки над функциями) и т.к. ассоциативных операций ещё больше, то неудивительно, что мы постоянно натыкаемся на монады.
VD>Давай уточним кто такие "мы". А то аналогия со звездочетами становится зловеще правдоподобной.
Увы, ты прав, после того, что я написал выше, я понял, что не всё так просто, бэкграунд действительно нужен. Но совсем небольшой.
VD>Мне кажется, что монады есть только там где а) есть факт связи двух вычислений по средствам функций, б) человек использующий это дело понимает что пользуется именно этим инструментом, а не отталкивается от какой-то другой теории (например, что он тупо выпрямляет дерево или вложенные списки в плоский список). Согласен?
а) есть жёсткое определение — имеем функтор (т.е. операцию Map), имеем ассоциативную операцию над ним (Join) — всё, есть монада. То что ты написал — скорее следствие, не всегда верное. Пример, есть два вычисления (1 + 2) и (3 + 4) мы связываем их посредством функции (+) — это монада? Нет. С другой стороны — дерево мы можем отобразить на дерево, сохранив структуру; из дерева деревьев можем сделать дерево значений, значит это монада.
б) "Слышен ли звук падения дерева в лесу, в котором нет наблюдателя?". Наверное, согласен, нет смысла от того, что там есть монада. Но мы так до философии математики доберёмся
L>>Попытка удалась? VD>Ну, как сказать. Разглядеть монаду (при желании) в SelectMany я мог и раньше. Точнее разглядеть я мог сигнатуру бинда. Но вот убей меня я не могу понять зачем приплетать монады туда где от их (логического) использования нет никакого смысла.
Если нет пользы, то приплетать не надо! Я то говорю о пользе. На удивление такой ну совершенно абстрактный инструмент оказался очень практичным. Монада хорошо ложится на list/query/monad comprehension ().
for y in x for z in y if z > 0 select sin(z)
это выражение похожее на определение множества
{ sin(z) | y ∈ x ; z ∈ y ; z > 0 }
замечательно обобщается до монадического bind, на котором и строится linq.
Зная законы монад/функторов ты можешь формальнее (а значит, корректнее) рассуждать о любой кошерной реализации linq.
Замены (equational reasoning — один из самых полезных инструментов практика, любой нормальный рефакторинг строится на нём)
from x in xs select x на xs.
from x in xs select f(x) на xs.Map(x).
from x in xs from y in foo(x) select y на xs.SelectMany(foo)
и т.д.
Задействовать свои комбинаторы, которые работают для любых реализаций linq (абстракция!) например
Map2, Map3 — схожий с обычным Map, но для нескольких контейнеров
from x in xs from y in ys select foo(x,y) на Map2(xs, ys)(foo)
Тот же Join, который оказывается полезным в самых неожиданных местах.
Зная о монадах мы можем предположить, что проблема, для которой мы сейчас ищем решение может быть решена в рамках linq
А это (нагло цитирую Last Cjow Rhrr и себя)
Продолжения
Обработка исключений
ГУИ
Логгинг
Коммуникации между процессами
Парсеры
Интерпретаторы
Энергичное исполнение кода
Интерфейс к коду на других языках (FFI)
Бэктрекинг
Логика
STM
Multiresult
optional result
случайные значения
недетерминированность
да и самому можно толпу придумать — например, упорядочивание результатов, или для моделирования устройств — вычисления с тактами, ну и т.д.
Многое из этого не нужно в рамках C#, но что-то ведь может и пригодится. Если какое-то знание позволит тебе увидеть одно из решений, возможно лучшее, то зачем лишать себя его?
VD>В прочем, с философской точки зрения попытка хорошая. Просто мы совершенно разные люди. Тебе видимо чужд не научный метод определения пола кошаков (бросил... побежала — кошка, побежал — кот) .
Честно говоря, я просто вижу как много практичности в математике и как она помогает мне писать программы. Я стал по другому подходить к решению задач, стал лучше рассуждать о коде. Ну, или мне так кажется
VD>ЗЫ VD>Кстати, ты как специаилст в области монад и другой нечисти, не мог бы нам объяснить, что "мощнее" полноценное (не ограниченное) продолжение или монада.
VD>Ну, в смысле отвата на два вопроса: VD>1. Можно ли выразить любую монаду продолжением?
Интуитивно не вижу к этому препятствий, как-то в "Декларативном Программировании" мы с palm_mute шалили
Здравствуйте, VladD2, Вы писали:
VD>Да... и за одно ответь, плиз, на вопрос. Что проще (и вообще реалистично ли это?) сделать сериализуемое ComputationExpressions или реализовать продолжение (ограниченное рамками одного класса) путем переписывания кода таким образом, чтобы он складывал параметры вызовов в списки, а не в стек?
Ой, я не специалист. Сначала почитаю про то, что такое ComputationExpressions.
Здравствуйте, VladD2, Вы писали:
L>>Ой, я не специалист. Сначала почитаю про то, что такое ComputationExpressions. VD>Монады переименованные для того чтобы не пугать гражданских и которым придан эдакий красивый синтаксис для языка не являющегося хаскелм.
Прочитал (про F#) — это же один-в-один do-нотация. Если это та самая штука, то вопрос всё равно я не понял
Здравствуйте, VladD2, Вы писали:
VD> сделать сериализуемое ComputationExpressions
Я тут покопался рефлектором. Оказывается, что компилятор F# генерирует функции (и замыкания ??) по возможности с атрибутом [Serializable] на уровне IL. Это означает, что во многих случаях можно попытаться сериализовать продолжение. То есть, всю последующую цепочку вычислений. И обернуть это в симпатичные computation expressions.
. Если программа запустилась с первого раза, ищите ошибку в компиляторе (с)
использование int когда есть TimeSpan диверсия.
