Können wir alle Computerprogramme als Grafiken darstellen?

7

Ich habe neulich nachgedacht, und mir ist aufgefallen, dass Computerprogramme alle als Diagramm (z. B. ein abstrakter Syntaxbaum) oder, sobald gemeinsame Ausdrücke kombiniert sind, als abstraktes Syntaxdiagramm darstellbar zu sein scheinen.

Mir ist aufgefallen, dass vielleicht jedes Computerprogramm als eines dieser Diagramme + Bewertungssemantik dargestellt werden kann. Ich bin neugierig, ob jemand weiß, ob dies für eine Turingmaschine allgemein gilt (ich gehe davon aus, dass Sie einen potenziell unendlichen Graphen erhalten können, aber dies ist Mathematik, also ist das in Ordnung). Ich habe darüber nachgedacht und viele Dinge wie starke Typsysteme und solche passen gut in diese Abstraktion (sie legen dem Graphen strukturelle Einschränkungen auf). Möglicherweise können Sie das Typsystem sogar als eigenes Programm betrachten und es als eine andere Grafik + Bewertungssemantik darstellen, die auf der Programmgrafik ausgeführt wird ...

Nur neugierig, ob dies eine bekannte Äquivalenz ist oder nicht.

graphs turing-machines machine-models gct
quelle
Es ist ein ziemlich grundlegendes Konzept zur Optimierung des Compiler-Designs.
Keshlam
1
Ich kann jede mathematische Gleichung grafisch darstellen. Was ist der Sinn?
Val
Eine ziemlich bizarre Antwort: Es ist bekannt, dass zeitkontinuierliche Quanten-Zufallsläufe universell berechnet werden können - genau wie adiabatische Quantencomputer. Sogar Schaltpläne sind technisch gesehen Graphen mit Eckpunkten, die als Funktionen fungieren, und diese können auch universell berechnet werden. nicht ganz das, woran du gedacht hast, wie es schien :)
hatte

Antworten:

10

Ich weiß nicht, ob es eine besonders bekannte Äquivalenz ist, aber es ist ziemlich einfach, wenn man darüber nachdenkt.

Es ist bekannt, dass Turingmaschinen dem (untypisierten) Lambda-Kalkül entsprechen. Die Church-Turing-These besagt, dass dies die mächtigste Form der Berechnung ist.

Der Lambda-Kalkül ist ein syntaktisch definiertes System zum Umschreiben von Begriffen. Im Wesentlichen ist es eine sehr einfache Programmiersprache. So kann es in einen abstrakten Syntaxbaum (Graph) analysiert werden.

Also haben wir:

  1. Jedes Computerprogramm ist in der untypisierten Lambda-Rechnung darstellbar.
  2. Jedes Lambda-Kalkülprogramm kann in einen abstrakten Syntaxbaum analysiert werden

Dies bedeutet, dass jedes Computerprogramm als abstrakter Lambda Calculus-Syntaxbaum dargestellt werden kann.

Diese Bäume haben möglicherweise nicht viel an interessanten Eigenschaften. Zum Beispiel sind sie definitiv nicht eindeutig, dh zwei verschiedene Bäume können identische Berechnungen durchführen.

jmite
quelle
1
Sie können auch eine Turing-vollständige Programmiersprache für allgemeine Zwecke (vorzugsweise strukturiert) verwenden. In der statischen Analyse werden Programme auch als Diagramme mit Zyklen dargestellt.
Bellpeace