末尾再帰最適化を実装した

scheme

遅くなったけど自前処理系に末尾再帰最適化を実装した。

(define (hoge i)
  (if (> i 1000000)
      i
      (hoge (+ 1 i))))
(display (hoge 0))

こんなコードを書いてもスタックの消費がとても少なくてうれしい。
これで Scheme 処理系を名乗れるかなー。

さあ次は GC の高速化だ。
↓GC 遅すぎ（ ﾟдﾟ）

sewashi% ./scheme test/test.scm && gprof ./scheme |head -20
####
OK: 1 tests, 928 assertions, 928 successes, 0 failures, 0 errors
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 22.22      0.12     0.12  2426958     0.00     0.00  gc_malloc
 22.22      0.24     0.12       48     2.50     4.17  gc_mark()
 14.81      0.32     0.08     8498     0.01     0.01  gc_mark_heap(GCRecord*)
  7.41      0.36     0.04  2426959     0.00     0.00  gc_record_initialize(GCRecord*)
  7.41      0.40     0.04  2371510     0.00     0.00  gc_record_remove(GCRecord*)
  7.41      0.44     0.04    55283     0.00     0.00  monash::Translator::translateList(monash::Cons*)
  3.70      0.46     0.02  2426958     0.00     0.00  gc_record_add_to_next(GCRecord*, GCRecord*)
  1.85      0.47     0.01   484152     0.00     0.00  util::BinaryTree<monash::Object*>::get(util::BinaryTree<monash::Object*>::Node const*, int) const
  1.85      0.48     0.01   394962     0.00     0.00  monash::Frame::lookup(monash::Variable*)
  1.85      0.49     0.01    98912     0.00     0.00  monash::Cons::toObjects(util::Vector<monash::Object*>*)
  1.85      0.50     0.01    95218     0.00     0.00  monash::Kernel::makeListOfValues(util::Vector<monash::Object*>*, int, monash::Argument*, monash::Environment*, util::Vector<monash::Object*>**)
  1.85      0.51     0.01    37765     0.00     0.00  monash::Environment::clone()
  1.85      0.52     0.01    37765     0.00     0.00  monash::Procedure::apply(util::Vector<monash::Object*>*, monash::Environment*, bool)
  1.85      0.53     0.01    19493     0.00     0.00  monash::Number::value() const
  0.93      0.54     0.01  1030627     0.00     0.00  monash::Cons::type() const