Algorithmic lists

Robert Virding <>
Tue Oct 17 12:02:41 CEST 2000


Andy with Recycled Electrons <> writes:
>Let me clarify...
>
>Accessing a list is a simple, real-time operation.  
>
>Accessing a Lazy List may mean accessing a megapixel image from Hong Kong,
>where it is ray traced in true color based on several dozen light
>sources.
>
>In other words, there would be no gurantee of ANY timing constraints.  As
>long as the "real time" system realizes this, everyone is happy. 

This whole argument of whether lazy lists violates the real time 
constraints is definitely weird!

Firstly, accessing a whole list is definitely not a simple operation,
only accessing the first cons cell.  For all the rest you step down the
list.

Secondly, the real difference between "normal" lists and "lazy" lists is
WHEN you build them.  For a "normal" list you build the whole list in
one go at creation time.  For "lazy" lists you build the list one cons
cell at a time when you access the list.  In essence you amortize the
list creation work over reading.

Thirdly, this does not affect the real time constraints of ERLANG as you
are not doing any new of type of action.  It's still just evaluating
functions, all you are doing is changing the time when you evaluate the
functions.

Fourthly, this may of course have a profound affect on the real time
constraints of the APPLICATION.  Sending (as an argument or message) a 
lazy list can affect when, where and who actually builds the list.

Fifthly, seeing Erlang doesn't natively support lazy evaluation you 
always have to KNOW whether the tail is a "normal" tail or an 
unevaluated "lazy" tail.  also every time you access the list you will 
have to re-evaluate the tails as Erlang will not automatically replace 
the tails with thier value.  This severely limits it usefulness.

Sixthly, in many lazy languages lazy lists are used as a form of 
communication bewtween coroutines.  Erlang has processes for this.  
What is left is then infinite lists.

Because of all this I don't really see that much use of lazy lists 
apart form as a fun programming exercise.  Find me a real application 
and try to convert me.  Personally I think fifthly is the real clincher.

	Robert

P.S. I once toyed with idea of doing a real lazy Erlang.  If you made 
message sending force the full evaluation of the message, and maybe 
force the evaluation of calls in which the result is ignored it 
would probably work.

-- 
Robert Virding                          Tel: +46 (0)8 545 55 017
Alteon Web Systems                      Email: 
S:t Eriksgatan 44                       WWW: http://www.bluetail.com/~rv
SE-112 34 Stockholm, SWEDEN
"Folk säger att jag inte bryr mig om någonting, men det skiter jag i".





More information about the erlang-questions mailing list