Простой интерпретатор Lisp на Umka

    Разработка моего статически типизированного скриптового языка Umka вошла в ту стадию, когда потребовалась проверка языковых возможностей на более сложных примерах, чем скрипты в пару десятков строк. Для этого я решил реализовать на своём языке интерпретатор Lisp. На это меня вдохновил педагогический эксперимент Роба Пайка, одного из создателей языка Go. Недавно Пайк опубликовал маленький интерпретатор Lisp на Go. Особенно впечатлило замечание Пайка, что описание интерпретатора заключено на одной странице 13 древнего руководства по Lisp 1.5. Учитывая синтаксическое родство Umka и Go, было трудно не поддаться соблазну построить такой интерпретатор на Umka, но не буквальным переносом кода Пайка, а полностью заново, от основ. Надеюсь, знатоки Lisp и функциональных языков простят мне наивное изумление от соприкосновения с прекрасным.

    На непосвящённых Lisp может произвести впечатление, близкое к шоку. Где граница между кодом и данными? Где циклы? Где стек? Единственной структурой данных является дерево. Оно же может представлять список. Оно же становится абстрактным синтаксическим деревом при разборе программы. Оно же заменяет собой стек при вычислении выражений. Любое дерево можно попытаться исполнить как код или использовать как данные. Вместо циклов — рекурсия. В ядре языка нет даже арифметики. И тем не менее, это полный по Тьюрингу язык, который можно бесконечно расширять и посыпать синтаксическим сахаром.

    Определение минимального интерпретатора Lisp действительно занимает меньше страницы. Конечно, с некоторой натяжкой: в нём используются функции, определённые на нескольких предыдущих страницах. Кажется, создатель Lisp Джон Маккарти из азарта старался превзойти сам себя в лаконизме и в итоге опубликовал микроруководство по Lisp, содержащее определение языка вместе с исходником интерпретатора — в общей сложности две журнальные страницы. Правда, добавил в заголовок: "Not the whole truth".

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

    Базовые конструкции языка для тех, кто с ними не знаком
    • (car x) — выделение головы списка x

    • (cdr x) — выделение хвоста списка x

    • (cons x y) — соединение списков x и y

    • (atom x) — проверка x на атомарность

    • (eq x y) — проверка атомарных элементов x и y на равенство

    • (cond (a x) (b y)) — выбор значения x или y по условию a или b

    • (quote x) — указание использовать x как есть, без вычисления

    • ((lambda (x) a) y) — вызов безымянной функции с телом a, формальным параметром x и фактическим параметром y

    • ((label ff (lambda (x) a)) y) — присвоение безымянной функции имени ff

    • t — истина

    • nil — ложь или пустое выражение

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

    ((label fac (lambda (n) (cond ((eq n 0) 1) ((quote t) (mul n (fac (sub n 1))))))) 6)

    В микроруководстве Маккарти этими средствами выражен весь интерпретатор Lisp, за исключением лексического и синтаксического разбора. В руководстве Lisp 1.5 на той самой странице 13 приведён почти такой же интерпретатор, но в более человекочитаемом псевдокоде. Его я и взял за основу своего маленького проекта. Потребовалось лишь добавить разбор текста программы, некое подобие REPL и импровизированную арифметику. Роб Пайк, видимо, поступил так же, но отказался от конструкции label в пользу defn, которая позволила ему не определять функцию заново всякий раз, когда требуется её вызвать. В ядре Lisp такой возможности не предусмотрено.

    Поскольку весь интерпретатор пронизан рекурсией и обработкой деревьев, он послужил отличным тестом многих возможностей языка Umka — от формирования стековых кадров до сборки мусора. Думаю, Umka хорошо справился с испытанием. Исправлять пришлось лишь два-три мелких бага, связанных с экспортом имён и опережающим описанием типов. Весь код интерпретатора занял меньше 400 строк.

    Желающим поиграть с моим интерпретатором и передать по эстафете вдохновение от Роба Пайка рекомендую взять папку с примерами из ветки master, а не из последнего выпуска.

    Средняя зарплата в IT

    110 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 8 431 анкеты, за 2-ое пол. 2020 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 2

      +2

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


      Очень хочется почитать о внутренностях этого языка и особенностях реализации компилятора. Просмотр исходников это совсем другое. Хотелось бы увидеть все, так сказать, глазами автора.

        0
        Спасибо! Думаю, мне стоит развить язык (например, добавив туда замыкания), прежде чем приниматься за описание внутренностей. Иначе буду выглядеть блёкло на фоне Crafting Interpreters. И да, собрать сообщество вокруг нового языка, если он не революционный, очень трудно. Скромное сообщество Umka пока помогло разве что протестировать интерпретатор на macOS и PowerPC и подготовить Makefile. Любопытствующих много, но когда ещё нет всего того обилия библиотек, какое есть для Python и Lua, практическая применимость языка страдает.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое