В общем суть такова: почему в качестве основного типа данных используются cons-ячейки? На мой взгляд более правильным было бы использовать массив, в таком случае cons-ячейка это просто массив с двумя значениями, а весь код прекрасно представляется в виде массива, элементами которого в свою очередь могут быть тоже массивы.

Какие я вижу преимущества:
1. -1 тип данных -- cons-ячейка. Проще в реализации, чище в теории.
2. Не нужно вносить иметь отдельный тип данных "массив", когда весь AST представлен в списке.
3. Массив имеет константную сложность для выборки элемента по индексу, таким образом (nth 3 '(0 1 2 3)) будет работать быстрее.
4. Массив занимает меньше места, чем список на cons-ячейках.
5. Массив определенной длины быстрее выделить в памяти, чем список на cons-ячейках.
6. Массив с константным временем доступа на cons-ячейках реализовать сложно/ресурсовемко/невозможно, поэтому в лиспах делают массив отдельным типом встроенным в Лисп-машину, реализовать же cons-ячейку на массивах тривиально.

Жду ваших комментариев почему я "***баёп" и мой Лисп "не нужын". Спасибо!

Ну, хорошо я сделаю подтип типа массив -- "веревочный массив" (по типу "веревочных строк" http://habrahabr.ru/post/144736/), который в любой момент можно будет (flatten! rope-array) -> array.

Цитата

---

1. -1 тип данных -- cons-ячейка. Проще в реализации, чище в теории.

---

Отказ от cons в пользу массивов повлечет за собой увеличение нагрузки на gc. В теории может и просто, а на практике - нехилый оверхед.

Цитата

---

2. Не нужно вносить иметь отдельный тип данных "массив", когда весь AST представлен в списке.

---

AST, состоящее из cons, проще(дешевле) модифицировать.

Цитата

---

5. Массив определенной длины быстрее выделить в памяти, чем список на cons-ячейках.

---

Зависит от реализации gc.

Цитата

---

minobull :
Отлично, убрали одну сущность - cons-ячейки, добавили другую - rope-array.
Профит-то в чем?

---

Хотя бы в том, что rope-array is array, то есть интерфейс будет един. Да и это не единственный пункт профита (см. первый пост).

Цитата

---

misha :
Отказ от cons в пользу массивов повлечет за собой увеличение нагрузки на gc. В теории может и просто, а на практике - нехилый оверхед.

---

"Зависит от реализации gc." (c) misha

Цитата

---

misha :
AST, состоящее из cons, проще(дешевле) модифицировать.

---

Если с операциями вставки и доступа по индексу это не так (как мы выяснили), то в каких случаях это ещё проще/дешевле?

Цитата

---

misha :
Проще реализовать подходящий тип данных, например, VList, и использовать его в своих программах, чем создавать свою реализацию из-за такой фигни.

---

Да, хороший тип, но все эти надстройки в виде rope-array и vlist можно реализовать поверх на самом языке с массивами. На мой взгляд, не очень удачный подход "любой задаче один тип", да и не всегда такой оверхед приемлем.
Массивы не единственное отличие реализации, просто одно из, которое я хотел обсудить.

Цитата

---

misha :
Но это разные типы.

---

Ну в данном случае rope-array это оптимизация, которая может быть, а может и не быть. Надо смотреть по результатам замеров нужна ли она в принципе.

Цитата

---

misha :
Это для rope-array еще как-то можно оптимизировать операции удаления/вставки. Кстати, после многочисленных операций удаления/вставки как время выборки, так и время вставки для rope-array может превысить аналогичный показатель для списка(cons). Т.е. нет ни константной, ни линейной зависимости. Да и добавление возможности создания циклических структур внесет свой оверхед.

---

Вообще говоря, да. Но использование более умных типов типа того же vlist будет усложнять возможности переиспользования данных (то есть -- часть массива A, является так же массивом B). Действительно, не всё так очевидно тут, надо подумать.

Цитата

---

misha :
А разве вы не этого хотите? Лично я не вижу необходимости в избавлении от cons. Пусть пользователь выбирает какой ему тип больше подходит.

---

Нет. Я хочу чтобы в основе системы был минимальный базис/ядро, такой, чтобы не было ограничений на его расширение. Причем важно, чтобы можно было реализовать типы и операции над ними с наилучшей сложностью. Таким образом, т.к. cons-ячейки в принципе реализуемы через массивы (в теории с операциями той же сложности), а обратное неверно, то cons-ячейки получаются лишние в ядре.
А для пользователя я как раз за максимальное количество типов -- должны быть и cons-ячейки, и массивы, и веревочные массивы, и списки, и vlist и пр. Но в качестве стандартной библиотеки.

Подход не правильный с теоретической точки зрения или у вас только к практической части вопросы?

> Нет. Я хочу чтобы в основе системы был минимальный базис/ядро

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

Цитата

---

Kergan :
> Нет. Я хочу чтобы в основе системы был минимальный базис/ядро

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

---

Если с конс-ячейками минимальное ядро, то как на таком ядре реализовать массивы? Я рассматриваю массив просто как отношение "лежит рядом в памяти", конс-ячейка реализует отношение "пара" или "пара лежащая рядом в памяти", здесь массив выражает более общее отношение, а конс-ячейка лишь его проекция для двух элементов.

То, что консы на массивах потребуют больше ресурсов это, конечно, плохо, но не так страшно, если конс перестанет быть типом на все случаи жизни.

Если пытаться решить и проблему с консами, то нужно признать, что и массив в качестве основания тоже подходит слабо. Но в этом случае остаются только совсем уже базовые "машинные" типы: указатель, структура и простые типы. Тогда мой МассивныйЛисп становится уже СишнымЛиспом или ЛисповымСи, в который и сборку мусора-то без танцев с бубном не встроишь, не говоря уже о макросах =).

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

Оффтоп: ещё интересен с данной точки зрения язык Lua, насколько я понимаю в нем единственный тип это таблица (она же массив, она же хеш-таблица), только там код не на S-выражениях и AST не на этих таблицах (не Лисп, в общем).

Цитата

---

Никак, очевидно. Это ядро недостаточно велико, чтобы можно было выразить масивы длины отличной от двух.

---

А почему нельзя?

Цитата

---

То, что массивы на консах потребуют больше ресурсов это, конечно, плохо, но не так страшно, если массив перестанет быть типом на все случаи жизни.

---

В принципе, можно реализовать относительно компактные массивы на gc изначально ориентированном на cons.

Цитата

---

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

---

Речь шла не о cons, а о gc изначально ориентированном на cons.

Цитата

---

это к чему?

---

Зависит от конкретной реализации gc.

Цитата

---

Да, только ценность консов в качестве отдельного типа данных я и пытаюсь поставить под сомнение.

---

Т.е. вы ставите под сомнение целесообразность использования s-выражений?

Цитата

---

На мой взгляд, гораздо чище в концептуальном плане иметь один тип - массив

---

Ну, тогда это будет не Лисп, а диалект АПЛ.

Цитата

---

S-выражения не на консах построены, а на списках, а списки не обязательно должны быть на консах

---

S-выражения построены на связанных списках. Вот, например, список (1 . 2), состоящий из одной cons, и при этом он является полноценным списком.

Цитата

---

более того, во всех языках кроме Лиспа списки не на консах

---

Так там рассматривается массив как список, ведь список - это абстрактный тип данных. Кстати, в Прологе связанные списки.

Цитата

---

Судя по определению "array programming language" это все таки другое. И на мой взгляд это будет все таки Лисп, т.к. представление AST в виде объектов языка в качестве s-expr сохранится.

---

А кто вас заставляет использовать синтаксис АПЛ? Вы можете свободно использовать массивы для представления АСД.

Цитата

---

У меня в голове было неправильное представление о типах CL сформированное на основе PCL, где было явно сказано, что "списков нет, есть cons-ячейки". А на практике получается что cons is list, что несколько меняет смысл.

---

Все эти "ускоренные курсы" рассчитаны на то, что прочитав их вы затем возьметесь за что-нибудь более солидное.

Цитата

---

S-выражение обязано быть proper list'ом?

---

Не обязано Просто этого требует синтаксис Лиспа.

Цитата

---

Мы же не можем (#'(lambda (x) (* x x)) . 10)?

---

"#'(lambda ..." не является синтаксически грамотным вызовом функции. Но мы можем записать, например, так

((lambda (x) (* x x)) . (10))

или так

((lambda . ((x . nil) . ((* x . (x)) . nil))) . (10 . nil))

Цитата

---

Вот, например, список (1 . 2), состоящий из одной cons, и при этом он является полноценным списком.

---

Нет, это не список. Список обязан заканчиваться на nil.

Цитата

---

Kergan :
s-выражение может быть любым readable-объектом лисп-системы. То есть это может быть, например, произвольный текст или запись 9 симфонии Бетховена, которая принимается с микрофона. Или ваще смотрящее в веб-камеру лицо.

---

То есть M-выражение может быть S-выражением?

Цитата

---

Kergan :
Но только он будет тормознее и жрать больше памяти. А так да - никакой разницы не будет.

---

Ладно, я посчитал и согласен.

Цитата

---

misha :
Если вы понимаете как происходит макроэкспанд, то вы должны уже были понять, что подобная замена приведет лишь к дополнительному расходу памяти, и в большинстве случаев замедлит экспанд в несколько раз.

---

Ну скорее да, вы правы.