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

Лабораторная работа 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, описать функцию, позволяющую определить, попадет ли точка с заданными координатами в область, ограниченную прямоугольником

 

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