Является ли система типов Haskell формально эквивалентной системе Java? [закрыто]

66

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

GlenPeterson
источник
4
Мне тоже любопытно услышать, как теоретики с категоричными ответами отвечают на этот вопрос; хотя я сомневаюсь, что я это особенно пойму, я все еще заинтересован в детализации этого. Я склоняюсь к тому, что я прочитал, что система типов HM позволяет компилятору знать тонну о том, что делает ваш код, поэтому он способен выводить типы так же, как и давать так много гарантий о поведении. Но это только мой внутренний инстинкт, и я уверен, что есть и другие вещи, о которых я совершенно не подозреваю.
Джимми Хоффа
1
Это отличный вопрос - пора твитнуть его последователям для великих дебатов на Haskell / JVM!
Мартейн Вербург
6
@ m3th0dman: Scala поддерживает те же функции высшего порядка, что и Java. В Scala функции первого класса просто представлены как экземпляры абстрактных классов с помощью одного абстрактного метода, как Java. Конечно, у Scala есть синтаксический сахар для определения этих функций, и у него есть богатая стандартная библиотека как предопределенных типов функций, так и методов, которые принимают функции, но с точки зрения системы типов , о которой идет речь в этом вопросе, нет никакой разницы , Итак, если Scala может это сделать, то и Java тоже может, и на самом деле есть библиотеки FP для Java, вдохновленные Haskell.
Йорг W Mittag
2
@ m3th0dman: Вопрос не в этом.
Фил
7
@ m3th0dman Они совершенно обычные типы. В списках нет ничего особенного, кроме синактических тонкостей. Вы можете легко определить свой собственный алгебраический тип данных, который эквивалентен встроенному типу списка, за исключением буквального синтаксиса и имен конструкторов.
sepp2k

Ответы:

63

(«Java», как здесь используется, определяется как стандарт Java SE 7 ; «Haskell», как здесь используется, определяется как стандарт Haskell 2010 ).

Вещи, которые есть в системе типов Java, но нет в Haskell:

  • номинальный полиморфизм подтипа
  • частичная информация о типе среды выполнения

Вещи, которые есть в системе типов Haskell, а в Java - нет:

  • ограниченный специальный полиморфизм
    • порождает "основанный на ограничениях" полиморфизм подтипа
  • параметрический полиморфизм высшего рода
  • основной тип

РЕДАКТИРОВАТЬ:

Примеры каждого из пунктов, перечисленных выше:

Уникально для Java (по сравнению с Haskell)

Номинальный подтип полиморфизма

/* declare explicit subtypes (limited multiple inheritance is allowed) */
abstract class MyList extends AbstractList<String> implements RandomAccess {

    /* specify a type's additional initialization requirements */
    public MyList(elem1: String) {
        super() /* explicit call to a supertype's implementation */
        this.add(elem1) /* might be overridden in a subtype of this type */
    }

}

/* use a type as one of its supertypes (implicit upcasting) */
List<String> l = new ArrayList<>() /* some inference is available for generics */

Частичная информация о типе среды выполнения

/* find the outermost actual type of a value at runtime */
Class<?> c = l.getClass // will be 'java.util.ArrayList'

/* query the relationship between runtime and compile-time types */
Boolean b = l instanceOf MyList // will be 'false'

Уникально для Haskell (по сравнению с Java)

Ограниченный специальный полиморфизм

-- declare a parametrized bound
class A t where
  -- provide a function via this bound
  tInt :: t Int
  -- require other bounds within the functions provided by this bound
  mtInt :: Monad m => m (t Int)
  mtInt = return tInt -- define bound-provided functions via other bound-provided functions

-- fullfill a bound
instance A Maybe where
  tInt = Just 5
  mtInt = return Nothing -- override defaults

-- require exactly the bounds you need (ideally)
tString :: (Functor t, A t) => t String
tString = fmap show tInt -- use bounds that are implied by a concrete type (e.g., "Show Int")

«Основанный на ограничениях» полиморфизм подтипа (основанный на ограниченном специальном полиморфизме)

-- declare that a bound implies other bounds (introduce a subbound)
class (A t, Applicative t) => B t where -- bounds don't have to provide functions

-- use multiple bounds (intersection types in the context, union types in the full type)
mtString :: (Monad m, B t) => m (t String)
mtString = return mtInt -- use a bound that is implied by another bound (implicit upcasting)

optString :: Maybe String
optString = join mtString -- full types are contravariant in their contexts

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

-- parametrize types over type variables that are themselves parametrized
data OneOrTwoTs t x = OneVariableT (t x) | TwoFixedTs (t Int) (t String)

-- bounds can be higher-kinded, too
class MonadStrip s where
  -- use arbitrarily nested higher-kinded type variables
  strip :: (Monad m, MonadTrans t) => s t m a -> t m a -> m a

Основной тип

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

Пламя Птариена
источник
7
Не используйте в lкачестве одной переменной буквы, это очень трудно отличить от 1!
recursion.ninja
5
Может быть, стоит отметить, что, хотя вы абсолютно правы в том, что в Java есть некоторая информация о типах среды выполнения, а в Haskell нет, вы можете использовать класс типов Typeable в Haskell, чтобы обеспечить нечто похожее на информацию о типах среды выполнения для многих типов (с более новым PolyKinded классы на пути, это будут все типы iirc), хотя я думаю, что это зависит от ситуации, передает ли он какую-либо информацию о типе во время выполнения или нет.
3
@ DarkOtter Я знаю Typeable, но у Haskell 2010 его нет (может, у Haskell 2014 будет?).
Пламя Птариена
5
Как насчет (закрытых) типов сумм? Это один из наиболее важных механизмов ограничения кодирования.
февраля
3
Допустимость пустой? Надежность (без ковариантных силлинсов)? Типы закрытой суммы / совпадения с образцом? Этот ответ слишком узкий
Пикер
32

В системе типов Java отсутствует более высокий родовой полиморфизм; Система типов Хаскелла имеет это.

Другими словами: в Java конструкторы типов могут абстрагироваться от типов, но не от конструкторов типов, тогда как в Haskell конструкторы типов могут абстрагироваться как от конструкторов типов, так и от типов.

На английском языке: в Java универсальный тип не может принимать другой универсальный тип и параметризировать его,

public void <Foo> nonsense(Foo<Integer> i, Foo<String> j)

в то время как в Haskell это довольно легко

higherKinded :: Functor f => f Int -> f String
higherKinded = fmap show
Йорг Миттаг
источник
28
Не могли бы вы повторить это на английском, на этот раз? : P
Мейсон Уилер
8
@ Matt: В качестве примера я не могу написать это в Java, но я могу написать эквивалент в Haskell: <T<_> extends Collection> T<Integer> convertStringsToInts(T<string> strings). Идея заключается в том, что если бы кто-то назвал его так, как convertStringsToInts<ArrayList>он бы взял массив строк и вернул список целых чисел. И если бы они вместо этого использовали convertStringsToInts<LinkedList>, то было бы то же самое со связанными списками вместо этого.
sepp2k
8
Разве это не более выраженный полиморфизм, чем ранг 1 против n?
Адам
8
@ JörgWMittag: Насколько я понимаю, полиморфизм более высокого ранга касается того, что вы можете использовать forallв своих типах. В Haskell тип a -> bявляется неявным forall a. forall b. a -> b. С помощью расширения вы можете сделать это forallявным образом и перемещать их.
Тихон Джелвис
8
@ Адам прав: более высокий ранг и более высокий род совершенно разные. GHC также может делать типы с более высоким рейтингом (то есть типы запросов) с некоторым расширением языка. Java не знает ни типов с более высоким, ни более высоким рейтингом.
Инго
11

Чтобы дополнить другие ответы, система типов Haskell не имеет подтипов , в то время как типизированные объектно-ориентированные языки, как в Java, имеют.

В теории языков программирования , подтипы (также подтип полиморфизма или включение полиморфизма ) является формой типа полиморфизма , в которых подтип является типом данных , который связан с другим типом данных ( супертип ) некоторым понятием взаимозаменяемости , а это означает , что программные элементы, как правило , подпрограммы или функции, написанные для работы с элементами супертипа, также могут работать с элементами субтипа. Если S является подтипом T, отношение подтипа часто записывается как S <: T, что означает, что любой термин типа S можно безопасно использовать в контексте, гдесрок типа T ожидается. Точная семантика подтипирования в решающей степени зависит от того, что «безопасно используется в контексте, где» означает в данном языке программирования. Система типов языка программирования по существу определяет свое собственное отношение подтипов, которое вполне может быть тривиальным.

Из-за отношения подтипов термин может принадлежать более чем одному типу. Следовательно, подтип является формой полиморфизма типов. В объектно-ориентированном программировании термин «полиморфизм» обычно используется для обозначения исключительно этого полиморфизма подтипа , в то время как методы параметрического полиморфизма будут рассматриваться как универсальное программирование ...

Петр Пудлак
источник
4
Хотя это не значит, что вы не получаете специальный полиморфизм. Вы делаете, просто в другой форме (классы типа вместо полиморфизма подтипа).
3
Подклассы не являются подтипами!
Фрэнк Шиарар
8

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

Еще одна вещь, о которой люди до сих пор не упоминали, - это алгебраические типы данных. То есть способность создавать типы из сумм ('или') и продуктов ('и') других типов. Классы Java делают продукты (скажем, поле a и поле b) хорошими. Но они на самом деле не делают суммы (например, укажите поле ИЛИ b). Scala должен закодировать это как несколько классов case, что не совсем одно и то же. И хотя это работает для Scala, довольно сложно сказать, что в Java это есть.

Haskell также может создавать типы функций, используя конструктор функций, ->. Хотя методы Java имеют сигнатуры типов, вы не можете их комбинировать.

Система типов Java позволяет использовать тип модульности , которого у Haskell нет. Пройдет некоторое время, прежде чем появится OSGi для Haskell.

GarethR
источник
1
@ MattFenwick, я изменил 3-й абзац на основе ваших отзывов. Системы двух типов по-разному относятся к функциям.
GarethR
Я бы не назвал ADT функцией системы типов. Вы можете полностью (если неуклюже) эмулировать их с помощью OO-оболочек.
оставил около
@ leftaroundabout Я думаю, что это возможно. Например, могут быть вещи, которые являются родными для системы типов одного языка, но могут быть реализованы с помощью шаблонов проектирования в другом. Очевидно, что способ проектирования по сравнению с нативным - это обходной путь. Обходной путь из-за более слабой системы типов.
Привет, Ангел,
В выбранном ответе упоминается «полный вывод типа» в разделе «Принципиальная типизация». Java может сортировать суммы с подтипами и информацией о типах среды выполнения, но, как вы говорите, это не то же самое, что сумма не является целостным атрибутом системы типов.
Шелби Мур III