[Haskell] Fwd: Mutually dependent functions

Ryan Ingram ryani.spam at gmail.com
Mon Jun 11 17:54:35 EDT 2007


I doubt this is a problem with the compiler as you state;

It's not immediately obvious by looking at your code what the problem is;
the code is really dense and it's not immediately obvious what you are
trying to accomplish.  I suspect that either you have a bug, or you are
pattern-matching against something you are depending on, which will force it
to evaluate to weak-head normal form so that it can be matched against.

Take a look at the section titled "Lazy Patterns" for an example of how to
solve that problem:
http://www.cs.auckland.ac.nz/references/haskell/haskell-intro-html/patterns.html

I don't understand what you are saying about "promises pushed onto the
stack".  A boxed value can either be a thunk (unevaluated promise) or the
evaluated result of that thunk.  Calls to functions just push pointers to
the boxes onto the stack.  When the result is needed the thunk gets
evaluated; if it somehow ends up depending on itself the thunk will get
called recursively which will eventually end up in a stack overflow.

  -- ryan

On 6/11/07, Michael Speer <knomenet at gmail.com> wrote:

> 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
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell/attachments/20070611/28897e92/attachment.htm


More information about the Haskell mailing list