- Haskell-Cafe - Haskell.org

Unbound: rebind and unrebind
by Eric Dobson 23 Apr '13

23 Apr '13

I am working at reimplementing the library Unbound to understand how it works. One issue I have come up with is that an equation that I thought held true doesn't. The equation is: Forall e::Rebind a b, e `aeq` (uncurry rebind . unrebind $ e) => True. That is that spliting the binding of a rebind and then adding it back should be the identity. The issue is that Rebind does not freshen its pattern variables on unrebind, because it assumes that a higher level unbind already did that if required. But I believe this is not sufficient as there is not necesarily a higher level Bind to be ubound as shown by this program: {-# LANGUAGE TemplateHaskell, UndecidableInstances, FlexibleInstances, MultiParamTypeClasses #-} module Main where import Unbound.LocallyNameless data Exp = Var (Name Exp) deriving Show $(derive [''Exp]) instance Alpha Exp instance Subst Exp Exp where isvar (Var x) = Just (SubstName x) x :: Name Exp x = string2Name "x" y :: Name Exp y = string2Name "y" rebindPass :: Alpha a => Rebind Exp a -> Rebind Exp a rebindPass = (uncurry rebind . unrebind) main :: IO () main = do let rebound = (rebind (Var y) (Embed (Var x))) print $ rebound let substed = subst x (Var y) rebound print $ substed print $ unrebind substed print $ rebindPass substed Which outputs: <<Var y>> {Var x} <<Var y>> {Var y} (Var y,{Var y}) <<Var y>> {Var 0@0} If the equation holds true then the second and fourth lines should be identical but they are not. Can someone explain why this is the correct behavior or if the implementation is incorrect?

2 2

ANN: ipopt-hs 0.0.0.0
by adam vogt 23 Apr '13

23 Apr '13

