May 2007 - Haskell-Cafe

Re: [Haskell-cafe] Safe forward-mode AD in Haskell?
by Björn Buckwalter 09 May '07

09 May '07

> > d :: Num a => (forall b. (Num b) => (a -> b) -> b -> b) -> a -> a > > d f x = let (Bundle y y') = f lift (Bundle x 1) in y' > > The key change is in the type of d, which now accepts a polymorphic > function on numbers, but passes in a "lift" function, which allows us to > pass in higher-level variables. In one sense this function is ugly. In > another sense, it's prettier, as you can now hide *all* of the Bundle data > in a "differentiation" module. To summarize: In my original version it is necessary to export 'd' and 'lift', which both expose 'Bundle' through their type signatures (and 'lift' even returns a 'Bundle', though how one could (ab)use it outside the intended context of a 'd' escapes me). In constrast, with your variation only 'd' need be exported and everything else in the module (including 'Bundle) is completely hidden. The cost is that functions must be "conditioned" before they can be differentiated. Thanks for your input! -Bjorn

1 0

Roles == type classes ???
by Magnus Therning 09 May '07

09 May '07

The way roles/traits are described in [1] (and the pages it links to) make me think of Haskell type classes. Am I completely off in doing that? /M [1]: http://griddlenoise.blogspot.com/2007/05/traits-roles-as-alternative-to-abs… -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus(a)therning.org Jabber: magnus.therning(a)gmail.com http://therning.org/magnus Software is not manufactured, it is something you write and publish. Keep Europe free from software patents, we do not want censorship by patent law on written works. Those who would give up Essential Liberty to purchase a little Temporary Safety, deserve neither Liberty nor Safety -- Benjamin Franklin, Historical Review of Pennsylvania, 1759

2 1

Re: Cost of Overloading vs. HOFs
by Conal Elliott 09 May '07

09 May '07

[switching to haskell-cafe] thanks for the explanation, John. doesn't the list cases mentioned in the definition of (+) below assume whole program, in order to know all Num instances? On 5/4/07, John Meacham <john(a)repetae.net> wrote: > > On Fri, May 04, 2007 at 05:06:10PM -0700, Conal Elliott wrote: > > Cool. You know which types to consider because jhc is a whole-program > > compiler? > > Yes. though, i have since redone the back end so there is no technical > reason for it to be whole program any more, you can just benefit from > more optimizations that way. The old backend required global knowledge > to compile at all. > > > > Given the whole program, why not monomorphize, and inline away all of > the > > dictionaries? > > Well that is the thing, there are no dictionaries at all, the only extra > arguments passed in are the types so, > > f :: forall a . (Foo a, Baz a, Bar a Int, Bred a) => a -> a > > still is only passed the single hidden argument of 'a' since a case on > it will determine what method to use. > > (+) a x y = case a of > Int -> plusInt x y > Float -> plusFloat x y > > and so forth. a here is a type, of kind '*'. > > > since the method lookup is done explicitly via the case statement, it > can be optimized via standard transformations in nice ways. > > John > > > > > > > > > > - Conal > > > > On 5/4/07, John Meacham <john(a)repetae.net> wrote: > > > > > >On Fri, May 04, 2007 at 03:07:41PM -0700, Conal Elliott wrote: > > >> Does anyone know what became of Dictionary-free Overloading by > Partial > > >> Evaluation <http://web.cecs.pdx.edu/%7Empj/pubs/pepm94.html>? Is it > > >> impractical for some reason? > > > > > >jhc also uses a dictionary free approach, doing a case directly on the > > >type parameter. > > > > > >The nice thing about this is that _all_ methods can be determined by a > > >single case evaluation, because finding out the right instance for any > > >method will determine the right instance for all other methods too for > a > > >given type. The standard case-of-known-value optimization takes care of > > >later scrutinizations (method lookups) on the same type. > > > > > > John > > > > > > > > >-- > > >John Meacham - ⑆repetae.net⑆john⑈ > > >_______________________________________________ > > >Glasgow-haskell-users mailing list > > >Glasgow-haskell-users(a)haskell.org > > >http://www.haskell.org/mailman/listinfo/glasgow-haskell-users > > > > > > -- > > Glasgow-haskell-users mailing list > > Glasgow-haskell-users(a)haskell.org > > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users > > > -- > John Meacham - ⑆repetae.net⑆john⑈ > _______________________________________________ > Glasgow-haskell-users mailing list > Glasgow-haskell-users(a)haskell.org > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users >

