Necesitaba 1+1 y terminó construyendo un lenguaje de programación funcional
Needed 1+1, built a functional programming language
Un estudiante recibe una tarea de estructuras de datos: evaluar 1+1+1 con un árbol binario. En lugar de resolverla y seguir, decide construir un evaluador completo. En pocos días implementa en C cierres, un recolector de basura, un asignador de memoria personalizado, un REPL y una FFI. El resultado es graphLang, un lenguaje funcional que nace de una simple suma.
Fib(40) literalmente consumió más de 12 GIGABYTES antes de agotar la memoria y colapsar.
- CodesInChaos
La décima regla de Greenspun de la programación:
> Cualquier programa en C o Fortran suficientemente complicado contiene una implementación ad hoc, informalmente especificada, llena de errores y lenta de la mitad de Common Lisp.
- tromp
> En general, construí un motor de reducción de grafos
Hice lo mismo para mi implementación eficiente del lenguaje de programación funcional puro BLC/BLC2,
que en más de 400 líneas contiene un motor de reducción de grafos para lógica combinatoria, al cual los programas de cálculo lambda se convierten mediante el algoritmo de abstracción de corchetes de Kiselyov.
- heronbank
Identificable. Pasé una semana optimizando una consulta que se ejecuta dos veces al año para un informe que nadie lee. La madriguera del conejo es real.
- gnarlouse
Esto me recuerda a hace décadas cuando... espera, todavía estaba escribiendo código hace como tres años.
- Joker_vD
> El asunto es que todos nuestros nodos se apuntan entre sí dentro de este bloque de memoria. Cuando lo reallocamos con un tamaño mayor, puede que se mueva a una nueva dirección de memoria. ¡Rompiendo por completo todos nuestros punteros y causando un segfault! ¿Cómo abordamos este problema?
¿Almacenar índices en el array del arena? Probablemente incluso podrías usar índices de 4 bytes y reducir el uso de memoria...
> Fib(40) literalmente tomó más de 12 GIGABYTES antes de alcanzar un OOM y crashear. ¿Por qué? Porque genera aproximadamente 1.3 mil millones de nodos.
Vale, quizás puedas mantener índices de 8 bytes.
> El recolector de basura de marca y barrido que acabamos de completar es un recolector de basura stop-the-world. Y el algoritmo que estamos ejecutando es inherentemente exponencial.
¿Qué tal un recolector de copia entonces? El Fibonacci recursivo genera mucha basura pero si no recuerdo mal su conjunto vivo es en realidad bastante pequeño en cualquier punto dado del tiempo. Si necesitas un benchmark para GC cuando tu función realmente tiene un conjunto vivo enorme, entonces algo como
def garbage(n):
if n == 0:
return None
return (garbage(n-1), garbage(n-1))
debería servir; si no tienes una estructura de datos adecuada puedes simularlo con closures de forma bastante trivial.
> Y podemos hacer algo sobre cómo evaluamos fib en sí
¿Te refieres a "cambiar de recorrer el AST recursivamente" o "escribir un Fibonacci no exponencial"?