Comments 50
Спасибо за отличный пример! На самом деле, очень хорошая реализация. На в вашем примере, чуть меньше ключевых слов, отсюда чуть меньше правил разбора конструкций, использующих эти слова. Например, в вашем примере нет отдельного способа определить функцию, кроме как присвоить люмду переменной. В моей реализации есть и такой способ и классический:
(def (sum a b) (+ a b))Вроде мелочь, а на самом деле это выливается усложнение правил разбора, так как теперь epression, который содержит имя в начале списка и агрументы далее — это не только вызво функции, а еще и ее объявление. Опять же, в вашем примере нет булевой логики, let scope и так далее, затом там много простых конструкций типа: null?, string?, number? eq? и так далее. Они делаются в одну строчку, но не расширяют возможности языка, я, например, в свою очередь перенес реализацию таких вещей напоследок, так как они делаются довольно просто и не ломают синтаксис.
Так же в приведенном вами примере никак не решают проблему everything is expression (поправьте меня, пожалуйста, если я ошибаюсь). То есть в результате выполенения такого кода:
(if (< 1 2) "yes" "no")Не вернется ничего, так как это в вашем примере транслируется просто в if cond:… else:…. Да, в ruby бы это не было проблемой, но в моем случае — это проблема. Возможно, в следующих статьях я освещу эту проблему и ее решение.
Тем не мнее, еще раз повторю, ваш пример реалзиации lisp очень хорош!
Присвоение переменной лямбды, как (define (func args) ...) является ничем иным, как обычным макросом (в данном случае — гигиеническим), разворачивающимся в (define func (lambda (args) ...)
Например, таким:
(define-syntax define
(syntax-rules (lambda)
((define (op . args) body)
(define op
(letrec ((op (lambda args body))) op)))))
Точно так же, как (let ...) спокойно разворачивается тем же способом в набор лямбд, вместо введения новой сущности:
(define-syntax let
(syntax-rules ()
((let ((var val) ...) exp . rest)
((lambda (var ...) exp . rest) val ...))
((let keyword ((var init) ...) exp . rest)
(letrec ((keyword (lambda (var ...) exp . rest))) (keyword init ...)))))
; где
(define-syntax letrec
(syntax-rules (rlambda)
((letrec ((?var ?val) ...) ?body) (rlambda (?var ...) (?val ...) ?body))
((letrec vars body ...) (letrec vars (begin body ...)))))
Или же list:
(define-syntax list
(syntax-rules ()
((list) '())
((list a . b)
(cons a (list . b)))))
То же самое касается 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.). Где-то так.
http://howtowriteaprogram.blogspot.ru/2010/11/lisp-interpreter-in-90-lines-of-c.html
Идеи простые:
1. Вместо иерархии списков использовать полноценное дерево (любой узел дерева имеет имя и список вложенных узлов).
2. Для выражения структуры использовать не скобки, а отступы, что гарантирует читаемость кода.
3. Вместо странных имён операторов типа «CADDR», использовать единообразные говорящие имена в духе «cut-tail cut-head», что сильно упрощает освоение.
Но там пока мало чего есть: тесты, макросы, песочница, базовые операции над списками. Реализация сейчас на D, потом портирую на TS. Идеи и пожелания приветствуются.
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)))
Разница довольно существенная. И прежде всего она выражается в синтаксисе. Вместо
(cdr '( one two three )), более наглядно:
cut-head one two three
При отладке нагенеренного макросами кода всё равно придётся копаться во всех этих caddr. Ну и обратная совместимость (ради которой и "не изобретается новый компилятор") привела бы к каше из новых и старых конструкций.
- Вот поэтому лисп и не завоевал мир :-) Код выглядит как каша в которой сложно разобраться неофиту. И фигурно выстроенные отступы тут мало спасают положение.
2. Вы и C++ код отлаживаете в ассемблерных инструкциях? Зачем вам отлаживать сгенерированный код, если есть возможность читать исходники?
3. Я обучил лиспу за пару вечеров 6-летнего ребенка (точнее научил синтаксису за 10 минут, а остальное время потратил на функции и рекурсию). Если ваши неофиты по уровню развития не превышают дошкольников, то пускай идут работать разнорабочими, а не программистами.
Для сравнения — синтаксис С он так и не смог адекватно понять.
Вы мне все же не ответили на вопрос — покажите, пожалуйста, как вышеприведенный, вполне простой и прозрачный код, будет выглядеть в вашем, более понятном и «гарантированно читабельном» виде? (ff-fold это свертка по хеш таблице, alive — внешняя функция проверки «а жива ли клетка», hash — хеш).
Думаю вам стоит почитать определение дерева, как структуры данных. Если вкратце, каждый узел дерева имеет некоторое значение и список дочерних узлов. В очень частном и довольно бесполезном случае, значение узла может быть пустым. В лиспе всё дерево состоит исключительно из таких "пустых" узлов. Именно поэтому в нём так сильно распространён костыль с разделением списка на голову и хвост, когда первый элемент списка мало того, что не гомогенен с остальными, но и фактически определяет их семантику. К сожалению, синтаксически эта их фундаментальная роль никак не выделена. А разница в синтаксисе — это очень даже разница для языков. И именно списочный синтаксис не даёт лиспу завоевать мир (других причин не использовать лисп я не вижу).
Когда я пишу кодогенератор (а макросы — это именно кодогенерация), то да, я смотрю, что там генерируется.
Вы научили ребёнка держать кисть, но не научили рисовать картины. Синтаксису брейнфака вы его можете научить вообще за минуту. О чём это говорит? Только лишь о том, что синтаксис примитивен. Но чтобы понимать написанное, надо знать не только синтаксис, но и все используемые идиомы. Идиомы должны быть близки к предметной области. А синтаксис должен помогать в них разбираться, а не выступать визуальным шумом.
- Вот видите, вам потребовалось объяснять что делают эти операторы с "говорящими" названиями "ff-fold" и "alive". И это настоящая беда языков прошлого века. Сейчас самодокументируемость куда важнее экономии байт и нажатий клавиш. Я знаком с синтаксисом лиспа, не раз писал игру "жизнь" на разных языках, каждый день использую свёртки и замыкания, но я совершенно не понимаю, что делает ваш код. Да, я тупой клоун на велосипеде. Уволюсь, пожалуй, и пойду работать по призванию — вагоны разгружать.
2. Несколько разные вещи, «смотреть что там сгенерировалось» и «программировать на языке», не находите?
3. Вы так и не поняли, о чем я писал; хоть дочитали предложение, или на слове «ребенок» остановились? Попытаюсь объяснить доступнее: шестилетний ребенок способен понять синтаксис языка, его конструкцию, как им пользоваться и базовые примитивы за пару вечеров. Неофит, которому это недоступно и код выглядит как каша — ленивая или глупая скотина, которой место на стройке, а не в программировании.
4. facepalm, у меня нет слов. Ну предложите свои варианты названий, которые будут «самодокументируемые», надеюсь это не будут get-value-by-key-from-hash-table и check-that-cell-is-alive-or-dead-because-i-like-self-describing-functions? И при чем тут экономия байт, это вообще к чему?
И таки да, вы ведете себя как клоун. Я вас попросил привести пример того, как будет выглядеть приведенный код в вашем, «более лучшем» синтаксисе — а вы разводите демагогию «у вас код сам себя не документирует». Неужели боитесь дать конкретный ответ на конкретный вопрос?
1) При чём тут пары? Речь о том, что для 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:12) Это справедливо для любого другого языка, кроме лиспа, где генерирование — неотъемлимая часть программирования :-)
3) Я-то прекрасно понял. Но понимание синтаксиса и понимание что оно делает — совершенно разные вещи.
4) Не впадайте в крайности. get и cell-check вполне хватит. А вот что делает ff-fold, например, нагуглить не удалось. Ну, то есть понятно, что это какая-то свёртка, только что означает это "ff"?
5) Все, кто не исполняют ваших просьб — клоуны? Повторяю: я не понимаю, что делает ваш код, а дословная калька не покажет никаких преимуществ. Кроме того, язык ещё не полноценен. Так что всё, что я могу пока предложить — это несколько тестов c эквивалентами на православном лиспе.
Дебажная инфа в узлах — отличное решение, но к контексту разговора не относящееся. Хотя да, удобно, спорить не буду.
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. Ладно, извините за клоуна. Я иногда, возможно, бываю слишком резок, когда кто-то достаточно безапелляционно выдает вполне, на мой взгляд, бредовые вещи. Но консенсус всегда достижим. Продолжаем?
У вас велосипедобоязнь? :-)
- Я прекрасно понимаю, что одна модель легко сводится к другой, но они всё же не эквивалентны.
- Не плохо, да. Только суть моей идеи не в том, что вы можете опускать скобки, а в том, что вы не можете опускать отступы. :-)
Для вас все, кто пытается изменить мир к лучшему — клоуны?
Наверняка, это отличная книга! Но, посыл статьи не был в том, чтобы написать именно лисп, он был в том, чтобы разобраться на примере лиспа, как пишутся формальные языки в современном мире. Например, на упомянутом в статье Jison'e написан CoffeeScript. Да и вообще, писать свои токенизатор/лексер/парсер/транслятор для реализации, скажем, языка размерки или конфигруации (да и ЯП) — не всегда хорошо и эффективно.
Да, это отличная книга. И в ней рассказывают именно о том, как написать формальный язык. Уж извините за критику, но то, что встатье — это базовые вещи. Это как если бы вы начали с букваря там, я не знаю.
Рекомендую ее почитать. Там нету никаких своих токенизатор/лексер/парсер/транслятор — там сразу берется готовый условный лисп (любой лисп имеет это все из коробки, естественно) и на нем же пишется новый условный лисп. Никакой долгой и муторной подготовки — сразу даются знания о том, как пишутся формальные языки программирования. И, что главное, последовательно и точно описываются все грабли, по которым вы, я так понимаю, намеревались уверенно станцевать.
А вот зацените мой маленький компилятор для C-like выражений в lisp. Менее чем в 90 строк кода.
Зачем столько специальных форм?
В упоминаемой ClojureScript специальных форм аж целых 20 штук (см. реализации этого мультиметода). Ну так то ClojureScript, который «production ready и имеет кучу приятных фич».
У вас же, насколько понимаю, все суть специальные формы. Даже map и reduce…
в котором принципиально нет компилятора и макросовНе забудьте только сказать об этом автору PicoLisp, а то он и не в курсе.
Вообще да, раз нету выделенной стадии компиляции (ибо это суть чистый интерпретатор), то вроде бы и нету макросов… Но ведь никто не запрещает биндить невыполеннные s-выражения а потом выполнять их через
eval. Можно делать как-то так:(de unless-my (c . body)
(if (not c)
(run body)))
А по поводу rosettacode…
1) PicoLisp явно ориентирован на «стенографическое программирование». Одно только de вместо def чего стоит (ух ты, букву сэкономили). А возможность писать (1 2 3) вместо '(1 2 3)… Дада, экономия целой кавычки!
2) Там очень много однострочников (по которым вообще языки гиблое дело сравнивать). Приведите плз большие примеры, которые на PicoLisp решаются гораздо (с ваших слов) компактнее. Конкретные примеры.
По поводу rosettacode: возможно вы правы насчет «стенографического программирования», но за счет краткости и экспрессивности он по скорости уделывает многих конкурентов. Когда-то в далеком 2006 году пиколисп участвовал в каком-то состязании по СУБД, и оказался на втором месте (на первом был MySQL. К сожалению в инете подробностей этой истории практически сейчас не найти. Насчет большого примера я пожалуй пас, это вам к автору, у него за 20 с лишним лет проектов накопилось прилично.
пиколисп участвовал в каком-то состязании по СУБДНу так сравнивался же не сам PicoLisp, а БД, встроенная в него! Еще вопрос, кстати, что и как сравнивалось… Огромный такой вопрос. :)
В любом случае, это не имеет отношения к экспресивности языка и к сравнению его в другими лиспами.
А обычных макросов там нету, поскольку они там и не нужны в силу специфики виртуальной машины пиколиспа.Простите, я привел вам высказывание автора, мол макросы есть… Привел пример макроса… И Вы все еще доказываете, что их там нет?! Право, у меня опускаются руки…
То что вы привели — это самая обычная функция. В PicoLisp в зависимости от формы определения параметров они (параметры) либо вычисляются перед вызовом функции, либо нет. Это не повод навешивать на подобную функцию ярлык «макрос». Причем в определении функции можно задать первые несколько параметров вычисляемыми, а остальное невычисляемыми (как раз ваш пример). Я подозреваю, вы и так в курсе.
По поводу СУБД: так практически вся СУБД на самом лиспе и написана, только самые низкоуровневые функции на ассемблере (если говорить о 64битной версии.
То что вы привели — это самая обычная функция.Ну так и макрос — это обычная функция…
Знаете, чем отличается макрос от обычной функции в 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)
Пишем свой Lisp на JavaScript