10. A programing language.md

#A Programming Language This gist is based on Chapter10, [EloquentJavascript] http://eloquentjavascript.net/ Building a programming is not hard as we think, as long as it can calculate the basic expression.
We's going to buid a programming language called Egg. ##Parsing The most basic part of a programming language is syntax, or notation. So, parsing have to read a text and convert them to the data structure. If the text is not valid form, parsing will show the error.
Everything in Egg is an expression. An Expression can be a variable, a string, a number, or an application!
DataStructure is presented in a bracket. It has some kinds of type:

{type: "value", value: [string or number]};
{type: "word", name: "[name]"}; // It likes an object has a name property
{
  type: "apply", 
  operator: {[word]},
  arg: {[some kinds of word or value]}
}

Now we have to have a function, which can convert a text to an object as we want. We call it is parseExpression. The first it will cut some wasted whitespace in the text, and after that, it using Regular Expression to check if the text is the three kinds of data Egg supports: string (has no special character), number and word. If the Text not match any one of three, parseEpression will throw and SyntaxError

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);
}

Okay, now, the next mission is check whole the text. (the program string has many expression, and the parseExpression above checks the minimum expression) we have another function to do next

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));
}

Oke, now you can run the function parseExpression("+(a,10)") to check if it works. But we want to using a function called parsed to call parseExpression function, and catch error expression

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

##Evaluator After parsing, we have a valid expression we want. And then, the next mission is running that code! And the evaluator will do that. With each type of expression, Evaluator will do different things.

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);

we know, all expression has type property (value, word, apply)

• value: evaluator just return the value of this type.
• word: evaluator will check if this name exist in the environment. What is the environment, we'll know later
• apply: this is quiet more complex. if they are special form, then do not evaluate anything, just send them to the function in special form, if they are normal call, we verify that is a function, and call that function.

##Special Forms We should define some special form like if, while, print

• if form:

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);
};

• while form:

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);

  // Since undefined does not exist in Egg, we return false,
  // for lack of a meaningful result.
  return false;
};

• do form: Egg does not using bracket to contain a block of code, so we use a special form called do to do this

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

• define form: when creating a new variable with a value, or update the variable with an expression, we use define special form

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;
};

##Environment environment define some operator, value, and console.log

var topEnv = Object.create(null);

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

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

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

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

##Run Oke, so the last thing we need to make Egg become an working language is how to run

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

And we have some example code to run base on this language:

• Hello World

run("do(define(x,\"Hello World\"),",
	"print(x))");

• Calculate sum from 1 to n

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

##Exersice ###Add special array for Egg

topEnv["array"] = function(){
  return Array.prototype.slice.call(arguments, 0);   
};

topEnv["length"] = function(array){
  return array.length;
};

topEnv["element"] = function(array, i){
  return array[i]; 
};

##Change skipspace to comment we can change regular expression in the skipSpace

function skipSpace = function(string){
  var execString = string.match(/^(\s|#.*)*/);
  return string.slice(first[0].length);
}

##Add Set special form to set a new value for an existed variable define is always create a new local variale, so we want to create new special form to set a new value for an existed variable, if that variable does not exist then throw an Exception

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

  for (var scope = env; scope; scope = Object.getPrototypeOf(scope)) {
    if (Object.prototype.hasOwnProperty.call(scope, varName)) {
      scope[varName] = value;
      return value;
    }
  }
  throw new ReferenceError("Setting undefined variable " + varName);
};