Введение в функциональное программирование

Тема : основы функционального программирования.

Основные термины, ключевые слова: функция, область определения, область значения, единообразное соответствие, S-выражение, базовые функции (примитивы) языка Lisp.

Инструмент для выполнения работы: интерпретатор языка Lisp под Windows –XLispWin.

Содержание отчета:

- титульный лист установленного образца;

- краткие теоретические сведения;

- задание на работу;

- описание S-выражения согласно варианту задания;

- описание применения базовых функций к полученному в предыдущем пункте S-выражению;

- выводы по работе.

Основные теоретические сведения. Функциональное программирование – это способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программ на части (модульность) является введение имени для функции, а единственным правилом композиции – оператор суперпозиции функции. Теоретической базой для функционального программирования является лямбда-исчисление Алонсо Черча. Не используются операторы (присваивания, цикла, передачи управления, etc.), блок-схемы, передачи управления.

Язык Lisp (LISt Processing – обработка списков) разработан в 1961 г. американским ученым Дж. Маккарти. Стандартом языка считается Common Lisp (общеупотребительный Лисп), который является расширением теоретически «чистого» Лиспа с ограниченным набором примитивов для обработки списков. Уже к 1962 г. число версий языка стало исключительно большим, библиотека языка пополнилась далеко не самыми примитивными функциями, работающими не только со списками, но и с другими структурами данных. Следует отметить, что в японском проекте машин пятого поколения в качестве одного из базовых языков выбор пал на Лисп.

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

Фундаментальным понятием математики является функция. Функция есть отображение (mapping), которое однозначно отображает одни значения на другие. Например, запись y=f(x) ставит в соответствие каждому элементу x из области определения (domain) единственный элемент y из области значений (range)) функции f.

В математике и обычных языках программирования используется префиксная запись функции, в которой имя функции стоит перед скобками, обрамляющими аргументы: f(x), fun(x, y), f(x, g(y, u)), etc. В языке Лисп как для вызова функций, так и для записи выражений принята единообразная форма записи, при которой имя функции и ее аргументы записываются внутри скобок. Общий формат записи следующий:

(name_function arg_1 arg_2 … arg_n), где

name_function – имя функции;

arg_I – аргументы.

Такая форма записи называется S-выражением.

Таким же образом записываются арифметические выражения, например, (+ 2 3), (- 4 3), (* x (+ y z)), etc. К такому способу записи программист привыкает быстро.

С помощью S-выражений в Лиспе представляются и структуры данных, например, информацию о каком-либо субъекте можно сформировать следующим образом:

((фамилия иванов)(имя иван)(отчество иванович)).

Характерной особенностью S-выражения является наличие скобок. Действительно, их количество и местоположение влияет на смысл и результат S-выражения. Кроме скобок в любом S-выражении имеются элементы, называемые атомами. Различают два типа атомов: символьные и числовые. Символьный атом состоит обычно из букв, но может содержать и другие символы (числа, символ подчеркивания), но обязательно должен содержать хотя бы один символ, отличающий его от числа. Символьный атом нельзя расчленять на составляющие символы. Единственная операция, допустимая над символами – операция сравнения. Числовой атом является последовательностью цифр, возможно следующих за знаком.

S-выражение может состоять из произвольной смеси символьных и числовых атомов. Простейшая форма S-выражения – атом.

Основное назначение Лиспа – обработка списков. В языке имеется набор базовых функций (примитивов) для работы со списками. Различают следующие виды функций – разбора (селекторы), создания (конструкторы) и проверки (предикаты).

Функции селекторы. Первый элемент списка является его головой (head), оставшиеся элементы – хвостом (tail) списка. Отделить голову от списка можно с помощью функции car, общий формат которой представляется следующим образом:

(car list)< enter>

Результатом работы функции будет S-выражение или сообщение об ошибке, если аргумент не является списком.

Примеры использования функции car:

1. > (car ‘(a s d f)); вызов функции

> a; ответ интерпретатора.

Комментарии к примеру. В первом предложении после вызова функции car, перед списком стоит символ апостроф (‘). Это специальный вид функции, который блокирует вычисления. Если его опустить, то интерпретатор воспримет первый элемент (символ а) списка как имя функции и попытается вызвать ее на исполнение. Эквивалентное действие (блокировку вычислений) выполняет функция quote, например для этого выражения эквивалентная форма записи будет выглядеть следующим образом: > (car (quote (a s d f))). Символ > – приглашение интерпретатора. Результат вызова функции, голова списка, представлен во второй строке.

