Haskell: Чем отличаются нестрогие и ленивые?

Question

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

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

Non-Strict Def:

Функция f называется строгой, если при применении к неопределенному выражению она также не завершается. Другими словами, f строгое, если значение f bot равно |, Для большинства языков программирования все функции являются строгими. Но это не так в Хаскеле. В качестве простого примера рассмотрим const1, функцию константы 1, определяемую как:

const1 x = 1

Значение бота const1 в Haskell равно 1. С практической точки зрения, поскольку const1 не "нуждается" в значении своего аргумента, он никогда не пытается его оценить и, таким образом, никогда не попадает в непрерывное вычисление. По этой причине нестрогие функции также называются "ленивыми функциями" и, как говорят, оценивают свои аргументы "лениво" или "по необходимости".

- Нежное Введение в Haskell: Функции

Мне очень нравится это определение. Кажется, это лучшее, что я смог найти для строгого понимания. Является const1 x = 1 а лень?

Нестрогость означает, что сокращение (математический термин для оценки) происходит извне,

так что если у вас есть (a + (bc)), то сначала вы уменьшаете +, а затем уменьшаете внутреннее (b c).

- Haskell Wiki: Lavy против нестрогих

Haskell Wiki действительно смущает меня. Я понимаю, что они говорят о порядке, но я не понимаю, как (a+(b*c)) будет оценивать не строго, если бы это было пройти _|_?

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

При церковном кодировании ленивая оценка операторов переводится в нестрогую оценку функций; по этой причине нестрогая оценка часто упоминается как "ленивая". Булевы выражения во многих языках используют форму нестрогого вычисления, называемого оценкой короткого замыкания, когда оценка возвращается, как только может быть определено, что однозначный логический результат будет получен - например, в дизъюнктивном выражении, где встречается true, или в конъюнктивное выражение, где встречается ложь, и так далее. Условные выражения также обычно используют ленивую оценку, где оценка возвращается, как только получится однозначная ветвь.

- Википедия: стратегия оценки

Lazy Def:

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

Очевидно, существует сильное соответствие между выражением thunk и частично оцененным выражением. Следовательно, в большинстве случаев термины "ленивый" и "нестрогий" являются синонимами. Но не совсем.

- Haskell Wiki: Lavy против нестрогих

Это похоже на конкретный ответ на Haskell. Я так понимаю, что ленивые средства, громкие слова и нестрогие средства частичной оценки. Это сравнение слишком упрощено? Всегда ли ленивый означает "гром" и " не строгий" всегда означает частичную оценку.

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

- Википедия: Ленивая оценка

Императивные примеры

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

Короткое замыкание

f1() || f2()

C#, Python и другие языки с "yield"

public static IEnumerable Power(int number, int exponent)
{
    int counter = 0;
    int result = 1;
    while (counter++ < exponent)
    {
        result = result * number;
        yield return result;
    }
}

- MSDN: выход (C#)

Callbacks

int f1() { return 1;}
int f2() { return 2;}

int lazy(int (*cb1)(), int (*cb2)() , int x) {
    if (x == 0)
        return cb1();
    else
        return cb2();
}

int eager(int e1, int e2, int x) {
    if (x == 0)
         return e1;
    else
         return e2;
}

lazy(f1, f2, x);
eager(f1(), f2(), x);

Вопросы

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

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

• Является const1 x = 1 тоже ленивый?
• Как оценка из "внутреннего" не строгая? Это потому, что внутрь допускается сокращение ненужных выражений, как в const1 x = 1? Сокращения, кажется, соответствуют определению ленивых.
• Всегда ли ленивый означает " гром" и " не строгий" всегда означает частичную оценку? Это просто обобщение?
• Являются ли следующие императивные понятия ленивыми, нестрогими, обоими или ни тем, ни другим?
  • Короткое замыкание
  • Используя урожай
  • Передача обратных вызовов, чтобы задержать или избежать исполнения
• Ленивое подмножество нестрогих или наоборот, или они взаимоисключающие. Например, возможно ли быть нестрогим, не будучи ленивым, или ленивым, не будучи нестрогим?
• Достигнут ли лукавство нестрогости Хаскеля?

Спасибо тебе!

Answer 1

Нестрогие и ленивые, хотя и неофициально взаимозаменяемы, применимы к различным областям обсуждения

Нестрогий относится к семантике: математическое значение выражения. Мир, к которому относится нестрогий, не имеет понятия времени работы функции, потребления памяти или даже компьютера. Он просто говорит о том, какие значения в доменной карте и какие значения в кодомене. В частности, строгая функция должна отобразить значение ⊥ ("внизу" - см. Ссылку на семантику выше для получения дополнительной информации)); не строгая функция разрешается не делать этого.

