Is lazy evaluation of infinite series possible?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Is lazy evaluation of infinite series possible?

Erisa
I am just learning Pharo (taking the MOOC actually!) and am wondering whether it is possible to model formal power series.  I have done this in Haskell quite easily and efficiently, but struggled to do it in Python without real success.  It requires one to perform operations on an infinite stream (such as multiplying two infinite power series).  One then only evaluates the terms as they are needed, i.e., lazily.  Any thoughts?
Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

Nicolai Hess-3-2


2016-05-28 20:57 GMT+02:00 Erisa <[hidden email]>:
I am just learning Pharo (taking the MOOC actually!) and am wondering whether
it is possible to model formal power series.  I have done this in Haskell
quite easily and efficiently, but struggled to do it in Python without real
success.  It requires one to perform operations on an infinite stream (such
as multiplying two infinite power series).  One then only evaluates the
terms as they are needed, i.e., lazily.  Any thoughts?

Hi Erisa,

we have generatos in Pharo!

See class Generator.


nicolai
 



--
View this message in context: http://forum.world.st/Is-lazy-evaluation-of-infinite-series-possible-tp4897956.html
Sent from the Pharo Smalltalk Users mailing list archive at Nabble.com.


Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

Evan Donahue
In reply to this post by Erisa
Hello,

I know infinite series are mentioned in the numerical methods book, although I haven't worked with those classes specifically.

http://files.pharo.org/books/numerical-methods/2016-04-NumericalMethods.pdf

You could also use a LazyList, depending on what you were doing, from http://smalltalkhub.com/#!/~EvanDonahue/Lazy/

x := 3.
Float e raisedTo: x. " = 20.085536923187664"

eX := LazyList wholes collect: [ :n | (x raisedTo: n) / n factorial ].
(eX take: 20) sum asFloat. " = 20.085536921517672"

2 * (Float e raisedTo: x). " = 40.17107384637533"

twoEX := eX with: eX collect: [ :a :b | a + b ].
(twoEX take: 20) sum asFloat. " = 40.171073843035344"

Will either of those work?

Evan
Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

stepharo
In reply to this post by Erisa
Hello Erisa

> I am just learning Pharo (taking the MOOC actually!)

:)

> and am wondering whether
> it is possible to model formal power series.  I have done this in Haskell
> quite easily and efficiently, but struggled to do it in Python without real
> success.  It requires one to perform operations on an infinite stream (such
> as multiplying two infinite power series).  One then only evaluates the
> terms as they are needed, i.e., lazily.  Any thoughts?
I'm eager to hear what other and you will say.
Now since blocks are closures, and I remember that long time ago I
implemented simply
infinite stream with a closure in CLOS it should be a same in Pharo.
Now it was probably 20 years ago so I forgot the exact implementation.

I hope that you have fun with our neat language.
Stef
>
>
>
> --
> View this message in context: http://forum.world.st/Is-lazy-evaluation-of-infinite-series-possible-tp4897956.html
> Sent from the Pharo Smalltalk Users mailing list archive at Nabble.com.
>
>


Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

Erisa
In reply to this post by Evan Donahue
I took a look at the numerical methods book, but it seems oriented to actually evaluating an infinite series up to a certain accuracy.  With formal power series all we want are the coefficients.  For example, consider the series

S = 1 + x + x^2 + x^3 + ...

The coefficients are an infinite list [1, 1, ...].  What I need is a class for S that would allow me to perform operations such as addition, multiplication, etc.  Thus I would like to able to do S * S and get the infinite list of the coefficients [1, 2, 3, 4, ...] and view say the first 10 or perhaps the nth coefficient.

Your LazyList looks promising.  To create the series this seems like it would work.

s := LazyList wholes collect: [ :n | 1 ]

But defining the operations is the difficult part.  I would like to look at your package, but I need some help.  How can I download your package from smalltalk hub so that I can examine it, play with it, but eventually easily remove it if I want.  As you can tell, I have just started learning Pharo.

Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

Evan Donahue
Hello,

Other people are probably better qualified to weigh in on the best ways to manage packages in a Pharo image, but this is what I do:

1) Left click on the "desktop" to bring up the "world menu" and select "Monticello Browser."
2) Click the "+Repository" button and select "smalltalkhub.com" from the popup menu.
3) Type 'EvanDonahue' and 'Lazy' inside the provided quotes next to owner: and project:, respectively (user and password can be left ''). Then click OK.
4) Highlight "Lazy-Core-EvanDonahue.26.mcz" on the right panel (may be 26 or any other number) and click the "Browse" button to explore the classes and methods without actually installing in your image.
5) Click the "Load" button to install the classes in the image. You may also want to install Lazy-Tests just to have some code examples to look at.
6) To remove everything later, open Monticello again, search for "Lazy," right-click Lazy-Core in the left pane, and "unload"

As for your use case, what you have written should work, but if you just want a ton of 1's, you can use
LazyList repeat: 1
There are other class methods of increasing generality for generating infinite lists, but of course you can always use #collect: and friends to compose appropriately. LazyList is technically still "under development," but it should be feature complete for most uses. Let me know if there's any functionality it's missing, or if you're wondering whether and how it can do something. If you want to say any more about the operations you are trying to perform, I can be more specific about how to do them. Roughly, aside from the infinite methods, the API follows the standard Pharo collections.

And also welcome to Pharo. It's a trip.

Cheers,
Evan
Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

HilaireFernandes
In reply to this post by Erisa
Did you take a look at Nicolai suggestion regarding the Generator class.
There is a fibonacci example in its test case.


fibo := GeneratorTest new fibonacciSequence

then to access the sequence term:
fibo next.

Hilaire
--
Dr. Geo
http://drgeo.eu


Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

Erisa
The fibonacciSequence example was really helpful.  I made a new class PowerSeries, a subclass of Generator.  Then I defined a binary operation  + as follows:

+ aPowerSeries
  ^ PowerSeries on: [ :ps |
    | a b |
    [ a := self next.
      b := aPowerSeries next.
      ps yield: (a + b) ]
    repeat ]

This works perfectly.  But now I am struggling with how to define multiplication.  When I do PS1 * PS2, the first yield should be a := PS1 next. b := PS2 next. ps yield (a * b).  Thereafter would come the PowerSeries, call it PSNew,  (PS2 .* a) + (PS1 * PS2'),  where .* is scalar multiplication (easy to implement) and PS2' is the original PS2 (i.e., rewound 1).  I see several problems here.  It looks like I need a way to clone (fork?) a PowerSeries since in this computation I need both the current PS2 and the original PS2 and be able to operate with them independently.  Second, how do I define the generator so that it first yields the scalar (a*b) and thereafter is represented by the PowerSeries PSNew?  Finally, will the recursion in the definition of * blow up rapidly?
Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

cedreek
I have no idea of the solution…
but what I just read brought to me « Continuation » . 
I wonder if it may help here.

My 0.2 cents,

Cédrik
Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

HilaireFernandes
In reply to this post by Erisa
Multiplication of power series looks tricky as for the term k of the
resulting power series you need to access terms where sum index value to
k. (ps1 next: i) and (ps2 next: k - i). Somehow the bloc of code
defining the multiplicated serie needs to know about its current rank k.

You should not need a dedicated .* operator, you can handle it with only
* operator with appropriate object testing.

No real answer

Le 30/05/2016 21:47, Erisa a écrit :

> The fibonacciSequence example was really helpful.  I made a new class
> PowerSeries, a subclass of Generator.  Then I defined a binary operation  +
> as follows:
>
> + aPowerSeries
>   ^ PowerSeries on: [ :ps |
>     | a b |
>     [ a := self next.
>       b := aPowerSeries next.
>       ps yield: (a + b) ]
>     repeat ]
>
> This works perfectly.  But now I am struggling with how to define
> multiplication.  When I do PS1 * PS2, the first yield should be a := PS1
> next. b := PS2 next. ps yield (a * b).  Thereafter would come the
> PowerSeries, call it PSNew,  (PS2 .* a) + (PS1 * PS2'),  where .* is scalar
> multiplication (easy to implement) and PS2' is the original PS2 (i.e.,
> rewound 1).  I see several problems here.  It looks like I need a way to
> clone (fork?) a PowerSeries since in this computation I need both the
> current PS2 and the original PS2 and be able to operate with them
> independently.  Second, how do I define the generator so that it first
> yields the scalar (a*b) and thereafter is represented by the PowerSeries
> PSNew?  Finally, will the recursion in the definition of * blow up rapidly?

--
Dr. Geo
http://drgeo.eu


Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

rausm
In reply to this post by Erisa
Hi,

> will the recursion in the definition of * blow up rapidly

Wouldn't memoization wrapper help (in case of re-evaluation) ?
Reply | Threaded
Open this post in threaded view
|

Re: Is lazy evaluation of infinite series possible?

wernerk
In reply to this post by Erisa
Hi Erisa,
one solution, using your notation, could eg be
* aPowerSeries
   ^ PowerSeries on:
        [ :generator |
                |a b|
                a:=OrderedCollection new.
                b:=OrderedCollection new.
                [ a add: self next.
           b add: aPowerSeries next.
                  generator yield:
                        a asDhbVector * b asDhbVector reverse
                ] repeat
        ]
the multiplication of DhbVectors is the same as your ".*". DhbVector is
not in the standard pharo, it is part of the polymath project, i was
just too lazy to program that part by hand, but changing that should be
no problem.
werner

On 05/30/2016 09:47 PM, Erisa wrote:

> The fibonacciSequence example was really helpful.  I made a new class
> PowerSeries, a subclass of Generator.  Then I defined a binary operation  +
> as follows:
>
> + aPowerSeries
>    ^ PowerSeries on: [ :ps |
>      | a b |
>      [ a := self next.
>        b := aPowerSeries next.
>        ps yield: (a + b) ]
>      repeat ]
>
> This works perfectly.  But now I am struggling with how to define
> multiplication.  When I do PS1 * PS2, the first yield should be a := PS1
> next. b := PS2 next. ps yield (a * b).  Thereafter would come the
> PowerSeries, call it PSNew,  (PS2 .* a) + (PS1 * PS2'),  where .* is scalar
> multiplication (easy to implement) and PS2' is the original PS2 (i.e.,
> rewound 1).  I see several problems here.  It looks like I need a way to
> clone (fork?) a PowerSeries since in this computation I need both the
> current PS2 and the original PS2 and be able to operate with them
> independently.  Second, how do I define the generator so that it first
> yields the scalar (a*b) and thereafter is represented by the PowerSeries
> PSNew?  Finally, will the recursion in the definition of * blow up rapidly?
>
>
>
> --
> View this message in context: http://forum.world.st/Is-lazy-evaluation-of-infinite-series-possible-tp4897956p4898204.html
> Sent from the Pharo Smalltalk Users mailing list archive at Nabble.com.
>
>