pattern matching - la mise en œuvre

StackOverflow https://stackoverflow.com/questions/586362

Question

Im se demandant comment pattern matching est généralement mis en œuvre. par exemple dans Erlang pensez-vous que sa mise en œuvre au niveau de bytecode (il y a un bytecode pour cela de sorte que son efficacité fait) ou est-il généré une série d'instructions (série de bytecode) par le compilateur? il est une chose utile que je viens de le mettre dans une langue de jouets bâtiment Im je vous remercie beaucoup

(liens sont plus de bienvenue)

Était-ce utile?

La solution

Vous pouvez voir ce qui se passe si la compilation du code 

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

Si vous voulez voir comment ressemble 

> c(match, to_core).

ou 

$ erlc +to_core match.erl

résultat est 

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)

Si vous voulez voir le code asm du faisceau que vous pouvez faire 

> c(match, 'S').

ou 

$ erlc -S match.erl

et le résultat 

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

Comme vous pouvez le voir {test,is_tuple,..., {test,test_arity,..., {get_tuple_element,... et {test,is_eq_exact,... sont l'instruction comment cette correspondance est réalisée en faisceau et il est transformé directement à octet code de faisceau.

compilateur Erlang est mis en œuvre Erlang lui-même et vous pouvez regarder à chaque phase de compilation dans le code source de

Autres conseils

Une très bonne description de la compilation pattern matching est donnée dans « La mise en œuvre des langages de programmation fonctionnelle » par Simon Peyton Jones. Il est un peu vieux, mais un très bon livre. Il contient également, entre autres, une description de la compilation compréhensions de la liste.

Le compilateur Erlang utilise ces deux algorithmes du livre.

Si vous voulez construire votre propre modèle matcher il y a un par Scott et Ramsey et un par Luc Maranget qui décrivent tous deux comment compiler des modèles pour les arbres de décision efficaces (états de commutation aka imbriquées).

La meilleure chose que je peux suggérer, est de compiler quelques fonctions de test et regarder le code généré. 

erlc -S test.erl

génère test.S qui est assez lisible.

Pour répondre à la question, les matches de motif sont construits de manière efficace des opérations plus primitives. Voici une partie du code à partir d'une correspondance de clause de fonction {X, [H | T]}. 

{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}]}.
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top