[Haskell-cafe] Monadic design patterns for the web Kickstarter project

[Greg Meredith]

Dear Haskellians,

Last week i went in to record the 2nd and 3rd installments of the C9 monadic
design patterns for the web videos. Charles Torre, the series producer, told
me there were over 40K distinct views of the first video. i know that many
of them came from this community. So, i really want to say thanks!

i also want to mention that i just initiated a Kickstarter
projectto
raise enough money to complete the book. i've been finding that i'm at
a
point where the book needs a certain level of focus that doesn't mix well
with juggling a ton of clients. i'm trying to raise just enough that i can
clear off my desk and focus on completing the book and the source code that
supports it. So, if it's of interest please let your friends and cronies
know and donate yourself, if you can. For your amusement, here's a little
video about it .

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com




-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Monads in the 'hood

[Greg Meredith]

Dear Haskellians,

Keepin' it light. For your amusement this weekend: monads in the
hood
.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Monadic Design Patterns for the Web C9 Video Series -- Part 2 is live!

[Greg Meredith]

Dear Haskellians,

Just in time for the Holidays!

Best wishes,

--greg

-- Forwarded message --
From: Charles Torre 
Date: Tue, Dec 14, 2010 at 11:31 AM
Subject: Part 2 is live!
To: Meredith Gregory 


Hi Greg!



Part 2 is now live on 9. Front and center:
http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic-Design-Patterns-for-the-Web-2-of-n


Thank you! See you in the new year to continue with this great series.



Best,

C



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Fwd: C9 video in the Monadic Design Patterns for the Web series

[Greg Meredith]

Dear Haskellians,

A new C9 video in the series!

So, you folks already know most of this... except for maybe the
generalization of the Conway construction!

Best wishes,

--greg

-- Forwarded message --
From: Charles Torre <...>
Date: Tue, Jul 26, 2011 at 1:12 PM
Subject: C9 video in the Monadic Design Patterns for the Web series
To: Meredith Gregory 
Cc: Brian Beckman <...>


 And we’re live!

** **

http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic-Design-Patterns-for-the-Web-4-of-n


C

** **

*From:* Charles Torre
*Sent:* Tuesday, July 26, 2011 11:51 AM
*To:* 'Meredith Gregory'
*Cc:* Brian Beckman
*Subject:* C9 video in the Monadic Design Patterns for the Web series

** **

Here it ‘tis:

** **

Greg Meredith <http://biosimilarity.blogspot.com/>, a mathematician and
computer scientist, has graciously agreed to do a C9 lecture series covering
monadic design principles applied to web development. You've met Greg before
in a Whiteboard jam session with Brian
Beckman<http://channel9.msdn.com/shows/Going+Deep/E2E-Whiteboard-Jam-Session-with-Brian-Beckman-Greg-Meredith-Monads-and-Coordinate-Systems/>
.

The fundamental concept here is the monad, and Greg has a novel and
conceptually simplified explanation of what a monad is and why it matters.
This is a very important and required first step in the series since the
whole of it is about the application of monadic composition to real world
web development.

In *part 4, *Greg primarily focuses on the idea that *a monad is really an
API* -- it's a view onto the organization of data and control structures,
not those structures themselves. In OO terms, it's an *interface*. To make
this point concrete Greg explores one of the simplest possible data
structures that supports at least two different, yet consistent
interpretations of the same API. The structure used, Conway's partisan
games<http://mathworld.wolfram.com/ConwayGame.html>,
turned out to be tailor-made for this investigation. Not only does this data
structure have the requisite container-like shape, it provided opportunities
to see just what's necessary in a container to implement the monadic
interface. ** **

Running throughout the presentation is a more general comparison of reuse
between an OO approach versus a more functional one. When the monadic API is
"mixed into" the implementing structure we get less reuse than when the
implementing structure is passed as a type parameter. Finally, doing the
work put us in a unique position to see not just how to generalize Conway's
construction, *monadically*, but the underlying pattern which allows the
generalization to suggest itself.

See *part 1
<http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic-Design-Patterns-for-the-Web-Introduction-to-Monads>
*See *part 
2<http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic-Design-Patterns-for-the-Web-2-of-n>
**
*See* part 
3<http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic-Design-Patterns-for-the-Web-3-of-n>
*

**
-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW
Seattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com




-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Fwd: C9 video in the Monadic Design Patterns for the Web series

[Greg Meredith]

Dear James,

This is so cool! It's so natural to express this as a monad transformer.
It's great insight and it's just the sort of insight that Haskell and this
way of thinking about computation makes possible. Bravo!

Best wishes,

--greg

On Wed, Jul 27, 2011 at 6:33 AM, James Cook  wrote:

> Dang, I should have played with both versions before sending this.  The 'R'
> instance has a very obvious error:
>
> >return x = R (ConwayT (return (Left x)) mzero)
>
> should be changed to
>
> >return x = R (ConwayT mzero (return (Left x)))
>
> Sorry!
>
> -- James
>
> On Jul 27, 2011, at 9:28 AM, James Cook wrote:
>
> For any who are interested, here's a quick and dirty Haskell version of the
> generalized Conway game monad transformer described in the video.  It uses
> two newtypes, "L" and "R", to select from two possible implementations of
> the Monad class.
>
> (all the LANGUAGE pragmas are just to support a derived Show instance to
> make it easier to play around with in GHCi - the type and monad itself are
> H98)
>
> -- James
>
>
> > {-# LANGUAGE StandaloneDeriving #-}
> > {-# LANGUAGE FlexibleInstances #-}
> > {-# LANGUAGE UndecidableInstances #-}
> > module Monads.Conway where
> >
> > import Control.Applicative
> > import Control.Monad
> >
> > data ConwayT m a
> > = ConwayT
> > { runLeftConwayT  :: m (Either a (ConwayT m a))
> > , runRightConwayT :: m (Either a (ConwayT m a))
> > }
> >
> > deriving instance (Eq   a, Eq   (m (Either a (ConwayT m a => Eq
> (ConwayT m a)
> > deriving instance (Ord  a, Ord  (m (Either a (ConwayT m a => Ord
>  (ConwayT m a)
> > deriving instance (Read a, Read (m (Either a (ConwayT m a => Read
> (ConwayT m a)
> > deriving instance (Show a, Show (m (Either a (ConwayT m a => Show
> (ConwayT m a)
> >
> > instance Functor m => Functor (ConwayT m) where
> > fmap f (ConwayT l r) = ConwayT (fmap g l) (fmap g r)
> > where
> > g (Left  x) = Left (f x)
> > g (Right x) = Right (fmap f x)
> >
> > bind liftS (ConwayT l r) f = ConwayT
> > (liftS g l)
> > (liftS g r)
> > where
> > g (Left  x) = Right (f x)
> > g (Right x) = Right (bind liftS x f)
> >
> > newtype L f a = L { runL :: f a } deriving (Eq, Ord, Read, Show)
> >
> > instance Functor m => Functor (L (ConwayT m)) where
> > fmap f (L x) = L (fmap f x)
> >
> > instance MonadPlus m => Monad (L (ConwayT m)) where
> > return x = L (ConwayT (return (Left x)) mzero)
> > L x >>= f   = L (bind liftM x (runL . f))
> >
> > newtype R f a = R { runR :: f a } deriving (Eq, Ord, Read, Show)
> >
> > instance Functor m => Functor (R (ConwayT m)) where
> > fmap f (R x) = R (fmap f x)
> >
> > instance MonadPlus m => Monad (R (ConwayT m)) where
> > return x = R (ConwayT (return (Left x)) mzero)
> > R x >>= f   = R (bind liftM x (runR . f))
>
>
>
>
> On Jul 27, 2011, at 4:31 AM, Greg Meredith wrote:
>
> Dear Haskellians,
>
> A new C9 video in the series!
>
> So, you folks already know most of this... except for maybe the
> generalization of the Conway construction!
>
> Best wishes,
>
> --greg
>
> -- Forwarded message --
> From: Charles Torre <...>
> Date: Tue, Jul 26, 2011 at 1:12 PM
> Subject: C9 video in the Monadic Design Patterns for the Web series
> To: Meredith Gregory 
> Cc: Brian Beckman <...>
>
>
>  And we’re live!
>
> ** **
>
>
> http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic-Design-Patterns-for-the-Web-4-of-n
> 
>
> C
>
> ** **
>
> *From:* Charles Torre
> *Sent:* Tuesday, July 26, 2011 11:51 AM
> *To:* 'Meredith Gregory'
> *Cc:* Brian Beckman
> *Subject:* C9 video in the Monadic Design Patterns for the Web series
>
> ** **
>
> Here it ‘tis:
>
> ** **
>
> Greg Meredith <http://biosimilarity.blogspot.com/>, a mathematician and
> computer scientist, has graciously agreed to do a C9 lecture series covering
> monadic design principles applied to web development. You've met Greg before
> in a Whiteboard jam session with Brian 
> Beckman<http://channel9.msdn.com/shows/Going+Deep/E2E-Whiteboard-Jam-Session-with-Brian-Beckman-Greg-Meredith-Monads-and-Coordinate-Systems/>
> .
>
> The fundamental concept here is the monad, and Greg has a novel and
> conceptu

[Haskell-cafe] Contract opportunity with Biosimilarity LLC

[Greg Meredith]

Dear Haskellians,

No desire to spam, but some folks on this list might find this of interest.

Best wishes,

--greg

Biosimilarity LLC is looking for a the next Merlin! We need an artiste with
a certain taste and technical instinct that have attracted them to next
generation functional programming languages and other high magic. We need a
technologist who can make the demons and dragons of web front ends do their
bidding while making sound architectural and platform choices. Naturally,
comfort with the Open Source ecosystem from git and GitHub to mvn and/or sbt
to Jenkins is a given. For such a candidate we don't have to talk about
familiarity with Scala or Haskell or ML or JavaScript or Clojure because
they eat languages for breakfast and graphics libraries for lunch.
The initial engagement is for a limited contract. However, if things go
well, who knows what adventures await? The innovations and market potential
of the project are guaranteed to keep any sorcerer fascinated. And, you'll
get a chance to work with a team of like-minded magicians with long track
records of delivering landmark software. While Biosimilarity is a
Seattle-based company, telecommuting is definitely an option for the right
candidate. If you feel like this might be you, please contact me directly at
this email or via the number provided below. Sending along a CV in advance
of a more personable communication is likely to be the most effective
protocol, but we're always open to creativity. An online portfolio of web
projects could also be an advantage, but again raw creativity and can-do
carry the day here.

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Monadic Design Patterns for the Web Chapter Review

[Greg Meredith]

*Dear Supporters, Friends and Colleagues,

i’m writing to you to say that i will be going over the material in
Chapters 3 through 9 of the book, MDP4tW in a Google+ hangout, 1 Chapter /
week. If any would like to participate in reviewing the material presented,
please let me know. i will limit participation in these reviews to 5 people
/ session with preference give to people who contributed to the Kickstarter
campaign. Please RSVP to me at lgreg.mered...@gmail.com and i will let you
know the dates and times.*

Best wishes,

--greg


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: how would Albus Dumbledore sell Haskell

[Greg Meredith]

Simon,

Regarding Justin Bailey's idea of a calculator -- here's a twist. There is
some sample Haskell code of Conway's account of numbers as games floating
around the internet (http://www.dcs.ed.ac.uk/home/pgh/conway.html,
http://www.dcs.ed.ac.uk/home/pgh/Conway.lhs). i can't vouch for the code as
i have not read it in anger. However, i've always thought it would be fun to
do the standard calculator example, but with Conway games on the back end
for doing the arithemetic.

Some of the attractions:

  - you could have another set of buttons for displaying the games
  respresentation of the numbers
  - you could really emphasize the polymorphism of the basic operations
  - you could emphasize the use of laziness for calculations involving
  infinitary entities
  - you could explain Conway games (which are an intellectual treat for
  those who never seen them and just get better and better the more you return
  to them)

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: haskell question

[Greg Meredith]

Oleg,

Many thanks for your help! i notice that the code you sent requires
-fglasgow-exts to be syntactically correct. Is there documentation on the
multi-parameter type classes? i think i see what you've done, but i'd like
to read up on it to make sure that i understand.

Best wishes,

--greg

On 4/20/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:



Greg Meredith wrote:
> The file compiles with ghc as is. If you uncomment the last
> section, however, you see that to close the loop on the constraints for
the
> agent syntax we hit a typing error. i think this is a hard
> constraint in Haskell that prevents this level of generality in the
> specification, but maybe you can see a way around it.

I believe the Haskell typechecker is right

> instance (Eq n, Eq p) =>
>  CoreAgentSyntax (MinimalAgentSyntax n p) where
>   bind [] proc = Thunk (\() -> proc)
>
> data MinimalAgentSyntax n p =
>  Thunk (() -> p)
>  | Abstraction ([n] -> p)
>  | Concretion [n] p

The bind method has the signature

bind :: (CoreProcessSyntax p, CoreAgentSyntax x) => [n] -> (p a x) ->
x

That is: for any agent x and for _any_ process p (regardless of x), we
should be able to perform the bind operation. The signature for bind
proclaims total independence between 'p' and 'x'. However, when we
define the instance

>  CoreAgentSyntax (MinimalAgentSyntax n p) where
>   bind [] proc = Thunk (\() -> proc)

we see that process proc and the agent aren't totally independent: the
result of bind has the type 'MinimalAgentSyntax n process' and thus is
dependent on the 'process == p a x'. We have broken our previously
made independence proclamation, and so the typechecker rightfully
complaints.

The following is one solution. It works sans the line marked TODO. I'm
not sure that line is correct:

--  -- TODO : lgm : need to substitute m for n in proc
--  bind (name:names) proc = Abstraction (\m -> bind names proc)

According to the type of Abstraction, 'bind names proc' should have
the type 'p', that is, the same type as proc. It should be a
process. OTH, bind returns an agent. Something is amiss here.


{-# OPTIONS -fglasgow-exts #-}

module Core where

-- What's in a name?

class Nominal n where
nominate :: i -> n i

newtype Name i = Nominate i deriving Eq

instance Nominal Name where nominate i = Nominate i

-- Where are we?

class Locality a where
locate :: (Eq s, Nominal n) => s -> (n i) -> a s (n i)
name :: (Eq s, Nominal n) => a s (n i) -> (n i)

data Location s n = Locate s n deriving Eq

instance Locality Location where
   locate s n = Locate s n
   name (Locate s n) = n


-- Constraints

class CoreProcessSyntax p a x | p -> a x where
zero :: p
sequence :: a -> x -> p
compose :: [p] -> p

class CoreAgentSyntax x p n | x -> p n where
bind  :: [n] -> p -> x
offer :: [n] -> p -> x

-- Freedom (as in freely generated)

data MinimalProcessSyntax l x =
 Null
 | Sequence l x
 | Composition [MinimalProcessSyntax l x]

data MinimalAgentSyntax n p =
 Thunk (() -> p)
 | Abstraction ([n] -> p)
 | Concretion [n] p

-- Constraining freedom

instance CoreProcessSyntax (MinimalProcessSyntax l x) l x where
 zero = Null
 sequence l a = Sequence l a
 compose [] = zero
 compose ps = Composition ps

instance CoreAgentSyntax (MinimalAgentSyntax n p) p n where
  bind [] proc = Thunk (\() -> proc)

--  -- TODO : lgm : need to substitute m for n in proc
--  bind (name:names) proc = Abstraction (\m -> bind names proc)
  -- here's the possible implementation. I don't know if it's right.
  -- But at least it types
  bind (name:names) proc = Abstraction (\m -> comp $ bind names proc)
  where comp (Thunk f) = f ()
-- comp (Concretion n p) = ...
  offer names proc = Concretion names proc





--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: haskell question

[Greg Meredith]

Oleg,

Many thanks. i also found some course notes from Advance Functional
Programming at Utrecht very useful. i have to wait until i have quality time
to go over this because the next step is to close the final loop to find the
fix point of

  - Process = Process(Nominate(Process))

i haven't worked out the correct instance syntax to express this idea. But,
i think the direction you pointed me in is the right one.

Best wishes,

--greg

On 4/22/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:



> Is there documentation on the multi-parameter type classes?

Sections 7.4.2. Class declarations, 7.4.3 Functional dependencies and
7.4.4. Instance declarations of the GHC user guide give the short
description of these features. These section refer to a couple of
papers. The best explanation can be found in papers by Mark P. Jones:
http://web.cecs.pdx.edu/~mpj/pubs.html
(see especially `qualified types').

> i think i see what you've done, but i'd like to read up on it to make
> sure that i understand.

The approach in the previous message was quite close to that used for
representing collections. The type of a particular collection implies
the type of collection's elements. In your case, the type of the agent
implies the type of the processor for that particular agent (and vice
versa). Incidentally, instance declarations can be recursive and
mutually recursive.





--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] On reflection

[Greg Meredith]

Oleg, Simon,

Thanks for your help. If i understand it correctly, the code below gives a
reasonably clean first cut at a demonstration of process calculi as
polymorphically parametric in the type of name, allowing for an
instantiation of the type in which the quoted processes play the role of
name. This is much, much cleaner and easier to read than the OCaml version.

Best wishes,

--greg

{-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-}

module Core(
   Nominal
  ,Name
  ,Locality
  ,Location
  ,CoreProcessSyntax
  ,CoreAgentSyntax
  ,MinimalProcessSyntax
  ,MinimalAgentSyntax
  ,ReflectiveProcessSyntax
--   ,make_process
  )
   where

-- What's in a name?

class Nominal n where
  nominate :: i -> n i

-- newtype Name i = Nominate i deriving (Eq, Show)
newtype Name i = Name i deriving (Eq, Show)

instance Nominal Name where nominate i = Name i

-- Where are we?

class Locality a where
  locate :: (Eq s, Nominal n) => s -> (n i) -> a s (n i)
  name :: (Eq s, Nominal n) => a s (n i) -> (n i)

-- data Location s n = Locate s n deriving (Eq, Show)
data Location s n = Location s n deriving (Eq, Show)

instance Locality Location where
 locate s n = Location s n
 name (Location s n) = n


-- Constraints

class CoreProcessSyntax p a x | p -> a x where
  zero :: p
  sequence :: a -> x -> p
  compose :: [p] -> p

class CoreAgentSyntax x p n | x -> p n where
  bind  :: [n] -> p -> x
  offer :: [n] -> p -> x

-- Freedom (as in freely generated)

data MinimalProcessSyntax l x =
   Null
   | Sequence l x
   | Composition [MinimalProcessSyntax l x]

data MinimalAgentSyntax n p =
   Thunk (() -> p)
   | Abstraction ([n] -> p)
   | Concretion [n] p

-- Responsibility : constraining freedom to enjoy order

instance CoreProcessSyntax (MinimalProcessSyntax l x) l x where
   zero = Null
   sequence l a = Sequence l a
   compose [] = zero
   compose ps = Composition ps

instance CoreAgentSyntax (MinimalAgentSyntax n p) p n where
   bind [] proc = Thunk (\() -> proc)
--  -- TODO : lgm : need to substitute m for name in proc
   bind (name:names) proc = Abstraction (\m -> comp $ bind names proc)
   where comp (Thunk fp) = fp ()
 -- comp (Abstraction abs) = abs name
   offer names proc = Concretion names proc

data ReflectiveProcessSyntax =
   Reflect
   (MinimalProcessSyntax
(Location [(Name ReflectiveProcessSyntax)] (Name
ReflectiveProcessSyntax))
(MinimalAgentSyntax (Name ReflectiveProcessSyntax)
ReflectiveProcessSyntax))

-- instance (CoreProcessSyntax p a x) =>
-- CoreProcessSyntax
-- (MinimalProcessSyntax
--  (Location
--   [(Name (MinimalProcessSyntax a x))]
--   (Name (MinimalProcessSyntax a x)))
--  (MinimalAgentSyntax
--   (Name (MinimalProcessSyntax a x))
--   (MinimalProcessSyntax a x)))
-- (Location
--   [(Name (MinimalProcessSyntax a x))]
--   (Name (MinimalProcessSyntax a x)))
-- (MinimalAgentSyntax
--   (Name (MinimalProcessSyntax a x))
--   (MinimalProcessSyntax a x))

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] efficient and/or lazy partitions of a multiset

[Greg Meredith]

HC-er's,

Find below some simple-minded code from a naive Haskeller for generating all
partitions of a multiset about which i have two questions.

mSplit :: [a] -> [([a], [a])]
mSplit [x] = [([x],[])]
mSplit (x:xs) = (zip (map (x:) lxs) rxs)
 ++ (zip lxs (map (x:) rxs))
 where (lxs,rxs) = unzip (mSplit xs)

  1. Is there a clever way to reduce the horrid complexity of the naive
  approach?
  2. How lazy is this code? Is there a lazier way?

i ask this in the context of checking statements of the form \phi * \psi |=
e_1 * ... * e_n where

  - [| \phi * \psi |] = { a \in U : a === b_1 * b_2, b_1 \in [| \phi |],
  b_2 \in [| \psi |] }
  - === is some congruence generated from a set of relations

A nice implementation for checking such statements will iterate through the
partitions, generating them as needed, checking subconditions and stopping
at the first one that works (possibly saving remainder for a rainy day when
the client of the check decides that wasn't the partition they meant).

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: efficient and/or lazy partitions of a multiset

[Greg Meredith]

Henning,

In your reply, you made a number of interesting suggestions. You could also
have written

mSplitC :: [a] -> [([a], [a])] -- C for comprehension

mSplitC [] = [([],[])]
mSplitC [x] = [([x],[])]
mSplitC (x:xs) = concat [ [(x:l,r),(l,x:r)] | (l,r) <- mSplitC xs ]

which Matthias Radestock suggested to me.

Note that if you only supply the empty multiset case, then you end up with
duplicates.

mSplitCD :: [a] -> [([a], [a])]
mSplitCD [] = [([],[])]
mSplitCD (x:xs)  = concat [[(x:l,r),(l,x:r)] | (l,r) <- mSplitCD xs]

*Zoup> mSplitCD [1,2,3]
[([1,2,3],[]),([2,3],[1]),([1,3],[2]),([3],[1,2]),([1,2],[3]),([2],[1,3]),([1],[2,3]),([],[1,2,3])]

*Zoup> mSplitC [1,2,3]
[([1,2,3],[]),([2,3],[1]),([1,3],[2]),([3],[1,2])]
*Zoup>

Is there anyway to peer under the hood to see the code being generated? i
notice, for example, that the original concat/zip-based implementation
occasionally comes in quite a bit faster that the comprehension based
example.

Best wishes,

--greg


On 5/21/07, Greg Meredith <[EMAIL PROTECTED]> wrote:


HC-er's,

Find below some simple-minded code from a naive Haskeller for generating
all partitions of a multiset about which i have two questions.

mSplit :: [a] -> [([a], [a])]
mSplit [x] = [([x],[])]
mSplit (x:xs) = (zip (map (x:) lxs) rxs)
  ++ (zip lxs (map (x:) rxs))
  where (lxs,rxs) = unzip (mSplit xs)

   1. Is there a clever way to reduce the horrid complexity of the
   naive approach?
   2. How lazy is this code? Is there a lazier way?

i ask this in the context of checking statements of the form \phi * \psi
|= e_1 * ... * e_n where

   - [| \phi * \psi |] = { a \in U : a === b_1 * b_2, b_1 \in [| \phi
   |], b_2 \in [| \psi |] }
   - === is some congruence generated from a set of relations

A nice implementation for checking such statements will iterate through
the partitions, generating them as needed, checking subconditions and
stopping at the first one that works (possibly saving remainder for a rainy
day when the client of the check decides that wasn't the partition they
meant).

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com





--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: efficient and/or lazy partitions of a multiset

[Greg Meredith]

Henning,

i need the bi-partitions of a multiset. That is, all the ways you can split
a multiset, M, into two multisets, M1 and M2, such that M = M1
`multiset-union` M2.

Best wishes,

--greg

On 5/23/07, Henning Thielemann <[EMAIL PROTECTED]> wrote:



On Tue, 22 May 2007, Greg Meredith wrote:

> mSplitC :: [a] -> [([a], [a])] -- C for comprehension
>
> mSplitC [] = [([],[])]
> mSplitC [x] = [([x],[])]
> mSplitC (x:xs) = concat [ [(x:l,r),(l,x:r)] | (l,r) <- mSplitC xs ]
>
> which Matthias Radestock suggested to me.
>
> Note that if you only supply the empty multiset case, then you end up
with
> duplicates.

That is ([1,2],[3]) and ([3],[1,2]) are considered the same? But you need
always pairs not only [1,2] and [3] ?





--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Monads and constraint satisfaction problems (CSP)

[Greg Meredith]

All,

All this talk about Mathematica and a reference to monadic treatments of
backtracking reminded me that a year ago i was involved in work on a
Mathematica-like widget. At the time i noticed that a good deal of the
structure underlying LP, SAT and other solvers was terribly reminiscent of
comprehension-style monadic structure. i think i asked Erik Meijer if he
knew of any work done on this and posted to LtU, but nobody seemed to have
understood what i was mumbling about. So, let me try here: does anybody know
of references for a monadic treatment of constraint satisfaction?

BTW, i think this could have a lot of bang-for-buck because the literature i
read exhibited two basic features:

  - the "standard" treatments (even by CS-types) are decidedly not
  compositional
  - the people in the field who face industrial strength csp problems
  report that they have to take compositional approaches because the problems
  are just too large otherwise (both from a human engineering problem as well
  as a computational complexity problem)


Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Monads and constraint satisfaction problems (CSP)

[Greg Meredith]

Brandon, Jeremy, et al,

Thanks for the pointers. The paper by OlegK, et al, articulates exactly the
structure i was noticing, except that i was coming at it from the other end.
i was noticing that a wide range of these CSP-style problems could be
decomposed into a trivial monad (e.g., list, multiset, set) and some
additional search machinery (over which a good solution should be
parametric). They show how to add a reasonable upper limit on the search
machinery to any monad.

Best wishes,

--greg

Date: Thu, 31 May 2007 11:36:55 -0700

From: "Jeremy Shaw" <[EMAIL PROTECTED]>
Subject: Re: [Haskell-cafe] Monads and constraint satisfaction
   problems (CSP)
To: "Greg Meredith" <[EMAIL PROTECTED]>
Cc: haskell-cafe 
Message-ID: <[EMAIL PROTECTED]>
Content-Type: text/plain; charset=US-ASCII

At Thu, 31 May 2007 10:42:57 -0700,
Greg Meredith wrote:

> BTW, i think this could have a lot of bang-for-buck because the
literature i
> read exhibited two basic features:
>
>- the "standard" treatments (even by CS-types) are decidedly not
>compositional
>- the people in the field who face industrial strength csp problems
>report that they have to take compositional approaches because the
problems
>are just too large otherwise (both from a human engineering problem
as well
>as a computational complexity problem)

This paper describes a non-monadic, compositional method for solving CSPs:


http://www.cse.ogi.edu/PacSoft/publications/2001/modular_lazy_search_jfp.pdf

There is also the LogicT monad transformer:

http://okmij.org/ftp/Computation/monads.html

j.



--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Java Monads?

[Greg Meredith]

HaskellyCaffeinated,

i noticed that there was a JavaMonad lib kicking around on the web, but all
the links i can find are stale. Does anybody have a live pointer to this
lib?

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] copy-on-write monad?

[Greg Meredith]

Fellow Functionally-Caffeinated,

i have a few questions regarding copy-on-write semantics. i am working for a
client that is stuck with a legacy in-house language that chose
copy-on-write as a way to provide aliasing-issue-free semantics to a user
population they perceived as not sophisticated in programming. Despite the
fact that they are now realizing there are a lot of very sophisticated and
performant ways of providing ways to avoid aliasing problems, they are stuck
having to support copy-on-write for legacy codes.

So, i have two basic questions. First, has anyone worked out a monadic
approach to copy-on-write? (And, Is there any analysis of perf
characteristics of said monadic schemes?)

Second, i have worked out a scheme which is like a version control system.
The mutable collection is treated like a source tree. A reference to a
mutable collection is like a tag for a branch of the tree. Updates attach
deltas to a given branch of the tree. Accesses have to be matched to see if
they are impacted by any update-deltas. There is an
optimization/memo-ization strategy in which certain events (access or
update) trigger a copy to be made, finally, and the updates applied to the
copy. This shifts perf characteristics so that access becomes slower and
update considerably faster in the common case. Does anyone know if such a
scheme has been studied? i'd like to compare implementations, too, if
possible.

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: copy-on-write monad?

[Greg Meredith]

Oleg,

Once again, many thanks. This is great info. BTW, i realized that my
approach has an underlying process algebraic formulation. Roughly speaking,
you can think of the mutable collection as a tuple space in which the names
of the tuple space are the mutable locations in the collection. Updates
correspond to persistent (i.e. replicated) outputs, accesses correspond to
inputs. There is a natural interpretation of this approach in terms of
delimited continuations; but, i think the other way round -- interpreting
delimited continuations in terms of process algebraic operations -- is
actually more natural.

Best wishes,

--greg

On 6/23/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:



Greg Meredith wrote:
> First, has anyone worked out a monadic
> approach to copy-on-write? (And, Is there any analysis of perf
> characteristics of said monadic schemes?)

If you use Zippers (Huet's or generic ones) with functional updates,
copy-on-write comes out automatically and by default. This is
explained in
http://okmij.org/ftp/Computation/Continuations.html#zipper
and, in a more readable form, in a recent paper
http://okmij.org/ftp/papers/context-OS.pdf

The web page also contains the complete code.





--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] let vs do?

[Greg Meredith]

Haskellians,

Once you have a polymorphic let, why do you need 'let' in the base language,
at all? Is it possible to formulate Haskell entirely with do-notation where
there is a standard monad for let environments? Probably this was all
discussed before in the design deliberations for the language standard.
Pointers would be very much appreciated.

Best wishes,

--greg

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] let vs do?

[Greg Meredith]

Thomas,

Thanks for the reply. My thinking was that once you have a polymorphic form,
why single out any other? Less moving parts makes for less maintenance, etc.

Best wishes,

--greg

On 6/28/07, Thomas Schilling <[EMAIL PROTECTED]> wrote:



On 28 jun 2007, at 21.17, Greg Meredith wrote:
>
> Once you have a polymorphic let, why do you need 'let' in the base
> language, at all? Is it possible to formulate Haskell entirely with
> do-notation where there is a standard monad for let environments?
> Probably this was all discussed before in the design deliberations
> for the language standard. Pointers would be very much appreciated.
>

   let x = ... in ...

is only equal

   do x <- ...; ...

in the Identity monad.  Also, why would "do" be more primitive than
"let".  That way you would have to use monads everywhere.  Also, let
is treated specially by the type checker (IIRC) and there are many,
many other reasons not to do that.

Why would you consider the syntactic sugar do { x <- e; .. } which is
just a different way of writing function binding (e >>= \x -> ...)
consider more primitive than "let"?

/ Thomas






--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] let vs do?

[Greg Meredith]

Thomas, Stefan,

Thanks for a most edifying exchange! i will reflect on this.

Best wishes,

--greg

On 6/28/07, Stefan Holdermans <[EMAIL PROTECTED]> wrote:


Thomas,

>   let x = ... in ...
>
> is only equal
>
>   do x <- ...; ...
>
> in the Identity monad.  Also, why would "do" be more primitive than
> "let".  That way you would have to use monads everywhere.  Also,
> let is treated specially by the type checker (IIRC) and there are
> many, many other reasons not to do that.

As you already hinted at in a later message, this has to do with let-
bindings being potentially polymorphic and monadic bindings being
necessarily monomorphic:

   import Control.Monad.Identity
   foo =   let id =  \x -> x  in(id 'x',
id 42) -- well-typed
   bar = runIdentity $ do  id <- return (\x -> x) ;  return (id 'x',
id 42) -- ill-typed

Cheers,

   Stefan





--
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] monads and groups -- instead of loops

[Greg Meredith]

Haskellians,

Though the actual metaphor in the monads-via-loops doesn't seem to fly with
this audience, i like the spirit of the communication and the implicit
challenge: find a pithy slogan that -- for a particular audience, like
imperative programmers -- serves to uncover the essence of the notion. i
can't really address that audience as my first real exposure to programming
was scheme and i moved into concurrency and reflection after that and only
ever used imperative languages as means to an end. That said, i think i
found another metaphor that summarizes the notion for me. In the same way
that the group axioms organize notions of symmetry, including addition,
multiplication, reflections, translations, rotations, ... the monad(ic
axioms) organize(s) notions of snapshot (return) and update (bind),
including state, i/o, control,  In short

group : symmetry :: monad : update

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] monads and groups -- instead of loops

[Greg Meredith]

Andrew,

;-) Agreed! As i said in my previous post, i can't address the imperative
programmer. i really don't think that way and have a hard time understanding
people who do! (-;

Best wishes,

--greg

On 8/1/07, Andrew Wagner <[EMAIL PROTECTED]> wrote:
>
> That's great, unless the imperative programmer happens to be one of
> the 90% of programmers that isn't particularly familiar with group
> theory...
>
> On 8/1/07, Greg Meredith <[EMAIL PROTECTED]> wrote:
> > Haskellians,
> >
> > Though the actual metaphor in the monads-via-loops doesn't seem to fly
> with
> > this audience, i like the spirit of the communication and the implicit
> > challenge: find a pithy slogan that -- for a particular audience, like
> > imperative programmers -- serves to uncover the essence of the notion. i
> > can't really address that audience as my first real exposure to
> programming
> > was scheme and i moved into concurrency and reflection after that and
> only
> > ever used imperative languages as means to an end. That said, i think i
> > found another metaphor that summarizes the notion for me. In the same
> way
> > that the group axioms organize notions of symmetry, including addition,
> > multiplication, reflections, translations, rotations, ... the monad(ic
> > axioms) organize(s) notions of snapshot (return) and update (bind),
> > including state, i/o, control,  In short
> >
> > group : symmetry :: monad : update
> >
> > Best wishes,
> >
> > --greg
> >
> > --
> > L.G. Meredith
> > Managing Partner
> > Biosimilarity LLC
> > 505 N 72nd St
> > Seattle, WA 98103
> >
> > +1 206.650.3740
> >
> > http://biosimilarity.blogspot.com
> > ___
> > Haskell-Cafe mailing list
> > Haskell-Cafe@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: monads and groups -- instead of loops

[Greg Meredith]

Haskellians,

But, along these lines i have been wondering for a while... the monad laws
present an alternative categorification of monoid. At least it's alternative
to monoidoid. In the spirit of this thought, does anyone know of an
expansion of the monad axioms to include an inverse action? Here, i am
following an analogy

monoidoid : monad :: groupoid : ???

i did a search of the literature, but was probably using the wrong
terminology to try to find references. i would be very grateful for anyone
who might point me in the right direction.

My intuition tells me this could be quite generally useful to computing in
situation where boxing and updating have natural (or yet to be discovered)
candidates for undo operations. i'm given to understand reversible computing
might be a good thing to be thinking about if QC ever gets real... ;-)

Best wishes,

--greg

On 8/1/07, Greg Meredith <[EMAIL PROTECTED]> wrote:
>
> Haskellians,
>
> Though the actual metaphor in the monads-via-loops doesn't seem to fly
> with this audience, i like the spirit of the communication and the implicit
> challenge: find a pithy slogan that -- for a particular audience, like
> imperative programmers -- serves to uncover the essence of the notion. i
> can't really address that audience as my first real exposure to programming
> was scheme and i moved into concurrency and reflection after that and only
> ever used imperative languages as means to an end. That said, i think i
> found another metaphor that summarizes the notion for me. In the same way
> that the group axioms organize notions of symmetry, including addition,
> multiplication, reflections, translations, rotations, ... the monad(ic
> axioms) organize(s) notions of snapshot (return) and update (bind),
> including state, i/o, control,  In short
>
> group : symmetry :: monad : update
>
> Best wishes,
>
> --greg
>
> --
> L.G. Meredith
> Managing Partner
> Biosimilarity LLC
> 505 N 72nd St
> Seattle, WA 98103
>
> +1 206.650.3740
>
> http://biosimilarity.blogspot.com




-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: monads and groups -- instead of loops

[Greg Meredith]

Arie,

Thanks for your thoughtful reply. Comments in-lined.

Best wishes,

--greg

Date: Thu, 2 Aug 2007 03:06:51 +0200 (CEST)
> From: "Arie Peterson" <[EMAIL PROTECTED]>
> Subject: Re: [Haskell-cafe] Re: monads and groups -- instead of loops
> To: haskell-cafe@haskell.org
> Message-ID: < [EMAIL PROTECTED]>
> Content-Type: text/plain;charset=iso-8859-1
>
> Math alert: mild category theory.
>
> Greg Meredith wrote:
>
> > But, along these lines i have been wondering for a while... the monad
> laws
> > present an alternative categorification of monoid. At least it's
> > alternative to monoidoid.
>
> I wouldn't call monads categorifications of monoids, strictly speaking.
> A monad is a monoid object in a category of endofunctors (which is a
> monoidal category under composition).


Sorry, i was being as fast and loose with the term as the rest of the
communities concerned with 'categorification' seem to be.

What do you mean by a 'monoidoid'? I only know it as a perverse synonym of
> 'category' :-).


Indeed.

> In the spirit of this thought, does anyone know of an
> > expansion of the monad axioms to include an inverse action? Here, i am
> > following an analogy
> >
> > monoidoid : monad :: groupoid : ???
>
> First of all, I don't actually know the answer.
>
> The canonical option would be a group object in the endofunctor category
> (let's call the latter C). This does not make sense, however: in order to
> formulate the axiom for the inverse, we would need the monoidal structure
> of C (composition of functors) to behave more like a categorical product
> (to wit, it should have diagonal morphisms diag :: m a -> m (m a) ).


It seems to me that there are two basic possibilities, here. One is that the
ambient categories over which one formulates computational monads are almost
always some type of Linear-Cartesian situation. So, you can possibly exploit
the additional structure there. That's certainly been the general flavor of
the situation that motivates me. Otherwise, you can go the route of trying
to excavate structure that might give meaningful interpretations. This has
appeal in that it is more general and might actually uncover something, but
as you observe it's not immediate.

i haven't wrestled with the idea in anger, yet, because i thought it such an
obvious thing to try that someone would have already done the work and was
hoping just to get a reference. Your note suggests that it might be worth
digging a little. i wonder... does a Hopf algebra-like structure do the job?

Maybe there is a way to get it to work, though. After all, what we (in FP)
> call a commutative monad, is not commutative in the usual mathematical
> sense (again, C does not have enough structure to even talk about
> commutativity).
>
>
> > My intuition tells me this could be quite generally useful to computing
> in
> > situation where boxing and updating have natural (or yet to be
> discovered)
> > candidates for undo operations. i'm given to understand reversible
> > computing
> > might be a good thing to be thinking about if QC ever gets real... ;-)
>
> If this structure is to be grouplike, the inverse of an action should be
> not only a post-inverse, but also a pre-inverse. Is that would you have in
> mind?
>
>
> (If I'm not making sense, please shout (or ignore ;-) ).)
>
>
> Greetings,
>
> Arie
>

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: RE [Haskell-cafe] Monad Description For Imperative

[Greg Meredith]

Ok,

You wrote

But please, let's keep one foot in the real world if possible.
> Monads were invented to solve the "how do I do imperative programming
> in a pure functional language" problem.
>

This is more than a little revisionist. Monads have been the subject of
mathematical study before people had an inkling that they might apply to
problems in computer science. Moggi didn't invent them, but noticed that
they might have an application to issues of composition in computation. It
is really intriguing that they do such a remarkable job of organizing
notions of update and were not invented with this application in mind. So,
revising history thus would be a real loss.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: RE [Haskell-cafe] Monad Description For Imperative

[Greg Meredith]

Haskellians,

i am delighted to see vigorous exchange that actually resulted in change of
positions. i confess i was going to give up, but glad others stepped into
the breach. This is yet another indication of what an unusual community this
is.

Best wishes,

--greg

Date: Fri, 3 Aug 2007 13:43:32 +1200
From: ok <[EMAIL PROTECTED]>
Subject: Re: RE [Haskell-cafe] Monad Description For Imperative
To: haskell-cafe Cafe 
Message-ID: <[EMAIL PROTECTED]>
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed

I asked "How is IO a functor"?

On 3 Aug 2007, at 11:50 am, Dan Piponi wrote:
> IO is a fully paid up Monad in the categorical sense. The category is
> the category whose objects are types and whose arrows are functions
> between those types. IO is a functor. The object a maps to IO a. An
> arrow f::a->b maps to (>>= return . f)::IO a -> IO b and that can be
> used to make IO an instance of Functor. The natural transforms eta and
> mu are called return and join.


Please go over this again, but slowly this time.
You have convinced me, but I'd like to understand the details a little
better.

I see that any type constructor TC :: * -> * is halfway to being a
functor
on this category of types.  It acts on the objects in the obvious way,
so the next step is to see about the arrows.

   If f :: a -> b then we want TC f :: TC a -> TC b

such that TC (f . g) = TC f . TC g and TC (id::a->a) = id :: TC a ->
TC a

Now this is precisely the Haskell Functor class, so TC is the object
part
and fmap is the arrow part.  You say that (>>= return . f) can be
used to
make [a Monad] an instance of Functor.  Try it... by golly it's true.
I see:  fmap f = (>>= return . f).

So why *aren't* Monads already set up using the type class machinery
to always *be* Functors in Haskell?  Isn't it bound to confuse people
if monads are functors but Monads are not Functors?

This is especially puzzling because Maybe, [], and IO already *are*
Functors, but the way this is done makes it look accidental, not like
the fundamental property of Monads it apparently is.

(By the way, I note that the on-line documentation for Control.Monad
glosses
 >>= as "Sequentially composes two actions...".)


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Monadic presentation of delimited continuations and dissection

[Greg Meredith]

Dear Haskellians,

After reading through the Dybvig, Jones and Sabry paper on the monadic
presentation of delimited continuations, it seems like one can come up with
a direct representation of the control contexts and meta continuations
framework as an instance of McBride's dissection mechanism. Do either of you
know if that work has already been done? McBride doesn't use that as an
example in his Clowns and Jokers paper.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] C9 video on monads and coordinate systems

[Greg Meredith]

Dear Haskellians,

You may be interested in this video i did with Brian
Beckman<http://channel9.msdn.com/shows/Going+Deep/E2E-Whiteboard-Jam-Session-with-Brian-Beckman-Greg-Meredith-Monads-and-Coordinate-Systems/>on
monads, location and coordinate systems.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] monadic design patterns for the web -- a 2 day, hands-on workshop

[Greg Meredith]

Dear Haskellians,

Biosimilarity and Stellar Scala Consulting will be running a 2 day workshop
in Seattle in September on monadic design patterns for the web. You can get
the details here .

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] C9 video on monads and coordinate systems

[Greg Meredith]

Dear Felipe,

Thanks for your note! Here's some quick and dirty code to get the point
across.

data T v = Constant Bool -- just to let us get off the ground...
| Mention v | Abstraction [v] (T v) | Application (T v) (T v)
deriving (Eq, Show)
data RN t = RN ( t, [((RN t), t)] ) deriving (Eq, Show)
data RT = RT (T (RN RT)) deriving (Eq, Show)

Best wishes,

--greg

On Thu, Jul 8, 2010 at 6:15 AM, Felipe Lessa  wrote:

> On Wed, Jul 7, 2010 at 8:00 PM, Greg Meredith
>  wrote:
> > Dear Haskellians,
> > You may be interested in this video i did with Brian Beckman on monads,
> > location and coordinate systems.
>
> Great, nice jamming! I wonder what's the URL of the Haskell code you
> have, however :).
>
> Cheers,
>
> --
> Felipe.
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] lambda terms in which the variables are positions in lambda terms

[Greg Meredith]

Dear Haskellians,

The following code may provide some amusement. i offer a free copy of
Barwise's Vicious Circles to the first person to derive deBruijn indices
from this presentation.

Best wishes,

--greg

-- -*- mode: Haskell;-*-
-- Filename:Term.hs
-- Authors: lgm
-- Creation:Tue Jul 20 16:37:37 2010
-- Copyright:   Not supplied
-- Description:
-- 

module Generators(
  Term
  , MuTerm
  , DoTerm
  , ReflectiveTerm
  , TermLocation
  , ClosedTermLocation
  , ClosedReflectiveTerm
  , unfoldLocation
  , unfoldTerm
  , makeMention
  , makeAbstraction
  , makeApplication
  , generateTerms
 )
where

-- M[V,A] = 1 + V + VxA + AxA
data Term v a =
 Divergence
 | Mention v
 | Abstraction v a
 | Application a a
   deriving (Eq, Show)

-- \mu M
data MuTerm v = MuTerm (Term v (MuTerm v)) deriving (Eq, Show)

-- \partial \mu M
data DoTerm v =
 Hole
 | DoAbstraction v (DoTerm v)
 | DoLeftApplication (DoTerm v) (MuTerm v)
 | DoRightApplication (MuTerm v) (DoTerm v)
   deriving (Eq, Show)

-- first trampoline
data ReflectiveTerm v = ReflectiveTerm (MuTerm (DoTerm v, ReflectiveTerm v))
deriving (Eq, Show)

-- second trampoline
data TermLocation v = TermLocation ((DoTerm v), (ReflectiveTerm v))
  deriving (Eq, Show)

-- first bounce
data ClosedTermLocation = ClosedTermLocation (TermLocation
ClosedTermLocation)
  deriving (Eq, Show)

-- second bounce
data ClosedReflectiveTerm =
ClosedReflectiveTerm (ReflectiveTerm ClosedTermLocation)
deriving (Eq, Show)

-- the isomorphisms implied by the trampolines
unfoldLocation ::
ClosedTermLocation
-> ((DoTerm ClosedTermLocation), (ReflectiveTerm
ClosedTermLocation))

unfoldLocation (ClosedTermLocation (TermLocation (k, t))) = (k, t)

unfoldTerm ::
ClosedReflectiveTerm
-> (MuTerm
((DoTerm ClosedTermLocation), (ReflectiveTerm
ClosedTermLocation)))

unfoldTerm (ClosedReflectiveTerm (ReflectiveTerm muT)) = muT

-- variable mention ctor
makeMention :: ClosedTermLocation -> ClosedReflectiveTerm

makeMention ctl =
(ClosedReflectiveTerm
 (ReflectiveTerm (MuTerm (Mention (unfoldLocation ctl)

-- abstraction ctor
makeAbstraction ::
ClosedTermLocation -> ClosedReflectiveTerm -> ClosedReflectiveTerm

makeAbstraction ctl crt =
(ClosedReflectiveTerm
 (ReflectiveTerm
  (MuTerm
   (Abstraction
(unfoldLocation ctl)
(unfoldTerm crt)

-- application ctor
makeApplication ::
ClosedReflectiveTerm -> ClosedReflectiveTerm -> ClosedReflectiveTerm

makeApplication crtApplicad crtApplicand =
(ClosedReflectiveTerm
 (ReflectiveTerm
  (MuTerm
   (Application
(unfoldTerm crtApplicad)
(unfoldTerm crtApplicand)

-- a simple test
generateTerms :: () -> [ClosedReflectiveTerm]

generateTerms () =
 -- x
[(makeMention
  (ClosedTermLocation
   (TermLocation (Hole, ReflectiveTerm (MuTerm Divergence),
 -- \x -> x
 (makeAbstraction
  (ClosedTermLocation
   (TermLocation (Hole, ReflectiveTerm (MuTerm Divergence
  (makeMention
   (ClosedTermLocation
(TermLocation (Hole, ReflectiveTerm (MuTerm Divergence)),
 -- ((\x -> x)(\x -> x))
 (makeApplication
  (makeAbstraction
   (ClosedTermLocation
(TermLocation (Hole, ReflectiveTerm (MuTerm Divergence
   (makeMention
(ClosedTermLocation
 (TermLocation (Hole, ReflectiveTerm (MuTerm Divergence))
  (makeAbstraction
   (ClosedTermLocation
(TermLocation (Hole, ReflectiveTerm (MuTerm Divergence
   (makeMention
(ClosedTermLocation
 (TermLocation (Hole, ReflectiveTerm (MuTerm Divergence)))]

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: Proofs and commercial code -- was Haskell Weekly News: Issue 85 - September 13, 2008

[Greg Meredith]

Daryoush,

One of the subtle points about computation is that -- via Curry-Howard --
well-typed programs are *already* proofs. They may not be the proof you were
seeking (there are a lot of programs from Int -> Int), or prove the theorem
you were seeking to prove (Ord a => [a] -> [a] is a lot weaker than 'this
program sorts lists of ordered types'), but they are witnesses of any type
they type-check against. In a system that has principal types, they are
proofs of their principal type. In this sense, the utility of proofs is
widespread: they are programs.

There is a really subtle dance between types that are rich enough to express
the theorems you would have your programs be proofs of and the termination
of type-checking for that type system. That's why people often do proofs by
hand -- because the theorems they need to prove require a greater degree of
expressiveness than is available in the type system supported by the
language in which the programs are expressed. Research has really been
pushing the envelope of what's expressible in types -- from region and
resource analysis to deadlock-freedom. Again, in that setting the program is
a witness of a property like

   - won't leak URLs to unsavory agents
   - won't hold on to handles past their garbage-collect-by date
   - won't get caught in a 'deadly embrace' (A is waiting for B, B is
   waiting for A)

Sometimes, however, and often in mission critical code, you need stronger
assurances, like

   - this code really does implement a FIFO queue, or
   - this code really does implement sliding window protocol, or
   - this code really does implement two-phase-commit-presumed-abort

It's harder -- in fact i think it's impossible for bullet item 2 above -- to
squeeze these into terminating type-checks. In those cases, you have to
escape out to a richer relationship between 'theorem' (aka type) and 'proof'
(aka program). Proof assistants, like Coq, or Hol or... can be very helpful
for automating some of the tasks, leaving the inventive bits to the humans.

In my experience, a proof of a theorem about some commercial code is pursued
when the cost of developing the proof is less than some multiple of the cost
of errors in the program in the life-cycle of that program. Intel, and other
hardware vendors, for example, can lose a lot of business when the
implementation of floating point operations is buggy; and, there is a
breaking point where the complexity/difficulty/cost of proving the
implementation correct is sufficiently less than that of business lost that
it is to their advantage to obtain the kind of quality assurance that can be
had from a proof of correctness.

One other place where proofs of correctness will be pursued is in
mathematical proofs, themselves. To the best of my knowledge, nothing
mission-critical is currently riding on the proof of the 4-color theorem.
The proof -- last i checked -- required programmatic checking of many cases.
Proving the program -- that implements the tedious parts of the proof --
correct is pursued because of the culture and standard of mathematical
proof.

Best wishes,

--greg

Date: Sat, 13 Sep 2008 22:24:50 -0700
From: "Daryoush Mehrtash" <[EMAIL PROTECTED]>
Subject: Re: [Haskell-cafe] Haskell Weekly News: Issue 85 - September
   13, 2008
To: "Don Stewart" <[EMAIL PROTECTED]>
Cc: Haskell Cafe 
Message-ID:
   <[EMAIL PROTECTED]>
Content-Type: text/plain; charset="iso-8859-1"

What I am trying to figure out is that say on the code for the IRC bot that
is show here

http://www.haskell.org/haskellwiki/Roll_your_own_IRC_bot/Source

What would theorem proofs do for me?

Daryoush

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Semantic Domain, Function, and denotational model.....

[Greg Meredith]

Daryoush,

Hopefully, the other replies about proving the monad laws already answered
your previous question: yes!

As for notions of semantic domain and denotational model, these ideas go
back quite a ways; but, were given solid footing by Dana
Scott.
In a nutshell, we have essentially three views of a computation

   - Operational  --
   computation is captured in a program and rules for executing it
   - Logical  --
   computation is captured in a proof and rules for normalizing it
   - Denotational  --
   computation is captured as a (completely unfolded) mathematical structure

In the latter view we think of computations/programs as denoting some
(usually infinitary) mathematical object. Our
aimis to completely define
the meaning of programs in terms of maps between
their syntactic representation and the mathematical objects their syntax is
intended to denote. (Notationally, one often writes such maps as [| - |] :
Program -> Denotation.) For example, we model terms in the lambda calculus
as elements in a D-infinity domain or Bohm trees or ... . Or, in more modern
parlance, we model terms in the lambda calculus as morphisms in some
Cartesian closed category, and the types of those terms as objects in said
category. The gold standard of quality of such a model is full
abstraction--
when the denotational notion of equivalence exactly coincides with an
intended operational notion of equivalence. In symbols,


   - P ~ Q <=> [| P |] = [| Q |], where ~ and = are the operational and
   denotational notions of equivalence, respectively


The techniques of denotational semantics have been very fruitful, but
greatly improved by having to rub elbows with operational characterizations.
The original proposals for denotational models of the lambda calculus were
much too arms length from the intensional structure implicit in the notion
of computation and thus failed to achieve full abstraction even for toy
models of lambda enriched with naturals and booleans (cf the so-called full
abstraction for PCF
problem).
On the flip side, providing a better syntactic exposure of the use of
resources -- ala linear logic -- aided the denotational programme.

More generally, operational models fit neatly into two ready-made notions of
equivalence

   - contextual
equivalence--
behaves the same in all contexts
   - bisimulation  -- behaves the
   same under all observations

Moreover, these can be seen to coincide with ready-made notions of
equivalence under the logical view of programs. Except for syntactically
derived initial/final denotational models -- the current theory usually
finds a more "home-grown" denotational notion of equivalence. In fact, i
submit that it is this very distance from the syntactic presentation that
has weakened the more popular understanding of "denotational" models to just
this -- whenever you have some compositionally defined map from one
representation to another that respects some form of equivalence, the target
is viewed as the denotation.

Best wishes,

--greg

Date: Mon, 15 Sep 2008 10:13:53 -0700
From: "Daryoush Mehrtash" <[EMAIL PROTECTED]>
Subject: Re: [Haskell-cafe] Semantic Domain, Function,  and
   denotational model.
To: "Ryan Ingram" <[EMAIL PROTECTED]>
Cc: Haskell Cafe 
Message-ID:
   <[EMAIL PROTECTED]>
Content-Type: text/plain; charset=ISO-8859-1

Interestingly, I was trying to read his paper when I realized that I
needed to figure out the meaning of denotational model, semantic
domain, semantic functions.  Other Haskell books didn't talk about
design in those terms, but obviously for him this is how he is driving
his design.   I am looking for a simpler tutorial, text book like
reference on the topic.

Daryoush

On Mon, Sep 15, 2008 at 1:33 AM, Ryan Ingram <[EMAIL PROTECTED]> wrote:
> I recommend reading Conal Elliott's "Efficient Functional Reactivity"
> paper for an in-depth real-world example.
>
> http://www.conal.net/papers/simply-reactive
>
>  -- ryan
>
> On Sun, Sep 14, 2008 at 11:31 AM, Daryoush Mehrtash <[EMAIL PROTECTED]>
wrote:
>> I have been told that for a Haskell/Functional programmer the process
>> of design starts with defining Semantic Domain, Function, and
>> denotational model of the problem.  I have done some googling on the
>> topic but haven't found a good reference on it.I would appreciate
>> any good references on the topic.
>>
>> thanks,
>>
>> daryoush
>>
>> ps.  I have found referneces like
>> http://en.wikibooks.org/wiki/Haskell/Denotational_semantic

Re: [Haskell-cafe] Semantic Domain, Function, and denotational model.....

[Greg Meredith]

Daryoush,

The two chapters in the Handbook of Logic in Computer Science -- especially
the one <http://www.cs.bham.ac.uk/%7Eaxj/pub/papers/handy1.pdf> by Abramsky
and Jung -- are good.  i noticed that Lloyd Allison wrote a book on
practical denotational semantics. i've never read it, but i was intrigued by
his work using minimal message length as the basis for a generic framework
in Haskell for machine-learning models. He might have something useful to
say.

It is difficult to judge what would be a good book for you, however, because
i don't know if you what your aim is. Do you want context, history and
mathematical foundations or a quick way to understanding enough FP-speak to
write better commercial code? As i said, a lot of people loosely speak of
the *target* of some compositionally defined function (usually based on some
structural recursion) that preserves some operational notion of equality as
the denotation. This is almost certainly what is going on in the references
you cited early. You can kind of leave it at that.

On the other hand, if you wish to go deeper, the study of the meaning of
programs is highly rewarding and will change the way you think. One
particularly fruitful place is games semantics. Guy McCusker's PhD thesis
might be a way in. Abramsky and Jagadeesan's papers might be a way in. As i
said before, the places where denotational and operational semantics have
had to rub elbows has been useful to both approaches. One of the hands down
best characterizations of the relationship of the logical and operational
view of computation is Abramsky's Computational Interpretations of Linear
Logic <http://www.comlab.ox.ac.uk/people/samson.abramsky/cill.ps.gz>. In
this paper Samson repeats the same process 3 times --

   1. specifies a logic by giving syntax for formulae and proof rules
   2. derives a term language (syntax of programs) and operational semantics
   that is sound w.r.t a type system given by the logical formulae
   3. derives a virtual machine for the term language
   4. refines the logic by an analysis of where the logic fails to capture
   our intuitions about resources -- looping back to step 1

The starting point is Intuitionistic Logic which yields the core of a
standard functional language. The next iteration is Intuitionistic Linear
Logic, which yields a linear FPL. The next iteration is Classical Linear
Logic which yields a concurrent language. Following the development of this
process will clarify the relationships between the logical and operational
view -- which ultimately bear on reasonable interpretations of denotational
interpretations.

If you make the step to say that the denotation must be the completely
unfolded structure -- the tree of reductions, the collection of possible
plays, etc -- then there are ways to see how these views logical,
operational and denotational are all calculable from one another -- and why
you might want to have all of them in any complete account of computation.

Best wishes,

--greg

On Wed, Sep 17, 2008 at 11:03 AM, Daryoush Mehrtash <[EMAIL PROTECTED]>wrote:

> I noticed that Wikipedia has listed a few text books on the topic:
>
> http://en.wikipedia.org/wiki/Denotational_semantics#Textbooks
>
> Any recommendations on which one might be a "better" read?
>
> Thanks,
>
> Daryoush
>
> 2008/9/16 Greg Meredith <[EMAIL PROTECTED]>:
> > Daryoush,
> >
> > Hopefully, the other replies about proving the monad laws already
> answered
> > your previous question: yes!
> >
> > As for notions of semantic domain and denotational model, these ideas go
> > back quite a ways; but, were given solid footing by Dana Scott. In a
> > nutshell, we have essentially three views of a computation
> >
> > Operational -- computation is captured in a program and rules for
> executing
> > it
> > Logical -- computation is captured in a proof and rules for normalizing
> it
> > Denotational -- computation is captured as a (completely unfolded)
> > mathematical structure
> >
> > In the latter view we think of computations/programs as denoting some
> > (usually infinitary) mathematical object. Our aim is to completely define
> > the meaning of programs in terms of maps between their syntactic
> > representation and the mathematical objects their syntax is intended to
> > denote. (Notationally, one often writes such maps as [| - |] : Program ->
> > Denotation.) For example, we model terms in the lambda calculus as
> elements
> > in a D-infinity domain or Bohm trees or ... . Or, in more modern
> parlance,
> > we model terms in the lambda calculus as morphisms in some Cartesian
> closed
> > category, and the types of those terms as objects in said category. The
> gold
> > standard of quality of such a

[Haskell-cafe] Ajax-Haskell framework?

[Greg Meredith]

Haskellians,

Is there an Ajax-Haskell framework? In case there are many, is there a
preferred one? Experiences people would like to share?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

re: [Haskell-cafe] ANNOUNCE: rewriting-0.1

[Greg Meredith]

Thomas,

Did you explore nominal rewrite at all? Do you know if it might be possible
to use the scrap-your-nameplate package to implement some useful subset of
the nominal rewrite machinery?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] monads with take-out options

[Greg Meredith]

Haskellians,
Some monads come with take-out options, e.g.

   - List
   - Set

In the sense that if unit : A -> List A is given by unit a = [a], then
taking the head of a list can be used to retrieve values from inside the
monad.

Some monads do not come with take-out options, IO being a notorious example.

Some monads, like Maybe, sit on the fence about take-out. They'll provide it
when it's available.

Now, are there references for a theory of monads and take-out options? For
example, it seems that all sensible notions of containers have take-out. Can
we make the leap and define a container as a monad with a notion of
take-out? Has this been done? Are there reasons for not doing? Can we say
what conditions are necessary to ensure a notion of take-out?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] monads with take-out options

[Greg Meredith]

Jonathan,
Nice! Thanks. In addition to implementations, do we have more mathematical
accounts? Let me expose more of my motives.

   - i am interested in a first-principles notion of data. Neither lambda
   nor π-calculus come with a criterion for determining which terms represent
   data and which programs. You can shoe-horn in such notions -- and it is
   clear that practical programming relies on such a separation -- but along
   come nice abstractions like generic programming and the boundary starts
   moving again. (Note, also that one of the reasons i mention π-calculus is
   because when you start shipping data between processes you'd like to know
   that this term really is data and not some nasty little program...) One step
   towards a first-principles characterization of data (as separate from
   program) is a first-principles characterization of containers.
  - Along these lines Barry Jay's pattern-matching calculus is an
  intriguing step towards such a characterization. This also links up with
  Foldable and Traversable.
  - i also looked at variants of Wischik's fusion calculus in which
  Abramsky's proof expressions characterize the notion of shippable data.
  (Part of the intuition here is that shippable data really ought to have a
  terminating access property for access to some interior region.
The linear
  types for proof expressions guarantee such a property for all well-typed
  terms.)
   - There is a real tension between nominal strategies and structural
   strategies for accessing data. This is very stark when one starts adding
   notions of data to the  π-calculus -- which is entirely nominal in
   characterization. Moreover, accessing some piece of data by path is natural,
   obvious and programmatically extensible. Accessing something by name is
   fast. These two ideas come together if one's nominal technology (think
   Gabbay-Pitt's freshness widgetry) comes with a notion of names that have
   structure.*
   - Finally, i think the notion of take-out option has something to do with
   being able to demarcate regions. In this sense i think there is a very deep
   connection with  Oleg's investigations of delimited continuations and --
   forgive the leap -- Linda tuple spaces.

As i've tried to indicate, in much the same way that monad is a very, very
general abstraction, i believe that there are suitably general abstractions
that account for a broad range of phenomena and still usefully separate a
notion of data from a notion of program. The category theoretic account of
monad plays a very central role in exposing the generality of the
abstraction (while Haskell's presentation has played a very central role in
understanding the utility of such a general abstractin). A similarly
axiomatic account of the separation of program from data could have
applicability and utility we haven't even dreamed of yet.

Best wishes,

--greg

* i simply cannot resist re-counting an insight that i got from Walter
Fontana, Harvard Systems Biology, when we worked together. In some sense the
dividing line between alchemy and chemistry is the periodic table. Before
the development of the periodic table a good deal of human investigation of
material properties could be seen as falling under the rubric alchemy. After
it, chemistry. If you stare at the periodic table you see that the element
names do not matter. They are merely convenient ways of referring to the
positional information of the table. From a position in the table you can
account for and predict all kind of properties of elements (notice that all
the noble gases line up on the right!). Positions in the table -- kinds of
element -- can be seen as 'names with structure', the structure of which
determines the properties of instances of said kind. i believe that a
first-principles account of the separation of program and data could have as
big an impact on our understanding of the properties of computation as the
development of the periodic table had on our understanding of material
properties.

On Mon, Nov 24, 2008 at 2:30 PM, Jonathan Cast <[EMAIL PROTECTED]>wrote:

> On Mon, 2008-11-24 at 14:06 -0800, Greg Meredith wrote:
> > Haskellians,
>
> > Some monads come with take-out options, e.g.
> >   * List
> >   * Set
> > In the sense that if unit : A -> List A is given by unit a = [a], then
> > taking the head of a list can be used to retrieve values from inside
> > the monad.
>
> > Some monads do not come with take-out options, IO being a notorious
> > example.
>
> > Some monads, like Maybe, sit on the fence about take-out. They'll
> > provide it when it's available.
>
> It might be pointed out that List and Set are also in this region.  In
> fact, Maybe is better, in this regard, since you know, if fromJust
> succeeds, that it will o

Re: [Haskell-cafe] monads with take-out options

[Greg Meredith]

Brandon,
i see your point, but how do we sharpen that intuition to a formal
characterization?

Best wishes,

--greg

On Mon, Nov 24, 2008 at 10:45 PM, Brandon S. Allbery KF8NH <
[EMAIL PROTECTED]> wrote:

> On 2008 Nov 24, at 17:06, Greg Meredith wrote:
>
> Now, are there references for a theory of monads and take-out options? For
> example, it seems that all sensible notions of containers have take-out. Can
> we make the leap and define a container as a monad with a notion of
> take-out? Has this been done? Are there reasons for not doing? Can we say
> what conditions are necessary to ensure a notion of take-out?
>
>
> Doesn't ST kinda fall outside the pale?  (Well, it is a container of sorts,
> but a very different from Maybe or [].)
>
> --
> brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED]
> system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED]
> electrical and computer engineering, carnegie mellon universityKF8NH
>
>
>


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] monads with take-out options

[Greg Meredith]

Claus,
Thanks for your thoughtful response. Let me note that fully abstract
semantics for PCF -- a total toy, mind you, just lambda + bools + naturals
-- took some 25 years from characterization of the problem to a solution.
That would seem to indicate shoe-horning, in my book ;-). Moreover, when i
look at proposals to revisit Church versus Parigot encodings for data
structures (ala Oliveira's thesis), i think we are still at the very
beginnings of an understanding of how data fits into algebraic accounts of
computation (such as lambda and π-calculi).

Obviously, we've come a long way. The relationship between types and
pattern-matching, for example, is now heavily exploited and generally a good
thing. But, do we really understand what's at work here -- or is this just
another 'shut up and calculate' situation, like we have in certain areas of
physics. Frankly, i think we are really just starting to understand what
types are and how they relate to programs. This really begs fundamental
questions. Can we give a compelling type-theoretic account of the separation
of program from data?

The existence of such an account has all kinds of implications, too. For
example, the current "classification" of notions of quantity (number) is
entirely one of history and accident.

   - Naturals
   - Rationals
   - Constructible
   - Algebraic
   - Transcendental
   - Reals
   - Complex
   - Infinitessimal
   - ...

Can we give a type theoretic reconstruction of these notions (of traditional
data types) that would unify -- or heaven forbid -- redraw the usual
distinctions along lines that make more sense in terms of applications that
provide value to users? Conway's ideas of numbers as games is remarkably
unifying and captures all numbers in a single elegant data type. Can this
(or something like it) be further rationally partitioned to provide better
notions of numeric type? Is there a point where such an activity hits a wall
and what we thought was data (real numbers; sequences of naturals; ...) are
just too close to programs to be well served by data-centric treatments?

Best wishes,

--greg

2008/11/24 Claus Reinke <[EMAIL PROTECTED]>

>  - i am interested in a first-principles notion of data. Neither lambda
>>  nor π-calculus come with a criterion for determining which terms
>> represent
>>  data and which programs. You can shoe-horn in such notions -- and it is
>>  clear that practical programming relies on such a separation -- but along
>>  come nice abstractions like generic programming and the boundary starts
>>  moving again. (Note, also that one of the reasons i mention π-calculus is
>>  because when you start shipping data between processes you'd like to know
>>  that this term really is data and not some nasty little program...)
>>
>
> I wouldn't call the usual representations of data in lambda shoe-horned
> (but perhaps you meant the criterion for distinguishing programs from
> data, not the notion of data?). Exposing data structures as nothing but
> placeholders for the contexts operating on their components, by making
> the structure components parameters to yet-to-be-determined continuations,
> seems to be as reduced to first-principles as one can get.
>
> It is also close to the old saying that "data are just dumb programs"
> (does anyone know who originated that phrase?) - when storage
> was tight, programmers couldn't always afford to fill it with dead
> code, so they encoded data in (the state of executing) their routines.
> When data was separated from real program code, associating data
> with the code needed to interpret it was still common. When high-level
> languages came along, treating programs as data (via reflective meta-
> programming, not higher order functions) remained desirable in some
> communities. Procedural abstraction was investigated as an alternative
> to abstract data types. Shipping an interpreter to run stored code was
> sometimes used to reduce memory footprint.
>
> If your interest is in security of mobile code, I doubt that you want to
> distinguish programs and data - "non-program" data which, when
> interpreted by otherwise safe-looking code, does nasty things, isn't
> much safer than code that does non-safe things directly. Unless you
> rule out code which may, depending on the data it operates on, do
> unwanted things, which is tricky without restricting expressiveness.
>
> More likely, you want to distinguish different kinds/types of
> programs/data, in terms of what using them together can do (in
> terms of pi-calculus, you're interested in typing process communication,
> restricting access to certain resources, or limiting communication
> to certain protocols). In the presence of suitably expressive type
> systems, procedural data abstractions need not be any less "safe"
> than dead bits interpreted by a separate program. Or if reasoning
> by suitable observational equivalences tells you that a piece of code
> can't do anything unsafe, does it matter whether that piece

[Haskell-cafe] re: monads with take-out options

[Greg Meredith]

John,
You write:

> Yes, you are describing 'co-monads'.
>

Good catch, but actually, that's too weak. i'm requesting something that is
both a monad and a co-monad. That makes it something like a bi-algebra, or a
Hopf algebra. This, however, is not the full story. i'm looking for a
reference to the full story. Surely, someone has already developed this
theory.

Best wishes,

--greg

From: John Meacham <[EMAIL PROTECTED]>
Subject: Re: [Haskell-cafe] monads with take-out options
To: haskell-cafe@haskell.org
Message-ID: <[EMAIL PROTECTED]>
Content-Type: text/plain; charset=utf-8

On Mon, Nov 24, 2008 at 02:06:33PM -0800, Greg Meredith wrote:
> Now, are there references for a theory of monads and take-out options? For
> example, it seems that all sensible notions of containers have take-out.
Can
> we make the leap and define a container as a monad with a notion of
> take-out? Has this been done? Are there reasons for not doing? Can we say
> what conditions are necessary to ensure a notion of take-out?

Yes, you are describing 'co-monads'.

here is an example that a quick web search brought up, and there was a
paper on them and their properties published a while ago
http://www.eyrie.org/~zednenem/2004/hsce/Control.Comonad.html

the duals in that version are

extract - return
duplicate - join
extend  - flip (>>=) (more or less)

   John


--
John Meacham - ⑆repetae.net⑆john⑈

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] haskell compiler never comes back

[Greg Meredith]

Haskellians,

The simple-minded and smallish code sample at this
linkcauses the compiler to go off
into never-never land. Any clues would be
greatly appreciated.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: haskell compiler never comes back

[Greg Meredith]

Haskellians,

An even simpler version <http://paste.pocoo.org/show/95518/> that reveals
the issue. i'm astounded that the compiler literally just hangs.

Best wishes,

--greg

On Mon, Dec 15, 2008 at 12:23 PM, Greg Meredith <
lgreg.mered...@biosimilarity.com> wrote:

> Haskellians,
>
> The simple-minded and smallish code sample at this 
> link<http://paste.pocoo.org/show/95503/>causes the compiler to go off into 
> never-never land. Any clues would be
> greatly appreciated.
>
> Best wishes,
>
> --greg
>
> --
> L.G. Meredith
> Managing Partner
> Biosimilarity LLC
> 806 55th St NE
> Seattle, WA 98105
>
> +1 206.650.3740
>
> http://biosimilarity.blogspot.com
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: haskell compiler never comes back

[Greg Meredith]

George,

Thanks for the response. If i take out the AllowUndecidableInstances i get
no complaints and the compiler hangs. See
this.
Thus, i can find no observable difference for this flag in this particular
code sample.

Best wishes,

--greg

On Mon, Dec 15, 2008 at 2:34 PM, George Pollard  wrote:

> This is precisely what AllowUndecidableInstances allows; the type
> checking becomes possibly non-terminating. It should *eventually*
> terminate because the stack depth is restricted.
>
> - George
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: haskell compiler never comes back

[Greg Meredith]

Daniel,

Thanks. i'm using

GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> :l monoidal.hs
[1 of 1] Compiling Monoidal ( monoidal.hs, interpreted )
  C-c C-cInterrupted.
> :q

Best wishes,

--greg

On Mon, Dec 15, 2008 at 2:50 PM, Daniel Fischer wrote:

> Am Montag, 15. Dezember 2008 23:16 schrieb Greg Meredith:
> > Haskellians,
> >
> > An even simpler version <http://paste.pocoo.org/show/95518/> that
> reveals
> > the issue. i'm astounded that the compiler literally just hangs.
> >
> > Best wishes,
> >
> > --greg
> >
> > On Mon, Dec 15, 2008 at 12:23 PM, Greg Meredith <
> >
> > lgreg.mered...@biosimilarity.com> wrote:
> > > Haskellians,
> > >
> > > The simple-minded and smallish code sample at this
> > > link<http://paste.pocoo.org/show/95503/>causes the compiler to go off
> > > into never-never land. Any clues would be greatly appreciated.
> > >
> > > Best wishes,
> > >
> > > --greg
>
> I can't confirm it, with 6.8.3:
>
> $ ghc -O2 --make Monoidal.hs
> [1 of 1] Compiling Monoidal ( Monoidal.hs, Monoidal.o )
>
> Monoidal.hs:110:11:
>Couldn't match expected type `i1'
>   against inferred type `Isomorpism (HFTensorExpr a i) a'
>  `i1' is a rigid type variable bound by
>   the instance declaration at Monoidal.hs:103:42
>In the expression: (PutIn (\ a -> (HFTLVal a)))
>In the third argument of `HFTExpr', namely
>`[(PutIn (\ a -> (HFTLVal a)))]'
>In the expression:
>(HFTExpr
>   (HFTLVal a)
>   (HFTRVal b)
>   [(PutIn (\ a -> (HFTLVal a)))]
>   [(PutIn (\ b -> (HFTRVal b)))])
> $
>
> and the earlier version:
>
> $ ghc -O2 --make Monoidal2.hs
> [1 of 1] Compiling Monoidal2( Monoidal2.hs, Monoidal2.o )
>
> Monoidal2.hs:105:18:
>Couldn't match expected type `HFTensorExpr a i'
>   against inferred type `[i1] -> [i1] -> HFTensorExpr a i1'
>In the expression: HFTExpr (HFTLVal a) (HFTRVal b)
>In the definition of `tMult':
>a tMult b = HFTExpr (HFTLVal a) (HFTRVal b)
>In the definition for method `tMult'
>
> Monoidal2.hs:122:10:
>Couldn't match expected type `[]' against inferred type `++ msa'
>  Expected type: [i]
>  Inferred type: ++ msa msb
>In the third argument of `HFTExpr', namely
>`((Shuffle
> (\ (HFTExpr (HFTExpr u v msu msv) w msuv msw)
>  -> (tAssoc (HFTExpr (HFTExpr u v msu msv) w msuv msw
> ::
>msa ++ msb)'
>In the expression:
>(HFTExpr
>   (HFTExpr a b msa msb)
>   c
>   ((Shuffle
>   (\ (HFTExpr (HFTExpr u v msu msv) w msuv msw)
>-> (tAssoc (HFTExpr (HFTExpr u v msu msv) w msuv msw
> ::
>  msa ++ msb)
>   msc)
>
> Monoidal2.hs:139:10:
>Couldn't match expected type `[]' against inferred type `++ msl'
>  Expected type: [i]
>  Inferred type: ++ msl msr
>In the third argument of `HFTExpr', namely
>`((Shuffle
> (\ (HFTExpr (HFTExpr a b msa msb) c msab msc)
>  -> (tAssoc (HFTExpr (HFTExpr a b msa msb) c msab msc
> ::
>msl ++ msr)'
>In the expression:
>(HFTExpr
>   (HFTExpr l r msl msr)
>   (HFTRVal b)
>   ((Shuffle
>   (\ (HFTExpr (HFTExpr a b msa msb) c msab msc)
>-> (tAssoc (HFTExpr (HFTExpr a b msa msb) c msab msc
> ::
>  msl ++ msr)
>   [(PutIn (\ b -> (HFTRVal b)))])
>
> Monoidal2.hs:150:11:
>Couldn't match expected type `i1'
>   against inferred type `Isomorpism (HFTensorExpr a i) a'
>  `i1' is a rigid type variable bound by
>   the instance declaration at Monoidal2.hs:103:42
>In the expression: (PutIn (\ a -> (HFTRVal a)))
>In the third argument of `HFTExpr', namely
>`[(PutIn (\ a -> (HFTRVal a)))]'
>In the expression:
>(HFTExpr
>   (HFTLVal a)
>   (HFTRVal b)
>   [(PutIn (\ a -> (HFTRVal a)))]
>   [(PutIn (\ b -> (HFTRVal b)))])
> $
>
> No hang, which compiler version did you use?
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: haskell compiler never comes back

[Greg Meredith]

Daniel,

BTW, if i comment out the version of PutIn that calls HF{L,R}Val and put in
the unit, instead, i see the complaint you're seeing. i'll upgrade ghc.

Best wishes,

--greg

On Mon, Dec 15, 2008 at 2:49 PM, Greg Meredith <
lgreg.mered...@biosimilarity.com> wrote:

> Daniel,
>
> Thanks. i'm using
>
> GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
> Loading package base ... linking ... done.
> Prelude> :l monoidal.hs
> [1 of 1] Compiling Monoidal ( monoidal.hs, interpreted )
>   C-c C-cInterrupted.
> > :q
>
> Best wishes,
>
> --greg
>
>
> On Mon, Dec 15, 2008 at 2:50 PM, Daniel Fischer 
> wrote:
>
>> Am Montag, 15. Dezember 2008 23:16 schrieb Greg Meredith:
>> > Haskellians,
>> >
>> > An even simpler version <http://paste.pocoo.org/show/95518/> that
>> reveals
>> > the issue. i'm astounded that the compiler literally just hangs.
>> >
>> > Best wishes,
>> >
>> > --greg
>> >
>> > On Mon, Dec 15, 2008 at 12:23 PM, Greg Meredith <
>> >
>> > lgreg.mered...@biosimilarity.com> wrote:
>> > > Haskellians,
>> > >
>> > > The simple-minded and smallish code sample at this
>> > > link<http://paste.pocoo.org/show/95503/>causes the compiler to go off
>> > > into never-never land. Any clues would be greatly appreciated.
>> > >
>> > > Best wishes,
>> > >
>> > > --greg
>>
>> I can't confirm it, with 6.8.3:
>>
>> $ ghc -O2 --make Monoidal.hs
>> [1 of 1] Compiling Monoidal ( Monoidal.hs, Monoidal.o )
>>
>> Monoidal.hs:110:11:
>>Couldn't match expected type `i1'
>>   against inferred type `Isomorpism (HFTensorExpr a i) a'
>>  `i1' is a rigid type variable bound by
>>   the instance declaration at Monoidal.hs:103:42
>>In the expression: (PutIn (\ a -> (HFTLVal a)))
>>In the third argument of `HFTExpr', namely
>>`[(PutIn (\ a -> (HFTLVal a)))]'
>>In the expression:
>>(HFTExpr
>>   (HFTLVal a)
>>   (HFTRVal b)
>>   [(PutIn (\ a -> (HFTLVal a)))]
>>   [(PutIn (\ b -> (HFTRVal b)))])
>> $
>>
>> and the earlier version:
>>
>> $ ghc -O2 --make Monoidal2.hs
>> [1 of 1] Compiling Monoidal2( Monoidal2.hs, Monoidal2.o )
>>
>> Monoidal2.hs:105:18:
>>Couldn't match expected type `HFTensorExpr a i'
>>   against inferred type `[i1] -> [i1] -> HFTensorExpr a i1'
>>In the expression: HFTExpr (HFTLVal a) (HFTRVal b)
>>In the definition of `tMult':
>>a tMult b = HFTExpr (HFTLVal a) (HFTRVal b)
>>In the definition for method `tMult'
>>
>> Monoidal2.hs:122:10:
>>Couldn't match expected type `[]' against inferred type `++ msa'
>>  Expected type: [i]
>>  Inferred type: ++ msa msb
>>In the third argument of `HFTExpr', namely
>>`((Shuffle
>> (\ (HFTExpr (HFTExpr u v msu msv) w msuv msw)
>>  -> (tAssoc (HFTExpr (HFTExpr u v msu msv) w msuv msw
>> ::
>>msa ++ msb)'
>>In the expression:
>>(HFTExpr
>>   (HFTExpr a b msa msb)
>>   c
>>   ((Shuffle
>>   (\ (HFTExpr (HFTExpr u v msu msv) w msuv msw)
>>-> (tAssoc (HFTExpr (HFTExpr u v msu msv) w msuv
>> msw
>> ::
>>  msa ++ msb)
>>   msc)
>>
>> Monoidal2.hs:139:10:
>>Couldn't match expected type `[]' against inferred type `++ msl'
>>  Expected type: [i]
>>  Inferred type: ++ msl msr
>>In the third argument of `HFTExpr', namely
>>`((Shuffle
>> (\ (HFTExpr (HFTExpr a b msa msb) c msab msc)
>>  -> (tAssoc (HFTExpr (HFTExpr a b msa msb) c msab msc
>> ::
>>msl ++ msr)'
>>In the expression:
>>(HFTExpr
>>   (HFTExpr l r msl msr)
>>   (HFTRVal b)
>>   ((Shuffle
>>   (\ (HFTExpr (HFTExpr a b msa msb) c msab msc)
>>-> (tAssoc (HFTExpr (HFTExpr a b msa msb) c msab
>> msc
>> ::
>>  msl ++ msr)
>>   [(PutIn (\ b -> (HFTRVal b)))])
>>
>> Monoidal2.hs:150:11:
>>Couldn't match expected type `i1'

Re: [Haskell-cafe] haskell compiler never comes back

[Greg Meredith]

Ian,

Thanks for your diligence! i upgraded to ghc 6.10.1 and that resolved the
issue. i've a working version of the sample at this
link<http://paste.pocoo.org/show/95533/>
.

Best wishes,

--greg

On Tue, Dec 16, 2008 at 10:28 AM, Ian Lynagh  wrote:

>
> Hi Greg,
>
> On Mon, Dec 15, 2008 at 12:23:08PM -0800, Greg Meredith wrote:
> >
> > The simple-minded and smallish code sample at this
> > link<http://paste.pocoo.org/show/95503/>causes the compiler to go off
> > into never-never land. Any clues would be
> > greatly appreciated.
>
> I've lost track of this thread, but if you still think there's a bug
> then can you report it in the GHC trac please?:
>http://hackage.haskell.org/trac/ghc/wiki/ReportABug
>
> Please give an example without UndecidableInstances if possible, and the
> smaller the example is the easier it is for us to look into it.
>
>
> Thanks
> Ian
>
>


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] 3 applications of "indexed composition" as a language design principle

[Greg Meredith]

Haskellians,

i've found a way to generalize the LogicT transformer and calculated it's
application to three fairly interesting examples. The approach -- with some
sample codes as scala+lift web apps -- is described
here.
Comments welcome.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Haskell on JVM

[Greg Meredith]

Simon, et al,

It might be interesting to look at
CALas a non-blank-slate
beginning for Haskell on the JVM. To my mind there are
three things that this needs to make it a real winner:

   - Much, much better Java interop. Basically, the bar to meet here is
   Scala/Java interop.
   - Better support for "std" Haskell syntax
  - and better support for some of the basic (semantic and syntactic)
  extensions
  - Figuring out what of Hackage it is reasonable to support


Best wishes,

--greg

Date: Tue, 23 Jun 2009 15:16:03 +0100
> From: Simon Peyton-Jones 
> Subject: RE: [Haskell-cafe] Haskell on the iPhone
> To: Rick R , Haskell Cafe
>
> Message-ID:
><
> 638abd0a29c8884a91bc5fb5c349b1c33f4baaf...@ea-exmsg-c334.europe.corp.microsoft.com
> >
>
> Content-Type: text/plain; charset="us-ascii"
>
> Good news about the iPhone port!
>
> There seems to be quite a bit more interest now in supporting platforms
> other than win/*nix on x86 these days*.  Maybe now there will be sufficient
> motivation to make the fundamental changes required. Caveat: I have
> absolutely no idea of the scope or complexity of said changes.  I will look
> through the LambdaVM code (and iPwn when available)  to get an idea.
>
> There is definitely an opportunity here for someone to make an impact.
>  There is no reason in principle why Haskell can't run on a JVM or .net or
> other platform.  But it's not just a simple matter of absorbing some patch
> or other.  Here's a summary I wrote a little while ago:
>
> http://haskell.org/haskellwiki/GHC:FAQ#Why_isn.27t_GHC_available_for_.NET_or_on_the_JVM.3F
>
> The short summary is:
>
> * There is interesting design work to do; and then interesting
> engineering work to make it a reality.
>
> * We (at GHC HQ) would love to see that happen, but are not likely
> to drive it.
>
> * If someone, or a small group, wanted to take up the cudgels and
> work on it, we'd be happy to advise.
>
> * We'd certainly consider folding the results into the HEAD,
> provided the author(s) are willing to maintain it, and we feel that the
> result is comprehensible and maintainable.
>
> * But another viable route might well be to use the GHC API, which
> means that the result wouldn't be part of GHC at all, just a client of the
> API.  That would make it much easier to distribute upgrades etc, just as a
> Cabal package.
>
> Simon
>

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Haskell on JVM

[Greg Meredith]

Jason,

CAL's syntax is not std Haskell syntax.

Best wishes,

--greg

On Thu, Jun 25, 2009 at 11:10 AM, Jason Dusek  wrote:

> 2009/06/24 Greg Meredith :
> > Better support for "std" Haskell syntax
>
>   What does this mean, actually? Better support for standard
>  Haskell syntax than what?
>
> --
> Jason Dusek
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
1219 NW 83rd St
Seattle, WA 98117

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Composition, delegation and interfaces -- a 20K ft critique of Noop

[Greg Meredith]

Dear Programmers,
Someone just asked me to give my opinion on Noop's composition
proposal.
It reminds me a little bit of
Selfwhich
found its way into JavaScript. It also reminds me a little of
Haskell's
type classes . In general, movement
away from inheritance is good. The proposal, however, feels a bit like
looking for the lost quarter where the light is good, rather than where you
lost it. Before considering delegation machinery, let's consider the
*value*of an interface. How many interfaces are there? One way to see
that is just
to consider all the sub interfaces of a single interface with n methods on
it. Hmmm... that's 2^n interfaces. That's a lot. Does that give us any
confidence that any one way of carving up functionality via interfaces is
going to be sane? Further, in practice, do we see random distribution
through this very large space?

What we see over and over again in practice is that the answer to these
questions is 'no!'. That means that there is *something* that binds a
collection of methods together. What might that something be? One place to
look is mathematics. Which maths should we look at? The maths of category
has been very fruitful both in explaining existing functional programming
techniques and -- perhaps more importantly -- suggesting ways to improve
them as well as wholly new techniques. What we find in category theory is
that it is natural to collect maps (read functions) together. A good example
of such a beast is a monad. A monad -- viewed categorically -- is

   - a map, T, taking types to new types and functions on those types to new
   functions. Let's call the universe of types and functions expressible in our
   model of computation (as proscribed by our programming language), C. Then T
   : C -> C.
   - a higher order map, unit. Just like T takes C to C, we can understand a
   "noop" like map that takes C to C, call it Id. Then unit : Id -> T. We
   intuitively think about it as putting basic types inside the container T,
   but it's really a higher order map.
   - another higher order map, mult : T^2 -> T. We talk about it as a kind
   of flattening (and in Scala it's called flatMap), but it's a higher order
   map.

Now, one is not finished spelling out a monad when giving this collection of
maps. One must also show that they satisfy certain constraints.

   - T is functorial, meaning T g f = T(g) T(f)
   - unit and mult are natural transformations, look up the meaning because
   unpacking it here would take to long
   - mult( mult T ) = mult( T mult )
   - mult( unit T ) = mult( T unit  )

This set of constraints must go with the monad. This example provides a
little more detail in terms of what binds a group of maps together, and
hence of what *might* replace the notion of interface and *explain* what we
see in practice. Good programmers invariably pick out just a few
factorizations of possible interfaces -- from the giant sea of
factorizations (read different ways to carve up the functionality). The
reason -- i submit -- is because in their minds there are some constraints
they know or at least intuit must hold -- but they have no good way at the
language level to express those constraints. A really practical language
should help the programmer by providing a way express and check the
constraints that hold amongst the maps in an interface.

i submit that this idea is not the same as "design by contract". i am not
proposing an Eiffel-like mechanism. Again, taking a functional approach to
computation via category theory leads one towards modeling interfaces as
categorical "situations" like monads, comonads, distribution laws, etc. This
means that a large number of the constraints come down to

   - functoriality
   - naturality
   - coherence

Language support for this approach might include *keywords for these kinds
of assertions*. It is a gnarly beast to offer automatic and/or compiler
support for checking general constraints. Even this limited family of
constraints that i'm proposing can generate some very difficult
computations, with very bad complexity. However, for those situations where
a general purpose solution to check assertions of functoriality, naturality
and coherence are infeasible, one can use these hints to generate tests to
probe for possible failures. This idea follows the in the same spirit of
replacing proof with proof-checking.

Of course, this is not the only way to go. i've yet to be convinced that
category theory offers a good account of concurrency. Specifically,
categorical composition does not line up well with concurrent composition.
So, interfaces organized around types for concurrency is also something to
consider. In this case, one might find a natural beginning in interfaces in
which -- roughly speaking -- the methods constitute the tokens of a formal
language the constructor

[Haskell-cafe] towards a new foundation for set theory with atoms

[Greg Meredith]

Haskellians,

i have a particular interest in FM-set theory in that it simplifies a host
of otherwise non-trivial aspects of programming language semantics,
especially, fresh names. You can provide semantics without sets with atoms,
but the functor category machinery is more than a little on the heavy side.
The down side of FM-set theory is that it posits an infinite collection of
atomic entities -- atomic in the sense that they have no observable internal
structure. This poses a real problem for computational accounts. No where do
we have an infinite supply of atomic entities. All our infinite collections
need some finite presentation -- some basic starting structure and then a
finite set of rules that say how to generate the rest. This is particularly
important since the atoms have to come with a equality predicate. If the
predicate cannot inspect internal structure, then the equality predicate is
too big to hold in any finitely presentable computation. Thus, there's a
little conundrum: how do you get all the conveniences of a set theory with
atoms and still have a finite presentation?

Here's one approach. The issue is that atoms cannot have internal structure
observable by the set-theoretic operators, \in : Set  -> Atom + Set -> Bool,
and { - } : [Atom + Set] -> Set. That doesn't mean they can't have
structure. Where would this structure come from? Well, it's related to
another observation about sets: they're really collections of pointers. More
specifically, the axiom of extensionality says that two sets are equal iff
they have exactly the same members. Thus, wherever we see the set { } it's
the same. Therefore, in { { }, { { } } } we see the very same set occurring
in two locations. This is not very physical. These notions of location or
identity must be more logical notions. And, one obvious way to resolve this
is that what's "inside" the braces are references or pointers. We can start
to formalize this naively using a simple grammar-nee type formulation.
Ordinary sets can be specified like this

Set ::= { Set* }

for some appropriately infinite  version of Kleene-star. (Note, this grammar
is really sugar for a domain equation.) Now, if we want sets over
references, we could modify the grammar, like this

RSet ::= { Ref* }
Ref ::= `Set*'

R-sets only contain references and references point to (collections of)
sets. Then, you can add a dereference operation to you theory to get back
the sets being referenced. But, while under the quotes, the internal
structure is not observable by the element-of and brace operators. Thus,
from the point of view of these operators, they look like atoms.

Note that as written, the quotes are serving a role isomorphic to the role
of the braces. They are essentially two different collection operators that
have been intertwined in an alternating manner. This alternation is in
perfect correspondence with games semantics. We interpret { as opponent
question, } as opponent answer, ` as player question, ' as player answer.
This means that winning strategies for opponent yield sets while winning
strategies for player yield references. The observation leads to a further
generalization. Nothing restricts us to two kinds of collection operators.
We could posit n different "colored" braces and element-of operators,
written {i - i}, \in_i, for color i. Then we have the following
specification for these sets

Set(i) ::= {i Set(0 <= j < n : j <> i)* i}

i have coded up (in my pidgin Haskell) a version for 3 colors and then shown
how to do the von Neumann encoding of the naturals in this setting. The code
can be found here:
http://svn.biosimilarity.com/src/open/mirrororrim/rsets/trunk/MPSet.hs

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: towards a new foundation for set theory with atoms

[Greg Meredith]

Haskellians,

A quick follow up. If you look at the code that i have written there is a
great deal of repeated structure. Each of these different kinds of sets and
atoms are isomorphic copies of each other. Because, however, of the
alternation discipline, i could see no way to abstract the structure and
simplify the code. Perhaps someone better versed in the Haskellian mysteries
could enlighten me.

Best wishes,

--greg

On 8/10/07, Greg Meredith <[EMAIL PROTECTED]> wrote:
>
> Haskellians,
>
> i have a particular interest in FM-set theory in that it simplifies a host
> of otherwise non-trivial aspects of programming language semantics,
> especially, fresh names. You can provide semantics without sets with atoms,
> but the functor category machinery is more than a little on the heavy side.
> The down side of FM-set theory is that it posits an infinite collection of
> atomic entities -- atomic in the sense that they have no observable internal
> structure. This poses a real problem for computational accounts. No where do
> we have an infinite supply of atomic entities. All our infinite collections
> need some finite presentation -- some basic starting structure and then a
> finite set of rules that say how to generate the rest. This is particularly
> important since the atoms have to come with a equality predicate. If the
> predicate cannot inspect internal structure, then the equality predicate is
> too big to hold in any finitely presentable computation. Thus, there's a
> little conundrum: how do you get all the conveniences of a set theory with
> atoms and still have a finite presentation?
>
> Here's one approach. The issue is that atoms cannot have internal
> structure observable by the set-theoretic operators, \in : Set  -> Atom +
> Set -> Bool, and { - } : [Atom + Set] -> Set. That doesn't mean they can't
> have structure. Where would this structure come from? Well, it's related to
> another observation about sets: they're really collections of pointers. More
> specifically, the axiom of extensionality says that two sets are equal iff
> they have exactly the same members. Thus, wherever we see the set { } it's
> the same. Therefore, in { { }, { { } } } we see the very same set occurring
> in two locations. This is not very physical. These notions of location or
> identity must be more logical notions. And, one obvious way to resolve this
> is that what's "inside" the braces are references or pointers. We can start
> to formalize this naively using a simple grammar-nee type formulation.
> Ordinary sets can be specified like this
>
> Set ::= { Set* }
>
> for some appropriately infinite  version of Kleene-star. (Note, this
> grammar is really sugar for a domain equation.) Now, if we want sets over
> references, we could modify the grammar, like this
>
> RSet ::= { Ref* }
> Ref ::= `Set*'
>
> R-sets only contain references and references point to (collections of)
> sets. Then, you can add a dereference operation to you theory to get back
> the sets being referenced. But, while under the quotes, the internal
> structure is not observable by the element-of and brace operators. Thus,
> from the point of view of these operators, they look like atoms.
>
> Note that as written, the quotes are serving a role isomorphic to the role
> of the braces. They are essentially two different collection operators that
> have been intertwined in an alternating manner. This alternation is in
> perfect correspondence with games semantics. We interpret { as opponent
> question, } as opponent answer, ` as player question, ' as player answer.
> This means that winning strategies for opponent yield sets while winning
> strategies for player yield references. The observation leads to a further
> generalization. Nothing restricts us to two kinds of collection operators.
> We could posit n different "colored" braces and element-of operators,
> written {i - i}, \in_i, for color i. Then we have the following
> specification for these sets
>
> Set(i) ::= {i Set(0 <= j < n : j <> i)* i}
>
> i have coded up (in my pidgin Haskell) a version for 3 colors and then
> shown how to do the von Neumann encoding of the naturals in this setting.
> The code can be found here:
> http://svn.biosimilarity.com/src/open/mirrororrim/rsets/trunk/MPSet.hs
>
> Best wishes,
>
> --greg
>
> --
> L.G. Meredith
> Managing Partner
> Biosimilarity LLC
> 505 N 72nd St
> Seattle, WA 98103
>
> +1 206.650.3740
>
> http://biosimilarity.blogspot.com




-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Re: towards a new foundation for set theory with atoms

[Greg Meredith]

Brandon,

Cool. Well spotted. i was thinking a lot about the symmetry in the type
space as a kind of group. i'll play around with your suggestion.

Best wishes,

--greg

On 8/11/07, Brandon Michael Moore <[EMAIL PROTECTED]>
wrote:
>
> On Fri, Aug 10, 2007 at 03:54:23PM -0700, Greg Meredith wrote:
> > Haskellians,
> >
> > A quick follow up. If you look at the code that i have written there is
> a
> > great deal of repeated structure. Each of these different kinds of sets
> and
> > atoms are isomorphic copies of each other. Because, however, of the
> > alternation discipline, i could see no way to abstract the structure and
> > simplify the code. Perhaps someone better versed in the Haskellian
> mysteries
> > could enlighten me.
>
> You could take a less absolute view of the game, and describe each node
> instead locally from the perspective of a player. Imagine Alice Bob and
> Carol sitting around a table:
>
> data ThreePlayers a b c =
>Next (ThreePlayer b c a)
> | Prev (ThreePlayers c a b)
>
> In general you can get subgroups of a symmetric group as your sets of
> colors this way (i.e, the set of elements of any group), I'm not quite
> sure how much freedom you have in the sets of allowed transitions
> (in particular, making some of the argument types identical can break
> symmetry).
>
> You could also go for the obvious big hammer, pretend that Haskell has
> a strongly normalizing subset and encode inequality explicitly with
> GADTs and such.
>
> date Eq a b where Refl a a
> data False
> type Neq a b = Eq a b -> False
> -- might be trouble if a and b are only equal non-constructively?
>
> data Red = Red
> data Green = Green
> 
>
> data Set color where
>   Red :: Neq Red color -> Set Red -> Set color
>   ...
>
> Brandon
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] haskell and reflection

[Greg Meredith]

Haskellians,

Am i wrong in my assessment that the vast majority of reflective machinery
is missing from Haskell? Specifically,

   - there is no runtime representation of type available for
   programmatic representation
   - there is no runtime representation of the type-inferencing or
   checking machinery
   - there is no runtime representation of the evaluation machinery
   - there is no runtime representation of the lexical or parsing
   machinery

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] haskell and reflection

[Greg Meredith]

Neil,

Thanks very much for the detailed response. When we did Rosette, a
reflective actor-based language, back in the late '80's and early '90's, we
were very much influenced by Brian Cantwell Smith's account of reflection in
3-Lisp and similarly by Friedman and Wand's "Mystery of the Tower Revealed".
Our analysis suggested the following breakdown

   - Structural reflection -- all data used in the evaluation of programs
   has a programmatic representation
   - Procedural reflection -- all execution machinery used in the
   evaluation of programs has a programmatic representation

The Java notion of reflection is restricted entirely to the first case and
then only to the data used once a normalized representation has been
achieved. In fact, lexing and parsing are of considerable interest and
complexity in the evaluation of programs and reflective access is extremely
useful.

Likewise, access to the evaluation machinery itself is of more than
theoretical interest. For example, in an ATM network management system i
wrote in Rosette, i used reflective methods -- where the evaluation itself
could be captured, stored and manipulated, much like a 1-shot continuation
-- to make a polling interface of an external trouble-ticketing system we
were required by business constraints to interface with look like an
interrupt-driven interface to the Rosette-based clients.

Best wishes,

--greg

On 9/11/07, Neil Mitchell <[EMAIL PROTECTED]> wrote:
>
> Hi
>
> > there is no runtime representation of type available for programmatic
> > representation
>
> Data.Typeable.typeOf :: Typeable a => a -> TypeRep
>
> > there is no runtime representation of the type-inferencing or checking
> > machinery
>
> Pretty much, no. The GHC API may provide some.
>
> > there is no runtime representation of the evaluation machinery
>
> Yhc provides some representation with the Yhc API.
>
> > there is no runtime representation of the lexical or parsing machinery
>
> lex provides some of this. There are various Haskell parsers out there
> in packages for us.
>
>
> I wouldn't have considered these things "reflection" - certainly the
> Java/C# use of the word reflection is quite different. Data.Generics
> does provide many of the reflection capabilities of Java.
>
> Thanks
>
> Neil
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] haskell and reflection

[Greg Meredith]

Jules,

Thanks for these comments. i wouldn't judge Haskell solely on the basis of
whether it embraced reflection as an organizing computational principle or
as a toolbox for programmers. Clearly, you can get very far without it. And,
it may be that higher-order functional gives you enough of the 'programs
that build programs' capability that 80% of the practical benefits of
reflection are covered -- without having to take on the extra level of
complexity that reflection adds to typing. i was really just seeking
information.

Best wishes,

--greg

On 9/11/07, Jules Bean <[EMAIL PROTECTED]> wrote:
>
> Greg Meredith wrote:
> > Haskellians,
> >
> > Am i wrong in my assessment that the vast majority of reflective
> > machinery is missing from Haskell? Specifically,
> >
> > * there is no runtime representation of type available for
> >   programmatic representation
> > * there is no runtime representation of the type-inferencing or
> >   checking machinery
> > * there is no runtime representation of the evaluation machinery
> > * there is no runtime representation of the lexical or parsing
> >   machinery
>
>
> As far as they go, those are true.
>
> Haskell compiler are permitted to erase types and GHC does so. There is
> no need to check types at runtime; that's the point of the system! There
> is no evaluator, or parser, built in to the standard libraries. (The
> lexer, or a version of it, is embedded in actual fact but that's not
> very exciting).
>
> However, one should not draw too strong negative conclusions from this.
> It is possible to get suprisingly far with more powerful, more typesafe
> techniques without surrendering the the pure dynamism of languages that
> lack compile-time guarantees. Deriving Typeable and Data is one tool
> which is useful.
>
> It is quite possible to embed a haskell compiler, see hs-plugins.
>
> Jules
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] "Prime" monads?

[Greg Meredith]

Haskellians,

Is there a characterization of "prime" monads? Here the notion of
factorization i'm thinking about is decomposition into adjoint situations.
For example, are there monads for which there are only the Kleisli and
Eilenberg-Moore decompositions into adjoint situations? Would this be a
characterization of quintessentially "free" or "generative"?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] help getting happy

[Greg Meredith]

Haskellians,

The code pasted in below causes Happy to return parE when invoked with happy
rparse.y -i . Is there anyway to get Happy to give me just a wee bit more
info as to what might be causing the parE (which i interpret a 'parse
error').

Best wishes,

--greg

{
module Main where
}
%name rparse
%tokentype { Token }
%error { parseError }
%token
  '{' { TokenLCurly }
  '}' { TokenRCurly }
  '[' { TokenLSquare }
  ']' { TokenRSquare }
  '(' { TokenLRound }
  ')' { TokenRRound }
  '@' { TokenAt }
  ',' { TokenComma }
  ';' { TokenSemi }
  lquote  { TokenLQuote }
  rquote  { TokenRQuote }
%%
Molecule: '{' '}'  { Zero }
| Name Reagent { Locate $1 $2 }
| '@' Name { Decode $2 }

ReagentList : Reagent  { [ $1 ] }
| ReagentList ';' Reagent  { $1 ++ [$3] }

Reagent : '?' '(' NameList ')' Mixture { Abstraction $3 $5 }
| '[' Mixture ']'  { Concretion $2 }

Mixture : Molecule { Mix [ $1 ] }
| '{' ReagentList '}'  { Mix $2 }

NameList: Name { [ $1 ] }
| NameList ',' Name{ $1 ++ [$3] }

Name: lquote Mixture rquote{ Name $2 }

{

parseError :: [Token] -> a
parseError _ = error "Parse error"

data Molecule
= Zero
| Locate Name Reagent
| Decode Name
  deriving (Eq, Show)

data Reagent
= Abstraction [Name] Mix
| Concretion Mix
  deriving (Eq, Show)

data Mix
= Mix [Molecule]
  deriving (Eq, Show)

data Name
= Name Mix
  deriving (Eq, Show)

data Token
  = TokenLQuote
  | TokenRQuote
  | TokenLCurly
  | TokenRCurly
  | TokenLSquare
  | TokenRSquare
  | TokenLRound
  | TokenRRound
  | TokenComma
  | TokenSemi
  | TokenAt
 deriving Show

lexer :: String -> [Token]
lexer [] = []
lexer (c:cs)
  | isSpace c = lexer cs
lexer ('{':cs) = TokenLCurly : lexer cs
lexer ('}':cs) = TokenRCurly : lexer cs
lexer ('[':cs) = TokenLSquare : lexer cs
lexer (']':cs) = TokenRSquare : lexer cs
lexer ('(':cs) = TokenLRound : lexer cs
lexer (')':cs) = TokenRRound : lexer cs
lexer (',':cs) = TokenComma : lexer cs
lexer (';':cs) = TokenSemi : lexer cs
lexer ('@':cs) = TokenAt : lexer cs
lexer ('<':'<':cs) = TokenLQuote : lexer cs
lexer ('>':'>':cs) = TokenRQuote : lexer cs

main = getContents >>= print . rparse . lexer
}

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: help getting happy

[Greg Meredith]

Simon,

Cheers. i solved the problem before i saw your email. The Happy i got was a
result of invoking

port install happy

What's the drift between macports and happy versions? Is there a way of
using Happy without being on or even near the cutting edge of development?

Best wishes,

--greg

On 9/13/07, Simon Marlow <[EMAIL PROTECTED]> wrote:
>
> Greg Meredith wrote:
> > Haskellians,
> >
> > The code pasted in below causes Happy to return parE when invoked with
> > happy rparse.y -i . Is there anyway to get Happy to give me just a wee
> > bit more info as to what might be causing the parE (which i interpret a
> > 'parse error').
>
> Please grab a more recent version of Happy from darcs:
>
>http://darcs.haskell.org/happy
>
> the parE thing was a bug in the error handling introduced in the last
> release.  You'll need Cabal-1.2 in order to build the latest Happy.
>
> Cheers,
> Simon
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] generic programming tutorial?

[Greg Meredith]

Haskellians,

i feel like i'm chasing a rabbit down the rabbit hole, but here goes. i'm
currently redoing my implementation of an evaluator for a reflective process
calculus, using Haskell instead of OCaml, this time. i thought i'd give a
James Cheney's FreshLib a whirl to

   - test out the state of the nominal machinery in Haskell
   - see if the nominal stuff works, practically, with my reflective
   account of nominal machinery

i've discovered that FreshLib makes essential use of a early version of
generic Haskell features. i need to bone up on generic Haskell, quickly.
i've got the papers. i need to see what's being released and supported in
the mainstream Haskell codebase. Is there documentation for this, or should
i grovel source?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] SYB3 codebase

[Greg Meredith]

Haskellians,

Does anyone know the status of SYB3 codebase? It appears that FreshLib
critically depends on it, but the code downloadable from
http://homepages.cwi.nl/~ralf/syb3/code.html dies in make test on the first
test with

lgmaclt:~/work/src/projex/biosimilarity/HS1/Process/haskell/SYB3 lgm$ make
test
make test1 stem=geq1
ghci -fglasgow-exts -fallow-overlapping-instances
-fallow-undecidable-instances -v0 geq1.hs < Main.in > geq1.out

geq1.hs:27:34:
Inferred type is less polymorphic than expected
  Quantified type variable `a1' escapes
Probable cause: `geq'' is applied to too few arguments
In the first argument of `gzipWithQ', namely `geq''
In the first argument of `and', namely `(gzipWithQ geq' x y)'

:1:0: Not in scope: `main'
diff -b geq1.out geq1.ref
0a1,4
> True
> False
> False
> True
make[1]: *** [test1] Error 1
make: *** [test] Error 2
lgmaclt:~/work/src/projex/biosimilarity/HS1/Process/haskell/SYB3 lgm$

Is there a newer version of this codebase? Has this functionality been
folded into mainline Haskell tree somewhere?

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] SYB3 codebase

[Greg Meredith]

Mads,

Many thanks for your help. i really appreciate it.

Best wishes,

--greg

On 10/19/07, Mads Lindstrøm <[EMAIL PROTECTED]> wrote:
>
> Hi Greg
>
> I forgot to say, that I did not stop using the Shelarcy patch because
> there was something wrong with the code. On the contrary it served me
> well for long time.
>
> The reason for using the HappS-version was that I wanted something that
> was Cabalized and that I thought it was good to minimize the number of
> SYB3's floating around.
>
>
> Greetings,
>
> Mads Lindstrøm
>
>
> > Haskellians,
> >
> > Does anyone know the status of SYB3 codebase? It appears that FreshLib
> > critically depends on it, but the code downloadable from
> > http://homepages.cwi.nl/~ralf/syb3/code.html dies in make test on the
> > first test with
> >
> > lgmaclt:~/work/src/projex/biosimilarity/HS1/Process/haskell/SYB3 lgm$
> > make test
> > make test1 stem=geq1
> > ghci -fglasgow-exts -fallow-overlapping-instances
> > -fallow-undecidable-instances -v0 geq1.hs < Main.in > geq1.out
> >
> > geq1.hs:27:34:
> > Inferred type is less polymorphic than expected
> >   Quantified type variable `a1' escapes
> > Probable cause: `geq'' is applied to too few arguments
> > In the first argument of `gzipWithQ', namely `geq''
> > In the first argument of `and', namely `(gzipWithQ geq' x y)'
> >
> > :1:0: Not in scope: `main'
> > diff -b geq1.out geq1.ref
> > 0a1,4
> > > True
> > > False
> > > False
> > > True
> > make[1]: *** [test1] Error 1
> > make: *** [test] Error 2
> > lgmaclt:~/work/src/projex/biosimilarity/HS1/Process/haskell/SYB3 lgm$
> >
> > Is there a newer version of this codebase? Has this functionality been
> > folded into mainline Haskell tree somewhere?
> >
> > Best wishes,
> >
> > --greg
> >
> > --
> > L.G. Meredith
> > Managing Partner
> > Biosimilarity LLC
> > 505 N 72nd St
> > Seattle, WA 98103
> >
> > +1 206.650.3740
> >
> > http://biosimilarity.blogspot.com
> > ___
> > Haskell-Cafe mailing list
> > Haskell-Cafe@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] surprised by type class binding -- is this a bug?

[Greg Meredith]

Haskellians,

i'm sure i don't understand type classes, yet. Still, i was surprised at
ghci's response to the code below. Clues gratefully accepted.

Best wishes,

--greg

-- transcript
-- Prelude> :l grn
-- [1 of 1] Compiling GeneticRegulatoryNetwork ( grn.hs, interpreted )

-- grn.hs:33:35:
--Couldn't match expected type `b1' (a rigid variable)
--   against inferred type `b' (a rigid variable)
--  `b1' is bound by the type signature for `sequence' at grn.hs:25:36
--  `b' is bound by the instance declaration at grn.hs:31:0
--  Expected type: [b1]
--  Inferred type: [b]
--In the expression: molecules
--In the definition of `sequence':
--sequence (Site l1 molecules) = molecules
-- Failed, modules loaded: none.
-- Prelude>

{-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-}
-- -*- mode: Haskell;-*-
-- Filename:grn.hs
-- Authors: lgm
-- Creation:Thu Dec  6 15:38:26 2007
-- Copyright:   Not supplied
-- Description:
-- 

module GeneticRegulatoryNetwork
where

data Segment p =
Nil
  | Section [p] (Segment p)
deriving (Eq, Show)

class BindingMolecule b l | b -> l where
name:: b -> l
complement  :: b -> b
complements :: b -> Bool

class Locale s l1 l2 | s -> l1 l2 where
label   :: s -> l1
sequence:: (BindingMolecule b l2) => s -> [b]
provides:: (BindingMolecule b l2) => s -> [b] -> Bool
matches :: (BindingMolecule b l2) => s -> [b] -> Bool

data (BindingMolecule b l2) => Site b l1 l2 = Site l1 [b] deriving (Eq,
Show)

instance (BindingMolecule b l2) => Locale (Site b l1 l2) l1 l2 where
label(Site l1 _)  = l1
sequence (Site l1 molecules) = molecules
provides (Site l1 molecules) molecules' = False -- tbd
matches  (Site l1 molecules) molecules' = False -- tbd



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Re: surprised by type class binding -- is this a bug?

[Greg Meredith]

Haskellians,

Belay that. i see the problem.

Best wishes,

--greg

On Dec 6, 2007 11:11 PM, Greg Meredith <[EMAIL PROTECTED]>
wrote:

> Haskellians,
>
> i'm sure i don't understand type classes, yet. Still, i was surprised at
> ghci's response to the code below. Clues gratefully accepted.
>
> Best wishes,
>
> --greg
>
> -- transcript
> -- Prelude> :l grn
> -- [1 of 1] Compiling GeneticRegulatoryNetwork ( grn.hs, interpreted )
>
> -- grn.hs:33:35:
> --Couldn't match expected type `b1' (a rigid variable)
> --   against inferred type `b' (a rigid variable)
> --  `b1' is bound by the type signature for `sequence' at grn.hs:25:36
> --  `b' is bound by the instance declaration at grn.hs:31:0
> --  Expected type: [b1]
> --  Inferred type: [b]
> --In the expression: molecules
> --In the definition of `sequence':
> --sequence (Site l1 molecules) = molecules
> -- Failed, modules loaded: none.
> -- Prelude>
>
> {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-}
> -- -*- mode: Haskell;-*-
> -- Filename:grn.hs
> -- Authors: lgm
> -- Creation:Thu Dec  6 15:38:26 2007
> -- Copyright:   Not supplied
> -- Description:
> -- 
>
> module GeneticRegulatoryNetwork
> where
>
> data Segment p =
> Nil
>   | Section [p] (Segment p)
> deriving (Eq, Show)
>
> class BindingMolecule b l | b -> l where
> name:: b -> l
> complement  :: b -> b
> complements :: b -> Bool
>
> class Locale s l1 l2 | s -> l1 l2 where
> label   :: s -> l1
> sequence:: (BindingMolecule b l2) => s -> [b]
> provides:: (BindingMolecule b l2) => s -> [b] -> Bool
> matches :: (BindingMolecule b l2) => s -> [b] -> Bool
>
> data (BindingMolecule b l2) => Site b l1 l2 = Site l1 [b] deriving (Eq,
> Show)
>
> instance (BindingMolecule b l2) => Locale (Site b l1 l2) l1 l2 where
> label(Site l1 _)  = l1
> sequence (Site l1 molecules) = molecules
> provides (Site l1 molecules) molecules' = False -- tbd
> matches  (Site l1 molecules) molecules' = False -- tbd
>
>
>
> --
> L.G. Meredith
> Managing Partner
> Biosimilarity LLC
> 505 N 72nd St
> Seattle, WA 98103
>
> +1 206.650.3740
>
> http://biosimilarity.blogspot.com




-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] grammars and generics

[Greg Meredith]

Haskellians,

Here is an idea so obvious that someone else must have already thought of it
and worked it all out. Consider the following grammar.

N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0
N1 ::= T3 N0

where Ti (0 <= i < 4) are understood to be terminals.

Using generics we can translate each production independently of the others.
Like so:

[| N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0  |]
=
data N0 n1 = T0 n1 | T1 n1 (N0 n1) | T2 (N0 n1) (N0 n1) deriving (Eq, Show)

[| N1 ::= T3 N0 |]
=
data N1 n0 = T3 n0 deriving (Eq, Show)

Then, we can compose the types to get the recursive grammar.

data G = N0 (N1 G) deriving (Eq, Show)

This approach has the apparent advantage of treating each production
independently and yet being compositional.

Now, let me de-obfuscate the grammar above. The first production should be
very familiar.

Term ::= Var Name | Abstraction Name Term | Application Term Term

The generics-based translation of this grammar yields something we already
know: we can use lots of different types to work as identifiers. This is
something that the nominal of Gabbay, Pitts, et al, have factored out
nicely.

The second production can be treated independently, but composes well with
the first.

Name ::= Quote Term

This illustrates that a particularly interesting class of names is one that
requires we look no further than our original (parametric) data type.

So, my question is this. Does anyone have a reference for this approach to
translation of grammars?

Best wishes,

--greg


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] grammars and generics

[Greg Meredith]

Dusan,

Excellent point. To close it off, you need to add an "empty" alternative.
Thus, the corrected form would be

N0 ::= TEmpty | T0 N1 | T1 N1 N0 | T2 N0 N0
N1 ::= T3 N0

In the lambda calculus, this would show up as a constant term, say 0, that
would have to be treated in the operational semantics. See my ltu
posting<http://lambda-the-ultimate.org/node/1930>of a year ago.

Best wishes,

--greg

On Dec 11, 2007 11:33 AM, Dušan Kolář <[EMAIL PROTECTED]> wrote:

> Hello,
>
>  I can't help you with the Haskell question as I'm not really in that
> much. Nevertheless, your grammar is non-generating one - that means, it
> cannot generate any sentence. If the starting non-terminal is N0 then
> there is no production generating a string of terminals, thus, both
> non-terminals (even if reachable from the staring one) are so called
> non-generating ones (they can be freely removed from the grammar and all
> involved productions too).
> Thus, you get empty grammar. Isn't that the problem? Shouldn't the
> grammar be like:
>
> N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0
> N1 ::= T3 T4
>
> ?
>
> Best regards
>
> Dusan
>
>
> Greg Meredith wrote:
> > Haskellians,
> >
> > Here is an idea so obvious that someone else must have already thought
> > of it and worked it all out. Consider the following grammar.
> >
> > N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0
> > N1 ::= T3 N0
> >
> > where Ti (0 <= i < 4) are understood to be terminals.
> >
> > Using generics we can translate each production independently of the
> > others. Like so:
> >
> > [| N0 ::= T0 N1 | T1 N1 N0 | T2 N0 N0  |]
> > =
> > data N0 n1 = T0 n1 | T1 n1 (N0 n1) | T2 (N0 n1) (N0 n1) deriving (Eq,
> > Show)
> >
> > [| N1 ::= T3 N0 |]
> > =
> > data N1 n0 = T3 n0 deriving (Eq, Show)
> >
> > Then, we can compose the types to get the recursive grammar.
> >
> > data G = N0 (N1 G) deriving (Eq, Show)
> >
> > This approach has the apparent advantage of treating each production
> > independently and yet being compositional.
> >
> > Now, let me de-obfuscate the grammar above. The first production
> > should be very familiar.
> >
> > Term ::= Var Name | Abstraction Name Term | Application Term Term
> >
> > The generics-based translation of this grammar yields something we
> > already know: we can use lots of different types to work as
> > identifiers. This is something that the nominal of Gabbay, Pitts, et
> > al, have factored out nicely.
> >
> > The second production can be treated independently, but composes well
> > with the first.
> >
> > Name ::= Quote Term
> >
> > This illustrates that a particularly interesting class of names is one
> > that requires we look no further than our original (parametric) data
> > type.
> >
> > So, my question is this. Does anyone have a reference for this
> > approach to translation of grammars?
> >
> > Best wishes,
> >
> > --greg
> >
> >
> > --
> > L.G. Meredith
> > Managing Partner
> > Biosimilarity LLC
> > 505 N 72nd St
> > Seattle, WA 98103
> >
> > +1 206.650.3740
> >
> > http://biosimilarity.blogspot.com
> > 
> >
> > ___
> > Haskell-Cafe mailing list
> > Haskell-Cafe@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
> --
>
>  Dusan Kolartel: +420 54 114 1238
>  UIFS FIT VUT Brno  fax: +420 54 114 1270
>  Bozetechova 2   e-mail: [EMAIL PROTECTED]
>  Brno 612 66
>  Czech Republic
>
> --
>
>


-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] re: generics and grammars

[Greg Meredith]

Ken,

Thanks for the references! Have two-level types been applied to parser
generation?

Best wishes,

--greg

Greg Meredith <[EMAIL PROTECTED]> wrote in article
<[EMAIL PROTECTED]
> > in gmane.comp.lang.haskell.cafe:
> > Here is an idea so obvious that someone else must have already thought
> of it
> > and worked it all out. Consider the following grammar.
>
> Hello!
>
> If I understand your basic idea correctly, it is to split a recursive
> data type into two parts, a non-recursive type constructor and a
> knot-tying recursive type.  This idea has been christened "two-level
> types" by
>
>Tim Sheard and Emir Pasalic. 2004.  Two-level types and
>parameterized modules.  Journal of Functional Programming
>14(5):547-587.
>
> The idea dates earlier, to initial-algebra semantics and "functional
> programming with bananas and lenses":
>
>Mark P. Jones. 1995.  Functional programming with overloading and
>higher-order polymorphism.  In Advanced functional programming:
>1st international spring school on advanced functional programming
>techniques, ed. Johan Jeuring and Erik Meijer, 97-136.  Lecture
>Notes in Computer Science 925.
>
> http://web.cecs.pdx.edu/~mpj/pubs/springschool.html<http://web.cecs.pdx.edu/%7Empj/pubs/springschool.html>
>
>Erik Meijer, Maarten Fokkinga, and Ross Paterson. 1991.  Functional
>programming with bananas, lenses, envelopes and barbed wire.  In
>Functional programming languages and computer architecture: 5th
>conference, ed. John Hughes, 124-144.  Lecture Notes in Computer
>Science 523.
>
> http://research.microsoft.com/~emeijer/Papers/fpca91.pdf<http://research.microsoft.com/%7Eemeijer/Papers/fpca91.pdf>
>
> Cheers,
>Ken
>

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
505 N 72nd St
Seattle, WA 98103

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] NW Functional Programming Interest Group

[Greg Meredith]

All,

Apologies for multiple listings.

A small cadre of us are organizing a Northwest Functional Programming
Interest Group (hey... NWFPIG, that's kinda funny). Our first official
meeting is at the

The Seattle Public Library
1000 - 4th Ave.
Seattle, WA  98104

from 17:00 - 18:00 on February 20th.

On the first meeting's agenda we'll be

   - giving people who are interested in or actively using FP for work or
   play a chance to meet
   - seeking to build up a pipeline of presentations and guest speakers
   - trying to keep organizational mishigosh to a minimum

Hope to see you there.

Monadically yours,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Fwd: NW Functional Programming Interest Group

[Greg Meredith]

All,

Apologies for multiple listings.

This is just a friendly reminder that a small cadre of us are organizing a
Northwest Functional Programming Interest Group. Our first official meeting
is today at the

The Seattle Public Library
1000 - 4th Ave.
Seattle, WA  98104

Spiral 6 Conference Room from 17:00 - 18:00 on February 20th.

On the first meeting's agenda we'll be

   - giving people who are interested in or actively using FP for work or
   play a chance to meet
   - seeking to build up a pipeline of presentations and guest speakers
   - trying to keep organizational mishigosh to a minimum

Hope to see you there.

Monadically yours,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Naming as infection

[Greg Meredith]

All,

Here  is
a deliberately provocative posting (with running code and a shameless plug
for BNFC) on the process of introducing naming and name management into the
design of data structures. Comments greatly appreciated.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] 2-level type analysis of introducing naming into data types

[Greg Meredith]

All,

The following Haskell code gives a 2-level type analysis of a
functorial approach to introducing naming and name management into a
given (recursive) data type. The analysis is performed by means of an
example (the type of Conway games). The type is naturally motivated
because through the application of one functor we arrive at a lambda
calculus with an embedded type for Conway games (giving access to
field operations for arithmetic on virtually every type of number ever
considered) -- while another functor provides a process calculi with a
similarly embedded data type. Moreover, the technique extends to a
wide variety of algebra(ic data type)s.

The recipe is simple.
1. Provide a recursive specification of the algebra.
Example. data Game = Game [Game] [Game]
2. Abstract the specification using parametric polymorphism.
Example. data PolyGame g = PolyGame [g] [g]
2.a. Identify the 2-Level knot-tying version of the recursive type
  Example. data RGame = RGame (PolyGame RGame)
3. Insert name management type into the knot-tying step of the 2-Level
version
Example.

data DefRefGame var = DefRefGame (PolyDefRef var (PolyGame (DefRefGame
var)))

given the basic form

data PolyDefRef var val = Def var (PolyDefRef var val) (PolyDefRef var
val)
 | Ref var
 | Val val

is the name management technology

We illustrate the idea with two other forms of name management
technology: the lambda calculus and the pi-calculus. Then we show that
names themselves can be provided as the codes of the terms of the new
type.
At the root of this work is the proposal that communication begins from the
concrete -- a "closed" recursive type -- representing some observation or
proposal of how something works in the universe (of discourse). As said
proposal develops or is explored, calculations need to rely more and more on
naming (i.e. "let x stand for ... in ..."). Thus, this capability is
"injected" into the data type -- moving from the concrete to the general.
The analysis above provides a concrete, disciplined procedure for achieving
this in both a sequential and concurrent computational setting.

Best wishes,

--greg

-- This code summarizes the previous post. It shows that for any
-- "closed" recursive type we can devise a closed extension of this
-- type embedding the type as a value in the lambda calculus

module Grho(
Game, PolyGame, PolyDefRef, DefRefGame, QDefRefGame
,Term, GTerm, QGTerm
,Sum, Agent, Process, GProcess, QGProcess
) where

-- Conway's original data type
data Game = Game [Game] [Game] deriving (Eq,Show)

-- Abstracting Conway's data type
data PolyGame g = PolyGame [g] [g] deriving (Eq,Show)

-- Recovering Conway's data type in terms of the abstraction
newtype RGame = RGame (PolyGame RGame) deriving (Eq,Show)

-- RGame ~ Game

-- Expressions with references and values
data PolyDefRef var val = Def var (PolyDefRef var val) (PolyDefRef var
val)
 | Ref var
 | Val val
   deriving (Eq,Show)

-- Games with references and values
data DefRefGame var = DefRefGame (PolyDefRef var (PolyGame (DefRefGame
var))) deriving (Eq,Show)

-- Games with references and values in which variables are quoted
games
newtype QDefRefGame = QDefRefGame (DefRefGame QDefRefGame) deriving
(Eq,Show)

-- Lambda terms with values
data Term var val = Var var
  | Abs [var] (Term var val)
  | App (Term var val) [Term var val]
  | Value val
deriving (Eq,Show)

-- Lambda terms with games as values
data GTerm var = Term var (PolyGame (GTerm var)) deriving (Eq,Show)

-- Lambda terms with games as values and variables that are quoted
lambda terms
data QGTerm = GTerm QGTerm

-- And the following defn's/eqns take it one step further by providing
a notion of process with
-- Conway games as embedded values

-- Process terms with values
-- Sums
data Sum var val agent = PValue val
   | Locate var agent
   | Sum [Sum var val agent]
 deriving (Eq,Show)

-- One of the recent observations i've had about the process calculi
-- is that '0' is Ground, and as such is another place to introduce
-- new Ground. Thus, we can remove the production for '0' and replace
-- it with the types of values we would like processes to 'produce';
-- hence the PValue arm of the type, Sum, above. Note that this
-- design choice means that we can have expressions of the form
-- v1 + v2 + ... + vk + x1A1 + ... xnAn
-- i am inclined to treat this as structurally equivalent to
-- x1A1 + ... xnAn -- but there is another alternative: to allow
-- sums of values to represent superpositions

-- Agents
data Agent var proc = Input [var] proc
| Output [proc]
  deriving (Eq,Show)

-- Processes
data Process var sum = Case sum
 | Deref var

Re: [Haskell-cafe] 2-level type analysis of introducing naming into data types

[Greg Meredith]

Justin,

Thanks for the query. Here are the considerations/concerns i with which i
was working.

   - Data is *not* native to either lambda or pi-calculi
  - operational encodings for simple types (Bool and Nat) were
  given near the inception of these calculi
  - embeddings of these types took several decades to work out
  semantically (full abstraction for PCF is an example of the difficulty in
  the case of lambda; i submit that we haven't really figured out the
  corresponding story for concurrency, yet)
  - On the other hand, naming is necessary for effective work with
   any moderately complex recursive data structure
  - this is so common we are like fish to this water -- we don't
  even recognize when we're doing it (as an example see Conway's original
  presentation of numbers as games -- he starts using naming but does not
  acknowledge this very subtle shift in the mathematics)
  - Lambda and pi-calculi are the best name management technology
   we know
   - Is there a natural and elementary way to provide the benefits of
   these name management technologies for dealing with these concrete data
   structures?

Yes, it turns out that the simplest way finds solutions as sitting between
least and greatest fixpoints of the functor that pops out of the 2-level
type analysis (hence the pretty domain equations that are expressed as
Haskell data types). Moreover, it also gives a freebie way to embed data
types in these decidedly operational calculi. Further, as i only recently
realized it gives a way to compare Brian Smith style reflection with the
reflection Matthias Radestock and i identified with the rho-calculus. See
this<http://svn.biosimilarity.com/src/open/mirrororrim/rho/trunk/src/main/haskell/grho.hs>new
code.

Best wishes,

--greg

On Mon, Mar 17, 2008 at 8:52 AM, Justin Bailey <[EMAIL PROTECTED]> wrote:

> 2008/3/15 Greg Meredith <[EMAIL PROTECTED]>:
> > All,
> >
> >
> > The following Haskell code gives a 2-level type analysis of a
> >  functorial approach to introducing naming and name management into a
> >  given (recursive) data type. The analysis is performed by means of an
>
> What's the upshot of this? That is, what does this analysis give you?
> I mostly follow the argument but I don't understand the benefits. I
> feel like I'm missing something.
>
> Justin
>



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] NW Functional Programming Interest Group

[Greg Meredith]

All,

Apologies for multiple listings.

A small cadre of us are organizing a Northwest Functional Programming
Interest Group (hey... NWFPIG, that's kinda funny). Our next
meeting is at the

The Seattle Public Library
1000 - 4th Ave.
Seattle, WA  98104

from 18:30 - 20:00 on March 19th.

On this meeting's agenda

   - i'll give a highly idiosyncratic talk about the Curry-Howard
   isomorphism
   - followed an informal discussion section

Hope to see you there.

Monadically yours,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Haskell vs Scheme

[Greg Meredith]

Douglas,

Excellent questions you posed to Simon P-J -- who then forwarded them to the
Haskell Cafe list. By way of answering i should say i was a Schemer from the
get-go; it was really the first programming language i studied as an
undergraduate majoring in maths at Oberlin in the early 80's. Eventually, i
went on to design and build my own language (at MCC with Christine
Tomlinson, the principal investigator) called Rosette. While Scheme was
Sussman and Abelson's way of making sense of Hewitt's ideas in a sequential
setting Rosette was our way of doing the full banana -- including the
actor-based form of concurrency as well as both structural and 3-Lisp-style
procedural reflection and a whole host of other advanced features. So, i was
naturally profoundly frustrated when the world at large turned to languages
like C, C++ and even Java. i have been waiting more than 20 years for the
industry to catch up to the joys of advanced language design.

Now that the industry has taken a shine to functional languages again i have
been spending more time with the various modern flavors and have to say that
while each of the major contenders (ML, OCaml, Erlang, Scala, Haskell) have
something to be said for them, Haskell stands out among them. Haskell enjoys
a particular form of mental hygiene that few other languages enjoy. Its
syntax, by comparison with Scheme, is remarkably concise -- and, the
importance of syntax is almost impossible to gauge because at the end of the
day it is code one is staring at ;-). The chief semantic differences that
make a difference to my mind may be classified as follows.

   - types
   - monads
   - meta-programming

In order, then: at its outset Haskell made a strong commitment to a potent
(static) typing scheme. Even if types can be layered on Scheme, the two
language design vectors are remarkably different and give programming a
different feel. As a result of my academic and professional training i have
come to rely heavily on types as a development discipline. In fact, if i
cannot devise a sensible type "algebra" for a given (application) domain
then i feel i don't really have a good understanding of the domain. One way
of seeing this from the Schemer point if view is that the deep sensibility
embodied in the Sussman and Abelson book of designing a DSL to solve a
problem is further refined by types. Types express an essential part of the
grammar of that language. In Haskell the close connection between typing and
features like pattern-matching are also part of getting a certain kind of
coherence between data and control. Again, this can be seen as taking the
coherence between data and control -- already much more evident in Scheme
than say C or C++ or even Java -- up a notch.

Haskell's language-level and library support for monads are really what set
this language apart. i feel pretty confident when i voice my opinion that
the most important contribution to computing (and science) that functional
programming has made in the last 15 years has been to work out practical
presentations of the efficacy of the notion of monad. As a Schemer i'm sure
you understand the critical importance of composition and compositional
design. The monad provides an important next step in our understanding of
composition effectively by making the notion parametric along certain
dimensions. This allows a programmer to capture very general container
patterns and control patterns (as well as other phenomena) with a very
concise abstraction. Again, this could be layered onto Scheme, but Haskell
embraced monad as a central abstraction at the language design level and
this leads to very different approaches to programming.

Now, the place where Haskell and the other statically typed functional
languages have some catching up to do is meta-programming. Scheme, Lisp and
other languages deriving from the McCarthy branch of the investigation of
lambda-calculus-based programming languages enjoy a much longer and deeper
investigation of meta-programming constructs. While MetaOCaml stands out as
a notable exception i think it safe to say that 3-Lisp and Brown are pretty
strong evidence of the long history and much richer investigation of
meta-programming notions along the McCarthy branch than along the Milner
branch. The industry as a whole, i think, has embraced the value of
meta-programming -- witness (structural) reflection in such mainstream
languages as Java and C#. And the Milner branch family of languages are
moving rapidly to catch up -- see the efforts on generic programming like S
P-J's SYB or TemplateHaskell -- but the deep coherence evident in the
simplicity of the monadic abstraction has not met up with the deep coherence
of 3-Lisp, yet.

Anyway, that's my two cents... but i note that US currency is not worth what
it used to be.

Best wishes,

--greg

Message: 21
Date: Tue, 1 Apr 2008 11:18:25 +0100
From: Simon Peyton-Jones <[EMAIL PROTECTED]>
Subject: [Haskell-cafe] FW: Haskell
To: Haskell Cafe 
Cc: "[EM

[Haskell-cafe] NW Functional Programming Interest Group

[Greg Meredith]

All,

Apologies for multiple listings.

It's that time again. Our growing cadre of functionally-minded north
westerners
is meeting at the

The Seattle Public Library
1000 - 4th Ave.
Seattle, WA  98104

from 18:30 - 20:00 on April 16th.

This meeting's agenda is a little more fluid, but...

   - i would like to talk about a proposal i'm mulling over around a much
   more general account of the Curry-Howard isomorphism by way of iterated
   distributive laws for monads
   - we also need to get a couple more people on the hook to give a talk

Hope to see you there.

Monadically yours,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] NW Functional Programming Interest Group

[Greg Meredith]

All,

Apologies for multiple listings.

It's that time again. Our growing cadre of functionally-minded north
westerners
is meeting at the

The Seattle Public Library
*University Branch* 5009 Roosevelt Way N.E. *Seattle*, WA 98105 206-684-4063

from 18:30 - 20:00 on May 28th.

 Note the change in venue 

Agenda

   - JP has graciously offered to give a talk on darcs
   - we also need to continue to fill the talk pipeline

Hope to see you there.

Monadically yours,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] NW Functional Programming Interest Group

[Greg Meredith]

All,

Apologies for multiple listings.

A small cadre of us, collectively known as the Northwest Functional
Programming
Interest Group, have been meeting monthly to discuss all things functional.
Our next meeting is at

The Seattle Public Library
5009 Roosevelt Way N.E. *
Seattle*, WA 98105
206-684-4063

from 18:30 - 19:50 on June 25th.

We'd hoped to have Andrew Birkett talk on a Haskell implementation of an
emacs-like editor, but sadly could not secure a meeting venue before
Andrew's flight back to the UK. Maybe we can set up a skype session for a
presentation by Andrew in future. Since it's so late in the game i will step
in and offer a presentation on a compositional representation of graphs i've
been tinkering 
with
-- unless someone has something they'd like to talk about at a moment's
notice.

Hope to see you there.

Monadically yours,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com

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

re: [Haskell-cafe] Swapping Monads

[Greg Meredith]

Dominic,

You can also reference Eugenia Cheng's paper on
arXiv
.

Best wishes,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] Fwd: NW Functional Programming Interest Group

[Greg Meredith]

All,

Apologies for multiple listings.

This is just a friendly reminder to Northwest functionally minded folks that
this month's meeting is to be held

The Seattle Public Library
5009 Roosevelt Way N.E.
Seattle, WA 98105
206-684-4063

from 18.30 - 19:45 on July 23rd.

We'll be getting a demo of a scala-lift-based application that compiles a
graphical rendition of functional expressions into expressions in a
functional language.

Hope to see you there.

Monadically yours,

--greg

-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com



-- 
L.G. Meredith
Managing Partner
Biosimilarity LLC
806 55th St NE
Seattle, WA 98105

+1 206.650.3740

http://biosimilarity.blogspot.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe