Введение в программирование на Лиспе



     Andractim gel подробности на сайте. |         

Структуры данных


Любые структуры данных строятся из более простых составляющих, простейшие из которых – элементарные данные. В Лиспе элементарные данные называют атомами. Для начала примем, что атом – это последовательность из букв и цифр, начинающаяся с буквы.

A Nil ATOM LISP Занятие2 Новый_год ВотДлинныйАтомНуОченьДлинныйНоЕслиНадоАтомМожетБытьЕщеДлинннее Ф4длш139к131б

Пример 3.1.

Одинаково выглядящие атомы не различимы по своим свойствам. Термин "атом" выбран по аналогии с химическими атомами, строение которых – предмет другой науки. Согласно этой аналогии атом может иметь достаточно сложное строение, но атом не предназначен для разбора на части базовыми средствами языка.

Более сложные данные в Лиспе выстраиваются из одинаково устроенных бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти, выделяемому системой программирования при организации и обработке структур данных. Выделение блока памяти и размещение в нем пары данных выполняет функция CONS (от слова consolidation), а извлечение левой и правой частей из блока выполняют функции CAR и CDR соответственно ("content of address part of register" , "content of decrement part of register").

ФункцияАргументыРезультат
Cons

Атом

X

( Атом . X )
Car( Атом . X )Атом
Cdr( Атом . X )X

При работе с системой соответствующие выражения показаны ниже:

ФункцияАргументыВид для системы
Cons

Атом

X

(CONS 'ATOM ' X )
Car( Атом . X )(CAR '(ATOM . X )
Cdr( Атом . X )(CDR '(ATOM . X )

Типичная форма записи символьных выражений называется списочной записью (list-notation). Элементы списка могут быть любой природы.

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

По соглашению атом Nil выполняет роль пустого списка. Бинарный узел, содержащий пару атомов ATOM и Nil, рассматривается как одноэлементный список (ATOM ) :


или для наглядности:


Если вместо атома "ATOM" подставлять произвольные атомы, а вместо "Nil" - произвольные списки, затем вместо атомов - построенные списки и так далее, то мы получим множество всех возможных списков.


Содержание  Назад  Вперед