Для начала следует задать простой вопрос: для чего?
Писать свой язык программирования — практически всегда плохая идея. Так зачем нам еще один лисп? Тем более, что уже есть ClojureScript, который на данный момент является production ready и имеет кучу приятных фич. Конкурировать даже с ClojureScript — безумие, — не гворя уже о TypeScript, CoffeeScript, etc. Но язык нам нужен и не для этого!
В первую очередь мы ведь хотим разобраться с тем, как они вообще пишутся. Плюс ко всему, не обязательно писать язык "программирования", зачастую возникают задачи написать свой собственный язык разметки текста, конфигурации и так далее. Все это можно решить похожим образом.
Пожалуй, начнем
Для начала условимся, что язык программирования — это некий формализованный язык, синтаксис которого подчиняется определенным правилам. Для разбора этих правил нам нужно знать, какие вообще "слова" (т.е. единицы языка) нам могут встретиться. Это могут быть не слова в привычном понимании, это могут быть знаки пунктуации, числа, строки и так далее.
Например, в нашем языке может встретиться такая конструкция:
(+ 2 3)В ней как минимум использовано четыре "слова". Каждое слово это так называемый token. И для начала мы должны разбить наш текст на эти самые токены. Процесс разбития нашего исходного кода на токены называется токенизацией. Пока не будем углубляться детали, давайте лучше двигаться дальше. Представим, что мы разбили весь текст на токены, далее все эти токены нам нужно распарсить для того, чтобы получить абстрактное синтаксическое дерево (AST). Для этого нам нужно написать парсер, который бы умел обрабатывать полученную последовательность токенов. Опять же, не вдаваясь в детали, перейдем к следующему шагу: компиляция/трансляция. Теперь нам нужно наше AST преобразовать либо в машинный код, либо странслировать в другой язык. В нашем случае мы будет писать транслятор из AST в JS.
Написание токенизатора, парсера и транслятора — это не такая уж тривиальная задача, а потребность в таких инструментах исторически возникала очень часто, поэтому умные люди для упрощения данной задачи разработали генераторы лексеров и парсеров. Одним из таких генераторов является Bison. Но так как мы будем писать наш лисп на JS, то воспользуемся его JS налогом — Jison
Переходим к сути
Генератор парсеров Jison довольно просто использовать, для его несть grunt, gulp и webpack плагины, которые позволяют все ваши .jison фалый транслировать в JS файлы, уже содержащие готовый парсер. Я не буду описывать здесь как вам организовать проект на базе grunt/gulp/webpack. Будем просто использовать онлайн генератор парсеров http://zaa.ch/jison/try/.
Давайте для начала разберем пример калькулятора, который есть на сайте jison.
/* description: Parses end evaluates mathematical expressions. */
/* lexical grammar */
%lex
%%
\s+ {/* skip whitespace */}
[0-9]+("."[0-9]+)?\b {return 'NUMBER';}
"*" {return '*';}
"/" {return '/';}
"-" {return '-';}
"+" {return '+';}
"^" {return '^';}
"(" {return '(';}
")" {return ')';}
"PI" {return 'PI';}
"E" {return 'E';}
<<EOF>> {return 'EOF';}
/lex
/* operator associations and precedence */
%left '+' '-'
%left '*' '/'
%left '^'
%left UMINUS
%start expressions
%% /* language grammar */
expressions
: e EOF
{return $1;}
;
e
: e '+' e
{$$ = $1 + $3;}
| e '-' e
{$$ = $1 - $3;}
| e '*' e
{$$ = $1 * $3;}
| e '/' e
{$$ = $1 / $3;}
| e '^' e
{$$ = Math.pow($1, $3);}
| '-' e %prec UMINUS
{$$ = -$2;}
| '(' e ')'
{$$ = $2;}
| NUMBER
{$$ = Number(yytext);}
| E
{$$ = Math.E;}
| PI
{$$ = Math.PI;}
;
В первой части этого файла, после комментария / lexical grammar /, как раз и находится описание всех наших "слов" языка. Здесь мы можем видеть как определяется число (да, можно определять токены через регулярные выражения, но это не всегда хорошо, иногда для определения высокоуровневого токена лучше использовать комбинацию более простых токенов). Здесь есть и токены арифметических операций: сложения, умножения, вычитания и деления.
Если скопировать весь текст грамматики в онлайн генератор, затем ввести выражение 10 + 10, то мы получим результат 20. Как так получается?
Давайте разберемся с тем, что, например, определяет эта конструкция:
e
: e '+' e
{$$ = $1 + $3;}
| e '-' e
{$$ = $1 - $3;}
| e '*' e
{$$ = $1 * $3;}
| e '/' e
{$$ = $1 / $3;}
| e '^' e
{$$ = Math.pow($1, $3);}
| '-' e %prec UMINUS
{$$ = -$2;}
| '(' e ')'
{$$ = $2;}
| NUMBER
{$$ = Number(yytext);}
| E
{$$ = Math.E;}
| PI
{$$ = Math.PI;}
;На самом деле, все очень просто, здесь мы говорим, что "e" (expression) может быть суммой двух выражений:
: e '+' e
{$$ = $1 + $3;}
...Из этого пример уже видно, что каждое наше определение любой новой синтаксической конструкции может быть рекурсивным. В данном случае, мы говорим, что expression может быть записан так: expression + expression. Встречая такую конструкцию, парсер будет ее токенезировать и затем выполнять код, который находится в фигурных скобках: { $$ = $1 + $3}. Это обычный JS код. Необычные тут только переменные, которыми мы оперируем: $$, $1, $3.
Давайте разбираться. $$ — это результат выражения, то есть то, что будет передано дальше по дереву разбора. $1 — первый элемент конструкции, на примере записи "10 + 10", $1 — это число 10. $3 — это третий элемент конструкции. Вторым элементом был бы '+', но так как сам по себе он нам не нужен, мы просто пропускаем его и выполняем сложение двух переменных с последующим сохранением результата в $$.
Далее следуют другие pattern'ы конструкции "e". Первый pattern всегда записывается через ":", последующие же — через "|", в конце ставится ";".
%start expressions
%% /* language grammar */
expressions
: e EOF
{return $1;}
;
Вот здесь мы говорим, что весь разбор начнется с pattern'a expressions, который в свою очередь представляет одно любое выражение "e" и конец файла. В фигурных скобочках здесь нам нужно вернуть результат всего разбора. В данном случае это будет результат одного выражения.
Переходим к написанию lisp
С калькулятором мы разобрались, давайте теперь попробуем заставить работать выражение:
(+ 1 2)Для этого давайте определим свою грамматику. Как я говорил ранее, в нашем выражении встречается как минимум 4 токена: "(", "+", "NUMBER" и ")".
Давайте опишем это в соответствующей части файла с грамматикой:
/* description: Parses end executes mathematical expressions. */
/* lexical grammar */
%lex
%%
\s+ /* skip whitespace */
[0-9]+("."[0-9]+)?\b return 'NUMBER'
"+" return '+'
"(" return '('
")" return ')'
<<EOF>> return 'EOF'
/lex
%start program
%% /* language grammar */
expr
: '(' '+' NUMBER NUMBER ')'
{ $$ = +$3 + +$4 }
;
program
: expr EOF
{return $1;}
;Это вся грамматика, которая позволит нам складывать два числа, но сложение двух чисел… Этого как-то мало. А что, если нам нужно сложить как в лиспе N чисел:
(+ 1 2 3 4 5)Давайте исправим нашу грамматику:
/* description: Parses end executes mathematical expressions. */
/* lexical grammar */
%lex
%%
\s+ /* skip whitespace */
[0-9]+("."[0-9]+)?\b return 'NUMBER'
"+" return '+'
"(" return '('
")" return ')'
<<EOF>> return 'EOF'
/lex
%start program
%% /* language grammar */
value
: NUMBER
{ $$ = +$1}}
;
values
: value
{ $$ = [$1] }
| values value
{ $$ = $1.concat($2)}
;
expr
: '(' '+' values ')'
{ $$ = $3.reduce(function(a, b){return a +b }) }
;
program
: expr EOF
{return $1;}
;Обратите внимание, что здесь я сначала перечисляю то, что у нас может выступать в качестве value, определяя тем самым value, а затем рекурсивно определяю values:
value
: NUMBER
{ $$ = +$1}}
;
values
: value
{ $$ = [$1] }
| values value
{ $$ = $1.concat($2)}
;То есть, values может быть одним или N подряд идущих value. При этом, я говорю, что value в values — это массив из одного value, а уже values — это объединение предыдущих значений массива с каждым последующим.
В результате парсинга values мы получаем массив чисел, для которого просто выполняем reduce, чтобы получить значение суммы всех чисел. Теперь операция:
( + 1 2 3 4 5)вернет 15.
Поздравляю! Мы с вами написали первую и самую простую конструкцию языка lisp. Думаю, что реализовать вычитание, умножение и деление тоже не составит для вас никакого труда. Естественно, в рамках одной статьи невозможно описать процесс разработки все языка, даже всех базовых конструкций, но! Если вы заинтересовались этой темой, то можете перейти по этой ссылке: https://github.com/daynin/tiny-lisp
Это репозиторий проекта, в котором как раз при помощи Jison разрабатывается Lisp на JS. Там уже много чего реализовано, но тем не менее, это по прежнему очень маленький проект. Если вы хотите попробовать себя в разработке языка, то этот проект вам как нельзя лучше подходит!
P.S.
Если вам интересна эта тем, то я могу превратить это в небольшой цикл статей, где бы рассказал и показал, как все же можно довести язык хотя бы того состояния, в котором он представлен по ссылке выше
Комментарии (50)
vintage
10.04.2016 21:36+2Я тут между делом убийцу лиспа разрабатываю :-)
Идеи простые:
1. Вместо иерархии списков использовать полноценное дерево (любой узел дерева имеет имя и список вложенных узлов).
2. Для выражения структуры использовать не скобки, а отступы, что гарантирует читаемость кода.
3. Вместо странных имён операторов типа «CADDR», использовать единообразные говорящие имена в духе «cut-tail cut-head», что сильно упрощает освоение.
Но там пока мало чего есть: тесты, макросы, песочница, базовые операции над списками. Реализация сейчас на D, потом портирую на TS. Идеи и пожелания приветствуются.
Uri
10.04.2016 23:28+31. Не вижу разницы.
3. Элементарно решается штатными средствами, вместо изобретения нового компилятора.
(define first car) (define second cadr) (define third caddr)
2. ??? Вы серьезно? Как у вас, например, должен выглядеть вот такой код:
; new convey's generation (ff-fold (lambda (st key value) (let ((x (mod key 65536)) (y (div key 65536))) (fold (lambda (st key) (let ((x (car key)) (y (cdr key))) (if (alive generation x y) (put st (hash x y) 1) st))) (if (alive generation x y) (put st (hash x y) 1) st) ; the cell (list (cons (- x 1) (- y 1)) ; possible cell neighbors (cons x (- y 1)) (cons (+ x 1) (- y 1)) (cons (- x 1) y ) ;cons x y ) (cons (+ x 1) y ) (cons (- x 1) (+ y 1)) (cons x (+ y 1)) (cons (+ x 1) (+ y 1)))))) #empty generation)))vintage
11.04.2016 10:14-1Разница довольно существенная. И прежде всего она выражается в синтаксисе. Вместо
(cdr '( one two three )), более наглядно:
cut-head one two three
При отладке нагенеренного макросами кода всё равно придётся копаться во всех этих caddr. Ну и обратная совместимость (ради которой и "не изобретается новый компилятор") привела бы к каше из новых и старых конструкций.
- Вот поэтому лисп и не завоевал мир :-) Код выглядит как каша в которой сложно разобраться неофиту. И фигурно выстроенные отступы тут мало спасают положение.
Uri
11.04.2016 20:531. Разница в синтаксисе — это НЕ разница. Вы написали, что «вместо иерархии списков используется полноценное дерево». Иерархия списков, в данном случае, это и есть полноценное дерево — полноценнее некуда. Может я вас неправильно понял?
2. Вы и C++ код отлаживаете в ассемблерных инструкциях? Зачем вам отлаживать сгенерированный код, если есть возможность читать исходники?
3. Я обучил лиспу за пару вечеров 6-летнего ребенка (точнее научил синтаксису за 10 минут, а остальное время потратил на функции и рекурсию). Если ваши неофиты по уровню развития не превышают дошкольников, то пускай идут работать разнорабочими, а не программистами.
Для сравнения — синтаксис С он так и не смог адекватно понять.
Вы мне все же не ответили на вопрос — покажите, пожалуйста, как вышеприведенный, вполне простой и прозрачный код, будет выглядеть в вашем, более понятном и «гарантированно читабельном» виде? (ff-fold это свертка по хеш таблице, alive — внешняя функция проверки «а жива ли клетка», hash — хеш).vintage
11.04.2016 22:48Думаю вам стоит почитать определение дерева, как структуры данных. Если вкратце, каждый узел дерева имеет некоторое значение и список дочерних узлов. В очень частном и довольно бесполезном случае, значение узла может быть пустым. В лиспе всё дерево состоит исключительно из таких "пустых" узлов. Именно поэтому в нём так сильно распространён костыль с разделением списка на голову и хвост, когда первый элемент списка мало того, что не гомогенен с остальными, но и фактически определяет их семантику. К сожалению, синтаксически эта их фундаментальная роль никак не выделена. А разница в синтаксисе — это очень даже разница для языков. И именно списочный синтаксис не даёт лиспу завоевать мир (других причин не использовать лисп я не вижу).
Когда я пишу кодогенератор (а макросы — это именно кодогенерация), то да, я смотрю, что там генерируется.
Вы научили ребёнка держать кисть, но не научили рисовать картины. Синтаксису брейнфака вы его можете научить вообще за минуту. О чём это говорит? Только лишь о том, что синтаксис примитивен. Но чтобы понимать написанное, надо знать не только синтаксис, но и все используемые идиомы. Идиомы должны быть близки к предметной области. А синтаксис должен помогать в них разбираться, а не выступать визуальным шумом.
- Вот видите, вам потребовалось объяснять что делают эти операторы с "говорящими" названиями "ff-fold" и "alive". И это настоящая беда языков прошлого века. Сейчас самодокументируемость куда важнее экономии байт и нажатий клавиш. Я знаком с синтаксисом лиспа, не раз писал игру "жизнь" на разных языках, каждый день использую свёртки и замыкания, но я совершенно не понимаю, что делает ваш код. Да, я тупой клоун на велосипеде. Уволюсь, пожалуй, и пойду работать по призванию — вагоны разгружать.
Uri
16.04.2016 01:31+11. А, так вы о конкретной реализации… Но ведь никто не мешает вам реализовать список как линейный массив указателей и/или непосредственных значений; никто вас не заставляет делать пары.
2. Несколько разные вещи, «смотреть что там сгенерировалось» и «программировать на языке», не находите?
3. Вы так и не поняли, о чем я писал; хоть дочитали предложение, или на слове «ребенок» остановились? Попытаюсь объяснить доступнее: шестилетний ребенок способен понять синтаксис языка, его конструкцию, как им пользоваться и базовые примитивы за пару вечеров. Неофит, которому это недоступно и код выглядит как каша — ленивая или глупая скотина, которой место на стройке, а не в программировании.
4. facepalm, у меня нет слов. Ну предложите свои варианты названий, которые будут «самодокументируемые», надеюсь это не будут get-value-by-key-from-hash-table и check-that-cell-is-alive-or-dead-because-i-like-self-describing-functions? И при чем тут экономия байт, это вообще к чему?
И таки да, вы ведете себя как клоун. Я вас попросил привести пример того, как будет выглядеть приведенный код в вашем, «более лучшем» синтаксисе — а вы разводите демагогию «у вас код сам себя не документирует». Неужели боитесь дать конкретный ответ на конкретный вопрос?vintage
16.04.2016 08:411) При чём тут пары? Речь о том, что для AST (коим и является программа на лиспе) лучше подходит структура "дерево", где у каждого узла есть некоторый тип. А если говорить о конкретной реализации, то в моём велосипеде у каждого узла есть ещё и ссылка на координаты, где он объявлен, что позволяет, например, выводить такой стектрейс:
core.exception.RangeError@./jin/tree.d(271): Range violation ./examples/test.jack.tree#87:20 cut-tail ./examples/test.jack.tree#87:11 cut-head ./examples/test.jack.tree#88:7 body ./examples/test.jack.tree#85:6 jack ./examples/test.jack.tree#83:0 test ./examples/test.jack.tree#1:1
2) Это справедливо для любого другого языка, кроме лиспа, где генерирование — неотъемлимая часть программирования :-)
3) Я-то прекрасно понял. Но понимание синтаксиса и понимание что оно делает — совершенно разные вещи.
4) Не впадайте в крайности. get и cell-check вполне хватит. А вот что делает ff-fold, например, нагуглить не удалось. Ну, то есть понятно, что это какая-то свёртка, только что означает это "ff"?
5) Все, кто не исполняют ваших просьб — клоуны? Повторяю: я не понимаю, что делает ваш код, а дословная калька не покажет никаких преимуществ. Кроме того, язык ещё не полноценен. Так что всё, что я могу пока предложить — это несколько тестов c эквивалентами на православном лиспе.
Uri
17.04.2016 22:461) Так никто же и не спорит, что именно дерево. Более того — AST как дерево (T — Tree), входит в изначальный дизайн языка. Так действительно, при чем здесь пары? При том, что (если я вас правильно понял) вы противопоставляете свой узел дерева как линейный массив элементов «настоящему» узлу лиспа, как списку, состоящему из пар; под словом «дерево», в данном случае, понимая конечную реализацию языка.
Дебажная инфа в узлах — отличное решение, но к контексту разговора не относящееся. Хотя да, удобно, спорить не буду.
2) В C есть макросы (кодогенерация). С тоже попадает в эту категорию? В С++ есть шаблоны (кодогенерация), то же самое?
3) Конечно разные. Но без первого не будет второго.
4) ff-fold, это специфическая для диалекта свертка — свертка по хеш-таблице (мне кажется, можно было по подсказке «хеш-таблица» догадаться, что если обычный fold в лямбду отдает state и value, то fold с тремя аргументами по хеш-таблице отдает state, key и value).
Вы же понимаете, что я просто выдрал кусочек рабочей программы с целью посмотреть на живом примере, как оно будет на деле в вашем синтаксисе, вместо того, что бы пустопорожне высказывать свой скепсис; а не тщательно готовился выбирая «самый правильный» и «самый r7rs-compliant» вариант? По моему мнению — этот кусочек вполне подходит чтобы оценить.
5) Что значит «дословная калька не покажет»? Вы написали, что используете отступы, а не скобки для гарантированной читаемости кода. Для того, чтобы оценить синтаксис — калька отлично подходит. А если вы собираетесь менять алгоритм — то это уже рефакторинг, а не синтаксические различия.
Я видел тесты, это чуть ли не первое, что я в проекте посмотрел. К сожалению, оценить по ним ничего не выходит — они слишком маленькие и простые. Поэтому и выдал свой пример, снова таки, вполне, по моему мнению, подходящий — там есть аргументы, есть лямбда, есть сложноотформатированный для лучшей читабельности список и условие в одну строку, тоже для лучшей читабельности.
p.s. Что делает этот код — на основании хеш-таблицы с прямой адресацией, в которой хранятся хешированные (как y*65536+x) координаты «живых» клеток, генерирует новую аналогичную хеш-таблицу, проверяя не только текущую клетку (а не должна ли она умереть), но и все 8 соседних (а не должны ли они родится). Результат — новое поколение на зацикленной карте 65536*65536. #empty — пустая таблица, но вроде это и так очевидно.
p.p.s. Ладно, извините за клоуна. Я иногда, возможно, бываю слишком резок, когда кто-то достаточно безапелляционно выдает вполне, на мой взгляд, бредовые вещи. Но консенсус всегда достижим. Продолжаем?
artemonster
11.04.2016 07:30+6Зачем городить свои велосипеды?
1. нет разницы между вложенными списками и деревьями. если вы это не понимаете, то у вас серьезёные проблемы
2. http://www.dwheeler.com/readable/
3. макросы или define, как уже сверху говорили.
Вечно вам «убийцу» изобрести нужно, когда на самом деле просто из себя клоуна делаете :(vintage
11.04.2016 10:37У вас велосипедобоязнь? :-)
- Я прекрасно понимаю, что одна модель легко сводится к другой, но они всё же не эквивалентны.
- Не плохо, да. Только суть моей идеи не в том, что вы можете опускать скобки, а в том, что вы не можете опускать отступы. :-)
Для вас все, кто пытается изменить мир к лучшему — клоуны?
artemonster
11.04.2016 11:31+2Не. велосипеды сам люблю. Только не бегу на хабр кричать о том, как я тут все стандарты сломал и «убил» — в этом и отличие клоунов от изобретателей, что мир к лучшему меняют. У последних нет tunnel vision/confirmation bias, что затмевает им все мозги и не дает видеть проблемы в своей идее. У вас же всё идеально в своих идеях. И не потому что это так, а потому что вы не хотите видеть эти проблемы.
vintage
11.04.2016 11:55Так расскажите об этих пробоемах. Именно для этого и был написан коментарий. А не для "проталкивания своего решения", которого, собственно, ещё и нет.
Uri
10.04.2016 23:14Тем, кому все же интересен лисп, а не очередной (полу)автоматический парсер из готовой тулзени, рекомендую отлично переведенную книгу «Lisp in Small Pieces». Ссылка на хабр же.
golovim
10.04.2016 23:24Наверняка, это отличная книга! Но, посыл статьи не был в том, чтобы написать именно лисп, он был в том, чтобы разобраться на примере лиспа, как пишутся формальные языки в современном мире. Например, на упомянутом в статье Jison'e написан CoffeeScript. Да и вообще, писать свои токенизатор/лексер/парсер/транслятор для реализации, скажем, языка размерки или конфигруации (да и ЯП) — не всегда хорошо и эффективно.
Uri
10.04.2016 23:45Ну так бы в первом абзаце и написали — «Я пишу цикл статей о формальных языках программирования. Для закрепления знаний на практике мы напишем простой Lisp. В первой части мы напишем парсер, во второй… и т.д.». И кому интересны именно ЯП, а не лишние телодвижения, сразу бы статью скипнули и не выдвигали претензий (а лично я бы вообще сразу перешел к написанию самого ЯП, а на парсер просто дал бы ссылку на гитхаб).
Да, это отличная книга. И в ней рассказывают именно о том, как написать формальный язык. Уж извините за критику, но то, что встатье — это базовые вещи. Это как если бы вы начали с букваря там, я не знаю.
Рекомендую ее почитать. Там нету никаких своих токенизатор/лексер/парсер/транслятор — там сразу берется готовый условный лисп (любой лисп имеет это все из коробки, естественно) и на нем же пишется новый условный лисп. Никакой долгой и муторной подготовки — сразу даются знания о том, как пишутся формальные языки программирования. И, что главное, последовательно и точно описываются все грабли, по которым вы, я так понимаю, намеревались уверенно станцевать.golovim
10.04.2016 23:49Еще раз спасибо! Книгу уже скачал, обязательно прочту (ну как минимум поптаюсь прочесть).
И, что главное, последовательно и точно описываются все грабли, по которым вы, я так понимаю, намеревались уверенно станцевать.
Не исключено, что по нектороым уже станцевал :)
Uri
11.04.2016 00:35Если вдруг что — стучитесь в личку. Там потом попадутся довольно сложные вещи; например, продолжения (call/cc) — программистов, которые понимают, что это такое, можно по пальцам в своем окружении пересчитать.
Ну а вообще — я за Lisp во всем мире. Удачи!artemonster
11.04.2016 10:25«в своем окружении пересчитать»: тогда нужно рекурсивно смотреть в parent environment? :D
Elfet
11.04.2016 07:45А вот зацените мой маленький компилятор для C-like выражений в lisp. Менее чем в 90 строк кода.
Beholder
11.04.2016 15:28+2Вот зачем создавать отдельные правила грамматики для плюса, минуса, умножения и т.п., если с точки зрения синтаксиса Lisp — они совершенно одинаковы?
golovim
11.04.2016 15:47-1Да, вы правы, возможно, все можно свести к "operation". Попробую посмотреть в эту сторону.
burjui
11.04.2016 16:35Так и есть, всё в Lisp является деревом, состоящим из атомов (литералов и идентификаторов) и списков. Список может означать как набор данных, так и код — всё зависит только от того, как вы его интерпретируете. Соответственно, и парсить ничего, кроме списков, вам не нужно.
ghosthope
11.04.2016 17:14Не пробовали смотреть в сторону pegjs (http://pegjs.org/)?
golovim
11.04.2016 17:18Да, видел этот проект. Остановился на Jison просто потому, что использовал его до этого и он меня всем устраивал. Возмжоно, pegis ничем не хуже, а может и лучше. Какую-то сравнительную оценку дать не могу.
anjensan
12.04.2016 11:29Автор, конечно, молодец… Но где макросы?!
Зачем столько специальных форм?
В упоминаемой ClojureScript специальных форм аж целых 20 штук (см. реализации этого мультиметода). Ну так то ClojureScript, который «production ready и имеет кучу приятных фич».
У вас же, насколько понимаю, все суть специальные формы. Даже map и reduce…
mmans
13.04.2016 09:03кстати, вот диалект лиспа: PicoLisp, в котором принципиально нет компилятора и макросов, но как ни странно, почти все задачи решаются гораздо компактнее, чем в других популярных лиспах. Пруф: rosettacode
anjensan
13.04.2016 12:34в котором принципиально нет компилятора и макросов
Не забудьте только сказать об этом автору PicoLisp, а то он и не в курсе.
Вообще да, раз нету выделенной стадии компиляции (ибо это суть чистый интерпретатор), то вроде бы и нету макросов… Но ведь никто не запрещает биндить невыполеннные s-выражения а потом выполнять их черезeval. Можно делать как-то так:
Чем не макрос?.. Ах, знаю! Тут же нету явного указания defmacros/define-syntax/etc!(de unless-my (c . body) (if (not c) (run body)))
А по поводу rosettacode…
1) PicoLisp явно ориентирован на «стенографическое программирование». Одно только de вместо def чего стоит (ух ты, букву сэкономили). А возможность писать (1 2 3) вместо '(1 2 3)… Дада, экономия целой кавычки!
2) Там очень много однострочников (по которым вообще языки гиблое дело сравнивать). Приведите плз большие примеры, которые на PicoLisp решаются гораздо (с ваших слов) компактнее. Конкретные примеры.mmans
13.04.2016 12:55я конечно не эксперт по части лиспов. Но насчет макросов: там есть только read-макросы, а это несколько другая вещь. А обычных макросов там нету, поскольку они там и не нужны в силу специфики виртуальной машины пиколиспа.
По поводу rosettacode: возможно вы правы насчет «стенографического программирования», но за счет краткости и экспрессивности он по скорости уделывает многих конкурентов. Когда-то в далеком 2006 году пиколисп участвовал в каком-то состязании по СУБД, и оказался на втором месте (на первом был MySQL. К сожалению в инете подробностей этой истории практически сейчас не найти. Насчет большого примера я пожалуй пас, это вам к автору, у него за 20 с лишним лет проектов накопилось прилично.anjensan
13.04.2016 13:08+1пиколисп участвовал в каком-то состязании по СУБД
Ну так сравнивался же не сам PicoLisp, а БД, встроенная в него! Еще вопрос, кстати, что и как сравнивалось… Огромный такой вопрос. :)
В любом случае, это не имеет отношения к экспресивности языка и к сравнению его в другими лиспами.
А обычных макросов там нету, поскольку они там и не нужны в силу специфики виртуальной машины пиколиспа.
Простите, я привел вам высказывание автора, мол макросы есть… Привел пример макроса… И Вы все еще доказываете, что их там нет?! Право, у меня опускаются руки…mmans
13.04.2016 13:30А вы не опускайте руки :)
То что вы привели — это самая обычная функция. В PicoLisp в зависимости от формы определения параметров они (параметры) либо вычисляются перед вызовом функции, либо нет. Это не повод навешивать на подобную функцию ярлык «макрос». Причем в определении функции можно задать первые несколько параметров вычисляемыми, а остальное невычисляемыми (как раз ваш пример). Я подозреваю, вы и так в курсе.
По поводу СУБД: так практически вся СУБД на самом лиспе и написана, только самые низкоуровневые функции на ассемблере (если говорить о 64битной версии.anjensan
13.04.2016 14:08+1То что вы привели — это самая обычная функция.
Ну так и макрос — это обычная функция…
Знаете, чем отличается макрос от обычной функции в Clojure… Булевым флагом у var-ячейки.
(def twice (fn [_ _ x] [x x])) ;; twice - функция, не обращаем внимания на 2 аргумента.... (twice nil nil (print "Ok")) ;; => Ok (alter-meta! #'twice assoc :macro true) ;; А теперь, *внезапно*, это макрос! (twice (print "Ok")) ;; => OkOk (alter-meta! #'twice assoc :macro false) ;; Не, пускай опять будет функцией... (twice nil nil (print "Ok")) ;; => Ok
Т.е. макрос — это самая обычная функция, которая не вычисляет свои агрументы при вызове, а вместо них получает сырые s-выражения. Остальное — уже детали реализации. Собственно, в PicoLisp вполне можно реализовать классический defmacro, а других лиспах можно реализовать аналог 'de. Было бы желание. Концептуально вещи равносильные, скорее вопрос терминологии.
По поводу СУБД: так практически вся СУБД на самом лиспе и написана, только самые низкоуровневые функции на ассемблере (если говорить о 64битной версии.
Не удивительно, учитывая interop с сишным кодом.
Опять же, без конкретных бенчмарков/цифр сравнение разных БД не стоит и выеденного яйца.~ > picolisp : (de a 123) -> a : (a 456) fish: “picolisp” terminated by signal SIGSEGV (Address boundary error)
mmans
13.04.2016 14:45сложно что-либо сказать по поводу того что макросы это те же функции, поскольку я не изучал детали реализации в других лиспах, в том числе и в Clojure. В PicoLisp же вообще нет понятия macro-expansion, насколько мне помнится. Т.е. исходный код фактически является конечным кодом для виртуальной машины.
artemonster
Интересное в лиспе — интерплитатор (с), окружения и правила работы с символами. Вы же всю статью писали про парсинг вложенных списков, что делается, кстати, за 10 строк. Буэ.
golovim
Я бы не сказал, что в 10 строк. Семантику этих самых вложенных списков еще определить нужно, разобрать и транслировать в JS. Задача была написть именно Lisp, синтасических элементов которого в JS нет.
artemonster
вот вам: http://norvig.com/lispy.html
написано на питоне, но это в этом контесте иррелевантно.
golovim
Спасибо за отличный пример! На самом деле, очень хорошая реализация. На в вашем примере, чуть меньше ключевых слов, отсюда чуть меньше правил разбора конструкций, использующих эти слова. Например, в вашем примере нет отдельного способа определить функцию, кроме как присвоить люмду переменной. В моей реализации есть и такой способ и классический:
Вроде мелочь, а на самом деле это выливается усложнение правил разбора, так как теперь epression, который содержит имя в начале списка и агрументы далее — это не только вызво функции, а еще и ее объявление. Опять же, в вашем примере нет булевой логики, let scope и так далее, затом там много простых конструкций типа: null?, string?, number? eq? и так далее. Они делаются в одну строчку, но не расширяют возможности языка, я, например, в свою очередь перенес реализацию таких вещей напоследок, так как они делаются довольно просто и не ломают синтаксис.
Так же в приведенном вами примере никак не решают проблему everything is expression (поправьте меня, пожалуйста, если я ошибаюсь). То есть в результате выполенения такого кода:
Не вернется ничего, так как это в вашем примере транслируется просто в if cond:… else:…. Да, в ruby бы это не было проблемой, но в моем случае — это проблема. Возможно, в следующих статьях я освещу эту проблему и ее решение.
Тем не мнее, еще раз повторю, ваш пример реалзиации lisp очень хорош!
Uri
Не надо усложнять правила разбора — Lisp потому и великолепен, что прост как бревно, даже Fort сложнее. Скобка — это всегда(!!!) список, первая лексема — всегда(!!!) операция. А для подавляющего большинства
извращенцевпрограммистов — существуют макросы.Присвоение переменной лямбды, как (define (func args) ...) является ничем иным, как обычным макросом (в данном случае — гигиеническим), разворачивающимся в (define func (lambda (args) ...)
Например, таким:
Точно так же, как (let ...) спокойно разворачивается тем же способом в набор лямбд, вместо введения новой сущности:
Или же list:
То же самое касается cond, case, and, or, begin и остального зоопарка.
Вообще, по минимальному принципу — чтобы сделать Lisp, от ядра языка требуются cons, car, cdr, type, eq?, less?, lambda, quote, define, if, values и define-syntax + syntax-rules. А, да, еще разворачивать ' в quote, а '(...) в (list quote. quote. quote.). Где-то так.
klvov
И в дополнение к статье Норвига еще одна статья, где автор пишет интерпретатор лиспа по мотивам Норвига, но не на Питоне, а на Си. Между прочим, там уточняется не совсем очевидный вопрос — как сделать лямбды, когда в языке реализации интерпретатора (Си) их нет. Вот ссылка:
http://howtowriteaprogram.blogspot.ru/2010/11/lisp-interpreter-in-90-lines-of-c.html
183614956
Не на C, а на C++, на чистом си не получилось бы так лаконично. И там нет сборщика мусора, и вроде бы обработки ошибок. Реализация лиспа на любом языке без сборщика мусора — нетривиальная задача.
183614956
удалено
klvov
Да, все так. Там автор сразу пишет, что это программа не для промышленного использования, в ней есть утечки памяти, и написана она была исключительно с целью поразбираться, как вообще работает интерпретатор лиспа. И мне кажется, что ценность его примера именно в том, что интерпретатор лиспа он реализует на C (ну или на C++), а это (по авторитетному мнению Пола Грэма), две различающиеся парадигмы вообще подхода к машинным вычислениям. Если «подход Си» идет от архитектуры вычислительных машин (архитектуры фон Неймана), то «подход лисп» идет, видимо, от математических построений, когда оказывается, что можно определить несколько примитивных функций в ядре языка (те, что перечислены в комментарии выше — cons, car, cdr и пр.), и из них построить функцию eval. Пол Грэм об этом интересно писал в своих эссе, кажется, «The roots of LISP».
183614956
У Пола Грэма написано про различия императивного (например, процедурное или объектно-ориентированное программирование) и декларативного подхода (например, функциональное программирование). В императивном программировании программа рассматривается как последовательность инструкций, а в функциональном программировании программа пишется как большая математическая формула, которая по мере исполнения сворачивается в результат. И на Python, и на C++ пишут в основном в императивном стиле, так что в этом смысле схема реализации Лиспа на них похожа. Довольно сильно отличаться она будет, например, на самом же Лиспе или на Хаскеле. :)
Принципиальное различие между реализацией на Python и C++ состоит в том, что в последнем нет сборщика мусора и управление памятью нужно осуществлять самостоятельно. То есть, тут стоит помнить о том, что даже если нет обработки ошибок, то сборка мусора хоть в каком-то виде должна быть, если речь идет о чем-то более менее серьезном. Но верно подмечено, что автор сам упомянул о недостатках своего кода, так что как учебный пример — пойдет, да и написать сборщик мусора можно самому, благо есть алгоритмы и стандартизированные подходы, так что это не очень сложно.