Lisp и сравнения...

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

> можно было написать функцию, сравнивающую свои аргументы

Считается правильным в твоем случае передавать в функцию дополнительный параметр -- функцию для сравнения. Для тривиальных случаев ввести сахару макросами.

Есть куча других вариантов. Можно написать макрос, который разворачивается в большой COND, который, в зависимости от аргумента (NUMBERP, STRINGP etc) возвращает правильную функцию для сравнения. Можно определить класс сравниваемых величин, и передавать в аргументах эти классы. Можно вынести из функции всю логику, зависимую от типа аргументов, и доставлять ее отдельным параметром -- замыканием. Возможностей миллион, я перечислил только те, которые мне сходу в голову пришли :)

Мне нравится для всяких сортировок передавать функцию сравнения, типо string= :)

В lisp чуть-чуть другой подход, более корявый, в маленьком массиве кода (:

Имхо самое правильное - передавать в функцию также и функцию, которая умеет сравнивать нужные типы.

Пасиба :) в принципе я что-то подобное и думал (это я про cond), Ну да фиг с ним.. мне сейчас это реально не надо :) посто игрался, написал кусорт:

(defun my-qsort (list-for-sort) (if (= (length list-for-sort) 0) '() (append (my-qsort (remove (first list-for-sort) (rest list-for-sort) :test #'<)) (list (first list-for-sort)) (my-qsort (remove (first list-for-sort) (rest list-for-sort) :test #'>=)))))

и хотел чтобы он работал со всем и сразу :) в принципе не кретично, прсто проба пера :)

В моём случае придётся передавать две функции, я так понимаю :)

рррр... форматирование...

(defun my-qsort (list-for-sort)
  (if (= (length list-for-sort) 0) '()
      (append (my-qsort (remove (first list-for-sort) (rest list-for-sort) :test #'<))
              (list (first list-for-sort))
              (my-qsort (remove (first list-for-sort) (rest list-for-sort) :test #'>=)))))

При желании, несложно сделать такую функцию, которая узнавала
 бы тип аргумента и находила бы для него нужные функции сравнения. 

совсем по-тупому что-нибудь вроде простенького

(defmacro make-comparer-fn-get (fn &rest arg)
    `(defun ,fn (arg)
        ,(let ((ca '((t (error "uncomparable type")))))
            (dolist (x arg)
                (push `((funcall #',(first x) arg) #',(second x)) ca))
            (cons 'cond ca))))

(defmacro make-comparer-fn (fn &rest arg)
    `(defun ,fn (arg argn)
        ,(let ((ca '((t (error "uncomparable type")))))
            (dolist (x arg)
                (push `((funcall #',(first x) arg) (funcall #',(second x) arg argn)) ca))
            (cons 'cond ca))))

(make-comparer-fn untyped-less
    (integerp <)
    (stringp string<))

(make-comparer-fn-get get-less-for
    (integerp <)
    (stringp string<))

(format t "comare result ~A~%" (untyped-less 1 2))
(format t "comare result ~A~%" (untyped-less "12" "13"))

(format t "comare result ~A~%" (funcall (get-less-for 1) 1 2))
(format t "comare result ~A~%" (funcall (get-less-for "12") "12" "13"))


(за ашыпки не пинайте, сонный и не проверял, но идея очевидна)
Второй вариант не так красив, зато полезен для той же сортировки,
 чтобы не тормозило лишний раз. Однако всё равно непонятно, зачем,
 если можно передать нужную функцию в качестве параметра.

> (if (= (length list-for-sort) 0) '()

это не нужно столько всего, достаточно:

(if (not list-for-sort) nil

или вообще лучше

(if list-for-sort
    ...
    nil)

иначе придут злые питоноеды ворчать на обилие скобок,
 ибо оне злы и занудны по причине скверных их условий существования.

Ок, пасиба за все советы :) я тока учусь, поэтому может что-то не очень красиво выглядит :)

funcall в макросах кстати излишество, достаточно было бы соответственно

(push `((,(first x) arg) #',(second x)) ca))

(push `((,(first x) arg) (,(second x) arg argn)) ca))

В лиспе разбираюсь плохо, но как насчет этого 

(defmethod less ((x integer)(y integer)) (< x y))
(defmethod less ((x string)(y string) (string< x y))
...

Скобочку забыл. Не ((x string)(y string), а ((x string)(y string))

> иначе придут злые питоноеды ворчать на обилие скобок, ибо оне злы и занудны по причине скверных их условий существования.

Не злы они, а только лишь справедливы. Ибо скобок девствительно дох... :)

> Ибо скобок девствительно дох... :)

А их кто-то считает?!... 0_0

> А их кто-то считает?!... 0_0

А че их считать, и так видно что их дох ...

> Не злы они, а только лишь справедливы. Ибо скобок девствительно дох...

Дело-то не в скобках. Если писать так:

> (if (= (length list-for-sort) 0) '()

То питоноеды скажут, что если так писать, то правильно написанная программа на тормозном Питоне будет быстрее, чем так коряво написанная программа на Lisp. Ибо тут O(n) вместо предложенных альтернатив O(1), если, конечно, умный компилятор не соптимизирует.

> То питоноеды скажут, что если так писать, то правильно написанная программа на тормозном Питоне будет быстрее, чем так коряво написанная программа на Lisp. Ибо тут O(n) вместо предложенных альтернатив O(1), если, конечно, умный компилятор не соптимизирует.

Ох уж эти питоноеды

К слову списки в питоне реализованы вроде через массивы (да, да, я сам офигел) так что аналогичный "плохой" код в питоне возможно будет выполняться за O(1) :) Питон рулит!

Только вот расширяться список будет долго ;)

Ну так и во многих лиспах или хаскелях под (LIST) отводится структура с массивом, который реаллочится по мере наполнения. Поэтому и для выяснения (LENGTH) ненужно пробегать весь список до '(), и работает сильно шустрее (на x86 может целиком в кеш всосаться, да и вообще последовательное чтение в RAM заметно быстрее, чем скачки по разным указателям).

> Ну так и во многих лиспах...

И? Зачем оглядываться на "многие", если есть "хорошие"? Это во-первых. А во-вторых, потери от "скачущего" #'length меньше, чем от резки/сборки массивов. И проход по нескольким указателям - ерунда, если вспомнить о "символьных вычислениях", "локальных окружениях" и прочем.

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

> И? Зачем оглядываться на "многие", если есть "хорошие"? Это во-первых. А во-вторых, потери от "скачущего" #'length меньше, чем от резки/сборки массивов. И проход по нескольким указателям - ерунда, если вспомнить о "символьных вычислениях", "локальных окружениях" и прочем.

Впринципе компилятор может выбрать какую реализацию списка ему использовать анализируя те действия, которые производятся над списком. Если используется только length, nth, car, cdr то почему бы не заменить на массив ? если удаление/вставка то можно использовать классическое представление списка - в виде цепочки указателей.

Ну это теритически... :)

> Ну это теритически... :)

Это сильно "теоретически", ибо это равносильно оптимизации работы с локальными параметрами/переменными определённого типа при условии наличия уверенности (какой?), что вызываемая из кода функция не будет пытаться оперировать этими самыми переменными по именам...

Я думаю - овчинка выделки не стоит. Других проблем хватает...

Хотя как делают "закрытые" топовые лиспы - х.з.

>Ну это теритически... :)

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

"Хорошие" компиляторы не будут резать/собирать массив из-за каждого изменения, они просто отмечают вылетевшие элементы флагом, а потом в нужный момент проводят вакуум (или как там его), когда запуститься gc :)

Потом, как часто используется в _списках_ мутация отдельных элементов? Самая обычная работа со списками -- это итерация (loop), отображение (map), свертка (fold) и подобное. Во многих таких случаях даже не нужен GC -- достаточно модифицировать исходный список. И здесь вполне разумным будет держать список в одном месте оперативной памяти (массиве), чтобы получить выигрыш за счет кэша и избежать задержек при чтении случайной ячейки RAM.

> если вспомнить о "символьных вычислениях", "локальных окружениях"

Это тоже неплохо оптимизируется в отдельных случаях :)

> поскольку может выясниться только в рантайме.

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

> Впринципе компилятор может выбрать

Между прочим, так оно и есть :) Есть даже лозунг хаскелистов -- Let the compiler do its work, в смысле, доверься компилятору =) Думаю, что так оно и должно быть, сейчас ведь все согласны с тем, что gcc сгенерирует ассемблерный код эффективней, нежели человек.

С другой стороны, в случае с хаскелем все проще -- там функции чистые, и можно применять некоторые техники суперкомпиляции, в смысле, модифицировать алгоритмы на уровне исходного текста.

Интересно было бы прочитать про применяемые методы выбора оптимальной реализации структуры данных, если там что-то по серьезней простого анализа dataflow-графа.

Я несколько месяцев назад наталкивался на очень хорошую статью, типа сборник хинтов при реализации производительного scheme-компилера. Попробуй выгуглить эту pdf-ку, я ее скачивал, но что-то не могу найти, куда-то похерил :(

> А че их считать, и так видно что их дох ...

Их хотя бы видно, в отличие от некоторых управляющих секвенциев оных последователей передовых идей, которые были заложены в славном Языке Программирования Будущего уайтспесе.

> "Хорошие" компиляторы не будут резать/собирать массив из-за каждого изменения, они просто отмечают вылетевшие элементы флагом, а потом в нужный момент проводят вакуум (или как там его), когда запуститься gc :)

Вылетевший элемент - это слишком просто.

> Потом, как часто используется в _списках_ мутация отдельных элементов? Самая обычная работа со списками -- это итерация (loop), отображение (map), свертка (fold) и подобное. Во многих таких случаях даже не нужен GC -- достаточно модифицировать исходный список.

Это очень жёстко оговорено - где можно модифицировать список а где нет. Нарушать стандарт можно, но только это уже не CL будет

> И здесь вполне разумным будет держать список в одном месте оперативной памяти (массиве), чтобы получить выигрыш за счет кэша и избежать задержек при чтении случайной ячейки RAM.

ИМХО, у вас очень странный опыт работы с лиспом/ковыряния в его потрохах. Посмотрите на макры: если такой-то элемент соответствует условиям - взять такую-то цепочку, выделить доку, декларации, остальное засунуть внутрь другого списка (это "простой" вариант, часто "тело" ещё надо "резать" и т.п.) и т.д. Приклеить к списку в голову другой - старый остается валиден (как часть нового). Посмотрите на возможные комбинации #\@ и #\, в макрах - перловка сказкой покажется...

Хотя я согласен, что компилятор может очень много наоптимизировать. Но, скорее всего, это будет "на грани фола", если не вовсе за рамками стандарта, согласно которого только #'func-name оградит вас от возможной подмены функции в рантайме. На счёт спец. форм только не уверен...

> Вылетевший элемент - это слишком просто.
> Приклеить к списку в голову другой

Не, ну зачем же сразу драматизировать =) 
Разумеется, я не предлагаю копировать области памяти, чтобы получить 
два списка. Но под новый список (с головой и указателем на хвост) 
можно выделить отдельный длинный регион, все остальные cons'ы к новому 
списку все равно будут идти подряд. Это технические детали, притом 
вполне решаемые :)

> Это очень жёстко оговорено - где можно модифицировать список а где нет.
Нарушать стандарт можно, но только это уже не CL будет.

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

(define plaintext->list-of-quoted-strings
  (lambda (file-name)
    (let ((list-of-strings
           (call-with-input-file file-name
             (lambda (input-port)
               (unfold eof-object?
                       values
                       (lambda (_) (read-line input-port))
                       (read-line input-port))))))
      (map (lambda (string)
             (string-append "'" string "'"))
           list-of-strings))))

Здесь компилятор в полном праве применить деструктивный map над 
элементами list-of-strings, ибо последний виден только внутри 
функции и уже далее никому не пригодится. Никакому стандарту здесь 
ничего не противоречит :)

Вырожденный случай :)

Таких случаев полно по всей программе :)

Вырожденная программа...

Да ладно, я не спорю - в вырожденном случае компилятор волен себе немного "посвоевольничать" если это во благо ;)

Это не вырожденный случай, это частный случай. Две большие разницы.

Гы. Чото я не то ляпнул. В том смысле что приведенный выше случай - достаточно распространенная ситуация в любой более или менее сложной программе.

> В том смысле что приведенный выше случай - достаточно распространенная ситуация в любой более или менее сложной программе.

Я ж не спорю - встречается конечно. Но это _очень_ частный случай работы со списками.

И кроме того - мало узнать, что "промежуточный" список нафиг не нужен после вычисления результата функции, надо быть уверенным, что функция, передаваемая в map, "чиста" сама и/или не использует глоб. переменные. А то я такого могу наворотить... А как вы можете обрести эту самую уверенность в лиспе?..

> Но это _очень_ частный случай работы со списками.

А какие операции со списками, с твоей точки зрения, наиболее частые? :)

> надо быть уверенным, что функция, передаваемая в map, "чиста"

> А как вы можете обрести эту самую уверенность в лиспе?

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

Разумеется, можно допустить, что ты можешь дернуть через ffi какой-нибудь нативный код, который напрямую полезет к памяти и начнет модифицировать список... Но тут уже ни в чем нельзя быть уверенным :)

А вообще советую еще поглядеть исходники Stalin Scheme Compiler :) Его код в процессе работы генерирует намного меньше мусора, чем обычный интерпретатор схемы, как раз за счет оптимизаций подобного рода.

> В рамках платформы это проверяется относительно несложно. Во многих случаях достаточно проанализировать граф ссылок на переменную.

А если в графе есть хоть один вызов не-inline функции по имени

(func x1 x2 x3) <==> (funcall 'func x1 x2 x3)

а не по её коду на момент компиляции

(funcall #'func x1 x2 x3)

возвращать 'оптимизация невозможна'? И часто тогда будут наступать случаи применения этой самой оптимизации?

Да я не говорю, что оптимизация невозможна. Но, ИМХО, стандарты написаны настолько свободно (т.е. оставляют на волю реализациям очень много), что либо придётся выходить за их рамки (я не говорю, что это плохо, просто об этом надо сообщать), либо "толку" будет намного меньше чем могло бы быть...

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