Понятие строго функционального языка.
Функциональное программирование – это способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программ на части (модульность) является введение имени для функции, а единственным правилом композиции – оператор суперпозиции функции. Теоретической базой для функционального программирования является лямбда-исчисление Алонсо Черча. Не используются операторы (присваивания, цикла, передачи управления, etc.), блок-схемы, передачи управления.
Структуризация данных
Функции более высокого порядка
Определение функции. Безымянная лямбда функция.
Функция есть отображение (mapping), которое однозначно отображает одни значения на другие.
В языке Лисп как для вызова функций, так и для записи выражений принята единообразная форма записи, при которой имя функции и ее аргументы записываются внутри скобок. Общий формат записи следующий:
(name_function arg_1 arg_2 … arg_n), где
name_function – имя функции;
arg_I – аргументы.
Такая форма записи называется S-выражением.
Ключевое понятие, базис функционального программирования лямбда-функция.
В Лиспе лямбда-выражение имеет вид
(lambda(x1,x2,x3,…xn) fn.).
Символ lambda означает, что речь идет об определении функции. Символы xi – формальные параметры определения, a fn – тело функции. Телом функции является произвольная форма. Под формой следует понимать любое выражение, значение которого может вычислить интерпретатор Лиспа.
Функцию вычисления суммы двух чисел можно определить следующим образом: (lambda (x y)(+ x y)). Здесь x и y – формальные параметры, а (+ x y) – тело лямбда-выражения.
Списки, операции над списками.
Список в Лиспе это упорядоченная последовательность, элементами которой являются атомы либо списки. Списки заключаются в круглые скобки, элементы списка разделяются пробелами. Список всегда начинается с открывающей скобки и заканчивается закрывающей скобкой. Например, следующий список состоит из трёх символов и одного подсписка, который в свою очередь состоит из двух атомов:
(x y (z 1) z)
Список это многоуровневая структура данных, в которой открывающие и закрывающие скобки находятся в строгом соответствии.
Список, в котором нет ни одного элемента, называется пустым списком и обозначается () или символом nil. Пустой список - это не то же самое, что "ничего".
Внутреннее представление списков.
Оперативная память машины, на которой работает Лисп, логически разбивается на области, которые называются списочными ячейками. Списочная ячейка состоит из двух частей, поля CAR и CDR. Каждое поле содержит указатель на объект или другую списочную ячейку. Указатели между ячейками образуют цепочку, по которой можно из предыдущей ячейки попасть в следующую. Графически списочная ячейка представляется прямоугольником (рис. 1), разделенным на две части – поля CAR и CDR.
Рис. 1. Графическое представление точечной пары
Изображение одноуровнего списка состоит из последовательности ячеек, связанных друг с другом через указатели в правых частях ячеек (рис. 2).
Правое поле последней ячейки списка в качестве признака конца списка ссылается на пустой список (ячейка перечеркнута). Указатели полей CAR ячеек списка List ссылаются на атомарные структуры, в данном случае на атомы A, B, C.
Рис. 2. Внутренне представление одноуровнего списка (A B C)
При определении базового примитива CONS упоминалось, что ее вторым аргументом обязательно должен быть список. Сейчас это ограничение снимается и в дальнейшем результатом функции (cons ‘a ‘b) будет являться новая структура (a . b), называемая точечной парой. Точечная пара – это не список, а более общее символьное выражение. Название происходит от использования в ее записи символа точки, обязательно выделенного с обеих сторон пробелами. Выражение слева от точки (атом, список, другая точечная пара) соответствует полю CAR, а выражение с права от точки – полю CDR.
Точечная нотация позволяет расширить класс объектов, представляемых с помощью списков. Ситуацию сравнивают с использованием дробей или комплексных чисел в арифметике.
Любой список можно записать в точечной нотации. Преобразование можно осуществить на всех уровнях следующим образом: (a1 a2 …an) ↔ (a1 . (a2 . …(an . NIL)…)). Например, список (a b c) в точечной нотации представляется следующим образом (a . (b . (c . NIL))).