[ИУ9] Основы информатики

Домашнее задание №4

1. Мемоизация

Реализуйте рекурсивные вычисления с использованием оптимизационных техник — мемоизации результатов вычислений и отложенных вычислений.

Важно! Eсли в программе используются гигиенические макросы и эта программа будет выполнена в среде guile 1.8.x (в том числе на сервере тестирования), то следует подключить модуль поддержки таких макросов, написав в начале программы следующую строку:

(use-syntax (ice-9 syncase))

Реализуйте процедуру memoized-factorial для вычисления факториала по рекурсивной формуле с мемоизацией результатов вычислений. Для мемоизации используйте ассоциативный список (словарь), который храните в статической переменной. Использовать для этой цели глобальную переменную запрещается.

Примеры вызова процедур сервером тестирования:

(begin
  (display (memoized-factorial 10)) (newline)
  (display (memoized-factorial 50)) (newline))

3628800
30414093201713378043612608166064768844377641568960512000000000000

2. Отложенные вычисления

Используя средства языка Scheme для отложенных вычислений, реализуйте средства для работы с бесконечными «ленивыми» точечными парами и списками:

На их основе определите:

Продемонстрируйте работу процедур на примере бесконечного списка натуральных чисел. Для этого определите процедуру-генератор (naturals start), возвращающую бесконечный «ленивый» список натуральных чисел, начиная с числа start.

Примеры вызова процедур сервером тестирования:

(display (lazy-head (naturals 10) 12)) 
(10 11 12 13 14 15 16 17 18 19 20 21)

Реализуйте процедуру (lazy-factorial n), которая возвращает значение n!, получая его из n-го элемента бесконечного списка факториалов.

Примеры вызова процедур сервером тестирования:

(begin
  (display (lazy-factorial 10)) (newline)
  (display (lazy-factorial 50)) (newline))

3628800
30414093201713378043612608166064768844377641568960512000000000000

3. Чтение из потока

Напишите процедуру (read-words), осуществляющую чтение слов, разделенных пробельными символами, из стандартного потока (порта) ввода (сервер тестирования направляет в  этот поток текстовый файл с примером). Слова в потоке разделены одним или более пробельными символами. Также пробельные символы могут присутствовать перед первым словом и после последнего слова, такие пробельные символы должны игнорироваться. Признак конца файла означает окончание ввода. Процедура должна возвращать список строк (один элемент списка — одно слово в строке). Для пустого файла или файла, содержащего только пробелы, процедура должна возвращать пустой список.

Анализ потока символов осуществляйте непосредственно при чтении файла, для чего используйте встроенные процедуры read-char, peek-char, eof-object? и  встроенные предикаты классификации символов.

Пример входных данных (⋅ — пробел, ¶ — конец строки):

⋅⋅one⋅two⋅three⋅⋅⋅¶
four⋅five⋅⋅six⋅⋅¶

Результат вызова процедуры для этих входных данных:

(read-words)
  ⇒ ("one" "two" "three" "four" "five" "six")

4. Структуры (записи)

Используя средства языка Scheme для метапрограммирования, реализуйте каркас поддержки типа данных «структура» («запись»). Пусть объявление нового типа «структура» осуществляется с помощью вызова (define-struct тип-структуры (имя-поля-1 имя-поля-2 … имя-поля-n). Тогда после объявления структуры программисту становятся доступны:

Пример использования каркаса:

(define-struct pos (row col)) ; Объявление типа pos
(define p (make-pos 1 2))     ; Создание значения типа pos

(pos? p)    ⇒ #t

(pos-row p) ⇒ 1
(pos-col p) ⇒ 2

(set-pos-row! p 3) ; Изменение значения в поле row
(set-pos-col! p 4) ; Изменение значения в поле col

(pos-row p) ⇒ 3
(pos-col p) ⇒ 4

Рекомендация. Для более короткой записи решения можно (но не обязательно) использовать квазицитирование (quasiquotation).

Важно! Если в программе используются гигиенические макросы и эта программа будет выполнена в среде guile 1.8.x (в том числе на сервере тестирования), то следует подключить модуль поддержки таких макросов, написав в начале программы следующую строку:

(use-syntax (ice-9 syncase))

5. Алгебраические типы данных

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

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

Пример. Необходимо вычислять периметры геометрических фигур (квадратов, прямоугольников, треугольников) и длины окружностей. Для этого в программе определен тип фигура, который может принимать значения квадрат, прямоугольник, треугольник, окружность. Значения создаются с помощью конструкторов (для каждой фигуры — свой конструктор) — процедур, принимающих в качестве аргументов длины сторон (1, 2 или 3 аргумента соответственно) или радиус (для окружности) и возвращающих значение типа фигура:

; Определяем тип
;
(define-data figure ((square a)
                     (rectangle a b)
                     (triangle a b c)
                     (circle r)))

; Определяем значения типа
;
(define s (square 10))
(define r (rectangle 10 20))
(define t (triangle 10 20 30))
(define c (circle 10))

; Пусть определение алгебраического типа вводит
; не только конструкторы, но и предикат этого типа:
;
(and (figure? s)
     (figure? r)
     (figure? t)
     (figure? c)) ⇒ #t

Функция расчета периметра или длины окружности — единая для всех фигур, принимает значение типа фигура и возвращает значение, вычисленное по формуле, выбранной в соответствии с вариантом фигуры:

(define pi (acos -1)) ; Для окружности
  
(define (perim f)
  (match f 
    ((square a)       (* 4 a))
    ((rectangle a b)  (* 2 (+ a b)))
    ((triangle a b c) (+ a b c))
    ((circle r)       (* 2 pi r))))
  
(perim s) ⇒ 40
(perim r) ⇒ 60
(perim t) ⇒ 60

Здесь match — сопоставление с образцом. В данном примере при вычислении (perim s) значение s будет сопоставлено с образцом (square a). При этом будет осуществлена подстановка фактического значения a, содержащегося в s, на место а в выражении (* 4 a) справа от образца. Вычисленое значение будет возвращено из конструкции match.

Рекомендации. Для более короткой записи решения можно (но не обязательно) использовать квазицитирование (quasiquotation). По литературе и ресурсам Интернет ознакомьтесь с тем, как работает сопоставление с образцом в других языках программирования.

«Ачивки»