Darstellung gebundener Variablen mit einer Funktion von Verwendungen bis zu Bindemitteln

Das Problem der Darstellung gebundener Variablen in der Syntax und insbesondere der Substitution zur Vermeidung von Captures ist bekannt und hat eine Reihe von Lösungen: benannte Variablen mit Alpha-Äquivalenz, De-Bruijn-Indizes, lokale Namenslosigkeit, nominale Mengen usw.

Aber es scheint einen anderen ziemlich offensichtlichen Ansatz zu geben, den ich dennoch nirgendwo verwendet habe. In der Grundsyntax haben wir nämlich nur einen "Variablen" -Term, der mit , und dann geben wir separat eine Funktion, die jede Variable einem Ordner zuordnet, in dessen Bereich sie liegt. Also ein λ- Term wie$\bullet$$\lambda$

würde geschrieben werden . ( λ . ∙ ∙ ) , und die Funktion würde das erste ∙ auf das erste λ und das zweite ∙ auf das zweite λ abbilden . Es ist also ein bisschen wie bei de Bruijn-Indizes, nur anstatt " λ s zählen" zu müssen, wenn Sie den Begriff verlassen, um das entsprechende Bindemittel zu finden, bewerten Sie einfach eine Funktion. (Wenn dies als Datenstruktur in einer Implementierung dargestellt wird, würde ich daran denken, jedes Objekt mit variablem Term mit einem einfachen Zeiger / Verweis auf das entsprechende Objekt mit Binderterm auszustatten.)$\lambda. (\lambda. \bullet\bullet)$$\bullet$$\lambda$$\bullet$$\lambda$$\lambda$

Offensichtlich ist dies nicht sinnvoll, um Syntax auf eine Seite zu schreiben, die der Mensch lesen kann, aber es gibt auch keine de Bruijn-Indizes. Es scheint mir, dass es mathematisch absolut sinnvoll ist, und insbesondere macht es die Substitution, die das Erfassen vermeidet, sehr einfach: Geben Sie einfach den Begriff ein, den Sie ersetzen, und nehmen Sie die Vereinigung der Bindungsfunktionen. Es ist wahr, dass es keinen Begriff von "freier Variable" gibt, aber (wieder) auch nicht wirklich de Bruijn-Indizes; In beiden Fällen wird ein Begriff, der freie Variablen enthält, als Begriff mit einer Liste von "Kontext" -Bindemitteln dargestellt.

Vermisse ich etwas und es gibt einen Grund, warum diese Darstellung nicht funktioniert? Gibt es Probleme, die es so viel schlimmer machen als die anderen, dass es sich nicht lohnt, darüber nachzudenken? (Das einzige Problem, an das ich im Moment denken kann, ist, dass die Menge der Begriffe (zusammen mit ihren Bindungsfunktionen) nicht induktiv definiert ist, aber das scheint nicht unüberwindbar.) Oder gibt es tatsächlich Orte, an denen sie verwendet wurden?

Die Antworten von Andrej und Łukasz machen gute Punkte, aber ich wollte zusätzliche Kommentare hinzufügen.

Um das zu wiederholen, was Damiano gesagt hat, ist diese Art der Darstellung der Bindung mithilfe von Zeigern diejenige, die von Beweisnetzen vorgeschlagen wird, aber der früheste Ort, an dem ich sie für Lambda-Begriffe sah, war in einem alten Aufsatz von Knuth:

• Donald Knuth (1970). Beispiele für formale Semantik. Im Symposium zur Semantik algorithmischer Sprachen , E. Engeler (Hrsg.), Lecture Notes in Mathematics 188, Springer.

$(\lambda y.\lambda z.yz)x$

Diese Art der grafischen Darstellung von Lambda-Begriffen wurde Anfang der 1970er Jahre in zwei Thesen unabhängig voneinander (und eingehender) untersucht, sowohl von Christopher Wadsworth (1971, Semantik und Pragmatik des Lambda-Kalküls ) als auch von Richard Statman (1974, Structural Complexity) von Beweisen ). Heutzutage werden solche Diagramme oft als "λ-Graphen" bezeichnet (siehe zum Beispiel dieses Papier ).

Beachten Sie, dass der Begriff in Knuths Diagramm linear ist , in dem Sinne, dass jede freie oder gebundene Variable genau einmal vorkommt - wie andere bereits erwähnt haben, müssen nicht triviale Probleme und Entscheidungen getroffen werden, um diese Art der Darstellung auf Nicht zu erweitern -lineare Terme.

$\alpha$

Ich bin mir nicht sicher, wie Ihre Variable-zu-Binder-Funktion dargestellt wird und für welchen Zweck Sie sie verwenden möchten. Wenn Sie Back-Pointer verwenden, ist die rechnerische Komplexität der Substitution, wie Andrej feststellte, nicht besser als die klassische Alpha-Umbenennung.

Aus Ihrem Kommentar zu Andrejs Antwort schließe ich, dass Sie in gewissem Maße daran interessiert sind, etwas zu teilen. Ich kann hier einen Beitrag leisten.

In einem typischen typisierten Lambda-Kalkül haben Schwächung und Kontraktion im Gegensatz zu anderen Regeln keine Syntax.

Fügen wir eine Syntax hinzu:

$C_a^{b,c}(\cdot)$$a$$b,c$

Mit dieser Syntax wird jede Variable genau zweimal verwendet, einmal dort, wo sie gebunden ist, und einmal dort, wo sie verwendet wird. Dies ermöglicht es uns, uns von einer bestimmten Syntax zu distanzieren und den Begriff als Diagramm zu betrachten, in dem Variablen und Begriffe Kanten sind.

Aufgrund der algorithmischen Komplexität können wir jetzt Zeiger nicht von einer Variablen zu einem Binder, sondern von Binder zu Variable verwenden und Substitutionen in einer konstanten Zeit haben.

Darüber hinaus können wir mit dieser Neuformulierung das Löschen, Kopieren und Teilen mit größerer Genauigkeit verfolgen. Man kann Regeln schreiben, die einen Begriff schrittweise kopieren (oder löschen), während Subterme geteilt werden. Dafür gibt es viele Möglichkeiten. In einigen eingeschränkten Einstellungen sind die Gewinne ziemlich überraschend .

Dies nähert sich den Themen Interaktionsnetze, Interaktionskombinatoren, explizite Substitution, lineare Logik, optimale Bewertung von Lamping, gemeinsame Nutzung von Diagrammen, Lichtlogik und anderem.

All diese Themen sind für mich sehr aufregend und ich würde gerne spezifischere Referenzen geben, aber ich bin mir nicht sicher, ob dies für Sie nützlich ist und was Ihre Interessen sind.

Ihre Datenstruktur funktioniert, ist jedoch nicht effizienter als andere Ansätze, da Sie jedes Argument bei jeder Beta-Reduzierung kopieren müssen und so viele Kopien erstellen müssen, wie die gebundene Variable vorkommt. Auf diese Weise zerstören Sie die Speicherfreigabe zwischen Subtermen. In Kombination mit der Tatsache, dass Sie eine nicht reine Lösung vorschlagen, die Zeigermanipulationen beinhaltet und daher sehr fehleranfällig ist, ist es wahrscheinlich nicht die Mühe wert.

Aber ich würde mich freuen, ein Experiment zu sehen! Sie können lambdaes mit Ihrer Datenstruktur übernehmen und implementieren (OCaml hat Zeiger, sie werden Referenzen genannt ). Mehr oder weniger müssen Sie nur syntax.mlund norm.mldurch Ihre Versionen ersetzen . Das sind weniger als 150 Codezeilen.

Andere Antworten befassen sich hauptsächlich mit Implementierungsproblemen. Da Sie Ihre Hauptmotivation als mathematische Beweise ohne zu viel Buchhaltung erwähnen, ist hier das Hauptproblem, das ich damit sehe.

Wenn Sie sagen "eine Funktion, die jede Variable einem Ordner zuordnet, in dessen Bereich sie liegt": Der Ausgabetyp dieser Funktion ist sicherlich etwas subtiler, als es sich anhört! Insbesondere muss die Funktion Werte in so etwas wie „den Bindemitteln des betrachteten Begriffs“ annehmen - dh einer Menge, die je nach Begriff variiert (und offensichtlich keine Teilmenge einer größeren Umgebungsmenge in irgendeiner nützlichen Weise ist). Bei der Substitution können Sie also nicht einfach „die Vereinigung der Bindungsfunktionen übernehmen“: Sie müssen auch ihre Werte neu indizieren, gemäß einer Zuordnung von Bindemitteln in den ursprünglichen Begriffen zu Bindemitteln im Ergebnis der Substitution.

Diese Neuindizierungen sollten sicherlich „Routine“ sein, in dem Sinne, dass sie vernünftigerweise entweder unter den Teppich gekehrt oder in Bezug auf eine Art Funktionalität oder Natürlichkeit gut verpackt werden könnten. Gleiches gilt jedoch für die Buchhaltung bei der Arbeit mit benannten Variablen. Insgesamt scheint es mir also wahrscheinlich, dass mit diesem Ansatz mindestens so viel Buchhaltung verbunden ist wie mit Standardansätzen.

Abgesehen davon ist es jedoch ein konzeptionell sehr ansprechender Ansatz, und ich würde es gerne sorgfältig ausgearbeitet sehen - ich kann mir gut vorstellen, dass er einige Aspekte der Syntax in einem anderen Licht erscheinen lässt als die Standardansätze.

$\lambda$Lazy.t

Insgesamt denke ich, dass es eine coole Darstellung ist, aber es beinhaltet einige Buchhaltung mit Zeigern, um das Brechen von Bindungslinks zu vermeiden. Es wäre möglich, den Code zu ändern, um veränderbare Felder zu verwenden, aber die Codierung in Coq wäre dann weniger direkt. Ich bin immer noch davon überzeugt, dass dies HOAS sehr ähnlich ist, obwohl die Zeigerstruktur explizit gemacht wird. Das Vorhandensein von Lazy.timpliziert jedoch, dass ein Code möglicherweise zur falschen Zeit ausgewertet wird. Dies ist in meinem Code nicht der Fall, da zur Zeit nur eine Ersetzung einer Variablen durch eine Variable erfolgen kann force(und beispielsweise keine Auswertung).

(* Representation of a term of the λ-calculus. *)
type term =
  | FVar of string      (* Free variable  *)
  | BVar of bvar        (* Bound variable *)
  | Appl of term * term (* Application    *)
  | Abst of abst        (* Abstraction    *)

(* A bound variable is a pointer to the corresponding binder. *)
and bvar = abst

(* A binder is represented as its body in which the bound variable points to
   the binder itself. Note that we need to use a thunk to be able to work
   underneath a binder (for substitution, evaluation, ...). A name can be
   given for easy printing, but no renaming is done. Only “visual capture”
   can happen since pointers are established the right way, even if names
   can clash. *)
and abst = { body : term Lazy.t ; name : string }

(* Terms can be built with recursive values for abstractions. *)

(* Krivine's notation is used for application (function in parentheses). *)

let id    : term = (* λx.x        *)
  Abst(let rec id = {body = lazy (BVar(id)); name = "x"} in id)

let idid  : term = (* (λx.x) λx.x *)
  Appl(id, id)

let delta : term = (* λx.(x) x *)
  Abst(let rec d = {body = lazy (Appl(BVar(d), BVar(d))); name = "x" } in d)

let weird : term = (* (λx.x) λy.(λx.(x) x) (C) y *)
  Appl(id, Abst(let rec x = {body = lazy (Appl(delta, Appl(FVar("C"),
    BVar(x)))); name = "y"} in x))

let omega : term = (* (λx.(x) x) λx.(x) x *)
  Appl(delta, delta)

(* Printing function is immediate. *)
let rec print : out_channel -> term -> unit = fun oc t ->
  match t with
  | FVar(x)   -> output_string oc x
  | BVar(x)   -> output_string oc x.name
  | Appl(t,u) -> Printf.fprintf oc "(%a) %a" print t print u
  | Abst(f)   -> Printf.fprintf oc "λ%s.%a" f.name print (Lazy.force f.body)

(* Substitution of variable [x] by [v] in the term [t]. Occurences of [x] in
   [t] are identified using physical equality ([BVar] case). The subtle case
   is [Abst], because we need to reestablish the physical link between the
   binder and the variable it binds. *)
let rec subst_var : bvar -> term -> term -> term = fun x t v ->
  match t with
  | FVar(_)   -> t
  | BVar(y)   -> if y == x then v else t
  | Appl(t,u) -> Appl(subst_var x t v, subst_var x u v)
  | Abst(f)   ->
      (* First compute the new body. *)
      let fv = subst_var x (Lazy.force f.body) v in
      (* Reestablish the physical link, using [subst_var] itself again. This
         requires a second traversal of the term. We could probably do both
         at once, but who cares the complexity is linear in [t] anyway. *)
      Abst(let rec g = {f with body = lazy (subst_var f fv (BVar(g)))} in g)

(* Actual substitution function. *)
let subst : abst -> term -> term = fun f v ->
  subst_var f (Lazy.force f.body) v

(* Normalization function (all the way, even under binders). *)
let rec eval : term -> term = fun t ->
  match t with
  | Appl(t,u) ->
      begin
        let v = eval u in
        match eval t with
        | Abst(f) -> eval (subst f v)
        | t       -> Appl(t,v)
      end
  | Abst(f)   ->
      (* Actual computation in the body. *)
      let fv = eval (Lazy.force f.body) in
      (* Here, the physical link is reestablished, but it is important to note
         that the computation of evaluation is done above. So the part below
         only takes a linear time in the size of the normal form of the body
         of the abstraction. *)
      Abst(let rec g = {f with body = lazy (subst_var f fv (BVar(g)))} in g)
  | _         ->
      t

let _ = Printf.printf "id         = %a\n%!" print id
let _ = Printf.printf "eval id    = %a\n%!" print (eval id)

let _ = Printf.printf "idid       = %a\n%!" print idid
let _ = Printf.printf "eval idid  = %a\n%!" print (eval idid)

let _ = Printf.printf "delta      = %a\n%!" print delta
let _ = Printf.printf "eval delta = %a\n%!" print (eval delta)

let _ = Printf.printf "omega      = %a\n%!" print omega
(* The following obviously loops. *)
(*let _ = Printf.printf "eval omega = %a\n%!" print (eval omega)*)

let _ = Printf.printf "weird      = %a\n%!" print weird
let _ = Printf.printf "eval weird = %a\n%!" print (eval weird)

(* Output produced:
id         = λx.x
eval id    = λx.x
idid       = (λx.x) λx.x
eval idid  = λx.x
delta      = λx.(x) x
eval delta = λx.(x) x
omega      = (λx.(x) x) λx.(x) x
weird      = (λx.x) λy.(λx.(x) x) (C) y
eval weird = λy.((C) y) (C) y
*)