CL быстрее прочих :)

в контексте разговора о DSL это плохо подходит

с моей точки зрения язык должен 1. догадываться 2. верифицировать

зачатки этого есть даже в DSL-ях на шаблонах с++, однако это там достаточно неудобно

Ну это вообще общепринято (если формально) называть языком множество цепочек над словарём. Любой конечный механизм задания этих цепочек в структурном виде это уже грамматика - Хомского, BNF, или любое из трёх математических определений синтаксиса как множеств термов в начале TAPL - тоже пойдёт. А вот любые вычисления на этих структурах в том числе верификация это уже из семантической категории вещи.

Кстати, вот же что говорит Fare Rideau (надеюсь не надо рассказывать кто это) про метапрограммирование в CL:

Если вам нравится использовать нетривиальное метапрограммирование, то рекомендую избегать такого примитивного в этом отношении языка, как Common Lisp, и использовать современный язык с многостадийной компиляцией и четко определенной семантикой (например, язык модулей PLT Scheme, camlp4 для OCaml, и другие системы, обрабатывающие файлы детерминированным образом). У макросов PLT есть ряд преимуществ: гигеничность, совместимость с отладчиками и другими инструментами и т.п.

Полный текст здесь.

> Большинство используемых структур данных не прямо описаны в коде, а строятся различными комбинациями cons-ячеек.

ADT по жизни строится через комбинацию простых типов данных, а по количеству встроенных типов CL даст прикурить многим и многим (см. стандарт). Может ты какой-то не такой лисп курил? Их много вообще-то.

надеюсь не надо рассказывать кто это

не надо ;)

Полный текст здесь.

Читал, и кстати это не имеет никакого отношения к отвечаемогу посту. То что макросы PLT более широкие по возможностям - это понятно.

Да нет там никаких ADT, говорят же вам :)

> Читал, и кстати это не имеет никакого отношения к отвечаемогу посту

Нет, просто вспомнил.

То что макросы PLT более широкие по возможностям - это понятно.

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

метапрограммирование не является самой сильной стороной Common Lisp

Лично я нигде проповедованием дслэй и метапрограммирования нигде не занимался, так что не надо меня переубеждать в чём то :) - так как не придерживаюсь, категорически, какой-то крайней точки зрения.

(Таки да - макросы PLT по выразительности надмножество над макросистемой CL).

> Скажу по-другому. Большинство используемых структур данных не прямо описаны в коде, а строятся различными комбинациями cons-ячеек. Поэтому носят характер «соглашения между программистами».

Структуры данных либо упакованы в абстракцию, либо объекты. Если же начинаем упираться в «соглашения между программистами», понимаем что делаем что то явно не так. Вобще такие соглашения стоит упаковывать контексты/окружения. Другой вопрос что табличка «под страхом расстрела» не висит, но cons-ы и списки это в основном для кода а не структур данных. Тривиальные вещи типа property list не учитываю уж.

А если найду?

P.S. и если речь не о ADT, то не понятно о чём говорит автор. Битовый вектор он и в лиспе битовый вектор, например.

> Если же начинаем упираться в «соглашения между программистами», понимаем что делаем что то явно не так.

Дык, создаём функции для создания-манипулирования даными и если кто-то лезет потными ручонками со своим caddar, например, в обход официальных геттеров с сеттерами, то он либо:

а) знает что делает (слава Лиспу и гибкости его);

б) сам себе злобный антропоморфный дендромутант.

ADT - algebraic data type. Это то чего нет. Его можно эмулировать макросом одно определение каторого сгенерирует кучку defstruct, но вместе с сопутствующими вещами получится что мы делаем новый язык над CL (хотя это конечно можно). К примеру если взять http://sebfisch.github.com/haskell-regexp/regexp-play.pdf то никак не получится писать в таком стиле (ещё до ленивости) - соответсвующие вещи будут делаться в более низкоуровневом виде в стандартном CL.

> Дык, создаём функции для создания-манипулирования даными и если кто-то лезет потными ручонками со своим caddar, например, в обход официальных геттеров с сеттерами, то он либо:

а) знает что делает (слава Лиспу и гибкости его);

б) сам себе злобный антропоморфный дендромутант.

пропущен самый важный пункт: он ошибся, и затем будет тратить свое ценное время на поиск ошибки, а затем возможно и на написание теста для ее последующего отлова

> ADT - algebraic data type. Это то чего нет.

Ты чего совсем загнался )) Самая распространённая и известная в программировании расшифровка ADT - Abstract data type, у меня целый двухтомник где-то валяется, который прям так и называется...

вот один пример, искусственный, но поясняющий ситуацию:

допустим, у нас есть класс, реализующий локи (Lock), написанный программистом А; все локи лежат в одном большом массиве, на стэке создаются на них указатели

программист В для предотвращения взаимных блокировок собрался упорядочить все локи, для упорядочивания взят адрес внутри массива

программист С создал свой сборщик мусора для массива локов, который останавливает мир, сканирует стэк (допустим адреса локов могут быть только на стэке), перемещает локи внутри массива и корректирует адреса на стэке

__________________________________

А теперь внимание — вопрос! Кто из программистов В и С злобный дендромутант?

Ведь каждое из их изделий вполне безглючно работает с локами, хотя и юзает недокументированную функциональность — но *вместе* эти изделия начнут глючить.

Ну или abstract, algebraic это то же самое но подразумеваем более конкретное определение этих типов.

> А теперь внимание — вопрос! Кто из программистов В и С злобный дендромутант?

C. Объяснить почему, или так ясно?

локи

на стэке создаются на них указатели

для предотвращения взаимных блокировок

создал свой сборщик мусора

перемещает локи внутри массива и корректирует адреса на стэке

Нечего и сказать - очень распостранённая ситуация, да :)

> Ну или abstract, algebraic это то же самое но подразумеваем

более конкретное определение этих типов.

Я не понял, значит ты утверждаешь, что там списком, очередей, деревьев в CL быть не может?

> > Большинство используемых структур данных не прямо описаны в коде, а строятся различными комбинациями cons-ячеек.

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

Ага, только в одном случае мы объявляем тип «прайс»(например) и делаем интерфейс к нему из примитивных операций, а в другом случае, не объявляя таких типов, тупо используем везде assoc.

Может ты какой-то не такой лисп курил? Их много вообще-то.

По-моему я четко и недвусмысленно дал понять, какой именно именно лисп курил и какую книжку.

> Очень интересно что под этим имеется в виду. Если можно с примерами перегруженных конструкций.

Да почти все же. Стоит пару вложенных друг в друга let-cond'ов сделать и гемора не разгребешь, особенно, если пишешь макрос. Понятное дело, что, если ты далеко не первый и не второй день смотришь на такой код, он для тебя совсем не страшный уже. Дело упирается в тренировку «мозжечка».

> C. Объяснить почему, или так ясно?

Потому что его зовут Гвидо? :)

> (...) Если же начинаем упираться в «соглашения между программистами», понимаем что делаем что то явно не так. (...)

Правильно. Так я же вроде относил это к недостаткам, а не достоинствам. Так что рассказывай это Graham'у.

> Потому что его зовут Гвидо? :)

Гвидо не опускается до того, чтобы реализовывать сборку мусора для Си :)

Вот пример в виде настоящих АТД:

(define-data-type (btree a) (leaf a) (branch btree btree))
(define-function reflect ((leaf n))     (leaf n))
(define-function reflect ((branch l r)) (branch (reflect r) (reflect l)))

А вот апроксимация CL-кодом:

;;; from define-data-type

