Throttling at the thunk+GC interaction as I suggested, thus transparent to the semantics of Haskell language, is an experimental concept that potentially convolves with the system-at-large. Perhaps I would also pursue an orthogonal strategy at the semantics layer, which is less global in scope. Perhaps it is possible to categorize and generalize many of the types of structures that cause space leaks, then handle them at the semantic layer (but afaics this can not be argued to most optimal in all respects). The latter is successful every time you generalize a case and are able to identify it automatically with an analyzer.

Generally, a form of lenient evaluation + lazy data structures can provide the benefits of Haskell non-strict evaluation without the drawbacks. A "reimagining" of Haskell cast in this mold might make for a very practical thesis.

Regards,

John A. De Goes N-Brain, Inc. The Evolution of Collaboration

http://www.n-brain.net | 877-376-2724 x 101

On Nov 4, 2009, at 7:29 PM, Shelby Moore wrote:

...

...

Hello, -Cafe,

I'm looking for an interesting topic to hack on in my thesis.

The thesis should be rather "theoretical"/abstract (writing a mail client in Haskell is not, for example), dealing with FP or related fields.

The theoretical concept of how to make lazy evaluation less discontinuously correlated to allocation space determinism:

http://www.haskell.org/pipermail/haskell-cafe/2009-November/ 068436.html http://www.haskell.org/pipermail/cvs-ghc/2009-October/050928.html http://www.haskell.org/pipermail/cvs-ghc/2009-November/050946.html http://www.haskell.org/pipermail/cvs-ghc/2009-November/050949.html (should have written "stochastic" instead of "statistical")

I think this would make you a hero also if you succeed, as I see this problem as the main problem stopping its adoption as a mainstream language.

The problem as I see it (Google "space leak Haskell" for examples), is that even a very small change in the code can cause a huge space leak that slows the program to molasses due to paging (faults) load. And these effects are not predictable or easy to reason about. When these discontinuous effects occur, we have to stop our development, do profiling, and try to isolate the obscure cause, then restructure code in bizzarre ways to try to get some determinism in space allocation.

My abstract idea is that it should be possible to stochastically throttle these effects, by throtting whether (and whic) thunks get cached to (WH)NF or re-valuated on each use.

I do think it is possible to teach people how to program in FP succinctly and without making their head hurt:

http://www.haskell.org/pipermail/haskell-cafe/2009-November/ 068564.html

You may not find many people here openly expressing their interest in these topics, but I think there are millions of people out there who would benefit. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

And we wonder why Haskell isn't mainstream... On Thu, Nov 5, 2009 at 4:31 PM, Deniz Dogan wrote:

2009/11/5 Andrew Coppin :

...

Matus Tejiscak wrote:

...

zygohistomorphic prepromorphisms

Please tell me this isn't a real technical term. o_O

http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms

Still can't tell if it's a joke or not...

-- Deniz Dogan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

I'm to blame for that page. I made the various 'greco'-morphisms from constructive algorithmics into independently combinable features in category-extras, and page spun out of a joke on the #haskell channel from people making fun of the ever more complicated recursion schemes I was supporting. It is a fairly useless technical term for a recursion scheme that no one in their right mind would use, but 'zygo-' 'histomorphic' and 'prepromorphism' all have real meanings. Each of these features can be composed. They are also fairly painfully abstract. A catamorphism is just a generalization of 'unfoldr' to arbitrary algebraic data types. A generalized catamorphism is a catamorphism that uses a distributive law for some comonad. A zygomorphism introduces mutual recursion with a helper function. It is just a generalized catamorphism using the reader/product comonad. However, in category-extras I defined 'comonad transformers', including a reader/product comonad transformer, so you can modify more complicated recursion schemes by adding 'zygo'. A histomorphism gives access to 'results obtained so far', and a prepromorphism is a modified catamorphism that also applies a natural transformation each time it recurses. This can be done by utilizing the fact that there is a "cofree comonad" for any functor f, which has a natural distributive law over f. So a histomorphism is just another generalized catamorphism. A prepromorphism is a slightly different animal, it applies a natural transformation each time it recurses. This lets you build up recursive operations like 'iterate' in a more formal manner. I generalized prepromorphisms, the way that you can generalize catamorphisms, allowing them to be parameterized on an arbitrary comonad. This means that all of the machinery you can use to parameterize your catamorphisms, can now be exploited to parameterize prepromorphism. Since you can apply the comonad transformer for reader to the cofree comonad of your base functor you can make a zygohistomorphic prepromorphism. The nice thing is that you can readily dualize each of these notions and start talking about the equivalent way to build UP a structure. One might argue that for consistency the name should be a zygohistoprepromorphism, but that starts to become unwieldy. The downside is that few people have read all of the papers to know what each of those terms mean in isolation, let alone when rolled into the same recursion scheme, so I wouldn't recommend using one in production maintainable code. =) -Edward Kmett On Thu, Nov 5, 2009 at 5:31 PM, Deniz Dogan wrote:

2009/11/5 Andrew Coppin :

...

Matus Tejiscak wrote:

...

zygohistomorphic prepromorphisms

Please tell me this isn't a real technical term. o_O

http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms

Still can't tell if it's a joke or not...

-- Deniz Dogan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Fri, Nov 06, 2009 at 03:29:47PM +0000, Stephen Tetley wrote:

Hello all,

Are any of the of the more exotic recursion schemes definable without a least-fixed point /Mu/ type?

Note that Haskell datatypes have a built-in implicit "mu" (that is, every recursive Haskell datatype can be thought of as the fixed point of some suitable functor); the "Mu" type you see in the types of those recursion schemes just makes the knot-tying explicit. Given any particular recursive type, it should be possible to implement any of the recursion schemes specifically for that type without mentioning Mu. However, to write recursion schemes that work generally over *any* recursive type (aside from generic programming techniques) requires the explicit use of the Mu type, because you need to be able to refer to the functor of which the recursive type is a fixed point, and there's no (easy) way to take a recursive Haskell data type and "unfix" it to get the underlying structure functor. -Brent

Matus Tejiscak wrote:

On Pi, 2009-11-06 at 17:25 -0500, Brent Yorgey wrote:

...

On Fri, Nov 06, 2009 at 03:29:47PM +0000, Stephen Tetley wrote:

...

Hello all,

Are any of the of the more exotic recursion schemes definable without a least-fixed point /Mu/ type? Note that Haskell datatypes have a built-in implicit "mu" (that is,

I'd say Mu gets you a greatest-fixed point. I don't have a proof, I just note that Mu(ΛX. 1 + A x X) contains infinite lists, too.

Mu is the notation for least-fixed, Nu is the notation for greatest-fixed. In Haskell, the two fixed points coincide due to laziness and _|_.

I wonder whether this is a problem; if I want to define an initial algebra of a functor, I should take a least fixed point (if I understand it correctly) -- but all I have is Mu. Inductively defined functions will loop on infinite lists, which are included in the resulting type, and -- i imagine -- the type system might prevent such errors, by not enabling casting from greatest-Mu(F) to least-Mu(F). But that's probably too restrictive to be useful.

If you want the type system to catch infinite looping like this, then you'll need to switch to a total functional programming language which distinguishes data and codata (and hence what can be inducted on vs what needs to be coinducted on). -- Live well, ~wren

Stefan Holdermans wrote:

http://people.cs.uu.nl/stefan/pubs/hage08heap.html

Getting connection refused on that. Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

2009/11/6 Deniz Dogan :

2009/11/6 Erik de Castro Lopo :

...

Stefan Holdermans wrote:

...

   http://people.cs.uu.nl/stefan/pubs/hage08heap.html

Getting connection refused on that.

Try this one, from Google's cache: http://preview.tinyurl.com/ydjuw2j

-- Deniz Dogan

Oops, those were slides. Here is the paper: http://preview.tinyurl.com/ycmneko -- Deniz Dogan

Stefan Holdermans wrote:

Erik,

...

...

http://people.cs.uu.nl/stefan/pubs/hage08heap.html

...

Getting connection refused on that.

Don't know: it still works for me.

Working for me as well now. Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/