Почему (постоянные) выражения не оцениваются во время компиляции в Haskell?

Question

Почему (постоянные) выражения не оцениваются во время компиляции в Haskell?

В настоящее время я изучаю Haskell, и есть одна вещь, которая сбивает меня с толку:

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

Исходя из фона C/C++, я привык к такой оптимизации.

В чем причина НЕ выполнять такую оптимизацию (по умолчанию) в Haskell / GHC? Каковы преимущества, если таковые имеются?

data Tree a =
   EmptyTree
 | Node a (Tree a) (Tree a)
 deriving (Show, Read, Eq)

elementToTree :: a -> Tree a
elementToTree x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = elementToTree x
treeInsert x (Node a left right)
  | x == a = Node x left right
  | x < a  = Node a (treeInsert x left) right
  | x > a  = Node a left (treeInsert x right)

treeFromList :: (Ord a) => [a] -> Tree a
treeFromList []     = EmptyTree
treeFromList (x:xs) = treeInsert x (treeFromList xs)

treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
  | x == a = True
  | x < a  = treeElem x left
  | x > a  = treeElem x right

main = do
  let tree = treeFromList [0..90000]
  putStrLn $ show (treeElem 3 tree)

Как это всегда будет печатать True Я ожидаю, что скомпилированная программа напечатает и закроет почти сразу.

9

performance haskell optimization compile-time compile-time-constant

Источник

user1116364 08 окт '13 в 21:51

3 ответа

Другие вопросы по тегам performance haskell optimization compile-time compile-time-constant

user791604 09 окт '13 в 00:35 2013-10-09 00:35 · Answer 1 · 2013-10-09 00:35

Вам может понравиться эта тема Reddit. Компилятор может попытаться сделать это, но это может быть опасно, поскольку константы любого типа могут делать забавные вещи, такие как цикл. Существует как минимум два решения: одно - суперкомпиляция, которая пока недоступна в составе какого-либо компилятора, но вы можете попробовать прототипы от разных исследователей; более практичным является использование Template Haskell, который является механизмом GHC, позволяющим программисту запрашивать какой-либо код для запуска во время компиляции.

user1463507 09 окт '13 в 03:50 2013-10-09 03:50 · Answer 2 · 2013-10-09 03:50

Процесс, о котором вы говорите, называется суперкомпиляцией, и он сложнее, чем вы думаете. Это на самом деле одна из активных тем исследований в области компьютерных наук! Есть некоторые люди, которые пытаются создать такой суперкомпилятор для Haskell (вероятно, на основе GHC, моя память расплывчата), но эта функция не включена в GHC (пока), потому что сопровождающие хотят сократить время компиляции. Вы упоминаете C++ как язык, который делает это - C++ также имеет печально известные времена компиляции!

Ваша альтернатива для Haskell состоит в том, чтобы выполнить эту оптимизацию вручную с помощью шаблона Haskell, который является системой макросов, оцениваемой во время компиляции Haskells.

user839246 08 окт '13 в 22:21 2013-10-08 22:21 · Answer 3 · 2013-10-08 22:21

В этом случае GHC не может быть уверен, что вычисление завершится. Это не вопрос ленивых против строгих, а скорее проблема остановки. Тебе кажется довольно простым сказать, что treeFromlist [0..90000] константа, которая может быть оценена во время компиляции, но как это узнает компилятор? Компилятор может легко оптимизировать [0..90000] до константы, но вы даже не заметите это изменение.