учебники, программирование, основы, введение в,

 

Элементарный Лисп

Основы символьной обработки. Базовые средства
Функциональный стиль программирования сложился в практике решения задач символьной обработки данных в предположении, что любая информация для компьютерной обработки может быть сведена к символьной. (Существование аналоговых методов принципиально не противоречит этой гипотезе.) Слово "символ" здесь близко понятию "знак" в знаковых системах. Информация представляется символами, смысл которых может быть восстановлен по заранее известным правилам.
Методы функционального программирования основаны на формальном математическом языке представления и преобразования формул. Поэтому можно дать точное, достаточно полное описание основ функционального программирования и специфицировать систему программирования для поддержкии разработки разных парадигм программирования, моделируемых с помощью функционального подхода к организации деятельности.
Такое определение будет приведено в шестой лекции, а сейчас необходимо освоить технические приемы символьной обработки. В дальнейшем будут проиллюстрированы и практические способы применения функционального программирования, превращающие его в удобную технологию современного программирования.
Функциональное программирование отличается от большинства подходов к программированию тремя важными принципами:
1) Природа данных
Все данные представляются в форме символьных выражений. В Лиспе Дж. Мак-Карти назвал их S-выражениями. Состав S-выражений и типы их элементов не ограничиваются, что позволяет его использовать как древообразные структуры. Это позволяет локализовывать любые важные подвыражения. Система программирования над такими структурами обычно использует для их хранения всю доступную память, поэтому программист освобожден от распределения памяти под отдельные блоки данных.
2) Самоописание обработки символьных выражений
Важная особенность функционального программирования состоит в том, что описание способов обработки S-выражений представляется программами, рассматриваемыми как символьные данные. Программы строятся из рекурсивных функций над S-выражениями. Определения и вызовы этих функций, как и любая информация, имеют вид S-выражений, то есть формально они могут обрабатываться как обычные данные, получаться в процессе вычислений и преобразовываться как значения.
3) Подобие машинным языкам
Система функционального программирования допускает, что программа может интерпретировать и/или компилировать программы, представленные в виде S-выражений. Это сближает методы функционального программирования с методами низкоуровнего программирования и отличает от традиционной методики применения языков высокого уровня.
Не все языки функционального программирования в полной мере допускают эту возможность, но для Лиспа она весьма характерна. В принципе, такая возможность достижима на любом стандартном языке, но так делать не принято.
Наиболее очевидные следствия из выбранных принципов:

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

Функциональное программирование активно применяется для генерации программ и выполнения динамически конструируемых прототипов программ, а также для систем, применяемых в областях с низкой кратностью повторения отлаженных решений (например, в учебе, проектировании, творчестве и научных исследованиях), ориентированных на оперативные изменения, уточнения, улучшения, адаптацию и т.п.
Данные
Любые структуры  данных начинаются с элементарных значений. Следуя Лиспу, в функциональном программировании такие значения называют атомами или символами. Внешне атом обычно выглядит как последовательность из букв и цифр, начинающаяся с буквы. В первых реализациях Лиспа было принято ограничивать длину атома, но ограничение было не слишком жестким (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) как стандартное представление, но роль такого значения может выполнить любой, отличный от пустого списка, объект.

Точечная нотация
Исторически при реализации Лиспа в качестве единой базовой структуры для конструирования S-выражений использовалась так называемая "точечная нотация" (dot-nоtation), согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.
Бинарный узел, содержащий пару атомов  ATOM1 и ATOM2, можно представить в виде S-выражения вида:
( ATOM1 . ATOM2 )


Таблица 2.1. Операции над списками. Примеры соответствия аргументов и результатов

Функциия

Аргументы

Результат

 

Конструирование структур данных

 

CONS

A и Nil

(A )

CONS

(A B) и Nil

((A B) )

CONS

A и (B)

(A B)

CONS

(Результат предыдущего CONS) и (C)

((A B) C)

CONS

A и (B C)

(A B C)

 

Доступ к компонентам структуры данных:

 

 

Слева

 

CAR

(A B C)

A

CAR

(A (B C))

A

CAR

((A B) C)

(A B)

CAR

A

не определен

 

Справа

 

CDR

(A )

Nil

CDR

(A B C D)

(B C D)

CDR

(A (B C))

((B C))

CDR

((A B) C)

(C)

CDR

A

не определен

 

Смешанная обработка данных:

 

CDR

(A B C)

(B C)

CAR

результат предыдущего CDR

B

CAR

(A C)

A

CAR

результат предыдущего CAR

не определен

CONS

A и (B)

(A B)

CAR

результат предыдущего CONS

A

CONS

A и (B)

(A B)

CDR

результат предыдущего CONS

(B)

 

Предикаты:

 

 

Атомарность — неделимость

 

ATOM

VeryLongStringOfLetters

T

CDR

(A B)

(B)

ATOM

результат предыдущего CDR

Nil

ATOM

Nil

T

ATOM

( )

T

 

Равенство

 

EQ

A A

T

EQ

A B

Nil

EQ

A (A B)

Nil

EQ

(A B) (A B)

не определен

EQ

Nil и ( )

T

