Перевод решения SICP со схемы на Python

Есть два способа подумать о переводе. Можно было бы написать дословный, прямой перевод, не соблюдая идиомы и соглашения Python - он будет выглядеть так:

def f(n):
    def iter(a, b, c, count):
        if count == 0:
            return a
        else:
            return iter(b, c, 2*b + 3*a + c, count-1)
    return iter(0, 1, 2, n)

Другой способ - написать код в стиле Pythonic, чтобы он уважал соглашения целевого языка и использовал свои механизмы итерации:

def f(n):
    a, b, c = 0, 1, 2
    for count in range(n):
        a, b, c = b, c, 2*b + 3*a + c
    return a

Кстати, вторая версия будет быстрее и не будет иметь проблем с ошибкой переполнения стека (Python не оптимизирован для рекурсии!). Неважно, что в рекурсивной версии count идет от n к 0, а в версии цикла count идет от 0 к n, потому что в любом случае значение count не используется ни для чего, кроме повторения заданного количества раз.

Давайте посмотрим на этот код:

;; ex 1.11. Iterative implementation 

(define (f n) 
  (define (iter a b c count) 
    (if (= count 0) 
      a 
      (iter b c (+ c (* 2 b) (* 3 a)) (- count 1)))) 
  (iter 0 1 2 n)) 

Прежде всего следует отметить, что определяются две функции. Один f, а другой iter. iter является вспомогательной функцией и предназначена для использования только f (поскольку она определена внутри из f. Однако нет причин, по которым вы не можете фактически разделить два определения на:

(define (iter a b c count) 
  (if (= count 0) 
    a 
    (iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))

(define (f n) 
  (iter 0 1 2 n)) 

В Lisps синтаксис (frob bar1 bar2 ...) означает, что вы вызываете функцию frob с аргументами bar1, bar2, .... Итак, определение f

(define (f n) 
  (iter 0 1 2 n)) 

должно быть относительно ясно. Вы определяете функцию f, которая принимает один аргумент n, а затем вызываете функцию iter с четырьмя аргументами: 0, 1, 2 и n. Так что же iter?

(define (iter a b c count) 
  (if (= count 0) 
    a 
    (iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))

iter принимает четыре аргумента. Во-первых, он проверяет, является ли count 0. Если это так, то iter вернет a. В противном случае iter рекурсивно вызывает себя с b, c. (+ c (* 2 b) (* 3 a)) и (- count 1), и возвращается значение, возвращаемое рекурсивным вызовом. Основываясь на приведенном выше описании синтаксиса Lisp, вы сможете сказать, что (+ c (* 2 b) (* 3 a)) - это просто математическое выражение c + 2b + 3a, а (- count 1) - это просто count-1 .

Я полагаю, что самая сложная часть всего этого - знать, что if принимает три аргумента: первый - это тестовое выражение; вторая часть - «тогда», также называемая консеквентом; и третья часть - «else», также называемая альтернативой. В отличие от некоторых других языков, где if используется только для условного выполнения некоторых операторов, (if ...) возвращает значение в Лиспе, и это значение является либо значением консеквента, либо значением альтернативы, в зависимости от того, значение теста было истинным или ложным.

С этим описанием вы сможете написать аналог на любом языке программирования, с которым вы знакомы.

Конечно, когда вы все это поймете, вам стоит прочитать некоторые из Криса Ратмана перевод кода SICP на Python, который включает перевод этого кода из упражнения 1.11:

# Exercise 1.11
def f(n):
   if n < 3:
      return n
   else:
      return f(n-1) + 2*f(n-2) + 3*f(n-3)
def f_iter(a, b, c, count):
   if count == 0:
      return c
   else:
      return f_iter(a + 2*b + 3*c, a, b, count-1)
def f(n):
   return f_iter(2, 1, 0, n)

Вот в основном как это выглядит на C

int iter (int a, int b, int c, int count)
{
    if( count == 0 )
       return a;
    else
       return iter(b, c, c + (2 * b) + (3 * a), count - 1);
}

Каждое выражение в Scheme оценивается как значение, поэтому оно неявно возвращается. if возвращает все, что выполняется ветвью, а iter возвращает все, что возвращает if, и так далее.

Не зная наверняка, это выглядит как рекурсивная последовательность, которая ссылается на 3 предыдущих числа для вычисления следующего, которое было выполнено итерацией в постоянный стек в схеме. Имейте в виду, что Python не использует хвостовой вызов для оптимизации этого, а C ++ и C, вероятно, потребуются специальные параметры компилятора и способный компилятор для этого.