Do we need a letrec construct?

[Richard Carlsson]

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/