Если вместо атомов ATOM1, ATOM2 рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то получим множество всех возможных S-выражений. Можно сказать, что S-выражение — это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой. Все сложные данные выстраиваются из одинаково устроенных блоков — бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.
ATOM
(A . B)
(C . (A . B))
((A . B) . C)
((A . B) . (D . C))
((A . B) . (D . (C . E)))
Любое S-выражение может быть построено из атомов с помощью CONS, и любая его часть может быть выделена с помощью CAR-CDR.
Расширение типа данных, допускаемых в качестве второго аргумента CONS, ни в малейшей степени не усложняет реализацию этой функции, равно как и реализацию функций CAR и CDR, зато их описания становятся проще. Функция CONS строит бинарный узел и заполняет его парой объектов, являющихся значениями пары ее аргументов. Первый аргумент размещается в левой части бинарного узла, а второй — в правой. Функция CAR обеспечивает доступ к объектам, расположенным слева от точки, а функция CDR — справа.

Таблица 2.2. Операции над произвольными S-выражениями

Функция

Аргументы

Результат

 

Конструирование структур данных

 

CONS

A и B

(A . B)

CONS

(A . B) и C

((A . B) . C)

CONS

A B

(A . B)

CONS

(результат предыдущего CONS) и C

((A . B) . C)

 

Доступ к компонентам структуры данных:

 

 

Слева

 

CAR

(A . B)

A

CAR

((A . B) . C)

(A . B)

 

Справа

 

CDR

(A . B)

B

CDR

(A . (B . C))

(B . C)

 

Смешанная обработка данных:

 

CONS

A и B

(A . B)

CAR

результат предыдущего CONS

A

CONS

A и B

(A . B)

CDR

результат предыдущего CONS

B

CDR

(A . (B . C))

(B . C)

CAR

результат предыдущего CDR

B

CDR

(A . C)

C

CAR

результат предыдущего CDR

не определен

 

Тождества: (на произвольных объектах)

 

CONS

два произвольных объекта x и y

(x . y)

CAR

результат предыдущего CONS

исходный объект x (первый аргумент CONS)

CONS

два произвольных объекта x и y

(x . y)

CDR

результат предыдущего CONS

исходный объект y (второй аргумент CONS)

CAR

произвольный составной объектx

(CAR x)

CDR

тот же самый объект x - не атом

(CDR x)

CONS

результаты предыдущих CAR и CDR

исходный объект x

 

Предикаты:

 

 

Атомарность — неделимость

 

ATOM

(A . B)

Nil - выполняет роль ложного значения

CDR

(A . B)

B

ATOM

результат предыдущего CDR

T

 

Равенство:

 

EQ

(A . B) (A . B)

не определен

Точечная нотация
Исторически при реализации Лиспа в качестве единой базовой структуры для конструирования S-выражений использовалась так называемая "точечная нотация" (dot-nоtation), согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.
Бинарный узел, содержащий пару атомов  ATOM1 и ATOM2, можно представить в виде S-выражения вида:
( ATOM1 . ATOM2 )


Таблица 2.1. Операции над списками. Примеры соответствия аргументов и результатов

Функциия

Аргументы

Результат

 

Конструирование структур данных

 

CONS

A и Nil

(A )

CONS

(A B) и Nil

((A B) )

CONS

A и (B)

(A B)

CONS

(Результат предыдущего CONS) и (C)

((A B) C)

CONS

A и (B C)

(A B C)

 

Доступ к компонентам структуры данных:

 

 

Слева

 

CAR

(A B C)

A

CAR

(A (B C))

A

CAR

((A B) C)

(A B)

CAR

A

не определен

 

Справа

 

CDR

(A )

Nil

CDR

(A B C D)

(B C D)

CDR

(A (B C))

((B C))

CDR

((A B) C)

(C)

CDR

A

не определен

 

Смешанная обработка данных:

 

CDR

(A B C)

(B C)

CAR

результат предыдущего CDR

B

CAR

(A C)

A

CAR

результат предыдущего CAR

не определен

CONS

A и (B)

(A B)

CAR

результат предыдущего CONS

A

CONS

A и (B)

(A B)

CDR

результат предыдущего CONS

(B)

 

Предикаты:

 

 

Атомарность — неделимость

 

ATOM

VeryLongStringOfLetters

T

CDR

(A B)

(B)

ATOM

результат предыдущего CDR

Nil

ATOM

Nil

T

ATOM

( )

T

 

Равенство

 

EQ

A A

T

EQ

A B

Nil

EQ

A (A B)

Nil

EQ

(A B) (A B)

не определен

EQ

Nil и ( )

T

Если вместо атомов ATOM1, ATOM2 рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то получим множество всех возможных S-выражений. Можно сказать, что S-выражение — это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой. Все сложные данные выстраиваются из одинаково устроенных блоков — бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.
ATOM

(A . B)
(C . (A . B))
((A . B) . C)
((A . B) . (D . C))
((A . B) . (D . (C . E)))
Любое S-выражение может быть построено из атомов с помощью CONS, и любая его часть может быть выделена с помощью CAR-CDR.
Расширение типа данных, допускаемых в качестве второго аргумента CONS, ни в малейшей степени не усложняет реализацию этой функции, равно как и реализацию функций CAR и CDR, зато их описания становятся проще. Функция CONS строит бинарный узел и заполняет его парой объектов, являющихся значениями пары ее аргументов. Первый аргумент размещается в левой части бинарного узла, а второй — в правой. Функция CAR обеспечивает доступ к объектам, расположенным слева от точки, а функция CDR — справа.


Таблица 2.2. Операции над произвольными S-выражениями

Функция

Аргументы

Результат

 

Конструирование структур данных

 

CONS

A и B

(A . B)

CONS

(A . B) и C

((A . B) . C)

CONS

A B

(A . B)

CONS

(результат предыдущего CONS) и C

((A . B) . C)

 

Доступ к компонентам структуры данных:

 

 

Слева

 

CAR

(A . B)

A

CAR

((A . B) . C)

(A . B)

 

Справа

 

CDR

(A . B)

B

CDR

(A . (B . C))

(B . C)

 

Смешанная обработка данных:

 

CONS

A и B

(A . B)

CAR

результат предыдущего CONS

A

CONS

A и B

(A . B)

CDR

результат предыдущего CONS

B

CDR

(A . (B . C))

(B . C)

CAR

результат предыдущего CDR

B

CDR

(A . C)

C

CAR

результат предыдущего CDR

не определен

 

Тождества: (на произвольных объектах)

 

CONS

два произвольных объекта x и y

(x . y)

CAR

результат предыдущего CONS

исходный объект x (первый аргумент CONS)

CONS

два произвольных объекта x и y

(x . y)

CDR

результат предыдущего CONS

исходный объект y (второй аргумент CONS)

CAR

произвольный составной объектx

(CAR x)

CDR

тот же самый объект x - не атом

(CDR x)

CONS

результаты предыдущих CAR и CDR

исходный объект x

 

Предикаты:

 

 

Атомарность — неделимость

 

ATOM

(A . B)

Nil - выполняет роль ложного значения

CDR

(A . B)

B

ATOM

результат предыдущего CDR

T

 

Равенство:

 

EQ

(A . B) (A . B)

не определен

Точечная нотация точнее, чем списки, представляет логику хранения данных в памяти и доступа к компонентам структур данных, но для непосредственного представления и обработки символьных выражений она оказалась менее удобной. Практически сразу была предложена более лаконичная запись наиболее употребимого подкласса S-выражений в виде списков произвольной длины вида (A B C D E F G H ). В виде списков можно представить лишь те S-выражения, в которых при движении вправо в конце концов обнаруживается атом Nil, символизирующий завершение списка.
Атом Nil, рассматриваемый как представление пустого списка (), играет роль ограничителя в любом списке. Одноэлементный список (A) идентичен S-выражению (A . Nil). Список (A1 A2 ... Ak) может быть представлен как S-выражение вида:
(A1 . (A2 . ( ... . (Ak . Nil) ... ))).

Точечная нотация
Исторически при реализации Лиспа в качестве единой базовой структуры для конструирования S-выражений использовалась так называемая "точечная нотация" (dot-nоtation), согласно которой левая и правая части бинарного узла равноправны и могут хранить данные любой природы.
Бинарный узел, содержащий пару атомов  ATOM1 и ATOM2, можно представить в виде S-выражения вида:
( ATOM1 . ATOM2 )


Таблица 2.1. Операции над списками. Примеры соответствия аргументов и результатов

Функциия

Аргументы

Результат

 

Конструирование структур данных

 

CONS

A и Nil

(A )

CONS

(A B) и Nil

((A B) )

CONS

A и (B)

(A B)

CONS

(Результат предыдущего CONS) и (C)

((A B) C)

CONS

A и (B C)

(A B C)

 

Доступ к компонентам структуры данных:

 

 

Слева

 

CAR

(A B C)

A

CAR

(A (B C))

A

CAR

((A B) C)

(A B)

CAR

A

не определен

 

Справа

 

CDR

(A )

Nil

CDR

(A B C D)

(B C D)

CDR

(A (B C))

((B C))

CDR

((A B) C)

(C)

CDR

A

не определен

 

Смешанная обработка данных:

 

CDR

(A B C)

(B C)

CAR

результат предыдущего CDR

B

CAR

(A C)

A

CAR

результат предыдущего CAR

не определен

CONS

A и (B)

(A B)

CAR

результат предыдущего CONS

A

CONS

A и (B)

(A B)

CDR

результат предыдущего CONS

(B)

 

Предикаты:

 

 

Атомарность — неделимость

 

ATOM

VeryLongStringOfLetters

T

CDR

(A B)

(B)

ATOM

результат предыдущего CDR

Nil

ATOM

Nil

T

ATOM

( )

T

 

Равенство

 

EQ

A A

T

EQ

A B

Nil

EQ

A (A B)

Nil

EQ

(A B) (A B)

не определен

EQ

Nil и ( )

T

Если вместо атомов ATOM1, ATOM2 рекурсивно подставлять произвольные атомы, затем построенные из них пары и так далее, то получим множество всех возможных S-выражений. Можно сказать, что S-выражение — это или атом или заключенная в скобки пара из двух S-выражений, разделенных точкой. Все сложные данные выстраиваются из одинаково устроенных блоков — бинарных узлов, содержащих пары объектов произвольного вида. Каждый бинарный узел соответствует минимальному блоку памяти.
ATOM
(A . B)
(C . (A . B))
((A . B) . C)
((A . B) . (D . C))
((A . B) . (D . (C . E)))
Любое S-выражение может быть построено из атомов с помощью CONS, и любая его часть может быть выделена с помощью CAR-CDR.
Расширение типа данных, допускаемых в качестве второго аргумента CONS, ни в малейшей степени не усложняет реализацию этой функции, равно как и реализацию функций CAR и CDR, зато их описания становятся проще. Функция CONS строит бинарный узел и заполняет его парой объектов, являющихся значениями пары ее аргументов. Первый аргумент размещается в левой части бинарного узла, а второй — в правой. Функция CAR обеспечивает доступ к объектам, расположенным слева от точки, а функция CDR — справа.


Таблица 2.2. Операции над произвольными S-выражениями

Функция

Аргументы

Результат

 

Конструирование структур данных

 

CONS

A и B

(A . B)

CONS

(A . B) и C

((A . B) . C)

CONS

A B

(A . B)

CONS

(результат предыдущего CONS) и C

((A . B) . C)

 

Доступ к компонентам структуры данных:

 

 

Слева

 

CAR

(A . B)

A

CAR

((A . B) . C)

(A . B)

 

Справа

 

CDR

(A . B)

B

CDR

(A . (B . C))

(B . C)

 

Смешанная обработка данных:

 

CONS

A и B

(A . B)

CAR

результат предыдущего CONS

A

CONS

A и B

(A . B)

CDR

результат предыдущего CONS

B

CDR

(A . (B . C))

(B . C)

CAR

результат предыдущего CDR

B

CDR

(A . C)

C

CAR

результат предыдущего CDR

не определен

 

Тождества: (на произвольных объектах)

 

CONS

два произвольных объекта x и y

(x . y)

CAR

результат предыдущего CONS

исходный объект x (первый аргумент CONS)

CONS

два произвольных объекта x и y

(x . y)

CDR

результат предыдущего CONS

исходный объект y (второй аргумент CONS)

CAR

произвольный составной объектx

(CAR x)

CDR

тот же самый объект x - не атом

(CDR x)

CONS

результаты предыдущих CAR и CDR

исходный объект x

 

Предикаты:

 

 

Атомарность — неделимость

 

ATOM

(A . B)

Nil - выполняет роль ложного значения

CDR

(A . B)

B

ATOM

результат предыдущего CDR

T

 

Равенство:

 

EQ

(A . B) (A . B)

не определен

Точечная нотация точнее, чем списки, представляет логику хранения данных в памяти и доступа к компонентам структур данных, но для непосредственного представления и обработки символьных выражений она оказалась менее удобной. Практически сразу была предложена более лаконичная запись наиболее употребимого подкласса S-выражений в виде списков произвольной длины вида (A B C D E F G H ). В виде списков можно представить лишь те S-выражения, в которых при движении вправо в конце концов обнаруживается атом Nil, символизирующий завершение списка.
Атом Nil, рассматриваемый как представление пустого списка (), играет роль ограничителя в любом списке. Одноэлементный список (A) идентичен S-выражению (A . Nil). Список (A1 A2 ... Ak) может быть представлен как S-выражение вида:
(A1 . (A2 . ( ... . (Ak . Nil) ... ))).
В памяти это фактически одна и та же структура данных. (Запятая в качестве разделителя элементов списка в первых реализациях Лиспа поддерживалась, но не прижилась. Пробел оказался удобнее.)
Для многошагового доступа к отдельным элементам такой структуры удобно пользоваться мнемоничными обозначениями композиций из многократных CAR-CDR. Имена таких композиций устроены как цепочки из "a" или "d", задающие маршрут движения из шагов CAR и CDR, соответственно, расположенный между "c" и "r". Указанные таким способом CAR-CDR исполняются с ближайшего к аргументу шага, т.е. в порядке, обратном записи.


Таблица 2.3. Соответствие списков и равнозначных им S-выражений

List-notation — списочная запись объекта

Dot-notation — точечная нотация того же объекта

(A B C)

(A . (B . (C . Nil)))

((A B) C)

((A . (B . Nil)) . (C . Nil))

(A B (C E))

(A . (B . ((C . (E . Nil)). Nil)))

(A)

(A . Nil)

((A))

((A . Nil) . Nil)

(A (B . C))

(A . ((B . C) . Nil))

(())

(Nil . Nil)

Таблица 2.4. Примеры многошагового доступа к элементам структуры

 

Многократные CAR-CDR

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

Caar

((A) B C)

A

Cadr

(A B C)

B — CDR затем CAR

Caddr

(A B C)

C — (дважды CDR) затем CAR

Cadadr

(A (B C) D)

C — два раза (CDR затем CAR)

 

Основные понятия: программа, функции и выражения
Гипотезу об универсальности символьных данных, прежде всего, следует проверить при выборе представления форм, возникающих при написании программы и ее основного конструктива — переменных, констант, выражений, определений, ветвлений, вызовов функций:
1) Самая простая форма выражения — это переменная. Она может быть представлена как атом.
X
Y
n
Variablel
LongSong
2) Более сложные формы могут пониматься как применение функции к ее аргументам (вызов функции). Аргументом функции может быть любая форма. Вызов функции можно строить как список, первый элемент которого — представление функции, остальные элементы — аргументы функции.
(функция аргумент1 аргумент2 ... )
Обычно S-выражение — это или атом, или список; значит, неатомарное S-выражение можно понимать как вызов функции, если все остальные понятия свести к применению некоторых функциональных объектов.
Теперь можно записывать формы для получения результатов операций изв виде списков:
(ATOM Nil)
(CONS Nil Nil )
((LAMBDA (Y X) (CONS X Y)) Nil (ATOM Nil))
;= (T)
((LAMBDA (X Y) (CONS X Y)) Nil (ATOM Nil))
;= (() . T)
";" - начало строчного комментария. Последние два примера показывают роль порядка аргументов функции, задаваемого с помощью специального LAMBDA-конструктора.
3) Имена функций, как и переменных, лучше всего изображать с помощью атомов, для наглядности можно выбирать заглавные буквы.
Соответствие между именем функции и ее определением можно задать с помощью специального конструктора функций LABEL (отсутствует в Common Lisp), первый аргумент которого — имя функции, второй — собственно именуемое определение функции. Формальным результатом LABEL является ее первый аргумент, который становится объектом другой категории. Он меняет свой статус — теперь это имя новой функции.
(LABEL третий         ;        имя новой функции
(LAMBDA (x)      ;        параметры функции
(CAR (CDR (CDR x)))     ; тело функции
)   )
Пример 2.1.
Новая функция "третий" действует так же, как "Caddr" в. Именование функций работает подобно присваиванию значений переменным, но идентификатору присваивается объект другой категории — структура, символизирующая функциональный объект, содержащая список формальных параметров функции и тело ее определения. По отношению к процессам обработки данных разница между константами и переменными заключается лишь в том, что значение переменной может быть в любой момент изменено, а константа  изменяется существенно реже. Обычно в рассуждениях о переменных и константах подразумевается, что речь идет лишь о данных. Поскольку функциональное программирование рассматривает представления функций как данные, постольку и функции могут быть как константными, так и переменными. Представления функции могут вычисляться и передаваться как параметры или результаты других функций. Соответствие между именем функции и ее определением может быть изменено, подобно тому, как меняется соответствие между именем переменной и ее значением.
4) Композиции функций можно строить с помощью вложенных скобок.
(функция1 (функция2 аргумент21 аргумент22 ... )
аргумент2 ... )
Приведенные правила ничего не говорят ни о природе данных и функций, ни о порядке вычисления аргументов и композиций функций. Речь идет исключительно о форме — внешнем виде списков, используемых для записи программы. Такая синтаксическая оболочка, в которой еще не конкретизированы операции над данными, является общей спецификацией реализационной основы для определения аппликативных систем, допускающих специализацию практически в любом направлении. Можно сказать, что Лисп является аппликативной системой, специализированной для обработки списков или S-выражений. (Язык функционального программирования Sisal специализирован для обработки многомерных векторов и организации параллельных процессов, выполняемых на суперкомпьютерах.)
Этих правил достаточно, чтобы более ясно выписать основные тождества Лиспа, формально характеризующие элементарные функции CAR, CDR, CONS, ATOM, EQ над S-выражениями:
(CAR (CONS x y))       ; = x
(CDR (CONS x y))       ; = y
(ATOM (CONS x y))     ; = Nil
(CONS (CAR x) (CDR x))  ; = x       для неатомарных x.
(EQ x x)   ; = T       если x атом
(EQ x y)   ; = Nil     если x и y различимы
Любые композиции заданного набора функций над конечным множеством произвольных объектов можно представить таким способом, но класс соответствующих им процессов весьма ограничен и мало интересен. Организация более сложного класса процессов требует более детального представления в программах соответствия между именами и их значениями или определениями, изображения ветвлений и объявления констант.
5) Традиция при изучении функционального программирования избегать знакомства с явными средствами объявления значений переменных ради формирования навыков задания таких значений как аргументов функций малосостоятельна, т.к. изменение переменных легко моделируется переопределением функций без аргументов. Поэтому признаем сразу, что значение переменной можно объявить специальной функцией  SET.
(Set 'PI 3.1415926)
6) Обычно в системы программирования встраивают наиболее часто используемые константы. Некоторые атомы изначально имеют определенный смысл, например,  базовые функции, представление пустого списка Nil и тождественно истинная константа T
В зависимости от контекста одни и те же объекты могут играть роль переменных или констант, причем значения и того, и другого могут быть произвольной сложности. Если объект играет роль константы, то для объявления константы достаточно заблокировать его вычисление, то есть как бы взять его в кавычки (quotation), отмечающие буквально используемые фразы, нетребующие обработки. Для такой блокировки вводится специальная функция QUOTE, предохраняющая свой единственный аргумент от вычисления.
(QUOTE A)              ; константа атом A
(QUOTE (A B C) )    ; константа список (A B C)
(ATOM (QUOTE A))  ; = T — аргумент предиката - атом A  
(ATOM (QUOTE (A B C) )) ; = Nil — аргумент предиката - список (A B C)
(ATOM A)                ;— значение не определено
Оно зависит от вхождения переменной A, а ее значение зависит от контекста и должно быть определено или задано до попытки выяснить, атом ли это.
Можно сказать, что функция QUOTE выполняет в древовидной структуре программы роль помеченного контейнера. С ее помощью любое выражение может быть заключено в контейнер, а контейнер помечен указанием, что вычислять его содержимое не следует. Потом, при выполнении функции QUOTE, пометка и контейнер исчезают, и выражение может обрабатываться по общей схеме. Например: (третий (QUOTE (A B C))) — применение функции "третий" к значению, не требующему вычисления.
7) Некоторые определения функций могут быть хорошо определены на одних аргументах, но зацикливаться на других, подобно традиционному определению факториала при попытке применить его к отрицательным числам. Результат может выглядеть как исчезновение свободной памяти или слишком долгий счет без видимого прогресса. Такие функции называют частичными. Их определения должны включать в себя ветвления для проверки аргументов на принадлежность фактической области определения функции — динамический контроль. Точнее, вычисление ряда форм в определении может быть обусловлено заранее заданными предикатами.
Ветвление (условное выражение) характеризуется тем, что ход процесса зависит от некоторых предикатов (условий), причем условия следует сгруппировать в общий комплект и соотнести с подходящими ветвями. Такую организацию процесса вычисления обеспечивает специальная функция  COND (condition), аргументами которой являются двухэлементные списки, содержащие предикаты и соответствующие им выражения. Аргументов может быть сколько угодно, а обрабатываются они по особой схеме: сначала вычисляются первые элементы аргументов по порядку, пока не найдется предикат со значением "истина". Затем выбирается второй элемент этого аргумента, и вычисляется его значение, которое и считается значением всего условного выражения.
(COND (p1 e1) (p2 e2) ... (pk ek) )
pi - предикаты для выбора ветви,
ei - ветви условного выражения
Каждый предикат pi или ветвь ei может быть любой формы: переменная, константа, вызов функции, композиция функций, условное выражение.
Обычное условное выражение (if Predicate Then Else) или (если Predicate то Then иначе Else) может быть представлено с помощью функции COND следующим образом:
(COND (Predicate Then)(T Else))

