сопоставление с образцом - реализация - PullRequest
Новая
       30

сопоставление с образцом - реализация

30 голосов
/ 25 февраля 2009

Мне интересно, как обычно осуществляется сопоставление с образцом. например, в Erlang вы думаете, что он реализован на уровне байт-кода (есть байт-код для его эффективного выполнения) или он генерируется компилятором как серия инструкций (ряд байт-кодов)? это настолько полезная вещь, что я просто должен поместить это в игрушечный язык, который я строю большое спасибо

(ссылки более приветствуются)

Ответы [ 4 ]

30 голосов
/ 13 марта 2009

Очень хорошее описание компиляции сопоставления с образцом дано в «Реализации функциональных языков программирования» Саймона Пейтона Джонса. Это немного старая, но очень хорошая книга. Он также содержит, среди прочего, описание составления списков.

Компилятор Erlang использует оба этих алгоритма из книги.

19 голосов
/ 25 февраля 2009

Вы можете увидеть, что произойдет, если скомпилировать код 

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

Когда вы хотите увидеть, как выглядит core 

> 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, и вы можете посмотреть каждый этап компиляции в исходном коде модуля compile и подробности в зависимых модулях.

13 голосов
/ 26 февраля 2009

Если вы хотите создать свой собственный сопоставитель шаблонов, есть бумага Скотта и Рэмси и бумага Люка Маранджета , в которых описано, как скомпилировать шаблоны для эффективных деревьев решений ака вложенные операторы switch).

2 голосов
/ 25 февраля 2009

Лучшее, что я могу предложить, - это скомпилировать некоторые тестовые функции и взглянуть на сгенерированный код. 

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