Двенадцатая глава. Проект: язык программирования

Оригинал: Project: A Programming Language

Переводчик: Фейлун

Лицензия: CC BY-NC-SA 4.0

С гордостью использую Google Translate.

Часть информации взята из книги «JavaScript: сильные стороны».

Определение значения выражения в языке программирования — это просто ещё одна программа.

Хэл Абельсон и Джеральд Сассман, «Структура и интерпретация компьютерных программ».

Построение собственного языка программирования не только просто (если ваши требования не слишком высоки), но и очень познавательно.

Я часто сталкиваюсь с идеями, которые кажутся мне невероятно умными и сложными, настолько, что я не могу полностью их понять. Однако после некоторого времени чтения и экспериментов я обнаружил, что они на самом деле не так сложны.

Мы создадим язык программирования под названием Egg. Это простой и компактный язык, но достаточно мощный, чтобы описать любые вычисления, которые вы можете себе представить. Он допускает простые абстракции на основе функций.

Анализ

Наиболее очевидная часть языка программирования — синтаксис или символы. Анализатор — это программа, которая считывает текст программы и создаёт соответствующую структуру данных. Если текст не является допустимой программой, анализатор должен указать на ошибку.

Наш язык программирования Egg прост и последователен. В Egg всё является выражением. Выражения могут быть привязками имён, числами или приложениями (application). Не только вызовы функций являются приложениями, но также конструкции языка, такие как if и while.

Чтобы обеспечить простоту анализатора, строки в Egg не поддерживают такие элементы, как escape-последовательности. Строка представляет собой простую последовательность символов (без двойных кавычек), заключённую в двойные кавычки. Число — это последовательность цифр. Привязка имени состоит из любых непробельных символов и не имеет специального значения в синтаксисе.

Способ записи приложений такой же, как в JavaScript: выражение, за которым следует пара скобок, содержащих любое количество параметров, разделённых запятыми.

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

Согласованность Egg проявляется в том, что все операторы в JavaScript (например, >) являются привязками в Egg, но могут вызываться как функции. Поскольку в синтаксисе нет понятия блоков операторов, мы должны использовать структуру do для представления последовательности выражений.

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

Выражения типа "value" представляют строки и числа. Их атрибут value содержит соответствующее строковое или числовое значение. Выражения типа "word" используются для идентификаторов (имён). Эти объекты хранят имя идентификатора в виде строки в атрибуте name. Наконец, выражения типа "apply" обозначают приложения. Объекты этого типа имеют атрибут operator, который указывает на выражение операции, и атрибут args, содержащий массив выражений параметров.

Приведённый выше код можно выразить следующим образом:

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

Мы называем эту структуру данных деревом выражений. Если представить объекты как точки, а связи между объектами как линии, эта структура данных станет древовидной. Деревья выражений также содержат другие выражения, которые, в свою очередь, содержат больше выражений, подобно ветвям дерева, разветвляющимся снова и снова.

Мы сравним этот анализатор с анализатором формата конфигурационного файла, который мы написали в девятой главе. Анализатор в девятой главе имеет простую структуру: он разбивает входной файл на строки и обрабатывает каждую строку по очереди. Кроме того, каждая строка имеет несколько простых синтаксических форм.

Нам нужно найти другой способ решения этой проблемы. В Egg нет разделения выражений на строки, и между выражениями существует рекурсивная структура. Приложения содержат другие выражения.

К счастью, мы можем использовать рекурсивный подход для написания функции анализатора и элегантно решить эту проблему, отражая рекурсивную природу самого языка.

Мы определяем функцию parseExpression, которая принимает строку и возвращает объект, содержащий выражение в начале строки и оставшуюся часть строки после анализа выражения. Когда мы анализируем подвыражение (например, параметры приложения), мы можем снова вызвать эту функцию и вернуть выражение параметра и оставшуюся строку. Оставшаяся строка может содержать больше параметров или может быть правой скобкой, обозначающей конец списка параметров.

Вот часть кода анализатора.