2. > (car ‘cat)

error: bad argument type – CAT.

Здесь действительно аргумент функции является не списком, а атомом.

3. > (car ‘((a s d) e r t))

> (a s d).

Как видно из последнего примера, в качестве головы списка может выступать произвольный объект, в том числе и список.

Следующая функция cdr – отделение хвоста от списка– имеет следующий формат:

(cdr list)< enter).

Результат работы функции – хвостовая часть списка.

Примеры использования функции cdr:

1. > (cdr ‘(a s d f))

> (s d f).

Следует отметить, что хвост списка также является списком.

2. > (cdr ‘(a))

> NIL.

Функция cdr определена только для списков и, из соображения удобства значением функции от пустого списка считается NIL. NIL – константа языка, обозначающая либо ложь, либо пустой список. В противоположность константа Т обозначает истину.

3. > (cdr ‘cat)

error: bad argument type – CAT

Выдача ошибки в данном случае уместна, так как аргумент не является списком.

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

(cons head old_list)< enter>

Одно замечание относительно второго аргумента – он обязательно должен быть списком. Примеры использования:

1. > (cons ‘a ‘(s d f))

> (a s d f).

Здесь видно, что функция cons конструирует из двух своих аргументов, первый из которых является произвольным объектом, в данном случае – символ, а второй – список, новый список – (a s d f).

2. > (cons (* 2 3) ‘(+ 4 4)).

Оттранслируйте это выражение, оцените и проанализируйте полученный ответ.

Предикаты Лиспа. Функции, проверяющие наличие свойства у своего аргумента, называются предикатами. В качестве результата предикаты возвращают либо T (true), либо NIL (false). Число предикатов и их имена могут существенно отличаться в различных реализациях языка. К числу основных (базовых) предикатов, имеющихся во всех реализациях, следует отнести:

(atom s-выражение) – возвращает Т, если аргумент является атомом;

(integerp num) – возвращает Т, если аргумент – целое число;

(floatp num) – возвращает Т, если аргумент – вещественное число;

(numberp num) – возвращает Т, если аргумент – число;

(oddp num) – возвращает Т, если аргумент – нечетное число;

(listp lst) – возвращает Т, если аргумент – список;

(null lst) – возвращает Т, если список пуст.

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

Отдельно необходимо отметить группу предикатов сравнения объектов, к таковым относятся:

(eq arg_1 arg_2) – возвращает Т, если оба аргумента являются символами;

(eql arg_1 arg_2) – возвращает Т, если оба аргументы числа одного типа (целые или вещественные) или же символы;

(equal arg_1 arg_2) – производит наиболее общее сравнение. С помощью этого предиката можно сравнивать списки;

(= num_1 num_2) – предикат для сравнения чисел произвольных типов.

Эти предикаты также следует опробовать в индивидуальном задании.

Индивидуальное задание.

Для всех вариантов выполнить следующие пункты:

1. Определить структуру, описывающую родственные связи между членами Вашей семьи (фамилии), например,

‘((отец(иванов иван петрович))

(мать(иванова мария сергеевна))

(сын(иванов петр иванович)))

…………

Можно (очень желательно) внести еще какую-нибудь информацию, например, возраст каждого человека, заработок и т.д. Количество членов семьи не менее 5.

2. Из полученной структуры выделить голову списка (главу семейства).

3. Из полученной структуры выделить оставшихся членов семьи.

4. Добавить новых членов Вашей семьи, например, если к Вам приехала (переехала) любимая бабушка (теща) или дед. Возможно, что кто-то из Ваших братьев женился или сестра вышла замуж.

5. Опробовать работу и проанализировать результаты предикатов Лиспа, проверяющих свойства объектов и предикатов группы сравнения. В отчете необходимо привести примеры их использования и реакцию интерпретатора.

Лабораторная работа 8

Функции в языке Лисп.

Вычисления в Лиспе

Тема : Лямбда-функция, определение функций пользователя.Вычислительные возможности языка Лисп.

Основные термины, ключевые слова: лямбда-определение, формальные и фактические параметры, лямбда-выражение, лямбда-функция, тело функции, форма.

Инструмент для выполнения работы: интерпретатор языка Lisp под Windows – XLispWin.

Содержание отчета:

- титульный лист установленного образца;

- краткие теоретические сведения;

- задание на работу;

- лямбда-выражение согласно индивидуальному варианту;

- определение собственных функций;

- изображение графика (эскиза функции) согласно третьему пункту индивидуального задания;

- выводы по работе.

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

lambda(x₁, x₂, x₃, …x_n), f_n_.

В Лиспе лямбда-выражение имеет вид

(lambda(x₁, x₂, x₃, …x_n) f_n_.).

Символ lambda означает, что речь идет об определении функции. Символы x_i – формальные параметры определения, a f_n – тело функции. Телом функции является произвольная форма. Под формой следует понимать любое выражение, значение которого может вычислить интерпретатор Лиспа. Функцию вычисления суммы двух чисел можно определить следующим образом: (lambda (x y)(+ x y)). Здесь x и y – формальные параметры, а (+ x y) – тело лямбда-выражения. Еще один пример, добавление нового элемента в список:

(lambda (x y) (cons x y)).

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

(lambda-expression a₁a₂ a₃ … a_n).

Здесь a_i – формы, задающие фактические параметры, например, для определения функции сложения двух чисел:

((lambda (x y)

(+ x y)) 34 61) < enter>.

Числа 34 и 61 представляют фактические параметры лямбда-вызова.

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

(defun name lambda-list body).

Если еще раз вернуться к вопросу сложения двух чисел, то его можно определить с помощью функции defun следующим образом:

(defun sum (x y)

(+ x y)).

Как видно из определения, здесь sum – имя функции (оно должно быть содержательным), x и y – формальные аргументы функции, играющие роль лямбда-списка. Тело функции должно выполнить все необходимые действия, согласно спецификации.

В языке Лисп есть функции и предикаты, позволяющие определить наличие связи символа с определением функции, а также выдающие в качестве результата определение функции или физический адрес начала функции в оперативной памяти машины. Предикат (fboundp name) принимает значение истина, если с именем name связано определение функции. Функция (symbol–function name) в качестве результата выдает определение функции.

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

1. Самоопределенные (self-evaluating) формы. Это лисповские объекты, представляющие лишь самих себя. К ним относят константы языка (T, NIL), числа.

2. Символы, используемые в качестве имен переменных.

3. Формы в виде списочной структуры, которыми являются:

3.1. Вызовы функций и лямбда-вызовы.

3.2. Специальные формы (special form), формы предназначенные для управления вычислительным процессом и контекстом.

3.3. Макровызовы.

К специальным формам относят такие формы, как let – создание локальной сети, prog1, prog2, prong – последовательные вычисления, cond, if, when, unless и др. – разветвление вычислительного процесса.

Новые локальные связи внутри какой-либо формы можно создать с помощью предложения (формы) let, которое имеет следующий формат:

(let ((m₁val₁)(m₂ val₂)…)

form₁

form₂

form₃ …),

где m_i – статические переменные, val_i – соответствующие им значения. Связывание происходит одновременно (! ), после чего последовательно вычисляются формы form₁, form₂, etc. Связи статических переменных со значениями после выполнения предложения теряются. Пример использования этого предложения: (let ((x 10) (y 20)) (* x y)), после чего следует ожидать результат произведения чисел 10 и 20.

Предложения серии prog предназначены для выполнения последовательных вычислений с несколькими формами. Общий формат этих предложений следующий:

(prog1 form₁ form₂ … form_n)

(prog2 form₁ form₂ … form_n)

(progn form₁ form₂ … form_n)

Во всех предложениях последовательно выполняются form₁ form₂ … form_n, а в качестве результата выдается значение соответственно первой, второй и последней форм. Примеры использования этих форм:

(prog1 (+ 23 44) (setq x 2) (setq y 8)), здесь в качестве результата следует ожидать сумму чисел 23 и 44, кроме того, создаются связи переменных x и y c помощью псевдофункции setq.

(prog2 (setq z 28) (/ z 4)), здесь в качестве результата можно ожидать число 7.

(prong (setq x 564) (setq y 34)(< x y)), результат – NIL.

Группа предложений для управления ходом вычислительного процесса в первую очередь представляется следующим предложением:

(cond (pred₁ form₁)

(pred₂ form₂)

…………….

(pred_n form_n)),

где pred_i – предикат, form_i – произвольная форма.

Работа предложения происходит по следующему сценарию: последовательно вычисляются значения предикатов pred_i до тех пор, пока значение одного из них не будет NIL, после чего вычисляется значение связанной с предикатом формы, которое выдается в качестве результата всего предложения. Если истинного предиката не обнаруживается, то в качестве результата выдается NIL. Рекомендуется в качестве последнего предиката использовать символ Т (true), и соответствующее ему результирующее выражение будет вычисляться всегда, когда ни одно другое условие не выполняется. Классический пример использования предложения cond – определение функции, которая в качестве результата выдает «тип» своего аргумента.

(defun type(arg)

(cond ((null arg) ‘null_list); пустой список

((integerp arg) ‘integer_number); целое число

((atom arg) ‘atom); атом

(t ‘list))); список.

Определение функции очевидно. Еще несколько предложений из этой группы:

(if condition then_form else_form)

(when condition form₁ form₂ … form_n)

(unless (not_condition) form₁ form₂ … form_n).

Предложение if по структуре и по результатам работы аналогично подобному предложению в алгоритмических языках программирования. Если выполняется условие (предикат), то результатом предложения будет then_form (то_форма), в противном случае – else_form (иначе_форма).

Предложения when и unless вначале вычисляют значение условия (предиката), а затем последовательно вычисляют формы form_i в случае, если условие выполняется (для when) или не выполняется (для unless). В качестве результирующего значения выдают значение последней формы или NIL.

Индивидуальные задания

1. Определить лямбда-вызов для вычисления площади прямоугольного треугольника. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную окружностью заданного диаметра. Центр окружности в точке с произвольными координатами.

2. Определить лямбда-вызов для вычисления площади равнобедренного треугольника. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную прямоугольником

3. Определить лямбда-вызов для вычисления площади равнобедренного треугольника. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную прямоугольником.

4. Определить лямбда-вызов для вычисления площади параллелограмма. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную прямоугольником. Прямоугольник распложен в произвольном месте.

5. Определить лямбда-вызов для вычисления площади ромба. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную тремя пересекающимися прямыми на плоскости

6. Определить лямбда-вызов для вычисления площади окружности. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную шестиугольником правильной формы. Расположение шестиугольника в прямоугольной системе координат – по желанию.

7. Определить лямбда-вызов для вычисления площади правильного n-угольника. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную параллелограммом, одна из сторон которого совпадает с осью абсцисс

8. Определить лямбда-вызов для вычисления площади поверхности куба. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную квадратом, сторона которого задается в виде отдельного параметра функции. Расположение квадрата в прямоугольной системе координат – по желанию.

9. Определить лямбда-вызов для вычисления площади поверхности шара. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную функцией sin и осью абсцисс.

10. Определить лямбда-вызов для вычисления площади поверхности треугольной пирамиды. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную функцией cos и осью абсцисс.

11. Определить лямбда-вызов для вычисления площади поверхности параллелепипеда. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную окружность единичного радиуса и осями координат. Центр окружности совпадает с началом системы координат.

12. Определить лямбда-вызов для вычисления площади поверхности шестиугольной призмы. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную квадратом, центр которого совпадает с началом системы координат и осями координат.

13. Определить лямбда-вызов для вычисления площади поверхности конуса. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную осями координат и прямой y = –kx..

14. Определить лямбда-вызов для вычисления объема шара. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную окружностью заданного радиуса. Расположение окружности в системе координат – произвольное.

15. Определить лямбда-вызов для вычисления объема шестиугольной призмы. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную прямоугольником. Размеры прямоугольника и его местоположение в системе координат – по выбору.

16. Определить лямбда-вызов для вычисления объема конуса. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную равнобедренной трапецией. Местоположение и размеры трапеции должны выступать как аргументы функции.

17. Определить лямбда-вызов для вычисления длины окружности заданного диаметра. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную прямой параллельной оси ординат, отстоящей от нее на расстоянии x и функцией синуса.

18. Определить лямбда-вызов для вычисления объема цилиндра. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную окружностью единичного радиуса с центром в точке с координатами x и y.

19. Определить лямбда-вызов для вычисления объема усеченной четырехугольной пирамиды. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную прямой параллельной оси абсцисс, отстоящей от нее на расстоянии y и функцией косинуса.

20. Определить лямбда-вызов для вычисления объема усеченной треугольной пирамиды. Определить функцию пользователя для предыдущего задания. Пользуясь предложениями cond, if, when или unless, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную окружность единичного радиуса и осями координат. Центр окружности совпадает с началом системы координат.

Примечание. В качестве варианта по третьему пункту индивидуального задания рекомендуется использовать различные виды предложений управления ходом вычислительного процесса. Это позволит оценить каждое из предложений и выработать навык применения каждого предложения в конкретных условиях.

Лабораторная работа № 9

⇐ Предыдущая 1 2 345 6 Следующая ⇒