Многие поклонников Хаскеля отмечают, что ленивость — это одна из самых интересных его особенностей.

Однако и многие его проблемы проистекают из ленивости. Когда данные становятся доступны только когда к ним обращаются вычисления становятся трудно понимаемыми и это противоречит идее побочных эффектов при вычислениях.

А, что если вместо ленивой модели вычислений, в которой доступность данных определяется их необходимостью, применять модель вычислений в которой вычисление определяется доступностью входных данных?

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

A = B.C + D; // A зависит от B.C и D, так что эта ветка выполнится последней
B.C = D; // B.C зависит от D, так что эта ветка выполнится второй
D = 42; // D ни от чего не зависит, так что ветка выполнится первой

Большинство свойств такого языка аналогичны "чистому" ленивому ФЯ:
1. Переменные вычисляются один раз.
2. Последовательность вычислений определяется зависимостями.

Однако так как вычисления происходят сразу же как будут доступны зависимости, не возникает проблем с побочными эффектами, отладкой и т.п.

Единственная проблем с его реализацией это создание эффективной машины для его исполнения или преобразования его в эффективный код. Если есть мысли по его эффективной реализации, прошу поделиться (граф зависимостей не предлагать, так как слишком много в памяти нужно держать и менять его на ходу затратно).

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

VD>Мы тут делали один DSL для типизации и сделали именно такую модель вычислений. Результат был очень интересным. Язык ведет себя как ленивый, но нет никаких проблем с побочными эффектами, так как вычисления просходят сразу как становятся доступными данные. Общая идея такая:

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

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

N>По-моему, все билд-скрипты работают по этому принципу.

Это понятно. Не понпонятно, почему бы это не использовать для ЯП?

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

Почему, неоднозначна? То что граф может быть отсортирован по разному не означает, что он должен сортироваться по разному. Используя один алгоритм получаем одинаковую (предсказуемую) последовательность выполнения.

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

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

VD>Когда данные становятся доступны только когда к ним обращаются вычисления становятся трудно понимаемыми и это противоречит идее побочных эффектов при вычислениях.

Каким образом? "идея побочных эффектов при вычислениях" — она о других аспектах. А под тот аспект который по всей видимости ты имеешь в виду, например попадает остановка при внезапной сборке мусора.

VD>Общая идея такая:
VD>

VD>A = B.C + D; // A зависит от B.C и D, так что эта ветка выполнится последней
VD>B.C = D; // B.C зависит от D, так что эта ветка выполнится второй
VD>D = 42; // D ни от чего не зависит, так что ветка выполнится первой

Ключевые слова для поиска: spreadsheet, reactive programming, future/promise, и как выше уже сказали — topological sorting.

VD>Однако так как вычисления происходят сразу же как будут доступны зависимости, не возникает проблем с побочными эффектами, отладкой и т.п.

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

VD>Единственная проблем с его реализацией это создание эффективной машины для его исполнения или преобразования его в эффективный код.

А что там будет помимо выражений, и как это будет выглядеть?

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

N>>Порядок вычислений не полностью детерминирован, так как топологическая сортировка в общем случае неоднозначна.
VD>Почему, неоднозначна? То что граф может быть отсортирован по разному не означает, что он должен сортироваться по разному. Используя один алгоритм получаем одинаковую (предсказуемую) последовательность выполнения.

А зачем предсказуемый порядок выполнения?
Оптимизаторы кода переставляют инструкции местами как им удобнее, если это не меняет семантику.
Более того, например в C++ не определён порядок вычисления аргументов функций: f(foo(), bar()).

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

VD>А, что если вместо ленивой модели вычислений, в которой доступность данных определяется их необходимостью, применять модель вычислений в которой вычисление определяется доступностью входных данных?

Комбинатор фиксированной точки получится сделать?

fix :: (a -> a) -> a
fix f = let a = f a in a

