模式匹配 - 实现 [英] pattern matching - implementation

问题描述

我想知道模式匹配是如何实现的。例如在Erlang你认为它是在字节码级别实现的（有一个字节码，以便它的高效完成），或者它是由编译器生成的一系列指令（一系列字节码）？
这是一个有用的事情，我只需要把它放入一个玩具语言我建立
非常感谢你

（链接更多然后欢迎）

解决方案

你可以看到编译一些代码会发生什么

   - 模（匹配）。 
 -export（[match / 1]）。 
 match（X） - > {a，Y} = X. 
  

当你想看看如何看起来像核心

 > c（match，to_core）。 
  

或

  $ erlc + to_core match.erl 
  

结果是

  module'match'['match'/ 1，
'module_info'/ 0，
'module_info'/ 1] 
属性[] 
'match'/ 1 = 
 %%行3 
 fun（_cor0） - > 
 case _cor0 of 
< {'a'，Y}>当'true' - > 
 _cor0 
（< _cor1> when'true' - > 
 primop'match_fail'
（{'badmatch'，_ cor1}）
  - compile_generated']）
 end 
'module_info'/ 0 = 
 fun（） - > 
调用'erlang'：'get_module_info'
（'match'）
'module_info'/ 1 = 
 fun（_cor0） - > 
调用'erlang'：'get_module_info'
（'match'，_cor0）
  

如果你想看到你可以做的光束的asm代码

 > c（match，'S'）。 
  

或

  $ erlc -S match.erl 
  

结果

  {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}]}。 
返回。 
 {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}}。 
  

正如你可以看到 {test，is_tuple，... ， {test，test_arity，... ， {get_tuple_element，... 和 {test，is_eq_exact，... 是指示如何在波束中执行此匹配，并直接转换为波束的字节码。

Erlang编译器在Erlang本身实现，您可以在编译模块和依赖模块中的详细信息。

Im wondering how pattern matching is usually implemented. for example in Erlang do you think its implemented at the byte-code level(there's a bytecode for it so that its done efficiently) or is it generated as a series of instructions(series of bytecodes) by the compiler? it is such a useful thing that I just have to put it into a toy language Im building thank you very much

(links are more then welcome)

解决方案

You can see what happen if compile some code

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

When you want see how looks like core

> c(match, to_core).

or

$ erlc +to_core match.erl

result is

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)

If you want see asm code of beam you can do

> c(match, 'S').

or

$ erlc -S match.erl

and result

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

As you can see {test,is_tuple,..., {test,test_arity,..., {get_tuple_element,... and {test,is_eq_exact,... are instruction how this match is performed in beam and it's transformed directly to byte-code of beam.

Erlang compiler is implemented in Erlang itself and you can look at each phase of compilation in source code of compile module and details in depend modules.

这篇关于模式匹配 - 实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！