How to Design Programs

«Как проектировать программы», How to Design Programs, — учебник по программированию, написанный авторами платформы Racket.

Две основные редакции: от 2003 года и активно дорабатываемая, от 2015 года.

Далее следует конспект второй редакции.

Основы

Числа

Пример простейшей программы на Scheme — выражение, применяющее арифметическую операцию сложения:

(+ 1 1)

Некоторые операции над числами: +, -, *, /, abs, add1, ceiling, denominator, exact->inexact, expt, floor, gcd, log, max, numerator, quotient, random, remainder, sqr, tan.

Вводится различие между точными числами и приближениями, типичный пример — (sqrt 2), что равняется приближению:

#i1.4142135623730951

Определение и вызов функции

Оператор определения в Scheme — define. Им задаются переменные:

(define x 3)
(define y 4)

и функции:

(define (f2c f) (* 5/9 (- f 32)))

Вызов функций — так же, как для примитивных операторов:

> (f2c 32)
0
> (f2c 212)
100
> (f2c -40)
-40

Строки

По традиции, строки отделяются двойными кавычками:

(string-append "hello " "world")

или просто:

"Hello World"

Выражение, использующее оба рассмотренных типа:

(+ (string-length "hello world") 60)
=
(+ 11 60)
=
71

Растры

Далее вводятся несколько функций, возвращающих графические объекты и демонстрируется способность среды Racket включать растры прямо в окне кода, растр оказывается примитивным типом, возвращающим себя:

(define cat )

Логика

Значения истинности: true, false. Операторы: and, or, not, и т. д.

Числовые сравнения: > < = <= >=

Проверки на тип: number?, string? и т. д.

Условный оператор:

(define (sign x)
 (cond
   [(> x 0) 1]
   [(= x 0)  0]
   [(< x 0) -1]))

Структуры

Задание структуры — пары, назначение переменной, как пары, и доступ к полям структуры:

(define-struct posn (x y))
(define a (make-posn 10 34))
(posn-x a)
(posn-y a)

Списки

Списки составляются через классические лисповы cons и list, car и cdr (последние также имеют синонимы first и rest.)

Кавычка

Кавычка — оператор отмены вычисления, который распространяется на любые списки:

> '(("a" 1)
    ("b" 2)
    ("d" 4))
(list (list "a" 1) (list "b" 2) (list "d" 4))

Обратная кавычка — такой же оператор, но тут можно «вернуть» процедуру извлечения значения символа с помощью приставки ,:

> `(1 ,(+ 1 1) 3)
(list 1 2 3)

Запятая со стыковкой:

>`(0 ,@'(1 2 3) 4)
'(0 1 2 3 4)

Приставка ,@ включает непосредственно элементы данного списка, а не сам список.

Обратная кавычка и запятая могут порождать шаблонные конструкции, т. к. запятая может возвращать (без исполнения) произвольные выражения. На основе таких шаблонов пишутся макросы.

Функции как значения

Рекурсивное определение функции-преобразователя списка:

(define (map1 k g)
  (cond
    [(empty? k) empty]
    [else
     (cons (g (first k))
           (map1 (rest k) g))]))

Здесь параметр g — функция, поочерёдно вызываемая для элементов передаваемого списка k.

Впрочем, map среди стандартных функций, принимающих функцию-параметр:

> (build-list 3 add1)
(list 1 2 3)
> (filter odd? (list 1 2 3 4 5))
(list 1 3 5)
> (sort (list 3 2 1 4 5) >)
(list 5 4 3 2 1)
> (map add1 (list 1 2 2 3 3 3))
(list 2 3 3 4 4 4)

Простые примеры того, как функция служит значением символа:

(define (f x) (x 10)); вызов функции x с аргументом 10.
(define (f x) (x f)); применение x к самой вводимой функции f.
(define (f x y) (x 'a y 'b)); вызов x c параметрами: символ a, y, символ b.

Локальные определения

В среде Racket синтаксис local — аналог стандартных let, let*, letrec… Только тут определения пишутся так же, как и в глобальной области:

(local ( ... последовательность определений ...) выражение)

Классический оператор lambda задаёт анонимную функцию. Возвращаемое значение (функцию) можно, например, назначить значением символа:

(define f ; the lambda version 
 (lambda (x) (+ (sin x) x (* 3 x))))

Это полный эквивалент простой записи для определения функций.