Lambda MicroEgg es una pequeña herramienta de reescritura basada en expresiones-S, construida alrededor de la elevación de las ideas de los grafos de equivalencia. Un grafo de equivalencia, o e-graph, almacena a la vez muchas formas equivalentes de una expresión; las reglas de reescritura añaden alternativas, y el motor puede extraer más tarde una forma más simple o útil de otro modo. El caso difícil aquí es el alcance: en una expresión lambda, un nombre de variable pertenece al enlazador más cercano, por lo que una reescritura no debe permitir por accidente que se refiera a la variable equivocada.
Colocada después de la explicación inicial de Lambda MicroEgg y los grafos de equivalencia, donde se presenta el propio proyecto.
El proyecto representa los enlazadores de forma genérica. Tanto `(@sum x BODY)` como `(@lam x BODY)` usan la misma estructura interna `Binder(Symbol, Id)`; `lam` es solo el símbolo convencional para el cálculo lambda. Los lados derechos de las reglas de reescritura también pueden solicitar una sustitución explícita mediante `#subst`, lo que reduce el riesgo de que mover un término a través de enlazadores capture una variable libre.
La correspondencia de patrones se restringe deliberadamente a patrones de Miller, una forma manejable de patrón de orden superior. En un patrón como `{?a x}`, la metavariable `?a` puede representar un cuerpo que contiene la variable enlazada distinta `x`, pero no puede capturar una variable no relacionada como `y`. Esa restricción hace que la correspondencia con alcance sea más fácil de implementar que la correspondencia de patrones de orden superior completa, que puede codificar problemas indecidibles. Un ejemplo de reducción beta proporcionado reescribe `[((@lam x {?body x}) ?e)]` como `[{?body ?e}]` y extrae `42` de aplicar la función identidad a `42`.
La implementación también usa anotaciones de adelgazamiento para rastrear cómo se mueven los términos entre contextos de variables. El autor informa de que los términos alfa-equivalentes —términos que difieren solo por un cambio de nombre de variables coherente— se consolidan por hash en la misma representación interna, mientras que los términos relacionados por debilitamiento pueden compartir parte de la memoria más profunda. Esta es una afirmación de diseño del proyecto, no un resultado de una evaluación independiente.
La principal compensación es el rendimiento frente a la expresividad. La página del autor informa de que una ejecución de saturación de orden superior fue más lenta que una ejecución similar con `egg`, y de que cambiar de aplicación de primer orden a aplicación de orden superior añadió coste. Lambda MicroEgg admite patrones de Miller ordenados, por lo que un patrón no lineal que usa la misma metavariable en un orden de argumentos diferente se rechaza en lugar de gestionarse en silencio. El repositorio describe puntos de entrada para la línea de comandos y una demostración en WebAssembly, pero el paquete no establece una adopción más amplia, garantías de corrección ni rendimiento en producción.