I'm pleased to announce the first release of ipopt-hs. This package is a binding to a software package for large-scale nonlinear optimization <https://projects.coin-or.org/Ipopt>. You can get it from hackage: http://hackage.haskell.org/package/ipopt-hs Or if the documentation doesn't build (since hackage probably doesn't have ipopt), check: http://code.haskell.org/~aavogt/ipopt-hs/dist/doc/html/ipopt-hs/Ipopt.html One useful feature is that derivatives needed for the optimization can be calculated by automatic differentiation, thanks to <http://hackage.haskell.org/package/ad>. Some of the caveats with this release: - has only been tested with one problem, and only on linux, ghc-7.6.2 - derivatives are computed and stored without taking advantage of the fact that they may be sparse - advanced functions in coin/IpStdCInterface.h such as SetIntermediateCallback are not included Cheers, Adam Vogt

1 0

Dynamic collections of wires with netwire?
by Kata 23 Apr '13

23 Apr '13

I'm using netwire to make a top-down shooter; the player can spawn projectiles by clicking, and projectiles will destroy themselves and whatever they hit on collisions. So the way I'm thinking of this is as a collection of wires, one for each projectile, that I can cast input events to; however, I'm not sure how to deal with the fact that the set of wires is dynamically changing, since you can't do projectileWires <- accum (++) [] -< newProjectiles projectileState <- multicast projectileWires -< () or whatever. Do I have to write the relevant code out by hand using stepWire/stepWireP, or is there a nicer way?

1 0

Implementing an embedded language that threads a global structure.
by Ian Bloom 23 Apr '13

23 Apr '13

Hi, I've been working on this problem for some time and I was hoping for some feedback. I'm trying to implement an embedded language that can thread a global structure through the evaluation of a term. A mini version of this language only includes three functions, lam, app and ext (lambda, apply and extension respectively). The only difference between this and other embedded languages is that terms embedded in an extension have access to a global variable that is invisible to the terms themselves. The writer of a term in this language can only access the global variable by applying an extension. The writer extensions insures that the effect of evaluation on the global variable is commutative and insures that the effect of the global variable on terms is constant regardless of the order of evaluation. For example the global variable could be a map with some sort of lazy processing. An extension that queries the map for an element might cause a change in the state of the map and return some information about an element, but as long as the change in state are commutative and the same information is returned about elements regardless of the order of evaluation then the concept is safe. My motivation for experimenting with such a language comes from a belief that certain complicated programs would be easier to express in such a language and that there might be very useful code transformations that could eventually be applied to such a language that would be possible because of the constraints on the behavior of extensions. However I have yet to properly implement a language in Haskell and so I decided to post what I have and look for comments. Basically the language takes a common form of embedded languages; a lambda expression such as \x y->x y would have the form: lam (\x -> lam (\y -> app x y)) however in order to evaluate an expression the need to also apply it to a global term: lam (\x -> lam (\y -> app x y)) global Ideally the result of evaluating this would be a (global', \x y-> x y), a modified version of global paired with the term. So the type of the term: lam (\x -> lam (\y -> app x y)) is something like g -> (g, (a -> b) -> a -> b) where g is the type of global. >From that came the first idea of the types of the evaluator functions: lam :: ( (g->(g,a)) -> (g->(g,b)) )-> (g->(g, a->b)) app :: (g->(g,a->b)) -> (g->(g, a)) -> (g->(g,b)) with some additional parenthesis for sake of clarity. Each sub-term has the type g->(g,t) any function can be included as an extension as long as the function has the type: (g->(g,a)) -> (g->(g,b)) This seems to work well except that it seems to be impossible (as far as I've tried) to construct a definition for the lam function that both fits this type and properly passes the global through the entire evaluation. For example it's easy to define app like this: app :: (g->(g,a->b)) -> (g->(g,a)) -> (g->(g,b)) app = (\ eA eB -> \ g0 -> let (gB, fB) = eB g0 in let (gA, fA) = eA gB in (gA, fA fB) ) but so far the definition of lam has eluded me. This is the closest I've come: lam :: ((g->(g,a)) -> (g->(g,b))) -> (g->(g,a->b)) lam = (\ f -> \ g0 -> (g0, \x -> snd $ (f (\ gv->(gv,x))) g0 )) This fits the type but I fear this definition does not return the properly modified version of global. I tried some other iterations of this idea. In one effort the first argument of a function is extracted into the type of a term. So a term of type a->b has the type (g->a->(g,b)). And a term of type a has the type (g->((g, a)) such that: lam2 :: ((g->(g,a)) -> (g->(g,b))) -> (g->a->(g,b)) lam2 = (\ f -> \ g x -> (f (\ gv -> (gv, x))) g) app2 :: (g->a->(g,b)) -> (g->(g,a)) -> (g->(g,b)) app2 = (\ eA eB -> \ g0 -> let (gB, fB) = eB g0 in eA gB fB ) This seems like a step in the right direction unfortunately because the return type of lam is now (g->a->(g,b)) and not (g->(g->c)) we cannot type the term lam (\x -> lam (\y -> app x y)). In other words this language can only express unary and nullary functions. Just to help clarify this for myself I created to addition functions lam2Helper and app2Helper: lam2Helper :: (g->a->(g,b)) -> (g->(g,a->b)) lam2Helper = (\f -> \g -> (g, \a -> snd $ f g a)) app2Helper :: (g->(g,a->b)) -> (g->a->(g,b)) app2Helper = (\f -> \g a-> let (g1, f1) = f g in (g1, f1 a)) these allow me to create the term: lam2 (\x -> lam2Helper $ lam2 (\y -> app2 (app2Helper x) y)) but just like the original definition of lam from my first try, there is no way to construct lam2Helper without improperly passing the global as I've done in my attempt. Finally on my third try I attempted to make every term have type (g->a->(g,b) by allowing embedded nullary functions to have the type (g->()->(g,t)) lam3 :: ((g->()->(g,a)) -> (g->()->(g,b))) -> (g->a->(g,b)) lam3 = (\ f -> \ g x -> (f (\ gv () -> (gv, x))) g () ) app3 :: (g->a->(g,b)) -> (g->()->(g,a)) -> (g->()->(g,b)) app3 = (\ eA eB -> \ gz () -> let (gB, fB) = eB gz () in eA gB fB ) This allows me to construct the term: lam (\x -> lam (\y -> app x y)) but only by throwing out important type information... A compilable example of this is available here: http://hpaste.org/86273 And with source candy here: http://hpaste.org/86274 My goal at this point is just to understand the problem better. I feel I'm at the edge of my understanding of type systems and arity and I'm unsure if what I want to do is possible in Haskell. My goal would eventually be to construct a working prototype of such a language and to construct a proof that it maintains the types of terms and that the global variable is evaluated once by every subterm. I appreciate any insight, interest or help. Thanks, Ian Bloom ianmbloom(a)gmail.com

2 1

17th BRAZILIAN SYMPOSIUM ON PROGRAMMING LANGUAGES
by Simon Thompson 22 Apr '13

22 Apr '13

[Apologies if you receive multiple copies of this CFP] ======================================================= CALL FOR PAPERS 17th BRAZILIAN SYMPOSIUM ON PROGRAMMING LANGUAGES Brasília, Distrito Federal, Brazil September 29th to October 4th, 2013 http://cbsoft2013.unb.br/en/sblp-en ======================================================== IMPORTANT DATES Paper abstract submission (15 lines): May 6th, 2013 (extended deadline) Full paper submission: May 10th, 2013 (extended deadline) Notification of acceptance: June 7, 2013 Final papers due: June 28th, 2013 INVITED SPEAKERS * Tim Harris, Oracle Labs * More TBA INTRODUCTION The 17th Brazilian Symposium on Programming Languages, SBLP 2013, will be held in Brasília, Brazil, on September 29th to October 4th, 2013. SBLP provides a venue for researchers and practitioners interested in the fundamental principles and innovations in the design and implementation of programming languages and systems. The symposium will be part of the 4th Brazilian Conference on Software: Theory and Practice, CBSoft 2013,http://cbsoft2013.cic.unb.br/, which will host four traditional, well-established symposia: * XXVII Brazilian Symposium on Software Engineering (SBES) * XVII Brazilian Symposium on Programming Languages (SBLP) * XVI Brazilian Symposium on Formal Methods (SBMF) * VII Brazilian Symposium on Components, Software Architecture and Software Reuse (SBCARS) SBLP 2013 invites authors to contribute with technical papers related (but not limited) to: * Program generation and transformation, including domain-specific languages and model-driven development in the context of programming languages. * Programming paradigms and styles, including functional, object-oriented, aspect-oriented, scripting languages, real-time, service-oriented, multithreaded, parallel, and distributed programming. * Formal semantics and theoretical foundations, including denotational, operational, algebraic and categorical. * Program analysis and verification, including type systems, static analysis and abstract interpretation. * Programming language design and implementation, including new programming models, programming language environments, compilation and interpretation techniques. SUBMISSIONS Contributions should be written in Portuguese or English. We solicit papers that should fall into one of two different categories: full papers, with at most 15 pages, or short papers, with at most 5 pages. Full papers submitted in English will be published in a volume of Lecture Notes in Computer Science (LNCS), by Springer. For this reason, all papers must be prepared using the LNCS template, available at http://www.springer.com/computer/lncs?SGWID=0-164-6-793341-0. We encourage the submission of short papers reporting on partial results of on-going master dissertations or doctoral theses. All accepted papers will be published in the conference proceedings distributed in a digital media by the CBSOFT organizers. Submissions should be done using SBLP 2013 installation of the EasyChair conference mangement system athttp://www.easychair.org/conferences/?conf=sblp2013. As in previous editions, a journal special issue, with selected papers from accepted contributions, is anticipated. Selected papers from 2003 to 2008 editions of SBLP were published in special issues of the Journal of Universal Computer Science, by Springer. The post-proceedings of SBLP from 2009 to 2012, also with selected papers from the conference proceedings, are being edited as special issues of Science of Computer Programming, published by Elsevier. CBSOFT CHAIRS Genaina Nunes Rodrigues, UnB Rodrigo Bonifácio, UnB Diego Aranha, UnB PROGRAMME CHAIRS André Rauber Du Bois, UFPel Phil Trinder, Glasgow University PROGRAMME COMMITTEE Alberto Pardo, Univ. de La Republica Alex Garcia, IME Alvaro Freitas Moreira, UFRGS André Rauber Du Bois, UFPel (co-chair) Andre Santos, UFPE Carlos Camarao, UFMG Christiano Braga, UFF Edwin Brady, University of St. Andrews Fernando Castor Filho, UFPE Fernando Quintão Pereira, UFMG Francisco Heron de Carvalho Junior, UFC Hans-Wofgang Loidl, Heriot-Watt University Jeremy Singer, Glasgow University Joao Saraiva, Universidade do Minho João F. Ferreira, Teesside University Lucilia Figueiredo, UFOP Luis Soares Barbosa, Univ. do Minho Manuel António Martins, Univ. de Aveiro Marcelo A. Maia, UFU Marcello Bonsangue, Leiden Univ/CWI Marcelo d'Amorim, UFPE Marco Tulio Valente, UFMG Mariza A. S. Bigonha, UFMG Martin A. Musicante, UFRN Noemi Rodriguez, PUC-Rio Peter Mosses, Swansea University Phil Trinder, Glasgow University (co-chair) Qiu Zongyang, Beijing University Rafael Dueire Lins, UFPE Renato Cerqueira, PUC-Rio Ricardo Massa, UFPE Roberto S. Bigonha, UFMG Roberto Ierusalimschy, PUC-Rio Sandro Rigo, UNICAMP Sergio Soares, UFPE Simon Thompson, Univ. of Kent Varmo Vene, Univ. de Tartu Simon Thompson | Professor of Logic and Computation School of Computing | University of Kent | Canterbury, CT2 7NF, UK s.j.thompson(a)kent.ac.uk | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt

1 0

CFP SBLP 2013: Deadline extension
by Andre Rauber Du Bois 22 Apr '13

22 Apr '13

[Apologies if you receive multiple copies of this CFP] ======================================================= CALL FOR PAPERS 17th BRAZILIAN SYMPOSIUM ON PROGRAMMING LANGUAGES Brasília, Distrito Federal, Brazil September 29th to October 4th, 2013 http://cbsoft2013.unb.br/en/sblp-en ======================================================== IMPORTANT DATES Paper abstract submission (15 lines): May 6th, 2013 (extended deadline) Full paper submission: May 10th, 2013 (extended deadline) Notification of acceptance: June 7, 2013 Final papers due: June 28th, 2013 INVITED SPEAKERS * Tim Harris, Oracle Labs * More TBA INTRODUCTION The 17th Brazilian Symposium on Programming Languages, SBLP 2013, will be held in Brasília, Brazil, on September 29th to October 4th, 2013. SBLP provides a venue for researchers and practitioners interested in the fundamental principles and innovations in the design and implementation of programming languages and systems. The symposium will be part of the 4th Brazilian Conference on Software: Theory and Practice, CBSoft 2013, http://cbsoft2013.cic.unb.br/, which will host four traditional, well-established symposia: * XXVII Brazilian Symposium on Software Engineering (SBES) * XVII Brazilian Symposium on Programming Languages (SBLP) * XVI Brazilian Symposium on Formal Methods (SBMF) * VII Brazilian Symposium on Components, Software Architecture and Software Reuse (SBCARS) SBLP 2013 invites authors to contribute with technical papers related (but not limited) to: * Program generation and transformation, including domain-specific languages and model-driven development in the context of programming languages. * Programming paradigms and styles, including functional, object-oriented, aspect-oriented, scripting languages, real-time, service-oriented, multithreaded, parallel, and distributed programming. * Formal semantics and theoretical foundations, including denotational, operational, algebraic and categorical. * Program analysis and verification, including type systems, static analysis and abstract interpretation. * Programming language design and implementation, including new programming models, programming language environments, compilation and interpretation techniques. SUBMISSIONS Contributions should be written in Portuguese or English. We solicit papers that should fall into one of two different categories: full papers, with at most 15 pages, or short papers, with at most 5 pages. Full papers submitted in English will be published in a volume of Lecture Notes in Computer Science (LNCS), by Springer. For this reason, all papers must be prepared using the LNCS template, available at http://www.springer.com/computer/lncs?SGWID=0-164-6-793341-0. We encourage the submission of short papers reporting on partial results of on-going master dissertations or doctoral theses. All accepted papers will be published in the conference proceedings distributed in a digital media by the CBSOFT organizers. Submissions should be done using SBLP 2013 installation of the EasyChair conference mangement system at http://www.easychair.org/conferences/?conf=sblp2013. As in previous editions, a journal special issue, with selected papers from accepted contributions, is anticipated. Selected papers from 2003 to 2008 editions of SBLP were published in special issues of the Journal of Universal Computer Science, by Springer. The post-proceedings of SBLP from 2009 to 2012, also with selected papers from the conference proceedings, are being edited as special issues of Science of Computer Programming, published by Elsevier. CBSOFT CHAIRS Genaina Nunes Rodrigues, UnB Rodrigo Bonifácio, UnB Diego Aranha, UnB PROGRAMME CHAIRS André Rauber Du Bois, UFPel Phil Trinder, Glasgow University PROGRAMME COMMITTEE Alberto Pardo, Univ. de La Republica Alex Garcia, IME Alvaro Freitas Moreira, UFRGS André Rauber Du Bois, UFPel (co-chair) Andre Santos, UFPE Carlos Camarao, UFMG Christiano Braga, UFF Edwin Brady, University of St. Andrews Fernando Castor Filho, UFPE Fernando Quintão Pereira, UFMG Francisco Heron de Carvalho Junior, UFC Hans-Wofgang Loidl, Heriot-Watt University Jeremy Singer, Glasgow University Joao Saraiva, Universidade do Minho João F. Ferreira, Teesside University Lucilia Figueiredo, UFOP Luis Soares Barbosa, Univ. do Minho Manuel António Martins, Univ. de Aveiro Marcelo A. Maia, UFU Marcello Bonsangue, Leiden Univ/CWI Marcelo d'Amorim, UFPE Marco Tulio Valente, UFMG Mariza A. S. Bigonha, UFMG Martin A. Musicante, UFRN Noemi Rodriguez, PUC-Rio Peter Mosses, Swansea University Phil Trinder, Glasgow University (co-chair) Qiu Zongyang, Beijing University Rafael Dueire Lins, UFPE Renato Cerqueira, PUC-Rio Ricardo Massa, UFPE Roberto S. Bigonha, UFMG Roberto Ierusalimschy, PUC-Rio Sandro Rigo, UNICAMP Sergio Soares, UFPE Simon Thompson, Univ. of Kent Varmo Vene, Univ. de Tartu

1 0

conditional branching vs pattern matching: pwn3d by GHC
by Albert Y. C. Lai 22 Apr '13

22 Apr '13

When I was writing http://www.vex.net/~trebla/haskell/crossroad.xhtml I wanted to write: branching on predicates and then using selectors is less efficient than pattern matching, since selectors repeat the tests already done by predicates. It is only ethical to verify this claim before writing it. So here it goes, eval uses pattern matching, fval uses predicates and selectors: module E where data E = Val{fromVal::Integer} | Neg{fromNeg::E} | Add{fromAdd0, fromAdd1 :: E} isVal Val{} = True isVal _ = False isNeg Neg{} = True isNeg _ = False isAdd Add{} = True isAdd _ = False eval (Val n) = n eval (Neg e0) = - eval e0 eval (Add e0 e1) = eval e0 + eval e1 fval e | isVal e = fromVal e | isNeg e = - fval (fromNeg e) | isAdd e = fval (fromAdd0 e) + fval (fromAdd1 e) Simple and clear. What could possibly go wrong! $ ghc -O -c -ddump-simpl -dsuppress-all -dsuppress-uniques E.hs ... Rec { fval fval = \ e -> case e of _ { Val ds -> ds; Neg ds -> negateInteger (fval ds); Add ipv ipv1 -> plusInteger (fval ipv) (fval ipv1) } end Rec } Rec { eval eval = \ ds -> case ds of _ { Val n -> n; Neg e0 -> negateInteger (eval e0); Add e0 e1 -> plusInteger (eval e0) (eval e1) } end Rec } Which of the following best describes my feeling? [ ] wait, what? [ ] lol [ ] speechless [ ] oh man [ ] I am so pwn3d [ ] I can't believe it [ ] what can GHC not do?! [ ] but what am I going to say in my article?! [ ] why is GHC making my life hard?! [X] all of the above

2 1

Fwd: GSoC Project Proposal: Markdown support for Haddock
by Joe Nash 21 Apr '13

21 Apr '13

I would be interested in discussing this project with a potential mentor if one happens to be reading. I'm a second year Computer Science student at the University of Nottingham, very interested in doing a haskell.org SoC project. On Tue, Apr 9, 2013 at 8:17 PM, David Waern <david.waern(a)gmail.com> wrote: > > > > 2013/4/8 Evan Laforge <qdunkan(a)gmail.com> > >> Can't we just add some features to haddock? There are a lot of ways >> to improve haddock a lot, and no one is doing them, so my impression >> is that haddock doesn't really have active maintainers. Adding a >> whole new backend seems risky, unless it results in new maintainers >> joining. >> > > As one of the official maintainers (the other one is Simon Hengel), I > agree that Haddock can barely be called actively maintained and it has been > like that for a long time now. It's sad, but we lack of time, which is the > usual excuse of course. A more resourceful maintainer would be great, so if > someone reading this is motivated and wants to help out, we'd love to be > contacted by you. > > I don't think a SoC project for Markdown support would be risky at all > (with a sufficiently good student), however. And it wouldn't require a new > backend, the backend would still be the existing HTML backend in Haddock. > > David > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

3 2

Frankfurt Haskell User Group - Meetup on Yesod, 24.4.13
by Peter Althainz 20 Apr '13

20 Apr '13

The Frankfurt Haskell User Group meets on 24.4.13 for a presentation on Yesod. http://www.meetup.com/Frankfurt-Haskell-User-Group/. Regards: Peter

1 0

unsafeInterleaveST (and IO) is really unsafe
by oleg＠okmij.org 19 Apr '13

19 Apr '13

Timon Gehr wrote: > I am not sure that the two statements are equivalent. Above you say that > the context distinguishes x == y from y == x and below you say that it > distinguishes them in one possible run. I guess this is a terminological problem. The phrase `context distinguishes e1 and e2' is the standard phrase in theory of contextual equivalence. Here are the nice slides http://www.cl.cam.ac.uk/teaching/0910/L16/semhl-15-ann.pdf Please see adequacy on slide 17. An expression relation between two boolean expressions M1 and M2 is adequate if for all program runs (for all initial states of the program s), M1 evaluates to true just in case M2 does. If in some circumstances M1 evaluates to true but M2 (with the same initial state) evaluates to false, the expressions are not related or the expression relation is inadequate. See also the classic http://www.ccs.neu.edu/racket/pubs/scp91-felleisen.ps.gz (p11 for definition and Theorem 3.8 for an example of a distinguishing, or witnessing context). > In essence, lazy IO provides unsafe constructs that are not named > accordingly. (But IO is problematic in any case, partly because it > depends on an ideal program being run on a real machine which is based > on a less general model of computation.) I'd agree with the first sentence. As for the second sentence, all real programs are real programs executing on real machines. We may equationally prove (at time Integer) that 1 + 2^100000 == 2^100000 + 1 but we may have trouble verifying it in Haskell (or any other language). That does not mean equational reasoning is useless: we just have to precisely specify the abstraction boundaries. BTW, the equality above is still useful even in Haskell: it says that if the program managed to compute 1 + 2^100000 and it also managed to compute 2^100000 + 1, the results must be the same. (Of course in the above example, the program will probably crash in both cases). What is not adequate is when equational theory predicts one finite result, and the program gives another finite result -- even if the conditions of abstractions are satisfied (e.g., there is no IO, the expression in question has a pure type, etc). > I think this context cannot be used to reliably distinguish x == y and y > == x. Rather, the outcomes would be arbitrary/implementation > defined/undefined in both cases. My example uses the ST monad for a reason: there is a formal semantics of ST (denotational in Launchbury and Peyton-Jones and operational in Moggi and Sabry). Please look up ``State in Haskell'' by Launchbury and Peyton-Jones. The semantics is explained in Sec 6. Please see Sec 10.2 Unique supply trees -- you might see some familiar code. Although my example was derived independently, it has the same kernel of badness as the example in Launchbury and Peyton-Jones. The authors point out a subtlety in the code, admitting that they fell into the trap themselves. So, unsafeInterleaveST is really bad -- and the people who introduced it know that, all too well.

5 5