function parseExpression(program) {
  program = skipSpace(program);
  let 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) {
  let first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

Поскольку Egg и JavaScript допускают произвольное количество пробелов между элементами, нам необходимо многократно удалять пробелы в начале программы. Функция skipSpace помогает в этом.

После удаления всех пробелов в начале parseExpression использует три регулярных выражения для обнаружения трёх основных элементов Egg: строк, чисел и слов. Анализатор строит различные типы данных в зависимости от результата сопоставления. Если ни одна из этих форм не совпадает с вводом, ввод является недопустимым выражением, и анализатор выдаст исключение. Мы используем SyntaxError вместо Error в качестве конструктора исключений, потому что это другой стандартный тип ошибки, более конкретный — он также возникает при попытке запустить недопустимую программу JavaScript.

Затем мы удаляем совпадающую часть из строки программы и передаём оставшуюся строку и объект выражения функции 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] != ")") {
    let 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 для упаковки parseExpression, после разбора выражения проверяем, достигнут ли конец ввода (программа Egg — это выражение), при достижении конца ввода возвращается соответствующая структура данных программы.

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

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

Программа работает нормально! Когда разбор выражения завершается неудачно, функция разбора не выводит никакой полезной информации и не сохраняет ошибочную строку и столбец, хотя эта информация полезна для последующего сообщения об ошибке. Но учитывая нашу цель, этот язык уже достаточно хорош.

Оценщик (evaluator)

После того как у нас есть синтаксическое дерево программы, что нам делать дальше? Конечно, выполнить программу! И это работа оценщика. Мы передаём синтаксическое дерево и объект области видимости оценщику, который будет оценивать выражения в синтаксическом дереве и возвращать результат всего процесса.

const specialForms = Object.create(null);

function evaluate(expr, scope) {
  if (expr.type == "value") {
    return expr.value;
  } else if (expr.type == "word") {
    if (expr.name in scope) {
      return scope[expr.name];
    } else {
      throw new ReferenceError(
        `Undefined binding: ${expr.name}`);
    }
  } else if (expr.type == "apply") {
    let {operator, args} = expr;
    if (operator.type == "word" &&
        operator.name in specialForms) {
      return specialForms[operator.name](expr.args, scope);
    } else {
      let op = evaluate(operator, scope);
      if (typeof op == "function") {
        return op(...args.map(arg => evaluate(arg, scope)));
      } else {
        throw new TypeError("Applying a non-function.");
      }
    }
  }
}

Оценщик предоставляет соответствующую логику обработки для каждого типа выражений. Буквальное выражение производит своё значение (например, значение выражения 100 равно числу 100). Что касается привязки, мы должны проверить, действительно ли она определена в программе, и если она уже определена, получить значение привязки.

Применение более сложное. Если применение имеет специальную форму (например, if), мы не оцениваем никаких выражений, а передаём параметры выражения и среду функции, которая обрабатывает эту форму. Если это обычный вызов, мы оцениваем оператор, проверяем, является ли он функцией, и вызываем функцию с параметрами, полученными в результате оценки.

Мы используем общие функции JavaScript для представления функций Egg. Когда мы определяем специальный формат fun, мы возвращаемся к этому вопросу.

Структура рекурсии оценки аналогична структуре парсера. Оба отражают структуру языка. Мы также можем объединить парсер и оценщик вместе, анализируя и оценивая выражения одновременно, но разделение их на два этапа делает программу более понятной.

Это весь необходимый код для объяснения Egg. Этот код очень прост, но без определения некоторых специальных форматов или добавления полезных значений в среду вы не сможете использовать этот язык для выполнения многих задач.

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

Объект specialForms используется для определения специальной грамматики в Egg. Он связывает слова и функции, которые оценивают эти формы. В настоящее время этот объект пуст, теперь давайте добавим if.

specialForms.if = (args, scope) => {
  if (args.length != 3) {
    throw new SyntaxError("Wrong number of args to if");
  } else if (evaluate(args[0], scope) !== false) {
    return evaluate(args[1], scope);
  } else {
    return evaluate(args[2], scope);
  }
};

Оператор if в Egg требует трёх параметров. Egg оценивает первый параметр, и если результат не равен false, то оценивается второй параметр, иначе оценивается третий параметр. По сравнению с оператором if в JavaScript, форма if в Egg больше похожа на оператор?: в JavaScript. Это выражение, а не утверждение, которое возвращает значение второго или третьего параметра.

Egg и JavaScript также имеют некоторые различия в обработке логических значений. Egg не рассматривает 0 или пустую строку как ложные, только когда значение действительно равно false, результат теста считается ложным.

Нам нужно выразить if как специальную форму, а не обычную функцию, потому что все параметры функции должны быть оценены перед вызовом функции, тогда как if должен основывать оценку второго параметра только на значении первого параметра. Форма while аналогична.

specialForms.while = (args, scope) => {
  if (args.length != 2) {
    throw new SyntaxError("Wrong number of args to while");
  }
  while (evaluate(args[0], scope) !== false) {
    evaluate(args[1], scope);
  }

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

Ещё один основной строительный блок — do, который выполняет все свои параметры сверху вниз. Значение всего выражения do — это значение последнего параметра.

specialForms.do = (args, scope) => {
  let value = false;
  for (let arg of args) {
    value = evaluate(arg, scope);
  }
};

Нам также нужно создать форму с именем define, чтобы создать привязку и присвоить ей значение. Первый параметр define — это слово, второй параметр — выражение, которое генерирует значение, и результат вычисления второго параметра присваивается первому параметру. Поскольку define также является выражением, оно должно возвращать значение. Мы определяем, что define должен возвращать присвоенное значение привязки (аналогично оператору = в JavaScript).

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

Среда

Функция оценки принимает область видимости в качестве аргумента, имя которой соответствует имени привязки, а значение — значению этой привязки. Мы определяем объект для представления глобальной области видимости.

Сначала нам нужно определить логическую привязку, прежде чем мы сможем использовать ранее определённый оператор if. Поскольку существует только два логических значения, нам не нужно определять для них специальную грамматику. Нам просто нужно связать имена true и false с соответствующими значениями.

const topEnv = Object.create(null);

topScope.true = true;
topScope.false = false;

Теперь мы можем оценить простое выражение для инвертирования логического значения.

let prog = parse(`if(true, false, true)`);
console.log(evaluate(prog, topScope));
// → false

Чтобы предоставить основные арифметические и сравнительные операторы, мы также добавляем некоторые функции в область видимости. Чтобы сделать код коротким, мы используем цикл для создания набора операторов вместо определения всех операторов по отдельности. topScope[op] = Function("a, b", return a ${op} b;);

Вывод также является полезной функцией, поэтому мы поместим console.log в функцию и назовём её print.

topScope.print = value => {
  console.log(value);
  return value;
};

Таким образом, у нас есть достаточно основных инструментов для написания простых программ. Следующая функция предоставляет удобный способ написания и запуска программы. Она создаёт новый объект среды и анализирует выполнение предоставленной ей отдельной программы.

function run(program) {
  return evaluate(parse(program), Object.create(topScope));
}

Мы будем использовать цепочку прототипов объектов для представления вложенных областей видимости, чтобы программа могла добавлять привязки к своей локальной области видимости без изменения глобальной области видимости.

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 = (args, scope) => {
  if (!args.length) {
    throw new SyntaxError("Functions need a body");
  let body = args[args.length - 1];
  let params = args.slice(0, args.1ength - 1).map(expr => {
    if (expr.type != "word") {
      throw new SyntaxError("Parameter names must be words");
    }
    return expr.name;
  });

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

Функции в Egg могут иметь свою собственную локальную область видимости. Форма 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, сначала используя Function, вызывая компилятор JavaScript для компиляции кода и преобразования программы Egg в программу JavaScript, а затем выполняя скомпилированный результат. Если это реализовано правильно, Egg может работать очень быстро, и реализация такого компилятора действительно проста.

Если читатель заинтересован в этой теме, рекомендуется попробовать реализовать компилятор в качестве упражнения.

Стоя на плечах гигантов

Возможно, вы заметили, что при определении if и while они более или менее похожи на их аналоги в JavaScript. Точно так же значения в 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

Это обычно называют предметно-ориентированным языком (Domain-specific Language), который представляет собой язык, специально разработанный для выражения очень ограниченного объёма знаний в определённой области. Он может точно описывать вещи, которые необходимо выразить в его области, без лишних элементов. Такой язык более выразителен, чем универсальный язык.

Задачи

Массивы

Для поддержки массивов в Egg необходимо добавить следующие три функции в глобальную область видимости: array(...values) для построения массива, содержащего значения параметров, 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 позволяет функциям ссылаться на окружающую их среду, подобно функциям JavaScript, тело функции может использовать все локальные привязки, доступные при определении функции.

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

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

Оглядываясь назад на определение формы fun, объясните, как работает этот механизм.

Комментарии

Было бы здорово, если бы мы могли писать комментарии в Egg. Например, всякий раз, когда встречается знак фунта (#), мы рассматриваем оставшуюся часть строки как комментарий и игнорируем её, аналогично // в JavaScript.

Синтаксическому анализатору не нужно сильно меняться, чтобы поддерживать эту функцию. Нам нужно только изменить skipSpace, чтобы он пропускал комментарии так же, как пропускает пробелы, и вызывать skipSpace для пропуска комментариев. Измените код, чтобы реализовать эту функцию.

// This is