Интересно, типа.

[migmit]

Вот есть, типа, такая типа штука, называется типа "зависимые типы". Когда сам тип содержит в себе значение. И два таких типа будут (типа) совместимы, если эти значения равны. А поскольку значения будут известны только в рантайме, приходится давать доказательство того, что значения таки равны.

А вот во всяких джавах с сиплюсплюсами равенств как минимум два. Не помню точно, как они называются, но, в общем, равенство по ссылке и по значению. Первое сильнее второго. То есть, если какие-то штуки лежат в одном и том же месте, то это одна и та же штука, и, значит, они одинаковые. Но если они одинаковые — это ещё не значит, что они лежат в одном и том же месте.

В агде, если мой эклер меня не обманывает, требуется равенство по значению. А есть ли зависимые типы с равенством по ссылке? То есть, для того, чтобы Vector n Int был тем же типом, что и Vector m Int нужно не только n=m, нужно, чтобы n и m были одной и той же переменной.

Такое где-нибудь есть?

Update: подсказали, что это, вроде, называется "path dependent types".

Comments

[krlz.livejournal.com]

В функциональных языках не может в принципе быть равенства по ссылке. У нас же referential transparency.

[deni-ok.livejournal.com]

Это сузит пространство возможностей.

(++) : Vec A n -> Vec A m -> Vec A (n + m)

Конкатенируя Vec A 3 и Vec A 4 мы получим Vec A 7, только эта семёрка гарантировано не будет ссылочно равна никакой другой семёрке.

[nealar.livejournal.com]

Vector (IORef n) Int ?

Зависимые типы

[livejournal.livejournal.com]

User nponeccop referenced to your post from Зависимые типы (http://nponeccop.livejournal.com/316607.html) saying: [...] В связи с [...]

[zhengxi.livejournal.com]

внутренние классы в скале ?

[migmit.livejournal.com]

Это какой-то сферический язык в вакууме. В Хаскеле, например, есть IORef-ы.

[migmit.livejournal.com]

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

Я имею в виду плюшки такого типа:

data Ord a = Ord {compare :: a -> a -> Ordering}
data Set a (Ord a) = какая-то реализация
ordInt :: Ord Int
ordInt = Ord {compare = compareInt#}
a :: Set a ordInt
...
ordIntFake :: Ord Int
ordIntFake = Ord {compare = flip compare ordInt}

Ни в каком случае a не будет воспринято как Set a ordIntFake. Система классов и инстансов в Хаскеле этого не обеспечивает — можно описать разные инстансы в разных модулях и закрутить всё так, что они не станут друг другу мешать; в результате вполне можно получить, например, Set, содержащий какое-то значение несколько раз. Если же запихивать значение внутрь Set-а, то будет сложно делать union, например. А так — всё хорошо.

[migmit.livejournal.com]

Не понял, это имеется в виду какой-то существующий язык?

[migmit.livejournal.com]

Ха, забавно, очень похоже на правду.

[krlz.livejournal.com]

Ну да, но есть же Eq IORef a, так что сравнения по ссылкам все равно нет.

[krlz.livejournal.com]

Имеются ввиду path dependent types? Так это просто разновидность dependent types.

[migmit.livejournal.com]

Не понял. Это и есть сравнение по ссылкам.

[migmit.livejournal.com]

Так я не спорю, что разновидность.

[some41.livejournal.com]

даже без IORef есть stable names: http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-Mem-StableName.html

[krlz.livejournal.com]

Ну так на уровне типов это работать то не будет.

[some41.livejournal.com]

что именно не будет работать? использование stable name в типе в хаскеле? так в хаскеле вообще dependent types нет

[migmit.livejournal.com]

Хотя почитал тут — больше похоже на такие расширенные existentials, чем на dependent types.

[jakobz.livejournal.com]

Ну что-то типа этого есть: http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-Mem-StableName.html

Глупо было бы не иметь бесплатного "точно равно, т.к. физически указатели на один и тот же объект".

[krlz.livejournal.com]

Там можно писать что-то вроде:

val x = ...
val y: x.T = ...

те мы можем ссылаться на type member-ы pure value-ов, и тип у нас реально зависит от значения

[krlz.livejournal.com]

Но это не полноценные dependent type-ы как в агде конечно. Реально у нас есть только dependent function types, а dependent products на скале не выразить (я не знаю как по крайней мере).

def xyz(a: BBB): a.T = {...}

[nealar.livejournal.com]

Это имеется в виду несуществующий тип Vector. Который надо привинтить к существующему языку.

[akuklev.livejournal.com]

Это называется runtime path dependent types. Могут быть реализованы в языках с зависимыми типами и individual types aka entities, т.е. “ран-тайм метками, равными только самим себе: совпасть должно не только место определения в коде, но и тред/момент создания”. Нужен оператор new, создающий такую метку, и процедуры использующие этот оператор — уже не чистые функции, результат их повторного выполнения с теми же аргументами отличается от исходного. Ещё можно красиво обобщить монады State и IO, так, чтобы там допустимо было использовать оператор new, тогда и только тогда, когда созданные объекты пихаются в состояние или вывод, а возвращаемое значение при одинаковых аргуменах одинаковое.

Бывают еще nominal path dependent types, там для равенства совпасть должно лишь место определения в коде, они эмулируются через экзистенциальные типы.

[migmit.livejournal.com]

Не от значения, а от ссылки. Потому что, если я правильно понимаю, возможно, что x == y, но x.T и y.T не совместимы.

[migmit.livejournal.com]

> Это называется runtime path dependent types.

Э-э-э, почему runtime-то?

> Могут быть реализованы в языках с зависимыми типами

Defeats the purpose.

> они эмулируются через экзистенциальные типы.

КАК?

[migmit.livejournal.com]

То есть, если я правильно понял, происходит примерно следующее: для каждой переменной x создаётся новый тип x.type, который наследует все поля и методы того типа, который для x объявлен; внутренние типы становятся его членами.