Здравствуйте, Sinclair, Вы писали:

N>>Квалификации — нет, а вот её оценке — есть.
N>>Я считаю, что на момент принятия того самого решения — иметь null как вариант значения указателя — оно было правильно, потому что практически реализуемо. Альтернатива была просто неподъёмна с тогдашними средствами.
S>Интересная гипотеза. В LISP, к примеру, обошлись без null, и ничего, тогдашними средствами всё поднялось.

В LISP не обошлись без null. В LISP он есть в виде NIL. Только не надо повторять ещё и ко мне ту чушь, что, мол, NIL это "пустой список", а не пустой указатель.
Нет, как раз пустой список реализован в LISP в виде пустого указателя, и тут он ничем не отличается от какой-нибудь C-подобной реализации где struct node с struct node *next, а NULL значит, что список пуст (длины 0).
Чтобы понять это глубже, посмотри, как в LISP работает хак (A.B) для неспискового B, где его используют и почему он нежелателен для общего применения.

N>>Главный вопрос — когда же это стало не просто подъёмно, но и необходимо. А вот это, я думаю, уже около 2000.
S>Как видим, языки без нулевых указателей были подъёмны в 1960.

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

N>>Пусть Хоар критикует себя тогдашнего сколько угодно, он прав в идеале, но неправ на практике.
S>Хороший ход. Ещё можно сказать, что он имел в виду совсем другое.

Ну с тем, кто так скажет, и дискутируй. Мне-то зачм твои ветряные мельницы?

N>>Где алгоритмы обычных операций с индексами — добавление, удаление ключа? Как управлять эффективностью хранения? Или это индекс из тех, что строятся один раз для постоянного набора?
N>>Как у него с конкурентностью? Для B-деревьев есть давно разработки с одновременным доступом из нескольких участников с адекватной синхронизацией, а тут?
S>Настолько детально я не разбирался. С модификациями там всё не вполне очевидно. А вот с конкурентностью всё хорошо известно — все древовидные структуры обрабатываются одинаково.

Точно все?

N>>Или не был такой нужен.
S> Эту гипотезу коллега vdimas уже высказывал. Контраргументы те же — вопросы компресии индексов интересовали разработчиков ещё в ранних 1980х. Это хорошо видно по публикациям статей.
S>Так что возможность уменьшить размер индекса в пару тысяч раз конечно же была востребована.

Теоретическая. Практически же тут есть непреодолимая пропасть — даже две — между 1) реализуемым в теории, 2) реализуемым на практике для константных деревьев и 3) реализуемым на практике для активно изменяемых деревьев. И что "реализуемо на практике" зависит от 100500 факторов.

То же LSM tree тоже ничто не мешало изобрести, например, в 1972 (возьмём за базу публикацию B-деревьев), он в разы проще тех же B-деревьев, но мешали аж три вещи:
1) недостаток места (чтобы индекс занимал место в 2-4 раза больше — не могли себе позволить);
2) отсутствие потребности в алгоритме для потоковой записи крупными порциями вместо одного блока;
3) проблема с организацией фоновых сжатий индекса (сейчас решается, например, через фоновые нити — а тогда надо было делать машину состояний и мириться с замираниями на сбор крупных порций).
Возможно, его тогда и изобретали кучу раз. А потом думали "и зачем эта фигня?" и забывали.
А вот ближе к 2000 начали давить тормоза позиционирования HDD, добило — появление SSD с записями порциями типа 128KB. А дисковое место на индексы стало доступно.
Вот то же самое и с потребностями при разработке языков.