Что такое вызов по потребности?

Question

Я хочу знать, что такое вызов по требованию.

Хотя я искал в википедии и нашел его здесь: http://en.wikipedia.org/wiki/Evaluation_strategy,, но не смог правильно понять.Если кто-то может объяснить с помощью примера и указать разницу с кол-во по значению, это было бы очень полезно.

Answer 1

Предположим, у нас есть функция

square(x) = x * x

и мы хотим оценить square(1+2).

В по стоимости мы делаем

1. square(1+2)
2. square(3)
3. 3*3
4. 9

В по имени мы делаем

1. square(1+2)
2. (1+2)*(1+2)
3. 3*(1+2)
4. 3*3
5. 9

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

В по требованию мы делаем что-то вроде следующего:

1. square(1+2)
2. let x = 1+2 in x*x
3. let x = 3 in x*x
4. 3*3
5. 9

На шаге 2 вместо копирования аргумента (как в вызове по имени) мы даем ему имя. Затем на шаге 3, когда мы замечаем, что нам нужно значение x, мы оцениваем выражение для x. Только тогда мы заменим.

Кстати, если выражение аргумента приводит к чему-то более сложному, например, к замыканию, может быть больше перемешивания let с, чтобы исключить возможность копирования. Формальные правила несколько сложны для записи.

Обратите внимание, что нам "нужны" значения для аргументов примитивных операций, таких как + и *, но для других функций мы используем подход "name, wait and see". Мы бы сказали, что примитивные арифметические операции являются «строгими». Это зависит от языка, но обычно примитивные операции строги.

Также обратите внимание, что «оценка» по-прежнему означает уменьшение до значения. Вызов функции всегда возвращает значение, а не выражение. (Один из других ответов получил это неправильно.) OTOH, ленивые языки обычно имеют ленивые конструкторы данных, которые могут иметь компоненты, которые оцениваются по необходимости, то есть, когда извлекаются. Таким образом, вы можете получить «бесконечный» список - возвращаемое вами значение представляет собой ленивую структуру данных. Но вызов по требованию против вызова по значению является отдельной проблемой от ленивых против строгих структур данных. Схема имеет ленивые конструкторы данных (потоки), хотя поскольку Схема является вызовом по значению, конструкторы являются синтаксическими формами, а не обычными функциями. И Haskell - это вызов по имени, но у него есть способы определения строгих типов данных.

Если это помогает думать о реализациях, то одна реализация call-by- name заключается в переносе каждого аргумента в thunk; когда аргумент необходим, вы вызываете thunk и используете значение. Одна реализация call-by- need похожа, но эффект запоминается; он выполняет вычисление только один раз, затем сохраняет его и после этого просто возвращает сохраненный ответ.

Answer 2

Представьте себе функцию:

fun add(a, b) {
  return a + b
}

А потом мы называем это:

 add(3 * 2, 4 / 2)

На языке вызовов по имени это будет оцениваться так:

1. a = 3 * 2 = 6
2. b = 4 / 2 = 2
3. return a + b = 6 + 2 = 8

Функция вернет значение 8.

В вызове по необходимости (также называемом ленивым языком) это оценивается так:

1. a = 3 * 2
2. b = 4 / 2
3. return a + b = 3 * 2 + 4 / 2

Функция вернет выражение 3 * 2 + 4 / 2. До сих пор почти не было вычислительных ресурсов. Целое выражение будет вычислено, только если его значение необходимо - скажем, мы хотим напечатать результат.

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

fun takeFirstThree(list) {
  return [list[0], list[1], list[2]]
}

takeFirstThree([0 ... infinity])

Там будет зависать язык вызовов по имени, пытаясь создать список от 0 до бесконечности. Ленивый язык просто вернет [0,1,2].

Answer 3

Простой, но наглядный пример:

function choose(cond, arg1, arg2) {
   if (cond)
      do_something(arg1);
   else
      do_something(arg2);
}

choose(true, 7*0, 7/0);

Теперь предположим, что мы используем страстную стратегию оценки, тогда она будет рассчитывать как 7*0, так и 7/0. Если это стратегия с отложенным вычислением (вызов по необходимости), то она просто отправит выражения 7*0 и 7/0 через функцию, не оценивая их.

Разница? вы ожидаете выполнить do_something(0), потому что первый аргумент используется, хотя на самом деле это зависит от стратегии оценки:

Если язык оценивает с энтузиазмом, то, как было сказано, он сначала оценит 7*0 и 7/0, а что такое 7/0? Ошибка деления на ноль.

Но если стратегия оценки ленива, он увидит, что ему не нужно вычислять деление, он вызовет do_something(0), как мы и ожидали, без ошибок.

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