Eta-Erweiterung im Muster Lambda-Kalkül

12

Klop, van Oostrom und de Vrijer haben eine Arbeit über den Lambda-Kalkül mit Mustern.

http://www.sciencedirect.com/science/article/pii/S0304397508000571

In gewissem Sinne ist ein Muster ein Baum von Variablen - obwohl ich es nur als verschachteltes Tupel von Variablen betrachte, zum Beispiel ((x, y), z), (t, s)).

In der Arbeit zeigten sie, dass, wenn die Muster linear sind, in dem Sinne, dass keine Variable in einem Muster wiederholt wird, die Regel gilt

(\p . m) n = m [n/p]

Dabei ist p ein variables Muster, und n ist ein Tupel von Termen mit der exakt gleichen Form wie p und ist konfluent.

Ich bin gespannt, ob es in der Literatur ähnliche Entwicklungen für den Lambda-Kalkül mit Mustern und der zusätzlichen eta-Regel (Expansion, Reduktion oder einfach nur Gleichheit) gibt.

Insbesondere meine ich mit eta 

m = \lambda p . m p

Direkter bin ich gespannt, welche Eigenschaften eine solche Lambda-Rechnung haben würde. Ist es zum Beispiel konfluent?

Es erzwingt das Schließen der klassifizierenden Kategorie, weil es die Eigenschaft erzwingt, dass

m p = n p implies m = n

Mit der \ xi-Regel dazwischen. Aber vielleicht könnte etwas schief gehen?

type-theory lambda-calculus typed-lambda-calculus extensionality Jonathan Gallagher
quelle
Kannst du schreiben, was eta Regel du meinst? Es sei denn, es ist sehr seltsam, Sie sollten in der Lage sein, es mit Summen zu codieren und ein Simulationsargument zu erstellen.
Max New
2
@MaxNew: Es sieht so aus, als würde er nach dem untypisierten Kalkül fragen. Alles, was mit Mustern zu tun hat, funktioniert perfekt mit Typen (ich schlage vor, dass ich mich auf die Musteranpassung konzentriere ), aber die nicht typisierte Lambda-Rechnung unterscheidet sich genug von der typisierten LC (insbesondere wrt eta), dass ich es nicht wage, ohne Beweise zu antworten .
Neel Krishnaswami
@MaxNew: Was würde Kodierung durch Summen bedeuten?
Jonathan Gallagher
@NeelKrishnaswami: Mich interessieren eigentlich beide. Ich glaube, ich bin nervös, Variablen eines Produkttyps zusammen mit der eta-Regel zu haben. Ich denke, das ist zum Beispiel gemacht, dicosmo.org/Articles/JFP96.pdf . Aber wenn ich mich irre, bitte korrigieren Sie mich. Dann haben Sie Gleichungen wie \ lambda x .mx = m = \ lambda (p, q). m (p, q) zum Beispiel. Vielen Dank für den Link zu Ihrem Artikel!
Jonathan Gallagher

Antworten:

7

Dies ist keine vollständige Antwort. Es ist ein Kommentar, der zu groß geworden ist.

Wenn Sie typisierte Lambda-Berechnungen mit Produkten mit projektiven Eliminatoren (dh Produkteliminatoren fst(e)und snd(e)) erweitern, gibt es grundsätzlich keinerlei Probleme. Der Grund, warum es so lange gedauert hat, ist, dass es sich als natürlicher herausstellt, Eta- Erweiterungen anstelle von Eta- Reduzierungen durchzuführen . Siehe Barry Jays Die Tugenden der Eta-Erweiterung .

Wenn Sie möchten, dass die Produkte einen Mustereliminator haben 

let (a,b) = e in t

Dann sind die Dinge komplexer. Die Hauptschwierigkeiten beim Pattern Matching sind die Pendelkonvertierungen . Das heißt, diese Kalküle haben die Gleichung

C[let (a,b) = e in t] === let (a,b) = e in C[t]

und herauszufinden, (a) welcher Kontext C[-]verwendet werden soll und (b) wie diese Gleichung zu orientieren ist, wird schwierig. IMO, der Stand der Technik für Umschreibungsansätze, sind Sam Lindleys Extensional Rewriting with Sums und Gabriel Scherers Deciding Equivalence with Sums und der Empty Type , die beide den typisierten Lambda-Kalkül sowohl für Produkte als auch für Summen berücksichtigen.

Neel Krishnaswami
quelle