Разница между Haskell и Idris: отражение времени выполнения/компиляции в типах вселенных

Итак, в Idris вполне допустимо написать следующее.

item : (b : Bool) -> if b then Nat else List Nat
item True  = 42
item False = [1,2,3] // cf. https://www.youtube.com/watch?v=AWeT_G04a0A

Без сигнатуры типа это выглядит как динамически типизированный язык. Но, действительно, Идрис зашифрован. Конкретный тип item b может быть определен только во время выполнения.

Это, конечно, Haskell-программист, говорящий: тип item b в смысле Идриса задается во время компиляции, это if b then Nat ....

Теперь мой вопрос: могу ли я заключить, что в Haskell граница между исполняемой средой и компиляцией выполняется точно между миром значений (False, "foo", 3) и миром типов (Bool, String, Integer), тогда как в Idris граница между исполняемой средой и компилятором проходит через вселенные?

Кроме того, могу ли я предположить, что даже с зависимыми типами в Haskell (используя DataKinds и TypeFamilies, cf. в этой статье) приведенный выше пример невозможно в Haskell, потому что Haskell вопреки Идрису не допускает утечки данных на уровне уровня?

Ответ 1

Да, вы правы, чтобы заметить, что различия между типами и значениями в Idris не совпадают с различием между компиляцией и временем выполнения и компиляцией. Это хорошо. Полезно иметь значения, которые существуют только в compiletime, так же как и в программной логике, мы имеем "переменные призрака", используемые только в спецификациях. Полезно также иметь представления типов во время выполнения, позволяя обобщенное программирование типа данных.

В Haskell DataKinds (и PolyKinds) напишем

type family Cond (b :: Bool)(t :: k)(e :: k) :: k where
  Cond 'True  t e = t
  Cond 'False t e = e

и в недалеком будущем мы сможем написать

item :: pi (b :: Bool) -> Cond b Int [Int]
item True  = 42
item False = [1,2,3]

но до тех пор, пока эта технология не будет реализована, мы должны делать с однопользовательскими подлогами зависимых типов функций, например:

data Booly :: Bool -> * where
  Truey  :: Booly 'True
  Falsey :: Booly 'False

item :: forall b. Booly b -> Cond b Int [Int]
item Truey  = 42
item Falsey = [1,2,3]

Вы можете получить довольно далеко с такой фальшивкой, но все это будет намного легче, если бы у нас была настоящая вещь.

Реально, план Haskell заключается в том, чтобы поддерживать и разделять forall и pi, поддерживая параметрический и специальный полиморфизм, соответственно. Lambdas и приложения, которые идут с forall, все равно могут быть стерты при генерации кода времени выполнения, как и сейчас, но сохраняются те для pi. Было бы также иметь смысл абстракции типа времени pi x :: * -> ... и выбросить в сложную мусорную корзину сложность, равную Data.Typeable, в мусорную корзину.

Ответ 2

Теперь мой вопрос: могу ли я сделать вывод, что в Хаскелле граница между runtime и compiletime работает точно между миром значений (False, "foo", 3) и мира типов (Bool, String, Integer), тогда как в Идрисе граница между временем выполнения и compiletime проходит через вселенные?

~~Идрис компилируется в Epic~~ (ОБНОВЛЕНИЕ: нет, он больше не компилируется в Epis как Spearman говорит в комментарии ниже):

Нет семантической проверки, кроме как видеть, находятся ли имена в области - это предполагается, что язык более высокого уровня будет выполнен typechecking, и в любом случае Epic не должен делать никаких предположений о системы более высокого уровня или любых примененных вами преобразований. Аннотации типа требуются, но они дают только подсказки компилятор (я могу это изменить).

Таким образом, типы не имеют значения денотационно, т.е. значение термина не зависит от его типа. Кроме того, некоторые вещи уровня ценности могут быть стерты, например. в Vect n A (где Vect - тип списков со статически известной длиной) n (длина) можно стереть, потому что

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

Дело в том, что pi в Идрисе действует для типов почти так же, как forall в Haskell: они оба параметрические (хотя эти параметрические различия в этом случае). Компилятор может использовать типы для оптимизации кода, но в обоих языках поток управления не зависит от типов, т.е. Вы не можете сказать if A == Int then ... else ... (хотя, если A находится в канонической форме, то вы знаете, статически ли он Int или нет и, следовательно, может написать A == Int, но это все равно не влияет на поток управления, потому что все решения выполняются до выполнения), Конкретный тип item b просто не имеет значения во время выполнения.

Однако, поскольку pigworker говорит, что он не обязательно должен быть параметрическим по типам. Как и не обязательно быть непараметрическим по значениям. Тип-уровень - уровень значения и параметрический - непараметрический - полностью ортогональные дихотомии. Подробнее см. этот.

Итак, Haskell и Idris отличаются друг от друга тем, как они обрабатывают вещи уровня ценности во время выполнения/компилируют контент (потому что в Idris вы можете пометить аргумент ., чтобы сделать его стираемым), но они обрабатывают типы примерно одинаково.