LINUX.ORG.RU

Практическая польза зависимых типов

 ,


1

5

Прочитал я тут, что Haskell и теория категорий уже не в моде среди диванных академиков, что будущее за Idris и зависимыми типами. С одной стороны, формальная верификация и доказательство корректности кода - это очень интересно. С другой, непонятно как использовать этот верифицированный код в реальном мире. Вот типичный пример из вики:

data Vect : Nat -> Type -> Type where
  Nil  : Vect 0 a
  (::) : (x : a) -> (xs : Vect n a) -> Vect (n + 1) a

total
pairAdd : Num a => Vect n a -> Vect n a -> Vect n a
pairAdd Nil       Nil       = Nil
pairAdd (x :: xs) (y :: ys) = x + y :: pairAdd xs ys
Утверждается, что благодаря зависимым типам, pairAdd может гарантировать на этапе компиляции, что оба списка будут одной длинны, и это преподносится как большое достижение. Но это значит, что в pairAdd можно передавать только списки, составленные на этапе компиляции, т.к. из произвольного пользовательского ввода никогда не получить значения типа Vect. Получается, что корректность гарантируется только для кода, не принимающего никакой информации извне, а значит не имеющего никакой практической ценности, кроме доказательства собственной корректности.

Правильно ли я понимаю, что зависимые типы нужны только математикам для использования в доказателях теорем, и формально верифицированное ядро ОС или гарантированно корректный веб-сервер на Idris не написать?

P.S. В С++ есть функционально близкая фича в виде параметризированных значениями шаблонов, за 25 лет ей нашлось применение только в std::array, да еще для расчета факториалов при компиляции.

да еще для расчета факториалов при компиляции.

Этого достаточно. ФП предназначено именно для этого. Иногда можно еще вздрочнуть список какой-нибудь. Остальное — для быдла.

anonymous
()

т.к. из произвольного пользовательского ввода никогда не получить значения типа Vect

Чо, совсем никак?

tailgunner ★★★★★
()

Но это значит, что в pairAdd можно передавать только списки, составленные на этапе компиляции,

Я не совсем понимаю как оно работает, но мне кажется оно происходит как-то так, типа если на вход поступает шняга которому этому типу не удовлетворяет, мы просто эксепшн бросаем, ну или там во всяких монадах типа Option или как там обрабатываем. Не?

Debasher ★★★★★
()
Последнее исправление: Debasher (всего исправлений: 2)
Ответ на: комментарий от Debasher

типа если на вход поступает шняга которому этому типу не удовлетворяет, мы просто эксепшн возвращаем, ну или там во всяких монадах Option или как там обрабатываем.

В этом не было бы смысла.

tailgunner ★★★★★
()

Вероятно это может быть полезно при вычислении константных значений в коде. У тебя же бывают в коде констнты? Кроме этого, наверное, больше не для чего.
Однако Идрис, вроде как и не является языком общего назначения. Если его делали только для математиков, то все в порядке, и сравнивать его с С++ - все равно, что сравнивать машину с пирогом.

Aswed ★★★★★
()
Ответ на: комментарий от anonymous

Не смог сдать зачет по ФП и теперь у тебя психологическая травма?

Aswed ★★★★★
()
Ответ на: комментарий от tailgunner

На сколько я понимаю, у Vect длинна списка является частью типа и должна быть определена на этапе компиляции. Т.е. ты не можешь написать функцию, возвращающую список с длинной, неизвестной в компайлтайм, т.е. содержащую произвольный пользовательский ввод.

nonimous
() автор топика
Ответ на: комментарий от tailgunner

Насколько я понимаю, ошибки отлавливаются при трансляции.

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

Debasher ★★★★★
()
Ответ на: комментарий от Aswed

Однако Идрис, вроде как и не является языком общего назначения

Мне казалось, что Идрис как раз является, а вот всякие Агды с Коками — нет.

devsdc ★★
()

Программирование не нужно. Будущее за HoTT.

mix_mix ★★★★★
()

Immutability Considered Harmful

A simple example: Apple's FoundationKit has a NSURLRequest object which can only be initialized with an initialized NSURL instance. NSURL can only be initialized with a URL string. The URL string in the NSURL cannot be changed after initialization and the NSURL cannot be changed after the NSURLRequest.

Now this is ok if you can assume you'll never need to change the URL after it's instantiated or change a NSURLRequest's url after it's instantiated. Unfortunately, these assumptions are wrong.

Consider an Amazon S3 request. Setting up the URL scheme, domain, path and parameters can involve logic specific to the S3 request. Naturally, we'd like something like an S3Request subclass of NSURLRequest that would contain this logic. But as our constructor effectively makes these things immutable by the instance, we can't.

So now we've got all this logic and data which should be handled by the request but can't be. So we can either do the wrong thing by creating giant constructor methods that try to pass in everything, and which invariably make their own false assumptions (e.g. that you'll never need to switch the url scheme from https to http for testing) or we can do the ugly thing by creating a new class that holds all the data which NSURLRequest does but is used to create a NSURLRequest request instance after all it's data is set.

The design decision to use constructors in these frameworks classes has the unseen consequence of limiting our design decisions to a choice between the wrong way or the ugly way and this isn't an isolated case. I've seen many other examples of this problem in the Java and C++ world but I suspect they are particularly common among FP languages which seem to actively encourage this pattern of design.

Final notes: It's not the use of a convenience constructor that is the problem, but that such uses are typically associated with the use of immutable instance state. Some might propose returning a new instance for each mutation as a solution, but this creates even worse code when you consider it potentially has to follow the entire immutable state chain and the consequences for multiple references.

http://www.dekorte.com/blog/2012

anonymous
()
Ответ на: комментарий от anonymous

https://gist.github.com/edwinb/0047a2aff46a0f49c881

Ага, вот это интереснее. Получается, можно откладывать отдельные проверки в рантайм, но полагать их истинными в соответствующей ветке кода. Но все равно не понятно, как это позволит использовать Vect с введенными пользователем значениями.

nonimous
() автор топика
Ответ на: комментарий от nonimous

Точно так же, только proposition в choose будет другой: либо у векторов одинаковая длина и можно использовать pairAdd, либо разная и нельзя.

anonymous
()
Ответ на: комментарий от ovk48

Для твоего, особенного мира, может и правильно, я хз.

anonymous
()
Ответ на: комментарий от anonymous

Но как ты получишь значение типа Vect из пользовательского ввода? Длинна известна в только в рантайме, типы должны быть определены в компайлтайме. В примере он «постулирует» свойство значения (y/=0), а не типа.

nonimous
() автор топика
Ответ на: комментарий от ovk48

Видимо, ему не ндравится выбирать между

the wrong way or the ugly way

anonymous
()
Ответ на: комментарий от nonimous

От пользователя можно получить лист, который затем сконвертировать в вектор с помощью аналога

fromList : ∀ {a} {A : Set a} → (xs : List A) → Vec A (List.length xs)

anonymous
()
Ответ на: комментарий от nonimous

На сколько я понимаю, у Vect длинна списка является частью типа

А насколько я понимаю, ограничение на длину накладывает pairAdd, И это ограничение - не константа, а выражение. Тип Vect не ограничивает количество элементов.

и должна быть определена на этапе компиляции

Нет.

tailgunner ★★★★★
()
Ответ на: комментарий от Debasher

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

Не совсем. Язык заставит тебя написать вход проверки данных, а если не напишешь - выдаст ошибку.

tailgunner ★★★★★
()
Ответ на: комментарий от anonymous

Ну ок.

До, ок, только ты непонел смысл мессаги. Автор как раз сетует, что такой возможности нет.

anonymous
()
Ответ на: комментарий от anonymous

Пусть автор расскажет о реально существующих проблемах, вместо нытья о том, какая ООП параша и его влажных фантазий вида

I suspect

anonymous
()
Ответ на: комментарий от tailgunner

А насколько я понимаю, ограничение на длину накладывает pairAdd, И это ограничение - не константа, а выражение.

И это выражение проверяется в компайлтайме, разве нет? Т.е. если ты написал в коде pairAdd xs ys, он не даст тебе скомпилировать, пока не докажет, что xs : Vect n A и ys : Vect n A для какого-то n.

Тип Vect не ограничивает количество элементов.

Первый аргумент типа - n - как раз указывает размер списка. Это как std::array<T, n>.

nonimous
() автор топика
Ответ на: комментарий от ovk48

copy(...)?

А цепочки наследования ты куда денешь? Что если нам надо переопределить одно поле в классе, уже после создания экземпляров и их копий. У тебя твоя копия унаследует изменения?

anonymous
()
Ответ на: комментарий от nonimous

Ты можешь обращаться с типами практически как с first-class объектами.

buddhist ★★★★★
()
Ответ на: комментарий от tailgunner

Нет.

Да. Ты путаешь зависимые типы с контрактами.

buddhist ★★★★★
()

По поводу того, как это делают в Идрисе: http://eb.host.cs.st-andrews.ac.uk/drafts/eff-tutorial.pdf

В ATS вообще не считается зазорным использовать другой стиль.

// ТС, твоей проблеме соответствует листинг №8 в файле по ссылке

buddhist ★★★★★
()
Последнее исправление: buddhist (всего исправлений: 1)
Ответ на: комментарий от nonimous

И это выражение проверяется в компайлтайме, разве нет?

При компиляции доказывается, что это выражение будет истинным при исполнении. Знать конкретные длины для этого не обязательно.

tailgunner ★★★★★
()
Ответ на: комментарий от anonymous

А цепочки наследования ты куда денешь? Что если нам надо переопределить одно поле в классе, уже после создания экземпляров и их копий. У тебя твоя копия унаследует изменения?

При чем тут цепочки наследования? Мы получаем экземпляр того же самого класса, но с другими значениями некоторых полей. Что тут должно пойти не так?

ovk48 ★★★
()
Ответ на: комментарий от buddhist

Это как раз то, что я спрашивал. Похоже нестыковка между компайлтаймом и рантаймом решается через dependent pairs, о которых я и не знал.

nonimous
() автор топика
Ответ на: комментарий от devsdc

Ну, если является, тогда согласен - не нужно

Aswed ★★★★★
()
Ответ на: комментарий от ovk48

Слушай, то что ты тут поешь — это детский сад. Либо ты за всю жизнь не написал ничего серьезного, либо ты издеваешься. Ты скопируешь объект, хрен с тобой, но при чем тут какая-то сраная копия твоего объекта, если нам нужен подкласс, который должен иметь свои экземпляры? И который может наследовать от другого класса, или нескольких классов? Мы расширяем наше приложение, добавляем новый функционал, по ходу разработки, пишем новые абстракции на основе существующих, это тебе не знакомо, не? Ты галдишь тут про свою сраную копию, это может быть решением в частном случае, в некоторых, частных случаях, но не в общем. Проблема остается. Ты, видимо, кроме дрочева факториалов ничем не занимался, даже не имеешь представления о серьезной разработке и проектировании. Твои рассуждения — это типа того, что «у меня штаны порвались — ну ниче, я мудя закрою, остальное пофигу, жопа у всех, авось одинаковая, а в бане и вовсе портки не нужны»

anonymous
()

Прими уже цианиду, шизофреник.

anonymous
()
Ответ на: комментарий от nonimous

На сколько я понимаю

Ты тупой. У тебя IQ ниже, чем у пня. Так что ты вообще ничего не понимаешь. Проходи мимо, ничтожество.

anonymous
()
Ответ на: комментарий от anonymous

Если будешь так напрягаться, схлопочешь инсульт в молодости. Я в процитированной телеге Декорте не вижу ничего про «Мы расширяем наше приложение, добавляем новый функционал, по ходу разработки, пишем новые абстракции на основе существующих». Я вижу сетования о том, что мы должны создавать урлы с помощью конструкторов, и после создания не можем подменять в них поля в специфических случаях. Если неправильно вижу, открой мне глаза. Ни о чем, кроме того, что он говорит в цитате, я пока спорить не хочу.

ovk48 ★★★
()
Ответ на: комментарий от ovk48

Naturally, we'd like something like an S3Request subclass of NSURLRequest that would contain this logic.

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

anonymous
()
Ответ на: комментарий от ovk48

А ты в курсах, что ты катишь бочку на человека, который создал язык, похлеще смоллтока и руби вместе взятых?

anonymous
()
Ответ на: комментарий от anonymous

Лол, ну если твой моск из

we'd like something like an S3Request subclass of NSURLRequest

делает

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

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

ovk48 ★★★
()
Ответ на: комментарий от anonymous

А ты в курсах, что ты катишь бочку на человека, который создал язык, похлеще смоллтока и руби вместе взятых?

Я знаю, что этот человек придумал прикольный эзотерический язычок, который от прототипа до реального применения хотя бы на уровне смолтолка не дойдет никогда, если им будет заниматься такое же коммьюнити и так же активно. А слово «похлеще» в отношении ЯП я не очень понимаю.

ovk48 ★★★
()

нет, неправильно. фишка верификации в том, что статически верифицируется динамическая система

jtootf ★★★★★
()

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

anonymous
()
Ответ на: комментарий от anonymous

Chuck Norris programs do not accept input.

И производят при этом побочный эффект (УЧННР), который в их случае считается не побочным, а основным.

korvin_ ★★★★★
()

Ты все не так понял. Статически доказывается то, что оба списка будут иметь один и тот же n, но не указывается какой именно, конкретная длина будет определяться динамически. Но какой бы она ни была, для обоих списков она будет одна и та же. С шаблонами С++ тут ничего общего. На C++ такую проверку в принципе на шаблонах не сделать. Как ни странно, на это способны generic'и в явашарпах и полиморфные типы в «обычной» функциональщине.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.