2 1

Safe forward-mode AD in Haskell?
by Björn Buckwalter 09 May '07

09 May '07

Dear all, = Introduction = In [1] Siskind and Pearlmutter expose the danger of "perturbation confusion" in forward-mode automatic differentiation. In particular they state: "We discuss a potential problem with forward-mode AD common to many AD systems, including all attempts to integrate a forward-mode AD operator into Haskell." This literate Haskell message shows how, using a type system extension of the Glasgow Haskell Compiler[2] (GHC), we can statically guarantee that perturbation confusion does not occur. = Code = The below code closely follows the Haskell code in the appendices of [1]. It relies on GHC's arbitrary-rank polymorphism(?) extension to Haskell 98. > {-# OPTIONS_GHC -fglasgow-exts #-} In our definition of the 'Bundle' data type we add the phantom type 's', which will be the key to disambiguating between different application of the 'd' operator. > data Bundle s a = Bundle a a > instance Num a => Show (Bundle s a) where > showsPrec p (Bundle x x') = showsPrec p [x,x'] > instance Num a => Eq (Bundle s a) where > (Bundle x x') == (Bundle y y') = (x == y) > lift z = Bundle z 0 > instance Num a => Num (Bundle s a) where > (Bundle x x') + (Bundle y y') = Bundle (x + y) (x' + y') > (Bundle x x') * (Bundle y y') = Bundle (x * y) (x * y' + x' * y) > fromInteger z = lift (fromInteger z) > instance Fractional a => Fractional (Bundle s a) where > fromRational z = lift (fromRational z) We provide a type signature for 'd' where we existentially quantify the phantom type 's' to prevent mixing of bundles from different 'd' operators. > d :: Num a => (forall s. Bundle s a -> Bundle s a) -> a -> a > d f x = let (Bundle y y') = f (Bundle x 1) in y' The extential quantification makes the definition ] constant_one' x = d (\y -> x + y) 1 impossible since 'x' originates externally to the 'd' operator. GHC rejects the definition with a "Inferred type is less polymorphic than expected". In order to pass the compiler the definition must be changed to the corrected[1] version. > constant_one x = d (\y -> (lift x) + y) 1 > should_be_one_a = d (\x -> x * (constant_one x)) 1 > should_be_one_b = d (\x -> x * 1 ) 1 > violation_of_referential_transparency = should_be_one_a /= should_be_one_b = References = [1] http://www.bcl.hamilton.ie/~qobi/nesting/papers/ifl2005.pdf [2] http://haskell.org/ghc/

2 4

Re: Building the community
by Rick Moen 08 May '07

08 May '07

