This talk does a good job of showing how Perl 6 lets you gradually enhance your programs using features like types, subtypes, and multimethods. Here's a functional, memoized version of fib that uses those three features:

  subset NonNegativeInt of Int where * >= 0;

  proto fib (|) is cached returns NonNegativeInt {*}
  multi fib (0) { 0 }
  multi fib (1) { 1 }
  multi fib (NonNegativeInt $n) { fib($n - 1) + fib($n - 2) }

  say fib(100)