Это было субботнее утро, и я только что проснулся в тумане, пытаясь вспомнить обрывки прошлой недели. Сколько производственных проблем было? Я спал последние два дня? Или это был просто сон, в котором критическая зависимость — больше похожая на черный ящик, от которого сильно зависит наше приложение — вышла из строя по странным причинам, и в сюрреалистическом приступе ярости мы уничтожили наш кластер Kubernetes и создали новый? Я не мог сказать. Единственное, в чем я был уверен — мне нужен кофе.

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

Но я хотел что-то простое, легкое для понимания и маленькое. С тех пор, как я посмотрел этот доклад и этот доклад Кевлина Хенни, я все время думал о процедурном программировании — не о привычном, как Pascal и в какой-то степени C, а о более похожем на прародителя всех этих языков — ALGOL. ! Поэтому я хотел, чтобы мой язык был скорее процедурным, чем функциональным или объектно-ориентированным. Как мы увидим, хорошо спроектированный процедурный язык может выглядеть очень похоже на функциональный язык.

Круто, у меня есть план и у меня есть два дня, а точнее полтора дня. Что я могу сделать?

Создать язык программирования сложно — сложнее для лишенного сна мозга. Поэтому мне нужно было решить, каковы будут начальные ограничения. Вот что я придумал:

  1. Это будет переводчик. Компиляторы сложно построить за короткое время.
  2. В нем будут только скалярные типы данных — числа, строки и т. д.
  3. Он должен поддерживать структурированное программирование, особенно примитивы последовательности, выбора и итерации. А также подпрограммы или процедуры.
  4. Нужен РЕПЛ.

Вот и все!

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

Я мог бы использовать любые популярные библиотеки лексеров и синтаксических анализаторов, доступные практически для любых основных языков программирования, но кофеин (или его отсутствие в настоящее время ближе к вечеру) снова дал о себе знать и заставил меня написать все с нуля! Что ж, мозг, если ты этого хочешь, я найду короткий путь к успеху. Я буду использовать Meta Circular Evaluator!!

Что такое метакруговой оценщик? Он возник в четвертой главе известной книги по информатике и моей самой любимой книги Структура и интерпретация компьютерных программ. Проще говоря, метакруговой оценщик — это программа, написанная на языке, способном анализировать и оценивать собственные выражения — как Лисп в Лиспе. В стране языков Lisp часто очень легко создать мини-Lisp и построить из него DSL. SICP демонстрирует, как можно создать небольшую версию языка Scheme на языке Scheme. И как только вы создали свой мини-язык, вы можете присвоить его формам разные значения и семантику — например, все лениво, а не жадно. Оказывается, я мог просто использовать S-Expressions. Это просто префиксные обозначения, в которых операция идет впереди, а все аргументы следуют после, заключенные в круглые скобки. Итак, 2 + 3 + 4 становится (+ 2 3 4). И аналогичным образом сложные выражения 2 * Pi * square(r) становятся (* 2 Pi (square r)). Если бы я мог зацепиться за этот стиль выражений, то все, что мне было бы нужно, — это читатель, который мог бы читать эти выражения и преобразовывать их в структуры данных, которыми я мог бы манипулировать. Все основные Лиспы поставляются со встроенной суперфункцией, которая может это сделать — могучей read.

reader, как это называется в большинстве Лиспов, — это функция, часто называемая read, которая может считывать из стандартного ввода форму самого языка и преобразовывать ее в структуру данных. Поскольку s-выражения Лиспа — это просто список символов, любая строка, содержащая допустимое s-выражение, может быть прочитана с помощью reader, и она вернет список этих символов. А сам список является синтаксическим деревом, так как все операции в префиксной записи.

Так что я могу поразить две цели с помощью одной функции — теперь у меня есть встроенные лексер и парсер. Но какой Lisp мне следует использовать?

Clojure — это выбор Lisp, к которому я в настоящее время склоняюсь больше всего. Сначала я долгое время был программистом на Common Lisp, создавая все свои любимые проекты на Common Lisp. В конце концов, я перешел на Racket из-за более включенных батарей. Несмотря на то, что Racket и Scheme дают чистый Lisp-подобный синтаксис, Clojure в последнее время, вероятно, является лучшим практичным диалектом Lisp с множеством библиотек и поддержкой. Поэтому я запустил Clojure REPL на Cursive и записал инь и ян метакругового оценщика.

(defn tronx-eval [code env]
  (cond
    (t-number? code) code
    (t-string? code) code
    (t-var? code) (t-lookup code env)
    (t-assignment? code) (t-assign code env)
    (t-do? code) (t-do code env)
    (t-if? code) (t-exec-if code env)
    (t-while? code) (t-do-while code env)
    (t-return? code) (t-make-return code env)
    (t-proc-defn? code) (t-make-proc code env)
    (t-proc-call? code) (t-proc-invoke code env)
    :else nil))

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

