Do we need a letrec construct?

Karlsson Mikael qramika@REDACTED
Tue Oct 31 13:13:04 CET 2000


I am not sure I understand the problem, but if you wan't
to change the behaviour of the way of making terms, is it
not possible to do something like:

mk_stream_from_file(Filename) ->
    {ok, File} = file:open(Filename),
    stream(File,fun mk_term_from_file/1,first).

stream(File,F,State) -> 
    fun() ->
        case F(File) of
            {ok, Term} ->
                case State of 
                    first ->
                        [Term | stream(File, 
                                fun mk_other_term_from_file/1,second)]; 
                    second ->
                        [Term | stream(File, 
                                fun mk_term_from_file/1,first)]
                end;
            eof ->
                []
        end
    end.


? / Mikael

> X-Authentication-Warning: harpo.it.uu.se: richardc owned process doing -bs
> Date: Tue, 31 Oct 2000 12:46:59 +0100 (MET)
> From: Richard Carlsson <richardc@REDACTED>
> X-Sender: richardc@REDACTED
> To: raimo.niskanen@REDACTED
> cc: erlang-questions@REDACTED
> Subject: Re: Do we need a letrec construct?
> MIME-Version: 1.0
> 
> 
> On Tue, 31 Oct 2000, Raimo Niskanen wrote:
> 
> > I recently ran into a problem where it would have been nice to have
> > something like the Lisp letrec construct in Erlang.
> >
> > [...] I started out something like this: 
> > 
> > mk_stream_from_file(Filename) ->
> >     {ok, File} = file:open(Filename),
> >     Stream = 
> >         fun() ->
> >             case mk_term_from_file(File) of
> >                 {ok, Term} ->
> >                     [Term | Stream]; % Stream not bound
> >                 eof ->
> >                     []
> >             end
> >         end
> >     end.
> > 
> > This does unfortunately not work since the variable Stream is not
> > bound while defining the fun, instead I had to write like this:
> > [...three functions...]
> > This I find less clear, it pollutes the module namespace and it
> > creates more funs in runtime, which is not for free. However, it
> > works!
> >
> > The problem is to write funs that are recursive, without passing the
> > fun as an argument to itself, and in the general case several funs
> > might need to call each other.
> 
> Yes, you could write it like this - but it doesn't really scale to several
> mutually recursive functions (and is not so easy to read):
> 
> mk_stream_from_file(Filename) ->
>     {ok, File} = file:open(Filename),
>     MkStream = 
>         fun (F) ->
>           fun() ->
>               case mk_term_from_file(File) of
>                   {ok, Term} ->
>                       [Term | F(F)]; % Stream not bound
>                   eof ->
>                       []
>               end
>           end
>         end,
>     MkStream(MkStream).
> 
> 
> > Suggestions
> > ===========
> > 
> > Here are two suggestions for extensions to Erlang. In this example I
> > alternate between two different mk_term_from_file/1 functions:
> > 
> > Suggestion 1, Lisp letrec style:
> > 
> > mk_stream_from_file(Filename) ->
> >     {ok, File} = file:open(Filename),
> >     letrec
> >         Stream = 
> >             fun() ->
> >                 case mk_term_from_file(File) of
> >                     {ok, Term} ->
> >                         [Term | Stream2]; % Stream2 is actually bound!
> >                     eof ->
> >                         []
> >                 end
> >             end,
> >         Stream2 = 
> >             fun() ->
> >                 case mk_other_term_from_file(File) of
> >                     {ok, Term} ->
> >                         [Term | Stream1];
> >                     eof ->
> >                         []
> >                 end
> >             end,
> >     end,
> >     Stream.
> > 
> > One problem with this syntax is that Stream2 (and of course Stream) is
> > actually bound in a source line (maybe far) above the line where it
> > appears.
> 
> Well, that can of course be the case also when you write mutually
> recursive top-level functions.
> 
> A more important problem is that if you allow any sort of definitions in a
> "letrec", you could actually define cyclic data structures:
> 
> 	infinite(X, Y) ->
> 	    letrec
> 	        A = {foo, X, B};
> 	        B = {bar, Y, A}
> 	    end,
> 	    A.
> 
> The result of "infinite(1, 2)" would then represent {foo, 1, {bar, 2,
> {foo, 1, {bar, 2, ...}}}}. This is something you don't want in the
> language for practical reasons.
> 
> The solution is simply to allow only function definitions in a letrec.
> 
> > I also think that 'letrec' is a lousy out-of-context choice of
> > keyword, there must be a better alternative (but i have not given it
> > much thought yet).
> 
> Well, following the reasoning above, it would be a construct for defining
> local, possibly recursive functions. A more suitable keyword could be
> "define", or maybe "local".
> 
> One thing, though: it should be an Erlang expression, and thus should have
> a value. If we allow the definitions to simply be exported from the
> construct, as with a "case" (and as in your example), it is not obvious
> what the value should be (I don't think it should be a constant). A better
> form would be something like
> 
> 	define
> 	    f1(X1, X2) -> <exprs> ;
> 	  ...
> 	    fN(X1, X2, X3, X4) -> <exprs> ;
> 	in
> 	    <exprs>
> 	end
> 
> where the functions are not visible outside "in ... end". However, this
> would be a bit at odds with the normal name-binding mechanisms of Erlang,
> and I'm not sure what would be the best solution.
> 
> Once upon a time, it was actually suggested that a non-recursive "let ...
> in ..." thing be added to Erlang, but this was turned down because of the
> strange effects caused by joining two different worlds of scoping rules.
> 
> I think a variant of letrec could be useful in many cases where one wants
> local functions, not cluttering the module-level namespace, even if the
> problem does not involve tricky recursion like in your example (and it is
> not difficult to handle letrec in the compiler, as long as only function
> definitions are allowed).
> 
> > Suggestion 2, new ':= 'assignment operator style:
> 
> Same thing, just more difficult to see what is a legal definition and what
> is not. And a lot more difficult to read.
> 
> 	/Richard Carlsson
> 
> 
> 
> Richard Carlsson (richardc@REDACTED)   (This space intentionally left blank.)
> E-mail: Richard.Carlsson@REDACTED	WWW: http://www.csd.uu.se/~richardc/
> 
> 
> 




More information about the erlang-questions mailing list