Когда в OCaml вступает в действие смягченное ограничение ценностей?

Question

Может ли кто-то дать краткое описание того, когда наступит ослабленное ограничение стоимости? Мне было трудно найти краткое и четкое описание правил. Есть бумага Гаррига:

http://caml.inria.fr/pub/papers/garrigue-value_restriction-fiwflp04.pdf

но это немного плотно Кто-нибудь знает более содержательный источник?

Приложение

Некоторые хорошие объяснения были добавлены ниже, но я не смог найти там объяснения для следующего поведения:

# let _x = 3 in (fun () -> ref None);;
- : unit -> 'a option ref = <fun>
# let _x = ref 3 in (fun () -> ref None);;
- : unit -> '_a option ref = <fun>

Кто-нибудь может уточнить выше? Почему ошибочное определение ссылки в пределах RHS вмещающей let влияет на эвристику.

Answer 1

Я не теоретик типов, но вот моя интерпретация объяснения Гаррига. У вас есть значение V. Начните с типа, который будет назначен V (в OCaml) при обычном ограничении значения. В типе будет некоторое количество (возможно, 0) переменных мономорфного типа. Для каждой такой переменной, которая появляется только в ковариантной позиции в типе (справа от стрелок функций), вы можете заменить ее полностью полиморфной переменной типа.

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

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

(Надеюсь, у меня есть это право. Конечно, @gasche будет лучше, как предполагает octref.)

Answer 2

Джеффри дал интуитивное объяснение того, почему расслабление является правильным. Что касается того, когда это полезно, я думаю, что мы можем сначала воспроизвести ответ octref, полезно связанный с:

Вы можете спокойно игнорировать эти тонкости до тех пор, пока однажды не столкнетесь с проблемой с вашим абстрактным типом, который не настолько полиморфен, как хотелось бы, и тогда вы должны помнить, чем может помочь ковариационная аннотация в подписи.

Мы обсуждали это на reddit / ocaml несколько месяцев назад:

Рассмотрим следующий пример кода:

module type S = sig
  type 'a collection
  val empty : unit -> 'a collection
end

module C : S = struct
  type 'a collection =
    | Nil
    | Cons of 'a * 'a collection
  let empty () = Nil
end

let test = C.empty ()

Тип, который вы получаете за test является '_a C.collectionвместо 'a C.collection что вы ожидаете. Это не полиморфный тип ('_a является мономорфной переменной логического вывода, которая еще не полностью определена), и в большинстве случаев она вас не устраивает.

Это потому что C.empty () не является значением, поэтому его тип не является обобщенным (сделанный полиморфным). Чтобы извлечь выгоду из смягченного ограничения значения, вы должны отметить абстрактный тип 'a collection ковариантны:

module type S = sig
  type +'a collection
  val empty : unit -> 'a collection
end

Конечно, это происходит только потому, что модуль C скреплено подписью S: module C : S = ..., Если модуль C не было дано явной сигнатуры, система типов будет выводить наиболее общую дисперсию (здесь ковариация), и этого никто не заметит.

Программирование на основе абстрактного интерфейса часто полезно (при определении функтора или применении дисциплины фантомного типа, или при написании модульных программ), так что такая ситуация определенно происходит, и тогда полезно знать об ограничении ослабленных значений.

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

В большинстве случаев это происходит без вашего ведома, когда вы манипулируете полиморфными структурами данных. [] @ [] имеет только полиморфный тип 'a list благодаря релаксации.

Конкретный, но более сложный пример - это Ber-MetaOCaml Олега, который использует тип ('cl, 'ty) code представлять кавычки, которые построены кусочно. 'ty представляет тип результата цитируемого кода, и 'cl является разновидностью переменной области фантома, которая гарантирует, что, когда она остается полиморфной, область видимости переменной в кавычном коде является правильной. Поскольку это основано на полиморфизме в ситуациях, когда выражения в кавычках строятся путем составления других выражений в кавычках (как правило, не являются значениями), оно в принципе не будет работать вообще без ослабленного ограничения значений (это побочное замечание в его превосходном, но техническом документе о типе умозаключение).

Answer 3

Вопрос, почему два примера, приведенные в приложении, напечатаны по-разному, озадачил меня на пару дней. Вот что я нашел, покопавшись в коде компилятора OCaml (отказ от ответственности: я не эксперт ни по OCaml, ни по системе типов ML).

резюмировать

# let _x = 3 in (fun () -> ref None);;        (*  (1)  *)
- : unit -> 'a option ref = <fun>

дается полиморфный тип (думаю, ∀ α. unit → α option ref) в то время как

# let _x = ref 3 in (fun () -> ref None);;    (*  (2)  *)
- : unit -> '_a option ref = <fun>

дается мономорфный тип (думаю, unit → α option refпеременная типа α не является универсально определенным).

Интуиция

В целях проверки типов компилятор OCaml не видит различий между примером (2) и

# let r = ref None in (fun () -> r);;         (*  (3)  *)
- : unit -> '_a option ref = <fun>

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

расширяемость

Чтобы понять, почему (1) и (2) напечатаны так, как они есть, давайте посмотрим, как на самом деле компилятор OCaml проверяет, является ли let Выражение является значением (т. е. "неэкспансивным") или нет (см. is_nonexpansive):

let rec is_nonexpansive exp =
  match exp.exp_desc with
    (* ... *)
  | Texp_let(rec_flag, pat_exp_list, body) ->
      List.for_all (fun vb -> is_nonexpansive vb.vb_expr) pat_exp_list &&
      is_nonexpansive body
  | (* ... *)

Так что let-выражение является значением, если его тело и все связанные переменные являются значениями.

В обоих примерах, приведенных в добавлении, тело fun () -> ref None, которая является функцией и, следовательно, значением. Разница между двумя частями кода заключается в том, что 3 это значение в то время как ref 3 не является. Поэтому OCaml считает первым let значение, но не второе.

Typing

Опять же, посмотрев на код компилятора OCaml, мы увидим, что то, считается ли выражение экспансивным, определяет, как тип let-выражения обобщены (см. выражение_представления):

(* Typing of toplevel expressions *)

let type_expression env sexp =
  (* ... *)
  let exp = type_exp env sexp in
  (* ... *)
  if is_nonexpansive exp then generalize exp.exp_type
  else generalize_expansive env exp.exp_type;
  (* ... *)

поскольку let _x = 3 in (fun () -> ref None) нерасширен, набирается с помощью generalize что дает ему полиморфный тип. let _x = ref 3 in (fun () -> ref None)с другой стороны, набирается через generalize_expansive, придав ему мономорфный тип.

Это насколько я понял. Если вы хотите копать еще глубже, читайте " Эффективное и проницательное обобщение" Олега Киселева вместе с generalize а также generalize_expansive может быть хорошим началом

Большое спасибо Лео Уайту из OCaml Labs в Кембридже за то, что он побудил меня начать копать!

Answer 4

Хотя я не очень знаком с этой теорией, я задал вопрос об этом.
Гаше дал мне краткое объяснение. Пример является лишь частью модуля карты OCaml. Проверьте это!
Может быть, он сможет дать вам лучший ответ. @gasche