Wie behandelt der Erlang-Compiler den Mustervergleich? Was gibt er aus?

Question

Ich habe gerade eine Frage darüber gestellt, wie der Erlang-Compiler Pattern-Matching implementiert, und ich habe einige großartige Antworten erhalten, von denen eine der kompilierte Bytecode ist (den man mit einem Parameter erhält, der an die Funktion c() Richtlinie):

{function, match, 1, 2}.
  {label,1}.
    {func_info,{atom,match},{atom,match},1}.
  {label,2}.
    {test,is_tuple,{f,3},[{x,0}]}.
    {test,test_arity,{f,3},[{x,0},2]}.
    {get_tuple_element,{x,0},0,{x,1}}.
    {test,is_eq_exact,{f,3},[{x,1},{atom,a}]}.
    return.
  {label,3}.
    {badmatch,{x,0}}

Es sind alles nur einfache Erlang-Tupel. Ich erwartete einige kryptische binäre thingy, schätze nicht. Ich frage dies auf Impuls hier (ich könnte auf den Compiler-Quellcode schauen, aber Fragen zu stellen endet immer besser mit zusätzlichen Einblick), wie wird diese Ausgabe in der binären Ebene übersetzt?

Sagen Sie {test,is_tuple,{f,3},[{x,0}]} zum Beispiel. Ich gehe davon aus, dass es sich um eine Anweisung namens "test" handelt... Jedenfalls wäre diese Ausgabe im Wesentlichen der AST der Bytecode-Ebene, aus dem die binäre Kodierung nur eine 1-1-Übersetzung ist?

Das ist alles so aufregend, ich hatte keine Ahnung, dass ich so einfach sehen kann, in was der Erlang-Compiler Dinge zerlegt.

Answer 1

Ok, also habe ich in den Compiler-Quellcode gegraben, um die Antwort zu finden, und zu meiner Überraschung wird die mit dem Parameter 'S' für die Funktion compile:file() erzeugte asm-Datei tatsächlich so konsultiert, wie sie ist (file:consult()), und dann werden die Tupel einzeln für weitere Aktionen überprüft (Zeile 661 - beam_consult_asm(St) -> - compile. erl). weiter unten gibt es dann eine generierte Mapping-Tabelle (Compile-Ordner des Erlang-Source), die zeigt, was die Seriennummer jedes Bytecode-Labels ist, und ich vermute, dass dies verwendet wird, um die tatsächliche binäre Signatur des Bytecodes zu generieren. großartiges Zeug. aber man muss einfach die consult()-Funktion lieben, man kann fast eine lispy Typsyntax für eine beliebige Sprache haben und die Notwendigkeit für einen Parser/Lexer vollständig vermeiden und einfach Quellcode in den Compiler konsultieren und etwas damit machen... Code als Daten Daten als Code...

Answer 2

Der Compiler hat eine sogenannte Mustervergleichs-Compiler das ein Muster zu einer Reihe von Verzweigungen, Schaltern und dergleichen kompiliert. Der Code für Erlang befindet sich in v3_kernel.erl im Compiler. Es verwendet Simon Peyton Jones, "The Implementation of Functional Programming Languages", online verfügbar unter

http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

Eine weitere beachtenswerte Arbeit ist die von Peter Sestoft,

http://www.itu.dk/~sestoft/papers/match.ps.gz

das einen Compiler für die Musterübereinstimmung ableitet, indem es die partielle Auswertung eines einfacheren Systems untersucht. Es ist vielleicht einfacher zu lesen, besonders wenn Sie ML kennen.

Der Grundgedanke ist, dass man, wenn man z. B.:

% 1
f(a, b) ->
% 2
f(a, c) ->
% 3
f(b, b) ->
% 4
f(b, c) ->

Nehmen wir nun an, wir haben einen Aufruf f(X, Y) . Sagen Sie X = a . Dann sind nur 1 und 2 anwendbar. Wir prüfen also Y = b y luego Y = c . Wenn auf der anderen Seite X /= a dann wissen wir, dass wir überspringen 1 und 2 und beginnen Sie mit den Tests 3 und 4. Der Schlüssel ist, dass wenn etwas nicht no Spiel sagt uns etwas darüber, wo das Spiel fortgesetzt werden kann und wann wir ein Spiel machen. Es handelt sich um eine Reihe von Beschränkungen, die wir durch Testen lösen können.

Pattern-Match-Compiler versuchen, die Anzahl der Tests so zu optimieren, dass möglichst wenige Tests durchgeführt werden müssen, bevor eine Schlussfolgerung gezogen werden kann. Statisch typisierte Sprachen haben hier einige Vorteile, da sie das wissen können:

-type foo() :: a | b | c.

und wenn wir dann

-spec f(foo() -> any().
f(a) ->
f(b) ->
f(c) ->

und wir haben nicht übereingestimmt f(a), f(b) dann f(c) debe Spiel. Erlang muss dies prüfen und scheitert dann, wenn es nicht übereinstimmt.