Глава 11

Проект: Език за програмиране

Оценителя, който определя смисъла на изразяване в един език за програмиране, е просто друга програма.”

Когато един ученик попитал майстора за естеството на движение на данни и контрол, Ян-Ма отговорил „Мислете за компютъра от съставянето му.””

Изграждане на собствен език за програмиране е изненадващо лесно (стига да не се стремите твърде високо) и много поучително.

Основното, което искам да покажа в тази глава е, че няма магия, която участва в изграждането на вашия собствен език. Аз често съм чувствал, че някои човешки изобретения са толкова умни и сложни, че никога няма да бъда в състояние да ги разбера. Но с малко четене и бърникане, такива неща често се оказват доста банални.

Ние ще изградим един език за програмиране, наречен Egg . Това ще бъде един малък, прост език, но достатъчно мощен за да се изрази всяко изчисление, което може да се сетите. Той също така ще позволи проста абстракция въз основа на функции.

Морфологичен разбор

Най-видимата част на един език за програмиране е неговия синтаксис или нотация. Анализатор е програма, която чете част от текст и произвежда структура от данни, които отразяват структурата на програмата съдържаща се в този текст. Ако текстът не образува валидна програма, анализатора трябва да се оплаче и да посочи грешка.

Нашият език ще има прост и еднообразен синтаксис. Всичко в Egg е израз. Израза може да бъде променлива, номер, string или заявление. Заявленията се използват, както за извикване на функции така и за конструкции, като if и while.

За да се запази анализатора елементарен, strings в Egg не поддържат неща, като обратно наклонена черата. Strings са просто поредица от характери, които не са двойни кавички, обвити в двойни кавички. Номерата са последователност от цифри. Имената на променливите могат да се състоят от всякакъв характер, които не е празно място и няма специално предназанчение в синтаксиса.

Приложенията са написани по начина, по който са в JavaScript, чрез поставяне на скоби след израза и имащи произволен брой аргументи между тези скоби, разделени със запетаи.

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

Еднаквостта на езика Egg означава, че нещата, които са оператори в JavaScript (като >) са нормални променливи в този език и се прилагат точно, както другите функции. И тъй като, синтаксиса няма понятие от блок, ние се нуждаем от do конструкция, за да представлява няколко неща в последователност.

Структурата от данни, която ще използва анализатора за описание на програмата, ще се състои от експресионни обекти, всеки от които има свойството type, което да показва вида на изразяване и други свойства, за да опише съдържанието.

Изрази от типа "value" представляват strings или номера. Тяхното свойство value съдържа string или цифрова стойност, която те представляват. Изрази от типа "word" се използват за идентификатори (имена). Такива обекти имат свойството name, което държи името на идентификатора, като string. И накрая "apply" изразите представляват приложения. Те имат свойство operator, който се отнася до израза върху, който се прилага и свойство args, което се отнася до масив от изрази на аргументи.

Частта >(x, 5) на предишната програма ще бъде представена по следния начин:

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

Такава структура от данни се нарича синтаксис дърво. Ако си представите обектите, като точки и връзките между тях, като линии между тези точки, те ще имат дървовидна форма. Фактът, че изрази съдържат други изрази, които от своя страна могат да съдържат повече изрази е подобен на начина, по който клоните се разделят и отново се разделят.

Сравнете това с анализатора, който писахме за формат на конфигурационен файл в Глава 9 и който имаше проста структура: тя разделя входящите редове и обработва тези редове в даден момент. Имаше само няколко прости форми, които редовете е позволено да имат.

Тука трябва да намерим по различен подход. Изразите не се разделят на редове и те имат рекурсивна структура. Изразите на приложения съдържат други подобни изрази.

За щастие този проблем може да бъде решен елегантно чрез писане на функция анализатор, която е рекурсивна по начин, който отразява рекурсивното естество на езика.

Ние ще дефинираме функция parseExpression, която взема string, като вход и връща обект, съдържащ структура от данни за изразяване в началото на string, заедно с останалата част на string, след като анализира този израз. Когато анализира под-изрази (например, аргумент към приложението) тази функция може да се извика отново, давайки израз на аргумента, както и текста който остава. Този текст на свой ред може да съдържа повече аргументи или може да бъде затваряща скоба, която завършва списъка от аргументи.

