---

Лабораторная работа № 2. Типы данных. Модульное тестирование
Дубанов А.В., Коновалов А.В.

4 сентября 2019

Цели работы
На практике ознакомиться с системой типов языка Scheme.
На практике ознакомиться с юнит-тестированием.
Разработать свои средства отладки программ на языке Scheme.
На практике ознакомиться со средствами метапрограммирования языка Scheme.
Задания
Реализуйте макрос trace для трассировки. Трассировка — способ отладки, при котором отслеживаются значения переменных или выражений на каждом шаге выполнения программы. Необходимость и вывести значение в консоль, и вернуть его в программу нередко требует существенной модификации кода, что может стать источником дополнительных ошибок. Реализуйте макрос, который позволяет ценой небольшой вставки, не нарушающей декларативность кода, выполнить и вывод значения в консоль с комментарием в виде текста выражения, которое было вычислено, и возврат его значения в программу.

Код без трассировки:

(define (zip . xss)
  (if (or (null? xss)
          (null? (car xss))) ; Надо отслеживать значение (car xss) здесь...
      '()
      (cons (map car xss)
            (apply zip (map cdr xss))))) ; ...и значение xss здесь.
Код с трассировкой:

(load "trace.scm")

(define (zip . xss)
  (if (or (null? xss)
          (null? (trace (car xss)))) ; Здесь...
      '()
      (cons (map car xss)
            (apply zip (map cdr (trace xss)))))) ; ... и здесь

(define counter
  (let ((n 0))
    (lambda ()
      (set! n (+ n 1))
      n)))
Консоль:

> (zip '(1 2 3) '(one two three))
(car xss) => (1 2 3)
xss => ((1 2 3) (one two three))
(car xss) => (2 3)
xss => ((2 3) (two three))
(car xss) => (3)
xss => ((3) (three))
(car xss) => ()
((1 one) (2 two) (3 three))

> (+ (trace (counter))
     (trace (counter)))
(counter) => 1
(counter) => 2
3
Вычисление значения выражения осуществляется после вывода цитаты этого выражения в консоль. Таким образом, в случае аварийного завершения программы из-за невозможности вычисления значения, вы всегда сможете определить, в каком выражении возникает ошибка.

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

В дальнейшем используйте этот макрос при отладке своих программ на языке Scheme.

Указание. Для вывода на экран используются следующие процедуры:

(write e) — вывод выражения e в однозначной, «машиночитаемой» форме: строки при выводе будут заключены в кавычки и управляющие символы в них будут записаны escape-последовательностями, литеры предварены #\, её следует использовать для вывода цитаты выражения,
(display e) — вывод выражения e в «человекочитаемой» форме — строки и символы выводятся буквально, её следует использовать для вывода =>,
(newline) — печатает перевод на следующую строку (аналогично (display "\n") или (display #\newline)).
Модульное тестирование (юнит-тестирование) — способ проверки корректности отдельных относительно независимых частей программы. При таком подходе для каждой функции (процедуры) пишется набор тестов — пар «выражение — значение, которое должно получиться». Процесс тестирования заключается в вычислении выражений тестов и автоматизированном сопоставлении результата вычислений с ожидаемым результатом. При несовпадении выдается сообщение об ошибках.

Реализуйте свой каркас для модульного тестирования. Пусть каркас включает следующие компоненты:

Макрос test — конструктор теста вида (выражение ожидаемый-результат).

Процедуру run-test, выполняющую отдельный тест. Если вычисленный результат совпадает с ожидаемым, то в консоль выводятся выражение и признак того, что тест пройден. В противном случае выводится выражение, признак того, что тест не пройден, а также ожидаемый и фактический результаты. Функция возвращает #t, если тест пройден и #f в противном случае. Вывод цитаты выражения в консоль должен выполняться до вычисления его значения, чтобы при аварийном завершении программы последним в консоль было бы выведено выражение, в котором произошла ошибка.

Процедуру run-tests, выполняющую серию тестов, переданную ей в виде списка. Эта процедура должна выполнять все тесты в списке и возвращает #t, если все они были успешными, в противном случае процедура возвращает #f.

Какой предикат вы будете использовать для сравнения ожидаемого результата с фактическим? Почему?

Пример:

;; Пример процедуры с ошибкой
;;
(define (signum x)
  (cond
    ((< x 0) -1)
    ((= x 0)  1) ; Ошибка здесь!
    (else     1)))

;; Пример процедуры с побочным эффектом
;;
(define counter
  (let ((n 0))
    (lambda ()
      (set! n (+ n 1))
      n)))

;; Загружаем каркас
;;
(load "unit-test.scm")

; Определяем список тестов
;;
(define the-tests
  (list (test (signum -2) -1)
        (test (signum  0)  0)
        (test (signum  2)  1)
        (test (counter) 1)
        (test (counter) 77) ; ошибка в тесте, должно быть 2
        (test (counter) 3)
        ;; тесты, демонстрирующие разницу
        ;; между write и display
        (test (* 7 7) "49")
        (test (string-append "4" "9") 49)))

;; Выполняем тесты
;;
(run-tests the-tests)
Пример результата в консоли:

(signum -2) ok
(signum 0) FAIL
  Expected: 0
  Returned: 1
(signum 2) ok
(counter) ok
(counter) FAIL
  Expected: 77
  Returned: 2
(counter) ok
(* 7 7) FAIL
  Expected: "49"
  Returned: 49
(string-append "4" "9") FAIL
  Expected: 49
  Returned: "49"
#f
Если перепутать write и display, последний пример будет показывать странный результат.

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

Обратите внимание, что тесты при создании не должны выполняться. Т.е. следующая строка не должна приводить к ошибке:

(define bad-test (test (/ 10 0) 100))
Однако, попытка запуска при помощи run-test должна приводить к ошибке деления на ноль:

> (run-test bad-test)
(/ 10 0)
‹СООБЩЕНИЕ ОБ ОШИБКЕ›
Выполните задание 1 из индивидуального варианта.

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

Выполните задание 2 из индивидуального варианта.

Индивидуальный вариант

Реализуйте процедуру (reverse! seq) деструктивного обращения последовательности (правильного списка, вектора или строки).

(define xs '(a b c d e))
(define ys (vector 1 2 3 4 5))
;; Синтаксис #(…) может создавать неизменяемый вектор
(define zs (string #\h #\e #\l #\l #\o))

(reverse! xs)
(reverse! ys)
(reverse! zs)

xs ⇒ (e d c b a)
ys ⇒ #(5 4 3 2 1)
zs ⇒ "olleh"
Добавьте в процедуру reverse! необязательный параметр-приёмник — если он задан, то исходная последовательность не меняется, результат её обращения записывается в приёмник:

(define xs (list 'a 'b 'c 'd 'e))
(define ys (vector 1 2 3 4 5))

(reverse! xs ys)

xs ⇒ (a b c d e)
ys ⇒ #(e d c b a)

(define zs (string #\h #\e #\l #\l #\o))

(reverse! zs xs)

zs ⇒ "hello"
xs ⇒ (#\o #\l #\l #\e #\h)

(define as '(a b c))
(define bs (append '(x y z) as))
bs ⇒ (x y z a b c)

;; Последние три элемента bs - список as
(set-car! as 1)
bs ⇒ (x y z 1 b c)

(reverse! bs)
bs ⇒ (c b 1 z y x)
as ⇒ (z y x)
;; Изменяться должно каждое звено списка!

(reverse! (cdr bs))
bs ⇒ (c x y z 1 b)
Можно считать, что размер источника и приёмника всегда должны совпадать.

Таким образом, применение процедуры с одним аргументом (reverse! seq) должно быть эквивалентно (reverse! seq seq).

Попробуйте предусмотреть все возможные варианты.

Совет. При написании юнит-тестов используйте let.

Примечание. Результатом выполнения задания должно быть одно определение процедуры reverse!. Алгоритм её работы должен определяться числом аргументов и их типами.

Подсказка. Процедура, заполняющая другой список:

(define xs '(a b c))
(define ys (append '(x y z) xs))

(define (fill src dest)
  (if (not (or (null? src) (null? dest)))
      (begin (set-car! dest (car src))
      (fill (cdr src) (cdr dest)))))
Запуск:

> (fill '(1 2 3 4 5) ys)
> ys
(1 2 3 4 5 c)
> xs
(4 5 c)
Разработайте наборы юнит-тестов и используйте эти тесты для разработки процедуры, выполняющей разложение на множители.

Реализуйте процедуру factorize, выполняющую разложение многочленов вида a2 − b2, a3 − b3 и a3 + b3 по формулам.

Пусть процедура принимает единственный аргумент — выражение на языке Scheme, которое следует разложить на множители, и возвращает преобразованное выражение. Возведение в степень в исходных выражениях пусть будет реализовано с помощью встроенной процедуры expt. Получаемое выражение должно быть пригодно для выполнения в среде интерпретатора с помощью встроенной процедуры eval. Упрощение выражений не требуется.

Примеры применения процедуры:

(factorize '(- (expt x 2) (expt y 2)))
  ⇒ (* (- x y) (+ x y))

(factorize '(- (expt (+ first 1) 2) (expt (- second 1) 2)))
  ⇒ (* (- (+ first 1) (- second 1))
         (+ (+ first 1) (- second 1)))

(eval (list (list 'lambda
                      '(x y)
                      (factorize '(- (expt x 2) (expt y 2))))
                1 2)
          (interaction-environment))
  ⇒ -3
Вопросы для защиты лабораторной работы
Суметь объяснить логику работы написанных определений и обосновать выбор используемых языковых конструкций.
Отчёт по лабораторной работе № 2
Отчёт должен содержать примеры, предложенные преподавателем и задания из индивидуального варианта, и то, и другое — с тестированием.

Отчёт выполняется в разметке Markdown по следующему шаблону:

% Лабораторная работа № 2. Типы данных. Модульное тестирование
% <лабораторная ещё не сдана>
% Кирилл Меньшиков, ИУ9-12/6

# Цель работы
…переписываете цель работы из задания…

# Индивидуальный вариант
…названия процедур, которые требуется реализовать…

# Реализация

```scheme
(define (hello name)
  (display "Привет, ")
  (display name)
  (display "!\n"))
```

# Тестирование

```
Welcome to DrRacket, version 6.10.1 [3m].
Language: R5RS; memory limit: 128 MB.
> (hello "Вася")
Привет, Вася!
> (hello "Пупкин")
Привет, Пупкин!
```

# Вывод
…пишете, чему научились…
В отчёте приведён лишь необходимый минимум. Можно писать больше и интереснее — интересные и вдумчивые отчёты поощряются дополнительным баллом.

Ваш отчёт будет конвертирован в PDF при помощи pandoc следующей командой:

pandoc \
  --pdf-engine=xelatex \
  -V 'mainfont:Liberation Serif' \
  -V 'monofont:Liberation Mono' \
  "$SOURCE" -o "$PDF"