Interpreting types as abstract values [The Abstract of the lecture notes] We expound a view of type checking as evaluation with `abstract values'. Whereas dynamic semantics, evaluation, deals with (dynamic) values like 0, 1, etc., static semantics, type checking, deals with approximations like int. A type system is sound if it correctly approximates the dynamic behavior and predicts its outcome: if the static semantics predicts that a term has the type int, the dynamic evaluation of the term, if it terminates, will yield an integer. As object language, we use simply-typed and let-polymorphic lambda calculi with integers and integer operations as constants. We use Haskell as a metalanguage in which to write evaluators, type checkers, type reconstructors and inferencers for the object language.
In denotational semantics and functional programming, the terms monad morphism, monad layering, monad constructor, and monad transformer have by now accumulated 20 years of twisted history. The exchange between Eric Kidd and sigfpe about the probability monad prompted me to investigate this history
Generalising Monoids The word 'monad' is derived from the word 'monoid'. The explanation usually given is that there is an analogy between monoids and monads. On the surface, this seems a bit unlikely. The join operation in a monad is supposed to correspond to the binary operator in the monoid, but join is a completely different kind of thing, certainly not a binary operator in any usual sense. I'm going to make this analogy precise so that it's clear that both monoids and monads are examples of the same construction. In fact, I'm going to write some Haskell code to define monoids and monads in almost exactly the same way. I was surprised to find I could do this because instances of Haskell's Monoid and Monad aren't even the same kind of thing (where I'm using 'kind' in its technical sense). But it can be done.
Syntax extension for Monads in Ocaml Jacques Carette, Lydia E. van Dijk and Oleg Kiselyov This Camlp4 extension provides some syntactic sugar to beautify monadic expressions. Example: A simple but realistic example of the use of a list monad looks like this bind [1; 2; 3] (fun a -> bind [3; 4; 5] (fun b -> return (a + b))) where we assume the appropriate definitions of the functions "bind" and "return". With the help of "pa_monad" this can be written as perform a <-- [1; 2; 3]; b <-- [3; 4; 5]; return (a + b) which is much clearer and thus easier to understand and maintain. By the way, the expression evaluates to [4; 5; 6; 5; 6; 7; 6; 7; 8] the sum of each pair of values of the input list
A continuation-based, backtracking, logic programming monad. An adaptation of the two-continuation implementation found in the paper Backtracking, Interleaving, and Terminating Monad Transformers available here: http://okmij.org/ Control.Monad.Logic.Class
Suppose someone stole all the monads but one, which monad would you want it to be? If you're a Haskell programmer you wouldn't be too bothered, you could just roll your own monads using nothing more than functions. But suppose someone stole do-notation leaving you with a version that only supported one type of monad. Which one would you choose? Rolling your own Haskell syntax is hard so you really want to choose wisely. Is there a universal monad that encompasses the functionality of all other monads? About a year ago I must have skimmed this post because the line "the continuation monad is in some sense the mother of all monads" became stuck in my head. So maybe Cont is the monad we should choose. This post is my investigation of why exactly it's the best choice. Along the way I'll also try to give some insight into how you can make practical use the continuation monad.
Comonads are an abstraction from category theory dualing many qualities of Monads. They are conceptually much simpler than arrows but seem to offer a solution to some problems not easily solved by monads. The ideas presented here are not novel except for the comonadic combinators for a nicer syntax. Typeclass Combinators Reader State Stream Writer Links
Tom Schrijvers, Peter Stuckey and Philip Wadler Abstract: A constraint programming system combines two essential components: a constraint solver and a search engine. The constraint solver reasons about satisfiability of conjunctions of constraints, and the search engine controls the search for solutions by iteratively exploring a disjunctive search tree defined by the constraint program. In this paper we give a monadic definition of constraint programming where the solver is defined as a monad threaded through the monadic search tree. We are then able to define search and search strategies as first class objects that can themselves be built or extended by composable search transformers. Search transformers give a powerful and unifying approach to viewing search in constraint programming, and the resulting constraint programming system is first class and extremely flexible. Let's briefly look at the n queens example from the paper. First, there is the nqueens model:
Total Functional Programming Here's an interesting paper recently mention in another thread: Total Functional Programming... Abstract: The driving idea of functional programming is to make programming more closely related to mathematics. A program in a functional language such as Haskell or Miranda consists of equations which are both computation rules and a basis for simple algebraic reasoning about the functions and data structures they define. The existing model of functional programming, although elegant and powerful, is compromised to a greater extent than is commonly recognized by the presence of partial functions. We consider a simple discipline of total functional programming designed to exclude the possibility of non-termination. Among other things this requires a type distinction between data, which is finite, and codata, which is potentially infinite. I presume that the bogus definiton of "fib" is a subtle reminder of the importance of eliminating bottom.
emir burak In Informatics, there are two (related) meanings of the word "monad": * A triple (T,eta,mu) following some laws in category theory * A way of structuring functional programs The first meaning can probably not be described easily in natural language. Michael Arbib and Ernest Manes' "Arrows, Structure, Functors - The Categorical Imperative". describe them as (generalized monoids) in Section 10.2 and through adjointness to the forgetful functor from algebras to sets. That last connection basically makes everything that we can write down or model using abstract syntax / universal algebra a monad. The second view is described in Wadler's papers. I mention category theory because we can describe things that are not computations as monads. It also reminds us why a monad is a collection of things taken together. With the List example in mind, a potentially more revealing account on monads (aka triples) can be found in the free book Barr, Wells
Just fire up your REPL and see for yourself how the malleable syntactic structures of the language grow in front of your eyes, alongside your program. Whether this is through Lisp macros or Ruby meta-programming or Scala control structures, the secret sauce is in the ability to implement more and more powerful abstractions within the language. But what makes one language shine more compared to another is the ability to combine abstractions leading to more powerful syntactic structures. Recently people have been talking about the Maybe monad and its myriads of implementation possibilities in Ruby. Because of its dynamic nature and powerful meta-programming facilities, Ruby allows you to write this .. @phone = Location.find(:first, ...elided... ).andand.phone Here andand is an abstraction of the Maybe monad that you can seamlessly compose with core Ruby syntax structures, effectively growing the Ruby language.
Once you start thinking about structuring your code to use Option in languages which have built-in support for it, you’ll find yourself dreaming about such patterns in other, less fortunate languages. It’s really sort of bizarre how much this little device can open your mind to new possibilities. Take my code, and give it a try in your project. Better yet, implement something on your own which solves the problem more elegantly! The stodgy old Java “best practices” could use a little fresh air. P.S. Yes, I know that the original implementation of this was actually the Maybe monad in Haskell. I picked Option instead mainly because a) I like the name better, and b) it’s Scala, so it’s far more approachable than Haskell.
One obvious solution is to do two passes -- one to lay everything out, then another to generate now that offsets are known.Here's where it gets clever. Rather than two passes, they instead write the code in such a way that the code-generator function's output is also passed as a parameter to the same function.
Collection of links to monad implementations in various languages. Due to recent discussions here on LtU and on the Haskell mailing lists I've compiled a list of links to implementations of monads in various languages. If you know of any that aren't listed here, please submit them in a comment. * Clean * Haskell * Java * Joy * OCaml * Perl * Prolog * Python * Ruby * Scheme
Data Platform Development The Microsoft Data Platform provides developers with a comprehensive programming framework in which to create data centric solutions that target mobile devices, desktops, Web servers, and enterprise servers. Getting Started with... ADO.NET ADO.NET Data Services ADO.NET Entity Framework LINQ MDAC/WDAC Microsoft Project Code Named "Velocity" SQL Server Driver for PHP SQL Server JDBC Driver SQL Server Native Client XML