Нетерпеливый против ленивого Haskell. Бесконечные списки возможны на языках нетерпеливых?

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

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

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

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


lazy-evaluation infinite eager haskell
person TheIronKnuckle    schedule 30.12.2011    source источник
comment
Страница, на которую вы ссылаетесь, кажется, дает обзор механизмов. Вы хотели уточнить что-то конкретное?   -  person C. A. McCann    schedule 30.12.2011
comment
Да, я просто понял это, когда продолжил читать. Надо было сначала прочитать все это. Я чувствую себя дураком: p для чего нужна процедура SO, когда кто-то делает такую ​​ошибку? Стоит ли удалить вопрос?   -  person TheIronKnuckle    schedule 30.12.2011
comment
Обычно нормально закрывать вопрос. Ответ ehird в любом случае полезен, и лучше ошибиться в сторону сохранения информации.   -  person C. A. McCann    schedule 30.12.2011
comment
Я думаю, что такой вопрос имеет ценность, поскольку связанная страница довольно длинна и содержит много деталей; краткое изложение того, как это работает, - это хорошо.   -  person ehird    schedule 30.12.2011
comment
Вы можете создавать бесконечные структуры данных на интересном языке. В качестве глупого примера вы можете рассматривать код Haskell, скомпилированный на C, как программу на C. Если программа на Haskell содержит бесконечную структуру, то и программа на C.   -  person redxaxder    schedule 30.12.2011

Ответы (1)


arrow_upward
11
arrow_downward

Это не совсем так: вы можете жадно оценивать термины 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 обрабатывает список по одному элементу, каждый раз отбрасывая заголовок, вы тратите память. Вот почему это сложно :)

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

person ehird    schedule 30.12.2011