embedded - ¿Es posible tener un tiempo real difícil con alcance léxico?

lisp scope

Question

Estaba leyendo este artículo sobre el problema del funarg, que es realmente el problema de mantener los entornos de cierres léxicos. Es un documento antiguo y no estoy seguro si las conclusiones del autor aún se mantienen, pero él insiste fuertemente en que, para tener un alcance léxico más que dinámico, debes abandonar la pila tradicional de estilo C y, en cambio, tener una estructura de árbol de entornos, asignados desde el montón.

¿Esto hace que sea imposible tener cierres de ámbito léxico en cualquier sistema de tiempo real? en los sistemas embebidos en tiempo real, donde las latencias se miden en microsegundos, la asignación de los montones generalmente está prohibida debido a la latencia no determinista que introduce.

Esta ha sido una curiosidad mía, porque hago mi pan mayormente como desarrollador de firmware donde C es el lenguaje de facto, y por un tiempo ahora parece que he estado usando mi poder cerebral para descubrir cómo forzar C a déjame hacer cosas que vienen gratis en idiomas más sofisticados. En consecuencia, comencé a preguntarme si podría implementar un compilador de micro-lisp específicamente para sistemas basados ​​en microcontroladores embebidos en tiempo real.

Como nota al margen: últimamente obtuve grandes conocimientos sobre temas profundos, como el cierre y los objetos son equivalentes, y así sucesivamente, y me da mayor admiración de tipos como Stallman y Rich Hickey, y Paul Graham. Implementar Lisp desde cero parece una tarea desalentadora para mí. Es difícil saber por dónde empezar. (Tal vez con la implementación de PG de la función de evaluación original de McCarthy, IDK). De todos modos, estoy divagando.

Answer 1

El alcance léxico es obviamente posible con "tiempo real", después de todo, usted dice que está usando C para aplicaciones en tiempo real, y C es un lenguaje de ámbito léxico. Supongo que realmente te preocupan las funciones de primera clase, no el alcance léxico. Asumiendo eso, hay un montón de técnicas de compilación conocidas para manejar eficientemente las funciones de primera clase.

En primer lugar, lo que verás en los libros de texto, etc. casi siempre está haciendo el entorno usual en forma de árbol, pero en la práctica eso no es necesario en absoluto si las funciones no se usan como valores. Prácticamente todo compilador decente del lenguaje funcional identificará dicho código y usará la pila en su lugar, por lo que no hay gastos generales para la asignación. (Tenga en cuenta que en este punto esto significa que si se limita al tipo de cosas que escribe en C, entonces no se necesita asignación). Entonces, hay muchas maneras adicionales de reducir las asignaciones, por ejemplo, considere algo como (lambda (x) (* x 9)) - esta función realmente no se cierra sobre ningún identificador libre, y por lo tanto los compiladores lo levantarán a la cima para que haya una sola copia de la función y, nuevamente, ninguna asignación. (Nota relacionada: con esta optimización ya obtienes más de lo que C te da y aún no hay asignación).

Hay un montón de optimizaciones adicionales que evitan la asignación, pero, por supuesto, hay casos en los que realmente necesita asignar un nuevo cierre. Pero estos lugares son identificables estáticamente, y si realmente te importan esas asignaciones, entonces no debería ser difícil piratear un compilador que te advierta sobre tales asignaciones. Ha habido una cantidad de tales idiomas, vea por ejemplo META , el nivel previo de muy bajo nivel. Pero IME la mayoría de las personas se familiariza rápidamente con las cosas y se hace obvio dónde ocurren las asignaciones, de modo que obtienes el beneficio de un lenguaje de alto nivel, y cuando se trata de un código que deseas optimizar, es fácil ver dónde ocurre la asignación. , y es fácil evitarlo de la manera habitual. (Y, por supuesto, todo esto no está relacionado con la optimización de asignaciones).

Answer 2

Encontré algunos asignadores en tiempo real, así que diría. alcance léxico en tiempo real es posible:

http://rtportal.upv.es/rtmalloc/

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.441&rep=rep1&type=pdf

Agregando a su digesión, antes de escribir mi propio micro-lisp, trataría de encontrar o portar lua para el sistema incrustado en cuestión. Es muy pequeño y ofrece gran parte de LISP: funciones de primera clase, cierres, no continuaciones, sino co-rutinas.

Lua es pequeño

Agregar Lua a una aplicación no lo hincha. El tarball para Lua 5.1.4, que contiene código fuente, documentación y ejemplos, toma 212K comprimido y 860K descomprimido. La fuente contiene alrededor de 17000 líneas de C. En Linux, el intérprete Lua construido con todas las bibliotecas Lua estándar tiene 153K y la biblioteca Lua tiene 203K.

Lua es gratis

Lua es un software libre de código abierto, distribuido bajo una licencia muy liberal (la conocida licencia MIT). Se puede usar para cualquier propósito, incluidos los comerciales, sin costo alguno. Solo descárguelo y úselo.