ruslanxdev/scip-01-1-the-elements-of-programming.md

Структура и интерпретация компьютерных программ / Элементы программирования

Источник: Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman — MIT.

Конспект

Выражения

Lisp использует префиксную нотацию, вначале идет оператор, а потом операнды.
Скобки обозначают выражение.
В префиксной нотации оператор может применятся к любому количеству операндов.

(+ 137 349)
486
(- 1000 334)
666
(* 5 99)
495

Именование и окружающая среда

Переменные определяются с помощью оператора define.
Можно определять переменные любими выражениями.

(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
314.159
(define circumference (* 2 pi radius))
circumference
62.8318

Оценка комбинаций

Можно составлять комбинации из выражений.

(* (+ 2 (* 4 6))
   (+ 3 5 7))

Составные процедуры

Процедура — это функция.
Определять процедуру можно по следующей форме:

(define (<name> <formal parameters>) <body>)

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

(define (square x) (* x x))
(square 21)
441

(define (sum-of-squares x y)
  (+ (square x) (square y)))
(sum-of-squares 3 4)
25

Модель подстановки для применения процедуры (Стратегия вычисления)

Lisp использует нормальный порядок вычислений.
Нормальный порядок вычислений (Normal order evaluation) — стратегия вычислений, при которой охватывающее выражение полностью редуцируется, применяя функции до вычисления аргументов.
Аппликативный порядок вычислений (Applicative order evaluation) — стратегия вычислений, при которой максимально редуцируются термы в теле функции до её применения.

Условные выражения и предикаты

Условные выражения — выражения, которые возвращают то, или иное значение в зависимости от заданных условий (предикатов).
Предикаты — процедуры, которые определяют истинность какого либо выражения и принимают булевое значение. Например: >, < и =.
Условные выражения определяются с помощью ключевого слова cond по следующей форме, где:
- p — предикат.
- e — последующее выражение.

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

$$ |r| = \begin{cases} r &r > 0\\ 0 &r = 0\\ -r &r < 0\\ \end{cases} $$

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

(define (abs x)
  (cond ((< x 0) (- x))
        (else x)))

Можно определять условные выражения с помощью ключевого слова if.
Выражение if используется, когда у нас только один предикат и два выражения.
Выражение if опередляется по следующей форме, где:
- predicate — предикат.
- consequent — выражение, которое возращается вследствие истинности предиката.
- alternative — выражение, которое возращается вследствие ложности предиката.

(if <predicate> <consequent> <alternative>)

(define (abs x)
  (if (< x 0)
      (- x)
      x))

Можно использовать логические операторы И, ИЛИ, НЕ с помощью ключевых слов and, or, not соответсвенно.
Логические операторы определяются по следующим формам:

(and <e1> ... <en>)
(or <e1> ... <en>)
(not <e>)

(and (> x 5) (< x 10))
(define (>= x y)
  (or (> x y) (= x y)))
(define (>= x y)
  (not (< x y)))

Пример: Квадратные корни по методу Ньютона

Квадратным корнем числа является такое число, которое больше нуля и квадрат которого равен числу, из которого извлекается этот корень.

$$ \sqrt{r} = x;, \text{где}; x >= 0,; x^2 = r $$

Алгоритм нахождения квадратного корня по методу Ньютона (метод нахождения корня (нуля) заданной функции):
- Сделать начальное предположение $x_{0}$.
- Проверяем, в нужных ли пределах погрешность.
- Если погрешность в нужных пределах, возвращаем результат.
- Если погрешность не в нужных пределах, вычисляем новое приближение $(x_{0} + r / x_{0}) / 2$, и повторяем шаг два.

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))
                 
(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))
  
(sqrt 9)
3.00009155413138

Процедуры как абстракции черного ящика (Black-Box Abstractions)

Значение процедуры должно быть независимым от имен параметров.
Имена параметров процедуры должны быть локальными для тела процедуры.
Внутренние определения и блочная структура. Можно определять переменные и процедуры внутри других тел процедур.

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))

ruslanxdev/scip-01-1-the-elements-of-programming.md

Select an option

No results found

Select an option

No results found

Структура и интерпретация компьютерных программ / Элементы программирования

Конспект

Выражения

Именование и окружающая среда

Оценка комбинаций

Составные процедуры

Модель подстановки для применения процедуры (Стратегия вычисления)

Условные выражения и предикаты

Пример: Квадратные корни по методу Ньютона

Процедуры как абстракции черного ящика (Black-Box Abstractions)

Ссылки: