Предыдущая страница [1] [2] > 3 <

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

Kergan

Members


Статус

300 сообщений

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

#6395   2012-08-04 10:55 GMT+3 часа(ов)      
Цитата
Любой начинающий лиспер должен уметь различать proper-list и improper-list.

проблема в том, что improper list - это никакой не list, а произвольный граф в памяти. какое есть основание называть его list?

misha

Moderators


Статус

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

#6397   2012-08-04 13:12 GMT+3 часа(ов)      
Цитата
(list? `(1 . 2))
SRFI-1
proper-list? x -> boolean
Returns true iff x is a proper list -- a finite, nil-terminated list.

More carefully: The empty list is a proper list. A pair whose cdr is a proper list is also a proper list:

<proper-list> ::= () (Empty proper list)
| (cons <x> <proper-list>) (Proper-list pair)

Note that this definition rules out circular lists. This function is required to detect this case and return false.

Nil-terminated lists are called "proper" lists by R5RS and Common Lisp. The opposite of proper is improper.

R5RS binds this function to the variable list?.
В схеме list? используется только для проверки на proper-list. Т.е. list? - это сокращение для proper-list? (SRFI-1). А в лиспе используется проверка на proper-list и improper-list, т.е. на любой вид списка.

misha

Moderators


Статус

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

#6398   2012-08-04 13:21 GMT+3 часа(ов)      
Цитата
проблема в том, что improper list - это никакой не list, а произвольный граф в памяти. какое есть основание называть его list?
Это не я придумал, так уж исторически сложилось, что существует деление на proper и improper. С другой стороны, что вам мешает использовать dotted-list? Его ведь также легко парсить как и proper-list.

Kergan

Members


Статус

300 сообщений

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

#6399   2012-08-04 13:24 GMT+3 часа(ов)      
Не понял, при чем тут парсинг. Понятно, что так исторически сложилось, но по факту improper list не являются списками. То есть они improper list, но не list.

misha

Moderators


Статус

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

#6401   2012-08-04 13:32 GMT+3 часа(ов)      
Цитата
Понятно, что так исторически сложилось, но по факту improper list не являются списками. То есть они improper list, но не list.
По какому факту?
CLHS
list n.
    1. a chain of conses in which the car of each cons is an element of the list, and the cdr of each cons is either the next link in the chain or a terminating atom. See also proper list, dotted list, or circular list.
    2. the type that is the union of null and cons.

misha

Moderators


Статус

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

#6402   2012-08-04 13:50 GMT+3 часа(ов)      
Цитата
Не понял, при чем тут парсинг.
А в чем проблема с improper-list? Тем более, что в случае dotted-list экономия в одну cons. Или может философия не позволяет?

Kergan

Members


Статус

300 сообщений

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

#6403   2012-08-04 18:17 GMT+3 часа(ов)      
Цитата
По какому факту?

по определению списка как АТД.

Цитата
А в чем проблема с improper-list?

в чем?

misha

Moderators


Статус

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

#6404   2012-08-04 19:59 GMT+3 часа(ов)      
Цитата
по определению списка как АТД.
По какому такому определению? Я же указал ранее, что improper-list полностью соответствует определению (приведенному выше).
Цитата
в чем?
Решили ответить по-еврейски? Ну, так я первый спросил.

Kergan

Members


Статус

300 сообщений

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

#6405   2012-08-04 20:13 GMT+3 часа(ов)      
Цитата
Решили ответить по-еврейски?

ну я не знаю ответа на этот вопрос. Про проблемы с improper list и парснигом видимо кто-то другой говорил.

Цитата
По какому такому определению?

list a = nil + a * a
это не лисповое определение, а вообще общепринятое определение списков. Понятно, конечно, что в рамках динамического ЯП оно смысла не имеет, но proper list по крайней мере соответтсвуют этому определению в некотором смысле. Называть же списком любую пару несколько странно, потому что пара - она и в африке пара: pair a b = a * b.

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

misha

Moderators


Статус

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

#6406   2012-08-04 20:53 GMT+3 часа(ов)      
Цитата
Про проблемы с improper list и парснигом видимо кто-то другой говорил.
Ну, так у вас есть проблемы с парснигом или нет? Или это секрет?
Цитата
это не лисповое определение, а вообще общепринятое определение списков.
Вне лиспа под nil обычно подразумевают null, что несколько меняет дело.
В общем-то любой лиспер знает, что proper-list завершается атомом nil, dotted-list - любым атомом, а circular-list - ссылкой на начало.
Цитата
Не стоит этой сущности давать еще и третье название (список)
Сами названия proper и improper уже говорят за себя. proper - истинный (общепринятый). А improper - ложный (мнимый).
И так так эти понятия являются общепринятыми среди лисперов, то не стоит пререкаться и искать альтернативы.

Kergan

Members


Статус

300 сообщений

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

#6408   2012-08-05 09:44 GMT+3 часа(ов)      
Цитата
Ну, так у вас есть проблемы с парснигом или нет? Или это секрет?


я же говорю - у меня нету никаких проблем с парсингом. Ни списков, ни массивов, ни хешей - ничего

Цитата
И так так эти понятия являются общепринятыми среди лисперов

и противоречат общепринятым _в принципе_

misha

Moderators


Статус

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

#6409   2012-08-05 12:15 GMT+3 часа(ов)      
Цитата
я же говорю - у меня нету никаких проблем с парсингом.
А так и должно быть, ведь парсить improper-list, как я уже сказал ранее, довольно просто.
Цитата
и противоречат общепринятым _в принципе_
Я подозреваю, что текущие "общепринятые" закрепились гораздо позже, нежели те сформировались в среде лисперов.

Kergan

Members


Статус

300 сообщений

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

#6416   2012-08-09 00:38 GMT+3 часа(ов)      
Цитата
А так и должно быть, ведь парсить improper-list, как я уже сказал ранее, довольно просто.

вроде никто и не спорил

Цитата
Я подозреваю, что текущие "общепринятые" закрепились гораздо позже, нежели те сформировались в среде лисперов.

ну так были еще более ранние общепринятые, если уж на то пошло. и там любой граф точно не был списком

misha

Moderators


Статус

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

#6424   2012-08-09 21:50 GMT+3 часа(ов)      
Цитата
вроде никто и не спорил
Ну, мне так не показалось
Цитата
ну так были еще более ранние общепринятые, если уж на то пошло. и там любой граф точно не был списком
Хотя данный вопрос довольно часто подымется на англоязычных форумах, но тем не менее лисперы как использовали improper-list, так их и используют. Наверное, в них есть что-то привлекательное

gihar

Moderators


Статус

249 сообщений

Где: --- да вот он я? приехал уже из Катманду
Род занятий: конкретный
Возраст: 0

#6454   2012-08-11 18:20 GMT+3 часа(ов)      
Цитата
metadeus :
В общем суть такова: почему в качестве основного типа данных используются cons-ячейки? На мой взгляд более правильным было бы использовать массив, в таком случае cons-ячейка это просто массив с двумя значениями, а весь код прекрасно представляется в виде массива, элементами которого в свою очередь могут быть тоже массивы.

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

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




Так как тема зашла в тупік, поэтому снова вніманіе на проблему топікстартера.

Конечно, никакого другого Лиспа Вы топикстартер не придумали, потому как факторы скорости и размера занимаемой памяти идеологию лиспа не волнуют по-умолчанию.

Собственно, Ваш вопрос это отраженіе прямого кріка Вашей пытливой душі: "Народ я так і не понял нафіга нужны cons-ячейки?

І вправду, нафіга нужны эты консы?

Проблемка то глобальная! Философская!

В каком типе кодерского действия раскрывается сакрыльный смысл конса?

)
Это было точно последнее редактирование

metadeus

Members


Статус

89 сообщений

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

#6458   2012-08-14 21:39 GMT+3 часа(ов)      
Цитата
gihar :
Так как тема зашла в тупік, поэтому снова вніманіе на проблему топікстартера.

Конечно, никакого другого Лиспа Вы топикстартер не придумали, потому как факторы скорости и размера занимаемой памяти идеологию лиспа не волнуют по-умолчанию.



Придумал. Так же как Scheme и CL это разные Лиспы, так и реализация этого диалекта была бы новым Лиспом.

Цитата
gihar :
Собственно, Ваш вопрос это отраженіе прямого кріка Вашей пытливой душі: "Народ я так і не понял нафіга нужны cons-ячейки?

І вправду, нафіга нужны эты консы?

Проблемка то глобальная! Философская!

В каком типе кодерского действия раскрывается сакрыльный смысл конса?

)



В этом топике ясно было сформулировано зачем нужны именно cons-ячейки и с тем, что они по праву занимают свое место я так же явно согласился.

Kergan

Members


Статус

300 сообщений

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

#6460   2012-08-14 22:54 GMT+3 часа(ов)      
Цитата
Так же как Scheme и CL это разные Лиспы, так и реализация этого диалекта была бы новым Лиспом.


Да нет, вы придумали не новый лисп, а новую реализацию лиспа. То есть то что вы описали - может быть тем же CL или Scheme.

metadeus

Members


Статус

89 сообщений

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

#6474   2012-08-20 19:18 GMT+3 часа(ов)      
Цитата
Kergan :
Да нет, вы придумали не новый лисп, а новую реализацию лиспа. То есть то что вы описали - может быть тем же CL или Scheme.



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

Kergan

Members


Статус

300 сообщений

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

#6475   2012-08-20 20:56 GMT+3 часа(ов)      
Цитата
Только программы написанные на CL не будут на нем исполняться и он не будет соответствовать стандарту

с чего вдруг? и стандарту будет соответствовать и программы будут исполняться. Стандарт CL не регламентирует конкретное представление cons-ячеек.

metadeus

Members


Статус

89 сообщений

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

#6476   2012-08-20 21:27 GMT+3 часа(ов)      
Цитата
Kergan :
с чего вдруг? и стандарту будет соответствовать и программы будут исполняться. Стандарт CL не регламентирует конкретное представление cons-ячеек.



Да, действительно будет соответствовать стандарту.

gihar

Moderators


Статус

249 сообщений

Где: --- да вот он я? приехал уже из Катманду
Род занятий: конкретный
Возраст: 0

#6477   2012-08-22 03:23 GMT+3 часа(ов)      
metadeus
Цитата
В этом топике ясно было сформулировано зачем нужны именно cons-ячейки и с тем, что они по праву занимают свое место я так же явно согласился.


мне трудно найті где тот посто где было сказано о сушності іспользованія этой вещи. Вот вы, например, в каких местах программы используете ілі відіте целесообразным іспользовать эти консы?
Это было точно последнее редактирование

gihar

Moderators


Статус

249 сообщений

Где: --- да вот он я? приехал уже из Катманду
Род занятий: конкретный
Возраст: 0

#6482   2012-08-23 15:41 GMT+3 часа(ов)      
чтобы знать зачем консы нужно погрузіться в атмосферу программірованія 70-80, нужно вспомніть как относілся к орграфам Дейкстра. Фантастіческіе ідеі по развітію іскусственного інтеллекта. Консы это программное отраженіе ідеі орграфа, где сушность имеет "имя + вес", это может быть даже "имя + фамилия" или "маршрут + цена" билета, а если обобщить полностью то "значеніе + тэг". Тэг-Алгоритмы, основанные на консах, не могут быть быстрыми для выполнения тривиальных задач. С другой стороны Дейкстре повезло со своим алгоритмом поиска кратчайшего пути, иначе не было бы ни одного доказательства в пользу ПАРЫ. Но одного этого алогоритма хватает чтобы вынести мозг. Идея CONS-алгоритма на манипуляции тегами, когда меняя один всего лишь тэг тот что CDR, не меняя функціональной базы (функцій і процедур) заставлять программу пріспосабліваться к новым условіям какбы іммітіруя мышленіе человека.

Еслі із Ліспа убрать КОНСЫ, то на выходе получім - обычное скучное Г. Это тоже самое, что із псіхікі человека убрать веру в сказку бесконечності міров вселенной, получім на выходе - особый сорт людей (ОСЛ).

Так мыслі вслух:
О скорості выполненія программ: простая аналогія: Одін пользуется скоростным автомобілем чтобы добраться за 2 часа до работы, а второй жівет рядом с местом работы і тратіт 5 мінут без авто. Как і в жізні в программинге, все решает правільная структурізація. ), і не оптімізація как некоторые могут подумать. Оптімізація это насіліе над собой ілі над программой в целях сократіть іздержкі времені і денег, вытекает в итоге в созданіе жесткого режіма ілі программной сістемы, где случайноге паденіе одного элемента вызывает лавинообразное паденіе других - "эффект доміно".
Эффект Структурізаціі это своего рода мудрость, качественный взгляд на предмет.

Очевидно, что Лисп предлагает способ структуризироваться - "Хитрыми Консами".
Однако, король промышленного программірованія - "Ассоціатівный он же Хэш Массів".
Это было точно последнее редактирование

metadeus

Members


Статус

89 сообщений

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

#6484   2012-08-27 17:11 GMT+3 часа(ов)      
Цитата
gihar :
мне трудно найті где тот посто где было сказано о сушності іспользованія этой вещи. Вот вы, например, в каких местах программы используете ілі відіте целесообразным іспользовать эти консы?



Вы имеете ввиду помимо AST'а?
Мне кроме как простых двоичных деревьев для доступа за log2(N) в голову больше ничего не приходит. Но их хорошее соответствие под задачу хранения и манипуляции AST'ом делает их хорошим выбором для того, чтобы стать частью языка Lisp.
Я, к слову, вообще не считаю, что у типа данных обязательно должно быть множество применений, лучше пусть тип данных будет заточен под одну задачу, но будет делать её хорошо. Например целое число можно использовать для хранения флагов в его битах как делают сишники, но зачастую код превращается в месиво и нагромождение битовых операций, я бы предпочел bit-array и большой перечень методов для работы с ним. Или, например, тип символ: его можно использовать как по прямому назначению, так и для организации хештаблицы по caseinsensitive строкам, но специализированный тип просто даст больше возможностей для поиска, фильтрации и т.п.
Короче каждой задаче свой тип данных. То, что эти типы будут основаны или построены на других более общих типах: массива, пары, целых чисел и т.п., то это просто требование реальности по переносимости систем между вычислителями. Взять любую низкоуровневую ВМ: у неё есть вполне определенный набор типов и некоторые возможности по их расширению (далеко не всегда), если стоит задача исполнять свой код на этой ВМ, то свои абстрактные типы должны каким то образом маппиться на типы ВМ, это и есть задача программиста.
Я бы, к примеру, задачу определения AST реализовал через вложенные массивы, но cons'ы судя по всему просто лучше подходят для этой задачи, а так как бенчмарков нет, то приходится полагаться на теоретические заключения.

snv

Members


Статус

25 сообщений
http://sym.at.ua/load
Где: Russia Серпухов
Род занятий: Безработный
Возраст: 32

#7041   2013-05-30 23:14 GMT+3 часа(ов)      
Цитата
metadeus :
почему в качестве основного типа данных используются cons-ячейки?

1. CONS-ячейки проще реализовать.
2. Они проще теоретически: разделяй и властвуй.

Цитата
На мой взгляд более правильным было бы использовать массив

Массив не поддерживает O(1) добавление и взятие хвоста.
Удобней уж закладочные catenable double ended queues с path-copying и закладками на концах (aka finger trees). Они дают O(log N) доступ/катенцию и O(1) доступ к концам.

Но cons-ячейки концептуально проще. Более того, списки должны присутствовать ещё на этапе bootstrap-а, когда неготовы сборщик мусора и компилятор. Т.е. разрвботчику компилятора приходится их ручками вводить. А Finger Trees и даже простые массивы - сложные структуры, требующие тонну бухгалтерии (для массива требуется тип элементов, размер и указатель).

Цитата

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

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


У вас premature-optimization. Большинcтво cons-списков и так исчезает после компиляции. А скорость исполнения макросов была приемлемой даже на железе 60х годов.
The hour will come in which all the peoples of the earth will awake, and the Jews will be the victims. -- Joseph Goebbels, 21 January 1945


Онлайн :

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




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