Pull to refresh

Comments 49

UFO landed and left these words here
Я бы не сказал, что в 10 строк. Семантику этих самых вложенных списков еще определить нужно, разобрать и транслировать в JS. Задача была написть именно Lisp, синтасических элементов которого в JS нет.
UFO landed and left these words here

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


(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 очень хорош!

Не надо усложнять правила разбора — Lisp потому и великолепен, что прост как бревно, даже Fort сложнее. Скобка — это всегда(!!!) список, первая лексема — всегда(!!!) операция. А для подавляющего большинства извращенцев программистов — существуют макросы.

Присвоение переменной лямбды, как (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
UFO landed and left these words here
Да, все так. Там автор сразу пишет, что это программа не для промышленного использования, в ней есть утечки памяти, и написана она была исключительно с целью поразбираться, как вообще работает интерпретатор лиспа. И мне кажется, что ценность его примера именно в том, что интерпретатор лиспа он реализует на C (ну или на C++), а это (по авторитетному мнению Пола Грэма), две различающиеся парадигмы вообще подхода к машинным вычислениям. Если «подход Си» идет от архитектуры вычислительных машин (архитектуры фон Неймана), то «подход лисп» идет, видимо, от математических построений, когда оказывается, что можно определить несколько примитивных функций в ядре языка (те, что перечислены в комментарии выше — cons, car, cdr и пр.), и из них построить функцию eval. Пол Грэм об этом интересно писал в своих эссе, кажется, «The roots of LISP».
UFO landed and left these words here
Продолжайте писать — тема интересная.
Спасибо! Чуть позже постараюсь написать о более сложных конструкциях языка и проблемах их трансляции в JS
Я тут между делом убийцу лиспа разрабатываю :-)
Идеи простые:
1. Вместо иерархии списков использовать полноценное дерево (любой узел дерева имеет имя и список вложенных узлов).
2. Для выражения структуры использовать не скобки, а отступы, что гарантирует читаемость кода.
3. Вместо странных имён операторов типа «CADDR», использовать единообразные говорящие имена в духе «cut-tail cut-head», что сильно упрощает освоение.

Но там пока мало чего есть: тесты, макросы, песочница, базовые операции над списками. Реализация сейчас на D, потом портирую на TS. Идеи и пожелания приветствуются.
Это очень здорово! Есть только один вопрос: а вы случайно не путаете средства предоставляемые окружением разразботки языка и средства самого языка? Вы пишите о том, что у вас есть тесты, макросы, песочница. Эти вещи предоставляет ваш язык?
Есть — громко сказано, конечно. Скорее на коленке слеплено. Скажем так, есть синтаксис (tree), есть реализации упомянутых базовых примитивов. Макросы и их исполнение в песочнице — основа. Тесты можно будет потом реализовать через макросы, но я ещё не дошёл до полноты по тьюрингу, а тестировать-то надо :-)
1. Не вижу разницы.

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)))
  1. Разница довольно существенная. И прежде всего она выражается в синтаксисе. Вместо (cdr '( one two three )), более наглядно:


    cut-head
        one
        two
        three

  2. При отладке нагенеренного макросами кода всё равно придётся копаться во всех этих caddr. Ну и обратная совместимость (ради которой и "не изобретается новый компилятор") привела бы к каше из новых и старых конструкций.


  3. Вот поэтому лисп и не завоевал мир :-) Код выглядит как каша в которой сложно разобраться неофиту. И фигурно выстроенные отступы тут мало спасают положение.
1. Разница в синтаксисе — это НЕ разница. Вы написали, что «вместо иерархии списков используется полноценное дерево». Иерархия списков, в данном случае, это и есть полноценное дерево — полноценнее некуда. Может я вас неправильно понял?

2. Вы и C++ код отлаживаете в ассемблерных инструкциях? Зачем вам отлаживать сгенерированный код, если есть возможность читать исходники?

3. Я обучил лиспу за пару вечеров 6-летнего ребенка (точнее научил синтаксису за 10 минут, а остальное время потратил на функции и рекурсию). Если ваши неофиты по уровню развития не превышают дошкольников, то пускай идут работать разнорабочими, а не программистами.
Для сравнения — синтаксис С он так и не смог адекватно понять.

Вы мне все же не ответили на вопрос — покажите, пожалуйста, как вышеприведенный, вполне простой и прозрачный код, будет выглядеть в вашем, более понятном и «гарантированно читабельном» виде? (ff-fold это свертка по хеш таблице, alive — внешняя функция проверки «а жива ли клетка», hash — хеш).
  1. Думаю вам стоит почитать определение дерева, как структуры данных. Если вкратце, каждый узел дерева имеет некоторое значение и список дочерних узлов. В очень частном и довольно бесполезном случае, значение узла может быть пустым. В лиспе всё дерево состоит исключительно из таких "пустых" узлов. Именно поэтому в нём так сильно распространён костыль с разделением списка на голову и хвост, когда первый элемент списка мало того, что не гомогенен с остальными, но и фактически определяет их семантику. К сожалению, синтаксически эта их фундаментальная роль никак не выделена. А разница в синтаксисе — это очень даже разница для языков. И именно списочный синтаксис не даёт лиспу завоевать мир (других причин не использовать лисп я не вижу).


  2. Когда я пишу кодогенератор (а макросы — это именно кодогенерация), то да, я смотрю, что там генерируется.


  3. Вы научили ребёнка держать кисть, но не научили рисовать картины. Синтаксису брейнфака вы его можете научить вообще за минуту. О чём это говорит? Только лишь о том, что синтаксис примитивен. Но чтобы понимать написанное, надо знать не только синтаксис, но и все используемые идиомы. Идиомы должны быть близки к предметной области. А синтаксис должен помогать в них разбираться, а не выступать визуальным шумом.


  4. Вот видите, вам потребовалось объяснять что делают эти операторы с "говорящими" названиями "ff-fold" и "alive". И это настоящая беда языков прошлого века. Сейчас самодокументируемость куда важнее экономии байт и нажатий клавиш. Я знаком с синтаксисом лиспа, не раз писал игру "жизнь" на разных языках, каждый день использую свёртки и замыкания, но я совершенно не понимаю, что делает ваш код. Да, я тупой клоун на велосипеде. Уволюсь, пожалуй, и пойду работать по призванию — вагоны разгружать.
1. А, так вы о конкретной реализации… Но ведь никто не мешает вам реализовать список как линейный массив указателей и/или непосредственных значений; никто вас не заставляет делать пары.

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:1

2) Это справедливо для любого другого языка, кроме лиспа, где генерирование — неотъемлимая часть программирования :-)


3) Я-то прекрасно понял. Но понимание синтаксиса и понимание что оно делает — совершенно разные вещи.


4) Не впадайте в крайности. get и cell-check вполне хватит. А вот что делает ff-fold, например, нагуглить не удалось. Ну, то есть понятно, что это какая-то свёртка, только что означает это "ff"?


5) Все, кто не исполняют ваших просьб — клоуны? Повторяю: я не понимаю, что делает ваш код, а дословная калька не покажет никаких преимуществ. Кроме того, язык ещё не полноценен. Так что всё, что я могу пока предложить — это несколько тестов c эквивалентами на православном лиспе.

1) Так никто же и не спорит, что именно дерево. Более того — 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. Ладно, извините за клоуна. Я иногда, возможно, бываю слишком резок, когда кто-то достаточно безапелляционно выдает вполне, на мой взгляд, бредовые вещи. Но консенсус всегда достижим. Продолжаем?
UFO landed and left these words here

У вас велосипедобоязнь? :-)


  1. Я прекрасно понимаю, что одна модель легко сводится к другой, но они всё же не эквивалентны.
  2. Не плохо, да. Только суть моей идеи не в том, что вы можете опускать скобки, а в том, что вы не можете опускать отступы. :-)

Для вас все, кто пытается изменить мир к лучшему — клоуны?

UFO landed and left these words here

Так расскажите об этих пробоемах. Именно для этого и был написан коментарий. А не для "проталкивания своего решения", которого, собственно, ещё и нет.

Тем, кому все же интересен лисп, а не очередной (полу)автоматический парсер из готовой тулзени, рекомендую отлично переведенную книгу «Lisp in Small Pieces». Ссылка на хабр же.

Наверняка, это отличная книга! Но, посыл статьи не был в том, чтобы написать именно лисп, он был в том, чтобы разобраться на примере лиспа, как пишутся формальные языки в современном мире. Например, на упомянутом в статье Jison'e написан CoffeeScript. Да и вообще, писать свои токенизатор/лексер/парсер/транслятор для реализации, скажем, языка размерки или конфигруации (да и ЯП) — не всегда хорошо и эффективно.

Ну так бы в первом абзаце и написали — «Я пишу цикл статей о формальных языках программирования. Для закрепления знаний на практике мы напишем простой Lisp. В первой части мы напишем парсер, во второй… и т.д.». И кому интересны именно ЯП, а не лишние телодвижения, сразу бы статью скипнули и не выдвигали претензий (а лично я бы вообще сразу перешел к написанию самого ЯП, а на парсер просто дал бы ссылку на гитхаб).

Да, это отличная книга. И в ней рассказывают именно о том, как написать формальный язык. Уж извините за критику, но то, что встатье — это базовые вещи. Это как если бы вы начали с букваря там, я не знаю.

Рекомендую ее почитать. Там нету никаких своих токенизатор/лексер/парсер/транслятор — там сразу берется готовый условный лисп (любой лисп имеет это все из коробки, естественно) и на нем же пишется новый условный лисп. Никакой долгой и муторной подготовки — сразу даются знания о том, как пишутся формальные языки программирования. И, что главное, последовательно и точно описываются все грабли, по которым вы, я так понимаю, намеревались уверенно станцевать.

Еще раз спасибо! Книгу уже скачал, обязательно прочту (ну как минимум поптаюсь прочесть).


И, что главное, последовательно и точно описываются все грабли, по которым вы, я так понимаю, намеревались уверенно станцевать.

Не исключено, что по нектороым уже станцевал :)

Если вдруг что — стучитесь в личку. Там потом попадутся довольно сложные вещи; например, продолжения (call/cc) — программистов, которые понимают, что это такое, можно по пальцам в своем окружении пересчитать.

Ну а вообще — я за Lisp во всем мире. Удачи!
UFO landed and left these words here
UFO landed and left these words here

Ага, чем-то похож на него. Но все же это больше postfix алгоритм.

Вот зачем создавать отдельные правила грамматики для плюса, минуса, умножения и т.п., если с точки зрения синтаксиса Lisp — они совершенно одинаковы?

Да, вы правы, возможно, все можно свести к "operation". Попробую посмотреть в эту сторону.

Так и есть, всё в Lisp является деревом, состоящим из атомов (литералов и идентификаторов) и списков. Список может означать как набор данных, так и код — всё зависит только от того, как вы его интерпретируете. Соответственно, и парсить ничего, кроме списков, вам не нужно.

Да, видел этот проект. Остановился на Jison просто потому, что использовал его до этого и он меня всем устраивал. Возмжоно, pegis ничем не хуже, а может и лучше. Какую-то сравнительную оценку дать не могу.

Автор, конечно, молодец… Но где макросы?!
Зачем столько специальных форм?

В упоминаемой ClojureScript специальных форм аж целых 20 штук (см. реализации этого мультиметода). Ну так то ClojureScript, который «production ready и имеет кучу приятных фич».

У вас же, насколько понимаю, все суть специальные формы. Даже map и reduce…
кстати, вот диалект лиспа: PicoLisp, в котором принципиально нет компилятора и макросов, но как ни странно, почти все задачи решаются гораздо компактнее, чем в других популярных лиспах. Пруф: rosettacode
в котором принципиально нет компилятора и макросов
Не забудьте только сказать об этом автору PicoLisp, а то он и не в курсе.
Вообще да, раз нету выделенной стадии компиляции (ибо это суть чистый интерпретатор), то вроде бы и нету макросов… Но ведь никто не запрещает биндить невыполеннные s-выражения а потом выполнять их через eval. Можно делать как-то так:
(de unless-my (c . body) 
  (if (not c)
    (run body)))
Чем не макрос?.. Ах, знаю! Тут же нету явного указания defmacros/define-syntax/etc!

А по поводу rosettacode…
1) PicoLisp явно ориентирован на «стенографическое программирование». Одно только de вместо def чего стоит (ух ты, букву сэкономили). А возможность писать (1 2 3) вместо '(1 2 3)… Дада, экономия целой кавычки!
2) Там очень много однострочников (по которым вообще языки гиблое дело сравнивать). Приведите плз большие примеры, которые на PicoLisp решаются гораздо (с ваших слов) компактнее. Конкретные примеры.
я конечно не эксперт по части лиспов. Но насчет макросов: там есть только read-макросы, а это несколько другая вещь. А обычных макросов там нету, поскольку они там и не нужны в силу специфики виртуальной машины пиколиспа.

По поводу 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)
Опять же, без конкретных бенчмарков/цифр сравнение разных БД не стоит и выеденного яйца.

сложно что-либо сказать по поводу того что макросы это те же функции, поскольку я не изучал детали реализации в других лиспах, в том числе и в Clojure. В PicoLisp же вообще нет понятия macro-expansion, насколько мне помнится. Т.е. исходный код фактически является конечным кодом для виртуальной машины.
Only those users with full accounts are able to leave comments. Log in, please.