Функционално програмиране (И) 2016/2017

План:

• Преговор - cond, if
• Локални дефиниции
• Модели на оценяване -  applicative vs. normal order evaluation; силна и слаба нормализация
• Специални форми
• Линейна, дървовидна и опашкова рекурсия

Интерактивна сесия: REPL.it

Задача 1: Да се напише функция, която взима 3 числа и връща сумата от квадратите на двете по-големи.

; Define a procedure that takes three numbers
; as arguments and returns the sum of the
; squares of the two larger numbers.

(define (f a b c)
  (define (sum-of-squares a b)
    (+ (* a a) (* b b)))

  (cond ((and (> a c) (> b c)) (sum-of-squares a b))
        ((> a b) (sum-of-squares a c))
        (else (sum-of-squares b c))))

Задача 2: Какво изчислява следната функция?

; What does the following function compute?
(define (mystery a b)
  ((if (> b 0) + -) a b))

Задача 3: Как да определим модела на оценяване в нашия интерпретатор?

; How to determine whether the interpreter is using 
; applicative-order evaluation or normal-order evaluation:
(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))

(test 0 (p))

Задача 4: Как да (не) си имплементираме if сами:

; My new 'if' implementation.
; Is there something wrong with it?
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (reciprocal n)
  (new-if (= n 0)
          (raise "zero division!")
          (/ 1 n)))

(reciprocal 4)

Задача 5: Да се напишат функции, които пресмятат сумата и произведението на числата от 1 до n.

; Linear recursion
(define (sum n)
  (if (zero? n)
      0
      (+ n 
         (sum (- n 1)))))

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

Задача 6: Да се напишат итеративни функции, които пресмятат сумата и произведението на числата от 1 до n.

; Tail recursion
(define (sum-1 n)
  (define (sum-iter n s)
    (if (zero? n)
        s
        (sum-iter (- n 1) (+ s n))))

  (sum-iter n 0))

(define (fact-1 n)
  (define (fact-iter n p)
    (if (zero? n)
        p
        (fact-iter (- n 1) (* p n))))

  (fact-iter n 1))

Задача 7: Напишете функция, която пресмята n^-тото число на Фибоначи.

; Tree recursion
(define (fib n)
  (cond ((zero? n) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Задача 8: Напишете итеративна функция, която пресмята n^-тото число на Фибоначи.

; Fibonacci's tale (or tail)
(define (fib-1 n)
  (define (fib-iter n a0 a1)
    (cond ((zero? n) a0)
          ((= n 1) a1)
          (else (fib-iter (- n 1) a1 (+ a0 a1)))))

  (fib-iter n 0 1))