воскресенье, 3 апреля 2011 г.

Мемоизация рекурсивных замыканий в Groovy - FIXED

Я и забыл написать, чем кончилась вся так история с мемоизацией рекурсивных замыканий - все там оказалось в итоге довольно просто, и бага, который я подозревал, там нет. После 3 минут общения с Jochen-ом (это техлид проекта Groovy), все как-то встало нормально на свои места.

Итак, рассмотрим, как работает мой вариант, тот который я предлагал, и как следует его изменить, чтобы он работал так, как мы ожидаем.

def fact {it -> sleep(100)it ?  it call(it 1g1g}
fact fact.memoize()
println fact(70)
println fact(71)

Что же происходит в этом случае "за сценой"? Если скомлировать этот код, и декомпилировать получившийся байткод в Java-код, для простоты понимания,  то это будет выглядеть (схематично) примерно так:

class Closure1 extends MemoizedClosure {
   call (param{
       bla-bla;
       return param * this.call(param-1); // this тут значит Closure1
   }
 } 
}

Т.е. можно видеть, что вызов call() в теле замыкания всегда обращается к тому объекту замыкания, внутри которого (в лексическом контексте которого), он вызывается. Т.е. в нашем случае это всегда Closure1, а не тот враппер, умеющий делать мемоизацию, который возвращает вызов fact.memoize() (да, метод memoize() всегда возвращает новый объъект замыкания).

А как следует правильно записать это мемоизируемо-рекурсивное замыкание? А вот так:

def fact
fact {it -> sleep(100)it ?  it * fact(it 1g1g}
fact fact.memoize()
println fact(70)
println fact(71)

Обратите внимание на выделанное. Мы определяем переменную fact, и присваиваем ей ссылку на создаваемый объект замыкания, после чего создаем враппер для нашего замыкания и присваиваем ссылку на этот враппер переменной fact. И, поскольку внутри тела нашего  замыкания мы не вызываем его метод call() напрямую, а вызываем fact(), то у нас возникает возможность направить рекурсию по правильному пути - т.е. все рекурсивные вызовы теперь будет проходить через наш fact (т.е. через враппер с поддержкой мемоизации). 

В Java-коде это будет (схематично) выглядеть так:

class Closure1 extends MemoizedClosure {
  // эта ссылка будет указывать на fact, т.е. на closure wrapper,
  // который поддерживает мемоизацию.
  private Closure reference 

   call (param{
       bla-bla;
       return param reference.call(param-1);
   }
 } 
}
Желающие могут запустить исправленный код на http://groovyconsole.appspot.com/ и убедиться в его правильности :).

Комментариев нет:

Отправить комментарий