Prägnantes Beispiel für exponentielle Kosten der ML-Typinferenz

Ich wurde darauf aufmerksam gemacht, dass die Kosten für Typinferenz in einer funktionalen Sprache wie OCaml sehr hoch sein können. Die Behauptung ist, dass es eine Folge von Ausdrücken gibt, so dass für jeden Ausdruck die Länge des entsprechenden Typs exponentiell zur Länge des Ausdrucks ist.

Ich habe die folgende Sequenz entwickelt. Meine Frage ist: Kennen Sie eine Sequenz mit präziseren Ausdrücken, die dieselben Typen erzielt?

# fun a -> a;;
- : 'a -> 'a = <fun>
# fun b a -> b a;;
- : ('a -> 'b) -> 'a -> 'b = <fun>
# fun c b a -> c b (b a);;
- : (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c = <fun>
# fun d c b a -> d c b (c b (b a));;
- : ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'd
= <fun>
# fun e d c b a -> e d c b (d c b (c b (b a)));;
- : (((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
   ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'e
= <fun>
# fun f e d c b a -> f e d c b (e d c b (d c b (c b (b a))));;
- : ((((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
     (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
    ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'e -> 'f) ->
   (((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
    (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'd -> 'e) ->
   ((('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'c -> 'd) ->
   (('a -> 'b) -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'f
= <fun>

In dieser Antwort, werde ich auf einen Kern ML - Fragment der Sprache bleiben, mit nur Lambda-Kalkül und polymorphe letfolgenden Hindley-Milner . Die vollständige OCaml-Sprache verfügt über zusätzliche Funktionen wie Zeilenpolymorphismus (der, wenn ich mich richtig erinnere, die theoretische Komplexität nicht ändert, bei dem echte Programme jedoch tendenziell größere Typen haben) und ein Modulsystem (das, wenn Sie hart genug stecken, nicht vorhanden sein kann) -terminierend in pathologischen Fällen mit abstrakten Signaturen).

Die Zeitkomplexität im schlimmsten Fall für die Entscheidung, ob ein Kern-ML-Programm einen Typ hat, ist ein einfaches Exponential in der Größe des Programms. Die klassischen Referenzen für dieses Ergebnis sind [KTU90] und [M90]. Eine elementarere, aber weniger vollständige Behandlung findet sich in [S95].

Die maximale Größe des Typs des Typs eines Kern-ML-Programms ist in der Größe des Programms tatsächlich doppelt exponentiell. Wenn die Typprüfung den Programmtyp drucken muss, kann die Zeit daher doppelt exponentiell sein. Es kann auf ein einfaches Exponential zurückgeführt werden, indem Abkürzungen für wiederholte Teile des Baums definiert werden. Dies kann der Freigabe von Teilen des Typbaums in einer Implementierung entsprechen.

Ihr Beispiel zeigt ein exponentielles Wachstum des Typs. Es ist jedoch zu beachten, dass es möglich ist, eine Darstellung des Typs in linearer Größe zu geben, indem Abkürzungen für wiederholte Teile des Typs verwendet werden. Dies kann der Freigabe von Teilen des Typbaums in einer Implementierung entsprechen. Zum Beispiel:

# fun d c b a -> d c b (c b (b a));;
t2 -> t2
where t2 = (t1 -> 'b -> 'c) -> t1 -> 'a -> 'd
where t1 = 'a -> 'b

Hier ist ein konzeptionell einfacheres Beispiel: Die Größe des Typs des Paares (x,x)ist doppelt so groß wie die Größe des Typs von x. Wenn Sie also die pairFunktion mal zusammensetzen, erhalten Sie einen Typ der Größe .Θ ( 2 N$N$$\Theta(2^N)$

# let pair x f = f x x;;
# let pairN x = pair (pair (pair … (pair x)…));;
'a -> tN
where tN = (tN-1 -> tN-1 -> 'bN) -> 'bN
…
where t2 = (t1 -> t1 -> 'b2) -> 'b2
where t1 = ('a -> 'a -> 'b1) -> 'b1

Durch die Einführung verschachtelter polymorpher letDefinitionen nimmt die Größe des Typs wieder exponentiell zu; Dieses Mal kann kein Teil des Teilens das exponentielle Wachstum abschneiden.

# let pair x f = f x x;;
# let f1 x = pair x in
  let f2 x = f1 (f1 x) in
  let f3 x = f2 (f2 x) in
  fun z -> f3 (fun x -> x) z;;

Verweise

[KTU90] Kfoury, J.; Tiuryn; Urzyczyn, P. (1990). "Die ML-Typisierbarkeit ist vollständig." Vorlesungsunterlagen in Informatik. CAAP '90 431: 206 & ndash; 220. [ Springer ] [ Google ]

[M90] Mairson, Harry G. (1990). "Die Entscheidung über die ML-Typisierbarkeit ist für die deterministische Exponentialzeit vollständig". Vorträge des 17. ACM SIGPLAN-SIGACT-Symposiums zu Prinzipien von Programmiersprachen. POPL '90 (ACM): 382–401. [ ACM ]

[P04] Benjamin C. Pierce. Fortgeschrittene Themen in Typen und Programmiersprachen. MIT Press, 2004. [ Amazon ]

[PR04] François Pottier und Didier Rémy. "Die Essenz der ML-Typinferenz". Kapitel 10 in [P04]. [ pdf ]

[S95] Michael I. Schwartzbach. Polymorphe Typinferenz. BRICS LS-95-3, Juni 1995. ps