lazy evaluation

[ct]

I was wondering if there is any interest to offer some lazy evaluation mechanics in the julia language (or if any exist currently)? 

Most of my work is very heavy on the memory consumption side of things and any mechanisms that offer lazy list or dictionary processing would be a really nice benefit. (similar to a python yield statement)

cheers,

ct

[Elliot Saba]

Try searching the archives of this list (https://groups.google.com/forum/?fromgroups#!forum/julia-dev), you might find what you're looking for.  There has been some work done on Lazy Evaluation by one member, and some parallel efforts by another with the goal of allowing GPGPU computation.

-E

[Patrick O'Leary]

Specifically, look for "delayed evaluation", though that's not really what I think ct is looking for. Depending on how your data set is stored, Tim's work on mmapped arrays may be of interest. For doing lazy i/o or lazy lists, you'll want to take a look at how iterators are implemented. Making an iterator lazy should just require putting the deferred work in the next() method for that iterator type.

On Thursday, May 17, 2012 6:06:58 PM UTC-5, Elliot Saba wrote:

Try searching the archives of this list (https://groups.google.com/forum/?fromgroups#!forum/julia-dev), you might find what you're looking for.  There has been some work done on Lazy Evaluation by one member, and some parallel efforts by another with the goal of allowing GPGPU computation.

-E

[Stefan Karpinski]

If you mean adding lazy evaluation semantics to the language, then no, that's definitely not going to happen.

If, on the other hand, you want to build lazy data structures like infinite lists, then that's perfectly doable without changing anything. You can override the behavior of index `x[i]` via the `ref` function and create data structures that don't compute values until they're requested. Iteration can also be done lazily without any changes — see, e.g., the EachLine iterator that iterates through lines read from an input stream.

I'm not sure what Python's yield statement has to do with lazy evaluation, but we already support the equivalent of yield since Julia has coroutines as one of its basic control flow constructs. In Julia yield is called "produce" and it's defined in terms of coroutines rather than being a keyword. You can create a producer task and then iterate the values it produces (yields), which may be what you want.

Performance warning: using coroutines is going to be much less performant than manually manipulating state using start/done/next. That's why all of our core iteration constructs use explicit state manipulation. Sometimes using a coroutine is handy though if you don't care that much about raw performance.

[david tweed]

It's not clear what the Python behaviour you're talking about is (to a
casual Python user like me). Could you describe a bit more what's
happening operationally: that would help to see if/how a similar
effect could be achieved in Julia.

FWIW, I've been looking at "implicit loop fusion" for the elimination
of temporaries in array expressions, but that's applicable in the
particular case you know all the data structure shapes in advance.

[ct]

Hey there, my apologies for dropping off the map. Lazy evaluation would be nice, I was also wondering about lazy data loading.

I hope this helps describe a little better what I'm interested in:

http://en.wikipedia.org/wiki/Lazy_loading 

Right now there are a bunch of very large matrix factorization problems I'd like to process but loading *all* of the matrix into memory is not really tractable for my work. Any method to hold off on completely loading those objects into memory until they are needed or the bare minimum would be perfect.

This is something that happened with an Octave solution I was attempting to code - the sparse representation was attempting to load bits of the matrix into their "full" representation and it was too much memory for octave to load in one sitting.

And that got me thinking a lazy loading slice operator would be really nice.

ct

On Thursday, May 17, 2012 7:06:58 PM UTC-4, Elliot Saba wrote:

Try searching the archives of this list (https://groups.google.com/forum/?fromgroups#!forum/julia-dev), you might find what you're looking for.  There has been some work done on Lazy Evaluation by one member, and some parallel efforts by another with the goal of allowing GPGPU computation.

-E

[ct]

Awesome! Stefan, that's exactly what I was looking for - much appreciated.

Has anyone done shared memory work Julia yet?

ct

[ct]

Just posted a quick response about lazy loading and evaluation. Hope that clarifies.

[Stefan Karpinski]

On Tue, May 22, 2012 at 9:37 PM, ct <christopher...@gmail.com> wrote:

Hey there, my apologies for dropping off the map. Lazy evaluation would be nice, I was also wondering about lazy data loading.

Lazy evaluation is definitely not going to happen. It is an insane feature in an impure, imperative programming language.

 

I hope this helps describe a little better what I'm interested in:

http://en.wikipedia.org/wiki/Lazy_loading 

Right now there are a bunch of very large matrix factorization problems I'd like to process but loading *all* of the matrix into memory is not really tractable for my work. Any method to hold off on completely loading those objects into memory until they are needed or the bare minimum would be perfect.

This is something that happened with an Octave solution I was attempting to code - the sparse representation was attempting to load bits of the matrix into their "full" representation and it was too much memory for octave to load in one sitting.

And that got me thinking a lazy loading slice operator would be really nice.

Tim wrote a great mmapped array implementation that's in the Julia standard library now. This offloads the laziness of loading data to the best possible place — the kernel. It doesn't solve all large data problems but it is very helpful.

[John Myles White]

I have the impression that Chris doesn't want lazy evaluation like R has, but is looking for something like an infinite list that is created as accessed. Is that right, Chris?

 -- John

[Stefan Karpinski]

Right, that's not what the term lazy evaluation means — those are lazy data structures. I was trying to clarify that distinction in my original response, but maybe failed to do so. In languages with true lazy evaluation like Haskell (not the weird half-lazy evaluation that R has), all data structures are lazy, so infinite data structures are natural to create, but lazy evaluation and lazy data structures are very different.

[Stefan Karpinski]

Interestingly, the wikipedia page doesn't make this a very clear distinction, which is a bit weird, but maybe I'm just wrong about that distinction.

[John Cowan]

On Tue, May 22, 2012 at 10:17 PM, Stefan Karpinski <ste...@karpinski.org> wrote:

> Right, that's not what the term lazy evaluation means — those are lazy data
> structures. I was trying to clarify that distinction in my original
> response, but maybe failed to do so. In languages with true lazy evaluation
> like Haskell (not the weird half-lazy evaluation that R has), all data
> structures are lazy, so infinite data structures are natural to create, but
> lazy evaluation and lazy data structures are very different.

Well, yes and no. Scheme and Pure are both impure eager languages
with both eager and lazy data structures available. (If it comes to
that, FILE is effectively a lazy data structure in C.) The Scheme
standards allow lazy data structures to be forced by primitive
procedures (the Chibi implementation makes this a compile-time option)
and Pure's list procedures will accept either eager or lazy lists.
That sounds like something Julia users might plausibly want: see
http://docs.pure-lang.googlecode.com/hg/pure.html#lazy-evaluation-and-streams
for details.

Pure and Julia should learn to go hand in hand. Both are dynamic
languages, both were designed for particular niches but are applicable
to much wider problems, both use LLVM, both can load arbitrary
C-compatible functions from dynamic libraries. Pure can also call
arbitrary functions from bitcode files; if Julia can learn to do that,
or at least to generate bitcode (which I understand is trivial), the
basis for interoperation will be present. Albert Gräf, the author of
Pure, has said he is in favor of it: see
https://groups.google.com/group/pure-lang/msg/c4df7941c15e171b?dmode=source&output=gplain&noredirect
for his take on Julia as of about a month ago.
--
GMail doesn't have rotating .sigs, but you can see mine at
http://www.ccil.org/~cowan/signatures

[Stefan Karpinski]

Pure interop would be very cool. There could even be whole-program, inter-procedural optimizations done since both languages are LLVM :-)

[John Cowan]

On Wed, May 23, 2012 at 1:31 AM, Stefan Karpinski <ste...@karpinski.org> wrote:

> Pure interop would be very cool. There could even be whole-program,
> inter-procedural optimizations done since both languages are LLVM :-)

Ooookay. So teach Julia to write bitcode files.

[Stefan Karpinski]

It's actually not so trivial because we JIT everything. Writing bitcode is easy (even necessary) when you do static compilation. We do not, so it's not that simple.

[John Cowan]

On Wed, May 23, 2012 at 1:48 AM, Stefan Karpinski <ste...@karpinski.org> wrote:

> It's actually not so trivial because we JIT everything. Writing bitcode is
> easy (even necessary) when you do static compilation. We do not, so it's not
> that simple.

Right, I forgot that you don't have a batch compiler.