Как сделать пустой список в lisp

Обновлено: 06.07.2024

Сначала же Лисп оперировал только символами и списками (отсюда и название — List processor).

Символ — это имя, состоящее из букв, цифр и[ли] специальных знаков < [ ] >. Символ обозначает произвольный объект или явление из прикладной области, вспомогательные объекты внутри программы, или некоторую структуру исходного кода. Имя функции — это тоже символ. Символ всегда имеет значение (утверждение явно не верно, см. intern).

О подобной многозначности символа nil будет подробно сказано позже, когда будут обсуждаться списки, логические операции, функции…

Символы t и nil суть встроенные константы и не могут быть переопределены (действительно - зачем?). Константа - символ, имеющий постоянное значение. Константа определяется (переопределяется) с помощью директивы defconstant .

Вы всегда можете проверить, является ли некий объект символом (предикат symbolp) и узнать его имя (функция symbol-name) или значение (symbol-value). Вы уже могли догадаться об этом, если видели чуть выше маленький клочок кода :-) Более общим понятием является атом. атомы ≡ символы ⋃ числа.

Список - структура, состоящая из элементов, которыми могут быть атомы или другие списки.

— это списки. Список может не содержать элементов вовсе, такой список называется пустым и обозначается () или nil.

Список - это фундамент лиспа, ибо в зависимости от интерпретации список может представлять как данные, так и лисповый код. (symbol-value t) - тоже список.

Помимо вышеперечисленного, в лиспе есть еще тонна различных типов данных. Но у тебя, уважаемый читатель, уже есть достаточно знаний, чтобы перейти к изучению функций, что и советую сделать, прежде чем переходить к знакомству с другими типами данных. А у меня пока будет время, чтобы дописать этот раздел :-)

Точечная пара (она же "точечный список") - структура, состоящая из двух элементов, разделенных точкой. Выглядит это примерно так:

Первый элемент точечной пары называется головой, второй элемент хвостом. Конструировать точечные пары можно при помощи функции cons, у которой всего два аргумента - голова и хвост будущей точечной пары. Например, вызов (cons 1 2) создаст точечную пару (1 . 2). Функция cons не создает список, путем присоединения головы списка к ее хвосту, как пишут во многих учебниках и интернетах.

Как видно из примеров конструировать можно точечные пары, элементами которых являются точечные пары. Рассмотрим третий пример:

Как правило такие точечные пары записывают в более простом виде

Как видно, это выражение очень сильно напоминает известную нам структуру - список. Собственно, список и есть структура, состоящая из точечных пар. Если хвостовой элемент точечной пары nil, то, для краткости записи точка опускается и, например, из примера 4 получаем ('a). Что это? Правильно - список, состоящий из одного элемента. Аналогично и с примером 3: если, скажем, у нас вместо 9 будет nil:

то, для краткости избавляясь от скобочек получим

а для еще более краткой записи и опустим точку с nil:

Наша точечная пара приобрела вид списка из двух элементов. Например такая сложная пара (1 . (2 . (3 . (4 . nil)))) после всех проделанных последовательных упрощений записи (предлагаю читателю этим заняться самостоятельно), приобретет вид простенького списка (1 2 3 4).

И наоборот, можно любой список представить в виде точечной пары:

Итак, списки - это синтаксический сахар над точечными парами. Сами точечные пары могут быть использованы и как двухэлементные кортежи для создания, например, key-value хранилищ.

Привет, Хабр!
LISP заинтересовал меня уже давно, но, к сожалению, активно использовать свои знания и стремления на практике шанса не было. Скоро новый учебный год, а значит у меня опять будет возможность изучать и, уже второй год, преподавать студентам LISP. Еще одной проблемой, кроме традиционного отсутствия интереса к сложным вещам, кажется отсутствие литературы. Да и вообще, тема LISP-а в интернете, а тем более в рунете освещена слабо. Вот и на Хабре публикаций довольно мало.

Краткая история

LISP был придуман Джоном Маккарти в 1958 году для решения задач нечислового характера и базировался на трех основных китах: алгебре списочных структур, лямбда исчислении, теории рекурсивных функций. Долгое время LISP использовался исключительно узким кругом специалистов по искусственному интеллекту. Но, начиная с 80-х годов прошлого века, LISP начал набирать обороты и сейчас активно используется, например, в AutoCad и Emacs.

Формы представления программ и обрабатываемых данных в LISP идентичны и являются списочными структурами. В связи с этим открывается несколько интересных возможностей – например, обработка программой других программ. Не говоря уже об универсальности, расширяемости и масштабируемости самого синтаксиса. Ядро LISP, написанное на LISP, занимает менее 200 строк, а интерпретатор ПРОЛОГа – чуть более 50 строк.
Реализация списков позволяет не задумываться об управлении памятью, резервировании и освобождение ячеек происходит динамически. Таким образом можно говорить о появлении сборщика мусора уже в первых версиях LISP.
LISP не является строго типизированным языком программирования. Сегодня это мало кого удивит, однако стоит напомнить, что на начальным этапах данная концепция противостояла строготипизированному Фортрану.
Префиксная нотация дает широкие возможности для синтаксического анализа выражений, а так же обеспечивает возможность использования единого списочного контекста для программ и данных.
Использование огромного количества скобок. Именно поэтому наряду с традиционной расшифровкой LISP (LISt Processing) существует и Lots of Idiotic Silly Parentheses.
Не следует забывать про существования LISP-машин – вычислительных машин, архитектура которых оптимизирована для эффективного выполнения программ на языке LISP. LISP-машины не слишком распространены, по некоторым данным их количество во всем мире не превышает 10000. (Насколько мне известно, в Украине нет ни одной. Лично я видел за свою жизнь лишь одну – в Бухарестском университете, активно используемые на лабораторных работах студентами). LISP-машины исследовательского центра Xerox стали прародителями некоторых распространенных идей и технологий: сборка мусора, лазерная печать, многооконные системы и т.д.). Надеюсь, у меня появится шанс поговорить об этом подробнее в одном из следующих выпусков.

Типы данных

Традиционно в LISP рассматривают два типа атомов: символы и числа. Символы могут обозначать числа, строки, сложные структуры, функции и другие объекты. Ограничения на имена символов зависят от используемого диалекта, но большинство из них не накладывает практически никаких ограничений на используемые в именах символы. Кроме того, опять же в большинстве диалектов, имена символов не зависят от регистра.
Некоторые символы имеют специальное назначение – это константы, встроенные функции, T (true, истина) и NIL (false, ложь).

Числа, в отличии от символов, не могут представлять другие объекты, таким образом число всегда является константным числом. Немного позже мы рассмотрим типы чисел в LISP.
Символы и числа представляют собой наиболее простые объекты LISP – атомы. Второй основной тип данных – точечные пары, которые синтаксически выражаются следующим образом:

Например, точечными парами являются выражения:

Атомы и точечные пары объединяют под общим названием S-выражения (S-expression, symbolic expression). Особым видом S-выражения является список, выражаемый следующим образом:

NIL в большинстве случаев определяется как пустой список, в таком случае определение списка можно переписать следующим образом:

Крылья, ноги… Главное хвост

И голова и хвост являются ключевыми понятиями в списочном контексте LISP. Первый элемент списка именуется головой списка, все остальные элементы – хвостом. Для работы с головой и хвостом существует набор базовых функций, рассмотренный немного ниже.
Пустой список эквивалентен паре пустых скобок:
NIL ().
Непустой список, состоящий из элементов a1, a2, a3… в соответствии с правилами записи S-выражений может быть записан следующим образом:

В LISP список можно записать и последовательностью элементов, заключенных в скобки и разделенных пробелами. По большему счету, список – это многоуровневая структура данных, для которой архиважна последовательность открывающих и закрывающих скобок.
Элементами списка могут быть атомы и списки, в том числе и пустой список. Например, () – пустой список, а (NIL) – список, состоящий из одного элемента NIL – что эквивалентно (()).
Следует понимать, что обычный синтаксис S-выражений может использоваться наравне со списочным синтаксисом, например, следующие выражение эквивалентны:

(a.(b.nil)), (a b.nil), (a b nil), (a b)

Если кому-нибудь интересно – можно будет рассказать и о внутреннем представлении списков в памяти. Это вполне самостоятельная и по интересу и по объему тема.

Основные функции и предикаты

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

Традиционном к базовым функциям относят QUOTE, CAR, CDR, CONS, ATOM, EQ.

Функция QUOTE

Для начала рассмотрим функцию QUOTE, предназначенную для блокирования вычисления выражения. Проще всего работу данной функции продемонстрировать простым примером:

(+ 5 10) -> 15 ; происходит вычисления выражения 5+10 и вывод результата
(quote (+ 5 10)) -> (+5 10) ; вычисление блокируется

Функцию QUOTE можно записать и короче:

‘(+ 5 10) -> (+ 5 10) ; ‘ – равноценно quote

Функция CAR

Предназначена для получения первого элемента точечной пары (или же головы списка). Использование данной функции возможно лишь в списочном контексте, использование для атома приведет к ошибке.

car (список) -> S-выражение.

(car ‘(a b c)) -> a
(car ‘(a)) -> a
(car ‘a) -> ERROR: a is not a list
(car ‘(nil)) -> nil
(car nil) -> nil
(car ‘(nil a)) -> nil

Для удобство головой пустого списка считается NIL.

Фунция CDR

Предназначена для получения второго элемента точечной пары (или же хвоста списка). Использование данной функции возможно лишь в списочном контексте, использование для атома приведет к ошибке.

cdr (список) -> список

Хвостом списка является весь список без первого элемента. Если список состоит из одного элемента, хвостом будет NIL. Хвостом пустого списка для удобства так же считается nil.
Несколько примеров:

(cdr ‘(a b c)) -> (b c)
(cdr ‘(a)) -> nil
(cdr ‘a) -> ERROR: a is not a list
(cdr ‘(a (b c))) -> ((b c))
(cdr ‘(nil a)) -> (a)
(cdr ()) -> nil

Функции CAR и CDR реализованы во всех диалектах LISP, но в некоторых для них созданы и синонимы: FIRST и REST, HEAD и TAIL).

Функция CONS

Предназначена для создания нового списка из переданных ей в качестве аргументов головы и хвоста:
cons (s-выражение, список) -> список

(cons ‘a ‘(b c)) -> (a b c)
(cons ‘a nil) -> (a)
(cons nil ‘(b c)) ->(nil b c)
(cons nil nil) ->(nil)
(cons ‘(a b) ‘(c)) ->((a b) c)

Фактически функция CONS является антиподом функций CAR и CDR:

(cons (car '(a b c)) (cdr '(a b c))) -> (a b c)

Функция ATOM

ATOM и EQ являются предикатами – т.е. функциями, проверяющих соответствие аргумента некоторому свойству и возвращающими T или NIL в зависимости от успешности проверки.

Предикат ATOM проверяет, является ли объект, переданный в качестве аргумента, атомом:

atom (S-выражение)

(atom ‘a) -> t
(atom ‘(a b c)) -> nil
(atom ()) -> t ;Т.к. пустой список равен nil, а следовательно атомарен

Функция EQ

Предикат, проверяющий идентичность двух символов.

eq (атом, атом)