Через ленивость мемоизируем заранее неизвестный аргумент, а дальше его раскручиваем через итерации. На этой идее в Haskell работают рекурсивные вычисления, в том числе, внутри монады IO (она на самом деле не такая уж и императивная, как ее обычно обзывают). Классная штука! Без нее будет совсем неинтересно

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

<>

У хаскелла ленивость неявная и принудительная, иногда это ведёт к распуханию графа отложенных вычислений.
(Разумеется, в любом языке можно сделать явную принудительную ленивость, с теми же последствиями; а в хаскелле можно сделать явную принудительную энергичность).

Во если сломать хаскелл, объявив, что ленивость необязательна, — мол, не рассчитывайте на неё, а только надейтесь, — и хорошенько поработать над оптимизирующим компилятором и умной средой исполнения...
Тогда не надо будет изучать разницу между foldl и foldl'

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

VD>А, что если вместо ленивой модели вычислений, в которой доступность данных определяется их необходимостью, применять модель вычислений в которой вычисление определяется доступностью входных данных?

VD>Мы тут делали один DSL для типизации и сделали именно такую модель вычислений. Результат был очень интересным. Язык ведет себя как ленивый, но нет никаких проблем с побочными эффектами, так как вычисления просходят сразу как становятся доступными данные. Общая идея такая:
VD>

VD>A = B.C + D; // A зависит от B.C и D, так что эта ветка выполнится последней
VD>B.C = D; // B.C зависит от D, так что эта ветка выполнится второй
VD>D = 42; // D ни от чего не зависит, так что ветка выполнится первой

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

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

VD>Мы тут делали один DSL для типизации и сделали именно такую модель вычислений. Результат был очень интересным. Язык ведет себя как ленивый, но нет никаких проблем с побочными эффектами, так как вычисления просходят сразу как становятся доступными данные. Общая идея такая:
С побочными эффектами ты сильно погорячился.
Эта модель их не допускает.

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

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

D>Комбинатор фиксированной точки получится сделать?
Нам ехать, а не шашечки.
Причём ехать быстро. Ибо задача сугубо практическая.

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

WH>С побочными эффектами ты сильно погорячился.
WH>Эта модель их не допускает.

Очень даже допускает. И я их делал.

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

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

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

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

VD>Очень даже допускает. И я их делал.
Формирование скопов побочным эффектом не является. Ибо результат мержа символов от порядка дефайнов не зависит.
Если ты их использовал для чего-то ещё, то если изменится стратегия вычислений, начнётся фейерверк.

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

WH>Формирование скопов побочным эффектом не является.

Причем тут списки? Вот изменение состояния объекта — является. И я их постоянно делаю. Плюс можно тупо вывести что-то в консоль и т.п.

WH>Ибо результат мержа символов от порядка дефайнов не зависит.

Какая разница что от чего зависит, если я меняю состояние объектов?

WH>Если ты их использовал для чего-то ещё, то если изменится стратегия вычислений, начнётся фейерверк.

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

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

WH>>Формирование скопов побочным эффектом не является.
VD>Причем тут списки?
Что? Я про списки вообще ничего не говорил.

VD>Вот изменение состояния объекта — является. И я их постоянно делаю.
Каких именно?

VD>Плюс можно тупо вывести что-то в консоль и т.п.
В хаскеле тоже можно. Там unsafePerformIO есть. Вот только лучше его не использовать.

WH>>Ибо результат мержа символов от порядка дефайнов не зависит.
VD>Какая разница что от чего зависит, если я меняю состояние объектов?
Большая.
Если изменение это добавление символа в скоп то проблем нет.
Слияние символов у нас ассоциативное и коммутативное.
Соответственно результат от порядка выполнения не зависит.

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

VD>Ничего нигде не начнется. Побочный эффект точно выполняется строго после расчета тех или иных значений. Я могу сохранить рассчитанное значение в файл или отправить на печать.
Порядок выполнения у нас таки не определён и может в будущем изменится.
Современная стратегия вычислений оптимальна или близка к оптимальной в большинстве случаев. Но худший случай у нас таки печален. O(N^2) от количества свойств в дереве.
Так что изменение алгоритма вполне возможно.

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

N>>По-моему, все билд-скрипты работают по этому принципу.

VD>Это понятно. Не понпонятно, почему бы это не использовать для ЯП?

Я к тому, что это не новая идея. Используется в специфических языках и фреймворках, там где это адекватно выполняемой задаче: MSBuild, Excel, TPL Dataflow. Кажется очень применимым для IDE, там где нужно выполнять сложные инкрементальные многофазные анализы на постоянно меняющихся входных данных (исходный код в редакторе). Ты предлагаешь сделать это стратегией выполнения по умолчанию для языков общего назначения? Было бы интересно посмотреть примеры реализации каких-то алгоритмов (в псевдокоде), и увидеть, какие это даёт преимущества перед традиционными энергичными или ленивыми стратегиями. Краткость записи? Скорость выполнения? Скорость компиляции? Экономия потребляемой памяти? Удобство отладки? Упрощение рефакторинга? Увеличение понятности кода? Уменьшение риска логических ошибок?

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

К>Во если сломать хаскелл, объявив, что ленивость необязательна, — мол, не рассчитывайте на неё, а только надейтесь, — и хорошенько поработать над оптимизирующим компилятором и умной средой исполнения...
К>Тогда не надо будет изучать разницу между foldl и foldl'

У меня давно есть идея, которую хочется попробовать (может быть, кто-то уже пробовал?). Мне кажется, что она может дать потенциальный выигрыш на многоядерных машинах для некоторых алгоритмов. Хотя слышал мнение, что оверхед реализации перевесит любой выигрыш.

Представим себе чистый функциональный язык, где по умолчанию вычисления ленивые. У нас в коде есть точки ветвления, например паттерн матчинг для некоторого выражения, или оператор if (который есть тот же паттерн матчинг булевского выражения по константам True, False). В точках ветвления мы вынуждены форсировать вычисление контролирующего выражения (от результата которого должен зависеть выбор условной ветви). Так как язык чистый, то вычисления различных условных ветвей не зависят друг от друга. Поэтому, параллельно с вычислением контролирующего выражения, мы можем начать спекулятивно вычислять все или несколько (в зависимости от наличия свободных ядер) условных ветвей. В случае, если вычисление контролирующего выражения заканчивается раньше, и выбор условной ветви становится известным, мы прерываем незаконченные вычисления ветвей, ставших ненужными, и продолжаем выполнение выбранной ветви. В случае, если вычисление какой-то ветви требует форсирования вычисления выражения, которое зависит от ещё неизвестных переменных, участвующих в незавершённом паттерн матчинге, выполнение данной ветви приостанавливается до завершения вычисления контролирующего выражения и завершения паттерн матчинга, и ядро освобождается для спекулятивного вычисления другой условной ветви (которая может быть из той же самой, или другой точки ветвления).

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

N>У меня давно есть идея, которую хочется попробовать (может быть, кто-то уже пробовал?). Мне кажется, что она может дать потенциальный выигрыш на многоядерных машинах для некоторых алгоритмов. Хотя слышал мнение, что оверхед реализации перевесит любой выигрыш.

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

На мой взгляд, такие предвычисления выгодны при достижении двух условий:
1. Общая комбинаторная сложность меньше количества доступных ядер.
2. Затраты на предвычисление ветки больше, чем время thread switch, и, в то же время, достаточно малы, чтобы идея вообще имела смысл.
Если эти условия не выполняются, то тогда надо смотреть на реактивную модель вычислений, да ещё чтоб хорошо ложилась на зелёные потоки. Т.е в сторону multiagent data mining со всеми особенностями и прелестями.

Оччень узкоспециализированная будет штука, другими словами. С другой стороны, для всяких data mining/olap тут нет ничего нового, поиск корреляций брутфорсом с незапамятных времён был. Как правило, в качестве мальчика для битья для "умных" подходов, но тем не менее был.
И даже иногда наносил ответный удар, как в первом в истории использовании университетского кластера для чего-то полезного

Как-то так

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

N>Представим себе чистый функциональный язык, где по умолчанию вычисления ленивые. У нас в коде есть точки ветвления, например паттерн матчинг для некоторого выражения, или оператор if (который есть тот же паттерн матчинг булевского выражения по константам True, False). В точках ветвления мы вынуждены форсировать вычисление контролирующего выражения (от результата которого должен зависеть выбор условной ветви). Так как язык чистый, то вычисления различных условных ветвей не зависят друг от друга. Поэтому, параллельно с вычислением контролирующего выражения, мы можем начать спекулятивно вычислять все или несколько (в зависимости от наличия свободных ядер) условных ветвей. В случае, если вычисление контролирующего выражения заканчивается раньше, и выбор условной ветви становится известным, мы прерываем незаконченные вычисления ветвей, ставших ненужными, и продолжаем выполнение выбранной ветви. В случае, если вычисление какой-то ветви требует форсирования вычисления выражения, которое зависит от ещё неизвестных переменных, участвующих в незавершённом паттерн матчинге, выполнение данной ветви приостанавливается до завершения вычисления контролирующего выражения и завершения паттерн матчинга, и ядро освобождается для спекулятивного вычисления другой условной ветви (которая может быть из той же самой, или другой точки ветвления).

Недетерминированная сеть Петри какая-то.
Я такую фигню делал однажды, правда, в одноядерном исполнении, — но её временная диаграмма оказалась настолько контринтуитивной (причём незадолго до отдачи заказчикам), что пришлось забить и сделать тактирование.

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

VD>Мы тут делали один DSL для типизации и сделали именно такую модель вычислений. Результат был очень интересным. Язык ведет себя как ленивый, но нет никаких проблем с побочными эффектами, так как вычисления просходят сразу как становятся доступными данные. Общая идея такая:
VD>

VD>A = B.C + D; // A зависит от B.C и D, так что эта ветка выполнится последней
VD>B.C = D; // B.C зависит от D, так что эта ветка выполнится второй
VD>D = 42; // D ни от чего не зависит, так что ветка выполнится первой

У меня довольно большой проект весь пронизан подобными вычислениями через IObservable<T>. Условно получается так:

this.WhenAnyValue(t => t.B.C, t => t.D)
    .Select((c, d) => c + d)
    .BindTo(this, t => t.A);

this.WhenAnyValue(t => t.D)
    .BindTo(this, t => t.B.C);

D = 42;

Оно отлично работает, плюс можно добавлять разные удобные фишки вроде Throttle, Timeout и т.д. и т.п.
Если получится сделать из этого DSL, то будет дюже круто.

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

N>Ты предлагаешь сделать это стратегией выполнения по умолчанию для языков общего назначения?

Да. Точнее не понимаю почему до сих пор этого не сделал. Может какие-то противопоказания есть.

N>Было бы интересно посмотреть примеры реализации каких-то алгоритмов (в псевдокоде), и увидеть, какие это даёт преимущества перед традиционными энергичными или ленивыми стратегиями.

У нас уже прототип работает. Правда, пока что он незаконченный. Сейчас такой язык доступен для расчета значений на AST-е, а мы хотим, чтобы он был доступен и на символах. Но примеры уже можно посмотреть.

N>Краткость записи?

Краткость примерно такая же как и у любого другого ФЯ, но вот семантика более близкая императивщикам получается. В прочем, это скорее вопрос дизайна языка.

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

N>Скорость выполнения? Скорость компиляции?

Со скоростью выполнения большой вопрос. Мы генерируем дотнетный код (считай машинный), но при этом есть некоторый код который немного увеличивает объем вычислений. Плюс у нас есть проблема вызванная расширяемостью. Наш AST должен поддерживать расширяемость (в том числе в рантайме), так что мы не можем строить граф зависимостей, а делаем частичную упорядоченность и вычисляем свойства обходом в всех ветвей AST-а. Но, получается очень шустро.

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

N>Экономия потребляемой памяти?

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

N>Удобство отладки?

Несомненно! В отличии от чисто императивных языков в языке на базе такой вычислительной модели можно можно реализовать функциональную чистоту с контролируемой императивностью. В отличии от чисто линивых языков никаких проблем с отладкой (хоть претипринтом, хоть отладчиком, хоть визуализацией расчетов (как в Эксел)) нет.

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

N>Упрощение рефакторинга?

Это от вычислительной модели не особо зависит.

N>Увеличение понятности кода?

Несомненно.

N>Уменьшение риска логических ошибок?

И это тоже.

Пожалуй лучше описать наш язык. Сразу оговорюсь, что это ДСЛ. В нем нельзя даже создать объекты явно, а типы объектов жестко ограничены ветками AST (в ближайшее время будут еще поддерживаться символы). Так что не надо искать в нем что-то мозговыворачивающие. Это просто язык который должен резко упростить расчеты по AST-у (типизацию).

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

Свойства делятся на три группы:
1. in-свойства. Их можно задавать извне объекта.
2. out-свойства. Их можно задавать изнутри объекта.
3. inout-свойства. По сути они образуют пару (in и out) свойств, но во многих местах интерпретируются и обрабатываются вместе.

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

В языке есть коллекции элементов AST заданного типа которые описывают структуру текущего узла. Если у элементов коллекции есть свои свойства, то в коллекции создаются свойства с теми же именами. Они позволяют обрабатывать списки без циклов, фолдов и прочей фигни усложняющей код. При этом такие псевдо-ствойства так же являются зависимыми.

Вот описания проекции свойств для списков:
1. Если у элемента коллекции есть in-свойство, то у списка появляется свойство с тем же именем и типом. При присвоении этого свойства значение присваивается аналогичным свойствам всех хранящихся в списке объектов.
2. Если у элемента коллекции есть out-свойство, то у списка появляется свойство типа список и склоненным именем и типом элемента соответствующим типу свойства хранимого объекта.
3. Если у элемента коллекции есть inout-свойство, то у списка появляется inout-свойство с тем же именем и типом. При присвоении значения in-части свойства это значение присваивает в in-часть свойства первого объекта хранящегося в коллекции. Когда становится доступным значение out-части свойства первого объекта, оно помещается в in-часть свойства второго объекта и так далее, пока не будет достигнут последний объект коллекции. out-часть свойства последнего объекта коллекции возвращается как значение out-части свойства всей коллекции. Таким образом проводится протаскивание вычисления через все объекты коллекции, что аналогично свертке слева на право в функциональных языках. Свертка справа налево нам была не нужна, но сделать ее не сложно.

Вот код связывания для C# написанный с использованием нашего DSL на основе зависимых свойств. Зависимые свойств выделены жирным.

  ast Reference
  {
    in Scope : Scope;
    out Symbol : Symbol2 = Scope.TryBind(this);
  }

  asts QualifiedReference
  {
  stage 1:
    in Arity : int = 0;
    in Scope   : Scope;
    out Symbol : Symbol2;

    | Simple
      {
        Name.Scope = Scope;
        Symbol     = Utils.TryResolveTypeOverload(Name.Symbol, Arity);

        Name : Reference; // Структурно свойство. Может содержать другие зависимые свойства. 
      }

    | Aliased 
      {
        Name.Scope = Scope;
        Symbol     = Utils.TryResolveTypeOverload(Name.Symbol, Arity);

        Alias : Reference;
        Name  : Reference;
      }

    | Qualified
      {
        Qualifier.Arity = 0;
        Qualifier.Scope = Scope;
        Name.Scope      = Qualifier.Symbol.Scope;
        Symbol          = Utils.TryResolveTypeOverload(Name.Symbol, Arity);

        Qualifier : QualifiedReference;
        Name      : Reference;
      }

    | Generic
      {
        Arguments.Arity     = 0; // инициализируются все свойства Arity всех объектов из списка
        QualifiedName.Arity = Arguments.Count;
        QualifiedName.Scope = Scope;
        Arguments.Scope     = Scope;
        Symbol              = QualifiedName.Symbol;

        QualifiedName : QualifiedReference;
        Arguments     : QualifiedReference*;
      }
  }

Объекты в таком языке можно создавать не инициализированными и инициализировать их по ходу вычислений. При этом не надо бояться за то, что кто-то обратится к не инициализированным свойствам. Этого просто не может произойти такие обращения будут отложены во времени до тех пор пока не вычисляться значения зависимостей.

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

I>Если получится сделать из этого DSL, то будет дюже круто.

Что значит получится? Уже.

Только он у нас пока что узко специализированный. Мы его используем для расчетов по AST-у. Естественно, под капотом никаких IObservable, замыканий и прочей траты памяти. На объект есть только одно лишнее битовое поле. Код вычислений выглядит как обычный:

  declarations GenericType : Type
  {
    out Symbol : GenericTypeSymbol;
  stage 1:
    out BodyScope : Scope;

    Modifiers.FlagsIn                 = Modifiers.None;
    TypeParameters.IndexIn            = 0;
    TypeParameters.PrevTypeParameters = Utils.TryGetPrevTypeParameters(this);
    Members.Parent                    = Symbol;
    BodyScope                         = Symbol.MakeBaseTypesScope(this.Scope);
    TypeBase.Scope                    = BodyScope;
    TypeParameterConstraints.Scope    = BodyScope;
    Members.TypeScope                 = BodyScope;

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

EP>А зачем предсказуемый порядок выполнения?

Хотя бы для той же отладки.

EP>Оптимизаторы кода переставляют инструкции местами как им удобнее, если это не меняет семантику.
EP>Более того, например в C++ не определён порядок вычисления аргументов функций: f(foo(), bar()).

Ага. Вот только не ясно почему в его наследниках (C# и Java) порядок вычисления был четко определен в спецификации?

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

EP>Каким образом? "идея побочных эффектов при вычислениях" — она о других аспектах. А под тот аспект который по всей видимости ты имеешь в виду, например попадает остановка при внезапной сборке мусора.

Нет. В ленивом языке вычисления откладываются даже если все данных для них есть. Так что ставить, например, печать результата выражения сразу за ним бесполезно. Пока вычисления не понадобятся кому-то другому этот код не вычислится.

В языке о котором говорю я все вычистился и на результат можно будет посмотреть в том месте где его ожидает "императивный" программист. Во всем же остальном язык больше похож на ленивый ФЯ.

EP>Ключевые слова для поиска: spreadsheet, reactive programming, future/promise, и как выше уже сказали — topological sorting.

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

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

Причем тут алгоритмическая сложность? Что касается бесконечных списков, то вряд ли они необходимы постоянно. И, если нужно, их не так уж сложно реализовать или предоставить в виде библиотечного решения. Тот же IEnumerable<T> обладает тем иже свойствами отгороженности вычисления и бесконечности.

EP>Или например получение нескольких алгоритмов из одного кода — линеаритмической сортировки и линейного алгоритма выбора.

Это все здорово, но мало пригодно для "гражданского" применения простыми смертными. А, вот, тот же spreadsheet (Ёкскель) постоянно используют люди даже не относящиеся к программированию. Для них нужна выразительность, безопасность и удобность, а не возможность почесать правое ухо пяткой левой ноги.

EP>А что там будет помимо выражений, и как это будет выглядеть?

Наш DSL я (вкратце) описал здесь

Автор: VladD2
Дата: 03.07.15

. А, вообще, в перспективе можно создать интересный функцонально-объектно-ориентированный язык общего назначения. Для нужд обработки данных на деревьях или графах он точно не плохо подходит.

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

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

D>>Комбинатор фиксированной точки получится сделать?
WH>Нам ехать, а не шашечки.
WH>Причём ехать быстро. Ибо задача сугубо практическая.

Рекурсивные вычисления как раз таки очень удобны для практики. Если более конкретно, то это так называемая "рекурсивная нотация do". Я использую у себя для краткого определения обыкновенных дифференциальных уравнений, например.

В основе реализации рекурсивных вычислений лежит идея о комбинаторе неподвижной точки. Это обобщение идеи. А реализуется через ленивость. Как обычно, в Haskell реализован общий механизм в отличие от упрощенных Scala и F#, где тоже есть что-то подобное.

Это все частности. Теперь более фундаментальное.

Подразумевает ли "новая" стратегия вычислений, что язык должен быть ссылочно-прозрачным? Если да, то это неминуемо ведет к тому требованию, что язык должен быть еще и чистым. Или ссылочная прозрачность по боку?

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

VD>А, что если вместо ленивой модели вычислений, в которой доступность данных определяется их необходимостью, применять модель вычислений в которой вычисление определяется доступностью входных данных?

наиболее близко это к out-of-order execution в cpu

VD>Однако так как вычисления происходят сразу же как будут доступны зависимости, не возникает проблем с побочными эффектами, отладкой и т.п.

а по мне наоборот — если в ленивом яхыке порядок вычислений диктуется самими данными (вычисляя a*b, мы рекурсивно погружаемся в вычисление а и b), то в таком языке вычислив x, мы внезапно начинаем вычислять сотни переменных, зависящих от него, причём ещё и в восходящем порядке. неужели это будет кому-то понятней??

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

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

в целом, по сравнению с ленивостью выходит менее удобно для отладки, требует больше вычислений (вычисляем всё что можно, а не всё что нужно), порядок вычислений так же недетерминирован (следует отличать детерминированность модели и конкретной реализации), и реализация похоже будет менее эффективной

но оригинально, с чем и поздравляю

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

BZ>наиболее близко это к out-of-order execution в cpu

Ну, это немного из другой оперы. Разве что похоже.

BZ>а по мне наоборот — если в ленивом яхыке порядок вычислений диктуется самими данными (вычисляя a*b, мы рекурсивно погружаемся в вычисление а и b), то в таком языке вычислив x, мы внезапно начинаем вычислять сотни переменных, зависящих от него, причём ещё и в восходящем порядке. неужели это будет кому-то понятней??

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

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

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

BZ>то же самое с побочными эффектами — никаких технических проблем с ними в хаскеле нет, они запрещены по идеологическим причинам, чтобы разделоить мат. понятие вычисления и алг. понятие выполнения

Проблема в том, что если значение не "запрашивать", то расчет производиться не будет, а стало быть, не будет и побочного эффекта. В остальном, согласен.

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

Ну, мы сделали реализацию для своих нужд которая позволяет обсчитывать, с помощью такого языка, значения на дереве (AST). Посчитано значение или нет хранится в битовом поле каждого узла АСТ и составляет по биту на зависимое свойство (там мы называем такие значения). Не эффективность заключается в том, что наш алгоритм расчета "нарезает круги" по AST, и при неблагоприятных обстоятельствах, этих кругов может оказаться больше чем нужно для линейного расчета. Мы не можем создавать граф зависимостей статически или динамически, так как наш AST динамически изменяемый. Но мы производим локальную сортировку (для одного узла) и полагаемся на то, что на практике дерево в 99% случаев обходится справа-налево, сверху-вниз (за исключения случаев, когда оно намеренно образует отдельные проходы). В итоге получается хорошая производительность. Но у нас все же не полноценный язык, а DSL ограниченных обработкой данных на дереве (AST).

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

BZ>в целом, по сравнению с ленивостью выходит менее удобно для отладки,

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

BZ>требует больше вычислений (вычисляем всё что можно, а не всё что нужно),

Вот это большой вопрос. Уверен, что ленивые вычисления не даются бесплатно. Хотелось бы оценить эти затраты и сравнить с теми что имеем мы. В идеале, можно даже попробовать сделать гибридную систему. Она бы нам не помешала. В режиме IDE ленивость была бы востребована на начальных этапах загрузки для ускорения отрисовки и приведения GUI в рабочий режим. Ну, а потом уже можно пустить все вычисления на отдельных потоках для ускорения расчетов и отклика IDE.

BZ>порядок вычислений так же недетерминирован (следует отличать детерминированность модели и конкретной реализации), и реализация похоже будет менее эффективной

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

А сама идея зависимых свойств позволяет нам инициализировать объект в псевдо-произвольном порядке и при этом не иметь проблем обычных для императивного подхода.

BZ>но оригинально, с чем и поздравляю

Спасибо. Вот только не верится, что нам эта идея пришла первым в голову. Интересно посмотреть на другие похожие. Плюс интересно сравнить его с ленивым исполнением и посмотреть нельзя ли связать эти оба механизма чтобы получить в одном языке преимущества обоих подходов. Чтобы ленивость была даже не по требованию того кто пишет программу, а по необходимости ее потребителя. Грузим мы проект в IDE — переходим в ленивый режим чтобы максимально быстро отобразить данные той функции что у программиста на экране и т.п. А, потом запускаем по потоку для каждого процессора и даем им в пакетном режиме протипировать AST всех фалов проекта.

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

D>Рекурсивные вычисления как раз таки очень удобны для практики. Если более конкретно, то это так называемая "рекурсивная нотация do". Я использую у себя для краткого определения обыкновенных дифференциальных уравнений, например.

А можно пример кода? Я как раз сейчас занимаюсь сходной проблемой, было бы интересно посмотреть.

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

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

D>>Рекурсивные вычисления как раз таки очень удобны для практики. Если более конкретно, то это так называемая "рекурсивная нотация do". Я использую у себя для краткого определения обыкновенных дифференциальных уравнений, например.

M>А можно пример кода? Я как раз сейчас занимаюсь сходной проблемой, было бы интересно посмотреть.

Можно поспорить с тем, насколько это практично. Для меня даже очень:

model :: Simulation Results
model = 
  mdo a <- integ (- ka * a) 100
      b <- integ (ka * a - kb * b) 0
      c <- integ (kb * b) 0
      let ka = 1
          kb = 1
      return $ results
        [resultSource "a" "variable A" a,
         resultSource "b" "variable B" b,
         resultSource "c" "variable C" c]

Это моя Айвика (англ. Aivika). У нее конек в сильной поддержке дискретно-событийного моделирования, но есть и поддержка системной динамики.

В примере самое интересное в том, как определяются три интеграла a, b и c. Каждый имеет тип Dynamics Double, но функция integ возвращает аппроксимацию интеграла в рамках вычисления Simulation по заданным производной и начальному значению, а точнее

integ :: Dynamics Double -> Dynamics Double -> Simulation (Dynamics Double)

Фокус в том, что Simulation является MonadFix, а потому можно использовать рекурсивную нотацию do. Здесь в примере это обозначается ключевым словом "mdo".

Да, еще для понимания. Dynamics Double является Num:

instance Num a => Num (Dynamics a)

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

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

D>>Рекурсивные вычисления как раз таки очень удобны для практики. Если более конкретно, то это так называемая "рекурсивная нотация do". Я использую у себя для краткого определения обыкновенных дифференциальных уравнений, например.

M>А можно пример кода? Я как раз сейчас занимаюсь сходной проблемой, было бы интересно посмотреть.

Вот, более интересный пример. Навеяно примером из документации к Vensim:

https://github.com/dsorokin/aivika-experiment-chart/blob/master/examples/Financial/Model.hs