Charakterystyka terminów lambda, które mają typy związków

29

Wiele podręczników obejmuje typy przecięć w rachunku lambda. Reguły pisania dla przecięcia można zdefiniować w następujący sposób (na górze zwykłego rachunku lambda z podtypami):

ΓM.:T.1ΓM.:T.2)ΓM.:T.1T.2)(ja)ΓM.:(ja)

Typy skrzyżowań mają interesujące właściwości w odniesieniu do normalizacji:

  • Terminarz lambda można wpisać bez użycia Iff, jeśli jest silnie normalizujący.ja
  • Termin lambda przyjmuje typ niezawierający iff ma normalną formę.

Co jeśli zamiast dodawać skrzyżowania, dodamy związki?

ΓM:T1ΓM:T1T2(I1)ΓM:T2ΓM:T1T2(I2)

Czy rachunek lambda z prostymi typami, podtypami i związkami ma jakąkolwiek interesującą podobną właściwość? Jak scharakteryzować terminy, które można wpisać w związku?

Gilles „SO- przestań być zły”
źródło
Interesujące pytanie. Czy możesz powiedzieć, że interfejsy OOP odpowiadają temu?
Raphael
Może możesz zainteresować się tym cs.cmu.edu/~rwh/courses/refinements/papers/Barbaneraetal95/…
Fabio F.

Odpowiedzi:

11

W pierwszym systemie to, co nazywasz subtypingiem, to dwie reguły:

Γ,x:T1M:SΓ,x:T1T2M:S(E1)Γ,x:T2M:SΓ,x:T1T2M:S(E2)

Odpowiadają zasadom eliminacji dla ; bez nich łącznik jest mniej lub bardziej bezużyteczny.

W drugim systemie (z łącznikami i , do którego moglibyśmy również dodać znak ) powyższe reguły podsieci są nieistotne i myślę, że towarzyszące im zasady były następujące:

Γ,x:T1M:SΓ,x:T2M:SΓ,x:T1T2M:S(E)Γ,x:M:S(E)

Dla tego, co jest warte, ten system pozwala na wpisanie (przy użyciu reguły ), którego nie można wpisać tylko prostymi typami, które mają normalną formę, ale nie są silnie normalizowane .(λx.ja)Ω:ZAZAmi


Losowe przemyślenia: (może warto zapytać w TCS)

To prowadzi mnie do przypuszczenia, że ​​powiązane właściwości są podobne do:

  • λ-termin przyjmuje typ niezawierający iff ma postać normalną dla wszystkich które mają postać normalną. ( nie przejdzie obu testów, ale powyższy λ-termin je zalicza)M.M.N.N.δ
  • λ okresie mogą być drukowane bez użycia zasada IFF jest silnie normalizację dla każdego silnie normalizowania .M.miM.N.N.

Ćwiczenie: udowodnij, że się mylę.

Wydaje się też, że jest to zdegenerowana sprawa, może powinniśmy rozważyć dodanie tego faceta do zdjęcia. O ile pamiętam, pozwoliłoby to uzyskać ?ZA(ZA)

Stéphane Gimenez
źródło
Dobra uwaga na temat reguł podsieci, pokazują, że typy unii nie są tak naturalne jak przecięcia (które są wpisywane prostopadle do strzałek). O drugiej części muszę jeszcze trochę pomyśleć.
Gilles 'SO - przestań być zły'
Myślę, że odpowiada na ćwiczenie, jeśli mówimy o typach związków. M.=(λx.xx)(λy.y)
jmad
O call / cc: potrzebuje więcej niż tylko warunków lambda (takich jak lambda-mu lub inne ramy), ale systemy typów są bardziej złożonymi, logicznymi systemami, w których typy związków mogą być nieistotne.
jmad
@jmad: Rzeczywiście, do wpisania tego terminu potrzebne są typy skrzyżowań :-( Może rozważenie związków i skrzyżowań razem byłoby interesujące?
Stéphane Gimenez
Byłbym zainteresowany λ-terminem, który można pisać z typami unii (rs. Z typami przecięcia), ale nie z typami prostymi (rs. Z typami przecięcia).
jmad
16

Chcę tylko wyjaśnić, dlaczego typy przecięć są odpowiednie do scharakteryzowania klas normalizacji (silna, głowa lub słaba), podczas gdy inne systemy typów nie mogą. (prosty typ lub system F).

Kluczową różnicą jest to, że musisz powiedzieć: „jeśli mogę wpisać i M 1M 2, to mogę wpisać M 1 ”. Często nie jest to prawdą w typach nie przecinających się, ponieważ termin można powielić:M.2)M.1M.2)M.1

(λx.M.xx)N.M.N.N.

a następnie wpisanie oznacza, że ​​możesz wpisać oba wystąpienia N, ale nie tego samego typu, na przykład M : T 1T 2T 3M.N.N.N. Za pomocą typów skrzyżowań możesz przekształcić to w: M : T 1T 2T 1T 2T 3

M.:T.1T.2)T.3)N.:T.1N.:T.2)
a następnie kluczowy krok jest teraz naprawdę łatwy: ( λ x . M x x ) : T 1T 2T 3
M.:T.1T.2)T.1T.2)T.3)N.:T.1T.2)
so ( λ x . M x x ) N można wpisywać za pomocą typów przecięć.
(λx.M.xx):T.1T.2)T.3)N.:T.1T.2)
(λx.M.xx)N.

Teraz o typach związków: załóżmy, że możesz wpisać pomocą jakiegoś typu związku, a następnie możesz także wpisać λ x . x x, a następnie pobierz dla niektórych typów S , T 1 , x : T 1T 2T nx x : S Ale wciąż musisz to udowodnić dla każdego i , x : T(λx.xx)(λy.y)λx.xxS.,T.1,

x:T.1T.2)T.nxx:S.
ja co wydaje się niemożliwe, nawet jeśli S jest rodzajem związku.x:T.jaxx:S.S.

Dlatego nie sądzę, aby można było łatwo scharakteryzować normalizację typów związków.

jmad
źródło