Разница в обработке рекурсии между языками

Question

Вот несколько фрагментов на разных языках.

Функция double, о которой идет речь, взята из SICP, ex. 1,41.

Лисп:

(define (double f) (lambda (x) (f (f x))))
(define (inc x) (+ x 1))
(((double (double double)) inc) 5)

Python:

def double(f):
  def result(x):
    return f(f(x))
  return result

def inc(x):
  return x + 1

double(double(double(inc)))(5)

Javascript:

var double = function(f) {
  return function(x) { return f(f(x)) };
};

var inc = function(x) { return x + 1  };

(double(double(double(inc))))(5);

Ruby:

double = lambda {|f| lambda {|x| f[f[x]] } }
inc = lambda {|x| x+1 }
double[double[double[inc]]][5]

Если я не псих, эти функции должны делать то же самое и возвращать одинаковый результат. Тем не менее, версия LISP возвращает 21, а другие возвращают 13. Можете ли вы объяснить мне эту разницу? Я что-то упустил?

Answer 1

То, как вы вызываете функции в коде схемы, отличается от других.Эквивалентный питон будет:

double(double(double))(inc)(5)

Словом, код схемы создает функцию, которая применяет другую функцию 16 раз, и применяет эту функцию к inc.Питон создает функции, которые применяются inc 8 раз;остальные работают так же, как питон.

Разница может быть немного яснее, если вы введете имена для промежуточных шагов.На схеме:

(define quadruple (double double))
(define hexadecuple (double quadruple)) ; hexadecuple may not actually be a word... 
(define add16 (hexadecuple inc))
(add16 5)

Надеюсь, это правильный синтаксис;я давно уже ничего не делал со схемой

В питоне:

add2 = double(inc)
add4 = double(add2)
add8 = double(add4)
add8(5)

Answer 2

Для полноты картины вот как будет выглядеть исправленная версия Ruby:

double = ->f { ->x { f.(f.(x)) }}
inc    = ->x { x.succ }

double.(double.(double)).(inc).(5)