模式匹配 - 实现

Question

我想知道如何通常实现模式匹配.例如在Erlang中你认为它是在字节码级实现的(它有一个字节码,以便它有效地完成),还是由编译器生成一系列指令(字节码系列)？它是如此有用的东西,我只需要把它变成玩具语言我非常感谢你

(链接更受欢迎)

Answer 1

Simon Peyton Jones在"函数式编程语言的实现"中给出了编译模式匹配的非常好的描述.它有点旧,但是一本非常好的书.除其他外,它还包含编译列表推导的描述.

Erlang编译器使用了本书中的这两种算法.

Answer 2

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

-module(match).
-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]
    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)

如果你想看到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}]}.
    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}}.

正如你所看到的{test,is_tuple,...,{test,test_arity,...,{get_tuple_element,...和{test,is_eq_exact,...是指令这场比赛是如何在束完成,它的直接转化为梁的字节码.

Erlang编译器是在Erlang本身实现的,您可以在编译模块的源代码中查看编译的每个阶段,并在依赖模块中查看详细信息.

Answer 3

如果你想建立自己的模式匹配器,Scott和Ramsey的论文和Luc Maranget的论文都描述了如何将模式编译成有效的决策树(也就是嵌套的switch语句).