Capítulo 11

Proyecto: Un lenguaje de programación

El evaluador, que determina el significado de las expresiones en un lenguaje de programación, es simplemente otro programa.

Cuando un estudiante le preguntó al maestro acerca de la naturaleza del ciclo de datos y control, Yuan-Ma respondió "Piensa en un compilador, compilándose."

Construir su propio lenguaje de programación es sorprendentemente fácil (siempre y cuando no apunte demasiado alto) y muy esclarecedor.

Lo principal que quiero mostrar en este capítulo es que no hay magia involucrada en la construcción de su propio idioma. A menudo he sentido que algunas invenciones humanas eran tan inmensamente inteligentes y complicadas que nunca sería capaz de entenderlas. Pero con un poco de lectura y retoques, tales cosas a menudo resultan ser bastante mundano.

Construiremos un lenguaje de programación llamado "Egg". Será un lenguaje pequeño y sencillo, pero que sea lo suficientemente poderoso para expresar cualquier cálculo que se pueda imaginar. También permitirá la abstracción simple basada en funciones.

Analizando

La parte más inmediatamente visible de un lenguaje de programación es su sintaxis, o notación. Un analizador es un programa que lee una parte del texto y produce una estructura de datos que refleja la estructura del programa contenido en ese texto. Si el texto no forma un programa válido, el analizador debe quejarse y señalar el error.

Nuestro lenguaje tendrá una sintaxis simple y uniforme. Todo en "Egg" es una expresión. Una expresión puede ser una variable, un número, una cadena o una aplicación. Las aplicaciones se utilizan para llamar a funciones, pero también para construcciones como if o while.

Para mantener el analizador simple, las cadenas en "Egg" no soportan nada como escapes de barra invertida. Una cadena es simplemente una secuencia de caracteres que no son comillas dobles, envueltos en comillas dobles. Un número es una secuencia de dígitos. Los nombres de las variables pueden consistir en cualquier carácter que no sea un espacio en blanco y no tenga un significado especial en la sintaxis.

Las aplicaciones se escriben de la forma en que están en JavaScript, poniendo paréntesis después de una expresión pudiendo tener cualquier número de argumentos entre esos paréntesis, separados por comas.

do(define(x, 10),
   if(>(x, 5),
      print("large"),
      print("small")))

La uniformidad del lenguaje "Egg" significa que las cosas que son operadores en JavaScript (como >) son variables normales en este lenguaje, aplicadas como otras funciones. Y puesto que la sintaxis no tiene concepto de un bloque, necesitamos una construcción do para representar hacer varias cosas en secuencia.

La estructura de datos que el analizador utilizará para describir un programa consistirá en objetos de expresión, cada uno de los cuales tiene una propiedad type que indica el tipo de expresión que es y otras propiedades para describir su contenido.

Expressions of type "value" represent literal strings or numbers. Their value property contains the string or number value that they represent. Expressions of type "word" are used for identifiers (names). Such objects have a name property that holds the identifier’s name as a string. Finally, "apply" expressions represent applications. They have an operator property that refers to the expression that is being applied, and they have an args property that refers to an array of argument expressions.

Las expresiones de tipo "value" representan cadenas literales o números. Su propiedad value contiene el valor de cadena o número que representan. Las expresiones del tipo "word" se utilizan para identificadores (nombres). Tales objetos tienen una propiedad de name que contiene una cadena con su nombre. Finalmente, las expresiones "apply" representan aplicaciones. Tienen una propiedad operator que hace referencia a la expresión que se está aplicando y tienen una propiedad args que hace referencia a una matriz con sus argumentos.

La parte >(x, 5) del programa anterior se representa así:

{
  type: "apply",
  operator: {type: "word", name: ">"},
  args: [
    {type: "word", name: "x"},
    {type: "value", value: 5}
  ]
}

Esta estructura de datos se llama un estructura de árbol. Si usted imagina los objetos como puntos y los enlaces entre ellos como líneas entre esos puntos, tiene una forma de árbol. El hecho de que las expresiones contengan otras expresiones, que a su vez podrían contener más expresiones, es similar al modo en que las ramas se dividen y se dividen de nuevo.

Compare esto con el analizador que escribimos para el formato de archivo de configuración en el Capítulo 9, que tenía una estructura simple: dividió la entrada en líneas y manejó esas líneas una a la vez. Solamente permitia tener alguna forma simples en una linea.

Aquí debemos encontrar un enfoque diferente. Las expresiones no se separan en líneas y tienen una estructura recursiva. Las expresiones de la aplicación contienen otras expresiones.

Afortunadamente, este problema se puede resolver elegantemente escribiendo una función recursiva en el analizador una manera que refleja la naturaleza recursiva de la lengua.

Definimos la función parseExpression, que toma una cadena como entrada y devuelve un objeto que contiene la estructura de datos para la expresión al principio de la cadena, junto con la parte de la cadena que queda después de analizar esta expresión. Al analizar las subexpresiones (el argumento a una aplicación, por ejemplo), esta función puede ser llamada de nuevo, dando la expresión del argumento, así como el texto que permanece. Este texto puede a su vez contener más argumentos o puede ser el paréntesis de cierre que termina la lista de argumentos.

Esta es la primera parte del analizador:

function parseExpression(program) {
  program = skipSpace(program);
  var match, expr;
  if (match = /^"([^"]*)"/.exec(program))
    expr = {type: "value", value: match[1]};
  else if (match = /^\d+\b/.exec(program))
    expr = {type: "value", value: Number(match[0])};
  else if (match = /^[^\s(),"]+/.exec(program))
    expr = {type: "word", name: match[0]};
  else
    throw new SyntaxError("Unexpected syntax: " + program);

  return parseApply(expr, program.slice(match[0].length));
}

function skipSpace(string) {
  var first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

Debido a que "Egg" permite cualquier cantidad de espacio en blanco entre sus elementos, tenemos que cortar repetidamente el espacio en blanco desde el inicio de la cadena del programa. Para esto nos ayuda la función skipSpace.

Después de salterse cualquier espacio en blanco, parseExpression utiliza tres expresiones regulares para detectar los tres elementos simples (atomic) que "Egg" soporta: cadenas, números y palabras. El analizador construye un tipo diferente de estructura de datos dependiendo de cuál coincide. Si la entrada no coincide con una de estas tres formas, no es una expresión válida y el analizador genera un error. SyntaxError es un tipo de objeto de error estándar, que se genera cuando se intenta ejecutar un programa no válido en JavaScript.

Podemos entonces cortar la parte que coincide con una cadena en el programa y pasar que, junto con el objeto de la expresión, a parseApply, que comprueba si la expresión es una aplicación. Si es así, analiza una lista de argumentos entre paréntesis.

function parseApply(expr, program) {
  program = skipSpace(program);
  if (program[0] != "(")
    return {expr: expr, rest: program};

  program = skipSpace(program.slice(1));
  expr = {type: "apply", operator: expr, args: []};
  while (program[0] != ")") {
    var arg = parseExpression(program);
    expr.args.push(arg.expr);
    program = skipSpace(arg.rest);
    if (program[0] == ",")
      program = skipSpace(program.slice(1));
    else if (program[0] != ")")
      throw new SyntaxError("Expected ',' or ')'");
  }
  return parseApply(expr, program.slice(1));
}

Si el siguiente carácter del programa no es un paréntesis de apertura, esto no es una aplicación y parseApply simplemente devuelve la expresión que se le dio.

De lo contrario, omite el paréntesis de apertura y crea el objeto de estructura de árbol para esta expresión de aplicación. A continuación, recursivamente llama a ParseExpression para analizar cada argumento hasta que se encuentra un paréntesis de cierre. La recursión es indirecta, a través de parseApply y parseExpression llamándose entre sí.

Because an application expression can itself be applied (such as in multiplier(2)(1)), parseApply must, after it has parsed an application, call itself again to check whether another pair of parentheses follows.

Porque una expresión de aplicación puede aplicarse por sí misma (como en multiplier(2)(1)), parseApply debe, después de haber analizado una aplicación, volver a llamar para comprobar si hay otro par de paréntesis.

Esto es todo lo que necesita el analizador "Egg". Lo envolvemos en una conveniente función de análisis que verifica que ha llegado al final de la cadena de entrada después de analizar la expresión (un programa "Egg" es una sola expresión), y que nos da la estructura de datos del programa.

function parse(program) {
  var result = parseExpression(program);
  if (skipSpace(result.rest).length > 0)
    throw new SyntaxError("Unexpected text after program");
  return result.expr;
}

console.log(parse("+(a, 10)"));
// → {type: "apply",
//    operator: {type: "word", name: "+"},
//    args: [{type: "word", name: "a"},
//           {type: "value", value: 10}]}

¡Funciona! No nos da información muy útil cuando falla y no almacena la línea y la columna en la que empieza cada expresión, lo que podría ser útil cuando se reportan errores más tarde, pero es lo suficientemente bueno para nuestros propósito.

El evaluador

¿Qué podemos hacer con la estructura de árbol del programa? Correrla, por supuesto! Y eso es lo que hace el evaluador. Se le asigna una estructura de árbol y un objeto de entorno que asocia nombres con valores y evaluará la expresión que representa el árbol y devolverá el valor que produce.

function evaluate(expr, env) {
  switch(expr.type) {
    case "value":
      return expr.value;

    case "word":
      if (expr.name in env)
        return env[expr.name];
      else
        throw new ReferenceError("Undefined variable: " +
                                 expr.name);
    case "apply":
      if (expr.operator.type == "word" &&
          expr.operator.name in specialForms)
        return specialForms[expr.operator.name](expr.args,
                                                env);
      var op = evaluate(expr.operator, env);
      if (typeof op != "function")
        throw new TypeError("Applying a non-function.");
      return op.apply(null, expr.args.map(function(arg) {
        return evaluate(arg, env);
      }));
  }
}

var specialForms = Object.create(null);

El evaluador tiene código para cada uno de los tipos de expresiones. Una expresión de valor literal simplemente produce su valor. (Por ejemplo, la expresión 100 equivale al número 100.) Para una variable, debemos comprobar si está realmente definida en el entorno y, si es así, buscar el valor de la variable.

Las aplicaciones están más comprometidas. Si son una forma especial, como if, no evaluamos nada y simplemente pasamos las expresiones de argumento, junto con el entorno, a la función que maneja esta estructura. Si es una llamada normal, evaluamos al operador, verificamos que es una función y lo llamamos con el resultado de evaluar los argumentos.

Utilizaremos funciones simple de JavaScript para representar los valores de funciones de "Egg". Volveremos a esto más adelante, cuando definamos la forma especial de llamar funciones.

La estructura recursiva de evaluate se asemeja a la estructura similar de parse. Ambos reflejan la estructura del lenguaje mismo. También sería posible integrar el parse con el evaluate y evaluar durante el análisis sintáctico, pero dividirlo de esta manera hace que el programa sea más legible.

Esto es realmente todo lo que se necesita interpretar "Egg". Así de simple. Sin embargo, sin definir algunas formas especiales y agregar algunas utilidades al entorno, todavía no se puede hacer nada con este lenguaje.

Special forms

El objeto specialForms se utiliza para definir sintaxis especial en "Egg". Asocia palabras con funciones que evalúan tales formas especiales. Actualmente está vacío. Añadamos algunas formas.

specialForms["if"] = function(args, env) {
  if (args.length != 3)
    throw new SyntaxError("Bad number of args to if");

  if (evaluate(args[0], env) !== false)
    return evaluate(args[1], env);
  else
    return evaluate(args[2], env);
};

El Constructor if de "Egg" espera exactamente tres argumentos. Se evaluará el primero, y si el resultado no es el valor false, se evaluará el segundo. Si no, el tercero se evaluara. Esta forma es más similar a operador ternario ?: que al de JavaScript if. Es una expresión, no una declaración, y produce un valor, es decir, el resultado del segundo o tercer argumento.

"Egg" difiere de JavaScript en cómo maneja el valor de la condición if. No tratará las cosas como cero o la cadena vacía como false, sólo el valor preciso false.

La razón por la que tenemos que representar if como una estructura especial, en lugar de una función regular, es que todos los argumentos a las funciones se evalúan antes de que se llame a la función, mientras que if debería evaluar sólo su segundo o su tercer argumento, dependiendo del valor del primero.

La estructura de while es similar.

specialForms["while"] = function(args, env) {
  if (args.length != 2)
    throw new SyntaxError("Bad number of args to while");

  while (evaluate(args[0], env) !== false)
    evaluate(args[1], env);

  // Como undefined no existe en Egg, devolvemos false,
  // para la falta de resultados válidos
  return false;
};

Otro bloque de construcción básico es do, que ejecuta todos sus argumentos de arriba a abajo. Su valor es el valor producido por el último argumento.

specialForms["do"] = function(args, env) {
  var value = false;
  args.forEach(function(arg) {
    value = evaluate(arg, env);
  });
  return value;
};

Para poder crear variables y darles nuevos valores, también creamos una specialForms llamada define. Espera una palabra como su primer argumento y una expresión que produce el valor para asignar a esa palabra como su segundo argumento. Dado que define, como toda una expresión, debe devolver un valor. Vamos a hacer que devuelva el valor que se asignó (Como el operador = de JavaScript)

specialForms["define"] = function(args, env) {
  if (args.length != 2 || args[0].type != "word")
    throw new SyntaxError("Bad use of define");
  var value = evaluate(args[1], env);
  env[args[0].name] = value;
  return value;
};

El entorno

El entorno aceptado por el evaluador es un objeto con propiedades cuyos nombres corresponden a nombres de variables y cuyos valores corresponden a los valores a los que están vinculadas. Vamos a definir un objeto de entorno para representar el ámbito global.

Para poder usar la construcción if que acabamos de definir, debemos tener acceso a valores booleanos. Como sólo tiene dos valores, no necesitamos sintaxis especial para ellos. Simplemente enlazamos dos variables a los valores true y false y los usamos.

var topEnv = Object.create(null);

topEnv["true"] = true;
topEnv["false"] = false;

Ahora podemos evaluar un expresión y devolver un valor boleano.

var prog = parse("if(true, false, true)");
console.log(evaluate(prog, topEnv));
// → false

Para facilitar aritmética y operadores de comparación, también agregaremos algunos valores de función al entorno. En interés de mantener el código corto, vamos a utilizar new Function para sintetizar un montón de funciones de operador en un bucle, en lugar de definir todos ellos individualmente.

["+", "-", "*", "/", "==", "<", ">"].forEach(function(op) {
  topEnv[op] = new Function("a, b", "return a " + op + " b;");
});

También es muy útiluna forma de mostrar valores de salida, así que vamos a envolver console.log en una función y lo llamamos print.

topEnv["print"] = function(value) {
  console.log(value);
  return value;
};

Eso nos da suficientes herramientas para escribir programas sencillos. La siguiente función run proporciona una forma conveniente de escribirlos y ejecutarlos. Crea un nuevo ámbito y analiza y evalúa las cadenas que le damos como un solo programa.

function run() {
  var env = Object.create(topEnv);
  var program = Array.prototype.slice
    .call(arguments, 0).join("\n");
  return evaluate(parse(program), env);
}

El uso de Array.prototype.slice.call es un truco para convertir un objeto en array-like(similar o que se asemeja a un array), con tantos elementos como arguments, en una Array así que podemos llamar a join. Toma todos los arguments dados para ejecutarlos y los trata como las líneas de un programa.

run("do(define(total, 0),",
    "   define(count, 1),",
    "   while(<(count, 11),",
    "         do(define(total, +(total, count)),",
    "            define(count, +(count, 1)))),",
    "   print(total))");
// → 55

Este es el programa que hemos visto varias veces antes, que calcula la suma de los números 1 a 10, expresada en "Egg". Es claramente más feo que el programa JavaScript equivalente, pero no está mal para un lenguaje implementado en menos de 150 líneas de código.

Funciones

Un lenguaje de programación sin funciones es un lenguaje verdaderamente pobre

Afortunadamente, no es difícil añadir una constructor fun, que trata su último argumento como el cuerpo de la función y todos los argumentos anteriores como los nombres de los argumentos de la función.

specialForms["fun"] = function(args, env) {
  if (!args.length)
    throw new SyntaxError("Functions need a body");
  function name(expr) {
    if (expr.type != "word")
      throw new SyntaxError("Arg names must be words");
    return expr.name;
  }
  var argNames = args.slice(0, args.length - 1).map(name);
  var body = args[args.length - 1];

  return function() {
    if (arguments.length != argNames.length)
      throw new TypeError("Wrong number of arguments");
    var localEnv = Object.create(env);
    for (var i = 0; i < arguments.length; i++)
      localEnv[argNames[i]] = arguments[i];
    return evaluate(body, localEnv);
  };
};

Las funciones en "Egg" tienen su propio entorno local, al igual que en JavaScript. Utilizamos Object.create para crear un nuevo objeto que tenga acceso a las variables del entorno externo (su prototipo) pero que también pueda contener nuevas variables sin modificar al ámbito global.

La función creada por el objecto fun crea este entorno local y le agrega las variables por argumentos. A continuación, evalúa el cuerpo de la función en este entorno y devuelve el resultado.

run("do(define(plusOne, fun(a, +(a, 1))),",
    "   print(plusOne(10)))");
// → 11

run("do(define(pow, fun(base, exp,",
    "     if(==(exp, 0),",
    "        1,",
    "        *(base, pow(base, -(exp, 1)))))),",
    "   print(pow(2, 10)))");
// → 1024

Compilación

Lo que hemos construido es un intérprete. Durante la evaluación, actúa directamente sobre la representación del programa producido por el analizador.

Compilación es el proceso de añadir otro paso entre el análisis y el funcionamiento de un programa, que transforma el programa en algo que puede ser evaluado de manera más eficiente haciendo todo el trabajo posible de antemano. Por ejemplo, en lenguajes bien diseñados es obvio, para cada uso de una variable, a qué variable se refiere, sin ejecutar realmente el programa. Esto puede usarse para evitar buscar la variable por nombre cada vez que se accede y para buscarla directamente desde una ubicación de memoria predeterminada.

Traditionally, compilationTradicionalmente, la compilación implica convertir el programa en código de máquina, el formato en bruto que el procesador de una computadora puede ejecutar. Pero cualquier proceso que convierte un programa en una representación diferente puede considerarse como compilación.

Sería posible escribir una estrategia de evaluación alternativa para "Egg", una que primero convierta el programa a un programa JavaScript, utilice una nueva Función para invocar al compilador de JavaScript y luego ejecute el resultado. Cuando se haga bien, esto hará que "Egg" corra muy rápido sin dejar de ser muy sencillo de implementar.

Si está interesado en este tema y está dispuesto a dedicar algo de tiempo a ello, le animo a que intente implementar un compilador como un ejercicio.

Trampeando

Cuando definimos if y while, probablemente notó que eran envolturas más o menos triviales alrededor de los propios if y while de JavaScript. Del mismo modo, los valores de "Egg" son sólo antiguos valores de JavaScript.

Si comparas la implementación de Egg, construida por encima de JavaScript, con la cantidad de trabajo y complejidad requerida para construir un lenguaje de programación directamente en la funcionalidad bruta proporcionada por una máquina, la diferencia es enorme. Independientemente, este ejemplo esperamos le dio una impresión de la forma en que funcionan los lenguajes de programación.

Y cuando se trata de hacer algo, hacer trampa es más eficaz que hacer todo tú mismo. Aunque el lenguaje de juguete de este capítulo no hace nada que no se pueda hacer mejor en JavaScript, hay situaciones en las que escribir lenguajes pequeños ayuda a realizar un trabajo real.

Tal lenguaje no tiene que parecerse a un lenguaje de programación típico. Si JavaScript no viene equipado con expresiones regulares, puede escribir su propio analizador y evaluador para tal sublenguaje.

O imagínese que está construyendo un gigantesco dinosaurio robótico y necesita programar su comportamiento. JavaScript podría no ser la forma más efectiva de hacerlo. En su lugar, puede optar por un idioma que tenga el siguiente aspecto:

behavior walk
  perform when
    destination ahead
  actions
    move left-foot
    move right-foot

behavior attack
  perform when
    Godzilla in-view
  actions
    fire laser-eyes
    launch arm-rockets

Esto es lo que se suele llamar un lenguaje específico del dominio, un lenguaje adaptado para expresar un estrecho dominio del conocimiento. Tal lenguaje puede ser más expresivo que un lenguaje de propósito general porque está diseñado para expresar exactamente las cosas que necesitan expresarse en su dominio y nada más.

Ejercicios

Arrays

Agregue soporte para arrays a "Egg" agregando las siguientes tres funciones al ámbito superior: array (...) para construir una matriz que contenga el valor de sus argumentos, length(array) para obtener la longitud de una matriz y element(array, n) para buscar la posición del elemento en el array.

// Modify these definitions...

topEnv["array"] = "...";

topEnv["length"] = "...";

topEnv["element"] = "...";

run("do(define(sum, fun(array,",
    "     do(define(i, 0),",
    "        define(sum, 0),",
    "        while(<(i, length(array)),",
    "          do(define(sum, +(sum, element(array, i))),",
    "             define(i, +(i, 1)))),",
    "        sum))),",
    "   print(sum(array(1, 2, 3))))");
// → 6

Closure

La forma en que hemos definido fun permite a las funciones de "Egg" "cerrar" el entorno, permitiendo que el cuerpo de la función use valores locales que eran visibles en el momento en que se definió la función, al igual que las funciones de JavaScript.

El siguiente programa lo ilustra: la función f devuelve una función que añade su argumento como argumentos de f, lo que significa que necesita acceso al ámbito local dentro de f para poder utilizar la variable a.

run("do(define(f, fun(a, fun(b, +(a, b)))),",
    "   print(f(4)(5)))");
// → 9

Vuelva a la definición de fun y explique qué mecanismo hace que funcione.

Comentarios

Sería bueno si pudiéramos escribir comentarios en "Egg". Si nosotros encontramos el hash (#), podríamos tratar el resto de la línea como un comentario e ignorarlo, similar a // en JavaScript.

No tenemos que hacer grandes cambios en el analizador para apoyar esto. Podemos simplemente cambiar skipSpace para omitir los comentarios como si fueran espacios en blanco para que todos los puntos donde skipSpace se llama ahora también saltarán los comentarios. Haga este cambio.

// This is the old skipSpace. Modify it...
function skipSpace(string) {
  var first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

console.log(parse("# hello\nx"));
// → {type: "word", name: "x"}

console.log(parse("a # one\n   # two\n()"));
// → {type: "apply",
//    operator: {type: "word", name: "a"},
//    args: []}

Fijando el alcance

Actualmente, la única forma de asignar una variable a un valor es define. Esta construcción actúa para definir nuevas variables como para dar a las existentes un nuevo valor.

This ambiguityEsta ambigüedad causa un problema. Cuando intenta dar una variable no local un nuevo valor, terminará definiendo una en local con el mismo nombre en su lugar. (Algunos lenguajes funcionan de esta manera por diseño, pero siempre he encontrado una manera simple de manejar el alcance.)

Agregue una functión especial set, similar a define, la cual da a una variable un nuevo valor, actualizando la variable en un ámbito externo si aún no existe en el ámbito interno. Si la variable no está definida en absoluto, lance un ReferenceError (El cual es otro tipo de error estándar).

La técnica de representar los ámbitos como objetos simples, ha hecho las cosas convenientes hasta ahora, se pondrá en contra un poco en este punto. Es posible que desee utilizar la función Object.getPrototypeOf, que devuelve el prototipo de un objeto. También recuerde que los ámbitos no derivan de Object.prototype, así que si quieres llamar a hasOwnProperty en ellos, debes usar esta expresión:

Object.prototype.hasOwnProperty.call(scope, name);

Esto recupera el método hasOwnProperty del prototipo de Object y lo llama a un objeto scope.

specialForms["set"] = function(args, env) {
  // Your code here.
};

run("do(define(x, 4),",
    "   define(setx, fun(val, set(x, val))),",
    "   setx(50),",
    "   print(x))");
// → 50
run("set(quux, true)");
// → Some kind of ReferenceError