[Haskell] Fwd: Mutually dependent functions

Michael Speer knomenet at gmail.com
Mon Jun 11 16:09:22 EDT 2007


The code I reference is located at :

http://michaelspeer.blogspot.com/2007/06/impossible-is-only-possible-sometimes.html

In the code I am building a parser for regular expressions.  I know it
is possible with ghc to have a function that accepts its own output as
its input so long as it does not utilize that piece of output in
generating itself.

E.g.
test x y = ( "World" , x , x ++ " " ++ y )
main = let ( a , b , c ) = test "Hello" a
       in do
           print $ ( a , b , c )

-- emits ("World","Hello","Hello World")

This contrived example works properly.  A more complex example can be
found in the linked-to function `aexn' ( and-extracted-nodes ).

It seems though, if you try this same trick with two different
functions that rely on each others input and output, that the compiler
will generate code, but the generated program causes the stack to
overflow as each function tries to force the other one to evaluate
first and neither bows out releasing an output of promises so that the
two functions can resolve.  They seem to encounter a lack of laziness.
 Well, more a duplication of effort.  I specifically refer to the
linked function `oexn' ( or-extracted-function-nodes ) that performs
this feat.  Or would if the program worked after being compiled.

If the compiler were forced to only make the function call once and
mark all variables generated by it immediately with either proper
values or promises than the second functions call would receive the
promises in place of the empty variables it feels the need to call the
original function to fill.

Are the promises added to the stack before or after the call?  If
after, then putting them on before may resolve this.  It would likely
make the implementation slower to do so however.

Is this a known problem that will one day be resolved, or is it
considered beyond the scope of the language?

As I only use ghc, I am unfamiliar if one of the other implementations
could handle this.  I have seen nothing referring to it though out my
searches regarding the matter.

- michael speer


More information about the Haskell mailing list