(eq ‘a ‘b) -> nil
(eq ‘a ‘a) -> t
(eq ‘a (car ‘(a b)) -> t
(eq () nil) -> t

Следует помнить, что предикат EQ применим лишь к атомарным аргументам и не может быть использован для списков. Так же не следует использовать EQ при сравнении чисел.

Более общим по сравнению с EQ является предикат EQL, позволяющий сравнивать однотипный числа:

(eq 1.0 1.0) -> nil
(eql 1.0 1.0) -> t

Еще более общим для чисел является предикат =, позволяющий сравнивать значения чисел различных типов:

(eql 1 1.0) -> nil
(= 1 1.0) -> t

Более общим для списков является предикат EQUAL, позволяющий сравнивать идентичность двух списков:

(equal ‘a ‘a) -> t
(equal ‘(a b) ‘(a b)) -> t

Наиболее общим предикатом является EQUALP, позволяющий сравнивать произвольные объекты.

Функция NULL

NULL проверяет, является ли объект, переданный в качестве аргумента, пустым списком:

(null ‘()) -> t
(null ‘(a b c)) -> nil
(null nil) -> t
(null t) -> nil

Судя по двум последним примером, можно сделать вывод, что функцию NULL можно использовать и как логическое отрицание. Для этих же целей в LISP существует и предикат NOT.

Что дальше?

Надеюсь, что смог заинтересовать. В следующий раз я планирую рассказать о существующих диалектах LISP (хотя на первых порах достаточно будет университетского XLisp), менее часто используемых базовых функциях, сворачивании CAR и CDR в что-то вроде CAAAADDAAR и определении собственных функций. Позже — рекурсия, управляющие структуры, область действия, ввод-вывод. Еще позже — если не надоем — о функционалах, макросах, свойствах символов и замыканиях. Ну и конечно, о том, о чем попросит общественность.
До встречи!

Я пытаюсь эмулировать Lisp-подобный список в JavaScript (просто упражнение без каких-либо практических соображений), но я изо всех сил пытаюсь понять, как лучше всего представлять пустой список.

Является ли пустым списком только значение nil или оно находится под капотом, хранящимся в ячейке cons?

но пустым списком наверняка не может быть (cons nil nil) , потому что он будет неотличим от списка, в котором хранится один nil . Ему нужно было бы сохранить другую специальную ценность.

С другой стороны, если пустой список не построен из ячейки cons, кажется невозможным иметь последовательный интерфейс высокого уровня для добавления одного значения в существующий список. Функция:

Изменит свой аргумент, но только если это не пустой список, который кажется уродливым.

Пустым списком является просто символ nil (а символы, по определению, не согласны). car и cdr определены для возврата nil , если задано nil .

Что касается функций list-mutation, они возвращают значение, которое вы должны переназначить для своей переменной. Например, посмотрите спецификацию nreverse : он может изменить данный список или нет, и вы должны использовать возвращаемое значение, а не полагаться на него, чтобы его можно было изменить на месте.

Даже nconc , квинтэссенция destructive-append функция, работает таким образом: его возвращаемое значение является добавленным списком, который вы должны использовать. Он является указанным для изменения данных списков (кроме последнего) на месте, но если вы дадите ему nil в качестве первого аргумента, он не может очень хорошо изменить , поэтому вам все равно придется использовать возвращаемое значение.

Верьте или нет, это на самом деле религиозный вопрос.

Есть диалекты, которые люди осмеливаются назвать своего рода Lisp, в котором пустые списки являются conses или совокупными объектами какого-то типа, а не просто как атом nil .

В NewLisp списки представляют собой контейнеры: объекты типа списка, которые содержат связанный список элементов, поэтому пустые списки - это пустые контейнеры. [Ссылка] .

В Lisp-языках, которые не являются впечатляющими кластерными искажениями такого рода, пустые списки - это атомы, а непустые списки - двоичные ячейки с полем, в котором находится первый элемент, а другое поле, которое содержит остальную часть списка. Списки могут содержать суффиксы. Для такого списка, как (1 2 3) , мы можем использовать cons для создания (a 1 2 3) и (bc 1 2 3) , оба из которых совместно используют хранилище для (1 2 3) .

Хорошие идеи, такие как разрешение (car nil) на Just Work (чтобы хакеры могли обрезать много ненужных строк кода из своих программ), не появлялись в одночасье. Идея разрешить (car nil) появилась в InterLisp. В любом случае бумага Evolution Of Lisp утверждает, что MacLisp (один из важных предшественников Common Lisp, не связанный с Apple Macintosh, который появился двадцать лет спустя), имитировал эту функцию от InterLisp (еще один из значимые предшественники).

Небольшие детали, подобные этому, делают разницу между приятным программированием и ругательством на мониторе: см., Например, Короткая баллада, посвященная росту программ , вдохновленная борьбой программиста Lisp с bletcherous диалектом, в котором пустые списки не могут быть доступны с помощью car , и не служат логическим ложным.

В этой главе рассматриваются представление списков и атомов в памяти машины, а также специальные функции, с помощью которых можно изменять внутреннюю структуру списков. Без знания внутренней структуры списков и принципов её использования изучение работы со списками и функциями остаётся неполным.
В чистом функциональном программировании специальные функции, изменяющие структуры, не используются. В функциональном программировании лишь создаются новые структуры путём анализа, расчленения и копирования ранее созданных структур. При этом созданные структуры никогда не изменяются и не уничтожаются структуры, значения которых уже не нужны. В практическом программировании псевдофункции, изменяющие структуры, иногда всё-таки нужны, хотя их использования в основном пытаются избежать.

Память Lisp состоит из списочных ячеек

Оперативная память машины, на которой работает Лисп-система, логически разбивается на маленькие области, которые называются списочными ячейками (cons). Списочная ячейка состоит из двух частей, полей first и rest. Каждое из полей содержит указатель. Указатель может ссылаться на другую списочную ячейку или на некоторый другой Lisp объект, как, например, атом. Указатели между ячейками образуют как бы цепочку, по которой можно из предыдущей ячейки попасть в следующую и так, наконец, до атомарных объектов. Каждый известный системе атом записан в определённом месте памяти лишь один раз. (В действительности в данной реализации языка можно использовать много пространств имён, в которых атомы с одинаковыми именами хранятся в разных местах и имеют различную интерпретацию.)

Графически списочная ячейка представляется прямоугольником, разделённым на части (поля) first и rest. Указатель изображается в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении другой ячейки или атоме, на которые ссылается указатель.

Значение представляется указателем

Указателем списка является указатель на первую ячейку списка. На ячейку могут указывать не только поля first и rest других ячеек, но и используемый в качестве переменной символ, указатель из которого ссылается на объект, являющийся значением символа. Указатель на значение хранится вместе с символом в качестве его системного свойства. Кроме значения системными свойствами символа могут быть определение функции, представленное в виде лямбда-выражения, несколько знаков, задающая внешний вид переменной, выражение, определяющее пространство, в которое входит имя, и список свойств.
Побочным эффектом функции присваивания setq является замещение указателя в поле значения символа. Например, следующий вызов:

создаёт в качестве побочного эффекта изображённую серую стрелку.

Список состоит из нескольких ячеек, связанных друг с другом через указатели в правой части ячеек. Правое поле последней ячейки списка в качестве признака конца списка ссылается на пустой список, т.е. на атом nil. Графически ссылку на пустой список часто изображают в виде перечёркнутого поля. Указатели из полей first ячеек списка ссылаются на структуры, являющиеся элементами списка, в данном случае на атомы a, b и c.

FIRST и REST выбирают поле указателя

Работа селекторов first и rest в графическом представлении становится совершенно очевидной. Если мы применим функцию first к списку list, то результатом будет содержимое левого поля первой списочной ячейки, т.е. символ a:

возвращает значение из правого поля первой списочной ячейки, т.е. список (b c).

CONS создаёт ячейку и возвращает на неё указатель

Допустим, что у нас есть два списка:

строит новый список из ранее построенных списков head и tail так, как это показано на рисунке.

cons создаёт новую списочную ячейку (и соответствующий ей список). Содержимым левого поля новой ячейки станет значение первого аргумента вызова, а правого - значение второго аргумента. Обратите внимание, что одна новая списочная ячейка может связать две большие структуры в одну новую структуру. Это довольно эффективное решение с точки зрения создания структур и их представления в памяти. Заметим, что применение функции cons не изменило структуры списков, являющихся аргументами, и не изменило значений переменных head и tail.

У списков могут быть общие части

На одну ячейку может указывать одна или более стрелок из списочных ячеек, однако из каждого поля ячейки может исходить лишь одна стрелка. Если на некоторую ячейку есть несколько указателей, то эта ячейка будет описывать общее подвыражение. Например, в списке

(кто-то приходит кто-то уходит)

символ кто-то является общим подвыражением, на которое ссылаются указатели из поля first из первой и из третьей ячейки списка.
Если элементами списка являются не атомы, а подсписки, то на месте атомов будут находится первые ячейки подсписков.
Из рисунка выше видно, что логически идентичные атомы содержатся в системе один раз, однако логически идентичные списки могут быть представлены различными списочными ячейками. Например, значения вызовов

являются логически одинаковым списком (b c), хотя они и представлены различными списочными ячейками:

Однако список (b c) может состоять и из тех же ячеек.

Эту структуру можно создать с помощью следующих вызовов:

Таким образом, в зависимости от способа построения логическая и физическая структуры двух списков могут оказаться различными. Логическая структура всегда имеет форму двоичного дерева, в то время как физическая структура может быть ациклическим графом, или, другими словами, ветви могут снова сходиться, но никогда не могут образовывать замкнутые циклы, т.е. указывать назад. В дальнейшем мы увидим, что, используя псевдофункции, изменяющие структуры (поля) (setfirst, setrest и другие), можно создать и циклические структуры.

Логическое и физическое равенство не одно и то же

Логически сравнивая списки, мы использовали предикат =, сравнивающий не физические указатели, а совпадение структурного построения списков и совпадение атомов, формирующих список.
Предикатом eq можно определить физическое равенство двух выражений (т.е. ссылаются ли значения аргументов на один физический объект) не зависимо от того, является ли он атомом или списком. При сравнении символов всё равно, каким предикатом пользоваться, поскольку атомарные объекты хранятся всегда в одном и том же месте. При сравнении списком нужно поступать осторожнее.
Вызовы функции eq из следующего примера возвращают в качестве значения false, так как логически одинаковые аргументы в данном случае представлены в памяти физически различными ячейками:

Поскольку части first и rest списка list2 представлены при помощи одних и тех же списочных ячеек, то получим следующий результат:

Точечная пара соответствует списочной ячейке

Определяя базовую функцию cons, мы предполагали, что её вторым аргументом является список. Это ограничение не является необходимым, так как при помощи списочной ячейки можно было бы, например, результат вызова

(nil cons 'a 'b)

представить в виде структуры, изображённой на рисунке.

На рисунке показан не список, а более общее символьное выражение, так называемая точечная пара. Для сравнения на рисунке мы изобразили список (a b).

Название точечной пары происходит из использованной в её записи точечной нотации, в которой для разделения полей first и rest используется выделенная пробелами точка:

Выражение слева от точки (атом, список или другая точечная пара) соответствует значению поля first списочной ячейки, а выражение справа от точки - значению поля rest. Базовые функции first и rest действуют совершенно симметрично:

Точечная нотация позволяет расширить класс объектов, изображаемых с помощью списков. Ситуацию можно было бы сравнить с началом использования дробей или комплексных чисел в арифметике.

Варианты точечной и списочной записей

Любой список можно записать в точечной нотации. Преобразование можно осуществить (на всех уровнях списка) следующим образом:

(a b (c d) e)
≡
(a . (b . ((c . (d . nil)) . (e . nil))))

Признаком списка здесь служит nil в поле rest последнего элемента списка, символизирующий его окончание.
Транслятор может привести записанное в точечной нотации выражение частично или полностью к списочной нотации. Приведение возможно лишь тогда, когда поле rest точечной пары является списком или парой. В этом случае можно опустить точку и скобки вокруг выражения, являющегося значением поля rest:

Точка останется в выражении лишь в случае, если в правой части пары находится атом, отличный от nil. Убедиться в том, что произведённые интерпретатором преобразования верны, можно, нарисовав структуры, соответствующие исходной записи и приведённому виду:

Использование точечных пар в программировании на Лиспе в общем-то излишне. С их помощью в принципе можно несколько сократить объём необходимой памяти. Например структура данных

записанная в виде списка, требует трёх ячеек, хотя те же данные можно представить в виде

требующем двух ячеек. Более компактное представление может несколько сократить и объём вычислений за счёт меньшего количества обращений в память.
Точечные пары применяются в теории, книгах и справочниках по Лиспу. Часто с их помощью обозначают список заранее неизвестной длины в виде:

(голова . хвост)

Точечные пары используются совместно с некоторыми типами данных и с ассоциативными списками, а также в системном программировании. Большинство программистов не используют точечные пары, поскольку по сравнению с требуемой в таком случае внимательностью получаемый выигрыш в объёме памяти и скорости вычислений обычно не заметен.

Управление памятью и сборка мусора

В результате вычислений в памяти могут возникать структуры, на которые потом нельзя сослаться. Это происходит в тех случаях, когда вычисленная структура не сохраняется с помощью setq или когда теряется ссылка на старое значение в результате побочного эффекта нового вызова setq или другой функции. Если, например, изображённому на рисунке списку list3

присвоить новое значение

то first-часть как-бы отделяется, поскольку указатель из атома list3 начинает ссылаться так, как это изображено на рисунке при помощи серой стрелки.

Теперь уже нельзя через символы и указатели добраться до четырёх списочных ячеек. Говорят, что эти ячейки стали мусором.
Мусор возникает и тогда, когда результат вычисления не связывается с какой-нибудь переменной. Например, значение вызова

лишь печатается, после чего соответствующая ему структура останется в памяти мусором.
Для повторного использования ставшей мусором памяти предусмотрен специальный мусорщик, который автоматически запускается, когда в памяти остаётся мало свободного места. Мусорщик перебирает все ячейки и собирает являющиеся мусором ячейки в список свободной памяти для того, чтобы их можно было использовать заново.

Вычисления, изменяющие и не изменяющие структуру

Все рассмотренные до сих пор функции манипулировали выражениями, не вызывая каких-либо изменений в уже существующих выражениях. Например, функция cons, которая вроде бы изменяет свои аргументы, на самом деле строит новый список, функции first и rest в свою очередь лишь выбирают один из указателей. Структура существующих выражений не могла измениться как побочный эффект вызова функции. Значения переменных можно было изменить лишь целиком, вычислив и присвоив новые значения целиком. Самое большее, что при этом могло произойти со старым выражением, - это то, что оно могло пропасть.
В Лиспе всё-таки есть и специальные функции, при помощи которых на структуры уже существующих выражений можно непосредственно влиять так же, как, например, в Паскале. Это осуществляют функции, которые, как хирург, оперируют на внутренней структуре выражений.
Такие функции называют структура-разрушающими, поскольку с их помощью можно разорвать структуру и склеить её по-новому.

SETFIRST и SETREST изменяют содержимое полей

Основными функциями, изменяющими физическую структуру списков, являются setfirst и setrest, которые уничтожают прежние и записывают новые значения в поля first и rest списочной ячейки:

(ячейка setfirst значение-поля)	;поле first
(ячейка setrest значение-поля)	;поле rest

Объектом является указатель на списочную ячейку, аргументом - записываемое в неё новое значение поля first или rest. Обе функции возвращают в качестве результата указатель на изменённую списочную ячейку.

Функция setrest выполняется так же, как setfirst, с той разницей, что меняется значение поля rest:

Используя функцию setrest, можно, например, определить функцию круг, превращающую произвольный список в кольцо:

Изменение структуры может ускорить вычисления

Разумно использованные структура-разрушающие функции могут, как и нож хирурга, быть эффективными и полезными инструментами. Далее мы для примера рассмотрим, как можно с помощью структура-разрушающих псевдофункций повысить эффективность функции + для списков. Эта функция объединяет в один список списки, являющиеся его аргументами:

Может показаться, что приведённый выше вызов +, как бы изменяет указатели так, как это показано серыми стрелками.

Однако это не верно, так как значение списка begin не может измениться, поскольку + не является структура-разрушающей функцией. Вычисляется и присваивается лишь новое значение переменной result. Мы получим структуры, изображённые на рисунке:

Из рисунка видно, что + создаёт копию списка, являющегося первым аргументом. Если этот список очень длинный, то долгими будут и вычисления. Создание списочных ячеек с помощью функции cons требует времени и в будущем добавляет работы мусорщику. Если, например, список begin содержит 1000 элементов, а end - один элемент, то во время вычисления будет создано 1000 новых ячеек, хотя вопрос состоит лишь в добавлении одного элемента к списку. Если бы расположение аргументов была другой, то создалась бы одна ячейка, и списки были бы объединены приблизительно в 1000 раз быстрее.
Если для нас не существенно, что значение переменной begin изменится, то мы можем вместо функции + использовать более быструю функцию +=. Функция += делает то же самое, что и +, с той лишь разницей, что она просто объединяет списки, изменяя указатель в поле rest последней ячейки списка, являющегося первым аргументом, на начало списка, являющегося вторым аргументом, как это показано на первом рисунке:

Использовав функцию +=, мы избежали копирования списка begin, однако в качестве побочного эффекта изменилось значение переменной begin. Так же изменятся и все другие структуры, использовавшие ячейки первоначального значения переменной begin.
Псевдофункции, подобные setfirst, setrest и +=, изменяющие внутреннюю структуру списков, используются в том случае, если нужно сделать небольшие изменения в большой структуре данных. С помощью структура-разрушающих функций можно эффективно менять за один раз сразу несколько структур, если у этих структур есть совмещённые в памяти подструктуры.
Коварные побочные эффекты, вроде изменения значений внешних переменных, могут привести к сюрпризам в тех частях программы, которые не знают об изменениях. Это осложняет написание, документирование и сопровождение программ. В общем случае функции, изменяющие структуры, пытаются не использовать.

Здесь вы можете скачать документацию и программы для САПР AutoCAD, PCAD, 3DS, Inventor, Pro/E, Solidworks и других CAD CAM CAE EDA GIS

Глава 4 Функции AutoLISPа (4.38 - 4.75)

Эта функция возвращает расстояние между 2-х мерными точками , где 2-х мерная точка - это список двух действительных чисел.

Эта функция определяет идентичны ли и , т.е. они фактически относятся к одному объекту (например, с помощью SETQ). EQ возвращает Т, если оба выражения идентичны, иначе nil. Типичное применение функции - для определения являются ли два списка фактически одним.

Hапример, зададимся следующими допущениями: тогда: Смотри так же функцию EQUAL ниже.

Это функция определяет равны ли и , т.е. их значение является одно и то же.

Hапример, зададимся следующими допущениями: тогда:

Отметим, что в то время, как два списка EQUAL, они могут не быть EQ, атомы, которые EQUAL всегда к тому же EQ. Добавим, что два списка, которые EQ, всегда EQUAL.

Функция возвращает результат выражения , где - любое выражение языка LISP.

Hапример, дано: тогда:

Эта функция вычисляет е в степени (натуральный антилогарифм), возвращает действительное число.

Эта функция возвращает , возведенное в указанную . Если оба аргумента целые, то результат - целое число. В любом другом случае, результат - действительное число.

Функция возвращает преобразование в целое. может быть как целым, так и действительным. Если оно действительное, то оно усекается до ближайшего целого путем отбрасывания дробной части.

Функция возвращает преобразование в действительное. может быть как целым, так и действительным.

Эта функция, проходя по , присваивает каждому элементу и вычисляет каждое для каждого элемента в списке. Может быть задано любое число . FOREACH выдает результат последнего, вычисленного .

Hапример: эквивалентно: кроме того, что FOREACH возвращает результат только последнего вычисленного выражения.

Функция возвращает наибольший общий делитель и . и должны быть целыми.

Эта функция создает паузу для того, чтобы пользователь ввел угол. - факультативная запись для высвечивания на экране в качестве подсказки, а - факультативная 2-х мерная базовая точка. Вы можете задать угол путем набора числа на клавиатуре в текущих для AutoCADa единицах измерения. Заметим, что, несмотря на то, что текущая единица измерения угла может быть градус, град, или какая либо еще, функция всегда возвращает угол в радианах.

Вы можете так же "показать" AutoLISPу угол путем указания двух 2-х мерных точек на экране. AutoCAD нарисует "резиновую" линию от первой точки к текущему положению курсора для того чтобы визуализировать угол. Факультативный аргумент GETANGLE - (если указывается) подразумевается как первая из этих двух точек, позволяя тем самым вам "показать" AutoLISPу угол, указывая на следующую точку.

Hиже приведены примеры функции GETANGLE.

GETCORNER возвращает точку, так же как GETPOINT. Однако для GETCORNER требуется и функция строит прямоугольник от в то время как пользователь передвигает курсор по экрану. Смотрите GETROINT и INITGET для уточнения. Вы не можете ввести другое LISP-выражение в ответ на запрос GETCORNER.

Эта функция создает паузу для того, чтобы пользователь ввел расстояние. [ ] - факультативная запись для высвечивания на экране в качестве подсказки, - факультативная базовая точка. Вы можете указать расстояние, набрав число на клавиатуре в текущих для AutoCADa единицах измерения. Заметим, какими бы ни были текущие единиц измерения (например, футы или дюймы), функция всегда возвращает расстояние как действительное число.

Вы можете так же "показать" AutoLISPу расстояние , указав две точки на экране. AutoCAD рисует "резиновую" линию от первой точки до текущего положения курсора для того, чтобы визуализировать расстояние. Факультативный аргумент GETDIST подразумевается как первый из этих двух точек, позволяя вам "показать" AutoLISPу расстояние, путем указания в любую другую точку. Hиже приведены примеры функции GETDIST:

Вы не можете ввести другое LISP-выражение как ответ на запрос GETDIST. Смотрите также INITGET.

Эта функция ожидает ввода пользователем целого числа и возвращает его. - факультативная запись для высвечивания на экране в качестве подсказки.

Вы не можете ввести другое LISP-выражение на запрос GETINT. Смотрите также INITGET.

Эта функция запрашивает ключевое слово у пользователя. Список имеющих смысл ключевых слов задается прежде чем вызывается функция GETKWORD, пользуясь функцией INITGET (описывается ниже). GETKWORD возвращает ключевое слово, соответствующее введенному пользователем как строковую константу. AutoCAD переспросит, если введенное не является одним из заданных ключевых слов. Пустой ввод возвращает nil (если позволяется вводить пустой ввод). Если не было установлено ни одного ключевого слова также возвращается nil.

запросит пользователя и установит в символ Х либо "Yes", либо "No", в зависимости от его ответа. Если ввод не соответствует ни одному ключевому слову, или же пользователь ответил пустым вводом, AutoCAD попросит пользователя повторить ввод еще раз. Вы не можете ввести другое LISP-выражение на запрос GETKWORD. Смотрите также INITGET.

В AutoLISPe углы всегда представляются в радианах с нулевым направлением слева направо (восток) и углы откладываются против часовой стрелки. Таким образом, должны иметь месть некоторые изменения, если пользователь хочет выбрать отсчет в градусах или желает изменить направление отсчета углов, используя команду UNITS или системные переменные ANGBASE и ANGDIR. GETRIENT похожа на GETANGLE-функцию, но отличается от нее тем, что измеряет углы в градусах и направление отсчета углов определяется другим способом чем в GETANGLE. GETANGLE используется, если вам необходим суммарный угол (относительный угол), в то время как GETORIENT используется для достижения ориентации (абсолютный угол). Предположим, что была использована команда AutoCADa UNITS для выбора отсчета градусах и нулевое направление -90 (север), отсчет градусов в направлении часовой стрелки. В таблице указаны значения, которые возвращают GETANGLE и GETORIENT (в радианах), если пользователем введены указанные значения (в градусах):

Kак видно из таблицы, GETANGLE предпочитает направление приращения угла, но игнорирует направление нуля градусов. Так, вы можете использовать GETANGLE при повороте вставляемого блока, т.к. введение нуля градусов будет всегда возвращать ноль радиан. С другой стороны, GETORIENT воспринимает как направление нуля градусов, так и направление приращения угла. Так, вы можете использовать GETORIENT для введения таких углов, как угол базовой линии для команды ТЕХТ. Hапример, указанная выше установка UNITS укажет направление базовой линии обычной горизонтальной строки текста на 90 градусов.

Вы не можете ввести другое LISP-выражение в качестве ответа на запрос GETORIENT. Смотрите также GETANGLE и INITGET.

Эта функция запрашивает от пользователя точку . Факультативный аргумент - базовая [ ] и [ ] - факультативная запись для высвечивания на экране в качестве подсказки. Вы можете ввести точку путем указания ее на экране или записав координаты в текущих единицах измерения. Если присутствует аргумент , AutoCAD нарисует "резиновую" линию от этой точки до текущего положения курсора.

Обычно, GETPOINT возвращает 2-х мерную точку (список из двух действительных чисел). Используя функцию INIGET для установки контрольного символа "3-х мерная точка", вы можете заставить GETPOINT возвращать 3-х мерную точку (список из трех действительных чисел).

Вы не можете ввести иное LISP-выражение в ответ на запрос GETPOINT. Смотрите также GETCORNER и INITGET.

Эта функция запрашивает пользователя ввести действительное число и возвращает его. -необязательный аргумент для высвечивания на экране в виде подсказки.

Вы не можете ввести иное LISP-выражение в ответ на запрос GETREAL. Смотрите также INITGET.

Эта функция запрашивает пользователя ввести строковую константу и возвращает этот константу. Если присутствует и не nil, вводимый поток может содержать пробелы (и должен, следовательно, оканчиваться RETURN). Иначе ввод текста (строковой константы) будет прерван пробелом RETURN. - факультативный аргумент для высвечивания на экране в виде подсказки.

Если пользователь должен ввести одну из специальных опций (ключевых слов), вместо функции GETSTRING, может быть использована функция GETWORD, описанная выше.

Вы не можете ввести иное LISP-выражение как ответ на запрос GETSTRING.

Эта функция возвращает значение системной переменной AutoCADa. Имя переменной должно быть заключено в кавычки ("имя").

Hапример, предположим, что радиус сопряжения был недавно определен в 0.25 единиц:

Если вы используете GETVAR с неизвестным AutoCADу именем переменной, функция возвратит nil. Список текущих системных переменных AutoCADa можно найти в приложении А руководства по AutoCADу. Смотрите также функцию SETVAR.

Эта функция переключает экран с текстового режима в графический в системах с одним экраном (также как функциональная клавиша "FLIP SCREEN" в AutoCADe). GRAPHSCR всегда возвращает nil. Смотрите так же функцию TEXTSCR.

Эта функция исполняет выражение по условию. Если не nil, тогда исполняется , иначе исполняется . Последнее выражение не обязательно. IF возвращает значение выбранного выражения; если отсутствует и nil, IF возвращает nil.

Эта функция устанавливает различные опции для использования последующими функциями GETxxx (кроме GETSTRING и GETVAR). INITGET всегда возвращает nil. - факультативный аргумент - целое число со следующими значениями:

Биты могут добавляться вместе в любой комбинации, чтобы сформировать значение от 0 до 63. (Последующие версии AutoLISPа могут включать дополнительные контрольные биты, так что избегайте указывать незадокументированные биты). Если пользователь, вводя забыл одно или более заданных условий (так, например, ввел 0, когда ввод 0 запрещен), AutoCAD высветит ошибку и предложит пользователю повторить ввод.

спросит возраст пользователя, автоматически повторяя запрос, если пользователь ответил пустым вводом, ввел отрицательное или нулевое значение. Если нет аргумента , подразумевается 0 (нет условий). Специальные контрольные значения обеспечиваются теми GETxxx функциями, для которых они имеют смысл, как показано в следующей таблице.

Контрольный бит со значением 32 воспринимается функциями GETPOINT, GETCORNER, GETDIST, GETANGLE и GETORIENT когда присутствует аргумент , и устанавливает режим использования пунктирной (или по-другому подсвеченной) линии в качестве "резиновой" линии или рамки, отрисовываемых курсором от заданной базовой точки. Если системная переменная POPUPS равна нулю, указывая тем самым, что драйвер дисплея не поддерживает улучшенный интерфейс пользователя, то AutoCAD проигнорирует этот бит функции INITGET.

Факультативный аргумент INITGET-функции определяет список ключевых слов, которые будут проверяться в последующем запросе GETxxx, если пользователь произвел ввод неправильного типа (например, точку для GETPOINT). Если ввод пользователя соответствует одному из ключевых слов из этого списка, это ключевое слово возвращается GETxxx функцией как результат типа STRING (строковая константа). Программа пользователя может тестировать ключевые слова и выполнять желаемые действия для каждого из них. Если ввод пользователя недозволенного типа и не соответствует ни одному из ключевых слов, AutoCAD предложит пользователю повторить ввод.

Список ключевых слов может быть такой формы :"Key1 KEy2 KEY3,ABBREV3". Отдельные ключевые слова отделяются пробелами. Сокращение необязательно и возможны два способа специфицирования. Необходимая для ввода часть ключевого слова может быть выделена заглавными буквами, остальная часть строчными или необходимая часть может быть повторена через запятую после ключевого слова. Второй способ применяется в случае использования иностранного языка, где переход из прописных в заглавные буквы сложен или невозможен. В обоих случаях длина необходимой части - минимальная длина, которая должна быть для точного различения. (Для метода с разделением запятой подразумевается, что сокращение - это начало ключевого слова.)

эквивалентные спецификации. Будет восприниматься любой ввод пользователя из "LTYPE", "LTYP", "LTY" или "LT", но "L" недостаточно, не подходят и "LTSCALE" "LTYPEX".

Рассмотрим следующую функцию, определенную пользователем: Здесь INITGET препятствует пустому вводу и устанавливает список из двух ключевых слов "Pi" и "Two-pi". Затем используется GETREAL для извлечения вещественного числа с помощью подсказки "Pi/Two-pi/ :" и результат помещается в локальный символ Х. Если пользователь вводит число, это число возвращается функцией GETNUM. Однако, если пользователь вводит ключевое слово "Pi" (или просто "P"), GETPOINT возвращает ключевое слово "Pi". Функция COND фиксирует это и в этом случае возвращает значение pi. Ключевое слово "Two-pi" трактуется аналогично. Список управляющих сигналов и ключевых слов, устанавливаемые INITGET, применимы только к следующему за INITGET вызываемому GETxxx и затем автоматически сбрасываются. Это позволяет Getxxx-функций избежать необходимости при следующем вызове очищать специальные состояния.

Функция INTERS проверяет два отрезка на пересечение и возвращает точку пересечения или nil, если они не пересекаются. и крайние точки первого отрезка, - крайние точки второго отрезка. Если факультативный аргумент присутствует и является nil, то отрезки будут восприниматься бесконечной длины и INTERS будет возвращать точку пересечения даже, если она находится за крайними точками одного или обоих отрезков. Если же аргумент отсутствует или не является nil, то точка пересечения должна находится на обоих отрезках или INTERS вернет nil.

Например, дано: тогда:

Эта функция возвращает преобразование целого числа в строковую константу.

Эта функция определяет "анонимную" функцию. Она обычно используется, когда при определении новая функции не именуется. Это так же делает замысел программиста более очевидным, за счет того, что функция находится там же, где она используется. LAMBDA возвращает значение последнего и часто используется в связи с APPLY и/или MAPCAR для выполнения функции над списком.

Эта функция возвращает последний элемент списка. не должен быть равен nil.

Например: Как видно, LAST возвращает либо атом, либо список. На первый взгляд LAST может являться хорошим путем для извлечения координаты Y точки. Хотя это так для 2-х мерных точек (список из 2-х действительных чисел). LAST будет возвращать координату Z в случае 3-х мерной точки. Чтобы ваши функции работали как следует при задании и 2-х мерных и 3-х мерных точек, мы рекомендуем вам использовать CADR для извлечения координаты Y и CADDR для извлечения координаты Z.

Эта функция возвращает целое число, означающее число элементов в .

Эта функция берет любое число выражений ( ) и организует из них строку, возвращая список.

Например: В AutoLISP эти функции часто используются для определения значений 2-х и 3-х мерных точек (список из 2-х или 3-х действительных чисел).

Эта функция возвращает T, если список, иначе nil.

Эта функция загружает файл выражений AutoLISPа и выполняет эти выражения. - это строковая константа, которая представляет собой имя файла без расширения (подразумевается расширение ".lsp"). может включать префикс директории, например "/function/test1". На системах MS-DOS/PS-DOS допускается так же использовать букву устройства ввода/вывода и вы можете пользоваться обратной косой чертой вместо прямой косой черты (но помните, чтобы ввести в строку одну обратную черту вы должны использовать "\\").

Если операция успешно завершена, LOAD возвращает имя последней функции, определенной в файле. Если операция не выполнена, LOAD возвращает имя файла в виде строкового выражения.

Например, предположим, что файл "/fred/test1.lsp" содержит DEFUN, определяющую функцию MY-FUNC, и что файл "test2.lsp" не существует:

Функция LOAD не может вызываться из другой функции LISP. Она должна вызываться непосредственно с клавиатуры (или из меню или скрипт-файла), в то время как ни одна другая функция LISP не находится в процессе выполнения.

Каждый раз, когда Редактор Чертежей AutoCAD начинает очередной сеанс, AutoLISP загружает файл "acad.lsp", если он существует. Вы можете поместить определения функций и часто используемые команды в этот файл и они будут исполняться автоматически, когда вы будете редактировать чертежи.

Эта функция возвращает натуральный логарифм как действительное число.

Эта функция возвращает результат действия побитового И над списком . Эти должны быть целые и результат - так же целое число.

Эта функция возвращает результат действия побитового ИЛИ над списком . должны быть целые и результат так же целое число.

Эта функция возвращает побитовый сдвиг на . и должны быть целыми и результат - тоже целое. Если положительно, то сдвигается влево; если отрицательно - то вправо. В каждом случае "нулевые" биты добавляются, а сдвигаемые биты сбрасываются. Если "единичный" бит сдвигается в высший (16-й) разряд целого числа, знак числа меняется.

Эта функция возвращает результат выполнения над отдельными элементами от до вводимыми как аргументы в . Число должно соответствовать числу аргументов, требующихся для .

Hапример: это эквивалентно: Kроме того, что MAPCAR возвращает список результатов. Так же: это то же самое, что и:

Функция LAMBDA может задавать "анонимную" функцию для выполнения функцией MAPCAR. Это полезно когда некоторые из аргументов функции константы или передаются каким-либо иным образом.

Hапример: и: возвращает (30 150.000000)

Эта функция возвращает наибольшее из заданных . Kаждое может быть действительным или целым.

Эта функция просматривает - встречается ли и возвращает часть , начинающуюся с первого найденного . Если в нет , MEMBER возвращает nil.

Читайте также: