On 2006-04-05 at 12:35EDT "Michael Goodrich" wrote:
> Greetings All: > > GHC gives: Fail: <<loop>> > > Hugs gives: [(ERROR - C stack overflow Nowt's up wi' ' runtime error message. GHC's perfectly lucid. It says your programme went into an infinite loop. This sort of thing belongs on haskell-cafe, by the way. I've moved it there. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 2006-04-05 at 14:03EDT "Michael Goodrich" wrote:
> BTW, I can't seem to locate 'haskell-cafe'. http://www.haskell.org/mailman/listinfo/haskell-cafe > The message responding to my sign-up said nothing about > haskell-cafe. Perhaps it should. It's so long since I signed up to haskell that I've forgotten what the sign-up message says. > Also, in my infinte-looping application, I am wrapping the > calculation in a 'take 1000' function - shouldn't this > guarantee termination? Not on its own loop = loop:: Char l = [1,2,3,loop,5,6] putStr $ show $ take 4 l will print 1 2 and 3 and then loop when trying to find the value for the fourth. -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Jon Fairbairn
Looks like my calulation involves a self referential set of definitions.
Is Haskell not able to deal with a self referential set of definitions? I was frankly hoing it would since otherwise there is then the specter of sequence, i.e. that I have to finesse the order in which things are calculated so as to avoid it. Thoughts? cheers, -Mike _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 4/5/06, Michael Goodrich <[hidden email]> wrote:
> Looks like my calulation involves a self referential set of definitions. > > Is Haskell not able to deal with a self referential set of definitions? Yes, it is, but not if that definition doesn't evaluate to a "proper" value. For example: main = do print x where x = 3 * x^2 What do you expect this to do? It may help if you toss us the offending code. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Michael Goodrich
Michael Goodrich wrote:
> Looks like my calulation involves a self referential set of definitions. > > Is Haskell not able to deal with a self referential set of definitions? > > I was frankly hoing it would since otherwise there is then the specter > of sequence, i.e. that I have to finesse the order in which things are > calculated so as to avoid it. > > Thoughts? Lazy evaluation is great with self-referential definitions, but id doesn't do so well with ill-founded definitions. It also won't find fixpoints of numeric equations. Here are some examples, and then some explanation. Things that work: {- for interactive use in ghci -} let ones = 1:ones --infinite list of ones let counting = 1:map (+1) counting -- infinite list counting up from one let fibs = 1:1:zipWith (+) fibs (tail fibs) --fibbonacci numbers {- A larger program. turns references by name into direct references Try on a cyclic graph, like buildGraph [("a",["b"]),("b",["a"])] -} import Data.List import Data.Map as Map data Node = Node String [Node] type NodeDesc = (String, [String]) buildNode :: Map String Node -> NodeDesc -> Node buildNode env (name,outlinks) = Node name (concat [Map.lookup other finalBinds | other <- outlinks]) buildGraph :: [(String,[String])] -> [Node] buildGraph descs = nodes where (finalBinds, nodes) = mapAccumR buildExtend Map.empty descs buildExtend binds desc@(name,_) = let node = buildNode finalBinds desc in (Map.insert name node binds, node) Things that will not work: let x = x -- no information on how to define x let x = 2*x + 1 -- this is not treated algebraically let broke = 1:zipWith (+) broke (tail broke) -- the second element depends on itself Recursive definitions in Haskell can be explained by saying that they find the least-defined fixedpoint of the equations. Every type in Haskell has all the usual values you would have in a strict language, plus an undefined value which corresponds to a nonterminating computation. Also, there are values where subterms of different types are undefined values of that type rather. For example, with pairs of numbers there are these posibilites (x,y) / \ (_|_,x) (x,|_|) \ / (_|_,_|_) | _|_ where x and y represent any defined number, and _|_ is "undefined", or a non-terminating computation. A value on any line is considered more defined than values on lower lines. Any value which can be obtained from another by replacing subterms with _|_ is less defined, if neither can be made from the other that way than neither is more defined that the other. Think of a definition like x = f x. That will make x the least-defined value which is a fixedpoint of f. For example, numeric operations are (generally) strict, so _|_ * x = _|_, _|_ + x = _|_, and _|_ is a fixedpoint of \x -> 2*x + 1. for broke, consider the function f = \l -> 1:(zipWith (+) l (tail l)) f (x:_|_) = 1:zipWith (+) (1:_|_) (tail (1:_|_)) = 1:zipWith (+) (1:_|_) _|_ = 1:_|_ so 1:_|_ is a fixedpoint. It's also the least fixedpoint, because _|_:_|_ is not a fixedpoint, and f _|_ = 1:<something>, so _|_ is not a fixedpoint either. If I try that definition of broke, ghci prints "[1" and hangs, indicating that the rest of the list is undefined. If multiple definitions are involved, think of a function on a tuple of all the definitions: x = y y = 1:x corresponds to the least fixedpoint of (\(x,y) -> (y,1:x)) The recursiveness in the graph example is more tedious to analyze like this, but it works out the same way - whatever value of "finalBinds" is fed into the recursive equation, you get out a map built by taking the empty map and adding a binding for each node name. Chase it around a few more times, and you'll get some detail about the nodes. Also, posting code really helps if you want specific advice. Thanks to the hard work of compiler writers, the error message are usually precise enough for a message like this to describe the possibilites. If you enjoy my rambling I suppose you should keep posting error messages :) Brandon > cheers, > > -Mike > > > ------------------------------------------------------------------------ > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by ihope
On 4/5/06, ihope <[hidden email]> wrote: On 4/5/06, Michael Goodrich <[hidden email]> wrote: I will be glad to. But just to make it more simple, it is a recursive function with a self referential set of definitions that builds a list like this : ------------------------------------------------------------------------------------------------------------ foo (step,r0,mu0) = bar (step,r1,r0,mu1,mu0) where r1 = r0-step*rd mu1 = mu0-step*mud rd = c*c*mu0 mud = c*c/r0 - (foobar_r z)/c c = baz(z) z = 6.378388e6-r0 baz z | z<125 = -0.25*z+1537.5 | otherwise = 0.0169*z+1504.1 foobar_r z | z<125 = 0.25 | otherwise = -0.0169 bar (step,r2,r1,mu2,mu1) = (r,z0) : bar (step,r1,r,mu1,m) where r = r2+2*step*rdc m = mu2+2*step*mudc rdc = (rd2+rd1+rd0)/6 mudc = (mud2+mud1+mud0)/6 rd2 = c2*c2*mu2 mud2 = c2*c2/r2 - (foobar_r z2)/c2 rd1 = c1*c1*mu1 mud1 = c1*c1/r1 - (foobar_r z1)/c1 rd0 = c0*c0*m mud0 = c0*c0/r - (foobar_r z0)/c0 c2 = baz(z2) c1 = baz(z1) c0 = baz(z0) z2 = 6.378388e6-r2 z1 = 6.378388e6-r1 z0 = 6.378388e6-r main :: IO () main = do print $ take 100 (foo (0.1, 6.378388e6,0)) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Michael Goodrich wrote:
[snip] > r = r2+2*step*rdc > rdc = (rd2+rd1+rd0)/6 > rd0 = c0*c0*m > c0 = baz(z0) > z0 = 6.378388e6-r The equations above form a loop: each one requires the one below it, and the last one requires the first one. (And yes, baz is strict) Regards, Roberto Zunino. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 4/5/06, Roberto Zunino <[hidden email]> wrote: Michael Goodrich wrote: Interesting, I was told that it is ok to have a mutually dependent set of definitions - are you saying that Haskell cannot handle this? Also I know what strict means, but why are you saying that baz is strict? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Brandon Moore
Oops, I just realized that you gave me the answer, namely that it won't find fixed points of numeric sets of equations. Pity, that would really have made Haskell useful for this kind of scientific computing. On 4/5/06, Brandon Moore <[hidden email]> wrote: Michael Goodrich wrote: _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Wednesday 05 April 2006 04:51 pm, Michael Goodrich wrote:
> Oops, I just realized that you gave me the answer, namely that it won't > find fixed points of numeric sets of equations. > > Pity, that would really have made Haskell useful for this kind of > scientific computing. See section 4 of: http://www.cs.chalmers.se/~rjmh/Papers/whyfp.html See also: http://www.haskell.org/haskellwiki/Libraries_and_tools/Mathematics http://users.info.unicaen.fr/~karczma/arpap/ > On 4/5/06, Brandon Moore <[hidden email]> wrote: > > Michael Goodrich wrote: > > > Looks like my calulation involves a self referential set of > > > definitions. > > > > > > Is Haskell not able to deal with a self referential set of definitions? > > > > > > I was frankly hoing it would since otherwise there is then the > > > specter of sequence, i.e. that I have to finesse the order in which > > > things are calculated so as to avoid it. > > > > > > Thoughts? > > > > Lazy evaluation is great with self-referential definitions, but id > > doesn't do so well with ill-founded definitions. It also won't find > > fixpoints of numeric equations. Here are some examples, and then some > > explanation. > > > > Things that work: > > > > {- for interactive use in ghci -} > > let ones = 1:ones > > --infinite list of ones > > let counting = 1:map (+1) counting > > -- infinite list counting up from one > > let fibs = 1:1:zipWith (+) fibs (tail fibs) > > --fibbonacci numbers > > > > {- A larger program. > > turns references by name into direct references > > Try on a cyclic graph, like > > buildGraph [("a",["b"]),("b",["a"])] > > -} > > import Data.List > > import Data.Map as Map > > > > data Node = Node String [Node] > > type NodeDesc = (String, [String]) > > > > buildNode :: Map String Node -> NodeDesc -> Node > > buildNode env (name,outlinks) = > > Node name (concat [Map.lookup other finalBinds | other <- outlinks]) > > > > buildGraph :: [(String,[String])] -> [Node] > > buildGraph descs = nodes > > where (finalBinds, nodes) = mapAccumR buildExtend Map.empty descs > > buildExtend binds desc@(name,_) = > > let node = buildNode finalBinds desc > > in (Map.insert name node binds, node) > > > > > > Things that will not work: > > > > let x = x > > -- no information on how to define x > > > > let x = 2*x + 1 > > -- this is not treated algebraically > > > > let broke = 1:zipWith (+) broke (tail broke) > > -- the second element depends on itself > > > > > > Recursive definitions in Haskell can be explained by > > saying that they find the least-defined fixedpoint of the equations. > > Every type in Haskell has all the usual values you would have in a > > strict language, plus an undefined value which corresponds to a > > nonterminating computation. Also, there are values where subterms > > of different types are undefined values of that type rather. > > > > For example, with pairs of numbers there are these posibilites > > (x,y) > > / \ > > (_|_,x) (x,|_|) > > \ / > > (_|_,_|_) > > > > _|_ > > where x and y represent any defined number, and _|_ is "undefined", > > or a non-terminating computation. A value on any line is > > considered more defined than values on lower lines. Any value which can > > be obtained from another by replacing subterms with _|_ is less defined, > > if neither can be made from the other that way than neither is more > > defined that the other. > > > > > > Think of a definition like x = f x. That will make x the least-defined > > value which is a fixedpoint of f. For example, numeric operations are > > (generally) strict, so _|_ * x = _|_, _|_ + x = _|_, and > > _|_ is a fixedpoint of \x -> 2*x + 1. > > > > for broke, consider the function f = \l -> 1:(zipWith (+) l (tail l)) > > f (x:_|_) = 1:zipWith (+) (1:_|_) (tail (1:_|_)) > > = 1:zipWith (+) (1:_|_) _|_ > > = 1:_|_ > > so 1:_|_ is a fixedpoint. It's also the least fixedpoint, because > > _|_:_|_ is not a fixedpoint, and > > f _|_ = 1:<something>, so _|_ is not a fixedpoint either. If I try that > > definition of broke, ghci prints "[1" and hangs, indicating that the > > rest of the list is undefined. > > > > If multiple definitions are involved, think of a function on a tuple of > > all the definitions: > > > > x = y > > y = 1:x > > > > corresponds to the least fixedpoint of (\(x,y) -> (y,1:x)) > > > > The recursiveness in the graph example is more tedious to analyze like > > this, but it works out the same way - whatever value of "finalBinds" is > > fed into the recursive equation, you get out a map built by taking the > > empty map and adding a binding for each node name. Chase it around a few > > more times, and you'll get some detail about the nodes. > > > > Also, posting code really helps if you want specific advice. Thanks to > > the hard work of compiler writers, the error message are usually precise > > enough for a message like this to describe the possibilites. If you > > enjoy my rambling I suppose you should keep posting error messages :) > > > > Brandon > > > > > cheers, > > > > > > -Mike > > > > > > > > > ----------------------------------------------------------------------- > > >- > > > > > > _______________________________________________ > > > Haskell-Cafe mailing list > > > [hidden email] > > > http://www.haskell.org/mailman/listinfo/haskell-cafe Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Michael Goodrich
Michael Goodrich wrote:
> Also I know what strict means, but why are you saying that baz is strict? Because otherwise the loop would be OK. For instance if baz were baz x = 100 -- lazy then the equations could be evaluated starting from c0 = baz z0 = 100 rd0 = c0*c0*m = 100*100*m -- etc. and eventually all the variables could be defined. Another example: the pair constructor (,) is lazy so c = (3, fst c) -- "loop" on c is OK, and defines c=(3,3). Regards, Roberto Zunino. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Jon Fairbairn
Thanks so much for your help. I should have made clear that I was aware
that the definitions were mutually dependent. What I was hoping
was that Haskell could solve this for me without my having to resort to
effectively finessing any sequencing considerations.
Perhaps I am really asking it to do too much. This I thought might be reasonable since one is supposed to be achieving a sequence-less style of programming. But this would seem to be a counter example where I will be essentially forced to implement a sequential processing semantic in a language environment which ostensibly would deny me such (for my own good I understand). Thoughts? On 4/6/06, Garrett Mitchener <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On 2006-04-06 at 11:25EDT "Michael Goodrich" wrote:
> Thanks so much for your help. I should have made clear that I was aware that > the definitions were mutually dependent. What I was hoping was that Haskell > could solve this for me without my having to resort to effectively finessing > any sequencing considerations. > > Perhaps I am really asking it to do too much. I think so. Haskell doesn't do anything magic; it's a programming language rather than a mathematical amanuensis, so you have to say what the algorithm is. In the kind of thing you were attempting, ⊥ is a valid solution to the equations, as in f a = g a + 1 g b = f a - 1 where, while f x = x+x + 1, g x = (x+x+1) - 1 is a valid solution, so are many others, and in particular so is f x = ⊥, g x = ⊥, which also has the merit of being simpler. If you want an iteration over values to happen, you have to say where to start and how to get from one approximation to the next (if you don't, how would the compiler choose for you?), and Haskell is very good at this, as described in the paper by John Hughes that someone posted earlier. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Michael Goodrich
> Thanks so much for your help. I should have made clear that I was aware that
> the definitions were mutually dependent. What I was hoping was that Haskell > could solve this for me without my having to resort to effectively finessing > any sequencing considerations. Haskell is a functional language. The program you are trying to solve sounds like a logic problem if I understand it correctly. There is a functional logic programming language called Curry [1] that has similar syntax to Haskell, but a different evaluation approach. (Note: I don't know anything about Curry other than what I read on the front page of their website, and the fact that someone wrote a Sudoku solver by writing the constraints and having the compiler generate a program that solves the puzzle.) > Perhaps I am really asking it to do too much. What you want is a program that looks for a set of values that satisfy a certain set of mathematical relations (you mentioned scientific computing). As I understand it, this is where logic programming shines. (If you can turn this into a system of equations, Mathematica might be able to solve it, btw.) > This I thought might be reasonable since one is supposed to be achieving a > sequence-less style of programming. I never really heard Haskell described this way. I've heard Haskell described as a declarative programming language, where you shouldn't worry about the order of execution of your functions, but I never thought it meant anything about complete sequence-less-ness; it seems very rooted in deterministic evaluation. > But this would seem to be a counter > example where I will be essentially forced to implement a sequential > processing semantic in a language environment which ostensibly would deny me > such (for my own good I understand). In fact, Haskell is big on sequencing. One of the key features of Haskell is the monad [2]; you might call it sequencing done right. I'm not sure how monads would help you (if you can express your code imperatively you are good to go, but it sounds like you want to keep things declarative). > Thoughts? Someone who knows about logic programming might point you to good resources about this perspective, if it applies (other than Curry [1]), which looks pretty fun. Hope that helps, Jared. [1] http://www.informatik.uni-kiel.de/~curry/ [2] http://www.nomaware.com/monads/html/ -- http://www.updike.org/~jared/ reverse ")-:" _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Michael Goodrich
On Apr 6, 2006, at 11:25 AM, Michael Goodrich wrote: > Thanks so much for your help. I should have made clear that I was > aware that the definitions were mutually dependent. What I was > hoping was that Haskell could solve this for me without my having > to resort to effectively finessing any sequencing considerations. > > Perhaps I am really asking it to do too much. > > This I thought might be reasonable since one is supposed to be > achieving a sequence-less style of programming. But this would > seem to be a counter example where I will be essentially forced to > implement a sequential processing semantic in a language > environment which ostensibly would deny me such (for my own good I > understand). > > Thoughts? [snip a bunch of code] I'm not an expert, but I'll take a crack at this. What you seem to want is a numeric fixpoint, wherein each variable in the mutually recursive set of equations is assigned a value that causes all equations to hold. This is called a fixpoint because it represents a point where the function in n-space generated by the n equations maps to itself. The notion of a fixpoint usually found in functional programming languages is a little different -- it is specifically the "least fixed point". Now, I'm getting a little out of my depth here, but I think that the Kleene fixpoint theorem tells us that the least fixpoint of the kind of function in the previous paragraph must be bottom - ie, non-termination (which, GHC can sometimes detect, in which case it prints the <<loop>> error you saw). You can't use the least fixpoint mechanism that the programming language gives you to calculate the those kind of numeric fixpoints, because the least fixpoint is completely uninteresting and not what you want. In haskell, the standard techinque for this kind of thing is to calculate an "infinite" list of successive approximations to the answer and choosing an element from the list according to some criteria (usually absolute or relative convergence of successive elements). You can easily build such a list with 'Data.List.iterate'. This should work for all attractive fixpoints of the function when given an appropriate initial approximation (modulo floating point rounding errors, as always). Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Thank you all for your excellent comments.
I was aware of Hughe's technique and the 'whyfp' paper. I had often thought that some kind of iteration would be necessary to reolve this, and to overcome initially this I was cheating and using one of the values one step late in order to break the closed cycle of references, in my C and Prolog protype versions. This cheat bothered me to the extent that I decided to fix it and that is when I decided that I might be missing the boat, and Haskell might have a built in solution to closed sets of references. But I see now in retrospect that this was a misguided (could I say silly ? ;-) notion and that indeed some kind of numerical algorithm will have to be effected to get the 'pure' solution. Again, many thanks to all, and I learned something valuable. My faith in Haskell and FP has been restored (assuming it ever did actually waiver) cheers, -Mike _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |