Хаскелл: Как отличается нестрогий и ленивый?

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

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

Нелинейная защита:

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

const1 x = 1

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

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

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

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

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

- Haskell Wiki: Lavy vs non-strict

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

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

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

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

Lazy Def:

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

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

- Haskell Wiki: Lavy vs non-strict

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

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

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

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

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

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

f1() || f2()

С#, 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: yield (С#)

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? Сокращения, похоже, соответствуют определению ленивого.
  • Значит ли ленивый thunks и нестрогий всегда означает частичную оценку? Это просто обобщение?
  • Являются ли следующие императивные понятия "ленивыми", "не строгими", "оба" или "нет"?
    • Короткое замыкание
    • Использование yield
    • Передача обратных вызовов для задержки или предотвращения выполнения
  • Является ленивым подмножеством нестрогим или наоборот, или они являются взаимоисключающими. Например, возможно ли быть нестрогим, не будучи ленивым или ленивым, не будучи нестрогим?
  • Не строгость Хаскелла достигается лень?

Спасибо вам!

Ответы

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

Это началось как обновление, но оно начало затягиваться.

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

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

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

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

Отрывок из "Ленивые императивные языки"

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

ВЫЗОВ ИЗ ЗНАЧЕНИЯ, ВЫЗОВ ЗА ЛАЗИЕЙ И ВЫЗОВОМ НА ИМЯ "Вызов по значению" - это общее имя, используемое для вызовов процедур со строгой семантикой. В вызове по valuelanguages, каждый аргумент вызова процедуры оценивается перед вызовом процедуры; значение затем передается процедуры или охватывающего выражения. Другое имя для вызова по значению "нетерпеливая" оценка. Значение по стоимости также известно как "прикладной порядок", оценки, поскольку все аргументы вычисляются до того, как функция применительно к ним. "Звонок ленивым" (с использованием терминологии Уильяма Клингера в [8]) - это имя, присвоенное процедурным вызовам, которые семантика. В языках с вызовом с помощью ленивых процедур аргументы не оцениваются перед заменой в процедуру тело. Звонок с ленивой оценкой также известен как "нормальный порядок" из-за заказа (от внешнего к самому внутреннему, слева справа) оценки выражения. "Вызов по имени" является особая реализация вызова ленивым, используемая в Алгол-60 [18]. дизайнеры "Алгол-60" предполагали, что параметры вызова по имени физически заменяемые в корпус процедуры, заключенные в круглые скобки и с подходящими изменениями имени, чтобы избежать конфликтов, прежде чем тело оценены.

ЗВОНОК ЛАЗИ VS. ЗВОНОК НУЖНО Звонок по необходимости - это расширение вызова ленивым, вызванное замечанием о том, что ленивый оценка может быть оптимизирована путем запоминания значения данного замедленное выражение, однажды принудительное, так что значение не обязательно должно быть пересчитывается, если это необходимо снова. Позвоните по необходимости, поэтому продлевает вызов ленивыми методами, используя мемуаризацию, чтобы избежать необходимость повторной оценки. Фридман и Мудрый были среди ранние пословицы вызова по оценке необходимости, предлагая "суицидальные приостановки", которые саморазрушились, когда они были впервые оценены, заменяя себя своими значениями.

Ответ 5

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

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