Разумеется, можно повышать наглядность подбором геометрии текста:
(COND
(Predicate Then)
(T Else)
)
(COND
((EQ (CAR x) (QUOTE A))
(CONS (QUOTE B) (CDR x)) )
(T x)
)
Пример 2.2.
Атом T представляет тождественную истину. Значение всего условного выражения получается путем замены первого элемента из значения переменной  x на B в том случае, если (CAR x) совпадает с A
Содержательно функции QUOTE, COND, LAMBDA образуют базовый комплект средств управления программами и процессами, поддерживающий стиль программирования, идеологически близкий структурному программированию.
Такие специальные функции  QUOTE, COND, LAMBDA существенно отличаются от элементарных функций CAR, CDR, CONS, ATOM, EQ правилом обработки аргументов. Обычные функции получают значения аргументов, предварительно вычисленные системой программирования по формулам фактических параметров функции. Специальные функции не требуют такой предварительной обработки параметров. Они сами могут выполнять все необходимое, используя представление фактических параметров в виде S-выражений.

Рекурсивные функции: определение и исполнение
8) Определения могут быть рекурсивными.
На практике такие определения обычно имеют глобальные имена, задаваемы с помощью функции DEFUN, о которой еще будет речь в конце этой лекции. Сейчас теоретически можно ограничиться конструктором локальных функций LABEL, которую мы вводим здесь для учебных целей (в системе GNU Clisp его нет, но для него проще определение интерпретатора, которое будем строить в следующей лекции).
Как правило, рекурсивные вызовы функций должны быть заданы в комплекте с нерекурсивными ветвями процесса. Основное применение условных выраженийрекурсивные определения функций.
(LABEL премьер          ; имя локальной функции
(LAMBDA (x)          ; определение функции
(COND ((ATOM x) x)
(T (премьер (CAR x)))
)    )   )
Пример 2.3.
Новая функция "премьер" выбирает первый атом из любого данного. Если x является атомом, то он является результатом, иначе функцию «премьер» следует применить к первому элементу значения x, которое получается в результате вычисления формулы (CAR x). На составных x будет выполняться вторая ветвь, выбираемая по тождественно истинному значению встроенной константы T.
Определение функции "премьер" рекурсивно. Эта функция действительно работает в терминах самой себя. Важно, что для любого S-выражения существует некоторое число применений функции CAR, после которого из этого S-выражения выделится какой-нибудь атом, следовательно, процесс вычисления функции всегда определен, детерминирован и завершится за конечное число шагов. Можно сказать, что для определенности рекурсивной функции следует формулировать условие ее завершения.
Введенные обозначения достаточны, чтобы проследить за формированием значений и преобразованием форм в процессе исполнения функциональных программ. Рассмотрим вычисление формы:
((LABEL премьер 
(LAMBDA (x)
(COND ((ATOM x) x)
(T (премьер (CAR x)))
)    )    )    ; объявлена локальная функция "премьер"
(QUOTE ((A . B) . C) )  ; дан аргумент локальной функции
)   ; завершено выражение с локальной функцией
LABEL вырабатывает представление функции, которое тут же может быть применено к аргументу. При этом дает имена обычным функциям, поэтому фактический параметр функции «премьер» будет вычислен до того, как начнет работать ее определение, и переменная x получит значение ((A . B) . C)).
x = ((A . B) . C))


