Forum: Ruby memoization example the ruby programming language question

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Hiro P. (Guest)
on 2008-10-28 18:32
Attachment: memoization.txt (0 Bytes)
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
Jesús Gabriel y Galán (Guest)
on 2008-10-28 19:58
(Received via mailing list)
On Tue, Oct 28, 2008 at 5:32 PM, Hiro P. <removed_email_address@domain.invalid>
wrote:

> 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.
James G. (Guest)
on 2008-10-28 20:00
(Received via mailing list)
On Oct 28, 2008, at 11:32 AM, Hiro P. wrote:

> 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 G. II
Hiro P. (Guest)
on 2008-10-29 20:58
Hiro P. wrote:
> 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
------------------------------------
This topic is locked and can not be replied to.