Ленивый относится к оперативному поведению: способ выполнения кода на реальном компьютере. Большинство программистов думают о программах оперативно, так что это, вероятно, то, что вы думаете. Ленивая оценка относится к реализации с использованием thunks - указателей на код, которые заменяются значением при первом запуске. Обратите внимание на несемантические слова: "указатель", "первый раз", "выполнено".

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

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

Answer 2

Пример для модели оценки, которая не является ни строгой, ни ленивой: оптимистическая оценка, которая дает некоторое ускорение, поскольку она может избежать большого количества "простых" приемов:

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

Как видите, эта модель оценки не является строгой: если вычисляется что-то, что дает _|_, но не требуется, функция все равно будет остановлена, так как механизм отменяет оценку. С другой стороны, возможно, что будет вычислено больше выражений, чем необходимо, так что это не совсем лениво.

Answer 3

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

Одно из главных отличий заключается в оценке сроков. Есть несколько стратегий для этого, начиная от "как можно скорее" до "только в последний момент". Термин " нетерпеливая оценка" иногда используется для стратегий, склоняющихся к первому, в то время как ленивая оценка правильно относится к семейству стратегий, сильно склоняющихся к последним. Различие между "ленивой оценкой" и соответствующими стратегиями, как правило, заключается в том, когда и где сохраняется результат оценки чего-либо, а не отбрасывается в сторону. На этом основана знакомая техника запоминания в Haskell - присвоение имени структуре данных и ее индексация. Напротив, язык, который просто объединяет выражения друг с другом (как в оценке "по имени"), может не поддерживать это.

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

Должно быть легко увидеть, как они взаимодействуют сложным образом; решения вовсе не являются ортогональными, поскольку крайности, как правило, несовместимы. Например:

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

• Очень строгая оценка делает неосторожность несколько неактуальной; если вы оцениваете все, решение о том, когда это делать, менее важно.

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

Answer 4

Это началось как обновление, но начало становиться длинным.

Laziness / Call-by-need - запомненная версия call-by-name, где, если аргумент функции оценивается, это значение сохраняется для последующего использования. В "чистом" (безэффектном) режиме это приводит к тем же результатам, что и вызов по имени; когда аргумент функции используется два или более раз, вызов по потребности почти всегда быстрее.
Императивный пример - по-видимому, это возможно. Есть интересная статья о Lazy Imperative Languages. Там написано, что есть два метода. Один требует замыканий, второй использует сокращения графов. Поскольку C не поддерживает замыкания, вам необходимо явно передать аргумент вашему итератору. Вы можете обернуть структуру карты и, если значение не существует, вычислить его, иначе вернуть значение.
Примечание: Haskell реализует это с помощью "указателей на код, которые заменяются значением при первом запуске" - luqui.
Это не строгий вызов по имени, но с разделением / запоминанием результатов.

Call-By-Name - при оценке call-by-name аргументы функции не оцениваются до вызова функции, а скорее подставляются непосредственно в тело функции (с использованием замены, избегающей захвата), а затем оставляются для оценивается всякий раз, когда они появляются в функции. Если аргумент не используется в теле функции, аргумент никогда не оценивается; если он используется несколько раз, он переоценивается каждый раз, когда появляется.
Императивный пример: обратные вызовы
Примечание. Это не является строгим, поскольку позволяет избежать оценки, если она не используется.

