32. Реализация вспомогательных функций для работы со списками (обращение по индексу, длина, мэпинг)
Получает в списке items n-й элемент:
(define (list-ref items n)
(if (= n 0)
(car items)
(list-ref (cdr items)(- n 1))
)
)
Получить длину списка:
(define (length items)(if (null? items) 0 (+ 1 (length (cdr items)))))
Применение функции ко всем элементам (мэпинг — отображение):
(define (map proc items)
(if (null? items)
nil
(cons (proc (car items))
(map proc (cdr items))
)
)
)
33. Горизонтальные барьеры абстракции. Диспетчеризация по типу
Горизонтальные барьеры отделяют «высокоуровневые» операции от «низкоуровневых» представлений.
Концептуальный уровень <-> Логический уровень <-> Физический уровень.
Главное, что нет вызовов физического из концептуального уровня.
Вертикальный барьер даёт нам возможность отдельно разрабатывать и добавлять альтернативные представления. У одной и той же логики может быть несколько реализаций. Функционально они одинаковы, но по-разному работают. Необходимо поддерживать несколько реализаций одного интерфейса. Подходы:
Диспетчеризация по типу
Программирование, управляемое данными
Диспетчеризация по типу
Рассматриваем пример с точкой на плоскости. Будем использовать две системы координат: декартову и полярную. У функций для декартовых координат будет префикс d_, а у полярных — p_. Создаём соответствующие конструкторы, которые внутри автоматически пересчитывают в нужные координаты:
И дополнительные методы:
d_get_x
d_get_y
d_get_r
d_get_ϴ
Такой же набор функций для точки в полярной системе координат, но реализация другая.
Любые данные (точки) представляются в виде:
(метка (b c))
Метка показывает, в каком виде хранится пара, декартовая или полярная система.
(define (get_x point)
(if (eq? (car point) `dec)
(d_get_x (cdr point))
(p_get_x (cdr point))
)
)
34. Программирование, управляемое данными
|
Операции ↓
|
|
Реализации →
|
d_x
|
d_y
|
|
p_x
|
p_y
|
Занести в таблицу значений: (put операция код_реализации функция)
Возвращает нужную функцию:(get op type)
(define (install decart)
(put `get_x `dec d_gex_x)
(put `get_y `dec d_gex_y)
)
(define (install decart)
(define …)
(define …)
)
(define (get_x point)
(
(get `get_x (car point))
(cdr point)
)
)
В этом и в предыдущем методе функция-селектор делает столбик таблицы, а install делает строчку. Это как управление сообщениями. Каждая функция соответствует типу.
35. Система с обобщёнными операциями
Обобщённые — это значит, что может принимать аргументы разных типов.
В код зашиваем еще и информацию, какие аргументы. Тип первого аргумента соответствует первому столбцу.
36. Приведение типов. Реализация
Добавляются столбцы, которые реализуют приведение. Сколько типов, столько и столбцов.
+
|
coercion-int
|
...
|
|
n → i
|
...
|
|
i → i
|
...
|
|
r → i
|
...
|
a+b: если типы одинаковые, то вычисляем. Иначе приводим. Когда два аргумента, можем жёстко прописать, что именно к чему приводить.
Иерархия типов. Если не можем выполнить приведение, переходим к надтипу.
Для каждой операции определяется набор допустимых значений типов аргументов и правил получения типа результат. Используется иерархия типов.
|
|
37,38. Моделирование объектов.Особые формы set! и begin. Моделирование простых объектов
Моделирование внешних объектов.
Нужна операция для изменения состояния объекта - это какая-то простая\составная информация.
Какое-то время выполняется процесс. Время жизни объекта никак не связано со временем процесса.
Моделирование объектов всегда требует операцию присваивания.
Особая форма set: (set! <�что> <�как>)
(begin .. ) набор операций, которые надо выполнить; возвращает результат их выполнения.
(define balance 100)
(define (withdraw amount)
(if (<= amount balance)
(begin
(set! balance (- balance amount))
balance
)
“No money, no honey”)
)
Надо спрятать баланс
(define (new-withdraw)
(let ((balance 100))
(lambda (amount)
(if <= amount balance)
(begin
(set! balance (- balance amount))
balance
)
“No money, no honey”)))
))
(define (make-withdraw balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Недостаточно денег на счете")))
При помощи make-withdraw можно следующим образом создать два объекта W1 и W2:
(define W1 (make-withdraw 100)) - счет1
(define W2 (make-withdraw 100)) - счет 2
(W1 50)
50
(W2 70)
30
Реализуем счет с тремя операциями: get/check - сколько денег
withdraw
add
(define (make balance)
(define (get) balance)
(define (withdraw amount) … )
(define (add amount) … )
(define (dispatch m)
(cond
((= m ‘get) get)
((= m ‘withdraw) withdraw)
((= m ‘add) add)
(else “error”)
)
)
ditpatch
)
Call:
(define a (make 100))
((a `add) 50)
((a `withdraw) 20)
(a `get)
39. Моделирование сложных объектов
Ха, а модель не поменялась. Каждый объект — абстракция (набор функций: конструктор, селектор, и вводится мутатор). Отличие от простых объектов в том, что в сложных объектах более одного поля, и соответственно больше селекторов и методов.
(make `get)
(make `withdraw)
(define p (cons a b))
(set! p ...)
(set! p (cons (car p) new_b))
Механизм изменяемые пары:
(define (cons x y)
(define (set_x value)...)
(define (set_y value) (set! y value))
(define (get_x ) x)
(define (dispatch m)
(cond
((= m ‘get_x) get_x)
((= m ‘set_x) set_x)
…
(else “error”)
)
)
dispatch
)
(define (car p) ((p ‘get_x)))
(define (set_car! p value)
((p ‘set_x) value)
)
40. Оператор присваивания. Достоинства и недостатки его использования
Императивные языки — те, где есть оператор присваивания.
простота и привычность
генератор случайных чисел (внутренняя переменная, которую пересчитываем)
(define rand
(define x (rand_init))
(lambda ()
(set! x (rand_update))
)
)
нужна формальная модель вычисления
для каждой переменной надо знать значение до и после set. Не подходит модель аппликативная и нормальная. Нужна другая.
(a (b value) (c value)) не понятно, какое будет value.
усложняется сравнение данных
(define a (make 100))
(define b (make 100))
(= a b) Сравнивать объекты или содержимое -?
важен порядок действий. Можно вычислять аргументы параллельно, поэтому нужна синхронизация потоков.
41. Модель вычисления с окружениями
[ тут понятнее http://newstar.rinet.ru/~goga/sicp/sicp.pdf стр 227 ]
Главный принцип - необходимо хранить значение переменной, а не вычислять каждый раз заново.
Окружение — набор кадров
Кадр — таблица связываний
[небесной красоты картинка]
Есть окружение более высокого уровня.
При запросе переменной она ищется сначала в последнем кадре, потом в родительском. Новый кадр создается в конце.
Процедура = пара:
Ссылка на окружение, где была создана эта процедура
Тело процедуры
(define x 10) ; создается новый кадр
(define (f x) 0)
(define (lambda (x) 0))
[еще картинка]
Когда (f 10) создается новое окружение, у которого в качестве родительского окружения указывается окружение, в котором создана функция, … .
Окружение живет, пока на него существуют ссылки (привет, garbage collector)
(define (h x) (lambda))
42. Моделирование потоков
Параллелизм:
(parallel-execute p1 p2 p3 …)
Сериализация доступа:
(make-serializer) - создание сериализатора, который может создать функцию f(x), гарантирующую, что в один момент времени будет выполняться только одна из них. Иными словами, на входе функция, на выходе lock-функция.
Пример:
(define s (make-serializer)) — создание сериализатора
(define s-put (s put)) — создание lock-функции s-put на основе функции put c помощью cериализатора s.
Семафоры:
(make-mutex) - аналогично.
(define m (make-mutex))
(m ‘acquire) - залочить
(m ‘release) - освободить
Реализация make-serializer:
(define (make-serializer)
(let (m (make-mutex)))
(lambda (p)
(define (serialized-p .args)
(begin (m ‘acquire)
let ((val p .args)))
(begin (m ‘release)
val))))
serialized-p)))
.args - для тех случаев, когда количество параметров четко не определенно.
Поток - упорядоченное множество данных небольшого объема (заявок). Заявки передаются из внешней среды в приложение, а приложение возвращает результат. (От меня) По сути, поток в лиспе - это список, у которого определен только текущий элемент. Остальные элементы пока неизвестны. Они находятся с помощью функции.
Операции работы с потоками (с префиксом stream-):
Проверка на пустоту: (stream-null? S)
Получение первого элемента: (stream-car S)
Получение продолжения: (stream-cdr S)
Создание потока: (cons-stream x y)
Пустой поток (не операция): the-empty-stream
Поток:
( элемент ; функция, возвращающая продолжение )
↓
( элемент ; функция, возвращающая продолжение )
↓
и т.д.
Функции:
Получение n-го элемента потока
(define (stream-ref s n)
(if (= n 0) (stream-car s)
(stream-ref (stream-cdr s) (- n 1))))
(define (stream-map s p)
(if (stream-null? s)
the-empty-stream
(cons-stream
(p (stream-car s)
(stream-map (stream-cdr s) p)
)
)
)
Работа с потоками (реализация):
Для начала, нужны две функции:
(define (delay x) (lambda () x)) - создает отложенное вычисление функции
(define (force x) (x)) - вычисляет функцию
(define (cons-stream x y))
(cons x (delay y)))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
Примеры потоков:
(define (integers n)
(cons-stream n
(integers (+ n 1))))
(define random
(cons-stream random_init
(stream-map rand-update random)))
Недостатки:
Не понятно, как представить задачу в виде потока.
Параллелизм: неизвестно, какому потоку отдать приоритет.
Мне печеньки за последний билет ♥ ты супер :*
|
