Mustererkennung - Implementierung

Question

Ich frage mich, wie Mustererkennung normalerweise implementiert wird. zum Beispiel in Erlang denken Sie, dass es auf der Byte-Code-Ebene implementiert ist (es gibt einen Bytecode, damit es effizient gemacht wird) oder wird es als eine Folge von Anweisungen (Reihe von Bytecodes) vom Compiler erzeugt? es ist so eine nützliche Sache, die ich gerade in ein Spielzeug Sprache Im Gebäude setzen müssen Ihnen danken sehr viel

(Links sind mehr als willkommen)

Answer 1

Sie können sehen, was passiert, wenn etwas Code kompilieren

-module(match). 
-export([match/1]). 
match(X) -> {a,Y} = X. 

Wenn Sie sehen möchten, wie sieht aus wie core

> c(match, to_core). 

oder

$ erlc +to_core match.erl 

Ergebnis ist

module 'match' ['match'/1, 
       'module_info'/0, 
       'module_info'/1] 
    attributes [] 
'match'/1 = 
    %% Line 3 
    fun (_cor0) -> 
     case _cor0 of 
      <{'a',Y}> when 'true' -> 
       _cor0 
      (<_cor1> when 'true' -> 
       primop 'match_fail' 
        ({'badmatch',_cor1}) 
      -| ['compiler_generated']) 
     end 
'module_info'/0 = 
    fun() -> 
     call 'erlang':'get_module_info' 
      ('match') 
'module_info'/1 = 
    fun (_cor0) -> 
     call 'erlang':'get_module_info' 
      ('match', _cor0) 

Wenn Sie asm wollen Code des Strahls sehen Sie

> c(match, 'S'). 

oder

tun können

$ erlc -S match.erl 

und führen

{module, match}. %% version = 0 

{exports, [{match,1},{module_info,0},{module_info,1}]}. 

{attributes, []}. 

{labels, 8}. 


{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}}. 


{function, module_info, 0, 5}. 
    {label,4}. 
    {func_info,{atom,match},{atom,module_info},0}. 
    {label,5}. 
    {move,{atom,match},{x,0}}. 
    {call_ext_only,1,{extfunc,erlang,get_module_info,1}}. 


{function, module_info, 1, 7}. 
    {label,6}. 
    {func_info,{atom,match},{atom,module_info},1}. 
    {label,7}. 
    {move,{x,0},{x,1}}. 
    {move,{atom,match},{x,0}}. 
    {call_ext_only,2,{extfunc,erlang,get_module_info,2}}. 

Wie Sie {test,is_tuple,... sehen können, {test,test_arity,..., {get_tuple_element,... und {test,is_eq_exact,... sind eine Anweisung, wie diese Übereinstimmung im Strahl ausgeführt wird, und sie wird direkt in den Byte-Code des Strahls transformiert.

Erlang Compiler ist in Erlang selbst implementiert und Sie können jede Phase der Kompilierung im Quellcode von compile Modul und Details in Abhängigkeit Module betrachten.

Answer 2

Das Beste, was ich vorschlagen kann, ist bis zu kompilieren einige Testfunktionen und werfen einen Blick auf den generierten Code.

erlc -S test.erl 

generiert test.S, die ziemlich lesbar ist.

Um die Frage zu beantworten, werden Musterübereinstimmungen effizient aus primitiveren Operationen aufgebaut. Hier ist ein Teil des Codes aus einer Funktionsklausel, die {X, [H | T]} entspricht.

{test,is_tuple,{f,1},[{x,0}]}. 
{test,test_arity,{f,1},[{x,0},2]}. 
{get_tuple_element,{x,0},0,{x,1}}. 
{get_tuple_element,{x,0},1,{x,2}}. 
{test,is_nonempty_list,{f,4},[{x,2}]}. 

Answer 3

Wenn Sie Ihren eigenen Muster-Matcher erstellen möchten, gibt es eine paper by Scott and Ramsey und eine paper by Luc Maranget, die beide beschreiben, wie man Muster zu effizienten Entscheidungsbäumen (auch verschachtelte Schalteranweisungen) kompiliert.

Answer 4

Eine sehr gute Beschreibung des Compiling Pattern Matchings finden Sie in "Die Implementierung funktionaler Programmiersprachen" von Simon Peyton Jones. Es ist ein bisschen alt, aber ein sehr gutes Buch. Es enthält unter anderem auch eine Beschreibung der Kompilierung von Listen.

Der Erlang-Compiler verwendet beide Algorithmen aus dem Buch.