Non-Strict = При нестрогом вычислении аргументы функции не оцениваются, если они не используются в действительности при оценке тела функции.
Императивный пример: короткое замыкание
Примечание: _|_ является способом проверки, если функция не является строгой

Так что функция может быть не строгой, но не ленивой. Функция, которая ленива, всегда не является строгой.Call-By-Need частично определяется Call-By-Name, который частично определяется Non-Strict

Отрывок из "Ленивых повелительных языков"

2.1. НЕСТРОЧНАЯ СЕМАНТИКА VS. Ленивая оценка Мы должны сначала прояснить различие между "не строгой семантикой" и "ленивой оценкой". Нестрогая семантика - это те, которые указывают, что выражение не оценивается, пока оно не понадобится примитивной операции. Могут быть различные типы не строгой семантики. Например, нестрогие вызовы процедур не оценивают аргументы, пока их значения не требуются. Конструкторы данных могут иметь не строгую семантику, в которой составные данные собираются из неоцененных частей. Ленивая оценка, также называемая отложенной оценкой, является техникой, обычно используемой для реализации не строгой семантики. В разделе 4 два метода, обычно используемых для реализации отложенной оценки, кратко суммированы.

CALL BY VALUE, CALL BY LAZY И CALL BY NAME "Вызов по значению" - это общее имя, используемое для вызовов процедур со строгой семантикой. При вызове valuelanguages ​​каждый аргумент вызова процедуры оценивается перед выполнением вызова процедуры; затем значение передается в процедуру или в выражение. Другое имя для вызова по значению - "нетерпеливая" оценка. Вызов по значению также известен как оценка "аппликативного порядка", поскольку все аргументы оцениваются до того, как к ним применяется функция."Вызов ленивым" (используя терминологию Уильяма Клингера в [8] ]) - это имя, данное вызовам процедур, которые используют не строгую семантику. В языках с вызовами по ленивому вызову процедуры аргументы не оцениваются, прежде чем подставляются в тело процедуры. Вызов с помощью отложенного вычисления также известен как вычисление "нормального порядка" из-за порядка (от крайнего к внутреннему, слева направо) вычисления выражения."Вызов по имени" - это конкретная реализация вызова с помощью отложенного выражения, используемая в Algol. -60 [18]. Разработчики Algol-60 предполагали, что параметры вызова по имени физически подставляются в тело процедуры, заключаются в круглые скобки и с соответствующими изменениями имени, чтобы избежать конфликтов, прежде чем тело будет оценено.

ЗВОНИТЕ Ленивый VS. CALL BY NEED Вызов по необходимости - это расширение вызова по отложенному принципу, вызванное наблюдением, что отложенная оценка может быть оптимизирована путем запоминания значения заданного выражения с задержкой, после принудительного вызова, так что значение не нужно пересчитывать, если оно понадобится снова. Следовательно, оценка по требованию расширяет вызов по ленивым методам, используя памятку, чтобы избежать необходимости повторной оценки. Фридман и Мудрый были одними из первых призывников оценки потребностей, предлагая "суицидальные суспензии", которые самоуничтожались при первой оценке, заменяя себя своими ценностями.

Answer 5

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

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

из ваших примеров...

f1() || f2()

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

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

int f1() { return 1;}
int f2() { return 2;}

int lazy(int (*cb1)(), int (*cb2)() , int x) {
    if (x == 0)
        return cb1();
    else
        return cb2();
}

int eager(int e1, int e2, int x) {
    if (x == 0)
         return e1;
    else
         return e2;
}

lazy(f1, f2, x);
eager(f1(), f2(), x);

Answer 6

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

Однако в данном конкретном специализированном контексте они могли приобретать различные технические значения. Я не думаю, что вы можете сказать что-то точное и универсальное о том, какая разница между "ленивым" и "нестрогим" может быть в ситуации, когда есть разница.