В чем разница между логической структурой и теорией типов? Оба они имеют типы, термины и основаны на лямбда-исчислении с зависимой типизацией. У нас есть Edinburg LF, который основан на исчислении лямбда-пи, однако мне кажется, что здесь есть некоторая тонкая...
Как я понимаю, в компьютерных науках типы данных не основаны на теории множеств из-за таких вещей, как парадокс Рассела, но, как и в реальных языках программирования, мы не можем выразить такие сложные типы данных, как «множество, которое не содержит себя», можем ли мы Скажите, что на практике тип...
Я знаю, как некоторые негативные события могут окончательно быть плохими: data False data Bad a = C (Bad a -> a) selfApp :: Bad a -> a selfApp (x@(C x')) = x' x yc :: (a -> a) -> a yc f = selfApp $ C (\x -> f (selfApp x)) false :: False false = yc id Однако я не уверен, что: все...
У меня есть книга, которая, вдохновленная Принципами математики Рассела (PM) и логическим позитивизмом, пытается формализовать определенную область, определяя аксиомы и выводя из них теоремы. Короче говоря, он пытается сделать для своей области то, что PM пытался сделать для математики. Как и PM,...
Теория типов Мартина-Лёфа использует W-типы для определения индуктивных структур, таких как целые числа, списки и т. Д. Однако, исчисление индуктивных конструкций не использует их одинаково, индуктивные типы там больше похожи на схемы аксиом. Являются ли эти два подхода эквивалентными (они...
Мне интересно, может ли кто-нибудь подсказать мне, почему строгая положительность индуктивных типов данных гарантирует строгую нормализацию. Чтобы было ясно, я вижу, как наличие отрицательных явлений приводит к расхождению, то есть путем определения: data X where Intro : (X->X) -> X мы можем...
Большинство помощников по доказательству имеют формализацию понятия «конечное множество». Эти формализации, однако, сильно отличаются (хотя можно надеяться, что все они по существу эквивалентны!). Что я не понимаю на данном этапе, так это пространство проектирования и каковы плюсы и минусы каждой...
У меня есть язык, на котором типы распакованы по умолчанию, с выводом типов на основе Хиндли-Милнера. Я хотел бы добавить полиморфизм более высокого ранга, в основном для работы с экзистенциальными типами. Я думаю, что понимаю, как проверить эти типы, но я не уверен, что делать при компиляции. В...
У меня есть следующая типизированная теория |- 1_X : X -> X f : A -> B, g : B -> C |- compose(g,f) : A -> C F, f : A -> B |- apply(F,f) : F(A) -> F(B) с уравнениями для всех членов: f : A -> B, g : B -> C, h : C -> D |- compose(h,compose(f,g)) = compose(compose(h,f),g) f...
Одна из немногих вещей, которые мне не нравятся в книге Окасаки о чисто функциональных структурах данных, заключается в том, что его код полон неисчерпаемого сопоставления с образцом. В качестве примера я приведу его реализацию очередей в реальном времени (рефакторинг для устранения ненужных...
Конструктивная теория типов с ее базовой интерпретацией под соответствием Карри Ховарда состоит только из полных вычислимых функций. В литературе некоторые говорили об использовании «теории вычислительных типов» для представления не-завершения в функциональных программах, но в работах, с которыми я...
Мы знаем, что бета-равенство просто типизированных лямбда-терминов разрешимо. Учитывая M, N: σ → τ, разрешимо ли для всех X: σ, MX
Это довольно известный факт, что для получения противоречия из неравенства (например, ) в теории типов Мартина-Лоэфа требуется вселенная.( 0 =1 ) → ⊥(0=1)→⊥(0=1) \to \bot Доказательство также довольно простое - в отсутствие юниверсов мы можем стереть зависимости из любого зависимого типа, чтобы...
В поисках исследовательских работ о системах типов для императивных языков я нахожу решения только для языка с изменяемыми ссылками, но без подлинных императивных структур управления, таких как составные операторы, циклы или условные выражения. Поэтому не ясно, как можно реализовать императивный...
В разделе «Расширенные темы по типам и языкам программирования» в главе, посвященной системам субструктурных типов, упоминается, что «тщательно разработанное» аффинное лямбда-исчисление с рекурсивным комбинатором для списков может вводить только те термины, которые имеют полиномиальное время...
Я нахожусь в ситуации, когда мне нужно показать, что проверка типов решаема для исчисления с зависимым типом, над которым я работаю. До сих пор я был в состоянии доказать, что система сильно нормализуется, и, таким образом, равенство определений разрешимо. Во многих ссылках, которые я читал,...
Скажем, я работаю в теории гомотопического типа, и мои единственные объекты изучения - это условные категории. Эквивалентности здесь даны функторами F:D⟶CF:D⟶CF:{\bf D}\longrightarrow{\bf C} а также G:C⟶DG:C⟶DG:{\bf C}\longrightarrow{\bf D}которые обеспечивают эквивалентность категорий C≃DC≃D{\bf...
Возможно, основным источником проблем с производительностью в Haskell является случай, когда программа по неосторожности создает поток неограниченной глубины - это вызывает как утечку памяти, так и потенциальное переполнение стека при оценке. Классический пример - определение sum = foldr (+) 0в...
Большинство зависимых типизированных систем имеют строгие условия положительности для индуктивных типов. Кто-нибудь знает пример, когда нарушение условия приводит к несогласованности в...
Итак, я читаю немного о разработке, в частности, алгоритмах, основанных на двухцветном исчислении конструкции, и я немного запутался. Я не понимаю, какова цель . Кажется, он идентичен за исключением того, что существует различие между неявными и явными аргументами для функций. В частности, я не...