[Программирование, Lisp, Компиляторы] Простой интерпретатор Lisp на Umka
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Разработка моего статически типизированного скриптового языка 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, а не из последнего выпуска.
===========
Источник:
habr.com
===========
Похожие новости:
- [DIY или Сделай сам, Космонавтика, Научно-популярное, Программирование микроконтроллеров] Per aspera ad astra, или как я строил ракету. Часть 2. Собираем альтиметр на STM32 и BMP280
- [C, Программирование микроконтроллеров, 3D-принтеры] Прошивка для фотополимерного LCD 3D-принтера своими руками. Часть 3
- [JavaScript, Программирование] Compose повсюду: композиция функций в JavaScript (перевод)
- [Читальный зал, Программирование, Управление персоналом] Вредные советы: Как обучить джуниора
- [3D-принтеры, C, Программирование микроконтроллеров] Прошивка для фотополимерного LCD 3D-принтера своими руками. Часть 2
- [Laravel, Программирование] Новинки Laravel 8
- [Java, Программирование] Знакомимся с Event Sourcing. Часть 2 (перевод)
- [Программирование, Разработка мобильных приложений, GitHub] Используем бесплатные возможности Github Actions для CI/CD на Flutter-проекте
- [PHP, Программирование] Собеседование php-developer в 2020
- [C++, Программирование] Полиморфные аллокаторы c++17
Теги для поиска: #_programmirovanie (Программирование), #_lisp, #_kompiljatory (Компиляторы), #_interpretator (интерпретатор), #_kompiljator (компилятор), #_funktsionalnoe_programmirovanie (функциональное программирование), #_interpreter, #_compiler, #_programmirovanie (
Программирование
), #_lisp, #_kompiljatory (
Компиляторы
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 18:17
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Разработка моего статически типизированного скриптового языка Umka вошла в ту стадию, когда потребовалась проверка языковых возможностей на более сложных примерах, чем скрипты в пару десятков строк. Для этого я решил реализовать на своём языке интерпретатор Lisp. На это меня вдохновил педагогический эксперимент Роба Пайка, одного из создателей языка Go. Недавно Пайк опубликовал маленький интерпретатор Lisp на Go. Особенно впечатлило замечание Пайка, что описание интерпретатора заключено на одной странице 13 древнего руководства по Lisp 1.5. Учитывая синтаксическое родство Umka и Go, было трудно не поддаться соблазну построить такой интерпретатор на Umka, но не буквальным переносом кода Пайка, а полностью заново, от основ. Надеюсь, знатоки Lisp и функциональных языков простят мне наивное изумление от соприкосновения с прекрасным.На непосвящённых Lisp может произвести впечатление, близкое к шоку. Где граница между кодом и данными? Где циклы? Где стек? Единственной структурой данных является дерево. Оно же может представлять список. Оно же становится абстрактным синтаксическим деревом при разборе программы. Оно же заменяет собой стек при вычислении выражений. Любое дерево можно попытаться исполнить как код или использовать как данные. Вместо циклов — рекурсия. В ядре языка нет даже арифметики. И тем не менее, это полный по Тьюрингу язык, который можно бесконечно расширять и посыпать синтаксическим сахаром.Определение минимального интерпретатора Lisp действительно занимает меньше страницы. Конечно, с некоторой натяжкой: в нём используются функции, определённые на нескольких предыдущих страницах. Кажется, создатель Lisp Джон Маккарти из азарта старался превзойти сам себя в лаконизме и в итоге опубликовал микроруководство по Lisp, содержащее определение языка вместе с исходником интерпретатора — в общей сложности две журнальные страницы. Правда, добавил в заголовок: "Not the whole truth". Ядро языка (здесь мы говорим о самых старых и простых диалектах) требует наличия пяти элементарных функций, четырёх ключевых слов и двух констант, которые не могут быть выражены средствами самого языка. Базовые конструкции языка для тех, кто с ними не знаком
=========== Источник: habr.com =========== Похожие новости:
Программирование ), #_lisp, #_kompiljatory ( Компиляторы ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 18:17
Часовой пояс: UTC + 5