HANSEI in Haskell?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

HANSEI in Haskell?

Daryoush Mehrtash-2
Is the "Embedded domain-specific language HANSEI for probabilistic models and (nested) inference"  described in: http://okmij.org/ftp/kakuritu/index.html#implementation  available in Haskell?     Is there a reason why the author did the package in Ocaml rather than Haskell?

--
Daryoush



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Chung-chieh Shan
Hello!  Thank you for your interest.

Daryoush Mehrtash <[hidden email]> wrote in haskell-cafe:
> Is the "Embedded domain-specific language HANSEI for probabilistic models
> and (nested) inference"  described in:
> http://okmij.org/ftp/kakuritu/index.html#implementation  available in
> Haskell?

The closest to that I know of is this one:
  http://d.hatena.ne.jp/rst76/20100706
  https://github.com/rst76/probability

Or you can apply this monad transformer to a probability monad:
  http://sebfisch.github.com/explicit-sharing/

> Is there a reason why the author did the package in Ocaml
> rather than Haskell?

Mostly we preferred (as do the domain experts we target) to write
probabilistic models in direct style rather than monadic style.
Haskell's laziness doesn't help -- in fact, to avoid running out of
memory, we'd have to defeat that memoization by sprinkling "() ->"
throughout the types.

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st graffitiist: QUESTION AUTHORITY!
2nd graffitiist: Why?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Daryoush Mehrtash-2
I would  very much appreciate if you can expand on this:

Haskell's laziness doesn't help -- in fact, to avoid running out of
memory, we'd have to defeat that memoization by sprinkling "() ->"
throughout the types.

Would it be possible to explain this with an example?

Thanks

Daryoush
 
On Wed, Feb 23, 2011 at 7:52 AM, Chung-chieh Shan <[hidden email]> wrote:
Hello!  Thank you for your interest.

Daryoush Mehrtash <[hidden email]> wrote in haskell-cafe:
> Is the "Embedded domain-specific language HANSEI for probabilistic models
> and (nested) inference"  described in:
> http://okmij.org/ftp/kakuritu/index.html#implementation  available in
> Haskell?

The closest to that I know of is this one:
 http://d.hatena.ne.jp/rst76/20100706
 https://github.com/rst76/probability

Or you can apply this monad transformer to a probability monad:
 http://sebfisch.github.com/explicit-sharing/

> Is there a reason why the author did the package in Ocaml
> rather than Haskell?

Mostly we preferred (as do the domain experts we target) to write
probabilistic models in direct style rather than monadic style.
Haskell's laziness doesn't help -- in fact, to avoid running out of
memory, we'd have to defeat that memoization by sprinkling "() ->"
throughout the types.

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st
graffitiist: QUESTION AUTHORITY!
2nd graffitiist: Why?


_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Leon Smith-2
In reply to this post by Chung-chieh Shan
On Wed, Feb 23, 2011 at 10:52 AM, Chung-chieh Shan
<[hidden email]> wrote:
> Mostly we preferred (as do the domain experts we target) to write
> probabilistic models in direct style rather than monadic style.
> Haskell's laziness doesn't help -- in fact, to avoid running out of
> memory, we'd have to defeat that memoization by sprinkling "() ->"
> throughout the types.

I don't think that "() ->" is even guaranteed to work...

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

oleg-30
In reply to this post by Daryoush Mehrtash-2

The topic of HANSEI in Haskell does come up from time to time. In
fact, there was a Haskell edition of the first version of Hansei:

        http://okmij.org/ftp/kakuritu/probM.hs

It was written to see how the code would look in Haskell, and how
memoization (inherent in lazy evaluation of GHC) may help. The code
contains some of the tests from the HANSEI distribution. The
experience showed that lazy evaluation hurts -- a lot. The problem is
not in lack of seq -- adding seq would make things even worse. There
is a bit of explanation at the end of probM.hs. The gist of the
problem is that approximate inference (sampling, to be precise) trades
space for time. The search tree is way too large to fit into
memory. Therefore, it is better to recompute the values (the branches
of the tree) than to keep storing them. That is precisely the opposite
to the trade-off of lazy evaluation. The end result is attempting to
allocate gigabytes (really!), even for toy problems. We can get around
the problem by using thunks explicitly. But then we lose the remaining
benefits of Haskell syntax (the ones that are left after we have to
switch to the monadic notation). OCaml becomes quite compelling then.

It must be stressed that laziness in general is _crucial_ for solving
even moderately complex problems. However, the needed laziness is NOT
of the kind provided by GHC. We need memoization specific to a
possible world, rather than the one that affects all possible
worlds. GHC gives only the latter. The sort of laziness needed for
non-deterministic programming calls for first-class store.  It can be
emulated, albeit imperfectly, for example, as was described in the
ICFP09 paper. Hansei uses a quite similar idea.  Ideally first-class
memory is provided as built-in, since it requires interaction with
garbage collection.  Greg Morrisett has written extensively on this
topic and done a few implementations; see for example,
        http://www.eecs.harvard.edu/~greg/papers/jgmorris-callcs.ps

Sadly, the topic has been forgotten.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Arnaud Clère
On 24/02/2011 09:30, [hidden email] wrote:
> The sort of laziness needed for non-deterministic programming calls
> for first-class store.  It can be emulated, albeit *imperfectly*,
 > for example, as was described in the ICFP09 paper.

What do you mean by "imperfectly"?
Do you think implementing 'probM' with 'share' would lead to the same
performance problems you experienced in probM.hs?

> Ideally first-class memory is provided as built-in, since it
 > requires interaction with garbage collection.  Greg Morrisett has
 > written extensively on this topic and done a few implementations;
 > see for example,
> http://www.eecs.harvard.edu/~greg/papers/jgmorris-callcs.ps



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Chung-chieh Shan
In reply to this post by Leon Smith-2
Leon Smith <[hidden email]> wrote in article <AANLkTikF6EX4U+uTwNcrdFZPj-ijTWb74o2W_RJMGOe=@mail.gmail.com> in gmane.comp.lang.haskell.cafe:
> On Wed, Feb 23, 2011 at 10:52 AM, Chung-chieh Shan
> <[hidden email]> wrote:
> > Mostly we preferred (as do the domain experts we target) to write
> > probabilistic models in direct style rather than monadic style.
> > Haskell's laziness doesn't help -- in fact, to avoid running out of
> > memory, we'd have to defeat that memoization by sprinkling "() ->"
> > throughout the types.
> I don't think that "() ->" is even guaranteed to work...

That's quite true.  Then again, it's not guaranteed that "() ->" is
needed for good memory usage.  We just need a sufficiently smart
compiler!

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st graffitiist: QUESTION AUTHORITY!
2nd graffitiist: Why?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Chung-chieh Shan
In reply to this post by Arnaud Clère
Arnaud Clère <[hidden email]> wrote in article <ik64e9$j6a$[hidden email]> in gmane.comp.lang.haskell.cafe:
> On 24/02/2011 09:30, [hidden email] wrote:
> > The sort of laziness needed for non-deterministic programming calls
> > for first-class store.  It can be emulated, albeit *imperfectly*,
>  > for example, as was described in the ICFP09 paper.
> What do you mean by "imperfectly"?

I think Oleg meant that, because the garbage collector only understands
the native store and not our emulation of first-class stores, cells of
a first-class store that are no longer referenced will nevertheless not
be garbage-collected until the store itself is garbage-collected.  What
we need is a way to tell the garbage collector that the store reference
and the cell reference are both needed to access the data so the data
can be garbage-collected as soon as *either* the store reference *or
the cell reference* is.  (Analogy from the capabilities literature:
the key and the lock are both needed to open the door so the door can
be garbage-collected as soon as either the key or the lock is.)  Any
thoughts on how to achieve that?

> Do you think implementing 'probM' with 'share' would lead to the same
> performance problems you experienced in probM.hs?

No, implementing probM with share would be like what OCaml HANSEI
currently does, except in monadic notation rather than direct style.

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st graffitiist: QUESTION AUTHORITY!
2nd graffitiist: Why?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Antoine Latter-2
On Thu, Feb 24, 2011 at 12:57 PM, Chung-chieh Shan
<[hidden email]> wrote:

> Arnaud Clère <[hidden email]> wrote in article <ik64e9$j6a$[hidden email]> in gmane.comp.lang.haskell.cafe:
>> On 24/02/2011 09:30, [hidden email] wrote:
>> > The sort of laziness needed for non-deterministic programming calls
>> > for first-class store.  It can be emulated, albeit *imperfectly*,
>>  > for example, as was described in the ICFP09 paper.
>> What do you mean by "imperfectly"?
>
> I think Oleg meant that, because the garbage collector only understands
> the native store and not our emulation of first-class stores, cells of
> a first-class store that are no longer referenced will nevertheless not
> be garbage-collected until the store itself is garbage-collected.  What
> we need is a way to tell the garbage collector that the store reference
> and the cell reference are both needed to access the data so the data
> can be garbage-collected as soon as *either* the store reference *or
> the cell reference* is.  (Analogy from the capabilities literature:
> the key and the lock are both needed to open the door so the door can
> be garbage-collected as soon as either the key or the lock is.)  Any
> thoughts on how to achieve that?
>

Here's a weak cell which is a candidate for GC as soon as either the
cell or the key is lost:

http://hpaste.org/44280/weak_ref_needing_both_halves

The implementation is GHC specific, as far as I know.

I don't know if it's exactly what you're looking for, but the idea
could be adapted towards some other purpose.

Antoine

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Chung-chieh Shan
On 2011-02-24T16:20:46-0600, Antoine Latter wrote:

> On Thu, Feb 24, 2011 at 12:57 PM, Chung-chieh Shan wrote:
> > What
> > we need is a way to tell the garbage collector that the store reference
> > and the cell reference are both needed to access the data so the data
> > can be garbage-collected as soon as *either* the store reference *or
> > the cell reference* is.  (Analogy from the capabilities literature:
> > the key and the lock are both needed to open the door so the door can
> > be garbage-collected as soon as either the key or the lock is.)  Any
> > thoughts on how to achieve that?
>
> Here's a weak cell which is a candidate for GC as soon as either the
> cell or the key is lost:
> http://hpaste.org/44280/weak_ref_needing_both_halves

That's promising!  The lock I have in mind would probably be a map from
Int to weak pointers.  I'm unfamiliar with System.Mem.Weak so I'll have
to study this code further.  What is "addFinalizer lock (finalize wk)"
for?  It seems wk doesn't have any finalizers to run.

Thanks!

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st graffitiist: QUESTION AUTHORITY!
2nd graffitiist: Why?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Antoine Latter-2
On Thu, Feb 24, 2011 at 10:15 PM, Chung-chieh Shan
<[hidden email]> wrote:

> On 2011-02-24T16:20:46-0600, Antoine Latter wrote:
>> On Thu, Feb 24, 2011 at 12:57 PM, Chung-chieh Shan wrote:
>> > What
>> > we need is a way to tell the garbage collector that the store reference
>> > and the cell reference are both needed to access the data so the data
>> > can be garbage-collected as soon as *either* the store reference *or
>> > the cell reference* is.  (Analogy from the capabilities literature:
>> > the key and the lock are both needed to open the door so the door can
>> > be garbage-collected as soon as either the key or the lock is.)  Any
>> > thoughts on how to achieve that?
>>
>> Here's a weak cell which is a candidate for GC as soon as either the
>> cell or the key is lost:
>> http://hpaste.org/44280/weak_ref_needing_both_halves
>
> That's promising!  The lock I have in mind would probably be a map from
> Int to weak pointers.  I'm unfamiliar with System.Mem.Weak so I'll have
> to study this code further.  What is "addFinalizer lock (finalize wk)"
> for?  It seems wk doesn't have any finalizers to run.
>

I was confused by GHC weak references for some time.

GHC Weak references have the following parts:

* a key
* a value
* finalizers attached to the key

Setting up a weak reference to a value ties the value's liveness to
the key's liveness (even if the weak reference itself is dead).

Calling 'finalize' on the weak reference breaks the link between the
weak reference, and runs the finalizers attached to the key.

So here, we attach a finalizer to the "Lock" structure which then
breaks the link between the key and the value (this doesn't break the
link from the weak ref to the value, it simply stops the key from
keeping the value alive).

This might not be entirely safe in the face of some optimizations -
finalizers on ForeignPtrs and MVars are odd, to work around other
oddities that I don't yet grasp.

Antoine

> Thanks!
>
> --
> Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
> 1st graffitiist: QUESTION AUTHORITY!
> 2nd graffitiist: Why?
>
>
> _______________________________________________
> 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
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Daryoush Mehrtash-2
In reply to this post by Chung-chieh Shan
I am confused about this comment:
 
Mostly we preferred (as do the domain experts we target) to write
probabilistic models in direct style rather than monadic


In the haskell implementation of the lawn model there are two different version of the grassModel (https://github.com/rst76/probability/blob/master/src/Lawn.hs)

grassModel :: PM Bool
grassModel =
  let_ (flip_ 0.3) (\ rain ->
  let_ (flip_ 0.5) (\ sprinkler ->
  let_ (dis (con (flip_ 0.9) rain)
            (dis (con (flip_ 0.8) sprinkler)
                 (flip_ 0.1))) (\ grassIsWet ->
  if_ grassIsWet rain (dist []))))


and

grassModel = do
rain <- flip_ 0.3
sprinkler <- flip_ 0.5
wetInRain <- flip_ 0.9
wetInSprinkler <- flip_ 0.8
wetInOther <- flip_ 0.1
let grassIsWet = rain && wetInRain
|| sprinkler && wetInSprinkler
|| wetInOther
if grassIsWet then return rain else dist []

By domain expert preferring direct style do you mean that they prefer the first version over the 2nd version?

thanks,

Daryoush



On Wed, Feb 23, 2011 at 7:52 AM, Chung-chieh Shan <[hidden email]> wrote:
Hello!  Thank you for your interest.

Daryoush Mehrtash <[hidden email]> wrote in haskell-cafe:
> Is the "Embedded domain-specific language HANSEI for probabilistic models
> and (nested) inference"  described in:
> http://okmij.org/ftp/kakuritu/index.html#implementation  available in
> Haskell?

The closest to that I know of is this one:
 http://d.hatena.ne.jp/rst76/20100706
 https://github.com/rst76/probability

Or you can apply this monad transformer to a probability monad:
 http://sebfisch.github.com/explicit-sharing/

> Is there a reason why the author did the package in Ocaml
> rather than Haskell?

Mostly we preferred (as do the domain experts we target) to write
probabilistic models in direct style rather than monadic style.
Haskell's laziness doesn't help -- in fact, to avoid running out of
memory, we'd have to defeat that memoization by sprinkling "() ->"
throughout the types.

--
Edit this signature at <a href="http://www.digitas.harvard.edu/cgi-bin/ken/sig 1st" target="_blank">http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st graffitiist: QUESTION AUTHORITY!
2nd graffitiist: Why?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



--
Daryoush

Weblog:  http://onfp.blogspot.com/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Chung-chieh Shan
Daryoush Mehrtash <[hidden email]> wrote in haskell-cafe:
> I am confused about this comment:
> > Mostly we preferred (as do the domain experts we target) to write
> > probabilistic models in direct style rather than monadic
>
> In the haskell implementation of the lawn model there are two different
> version of the grassModel (
> https://github.com/rst76/probability/blob/master/src/Lawn.hs)...
> By domain expert preferring direct style do you mean that they prefer
> the first version over the 2nd version?

No, there is no way to write probabilistic models in direct style in
Haskell, and domain experts prefer neither Haskell version you showed.

A symptom of direct style is being able to write something like

    flip 0.3 && flip 0.5

where (&&) takes two Bool arguments.

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st graffitiist: QUESTION AUTHORITY!
2nd graffitiist: Why?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Daryoush Mehrtash-2
I see the problem now.  But I am confused as to why there are no Bool class (like Num, Fractional...) in Haskell.   If I had such a class then the problem is solved, (by making the "pm a" an instance of it) right?  Or are there still more issues that I am not seeing?

thanks,

daryoush

On Mon, Feb 28, 2011 at 7:34 AM, Chung-chieh Shan <[hidden email]> wrote:
Daryoush Mehrtash <[hidden email]> wrote in haskell-cafe:
> I am confused about this comment:
> > Mostly we preferred (as do the domain experts we target) to write
> > probabilistic models in direct style rather than monadic
>
> In the haskell implementation of the lawn model there are two different
> version of the grassModel (
> https://github.com/rst76/probability/blob/master/src/Lawn.hs)...
> By domain expert preferring direct style do you mean that they prefer
> the first version over the 2nd version?

No, there is no way to write probabilistic models in direct style in
Haskell, and domain experts prefer neither Haskell version you showed.

A symptom of direct style is being able to write something like

   flip 0.3 && flip 0.5

where (&&) takes two Bool arguments.

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st
graffitiist: QUESTION AUTHORITY!
2nd graffitiist: Why?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



--
Daryoush

Weblog:  http://onfp.blogspot.com/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: HANSEI in Haskell?

Chung-chieh Shan
Daryoush Mehrtash <[hidden email]> wrote in article <AANLkTim0LTOviud2fyzU7NAsraQMuCKa=[hidden email]> in gmane.comp.lang.haskell.cafe:
> I see the problem now.  But I am confused as to why there are no Bool class
> (like Num, Fractional...) in Haskell.   If I had such a class then the
> problem is solved, (by making the "pm a" an instance of it) right?  Or are
> there still more issues that I am not seeing?

Sorry, I gave a bad example.  Here are two more general symptoms of
direct style: being able to write something like

    f (if flip 0.3 then LT else EQ)

where f is an existing function that takes an Ordering argument, and
even being able to write something like

    and (map flip [0.3, 0.5])

where and :: [Bool] -> Bool
      map :: (a -> b) -> [a] -> [b]
are existing functions.

--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
1st graffitiist: QUESTION AUTHORITY! 2nd graffitiist: Why?


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe