Функциональное программирование:
содержание лекций

• Императивное
  • "сначала сделать это, потом сделать то"
  • наиболее очевидная абстракция над архитектурой фон Неймана
  • пошаговое изменение состояния программы, как функция от времени
  • выполнение команд в порядке, определенном управляющими конструкциями
  • типичные команды: присваивание, ввод/вывод, вызов процедур
  • основная абстракция — процедура, выполнение множества действий как одной команды.
• Декларативное (что, а не как)
  • нет переменных и операторов присваивания
  • функциональное
    • "вычислить значение выражения и использовать его"
      • разные языки используют разный порядок вычислений
      • вычисление по мере необходимости
    • основано на математике и математическом понятии функция
    • неизменяемые значения, ссылочная прозрачность, понятие побочных эффектов
    • нет привязки ко времени
    • работа с функциями, как с любыми значениями
    • академическое использование.
    • индустриальное использование.
    • языки: семейство ML (OCaml, F#), Haskell, Erlang, семейство Lisp, гибридные (JavaScript, Python)
    • электронные таблицы
    • элементы ФП широко используются и в императивных языках, например, lambda-выражения в C++11 и Java.
  • логическое автоматический вывод на основе аксиом и правил
  • программирование потоков данных, реактивное программирование потоки данных и распространение изменений
• ООП
  • объекты, обменивающиеся сообщениями
  • в основном императивное

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

• Джон Маккарти, 1958
  • изначально, как математическая нотация для программ, основанная на λ-исчислении
• ИИ и символьные вычисления
  • Гомоиконичность, метапрограммирование
  • Динамический интерактивный язык REPL
  • Семейство языков

Значение Лиспа:

• Большое влияние на другие языки.

• Меняет представление о программировании

  «A language that doesn’t affect the way you think about programming, is not worth knowing.» (Alan Perlis)

Некоторые диалекты и реализации языков семейства Лисп.

• Common Lisp (1984)
• Emacs Lisp (1985)
• Scheme (1975)
  • GNU Guile (1993)
  • Racket (1995)
• Clojure (2007) и ClojureScript

SICP, раздел 1.2.

• Функция вычисления факториала. Линейно рекурсивный и линейно итеративный процессы, хвостовая рекурсия.

  (define (factorial n)
    (define (iter product counter)
      (if (> counter n)
          product
          (iter (* counter product)
                (+ counter 1))))
    (iter 1 1))
  

• Функция расчета чисел Фибоначчи и древовидная рекурсия.

  (define (fib1 n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib1 (- n 1))
                   (fib1 (- n 2))))))
  
  (define (fib2 n)
    (define (iter a b i)
      (if (>= i n)
          b
          (iter (+ a b) a (+ i 1))))
    (iter 1 0 0))
  

Пример из SICP, раздел 1.3.1.

lambda-выражения. Свободные переменные и замыкание.

Процедуры, возвращающие процедуры.

(define (negate f)
  (λ (a) (not (f a))))

(define (negate* f)
  (λ a (not (apply f a))))

(define (negate* f)
  (compose not f))

Каррирование и композиция.

λ-исчисление, переменные, абстракция, аппликация

• свободные и связанные переменные
• α-эквивалентность λx.M[x] → λy.M[y]
• β-редукция (λx.M) E → M[x:=E]
• η-преобразование λx.f x → f (x не входит свободно в f)
• каррирование f(x,y) = x+y λx.λy.x+y Сокращенная запись: λxy.x+y

Комбинатор неподвижной точки

(define (fact* f)
  (λ (n)
    (if (zero? n)
        1
        (* n (f (- n 1))))))

(fact* f) возвращает функцию, которая работает как рекурсивная функция вычисления факториала, но вместо вызова себя вызывает f.

Если мы найдем неподвижную точку fact* — такую f, что (fact* f) будет равна самой f, то f и будет функцией вычисления факториала.

;; Комбинатор неподвижной точки.
(define (Y x)
  ((λ (f) (f f))
   (λ (f) (x (λ (a) ((f f) a))))))

;; Или так для функции произвольного числа аргументов.
;; (define (Y x)
;;   ((λ (f) (f f))
;;    (λ (f) (x (λ a (apply (f f) a))))))

;; Y превращает fact* в рекурсивную функцию вычисления факториала.
((Y fact*) 5)

Объяснение принципа работы

• Пары cons
• Пример: рациональные числа
• Барьеры абстракции

• Данные и процедуры

  (define (cons a b)
    (λ (m)
      (cond ((= m 0) a)
            ((= m 1) b)
            (else (error "Аргумент не 0 или 1:" m)))))
  
  (define (car c) (c 0))
  (define (cdr c) (c 1))
  

• Пары и списки, представление списков car, cdr, caar, cddr, cadr, cdar
• range

  • рекурсивная реализация, почему в итеративной список получается в обратном порядке.

    ;; Не работает для отрицательных step и нерациональных аргументов.
    (define (my-range a b (step 1))
      (define (iter b c)
        (if (> a b)
            c
            (iter (- b step) (cons b c))))
      (iter (- (- b 1) (modulo (- b a 1) step)) '()))
    

• length
• reverse
• map, filter
• свертки: foldl, foldr, реализация map и filter через свертки
• вложенные отображения (перечислить все пары чисел в диапазоне)

• Пример: найти все пары 1 ≤ j < i ≤ n, т. ч. i + j — простое.

  (filter (λ (p) (prime? (+ (car p) (cadr p))))
          (append-map (λ (i)
                        (map (λ (j)
                               (list i j))
                             (range 1 i)))
                      (range 1 10)))
  
  (for*/list ((i (range 1 10))
              (j (range 1 i))
              #:when (prime? (+ i j)))
    (list i j))
  

• Пример: гипотеза Гольдбаха (задача из курса «Основы информатики и программирования»)

  (map (λ (x)
         (filter
          (λ (a) (and (prime? a) (prime? (- x a))))
          (range 2 (add1 (quotient x 2)))))
       (range 4 50 2))
  

• Разделение памяти списками.
• Символы и строки
  • эквивалентность и идентичность (основное, подробно будет в теме про изменяемость)
  • string->list
• Ассоциативные списки
• Символьные данные (SICP 2.3)
  • quote, quasiquote
  • представление выражений и eval
  • namespace
  • порождение HTML
  • структурное представление против конкатенации строк
  • пример: символьное дифференцирование (SICP 2.3.2)

• присваивание
• set!, begin

• пример итеративной процедуры, проблема порядка присваиваний

  ;; С присваиванием (императивная реализация)
  (define (fib n)
    (let ((a 0)
          (b 1))
      (for ((i (in-range 1 (add1 n))))
        (let ((t a))
          (set! a b)
          (set! b (+ a t))))
      a))
  
  ;; Рекурсия (итеративная форма процесса)
  (define (fib n)
    (let loop ((a 0)
               (b 1)
               (i 0))
      (if (< i n)
          (loop b (+ a b) (add1 i))
          a)))
  

• пример с банковским счетом

  (define balance 100)
  
  (define (withdraw amount)
    (if (>= balance amount)
        (begin
          (set! balance (- balance amount))
          balance)
        (error "Недостаточно средств")))
  
  ;; Или так
  (define (withdraw amount)
      (when (< balance amount)
          (error "Недостаточно средств"))
      (set! balance (- balance amount))
      balance)
  

  • проблема моделирования времени
  • объект с внутренней переменной состояния (make-withdraw и make-account с диспетчеризацией сообщений)
  • идентичность объектов и ссылочная прозрачность
  • эквивалентность и идентичность =, equal?, eqv?, eq?
  • параллельность и потокобезопасность
• Изменяемые структуры данных
  • изменяемые пары (на примере Guile или mcons в Racket)
  • разделение памяти списками и последствия изменяемости
  • циклические структуры
  • сборка мусора
• Мемоизация (пример fib)

  • вопрос использования памяти, weak-hash

    (define (memoize f)
      (define m (make-hash))
      (λ a
        (if (hash-has-key? m a)
            (hash-ref m a)
            (let ((v (apply f a)))
              (hash-set! m a v)
              v))))
    
    ;; С weak-hash и hash-ref!
    (define (memoize f)
      (define m (make-weak-hash))
      (λ a (hash-ref! m a (λ () (apply f a)))))
    

Отложенные вычисления: delay и force.

Потоки: общий принцип.

Построение потоков (SRFI 41)

• stream-cons, stream-car, stream-cdr
• "четные" и "нечетные" потоки (SRFI 41 vs SICP)
• Приверы: stream-range, stream-from

Обработка потоков

• stream-map, stream-filter
• stream-fold, stream-scan
• sieve

(define (divisible? a b)
  (zero? (remainder a b)))

(define (sieve stream)
  (stream-cons
   (stream-car stream)
   (sieve (stream-filter
           (λ (x) (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (stream-from 2)))

SICP, рис. 3.31. Решето для поиска простых чисел в виде системы обработки сигналов.

  +---------------------------------------------------------------+
  | sieve                                                         |
  |                                                               |
  |        __/|                                        |\__       |
  |     __/car|........................................|   \__    |
  |   _/      |           :                            |      \_  |
----><_       |           V                            |  cons _>---->
  |    \__    |    +------------+    +------------+    |    __/   |
  |       \cdr|--->| filter:    |    | sieve      |--->| __/      |
  |          \|    |            |--->|            |    |/         |
  |                | not        |    |            |               |
  |                | divisible? |    |            |               |
  |                +------------+    +------------+               |
  +---------------------------------------------------------------+

Корекурсия: ones, nats, fibs, primes.

Другой способ поиска простых чисел (быстрее, проверям делимость только до √n):

(define primes (stream-cons 2 (stream-filter prime? (stream-from 3))))

(define (prime? n)
  (define (iter ps)
    (cond ((> (sqr (stream-car ps)) n) #t)
          ((divisible? n (stream-car ps)) #f)
          (else (iter (stream-cdr ps)))))
  (iter primes))

Поток пар (pairs и interleave).

(define-stream (interleave a b)
  (if (stream-null? a)
      b
      (stream-cons (stream-car a)
                   (interleave b (stream-cdr a)))))

(define (pairs a b)
  (stream-cons
   (list (stream-car a) (stream-car b))
   (interleave
    (stream-map (λ (x) (list (stream-car a) x))
                (stream-cdr b))
    (pairs (stream-cdr a) (stream-cdr b)))))

;; Проще, но здесь важно использовать define-stream.
(define-stream (pairs a b)
  (interleave
   (stream-map (λ (x) (list (stream-car a) x)) b)
   (pairs (stream-cdr a) (stream-cdr b))))

Пример ftw (GNU Guile).

Пример sqr-stream (SICP 3.5.3).

Взгляд на время в функциональном программировании (SICP, раздел 3.5.5, A functional-programming view of time).

• Моделирование времени (пример со счетом)
• Функциональное реактивное программирование
• "World programs" (2htdp/universe). Пример игры (управление ракетой).

• Рекурсивная процедура для вычисления факториала с использованием сопоставления по шаблону (match).

  (define (fact n)
    (match n
      (0 1)
      ((? natural?) (* n (fact (sub1 n))))))
  
  ;; Или так
  (define/match (fact n)
    ((0) 1)
    (((? natural?)) (* n (fact (sub1 n)))))
  

• Конкатенация списков

;; Рекурсивное определение
(define (my-append . ls)
  (match ls
    ;; 0 списков
    ('() '())
    ;; 2 списка, 1-й пустой
    ((list '() b) b)
    ;; 2 списка
    ((list (cons f r) b) (cons f (my-append r b)))
    ;; 1 или более 2 списков
    ((cons f r) (my-append f (apply my-append r)))))

;; Более строгий контроль типов аргументов
(define (my-append . ls)
    (match ls
      ('() '())
      ((list '() (list b ...)) b)
      ((list (list f r ...) b) (cons f (my-append r b)))
      ((list (list f ...) r ...) (my-append f (apply my-append r)))))

;; С использованием функций свертки
(define (my-append . lists)
    (match lists
      ((list a b) (foldr cons b a))
      (l (foldr my-append '() l))))

;; Более строгий контроль типов аргументов
(define (my-append . lists)
  (match lists
    ((list (? list? a) (? list? b)) (foldr cons b a))
    ((list (? list?) ...) (foldr my-append '() lists))))

• Преобразование арифметического выражения из инфиксной формы в префиксную

(define (infix->prefix form)
  (match form
    [(list h ... a '* b t ...)
     (infix->prefix `(,@h (* ,(infix->prefix a) ,(infix->prefix b)) ,@t))]
    [(list h ... a '+ b t ...)
     (infix->prefix `(,@h (+ ,(infix->prefix a) ,(infix->prefix b)) ,@t))]
    [(list (list a ...)) a]
    [_ form]))

expand, expand-once. Примеры разворачивания существующих конструкций: let, let*, define, thunk, or, cond.

define-syntax, syntax, преобразователь, syntax-rules.

Реализация синтаксиса when.

(define-syntax my-when
  (syntax-rules ()
    ((when condition exp ...)
     (if condition
         (begin exp ...)
         (void)))))

Реализация thunk.

(define-syntax my-thunk
  (syntax-rules ()
    ((my-thunk exp ...)
     (λ () exp ...))))

(define-syntax-rule (my-thunk exp ...)
  (λ () exp ...))

Вариант let с одной парой имя-значение.

(define-syntax let1
  (syntax-rules ()
    ((_ (var val) exp exp* ...)
     (let ((var val)) exp exp* ...))))

Буквальное сопоставление идентификаторов. Пример: обработка одного правила cond.

(define-syntax cond1
  (syntax-rules (=> else)
    ((_ test => fun)
     (let ((exp test))
       (if exp (fun exp) #f)))
    ((_ test exp exp* ...)
     (if test (begin exp exp* ...) #f))
    ((_ else exp exp* ...)
     (begin exp exp* ...))))

Гигиена макросов. Реализация or.

(define-syntax my-or
  (syntax-rules ()
    ((_) #f)
    ((_ exp) exp)
    ((_ exp rest ...)
     (let ((t exp))
       (if t t (my-or rest ...))))))

;; t здесь и t в определении синтаксиса my-or разные!
(let ((t #t)) (my-or #f t))

syntax-case, syntax

;; Увеличивает значение переменной на 1 (новое значение
;; присваивается).
(define-syntax add1!
  (lambda (x)
    (syntax-case x ()
      ((_ var) (identifier? #'var)
       #'(set! var (add1 var))))))

Анафорический if: в варажениях-ветках можно использовать it, чтобы сослаться на результат условного выражения.

;; не работает
(define-syntax aif
  (λ (x)
    (syntax-case x ()
      ((_ test then else)
       #'(let ((it test))
           (if it then else))))))

;; работает
(define-syntax aif
  (λ (stx)
    (syntax-case stx ()
      ((_ test then else)
       (with-syntax ((it (datum->syntax stx 'it)))
         #'(let ((it test))
             (if it then else)))))))

quasisyntax, unsyntax

Время вычисления синтаксических правил.

Пример: фиксация времени компиляции.

(define-syntax display-compile-timestamp
  (lambda (x)
    (syntax-case x ()
      ((_)
       #`(begin
           (display "The compile timestamp was: ")
           (display #,(current-milliseconds))
           (newline))))))

• Программирование в стиле передачи продолжений (CPS).

  Пример: представление процедуры вычисления гипотенузы в CPS.

  ;; Исходная процедура.
  (define (hypot x y)
    (sqrt (+ (* x x) (* y y))))
  
  ;; В стиле передачи продолжений.
  (define (hypot& x y k)
    (*& x x (λ (x2)
              (*& y y (λ (y2)
                        (+& x2 y2 (λ (p2)
                                    (sqrt& p2 k))))))))
  

  Пример: CPS-представление рекукрсивной процедуры вычисления факториала.

  (define (fact& n k)
    (=& n 0 (λ (b)
              (if b
                  (k 1)
                  (-& n 1 (λ (nm1)
                            (fact& nm1 (λ (f)
                                         (*& n f k)))))))))
  

• Вызов с текущим продолжением (call-with-current-continuation aka call/cc).

  (define kont #f)
  
  (+ 1 (call/cc (λ (k)
                  ;; Запоминаем текущее продолжение в kont.
                  (set! kont k)
                  2)))
  
  ;; Возвращаемся к сохраненному выше продолжению.
  (kont 3)
  

• Применения

  • return

    (define (f return)
      (return 1)
      (displayln "xxx")
      2)
    
    (+ 1 (f (const #f)))
    
    (+ 1 (call/cc f))
    

    (define-syntax define/return
      (λ (x)
        (syntax-case x ()
          ((_ (id args ...) expr ...)
           (with-syntax ((return (datum->syntax x 'return)))
             #'(define (id args ...)
                 (define (f return)
                   expr ...)
                 (call/cc f)))))))
    
    (define/return (f)
        (foldl (λ (a b)
                 (if (> b 3)
                     (return b)
                     (+ a b)))
               0
               '(1 2 3 4 5)))
    

  • генераторы

    (define (generator* f)
        (define (next . args)
          (call/cc (λ (nk)
                     (define (yield v)
                       (call/cc (λ (yk)
                                  (set! next yk)
                                  (nk v))))
                     (apply f yield args))))
        (λ args (apply next args)))
    
    (define g (generator* (λ (yield l)
                            (for ((x l))
                              (yield x)))))
    
    (define g (generator* (λ (yield l)
                              (foldl (λ (x s)
                                       (yield s)
                                       (+ x s))
                                     0
                                     l))))
    
    (define-syntax generator
        (λ (x)
          (syntax-case x ()
              ((_ (args ...) expr ...)
               (with-syntax ((yield (datum->syntax x 'yield)))
                 #'(generator* (λ (yield args ...) expr ...)))))))
    

  • исключения
  • обратная инверсия управления (для веб-приложния)