Call-by-name в Скале против ленивой оценки в Haskell?

Question

Hazell's ленивая оценка will never сделать больше шагов оценки, чем ожидаемая оценка.

С другой стороны, оценка Scala по вызову may require больше этапов оценки, чем вызов по значению (если выгоды от короткого замыкания более чем компенсируются стоимостью повторных вычислений).

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

Я предполагаю, что, возможно, язык Haskell указывает, что memoization должен использоваться во время оценки; но в этом случае почему Scala не делает то же самое?

Answer 1

Существует некоторая широта в названиях, данных стратегий оценки, но они дошли до примерно так:

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

  В Scala, вы пишете это как:

  scala> def f(x:=> Int): Int = x + x 
  scala> f({ println("evaluated"); 1 }) 
  evaluated 
  evaluated 
  2 
  

  В Haskell вы не построили в способ сделать это, но вы всегда могли представлять вызов по имени значения как функции типа () -> a. Это немного более размыто, хотя из-за ссылочной прозрачности вы не сможете проверить это так, как это было бы с Scala (и компилятор мог бы оптимизировать «часть» по вашему имени).

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

  В Scala, вы не объявляете ваши аргументы функции лениться, вы делаете заявление ленивый:

  scala> lazy x: Int = { println("evaluated"); 1 } 
  scala> x + x 
  evaluated 
  2 
  

  В Haskell это, как все функции работают по умолчанию.

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

  В Scala это то, как работают функции по умолчанию.

  scala> def f(x: Int): Int = x + x 
  scala> f({ println("evaluated"); 1 }) 
  evaluated 
  2 
  

  В Haskell, вы можете заставить это поведение с шаблонами BANG на аргументы функции:

  ghci> :{ 
  ghci> f :: Int -> Int 
  ghci> f !x = x 
  ghci> :} 
  

Таким образом, если вызов по необходимости (ленивый) делает столько же или меньше оценки (как одно из другие стратегии), зачем использовать что-нибудь еще?

Леновая оценка трудно объяснить, если у вас нет ссылочной прозрачности, потому что тогда вам нужно точно определить , когда оценили ваше ленивое значение. Поскольку Scala построена для взаимодействия с Java, она должна поддерживать обязательное, побочное действие. Как следствие, во многих случаях не a хорошая идея использовать lazy в Scala.

Кроме того, lazy имеет накладные расходы на производительность: вам нужно иметь дополнительное косвенное указание, чтобы проверить, было ли уже оценено значение. В Scala это переводит в кучу больше объектов, что создает еще большую нагрузку на сборщик мусора.

И, наконец, есть случаи, когда ленивая оценка оставляет утечки «пространства». Например, в Haskell сложение большого списка чисел справа путем добавления их вместе является плохой идеей, потому что Haskell будет наращивать эту гигантскую серию ленивых звонков до (+), прежде чем оценивать их (когда на самом деле вам просто нужно, чтобы она .. аккумулятор известным примером космических вопросов, которые вы получите, даже в простых ситуациях является foldr vs foldl vs foldl'

Answer 2

Я не знаю, почему Scala не^{Оказывается, это делает} «правильный» ленивые вычисления - скорее всего, это просто не так просто реализовать, особенно если вы хотите, чтобы язык плавно взаимодействовал с JVM.

Вызов по имени (как вы видели) не эквивалентен ленивой оценке, а замене аргумента типа a аргументом типа () -> a. Такая функция содержит тот же объем информации, что и обычное значение a (типы являются изоморфными), но для фактического получения этого значения вам всегда необходимо применить функцию к аргументу фиктивного аргумента (). Когда вы дважды оцениваете функцию, вы получите twice the same result, но она должна каждый раз рассчитываться заново (с automatically memoising functions is not feasible).

Ленивых вычисления эквивалентны замена аргумента типа a с аргументом типа, который ведет себя как следующий класс OO:

class Lazy<A> { 
    function<A()> computer; 
    option<A> containedValue; 
public: 
    Lazy(function<A()> computer): 
     computer = computer 
    , containerValue = Nothing 
    {} 
    A operator()() { 
    if isNothing(containedValue) { 
     containedValue = Just(computer()); 
    } 
    return fromJust(containedValue); 
    } 
} 

Это по существу только мемоизация-обертка вокруг конкретного вызова по -name-function type. Что не так приятно, так это то, что эта оболочка фундаментально использует побочные эффекты: когда сначала оценивается ленивое значение, вы должны мутировать containedValue, чтобы представить тот факт, что значение теперь известно. Haskell имеет этот механизм, запеченный в основе его времени исполнения, хорошо протестированный для обеспечения безопасности потоков и т. Д. Но на языке, который пытается максимально использовать виртуальную виртуальную машину, это, вероятно, вызовет массивные головные боли, если эти побочные мутации чередуются с явными побочными эффектами. Особенно, потому что действительно интересные приложения ленивости не просто имеют один аргумент функции ленивый (который не будет покупать вас много), но разбросайте ленивые значения по всему позвоночнику глубокой структуры данных. В конце концов, это не просто одна функция задержки, которую вы оцениваете позже, чем ввод ленивой функции, это тотал торрентов вложенных вызовов таких функций (действительно, возможно, бесконечно много!), Поскольку потребляется ленивая структура данных.

Итак, Scala избегает опасностей этого, не делая ничего ленивым по умолчанию, хотя, как говорит Алек, он предлагает ключевое слово lazy, которое в основном добавляет оболочку memoised-function, как указано выше, в значение.

Answer 3

Это может быть полезно и не подходит для комментариев.

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

def foo(x: => Int) = { 
    lazy val _x = x 
    // make sure you only use _x below, not x 
}