Мне интересно, как обычно выполняется сопоставление шаблонов. например, в Erlang вы думаете, что он реализован на уровне байтового кода (там байт-код для него так, чтобы он выполнялся эффективно), или он генерируется компилятором в виде серии инструкций (серии байт-кодов)? это такая полезная вещь, что мне просто нужно положить ее в игрушечный язык Im building большое спасибо
(ссылки более приветствуются)
Вы можете увидеть, что произойдет, если скомпилировать код
-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 и детали в зависимости модули.
Очень хорошее описание компиляции соответствия шаблонов приведено в "Реализация языков функционального программирования" Саймона Пейтона Джонса. Это немного старая, но очень хорошая книга. Он также содержит, среди прочего, описание компиляции списков.
Компилятор Erlang использует оба этих алгоритма из книги.
Если вы хотите создать свой собственный шаблонный шаблон, бумага Скотта и Рэмси и статья Luc Maranget, в которой описывается, как скомпилировать шаблоны для эффективных деревьев решений (например, вложенные операторы switch).
Лучшее, что я могу предложить, - это скомпилировать некоторые тестовые функции и посмотреть на сгенерированный код.
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}]}.