Следующая страница > 1 < [2] [3]

Автор Сообщение

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6239   2012-06-29 21:31 GMT+3 часа(ов)      
В общем суть такова: почему в качестве основного типа данных используются cons-ячейки? На мой взгляд более правильным было бы использовать массив, в таком случае cons-ячейка это просто массив с двумя значениями, а весь код прекрасно представляется в виде массива, элементами которого в свою очередь могут быть тоже массивы.

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

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

minobull

Members


Статус

8 сообщений

Где: Russia
Род занятий:
Возраст:

#6240   2012-06-30 00:15 GMT+3 часа(ов)      
Теперь подумай над кодогенерацией и раскрытием макросов. Проще вставить в указанную часть списка подсписок или создать новый массив?

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

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

minobull

Members


Статус

8 сообщений

Где: Russia
Род занятий:
Возраст:

#6242   2012-07-02 02:59 GMT+3 часа(ов)      
Отлично, убрали одну сущность - cons-ячейки, добавили другую - rope-array.
Профит-то в чем?

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6243   2012-07-02 04:47 GMT+3 часа(ов)      
Цитата
1. -1 тип данных -- cons-ячейка. Проще в реализации, чище в теории.
Отказ от cons в пользу массивов повлечет за собой увеличение нагрузки на gc. В теории может и просто, а на практике - нехилый оверхед.
Цитата
2. Не нужно вносить иметь отдельный тип данных "массив", когда весь AST представлен в списке.
AST, состоящее из cons, проще(дешевле) модифицировать.
Цитата
5. Массив определенной длины быстрее выделить в памяти, чем список на cons-ячейках.
Зависит от реализации gc.

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6244   2012-07-02 05:09 GMT+3 часа(ов)      
Цитата
metadeus :
Ну, хорошо я сделаю подтип типа массив -- "веревочный массив" (по типу "веревочных строк" http://habrahabr.ru/post/144736/), который в любой момент можно будет (flatten! rope-array) -> array.

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

отредактировал(а) misha: 2012-07-02 05:16 GMT+3 часа(ов)

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6247   2012-07-04 15:37 GMT+3 часа(ов)      
Цитата
minobull :
Отлично, убрали одну сущность - cons-ячейки, добавили другую - rope-array.
Профит-то в чем?


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

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


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

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


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

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


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

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6248   2012-07-04 20:52 GMT+3 часа(ов)      
Цитата
Хотя бы в том, что rope-array is array, то есть интерфейс будет един.
Но это разные типы.
Цитата
Если с операциями вставки и доступа по индексу это не так (как мы выяснили), то в каких случаях это ещё проще/дешевле?
Это для rope-array еще как-то можно оптимизировать операции удаления/вставки. Кстати, после многочисленных операций удаления/вставки как время выборки, так и время вставки для rope-array может превысить аналогичный показатель для списка(cons). Т.е. нет ни константной, ни линейной зависимости. Да и добавление возможности создания циклических структур внесет свой оверхед.
Цитата
На мой взгляд, не очень удачный подход "любой задаче один тип", да и не всегда такой оверхед приемлем.
А разве вы не этого хотите? Лично я не вижу необходимости в избавлении от cons. Пусть пользователь выбирает какой ему тип больше подходит.

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6249   2012-07-04 21:44 GMT+3 часа(ов)      
Цитата
misha :
Но это разные типы.



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

Цитата

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


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

Цитата

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


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

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

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6250   2012-07-05 03:39 GMT+3 часа(ов)      
Цитата
Ну в данном случае rope-array это оптимизация, которая может быть, а может и не быть. Надо смотреть по результатам замеров нужна ли она в принципе.
С практической точки зрения, rope-array лучше реализовать как отдельный тип данных. Пусть пользователь сам выбирает, что ему лучше использовать.
Цитата
Но использование более умных типов типа того же vlist будет усложнять возможности переиспользования данных (то есть -- часть массива A, является так же массивом B). Действительно, не всё так очевидно тут, надо подумать.
Еще не стоит забывать про то, что неиспользуемые части(куски) массивов(векторов) будут приводить к скрытой фрагментации памяти.
Цитата
Я хочу чтобы в основе системы был минимальный базис/ядро, такой, чтобы не было ограничений на его расширение. Причем важно, чтобы можно было реализовать типы и операции над ними с наилучшей сложностью.
Так уж завелось, что cons является базовым типом для любой лисп системы. И на практике он используется довольно часто, например, для создания сложных структур данных, разрешения коллизий при хешировании. Поэтому желательно оптимизировать процесс создания cons (и сборки мусора).
Цитата
Таким образом, т.к. cons-ячейки в принципе реализуемы через массивы (в теории с операциями той же сложности), а обратное неверно, то cons-ячейки получаются лишние в ядре.
Вообще-то в этом случае вам придется реализовывать через структуры. Вам также придется учитывать, что наличие огромного количества неиспользуемых малых фрагментов(мусор) может вызвать нехилую фрагментацию памяти. В итоге вам необходимо будет реализовывать сжимающий(или копирующий) сборщик мусора.

отредактировал(а) misha: 2012-07-05 03:46 GMT+3 часа(ов)

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#6251   2012-07-05 11:47 GMT+3 часа(ов)      
> Нет. Я хочу чтобы в основе системы был минимальный базис/ядро

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

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#6252   2012-07-05 11:50 GMT+3 часа(ов)      
> В итоге вам необходимо будет реализовывать сжимающий(или копирующий) сборщик мусора.

Перемещающий сборщик мусора в любом случае необходимо использовать, т.к. только с таким сборщиком память может быть выделена эффективно (за несколько инструкций процессора). К слову, есть вариант простого и эффективного перемещающего сборщика с константным потреблением памяти (требуется несколько десятков байт на весь процесс сборки) и отсутствием дополнительных полей для маркировки при условии unidirectional heap.

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6253   2012-07-05 14:11 GMT+3 часа(ов)      
Цитата
Kergan :
> Нет. Я хочу чтобы в основе системы был минимальный базис/ядро

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



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

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

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

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

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

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#6254   2012-07-07 11:17 GMT+3 часа(ов)      
Цитата
Если с конс-ячейками минимальное ядро, то как на таком ядре реализовать массивы?

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

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

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

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

По-этому во всех нормальных диалектах есть и массивы и консы, очевидно.

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6255   2012-07-08 01:45 GMT+3 часа(ов)      
Цитата
Никак, очевидно. Это ядро недостаточно велико, чтобы можно было выразить масивы длины отличной от двух.
А почему нельзя?
Цитата
То, что массивы на консах потребуют больше ресурсов это, конечно, плохо, но не так страшно, если массив перестанет быть типом на все случаи жизни.
В принципе, можно реализовать относительно компактные массивы на gc изначально ориентированном на cons.

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#6256   2012-07-08 14:09 GMT+3 часа(ов)      
Цитата
А почему нельзя?

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

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

это к чему?

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6257   2012-07-08 14:50 GMT+3 часа(ов)      
Цитата
Ятп под массивом подразумевалась структура данных с константным временем доступа. через консы, понятное дело, не реализуешь.
Речь шла не о cons, а о gc изначально ориентированном на cons.
Цитата
это к чему?
Зависит от конкретной реализации gc.

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6259   2012-07-08 22:32 GMT+3 часа(ов)      
Цитата
Kergan :
То, что массивы на консах потребуют больше ресурсов это, конечно, плохо, но не так страшно, если массив перестанет быть типом на все случаи жизни.


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

Цитата
Kergan :
По-этому во всех нормальных диалектах есть и массивы и консы, очевидно.


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

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6261   2012-07-09 02:45 GMT+3 часа(ов)      
Цитата
Да, только ценность консов в качестве отдельного типа данных я и пытаюсь поставить под сомнение.
Т.е. вы ставите под сомнение целесообразность использования s-выражений?
Цитата
На мой взгляд, гораздо чище в концептуальном плане иметь один тип - массив
Ну, тогда это будет не Лисп, а диалект АПЛ.

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6262   2012-07-09 15:07 GMT+3 часа(ов)      
Цитата
misha :
Цитата
Да, только ценность консов в качестве отдельного типа данных я и пытаюсь поставить под сомнение.
Т.е. вы ставите под сомнение целесообразность использования s-выражений?



Нет, конечно. S-выражения не на консах построены, а на списках, а списки не обязательно должны быть на консах (более того, во всех языках кроме Лиспа списки не на консах).

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


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

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6263   2012-07-09 16:48 GMT+3 часа(ов)      
Цитата
S-выражения не на консах построены, а на списках, а списки не обязательно должны быть на консах
S-выражения построены на связанных списках. Вот, например, список (1 . 2), состоящий из одной cons, и при этом он является полноценным списком.
Цитата
более того, во всех языках кроме Лиспа списки не на консах
Так там рассматривается массив как список, ведь список - это абстрактный тип данных. Кстати, в Прологе связанные списки.
Цитата
Судя по определению "array programming language" это все таки другое. И на мой взгляд это будет все таки Лисп, т.к. представление AST в виде объектов языка в качестве s-expr сохранится.
А кто вас заставляет использовать синтаксис АПЛ? Вы можете свободно использовать массивы для представления АСД.

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6266   2012-07-10 16:17 GMT+3 часа(ов)      
Цитата
misha :
S-выражения построены на связанных списках. Вот, например, список (1 . 2), состоящий из одной cons, и при этом он является полноценным списком.


Оп-па, а ведь действительно. У меня в голове было неправильное представление о типах CL сформированное на основе PCL, где было явно сказано, что "списков нет, есть cons-ячейки". А на практике получается что cons is list, что несколько меняет смысл. Но деление тогда идет proper/improper list:
(1 . 2) is list (improper list)
(1 . (2 . nil)) is list (proper list)
S-выражение обязано быть proper list'ом? Мы же не можем (#'(lambda (x) (* x x)) . 10)?

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

Ну значит s-expr в виде списков на массивах или на связанных списках или vlist вполне себе возможны.

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

Я про синтаксис и не говорю ничего, я лишь о том, что "array programming language" это: "In computer science, array programming languages (also known as vector or multidimensional languages) generalize operations on scalars to apply transparently to vectors, matrices, and higher dimensional arrays." по Педивикии, а я ничего подобного не замышлял. То есть я считаю если заменить основу list с cons на array, а представление AST как было на основе list, так и оставить, то получится Лисп, т.к. семантика останется нетронутой.

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6267   2012-07-10 17:47 GMT+3 часа(ов)      
Цитата
У меня в голове было неправильное представление о типах 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))

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6268   2012-07-10 18:04 GMT+3 часа(ов)      
Цитата
я ничего подобного не замышлял
Тогда я не вижу никакой существенной выгоды от замены.
Цитата
То есть я считаю если заменить основу list с cons на array, а представление AST как было на основе list, так и оставить, то получится Лисп, т.к. семантика останется нетронутой.
Если вы понимаете как происходит макроэкспанд, то вы должны уже были понять, что подобная замена приведет лишь к дополнительному расходу памяти, и в большинстве случаев замедлит экспанд в несколько раз.

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#6273   2012-07-13 03:05 GMT+3 часа(ов)      
Цитата
Вот, например, список (1 . 2), состоящий из одной cons, и при этом он является полноценным списком.

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

Kergan

Members


Статус

300 сообщений

Где: ---
Род занятий:
Возраст:

#6274   2012-07-13 03:07 GMT+3 часа(ов)      
Цитата
S-выражение обязано быть proper list'ом?

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

Цитата
То есть я считаю если заменить основу list с cons на array, а представление AST как было на основе list, так и оставить, то получится Лисп, т.к. семантика останется нетронутой.

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

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6275   2012-07-13 14:54 GMT+3 часа(ов)      
Цитата
Kergan :
s-выражение может быть любым readable-объектом лисп-системы. То есть это может быть, например, произвольный текст или запись 9 симфонии Бетховена, которая принимается с микрофона. Или ваще смотрящее в веб-камеру лицо.

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

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

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

отредактировал(а) metadeus: 2012-07-13 16:37 GMT+3 часа(ов)

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6276   2012-07-13 14:55 GMT+3 часа(ов)      
Цитата
Kergan :
Цитата
Вот, например, список (1 . 2), состоящий из одной cons, и при этом он является полноценным списком.

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


Это противоречит тому, что cons это наследник list.

metadeus

Members


Статус

89 сообщений

Где: Russia
Род занятий:
Возраст:

#6277   2012-07-13 16:36 GMT+3 часа(ов)      
Цитата
misha :
Если вы понимаете как происходит макроэкспанд, то вы должны уже были понять, что подобная замена приведет лишь к дополнительному расходу памяти, и в большинстве случаев замедлит экспанд в несколько раз.

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

misha

Moderators


Статус

1273 сообщений
http://racket-lang.org/
Где: Yemen
Род занятий:
Возраст:

#6283   2012-07-16 02:32 GMT+3 часа(ов)      
Цитата
Kergan :
Цитата
Вот, например, список (1 . 2), состоящий из одной cons, и при этом он является полноценным списком.

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

Список - это абстрактный тип данных. В Лиспе список это nil (empty proper list), либо cons. Условно связанные списки можно разделить на proper, dotted, и circular.


Онлайн :

0 пользователь(ей), 11 гость(ей) :




Реклама на сайте: