News aggregator

Hi folks. Hackage contains several JSON packages but as far as I see, they all provide 'static' conversion from JSON format to Haskell data type. Is there a method of converting object containing optional filed 'a' to for example Maybe a. Thanks, Sergey

Rewriting is the science of replacing equals by equals and thus a very powerful method for dealing with equations. There are strong connections between Haskell programming and rewriting. Therefore, we announce a new workshop, International Workshop on Haskell And Rewriting Techniques (HART 2013) http://www.imn.htwk-leipzig.de/HART2013/ to be held on June 27, in conjunction with RDP 2013, in Eindhoven. (RDP contains RTA, the main rewriting conference.) We plan a half day of discussions, in an informal setting, on how Haskell and rewriting techniques and theories can cross-fertilize each other. Topics of interest are, for example, equational reasoning and other rewriting techniques for program verification and analysis; lambda calculi and type systems for functional programs and higher order rewriting systems; rewriting of type expressions in the type checker; rewriting of programs by refactoring tools, optimizers, code generators; execution of programs as a form of graph rewriting; temp

submitted by tondwalkar
[link] [3 comments]

For me, the best way to understand something is usually to implement it myself. So when I first started getting serious about Haskell, I implemented (in Common Lisp) a simple lazy functional programming language that used graph rewriting for the interpretation. Then, years later, I mentioned this implementation in a Reddit thread about writing a Lisp interpreter in Haskell (maybe inspired by the well-known Haskell tutorial and this blogpost's namesake). I now decided to clean up that old code, throw out all the unnecessary cruft, and arrive at something easy to understand. The finished interpreter is less than 500 lines of Common Lisp (not including the type checker which will be the subject of my next post).

I should also add that of course we're not going to actually implement Haskell here. As we'll see, the language is a very much simplified model of pure, lazy functional languages. It's actually closer to GHC's Core than Haskell.

Syntax

We're not going to bother with parsing: our input programs will be S-expressions. For example, instead of the following Haskell program:

data List a = Nil | Cons a (List a) map f Nil = Nil map f (Cons x xs) = Cons (f x) (map f xs)

we will write:

(defdata list (a) nil (cons a (list a))) (deffun map ((f nil) nil) ((f (cons x xs)) (cons (f x) (map f xs))))

As you can see, there is no syntactic distinction between variable names and constructor names — when translating these S-expressions, we'll take special care to always register constructor names before processing expressions.

Internally, we'll represent programs in an even more simplified way, by making all function applications explicit. Multi-parameter functions and constructors, of course, will be implemented via schönfinkeling. The syntax tree itself is represented using two class hierarchies: subclasses of expr for expressions, and subclasses of pattern for patterns:

Going from S-expressions to this object-oriented representation is straightforward:

Graph rewriting semantics

The basic idea behind implementing a lazy functional language using graph rewriting is to represent terms as directed graphs, and reducing a function application is implemented by replacing the application node with the graph corresponding to the right-hand side of the function definition, of course with all the references to formal arguments instantiated to the actual arguments.

Let's look at a simple example first, with no sharing or recursion:

(defvar x (let ((primes (cons 2 (cons 3 (cons 5 nil))))) (map (+ (+ 1 1) primes))))

As you can see, the green boxes represent constructors (with rounded corners for primitive values), yellow ones are functions, and the small gray circles are function applications. There are no variables, since references are resolved when building this graph.

We can simplify this format by omitting application nodes and just pushing arguments under their function node (until it becomes saturated), like this:

Reducing this entails instantiating the following graph (from the second case of map), with f bound to (+ (+ 1 1), x bound to 2, and xs bound to (cons 3 (cons 5 nil)). Note the explicit application node: we won't know the arity of f until it's bound to something.

Resulting in

Note how the first argument to + is shared in the result. Also note how (+ (+ 1 1) 2) is not reduced by map, since it is lazy in its first argument.

Our second example shows recursively-defined terms:

(defvar nats (cons 0 (map (+ 1) nats)))

This is already in WHNF, but we can nevertheless reduce the tail of the list, to get this:

and so on.

Representing the graphs

Since we want to be able to replace function application subgraphs easily (when reducing those applications), the representation uses an extra level of indirection: gnodes contain the payload: the type of the node and pointers to its children grefs; and each gref contains a single reference to its content gnode. grefs can be shared, so when its content gnode is replaced, all the shared references are updated.

Variable nodes

Earlier, we said variables are not present as such in the graph representation, since they are inlined (respecting sharing, of course). But we still have a var-gnode class defined above. The reason for that is simply to mark occurances of formal variables in function definitions, which will be filled in when reducing function applications.

But there's another, more compilcated problem with variables. Our language's let construct is mutually recursive, so we can't just build up the variables' graphs one by one:

(defvar main (let ((zig (cons 0 zag)) (zag (cons 1 zig))) zig))

Of course, not everything can be helped by this:

(defvar silly-list (let ((xs xs)) (cons 1 xs)))

So we'll add a gnode subclass for temporarily storing let-bound variable occurances, and replace them after the fact. Unfortunately, this also causes the code that translates from expr to gnode to become a little spaghetti-y. On the other hand, we don't implement lambda lifting, as it's not strictly essential — the programmer will have to do it by hand, by writing top-level functions instead.

Making it tick

There are three parts to making reductions work: first, a way to do pattern matching against function alternatives. Second, given a mapping from this match, instantiating a function definition by replacing var-gnodes. The third part is orchestrating all of this by taking care of choosing which nodes to reduce.

Pattern matching is a relatively straightforward matter: a variable pattern always succeeds (and binds the subgraph) and a constructor pattern can either succeed and recurse, fail, or (if the actual node is a function application) force reduction. This latter is done via raising a Lisp condition.

Once we have the bindings in the format returned by match-pattern, we can easily instantiate function bodies, we just have to maintain a mapping from old node to new to avoid diverging on cycles.

Actual reduction then becomes just a matter of putting these two modules together. Several functions are provided with varying granularity: reduce-graph tries direct reduction, reduce-graph* catches need-reduce conditions and recurses on those nodes, in effect making sure a single reduction step at the target site can be made; and reduce-to-whnf repeatedly uses reduce-graph* until the head is either a constructor, or a non-saturated function application. simplify-apps is not really a reduction step, it just removes superfluous apply-gnodes.

Housekeeping

The rest of the code just keeps a registry of functions and constructors, and defines some primitive functions (note how we need the very simple bool ADT to be a built-in just so we have a return type for >=).

Putting it all together

Given an S-expression containing an Alef program, we can transform it into a graph suitable for reduction by doing the following steps:

1. Split into datatype definitions, variable definitions and function definitions
2. Process datatype definitions by registering the constructor names (since we don't do typechecking yet, the only information needed about constructors is that they are not function calls/variable references)
3. Register top-level variable names
4. Register function names
5. Process top-level variable definitions into graphs
6. Process function definitions into graph templates
7. Return the graph of the top-level variable called main as the actual program

Visualization

The nice plots in this blogpost were created by dumping the program's graph in GraphViz format, and running dot on the output. The visualization code is a straightforward traversal of the graph. Note how we store a stable name (generated using gensym) in each node, to ensure a correspondence in the generated GraphViz nodes between reduction steps. In the future, this could be used to e.g. animate the graph to show each reduction step.

We can use this like so:

(in-fresh-context (let ((g (parse-program '((defvar main (string-append "Hello, " "world!")))))) (simplify-apps g) (with-open-file (s "hello.dot" :direction :output :if-exists :supersede) (dot-from-graph g s)) (reduce-to-whnf g) (with-open-file (s "hello-reduced.dot" :direction :output :if-exists :supersede) (dot-from-graph g s))))

Which results in the very uninteresting graphs:

and

In conclusion

SLOCCount tells me the whole code presented in this blogpost is 471 lines of Common Lisp; you can check out the full source code on GitHub. It implements lazy semantics for a pure functional programming language with pattern matching on algebraic datatypes; of course, by changing the definition of reduce-function, we could easily make it strict.

Next time

In my next blog post, I'll be adding Hindley-Milner type inference / typechecking. Because of the type-erasure semantics of our language, we could implement our evaluator without any type system implementation, simply by assuming the input program to be well-typed. So all that we'll need is an extra typechecking step between parsing and graph building that either rejects or accepts an Alef program.

Recently I have specialized Repa 3 for processing arrays of small vectors of numbers, particulary images: Yarr library (docs). In spite of Yarr library isn't fully completed yet, IMHO it already adds value to Repa in this domain.

The problem is that I have no motivation to develop the library because indeed I don't use it. It is just a course project. On the other hand, it is a pity to dig the library unused.

So I want to hand over the library to someone who is interested in its functionality.

submitted by leventov
[link] [6 comments]

Hello cafe, I've been poking around and I haven't seen this addressed anywhere except obliquely in the end of section 8.5.1 of the report, where it says that variable argument C functions aren't supported: http://www.haskell.org/onlinereport/haskell2010/haskellch8.html The scenario is pretty simple. I generate C code at runtime. I compile it to a .so. I know how many arguments it expects (but only at runtime), and I get a FunPtr back from 'dlsym'. How do I call it? I was hoping there would be some "Raw" lower level FFI layer that I could use to invoke a C function without automagic marshaling and all the other goodness provided by the normal "foreign import" mechanism. Failing that, will I just have to generate complex wrappers on the C side which I call N times to load up N arguments into some stateful container before finally launching the function? Thanks, -Ryan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >haskell.org http://www.haskell.org/mailman

submitted by lethalman
[link] [5 comments]

Has anyone formulated a reasonable set of laws for MonadReader? The instances for continuation-based monad transformers contradict any intuition about local and ask. E.g. for LogicT: > flip runReader 1 $ observeAllT $ local (const 2) ask [1] > flip runReader 1 $ observeAllT $ local (const 2) mzero <|> ask [2] I wonder whether there are any real use cases for such instances (and, consequently, whether they should be removed). Roman

As my wife likes to say, I'm starting to have an "affair" with another language. This weekend, I thought I would give Haskell a try. I'm loving the REPL experience so far, but I'm hitting an environmental problem trying to run this word count program I found here: https://gist.github.com/FranklinChen/1448622

It can't seem to find the HashMap module, but I thought that was standard. Isn't it? If not, how do I install it?

$ ghc --make wordcount.hs wordcount.hs:4:17: Could not find module `Data.HashMap.Strict': Use -v to see a list of the files searched for.

If it helps, this is on Debian (in VMWare). I installed the haskell-platform package.

$ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.12.1 submitted by chindogubot
[link] [5 comments]

Wednesday 27-Feb-2013 6-45pm (prompt) City University, College Building, St John Street, London. EC1V 4PB http://www.meetup.com/London-HUG/events/103545552/ Being Lazy Speaker: Peter Marks This talk will explore lazy evaluation in Haskell. After a brief introduction to non-strictness, and establishing a basic conceptual model of evaluation in Haskell, the primary focus will be on how we can utilize laziness to allow us to write programs differently to how we would in an eagerly evaluated language. The session will be rich on code with a worked example of a complete program. We'll also touch on some of the pitfalls of laziness that we run into in real world situations. Peter Marks has been developing software for over thirty years and has been using Haskell commercially for four years. He currently leads the FPF team at Barclays and is an active member of the London Haskell community, running the Hoodlums meetup group. N.B. The start time is slightly later than previously, to make sure ever

submitted by FPguy
[link] [2 comments]

submitted by FPguy
[link] [2 comments]

submitted by FPguy
[link] [12 comments]

A question we hear a lot is: who's already using Haskell commercially, and how is it going?

Fortunately, there are a lot of Haskell users happy to talk about their experiences. Several companies have been generous enough to spend their time with us, being interviewed about their experiences so we can share them with you.

Please enjoy our new Case Studies collection, which we are launching with studies of three commercial Haskell users: Bump Technologies, Janrain, and Silk. Read about their own experiences putting Haskell to work.

We are already interviewing more commercial Haskell users in other industries, so this collection will continue to grow.

A question we hear a lot is: who’s already using Haskell commercially, and how is it going?

Fortunately, there are a lot of Haskell users happy to talk about their experiences. Several companies have been generous enough to spend their time with us, being interviewed about their experiences so we can share them with you.

Please enjoy our new Case Studies collection, which we are launching with studies of three commercial Haskell users: Bump Technologies, Janrain, and Silk. Read about their own experiences putting Haskell to work.

We are already interviewing more commercial Haskell users in other industries, so this collection will continue to grow.

submitted by FPguy
[link] [4 comments]

submitted by crntaylor
[link] [7 comments]

submitted by fluffynukeit
[link] [49 comments]