Master's thesis topic sought

[Matus Tejiscak]

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. I've had a few (blurry) ideas, ranging from investigating
(possibilities for) Haskell extensions, to zygohistomorphic
prepromorphisms, but nothing concrete, possibly because I'm not familiar
with these areas enough to see what could be done -- which brings up a
question whether it is a good idea to even try hacking on a topic like
this.

However, I'm eager to learn so if you have a topic you'd need somebody
to work on, or just an interesting (or maybe even an uninteresting)
idea, i'd be grateful for suggestions. :)

Thanks,
Matus

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

[shelby-3]

> 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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[John A. De Goes]

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@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[shelby-3]

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@...
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

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

[Luke Palmer-2]

On Wed, Nov 4, 2009 at 5:52 PM, Matus Tejiscak <ziman@...> 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. I've had a few (blurry) ideas, ranging from investigating
> (possibilities for) Haskell extensions, to zygohistomorphic
> prepromorphisms, but nothing concrete, possibly because I'm not familiar
> with these areas enough to see what could be done -- which brings up a
> question whether it is a good idea to even try hacking on a topic like
> this.
>
> However, I'm eager to learn so if you have a topic you'd need somebody
> to work on, or just an interesting (or maybe even an uninteresting)
> idea, i'd be grateful for suggestions. :)

Yes!  I have been trying to experiment with lazy specializing virtual
machine, but I am starting a company so basically have no time for
such academic pursuits.

Here is a short brainstormy introduction I wrote about lazy
specialization to whet your appetite:
http://lukepalmer.wordpress.com/2009/07/07/emphasizing-specialization/

And an overnight hack proof of concept: http://github.com/luqui/vatican

But I think the area deserves *much* more research than it is
currently getting, and could end up being a influential piece of
functional programming.

There are a fair amount of topics in there -- the one I am most
interested in is simply the art of engineering for a lazy specializer.
 I.e. how does having a lazy specializing language affect the way we
write efficient purely functional programs?

If you are interested, I would be happy to guide you through what I
know so you can find something interesting and pick it up quickly.

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

[shelby-3]

> Here is a short brainstormy introduction I wrote about lazy
> specialization to whet your appetite:
> http://lukepalmer.wordpress.com/2009/07/07/emphasizing-specialization/

Quoting from your linked page:

"...The key point about data structures is that they can be decomposed;
you can peel off the root of a tree and leave yourself with only one of
the branches, and the other branch will be garbage collected.

A lazy specializer promotes full-blown functions to the level of data
structures. Functions can now be decomposed (by composing!) in the same
way, sharing important pieces and forgetting unimportant ones...

...removes the encouragement to fiddle with the details of a function for
more speed...

...thus arbitrary functions separate us from the enclosed Behavior, about
which we must selectively forget things. However, the lazy specializer has
no trouble looking through those functions, and will modify the behavior
anyway, ridding us of the dreaded space leak..."


Analyzing structure (for optimization of speed and unconflating data) at
the semantic layer can also eliminate space leaks, which was an area of
work I was suggesting here:

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

"...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..."
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Andrew Coppin]

Matus Tejiscak wrote:
> zygohistomorphic prepromorphisms

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

As for concrete suggestions... I've always thought we could do more to
use static information about the program to aid runtime GC. It's no deep
secret that destructive updates are essentially like a compile-time /
coding-time GC operation. You determine before runtime that the old
version of the data will never be needed again, and hence update it
in-place. Making this kind of thing more automatic could be interesting
theoretically and practically. The other thing is connectedness; a GC
performs a sweep of a big chunk of memory to find live objects, but if
you somehow knew from compile-time analysis something about what the
runtime linking structure is going to be, you might be able to do
something interesting. (OTOH, laziness and sharing probably spoils this.)

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

[Deniz Dogan-3]

2009/11/5 Andrew Coppin <andrewcoppin@...>:
> 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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stefan Holdermans]

Andrew,

> As for concrete suggestions... I've always thought we could do more  
> to use static information about the program to aid runtime GC. It's  
> no deep secret that destructive updates are essentially like a  
> compile-time / coding-time GC operation. You determine before  
> runtime that the old version of the data will never be needed again,  
> and hence update it in-place. Making this kind of thing more  
> automatic could be interesting theoretically and practically.

[Warning: shameless plug follows.]

Have you had a look at our 2008 PEPM paper?

   Jurriaan Hage and Stefan Holdermans. Heap recyling for lazy  
languages.
   In John Hatcliff, Robert Glück, and Oege de Moor, editors,  
Proceedings
   of the 2008 ACM SIGPLAN Symposium on Partial Evaluation and  
Semantics-
   Based Program Manipulation, PEPM 2008, San Francisco, California,  
USA,
   January 7–8, 2008, pages 189–197. ACM Press, 2008.

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

As far as automatic detection of opportunities for in-place updates is  
concerned, the Clean compiler seems to do some interesting things.

   http://clean.cs.ru.nl/

I am not quite sure whether the details (a formal semantics, for  
example) have ever been published. I would be very much interested in  
such a description myself, actually, so if someone knows of any...

Cheers,

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

[Patrick Brannan]

And we wonder why Haskell isn't mainstream...

On Thu, Nov 5, 2009 at 4:31 PM, Deniz Dogan <deniz.a.m.dogan@...> wrote:

> 2009/11/5 Andrew Coppin <andrewcoppin@...>:
>> 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@...
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

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

[Anton van Straaten]

Deniz Dogan wrote:
> 2009/11/5 Andrew Coppin <andrewcoppin@...>:
>> 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...

You might also be interested in Chapter 9 of the upcoming book described
here:

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

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

[Roel van Dijk-3]

On Thu, Nov 5, 2009 at 11:11 PM, Andrew Coppin
<andrewcoppin@...> wrote:
> Matus Tejiscak wrote:
>>
>> zygohistomorphic prepromorphisms
>
> Please tell me this isn't a real technical term. o_O
>

You can even generalize them:
g_prepro_zygo :: (Functor f, Comonad w) => GAlgebra f w b -> Dist f w
-> GAlgebra f (ZygoT w b) a -> (f :~> f) -> FixF f -> a

Brought to you by the wonderful world of category theory:
http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Morphism-Zygo.html

Here is an explanatory diagram:
http://bifunctor.homelinux.net/~roel/zygohistomorphic_prepromorphism.gif
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Erik de Castro Lopo-34]

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/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Deniz Dogan-3]

2009/11/6 Erik de Castro Lopo <mle+hs@...>:
> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Deniz Dogan-3]

2009/11/6 Deniz Dogan <deniz.a.m.dogan@...>:

> 2009/11/6 Erik de Castro Lopo <mle+hs@...>:
>> 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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Stefan Holdermans]

Erik,

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

> Getting connection refused on that.

Don't know: it still works for me.

Cheers,

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

[Erik de Castro Lopo-34]

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/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[shelby-3]

> 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.

I added a refined description of the algorithm I am proposing (as a
starting point for further work):

http://hackage.haskell.org/trac/ghc/ticket/3630#comment:4

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

[edwardk]

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 <deniz.a.m.dogan@...> wrote:

2009/11/5 Andrew Coppin <andrewcoppin@...>:

> 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@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[Stephen Tetley-2]

Hello all,

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

The only definitions of zygomorphism etc. I've seen use it.

Thanks

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