Здравствуйте, Gaperton, Вы писали:
Q>>yeild return != continuations. И я не слышал о реализациях через стек. G>Ок, объясни разницу.
yield неявно создает продолжение только для текущей функции, а не для программы в целом. И мы не можем ничего сделать со стеком. Если язык поддерживает продолжения или позволяет легко писать в CPS стиле, то проблемы стека нет, но C# не такой.
В С# мы можем написать, например, следующий код:
let a = choose_from list1 in
let b = choose_from list2 in
if a = b then a else fail ();;
Где choose_from возвращает по элементу из списка (сохраняя продолжения), а fail вызывает последнее сохраненное продолжение. Но не сможем такой:
let do_something x =
if x = 3 then true else fail ();;
let x = choose_from list in
do_something x;;
Или еще хуже, когда мы обнаруживаем, что элемент не тот вообще в другом месте программы
Здравствуйте, Quintanar, Вы писали:
Q>Здравствуйте, Курилка, Вы писали:
Q>>>Точно не так же гладко. Например, ни одна библиотека не позволит работать с продолжениями также гладко, как это позволяет Scheme. Даже в Lisp, самом гибком языке, соответствующая библиотека имеет существенные ограничения.
К>>А вот тут можно чуть подробнее?
Q>Про Лисп: Q>Если происходит CPS преобразование программы (есть такая библиотека), то нельзя пользоваться в call-with-current-continuation некоторыми специальными формами (типа обработки исключений, вроде). Если же используется полуавтоматическое преобразование как у Грехема, то все функции должны удовлетворять довольно жестким условиям. В частности, любой путь исполнения должен заканчиваться или вызовом другой аналогичной функции или специальным макросом возврата результата + еще кое что. Это можно посмотреть в его книге.
Здравствуйте, Gaperton, Вы писали:
G>Ну раз ты это говоришь, то имеет смысл разобраться поподробнее, что такое continuations .
Имхо — извращение, ещё большее, чем монады .
Здравствуйте, Трурль, Вы писали:
Т>Здравствуйте, Gaperton, Вы писали:
G>>Ну раз ты это говоришь, то имеет смысл разобраться поподробнее, что такое continuations . Т>Имхо — извращение, ещё большее, чем монады .
Не согласен. Во-первых, продолжения существенно проще для понимания, во-вторых, в некоторых задачах они очень удобны. Например, при обходе какой-нибудь сложной структуры, как тут уже говорили.
Здравствуйте, Quintanar, Вы писали:
Q>Здравствуйте, Gaperton, Вы писали:
Q>>>Совсем необязательно, чтобы вызов каждой функции обязательно шел через стек. На ФЯ можно написать большую программу, которая вообще не будет использовать стек для вызова функций. Если все функции хвостово-рекурсивные, компилятор проведет оптимизацию и вызов функций будет выглядеть как jump. G>>Не совсем так. Обычно виртуальная машина поддерживает хвостовую рекурсию именно как вызов функции, т. е. она не переводится в jump. Стеком нельзя не пользоваться, на нем выделяются локальные переменные. Кстати, мне точно известно, что дотнетовская виртуальная машина Mono тоже поддерживает хвостовую рекурсию.
Q>Я приводил в Декларативном Программировании пример программы на OCaml с использованием continuations. Это была простая операционная система. Все функции были хвостово-рекурсивными и для проверки я запустил тест на переключение двух задач огромное количество раз. Поскольку память не расходовалась вообще, я сделал вывод, что стек не используется и все вызовы функций преобразованы в прямые переходы.
Память не расходуется, это так, но стек используется (для аллокации локальных переменных). Просто при "хвостовом" вызове вместо создания нового стек-фрейма переиспользуется фрейм последнего вызова — так проще.
Если применяется виртуальная машина — то обычно делают специальную поддержку для хвостовой рекурсии на уровне команд виртуальной машины. При компиляции в машинный код в некоторых местах возможны оптимизации посредством замены на прямые переходы.
Здравствуйте, Quintanar, Вы писали:
Q>Не согласен. Во-первых, продолжения существенно проще для понимания, во-вторых, в некоторых задачах они очень удобны.
Глобальный goto еще проще для понимания и тоже очень удобен в некоторых задачах.
Хотя собсвенно против продолжений ничего не имею, но где-нибудь глубоко в библиотеках, или в макросах, или в промежуточном коде.
Здравствуйте, Трурль, Вы писали:
Т>Глобальный goto еще проще для понимания и тоже очень удобен в некоторых задачах. Т>Хотя собсвенно против продолжений ничего не имею, но где-нибудь глубоко в библиотеках, или в макросах, или в промежуточном коде.
Да, это верно, хотя сравнение все-таки не совсем точное. Продолжения могут привести к очень запутанному коду, с этим не поспоришь.
Здравствуйте, Quintanar, Вы писали:
Q>Здравствуйте, Gaperton, Вы писали:
Q>>>yeild return != continuations. И я не слышал о реализациях через стек. G>>Ок, объясни разницу.
Q>yield неявно создает продолжение только для текущей функции, а не для программы в целом. И мы не можем ничего сделать со стеком. Если язык поддерживает продолжения или позволяет легко писать в CPS стиле, то проблемы стека нет, но C# не такой.
То есть, разница только в том, что в C# continuation не является first-class object, т.е.
1) нельзя явно создать continuation и
2) явно передать его в функцию параметром (всегда происходит возврат только в вызывающий continuation).
В результате continuation passing style применять невозможно. Я правильно понимаю?
Здравствуйте, Трурль, Вы писали:
Т>Здравствуйте, Gaperton, Вы писали:
G>>Ну раз ты это говоришь, то имеет смысл разобраться поподробнее, что такое continuations . Т>Имхо — извращение, ещё большее, чем монады .
Здравствуйте, Gaperton, Вы писали:
G>То есть, разница только в том, что в C# continuation не является first-class object, т.е. G>1) нельзя явно создать continuation и G>2) явно передать его в функцию параметром (всегда происходит возврат только в вызывающий continuation). G>В результате continuation passing style применять невозможно. Я правильно понимаю?
CPS — это, насколько я понимаю, нечто типа объектно-ориентированного стиля. Некоторые языки поддерживают его с рождения, в некоторых его можно в какой-то степени имитировать. В C# с ним очень плохо, поскольку невозможно красиво эмулировать функции без возврата, сильно мешает стек. В ФЯ с этим легче за счет того, что 1) функции гораздо короче и меньше проблем с их CPS-изацией 2) можно использовать хвостовую оптимизацию и 3) лексические замыкания помогают легко запомнить локальное состояние.
Т.е. писать в CPS на C# можно, но нет никакого смысла с точки зрения понятности программы и быстроты разработки. Можно как в статье применять его в ограниченных пределах и все.
Gaperton пишет: > Q>>>yeild return != continuations. И я не слышал о реализациях через стек. > G>>Ок, объясни разницу. > > Q>yield неявно создает продолжение только для текущей функции, а не для > программы в целом. И мы не можем ничего сделать со стеком. Если язык > поддерживает продолжения или позволяет легко писать в CPS стиле, то > проблемы стека нет, но C# не такой. > То есть, разница *только *в том, что в C# continuation не является > first-class object, т.е. > 1) нельзя явно создать continuation и > 2) явно передать его в функцию параметром (всегда происходит возврат > только в вызывающий continuation). > > В результате continuation passing style применять невозможно. Я > правильно понимаю?
Здравствуйте, Quintanar, Вы писали:
Q>Здравствуйте, Gaperton, Вы писали:
G>>То есть, разница только в том, что в C# continuation не является first-class object, т.е. G>>1) нельзя явно создать continuation и G>>2) явно передать его в функцию параметром (всегда происходит возврат только в вызывающий continuation).
Q>Т.е. писать в CPS на C# можно, но нет никакого смысла с точки зрения понятности программы и быстроты разработки. Можно как в статье применять его в ограниченных пределах и все.
Ладно, CPS — это в конце концов вторично. Подтвердите или опровергните изначальные тезисы 1 и 2 (когда я говорю о continuation в С# я имею в виду yield return). Вы согласны с ними?
Здравствуйте, stalcer, Вы писали:
К>>...в шарпе создаётся объект, хранящий этот самый контекст...
S>Вот в этом-то я сильно сомневаюсь . Скорее всего локальные переменные все таки хранятся в стеке.
Нет ничего проще чем проверить на практике. Вот реализация итератора из примера:
[CompilerGenerated]
private sealed class _Power_d__0 : IEnumerator<object>, IEnumerator, IDisposable
{
private int _1__state;
private object _2__current;
public int _counter_5__1;
public int _result_5__2;
public int exponent;
public int number;
public _Power_d__0(int _1__state)
{
this._1__state = _1__state;
}
private bool MoveNext()
{
switch (_1__state)
{
case 0:
_1__state = -1;
_counter_5__1 = 0;
_result_5__2 = 1;
break;
case 1:
_1__state = -1;
break;
default:
return false;
}
if (_counter_5__1++ < exponent)
{
_result_5__2 *= number;
_2__current = _result_5__2;
_1__state = 1;
return true;
}
return false;
}
void IEnumerator.Reset()
{
throw new NotSupportedException();
}
void IDisposable.Dispose(){}
object IEnumerator<object>.Current
{
get { return _2__current; }
}
object IEnumerator.Current
{
get { return _2__current; }
}
}
Здравствуйте, Serginio1, Вы писали:
S> А нука покажи рекурсивный обход на FW 2.
Вот, на скорую руку накидал. Вроде работает.
using System;
using System.Collections;
using System.Collections.Generic;
public class Node
{
private readonly string _name;
private readonly List<Node> _children;
public Node(string name, params Node[] children)
{
_name = name;
_children = new List<Node>(children);
}
public override string ToString()
{
return _name;
}
public IEnumerable EnumerateRecursively()
{
yield return this;
foreach (Node c in _children)
foreach (Node cc in c.EnumerateRecursively())
yield return cc;
}
}
public class Test
{
static void Main()
{
Node root = new Node("1",
new Node("11",
new Node("111",
new Node("1111")),
new Node("112"),
new Node("113",
new Node("1131",
new Node("11311",
new Node("113111",
new Node("1131111"),
new Node("1131112",
new Node("11311121")),
new Node("1131113")))))),
new Node("12"),
new Node("13"));
foreach (Node node in root.EnumerateRecursively())
Console.WriteLine(node);
}
}
Файберы — рулят, ни разу не глючны, на портабельность плевать — будут проблемы и похуже при попытке портировать нечно с Win32 (хотя аналоги есть и в Unix под названием user-level threads), развиваться там нечему — все крайне просто (весь API — вызовов 6), и даже если бы не было файберов в API, их можно было бы написать ручками на asm-е.
И разумеется, файберы дают массу преимуществ при грамотном использовании. Применение файберов в рамках legacy-продуктов CQG позволило нам более чем вдвое удешевить разработку и рефакторинг некоторых подсистем клиента и сервера. Про глючность — выдумки, у нас уже три года сервера на файберах крутятся, и ни одной проблемы с ними не было.
Что касательно производительности — накладные расходы на переключение файбера мизерные по сравнению и с переключением контекста потока, и с раскруткой стека при коллбэчном асинхронном стиле программирования, что позволяет применять их совершенно по другому — плодить их в большом количестве, часто переключать контексты, и т.д. Короче, файберы рулят со страшной силой.
Статья эта — отстой полный.
They're also HARD to deal with — you essentially have to write your own scheduler.
Ай-ай-ай. Как раз поэтому файберы и хороши, что можно (но совсем не обязательно) писать свой шедулер. Наш шедулер занимает 468 строк на С++. Пишется за пару недель. И он очень хорош, просто великолепен. Управляется с приоритетами так, как нужно нам, а не оперсистеме, и работает нормально на том количестве параллельных активностей, которая удобна нам, а не разработчикам ядра. Нам, например, удобно, чтобы их было порядка 10К, а не идиотская сотня с идиотскими пулами.
Далее, я написал очень много файберного кода, и как врач говорю, что в нем существенно реже возникают проблемы синхронизации даже при использовании той же самой модели разделяемых данных. Файбер не может прерваться в любой момент, вы сами говорите ему — где, что сильно уменьшает как количество примитивов синхронизации в вашей программе, так и упрощает доказательство корректности программ. Файберный код — более надежен, чем потоковый, его проще писать, и его проще отлаживать.
Второй момент — на файберах удобно реализовывать сопрограммы и continuations. Что не требует планировщика — автор очевидно этот случай вообще не рассматривает. Афтарлох, короче.
The other reason that fibers have remained obscure is more fundamental. It has to do with Moore's law (there's a reason for the posts yesterday and the day before).
Ну-ну. Закон Мура что-то не помогает виндам чувствовать себя нормально хотя-бы с 1К потоков на процесс — я уже не говорю о большом количестве активно взаимодействующих потоков, которые часто переключаются и жрут мало CPU на обработку одной мессаги. То есть в том сценарии, когда мы в процентах много теряем на переключение контекста — мы продолжим терять столько же. И закон Мура ровным счетом никак не помогает.
Здравствуйте, Gaperton, Вы писали:
G>>>То есть, разница только в том, что в C# continuation не является first-class object, т.е. G>>>1) нельзя явно создать continuation и G>>>2) явно передать его в функцию параметром (всегда происходит возврат только в вызывающий continuation).
G>Ладно, CPS — это в конце концов вторично. Подтвердите или опровергните изначальные тезисы 1 и 2 (когда я говорю о continuation в С# я имею в виду yield return). Вы согласны с ними?
2) поскольку кроме yield (return | break) ничего больше нет, то мы вернемся в вызвавшую функцию. Поэтому мы не можем передать продолжение, созданное в месте вызова yield выше. Наверно, можно передать this, но все это будет некрасивым хаком.
1) Можно, но только для данной функции и при наличии больших ограничений.
Короче, мы зашли куда-то не туда. yield на нормальные продолжения похож очень слабо, нет вообще смысла их сравнивать, поскольку yield был создан для упрощения программирования итераторов и только.
.
.
Ай-ай-ай. Как раз поэтому файберы и хороши, что можно (но совсем не обязательно) писать свой шедулер. Наш шедулер занимает 468 строк на С++. Пишется за пару недель. И он очень хорош, просто великолепен. Управляется с приоритетами так, как нужно нам, а не оперсистеме, и работает нормально на том количестве параллельных активностей, которая удобна нам, а не разработчикам ядра. Нам, например, удобно, чтобы их было порядка 10К, а не идиотская сотня с идиотскими пулами.