Таблица 2.5. Схема вывода результата формы с рекурсивной функцией

Вычисляемая форма

Очередной шаг

Результат и комментарии

 

Вход в рекурсию

(премьер (QUOTE ((A . B) . C)))

Выбор определения функции и

(COND ((ATOM x) x)(T (премьер (CAR x))) )

 

Первый шаг рекурсии

 

выделение параметров функции

(QUOTE ((A . B) . C))

(QUOTE ((A . B) . C))

Вычисление аргумента функции

x = ((A . B) . C)

(COND ((ATOM x)x)

Перебор

(ATOM x)

(T (премьер (CAR x))) )

предикатов: выбор первого

 

(ATOM x)

Вычисление первого предиката

Nil = «ложь», т.к. x — не атом. Переход ко второму предикату

T

Вычисление второго предиката

T = «истина» — константа. Переход к выделенной ветви

 

Второй шаг рекурсии

(премьер (CAR x))

выделение параметров функции

(CAR x)

(CAR x)

Вычисление аргумента функции

x = (A . B). Рекурсивный переход к редуцированному аргументу

(COND ((ATOM x) x) (T (премьер (CAR x))) )

Перебор предикатов: выбор первого

(ATOM x)

(ATOM x)

Вычисление предиката первого

Nil = «ложь», т.к. x — не атом. Переход ко второму предикату

T

Вычисление второго предиката

T = «истина» — константа. Переход ко второй ветви

 

Третий шаг рекурсии

(премьер (CAR x))

выделение параметров функции

(CAR x)

(CAR x)

Вычисление аргумента функции

x = A. Рекурсивный переход к редуцированному аргументу

(COND ((ATOM x) x) (T (премьер (CAR x))) )

Перебор предикатов: выбор первого

(ATOM x)

(ATOM x)

Вычисление первого предиката

T — т.к. x теперь атом.Переход к первой ветви

x

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

A Значение функции получено и вычисление завершено

 

Выход из рекурсии

Условные выражения не менее удобны и для численных расчетов:

(LABEL Абс
     (LAMBDA (x)
            (COND
                     ((< x 0 ) (- x))
                     (T x)
 )   )      )         
Пример 2.4. Абсолютное значение числа
(LABEL Факториал
     (LAMBDA (N)
         (COND
                ((= N 0 ) 1 )
   (T ( * N (Факториал (- N 1 ))) )
 )   )   )
Пример 2.5. Факториал неотрицательного числа
Это определение не завершается на отрицательных аргументах. Функция, определенная лишь для некоторых значений аргументов естественной области определения, называется частичной функцией.
Работа с числами, строками и другим элементарными типами данных обычно строится как включение в язык и систему так называемых самоопределимых данных, выглядящих достаточно естественно, чтобы их смысл не требовал особых пояснений. Включается и набор наиболее употребимых базовых операций над такими данными. Если введены числа, то введены и традиционные арифметические операции, но форма их применения подчинена общим правилам:
(+ 1 2 3 4) = 10
(LABEL НОД
     (LAMBDA (x y)
          (COND
                ((< x y) (НОД y x))
                ((= (остаток y x ) 0 ) x )
   (T (НОД (остаток y x) x ))
 )   )    )
