Вопрос по types, haskell – Можно ли автоматически генерировать код с учетом сигнатуры типа языка Haskell?

26

Что это говорит в названии. Если я напишу сигнатуру типа, можно ли алгоритмически сгенерировать выражение, имеющее эту сигнатуру типа?

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

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

Can it be done?

If so, how?

If not, are there any restricted situations where it becomes possible?

It's quite possible for two distinct expressions to have the same type signature. Can you compute all of them? Or even some of them?

Does anybody have working code which does this stuff for real?

ghc --guess-what-i-want-to-do --and-make-me-tea-while-you-re-at-it, В конце концов, учитываяmain :: IO () Вы могли бы создать всю программу. Cat Plus Plus
смотреть наDjinn, В принципе, да, это может быть сделано. kizzx2

Ваш Ответ

4   ответа
7

это невозможно (и для таких языков, как Haskell, который даже не обладает свойством сильной нормализации), и возможно только в некоторых (очень) особых случаях (и для более ограниченных языков), например, когда тип кодомена имеет единственный конструктор (например, функцияf :: forall a. a -> () можно определить однозначно). Чтобы свести набор возможных определений для данной сигнатуры к одноэлементному набору с одним определением, нужно дать больше ограничений (например, в виде дополнительных свойств, все еще трудно представить, как это может быть полезным без предоставления пример использования).

С (n-) категориальной точки зрения типы соответствуют объектам, термины соответствуют стрелкам (конструкторы также соответствуют стрелкам), а определения функций соответствуют 2-стрелкам. Вопрос аналогичен вопросу о том, можно ли построить 2-категорию с требуемыми свойствами, указав только набор объектов. Это невозможно, поскольку вам нужна либо явная конструкция для стрелок и 2-стрелок (то есть написание терминов и определений), либо дедуктивная система, которая позволяет вывести необходимую структуру с использованием определенного набора свойств (которые все еще должны быть определены явно ).

Существует также интересный вопрос: с учетом ADT (то есть подкатегории Hask) можно автоматически получать экземпляры для Typeable, Data (да, используяНСБ), Traversable, Foldable, Functor, Pointed, Applicative, Monad и т. Д. (?). В этом случае у нас есть необходимые подписи, а также дополнительные свойства (например, законы монады, хотя эти свойства не могут быть выражены в Haskell, но они могут быть выражены на языке с зависимыми типами). Есть несколько интересных конструкций:

http://ulissesaraujo.wordpress.com/2007/12/19/catamorphisms-in-haskell

который показывает, что можно сделать для списка ADT.

3

и я не уверен в ответе, если вы спрашиваете о полной славе типов Haskell, включая семейства типов, GADT и т. Д.

Вы спрашиваете, может ли программа автоматически доказать, что произвольный типinhabited (содержит значение), выставляя такое значение. Принцип, называемый соответствием Карри-Говарда, говорит, что типы могут интерпретироваться как математические суждения, и тип является обитаемым, если суждение конструктивно доказуемо. Таким образом, вы спрашиваете, является ли она программой, которая может доказать определенный класс предложений как теоремы. В таком языке, как Agda, система типов достаточно мощна, чтобы выразитьarbitrary математические предложения и доказательство произвольных неразрешимо по теореме G о неполноте дельта. С другой стороны, если вы перейдете на (скажем) чистый Хиндли-Милнер, вы получите гораздо более слабую и (я думаю) разрешимую систему. С Haskell 98 я не уверен, потому что классы типов должны быть эквивалентны GADT.

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

(Обновление :) О, мне приходит в голову гораздо более простая интерпретация вашего вопроса: возможно, вы спрашиваете, обитает ли каждый тип языка Haskell. Ответ, очевидно, нет. Рассмотрим полиморфный тип

a -> b

С этой сигнатурой нет функции (не считая что-то вроде unsafeCoerce, что делает систему типов несовместимой).

Конечно, я понимаю, что вся эта интересная теория применима только к Haskell, "если вы не обманываете". У нас есть бесконечные циклы, исключения,unsafeCoerce, FFI ... MathematicalOrchid
Чтобы быть педантичным, каждый тип в Haskell обитаем (система типов уже противоречива), например отundefined, Обычно, когда мы задаем такой вопрос, мы хотимtotal ценности, но тогда мы должны быть осторожны, что мы подразумеваем под этим, потому что, например,fix не тотально, но, безусловно, довольно интересная функция; является[1 ..] Всего? Это типdata Stream a = Cons a (Stream a) населены?
Также есть такие функции какf :: t; f = f который можно использовать какundefined (такие функции невозможны в HM или в SystemF, поскольку они нарушают свойство сильной нормализации).
AFAIK, H98 основана на HM и разрешима (классы типов без fundeps просто дезагрегированы), система GHC основана на SystemFC и неразрешима (есть возможность записать LC на уровне типа и затем записать в него неопределенный термин).
33

Джинн делает это для ограниченного подмножества типов Haskell, соответствующих логике первого порядка. Однако он не может управлять рекурсивными типами или типами, для реализации которых требуется рекурсия; так, например, он не может написать термин типа(a -> a) -> a (типfix), что соответствует предложению «еслиa подразумеваетa, затемa& quot ;, что явно неверно; Вы можете использовать это, чтобы доказать что-нибудь. Действительно, вот почемуfix дает начало & # x22A5 ;.

если тыdo разрешатьfixзатем написание программы для определения термина любого типа тривиально; программа просто напечатаетfix id для каждого типа.

Джинн в основном игрушка, но она может делать забавные вещи, например, выводить правильныеMonad случаи дляReader а такжеCont учитывая типыreturn а также(>>=), Вы можете попробовать это, установивджинн пакет, или используяlambdabotкоторый интегрирует это как@djinn команда.

+1 за ссылку на Джинна. Очевидно, мне придется изучить это. Меня больше всего интересует, могут ли они распутать хитрые проблемы монадного трансформатора ... MathematicalOrchid
14

Олег вokmij.org имеет реализацию этого. Есть краткое введениеВот нограмотный источник на Haskell содержит детали и описание процесса. (Я не уверен, насколько это соответствует власти Джинна, но это еще один пример.)

Есть случаи, когда нет уникальной функции:

fst', snd' :: (a, a) -> a
fst' (a,_) = a
snd' (_,b) = b

Не только это; Есть случаи, когда существует бесконечное количество функций:

list0, list1, list2 :: [a] -> a
list0 l = l !! 0
list1 l = l !! 1
list2 l = l !! 2
-- etc.

-- Or 
mkList0, mkList1, mkList2 :: a -> [a]
mkList0 _ = []
mkList1 a = [a]
mkList2 a = [a,a]
-- etc.

(Если вам нужны только полные функции, то подумайте[a] как ограничено бесконечными списками дляlist0, list1 и т. д., т.е.data List a = Cons a (List a))

Фактически, если у вас есть рекурсивные типы, любые типы, включающие их, соответствуют бесконечному количеству функций. Однако, по крайней мере, в вышеописанном случае существует счетное количество функций, поэтому можно создать (бесконечный) список, содержащий все из них. Но я думаю, что тип[a] -> [a] соответствует несчетно бесконечному числу функций (снова ограничить[a] в бесконечные списки), так что вы даже не можете перечислить их все!

(Резюме: существуют типы, которые соответствуют конечному, счетно бесконечному и бесчисленно бесконечному числу функций.)

+1 для более полезного понимания. Меня не удивляет, что данный тип может иметь несколько реализаций. Сколько способов вы можете использовать Int - & gt; Int? Я думаю, довольно много. Интересно то, как часто эти методы генерируютuseful код... MathematicalOrchid
Из интереса, в чем ваше различие между функцией и реализацией?
Там может быть (2 ^ n) ^ (2 ^ n) различныхfunctions типа Int - & gt; Int, но я бы предположил, что есть ещеimplementations чем это. ;-) И Integer не представляет неограниченные целые числа на любой физической машине, на которой работает Haskell. Если мы собираемся разделить волосы ... MathematicalOrchid
Это означает, что каждая функция имеет бесконечно много реализаций:\x -> const (x + 2) <arbitrary expression>.
@MateticOrchid, зависит от вашего определения «полезного» :) Есть & quot; только & quot;2^(2^37) функцииInt -> Int еслиInt 32-битный (или, в более общем(2^n)^(2^n) == 2^(n*2^n) еслиInt являетсяn биты). Но есть неисчислимо много функцийInteger -> Integer, Хотя только счетное количество из нихcomputable.

Похожие вопросы