Являются ли «длинные» вызовы переписанными как постоянные ints GHC?

Просто случайное размышление, глядя на мои многочисленные звонки length, мне приходит в голову, что компилятор может рассказать длину любого списка благодаря неизменяемости и ссылочной прозрачности (даже если новые списки concat -ed из существующих известных списков/кодовые пути). Тогда он, скорее всего, заменит все length l «звонки» с фактическим int на какой-то стадии при генерации низкоуровневого кода, не так ли?Являются ли «длинные» вызовы переписанными как постоянные ints GHC?

Удивление, действительно ли это происходит, или я что-то упустил в своей новизне о чистых функциональных языках/компиляторе.

источник

2016-12-04 metaleap

Show/Сообщите нам подробнее о вашем коде. Постоянны ли списки? – ThreeFx

Просто осознание моего было таким глупым вопросом (время разрыва, я думаю), конечно, многие из моих списков - это строки, загруженные из IO и полностью динамические. Я должен предположить, что проект компилятора с 25-летним стажем будет содержать известные длины постоянных списков. – metaleap

Это не имеет никакого отношения к 25-летнему компилятору - это зависит от реализации используемой структуры данных. Списки не сохраняют информацию о длине, и поэтому у вас нет постоянной длины со списками. – ThreeFx

Я считаю, что вопрос спрашивает, поворачивает ли GHC, например, length [1,2,3] в 3 во время компиляции. GHC 8.0.1 является первой версией GHC для этой оптимизации (по крайней мере, среди версий, которые я установил).

Теперь давайте обратимся ко второй части вашего вопроса. Давайте дадим дату первой бета-версии GHC из Википедии в качестве даты начала GHC: 1 апреля 1991 года. GHC 8.0.1 был выпущен в мае 2016 года. Таким образом, похоже, что ваша теория о том, что это оптимизация, которая характеризует В этом случае проверяются проекты компиляторов на 25+ лет.

источник

2016-12-04 14:46:15

WIll это также делает это для строк/списков, считанных из файлов, которые не известны во время компиляции? – ThreeFx

@Reid Barton хорошо подходит для меня, а затем с 8.0.1! Случай с «списками» был действительно о множестве строковой обработки со множеством строковых констант, разбросанных вокруг (предопределенные форматы для генерации и т. Д.) --- недостаточно высокого уровня, чтобы использовать расширенные пакеты обработки текста, но достаточно запутанный, что я заметил, m делает так много «длин» на константах или 'concat'-константах, а также в глубоких рекурсиях и для неизвестных номеров файлов in/out и т. д., что заставило меня задуматься о том, насколько постоянны мои константы на этом этапе» .. – metaleap

@ThreeFx вряд ли теперь не так ли? Такие интеллектуальные способности должны быть материалом следующей вещи после квантовых вычислений. – metaleap

Все зависит от используемой структуры данных. Обычные списки простые односвязаны списки:

data List a = Nil | Cons a (List a)

Вы можете себе представить, length определяются следующим образом:

length []  = 0 
length (x:xs) = 1 + length xs

Это требует O (N) времени для запуска, так как нет более быстрого способа, чтобы определить длина этой структуры.

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

Использование пакета Data.Vector вы получите O (1) вызовы длины, но теряет некоторые свойства списка.

источник

2016-12-04 14:32:35 ThreeFx

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

Являются ли «длинные» вызовы переписанными как постоянные ints GHC?

ответ

Смежные вопросы