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

Question

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

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

Answer 1

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

-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-код beam, вы можете сделать

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

Компилятор Erlang реализован в самом Erlang, и вы можете посмотреть на каждый этап компиляции в исходном коде скомпилировать модуль и детали в зависимых модулях.

Answer 2

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

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

Answer 3

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

Answer 4

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

erlc -S test.erl

генерирует тест.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}]}.