Продолжаем конструировать язык Hi. Сегодня рассмотрим встроенную реализацию связного списка (linked list).
Не все промышленные языки имеют встроенную поддержку связного списка как структуры данных. Впрочем, его нетрудно реализовать самостоятельно как класс или структуру. Для комфортной работы с релевантными алгоритмами мы добавим встроенные двунаправленные связные списки уже в базовое определение языка Hi.
Для начала создадим экземпляр нашего экспериментального списка:
В примере выше для трех узлов автоматически создаются двунаправленные ссылки.
Связанный непустой список в языке Hi всегда имеет один узел, который является текущим или «активным». По умолчанию это последний добавленный элемент, то есть сейчас это «be». Проверим это:
Добавим в наш список еще два элемента:
Встроенный метод insert добавляет новые элементы сразу после активного узла, автоматически выстраивает новые связи и делает текущим последний добавленный элемент (добавить и сделать первым новый узел списка можно методом insertFirst).
Удаление осуществляется похожим образом для текущего элемента:
Впрочем, можно сразу удалить и несколько элементов, для этого нужно предварительно установить указатель на первый удаляемый узел:
При этом узел, предыдущий перед удаляемым, становится текущим. Если удаляется первый элемент списка, то текущим становится новый первый элемент.
Можно заменить текущий узел на другой, просто присвоив элементу новое значение:
Удалить все узлы, то есть сделать список пустым можно так:
Переходить на первый и последний узел удобно следующим образом:
Таким образом можно достаточно легко осуществлять разнообразные операции со списком:
Update 12 October 2020: Продолжение статьи в комментариях здесь и здесь:
Связный список >
Связный список представляет цепь элементов — узлов, каждый из которых, кроме последнего, связан, то есть имеет ссылку на один следующий элемент (однонаправленный список) и для двунаправленного списка каждый элемент, кроме первого, связан с одним предыдущим элементом.
Не все промышленные языки имеют встроенную поддержку связного списка как структуры данных. Впрочем, его нетрудно реализовать самостоятельно как класс или структуру. Для комфортной работы с релевантными алгоритмами мы добавим встроенные двунаправленные связные списки уже в базовое определение языка Hi.
Для начала создадим экземпляр нашего экспериментального списка:
VAR list = <"I", "will", "be">В примере выше для трех узлов автоматически создаются двунаправленные ссылки.
Связанный непустой список в языке Hi всегда имеет один узел, который является текущим или «активным». По умолчанию это последний добавленный элемент, то есть сейчас это «be». Проверим это:
PRINT list.current # печатает "be"Добавим в наш список еще два элемента:
list.insert "back", "!" # теперь list включает элементы: "I", "will", "be", "back", "!"Встроенный метод insert добавляет новые элементы сразу после активного узла, автоматически выстраивает новые связи и делает текущим последний добавленный элемент (добавить и сделать первым новый узел списка можно методом insertFirst).
Удаление осуществляется похожим образом для текущего элемента:
list.remove # list включает элементы: "I", "will", "be", "back"Впрочем, можно сразу удалить и несколько элементов, для этого нужно предварительно установить указатель на первый удаляемый узел:
VAR secList = list
secList.prev 2
secList.remove 2 # secList сейчас включает элементы: "I", "back"При этом узел, предыдущий перед удаляемым, становится текущим. Если удаляется первый элемент списка, то текущим становится новый первый элемент.
Можно заменить текущий узел на другой, просто присвоив элементу новое значение:
secList.сurrent = "smile" # secList включает элементы: "smile ", "back"Удалить все узлы, то есть сделать список пустым можно так:
secList = <>Переходить на первый и последний узел удобно следующим образом:
list.first
LET last = list.last # одновременно мы присваиваем новой константе значение активного элементаТаким образом можно достаточно легко осуществлять разнообразные операции со списком:
PRINT list # печатает "I", "will", "be", "back"
list.first
list.next
list.insert "not"
LET be = listUpdate 12 October 2020: Продолжение статьи в комментариях здесь и здесь:
mSnus
Простите, не понимаю. Если у каждого элемента может быть всего один дочерний, то это просто упорядоченный массив, и там удобно, когда элементы пронумерованы, а работа только через current / next / insert выглядит неудобной. Если это все же дерево, то вообще непонятно, как этими методами обойтись..
SpiderEkb
Про Кнута, надо понимать, Вам не рассказывали :-)
Массив — это массив. А список это список. Вещи разные, каждая для своей цели.
Вот представте — у вас массив на 100 элементов. И нужно вам добавить туда 101-й. И не просто добавить, а вставить между 63-м и 64-м элементами. Представьте к чему это приведет — realloc + memmove. И хорошо, если это 100 элементов, а не 100 000 или 1 000 000…
Нет, я понимаю, что есть фреймворк, там все это реализовано и все работает. Но надо же понимать что вы делаете и как ваши действия скажутся на производительности системы в целом.
А еще у банка есть процессинг — тот самый, что обеспечивает возможность клиентам расплачиваться пластиковыми картами в магазине. С точки зрения сервера это некая внешняя система, которая посылает запросы, на каждый из которых нужно дать ответ, уложившись в таймаут (не уложишься в таймаут — клиенту не дадут расплатится пластиком в магазине т.к. «нет ответа от банка»).
И тут я, такой весь умный и прошаренный в использовании различных фреймворков (но абсолютно не интересующийся а как оно там внутри устроено — мне это не нужно), пишу еще один процесс, 1 001-й. Процесс сложный, объемный. Для облегчения своего труда я использую очень навороченный фреймворк с реализацией динамических массивов и всего такого. А массивы у меня огромные — несколько сотен тысяч элементов.
И все получается красиво и элегантно. И главное модно — самый крутой фреймворк использую.
Но при установке на прод вдруг выясняется, что в периоды пиковой нагрузки мой процесс начинает жрать ресурсы как не в себя. Что приводит к замедлению других 1 000 процессов и периодическому отваливанию процессинга по таймаутам. А в результате сотни тысяч
лемминговклиентов, пытающихся расплатиься в магазине пластиком моего банка получают отлупы — «нет ответа от банка» и роются по карманам в поисках кеша, зовут на кассу всемогущую «Галю» для отмены покупок т.п.В итоге вызывают меня, умного и прошаренного, на комиссию по инцидентам и спрашивают строго — считаю ли я свою квалификацию соответствующей занимаемой должности. Ибо инцидент, произошедший по моей вине, в пределе тянет на отзыв у банка лицензии ввиду «неисполнения обязательств перед клиентами» (а как минимум штраф от регулятора со многими нулями).
Пример утрирован и гипертрофирован, но толика смысла в нем есть.
mSnus
Вы знаете, спасибо за экскурс в основы программирования, но мне казалось — мы тут говорим об очень высокоуровневом языке, на котором ещё и будет легко писать.
И в таком случае мне всё равно, как там «под капотом» реализованы массивы, коллекции, слайсы, списки и прочие «объекты, реализующие интерфейс IEnumerable».
Из этой статьи вы совершенно не знаете, как это реализовано и как скажется на производительности в целом. Может, там под каждый элемент списка выделяется чанк в 16Кб, на всякий случай? ))
Даже если это именно список, не иметь возможности взять из него 5-й элемент, или элементы с 1-го по 5-й без дополнительных велосипедов — нонсенс. И это должно быть на уровне языка, а не фреймворка, особенно если задумываться-таки о производительности и эффективности.
SpiderEkb
Постановка вопроса «а зачем списки когда есть массивы» подразумевает необходимость такого экскурса.
Я привел пример что бывает когда «мне все равно как оно внутри устроено».
Нет, на определенном уровне и для определенных задач оно прокатывает. До поры до времени.
Жопа — самый универсальный интерфейс ибо через нее можно сделать абсолютно все.
Суть списка в его динамичности. Он всегда занимает ровно столько памяти, сколько нужно под хранение текущего количества элементов. А каждый элемент занимает ровно столько памяти, сколько нужно для хранения его данных + связей с соседями. В этом кардинальное отличие списка от массива.
Если вам надо хранить разнородные элементы:
целое 2 байта
целое 4 байта
целое 8 байт
вещественное 8 байт
строка от 1 байт и более
то элемент списка будет выглядеть так:
тип элемента (целое, вещественное, строка) — допустим, 1 байт
размер элемента — допустим, 4 байта
данные элемента — N байт
связи (следующий, предыдущий) — 4+4 байта
Итого, N + 13 байт
Если все то же запихивать в массив, то там все элементы должны быть одного размера. И тогда вы, во-первых, должны ограничить максимальный размер строки, в-вторых, хранить, скажем, 2 байта целого в элементе максимального размера.
Способы есть. Другое дело, что в большинстве случаев это не нужно. Я лично достаточно широко использую обычные двусвязные списки там, где рандомный доступ к элементам не требуется. Например, когда нужно собрать большое количество данных из разных источников, а потом обработать их (так или иначе). Сначала добавляем все данные в конец списка, затем просто проходим от первого элемента к последнему.
Если мне нужен поиск по списку, я буду использовать SkipList для пар «ключ-данные». Обычно использую это для разного рода кешей (например, когда из одной и той же таблицы в разных местах и в разное время нужно читать по ключу примерно одни данные — единожды прочитанный ключ заносится в кеш и второй раз из таблицы уже не читается.
Вот это совсем не факт. Ибо что там с производительностью на уровне языка тоже большой вопрос. Мне часто приходилось отказываться от универсальных реализаций на уровне разных фреймворков и библиотек в пользу собственной реализации под конкретную задачу именно потому что универсальная реализация в силу своей универсальности проигрывала частной, построенной с учетом специфики конкретной задачи.
Но у меня так сложилось, что все, что делал за последние 25+ лет, имело повышенные требования к эффективности и скорости. Порой на уровне паранойи.
mSnus
Простите, а что мешает реализовать массивы так, чтобы «под капотом» это была просто последовательность указателей на данные произвольной длины? У вашего списка явная проблема — чтобы добраться до 1000 элемента, надо пройти всю цепочку, чтобы от этого избавиться — к нему надо добавлять индекс, в результате придём опять к массиву. Ваш SkipList, как я понимаю, примерно тем и занят?
Да, для массива целых чисел (и других данных или структур фиксированной длины) можно пытаться размещать сами данные подряд в памяти, а не указатели на них. Но тут начнутся проблемы с поиск подходящего куска подряд свободной памяти, и тут снова придётся возвращаться к индексу/массиву указателей.
Но мы говорили о высокоуровневом языке, где эти подробности и «подкапотное» излишне. А вот задача быстрой выборки нужных элементов очень частая. Поэтому я так удивился, что встроенных средств для этого нет.
SpiderEkb
Согласен. Ничего не мешает.
Да. Поэтому списки используются там, где не нужно «добираться до 1000-го элемента».
А массивы там, где заранее известно сколько будет элементов всего и известно, что время жизни элемента совпадает со временем жизни массива. Т.е. где не будет операции «удалить элемент 563, а потом вставить три элемента в начало списка».
Фактически на списках легко реализуются такие примитивы как стек или очередь. Надеюсь, знаете что это такое и зачем.
SkipList не мой. Чем он занят можно понять из оригинальной статьи автора алгоритма (это первая статья с описанием базового принципа, есть дальнейшее развитие алгоритма описанное как самим автором, так и другими людьми).
Работает очень быстро:
Среднее время вычислялось по 100 000 замерам.
Время в микросекундах. Разброс значений обусловлен отчасти вероятностным характером самого алгоритма, отчасти средой выполнения — сервер, на котором одно временно работает очень много процессов и загрузка которого постоянно меняется.
Проблемы с массивом начнутся сразу же, как только вам потребуется вставить 10001-й элемент в середину массива, рассчитанного на 10000 элементов.
Увы, но как только вы столкнетесь с жесткими требованиями к эффективности, знания о том как это работает под капотом становятся весьма актуальными.
Частая. Согласен. Только в моих задачах потребность формулируется обычно так — «выбрать из списка строки, начинающиеся на 'ASKJHS'» (например). как тут может помочь массив — ума не приложу.
Что касается «встроенных средств» — не надо пихать в язык все подряд. А то кому-то потребуется список, а кому-то тройной эллиптический интеграл. Все эти вещи реализуются внешними библиотеками.
А вот сортированный список, построенный на алгоритме SkipList (модификация в том, что нет выделенного ключа — сами данные являются ключом) работает на ура.
Массивы хороши когда это захардкоженная таблица каких-то справочных значений (ну например, таблица предрассчитанных значений какой-то сложной функции где индекс массива является производной от агрумента).
А когда вам надо закешировать выборку из БД, выполненную по некоторому индексу, а потом искать в ней данные (вместо того, чтобы опять лезть в БД), тут массивы ну никак не помогут — ни размер выборки неизвестен, ни поиск по данному значению ключа в массиве неэффективен.
Т.е. опять — массив это массив, список это список. Разные сущности для разных задач.
mSnus
Спасибо за такой развернутый ответ!
Единственное — не логичнее все же стек делать на базе массива? Как-то он проще кажется для такой задачи… или вы имеете в виду стек произвольной длины?
SpiderEkb
Ну тут от задачи зависит. Есть ситуации где максимальная глубина стека заранее известна — там массив будет проще (и эффективнее).
Если же максимальна глубина стека неизвестна (например, разбор некоторой математической формулы с переводом в обратную польскую нотацию для последующего ее вычисления) — предпочтительнее сделать стек на списке.
Аналогично с очередями (например, для батчмашины) — динамический список в котором новый элемент всегда добавляется в начало очереди, а берутся элементы всегда из конца очереди (и при этом удаляются). Такое применяется при распараллеливании обработки больших объемов данных.
Есть процесс-мастер. Он занимается формированиями пакетов-заданий на обработку. После старта мастер запускает несколько процессов-обработчиков и создает очередь заданий.
Задания формируются мастером и помещаются в начало очереди (т.е. добавление в начало списка). Каждый обработчик берет задание из конца очереди (при этом оно удаляется из очереди) и выполняет его. Следующий обработчик опять берет задание из конца и выполняет… Как выполнил задание — берет следующее и так далее, пока очередь не опустеет. На практике когда заданий больше нет, мастер выкладывает в очередь несколько (по количеству обработчиков) «заглушек» — пустых заданий.
Очередной обработчик берет из очереди задание, видит что это «заглушка» и завершает работу.
Мастеру остается только дождаться пока очередь не станет пустой (это значит что все задания выполнены, все «заглушки» получены и все обработчик завершили работу), удалить очередь и самому завершить работу.
На массивах такое тоже можно (организовав массив в виде кольцевого буфера), но придется еще контролировать наличие свободного места в массиве и держать индексы первого (куда добавлять новое задание) и последнего (откуда брать задание) элементов.
Впрочем, такая организация (кольцевой буфер) используется там, где память сильно ограничена (например, различные микроконтроллеры — те же очереди отправки пакетов на хост или приема пакетов от хоста — там такой подход оправдан).
smurfomen
Массив — непрерывная область памяти, отсюда и название. Элементы списка могут лежать вообще где угодно, но элементы знают о своих соседях (как — зависит от направленности списка).
Если хотя бы чуть чуть в С могете, то поймете, почему в массив добавить элемент дороже чем в список. И почему доступ к злементу списка дороже чем, из массива. Причем в обоих случаях стоимость прямо пропорциональна размеру.
mSnus
Окей, но массив указателей — тоже массив?
smurfomen
Коротко — разумеется да.
Указатель — такая же область памяти как и любая другая переменная. У него есть стандартный размер — машинное слово — соответствующий разрядности адресной шины. Обычно, ширина адресной шины определяет размер машинного слова, например если ширина 64бит то и размер машинного слова будет 64бита, т.е. 8 байт.
Массив или список это способ хранения каких-либо данных одного размера, а не какая-то фича конкретного языка.
В случае массива, указатели будут лежать согласно Array Padding для вашего ЯП. В зависимости от реализации, они могут иметь выравнивание по наибольшему или по размеру машинного слова.
Со списком вы имеете разбросанные по памяти ноды из указателей, каждый из которых указывает на соседей и хранимое значение.
Mikluho
У вашей реализации связного списка как минимум две проблемы:
1. Очень бедный api. Как найти элемент в списке? Как вставить значения перед текущим элементом? Как получить значение предыдущего/следующего элемента, не меняя указатель на текущий?
2. Очень плохо, что методы, обозначенные существительными, что-то меняют.
Да и вообще, путаница между существительными и глаголами сразу сводит на нет удобство читаемости языка. Вместо того, чтобы «легко читать» листинги, придётся заучивать нелогичный api.
SergeKotov Автор
1. Реализации пока нет (см. коммент ниже), в экспериментах это выглядело примерно так:
Примеры #2 и #3 выглядят симпатично но имеют некоторые нерешенные вопросы
2. first, next, prev, last это команды действия, передвигающий указатель на текущий элемент списка — current (фактически это указатель, работающий снаружи списка как property в экземпляре класса)
SpiderEkb
Не очень понятен смысл реализации всего этого непосредственно в языке.
Тут сразу встанет вопрос — а почему в языке реализован список, но не реализованы деревья во всем их многобразии? Дальше кому-то захочется алгоритм, скажем, фильтра Калмана еще кому-то регрессию, хотя бы линейную и т.д. и т.п.
И что из всего этого тащить непосредственно в язык?
В моем понимании язык это некоторая база, которая позволяет делать все остальное. А вот это «все остальное» — это уже расширения в виде библиотек различной направленности.
SergeKotov Автор
Язык, который мы используем определяет характер нашего мышления. Эффективный язык должен доносить сообщение адресату с минимумом затрат на формирование самого сообщения.
Для языка программирования целесообразно включить полный сет встроенных возможностей для целевого использования, следовательно, например, язык, предназначенный для расчетов с математической статистикой должен иметь все необходимые встроенные методы работы с ней, чтобы не искать фреймворки на стороне (в довесок возможно еще иметь конкуренцию фреймворков, риски поддержки) или программисту не собирать из кода велосипед.
Как пример полезной эволюции языка. В ранних версиях Swift не было встроенной поддержки генерации рандомных чисел. Приходилось или подключать свою оболочку, или GameplayKit или использовать в коде довольно тяжеловесные конструкции c конверсией типов из UInt32 вида:
В версии 4.2 появилась встроенная поддержка:
Стало логично и гораздо удобнее. Язык вроде как усложнился, а программисту стало проще.
Причина экспериментов с linked list здесь на самом деле другая. Язык Hi конструируется с прицелом на гораздо более широкое применение в будущем, чем просто быстро программировать несложные задачи для начинающих в алгоритмическом стиле с дружелюбным environment.
Чтобы нам спроектировать будущий язык целесообразно [и попутно выполнить декларацию полной выполнимости исходного текстового кода в будущем], нужно пытаться на существующем языке реализовать сложные концепции, для которых он пока еще не предназначен. На примере linked list и еще некоторых примерах стало понятно, что c optionals лучше работать, чем их не иметь в языке даже в базовой версии. Соответственно теперь задача так их интегрировать в выразительные средства, чтобы было логично, просто, надежно. Работа с optionals требует продумывания обработки ситуаций с nil и т.д.
Концептуально создавать простой и понятный, функционально удобный язык очень непросто. Это означает, что в значительной мере сложность задач уходит от программиста к дизайнеру языка.
SpiderEkb
Хорошо. Тогда в чем его преимущество перед остальными? Где он будет применяться, кто будет на нем писать, кто будет поддерживать уже написанное года через 3 хотя бы? Кто будет его развивать? И, главное, кто будет отвечать перед пользователями за возможные проблемы с языком и оперативно их решать?
Вот именно. И это, в том числе означает что не надо в язык пихать сущностей сверх необходимого («бритва Оккама»). Посмотрите на тот же С++ — есть сам язык, содержащий минимальный набор типов и инструкций и есть библиотеки. Как рантайм, так и STL (фактически являющаяся частью стандарта).
SergeKotov Автор
Диалектика для «бритвы Оккама» здесь в том, что сам C++ в том числе с помощью механизма множественного наследования является почти идеальным генератором сущностей и без особой
необходимостипродуманности в том числе.SpiderEkb
Эти сущности генерируются вне самого языка. В том и суть — разработчику дается мощный инструмент, который он может использовать по своему усмотрению.
А если Вы изначально хотите ограничить мощность инструмента дабы разработчик, не дай бог, себе в ногу не выстрелил, то это будет очередной учебный недоязык, заранее обреченный на провал в плане промышленного использования.
SergeKotov Автор
Это как раз не беспокоит. Говоря метафорами, наша будущая цель не дать вместо совка лопату [для промышленного использования], а предоставить робота с лопатой. И более интересует, чтобы робот не воткнул лопату в электрический кабель.
SpiderEkb
У вас есть хоть какое-то техническое обоснование всего этого?
Мой личный опыт говорит о том, что любая успешная разработка начинается с обоснования ее необходимости. У нас это называется BRD — задание на разработку, в котором описываются бизнес-требования того, что хочется получить и зачем все это нужно.
Дальше идет согласование BRD, которое гарантирует что требования реальны и обоснованы.
Далее, на основе BRD пишется FSD — это уже ТЗ для разработчика. В нем описывается архитектура и конкретные алгоритмы как что будет реализовано. Оно тоже согласуется — тут получаем гарантию непротиворечивости, эффективности и прочего.
И только после этого начинается собственно разработка.
С момента начала разразботки BRD и FSD фиксируется. Т.е. никакого «ой, а мы тут забыли...» от заказчика и «опа! а мы тут еще классную фичу придумали!» от разработчика. Такие вещи делают проект незаканчивающимся никогда. Более того, такие вещи легко могут порушить архитектуру проекта, которая изначально была выстроена под вполне конкретный набор требований.
Когда разработка закончена, начинается тестирование. Сначала компонентное — соответствие продукта требованиям FSD. Потом бизнес — соответствие требованиям BRD. Потом нагрузочное — эффективность. У нас еще интеграционное есть — взаимодействие с остальными компонентами системы.
Такая схема гарантирует что вы получите какой-то рабочий продукт в конечные сроки.
Но все идет от BRD — что вы хотите получить и зачем все это нужно.
Т.е. для себя вы должны определить чем ваш язык будет лучше других (и почему).
Основной риск тут в том, что вы его сейчас сделаете, а потом ваша команда разбежится и все, на нем написанное превратится в легаси, которое следующая команда будет переписывать полностью. Т.е. скатиться в хреносозидательство по причине обострения чешижопицы тут как с добрым утром.
SergeKotov Автор
То, что вы описали выше я и сам не раз объяснял юным поклонникам Agile, как технологию организацию работ в крупной компании, для которой критична надежность работы корпоративного ПО в режиме эксплуатации.
Впрочем, не всегда водопадный подход работает хорошо даже для крупных проектов. Например, разработка игр. Дело в том, что нельзя создать заведомо качественный BRD для инновационной игры, потому что слишком много неизвестного. Здесь целесообразна итерационная разработка и эксперименты с прототипами. Иногда в процессе создания игры полностью меняется исходный концепт и почти всегда он частично трансформируется. Иногда приходится досрочно завершать разработку, потому что исходные гипотезы не подтверждаются. В книгах по гейм-дизайну, это детальнее описано, например The Art of Game Design: A Book of Lenses (книга вроде есть в русском переводе).
Но в любом случае спасибо, что вы так беспокоитесь и всегда приятно читать хорошо продуманные и изложенные тексты, впрочем,
несколько портит впечатление.
SpiderEkb
Все что пишу — выстрадано опытом.
Пришел к этому еще когда работал в одной маленькой, но гордой компании (фактически это начиналось как стартап, но тогда таких слов еще не знали), хотя проект был большой и весьма серьезный.
Сейчас это просто стандарт там, где работаю. Но тут цена ошибки очень велика. Любое падение прома — это инцидент, который выносится на комиссию. Серьезное падение, приводящее к недоступности для внешних систем (тот же процессинг) — это уже грозит штрафом от регулятора. А в особо тяжелых случаях можно и лицензию потерять с формулировкой «неисполнение обязательств перед клиентами» (вероятность крайне мала, но все же...).
А недоступность для внешних систем может случиться просто по причине резкого падения производительности из-за какого-то модуля, который начал вдруг жрать ресурсы как не в себя. Посему, эффективность у нас на уровне паранойи — любой код всегда анализируется на предмет «а можно ли сделать лучше». Ну и нагрузочное тестирование обязательно.
В общем, я примерно себе представляю что нужно сделать чтобы получить надежный и эффективный продукт.
В вашем случае (разработка языка) все еще сложнее. Ибо если использование вашего продукта в серьезном проекте приведет в факапу с материальным ущербом, все шишки повалятся на вас.
Хотя скорее всего, сторонние команды не будут использовать продукт, для которого не гарантирована серьезная круглосуточная поддержка.
А иначе, увы, не скажешь. Когда делается непонятно что непонятно зачем и непонятно для кого, просто потому что в голову ударило. Такие проекты мертворожденные изначально.
SergeKotov Автор
А вот сформулировали же по другому :-)
В первой работе указано назначение языка. Полагаю, с точки зрения документов вида BRD оно выглядит нелепо. Но внутренняя логика есть, она неочевидна, так как основана на своеобразном исходном концепте, примера реализации которого, наверное, на данный момент еще нет.
Поживем, увидим. В любом случае это интересно делать.
SpiderEkb
Я имел ввиду когда что-то делается непонятно зачем, просто от нечего делать.
Извините, но язык, позволяющий строит очень сложные системы, но не поддерживающий внешние библиотеки — это нонсенс. Вы очень быстро наткнетесь на то, что нужно или подключать внешнюю библиотеку, или до бесконечности раздувать сам язык для поддержки все новых и новых алгоритмов.
Да еще и интерпретатор… Любая сложная система рано-поздно сталкивается с проблемой эффективности и быстродействия. Или начинает тормозить.
Претензии на некий искусственный интеллект подразумевает (в моем понимании) поддержку нейросетей, элементов нечеткой логики…
Я бы обратил внимание на Prolog особенно, на Visual Prolog и начал бы плясать оттуда, а не изобретать велосипед с нуля.
SergeKotov Автор
Парни, это же шутка — начиная с даты и точного времени этой публикации (сегодня же пятница) и до последнего statement.
Шутка над поклонением сарафанным представлениям (передаю очередной привет уважаемому мной Тьюрингу), шутка над изящной реализацией LinkedList в Java, шутка над дотошными читателями habr, что иногда парсят твой код в поисках нестыковок дотошней, чем старый профессор в универе, не догадываясь о вложенной мета-семантике в примерах, etc.
Конечно, переходить от элементарных типов данных к linked list нам здесь не нужно — концепт предполагает абстракцию от памяти и архитектуры компьютеров, хотя сама идея непривязанной к линейному пространству ленты с ячейками и логической головкой записи / чтения — удобная для специальных случаев.
Задачи и эксперимент на трех коротких публикациях завершен, далее на русском языке не планирую, пока будем работать в тишине и удалении.
P.S. Благодарю SpiderEkb за простое и компетентное объяснение идеи списков. Не могу поставить плюсик, так как не хватает местной «кармы». Зарабатывать мега-карму habr душещипальными историями на тему «наших бьют» не интересно, лучше продолжу учить машины смеяться, а то скоро люди, кажется, перестанут.
Mikluho
Вы в вашей шутке забыли про лопату.
Лично мне концепция показалась интересной. Мне захотелось её понять. А тут такое… нелогичное.
SergeKotov Автор
Хорошо, подготовлю концепцию отдельно в качестве комментария. Потребуется несколько дней.
SergeKotov Автор
done
smurfomen
Логика такого списка контр-интуитивна.
1) зачем в списке членом хранить итератор (или что у вас там?) на какой-то элемент? В первом примере вы с таким же успехом могли вызвать last.
2) такой список не выглядит консистентным. Вместо такого «дубового» подхода логичнее использовать отдельный итератор, с методами next, prev и т.д.
3) методы insert и insertFirst семантически не соответствуют, у вас должно быть тогда insert i, pushFront, pushBack
SergeKotov Автор
Идея использования внешнего итератора для возможного переопределения его поведения разработчиком объяснима, но точно не является простой и понятной, тем более для концепции этого языка.
Инкапсуляция в список (то есть цепь статичных объектов с указателями друг на друга) специальных методов работы с отслеживанием текущего и предыдущего состояния, а также встроенной поддержкой указателей на отдельные интересные узлы очень удобна, особенно для списков очень большой величины, которые используются как динамичная очередь с началом и концом.
SergeKotov Автор
По просьбе читателей в дополнение к основной статье уточним некоторые детали исходно шуточной идеи концепта реализации linked list.
Связный список может содержать элементы одного типа или разных типов.
Объявление списка с инициацией можно делать через присвоение начальных значений с заданным сетом элементов.
Каждый конкретный экземпляр списка в каждый момент существования объекта инкапсулирует структуру данных, указатель на текущий узел и специальные методы работы со списком.
Рассмотрим их на примере. Допустим мы хотим создать свой список чтения интересных постов и статей по программированию. Так как мы имеем только одну голову, то есть можем читать в один конкретный момент времени только один элемент, определим некоторый порядок чтения, одно за другим. Обычно новые статьи мы помещаем в конец списка, впрочем, при появлении интересной работы по нашим тегам мы можем поместить её, допустим, ближе к началу списка. Прочитанные статьи, в том числе и из середины списка удаляем. Так как в мире сейчас писателей больше, чем читателей, то наш список может быть о-очень большим.
Создаем начальный список с самой интересной работы:
В первую очередь нам нужны методы по добавлению (insert) и удалению (remove) узлов.
Стоп. Последний пост нас не интересует, удалим его.
То есть наша реализация списка всегда имеет встроенный указатель на текущий, активный узел. Похожим образом в итерационных циклах мы имеем активный элемент node в конструкциях с итератором вида:
Логика работы insert и remove описана в основной статье.
В любой момент времени для не пустого списка мы может получить как сам объект, так и ссылку на него для быстрого доступа.
Ссылку мы можем использовать позднее, когда после добавления, удаления, перемещения элементов списка, решим вернуться к узлу. Разумеется, ссылка на ранее удаленный элемент списка не приводит к run time error, а переводит list.current в NIL.
Количество таких ссылок неограниченно, мы можем сделать что-то вроде мета-списка избранного чтения, допустим 100 лучших статей из нашего списка, включив линки, например, в линейный массив.
Если нам нужно заменить один элемент на другой, то мы делаем это как с property экземпляра класса в некоторых языках:
Встроенные методы для linked list включают следующие команды (прям как в музыкальном плейере):
Важное уточнение. Все команды выше могут использоваться как процедуры и как функции, возвращая релевантный элемент списка, например так:
Это как на книжной полке, мы не просто перебираем корешки книг, но сразу получаем в руки каждую из них. Если не нужна – ищем дальше, нужна – убираем с полки и кладем в карман.
В принципе, ничего не мешает нам также сделать что-то вроде словаря из отдельных tuple:
Mikluho
Ну допустим, что ваш список похож на машину Тьюринга. Возможно, это даже забавно.
Но всё равно, почему бы для обозначения действий не использовать глаголы?
SergeKotov Автор
Ак как вы предлагаете именовать, допустим, list.next?
Mikluho
Да хоть бы и list.GotoNext. Или MovetoNext
SergeKotov Автор
В таком виде IMO cкорее усложняет прочтение, чем делает яснее.
Использование Goto сразу оживляет призрак Дейкстры (не путать с Дийкстра из Ведьмака) с топором в руках