Wie lese ich Tippregeln?

18

Ich fing an, immer mehr sprachwissenschaftliche Artikel zu lesen. Ich finde es sehr interessant und eine gute Möglichkeit, mehr über das Programmieren im Allgemeinen zu lernen. Es gibt jedoch normalerweise einen Abschnitt, mit dem ich immer zu kämpfen habe (nehmen Sie zum Beispiel Teil drei davon ), da mir der theoretische Hintergrund in der Informatik fehlt: Typregeln.

Gibt es in diesem Bereich gute Bücher oder Online-Ressourcen für den Einstieg? Wikipedia ist unglaublich vage und hilft Anfängern nicht wirklich.

logic reference-request terminology type-theory suls
quelle

1

Haben Sie den verlinkten Artikel über Inferenzregeln gelesen ?

Raphael

2

Benjamin Pierces TAPL ist wirklich gut.

Gilles 'SO- hör auf böse zu sein'

25

In den meisten Typsystemen arbeiten die Typregeln zusammen, um Urteile der Form zu definieren:

Γ ⊢ e : τ

$\Gamma\vdash e:\tau$

Dies besagt, dass im Kontext der Ausdruck den Typ . ist eine Abbildung der freien Variablen von auf ihre Typen. $\Gamma$ $e$ $\tau$
$\Gamma$ $e$

Ein Typensystem besteht aus einer Reihe von Axiomen und Regeln (ein formales System von Inferenzregeln , wie Raphael hervorhebt).

Ein Axiom ist von der Form

\frac{}{Γ ⊢ e : τ}

$\dfrac{}{\Gamma \vdash e:\tau}$

Dies besagt, dass das Urteil (immer) gilt. $\Gamma \vdash e:\tau$

Ein Beispiel ist

\frac{}{x : τ ⊢ x : τ}

$\dfrac{}{x:\tau\vdash x:\tau}$

die besagt , daß unter der Annahme , dass die Art der Variablen $x$ ist $\tau$ , dann wird der Ausdruck $x$ hat Typ $\tau$ .

Inferenzregeln nehmen bereits ermittelte Tatsachen und bauen daraus größere Tatsachen auf. Zum Beispiel die Inferenzregel

\frac{Γ ⊢ e_{1} : τ \to τ^{'} Γ ⊢ e_{2} : τ}{Γ ⊢ e_{1} e_{2} : τ^{'}}

$\dfrac{\Gamma\vdash e_1:\tau\to\tau' \quad \Gamma\vdash e_2:\tau}{\Gamma\vdash e_1\ e_2:\tau'}$

sagt, wenn ich eine Ableitung der Tatsache und eine Ableitung der Tatsache , dann kann ich eine Ableitung der Tatsache . In diesem Fall ist dies die Regel für die Eingabe von Funktionsanwendungen. $\Gamma\vdash e_1:\tau\to\tau'$ $\Gamma\vdash e_2:\tau$ $\Gamma\vdash e_1\ e_2:\tau'$

Es gibt zwei Möglichkeiten, diese Regel zu lesen:

top-down - Wenn zwei Ausdrücke (eine Funktion und ein anderer Ausdruck) und einige Einschränkungen für ihren Typ gegeben sind, können wir einen weiteren Ausdruck (die Anwendung der Funktion auf den Ausdruck) mit dem gegebenen Typ konstruieren.
bottom-up - bei einem Ausdruck, bei dem es sich in diesem Fall um die Anwendung einer Funktion auf einen Ausdruck handelt, werden zuerst die beiden Ausdrücke eingegeben, um sicherzustellen, dass ihre Typen bestimmten Bedingungen entsprechen, d. h Funktionstyp und dass der zweite den Argumenttyp der Funktion hat.

Einige Inferenzregeln manipulieren auch indem sie neue Zutaten hinzufügen (von unten nach oben betrachtet). Hier ist die Regel für -abstraction: $\Gamma$ $\lambda$

\frac{Γ x : τ ⊢ e : τ^{'}}{Γ ⊢ λ x . e : τ \to τ^{'}}

$\dfrac{\Gamma x:\tau\vdash e:\tau'}{\Gamma\vdash \lambda x.e:\tau\to \tau'}$

Die Inferenzregeln werden induktiv angewendet, basierend auf der Syntax des Ausdrucks, der als Ableitungsbaum betrachtet wird. An den Blättern des Baumes (oben) werden Axiome und Zweige gebildet, indem Folgerungsregeln angewendet werden. Ganz unten im Baum befindet sich der Ausdruck, den Sie eingeben möchten.

$\lambda f.\lambda x.f\ x$

\frac{\frac{}{f : τ \to τ^{'}, x : τ ⊢ f : τ \to τ^{'}} \frac{}{f : τ \to τ^{'}, x : τ ⊢ x : τ}}{\frac{f : τ \to τ^{'}, x : τ ⊢ f x : τ^{'}}{\frac{f : τ \to τ^{'} ⊢ λ x . f x : τ^{'}}{⊢ λ f . λ x . f x : τ^{'}}}}

$\dfrac{\dfrac{}{f:\tau\to\tau',x:\tau\vdash f:\tau\to\tau'} \qquad \dfrac{}{f:\tau\to\tau',x:\tau\vdash x:\tau}} {\dfrac{f:\tau\to\tau',x:\tau\vdash f\ x:\tau'}{ \dfrac{f:\tau\to\tau'\vdash \lambda x.f\ x:\tau'}{\vdash \lambda f.\lambda x.f\ x:\tau'}}}$

Typen und Programmiersprachen von Benjamin Pierce
Praktische Grundlagen für Programmiersprachen von Robert Harper

Beide Bücher sind sehr umfangreich, beginnen jedoch langsam und bilden ein solides Fundament.

Dave Clarke
quelle

8

Es gibt ein niedliches interaktives Online-Tutorial über Folgerechnung, das helfen kann, einige Intuitionen aufzubauen und zu spüren, wie Folgerungen funktionieren: Ein interaktives Tutorial der Folgerechnung

aemxdp
quelle

3

Das ist wirklich cool.

Dave Clarke

1

Genial. Ich muss ein Tag-Wiki finden, in das ich das einfügen kann.

Raphael

5

Auf dieser Wikipedia-Seite wird " Type Systems, Luca Cardelli, ACM Computing Surveys " empfohlen. Hierbei handelt es sich um eine 2-seitige Umfrage, die Ihnen helfen kann, das Lesen einer Regel zu verstehen. Wie auch immer, wie man eine Regel liest, wird auf dieser Wikipedia-Seite (oder noch besser in der 2-Seiten-Umfrage) perfekt erklärt. Doch das Ganze zu verstehen, müssen Sie verstehen , was ein Typisierungssystem ist (von mehreren Regeln zusammengesetzt), für die der „ Type System “ Wikipedia - Artikel ist ein guter Anfang (und Sie haben mehrere Bücher im Abschnitt „ Referenzen “ davon Seite, wenn Sie weiter gehen möchten).

Alejandro DC
quelle

Wie lese ich Tippregeln?

Antworten: