Автор | Сообщение |
Kergan
300 сообщений |
#6395 2012-08-04 10:55 GMT+3 часа(ов) |
Цитата проблема в том, что improper list - это никакой не list, а произвольный граф в памяти. какое есть основание называть его list? |
|
misha![]()
1275 сообщений |
#6397 2012-08-04 13:12 GMT+3 часа(ов) |
Цитата SRFI-1В схеме list? используется только для проверки на proper-list. Т.е. list? - это сокращение для proper-list? (SRFI-1). А в лиспе используется проверка на proper-list и improper-list, т.е. на любой вид списка. |
|
misha![]()
1275 сообщений |
#6398 2012-08-04 13:21 GMT+3 часа(ов) |
ЦитатаЭто не я придумал, так уж исторически сложилось, что существует деление на proper и improper. С другой стороны, что вам мешает использовать dotted-list? Его ведь также легко парсить как и proper-list. |
|
Kergan
300 сообщений |
#6399 2012-08-04 13:24 GMT+3 часа(ов) |
Не понял, при чем тут парсинг. Понятно, что так исторически сложилось, но по факту improper list не являются списками. То есть они improper list, но не list.
|
|
misha![]()
1275 сообщений |
#6401 2012-08-04 13:32 GMT+3 часа(ов) |
ЦитатаПо какому факту? CLHS |
|
misha![]()
1275 сообщений |
#6402 2012-08-04 13:50 GMT+3 часа(ов) |
ЦитатаА в чем проблема с improper-list? Тем более, что в случае dotted-list экономия в одну cons. Или может философия не позволяет? |
|
Kergan
300 сообщений |
#6403 2012-08-04 18:17 GMT+3 часа(ов) |
Цитата по определению списка как АТД. Цитата в чем? |
|
misha![]()
1275 сообщений |
#6404 2012-08-04 19:59 GMT+3 часа(ов) |
ЦитатаПо какому такому определению? Я же указал ранее, что improper-list полностью соответствует определению (приведенному выше). ЦитатаРешили ответить по-еврейски? Ну, так я первый спросил. |
|
Kergan
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![]()
1275 сообщений |
#6406 2012-08-04 20:53 GMT+3 часа(ов) |
ЦитатаНу, так у вас есть проблемы с парснигом или нет? Или это секрет? ![]() ЦитатаВне лиспа под nil обычно подразумевают null, что несколько меняет дело. В общем-то любой лиспер знает, что proper-list завершается атомом nil, dotted-list - любым атомом, а circular-list - ссылкой на начало. ЦитатаСами названия proper и improper уже говорят за себя. proper - истинный (общепринятый). А improper - ложный (мнимый). И так так эти понятия являются общепринятыми среди лисперов, то не стоит пререкаться и искать альтернативы. |
|
Kergan
300 сообщений |
#6408 2012-08-05 09:44 GMT+3 часа(ов) |
Цитата я же говорю - у меня нету никаких проблем с парсингом. Ни списков, ни массивов, ни хешей - ничего ![]() Цитата и противоречат общепринятым _в принципе_ |
|
misha![]()
1275 сообщений |
#6409 2012-08-05 12:15 GMT+3 часа(ов) |
ЦитатаА так и должно быть, ведь парсить improper-list, как я уже сказал ранее, довольно просто. ЦитатаЯ подозреваю, что текущие "общепринятые" закрепились гораздо позже, нежели те сформировались в среде лисперов. |
|
Kergan
300 сообщений |
#6416 2012-08-09 00:38 GMT+3 часа(ов) |
Цитата вроде никто и не спорил Цитата ну так были еще более ранние общепринятые, если уж на то пошло. и там любой граф точно не был списком ![]() |
|
misha![]()
1275 сообщений |
#6424 2012-08-09 21:50 GMT+3 часа(ов) |
ЦитатаНу, мне так не показалось ![]() ЦитатаХотя данный вопрос довольно часто подымется на англоязычных форумах, но тем не менее лисперы как использовали improper-list, так их и используют. Наверное, в них есть что-то привлекательное ![]() |
|
gihar
249 сообщений |
#6454 2012-08-11 18:20 GMT+3 часа(ов) |
Цитата Так как тема зашла в тупік, поэтому снова вніманіе на проблему топікстартера. Конечно, никакого другого Лиспа Вы топикстартер не придумали, потому как факторы скорости и размера занимаемой памяти идеологию лиспа не волнуют по-умолчанию. Собственно, Ваш вопрос это отраженіе прямого кріка Вашей пытливой душі: "Народ я так і не понял нафіга нужны cons-ячейки? І вправду, нафіга нужны эты консы? Проблемка то глобальная! Философская! В каком типе кодерского действия раскрывается сакрыльный смысл конса? ![]() |
|
Это было точно последнее редактирование
|
|
metadeus
89 сообщений |
#6458 2012-08-14 21:39 GMT+3 часа(ов) |
Цитата Придумал. Так же как Scheme и CL это разные Лиспы, так и реализация этого диалекта была бы новым Лиспом. Цитата В этом топике ясно было сформулировано зачем нужны именно cons-ячейки и с тем, что они по праву занимают свое место я так же явно согласился. |
|
Kergan
300 сообщений |
#6460 2012-08-14 22:54 GMT+3 часа(ов) |
Цитата Да нет, вы придумали не новый лисп, а новую реализацию лиспа. То есть то что вы описали - может быть тем же CL или Scheme. |
|
metadeus
89 сообщений |
#6474 2012-08-20 19:18 GMT+3 часа(ов) |
Цитата Только программы написанные на CL не будут на нем исполняться и он не будет соответствовать стандарту, а так да -- тот же CL. |
|
Kergan
300 сообщений |
#6475 2012-08-20 20:56 GMT+3 часа(ов) |
Цитата с чего вдруг? и стандарту будет соответствовать и программы будут исполняться. Стандарт CL не регламентирует конкретное представление cons-ячеек. |
|
metadeus
89 сообщений |
#6476 2012-08-20 21:27 GMT+3 часа(ов) |
Цитата Да, действительно будет соответствовать стандарту. |
|
gihar
249 сообщений |
#6477 2012-08-22 03:23 GMT+3 часа(ов) |
metadeus
Цитата мне трудно найті где тот посто где было сказано о сушності іспользованія этой вещи. Вот вы, например, в каких местах программы используете ілі відіте целесообразным іспользовать эти консы? |
|
Это было точно последнее редактирование
|
|
gihar
249 сообщений |
#6482 2012-08-23 15:41 GMT+3 часа(ов) |
чтобы знать зачем консы нужно погрузіться в атмосферу программірованія 70-80, нужно вспомніть как относілся к орграфам Дейкстра. Фантастіческіе ідеі по развітію іскусственного інтеллекта. Консы это программное отраженіе ідеі орграфа, где сушность имеет "имя + вес", это может быть даже "имя + фамилия" или "маршрут + цена" билета, а если обобщить полностью то "значеніе + тэг". Тэг-Алгоритмы, основанные на консах, не могут быть быстрыми для выполнения тривиальных задач. С другой стороны Дейкстре повезло со своим алгоритмом поиска кратчайшего пути, иначе не было бы ни одного доказательства в пользу ПАРЫ. Но одного этого алогоритма хватает чтобы вынести мозг. Идея CONS-алгоритма на манипуляции тегами, когда меняя один всего лишь тэг тот что CDR, не меняя функціональной базы (функцій і процедур) заставлять программу пріспосабліваться к новым условіям какбы іммітіруя мышленіе человека.
Еслі із Ліспа убрать КОНСЫ, то на выходе получім - обычное скучное Г. Это тоже самое, что із псіхікі человека убрать веру в сказку бесконечності міров вселенной, получім на выходе - особый сорт людей (ОСЛ). Так мыслі вслух: О скорості выполненія программ: простая аналогія: Одін пользуется скоростным автомобілем чтобы добраться за 2 часа до работы, а второй жівет рядом с местом работы і тратіт 5 мінут без авто. Как і в жізні в программинге, все решает правільная структурізація. ![]() Эффект Структурізаціі это своего рода мудрость, качественный взгляд на предмет. Очевидно, что Лисп предлагает способ структуризироваться - "Хитрыми Консами". Однако, король промышленного программірованія - "Ассоціатівный он же Хэш Массів". |
|
Это было точно последнее редактирование
|
|
metadeus
89 сообщений |
#6484 2012-08-27 17:11 GMT+3 часа(ов) |
Цитата Вы имеете ввиду помимо AST'а? Мне кроме как простых двоичных деревьев для доступа за log2(N) в голову больше ничего не приходит. Но их хорошее соответствие под задачу хранения и манипуляции AST'ом делает их хорошим выбором для того, чтобы стать частью языка Lisp. Я, к слову, вообще не считаю, что у типа данных обязательно должно быть множество применений, лучше пусть тип данных будет заточен под одну задачу, но будет делать её хорошо. Например целое число можно использовать для хранения флагов в его битах как делают сишники, но зачастую код превращается в месиво и нагромождение битовых операций, я бы предпочел bit-array и большой перечень методов для работы с ним. Или, например, тип символ: его можно использовать как по прямому назначению, так и для организации хештаблицы по caseinsensitive строкам, но специализированный тип просто даст больше возможностей для поиска, фильтрации и т.п. Короче каждой задаче свой тип данных. То, что эти типы будут основаны или построены на других более общих типах: массива, пары, целых чисел и т.п., то это просто требование реальности по переносимости систем между вычислителями. Взять любую низкоуровневую ВМ: у неё есть вполне определенный набор типов и некоторые возможности по их расширению (далеко не всегда), если стоит задача исполнять свой код на этой ВМ, то свои абстрактные типы должны каким то образом маппиться на типы ВМ, это и есть задача программиста. Я бы, к примеру, задачу определения AST реализовал через вложенные массивы, но cons'ы судя по всему просто лучше подходят для этой задачи, а так как бенчмарков нет, то приходится полагаться на теоретические заключения. |
|
snv
25 сообщений |
#7041 2013-05-30 23:14 GMT+3 часа(ов) |
Цитата 1. CONS-ячейки проще реализовать. 2. Они проще теоретически: разделяй и властвуй. Цитата Массив не поддерживает O(1) добавление и взятие хвоста. Удобней уж закладочные catenable double ended queues с path-copying и закладками на концах (aka finger trees). Они дают O(log N) доступ/катенцию и O(1) доступ к концам. Но cons-ячейки концептуально проще. Более того, списки должны присутствовать ещё на этапе bootstrap-а, когда неготовы сборщик мусора и компилятор. Т.е. разрвботчику компилятора приходится их ручками вводить. А Finger Trees и даже простые массивы - сложные структуры, требующие тонну бухгалтерии (для массива требуется тип элементов, размер и указатель). Цитата У вас 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
|