Будем считать, что деревья, растущие от общего корня - это разные деревья, ведь корень это такая абстракция...
Нет, не будем так считать. Все деревья это ветви одного корня и имеют одно начало. При этом программист во время выполнения получает доступ только к определенно ветви, начало которой для него и есть корень. Эта основа языка и вычислительная модель построена именно таким образом. В этом и заключается фишка - все объекты имеют одну общую природу и потому к ним применимы некоторые общие операции (типа удаление, перемещение, копирование и пр.).
Математически все что можно использовать в языке есть некоторые элементы множества А, где а ∈ А . Соответственно, если есть а ∈ А, и b ∈ А, то справедливо
F(a) ⇒ F(b), так как F ∃ A. Всё что имеет общие свойства имеют и общие операции. На практике реализовать такое конечно очень сложно, но в целом язык следует такому правилу. От корня есть и другие ветви, немного с картинками это есть в описании языка (я недавно выкладывал более формализованное).
Если деревьев много, то это целый лес.
Если это лес, то в нём можно запросто заблудиться.
Что есть, то есть. Это реальная проблема во многих языках программирования - я имею ввиду удобное обращение и манипулирование объектами. И это реальная проблема человеческой деятельности вообще - тут наверно проблема в восприятии человеком окружающей действительности.
А указателей у Уткина нет, у него сплошные строки
Указателей нет, в смысле прямого обращения к ячейкам памяти. Так имя переменной или функции (или объекта или класса) это тоже указатели, просто иного рода. Это вопрос больше эстетический и теоретизированный, чем вопрос практического значения. Нельзя написать программу не дав указание на манипулирование объектом (даже не явно), а указание любого рода есть работа с указателями и ссылками. Просто имена это более высокоуровневые указатели, в сравнении с простым адресом в памяти. Просто в литературе использование термина "указатель" в большинстве случаев означает адрес конкретной ячейки памяти (обычно ОЗУ).
(и вообще, по-моему, язык без статической проверки типов, но могу ошибаться)
Да, без автоматической проверки типов. И уже тем более без статики.
И вот, пользователю юткина нужно указывать на конкретные листья. Как он будет это делать? Я бы использовал что-то типа XPath.
Да так и есть, только XPath это очень круто - на его написание нужно времени не меньше, чем на сам язык наверно. Для деревьев есть концепция "полный сцепленный ключ" - ничего не обычного - XPath в простом виде он и есть (XPath умеет много чего больше чем просто ссылаться на объект). Только вместо слешиков решили (на Remdev.org) использовать точку.
Но ведь такого рода длинные описания путей гораздо более ресурсоёмкие, чем прямые указатели в памяти.
Верно. Все что отличается от команд непосредственно исполняемых процессорами есть ресурсоемко. Правда, если посмотреть современные тенденции языкоклепания, то видим, что имеется четко выраженная направленность использовать именно механизмы сильно отличающиеся от встроенных (первым таким были строки).
Не будут ли программы на языке Уткина редкостным тормозиловом? И если нет, то почему?
Они будут тормозиловым, но не жутким. Потому что несмотря на то, что модель использует дерево, реализовано оно плоско, потому что память компьютера плоская и нет возможность реализовать иначе быстро и эффективно. Для поиска узлов (сразу на всем сцепленном ключе, без перехода от узла к узлу) используется бинарный поиск - то есть все узлы отсортированы лексикографически в соответствии со своими сцепленными ключами (особым приятным побочным эффектом данного процесса является то, что в результате получаем дочерние узлы, сразу же следующие за своим родителем - мелочь, но очень приятная в плане производительности). В результате нам доступна операция сравнения и возможность отсечения половины интервала (ну просто бинарный поиск) - сначала сравниваем в центре диапазона, потом в центре одной из половин и т.д. (для 100 элементов в наихудшем варианте требуется просмотреть 7 или 8 элементов, для 1000 элементов требуется 10 или 11 сравнений, для 100 000 элементов требуется примерно 20 сравнений в наихудшем варианте). Бинарный поиск не самый эффективный алгоритм поиска, но на данном этапе важно рождение системы в принципе, оптимизацией процесса займемся позже. Тем более возможности оптимизации имеются - все тот же факт того, что дочерние узлы располагаются сразу же после родительского - это дает некоторую возможность искать не сначала списка узлов. В общем это тормозилово, если сравнивать с арифметикой указателей, но не жуткое тормозилово вообще.
Могу Вас успокоить, что загрузка и анализ конструкций из файла на диске занимает гораздо больше времени, чем поиск в 100 узлах (правда загрузка пока производится только одного синтаксиса и однократно).
ЗЫ. Специально для Вас - строки не сравниваются целиком, сначала идет сравнение для длины строки (в смысле количество символов, байтовое сравнение юникодовых символов это очень интересная тема), потом первых символов строк и только если они совпадают происходит дальнейшее сравнение.... Поэтому полноценные сравнения проводятся только для очень похожих ключей.
Отредактировано utkin (2018-01-29 13:50:37)