bike 0.14.0 - документация!

Связный список так не работает. Вы хотите двухсвязный список, по которому можно ходить в обе стороны. Естественно двухсвязные списке, как и все основные структуры данных есть в CL и других лиспах.

Естественно двухсвязные списке, как и все основные структуры данных есть в CL и других лиспах.

В стандартной библиотеке нет.

У сишки в стандартной библиотеке вообще мышь повесилась и ничего, живут как-то с нестандартными.

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

Всё ж с практической точки зрения: чтобы в языке были базовые строительные блоки и в библиотеках уже были реалзованы остальные. Если это есть, то разделение чего положить в стандартную библиотеку, а чего — в нестандартные уже является вопросом вкуса и привычки.

От ведь. А действительно. Мне почему-то казалось, что ООП в Turbo Pascal завезли позже.

ООП и в виртовском паскале был, но он был классический как в java один класс на один файл, что очень неудобно, Turbo Pascal с его gui инструментами Turbo Vision, ООП был великолепен так как появилось вместе с продуктом его использующим.

Это сейчас модули только в самом зародыше :)

namespace сильно ускоряет работу интерпретаторов так ускоряет поиск именованных объектов, на компиляторы это не влияет, а конфликты имён программист решал

ООП и в виртовском паскале был,

Скорее уж в Oberon-е, а не в Паскале. В Виртовских Pascal и Modula-2 я ООП не помню.

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

Си++ на своём примере показал, что если посчитать это вопросом вкуса, можно легко получить вместо языка набор малосвязанных диалектов. Причём проблема возникает при перекосе в любую сторону. Сначала не было стандартных строк и умных указателей: получили несовместимые строки в каждой более-менее крупной библиотеке. Теперь воткнули в стандартную библиотеку всё, что можно, и получили проклятие PL/1：почти ни у кого нет полной реализации этой библиотеки. И если кто-то захочет сделать альтернативный компилятор, это практически невозможно (также как и альтернативный движок браузера, соответствующий всем стандартам).

В C есть <sys/queue.h>

Это не в Си есть. Это сторонняя библиотека.

Естественно, что в CL существует множество сторонних библиотек с любыми структурами данных вообще, какие только можно представить.

Это не в Си есть. Это сторонняя библиотека.

Это маленький заголовочный файл который есть в BSD, Linux, и притащить его в Windows труда не составит, хотя возможно и там он есть, с MSYS2 уж точно будет. Но вообще я не про то что в С есть списки, а про то что в популярном решении для списков есть Insert.

Во-первых, в лиспе связных списков вообще нет. Есть только cons-ячейки и символ NIL.

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

В-третьих, касательно массивов - дело в том что существуют разные виды массивов, и для некоторых операция «вставки» не имеет смысла. Для других видов, ее смысл неоднозначен.

Самое близкое к дотнетовскому, скажем, List<>, или к питоновскому списку, это одномерные расширяемые массивы с указателем заполнения.

Для них не составляет труда написать функцию самому:

(defun vector-insert (vector index element)
  (declare (type (array * (*)) vector)
           (type (integer 0 #.array-total-size-limit) index))
  "Inserts an ELEMENT into the VECTOR at an INDEX.
The VECTOR must be an adjustable one-dimensional array with a fill pointer."
  (let ((capacity (array-total-size vector))
        (fp (fill-pointer vector)))
    (when (or (< index 0)
              (> index fp))
      (error 'type-error :datum index
                         :expected-type `(integer 0 ,fp)))
    (when (= fp capacity)
      (adjust-array vector (1+ (* capacity 2))))
    (incf fp)
    (setf (fill-pointer vector) fp)
    (replace vector vector :start1 (1+ index) :start2 index)
    (setf (aref vector index) element)
    (values index vector)))

Вот тебе delete функция впридачу

(defun vector-delete (vector index)
  (declare (type (array * (*)) vector)
           (type (integer 0 #.array-total-size-limit) index))
  "Removes an element from the VECTOR at an INDEX.
The VECTOR must be an adjustable one-dimensional array with a fill pointer."
  (let ((fp (fill-pointer vector)))
    (when (or (< index 0)
              (>= index fp))
      (error 'type-error :datum index
                         :expected-type `(integer 0 ,(1- fp))))
    (let ((element (aref vector index))
          (element-type (array-element-type vector)))
      ;; to prevent memory leak
      (setf (aref vector index) (case element-type
                                  ((base-char character) (code-char 0))
                                  (long-float 0.0l0)
                                  (double-float 0.0d0)
                                  (single-float 0.0f0)
                                  (short-float 0.0s0)
                                  (t 0)))
      (replace vector vector :start1 index :start2 (1+ index))
      (decf fp)
      (setf (fill-pointer vector) fp)
      (values element vector))))

Касательно Contains - это функция find.

IndexOf - функция position

Во-первых, в лиспе связных списков вообще нет. Есть только cons-ячейки и символ NIL.

Понятие proper list в стандарте есть. copy-list тоже есть. А ячейки - это особенность реализации. Как в «Си нет строк», но есть strcpy и strcat.

proper list, а также property list, alist итд это абстрактные концепции.

В лиспе нет структуры данных «список»

в лиспе все принято делать в функциональном стиле

setf setf setf

О да.

;; to prevent memory leak

В SBCL если явно не очистить ячейку массива, сборщик мусора её потеряет??? Я про него намного лучше думал.

Справедливости ради, в функциональном стиле массивы работают медленно. Хотя можно (на Racket)

(define (vector-insert vec index element)
  (define-values (start end) (vector-split-at vec index))
  (vector-append start (vector element) end))

В лиспе нет структуры данных «список»

Тогда какоую структуру данных ожидает стандартная функция list-length?

это абстрактные концепции

Так при желании про любой тип данных можно сказать. Ведь всё есть набор битов, а сверху только абстрактные концепции.

в функциональном стиле массивы работают медленно

Зависит от того, как они реализованы. Если это иммутабельные персистентные структуры данных, которые не нужно полностью копировать при каждом «изменении», то вполне приемлемо работают. (На случай, если это реально узкое место в алгоритме, в кложе есть transients, в порядке исключения позволяющие локальные setf-like фокусы — с непременным последующим разоблачением преобразованием в персистентную коллекцию, обычные функции для работы с коллекциями бросают исключения на транзиентах).

Но это не про борщелисп, я так понемаю. Там структуры данных по умолчанию мутабельные и никто setf-а не стесняется особо.

Если это иммутабельные персистентные структуры данных, которые не нужно полностью копировать при каждом «изменении»

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

На самом деле, хороший компилятор преобразует

(define (f ...)
  (define v (vector ...))
  ...
  (g (vector-insert v i e) ...))

(то есть, если есть гарантия, что после передачи в vector-insert оригинальный массив уже не нужен) в версию, в которой vector-split-at в качестве start вернёт оригинальный массив с ограничением длины, а vector-append попытается сделать расширение массива на месте.

Но это не про борщелисп, я так понемаю. Там структуры данных по умолчанию мутабельные и никто setf-а не стесняется особо.

Да. В отличие от Racket в CL setf и макросы используются там, где можно было бы обойтись и без них.

И версия функции через dolist/loop в CL будет быстрее, чем через рекурсию и хвостовую оптимизацию.

Поэтому CL позволяет писать функционально, но принято это не больше, чем в Rust, например.

если fill-pointer поменять, объект то в массиве останется

Я про (setf (aref vector index) ...). Следующей же строкой эти данные затираются функцией replace.

При чём тут вообще fill-pointer? Он только на хвост массива влияет.

Если это на частный случай, когда удаляется последний элемент, так лучше бы добавить ветку

(cond
  ((= fp index)
   (vector-pop vector))

чем при любом удалении дополнительную запись в массив делать, а при удалении последнего холостой вызов replace.

P.S. Или vector-pop в SBCL тоже оставляет возвращённый объект в массиве и не даёт GC его очистить?

одно из двух: или не нужно полностью копировать или быстрый доступ по индексу

Персистентный вектор в кложе может и то, и то. Не O(1)-быстрый, но O(log(n)) с большим основанием (под капотом hash array mapped trie, дерево с 32 ветвями на узел).

Че значит явно очистить? Если ты fill-pointer поменял, объекты в массиве у тебя все-равно остались.

Я аж икать начал.

Я аж икать начал.

Немедленно переименовать lisp в просто p!

– Ты кто?
– Я джава-программист!
– Понятно. А ты кто?
– Я жаваскрипт-программист!
– Ну бывает. А ты?
– Я п-программист!
– Заикаешься, что ли? Раньше вроде шепелявил.

просто p!

Веб-студия «Коммон Пэ». Простите, не удержался.

Персистентный вектор в кложе может и то, и то. Не O(1)-быстрый, но O(log(n)) с большим основанием (под капотом hash array mapped trie, дерево с 32 ветвями на узел).

Вычисление hash уже очень не быстро. Я как-то с Перла на Си переносил программу. Сначала 1-в-1, получил ускорение в 4 раза. Потом заменил хеши на массивы, получил ускорение в 50 раз.

Если ты fill-pointer поменял, объекты в массиве у тебя все-равно остались.

Понял. Он только на length влияет.

Но чистить тогда надо элемент в конце, а не тот, который через replace затрётся (если не последний). В общем, код всё равно странный.

И 5 лет не прошло!

Вычисление hash уже очень не быстро.

Подозреваю (в исходники не смотрел), что вектор использует просто индексы как хэши. По крайней мере, звучит логично.

заменил хеши на массивы

И вся реализация работы с ассоциативной структурой данных переехала в пользовательскую программу? %)

что вектор использует просто индексы как хэши

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

И вся реализация работы с ассоциативной структурой данных переехала в пользовательскую программу? %)

В смысле? Там всё было пользовательской программой.

Изначально ассоциативный массив был потому что в Перле они удобны. Типа $a{"OK"}++. Там, где был ассоциативный массив от набора чисел заменил сплошным размером по максимальному числу. Там, где был от строк, перевёл в перечисление. Реально данных от произвольного ключа в программе не оказалось.

это не хэш, а просто массив деревьев

Да, это не хэш (hash-table), это префиксное дерево (trie), в котором роль префиксов играют куски ключа элемента или производного от него значения (хэша ключа).

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

будет срыв кэша практически на каждом элементе

Да, говорят, с кэшем есть некоторые сложности. Но зато имеем эффективные иммутабельные персистентные структуры данных без постоянных копирований всего массива. Как всегда — серебряной пули нет, есть набор компромиссов.

Есть любопытная серия постов как раз про персистентные векторы: https://hypirion.com/musings/understanding-persistent-vector-pt-1

Реально данных от произвольного ключа в программе не оказалось.

Ну то есть и в программе на Перле хэш был не так чтобы сильно и нужен, и можно было ускорить и её тем же методом (не в 50 раз, конечно).

Ну то есть и в программе на Перле хэш был не так чтобы сильно и нужен, и можно было ускорить и её тем же методом (не в 50 раз, конечно).

Да. Это как раз иллюстрация к базовым типам. Если нужна какая-то коллекция, то в Си++ это будет массив, в перле хэш, в лиспе список. А смена типа данных будет только если требуется оптимизация.

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

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

зачем они иммутабельные

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

А самое печальное — что иногда курва бобр это ты сам. И довольно часто.

В общем, иммутабельные структуры данных упрощают написание и понимание написанного, экономят время, нервные клетки и волосы на жопе. Особенно если язык и его стандартная библиотека спроектированы для работы с ними. (Можно использовать какой-нибудь immutable.js в жопаскрипте, но сам язык не поощряет такой подход и это сразу заметно.)

Чтобы тебе не приходилось для защиты от бобров заниматься неэффективным по времени и памяти защитным копированием, городить блокировки, ловить гонки и дедлоки, тащемта.

ACID на минималках? Так всё равно потом выбирать, какую версию данных считать правильной. По мне, так уж лучше очередь сделать к одному хранителю массива. Тогда точно есть и всегда актуальная версия данных и гарантированно последовательная запись в массив и отслеживание, если кто-то получил протухшие данные (оптимистичная блокировка). Или вообще реальный ACID на какой-нибудь СУБД в памяти.

По мне, так уж лучше очередь сделать к одному хранителю массива

Для некоторых задач тоже вариант, почему нет. Но от внезапного изменения данных из другого треда никак не защищает. Получил ты ссылочку на массив, читаешь его, а кто-то тем временем ему shuffle сделал.

Если нужна какая-то коллекция, то в Си++ это будет массив, в перле хэш, в лиспе список

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

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

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

Хотя согласен, «городить блокировки, ловить дедлоки» этот вариант не исключает.

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

Блокировать запись, пока кто-то читает, и наоборот? На вкус совсем как орбит отрицательный прирост производительности %)

По идее, нужны и последовательные коллекции, и ассоциативные

А они тоже от языка зависят.

В перле будет нетипизированный массив и хеш

В си++ будет типизированный массив и дерево

В лиспе будет список и список пар.

В хаскеле будет неизменяемый список и неизменяемое дерево

Блокировать запись, пока кто-то читает, и наоборот?

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

В лиспе будет список и список пар.

Ну вот это и есть оно самое — городим хэш для бедных из того, что есть под рукой. При этом как вектор список тоже говно, потому что нет доступа к произвольному элементу за О(1).

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

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

Примерно до 50 элементов, этот вариант работает быстрее, чем хэш. Поэтому, если надо что-то вроде питоновского объекта, то лучше список, чем хэш. Потом достаточно долго дерево быстрее, чем хэш. И только когда количество объектов уже десятки тысяч, хэш становится быстрее.

Ещё быстрее на малом количество объектов упакованный массив паскалевских строк. То есть ключ вида «{байт 4}key1$$$${байт 5}key42$$$${байт 7}longkey$$$$», где $$$$ адреса соответствующих значений или сами значения, если они фиксированной длины.

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

Иммутабельные данные нельзя испортить же, они могут только устареть. Если мы хотим иметь какое-то изменяемое состояние и читать всегда последнюю версию, достаточно предусмотреть механизм, который будет атомарно заменять старое иммутабельное значение на новое (и прятать под капотом все очереди и блокировки, если они нужны) — как это делают ссылочные типы данных в кложе (atom, ref, agent, var).

Без иммутабельности это всё нормально работать не будет, конечно. (А без эффективной реализации персистентности будет, ahem, неэффективно.)

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

Так это и есть. Как только поток начал работать с копией, если другой поток изменил массив, та копия устарела. Всё равно, что git с многими пользователями. Если пока редактировал, файл изменился, надо как-то делать слияние. А если редактируешь один файл, а другой пользователь редактирует логически связанный файл, так вообще легко неработающую программу получить.

В этом смысле вариант 1С, когда модуль, в котором ты работаешь, никто другой править не может, выглядит предпочтительней.

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

Ссылочные типы данных как раз эту проблему и решают. Если два (или больше) потока одновременно делают swap! (замену значения) одному атому, успешно завершится только одна операция, а остальные будут автоматически перезапущены (и будут всегда видеть последнюю версию данных). Причём замена происходит атомарно и читатели, сделав атому deref (получить текущее значение), всегда видят консистентное значение, результат последней завершившейся на этот момент операции swap!/reset!.