Back on December 14, Conrad Parker write: > On 15/12/06, Nicolas Frisby <nicolas.frisby(a)gmail.com> wrote: > > 2) The "welcome to the mailing list" message could say "if you're > > new to Haskell, please check this FAQ first". I'm talking big letters > > here; I'd even be OK with <marquee>. > > .. hence I'd caution against such a rule. Part of the reason this > community is welcoming is because there is no such barrier for people > new to Haskell to ask questions. Everyone has a different mathematics > ability and programming experience, and an ambiguously posed question > is often just scratching the surface of what someone really wants to > know. It's great that this community recognises that and responds > accordingly. > > By contrast, many technical communities follow the advice of a > document called "How to ask questions the smart way" by Eric Raymond > and Rick Moen [0]. That would be the guy I shave. > Although it contains some useful advice for individuals who want to > find the answers to simply definable technical questions, imposing > that advice on people who ask questions often ends up being elitist. I just re-read the essay (which some love, some hate, and I personally find too verbose to be useful), and find no suggestion therein that anything whatsoever should be "imposed" on querents. Nada. Rein du tout. > At best, answering questions (the smart way ;-) should be thought of > as taking part in a mathematical dialogue, not as a game of wits where > the original poster is only given one chance to precisely formulate > their question. I'll be glad to send US $100 to Conrad if he show me where Eric's and my essay suggests the latter -- as a bug bounty. > For an example from that document: > > What we [hackers] are, unapologetically, is hostile to people who > seem to be unwilling to think or to do their own homework before > asking questions. People like that are time sinks -- they take > without giving back, and they waste time we could have spent on > another question more interesting and another person more worthy of > an answer. We call people like this "losers" (and for historical > reasons we sometimes spell it "lusers"). > > I hope the Haskell community never adopts such an arrogant tone. It's unfortunate that Conrad saw fit to cut out the explanatory comments that immediately _follow_ that quoted passage: We realize that there are many people who just want to use the software we write, and who have no interest in learning technical details. For most people, a computer is merely a tool, a means to an end; they have more important things to do and lives to live. We acknowledge that, and don't expect everyone to take an interest in the technical matters that fascinate us. Nevertheless, our style of answering questions is tuned for people who do take such an interest and are willing to be active participants in problem-solving. That's not going to change. Nor should it; if it did, we would become less effective at the things we do best. We're (largely) volunteers. We take time out of busy lives to answer questions, and at times we're overwhelmed with them. So we filter ruthlessly. In particular, we throw away questions from people who appear to be losers in order to spend our question-answering time more efficiently, on winners. If you find this attitude obnoxious, condescending, or arrogant, check your assumptions. We're not asking you to genuflect to us -- in fact, most of us would love nothing more than to deal with you as an equal and welcome you into our culture, if you put in the effort required to make that possible. But it's simply not efficient for us to try to help people who are not willing to help themselves. It's OK to be ignorant; it's not OK to play stupid. So, while it isn't necessary to already be technically competent to get attention from us, it is necessary to demonstrate the kind of attitude that leads to competence -- alert, thoughtful, observant, willing to be an active partner in developing a solution. If you can't live with this sort of discrimination, we suggest you pay somebody for a commercial support contract instead of asking hackers to personally donate help to you. If you decide to come to us for help, you don't want to be one of the losers. You don't want to seem like one, either. The best way to get a rapid and responsive answer is to ask it like a person with smarts, confidence, and clues who just happens to need help on one particular problem. In my world, a highly public essay that prominently says "most of us would love nothing more than to deal with you as an equal and welcome you into our culture" -- and explains the most effective way to do so -- would qualify as the exact polar opposite of "elitist". Elitism would be the _lack_ of such an essay. It would be, for example, a happy, positive-thinking, nurturing-feeling online environment where people nonetheless seldom effective help because nobody bothered to tell newcomers the truth about how to go about it. Eric and I tried to tell exactly that truth. We were blunt because bluntness _works_ in exactly the way that tiptoeing around important, key facts completely fails to work. (I submit that, if you're a busy technical expert and claim you don't filter ruthlessly and bypass poorly framed questions in favour of answerable and thoughtful ones, you are probably not being honest with yourself, as the trait is pretty nigh unto universal.) Sometimes, when you tell relevant truths, many people don't want to hear them, listen selectively if at all, and then call you names. Oh well. I note that Conrad's objection to Nicholas's suggestion of a FAQ pointer is that it would be a "barrier to asking questions". Huh? A suggestion in the welcome message that "if you're new to Haskell, please check this FAQ first" would tend to deter people from asking questions? How does that work? The suggestion's going to reach over and bruise their fingers? This does reveal one of the many hazards of writing documentation (in addition to http://linuxmafia.com/~rick/lexicon.html#moenslaw-documentation) Some people are hostile to the effort. Oh well. To quote the late Kurt Vonnegut, "So it goes." -- Cheers, If men are from Mars and women are from Venus, there's going Rick Moen to be one big-ass fight over where to set the thermostat. rick(a)linuxmafia.com -- Jim Rosenberg, in The Monastery

1 0

Indenting with PPrint
by Joel Reymont 08 May '07

08 May '07

Folks, Are you using UU.PPrint [1]? Can you tell me how to print stuff like this? { blah blah } I tried the following which sort of works but doesn't return the closing brace to the indentation level of the first one. braces x = PP.braces $ linebreak <> indent 4 x Thanks, Joel [1] http://tinyurl.com/25t6xz -- http://wagerlabs.com/

2 3

QuickCheck invariants for AST transformations
by Joel Reymont 08 May '07

08 May '07

I'm looking for suggestions on how to create invariants for the following AST transformation code. Any suggestions are appreciated! I asked this question before and Lennart suggested abstract interpretation as a solution. This would require interpreters for both ASTs to determine that the result they achieve is the same. I don't fancy writing a C# interpreter, though, so I'm looking for an easier way out. Thanks, Joel [1] http://tinyurl.com/368whq --- instance SharpTransform C.Type Type where toSharp C.TyInt = return TyInt toSharp C.TyFloat = return TyFloat toSharp C.TyStr = return TyStr toSharp C.TyBool = return TyBool toSharp (C.TyArray x) = liftM2 TyArray (toSharp x) (return []) toSharp (C.TySeries C.TyFloat) = return $ TyCustom "DataSeries" toSharp (C.TySeries x) = error $ "Unsupported series type: " ++ show x toSharp (C.TyProp x) = toSharp x toSharp C.TyUnit = return TyVoid instance SharpTransform C.VarIdent VarIdent where toSharp (C.VarIdent x) = return $ VarIdent x instance SharpTransform (Maybe C.Expr) (Maybe Expr) where toSharp Nothing = return Nothing toSharp (Just e) = liftM Just (toSharp e) instance SharpTransform C.Subscript [Expr] where toSharp xs = mapM toSharp xs instance SharpTransform C.BarsAgo Expr where toSharp C.Now = return $ Int 0 toSharp (C.BarsAgo e) = toSharp e -- http://wagerlabs.com/

2 1

Listing package dependencies from GHC
by Dougal Stanton 08 May '07

08 May '07

If I'm doing development between ghci and vim, all the different dependencies I need get linked in when required without me asking. Similarly if I call "ghc --make" from the command line. But I have to write them in manually to my *.cabal file otherwise the compilation process will fail. Until now I've just loaded the program in to ghci and noted down all the dependencies it links in. Am I missing a trick? There must be an easier way, especially for multiple source files. cheers, D.

4 7

Using dump in Netwotk.Pcap
by Harald ROTTER 08 May '07

08 May '07

Dear Haskellers, as a Haskell newbie I really enjoyed Austin Seipp's article on writing a packet sniffer in Haskell using the libpcap. I played around with Network.Pcap and tried to dump packets into a pcap file using the dump function: dump :: Ptr PcapDumpTag -> Ptr PktHdr -> Ptr Word8 -> IO () As compared to the loop function (used by Austin's packet sniffer) loop :: Ptr PcapTag -> Int -> Callback -> IO Int type Callback = PktHdr -> Ptr Word8 -> IO () the dump function takes a "Ptr PktHdr". If I want to "dump" inside a Callback, I have the problem of getting a "PktHdr" argument, but I need a "Ptr PktHdr" to dump. I tried to use "with": with :: Storable a => a -> (Ptr a -> IO b) -> IO b but PktHdr is unfortunately not an instance of the "Storable" class. How is it possible to use the "dump" function (that needs a Ptr PktHdr) inside a Callback that only passes PktHdr ? Any help is appreciated. Thank you Harald. " Ce courriel et les documents qui y sont attaches peuvent contenir des informations confidentielles. Si vous n'etes pas le destinataire escompte, merci d'en informer l'expediteur immediatement et de detruire ce courriel ainsi que tous les documents attaches de votre systeme informatique. Toute divulgation, distribution ou copie du present courriel et des documents attaches sans autorisation prealable de son emetteur est interdite." " This e-mail and any attached documents may contain confidential or proprietary information. If you are not the intended recipient, please advise the sender immediately and delete this e-mail and all attached documents from your computer system. Any unauthorised disclosure, distribution or copying hereof is prohibited."

1 0

How to parse a date and time?
by Justin Bailey 08 May '07

08 May '07

Looking at the libraries documentation, it seems like parsing a string into a time and date should be as simple as: import Data.Time.Format (parseTime) myDate = parseTime "..." where "..." is some string. But these functions don't seem to exist! I can't find many references to them in the wild, and the module "Data.Time.Format" is not found under GHC 6.6 or Hugs. I am running Windows, if it makes a difference. Are the docs just out of date[1] or is it my install? How can I parse a string into a Data.Time.Calendar.Day value (or some other time value)? Thanks for any help! Justin [1] http://haskell.org/ghc/docs/latest/html/libraries/time/Data-Time-Format.html

2 1