Вывод типа мешает ссылочной прозрачности

Question

Какое точное обещание / гарантию предоставляет язык Haskell в отношении прозрачности ссылок? По крайней мере, в отчете на Haskell это понятие не упоминается.

Рассмотрим выражение

(7^7^7`mod`5`mod`2)

И я хочу знать, равно ли это выражение 1. Для моей безопасности я выполню это дважды:

( (7^7^7`mod`5`mod`2)==1, [False,True]!!(7^7^7`mod`5`mod`2) )

который сейчас дает (True,False) с GHCi 7.4.1.

Очевидно, это выражение теперь является непрозрачным. Как я могу определить, является ли программа объектом такого поведения? Я могу залить программу :: все кончено, но это не делает его очень читабельным. Есть ли какой-то другой класс программ на Haskell между которыми я скучаю? То есть между полностью аннотированным и аннотированным?

(Помимо единственно связанного вопроса, который я нашел на SO, должно быть что-то еще по этому поводу)

Answer 1

Проблема в перегрузке, которая действительно нарушает прозрачность ссылок. Вы понятия не имеете, что-то вроде (+) делает в Хаскеле; это зависит от типа.

Когда числовой тип не ограничен в программе на Haskell, компилятор использует тип по умолчанию, чтобы выбрать подходящий тип. Это для удобства и, как правило, не вызывает никаких сюрпризов. Но в этом случае это привело к сюрпризу. В GHC вы можете использовать -fwarn-type-defaults чтобы увидеть, когда компилятор использовал значение по умолчанию, чтобы выбрать тип для вас. Вы также можете добавить строку default () на ваш модуль, чтобы остановить все по умолчанию.

Answer 2

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

Сессия GHCi:

> class C a where num :: a
> instance C Int    where num = 0
> instance C Double where num = 1
> num + length []  -- length returns an Int
0
> num + 0          -- GHCi defaults to Double for some reason
1.0

Это выглядит как нарушение ссылочной прозрачности, так как length [] а также 0 должно быть равным, но под капотом это num это используется в разных типах.

Также,

> "" == []
True
> [] == [1]
False
> "" == [1]
*** Type error

где можно было ожидать False в последней строке.

Поэтому я думаю, что ссылочная прозрачность имеет место только тогда, когда указаны точные типы для разрешения полиморфизма. Приложение с явным параметром типа, как System F, позволило бы всегда заменять переменную ее определением без изменения семантики: насколько я понимаю, GHC внутренне делает именно это во время оптимизации, чтобы гарантировать, что семантика не затронута. Действительно, GHC Core имеет явные аргументы типа, которые передаются.

Answer 3

Я думал о чем-то, что могло бы помочь прояснить ситуацию...

Выражение mod (7^7^7) 5 имеет тип Integral a так что есть два распространенных способа преобразовать его в Int:

1. Выполните всю арифметику, используя Integer операции и типы, а затем преобразовать результат в Int,
2. Выполните всю арифметику, используя Int операции.

Если выражение используется в Int контекст Haskell выполнит метод #2. Если вы хотите заставить Haskell использовать #1, вы должны написать:

fromInteger (mod (7^7^7) 5)

Это обеспечит выполнение всех арифметических операций с использованием Integer операции и виды.

Когда вы вводите выражение в REPL ghci, правила по умолчанию вводят выражение как IntegerТаким образом, метод № 1 был использован. Когда вы используете выражение с !! Оператор это было напечатано как Int, так что это было вычислено с помощью метода #2.

Мой оригинальный ответ:

В Haskell оценка выражения как

(7^7^7`mod`5`mod`2)

полностью зависит от которого Integral используется экземпляр, и это то, что каждый программист на Haskell учится принимать.

Второе, что должен знать каждый программист (на любом языке), - это то, что числовые операции подвержены переполнению, недостаточному значению, потере точности и т. Д., И, следовательно, законы арифметики могут не всегда выполняться. Например, x+1 > x не всегда верно; сложение и кратность действительных чисел не всегда ассоциативны; закон распределения не всегда имеет место; и т. д. Когда вы создаете переполненное выражение, вы входите в область неопределенного поведения.

Кроме того, в этом конкретном случае есть более эффективные способы оценки этого выражения, которое сохраняет больше нашего ожидания того, каким должен быть результат. В частности, если вы хотите эффективно и точно вычислить a^b mod c, вам следует использовать алгоритм "power mod".

Обновление: запустите следующую программу, чтобы увидеть, как выбор Integral экземпляр влияет на то, что выражение оценивает:

import Data.Int
import Data.Word
import Data.LargeWord -- cabal install largeword

expr :: Integral a => a
expr = (7^e `mod` 5)
  where e = 823543 :: Int

main :: IO ()
main = do
  putStrLn $ "as an Integer: " ++ show (expr :: Integer)
  putStrLn $ "as an Int64:   " ++ show (expr :: Int64)
  putStrLn $ "as an Int:     " ++ show (expr :: Int)
  putStrLn $ "as an Int32:   " ++ show (expr :: Int32)
  putStrLn $ "as an Int16:   " ++ show (expr :: Int16)
  putStrLn $ "as a Word8:    " ++ show (expr :: Word8)
  putStrLn $ "as a Word16:   " ++ show (expr :: Word16)
  putStrLn $ "as a Word32:   " ++ show (expr :: Word32)
  putStrLn $ "as a Word128:  " ++ show (expr :: Word128)
  putStrLn $ "as a Word192:  " ++ show (expr :: Word192)
  putStrLn $ "as a Word224:  " ++ show (expr :: Word224)
  putStrLn $ "as a Word256:  " ++ show (expr :: Word256)

и вывод (скомпилированный с GHC 7.8.3 (64-бит):

as an Integer: 3
as an Int64:   2
as an Int:     2
as an Int32:   3
as an Int16:   3
as a Word8:    4
as a Word16:   3
as a Word32:   3
as a Word128:  4
as a Word192:  0
as a Word224:  2
as a Word256:  1

Answer 4

Какое точное обещание / гарантию предоставляет язык Haskell в отношении прозрачности ссылок? По крайней мере, в отчете на Haskell это понятие не упоминается.

Haskell не дает точного обещания или гарантии. Там существует много функций, таких как unsafePerformIO или же traceShow которые не являются ссылочно прозрачными. Расширение под названием Safe Haskell, однако, дает следующее обещание:

Ссылочная прозрачность - функции на безопасном языке являются детерминированными, их оценка не вызовет никаких побочных эффектов. Функции в монаде IO все еще разрешены и ведут себя как обычно. Любая чистая функция, хотя и в соответствии с ее типом, гарантированно будет действительно чистой. Это свойство позволяет пользователю безопасного языка доверять типам. Это означает, например, что функция unsafePerformIO:: IO a -> запрещена на безопасном языке.

За пределами этого Haskell дает неофициальное обещание: библиотеки Prelude и базовые библиотеки, как правило, не имеют побочных эффектов, а программисты на Haskell склонны маркировать вещи побочными эффектами как таковыми.

Очевидно, это выражение теперь является непрозрачным. Как я могу определить, является ли программа объектом такого поведения? Я могу залить программу с помощью:: во всем, но это не делает ее очень удобочитаемой. Есть ли какой-то другой класс программ на Haskell между которыми я скучаю? То есть между полностью аннотированным и аннотированным?

Как уже говорили другие, проблема возникает из этого поведения:

Prelude> ( (7^7^7`mod`5`mod`2)==1, [False,True]!!(7^7^7`mod`5`mod`2) )
(True,False)
Prelude> 7^7^7`mod`5`mod`2 :: Integer
1
Prelude> 7^7^7`mod`5`mod`2 :: Int
0

Это происходит потому, что 7^7^7 это огромное число (около 700000 десятичных цифр), которое легко переполняет 64-битную Int типа, но проблема не будет воспроизводиться на 32-битных системах:

Prelude> :m + Data.Int
Prelude Data.Int> 7^7^7 :: Int64
-3568518334133427593
Prelude Data.Int> 7^7^7 :: Int32
1602364023
Prelude Data.Int> 7^7^7 :: Int16
8823

При использовании rem (7^7^7) 5 остаток для Int64 будет указан как -3 но так как -3 эквивалентно +2 по модулю 5, mod сообщает +2.

Integer Ответ используется слева из-за правил по умолчанию для Integral классы; специфичная для платформы Int Тип используется справа из-за типа (!!) :: [a] -> Int -> a, Если вы используете соответствующий оператор индексации для Integral a вместо этого вы получаете что-то последовательное:

Prelude> :m + Data.List
Prelude Data.List> ((7^7^7`mod`5`mod`2) == 1, genericIndex [False,True] (7^7^7`mod`5`mod`2))
(True,True)

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

Answer 5

Другой тип был выбран, потому что !! требует Int, Полное вычисление теперь использует Int вместо Integer,

λ> ( (7^7^7`mod`5`mod`2 :: Int)==1, [False,True]!!(7^7^7`mod`5`mod`2) )
(False,False)

Answer 6

Как вы думаете, это имеет отношение к ссылочной прозрачности? Ваше использование 7, ^, mod, 5, 2, а также == Да, но я не понимаю, почему вы думаете, что этот факт делает Хаскель непрозрачным. Часто применение одной и той же функции к разным аргументам приводит к разным результатам, в конце концов!

Ссылочная прозрачность имеет отношение к этому выражению:

let x :: Int = 7^7^7`mod`5`mod`2 in (x == 1, [False, True] !! x)

x здесь одно значение, и всегда должно иметь одно и то же значение.

Напротив, если вы говорите:

let x :: forall a. Num a => a; x = 7^7^7`mod`5`mod`2 in (x == 1, [False, True] !! x)

(или используйте выражение inline, которое эквивалентно), x теперь является функцией и может возвращать различные значения в зависимости от Num аргумент, который вы предоставляете ему. Вы могли бы также жаловаться, что let f = (+1) in map f [1, 2, 3] является [2, 3, 4], но let f = (+3) in map f [1, 2, 3] является [4, 5, 6] а затем сказать "Haskell дает разные значения для map f [1, 2, 3] в зависимости от контекста, поэтому это непрозрачно "!

Answer 7

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

Пример из "Истории Хаскелла":
Рассмотрим функцию genericLength из Data.List

genericLength :: Num a => [b] -> a

И рассмотрим функцию:

f xs = (len, len) where len = genericLength xs

len имеет тип Num a => a и без ограничения мономорфизма его можно вычислить дважды.

Обратите внимание, что в этом случае типы обоих выражений одинаковы. Результаты тоже есть, но замена не всегда возможна.