Hasta ahora tienes algunas buenas respuestas; Permítame darle un ejemplo poco práctico pero altamente educativo de cómo puede diseñar un lenguaje sin la noción de pilas o "flujo de control" en absoluto. Aquí hay un programa que determina factoriales:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)
Colocamos este programa en una cadena y evaluamos el programa mediante una sustitución textual. Entonces, cuando estamos evaluando f(3)
, hacemos una búsqueda y reemplazamos con 3 para i, como esto:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)
Genial. Ahora realizamos otra sustitución textual: vemos que la condición del "si" es falsa y hacemos otra cadena de reemplazo, produciendo el programa:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)
Ahora hacemos otra cadena de reemplazo en todas las sub-expresiones que involucran constantes:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)
Y ves cómo va esto; No voy a trabajar más el punto. Podríamos seguir haciendo una serie de sustituciones de cadenas hasta que bajemos a let x = 6
y lo hagamos.
Usamos la pila tradicionalmente para variables locales e información de continuación; recuerda, una pila no te dice de dónde vienes, te dice a dónde vas a ir con ese valor de retorno en la mano.
En el modelo de programación de sustitución de cadenas, no hay "variables locales" en la pila; los parámetros formales se sustituyen por sus valores cuando la función se aplica a su argumento, en lugar de colocarse en una tabla de búsqueda en la pila. Y no hay "ir a algún lado" porque la evaluación del programa es simplemente aplicar reglas simples para la sustitución de cadenas para producir un programa diferente pero equivalente.
Ahora, por supuesto, hacer sustituciones de cadenas probablemente no sea el camino a seguir. Pero los lenguajes de programación que admiten el "razonamiento ecuacional" (como Haskell) utilizan lógicamente utilizando esta técnica.