34

パターンマッチングは通常どのように実装されているのだろうか。たとえばErlangでは、バイトコードレベルで実装されていると思いますか（効率的に実行できるようにバイトコードがあります）、それともコンパイラによって一連の命令（一連のバイトコード）として生成されますか？

これは非常に便利なので、作成中のおもちゃの言語に組み込む必要があります。

4

4 に答える 4

35

サイモン ペイトン ジョーンズによる「関数型プログラミング言語の実装」には、パターン マッチングのコンパイルに関する非常に適切な説明が記載されています。少し古い本ですがとても良い本です。また、とりわけ、リスト内包表記のコンパイルに関する説明も含まれています。

Erlang コンパイラは、本にあるこれらのアルゴリズムの両方を使用します。

于 2009-03-13T14:11:19.013 に答える
20

いくつかのコードをコンパイルするとどうなるかを見ることができます

-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自体に実装されており、コンパイルモジュールのソースコードと依存モジュールの詳細でコンパイルの各フェーズを見ることができます。

于 2009-02-25T16:27:23.573 に答える
14

独自のパターン マッチャーを作成する場合は、Scott と Ramsey による論文と Luc Maranget による論文があり、どちらもパターンを効率的な決定木 (ネストされた switch ステートメント) にコンパイルする方法を説明しています。

于 2009-02-26T03:39:21.977 に答える
2

私が提案できる最善の方法は、いくつかのテスト関数をコンパイルして、生成されたコードを確認することです。

erlc -S test.erl

かなり読みやすい test.S を生成します。

この質問に答えるために、パターン マッチはより基本的な操作から効率的な方法で構築されます。{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}]}.
于 2009-02-25T16:23:10.870 に答える