Может ли кто-нибудь дать обзор того, как связанные списки, например, в LISP, представлены в память компьютера? Использует ли компьютер регистры процессора, чтобы удерживать указатели на голове и остальной части списка или на куче, что используется?Представление связанного списка, например, в lisp
Это сильно зависит от используемого конкретного компилятора и языка исполнения. Однако в общем случае структуры данных в Lisp-подобных языках представляют собой ячейки, выделенные кучами, с указателями на своих соседей. Затем они загружаются в аппаратные регистры, когда функции работают с данными.
Рассмотрим связанного типа списка в Haskell:
data [a] = [] | a : [a]
Данный список может быть записан как:
1: (2: (3: (4: (5: []))))
или более сжато:
[1,2,3,4,5]
Это представлено в виде кучи-Alloc ованный объект формы:
, где стрелки представляют указатели; и (:) представляет собой «cons cell», небольшую структуру, в которой хранится указатель на текущий элемент и хвост списка.
Теперь, когда функция обращается к этой структуре данных, она будет загружать указатели на структуру в регистры и запускать загрузку данных из этих указателей. Точные сведения о них зависят от модели компиляции и модели системы времени исполнения. Например. для GHC Haskell это задается STG Machine. Кроме того, младшие биты в указателях могут использоваться для указания на конкретный конструктор, на который указывают; его оценка (оцененная или неоцененная) и даже сама ценность, если она небольшая (это pointer tagging optimization).
Зависит. Stackoverflow лучше, если у вас есть настоящая проблема.
«LISP» - это большое семейство языков и сотни различных реализаций.
Пробуятся всевозможные способы реализации связанных списков.
Есть книги о реализации Лиспа, и есть много небольших и больших версий Lisp с открытым исходным кодом для изучения.
Соответствующая литература можно найти, например, здесь: http://library.readscheme.org/page8.html
Для таких философских вопросов о Лиспе один из самых вдохновляющих источников - Anatomy of Lisp. Даже если он немного устарел. Чтение его (ну, много лет назад) было для меня просвещением не только о Лиспе, но и о программировании в целом. Еще одна отличная книга о реализации Лиспа - Lisp in Small Pieces. Если вы серьезно относитесь к изучению внутренних функций Lisp, эти два помогут вам многое.