coincidencia de patrones - implementación

Question

Me pregunto cómo se suele implementar la coincidencia de patrones. por ejemplo, en Erlang, ¿cree que está implementado en el nivel de código de bytes (hay un bytecode para que se haga de manera eficiente) o se genera como una serie de instrucciones (series de códigos de bytes) por el compilador? es una cosa tan útil que sólo tengo que ponerlo en un edificio Im lenguaje de juguete muchas gracias

(enlaces son más que bienvenidos)

Answer 1

Se puede ver lo que sucedería si compilar un código

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

Cuando se quiere ver cómo se parece a core

> c(match, to_core). 

o

$ erlc +to_core match.erl 

resultado es

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) 

Si desea ver el código asm de la viga que puede hacer

> c(match, 'S'). 

o

$ erlc -S match.erl 

y el resultado

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

Como se puede ver {test,is_tuple,..., {test,test_arity,..., {get_tuple_element,... y {test,is_eq_exact,... son instrucciones de cómo se realiza esta coincidencia en haz y se transforma directamente en código de byte de haz.

El compilador Erlang se implementa en Erlang y se puede ver cada fase de compilación en el código fuente del módulo compile y los detalles en los módulos dependientes.

Answer 2

Lo mejor que puedo sugerir es para compilar hasta algunas funciones de prueba y eche un vistazo al código generado.

erlc -S test.erl 

genera test.S que es bastante legible.

Para responder a la pregunta, las coincidencias de patrones se crean de forma eficiente a partir de operaciones más primitivas. Aquí hay una parte del código de una cláusula de función que coincide con {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}]}. 

Answer 3

Si desea construir su propio patrón de coincidencia existe un paper by Scott and Ramsey y un paper by Luc Maranget que describen cómo compilar patrones para árboles de decisión eficientes (también conocidos como declaraciones de cambio anidado).

Answer 4

Una muy buena descripción de la coincidencia de patrones de compilación figura en "La implementación de lenguajes de programación funcionales" por Simon Peyton Jones. Es un poco viejo pero un libro muy bueno. También contiene, entre otras cosas, una descripción de la compilación de listas de comprensión.

El compilador de Erlang utiliza estos dos algoritmos del libro.