Стремится против ленивого Хаскелла. Возможны ли бесконечные списки в нетерпеливых языках? - PullRequest
5 голосов
/ 30 декабря 2011

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

http://csg.csail.mit.edu/pubs/haskell.html

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

Ключевым моментом здесь является то, что «у нас есть механизмы для восстановления, если наша программа слишком энергичная» Что это за механизм? Как они допускают бесконечные структуры данных и другие аспекты ленивых вычислений, которые, как мне показалось, невозможны на нетерпеливом языке?

1 Ответ

11 голосов
/ 30 декабря 2011

Это не совсем так: вы можете оценить термины на Haskell с нетерпением , если докажете, что они не расходятся .

Например, когда вы видите f x, вы можете сначала выполнить до 1000 шагов x (остановка при достижении WHNF (нормальная форма слабой головы) или ошибка), а затем передать его на f - семантика сохраняется, но если вы думаете, что x будет оцениваться, то вы можете организовать это заранее как оптимизацию.

Если x = fix id, он просто сдастся после 1000 шагов и никуда не денется. Если x = undefined, это вызовет ошибку и сдастся (восстанавливая исходный блок и передавая его f ). И так далее.

Если x = [1..], то это может привести к уменьшению его до 1 : 2 : 3 : ... : 999 : 1000 : [1001..], достижению предела и остановке на нем, передавая результат в f .

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

Конечно, недостатком является то, что если x окажется действительно дорогим вычислением, для которого f использует только половину, вы потратите 1000 шагов сокращения, тратя время впустую. А в случае [1..] вы можете использовать много памяти для хранения списка; если f обрабатывает список по одному элементу за раз, каждый раз отбрасывая голову, тогда вы тратите впустую память. Вот почему это сложно:)

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

...