Нелокальные управляющие конструкции считать вредными - Философия программирования

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

С вашего позволения прокомментирую.

M>Нет. Нити не предлагают противоположный подход. Нити появляются там, где "недетерминизм реально нужен". Обработка данных на нескольких ядрах, параллельное выполнение блокирующих и неблокирующих операций (чтение данных и пользовательский UI) и т.п. А вот уже после того, как нити стали нужны, приходится бороться с недетерминизмом и всем остальным.

Нити не нужны вообще, это ошибка эволюции. Нужны легковесные процессы, как в Singularity. И там общение с дочерними процессами вполне детерминировано.

T>>* Continuations
M>Полезны в определенных случаях. Какие-нибудь data flow строить, например. Еще лучше — динамически строить тот же data flow. Вручную перекладывание данных в "процедурном стиле" из одного источника в другой будет ничуть не лучше.

Пример не покажете?

T>>* Сопрограммы
T>>* Генераторы
M>Это которые yield return? Так удобно же! Код "генератора вручную" читать и писать гораздо тяжелее, чем yield return.

Писать может и удобно, а вот читать — не уверен.

M>Да пожалуйста. Приведите аналог "нитей исполнения" в локальном и детерминированном эквиваленте. И желательно в контексте, когда в одном потоке мы читаем файл, а второй обрабатывает события пользовательского интерфейса (хотя бы только перерисовку, ладно уж).

