Минусы - Cons

Эта статья о функции программирования на Лиспе. Для использования в других целях см. Минусы (значения).

В компьютерное программирование, минусы (/ˈkɒпz/ или же /ˈkɒпs/) является фундаментальным функция на большинстве диалектов Язык программирования Лисп. минусы минусыконтракты объекты памяти, которые содержат два значения или указатели на значения. Эти объекты называются (cons) ячейками, conses, неатомарными s-выражения («NATSes») или (против) пары. На жаргоне Лиспа выражение «to cons Икс на у"означает создание нового объекта с (минусы Икс у). У полученной пары есть левая половина, называемая машина (первый элемент или содержимое адресный регистр ), и правая половина (второй элемент или содержимое регистр декремента ), называемый CDR.

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

Слово «против» и выражения типа «против» также являются частью более общего функциональное программирование жаргон. Иногда операторы которые имеют аналогичное назначение, особенно в контексте обработки списков, произносятся "cons". (Хорошим примером является :: оператор в ML, Scala, F # и Вяз или : оператор в Haskell, который добавляет элемент в начало списка.)

Использовать

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

Заказанные пары

Например, выражение Лиспа (минусы 1 2) строит ячейку, содержащую 1 в левой половине (так называемый машина поле) и 2 в его правой половине ( CDR поле). В нотации Лиспа значение (минусы 1 2) похоже:

(1 . 2)

Обратите внимание на точку между 1 и 2; это указывает на то, что S-выражение является «пунктирной парой» (так называемая «cons-пара»), а не «списком».

Списки

Диаграмма ячейки Cons для списка (42 69 613), записанная с минусы: 
(минусы 42 (минусы 69 (минусы 613 ноль)))
и написано с список: 
(список 42 69 613)

В Лиспе списки реализованы поверх пар минусов. В частности, любая структура списка в Лиспе:

  1. Пустой список (), который представляет собой специальный объект, обычно называемый ноль.
  2. Консульская ячейка, чья машина является первым элементом списка и чей CDR это список, содержащий остальные элементы.

Это составляет основу простого, односвязный список структура, содержимым которой можно управлять с помощью минусы, машина, и CDR. Обратите внимание, что ноль это единственный список, который также не является парой минусов. В качестве примера рассмотрим список с элементами 1, 2 и 3. Такой список можно создать в три этапа:

  1. Минусы 3 на ноль, пустой список
  2. Минусы 2 на результат
  3. Минусы 1 на результат

что эквивалентно одному выражению:

(минусы 1 (минусы 2 (минусы 3 ноль)))

или его сокращение:

(список 1 2 3)

В результате получается список:

(1. (2. (3. Nil)))

т.е.

 * - * - * - ноль | | | 1 2 3

что обычно сокращается как:

(1 2 3)

Таким образом, минусы может использоваться для добавления одного элемента в начало существующего связанного списка. Например, если Икс это список, который мы определили выше, тогда (минусы 5 Икс) создаст список:

(5 1 2 3)

Еще одна полезная процедура списка: добавить, который соединяет два существующих списка (т.е. объединяет два списка в один).

Деревья

Бинарные деревья которые хранят данные только в своих листья также легко создаются с помощью минусы. Например, код:

(минусы (минусы 1 2) (минусы 3 4))

приводит к дереву:

((1 . 2) . (3 . 4))

т.е.

   *  / \ *   */ \ / \1 2 3 4

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

 * - * - * - ноль | | | 1 2 3

на следующий эквивалент:

   * /  1 * /  2 * /  3 ноль

Используйте в разговоре

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

Я немного ускорил код, вставив побочные эффекты вместо того, чтобы иметь это нелепо.

Функциональная реализация

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

(определять (минусы Икс у)  (лямбда (м) (м Икс у)))(определять (машина z)  (z (лямбда (п q) п)))(определять (CDR z)  (z (лямбда (п q) q)))

Этот метод известен как Церковная кодировка. Он повторно реализует минусы, машина, и CDR операций, используя функцию в качестве «cons-ячейки». Кодирование Чёрча - это обычный способ определения структур данных в чистом виде. лямбда-исчисление, абстрактная теоретическая модель вычислений, которая тесно связана со Scheme.

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

Однако такой же тип кодирования может использоваться для более сложных алгебраических типов данных с вариантами, где он может даже оказаться более эффективным, чем другие виды кодирования.[1]Эта кодировка также имеет то преимущество, что ее можно реализовать на статически типизированном языке, который не имеет вариантов, таких как Ява, используя интерфейсы вместо лямбда-выражений.

Смотрите также

Рекомендации

  1. ^ «Архивная копия» (PDF). Архивировано из оригинал (PDF) 31 марта 2010 г.. Получено 2009-03-01.CS1 maint: заархивированная копия как заголовок (ссылка на сайт)

внешняя ссылка

  • SDRAW, Common Lisp код для рисования рисует структуры cons-ячеек. От Дэвида С. Турецки.