Fwd: Mutually dependent functions
The code I reference is located at : http://michaelspeer.blogspot.com/2007/06/impossible-is-only-possible-sometim... 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
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.... 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@gmail.com> wrote:
The code I reference is located at :
http://michaelspeer.blogspot.com/2007/06/impossible-is-only-possible-sometim...
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Hi Michael, Michael Speer schrieb:
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. [...]
It seems though, if you try this same trick with two different functions that rely on each others input and output, that [...] 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. [...] 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.
This has nothing to do with how many functions you have working with some input. The evaluation order of haskell expressions is induced by the data dependencies between haskell expressions. This work's fine as long as the data dependencies aren't circular. For example numbers = 1 : map (1 +) numbers works fine because the value of the i'th element of numbers depends only on the value of the (i-1)'th element of numbers, but not on it's own value: the first element is given as 1. the second element is the first element + 1, so it is 2. the third element is the second element + 1, so it is 3. and so on... But infinity = 1 + infinity doesn't work at all, because the value of infinity depends on it's own value.
The code I reference is located at :
http://michaelspeer.blogspot.com/2007/06/impossible-is-only-possible-sometim...
Your code contains the following definitions (among others):
exn (c:_) n l = ( [ [ ( Just c , (n+1) ) ] ] , (n+1) ) aexn (b:[]) n l = exn b n l oexn (g:[]) n l = let ( ns , x ) = ( aexn g x l ) in ( [] , ns , x )
The definition of exn says that the second component of exn's result depends on it's second argument. The definition of oexn feeds the second component of exn's result back as it's second argument. This creates a data dependency loop and the value of the third component of oexn is not defined. Your code is actually similiar to my infinity example above. Your code looks complicated, partly because you normalize some string representations instead of creating a domain specific algebraic data type. Wich aproach of the website you link to do you follow? Have you considered using a parser combinator library? Tillmann
For example numbers = 1 : map (1 +) numbers works fine [snip] But infinity = 1 + infinity doesn't work at all, because the value of infinity depends on it's own value. Another nice way to think about this is in terms of fixed points. Remember that an equation like: numbers = 1 : map (1 +) numbers Is equivalent to a version using fix: numbers = fix (\ns -> 1 : map (1 +) ns) So numbers gets assigned the fixpoint of the function \ns -> 1 : map (1 +) ns. We can easily see that the list of positive integers [1, 2, 3...] is a fixpoint of that function, because adding 1 to every element and sticking a 1 on the front results in the positive integers again. On the other hand, the equation for infinity: infinity = fix (1 +) Results in infinity = _|_, because there is no fixpoint of the function (1 +) (there is no number that, when you add one to it, results in that same number.) Interestingly, though, if you define Peano natural numbers: data Nat = Z | S Nat -- For example: zero = Z one = S Z two = S (S Z) infinity = S infinity Then infinity is _not_ _|_, but is in fact S (S (S ...)). This may not seem very useful, but say we were to write an Ord instance for Nat: instance Ord Nat where Z `compare` Z = EQ S _ `compare` Z = GT Z `compare` S _ = LT S n `compare` S m = n `compare` m (I.e. compare works by unwrapping S constructors from its two arguments and seeing which one runs out first.) Then infinity serves as a value which is GT than all other values. -David House, dmhouse@gmail.com
Am Dienstag, 12. Juni 2007 11:51 schrieb David House:
[…]
Another nice way to think about this is in terms of fixed points. Remember that an equation like:
numbers = 1 : map (1 +) numbers
Is equivalent to a version using fix:
numbers = fix (\ns -> 1 : map (1 +) ns)
So numbers gets assigned the fixpoint of the function \ns -> 1 : map (1 +) ns.
It is always the *least* fixpoint. For example, (0 *) has the fixpoint _|_ (because 0 * _|_ = _|_) but every integer is also a fixpoint of it. However, _|_ is less than all those integers in the sense of “less defined”, and so the result of fix (0 *) is _|_.
[…]
Best wishes, Wolfgang
From: Wolfgang Jeltsch <g9ks157k@acme.softbase.org> It is always the *least* fixpoint. For example, (0 *) has the fixpoint _|_ (because 0 * _|_ = _|_) but every integer is also a fixpoint of it. However, _|_ is less than all those integers in the sense of âless definedâ, and so the result of fix (0 *) is _|_. True, that's worth mentioning. By the way, the Haskell Wikibook chapter on Denotational Semantics [1] will make for interesting reading for anyone following along with this discussion. [1]: http://en.wikibooks.org/wiki/Haskell/Denotational_semantics -David House, dmhouse@gmail.com
You may also want to read the discussions on and linked to from: http://www.haskell.org/haskellwiki/Regular_expressions You may also want to consult my regular expression library regex-tdfa which has a Parsec parser for extended regular expressions at: http://darcs.haskell.org/packages/regex-unstable/regex-tdfa/Text/Regex/TDFA/... which makes a Pattern data type as the result of parsing which is defined in: http://darcs.haskell.org/packages/regex-unstable/regex-tdfa/Text/Regex/TDFA/... The laziness works for multiple functions but it must be correct. In "c" it is easy to make "goto" based code into an infinite loop, or to dereference a null pointer. In Haskell it is easy to define "x=y ; y=x" and enter an infinite loop. -- Chris Kuklewicz
Michael Speer wrote:
test x y = ( "World" , x , x ++ " " ++ y ) main = let ( a , b , c ) = test "Hello" a in do print $ ( a , b , c )
This works, but in your code you actually wrote let ( ( a, b, c ), ( d, e, f ), ( g, h, i ) ) = ( foo, bar, baz ) with the right side involving the stuff on the left. This won't work; for Haskell to bind values to a, b, and so on, it has to examine the value being matched to check whether it is really a tuple (and not _|_). You can defer the check, and that's called a lazy or irrefutable pattern binding: let ( ~( a, b, c ), ~( d, e, f ), ~( g, h, i ) ) = ( foo, bar, baz ) This would work. The reason you didn't run into this earlier (and why I apprently forgot a tilde) is that let-bindings are always lazy, as if you had put a tilde there, but this doesn't hold for nested patterns. This means that not tupling your three functions and instead using a group of bindings would work, too, and look prettier anyway: let ( a, b, c ) = foo ( d, e, f ) = bar ( g, h, i ) = baz Yes, let groups allow mutually recursive bindings, the same is true for where clauses and mdo blocks.
Is this a known problem that will one day be resolved, or is it considered beyond the scope of the language?
Neither, it's supposed to be this way. Btw, you might consider posting a _minimal_ code example when illustrating your next problem. I didn't even try to run your big chunk of code, so the above is only guesswork. -Udo -- Always call a spade a spade, except in classes that both dig holes and play bridge. -- a guideline for Eiffel programmers
participants (8)
-
David House -
haskell＠list.mightyreason.com -
Michael Speer -
Ryan Ingram -
Tillmann Rendel -
Tomasz Zielonka -
Udo Stenzel -
Wolfgang Jeltsch