Программирование на Scheme

Примитивные выражения: булевы значения #t и #f, числа (42), строки ("Hello, world"), символы ('scheme).

Попробуйте ввести различные значение перечисленных типов.

#t

Для составных выражений используется префиксная запись: применение процедуры — в скобках имя процедуры (символ) и аргументы.

(+ 1 2 3)

Сложные выражения могут быть вложенными. Попробуйте сконструировать различные выражения с числовыми константами и арифметическими процедурами +, -, *, /.

(+ (* 3 5) (- 10 6))

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

С помощью специального выражения define значения можно связывать с символами:

(define a 3)
(define b 5)

(+ (* a a) (* b b))

Попробуйте поменять значения a и b. Объявите значение c и преобразуйте следующее выражение в префиксную форму: \[\frac{abc}{ab + ac + bc}\]

Также с помощью define можно определять процедуры, сопоставляя выражение символу-имени процедуры.

(define (square x) (* x x))

(square 3)

Реализуйте процедуру, возвращающую сумму квадратов двух чисел (замените символ 'todo нужным выражением):

(define (sqr-sum a b)
  'todo)

(sqr-sum 3 5) ; 34

Предикат — выражение возвращающее булево значение. Сравнение: <, >, =; логические операторы:

• (and a1 a2 ... an),
• (or a1 a2 ... an),
• (not a).

Условные выражения:

;; Вычисление модуля числа
(define (abs1 x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

;; То же самое
(define (abs2 x)
  (cond ((< x 0) (- x))
        (else x)))

;; Или так, используя if
(define (abs3 x)
  (if (< x 0) (- x) x))

(abs1 -1)

Проверьте, что функции abs1, abs2, abs3 и стандартная функция abs работают одинаково для разных значений x.

Реализуйте процедуру my<= (меньше или равно) для двух аргументов, сравните ее работу со стандартной <=.

(define (my<= a b)
  'todo)

(my<= 1 2) ; true

Пример вычисления факториала с помощью рекурсивной процедуры, поражающей линейно-рекурсивный процесс:

(define (fact1 n)
  (if (= n 0)
      1
      (* n (fact1 (- n 1)))))

(fact1 5)

Процесс вычисления можно представить следующим образом:

(fact1 5)
(* 5 (fact1 4)
(* 5 (* 4 (fact1 3)))
(* 5 (* 4 (* 3 (fact1 2))))
(* 5 (* 4 (* 3 (* 2 (fact1 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact1 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

Другая реализация факториала. Процедура fact2 использует процедуру fact-iter, порождающую линейно-итеративный процесс:

(define (fact2 n)
  (define (fact-iter p n)
    (if (<= n 1)
        p
        (fact-iter (* p n) (- n 1))))
  (fact-iter 1 n))

(fact2 5)

Обратите внимание, что процедура fact-iter объявлена внутри fact2 и не доступна для вызова во внешнем контексте.

Порождаемый процедурой процесс вычисления:

(fact2 5)
(fact-iter   1 5)
(fact-iter   5 4)
(fact-iter  20 3)
(fact-iter  60 2)
(fact-iter 120 1)
120

С точки зрения процесса вычисления, производительности и использования памяти, вторая реализация эквивалентна вычислению факториала с помощью цикла на императивном языке программирования:

int fact2(int n) {
    int p = 1;
    while (n > 0) {
        p = p * n;
        n = n - 1;
    }
    return p;
}

Рекурсивный вызов fact-iter находится в хвостовой позиции и должен быть выполнен интерпретатором без выделения нового кадра стека.

Реализуйте процедуру, вычисляющую \(n\)-ю степень аргумента, где \(n\) — неотрицательное целое.

1. Простой алгоритм, выполняющий \(n\) умножений в виде процедуры, порождающей a) линейно рекурсивный процесс, b) линейно итеративный процесс.

   (define (my-expt b n)
     'todo)
   
   (define (my-expt-iter p b n)
     'todo)
   

2. Эффективный алгоритм с логарифмической степенью роста также в двух вариантах. Подсказка: используйте предикат even? для проверки четности n.

   (define (fast-expt b n)
     'todo)
   
   (define (fast-expt-iter p b n)
     'todo)
   

1. Х. Абельсон, Дж. Сассман. Структура и интерпретация компьютерных программ (книга на английском, перевод)
2. BiwaScheme — реализация языка Scheme на JavaScript, используемая для выполнения примеров на этой странице
3. Klipse — встраиваемая в веб-страницу интерактивная среда программирования