Каналы процессов (http://www.rsdn.ru/article/singularity/singularity.xml).

M>Да. Вопрос только — какой ценой. Вот, пожалуйста, пример. Async.applySync(someFunction, [loadDataA, loadDataB, preloadImages]). Эта страшная штука применяет someFunction после того, как будут загружены данные A, B, и предзагружены картинки. Вся загрузка — асинхронная (сетевая) и параллельная. Это не совсем continuations, (параметров многовато), ну да ладно. Для усложнения ситуации там до этого вполне может быть loadDataB = Async.applyAsync(loadDataB, [loadDataA, loadDataC]), т.е. данные B загружаются после загрузки данных A и C (мало ли что там, ссылки на другие данные, например).

Эта "страшная штука" — опять те же нити. Причем тут continuation? Дайте пример без async.

M>А мы про какие контексты говорим? Для "чистых" программ — да, можно. А вот как быть, если программа с внешней средой взаимодействует? Ну там картинку из интернета загружает и ее в файл сохраняет? При этом пользователь загрузку и отменить может. Ну и OS еще во все это вмешивается снаружи. А еще мы какие-нибудь плагины добавим для обработки фотографии (подгружаемые только в рантайме). Это все компилятор сможет детерминированно отпараллелить? Или ему нужно будет подать на вход все, включая исходную операционную систему?

Для нечистых тоже можно (см. ту же Singularity). По утверждению авторов контракты каналов позволяют проверить даже наличие deadlock-ов.

M>Да нет, не только разработки. Чтения тоже (yield return читать проще, чем большой и страшный автомат).

Не спора ради, а истины для. Не приведете пример убедительного превосходства yield return?

M>Кстати, вы от OOP и наследования от интерфейсов тоже предлагаете избавится? Они же недетерминизм вносят (как только мы dependency заинжектили — все, детерминизм кончился).

Не понял, какой здесь вносится недетерминизм? Если контракты интерфейса соблюдены, то все детерминировано. Кстати, интерфейсы бывают не только в C# или Java. Eiffel или выброшенные из С++ концепты предлагают более широкие возможности — предусловия-постусловия, аксиомы.

M>И касается это в первую очередь внешнего API... Не кода, не того, что и куда там переходит. А внешнего API.

Ну уж нет. Спагетти-код никакое API не вытянет.

M>А вот здесь вы ошибаетесь. Нельзя выкинуть глобальные переменные. И никто этого не делает. Обычно их инкапсулируют во что-нибудь менее страшное.

Есть языки без глобальных переменных (Eiffel).

M>Поэтому и работать с ними приходится. А давайте мы еще пару "безопасностей" добавим — безопасность относительно освобождения ресурсов и безопасность относительно гарантии обработки всех ошибок. Тоже откажемся? А ведь освобождение ресурсов это вообще частный случай "глобальных переменных"! Т.е. мы откажемся от работы с памятью (можно попробовать на GC поменять), работы с файлами и от всего остального.

Не думаю, что взаимодействие с внешним миром стоит приравнивать к глобальным переменным. Мир — это не глобальная переменная, он меняется независимо от программы. Уйти от взаимодействия с ним обычно нельзя. А глобальные переменные просто ухудшают структуру программы, ничего не давая взамен (ну точнее они дают легкость написания неподдерживаемого быдлокода

).

M>Кстати, как вы хотите бороться с "глобальным состоянием" там, где оно существует исходя из контекста задачи? Банальный почтовый клиент возьмите. Вот пришло пользователю новое сообщение. Это глобальное или локальное состояние?

Локальное.

M>Или нам весь мир нужно перестроить (да, уже там все будет достаточно сложно, потому что событие произошло далеко внизу и придется распутывать сплетения монад друг над другом). А самое интересное, что в процессе "перестроения мира" выяснится, что пользователь подвел курсор мышки к кнопочке и у нас анимация играется уже 0.2 секунды (и осталось еще 0.4 секунды проигрывания).

Ничего не понял, зачем чего-то перестраивать.

M>Да и на экране нужно вывести что-нибудь, а это "глобальное состояние" ОС, монитора и пользователя, так что еще и все состояние OS нужно куда-нибудь передать и создать.

Это опять внешний мир, а не глобальные переменные.

M>Ну и так же, как с глобальными переменными — мы не отказываемся от них, мы их инкапсулируем.

Куда инкапсулируем, в синглтоны?

M>Исключения — замена кодам ошибок. Иногда — достаточно хорошая. Потому что иногда приходится возвращать сложную структуру. Или там long long произвольный. Как вы его на кодах ошибок вернете? Через глобальные переменные (от которых мы отказались)? Или через выделение структуры?

Через discriminated union.

M>Очевидно, что структура будет выделяться на стороне вызывающего (потому что внутри функции память может не выделиться, а код ошибки мы вернуть не можем

).

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

M>А локальные переменные (которые мутабельные) вы еще не предлагали запретить? Про них можно все те же аргументы привести, что и про глобальные переменные (только чуть в меньшем масштабе).

"Те же аргументы" можно привести только если у вас метод длиной в тысячи строк. В ином случае это малость неадекватно.

M>P.S. Исключения — это локальный переход!

Нет, не локальный, т.к. мы не знаем конечной точки.

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

"Глаголы — говно. Я презрение глаголы. Злость на людей, которые их похвала."

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

ARK>Нити не нужны вообще, это ошибка эволюции. Нужны легковесные процессы, как в Singularity. И там общение с дочерними процессами вполне детерминировано.
А как там interpocess communication реализуется? Мне в идеале хочется гонять структуры между различными частями программы (теми самыми легковесными процессами). Иногда — достаточно большие объемы. Ну вот банальщину возьмем. Игру какую-нибудь сетевую. Один поток ведет сетевой обмен. Второй поток обсчитывает механику (очевидно, должен получать сообщения от сети в удобоваримом виде). Третий поток картинку генерирует к физике. И системный процесс все это безобразие на экран выводит (double buffering в отрисовке). В зависимости от удобства API мы получим либо те же shared memory со всеми ее проблемами (buffered image передавать надо как-то), либо кучу неудобств на ровном месте. Ну или дайте ссылку на конкретный API, я посмотрю. Если что, "высокоуровневые" примитивы обмена ведь и с обычными потоками можно использовать.

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

T>>>* Continuations
ARK>Пример не покажете?

Ну... С одной стороны, это все те же yield. Это из общего соображения. cps (continuation passing style) — обработка данных. Наиболее часто — вывод мультимедиа (сбор графов на источнике/получателе данных). Я что-то подобное делал, когда данные из базы нужно было загружать, обрабатывать и выгружать. То ли база данных для lucene собиралась, то ли что-то еще. С точки зрения интерфейса чтения данных из базы, все остальное за ним — continuation...

ARK>Писать может и удобно, а вот читать — не уверен.
Удобнее, чем явный автомат. Как минимум в типичных случаях. Можно, конечно, и ужасы написать. Но от misuse никто не застрахован.

ARK>Каналы процессов (http://www.rsdn.ru/article/singularity/singularity.xml).
Ок. Хорошо. Мы можем в некоторых местах перейти на каналы. Если эффективность нас не особо волнует, наверное, мы много чего сможем на них сделать. В голову вроде бы ничего не приходит невозможного. Остается вопрос эффективности. Например, у нас 10 игроков. Мы генерируем уникальные идентификаторы каких-то сообщений (того же чата, например, только не спрашивайте, зачем мы это делаем...). Я правильно понимаю, что без отсутствия shared state мы у специального процесса будем запрашивать генерацию и ожидать ответ на канале?

Собственно, все это можно делать уже и сейчас. Есть же очереди сообщений. Да, у нас не легковесные процессы, у нас потоки. Но примитивы те же самые (блокирующие типизированные очереди). Но вот ведь беда, иногда требуется эффективность выше. Начиная от простейщего incrementAndGet и заканчивая сложными мутабельными структурами (вроде nonblocking list/nonblocking map). Ведь не от хорошей же жизни всем этим пользуются... А где можно не пользоваться сложными структурами (и обеспечивать необходимую безопасность), ими и не пользуются.

M>>Async.applySync(someFunction, [loadDataA, loadDataB, preloadImages]).
ARK>Эта "страшная штука" — опять те же нити. Причем тут continuation? Дайте пример без async.
Вот в данном то конкретном случае нитей там и не было

Это полностью однопоточный код (и вообще там в рантайме поддержки потоков нет!). Где-то на верхнем уровне он вырождатеся в тот самый цикл на сообщениях:

while (true) {
  case (waitForNextMessage()) {
    case WM_RENDER:
      fireNextFrameListeners();
      renderNextFrame();
    case WM_NET_EVENT(e):
      var netQueue = findNetQueue(e.queueId);
      netQueue.appendData(e.data);
      ...
    case WM_MOUSE_EVENT(e):
      ...
  }
}

Собственно, async он далеко не потому, что выполняется в другом потоке. Async он потому, что актуальная функция (someFunction) выполняется уже после того (в общем случае), как выполнилась Async.applySync (и вооще через несколько итераций цикла обработки сообщений). someFunction — типичная continuation (она и методом объекта может быть, и всем остальным). Выполняется "по завершению" loadDataA, loadDataB, preloadImages.

Да в общем, это и не важно. Как бы вы подобный код написали в однопоточном виде? Ну пусть через те же каналы. В некоторых случаях — через waitForMultipleObjects. Только не везде можно было бы обойтись этим (все равно и каналы новые нужно создавать, и запросы отправлять). Да, я писал вначале "ручные" автоматы (if loadState == ... и if loadedCount == ...). Когда переписал на continuations + async, вздохнул с огромным облегчением.

Типичный метод:

public function doSomething(app, arg1, arg2) : OperationState<Void> {
  var dataA = loadSomethingVeryAsync(arg1);
  var dataB = loadSomethingOverAsync(arg2);
  var preloadedImages = Async.applyAsync(preloadImagesForData, [dataA]);
  var externalData = Async.applyAsync(loadDataFromExternalSystem, [dataB, arg2]);
  var appUI = Async.applySync(createUI, [app, dataA,  extenralData, preloadedImages]);
  return Async.applySync(app.addDialog, [appUI]);
}

Практически все методы грузят данные, строят какой-то UI и потом выводят его. На событиях было бы одно выходное (когда все готово) в app.addDialog (или соответствующем событии). При такой структуре методов вопросов не возникает. Пример, переписанный в "машину состояний на событиях" превращаяется в страх и ужас. Конечно, эта машина состояний где-то все-равно существует, только хорошо инкапсулирована.

И еще. Обратите внимание на уровень декларативности кода. Ему совершенно без разницы, на потоках происходит вся асинхронность или "в цикле на событиях"! Еще оно прозрачно и ошибки возвращает (ну правда, не вручную же на каждом канале проверять, успешно все закончилось или нет). А все — на continuation (потому что addDialog, createUI, loadDataFromExternalSystem — это некое continuation в самом широком смысле слова).

ARK>Для нечистых тоже можно (см. ту же Singularity). По утверждению авторов контракты каналов позволяют проверить даже наличие deadlock-ов.
Так там же нет "детерминированного параллелизма"! Там вполне себе недетерминированный параллелизм и обработка очереди сообщений. Будет ли там в очередь посылать поток или процесс, не слишком важно. Важно наличие "недетерминизма". ОП вообще говорил про параллелизм в стиле MPI. Тот параллелизм вообще в основном для обработки больших-больших матриц предназначен.

Отсутствие deadlock — это хорошо (без иронии). Может ли singularity гарантировать, что обработчик сообщений справится со всем потоком (т.е. очередь не будет расти бесконечно)? Вопрос серьезный. Например, для "автоматического парралелизма в стиле MPI" это чисто теоретически можно доказать. А иначе опять руками все доказывать...

И еще раз замечу, что моему коду выше (на continuation passing в async комбинатор) никакого дела до физической реализации асинков нет. Могу на процессы переписать, могу на каналы. И для каналов таки напишу аналог, если придется (потому что короче, чем на автоматах врукопашную).

ARK>Не спора ради, а истины для. Не приведете пример убедительного превосходства yield return?
Ну что-то вроде:

def listInTree(curNode, pred):
  if pred(curNode):
    yield return curNode
  else:
    for sub in curNode.children():
      for res in listInTree(sub, pred)
         yield return res

Можно еще всякие графы более сложные обходить, например. Но это так, навскидку. Я на языки с yield return совсем недавно освоил, поэтому ничего сильно лучше под рукой нет.

M>>Кстати, вы от OOP и наследования от интерфейсов тоже предлагаете избавится? Они же недетерминизм вносят (как только мы dependency заинжектили — все, детерминизм кончился).
ARK>Не понял, какой здесь вносится недетерминизм?
Ну как... В вашем же определении "Нет, не локальный, т.к. мы не знаем конечной точки." А конечной точки мы не знаем

ARK>Если контракты интерфейса соблюдены, то все детерминировано. Кстати, интерфейсы бывают не только в C# или Java. Eiffel или выброшенные из С++ концепты предлагают более широкие возможности — предусловия-постусловия, аксиомы.

Очень хорошо. А кто в этих случаях аксиомы доказывает? Пользователь или компилятор? Но даже это не важно. Вот объясните мне, почему мы можем проверить "контракты соблюдены", а "метод выбрасывает только исключения из списка ..." не можем? А если можем проверить "список исключений", то какие тогда вообще проблемы? Исключение — это не переход. Исключение — это результат работы метода! Монада такая. Все, после этого мы все, что угодно, можем доказывать.

M>>А вот здесь вы ошибаетесь. Нельзя выкинуть глобальные переменные. И никто этого не делает. Обычно их инкапсулируют во что-нибудь менее страшное.
ARK>Есть языки без глобальных переменных (Eiffel).
Это вряд ли. Переменная в замыкании примерно такая же глобальная переменная, как и все остальные. То, о чем говорил ТС, это "глобальные переменные, доступные откуда угодно". Да, эту проблему решает инкапсуляция. Только вот тоже плохо решает — все зависит от дисциплины программиста. Если я захочу, то инстанс (замыкание/класс/объект) я тоже по всей программе протащу. Собственно, вопрос здесь только в инкапсуляции и дисциплине доступа.

ARK>Не думаю, что взаимодействие с внешним миром стоит приравнивать к глобальным переменным. Мир — это не глобальная переменная, он меняется независимо от программы. Уйти от взаимодействия с ним обычно нельзя. А глобальные переменные просто ухудшают структуру программы, ничего не давая взамен (ну точнее они дают легкость написания неподдерживаемого быдлокода

).

Стоит, стоит мир рассматривать как глобальную переменную. Ведь можно в файлик записать в одном месте программы а потом в другом месте попробовать считать. Да, конечно, мир еще менее детерминированный, чем глобальные переменные, ну так и что?

Лирическое отступление по внешнему миру. Одно время (еще студентом) будучи студентами мы как-то попрбовали зареверсить msgina.dll (за аутентификацию пользователей отвечает). Хотели посмотреть на сообщение "logout denied" (да, logout, оказывается, может не сработать!). И вот там в процедуре входа пользователя в систему был поразительный фрагмент. Он читал число из реестра и пытался вызвать по этому адресу процедуру! Может, конечно, мы это отреверсили неправильно, но мораль такая — мир нельзя исключать из рассмотрения (за исключением специальных случаев).

M>>Кстати, как вы хотите бороться с "глобальным состоянием" там, где оно существует исходя из контекста задачи? Банальный почтовый клиент возьмите. Вот пришло пользователю новое сообщение. Это глобальное или локальное состояние?
ARK>Локальное.
Почему? А если это singleton? А если это не singleton, но список писем можно вытащить из любого места программы (потому что "application state" у нас отсутствует только в самых харкдорных библиотеках)?

M>>Или нам весь мир нужно перестроить
ARK>

Ничего не понял, зачем чего-то перестраивать.
Это если инкапсуляция хорошая. А так ведь у нас какое-нибудь UI завязано на "глобальное состояние" списка писем и еще на подобную кучу "локальных" состояний кнопок. В общем, отказ от глобальны переменных в узком смысле "глобальная переменная в стиле c" ничего не даст, все равно их можно изобразить (и глобальное состояние программы так или иначе где-то существует).

M>>Да и на экране нужно вывести что-нибудь, а это "глобальное состояние" ОС, монитора и пользователя, так что еще и все состояние OS нужно куда-нибудь передать и создать.
ARK>Это опять внешний мир, а не глобальные переменные.
Так он по всем свойствам (общая точка доступа, единственный экземпляр) как раз и является типичной глобальной переменной. И все техники по работе с ним похожи на техники работы с глобальными переменными. Так что без них никуда...

M>>Ну и так же, как с глобальными переменными — мы не отказываемся от них, мы их инкапсулируем.
ARK>Куда инкапсулируем, в синглтоны?

В инстансы, которые потом по программе таскаем

. А вообще, наверное, вы правы. Стоит различать глобальные переменные в смысле "нечто, что существует все время работы программы" и в более узком "переменная, объявленная на самом верхнем уровне/в единственном контексте". Со вторыми можно достаточно успешно бороться. Правда, не всегда удобно (в типичном UI много с собой носить приходится).

M>>Как вы его на кодах ошибок вернете?
ARK>Через discriminated union.
M>>Очевидно, что структура будет выделяться на стороне вызывающего (потому что внутри функции память может не выделиться, а код ошибки мы вернуть не можем

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

Не другой. Вопрос примерно такой же, как и с исключениями. В зависимости от механизма вашего discriminated union я буду выбирать механизм для discriminated union в случае исключений. "Исключения" в общем случае тоже "можно выделять на стеке". OutOfMemoryException можно и заранее выделить (и на стек забить, раз уж все так плохо). Так что OutOfMemory всегда есть. А все остальное ровно через те же механизмы и переписывается автоматически. Точно так же, как на кодах возврата. Только автоматически. Что-то вроде:

int someFunction(res, &abrupt) {
a(1,2,3);
b(2,3,4);
return c(d(3), r(5));
}
// переписывается в 
int someFunction(res, &abrupt) {
var state = Normal;
var rd, rr, res;
a(1, 2, 3, &state);
if (!isAbruptCompletion(state))
  b(2, 3, 4, &state)
if (!isAbruptCompletion(state))
  rd = d(3, &state);
if (!isAbruptCompletion(state))
  rr = r(5)
if (!isAbruptCompletion(state))
  res = c(rd, rr);
(*abrupt) = *state;
return res;
}

Вот. Кстати, вы уверены, что на вызовах c(...) вы нигде коды ошибок не забываете обработать? Можно и через discriminated union вернуть, если память позволяет. Где здесь нелокальность???

M>>P.S. Исключения — это локальный переход!
ARK>Нет, не локальный, т.к. мы не знаем конечной точки.
Вызов полиморфного (вирутального/динамического метода) — нелокальный переход (мы не знаем конечной точки). Хуже того, return — это нелокальный переход (по той же причине)! return нужно запретить! Только вглубь методов (continuation passing нас спасут, потому что больше ничего не осталось, а вы говорите — continuation зло!). Кстати, continuation (которые через continuation passing, а не через dsl (yield — частный случай dsl для генераторов)) очень и очень близки к полиморфизму. И при заворачинваии в интерфейс именно им и являются.

Если же подходить с точки зрения "структурного программирования" (есть конструкции с "одним входом и одним выходом") и исключения, и break/continue (частные случаи goto) являются структурными конструкциями! Только при этом тип каждого выражения/statement не такой, как записан, а монадный. Either<AbruptCompletion, A>. Да, превая часть не пишется, но всегда есть. И пролет исключения "мимо" метода все равно выходит из всех блоков (с Left<SomeException>) и из метода (с тем же Left<SomeException>). Вон, выше показал пример. Так что уж в исключениях то ничего плохого нет. Это вполне детерминированная раскрутка стека (с переходом в вызвавшую функцию) и вполне определенными механизмами взаимодействия с этой раскруткой. "Нелокальный переход" — это другое. Это "у нас выполнялась функция, а теперь вдруг перестала и об этом мы вообще никак узнать не можем".

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

M>А как там interpocess communication реализуется? Мне в идеале хочется гонять структуры между различными частями программы (теми самыми легковесными процессами). Иногда — достаточно большие объемы.

Ну статью-то почитайте.

Взаимодействие — через сообщения с семантикой копирования. Для обмена большими кусками данных есть Exchange Heap, но доступ туда — только через уникальные указатели (т.е. в один момент времени — один владелец).

M>Ну вот банальщину возьмем. Игру какую-нибудь сетевую. Один поток ведет сетевой обмен. Второй поток обсчитывает механику (очевидно, должен получать сообщения от сети в удобоваримом виде). Третий поток картинку генерирует к физике. И системный процесс все это безобразие на экран выводит (double buffering в отрисовке). В зависимости от удобства API мы получим либо те же shared memory со всеми ее проблемами (buffered image передавать надо как-то), либо кучу неудобств на ровном месте. Ну или дайте ссылку на конкретный API, я посмотрю. Если что, "высокоуровневые" примитивы обмена ведь и с обычными потоками можно использовать.

Shared memory не обязательно должен иметь типичные проблемы с блокировками, если доступ идет через уникальные ссылки (http://en.wikipedia.org/wiki/Uniqueness_type). Примеры API — ну если только исходники той же Singularity или JX (http://www4.cs.fau.de/Projects/JX/index.html), там доступ к shared data идет через "порталы". Но сам я эти API глубоко не копал, вероятно там есть свои заморочки. Но вряд ли сопоставимые с геморроем с синхронизациями.

ARK>>Писать может и удобно, а вот читать — не уверен.
M>Удобнее, чем явный автомат. Как минимум в типичных случаях. Можно, конечно, и ужасы написать. Но от misuse никто не застрахован.

Фиг знает. Не нравятся мне разбросанные везде точки выхода.

M>Ок. Хорошо. Мы можем в некоторых местах перейти на каналы. Если эффективность нас не особо волнует, наверное, мы много чего сможем на них сделать. В голову вроде бы ничего не приходит невозможного. Остается вопрос эффективности.

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

M>Например, у нас 10 игроков. Мы генерируем уникальные идентификаторы каких-то сообщений (того же чата, например, только не спрашивайте, зачем мы это делаем...). Я правильно понимаю, что без отсутствия shared state мы у специального процесса будем запрашивать генерацию и ожидать ответ на канале?

Ээ... ну наверное да. А как иначе-то. В принципе, получается та же блокировка, но реализованная на системном уровне.

M>>>Async.applySync(someFunction, [loadDataA, loadDataB, preloadImages]).
ARK>>Эта "страшная штука" — опять те же нити. Причем тут continuation? Дайте пример без async.
M>Вот в данном то конкретном случае нитей там и не было

Это полностью однопоточный код (и вообще там в рантайме поддержки потоков нет!). Где-то на верхнем уровне он вырождатеся в тот самый цикл на сообщениях:

Э, нет. Если есть "цикл на сообщениях", это получаются те же самые нити, но реализованные вручную. Велосипед с квадратными колесами. А если код истинно однопоточный, то вместо Async.applySync(someFunction, [loadDataA, loadDataB, preloadImages]) мы имеем право с чистой совестью написать:

  loadDataA();
  loadDataB();
  preloadImages();
  someFunction();

M>Да в общем, это и не важно. Как бы вы подобный код написали в однопоточном виде? Ну пусть через те же каналы. В некоторых случаях — через waitForMultipleObjects. Только не везде можно было бы обойтись этим (все равно и каналы новые нужно создавать, и запросы отправлять). Да, я писал вначале "ручные" автоматы (if loadState == ... и if loadedCount == ...). Когда переписал на continuations + async, вздохнул с огромным облегчением.

Ну как, вот так как-то (псевдокод):

  // parent process
  this.data = receive childChannel.GetData();
  someFunction();

  // ...

  // child channel
  public Data GetData()
  {
    loadDataA();
    loadDataB();
    preloadImages();
  }

M>Типичный метод:
M>

M>public function doSomething(app, arg1, arg2) : OperationState<Void> {
M>  var dataA = loadSomethingVeryAsync(arg1);
M>  var dataB = loadSomethingOverAsync(arg2);
M>  var preloadedImages = Async.applyAsync(preloadImagesForData, [dataA]);
M>  var externalData = Async.applyAsync(loadDataFromExternalSystem, [dataB, arg2]);
M>  var appUI = Async.applySync(createUI, [app, dataA,  extenralData, preloadedImages]);
M>  return Async.applySync(app.addDialog, [appUI]);
M>}
M>

M>Практически все методы грузят данные, строят какой-то UI и потом выводят его. На событиях было бы одно выходное (когда все готово) в app.addDialog (или соответствующем событии). При такой структуре методов вопросов не возникает. Пример, переписанный в "машину состояний на событиях" превращаяется в страх и ужас. Конечно, эта машина состояний где-то все-равно существует, только хорошо инкапсулирована.

Тут слишком много асинхронности для обычного метода. Это скорее какой-то диспетчер совсем верхнего уровня, каких в системе единицы.

M>И еще. Обратите внимание на уровень декларативности кода. Ему совершенно без разницы, на потоках происходит вся асинхронность или "в цикле на событиях"! Еще оно прозрачно и ошибки возвращает (ну правда, не вручную же на каждом канале проверять, успешно все закончилось или нет). А все — на continuation (потому что addDialog, createUI, loadDataFromExternalSystem — это некое continuation в самом широком смысле слова).

Вообще, больше обратил внимание на отсутствие типов данных и в связи с этим многое не понял.

Что такое dataA, dataB — данные или методы?
Насчет continuation. Здесь разве есть continuation вообще? Continuation — это когда мы вызываем метод и больше не возвращаемся. А у вас обычные асинхронные вызовы.

M>Отсутствие deadlock — это хорошо (без иронии). Может ли singularity гарантировать, что обработчик сообщений справится со всем потоком (т.е. очередь не будет расти бесконечно)? Вопрос серьезный. Например, для "автоматического парралелизма в стиле MPI" это чисто теоретически можно доказать. А иначе опять руками все доказывать...

Ну, такого рода доказательства возможны только в условиях серьезных ограничений (отсутствия динамически выделяемой памяти, сборщика мусора, рекурсии и много чего еще). В общем случае это невозможно.

ARK>>Не спора ради, а истины для. Не приведете пример убедительного превосходства yield return?
M>Ну что-то вроде:
M>

M>def listInTree(curNode, pred):
M>  if pred(curNode):
M>    yield return curNode
M>  else:
M>    for sub in curNode.children():
M>      for res in listInTree(sub, pred)
M>         yield return res
M>

M>Можно еще всякие графы более сложные обходить, например. Но это так, навскидку. Я на языки с yield return совсем недавно освоил, поэтому ничего сильно лучше под рукой нет.

  List<TreeNode> ListInTree(TreeNode node, Predicate pred)
  {
    var result = new List<TreeNode>();

    if (pred(node))
    {
      result.Add(node);

      foreach (var childNode in node.Children)
      {
        result.AddRange(ListInTree(childNode, pred));
      }
    }

    return result;
  }

По-моему, читабельность тут не особо ниже (если вообще ниже).

M>>>Кстати, вы от OOP и наследования от интерфейсов тоже предлагаете избавится? Они же недетерминизм вносят (как только мы dependency заинжектили — все, детерминизм кончился).
ARK>>Не понял, какой здесь вносится недетерминизм?
M>Ну как... В вашем же определении "Нет, не локальный, т.к. мы не знаем конечной точки." А конечной точки мы не знаем

А, в таком смысле. Тогда да. Но такой недетерминизм неизбежен, если есть полиморфизм в коде (любой).

M>Очень хорошо. А кто в этих случаях аксиомы доказывает? Пользователь или компилятор? Но даже это не важно. Вот объясните мне, почему мы можем проверить "контракты соблюдены", а "метод выбрасывает только исключения из списка ..." не можем? А если можем проверить "список исключений", то какие тогда вообще проблемы? Исключение — это не переход. Исключение — это результат работы метода! Монада такая. Все, после этого мы все, что угодно, можем доказывать.

Да, checked exceptions — доказуемы. Но вот беда, с ними возни столько, что польза становится сомнительной. Смысла в них особого нет, ИМХО. Сильно прозрачнее код они не сделают. Я это все к тому, что такие исключения — это и не исключения в общем-то (в том смысле, в каком они упоминаются в стартовом посте).

M>Это вряд ли. Переменная в замыкании примерно такая же глобальная переменная, как и все остальные. То, о чем говорил ТС, это "глобальные переменные, доступные откуда угодно". Да, эту проблему решает инкапсуляция. Только вот тоже плохо решает — все зависит от дисциплины программиста. Если я захочу, то инстанс (замыкание/класс/объект) я тоже по всей программе протащу. Собственно, вопрос здесь только в инкапсуляции и дисциплине доступа.

Все же явное протаскивание класса — гораздо лучше. Просто потому, что оно явное, и в том месте, где оно не нужно, его не будет. А глобальная переменная загаживает весь контекст.

M>>>Кстати, как вы хотите бороться с "глобальным состоянием" там, где оно существует исходя из контекста задачи? Банальный почтовый клиент возьмите. Вот пришло пользователю новое сообщение. Это глобальное или локальное состояние?
ARK>>Локальное.
M>Почему? А если это singleton? А если это не singleton, но список писем можно вытащить из любого места программы (потому что "application state" у нас отсутствует только в самых харкдорных библиотеках)?

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

M>>>Ну и так же, как с глобальными переменными — мы не отказываемся от них, мы их инкапсулируем.
ARK>>Куда инкапсулируем, в синглтоны?

M>В инстансы, которые потом по программе таскаем

. А вообще, наверное, вы правы. Стоит различать глобальные переменные в смысле "нечто, что существует все время работы программы" и в более узком "переменная, объявленная на самом верхнем уровне/в единственном контексте". Со вторыми можно достаточно успешно бороться. Правда, не всегда удобно (в типичном UI много с собой носить приходится).

Да, я именно про это. От первого никуда не уйти, а второе в топку.

M>Вот. Кстати, вы уверены, что на вызовах c(...) вы нигде коды ошибок не забываете обработать? Можно и через discriminated union вернуть, если память позволяет.

Если возврат через discriminated union, то забыть обработать не выйдет.

Придется матчить тэг и смотреть, что вернулось.

M>Где здесь нелокальность???

При возврате кода ошибки мы всегда после вызова функции окажемся на следующей строке.
На исключениях мы этого гарантировать не можем — вот и нелокальность.

M>>>P.S. Исключения — это локальный переход!
ARK>>Нет, не локальный, т.к. мы не знаем конечной точки.
M>Вызов полиморфного (вирутального/динамического метода) — нелокальный переход (мы не знаем конечной точки).

Верно.

Поэтому в языках, пытающихся дать строгие гарантии относительно выполнения, это запрещено (Ada SPARK, например).
Но в языках общего назначения отказаться от таких штук совсем затруднительно.

M>Хуже того, return — это нелокальный переход (по той же причине)! return нужно запретить!

return вызывает переход на следующую строку после вызова.

Вполне определенная точка.

M>Если же подходить с точки зрения "структурного программирования" (есть конструкции с "одним входом и одним выходом") и исключения, и break/continue (частные случаи goto) являются структурными конструкциями!

Структурными, однозначно.

M>"Нелокальный переход" — это другое. Это "у нас выполнялась функция, а теперь вдруг перестала и об этом мы вообще никак узнать не можем".

Не понял, чуть подробнее можете расписать?
Кстати, педивикия так не считает: http://en.wikipedia.org/wiki/Control_flow#Structured_non-local_control_flow

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

ARK>вероятно там есть свои заморочки. Но вряд ли сопоставимые с геморроем с синхронизациями.
Ну так надо подробно смотреть. На самом деле "геморроя синхронизации" обычно нет. Да, если идет сложная работа с многопоточностью, учитывать необходимость синхронизации нужно. В большинстве случаев все проблемы решаются правильной расстановкой syncrhonized-блоков (это тоже структурная конструкция). В более сложных иногда приходится думать. Но даже на те же очереди сообщений далеко не всегда удобно переписывать код...

ARK>Фиг знает. Не нравятся мне разбросанные везде точки выхода.
Это дело привычки. "Точки выхода" разбросаны не везде, а в теле одного метода. И метод на самом деле немного специальный — вместо обычного типа возвращает генератор. Считайте, что это локальный язык такой.

M>>Например, у нас 10 игроков. Мы генерируем уникальные идентификаторы каких-то сообщений (того же чата, например, только не спрашивайте, зачем мы это делаем...). Я правильно понимаю, что без отсутствия shared state мы у специального процесса будем запрашивать генерацию и ожидать ответ на канале?
ARK>Ээ... ну наверное да. А как иначе-то. В принципе, получается та же блокировка, но реализованная на системном уровне.

Сейчас это принято делать неблокирующими вызовами. interlocked increment или как оно там правильно в процессорах зовется. Фокус именно в том, что это выполняется на уровне процессора (с обеспечением всех безопасностей). И никаких явных синхронизаций, ожиданий и т.п. Банальный atomicInt.incrementAndGet() в Singularity превращается в запрос состояния и обмен (хотя, может, там и есть что-то подобное, не читал я документцаию). При этом еще и с блокировками на очередях. А на incrementAndGet блокировок вообще нет. Она "за константное" время выполлняется. Примерно та же история и с nonblocking collections. Так что либо в singularity мы получаем опять проблемы с производительностью, либо все подобные техники мы можем в обычном языке (на потоках) делать. Хотя, например, в mainstream я uniqueness types не видел. Было бы интересно посмотреть, как на них atomicInteger записывался бы

.

ARK>Э, нет. Если есть "цикл на сообщениях", это получаются те же самые нити, но реализованные вручную. Велосипед с квадратными колесами.
Ну не совсем с квадратными. Пользователя избавили от всех "сложностей многопоточности". Не нужны никакие критические секции, сложные инструкции вроде cmpxchg. На уровне стандартной библиотеки даже реентерабельность не нужна. Фактически, получилось примерно то, что происходит в singularity — обмен сообщенями через каналы. Между прочим, тут еще и очень важная гарантия проверяется: поток, обрабатывающий события UI, не блокируется на других каналах. Только вот видите, не удобно это все в "последовательном и безопасном" виде получилось. Все равно пришлось "потоки" на уровне внутреннего API изобрести.

ARK>А если код истинно однопоточный,
В строгом смысле слова он однопоточный. Обработка событий в одном конкретном месте. А вот "иллюзия многпоточности" как раз с использванием continuations. На безопасном API слишком неудобно. Я боюсь, что на практике singularity постигнет та же участь — будут добавлены "небезопасные", но удобные обертки.

ARK>Ну как, вот так как-то (псевдокод):
ARK>

ARK>  // child channel
ARK>  public Data GetData()
ARK>  {
ARK>    loadDataA();
ARK>    loadDataB();
ARK>    preloadImages();
ARK>  }
ARK>

К сожалению, это не эквивалент. Загрузка данных dataA и dataB должна идти параллельно. Это сокращает время ожидания пользователем доступности данных. Код — пример того, что "безопасный уровень" далеко не всегда удобен, а вот "continuations" в самом широком смысле — вполне нормальные. Я был бы рад, если бы из строго последовательный кода комплиятор преобразовал бы в то, что было в примере. Но, к сожалению, компилятор не умеет. Поэтому приходится вручную делать.

M>>Типичный метод:
ARK>Тут слишком много асинхронности для обычного метода. Это скорее какой-то диспетчер совсем верхнего уровня, каких в системе единицы.
Да какой это диспетчер? Каждый второй диалог примерно этим занимается. Если рассматривать только "крупные" диалоги, то вообще каждый первый! Картинки свои грузит, дополнительные данные, картинки для дополнительных данных и т.п. И это все только после того, как сам файл с кодом диалога загрузился. Вполне реальная задача, между прочим. Десяток подобных окон точно наберется. Может, даже и два десятка.

ARK>Вообще, больше обратил внимание на отсутствие типов данных и в связи с этим многое не понял.

Что такое dataA, dataB — данные или методы?

public interface Reactive<T> {
  public T get();
  public void addChangeListener(...);
  public void removeChangeListener(...);
}

data CommState<a> = Error String | Progress Double | Result a;

var dataA : Reactive<CommState<Ta>>
var dataB : Reactive<CommState<Tb>>
var preloadImages : Reactive<CommState<Unit>>
var externalData : Reactive<CommState<ExtT>>
var appUI : Reactive<CommState<UIControl>>
function preloadImagesForData(a : TA) : Reactive<CommState<Unit>>{}
function loadDataFromExternalSystem(b : Tb, arg2: someType) : Reactive<CommState<ExtT>>
function createUI(app : Application, a : Ta, ext : ExtT, imagesLoaded : Unit) : UIControl
function app.addDialog(ui : UIControl) : Unit

Вот такая типизация. Извините, applySync/applyAsync типизировать не могу. Не знаю подходящей системы типов, в которой его можно было бы выразить достаточно точно. Похоже, математиков не очень интересуют объекты реального мира

ARK>Насчет continuation. Здесь разве есть continuation вообще? Continuation — это когда мы вызываем метод и больше не возвращаемся. А у вас обычные асинхронные вызовы.
Ну я с wiki брал определение.

In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process' execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment.

Оно нечеткое. Считать ли обычную функцию класса "continuation" или нет? Считать ли, что только компилятор может создавать continuation или нет? Там в примерах есть continuation из scheme. Таких не пробовал, не знаю. Генераторы? Это некоторый сахар к порождающим функциям, я его не как "общий continuation" читаю. Скорее, он воспринимается как "асинхронный" producer и взаимодействие через ranvedous-point с потребителем.

Кстати, есть у меня и полностью однопоточный пример на "abstract representation of the control state of a computer program". Это push-parser комбинаторы. Т.е. не те, которые вызывал и получил результат, а которым можно по одному символу кормить и в конце концов что-нибудь из них извлечь. Вот оно в определенных местах примерно этим и кончается — мы получаем символ, вычисляем следующее состояние и передаем текущее состояние (частичный результат) следующему парсеру (или парсерам, если разбор недетерминированный). Только вот опять вопрос — считать ручное управление control state как continuation или нет? Или тот же fork/join параллелизм (мой пример с Async именно им и занимается, кстати)? Или только если он компилятором реализован?

M>>Отсутствие deadlock — это хорошо (без иронии). Может ли singularity гарантировать, что обработчик сообщений справится со всем потоком (т.е. очередь не будет расти бесконечно)? Вопрос серьезный. Например, для "автоматического парралелизма в стиле MPI" это чисто теоретически можно доказать. А иначе опять руками все доказывать...
ARK>Ну, такого рода доказательства возможны только в условиях серьезных ограничений (отсутствия динамически выделяемой памяти, сборщика мусора, рекурсии и много чего еще). В общем случае это невозможно.
Так зато безопасно! Или все-таки это создает слишком много неудобств? И за хорошими гарантиями гоняться не стоит? Но тогда чем в этом плане отличаются все якобы "нелокальные" переходы? Они еще ухудшают доказуемость (автоматическую безопасность) программ, но повышают удобство программиста.

ARK>

ARK>  List<TreeNode> ListInTree(TreeNode node, Predicate pred)
ARK>  {
ARK>    var result = new List<TreeNode>();

ARK>    if (pred(node))
ARK>    {
ARK>      result.Add(node);

ARK>      foreach (var childNode in node.Children)
ARK>      {
ARK>        result.AddRange(ListInTree(childNode, pred));
ARK>      }
ARK>    }

ARK>    return result;
ARK>  }
ARK>

ARK>По-моему, читабельность тут не особо ниже (если вообще ниже).
Угу. Только вот ваш код в худшем случае требует примерно в три раза больше памяти, чем мой. А так — все зависит от ветвистости дерева.

На самом деле еще хуже. Мой код требует памяти O(depth), где depth — глубина дерева (на самом деле поиска, я в дочерние узлы не захожу, если текущий узел удовлетворяет результату). Результат "разбирается" на месте. Ваш код требует O(depth) на стеке и еще O(result) для возврата результата. Там что-то порядка двоечки в O(result) входит, потому что на самом верхнем уровне рекурсии мы можем копировать почти весь результат с одной из веток. Да и со временем выполнения у вас не все гладко

.

Пара проблем из обозначенных, конечно, решается. Нужно переписывать функцию на аккумулятор. Но тогда придется писать две функции, да и от лишних O(result) по памяти вы никуда не денетесь. Так что ваш код не эквивалентен моему. Он хуже по time/space complexity (преимущество у него будет только если стека больше, чем обычной памяти) и занимает больше кода.

ARK>А, в таком смысле. Тогда да. Но такой недетерминизм неизбежен, если есть полиморфизм в коде (любой).
Ну так отлично. Вот мы уже разобрались, что на самом деле "недетерминизм" нас не пугает (потому что есть полиморфизм). Теперь нужно понять, пугает ли нас недетерминизм в виде исключений (которые вполне предсказуемые и структурные).

ARK>Да, checked exceptions — доказуемы. Но вот беда, с ними возни столько, что польза становится сомнительной. Смысла в них особого нет, ИМХО. Сильно прозрачнее код они не сделают. Я это все к тому, что такие исключения — это и не исключения в общем-то (в том смысле, в каком они упоминаются в стартовом посте).

Почему это "не исключения в общем-то"? Ввели немного "дисциплины", и все. Точно так же переход выполняется "неизвестно куда". Вот что неудобные — согласен. Для них очень нужны discriminated unions (еще и открытые), union types и вывод типов исключений. А смысл там не в прозрачности. Смысл — в дополнительных гарантиях. Что определенные классы ошибок будут отловлены и соответствующим способом обработаны (да хотя бы во что-то другое завернуты). В определенных случаях и с дополнительными практиками вроде code review очень и очень хорошо помогают.

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

M>>Вот. Кстати, вы уверены, что на вызовах c(...) вы нигде коды ошибок не забываете обработать? Можно и через discriminated union вернуть, если память позволяет.
ARK>Если возврат через discriminated union, то забыть обработать не выйдет.

Придется матчить тэг и смотреть, что вернулось.
Одними discriminated union вы не отделаетесь. Вам еще и union types нужно будет, иначе high-order functions очень неудобно реализуются. Везде, куда мы передали функцию, та функция может вернуть какой-нибудь код ошибки. Для каких-нибудь примитивов уровня OS это не важно. Там обычно все достаточно конкретно. А вот для функций общего назначения (iter, fold, map, filter, композиция функций и т.п.) подобное очень нужно.

Что характерно, после введения нормальных union types и вывода типов, вы получите те же самые checked exceptions, реализованные вручную

M>>Где здесь нелокальность???
ARK>При возврате кода ошибки мы всегда после вызова функции окажемся на следующей строке.
ARK>На исключениях мы этого гарантировать не можем — вот и нелокальность.

Так я же показал (развернул модель вычисления). На следующую строку управление и возвращается, только в состоянии abrupt completion. И обычно в языках есть нормальные способы таки узнать о наличии Abrupt completion и что-нибудь сделать. (те же try/catch/finally). Ну да, про наличие монады забывать нельзя. Но учитывая, что в любой строке может банальный stack overflow возникнуть, это вполне нормально. При повышенной безопасности (вроде проверки диапазона массивов во время выполнения) список различных проблем только увеличивается. Так что проще привыкнуть проверять необходимые гарантии освобождения ресурсов (благо в современных языках их не так много нужно контроллировать).

ARK>Но в языках общего назначения отказаться от таких штук совсем затруднительно.

Вот. С этим я тоже согласен. Но к многим штукам, которые ОП предлагает запретить, быстро и легко привыкаешь. Да, повсюду их пихать плохо. Но в удобных местах они экономят много кода и сил. Что такое "удобные" определяется многими факторами. Можно, например, стандартами кодирования и ревью контроллировать, что все в команде понимают код.

M>>Хуже того, return — это нелокальный переход (по той же причине)! return нужно запретить!

ARK>return вызывает переход на следующую строку после вызова.

Вполне определенная точка.

После вызова где? Правильно, в какую-то неизвестную в данном месте строчку неизвестно кого.
И вы просто не встречались с нетривиальным return. Scala:

package com.pm.application.api

object Test extends App {
  private def xxx(a: => Int) {
    System.out.println("In XXXX")
    val aa = a
    System.out.println("AAA : " + aa)
  }

  private def bbb() : Int = {
    xxx({
      return 5
    })
    System.out.println("After XXX")
    6
  }
  
  System.out.println("BBB : " + bbb())
}

---- Output:
In XXXX
BBB : 5

Обратите внимание, return выходит совсем не туда, куда казалось бы. Да и простое "вычисление значения, переданного как call-by-name" является нелокальным переходом. Но это, конечно, экзотика (кстати, ловится обычным catch). Можно что-нибудь более каноничное и гораздо более предсказуемое (как минимум, я знаю по спецификации, как и что оно вычисляет). Java:

int calculateSomething() {
  int j = 5;
  for (int i = 0; i < 10; i++) {
    try {
      return i; /// Just a return!
    } finally {
      j = i;
      if (i != 7)
        continue;
      else
        break;
    }
  }

  return j+1;
}

Вот... Так что ваша теория работает. Но, наверное, не совсем так, как вы ожидали. Переход действительно выполняется на следующую строчку. Только вот в том же самом методе! И статус abrupt completion устанавливается в Return(value). В общем, никакой особой разницы с исключениями.

M>>"Нелокальный переход" — это другое. Это "у нас выполнялась функция, а теперь вдруг перестала и об этом мы вообще никак узнать не можем".
ARK>Не понял, чуть подробнее можете расписать?

Могу, конечно. Под "нелокальными переходами" я в первую очередь подразумеваю что-то вроде setjmp/longjmp. Это такое continuation на C. Совершенно небезопасное и неструктурное. Оно стек не раскручивает, а сносит и заменяет на новый. Это вот как раз нелокальный переход, а все остальное по сравнению с ним — детские игры.

Может быть, еще вариантами нелокального перехода являются lisp conditions и list continuations же, но я не знаю, как они работают, поэтому ничего определенного сказать не могу.

ARK>Кстати, педивикия так не считает: http://en.wikipedia.org/wiki/Control_flow#Structured_non-local_control_flow
Бывает. Но вот исключения, например, в зависимости от нижележащей модели вычислений, могут являться или не являться нелокальным переходом. В "монадной" модели — не являются. Поэтому я предпочитаю использовать ее. Может быть, conditions тоже сводятся к подобному. Например, там будет union различных установленных conditions в данный момент. И скорее это будет не локальный переход, а implicit context, например.

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

Размеры постов превысили размер моего мозгового буфера.

Поэтому только пара замечаний.

M>Сейчас это принято делать неблокирующими вызовами. interlocked increment или как оно там правильно в процессорах зовется. Фокус именно в том, что это выполняется на уровне процессора (с обеспечением всех безопасностей). И никаких явных синхронизаций, ожиданий и т.п.

Думаю, то, что выполняется на уровне процессора, может быть вынесено прямо в API. Как примитивная операция типа сложения.

M>Угу. Только вот ваш код в худшем случае требует примерно в три раза больше памяти, чем мой. А так — все зависит от ветвистости дерева.
M>На самом деле еще хуже. Мой код требует памяти O(depth), где depth — глубина дерева (на самом деле поиска, я в дочерние узлы не захожу, если текущий узел удовлетворяет результату). Результат "разбирается" на месте. Ваш код требует O(depth) на стеке и еще O(result) для возврата результата. Там что-то порядка двоечки в O(result) входит, потому что на самом верхнем уровне рекурсии мы можем копировать почти весь результат с одной из веток. Да и со временем выполнения у вас не все гладко

.

А, ну с дочерними узлами я просто ошибся. Дополнительная память для результата — ну да, потому что мой код энергичный. Вам она тоже потребуется, если запросите всю последовательность. Хотя, если обрабатывать поэлементно, то наверное не понадобится. А со временем что не так (если отбросить мою ошибку с дочерними узлами)?

M>Пара проблем из обозначенных, конечно, решается. Нужно переписывать функцию на аккумулятор. Но тогда придется писать две функции, да и от лишних O(result) по памяти вы никуда не денетесь. Так что ваш код не эквивалентен моему. Он хуже по time/space complexity (преимущество у него будет только если стека больше, чем обычной памяти) и занимает больше кода.

Это, кстати, еще надо проверить — во что там переписываются ваши yield return.

А то может статься, что все хуже, чем вы думаете.

Кстати, мне думается, что ленивость можно сделать без yield return. Для программиста это будет выглядеть как мой код, но вместо List<TreeNode> будет нечто вроде LazyList<TreeNode>. Умный компилятор перепишет это в такой же ленивый генератор.

M>Кстати, если заменить весь ввод/вывод на асинхронный (т.е. приходят события о поступлении данных), то места исключениям сразу становится гораздо меньше. Они остаются только в парсинге пришедших данных. Всем остальным занимается большой и страшный Async-комбинатор. А все остальное — это уже ошибки в коде.

Не находите, что что-то здесь не так? С исключениями-то? Как асинхронный код — сразу старые добрые коды ошибок. По мне, это показывает несовершенство механизма.

M>Что характерно, после введения нормальных union types и вывода типов, вы получите те же самые checked exceptions, реализованные вручную

Но без прыжков неизвестно куда.

M>Так я же показал (развернул модель вычисления). На следующую строку управление и возвращается, только в состоянии abrupt completion.

У вас пример неверный, по-моему. После выхода из процедуры с вашим abrupt completion мы должны сделать GOTO на ближайший подходящий обработчик.
Концептуально возврат идет неизвестно куда — в случае успешного выполнения на следующую строку, в случае неуспешного — на какой-то обработчик фиг знает где выше.

ARK>>return вызывает переход на следующую строку после вызова.

Вполне определенная точка.
M>После вызова где? Правильно, в какую-то неизвестную в данном месте строчку неизвестно кого.

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

M>И вы просто не встречались с нетривиальным return. Scala:
M>Обратите внимание, return выходит совсем не туда, куда казалось бы.

За такое надо вырывать с корнем руки.

И такой return точно не нужен. Кстати, это то же самое, что и крышка в Smalltalk.

M>Можно что-нибудь более каноничное и гораздо более предсказуемое (как минимум, я знаю по спецификации, как и что оно вычисляет). Java:
M>Вот... Так что ваша теория работает. Но, наверное, не совсем так, как вы ожидали. Переход действительно выполняется на следующую строчку. Только вот в том же самом методе! И статус abrupt completion устанавливается в Return(value). В общем, никакой особой разницы с исключениями.

За такой двусмысленный код руки тоже надо того...

На мой взгляд, здесь вместо знания спецификации должна быть ошибка компиляции. Наверняка в C# так и есть, хотя я не проверял. Впрочем, насколько я помню, Java позволяет всякую тупизну и типа такого:

  try
  {
    return 1;
  }
  finally
  {
    return 2;
  }

Это — чистой воды говнокод. И, заметьте, из-за goto-подобных операторов return, break и continue.

Если бы их не было, то таких вопросов не было бы в принципе.

В целом из всех "прыгающих" операторов я пока не знаю, как отказаться от исключений (про это писал в одном из постов выше). Ну и от полиморфизма отказываться не стоит.

Остальное, ИМХО, вполне можно упразднить с разной степенью успеха.

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

ARK>Кстати, мне думается, что ленивость можно сделать без yield return. Для программиста это будет выглядеть как мой код, но вместо List<TreeNode> будет нечто вроде LazyList<TreeNode>. Умный компилятор перепишет это в такой же ленивый генератор.

Можно сделать, но в энергичном языке компилятор сам не догадается, придется
разыменовывать как указатели, например такие ленивые типы есть в OCaml и F#.

Но очень большой плюс yield кроме ленивости это возможность легко комбинировать
функции и использовать рекурсию, во многом аналогично ФВП в функциональных языках.
Например в питоне набор функций для итераторов http://docs.python.org/2/library/itertools.html
вполне сопоставим с базовым набором ФВП для списков http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html
в OCaml и также позволяет легко комбинировать и создавать функции более высокого порядка.
При этом выразительность получается вполне на уровне ФВП, как пример можно посмотреть
вот эту библиотечку для питона https://github.com/JulienPalard/Pipe .

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

ARK>В целом из всех "прыгающих" операторов я пока не знаю, как отказаться от исключений (про это писал в одном из постов выше). Ну и от полиморфизма отказываться не стоит.

Остальное, ИМХО, вполне можно упразднить с разной степенью успеха.

Надо идти дальше из управляющих конструкций оставить только условный оператор и рекурсию.

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

FR>Надо идти дальше из управляющих конструкций оставить только условный оператор и рекурсию.

Ну, это перебор.

Я предлагаю минимизировать не число управляющих конструкций вообще, а число гото-подобных. Кстати, вот в Eiffel нет return, break и continue. А это все же не совсем маргинальный язык, хотя и не мейнстримовый.

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

ARK>>Кстати, мне думается, что ленивость можно сделать без yield return. Для программиста это будет выглядеть как мой код, но вместо List<TreeNode> будет нечто вроде LazyList<TreeNode>. Умный компилятор перепишет это в такой же ленивый генератор.

FR>Можно сделать, но в энергичном языке компилятор сам не догадается, придется
FR>разыменовывать как указатели, например такие ленивые типы есть в OCaml и F#.

Прошу прощения, не понял, можете пояснить? О чем должен догадаться компилятор?

FR>Но очень большой плюс yield кроме ленивости это возможность легко комбинировать
FR>функции и использовать рекурсию, во многом аналогично ФВП в функциональных языках.
FR>Например в питоне набор функций для итераторов http://docs.python.org/2/library/itertools.html

Посмотрел, но, по-моему, тут yield return опять же только ленивости везде. Все функции и без него переписываются 1-в-1 с обычными контейнерами. Я не прав?
К примеру,

def takewhile(predicate, iterable):
    # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
    for x in iterable:
        if predicate(x):
            yield x
        else:
            break

меняем на

IEnumerable<T> takewhile<T>(Predicate<T> predicate, IEnumerable<T> iterable)
{
  var result = new List<T>();

  foreach (var x in iterable)
  {
    if (predicate(x))
      result.Add(x);
    else
      break;
  }

  return result;
}

FR>При этом выразительность получается вполне на уровне ФВП, как пример можно посмотреть
FR>вот эту библиотечку для питона https://github.com/JulienPalard/Pipe .

Посмотрел. Вроде тут везде просто применение уже готовых функций из itertools.

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

ARK>Прошу прощения, не понял, можете пояснить? О чем должен догадаться компилятор?

О том где нужно использовать ленивость а где строгость, придется это указывать вручную.
В том же OCaml для этого есть функция force.

FR>>Но очень большой плюс yield кроме ленивости это возможность легко комбинировать
FR>>функции и использовать рекурсию, во многом аналогично ФВП в функциональных языках.
FR>>Например в питоне набор функций для итераторов http://docs.python.org/2/library/itertools.html

ARK>Посмотрел, но, по-моему, тут yield return опять же только ленивости везде. Все функции и без него переписываются 1-в-1 с обычными контейнерами. Я не прав?

Если не сохранять ленивость то да прав, но кому нужна квадратичная сложность вместо линейной?

Если ленивость сохранять то твой код сильно усложнится в сравнении с кодом использующим
yield. Например для того же OCaml есть библиотечка аналог itertools для питона
http://ocaml-batteries-team.github.com/batteries-included/hdoc/BatEnum.html если ее
использовать только комбинируя заданные ФВП все отлично, но если нужно писать свои базовые
функции то все становится грустно из-за отсутствия yield.

ARK>Посмотрел. Вроде тут везде просто применение уже готовых функций из itertools.

Я хотел продемонстрировать выразительность, тот же пример

euler2 = fib() | where(lambda x: x % 2 == 0)
               | take_while(lambda x: x < 4000000)
               | add

вполне нормально смотрится и на фоне хаскеля с окамлом.

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

ARK>Ну, это перебор.

Интересный язык кстати может получится из трех только вещей: условный оператор, рекурсия и undelimited continuations

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

FR>О том где нужно использовать ленивость а где строгость, придется это указывать вручную.
FR>В том же OCaml для этого есть функция force.

Эээ... а название типа ему в этом не поможет? Если функция возвращает List, то код энергичный, если LazyList — то делается генератор а-ля yield.
А на вызывающей стороне должно быть пофиг.

ARK>>Посмотрел, но, по-моему, тут yield return опять же только ленивости везде. Все функции и без него переписываются 1-в-1 с обычными контейнерами. Я не прав?
FR>Если не сохранять ленивость то да прав, но кому нужна квадратичная сложность вместо линейной?

А где квадратичная? По памяти в 2 раза больше, по времени то же самое. Нет?

FR>Если ленивость сохранять то твой код сильно усложнится в сравнении с кодом использующим
FR>yield.

Дык, мы же с этого начали — я сделал предположение, что с ~~сферическим~~ умным компилятором усложнения быть не должно (просто взять LazyList вместо List).

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

ARK>Эээ... а название типа ему в этом не поможет? Если функция возвращает List, то код энергичный, если LazyList — то делается генератор а-ля yield.
ARK>А на вызывающей стороне должно быть пофиг.

В таком случае получаем тот же yield вид сбоку.
Но менее удобный, смотри тот же BatEnum.
Менее удобный потому что yield позволяет передать управление не теряя контекста,
в этом он похож чем-то на замыкания. Без него придется все делать ручками и вместо
простого и наглядного:

def Fib(n):
    a, b = 0, 1
    for i in xrange(n):
        yield a
        a, b = b, a + b

мы получим такое страшилище:

class Fibonacci:
  def __init__(self, max):
    self.n, self.a, self.b, self.max = 0, 0, 1, max
  def __iter__(self):
    return self
  def next(self):
    if self.n < self.max:
      a, self.n, self.a, self.b = self.a, self.n+1, self.b, self.a+self.b
      return a
    else:
      raise StopIteration

ARK>

А где квадратичная? По памяти в 2 раза больше, по времени то же самое. Нет?

Да тут я дал маху, но N прогонов по циклу вместо одного в цепочке из N функций
все равно получим.

ARK>Дык, мы же с этого начали — я сделал предположение, что с ~~сферическим~~ умным компилятором усложнения быть не должно (просто взять LazyList вместо List).

Не вижу как можно сделать такой компилятор.

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

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

ARK>А со временем что не так (если отбросить мою ошибку с дочерними узлами)?
Сильно несбалансированное дерево. Допустим, даже двоичное. Левая ветка сразу является искомым узлом. Правая — продолжается перекошенное вправа дерево. А дальше все зависит от от реализации буфера. Если это что-то на базе одного массива, то вы будете на каждом шаге переписывать весь хвост в новый буфер (к одному элементу из левого поддерева). Итого общая сложность будет O(depth^2), где depth — глубина дерева. Наверное, могут спасти ropes (это "строки" с легкой конкатенацией).

ARK>Умный компилятор перепишет это в такой же ленивый генератор.
Ну да. FR уже заметил, что разницы между LazyList.add и yield return практически никакой (только в названии).

M>>Кстати, если заменить весь ввод/вывод на асинхронный (т.е. приходят события о поступлении данных), то места исключениям сразу становится гораздо меньше. Они остаются только в парсинге пришедших данных. Всем остальным занимается большой и страшный Async-комбинатор. А все остальное — это уже ошибки в коде.
ARK>Не находите, что что-то здесь не так? С исключениями-то? Как асинхронный код — сразу старые добрые коды ошибок. По мне, это показывает несовершенство механизма.

Да нет, все нормально. Как раз потому, что исключения нужно понимать в "монадном" смысле. Вот если бы исключения были нелокальным переходом, их можно было бы использовать. А так исключения всего лишь удобная обертка над кодами ошибок. Весь тот async — тоже обертка над похожими (асинхронными) кодами ошибок. Информация об ошибке является объектом (так же, как и исключение). Для большинства функций ошибки обрабатываются прозрачно (проходят на более высокий уровень), исключения всплывают подобным уровнем. У меня даже аналог catch есть (можно получить не только успешное значение, а результат с описанием ошибки или результатом). Вообще, async по сути образуют примитивный язык, поддерживающий только вызовы функций и литералы. Умел бы компилятор его правильно компилировать (не в "последовательной" монаде, а в "асинхронном выполнении"), был бы тоже имеративный код с исключениями

M>>Так я же показал (развернул модель вычисления). На следующую строку управление и возвращается, только в состоянии abrupt completion.
ARK>У вас пример неверный, по-моему. После выхода из процедуры с вашим abrupt completion мы должны сделать GOTO на ближайший подходящий обработчик.

Точно верный. Почему это мы должны сделать GOTO? У нас вызов завершился с abrupt completion. Если ничего специально не делать, все выражения в текущем методе тоже завершатся с abrupt completion. Затем аналогично завершатся методы еще на уровень выше и т.д. В конце концов обработчик будет найден. Весь этот сложный процесс примерно эквивалентен "переходу на подходящий обработчик" и приводит к такому же результату. try/finally — это тоже подходящий обработчик с последующим выбросом полученного ранее исключения. Какая-нибудь автоматика по вызову деструкторов в C++ — тоже подходящие обработчики (точно так же перебрасывающие исключения). Зато в подобной модели выполнения вся раскрутка стека детерминированна. Вроде бы во всех языках, которые я знаю, исключения как раз и работают по этой модели. Да, может быть, они описываются через "GOTO обработчик" и кучу описаний побочных эффектов от других инструкций (вроде вызова деструкторов при пролетающем мимо исключении). "Нелокальный переход" — это просто очень неудачное объяснение вполне удачной конструкции.

M>>Можно что-нибудь более каноничное и гораздо более предсказуемое (как минимум, я знаю по спецификации, как и что оно вычисляет). Java:
M>>Вот... Так что ваша теория работает. Но, наверное, не совсем так, как вы ожидали. Переход действительно выполняется на следующую строчку. Только вот в том же самом методе! И статус abrupt completion устанавливается в Return(value). В общем, никакой особой разницы с исключениями.

ARK>Впрочем, насколько я помню, Java позволяет всякую тупизну и типа такого:
ARK>

ARK>  try
ARK>  {
ARK>    return 1;
ARK>  }
ARK>  finally
ARK>  {
ARK>    return 2;
ARK>  }
ARK>

ARK>Это — чистой воды говнокод. И, заметьте, из-за goto-подобных операторов return, break и continue.

Если бы их не было, то таких вопросов не было бы в принципе.

Позволяет. Побочные эфффекты удачно определенной монады. Как-то поведение все равно пришлось бы специфицировать (для обработки исключений, continue из catch и прочих радостей). Поэтому получилось то, что получилось. Да и нормально все. Ваш код — аналог следующего:

int retval;
{
  {
    retval = 1;
  }
  retval = 2;
}
return retval;

Это тот же код, переписанный в single return и на явных return state. Примерно такой же говнокод, но на Java это заметно лучше. От break/continue/return можно избавиться, это не слишком сложная задача. Но код усложнится (лишние проверки). Фактически, магию обработки (abrupt completion) вы выписываете вручную. И не факт, что потом в развернутом коде проблемы будет легко искать. А еще отказ от return'а приводит периодически к длинным-длинным лесенкам if'ов (вместо if(condition) return ... ; ), что явно не способствует читабельности кода.

ARK>В целом из всех "прыгающих" операторов я пока не знаю, как отказаться от исключений (про это писал в одном из постов выше). Ну и от полиморфизма отказываться не стоит.

Остальное, ИМХО, вполне можно упразднить с разной степенью успеха.

А я бы, наоборот, повводил еще несколько моделей вычисления. Например, "реактивное программирование", когда присваивание значения переменной может приводить к изменению значений других выражений и вызову определенных методов. Тоже нелокальность (в духе полиморфизма). Так что я за сохранение и приумножение разнообразия различных моделей вычислений. Естественно, без лишнего фанатизма.

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

T>Все эти три цитаты говорят об одном и том же -- о принципиальной вредности нелокальных управляющих конструкций. Какие вообще нелокальные управляющие конструкции мы знаем? Очень много, увы. Дейкстра был счастливчиком имея дело всего лишь с GOTO.

http://www.youtube.com/watch?v=c76xD3qNLc4&t=49m26s

Я очень горд, что в этой книжке (Elements of Programming) есть, вы сейчас просто @#$%&%@#, GOTOS. Почему? Потому что в какой-то момент мы показываем, специально, потому что знаем, что вы будете кричать БУУУУУ и писать письма, может быть не все, но некоторые — мне всегда пишут письма что я дурак — потому что я не верю в объектную ориентацию, я использую goto — пропащий человек. И многие люди, в программировании есть такая идея что люди считают что это очень мило написать незнакомому человеку письмо говорящие что "ты дурак". Даже если вы так думаете — вы мне не говорите, потому что — не нужно, не обязательно.
Мы используем goto, для чего — потому что у нас есть структура которая реально является конечным автоматом. Если вы описываете конечный автомат, что он делает — он переходит из состояния этого в состояние то. Как нужно переходить из одного состояния в другое? Есть правильная инструкция — называется goto: идите от туда — туда. И структура программы становится очень элегантной.
То есть идея Дейкстры, Дейкстра великий человек — вы не думайте что $#%@#$%@#$, но он конечно же был не прав, потому что он думал, что плохая программа, потому что она пользуется какой-то синтаксической структурой. Нет — программа плохая, если она плохая.
То есть может быть очень красивая программа на языке Assembler — очень элегантная. Может быть очень плохая программа на Java, уверяю вас.
Немецкий язык такой непоэтичный — но какая поэзия Самые красивые песни на каком языке? На немецком — Шуберт — необыкновенная красота. Хотя у них там гортанный, странный язык, но невероятно красивый.
Всё можно сделать. goto может быть красивым. Я не верю в синтаксические лишения в семантических вопросах.
В меня всю жизнь камнями кидают, потому что я всё время такие вещи говорю — и мне говорят что я дурак. Но я не пытаюсь просто сказать дерзость. Я на самом деле пытаюсь объяснить какие-то вещи и в этой книжке никаких дерзостей.

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

T>* Continuations

Иногда полезно использовать — упрощают структуру.

T>* Исключения

Намного чаще приносят пользу чем вред.

T>* Сопрограммы

Иногда полезно использовать — упрощают структуру.
Например при программировании асинхронных потоков — помогают спрятать много синтаксического шума в библиотеку.

T>* Генераторы

Отличный синтаксис для генерации single pass последовательностей — упрощают код.

T>Каждая нелокальная управляющая конструкция имеет локальный и детерминированный эквивалент.
T>Нелокальный GOTO и необходимость использования continuations могут быть ликвидированы при хорошей структурированности программы, исключения и нотификации -- заменены обработкой кодов возврата, сопрограммы и генераторы -- вызовами функций

Каждую программу можно выразить в терминах машины тьюринга.
Каждую программу можно выразить на языке unlabmda в котором всего две встроенные функции(i — не нужен) и один оператор + пару функций для I/O — все на unlambda!

T>В отчёте С++ performance technical report [7], про исключения аккуратно сказано: "для некоторых программ проблему составляет сложность в предсказании времени, требующегося для передачи управления от throw до подходящего catch" и предлагается провести для каждой точки возможного выброса исключений сложный анализ, включающий анализ времени работы всех деструкторов объектов, которые могут быть вызваны при раскрутке стека, который позволит установить верхнюю и нижнюю границу времени выполнения.

"некоторых программ", это:

Enable exception handling for real-time critical programs only if exceptions are actually used. A complete analysis must always include the throwing of an exception, and this analysis will always be implementation dependent.
On the other hand, the requirement to act within a deterministic time might loosen in the case of an exception (e.g. there is no need to handle any more input from a device when a connection has broken down).

А конкретно, для <b><u>JOINT STRIKE FIGHTER AIR VEHICLE</u></b>.

T>Именно поэтому я предлагаю все нелокальные управляющие конструкции считать вредными.

I do not buy the author's arguments either. I keep running into this meme at least a few times every year "exceptions are bad, they're a nightmare, etc..."

My typical reply is also somewhere along the same lines: if you don't like to use exceptions, then just don't use them. Leave that job to the professionals

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

ARK>>Дык, мы же с этого начали — я сделал предположение, что с ~~сферическим~~ умным компилятором усложнения быть не должно (просто взять LazyList вместо List).

FR>Не вижу как можно сделать такой компилятор.

Элементарно же.

Вот это

IEnumerable<T> takewhile<T>(Predicate<T> predicate, IEnumerable<T> iterable)
{
  var result = new LazyList<T>();

  foreach (var x in iterable)
  {
    if (predicate(x))
      result.Add(x);
    else
      break;
  }

  return result;
}

автоматом переписывается в

IEnumerable<T> takewhile<T>(Predicate<T> predicate, IEnumerable<T> iterable)
{
  foreach (var x in iterable)
  {
    if (predicate(x))
      yield return x;
    else
      break;
  }
}

Может показаться, что это попахивает жульничеством. Но нет. Концептуально в первом варианте мы имеем один вход и один выход. А что там внизу — пофиг. В ассемблере вообще одни goto label, и что с того?

Более того — похоже, можно вообще любой метод помечать атрибутом [Lazy] и все! Безо всяких дополнительных управляющих конструкций и без потери читабельности.

А если пойти еще дальше — то ленивость можно сделать полностью автоматической оптимизацией. Я даже думаю, что программист далеко не всегда может сам определить, должен ли метод быть ленивым.
Где нужна вообще ленивость? (На полноту и истину не претендую.)
1) Бесконечные структуры данных. Оставим этот вариант безумным ученым. Если кому очень надо, можно сделать вручную.
2) Отложенные вычисления — надеемся, что (вдруг) вычислять вообще не придется. Это плюс. Минус — это ухудшает реактивность и предсказуемость работы системы в целом. Поэтому опять в топку, при сильной необходимости делаем вручную.
3) Когда не нужно хранить всю последовательность, а обрабатываем ее поэлементно. А вот тут компилятор может сам подставить ленивость (иногда

).
Одним словом, мне кажется, что ленивость и yield — это просто высокоуровневая оптимизация.

Еще раз основная мысль поста: на мой взгляд можно обойтись без yield return и не потерять в читабельности.

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

ARK>>А со временем что не так (если отбросить мою ошибку с дочерними узлами)?
M>Сильно несбалансированное дерево. Допустим, даже двоичное. Левая ветка сразу является искомым узлом. Правая — продолжается перекошенное вправа дерево. А дальше все зависит от от реализации буфера. Если это что-то на базе одного массива, то вы будете на каждом шаге переписывать весь хвост в новый буфер (к одному элементу из левого поддерева). Итого общая сложность будет O(depth^2), где depth — глубина дерева. Наверное, могут спасти ropes (это "строки" с легкой конкатенацией).

Да нет же.

Добавление элемента в массив выполняется за линейное время (амортизированное).
Так что все там нормально со временем. Да и с памятью тоже, ведь, как ни крути, O(2N)=O(N).

ARK>>Умный компилятор перепишет это в такой же ленивый генератор.
M>Ну да. FR уже заметил, что разницы между LazyList.add и yield return практически никакой (только в названии).

ИМХО, есть разница. Я там ответил — http://www.rsdn.ru/forum/philosophy/5114101

M>>>Так я же показал (развернул модель вычисления). На следующую строку управление и возвращается, только в состоянии abrupt completion.
ARK>>У вас пример неверный, по-моему. После выхода из процедуры с вашим abrupt completion мы должны сделать GOTO на ближайший подходящий обработчик.
M>Точно верный. Почему это мы должны сделать GOTO? У нас вызов завершился с abrupt completion. Если ничего специально не делать, все выражения в текущем методе тоже завершатся с abrupt completion. Затем аналогично завершатся методы еще на уровень выше и т.д. В конце концов обработчик будет найден.

А, ну да. Но вообще это тонкий момент. Я, например, когда смотрю код, я не вижу, что функция "монадная". (Собственно, в этом и профит исключений.) А раз не вижу, значит концептуально "прыжок неизвестно куда" есть. То, что можно код переписать на abrupt completion — ничего не меняет, это всего лишь одна из возможных реализаций. Причем в реальности не использующаяся. Мы же не говорим, что if — это goto, несмотря на то, что реализовано оно именно так?

M>Это тот же код, переписанный в single return и на явных return state. Примерно такой же говнокод, но на Java это заметно лучше.

Я бы сказал, что на Java заметно хуже. Двусмысленность же. Недаром в C# это ошибка компиляции.

M>А я бы, наоборот, повводил еще несколько моделей вычисления. Например, "реактивное программирование", когда присваивание значения переменной может приводить к изменению значений других выражений и вызову определенных методов. Тоже нелокальность (в духе полиморфизма).

Да, тут недалеко в философии есть длинный разговор про реактивное программирование.

M>Так что я за сохранение и приумножение разнообразия различных моделей вычислений. Естественно, без лишнего фанатизма.

Дык — контроль нужен, вот в чем дело. Желательно формальный. Иначе кул ксакепы в порыве самореализации наплодят ужасов и это расползется по библиотекам. Вот, например: http://www.rsdn.ru/forum/java/5097238

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

T>Дейкстра в классической статье [1] приводит несколько серьёзных доводов против нелокального goto. В частности, он пишет: "наши интеллектуальные возможности в основном направлены на анализ статических отношений и, напротив, наши способности представлять ход процессов, разворачивающихся во времени, развиты сравнительно слабо. Поэтому мы должны (как умные программисты, осознающие, собственные ограничения) делать всё от нас зависящее, чтобы уменьшать концептуальный зазор между статическим кодом программы и динамическим процессом её выполнения, добиваясь как можно более тривиального соответствия между программой (разворачивающейся в виде текста) и порождённым ей процессом (разворачивающимся во времени)".

Пускай каждый программист выбирает те средства, которые способен охватить своим сознанием.
Кому-то Лого будет пределом, а кому-то и макароны из тысячи потоков предстают цельной и ясной конструкцией.
Вот и всё, что требуется для уменьшения концептуального зазора.

<>

T>Очень похожие аргументы о недетерминированном поведении кода приводит Edward A. Lee из Berkeley в своей работе [4], посвященной критике нитей исполнения (threads). Он пишет: "мы должны (и можем) строить детерминированные модели параллельного исполнения, в которые обоснованно и осторожно вносить недетермнизм там, где он реально нужен. Нити исполнения предлагают противоположный подход. Они делают программы абсурдно недетерминистичными и сильно полагаются на хороший стиль программирования, чтобы ограничить этот недетерминизм и достичь детерминированных целей"

Если исключения — это просто мрачный механизм (вполне себе детерминированный, но создающий слишком много путей исполнения), то с потоками всё веселее: начинает влиять окружающая среда в виде планировщика. Система внезапно становится открытой.

T>Все эти три цитаты говорят об одном и том же -- о принципиальной вредности нелокальных управляющих конструкций.

Не о вредности, а о неподъёмности для средних умов. (А статические анализаторы кода — это посредственные умы, просто очень въедливые).

T> Какие вообще нелокальные управляющие конструкции мы знаем? Очень много, увы. Дейкстра был счастливчиком имея дело всего лишь с GOTO. Вот только некоторые источники головной боли в наше время:

T>* Нелокальный GOTO
T>* Continuations
T>* Исключения
T>* Сигналы
T>* Нотификации
T>* Сопрограммы
T>* Генераторы
T>* Нити исполнения
T>... имя им легион ...

T>Каждая нелокальная управляющая конструкция имеет локальный и детерминированный эквивалент. Нелокальный GOTO и необходимость использования continuations могут быть ликвидированы при хорошей структурированности программы, исключения и нотификации -- заменены обработкой кодов возврата, сопрограммы и генераторы -- вызовами функций, нити исполнения -- детерминированным параллелизмом на уровне компилятора, таким как OpenMP. Тем не менее они возникают снова и снова в разных видах из-за ложного чувства упрощения разработки, которое они дают.

Ну хорошо, возьмём и заменим всё вышеперечисленное громоздкими "чистыми" эквивалентами.
Поскольку рефакторинг — это изоморфизм, то мы получим точно такое же бешеное количество путей исполнения, только вместо тайного — явное.
Ещё и захламим код, исключив последние возможности для Eye-Driven Development.

Разве лишь человеческая лень заставит переосмыслить код и сделать всё то же самое по-другому и проще.

А что касается ООП, так я напомню: у объекта есть поведение и состояние. Говнокод на машине состояний ничем не лучше говнокода на сопрограмме.
Только если мы эту машину состояний родим из какого-то формального описания, которое поддаётся верификации.
Если родим её руками или напишем собственный велосипед, который должен работать как машина состояний — никакой статический анализатор не осилит.

<.....>
T>Именно поэтому я предлагаю все нелокальные управляющие конструкции считать вредными.

и вернуться в однопоточный ДОС.

	От:	AlexRK
	Дата:	23.03.13 17:57
	Оценка:

От:	D. Mon	http://thedeemon.livejournal.com
Дата:	24.03.13 15:31
Оценка:

	От:	maxkar
	Дата:	24.03.13 16:31
	Оценка:

	От:	AlexRK
	Дата:	24.03.13 19:55
	Оценка:

	От:	maxkar
	Дата:	25.03.13 16:37
	Оценка:

	От:	Evgeny.Panasyuk
	Дата:	26.03.13 18:18
	Оценка:	6 (1) +3

	От:	Кодт
	Дата:	26.03.13 21:43
	Оценка:	37 (3) +2