- Haskell-Cafe - Haskell.org

ANN: unification-fd 0.8.0
by wren ng thornton 11 Jul '12

11 Jul '12

-------------------------------------------- -- unification-fd 0.8.0 -------------------------------------------- The unification-fd package offers generic functions for single-sorted first-order structural unification (think of programming in Prolog, or of the metavariables in type inference)[1][2]. The library *is* sufficient for implementing higher-rank type systems a la [Peyton Jones, Vytiniotis, Weirich, Shields], but bear in mind that unification variables are the metavariables of type inference--- not the type-variables. As of this version, the library is also sufficient for implementing (non-recursive) feature structure unification. An effort has been made to make the package as portable as possible. However, because it uses the ST monad and the mtl-2 package it can't be H98 nor H2010. However, it only uses the following common extensions which should be well supported[3]: Rank2Types MultiParamTypeClasses FunctionalDependencies -- Alas, necessary for type inference FlexibleContexts -- Necessary for practical use of MPTCs FlexibleInstances -- Necessary for practical use of MPTCs UndecidableInstances -- For Show instances due to two-level types -------------------------------------------- -- Changes (since 0.7.0) -------------------------------------------- This release is another API breaking release, though hopefully minor. In particular, the type of the zipMatch method for Unifiable has changed from: zipMatch :: t a -> t b -> Maybe (t (a, b)) to: zipMatch :: t a -> t a -> Maybe (t (Either a (a, a))) With the new type each of the unification subproblems can be declared as fully resolved (Left xy) or as still pending solution (Right (x,y))--- whereas the previous type only allowed the latter. This extension is necessary for implementing unification of feature structures (e.g., t ~ Map k). Given two feature structures which do not fully overlap, we can now declare that the non-intersecting parts have been unified and only require further unification for the parts which intersect--- whereas previously we would've been forced to declare the non-intersecting parts as requiring unification with themselves, which will always succeed and introduces extra work. This feature is one I had available in earlier unpublished versions of the code, but errantly removed it when simplifying things for publishing on Hackage. To fix extant Unifiable instances, just wrap each tuple with Right. For those who care about such things, I have not been able to discern any noticeable difference in performance between the two versions. If you can provide benchmarks demonstrating otherwise, I'd be pleased to look at them. In addition, the Show instance for Fix has been adjusted to use showsPrec in lieu of show, correcting some infelicities with the output. -------------------------------------------- -- Description -------------------------------------------- The unification API is generic in the type of the structures being unified and in the implementation of unification variables, following the two-level types pearl of Sheard (2001). This style mixes well with Swierstra (2008), though an implementation of the latter is not included in this package. That is, all you have to do is define the functor whose fixed-point is the recursive type you're interested in: -- The non-recursive structure of terms data S a = ... -- The recursive term type type Term = Fix S And then provide an instance for Unifiable, where zipMatch performs one level of equality testing for terms and returns the one-level spine filled with pairs of subterms to be recursively checked, or Nothing if this level doesn't match. Each subterm can be separately marked as being resolved, Left xy, or as requiring further unification, Right(x,y). class (Traversable t) => Unifiable t where zipMatch :: t a -> t a -> Maybe (t (Either a (a, a))) The choice of which variable implementation to use is defined by similarly simple classes Variable and BindingMonad. We store the variable bindings in a monad, for obvious reasons. In case it's not obvious, see Dijkstra et al. (2008) for benchmarks demonstrating the cost of naively applying bindings eagerly. There are currently two implementations of variables provided: one based on STRefs, and another based on a state monad carrying an IntMap. The former has the benefit of O(1) access time, but the latter is plenty fast and has the benefit of supporting backtracking. Backtracking itself is provided by the logict package and is described in Kiselyov et al. (2005). In addition to this modularity, unification-fd implements a number of optimizations over the algorithm presented in Sheard (2001)--- which is also the algorithm presented in Cardelli (1987). * Their implementation uses path compression, which we retain. Though we modify the compression algorithm in order to make sharing observable. * In addition, we perform aggressive opportunistic observable sharing, a potentially novel method of introducing even more sharing than is provided by the monadic bindings. Basically, we make it so that we can use the observable sharing provided by the modified path compression as much as possible (without introducing any new variables). * And we remove the notoriously expensive occurs-check, replacing it with visited-sets (which detect cyclic terms more lazily and without the asymptotic overhead of the occurs-check). A variant of unification which retains the occurs-check is also provided, in case you really need to fail fast. * Finally, a highly experimental branch of the API performs *weighted* path compression, which is asymptotically optimal. Unfortunately, the current implementation is quite a bit uglier than the unweighted version, and I haven't had a chance to perform benchmarks to see how the constant factors compare. Hence moving it to an experimental branch. These optimizations pass a test suite for detecting obvious errors. If you find any bugs, do be sure to let me know. Also, if you happen to have a test suite or benchmark suite for unification on hand, I'd love to get a copy. -------------------------------------------- -- Notes and limitations -------------------------------------------- [1] At present the library does not appear amenable for implementing higher-rank unification itself; i.e., for higher-ranked metavariables, or higher-ranked logic programming. To be fully general we'd have to abstract over which structural positions are co/contravariant, whether the unification variables should be predicative or impredicative, as well as the isomorphisms of moving quantifiers around. It's on my todo list, but it's certainly non-trivial. If you have any suggestions, feel free to contact me. [2] At present it is only suitable for single-sorted (aka untyped) unification, a la Prolog. In the future I aim to support multi-sorted (aka typed) unification, however doing so is complicated by the fact that it can lead to the loss of MGUs; so it will likely be offered as an alternative to the single-sorted variant, similar to how the weighted path-compression is currently offered as an alternative. [3] With the exception of fundeps which are notoriously difficult to implement. However, they are supported by Hugs and GHC 6.6, so I don't feel bad about requiring them. Once the API stabilizes a bit more I plan to release a unification-tf package which uses type families instead, for those who feel type families are easier to implement or use. There have been a couple requests for unification-tf, so I've bumped it up on my todo list. -------------------------------------------- -- References -------------------------------------------- Luca Cardelli (1987) /Basic polymorphic typechecking/. Science of Computer Programming, 8(2):147--172. Atze Dijkstra, Arie Middelkoop, S. Doaitse Swierstra (2008) /Efficient Functional Unification and Substitution/, Technical Report UU-CS-2008-027, Utrecht University. <http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-027.pdf> Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, Mark Shields /Practical type inference for arbitrary-rank types/, to appear in the Journal of Functional Programming. (Draft of 31 July 2007.) Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry (2005) /Backtracking, Interleaving, and/ /Terminating Monad Transformers/, ICFP. <http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf> Tim Sheard (2001) /Generic Unification via Two-Level Types/ /and Paramterized Modules/, Functional Pearl, ICFP. <http://web.cecs.pdx.edu/~sheard/papers/generic.ps> Tim Sheard & Emir Pasalic (2004) /Two-Level Types and/ /Parameterized Modules/. JFP 14(5): 547--587. This is an expanded version of Sheard (2001) with new examples. <http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps> Wouter Swierstra (2008) /Data types a la carte/, Functional Pearl. JFP 18: 423--436. <http://www.cs.ru.nl/~wouters/Publications/DataTypesALaCarte.pdf> -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/unification-fd Darcs: http://community.haskell.org/~wren/unification-fd Haddock (Darcs version): http://community.haskell.org/~wren/unification-fd/dist/doc/html/unification… -- Live well, ~wren

1 0

Any good tool to write Haskell documents including tests?
by Takayuki Muranushi 10 Jul '12

10 Jul '12

Hello, I have been a forgetful person, and lots of things I have only pretended to understand. I want to change this. So, to educate myself, I'd like to write documented tests for many libraries I meet, and also publish them onto the web so that others may find them useful or find mistakes for me. OK, blog articles are good, but they have no (forced) tests. Maybe some of you have practiced this or developping such tools. I see some candidate tools, too. What is your suggestion for this? I have tried doctest, because of its read–eval–print loop (REPL) style I liked. https://github.com/nushio3/practice/tree/master/control-monad-loop It produces html as attached to this mail. It's pretty, but I'd like to have more control on HTML. Maybe Gitit + Doctest in Pandoc is a good alternative? I'd also like to know what is a good way to publish a small executable examples with automated dependency install capability. Can you point out any problems with following Makefile + cabal ? What are better ways to do this? https://github.com/nushio3/practice/blob/master/control-monad-loop/Loop.cab… https://github.com/nushio3/practice/blob/master/control-monad-loop/Makefile Thanks in advance, -- Takayuki MURANUSHI The Hakubi Center for Advanced Research, Kyoto University http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

3 3

Memory corruption issues when using newAlignedPinnedByteArray, GC kicking in?
by Nicolas Trangez 10 Jul '12

10 Jul '12

All, While working on my vector-simd library, I noticed somehow memory I'm using gets corrupted/overwritten. I reworked this into a test case, and would love to get some help on how to fix this. Previously I used some custom FFI calls to C to allocate aligned memory, which yields correct results, but this has a significant (+- 10x) performance impact on my benchmarks. Later on I discovered the newAlignedPinnedByteArray# function, and wrote some code using this. Here's what I did in the test case: I created an MVector instance, with the exact same implementation as vector's Data.Vector.Storable.Mutable.MVector instance, except for basicUnsafeNew where I pass one more argument to mallocVector [1]. I also use 3 different versions of mallocVector (depending on compile-time flags): mallocVectorOrig [2]: This is the upstream version, discarding the integer argument I added. Then here's my first attempt, very similar to the implementation of mallocPlainForeignPtrBytes [3] at [4] using GHC.* libraries. Finally there's something similar at [5] which uses the 'primitive' library. The test case creates vectors of increasing size, then checks whether they contain the expected values. For the default implementation this works correctly. For both others it fails at some random size, and the values stored in the vector are not exactly what they should be. I don't understand what's going on here. I suspect I lack a reference (or something along those lines) so GC kicks in, or maybe the buffer gets relocated, whilst it shouldn't. Basically I'd need something like GHC.ForeignPtr.mallocPlainAlignedForeignPtrBytes :: Int -> Int -> IO (ForeignPtr a) Thanks, Nicolas [1] https://gist.github.com/3084806#LC37 [2] https://gist.github.com/3084806#LC119 [3] http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-Fo… [4] https://gist.github.com/3084806#LC100 [5] https://gist.github.com/3084806#LC81

2 1

hiring haskell programmer.
by Vagif Verdi 10 Jul '12

10 Jul '12

Hello. My company is looking to hire a haskell developer. South California (San Dimas), full time job, local only (no telecommute) We use yesod (haskell web framework) for internal web application and web services, and compojure (clojure web framework) for customer facing web site. All development will be ether with haskell (if libraries permit) or clojure on JVM. If interested please contact me. Regards, Vagif Verdi

1 0

Connecting Travis CI and hackage
by Dmitry Malikov 10 Jul '12

10 Jul '12

*tldr*: is there a way to upload package to hackage from Travis automatically and safely (hiding password to hackage account)? Several days ago I discovered Travis ( http://travis-ci.org/ ) - nice open source build-service, easy to start and monitoring. I've configured some github projects and add build status to it's readme. It's usable to know how is your haskell package building on separate fresh machine. Following git-flow developing model there is a develop branch for snapshots and master branch for release. That why every commit in master branch should produce new release build ⇒ every commit in master branch should produce new hackage build upload. And also it will be nice to have that routine process done automatically. It could be done using cabal-upload tool and --username and --password options. But it means that .travis.yml file should contain my hackage-password explicitly. How can I avoid that? -- Best regards, dmitry malikov !

3 3

Combining Network Descriptions in Reactive.Banana
by Alexander Foremny 10 Jul '12

10 Jul '12

Hello list, I am currently experimenting with Reactive.Banana and I am trying to write a program that simply displays a String which is supplied by the user. Thus in Main.hs I'd like to create a Behavior t String from some arbitrary sources and pass this to a library function performing the printing. However, I am not able to get the desired behavior of my program. A sample Main.hs is available as Gist [1]. The cause of error appears to be that the type t over which NetworkDescription and Behavior are parameterized are distinct! I tried several variations of the code in [1] using ExistentialQuantification over t and/or giving explicit type signatures. The error is slightly different in each case, but always boils down to the same reason. In case explicit error messages are required I can post them to the list. Any insight into this would be of great help. And additionally I'd be interested if this kind of program is possible with Reactive.Banana at all. [1] https://gist.github.com/3004430

4 4

Linking against Sqlite3 on Windows problem
by Eugene Dzhurinsky 10 Jul '12

10 Jul '12

Hi all! I created simple application, which uses sqlite3 as it's datastore back-end. I faced no problems when building and running it on Linux, but after I tried to build it on Windows, I see weird linking error: Linking dist\build\hnotes\hnotes.exe ... C:\Documents and Settings\Admin\Application Data\cabal\sqlite-0.5.2.2\ghc-7.0.4/libHSsqlite-0.5.2.2. a(sqlite3-local.o):sqlite3-local.c:(.text+0x21): undefined reference to `sqlite3_temp_directory' C:\Documents and Settings\Admin\Application Data\cabal\sqlite-0.5.2.2\ghc-7.0.4/libHSsqlite-0.5.2.2. a(sqlite3-local.o):sqlite3-local.c:(.text+0x40): undefined reference to `sqlite3_temp_directory' collect2: v ld 1 cabal.EXE: Error: some packages failed to install: hnotes-0.1 failed during the building phase. The exception was: ExitFailure 1 What may be wrong there? I suspect that qalite3.dll has to be added to linking stage, but have no idea how to do that. Adding --extra-lib-dirs=path-to-sqlite-dll doesn't help either (perhaps because I need to update my cabal file somehow, to support this?). Thank you for the help! -- Eugene N Dzhurinsky

2 1

ANNOUNCE: control-monad-loop 0.1
by Joey Adams 09 Jul '12

09 Jul '12

This package provides imperative-style loops supporting "continue" and "break". For example: import Control.Monad import Control.Monad.IO.Class import Control.Monad.Trans.Loop import Control.Monad.Trans.Class main :: IO () main = foreach [0..] $ \i -> foreach [0..] $ \j -> do when (j == 0) $ continue -- skip to next iteration when (j >= 5) $ exit -- exit the loop when (i >= 5) $ lift exit -- exit the outer loop by calling 'exit' in the parent monad liftIO $ print (i, j) It works by having the loop body run under the LoopT monad transformer, which provides early exit functions 'continue' and 'exit'. Functions like 'foreach' and 'while' run a LoopT callback, passing it continuations defining 'continue' and 'exit'. http://hackage.haskell.org/package/control-monad-loop

2 3

ANNOUNCE: Sifflet visual programming language, release 2.0.0.0
by gdweber＠iue.edu 09 Jul '12

09 Jul '12

I don't usually get this excited about a release, but after nearly a year of not being able to do any work on Sifflet, I am now *Extremely Happy* to announce -- Sifflet and sifflet-lib 2.0.0.0, now available on Hackage! This version introduces a type checker and partial support for higher order functions in Sifflet, the visual, functional programming language and support system for students learning about recursion. Sifflet programmers define functions by drawing diagrams, and the Sifflet interpreter uses the diagrams to show how function calls are evaluated. Sifflet-lib is the library containing many modules of the Sifflet application. What's New ---------- July 5, 2012, Version 2.0.0.0: * Partial support for higher order functions, like map and filter. See Lesson 10 in the Sifflet Tutorial. * Sifflet now provides type checking and type inference. This should make it possible to provide exporters to languages, like Java, that require type declarations. (Unfortunately, the error messages for incorrectly typed functions are not yet friendly for novice programmers.) * Added a menu command (File / Save image ...) to save vector graphic images of functions in the Sifflet Workspace or Edit function windows. Images can be saved in SVG, Postscript, and PDF formats. * Reorganized hierarchical modules in the library to conform to the recommended practice. See the RELEASE-NOTES for details. * Several bugs are fixed, including one which crashed Sifflet when applying a function definition with an incomplete `if` tree. See ISSUES for details. * There is a new file format for saving function definitions to support higher-order function types. The new format, siffml 2.0, has a RELAX NG schema; siffml 1.0 files can still be opened in Sifflet 2.0. About Sifflet ------------- Sifflet is a visual, functional programming language intended as an aid for learning about recursion. * A picture explains Sifflet better than words: please see the screenshot showing how to evaluate 3!: http://mypage.iu.edu/~gdweber/software/sifflet/home.html * Features: - Visual editor. - Visual tracer/debugger which shows how recursive and other function calls are evaluated. To support active learning and avoid screen clutter, Sifflet displays only as much of the computation as the user requests. - Carefully crafted tutorial with 44 pictures, about 26 pages if printed. - Number, string, and list data types. - Small collection of primitive functions. - Runnable examples of compound functions. - Sifflet functions can be exported to Scheme, Python 3, and Haskell. References ---------- * Download: http://hackage.haskell.org/package/sifflet-lib http://hackage.haskell.org/package/sifflet * Home page: http://mypage.iu.edu/~gdweber/software/sifflet/home.html * Sifflet Tutorial: http://mypage.iu.edu/~gdweber/software/sifflet/doc/tutorial.html * RELEASE-NOTES: http://mypage.iu.edu/~gdweber/software/sifflet/RELEASE-NOTES * ISSUES: http://mypage.iu.edu/~gdweber/software/sifflet/ISSUES ------------------------------------------------------------------------ -- Gregory D. Weber, Ph. D. : Associate Professor of Informatics / \ Indiana University East 0 : Tel. (765) 973-8420; FAX (765) 973-8550 / \ http://mypage.iu.edu/~gdweber/ 1 []

2 3

combining predicates, noob question
by Sebastián Krynski 09 Jul '12

09 Jul '12

As I was using predicates (a -> bool) , it appeared the need for combining them with a boolean operator (bool -> bool -> bool) in order to get a new predicate combining the previous two. So I wrote my function combinerPred (see code below). While I think this is JUST ok, i'm feeling a monad in the air. So.. where is the monad? combinerPred :: (a -> Bool) -> (a -> Bool) -> (Bool -> Bool -> Bool) -> (a -> Bool) combinerPred pred1 pred2 op = \x -> op (pred1 x) (pred2 x) thanks Sebastián

4 5