Това е първата част на анализатора:

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

Понеже Egg позволява всякакъв размер на празно пространство между неговите елементи, ние трябва изцяло да намалим интервалите в началото на string на програмата. Това, което функцията skipSpace прави.

След като, прескочим всяко празно пространство, parseExpression използва три регулярни израза, за място на три прости елемента, които Egg поддържа: string, числа и думи. Анализатора изгражда различен тип структура от данни в зависимост от това на което отговарят. Ако входа не съвпада с тези три форми, то той е невалиден израз и анализатора хвърля грешка. SyntaxError е стандартен тип обект за грешки, който се изпълнява, когато се направи опит да се изпълни невалидна JavaScript програма.

След това можем да отрежем част от съвпадащия с програмата string и да го подадем с обекта за изразяване към parseApply, който проверява дали израза е заявление. Ако е така анализира списъка с аргументите в скобите.

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

Ако следващият характер в програмата не е отваряща скоба, това не е валидно заявление и parseApply просто връща израза, който и е даден.

В противен случай, той пропуска отварящата скоба и създава дървовиден обект на синтаксиса за това заявление на израз. След това, рекурсивно извиква parseExpression за да анализира всеки аргумент, докато намери затваряща скоба. Рекурсията е косвена, чрез parseApply и parseExpression извикващи се един друг.

Тъй като, израза на заявлението може да се приложи (както multiplier(2)(1)), parseApply трябва, след като анализира заявлението да извика отново себе си, за да провери дали не следва друга двойка скоби.

Това е всичко, което трябва да анализира Egg. Ние го увиваме в удобна parse функция, която удостоверява, че той е достигнал края на вохдящия string след анализа на израза (програмата Egg е един израз) и това ни дава структурата от данни на програмата.

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

Работи! Тя не ни дава много полезна информация, когато се провали и не съхранява реда и колоната, на която започва всеки израз, което може да бъде полезно при отчитане на грешки по-късно, но това е достатъчно добре за нашите цели.

Оценителят

Какво можем да направим със синтаксиса на дървото на програмата? Да го стартираме, разбира се! И това е, което оценителя прави. Можем да му дадем дървото на синтаксиса и среда на обект, който свързва имена със стойности и той ще оцени израза, който дървото представлява и ще върне стойността, която се произвежда.

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

Оценителят има код за всеки от типовете изрази. Стойността на израза просто произвежда своята стойност.(Например, изразът 100, просто оценява номер 100). За променливата, ние трябва да проверим дали действително е определена в заобикалящата среда и ако е така, да и прикачим тази стойност.

Заявленията са по-ангажиращи. Ако те са специална форма, като if, ние не оценяваме нищо и просто подаваме израза на аргумента заедно със заобикалящата среда към функцията, която обработва тази форма. Ако това е нормално извикване, ние оценяваме оператора, потвърждаваме, че е функция и я извикваме с резултата от оценката на аргументите.

Ние ще използваме обикновени функционални стойности на JavaScript, за да представим функционалните стойности на Egg. Ще се върнем към това по-късно, когато специалната форма, наречена fun дефинирана.

Рекурсивната структура на evaluate прилича на подобната структура на анализатора. И двата отразяват структурата на самия език. Също така е възможно да се интегрира анализатор с оценител и да оценяват по време на анализа, но ние ги разделяме и по този начин правим програмата по-четима.

Това наистина е всичко, което е необходимо за да се интерпретира Egg. Толкова е просто. Но без да определим няколко специални форми и да добавим някои полезни стойности към заобикалящата средата, няма да можем да направим нищо с този език, все още.

Специални форми

Обекта на specialForms се използва за определяне на специален синтаксис в Egg. Той свързва думи с функции, които правят оценка на такива специални форми. Сега е празен. Нека добавим някои форми.

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

Конструкцията на if в Egg , очаква точно три аргумента. Тя ще оцени първия и ако резултата не е false, ще направи оценка на втория. В противен случай, третият получава оценка. Тази if форма е сходна с трикомпонентната if форма на оператора ?: в JavaScript. Това е израз, а не твърдение и произвежда стойност, а именно резултата от втория или третия аргумент.

Egg се различава от JavaScript, по това как обработва условието на стойностите към if. Той няма да третира неща, като нула или празен string, като неверни, а с точната стойност false.

Причината, поради която трябва да представим if, като специална форма, а не редовна функция, е че всички аргументи на функции се оценяват преди извикването на функцията, докато if трябва да оцени само втория или третия си аргумент, в зависимост от стойността на първия.

Формата за while е подобна:

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, който изпълнява всички свои аргументи от горе до долу. Неговата стойност е стойността произведена от последния аргумент.

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

За да бъдем в състояние да създаваме променливи и да им даваме нови стойности, трябва също да създадем форма наречена define. Тя очаква една дума, като първи аргумент и израз, произвеждащ стойноста за присвояване към тази дума, като втори аргумент. Тъй като, define, както всичко, което е израз трябва да върне стойност. Ще го направим да връща стойността, която е присвоена ( точно, както в 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;
};

Заобикаляща среда

Заобикалящата среда приета от evaluate е обект със свойства, чиито имена съответстват на имената на променливите и чиито стойности отговарят на стойностите на тези променливи, с които са обвързани. Нека определим обекта на заобикалящата среда да представлява глобалния обхват.

За да можем да използваме if конструкцията да го определи, ние трябва да имаме достъп до булеви стойности. Тъй като, има само две булеви стойности, ние не се нуждаем от специален синтаксис за тях. Просто ще свържем две променливи със стойностите true и false и ще ги използваме, като такива.

var topEnv = Object.create(null);

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

Сега можем да оценим един прост израз с негативна булева стойност.

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

За да предоставим основни аритметични и сравнителни оператори, ще добавим някои функционални стойности към заобикалящата среда. В интерес на запазване на краткия код, ще използваме new Function да синтезира един куп функции за оператори с цикъл, а не да ги определяме индивидуално.

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

Начин за показване на изходни стойности също е много полезен, така че ще увием console.log във функция и ще я наречем print.

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

Това ни дава достатъчно елементарни инструменти, за да се пишат прости програми. Следващата run функция предлага удобен начин да се пишат и изпълняват. Тя създава нова среда, анализира и оценява strings, които ние и даваме, като една единствена програма.

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

Използването на Array.prototype.slice.call е трик за да превърнем един масиво-подобен обект, например arguments, в истински масив, така че да можем да извикаме join върху него. Той взема всички аргументи, подадени на run и ги третира, като редове на програма.

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

Това е програма, която сме виждали няколко пъти преди за изчисляване на сумата на числата от 1 до 10, изпълнена в Egg. То е ясно, че е по-грозна от същата програма в JavaScript, но никак не е зле за език с по-малко от 150 реда код.

Функции

Език за програмиране без функции е беден език за програмиране.

За щастие, не е трудно да добавим fun конструкция, която третира последния си аргумент, като тяло на функцията и третира всички аргументи преди това, като имена на аргументите на функцията.

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

Функциите в Egg имат своя собствена локална среда, точно както в JavaScript. Ние използваме Object.create да направи нов обект, който има достъп до променливите във външната среда (негов прототип), но също така да съдържа и нови променливи без да променя външния обхват.

Функцията създадена от fun формата, създава тази локална среда и добавя променливи на аргументи към нея. След това тя оценява тялото на функцията в тази среда и връща резултата.

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

Компилация

Това което, изградихме досега е интерпретатор. По време на оценката, той действа директно върху представянето на програмата, произведена от анализатора.

Компилация е процес на добавяне на още една стъпка между анализирането и управлението на една програма, която трансформира програмата в нещо, което може да оценява по-ефективно, като извършва толкова работа, колкото е възможно предварително. Например, в добре проектирани езици е очевидна всяка употреба на една променлива, която е посочена без всъщност да работи програмата. Това може да се използва, за да се избегне търсенето на променливата по име всеки път, когато тя е достъпна и директно да се вземе от някое предварително определено място в паметта.

Традиционно компилацията включва превръщането на програмата в машинен код със суров формат, който процесорът на компютъра може да изпълни. Всеки процес, който преобразува програма в различно представяне, може да се мисли за него, като за компилация.

Възможно е да се напише стратегия за алтернативно оценяване за Egg, която първо преобразува програмата в програма на JavaScript, използва new Function за да призове компилатора на JavaScript върху нея и след това изпълнява резултата. Когато е завършена, това ще направи изпълнението на Egg да работи много по-бързо докато все още е доста лесна за осъществяване.

Ако се интересувате от тази тема и искате да и отделите известно време, аз ви насърчавам да се опитате да въведете някакъв компилатор, като упражнение.

На готово

Когато дефинирахме if и while, вероятно сте забелязали, че те са повече или по-малко тривиални обвивки на JavaScript-ските if и while. По същия начин стойностите в Egg са просто обикновени стари стойности на JavaScript.

Ако сравните реализацията на Egg, изградена върху JavaScript, с обема на работа и сложността необходима за изграждане на един език за програмиране директно в суровата функционалност предоставена от една машина, разликата е огромна. Независимо от това, с този пример се надявам да добиете представа за начина, по който програмните езици работят.

И когато става въпрос за получаване на нещо направено на готово е по-ефективно, отколкото да правите всичко сами. Въпреки, че езикът - играчка в тази глава не прави нищо, което да не може да се направи по-добре в JavaScript, има ситуации, в които написването на малки езици помага да се свърши реална работа.

Такъв език не трябва да прилича на типичен език за програмиране. Ако JavaScript не беше оборудван с регулярни изрази, можеше да напишете свой собствен анализатор и оценител за такъв под - език.

Или си представете, че изграждате гигантски робот - динозавър и трябва да програмирате поведението му. JavaScript може да не е най-ефективния начин да направите това. Вместо това, може да предпочетете език, който изглежда така:

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

Това обикновено се нарича домейн - специфичен език, пригоден да изрази тясна област от знанието. Такъв език може да бъде по-изразителен, в сравнение с език с общо предназначение, тъй като е проектиран да изрази точно това, което трябва да се изрази в неговия домейн и нищо друго.

Упражнения

Масиви

Добавете подкрепа за масиви в Egg, чрез добавяне на следните три функции в началото на обхвата: array(...) за да изгради масив съдържащ стойностите на аргумента, length(array) за да получи дължината на масива, а element(array, n) за да извлече n-тия елемент от масива.

// 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

Закриване

Начинът, по който е дефиниран fun позволява на функциите в Egg , да се “затворят над” заобикалящата среда, което позволява на тялото на функцията да използва локалните стойности, които са видими по време на дефиниране на функцията, точно както функциите в JavaScript правят.

Следната програма илюстрира това: функция f връща функция, която добавя своя аргумент към аргумента на f, което означава, че се нуждае от достъп до локалния обхват вътре в f за да бъде в състояние да използва променливата a.

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

Върни се на определянето за fun формата и си обясни, кой механизъм е причината това да работи.

Коментари

Би било хубаво, ако можехме да пишем коментари в Egg. Например, когато поставим знака (#) отпред, бихме могли да третираме останалата част от реда, като коментар и да го игнорираме, подобно на // в JavaScript.

Ние не трябва да правим някакви големи промени в анализатора в подкрепа на това. Можем просто да променим skipSpace да пропуска коментарите, все едно, че са празни пространства, така че всички точки, където се извиква skipSpace също да пропуска коментарите. Направи тази промяна.

// 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: []}

Определяне на обхвата

В момента единственият начин да присвоите стойност към променлива е define. Тази конструкция действа, като начин за определянето на нови променливи и дава на съществуващите такива нови стойности.

Тази неяснота създава проблем. Когато се опитате да зададете на не локална променлива нова стойност, ще се окажете пред определяне на локална променлива със същото име. (На някои езици дизайна им работи така, но аз винаги съм го намирал за глупав начин да се справят с обхвата.)

Добави специална форма set подобна на define, която дава нова стойност на променлива и актуализира променливата във външния обхват, ако тя все още не съществува във вътрешния обхват. Ако променливата не е определена изобщо, хвърли ReferenceError (който е друг стандартен тип грешка).

Техниката за представяне на обхвати, като прости обекти, която е правила нещата удобни досега, ще ви помогне малко в този момент. Може би ще искате да използвате Object.getPrototypeOf функцията, която връща прототипа на даден обект. Също така не забравяйте, че обхватите не произтичат от Object.prototype, така че ако искате да извикате hasOwnProperty върху тях, вие ще трябва да използвате този тромав израз:

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

Това извлича hasOwnProperty метода от Object прототипа и след това го извиква върху обхвата на обект.

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