memoization example the ruby programming language question

H

Hiro Protagonist

Hi all,

Attached is the example of memoization from the above book.

I am awed by ruby.

I understand what the program does in that I inserted puts statements
to follow it's logic. It definitely caches the recursive calls. In
fact you can even enlarge the cache by asking for a larger factorial and
the factorial Lambda Proc object will not do any unnecessary
computations and use cached results if they exist. For example if I
initially do factorial.call(4) the results will be cached. If I then do
factorial.call(5) it will do a computation and use the factorial.call(4)
cached result saving considerable amount of work.

I marked the line that I don't understand. I want an explanation in
terms of syntax. If cache has data why is method memoize called first?
I understand the initially recursive calls when cache is empty. In empty
cache scenario the factorial lambda Proc keeps being called recursively
until x == 0. Once this happens memoize is called up the stack for each
factorial call and data is cached for each value of x. But when cache
is full and momoization is used. Why does it go to method memoize
first? I just don't see it syntactically. This example may use some
ruby 1.9 syntax. I think factorial[x-1] is equivalent to
factorial.call(x-1).

I need an explanation of syntax. Also I have never seen the syntax:
factorial = lambda {|x| return 1 if x==0; x*factorial[x-1]; }.memoize
where the memoize method is attached to end of lambda {}. Does
factorial PROC object contain lambda block plus the appended memoize
method?

I understand what it does but I am missing the syntax.

Thanks,
pete

Attachments:
http://www.ruby-forum.com/attachment/2859/memoization.txt
 
J

Jesús Gabriel y Galán

I marked the line that I don't understand. I want an explanation in
terms of syntax. If cache has data why is method memoize called first?

This:

class Proc; include Functional; end

adds the method "memoize" to the Proc class.

This:

lambda {|x| return 1 if x==0; x*factorial[x-1]; }

creates a Proc object, which, by means of the above extension
has a method memoize. With this:

lambda {|x| return 1 if x==0; x*factorial[x-1]; }.memoize

you call the method memoize of the created Proc object.
Maybe this is more clear:

temp_proc = lambda {|x| return 1 if x==0; x*factorial[x-1]; }
factorial = temp_proc.memoize()

The method memoize returns a Proc itself. This new Proc
maintains a cache of calls. When there's a cache miss, it calls
the original Proc (check uses of "self" inside the memoize method).
When there's a cache hit, the original proc is not called, and the cached
value is returned instead.

I understand the initially recursive calls when cache is empty. In empty
cache scenario the factorial lambda Proc keeps being called recursively
until x == 0. Once this happens memoize is called up the stack for each
factorial call and data is cached for each value of x. But when cache
is full and momoization is used. Why does it go to method memoize
first? I just don't see it syntactically. This example may use some
ruby 1.9 syntax. I think factorial[x-1] is equivalent to
factorial.call(x-1).

Yes, but factorial here is not your original proc. It's the proc returned
but the memoize method.
I need an explanation of syntax. Also I have never seen the syntax:
factorial = lambda {|x| return 1 if x==0; x*factorial[x-1]; }.memoize
where the memoize method is attached to end of lambda {}. Does
factorial PROC object contain lambda block plus the appended memoize
method?

I think you are confusing the terms here. "memoize" is a method of proc
objects that returns a proc.

Let me know if this sheds some light...

Jesus.
 
J

James Gray

Hi all,
Hello.

Attached is the example of memoization from the above book.
I marked the line that I don't understand. I want an explanation in
terms of syntax.

OK, lambda() is just the tool that creates the Proc object for you.
You call memoize() on that to turn it into a meomized Proc.
If cache has data why is method memoize called first?

The memoize() method is called on a Proc, to transform it into a
memoized Proc. From then on, you get the cached magic when you use it.
This example may use some ruby 1.9 syntax. I think factorial[x-1]
is equivalent to factorial.call(x-1).

That's valid in Ruby 1.8 as well.

Hope that helps explain things.

James Edward Gray II
 
H

Hiro Protagonist

Hiro said:
Hi all,

Attached is the example of memoization from the above book.

I am awed by ruby.

I understand what the program does in that I inserted puts statements
to follow it's logic. It definitely caches the recursive calls. In
fact you can even enlarge the cache by asking for a larger factorial and
the factorial Lambda Proc object will not do any unnecessary
computations and use cached results if they exist. For example if I
initially do factorial.call(4) the results will be cached. If I then do
factorial.call(5) it will do a computation and use the factorial.call(4)
cached result saving considerable amount of work.

I marked the line that I don't understand. I want an explanation in
terms of syntax. If cache has data why is method memoize called first?
I understand the initially recursive calls when cache is empty. In empty
cache scenario the factorial lambda Proc keeps being called recursively
until x == 0. Once this happens memoize is called up the stack for each
factorial call and data is cached for each value of x. But when cache
is full and momoization is used. Why does it go to method memoize
first? I just don't see it syntactically. This example may use some
ruby 1.9 syntax. I think factorial[x-1] is equivalent to
factorial.call(x-1).

I need an explanation of syntax. Also I have never seen the syntax:
factorial = lambda {|x| return 1 if x==0; x*factorial[x-1]; }.memoize
where the memoize method is attached to end of lambda {}. Does
factorial PROC object contain lambda block plus the appended memoize
method?

I understand what it does but I am missing the syntax.

Thanks,
pete
-------------------------
Thanks for explanation!!! Boy I would never would have seen it.
Insane!

I read the K&R The C Programming Language which to me is a tour de
force. Have not seen too many books of that caliber. I would say this
book, The ruby programming language, might be of that caliber.

I was never awed by objects I am not convinced they are as great as
everybody says they are. I come from a procedural language background.
Even worked in assembler. Ruby though impresses me !!!!

Thanks again,
Pete
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top