LINUX.ORG.RU

Сравнение списков в разных лиспах

 


0

1

Здравствуйте.

Небольшая непонятка. Насколько я понял, при сравнении списков в picolisp и newlisp сравниваются непосредственно сами списки, а не символы, указывающие на них. Это показалось мне странным, особенно в контексте производительности, учитывая, что (особенно) picolisp рвет на списочных структурах все лиспы как тузик грелку. Пруф.

picolisp:


(set 'a (1 2 3))
(set 'b (1 2 3))
(print (= a b)) # T

В newlisp то же самое.

scheme:


(define a '(1 2 3))
(define b '(1 2 3))
(write (eq? a b)) ; #f
(write (equal? a b)); #t

Разве сравнение по «указателям» не должно быть быстрей? Ведь при сравнении списков приходится каждый раз их обходить, или это не так?


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

это как?

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

и всё это ради ускорения сравнительно редкого сравнеия списков

stevejobs ★★★★☆ ()

или ты предлагаешь как в Си ввести constant declaration, и при первоначальной конпеляции скидывать все константы в отдельную область, с которой потом сравнивать?

stevejobs ★★★★☆ ()
Ответ на: комментарий от stevejobs

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

Да нет, я как раз думал, что если мы хотим быстрого сравнения, лучше сравнивать по указателям, чтобы не парсить списки каждый раз. В scheme eq? - сравнение по указателям, equal? - сравнение по структуре. А в picolisp отдельного оператора сравнения по указателям вроде нет.

phill ()
Ответ на: комментарий от buddhist

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

phill ()
Ответ на: комментарий от buddhist

Авторы picolisp решили обойтись одним = вместо eq, eql и equal?

Begemoth ★★★★★ ()

К лиспам пытался приобщиться давно со scheme, потому как он вроде маленький компактный лисп. Возникали такие же вопросы, а почему так, а не эдак, а на хрена это. Забросил. Потом через N лет решил посмотреть CL. Лишние «философские» вопросы возникать перестали. Рекомендую выкинуть все эти newlisp-ы и юзать CL.

seg-fault ()

У тебя вопрос не связан с примерами, т.к. неизвестно, указывают ли а и б на один список. Во-вторых с чего ты взял, что пико не смотрит сначала на identity, и только потом сравнивает. В-третьих identity всегда подразумевает equality, но не наоборот, собственно в этом и разница eq? и equal?. Наверняка в пико есть и identity-тест.

http://software-lab.de/doc/ref_.html#==

http://software-lab.de/doc/ref.html#cmp

arturpub ★★ ()
Ответ на: комментарий от arturpub

Как это неизвестно? Они указывают на разные списки во всех примерах, это очевидно. Если на один, то будет (set 'a (1 2 3)) (set 'b a).

phill ()
Ответ на: комментарий от phill

Тогда непонятно, в чем заключался вопрос. Если в этом:

Насколько я понял, при сравнении списков в picolisp и newlisp сравниваются непосредственно сами списки, а не символы, указывающие на них.

то ответ в http://software-lab.de/doc/ref_.html#= http://software-lab.de/doc/ref.html#cmp

arturpub ★★ ()
Последнее исправление: arturpub (всего исправлений: 1)
Ответ на: комментарий от arturpub

Че то подумал щас, eq? проверяет не identity, во всяком случае, не в этом смысле. Например:


(define foo (lambda() 'x))
(define bar foo)
(write (eq? foo bar)) ; #t
(write (equal? foo bar)) ; #t

Здесь никаког явного идентификатора нет. Если он и есть на уровне реализации, то он создается за кулисами, и программисту не доступен. Здесь и foo и bar ссылаются на скомпилированный объект функции. Этот объект как список недоступен, поэтому equal? проверяет эквивалентность точно так же как eq? В любом другом случае, по-моему, equal? может заменгить eq? Получается, что eq? — это кастрированный equal? Он делает всегда то же самое что equal? но не может проверить списки. Нах*я он вообще нужен тогда?

phill ()
Ответ на: комментарий от phill

Нах*я он вообще нужен тогда?

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

anonymous ()
Ответ на: комментарий от anonymous

Да, кажись, так оно и есть, equal? наверное, сам определен через eq?, но, получается, что eq? нужен только для того, чтобы определить equal? больше он не нужен нигде.

phill ()
Ответ на: комментарий от phill

Опять тебя не туда понесло.Тебе нужно чтобы a и b были разными списками , на каком то этапе может случится к примеру, что a = (foo bar) и b = (foo bar) Но тебе нужно знать что это разные списки , а equal тебе вернёт #t

anonymous ()
Ответ на: комментарий от anonymous

Да, все верно, занесло, каюсь. Собственно для этого (только лишь) он и нужен.

phill ()
Ответ на: комментарий от phill

https://github.com/sbcl/sbcl/blob/17ba9560a86774392eed4e94896115865efafe13/sr...

;;; This is real simple, 'cause the compiler takes care of it.
(defun eq (obj1 obj2)

^ простая проверка уровня сравнения указателей, слов, того факта, что это единственный объект в памяти.

(defun equal (x y)
...

^ проверка на равенство — объекты могут быть разные (в памяти, не идентичны), но быть равны как значения. Видно, что equal занимается обходом любых сколько-нибудь сложных структур, но первым делом пробует %eql, который пробует eq.

Из identity => equality. Но equality !=> identity.

quasimoto ★★★★ ()
Ответ на: комментарий от phill

eq? проверяет identity. (eqv? x y) <=> (eq? x y), если для типов х/у не указано иное. (equal? x y) <=> (eqv? x y), если для типов х/у не указано иное.

anonymous ()

Пруф.

Высер от автора-идиота ты называешь пруфом, толстенький?

hvatitbanit ()
Ответ на: комментарий от hvatitbanit

ты на мунспике разговариваешь? а то мне комментарии в исходниках непонятны.

и ещё, пара pdf есть про ISLISP реализации, но моё знание японского недостаточно хорошо чтобы их перевести :(((

а так печалька — tisl исходники симпатичные, но мунспик немного смущает ((

вообще с реализациями ISLISP не всё ОК: 2 на мунспике, из них одна ANSI C (tisl), другая под андроед; по 1 шт на .NET и на Java; и самая вменяемая, но увы, за многие евро — OpenLisp.

эх, переписать что ли ту явовскую на D... была какая-та схемка на D с CTFE в духе InterLib, вот что-то такое и ISLISP — имхо, было бы идеально.

anonymous ()

Хорошо хоть у тебя по таблице умножения вопросов нет...

(это вместо RTFM! бл.......)

yyk ★★★★★ ()
Ответ на: комментарий от phill

Он делает всегда то же самое что equal? но не может проверить списки. Нах*я он вообще нужен тогда?

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

ps это equal делает то же самое что eq? в качестве оптимизации, насколько я знаю

pseudo-cat ★★★ ()
Последнее исправление: pseudo-cat (всего исправлений: 1)
Ответ на: комментарий от pseudo-cat

У меня такое в голову приходит. Не знаю насколько реальный пример.

CL-USER> (let ((xyz '(1 2 3))) 
	   (defun airplane-1 () xyz))
AIRPLANE-1
CL-USER> (let ((xyz '(1 2 3))) 
	   (defun airplane-2 () xyz))
AIRPLANE-2
CL-USER> (defun in-one-place? (airplane-1 airplane-2)
	   (equal (funcall airplane-1) (funcall airplane-2)))
IN-ONE-PLACE?
CL-USER> (defun is-same? (airplane-1 airplane-2)
	   (eq (funcall airplane-1) (funcall airplane-2)))
IS-SAME?
CL-USER> (in-one-place? #'airplane-1 #'airplane-2)
T
CL-USER> (is-same? #'airplane-1 #'airplane-2)
NIL
CL-USER> 
pseudo-cat ★★★ ()
Ответ на: комментарий от pseudo-cat

Четянихнипонел. У тебя в разных областях памяти записаны одинаковые координаты. Т.е., можно сказать, что две разные области памяти «указывают» на одно и тоже. Два аэроплана указывают на разные области памяти. Получается у тебя 2 разных аэроплана: они записаны в разных замыкниях. А их координаты - одни и те же. 2 разных объекта находятся в одном месте, так чтоли получается?

phill ()
Ответ на: комментарий от phill

ты еще более удивишься, когда узнаешь, что (is-same? #'airplane-1 #'airplane-2) на самом деле не NIL, а NIL or T в зависимости от реализации.

anonymous ()
Ответ на: комментарий от phill

2 разных объекта находятся в одном месте, так чтоли получается?

да.

pseudo-cat ★★★ ()
Ответ на: комментарий от anonymous

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

pseudo-cat ★★★ ()
Ответ на: комментарий от pseudo-cat

нет, я про то что (is-same? #'airplane-1 #'airplane-2) => NIL or T в зависимости от реализации. хочешь опровергнуть это очевидно истинное утверждение? пожалуйста.

anonymous ()
Ответ на: комментарий от anonymous

(is-same? #'airplane-1 #'airplane-2) => NIL or T в зависимости от реализации

пока ты это не доказал, это гипотеза.

Ладно, раз ты такой дуб, начну я. Вот, к примеру, что я вижу:

http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_i.htm#identical

identical adj. the same under eq.

http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_s.htm#same

The conses returned by two successive calls to cons are never the same.

Но, конечно, LW не стандарт, так что я просто спрашиваю тебя, известна ли тебе реализация CL, где будет T в данном случае?

pseudo-cat ★★★ ()
Ответ на: комментарий от anonymous

Хотя нет, это, можно считать, стандарт.

The Common Lisp HyperSpec™ is the acclaimed online version of the ANSI Common Lisp Standard, suitable for LispWorks users. The HyperSpec is derived from the official standard with permission from ANSI and NCITS (previously known as X3).

в том же LW, случайно, не T будет?

как там может быть T, даже теоретически, если у них в документации прописано что такое невозможно?

pseudo-cat ★★★ ()
Ответ на: комментарий от pseudo-cat

Хотя нет, это, можно считать, стандарт.

итак, сегодня ты узнал, что можно считать стандартом Common Lisp, поздравляю. скоро уже сможешь экспертные мнения высказывать, наверно.

как там может быть T, даже теоретически, если у них в документации прописано что такое невозможно?

где в документации это сказано?

anonymous ()
Ответ на: комментарий от pseudo-cat

В твоем случае никто консы не возвращает - это literal data, а литералы могут быть interned. вот если (list 1 2 3), а не '(1 2 3) - то они точно будут разные.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.