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

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

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

Мы тут делали один 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*;
      }
  }

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