(deftype btree () '(or leaf branch))

(defstruct (leaf
            (:constructor leaf (atom)))
  atom)

(defstruct (branch
            (:constructor branch (left right)))
  (left  nil :type btree)
  (right nil :type btree))

;;; printers

(defmethod print-object ((leaf leaf) stream)
  (format stream "~A" (leaf-atom leaf)))

(defmethod print-object ((branch branch) stream)
  (format stream "<~A, ~A>"
          (branch-left branch)
          (branch-right branch)))

;;; from define-function

(declaim (ftype (function (btree) btree) reflect))
(defun reflect (btree)
  (etypecase btree
    (leaf    btree)
    (branch  (branch (reflect (branch-right btree))
                     (reflect (branch-left  btree))))))

(reflect (branch (leaf 1) (leaf 2)))

(branch (leaf 1) (leaf 2))           ;=> <1, 2>
(reflect (branch (leaf 1) (leaf 2))) ;=> <2, 1>

> Вот пример в виде настоящих АТД:

Перестань гнать. Или хотя прочитай определение абстрактных типов данных. Только не в учебниках по штанге.

В учебниках по штанге они алгебраические.

И ещё, скажи, нахрена ты лезешь во всякий матан, когда тривиальных вещей не знаешь?

Угу, скоро мы придём к тому, что программирование штангисты придумали, а прочих здесь и не стояло...

Вот пример в виде настоящих АТД:

Перестань гнать.

А вот и у меня уже состояние (0_o), к чёрту концепции даёшь три строки vs. портянка! В чём профит, видно же (?)

Или хотя прочитай определение абстрактных типов данны

Что мне это даст - в какой-то раз про «основные абстрактные типы данных, используемых в программировнии». Кнута, Седжвика или Кормена - не важно. Я ж уточнил - я абстрактные типы всегда свожу к алгебраическим, так как первое может быть чем угодно, а второе весьма определённая вещь - та первая строчка на самом деле лежит экстремально близко к некоторому (обще-топологическому) математическому определению (поэтому «алгебраические» типы).

И ещё, скажи, нахрена ты лезешь во всякий матан, когда тривиальных вещей не знаешь?

Каких тривиальных вещей я не знаю?

Ну, к чему придет quasimoto, я боюсь прогнозировать, ибо хаос. А вот /me, например, не относит понятие алгебраических типов данных исключительно к штанге, и уж тем более понятие абстрактных типов данных.

> Я ж уточнил - я абстрактные типы всегда свожу к алгебраическим

Издеваешься что-ли? Нахрена? Что это вообще значит «я свожу»? Есть устоявшаяся общепринятая терминология и все, кроме штангистов, под ADT понимаю именно абстрактные типы данных, которые вовсе не алгебраические.

> все, кроме штангистов, под ADT понимаю именно абстрактные типы данных

и кроме ML-щиков, и скалистов. Да кроме всех, кто использует современные языки :)

Ну, ещё раз - в большинстве случаев в большинстве языков ADT это «абстрактные типы данных», потому что языки разные и нужно наиболее общий термин для того чтобы очертить эту возможность - определять типы для стеков/очередей/дэк и т.п. В Си для этого есть структуры, где-то в Python можно использовать либо встроенный в язык богатый набор разных типов или использовать class-ы, в CL принято использовать списки (что плохо), структуры (как в примере выше для бинарных деревьев) или CLOS. Вот так - везде по разному, поэтому «**абстрактные** типы данных».

И раз везде по разному - типично для языков программирования - встаёт вопрос об оптимальном способе, о наиболее формальном, верифицируемом, и даже простом. Так получилось что математическая теория типа претерпевала некоторое развитие и в последние десятилетия имела некоторые связи с программированием. В итоге из всех возможных способов задавать эти «абстрактные типы данных» выделился (ну нет что прям - бац, и возник, скорее его можно выделить) один. Это способ наиболее близкий представлению о типах в теоретико-множественном смысле к представлению о функциях как об отображениях и вообще к близок к теории типов в категорном смысле. Короче этот оодин из спсобов задавать «абстрактные типы данных» и есть «алгебраические типы данных».

Нафига? Очень просто и декларативно - выше я определил бинарное дерево одной строчкой (вместо нескольких defstruct и возможных вспомагательных функций) - этим определяется _вообще_ всё о типе данных *бинарное дерево*, даже больше - этим определяется катаморфизм а с ним куча функций для опереривания бинарноми деревьями, но этого я не писал - вместо этого там две строчки для определения reflect - чтобы показать связь ADT и pattern-matching. И опять - при реализации типичными средствами (не связанных с Алгеб. типами Данных) получается reflect с бо'льшим количесвом ненужного кода.

// выдохнул )

Мда. Ну хотя бы русскую вики открыл.

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

Он абстрактный не от того, что реализуется в разных языках по-разному.

Он абстрактный не от того, что реализуется в разных языках по-разному.

Да не говорил я этого, появляются нездоровые ассоциации? Гоните их :)

Просто попытался выразится более подробно чтобы донести основную мысль - вот и получились двусмысленности (да и очепятки).

> Это способ наиболее близкий представлению о типах в теоретико-

множественном смысле к представлению о функциях как об отображениях

и вообще к близок к теории типов в категорном смысле. Короче этот

оодин из спсобов задавать «абстрактные типы данных» и есть

«алгебраические типы данных».

Ты чего сильно путаешь, ибо абстрактные типы данных отличаются тем, что вся работа с ними (в том числе создание) производится через заданный интерфейс, а как они реализованы, через списки ли, через структуры, или ещё как - абсолютно не важно. Поэтому слова «из всех возможных способов задавать эти „абстрактные типы данных“ выделился» лишены какого-либо смысла с точки зрения ADT.

Очень просто и декларативно - выше я определил бинарное

дерево одной строчкой

Не знаю что ты там определил, но точно не ADT.

> > Он абстрактный не от того, что реализуется в разных языках по-разному.

Да не говорил я этого, появляются нездоровые ассоциации? Гоните их :)

В Си для этого есть структуры, где-то в Python можно использовать либо встроенный в язык богатый набор разных типов или использовать class-ы, в CL принято использовать списки (что плохо), структуры (как в примере выше для бинарных деревьев) или CLOS. Вот так - везде по разному, поэтому «**абстрактные** типы данных».

Попытки тебя понять вызывают сплошную боль.

Поэтому слова «из всех возможных способов задавать эти „абстрактные типы данных“ выделился» лишены какого-либо смысла с точки зрения ADT.

Из всех возможных способов (аксиоматических, если угодно) говорить о языках задания ADT. Это мета-уровень, а не уровень того языка в котором задаётся ADT, фактически это уровень формального математичского языка.

Не знаю что ты там определил, но точно не ADT.

Это то же самое что:

data BTree a = Leaf a | Branch BTree BTree

Хотя, я не навязываю ничего. Раз ненужно - значит ненужно.

Понятно, звёздочки сыграли свою роль :(. Так вот - я не имел ввиду то что тебе показалось. Безусловно, с помощью структур CL или Си можно задавать абстрактные типы данных. А вот в ML и последователях принят подход к заданию этих АТД базирующийся на лежащих в бэкграунде понятий формальных теорий типов и функций.

> Из всех возможных способов (аксиоматических, если угодно) говорить

о языках задания ADT.

Ничего не понял, зачем об этом говорить?

Это мета-уровень, а не уровень того языка в котором задаётся ADT,

фактически это уровень формального математичского языка.

Ты вообще что хотел сказать? Слова по отдельности понял, а смысла не уловил.

Точнее,

data BTree a = Leaf a | Branch (BTree a) (BTree a)

утверждает обще-топологический изоморфизм:

(BTree a) ~ (Leaf a) ⊕ (BTree a) ⊗ (BTree a)

Хм, по чём нынче «корабль» хаскеля?

Ничего не понял, зачем об этом говорить?

Ну вот у deftype/defstruct/defun в CL есть своё поведение, можно сказать что его описание в стандарте - это такой пересказ в прозе на мета-языке свойств целевого языка. И с помощью этих элементов можно строить разные абстрактные ТД и работать с ними.

А теперь возьмём языки следующие ML - оказывается там те же АТД вводятся иначе, и тоже на мета языке (формально, или интуитивно) можно описать поведение соответсвующих выразительных средств.

Т.е. получается - есть разные способы (на мета-уровне) вводить средства введния АТД («средства введени» - мета уровень :))

Инструменты работы с АТД в CL (имею в виду deftype/defstruct/defun/typecase) не формальны. В ML эти инструменты основываются на всяком «матане». Вот и вопрос - какой подход удобнее при написании программ? Я попытался на него ответить. Противоречий тут нет - просто один подход более высокого уровня чем другой, поэтому в каком-то языке нужно обеспечить (в будущем) прокачку абстракций.

Хм, по чём нынче «корабль» хаскеля?

Эээ, ты зачэм меня такие вещи спрашиваешь, а? :)

> Ну вот у deftype/defstruct/defun в CL есть своё поведение, можно

сказать что его описание в стандарте - это такой пересказ в прозе

на мета-языке свойств целевого языка

Это пропустим, ибо что за мета-язык и проза на нём мне не понять.

И с помощью этих элементов можно строить разные абстрактные ТД

и работать с ними.

ADT задаётся спецификацией, которая не зависит от языка. Что значит строить? И при чём здесь «строить»?

Т.е. получается - есть разные способы (на мета-уровне)

вводить средства введния АТД («средства введени» - мета уровень :))

Нет, я знаю только один реальный, взять ручку с бумажной и написать там интерфейс. Можно конечно на граните его выбить. Или на песке веточкой нарисовать. Но что за метоуровень такой?

Инструменты работы с АТД в CL (имею в виду

deftype/defstruct/defun/typecase) не формальны.

Хм, смешлись люди, кони... В смысле, не формальны. Прописаны в стандарте. Только почему ты выделил эти формы как инструменты для работы с ADT?

Противоречий тут нет - просто один подход более высокого уровня

чем другой, поэтому в каком-то языке нужно обеспечить (в будущем)

прокачку абстракций.

Какой? Вообще, ты по какому критерию сравниваешь между собой совершенно разные понятия и определяешь что выше?

Вот и вопрос - какой подход удобнее при написании программ?

Нет, вопрос совсем другой. balodja пожаловался, что Грэхэм для определения ADT использует списки, так что нужно отдельно заводить селекторы, а если про это забыть и залеть в них «грязным» cdr (чему язык не препятствует), то может случиться беда. Если бы Грэхэм использоваться для определения ADT, например, классы, то таких бы проблем не было бы. Вот и весь вопрос. А ты начал утверждать, что в CL никаких ADT нет. И рассказывать про абстрактные типы штанги. К чему мне совершенно не понятно.

Видимо, мета — от метамфетамин.

Это пропустим, ибо что за мета-язык и проза на нём мне не понять.

Мета-язык - язык о языке, под прозой подразумевалось неформальные определения/спецификации и т.д.

ADT задаётся спецификацией, которая не зависит от языка. Что значит строить? И при чём здесь «строить»?

Нет, я знаю только один реальный, взять ручку с бумажной и написать там интерфейс. Можно конечно на граните его выбить. Или на песке веточкой нарисовать. Но что за метоуровень такой?

Ты говоришь о задании АТД. А я говорю о задании способа задания АТД - при дизайне языка. В CL можно использовать классы для задания АТД - набор классов определяет АТД (или интерфейс, по твоему), а вот введение классов в язык это мета-уровень - определение средства которое само что-то определяет.

Речь не идёт о задании самих АТД, а о задании средств определения АТД в разных языках - просто следующий уровень рассмотрения.

Хм, смешлись люди, кони... В смысле, не формальны. Прописаны в стандарте. Только почему ты выделил эти формы как инструменты для работы с ADT?

Ничего не смешалось - с помощью deftype и defstruct мы определяем структурный АТД, возможно РТД. С помощью defun/typecase/case мы определяем функции для работы с ними и спецификацию по типам и значениям. На уровне CLOS - тоже самое defcalss, defmethod (вместе с матчингом по классам и по значениям с помощью eql в аргументе, между прочем не полная система-то - для её расширения делается filtred function в closer-mop). А не формальные потому что «просто так, с потолка» - так сделали потому что так решили. Формально это значит исходя из каких-то принципов - когда эти принципы не позволяют решить как-то иначе. Так оно в языках с алгебраическими типами данных.

Какой? Вообще, ты по какому критерию сравниваешь между собой совершенно разные понятия и определяешь что выше?

С помощью выразительного средства более высокого уровня можно выразить всё то же самое что при помощи средства более низкого уровня (может, ещё что-то - но не обязательно), и при этом - меньшим количеством кода (как можно было сказать - с помощью термов меньшего размера). В рассматриваемом случае менее выразительные средства являются target-языком при трансляции из представления в более выразительном виде.

Нет, вопрос совсем другой. balodja пожаловался, что Грэхэм для определения ADT использует списки, так что нужно отдельно заводить селекторы, а если про это забыть и залеть в них «грязным» cdr (чему язык не препятствует), то может случиться беда. Если бы Грэхэм использоваться для определения ADT, например, классы, то таких бы проблем не было бы. Вот и весь вопрос. А ты начал утверждать, что в CL никаких ADT нет. И рассказывать про абстрактные типы штанги. К чему мне совершенно не понятно.

Правильно, цепочка такова:

списки для ADT -> «эмулирование» (пренебрежительно :) ADT с помощью CLOS -> Нормальные алгебраические типы данных с паттен-матчингом.

Т.е. списки никуда не годятся при сравнее с CLOS (в вопросах определения ADT), ну а CLOS...

«мета» от «метаматематики», как раз сейчас перелистываю TAPL :)