Теперь осталось собрать кусочки головоломки, и все должно заработать. Мы рассмотрим одну из этих частей головоломки, чтобы понять, как отдельные части также зависят от этого eval при выполнении своей работы. Вот определение t-assign

(defn t-assign [code env]
  (swap! env 
         merge {(second code) 
                (tronx-eval
                  (nth code 2)
                  env)}))

Эта функция принимает код в форме (:= x 12) и устанавливает для нашей среды значение 12, связанное с символом x. Но самое интересное, что он не просто берет то, что находится в третьем элементе списка кодов, но и вызывает для него eval. Конечным результатом является то, что мы можем назначить любой действительный результат кода для x, и он все равно будет работать! Так:

(:= x (foo (+ y 1) (* z 10)))

А как насчет env? Он представляет собой среду, в которой все переменные хранятся и передаются между различными фазами оценки. Здесь же хранятся новые определения процедур. И встроенные процедуры тоже. Таким образом, когда программа входит в новую область видимости, все новые переменные и процедуры привязываются к переданной среде, скрывая все, что в ней уже содержится. При выходе из области действия среда восстанавливается до того состояния, в котором она была до входа в область действия. В tronx новая область создается каждый раз, когда выполняется процедура или блок do.

Хорошо! Теперь, когда основные части собраны вместе, давайте попробуем.

(tronx-eval-code '((proc fact (n)
                           (:= p 1)
                           (while (>= n 1)
                             (:= p (* p n))
                             (:= n (- n 1)))
                           (return p))
                     (writeln "Factorial of 5 = " (fact 5)))
                   (new-env)) # Output: Factorial of 5 = 120

Этот тестовый код объединяет все части вместе. Исходный код tronx представляет собой список Clojure. Мы оцениваем этот фрагмент кода в свежей новой среде. Сам код в изолированном виде выглядит так:

(proc fact (n)
     (:= p 1)
     (while (>= n 1)
       (:= p (* p n))
       (:= n (- n 1)))
     (return p))

(writeln "Factorial of 5 = " (fact 5))

Мы определяем факториальную процедуру с итерацией — циклом while. В отличие от Pascal, tronx может определить процедуру для возврата значения, так что большой разницы между процедурой и функцией нет. Однако между возвратом tronx и другими языками есть тонкая разница. Вот один пример:

int calculate_sum(int x, int y)
{
    if (x <= 0) return 0;
    if (y >= 10) return 0;
    return x + y;
}

В этом коде C у нас есть два предварительных условия: 1. x должно быть больше 0 и 2. y должно быть меньше 10. Если какое-либо из этих условий не выполняется, мы возвращаем 0. Некоторые утверждают, что это действительно не так. чистая форма процедурного программирования, так как имеет несколько точек выхода из процедуры. Скорее настоящая процедура имеет только одну точку выхода — в конце. Tronx обеспечивает это, возвращая not при упоминании оператора return — он просто записывает его как возвращаемое значение и движется дальше. Следовательно, если мы не можем написать код, подобный приведенному выше, в tronx. Эквивалентный код tronx:

(proc calculate-sum (x y)
         (:= result 0)
         (if (> x 0)
           (if (< y 10)
             (:= result (+ x y))))
         (return result))

 (writeln (calculate-sum 0 3))
 (writeln (calculate-sum 2 10))
 (writeln (calculate-sum -1 9))
 (writeln (calculate-sum 5 5))
 (writeln (calculate-sum -1 13))

Теперь последнее — REPL. С Clojure read это легко.

(defn repl [prompt env]
  (loop []
    (print prompt " ")
    (flush)
    (let [code (read)
          e (tronx-eval code env)]
      (println
        (if (or
              (instance? clojure.lang.Atom e)
              (map? e))
          ""
          e)))
    (recur)))

И у меня появился рабочий язык в CLI — миссия выполнена!

Оглядываясь назад, использование Clojure в качестве языка реализации для нашего крошечного языка дало нам много преимуществ.

  1. Мы получили рабочую читалку бесплатно.
  2. Разбор синтаксического дерева был просто прохождением по списку Clojure.
  3. С eval/apply способ структурирования кода позволяет точно кодировать язык.
  4. У нас есть много функций, таких как процедуры более высокого порядка, бесплатно. Вот пример того, как процедура может быть передана в качестве аргумента — очень похоже на функциональные языки.
~>  (proc select (x p1 p2)
      (if (< x 0)
        (p1 x)
        (p2 x)))

~>  (proc f1 (x) (writeln (+ x 1)))

~>  (proc f2 (x) (writeln (- x 1)))

~>  (select -1 f1 f2)
0

~>  (select 1 f1 f2)
0

Было чертовски весело реализовать новый язык так быстро. Когда у меня был базовый язык, теперь было бы интересно расширить его, чтобы посмотреть, что можно добавить еще. Конечно, у меня есть список задач — массивы и хэши, типы структур, модули и базовый параллелизм. Но для этого придется подождать очередных выходных с кофеином! А пока код можно найти здесь: https://github.com/souravdatta/tronx