Данные
Любые структуры данных начинаются с элементарных значений. Следуя Лиспу, в функциональном программировании такие значения называют атомами или символами. Внешне атом обычно выглядит как последовательность из букв и цифр, начинающаяся с буквы. В первых реализациях Лиспа было принято ограничивать длину атома, но ограничение было не слишком жестким (30 литер). Теперь ограничивают лишь число значащих литер (порядка 60), по которым атомы распознаются как различимые объекты с помощью хэш-таблицы объектов.
A ATOM ВотВесьмаДлинныйАтомНоЕслиНадоМожетБытьЕщеДлинннее Ф4длш139к131б
Одинаково выглядящие атомы не различимы по своим свойствам, хотя проявления этих свойств могут быть обусловлены контекстом использования атомов. Термин "атом" выбран по аналогии с химическими атомами. Согласно этой аналогии атом может иметь достаточно сложное строение, но оно не рассматривается как обычное S-выражение. Устройство атома реализационно зависимо и лишь соответствует некоторой спецификации, содержание которой будет рассмотрено в девятой лекции. Атом не предназначен для разбора на части базовыми средствами языка.
Более сложные данные выстраиваются из унифицированных структур данных — одинаково устроенных блоков памяти. В Лиспе это бинарные узлы, содержащие пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти, выделяемому системой программирования при организации и обработке структур данных. Выделение блока памяти и размещение в нем пары данных выполняет функция CONS (от слова consolidation), а извлечение левой и правой частей из блока выполняют функции CAR и CDR, соответственно. (В других языках функционального программирования используются векторы, кортежи, последовательности, потоки, множества, сети и другие структуры данных, обладающие достаточной гибкостью, т.е. способностью к организации единого доступа к любому числу элементов произвольного типа.)
CONS =>> [CAR | CDR]
Бинарный узел, содержащий пару атомов ATOM и Nil, рассматривается как одноэлементный список:
(ATOM) = [ ATOM | Nil ]
Если вместо атома ATOM рекурсивно подставлять произвольные атомы, а вместо Nil — произвольные списки, затем вместо ATOM — построенные списки и так далее, то мы получим множество всех возможных списков. Атом Nil играет роль пустого списка и фактически эквивалентен ему. Можно сказать, что список — это заключенная в скобки последовательность из атомов, разделенных пробелами, или списков.
ATOM (A B) (A B C D E F G H I J K L M N O P R S T U V W X Y Z) (C (A B)) ((A B) C) ((A B) (D C)) ((A B)(D(C E)))
Такая форма представления информации называется списочной записью (list-notation). Ее основные достоинства — лаконичность, удобство набора и отсутствие "синтаксического сахара". Она достаточно отражает взаимосвязи структур данных, размещаемых в памяти, и помогает задавать процедуры доступа к их компонентам.
Любой список может быть построен из пустого списка и атомов с помощью CONS, и любая его часть может быть выделена с помощью подходящей композиции CAR-CDR.
Функция CONS строит списки из бинарных узлов, заполняя их парами объектов, являющихся значениями пары ее аргументов. Первый аргумент произвольного вида размещается в левой части бинарного узла, а второй, являющийся списком, — в правой.
Функция CAR обеспечивает доступ к первому элементу списка — его "голове", а функция CDR — к укороченному на один элемент списку — его "хвосту", т.е. к тому, что остается после удаления головы.
Функция ATOM позволяет различать составные и атомарные
объекты: на атомах ее значение "истина", а на структурированных объектах — "ложь".
Функция EQ выполняет проверку атомарных объектов на равенство.
Различие истинностных значений в Лиспе принято отождествлять с разницей между пустым списком и остальными объектами, которым программист может придать в программе некоторый другой смысл. Таким образом, значение "ложь" — это всегда Nil. (Во многих языках программирования используется 0 – 1 или идентификаторы True — False и др.)
Если требуется явно изобразить истинностное значение, то для определенности в качестве значения "истина" используется константа — атом T (true) как стандартное представление, но роль такого значения может выполнить любой, отличный от пустого списка, объект.