Подробное изложение теории функций, определяемых рекурсивными выражениями, можно найти у многих математиков, например.
По мнению Дж. Мак-Карти, даже математики, включая логиков, термин "функция" используют не вполне аккуратно, применяя его к формулам вида "x + y^2" с уверенностью, что читатель, слушатель или собеседник правильно поймет, о чем идет речь. Автоматическая обработка данных, символизирующих функции, требует более точного различия между функциями и формами их применения. Для этих целей выработана система обозначений, известная как "лямбда-исчисление", которую предложил Алонсо Черч в работах по исследованию понятия "функция". Соответствующие рассуждения поясняются в книге по Lisp 1.5 на простом примере (неофициальный перевод):
«Допустим, F — выражение, представляющее функцию двух целочисленных переменных. Необходима возможность приписывать к представлению функции ее аргументы так, чтобы однозначно понимать, каким будет результат применения функции. Традиционная форма F [3, 4] пригодна для функций, значение которых не зависит от порядка аргументов, например, если речь идет о сумме или произведении чисел: сумма [3, 4] = сумма [4, 3] = 7. Выражение «x + y^2 [3, 4]» не удовлетворяет такому требованию. Из его записи не ясно, 13 или 19 является его значением. Поэтому «x + y^2» лучше называть не функцией, а формой, которую можно превратить в функцию, если дать способ точного определения соответствия между переменными, входящими в форму, и аргументами описываемой функции. Именно это и выполняется с помощью так называемого «лямбда-конструктора». Любую форму E можно превратить в функцию, если объявить перечень ее формальных аргументов x1,x2,...,xk в виде лямбда-выражения (LAMBDA (x1 x2 ... xk) E). Аргументы такой функции следует перечислять в том же порядке, в каком они перечислены в лямбда-выражении. Например, (LAMBDA (x y) (x + y^2) ) — может работать как функция двух переменных и (LAMBDA (x y) (x + y^2) ) [3, 4] = 3 + 4^2 = 19, а (LAMBDA (y x) (x + y^2) ) [3, 4] = 4 + 3^2 = 13.
Переменные в лямбда-выражении называются номинальными или связанными, потому что их систематическая замена не меняет смысла функции. Таким образом, (LAMBDA (z t) (z + t^2) ) — это то же самое, что и (LAMBDA (x y) (x + y^2) ). Возможны выражения, в которых не все переменные связаны. Например, в функции двух переменных (LAMBDA (z t) (z^N + t^N) ) переменная N не связана. Это так называемая «свободная» переменная. Ее можно рассматривать как параметр. Если значение такого параметра не задано до попытки вычислить функцию, то значение функции должно быть не определено».
Соответствие между именем функции и ее определением можно задать с помощью более удобной специальной псевдо-функции  DEFUN, первый аргумент которой — имя функции, второй — список ее формальных параметров, третий — собственно тело определения функции. Формальным результатом  DEFUN, как и LABEL, является ее первый аргумент, который также становится объектом другой категории, но теперь это имя новой функции, известной во всей дальнейшей программе.
(DEFUN третий  ; имя новой функции
           (x)        ; параметры функции
           (CAR (CDR (CDR x )))   ; тело функции
 )
Пример 2.7.
Новая функция "третий" действует почти так же, как и ранее приведенное определение, но теперь можно функцию рассматривать как глобальную и обращаться к ней в форме.
(третий (QUOTE (A B C)) ) ; — применение новой функции
Вышеописанные лямбда-обозначения не вполне удобны для именования рекурсивных функций, хотя это возможно. Название функции используется внутри рекурсивных определений, символизируя целое определение. При определении функции «премьер» удобнее использовать специальную функцию DEFUN, связывающую название функции и с определяющей формой, и со списком переменных.
(defun премьер (x)
    (cond ((atom x) x)
             (T (премьер (car x)) )
 )  )
Собственно механизм связывания пока определен не был. Функция DEFUN использует лямбда-конструктор, чтобы представление функции получалось более естественно и использовалось как единая конструкция. Фактически LABEL и DEFUN реализуют аналог тождества:
премьер = (LAMBDA (x) (cond ((atom x) x)
                                             (T (премьер (car x)) ) ))
Роль локального связывания имени и определения функции в Лиспе выполняет специальная функция LABEL. Если EF — определение, а NF — его имя, то (LABEL NF EF) — функция, знающая свое имя NF. В форме (DEFUN премьер (x) (cond ((atom x) x) (T (премьер (car x))) )) x — связанное имя переменной, а «премьер» — связанное имя функции, доступное программе.
Механизм конструирования определений функций на базе LABEL более логичен, чем DEFUN: наличие локального механизма формально пригодно и для реализации глобальных связей — они просто должны быть объявлены или расположены раньше всех локальных. Именно так и был формально определен реализационный базис чистого Лиспа для раскрутки полной Лисп-системы. Но на практике поначалу удобнее пользоваться функцией DEFUN, отдавая себе отчет в том, что это нечто вроде строительных лесов, помогающих создать более стройное здание. DEFUN совмещает работу LABEL и LAMBDA — сразу, как и в большинстве языков программирования, позволяет ввести и название функции, и имена ее арументов. Если LABEL строит именованную функцию для ее рекурсивного применения внутри текущего выражения, то DEFUN запоминает определение имени для вызова функции в любом месте программы.
Как и любая форма, любое S-выражение, символьные представления функций могут быть значениями аргументов — функциональные аргументы.
Базис элементарного Лиспа образуют пять функций над S-выражениями, CAR, CDR, CONS, ATOM, EQ, и четыре специальных функции, обеспечивающие управление программами и процессами и конструирование функциональных объектов QUOTE, COND, LAMBDA, LABEL.
Точные границы применимости построений над таким базисом будут определены в следующей лекции в форме определения универсальной функции EVAL, позволяющей вычислять значения выражений, представленных в виде списков, — правило интерпретации выражений.
Формально для перехода к самостоятельным упражнениям нужна несколько большая определенность по механизмам исполнения программ, представленных S-выражениями:

  • аргументы функций, как правило, вычисляются в порядке их перечисления;
  • композиции функций выполняются в порядке от самой внутренней функции наружу до самой внешней;
  • представление функции анализируется до того, как начинают вычисляться аргументы, т.к. в случае специальных функций аргументы можно не вычислять;
  • при вычислении лямбда-выражений связи между именами переменных и их значениями, а также между именами функций и их определениями, накапливаются в так называемом ассоциативном списке, пополняемом при вызове функции и освобождаемом при выходе из нее.
 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика