[Haskell-cafe] Monadic Design Patterns for the Web Chapter Review
*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] Contract opportunity with Biosimilarity LLC
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] Fwd: C9 video in the Monadic Design Patterns for the Web series
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 lgreg.mered...@gmail.com 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 Beckmanhttp://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 gameshttp://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 2http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Greg-Meredith-Monadic-Design-Patterns-for-the-Web-2-of-n ** *See* part 3http://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
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 mo...@deepbondi.net 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 lgreg.mered...@gmail.com 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 Beckmanhttp://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
[Haskell-cafe] Monadic Design Patterns for the Web C9 Video Series -- Part 2 is live!
Dear Haskellians, Just in time for the Holidays! Best wishes, --greg -- Forwarded message -- From: Charles Torre cto...@microsoft.com Date: Tue, Dec 14, 2010 at 11:31 AM Subject: Part 2 is live! To: Meredith Gregory lgreg.mered...@gmail.com 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] Monads in the 'hood
Dear Haskellians, Keepin' it light. For your amusement this weekend: monads in the hoodhttp://www.youtube.com/watch?v=rYANU61J5eY . 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 Kickstarter project
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 projecthttp://www.kickstarter.com/projects/1499410734/monadic-design-patterns-for-the-web-bookto 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 http://www.youtube.com/watch?v=qOj0tgQDSeQ. 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] lambda terms in which the variables are positions in lambda terms
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
Re: [Haskell-cafe] C9 video on monads and coordinate systems
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 felipe.le...@gmail.com wrote: On Wed, Jul 7, 2010 at 8:00 PM, Greg Meredith lgreg.mered...@biosimilarity.com 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] C9 video on monads and coordinate systems
Dear Haskellians, You may be interested in this video i did with Brian Beckmanhttp://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
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 http://monadic.eventbrite.com/. 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 presentation of delimited continuations and dissection
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] Composition, delegation and interfaces -- a 20K ft critique of Noop
Dear Programmers, Someone just asked me to give my opinion on Noop's composition proposalhttp://code.google.com/p/noop/wiki/ProposalForComposition. It reminds me a little bit of Selfhttp://en.wikipedia.org/wiki/Self_%28programming_language%29which found its way into JavaScript. It also reminds me a little of Haskell's type classes http://en.wikipedia.org/wiki/Type_class. 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 constructors of which are
Re: [Haskell-cafe] Haskell on JVM
Jason, CAL's syntax is not std Haskell syntax. Best wishes, --greg On Thu, Jun 25, 2009 at 11:10 AM, Jason Dusek jason.du...@gmail.com wrote: 2009/06/24 Greg Meredith lgreg.mered...@biosimilarity.com: 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] Haskell on JVM
Simon, et al, It might be interesting to look at CALhttp://labs.businessobjects.com/cal/as 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 simo...@microsoft.com Subject: RE: [Haskell-cafe] Haskell on the iPhone To: Rick R rick.richard...@gmail.com, Haskell Cafe haskell-cafe@haskell.org 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
[Haskell-cafe] 3 applications of indexed composition as a language design principle
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 herehttp://biosimilarity.blogspot.com/2009/01/3-applications-of-indexed-composition.html. 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
Re: [Haskell-cafe] haskell compiler never comes back
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 linkhttp://paste.pocoo.org/show/95533/ . Best wishes, --greg On Tue, Dec 16, 2008 at 10:28 AM, Ian Lynagh ig...@earth.li 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 linkhttp://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] haskell compiler never comes back
Haskellians, The simple-minded and smallish code sample at this linkhttp://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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: haskell compiler never comes back
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 linkhttp://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
George, Thanks for the response. If i take out the AllowUndecidableInstances i get no complaints and the compiler hangs. See thishttp://paste.pocoo.org/show/95523/. 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 por...@porg.es 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
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 daniel.is.fisc...@web.dewrote: 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 linkhttp://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
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 daniel.is.fisc...@web.dewrote: 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 linkhttp://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 -- 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: monads with take-out options
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] monads with take-out options
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
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 only have once value to return. head might find one value to return, no values, or even multiple values. A better example of a monad that always has a left inverse to return is ((,) w), where w
Re: [Haskell-cafe] monads with take-out options
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
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 is program or data? That may be too simplistic for your
re: [Haskell-cafe] ANNOUNCE: rewriting-0.1
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
Re: [Haskell-cafe] Semantic Domain, Function, and denotational model.....
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 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
[Haskell-cafe] Ajax-Haskell framework?
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
[Haskell-cafe] Semantic Domain, Function, and denotational model.....
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 Scotthttp://en.wikipedia.org/wiki/Dana_Scott. In a nutshell, we have essentially three views of a computation - Operational http://en.wikipedia.org/wiki/Operational_semantics -- computation is captured in a program and rules for executing it - Logical http://en.wikipedia.org/wiki/Proof-theoretic_semantics -- computation is captured in a proof and rules for normalizing it - Denotational http://en.wikipedia.org/wiki/Denotational_semantics -- 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 aimhttp://en.wikipedia.org/wiki/Domain_theoryis 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 abstractionhttp://en.wikipedia.org/wiki/Denotational_semantics#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 problemhttp://en.wikipedia.org/wiki/Programming_language_for_Computable_Functions). 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 equivalencehttp://encyclopedia2.thefreedictionary.com/Contextual+equivalence-- behaves the same in all contexts - bisimulation http://en.wikipedia.org/wiki/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 haskell-cafe@haskell.org 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_semantics which talks about semantic domain for the
[Haskell-cafe] Fwd: NW Functional Programming Interest Group
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
re: [Haskell-cafe] Swapping Monads
Dominic, You can also reference Eugenia Cheng's paper on arXivhttp://arxiv.org/abs/0710.1120 . 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] NW Functional Programming Interest Group
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 withttp://biosimilarity.blogspot.com/2008/06/algebra-of-graphs-individually-and.htmlh -- 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 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
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
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] Haskell vs Scheme
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
[Haskell-cafe] NW Functional Programming Interest Group
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
Re: [Haskell-cafe] 2-level type analysis of introducing naming into data types
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 thishttp://svn.biosimilarity.com/src/open/mirrororrim/rho/trunk/src/main/haskell/grho.hsnew 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] 2-level type analysis of introducing naming into data types
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 |
[Haskell-cafe] Naming as infection
All, Here http://biosimilarity.blogspot.com/2008/03/naming-as-dialectic.html 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] Fwd: NW Functional Programming Interest Group
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] re: generics and grammars
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.htmlhttp://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.pdfhttp://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] grammars and generics
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
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 postinghttp://lambda-the-ultimate.org/node/1930of 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] surprised by type class binding -- is this a bug?
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?
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
Re: [Haskell-cafe] SYB3 codebase
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)' interactive: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] SYB3 codebase
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)' interactive: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
[Haskell-cafe] generic programming tutorial?
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] Re: help getting happy
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] help getting happy
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] haskell and reflection
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
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
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?
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
Re: [Haskell-cafe] Re: towards a new foundation for set theory with atoms
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] towards a new foundation for set theory with atoms
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
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: RE [Haskell-cafe] Monad Description For Imperative
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 haskell-cafe@haskell.org 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] Re: monads and groups -- instead of loops
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
[Haskell-cafe] monads and groups -- instead of loops
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
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
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
Re: [Haskell-cafe] let vs do?
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] let vs do?
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?
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
[Haskell-cafe] Re: copy-on-write monad?
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] copy-on-write monad?
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] Java Monads?
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] Monads and constraint satisfaction problems (CSP)
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)
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 haskell-cafe@haskell.org 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
Re: [Haskell-cafe] Re: efficient and/or lazy partitions of a multiset
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] Re: efficient and/or lazy partitions of a multiset
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
[Haskell-cafe] efficient and/or lazy partitions of a multiset
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] On reflection
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] Re: haskell question
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] Re: how would Albus Dumbledore sell Haskell
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
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 bithink/i/b 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