Selbsttypen sind eine Erweiterung der Konstruktionsrechnung [1], mit der die Sprache algebraische Datentypen ausdrücken kann, die durch die Scott-Codierung codiert werden. Die Scott-Codierung bietet die Möglichkeit zur Musterübereinstimmung O(1)
, was einer der Hauptgründe für die Aufnahme induktiver Definitionen in CC ist. Selbsttypen sind jedoch eine viel einfachere und elegantere Basistheorie und scheinen nicht weniger mächtig zu sein.
Machen Selbsttypen unter theoretischen Gesichtspunkten CIC überflüssig, oder gibt es noch einen Aspekt, bei dem CIC in Bezug auf Selbsttypen günstig ist?
[1] http://staff.computing.dundee.ac.uk/pengfu/document/talks/mvd-2012.pdf
* : *
@GIlles, nicht fürSelf
?Antworten:
Ich bin kein Experte in dieser Arbeit, aber es scheint mir, dass das Hauptproblem ein Mangel an SN-Beweisen ist, selbst mit Einschränkungen. Diese Beweise sind jedoch notorisch schwierig, selbst wenn der Kalkül korrekt ist, also würde ich ihm ein wenig Zeit geben. Die Arbeit ist sicherlich sehr vielversprechend.
Zu beachten ist, dass diese Einschränkungen eigentlich nicht trivial auszudrücken sind, was einen großen Teil der Komplexität der Formulierung der induktiven Familien im CIC ausmacht. Das eigentliche Verkaufsargument eines solchen Ansatzes wäre die präzise Formulierung dieser Bedingungen.
Es ist ein seit langem offenes Problem, eine abhängig getippte Sprache zu haben
Ein solcher Versuch, den ich kenne, ist die Sprache Altenkirch & al , der ebenfalls eine vollständige metatheoretische Studie fehlt (und die auch ohne weitere Einschränkungen nicht konsistent ist).ΠΣ
quelle