40гг первые цифровые компьютеры программирование путем коммутации проводов

1   ...   4   5   6   7   8   9   10   11   12

(define & and)

(& (< 1 2) (< 2 3))

#t

Значение and, то есть встроенная функция связывается с именем &, после чего & можно использовать вместо and.


(define (sqr x) (* x x))

sqr

#


(sqr 5)

25

Теперь с именем sqr связана вновь определённая функция и ее можно использовать для возведения в квадрат. Подобно встроенным функциям, она не отображается. Дело в том, что интерпретатор не сохраняет определения как синтаксические деревья, а компилирует их в байт-код.


Лямбда-выражения

В Лиспе можно отделить два понятия - определение функции, и её именование.

Дать имя функции можно все той же конструкцией define  

(define sqr <функция возведения в квадрат>)
а определить - с помощью специальной формы: лямбда-выражения.

(lambda (a1…an) e)

возвращает функцию, вычисляющую значение выражения e при подстановке фактических параметров вместо a1…an.


Например, sqr можно было бы определить и так

(define sqr (lambda (x) (* x x)))

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

([lambda (x) (* x x)] 2)
4


Связывающие формы

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

(let ((a1 e1)(a2 e2) … (an en)) e)

Значением этой формы будет значение выражения e, в котором каждое ai заменено значением выражения ei.

Например, функция для вычисления площади треугольника по формуле Герона.

(define (square-triangle a b c)

(let ((p (/ 2 (+ a b c))))

(sqrt (* p (- p a) (- p b) (- p c))))


Того же эффекта можно было бы добиться применяя лямбда-выражение.

(define (square-triangle a b c)

(lambda (p) (sqrt (* p (- p a) (- p b) (- p c))) (/ 2 (+ a b c))))


Семантически это одно и то же, но, запись с let намного нагляднее


Составные данные

Любые два объекта можно объединить в новый объект, называемый (точечной) парой с помощью примитивной функции cons. Чтобы получить составные части пары, используются функции car и cdr.

(cons a b) - возвращает составной объект - пару (a . b)

(car a) - возвращает первый элемент пары

(cdr a) - возвращает второй элемент пары

(define x (cons 1 2))
x
(1 . 2)
(car x)
1
(cdr x)
2

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


(pair? a)


возвращает #t, если аргумент представляет собой пару и #f в противном случае.


Вложенные цепочки пар называются списками.

(cons 1 (cons 2 (cons 3 () )))
(1 2 3)

Списки играют особую роль в Лиспе. Чтобы упростить их формирование, предусмотрена специальная функция list.

(list a1…an) возвращает список объектов  (a1…an), то есть (a1 .(a2 . …(an . nil)…)).

(list 1 2 3)

(1 2 3)

(car (list 1 2 3))

1

(cdr (list 1 2 3))

(2 3)


В действительности, выражения Лиспа представляют собой ни что иное, как списки. Это даёт возможность обрабатывать их как данные. Чтобы получить выражение как таковое, а не его значение используется специальная форма quote.

(quote a) - возвращает в качестве значения свой аргумент, не вычисляя его. Аналог – знак апострофа.

(quote a) а	''a (quote a)	(car '(+ 1 2)) +
'а а	'(+ 1 2) (+ 1 2)	䦋㌌㏒㧀좈໱琰茞ᓀ㵂Ü

Противоположность quote - функция eval, вычисляющая значение выражения.

(eval '(+ 1 2))

3

(eval (list + 1 2))

3


Рекурсивные определения.


Для того чтобы рекурсивное определение было полезным необходимо выполнение следующих двух условий:

1. Наличие нерекурсивного определения для базового случая.
   
2. Параметр рекурсивного обращения должен быть «проще», чем параметр определяемой функции.
   

Вычисление факториала

Факториал положительного целого числа n определяется как произведение всех чисел от 1 до n.

n!=1*2*3*…*n.

Для любого n>1 n! = n*(n-1)!. Таким образом, мы можем вычислить n!, вычисляя (n - 1)! и умножая результат на n. Если мы прибавим соглашение что 1! = 1, получим следующее определение:

(define (fac n)

(cond ((= n 1) 1)

((> n 1) (* n (fac (- n 1))))))

(fac 20)

2432902008176640000

(/ (fac 100) (fac 99))

100


Числа Фибоначчи

Определение чисел Фибоначчи само по себе рекурсивно. Каждое число в последовательности, кроме двух первых является суммой двух предшествующих.

F1 = 1
F2 = 1
Fn = Fn-1+ Fn-2.

Это определение непосредственно записывается на Лиспе.

(define (fib n)

(cond ((= n 1) 1)

((= n 2) 1)

((> n 2) (+ (fib (- n 1)) (fib (- n 2))))))


Наибольший общий делитель (НОД)

НОД двух натуральных чисел a и b определен, как наибольшее натуральное число, которое делит a и b без остатка. Если число n делит оба числа а и b, то оно делит их сумму и разность, и отсюда

НОД(a, b) = НОД(a+b, b) = НОД(a, a+b) = НОД(a-b, b) = НОД(a, a-b).

Можно найти ещё множество интересных свойств НОД, но уже здесь мы замечаем, что НОД(a-b, b) выглядит несколько «проще» чем НОД(a, b) в том смысле, что приходится иметь дело с меньшими числами. Добавляя сюда тот очевидный факт, что НОД(a, a) = a, приходим к знаменитому алгоритму Евклида.

(define (gcd a b)

(cond ((= a b) a)

((> a b) (gcd (- a b) b) )

((< a b) (gcd (- b a) a) )))