| Author |
Message |
|
| etxuwig at etxb.ericsson. |
 Posted: Mon Oct 16, 2000 10:28 am |
 |
|
|
Guest
|
Here's a thought:
We (a few lunatics at AXD 301) would like to see the lists module
support an alternative formulation of lists.
A list could be expressed in the following manner:
[Head | fun(Head, F)]
Example:
-module(alglists).
-author('etxuwig_at_etxb.ericsson.se').
-export([seq/2, foreach/2]).
%%-export([Function/Arity, ...]).
seq(Start, Stop) when Start < Stop ->
[Start | fun(N, F) when N == Stop ->
[];
(N, F) ->
[N+1 | F]
end].
foreach(F, []) ->
[];
foreach(F, [H|T]) when list(T) ->
F(H),
foreach(F, T);
foreach(F, [H|T]) when function(T) ->
F(H),
foreach(F, T(H, T)).
Eshell V4.8.2.7 (abort with ^G)
1> lists:foreach(fun(X) -> io:format("-- ~p~n", [X]) end,
lists:seq(1,5)). -- 1
-- 2
-- 3
-- 4
-- 5
ok
2> c(alglists).
{ok,alglists}
3> alglists:foreach(fun(X) -> io:format("-- ~p~n", [X]) end,
alglists:seq(1,5)).
-- 1
-- 2
-- 3
-- 4
-- 5
ok
(Perhaps to avoid breaking half the Erlang programs in the universe,
functions in lists should not return lists on this form, but should be
able to process them.)
Let me briefly tell you why we'd like to do this:
On several occasions, we've rewritten code that generates a large
list on the heap and then traverses it. It's a shame from one
perspective, because the new code (which usually uses ets:next/2) is
not FP-style, and less elegant -- but it is more well behaved from a
memory management perspective, which is its one (but vital) merit.
We'd like to keep the concept of list processing, but avoid the large
lists, which cause havoc in the GC.
What'ya think? Awful? Elegant?
BTW, Joe already posted something like this on the erlang-questions
list in March '99, but he was using zero-argument funs.
http://www.erlang.org/ml-archive/erlang-questions/199903/msg00013.html
/Uffe
--
Ulf Wiger tfn: +46 8 719 81 95
Strategic Product & System Management mob: +46 70 519 81 95
Ericsson Telecom AB, Datacom Networks and IP Services
Varuv |
|
|
| Back to top |
|
| richardc at it.uu.se |
| Posted: Mon Oct 16, 2000 10:56 am |
|
|
|
Guest
|
On Mon, 16 Oct 2000, Ulf Wiger wrote:
> We (a few lunatics at AXD 301) would like to see the lists module
> support an alternative formulation of lists.
>
> A list could be expressed in the following manner:
>
> [Head | fun(Head, F)]
>
> [...]
>
> What'ya think? Awful? Elegant?
>
>
> BTW, Joe already posted something like this on the erlang-questions
> list in March '99, but he was using zero-argument funs.
>
> http://www.erlang.org/ml-archive/erlang-questions/199903/msg00013.html
They are indeed elegant, and Joe was correct - they're called lazy lists,
and should be implemented using zero-argument funs. To give a type
declaration of sorts:
LazyList :: [] | [term() | fun() -> LazyList]
Writing a module 'lazy_lists' should be a doddle. In fact, I might do it
myself.
/Richard Carlsson
Richard Carlsson (richardc_at_csd.uu.se) (This space intentionally left blank.)
E-mail: Richard.Carlsson_at_csd.uu.se WWW: http://www.csd.uu.se/~richardc/
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| tobbe at bluetail.com |
| Posted: Mon Oct 16, 2000 11:05 am |
|
|
|
Guest
|
Talking of lazy lists, Phil Waldler once
helped me writing the following stuff.
Cheers /Tobbe
-module(ns).
-author('tnt_at_home.se').
-compile(export_all).
-define( return(X) , fun() -> X end ).
-define( force(X) , begin XXXfunnyvar=X, XXXfunnyvar() end ).
-define( vforce(V,X) , begin V=X, V() end ).
-define( bind(X,D,K) , fun() -> X=?vforce(XXXfunnyvar1,D), ?vforce(XXXfunnyvar2,K) end ).
-define( cons(H,T) , ?return({cons,H,T}) ).
-define( nil(), ?return(nil) ).
%% A lazy first...
first(0,_) -> ?nil();
first(N,S) when N>0 ->
?bind(S1,S,
case S1 of
nil ->
?nil();
{cons,H,T} ->
?cons(H,first(N-1,T))
end).
%% 24> statistics(reductions),ns:first(7,ns:primes()),statistics(reductions).
%% {1705891,61}
%% 25> statistics(reductions),ns:stream_to_list(ns:first(7,ns:primes())),statistics(reductions).
%% {1708314,616}
%% 6> statistics(reductions),streams:first(7,streams:primes()),statistics(reductions).
%% {1712785,576}
nth(0,S) ->
case ?force(S) of
{cons,H,T} -> H
end;
nth(N,S) when N>0 ->
case ?force(S) of
{cons,_,T} -> nth(N-1,T)
end.
map(F,S) ->
?bind(S1,S,
case S1 of
nil ->
?nil();
{cons,H,T} ->
?cons(F(H),map(F,T))
end).
scale(C,S) ->
map(fun(X) -> X*C end,S).
double(S) -> scale(2,S).
%% Example:
%%
%% 15> ns:stream_to_list(ns:first(8,ns:append(ns:first(5,ns:naturals()),ns:first(5,ns:naturals())))).
%% [0,1,2,3,4,0,1,2]
%% 77> statistics(reductions),ns:stream_to_list(ns:first(8,ns:append(ns:naturals(),ns:naturals()))),statistics(reductions).
%% {1909897,270}
%% 78> statistics(reductions),ns:lf(8,lists:append(lists:seq(1,500),lists:seq(1,500))),statistics(reductions).
%% {1919732,1157}
append(S,R) ->
?bind(S1,S,
case S1 of
nil -> R;
{cons,H,T} -> ?cons(H,append(T,R))
end).
naturals() ->
integers_starting_from(0).
integers_starting_from(N) ->
?cons(N,integers_starting_from(N+1)).
primes() -> sieve(integers_starting_from(2)).
sieve(S) ->
?bind(S1,S,
(case S1 of
nil ->
?nil();
{cons,H,T} ->
Pred = fun(X) -> 'not'(divisible(X,H)) end,
?cons(H,sieve(filter(Pred,T)))
end)).
filter(Pred,S) ->
?bind(S1,S,
case S1 of
nil ->
?nil();
{cons,H,T} ->
case Pred(H) of
true ->
?cons(H,filter(Pred,T));
false ->
filter(Pred,T)
end
end).
divisible(X,Y) ->
if
X rem Y == 0 -> true;
true -> false
end.
'not'(true) -> false;
'not'(false) -> true.
gcd(A,0) -> A;
gcd(A,B) -> gcd(B,A rem B).
%% Try this:
%% 22> ns:stream_to_list(ns:first(10,ns:map(fun(X)-> round(X) end,ns:scale(100,ns:random_numbers(random:seed()))))).
%% [9,44,72,95,50,31,60,92,67,48]
random_numbers(Seed) ->
?cons(random:uniform(),random_numbers(Seed)).
cesaro_stream() ->
F = fun(R1,R2) -> case gcd(R1,R2) of 1 -> true; _ -> false end end,
map_successive_pairs(F,map(fun(X)-> round(X) end,scale(100,random_numbers(random:seed())))).
map_successive_pairs(F,S) ->
?bind(S1,S,
case S1 of
{cons,H,T} ->
case ?force(T) of
{cons,H2,T2} ->
?cons(F(H,H2),
map_successive_pairs(F,T2))
end
end).
monte_carlo(S,Nt,Nf) ->
?bind(S1,S,
(case S1 of
{cons,H,T} ->
Next = fun(Nnt,Nnf) ->
Q = Nnt+Nnf,
?cons(Nnt/Q,monte_carlo(T,Nnt,Nnf))
end,
case H of
true -> Next(Nt+1,Nf);
false -> Next(Nt,Nf+1)
end
end)).
%% An approximation of pi.
%% We will use the fact that the probability that
%% two integers choosen at random will have no factors
%% in common (i.e their GCD is 1) is 6/pi**2. The
%% fraction of times the test is passed gives us an
%% estimate of this probability. So the further you
%% look into the stream, the better approximation you'll get.
pi() ->
map(fun(P) -> math:sqrt(6/P) end,
monte_carlo(cesaro_stream(),0,0)).
%% Converting routines: streams <--> lists
stream_to_list(S) ->
case ?force(S) of
{cons,H,T} ->
[H|stream_to_list(T)];
nil ->
[]
end.
list_to_stream([H|T]) -> ?cons(H,list_to_stream(T));
list_to_stream([]) -> ?nil().
%% Misc. routines
rv(File,NewFile) when list(File) ->
M = erl_kernel:file(File),
{ok,T,_} = erl_kernel:module(M),
{ok,F} = file:open(NewFile,write),
erl_kernel:pp(T,F),
file:close(F).
lf(0,_) -> [];
lf(N,[H|T]) -> [H|lf(N-1,T)].
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| thomas at cslab.ericsson. |
| Posted: Mon Oct 16, 2000 11:09 am |
|
|
|
Guest
|
Ulf Wiger wrote:
>
> Here's a thought:
>
> We (a few lunatics at AXD 301) would like to see the lists module
> support an alternative formulation of lists.
>
> A list could be expressed in the following manner:
>
> [Head | fun(Head, F)]
I don't really like that notation, since the tail of a list is
no longer a list now (but a function returning a list). I find
it more natural to return a tuple, a kind of continuation.
Basically you try to introduce lazy evaluation in an eager
language. I think this is indeed sometimes needed (I wrote
a lazy version of "all subsets of a set" recently). When
dealing with the create and filter paradigm, one basically
wants to generate a list and drop all items that do not
respect a certain filter function. That's the same here,
except that instead of just removing it from the list,
you add a side-effect.
It would be nice if this could be established by a smart,
lazy list-comprehension:
[ X || X<-seq(1,5), condition(X) ]
where condition(X) is
condition(X) ->
io:format("-- ~p~n", [X]),
false.
The result would be the empty list, but (as far as I recall
the Erlang semantics) the list seq(1,5) is generated before
the tests on the arguments is performed. It would be nice to have
a lazy list-comprehension as well. An element is computed, the
filter is applied and so on. Syntax could be basically the same, as
long as no side-conditions are allowed in the generators, I
think the execution of the strict and the eager variant should be
the same.
Solving it this way, would keep your code more readable ;0).
Implementation in the compiler seems not so hard to me, but let
a compiler writer comment on that.
With respect to your solution, why not using the tuple construct:
implicitely defining the continuation type:
+deftype continuation(T) = {} | {T, fun(T,continuation(T)) -> continuation(T)}.
+type seq(int(),int()) -> continuation(int()).
seq(Start, Stop) when Start < Stop ->
{Start , fun(N, F) when N == Stop ->
{};
(N, F) ->
{N+1 , F}
end].
+type foreach(fun(A) -> B, continuation(A)) -> void().
foreach(F, {}) ->
void;
foreach(F, {H,C}) ->
F(H),
foreach(F, C(H, C)).
Sure, overloading of foreach needs the two lines
> foreach(F, []) ->
> [];
> foreach(F, [H|T]) ->
> F(H),
> foreach(F, T);
as well, because of Erlang's structure.
Implementing it within Erlang in this way has the disadvantage
that you need to program quite a lot, which is not the case if
it would have been given as a language primitive.
/Thomas
>
>
> Example:
>
> -module(alglists).
> -author('etxuwig_at_etxb.ericsson.se').
>
> -export([seq/2, foreach/2]).
>
> %%-export([Function/Arity, ...]).
>
> seq(Start, Stop) when Start < Stop ->
> [Start | fun(N, F) when N == Stop ->
> [];
> (N, F) ->
> [N+1 | F]
> end].
>
> foreach(F, []) ->
> [];
> foreach(F, [H|T]) when list(T) ->
> F(H),
> foreach(F, T);
> foreach(F, [H|T]) when function(T) ->
> F(H),
> foreach(F, T(H, T)).
>
> Eshell V4.8.2.7 (abort with ^G)
>
> 1> lists:foreach(fun(X) -> io:format("-- ~p~n", [X]) end,
> lists:seq(1,5)). -- 1
> -- 2
> -- 3
> -- 4
> -- 5
> ok
> 2> c(alglists).
> {ok,alglists}
> 3> alglists:foreach(fun(X) -> io:format("-- ~p~n", [X]) end,
> alglists:seq(1,5)).
> -- 1
> -- 2
> -- 3
> -- 4
> -- 5
> ok
>
> (Perhaps to avoid breaking half the Erlang programs in the universe,
> functions in lists should not return lists on this form, but should be
> able to process them.)
>
> Let me briefly tell you why we'd like to do this:
>
> On several occasions, we've rewritten code that generates a large
> list on the heap and then traverses it. It's a shame from one
> perspective, because the new code (which usually uses ets:next/2) is
> not FP-style, and less elegant -- but it is more well behaved from a
> memory management perspective, which is its one (but vital) merit.
> We'd like to keep the concept of list processing, but avoid the large
> lists, which cause havoc in the GC.
>
> What'ya think? Awful? Elegant?
>
> BTW, Joe already posted something like this on the erlang-questions
> list in March '99, but he was using zero-argument funs.
>
> http://www.erlang.org/ml-archive/erlang-questions/199903/msg00013.html
>
> /Uffe
> --
> Ulf Wiger tfn: +46 8 719 81 95
> Strategic Product & System Management mob: +46 70 519 81 95
> Ericsson Telecom AB, Datacom Networks and IP Services
> Varuv |
|
|
| Back to top |
|
| simonb at terminus.ericss |
| Posted: Mon Oct 16, 2000 11:17 am |
|
|
|
Guest
|
Is this what is known as lazy evaluation in functional programming
terms?
i.e. it allows you to define a possibly infinite list, and the values in
the list are only evaluated and returned as and when they are required?
If this is the case, it brings Erlang closer to the idea of an
executable specification (which people were discussing in the context of
"Who is a Programmer?") as you can define a set by intension rather than
by extension.
Simon Bennett
___________________________________________________________________
Simon Bennett E-mail: simonb_at_terminus.ericsson.se
Ericsson Intracom http://www.ericsson.co.uk/UK/intracom
1 Bede Island Road Voice (UK) 0116 2542400
Leicester Voice (int) +44 116 2542400
England Voice ECN: 832 707 ext 232
LE2 7EU Fax: +44 (0)116 2046111
___________________________________________________________________
Ulf Wiger wrote:
>
> Here's a thought:
>
> We (a few lunatics at AXD 301) would like to see the lists module
> support an alternative formulation of lists.
>
> A list could be expressed in the following manner:
>
> [Head | fun(Head, F)]
>
> Example:
>
> -module(alglists).
> -author('etxuwig_at_etxb.ericsson.se').
>
> -export([seq/2, foreach/2]).
>
> %%-export([Function/Arity, ...]).
>
> seq(Start, Stop) when Start < Stop ->
> [Start | fun(N, F) when N == Stop ->
> [];
> (N, F) ->
> [N+1 | F]
> end].
>
> foreach(F, []) ->
> [];
> foreach(F, [H|T]) when list(T) ->
> F(H),
> foreach(F, T);
> foreach(F, [H|T]) when function(T) ->
> F(H),
> foreach(F, T(H, T)).
>
> Eshell V4.8.2.7 (abort with ^G)
>
> 1> lists:foreach(fun(X) -> io:format("-- ~p~n", [X]) end,
> lists:seq(1,5)). -- 1
> -- 2
> -- 3
> -- 4
> -- 5
> ok
> 2> c(alglists).
> {ok,alglists}
> 3> alglists:foreach(fun(X) -> io:format("-- ~p~n", [X]) end,
> alglists:seq(1,5)).
> -- 1
> -- 2
> -- 3
> -- 4
> -- 5
> ok
>
> (Perhaps to avoid breaking half the Erlang programs in the universe,
> functions in lists should not return lists on this form, but should be
> able to process them.)
>
> Let me briefly tell you why we'd like to do this:
>
> On several occasions, we've rewritten code that generates a large
> list on the heap and then traverses it. It's a shame from one
> perspective, because the new code (which usually uses ets:next/2) is
> not FP-style, and less elegant -- but it is more well behaved from a
> memory management perspective, which is its one (but vital) merit.
> We'd like to keep the concept of list processing, but avoid the large
> lists, which cause havoc in the GC.
>
> What'ya think? Awful? Elegant?
>
> BTW, Joe already posted something like this on the erlang-questions
> list in March '99, but he was using zero-argument funs.
>
> http://www.erlang.org/ml-archive/erlang-questions/199903/msg00013.html
>
> /Uffe
> --
> Ulf Wiger tfn: +46 8 719 81 95
> Strategic Product & System Management mob: +46 70 519 81 95
> Ericsson Telecom AB, Datacom Networks and IP Services
> Varuv |
|
|
| Back to top |
|
| richardc at it.uu.se |
| Posted: Mon Oct 16, 2000 11:32 am |
|
|
|
Guest
|
On Mon, 16 Oct 2000, Thomas Arts wrote:
> Ulf Wiger wrote:
> >
> > A list could be expressed in the following manner:
> >
> > [Head | fun(Head, F)]
>
> I don't really like that notation, since the tail of a list is no
> longer a list now (but a function returning a list). I find it more
> natural to return a tuple, a kind of continuation.
Yes, however, the cons cells are much more efficient in terms of memory
allocation (in current Erlang implementations), only needing 2 words where
a tuple needs three. I don't find it unreasonable to use cons cells for
certain datatype representations, when they map so naturally to "cons or
nil" as in this case. "cons cell" does not always have to imply "proper
list", although for general purpose programming cons cells should not be
used.
> It would be nice if this could be established by a smart,
> lazy list-comprehension:
>
> [ X || X<-seq(1,5), condition(X) ]
I agree that it would be quite nice for Erlang to have language support
for lazy list comprehensions. As I recall, when list comprehensions were
first about to be introduced in Erlang, there was some debate about
whether they should have lazy semantics or not. However, I think that it
was correct that normal list comprehensions in Erlang should have strict
semantics.
It should probably not be a problem to implement a lazy version also.
/Richard Carlsson
Richard Carlsson (richardc_at_csd.uu.se) (This space intentionally left blank.)
E-mail: Richard.Carlsson_at_csd.uu.se WWW: http://www.csd.uu.se/~richardc/
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| thomas at cslab.ericsson. |
| Posted: Mon Oct 16, 2000 11:44 am |
|
|
|
Guest
|
Richard Carlsson wrote:
>
> On Mon, 16 Oct 2000, Thomas Arts wrote:
>
> > Ulf Wiger wrote:
> > >
> > > A list could be expressed in the following manner:
> > >
> > > [Head | fun(Head, F)]
> >
> > I don't really like that notation, since the tail of a list is no
> > longer a list now (but a function returning a list). I find it more
> > natural to return a tuple, a kind of continuation.
>
> Yes, however, the cons cells are much more efficient in terms of memory
> allocation (in current Erlang implementations), only needing 2 words where
> a tuple needs three. I don't find it unreasonable to use cons cells for
> certain datatype representations, when they map so naturally to "cons or
> nil" as in this case. "cons cell" does not always have to imply "proper
> list", although for general purpose programming cons cells should not be
> used.
I am horrified by the idea to find the AXD 301 software full with
cons cells, just in order to save those few bytes. In particular since
in these lazy lists, the elements have a very short lifetime (Ulf wants
to generate a side-effect and throw the value away), it would only
save you one word. If efficiency turns outto be so much an issue, than
adding a new type to Erlang (similar to cons, but with different notiation,
would be preferable).
/Thomas
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| etxuwig at etxb.ericsson. |
| Posted: Mon Oct 16, 2000 12:20 pm |
|
|
|
Guest
|
We (Kurt Jonsson and I) also discussed using tuples. It has the
disadvantage for us that it involves more changes to existing code
(which is naturally using the list "cons syntax" today.)
/Uffe
On Mon, 16 Oct 2000, Thomas Arts wrote:
>I am horrified by the idea to find the AXD 301 software full with
>cons cells, just in order to save those few bytes. In particular since
>in these lazy lists, the elements have a very short lifetime (Ulf wants
>to generate a side-effect and throw the value away), it would only
>save you one word. If efficiency turns outto be so much an issue, than
>adding a new type to Erlang (similar to cons, but with different notiation,
>would be preferable).
--
Ulf Wiger tfn: +46 8 719 81 95
Strategic Product & System Management mob: +46 70 519 81 95
Ericsson Telecom AB, Datacom Networks and IP Services
Varuv |
|
|
| Back to top |
|
| bjorn at erix.ericsson.se |
| Posted: Mon Oct 16, 2000 12:39 pm |
|
|
|
Guest
|
Thomas Arts <thomas_at_cslab.ericsson.se> writes:
> I am horrified by the idea to find the AXD 301 software full with
> cons cells, just in order to save those few bytes. In particular since
> in these lazy lists, the elements have a very short lifetime (Ulf wants
> to generate a side-effect and throw the value away), it would only
> save you one word. If efficiency turns outto be so much an issue, than
> adding a new type to Erlang (similar to cons, but with different notiation,
> would be preferable).
We don't have any free tags to add a new cons-like type. A new type would
need a header word indicating the type and size, and would therefore not
be smaller than a tuple.
We already use non-normalised lists in Erlang and OTP. The list_to_binary/1
BIF and ports accept binaries in list tails.
>
>
> /Thomas
>
/Bj |
|
|
| Back to top |
|
| aba3600 at omega.uta.edu |
| Posted: Mon Oct 16, 2000 7:44 pm |
|
|
|
Guest
|
Tell me if I'm wrong, but lazxy evaluation would screw up Real Time,
right?
Andy
Recycled Electrons
> > We (a few lunatics at AXD 301) would like to see the lists module
> > support an alternative formulation of lists.
>
> They are indeed elegant, and Joe was correct - they're called lazy lists,
> and should be implemented using zero-argument funs. To give a type
> declaration of sorts:
>
> LazyList :: [] | [term() | fun() -> LazyList]
>
> Writing a module 'lazy_lists' should be a doddle. In fact, I might do it
> myself.
>
> /Richard Carlsson
>
>
> Richard Carlsson (richardc_at_csd.uu.se) (This space intentionally left blank.)
> E-mail: Richard.Carlsson_at_csd.uu.se WWW: http://www.csd.uu.se/~richardc/
>
>
Sincerely,
Andy Allen
Recycled Electrons
email: andy_at_recycledelectrons.com
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| aba3600 at omega.uta.edu |
| Posted: Mon Oct 16, 2000 9:19 pm |
|
|
|
Guest
|
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.
Also, is there a way to overload operators (not function calls) in Erlang?
I'd love to overload "+" or "-" for a specific kind of input, so that a
call is made to my function. The data units I am passing in are 3-element
tuples right now, but I can change that.
I.E., In the second half of this eMail I am searching for a way to define
my own data type in Erlang and overload existing operators based on it.
Does anyone have an example?
Andy
Recycled Electrons
On Mon, 16 Oct 2000, Andy with Recycled Electrons wrote:
> Date: Mon, 16 Oct 2000 14:43:57 -0500 (CDT)
> From: Andy with Recycled Electrons <aba3600_at_omega.uta.edu>
> To: erlang-questions_at_erlang.org
> Subject: Re: Algorithmic lists
>
> Tell me if I'm wrong, but lazxy evaluation would screw up Real Time,
> right?
>
> Andy
> Recycled Electrons
>
> > > We (a few lunatics at AXD 301) would like to see the lists module
> > > support an alternative formulation of lists.
> >
> > They are indeed elegant, and Joe was correct - they're called lazy lists,
> > and should be implemented using zero-argument funs. To give a type
> > declaration of sorts:
> >
> > LazyList :: [] | [term() | fun() -> LazyList]
> >
> > Writing a module 'lazy_lists' should be a doddle. In fact, I might do it
> > myself.
> >
> > /Richard Carlsson
> >
> >
> > Richard Carlsson (richardc_at_csd.uu.se) (This space intentionally left blank.)
> > E-mail: Richard.Carlsson_at_csd.uu.se WWW: http://www.csd.uu.se/~richardc/
> >
> >
>
> Sincerely,
>
> Andy Allen
> Recycled Electrons
> email: andy_at_recycledelectrons.com
>
>
>
Sincerely,
Andy Allen
Recycled Electrons
email: andy_at_recycledelectrons.com
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| etxuwig at etxb.ericsson. |
| Posted: Tue Oct 17, 2000 6:56 am |
|
|
|
Guest
|
Here's my first (and perhaps last) hack of sys_pre_expand.erl.
It handles at least my very simple test function with a list
comprehension that is fed a lazy list:
=========================
-module(alglists).
-author('etxuwig_at_etxb.ericsson.se').
-export([seq/2, foreach/2, foo/0]).
seq(Start, Stop) when Start =< Stop ->
[Start | fun() ->
seq(Start+1, Stop)
end];
seq(Start, Stop) ->
[].
foreach(F, []) ->
ok;
foreach(F, [H|T]) when list(T) ->
F(H),
foreach(F, T);
foreach(F, [H|T]) when function(T) ->
F(H),
foreach(F, T(H, T)).
foo() ->
[X || X <- seq(1,5),
X > 3].
=========================
Eshell V5.0.1 (abort with ^G)
1> c(alglists).
{ok,alglists}
2> alglists:seq(1,5).
[1|#Fun<alglists.0.8325658>]
3> alglists:foo().
[4,5]
Unfortunately, it doesn't address LCs in the shell (that's done in
erl_eval.erl).
There is at least one really ugly hack in there:
etxuwig_at_avc303 > diff
.../otp_src_R7A-0/lib/compiler/src/sys_pre_expand.erl
sys_pre_expand.erl
443c443,447
< {Lc,St3} = lc_tq(Line, E, Qs, NewMore, St2),
---
> NewMoreFun = {call,Lg,Fun,[{call,Lg,Tail,[]},Fun]},
> IsList = [{call,Lg,{atom,Lg,list},[Tail]}],
> IsFun = [{call,Lg,{atom,Lg,function},[Tail]}],
> {LcL,_} = lc_tq(Line, E, Qs, NewMore, St2),
> {LcF,St3} = lc_tq(Line, E, Qs, NewMoreFun, St2),
447,448c451,456
< {clauses,[{clause,Lg,[{cons,Lg,P,Tail},Fun],[],[Lc]},
<
{clause,Lg,[{cons,Lg,{var,Lg,'_'},Tail},Fun],[],[NewMore]},
---
> {clauses,[{clause,Lg,[{cons,Lg,P,Tail},Fun],[IsList],[LcL]},
> {clause,Lg,[{cons,Lg,P,Tail},Fun],[IsFun],[LcF]},
> {clause,Lg,[{cons,Lg,{var,Lg,'_'},Tail},Fun],
> [IsList],[NewMore]},
> {clause,Lg,[{cons,Lg,{var,Lg,'_'},Tail},Fun],
> [IsFun],[NewMoreFun]},
On 16 Oct 2000, Bjorn Gustavsson wrote:
>We don't have any free tags to add a new cons-like type. A new type
>would need a header word indicating the type and size, and would
>therefore not be smaller than a tuple.
>
>We already use non-normalised lists in Erlang and OTP. The
>list_to_binary/1 BIF and ports accept binaries in list tails.
Personally, I think it's more intuitive to stay close to the list
syntax. After all, we are looking to extend the list semantics.
/Uffe
--
Ulf Wiger tfn: +46 8 719 81 95
Strategic Product & System Management mob: +46 70 519 81 95
Ericsson Telecom AB, Datacom Networks and IP Services
Varuv |
|
|
| Back to top |
|
| etxuwig at etxb.ericsson. |
| Posted: Tue Oct 17, 2000 6:58 am |
|
|
|
Guest
|
On Mon, 16 Oct 2000, Andy with Recycled Electrons wrote:
>Tell me if I'm wrong, but lazxy evaluation would screw up Real Time,
>right?
>
>Andy
>Recycled Electrons
Well, not any more than would the otherwise mandatory rewrite into an
ets:first()/ets:next() loop. The real-time behaviour will be the
same, but the amount of changes needed to the code will be less with a
lazy list syntax.
In a system like the AXD 301, it is taken for granted that programmers
must know what they are doing at all times (or at least most of the
time). Another example of something that can screw up real time
behaviuor is distributed message passing; it's a vital part of our
system, but its use must be tightly controlled.
Obviously, with lazy lists, it's quite easy to create an infinite
loop, but not much more so than with the first program Erlang we
teach:
factorial(N) ->
N * factorial(N-1);
factorial(0) ->
1.
(yes, I know this function can loop endlessly.)
/Uffe
>> > We (a few lunatics at AXD 301) would like to see the lists module
>> > support an alternative formulation of lists.
>>
>> They are indeed elegant, and Joe was correct - they're called lazy lists,
>> and should be implemented using zero-argument funs. To give a type
>> declaration of sorts:
>>
>> LazyList :: [] | [term() | fun() -> LazyList]
>>
>> Writing a module 'lazy_lists' should be a doddle. In fact, I might do it
>> myself.
>>
>> /Richard Carlsson
>>
>>
>> Richard Carlsson (richardc_at_csd.uu.se) (This space intentionally left blank.)
>> E-mail: Richard.Carlsson_at_csd.uu.se WWW: http://www.csd.uu.se/~richardc/
>>
>>
>
>Sincerely,
>
>Andy Allen
>Recycled Electrons
>email: andy_at_recycledelectrons.com
>
>
>
--
Ulf Wiger tfn: +46 8 719 81 95
Strategic Product & System Management mob: +46 70 519 81 95
Ericsson Telecom AB, Datacom Networks and IP Services
Varuv |
|
|
| Back to top |
|
| richardc at it.uu.se |
| Posted: Tue Oct 17, 2000 9:54 am |
|
|
|
Guest
|
On Mon, 16 Oct 2000, Andy with Recycled Electrons wrote:
> 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.
Programming with lazy evaluation as the general rule (as in Haskell) does
indeed make it difficult for the programmer (unless he happens to be John
Hughes) to get an intuitive grasp of how time-consuming a particular
computation will be. It does not have to involve disk or network access to
be so: one can fairly easily happen to create a function that seems
straightforward but actually has exponential space complexity, and if you
are not one of the cognoscenti, the ways of rewriting it so it behaves
nicer may simply appear like waving so many dead chickens.
That said, one can do a lot of neat things with lazy evaluation (even if
you simulate it in a strict language like Erlang), and a library for
working with lazy lists could be a nice thing to have, since it seems more
likely that someone who uses that library does more or less know what he
is doing, and why.
> Also, is there a way to overload operators (not function calls) in
> Erlang? I'd love to overload "+" or "-" for a specific kind of input,
> so that a call is made to my function. The data units I am passing in
> are 3-element tuples right now, but I can change that.
No, there isn't. (Or rather, yes, there is, it's called "parse
transforms", and you should really not be doing it.) My advice: implement
a nice abstract datatype with functions "add(X, Y)", "subtract(X, Y)",
etc., or if you really feel you want `+' and `-', you can actually call
your functions "'+'(X, Y)" and "'-'(X, Y)" as long as you use
single-quoting.
/Richard Carlsson
Richard Carlsson (richardc_at_csd.uu.se) (This space intentionally left blank.)
E-mail: Richard.Carlsson_at_csd.uu.se WWW: http://www.csd.uu.se/~richardc/
Post generated using Mail2Forum (http://m2f.sourceforge.net) |
|
|
| Back to top |
|
| rv at bluetail.com |
| Posted: Tue Oct 17, 2000 10:03 am |
|
|
|
Guest
|
Andy with Recycled Electrons <aba3600_at_omega.uta.edu> 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: rv_at_bluetail.com
S:t Eriksgatan 44 WWW: http://www.bluetail.com/~rv
SE-112 34 Stockholm, SWEDEN
"Folk s |
|
|
| Back to top |
|
|
|
All times are GMT
Page 1 of 2
Goto page 1, 2 Next
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
