tag:blogger.com,1999:blog-81303268260659832172024-03-08T19:45:02.017+01:00splonderzoekGeeky things and other research from a work in progressAnonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-8130326826065983217.post-27233369760884904412011-03-24T15:07:00.000+01:002011-03-24T15:07:42.163+01:00Draft: "Type-Changing Program Improvement with Type and Transform Systems"<p><a href="http://people.cs.uu.nl/johanj/">Johan Jeuring</a>, <a href="http://andres-loeh.de/">Andres Löh</a>,and I have submitted a paper to <a href="http://www.icfpconference.org/icfp2011/">ICFP 2011</a>.</p>
<blockquote>
<p><strong><a href="http://people.cs.uu.nl/leather/publications/icfp2011/leather-tts-icfp2011.pdf">Type-Changing Program Improvement with Type and Transform Systems</a></strong></p>
<p>Structured program improvement is monotonous and error-prone and should be automated whenever possible. Typical approaches such as refactoring are too restrictive, allowing for only minimal changes to types in the program. Other improvement techniques that allow type changes are few and somewhat limited.</p>
<p>We are interested in type-driven program transformations that spread virally throughout code, infecting both function definitions and applications. Such transformations are beneficial for software evolution or migrating a program to a new library interface. An example transformation is the optimization of list-based strings to Hughes' lists, a transformation that can potentially infect every string in a program.</p>
<p>We present type and transform systems, an approach to type-safe, automatic program improvement in which complex transformations can be expressed by simple inference rules that define a relation between source and target programs. In this paper, we describe the relations, their properties, how to design transformations, and a prototype implementation. We also demonstrate automatic string optimization, which, to the best of our knowledge, has not been shown before.</p>
</blockquote>
<p>The <a href="http://people.cs.uu.nl/leather/publications/icfp2011/tts-0.1.tar.gz">prototype code</a> is also available for a test drive.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com0tag:blogger.com,1999:blog-8130326826065983217.post-47833786073453119362010-03-19T15:55:00.003+01:002010-03-19T15:58:10.883+01:00Call for Papers: IFL 2010<p>I'm involved with planning <a href="http://www.cs.uu.nl/wiki/IFL2010" style="font-weight:bold">IFL 2010, the 22nd Symposium on Implementation and Applications of Functional Languages</a>, held in <a href="http://en.wikipedia.org/wiki/Alphen_aan_den_Rijn">Alphen aan den Rijn</a> in the Netherlands. Of course, I think you should consider submitting something to the conference. Note that submissions are reviewed after the symposium for the proceedings, so it's easy to use the venue as a way to refine incomplete/unfinished products. The call for papers follows.</p>
<hr width="33%">
<div>
22nd Symposium on Implementation and Applications of Functional Languages (IFL 2010)<br>
September 1-3, 2010<br>
Utrecht University<br>
Alphen aan den Rijn, The Netherlands<br>
<a href="http://www.cs.uu.nl/wiki/IFL2010">http://www.cs.uu.nl/wiki/IFL2010</a>
</div>
<p>
After a first successful visit to the USA, the Symposium on Implementation and Applications of Functional
Languages returns to Europe for its 22nd edition. The hosting institution is Utrecht University in the
Netherlands, although the conference itself will take place in the ornithological theme park Avifauna
in Alphen aan den Rijn, situated conveniently close to Schiphol (Amsterdam Airport). The symposium dates
are September 1-3, 2010.
</p>
<p>
The goal of the IFL symposia is to bring together researchers actively engaged in the implementation and
application of functional and function-based programming languages. IFL 2010 will be a venue for researchers
to present and discuss new ideas and concepts, work in progress, and publication-ripe results related to
the implementation and application of functional languages and function-based programming.
</p>
<p>
Following the IFL tradition, IFL 2010 will use a post-symposium review process to produce formal proceedings
which will be published by Springer Verlag in the Lecture Notes in Computer Science series. All participants in
IFL 2010 are invited to submit either a draft paper or an extended abstract describing work to be presented
at the symposium. At no time may work submitted to IFL be simultaneously submitted to other venues. Here
we follow the <a href="http://www.sigplan.org/republicationpolicy.htm">ACM Sigplan republication policy</a>.
The submissions will be screened by the program committee chair to make sure they are within the scope of IFL,
and will appear in the draft proceedings distributed at the symposium. Submissions appearing in the draft
proceedings are not peer-reviewed publications. After the symposium, authors will be given the opportunity
to incorporate the feedback from discussions at the symposium and will be invited to submit a revised full
article for the formal review process. These revised submissions will be reviewed by the program committee
using prevailing academic standards to select the best articles, which will appear in the formal proceedings.
</p>
<h3>INVITED SPEAKER</h3>
<p>
Johan Nordlander of Lulea University, the designer and developer of the Timber language, is the invited
speaker at IFL 2010. Timber is a functional programming language that draws some of its concepts from
object-oriented programming, and has built-in facilities for concurrent execution. The language is
specifically targeted at implementing real-time embedded systems.
</p>
<h3>TOPICS</h3>
<p>
IFL welcomes submissions describing practical and theoretical work as well as submissions describing
applications and tools. If you are not sure that your work is appropriate for IFL 2010, please contact
the PC chair at jur@cs.uu.nl. Topics of interest include, but are not limited to:
<ul>
<li>language concepts</li>
<li>type checking</li>
<li>contracts</li>
<li>compilation techniques</li>
<li>staged compilation</li>
<li>runtime function specialization</li>
<li>runtime code generation</li>
<li>partial evaluation</li>
<li>(abstract) interpretation</li>
<li>generic programming techniques</li>
<li>automatic program generation</li>
<li>array processing</li>
<li>concurrent/parallel programming</li>
<li>concurrent/parallel program execution</li>
<li>functional programming and embedded systems</li>
<li>functional programming and web applications</li>
<li>functional programming and security</li>
<li>novel memory management techniques</li>
<li>runtime profiling and performance measurements</li>
<li>debugging and tracing</li>
<li>virtual/abstract machine architectures</li>
<li>validation and verification of functional programs</li>
<li>tools and programming techniques</li>
<li>industrial applications of functional programming</li>
</ul>
</p>
<h3>PAPER SUBMISSIONS</h3>
<p>
Prospective authors are encouraged to submit papers or extended abstracts to be published in the draft proceedings
and to present them at the symposium. All contributions must be written in English, conform to the Springer-Verlag
LNCS series format and not exceed 16 pages. The draft proceedings will appear as a technical report of the
Department of Computer Science of Utrecht University.
</p>
<h3>PETER LANDIN PRIZE</h3>
<p>
The Peter Landin Prize is awarded to the best paper presented at the symposium every year.
The honored article is selected by the program committee based on the submissions received for
the formal review process. The prize carries a cash award equivalent to 150 Euros.
</p>
<h3>IMPORTANT DATES</h3>
<p>
<table>
<tr><td>Draft proceedings submission deadline</td><td>July 25, 2010</td></tr>
<tr><td>Registration deadline</td><td>August 1, 2010</td></tr>
<tr><td>IFL 2010 Symposium</td><td>September 1-3, 2010</td></tr>
<tr><td>Submission for review process deadline</td><td>October 25, 2010</td></tr>
<tr><td>Notification Accept/Reject</td><td>December 22, 2010</td></tr>
<tr><td>Camera ready version</td><td>February 17, 2011</td></tr>
</table>
</p>
<h3>PROGRAM COMMITTEE</h3>
<p>
<table>
<tr><td>Jost Berthold</td><td>University of Copenhagen (DIKU), Denmark</td></tr>
<tr><td>Olaf Chitil</td><td>University of Kent, UK</td></tr>
<tr><td>John Clements</td><td>California Polytechnic State University, USA</td></tr>
<tr><td>Matthew Fluet</td><td>Rochester Institute of Technology, USA</td></tr>
<tr><td>Andy Gill</td><td>Kansas University, USA</td></tr>
<tr><td>Jurriaan Hage (Chair)</td><td>University of Utrecht, Netherlands</td></tr>
<tr><td>Bastiaan Heeren</td><td>Open University, Netherlands</td></tr>
<tr><td>Ralf Hinze</td><td>University of Oxford, UK</td></tr>
<tr><td>John Hughes</td><td>Chalmers University of Technology, Sweden</td></tr>
<tr><td>Yukiyoshi Kameyama</td><td>University of Tsukuba, Japan</td></tr>
<tr><td>Gabriele Keller</td><td>University of New South Wales, Australia</td></tr>
<tr><td>Pieter Koopman</td><td>Radboud University Nijmegen, Netherlands</td></tr>
<tr><td>Luc Maranget</td><td>INRIA, France</td></tr>
<tr><td>Simon Marlow</td><td>Microsoft Research, UK</td></tr>
<tr><td>Marco T. Morazan</td><td>Seton Hall University, USA</td></tr>
<tr><td>Rex Page</td><td>University of Oklahoma, USA</td></tr>
<tr><td>Ricardo Pena</td><td>Universidad Complutense de Madrid, Spain</td></tr>
<tr><td>Sven-Bodo Scholz</td><td>University of Hertfordshire, UK</td></tr>
<tr><td>Tom Schrijvers</td><td>Catholic University of Leuven, Belgium</td></tr>
<tr><td>Don Stewart</td><td>Galois, USA</td></tr>
<tr><td>Wouter Swierstra</td><td>Vector Fabrics, Netherlands</td></tr>
<tr><td>Don Syme</td><td>Microsoft, UK</td></tr>
<tr><td>Peter Thiemann</td><td>University of Freiburg, Germany</td></tr>
<tr><td>Phil Trinder</td><td>Heriott-Watt University, Scotland</td></tr>
<tr><td>Janis Voigtlaender</td><td>University of Bonn, Germany</td></tr>
<tr><td>Viktoria Zsok</td><td>Eotvos Lorand University, Hungary</td></tr>
</table>
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com0Zurich, Switzerland47.3690239 8.538032647.252761400000004 8.3045730999999989 47.4852864 8.7714921tag:blogger.com,1999:blog-8130326826065983217.post-11328759883246647412010-03-12T10:44:00.001+01:002010-03-12T10:45:46.400+01:00Final: "Push-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization"<p>We have put up the final copy of our <a href="http://blogs.shu.edu/projects/IFL2009/">IFL 2009</a> paper. Here are the <a href="http://people.cs.uu.nl/andres/Incrementalization/">PDF and source code</a>.</p>
<blockquote><strong>Abstract</strong> Programs in languages such as Haskell are often datatype-centric and make extensive use of folds on that datatype. Incrementalization of such a program can significantly improve its performance by transforming monolithic atomic folds into incremental computations. Functional incrementalization separates the recursion from the application of the algebra in order to reduce redundant computations and reuse intermediate results. In this paper, we motivate incrementalization with a simple example and present a library for transforming programs using upwards, downwards, and circular incrementalization. Our benchmarks show that incrementalized computations using the library are nearly as fast as handwritten atomic functions.</blockquote>
<p>The focus is quite a bit different from the <a href="http://splonderzoek.blogspot.com/2009/11/draft-pull-ups-push-downs-and-passing.html">draft submission</a>. We concentrate more on describing how to specify incrementalized computations. We also compare the performance of handwritten atomic functions, specifications written with folds, and incrementalized functions. We found that incrementalization had a relatively small impact on an atomic function's performance. If you have the right needs, of course, the impact on your program time can be profound.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com1Padualaan 14, 3584 Utrecht, The Netherlands52.0848611 5.169702652.0815646 5.1624071 52.088157599999995 5.1769981tag:blogger.com,1999:blog-8130326826065983217.post-71784475970895324682009-11-05T16:12:00.004+01:002010-03-12T10:47:23.043+01:00Draft: "Pull-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization"<p><strong>Update!</strong> The <a href="http://splonderzoek.blogspot.com/2010/03/final-push-ups-push-downs-and-passing.html">final version</a> is now available.</p>
<p><a href="http://andres-loeh.de/">Andres Löh</a>, <a href="http://people.cs.uu.nl/johanj/">Johan Jeuring</a>, and I have submitted a paper to <a href="http://blogs.shu.edu/projects/IFL2009/">IFL 2009</a>.</p>
<blockquote>
<p><strong><a href="http://docs.google.com/uc?export=download&id=0Bxsn6dYLD_DHNWE5MmNjNmQtYzI1My00MmU0LWIzOTgtY2FjMDkzNTU3Yjdm">Pull-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization</a></strong></p>
<p><strong>Abstract</strong> Programs in functional programming languages with algebraic datatypes are often datatype-centric and use folds or fold-like functions. Incrementalization of such a program can significantly improve its performance. Functional incrementalization separates the recursion from the calculation and significantly reduces redundant computation. In this paper, we motivate incrementalization with a simple example and present a library for transforming programs using upwards, downwards, and circular incrementalization. We also give a datatype-generic implementation for the library and demonstrate the incremental zipper, a zipper extended with attributes.</p>
</blockquote>
<p>This is the result of work that has previously been mentioned on this blog:
<ol>
<li><a href="http://splonderzoek.blogspot.com/2008/01/smart-constructors.html">Smart constructors</a></li>
<li><a href="http://splonderzoek.blogspot.com/2009/02/incremental-fold-design-pattern.html">Incremental fold, a design pattern</a></li>
<li><a href="http://splonderzoek.blogspot.com/2009/03/incremental-attributes.html">Incremental attributes</a></li>
<li><a href="http://splonderzoek.blogspot.com/2009/04/latest-on-incremental-fold-and.html">Latest on the incremental fold and attributes</a></li>
<li><a href="http://splonderzoek.blogspot.com/2009/09/upwards-and-downwards-accumulations-on.html">"Upwards and downwards accumulations on trees" translated into Haskell</a></li>
</ol>
</p>
<p>We would be happy to have any feedback.</p>
<p><strong>Update!</strong> Here's the (completely messy, badly formatted, undocumented, and screwy) <a href="http://github.com/spl/splonderzoek/blob/master/Draft_IFL_2009.hs">code used in the paper</a> if you want to have a go at it.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com4Padualaan 14, 3584 Utrecht, The Netherlands52.0848611 5.169702652.0815646 5.1624071 52.088157599999995 5.1769981tag:blogger.com,1999:blog-8130326826065983217.post-55337441526193508492009-09-30T10:34:00.001+02:002009-10-02T17:11:25.087+02:00"Extensibility and type safety in formatting: the design of xformat" at the Dutch HUG<p>I'm finally getting around to posting the slides for my talk at the <a href="http://haskell.org/haskellwiki/Dutch_HUG">Dutch HUG</a> on 11 September. After that, I was preparing my talk for <a href="http://blogs.shu.edu/projects/IFL2009/">IFL</a> on incrementalization of datatype-centric programs. I arrived back in Utrecht yesterday morning and crashed mid-day.</p>
<p>You can find the slides <a href="http://www.scribd.com/doc/20111590/Extensibility-and-type-safety-in-formatting-the-design-of-xformat-Dutch-HUG-11-September-2009">on Scribd</a> and <a href="http://github.com/spl/dutchhug2009">on Github</a>. Enjoy!</p>
<p><strong>Update</strong>: Thanks to <a href="http://tom.lokhorst.eu/">Tom Lokhorst</a>, my talk is also <a href="http://vimeo.com/6864643">on video</a>.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com4Padualaan 14, 3584 Utrecht, The Netherlands52.0848619 5.17044152.0815654 5.1631455000000006 52.0881584 5.1777365tag:blogger.com,1999:blog-8130326826065983217.post-54434741038551327012009-09-09T14:50:00.002+02:002009-12-14T20:45:56.432+01:00"Upwards and downwards accumulations on trees" translated into Haskell<p>I was reading "<a href="http://www.citeulike.org/user/spl/article/5486052">Upwards and downwards accumulations on trees</a>" by <a href="http://www.softeng.ox.ac.uk/Jeremy.Gibbons/">Jeremy Gibbons</a>, and it's written in the <a href="http://en.wikipedia.org/wiki/Bird-Meertens_Formalism">Bird-Meertens formalism</a> (a.k.a. Squiggol) of yesteryear. Not that I have anything against people who can write and understand this stuff (in fact, I have a lot of respect for them), but for me, the inconsistent and seemingly arbitrary notation leaves something to be desired. In an attempt to understand what was actually being done, I translated most of the equations to <a href="http://github.com/spl/splonderzoek/blob/master/Accumulations.hs" style="font-weight:bold">Haskell code</a>. If you plan on reading this paper, here's hoping I could jump-start your comprehension with this contribution.</p>
<p>The only real issue that I ran into while performing this translation is in the function <code>s_fork_sl2</code>. The second component of the catamorphism, ((⊙ ↟ ≪) ∘ ≪²), does not have the expected type <code>(b, b) -> a -> (b, b) -> (b, b)</code>. After attempting to puzzle through how to unify the two, I eventually gave up and just came up with a function that seemed to do what I thought it should do, <code>pairs g (x, _) _ (y, _) = (g x y, x)</code> where <code>g :: b -> b -> b</code> is ⊙. But I'm not sure whether there's a bug in the definition in the paper or the one in my code. The code seems to work for a few tests. If you've already read this paper or you're at all interested in debugging Squiggol, I would be happy to learn how this works.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com5Padualaan 14, 3584 Utrecht, The Netherlands52.0848619 5.17044152.0815654 5.1631455000000006 52.0881584 5.1777365tag:blogger.com,1999:blog-8130326826065983217.post-70987835335087466172009-08-06T21:12:00.000+02:002009-08-06T21:12:09.756+02:00Sharing on Google Reader<p>I <a href="http://www.google.com/reader/shared/sean.leather">share things</a> regularly on <a href="http://reader.google.com/">Google Reader</a>. They tend to be eclectic but sometimes technical and sometimes PLT- or Haskell-related. I would like to find out who else uses Reader. If you're interested in letting me and other people know about your own shared items, please post the link in the comments. We can perhaps create a cozy little Reader community.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com5tag:blogger.com,1999:blog-8130326826065983217.post-55575508323896427902009-07-10T02:41:00.000+02:002009-07-10T02:41:31.852+02:00Fun and generic things to do with EMGM at the London HUG<p>
I just gave a talk about <a href="http://www.cs.uu.nl/wiki/GenericProgramming/EMGM">EMGM</a> at the <a href="http://www.londonhug.net/">London HUG</a>. The slides can be found <a href="http://www.scribd.com/doc/17243250/Fun-and-generic-things-to-do-with-EMGM-London-HUG-9-July-2009">on Scribd</a> or <a href="http://github.com/spl/londonhug2009">on Github</a>.
</p>
<p>
Thanks to everybody who showed up! I'm very sorry I was so late. Thanks to <a href="http://community.haskell.org/~ndm/">Neil</a> for filling in until I got there.
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com0Parks Rd, Oxford OX1, UK51.7590277 -1.256415851.755707199999996 -1.2637113 51.7623482 -1.2491203000000002tag:blogger.com,1999:blog-8130326826065983217.post-73157579629154234672009-06-23T19:14:00.002+02:002009-06-23T23:56:00.103+02:00RFC: Extensible, typed scanf- and printf-like functions for Haskell<p>
I recently found myself inspired (and simultaneously frustrated as it usually happens), and I felt there was something truly missing from the collection of available code for Haskell. So, I sought to do something about it. Now, I would like some feedback on that work. But first, the story...
</p>
<p>
The inspiration came from none other than <a href="http://okmij.org/ftp/">Oleg Kiselyov</a>. Not too long ago, he sent out an email responding to some comments about a printf with Template Haskell. His <a href="http://article.gmane.org/gmane.comp.lang.haskell.general/17251">safe and generic printf with C-like format string</a> led me to think it would be nice if we had a safe and generic <a href="http://en.wikipedia.org/wiki/Printf">printf</a> and <a href="http://en.wikipedia.org/wiki/Scanf">scanf</a> library. So I thought I could do that. I could take Oleg's code and polish it up and publish it.
</p>
<p>
I did take his code and play around with it for a while. In fact, what I did sits at its current state in <a href="http://github.com/spl/splonderzoek/blob/1d1f93b25756ee6dee167bc5ee58a467cdfea06b/Format.hs">Format.hs</a> and <a href="http://github.com/spl/splonderzoek/blob/1d1f93b25756ee6dee167bc5ee58a467cdfea06b/FormatTest.hs">FormatTest.hs</a>. It was fun to play around in that area. I created a bunch of different descriptors for a wide variety of formats. And being the researcher of generic programming that I am, I wanted to make it generic. I wanted users to be able to add their own formats. As I got to thinking about it, I realized that this string format approach doesn't scale. There are only so many characters in the alphabet for one thing. And if I wanted to add alignment and spacing for some descriptors, then I need to create parsers for those. This is too much work for users to do for an extension, too.
</p>
<p>
The frustration then came. How do I improve on this? How do I make it more extensible? So I researched. With Google, of course. Eventually, I came upon Ralf Hinze's function pearl on <a href="http://www.citeulike.org/user/spl/article/4903229">"Formatting: a class act."</a> That looked good. It's a type-indexed function that provides a safe way to extend for new types using a multiparameter type class with functional dependencies.
</p>
<p>
More playing with code ensued. I tried the approach using associated type synonyms because I like how they look (superficial, I suppose). Everything worked well enough, but occasionally I would run into a problem and have trouble debugging it. I eventually came to realize that a lot of those problems were due to the lack of visibility in the types. The type family approach hid the types behind unresolved synonyms. Since I couldn't see the final type, I was having trouble figuring out what I should do with the result. I learned that changing my class to use a functional dependency allowed me to see the resolved type. This helped me quite a bit. I still like how associated type synonym looked, but I gained a new appreciation for functional dependencies.
</p>
<p>
After working on <code>showf</code>, the printf-like function, for a while, I tried my had at a scanf-like function. At first, I tried to make it too much like <code>showf</code> without success. I wanted a variable-sized result for <code>readf</code> in the same way that <code>showf</code> had a variable number of arguments. In fact, that might still be possible. But for now, the input format descriptor directly determines the output's structure.
</p>
<p>
So, in the end, I came out with <a href="http://github.com/spl/xformat/tree/master">xformat</a>. It has one module for <a href="http://github.com/spl/xformat/blob/816253521592a6e23bae89aedee11b52a9e59d46/src/Text/XFormat/Show.hs">showf</a> and one for <a href="http://github.com/spl/xformat/blob/816253521592a6e23bae89aedee11b52a9e59d46/src/Text/XFormat/Read.hs">readf</a>. It also has quite a few format descriptors. To give you an idea of what you can do, let me share a few examples.
</p>
<p>
Using the Text.XFormat.Show module:
<pre><code>
module S where
import Text.XFormat.Show
s1 :: Int -> String
s1 = showf Int
-- Variable number of arguments mixed with constants
s2 :: String
s2 = showf ("Hello, " % String % Char) "World" '!'
-- Use tuples to group a format descriptor
s3 = showf ("The Answer is ", Int, ".") 42
-- Align right in a column width of 37.
s4 = showf (Align R 37 "Hello darkness, my old friend.")
</code></pre>
</p>
<p>
Using the Text.XFormat.Read module:
<pre><code>
{-# LANGUAGE TypeOperators #-}
module R where
import Text.XFormat.Read
r1 :: String -> Maybe Int
r1 = readf Int
-- Variable size format and output
r2 :: Maybe (String :%: (String :%: Char))
r2 = readf ("Hello, " % String % Char) "Hello, World!"
-- Use tuples to group a format descriptor
r3 = let Just (_, ans, _) = readf ("The Answer is ", Int, ".") "The Answer is 42."
in ans
-- Extract the value in parentheses
r4 = readf (Wrap '(' Int ')') "(37)"
</code></pre>
</p>
<p>
Now, finally to my request. I'd like some feedback on <a href="http://github.com/spl/xformat/tree/master">this library</a>. Is the basic design reasonable? Can it be improved either aesthetically, performance-wise, or usability-wise? Any other comments on it? I'd like to go through some community improvement before committing it to Hackage.
</p>
<p>
I greatly appreciate any thoughts you might have.
</p>
<p>
<strong>Update:</strong> Soon after I posted this, I realized it didn't make much sense to ask for feedback when it's rather difficult to get access to the library. Thus, you may now find the package on the <a href="http://hackage.haskell.org/package/xformat">xformat Hackage page</a>.
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com6Padualaan 14, 3584 Utrecht, The Netherlands52.0848524 5.17044152.081555900000005 5.1631455000000006 52.0881489 5.1777365tag:blogger.com,1999:blog-8130326826065983217.post-44191720248335836022009-04-12T20:49:00.001+02:002009-04-21T15:52:23.872+02:00Latest on the incremental fold and attributes<p>
Inspired by <a href="http://comonad.com/reader/">Edward Kmett</a>'s <a href="http://comonad.com/reader/2009/incremental-folds/">adaptation of my incremental fold</a>, I have developed new versions of the <a href="http://splonderzoek.blogspot.com/2009/02/incremental-fold-design-pattern.html">incremental fold</a> and the <a href="http://splonderzoek.blogspot.com/2009/03/incremental-attributes.html">incremental attributes</a>. These use a style very much based on Edward's fixed-point representation (i.e. the <code>Mu</code> datatype). Normally, I would discuss the code in more depth, but my available time for this post is limited. So, I will just introduce the code and point to it for a more in-depth perusal if you so desire.
</p>
<h4>Fixed Point for an Incremental Fold</h4>
<p>
First, we have the <a href="http://github.com/spl/splonderzoek/blob/98e9d4dc19f2c2b4530366eff9be10f648c19447/IncrementalFixFold.hs">fixed-point incremental fold</a>. It is similar to Edward's, but rather than using a different fixed-point datatype (his <code>(:>)</code>), I use a datatype embedded in the typical <code>Mu</code>.
</p>
<pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>newtype Mu f = In { </span
><span class="Function FunctionDefinition"
>out ::</span
><span class="Normal NormalText"
> f (Mu f) }</span
><br
/><br
/><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Ext z f r = Ext { </span
><span class="Function FunctionDefinition"
>tag ::</span
><span class="Normal NormalText"
> z, </span
><span class="Function FunctionDefinition"
>fun ::</span
><span class="Normal NormalText"
> f r }</span
><br
/><br
/><span class="Keyword"
>type</span
><span class="Normal NormalText"
> EMu z f = Mu (Ext z f)</span
><br
/></code
></pre
>
<p>
Also, I have renamed <code>remember</code> and <code>forget</code> to <code>ein</code> and <code>eout</code>, because they are simply the "in" and "out" for this extended fixed-point representation.
</p>
<pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>ein' ::</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Functor</span
><span class="Normal NormalText"
> f) => (f z -> z) -> f (EMu z f) -> EMu z f</span
><br
/><span class="Normal NormalText"
>ein' phiz x = emu (phiz (</span
><span class="Function"
>fmap</span
><span class="Normal NormalText"
> result x)) x</span
><br
/><br
/><span class="Function FunctionDefinition"
>ein ::</span
><span class="Normal NormalText"
> (Algebra f z) => f (EMu z f) -> EMu z f</span
><br
/><span class="Normal NormalText"
>ein = ein' alg</span
><br
/><br
/><span class="Function FunctionDefinition"
>eout ::</span
><span class="Normal NormalText"
> EMu z f -> f (EMu z f)</span
><br
/><span class="Normal NormalText"
>eout = fun . out</span
><br
/></code
></pre
>
<p>
As a learning experience, I implemented the catamorphism, anamorphism, hylomorphism, paramorphism, and zygomorphism for <code>EMu</code>. See the <a href="http://github.com/spl/splonderzoek/blob/98e9d4dc19f2c2b4530366eff9be10f648c19447/IncrementalFixFold.hs">code</a> for details.
</p>
<p>
To experiment with incremental folds, I implemented functions for three fixed-point datatypes, <code>Nat</code>, <code>Tree</code>, and <code>List</code>. Since we've been talking about trees, here's what the datatype looks like:
</p>
<pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> TreeF a r = Bin a r r | Tip </span
><span class="Keyword"
>deriving</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Eq</span
><span class="Normal NormalText"
>, </span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
>, </span
><span class="Keyword Class"
>Show</span
><span class="Normal NormalText"
>, </span
><span class="Keyword Class"
>Read</span
><span class="Normal NormalText"
>)</span
><br
/><span class="Normal NormalText"
> </span
><br
/><span class="Keyword"
>instance</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Functor</span
><span class="Normal NormalText"
> (TreeF a) </span
><span class="Keyword"
>where</span
><span class="Normal NormalText"
> ...</span
><br
/><span class="Normal NormalText"
> </span
><br
/><span class="Keyword"
>type</span
><span class="Normal NormalText"
> Tree a = Mu (TreeF a)</span
><br
/><span class="Keyword"
>type</span
><span class="Normal NormalText"
> ETree z a = EMu z (TreeF a)</span
><br
/></code
></pre
>
<p>
Along with each datatype, there are functions that would potentially be part of a library. Though not necessary, I implemented some of these as catamorphisms, anamorphisms, and paramorphisms. It's actually quite nice to see these in use, especially when you can compare it to the implementation with implicit recursion. For an example, compare <code>insert</code> and <code>insert_rec</code> for trees.
</p>
<p>
Any of these datatypes and functions now support an incremental fold for a given algebra of type <code>f a -> a</code> where <code>f</code> is the functor of the datatype. I have included a few example algebra implementations.
</p>
<p>
Again, you can find the code for incremental fold on a fixed point <a href="http://github.com/spl/splonderzoek/blob/98e9d4dc19f2c2b4530366eff9be10f648c19447/IncrementalFixFold.hs">here</a>.
</p>
<h4>Fixed Point for Incremental Attributes</h4>
<p>
As I mentioned before, the fold is a specific instance of <a href="http://splonderzoek.blogspot.com/2009/03/incremental-attributes.html">incremental attributes</a>. Starting with the code for the incremental fixed-point fold, I put together a generalized version of <a href="http://github.com/spl/splonderzoek/blob/d9a9b422fe74d20b4c072a9991287b06cab2aa0a/IncrementalFixAttributes.hs">incremental attributes for fixed-point datatypes</a>. Much of the code is the same, so let me highlight the differences from the above.
</p>
<p>
We first take <code>Ext</code> and extend it further with an inherited attribute. Recall that the incremental catamorphism is strictly synthesized (from the children to the parent), and to generalize, we need to pass attributes from the parent to the children. This gives us <code>Att</code>, and the adaptation of <code>EMu</code> is now <code>AMu</code>
</p>
<pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Att i s f r = Att { </span
><span class="Function FunctionDefinition"
>itag ::</span
><span class="Normal NormalText"
> i , </span
><span class="Function FunctionDefinition"
>stag ::</span
><span class="Normal NormalText"
> s , </span
><span class="Function FunctionDefinition"
>fun ::</span
><span class="Normal NormalText"
> f r }</span
><br
/><span class="Normal NormalText"
> </span
><br
/><span class="Keyword"
>type</span
><span class="Normal NormalText"
> AMu i s f = Mu (Att i s f)</span
><br
/></code
></pre
>
<p>
This causes our "in" and "out" isomorphism to be quite different.
</p>
<pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>ain' ::</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Functor</span
><span class="Normal NormalText"
> f, Zippable f) => (i -> f s -> (s, </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> (f i))) -> i -> f (AMu i s f) -> AMu i s f</span
><br
/><span class="Normal NormalText"
>ain' rho i x = In (Att i s y)</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><span class="Normal NormalText"
> fs = </span
><span class="Function"
>fmap</span
><span class="Normal NormalText"
> sresult x</span
><br
/><span class="Normal NormalText"
> (s, fi) = rho i fs</span
><br
/><span class="Normal NormalText"
> push j = ain' rho j . fun . out</span
><br
/><span class="Normal NormalText"
> y = </span
><span class="Keyword"
>case</span
><span class="Normal NormalText"
> fi </span
><span class="Keyword"
>of</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword DataConstructor"
>Nothing</span
><span class="Normal NormalText"
> -> x</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword DataConstructor"
>Just</span
><span class="Normal NormalText"
> fj -> fromMaybe x (</span
><span class="Function"
>zipWith</span
><span class="Normal NormalText"
> push fj x)</span
><br
/><span class="Normal NormalText"
> </span
><br
/><span class="Function FunctionDefinition"
>ain ::</span
><span class="Normal NormalText"
> (AAlgebra f i s) => i -> f (AMu i s f) -> AMu i s f</span
><br
/><span class="Normal NormalText"
>ain = ain' aalg</span
><br
/><span class="Normal NormalText"
> </span
><br
/><span class="Function FunctionDefinition"
>aout ::</span
><span class="Normal NormalText"
> AMu i s f -> (f (AMu i s f), i)</span
><br
/><span class="Normal NormalText"
>aout = fork fun itag . out</span
><br
/></code
></pre
>
<p>
Looking at the above, we need a <code>zipWith</code> for each datatype, and we have a different algebra as well. The type of the algebra is really the key to understanding what an implementation of incremental attributes does.
</p>
<pre class="sourceCode haskell"
><code
><span class="Keyword"
>class</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Functor</span
><span class="Normal NormalText"
> f, Zippable f) => AAlgebra f i s </span
><span class="Keyword"
>where</span
><br
/><span class="Normal NormalText"
> </span
><span class="Function FunctionDefinition"
>aalg ::</span
><span class="Normal NormalText"
> i -> f s -> (s, </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> (f i))</span
><br
/></code
></pre
>
<p>
It says that, given an inherited attribute (from the parent) and a functor of synthesized attributes (from the children), an algebra produces a pair of a synthesized attribute (for the parent) and a functor of inherited attributes (for the children). The <code>Maybe</code> is just an added convenience to allow synthesizing-only algebras the pleasure of not having to produce the inheritable functor.
</p>
<p>
I have provided much of the same set of examples in <a href="http://github.com/spl/splonderzoek/blob/d9a9b422fe74d20b4c072a9991287b06cab2aa0a/IncrementalFixAttributes.hs">this module</a> as in the fold one. Noticeably different, however, is the addition of the float differencing implementation and a counter that ranks in-order nodes. Both were described in the <a href="http://splonderzoek.blogspot.com/2009/03/incremental-attributes.html">post on incremental attributes</a>. It's also worth pointing out that several of the morphisms and algebras had to change due to the inherited attribute that must be provided as input.
</p>
<p>
Well, that's the current story on incremental attributes. I'm greatly appreciative to Edward Kmett for his <a href="http://comonad.com/reader/2009/incremental-folds/">article</a>. I'm also currently working on the generic thoughts behind the idea. Perhaps there will be more to come...
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com2Padualaan 14, 3584 Utrecht, The Netherlands52.0848524 5.17044152.081555900000005 5.1631455000000006 52.0881489 5.1777365tag:blogger.com,1999:blog-8130326826065983217.post-68216895502465297282009-04-12T19:14:00.000+02:002009-04-12T19:14:57.556+02:00Haskell mode for Vim on a Mac<p>
I set up <a href="http://community.haskell.org/~claus/">Claus Reinke</a>'s <a href="http://projects.haskell.org/haskellmode-vim/">Haskell mode for Vim</a> today. Based on the documentation and code, it doesn't appear to have gotten much exposure to a Mac. And I didn't find anybody else describing what to do. So, this is my little contribution towards helping those Mac+Vim users that want to use it.
</p>
<p>
As described, it's simplest to set up using the <a href="http://vimdoc.sourceforge.net/htmldoc/pi_vimball.html">vimball</a>. Simply download the latest vba file linked from the <a href="http://projects.haskell.org/haskellmode-vim/">project page</a>, and open it in Vim:
</p>
<pre><code>
wget http://projects.haskell.org/haskellmode-vim/vimfiles/haskellmode-20090410.vba
vim haskellmode-20090410.vba
</code></pre>
<p>
Once in Vim, <a href="http://vimdoc.sourceforge.net/htmldoc/repeat.html#:source">source</a> the file:
</p>
<pre><code>
:source %
</code></pre>
<p>
Then, quit and open up your <a href="http://vimdoc.sourceforge.net/htmldoc/starting.html#VIMINIT"><code>$VIMINIT</code> file</a> (usually <code>.vimrc</code> or <code>_vimrc</code>). Follow the directions on the <a href="http://projects.haskell.org/haskellmode-vim/">project page</a>, but use these lines for setting up the Haddock browser variable.
</p>
<pre><code>
" Configure browser for haskell_doc.vim
let g:haddock_browser = "open"
let g:haddock_browser_callformat = "%s %s"
</code></pre>
<p>
The Mac OS X <a href="http://developer.apple.com/documentation/Darwin/Reference/Manpages/man1/open.1.html"><code>open</code></a> command uses the <a href="http://www.wikihow.com/Change-the-Default-Web-Browser-in-Mac-OS-X">default browser</a> to open URLs, and the internals of the Vim script use URLs for Haddock pages and such. So, the above settings will tell Haskell mode to open any URL in the default browser.
</p>
<p>
If you decide you don't want to use your default browser, you can then, for example, use <a href="http://www.mozilla.com/firefox/">Firefox</a> instead of Safari.
</p>
<pre><code>
let g:haddock_browser = "open"
let g:haddock_browser_callformat = "%s -a Firefox %s"
</code></pre>
<p>
Note that we can't change <code>g:haddock_browser</code> here. The script is using <a href="http://vimdoc.sourceforge.net/htmldoc/eval.html#executable()"><code>executable()</code></a> to verify <code>g:haddock_browser</code>, so we can't add flags to it.
</p>
<p>
And that's it! Now, you can quit and open up a Haskell file to play with it. Hopefully, your GHC build has the documentation for the libraries and the user guide, so you can take advantage of the undocumented <code>:Doc</code> command. Unfortunately, I'm using the MacPorts GHC, and it doesn't build the user guide documentation.
</p>
<p>
If you're not sure whether you should set up Haskell mode for Vim, check out <a href="http://projects.haskell.org/haskellmode-vim/screencasts.html">these nice screencasts</a> that demonstrate its power (and the <code>:Doc</code> command).
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com4Padualaan 14, 3584 Utrecht, The Netherlands52.0848524 5.17044152.081555900000005 5.1631455000000006 52.0881489 5.1777365tag:blogger.com,1999:blog-8130326826065983217.post-49669562233087750952009-03-31T22:52:00.001+02:002009-04-12T20:45:33.695+02:00Incremental attributes<p>
I previously wrote about a design pattern I called an <a
href="http://splonderzoek.blogspot.com/2009/02/incremental-fold-design-pattern.html">incremental fold (or catamorphism)</a>. I described it as a design pattern, because, as written, it cannot be factored into code. That is, it is a pattern for designing part of a program.
</p>
<p>
The pattern I presented is a useful way to implement functions that can be expressed as <a href="http://knol.google.com/k/edward-kmett/catamorphisms/3qi7x2qrdushx/2">catamorphisms</a> such that the result is incrementally computed for each operation on a value of a datatype. Unlike a fold defined directly as a function, which traverse an entire value, the incremental fold only traverses parts that are updated. For some values, this may provide a performance benefit.
</p>
<p>
This post shows how we can adapt the above idea to a more general concept that I'm calling incremental attributes. It's more general in that incremental attributes can express the incremental fold as well as other flows of incremental computation.
</p>
<h4>Review of the incremental fold</h4>
<p>
First, let's review the implementation of the incremental fold.
</p>
<p>
[<em>Note: This is <strong>not</strong> a literate Haskell article, because there's too much duplicated code required; however, all <a href="http://github.com/spl/splonderzoek/tree/master">source files</a> are available.</em>]
</p>
<pre class="sourceCode haskell"
><code
><span class="Keyword"
>module</span
><span class="Normal NormalText"
> <a href="http://github.com/spl/splonderzoek/blob/9b6c144e905fa1d8493a653620a9129c1f7beefc/IncrementalAttributes1Synthesized.hs">IncrementalAttributes1Synthesized</a> </span
><span class="Keyword"
>where</span
><br
/><br
/><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Tree a s</span
><br
/><span class="Normal NormalText"
> = Tip s</span
><br
/><span class="Normal NormalText"
> | Bin a (Tree a s) (Tree a s) s</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>deriving</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Show</span
><br
/><br
/><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Alg a s</span
><br
/><span class="Normal NormalText"
> = Alg { </span
><span class="Function FunctionDefinition"
>stip ::</span
><span class="Normal NormalText"
> s, </span
><span class="Function FunctionDefinition"
>sbin ::</span
><span class="Normal NormalText"
> a -> s -> s -> s }</span
><br
/><br
/><span class="Function FunctionDefinition"
>result ::</span
><span class="Normal NormalText"
> Tree a s -> s</span
><br
/><span class="Normal NormalText"
>result (Tip s) = s</span
><br
/><span class="Normal NormalText"
>result (Bin _ _ _ s) = s</span
><br
/><br
/><span class="Function FunctionDefinition"
>tip ::</span
><span class="Normal NormalText"
> Alg a s -> Tree a s</span
><br
/><span class="Normal NormalText"
>tip alg = Tip (stip alg)</span
><br
/><br
/><span class="Function FunctionDefinition"
>bin ::</span
><span class="Normal NormalText"
> Alg a s -> a -> Tree a s -> Tree a s -> Tree a s</span
><br
/><span class="Normal NormalText"
>bin alg x lt rt = Bin x lt rt (sbin alg x (result lt) (result rt))</span
><br
/><br
/><span class="Function FunctionDefinition"
>empty ::</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
> a) => Alg a s -> Tree a s</span
><br
/><span class="Normal NormalText"
>empty = tip</span
><br
/><br
/><span class="Function FunctionDefinition"
>singleton ::</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
> a) => Alg a s -> a -> Tree a s</span
><br
/><span class="Normal NormalText"
>singleton alg x = bin alg x (tip alg) (tip alg)</span
><br
/><br
/><span class="Function FunctionDefinition"
>insert ::</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
> a) => Alg a s -> a -> Tree a s -> Tree a s</span
><br
/><span class="Normal NormalText"
>insert alg x t =</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>case</span
><span class="Normal NormalText"
> t </span
><span class="Keyword"
>of</span
><br
/><span class="Normal NormalText"
> Tip _ -></span
><br
/><span class="Normal NormalText"
> singleton alg x</span
><br
/><span class="Normal NormalText"
> Bin y lt rt _ -></span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>case</span
><span class="Normal NormalText"
> </span
><span class="Function"
>compare</span
><span class="Normal NormalText"
> x y </span
><span class="Keyword"
>of</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword DataConstructor"
>LT</span
><span class="Normal NormalText"
> -> bin alg y (insert alg x lt) rt</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword DataConstructor"
>GT</span
><span class="Normal NormalText"
> -> bin alg y lt (insert alg x rt)</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword DataConstructor"
>EQ</span
><span class="Normal NormalText"
> -> bin alg x lt rt</span
><br
/><br
/><span class="Function FunctionDefinition"
>fromList ::</span
><span class="Normal NormalText"
> (</span
><span class="Keyword Class"
>Ord</span
><span class="Normal NormalText"
> a) => Alg a s -> [a] -> Tree a s</span
><br
/><span class="Normal NormalText"
>fromList alg = </span
><span class="Function"
>foldr</span
><span class="Normal NormalText"
> (insert alg) (empty alg)</span
><br
/><br
/><span class="Function FunctionDefinition"
>heightAlg ::</span
><span class="Normal NormalText"
> Alg a </span
><span class="DataType TypeConstructor"
>Integer</span
><br
/><span class="Normal NormalText"
>heightAlg = Alg </span
><span class="DecVal Decimal"
>0</span
><span class="Normal NormalText"
> (\_ x y -> </span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
> + </span
><span class="Function"
>max</span
><span class="Normal NormalText"
> x y)</span
><br
/><br
/><span class="Normal NormalText"
>t1 = fromList heightAlg </span
><span class="String"
>"azbycx"</span
><br
/></code
></pre>
<p>
This will be the starting point for our discussion. We have a basic binary tree with an algebra type that gives the fold functions, <code>stip</code> and <code>sbin</code>. The application of the algebra is blended into the utility functions just as it was with the <a
href="http://splonderzoek.blogspot.com/2009/02/incremental-fold-design-pattern.html">incremental fold</a>. I have chosen to keep the representation simple, so the algebra is passed around as an argument to the functions. This could, of course, be done with type classes. Lastly, we have an example algebra that determines the height of a tree. To get the height of the example <code>t1</code>, simply type <code>result t1</code> after loading this file into GHCi.
</p>
<h4>Incrementally inherited attributes</h4>
<p>
Suppose that, instead of height, we wanted to incrementally compute the depth of every node. Thus, we would attach a value to each node that stored its distance from the root. We can't do that with the above implementation, because attributes are only fed "upwards" or from the leaves to the root. We have no way of passing information downwards. The solution is to use inherited attributes.
</p>
<p>
Before presenting the <a href="http://github.com/spl/splonderzoek/blob/9b6c144e905fa1d8493a653620a9129c1f7beefc/IncrementalAttributes2Inherited.hs">code</a>, here is a little side note. You may notice the use of the words <em>synthesized</em> and <em>inherited</em> here. The terminology comes from the study of <a href="http://en.wikipedia.org/wiki/Attribute_grammar">attribute grammars</a>, extending context-free grammars to support semantic operations. <a href="http://www.cse.chalmers.se/~wouter/">Wouter Swierstra</a> wrote a great <a href="http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter">tutorial on attribute grammars in Haskell</a> for <a href="http://www.haskell.org/haskellwiki/The_Monad.Reader">The Monad Reader</a> in 2005. In fact, I use an example from there at the end of this article. You can think of <em>synthesized</em> as "produced by the children for the parent" and <em>inherited</em> as "passed down from the parent to the children."
</p>
<p>
As you can now imagine, inherited attributes will allow us to bring information to the leaves. Many of the <a href="http://github.com/spl/splonderzoek/blob/9b6c144e905fa1d8493a653620a9129c1f7beefc/IncrementalAttributes2Inherited.hs">changes to the code</a> are trivial, so we ignore them. The relevant changes are the following:
</p>
<pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Alg a i</span
><br
/><span class="Normal NormalText"
> = Alg { </span
><span class="Function FunctionDefinition"
>itip ::</span
><span class="Normal NormalText"
> i -> i, </span
><span class="Function FunctionDefinition"
>ibin ::</span
><span class="Normal NormalText"
> a -> i -> i }</span
><br
/><br
/><span class="Function FunctionDefinition"
>tip ::</span
><span class="Normal NormalText"
> Alg a i -> i -> Tree a i</span
><br
/><span class="Normal NormalText"
>tip alg i = Tip (itip alg i)</span
><br
/><br
/><span class="Function FunctionDefinition"
>bin ::</span
><span class="Normal NormalText"
> Alg a i -> i -> a -> Tree a i -> Tree a i -> Tree a i</span
><br
/><span class="Normal NormalText"
>bin alg i x lt rt = Bin x (update i lt) (update i rt) i</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><span class="Normal NormalText"
> update i' t =</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>case</span
><span class="Normal NormalText"
> t </span
><span class="Keyword"
>of</span
><br
/><span class="Normal NormalText"
> Tip _ -></span
><br
/><span class="Normal NormalText"
> tip alg i'</span
><br
/><span class="Normal NormalText"
> Bin x lt rt _ -></span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>let</span
><span class="Normal NormalText"
> s = ibin alg x i' </span
><span class="Keyword"
>in</span
><br
/><span class="Normal NormalText"
> Bin x (update s lt) (update s lt) s</span
><br
/></code
></pre
>
<p>
The datatype <code>Alg</code> (that I'm still calling the algebra, though that may not be proper use of the category theoretical term) now has functions that take an inherited attribute from a parent and create a new inherited attribute to be stored with the node and passed on to its children. The change to <code>bin</code> is the more complicated of the changes, because once a <code>Bin</code> constructor is constructed, all of its child nodes must be updated with new inherited values.
</p>
<p>
To implement an algebra for depth, we do the following:
</p>
<pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>depthAlg ::</span
><span class="Normal NormalText"
> Alg a </span
><span class="DataType TypeConstructor"
>Int</span
><br
/><span class="Normal NormalText"
>depthAlg = Alg (+</span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
>) (</span
><span class="Function"
>const</span
><span class="Normal NormalText"
> (+</span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
>))</span
><br
/><br
/><span class="Normal NormalText"
>t1 = fromList depthAlg </span
><span class="DecVal Decimal"
>0</span
><span class="Normal NormalText"
> </span
><span class="String"
>"azbycx"</span
><br
/></code
></pre
>
<p>
Load the <a href="http://github.com/spl/splonderzoek/blob/9b6c144e905fa1d8493a653620a9129c1f7beefc/IncrementalAttributes2Inherited.hs">code</a> and check the result to see for yourself what it looks like.
</p>
<h4>One is not enough</h4>
<p>
Now that we have use cases for synthesized and inherited incremental attributes, we're going to want both. Fortunately, that's not too difficult. The new datatypes are simply a product of the two previous:
</p>
<pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Tree a i s</span
><br
/><span class="Normal NormalText"
> = Tip i s</span
><br
/><span class="Normal NormalText"
> | Bin a (Tree a i s) (Tree a i s) i s</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>deriving</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Show</span
><br
/><br
/><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Alg a i s</span
><br
/><span class="Normal NormalText"
> = Alg { </span
><span class="Function FunctionDefinition"
>itip ::</span
><span class="Normal NormalText"
> i -> i, </span
><span class="Function FunctionDefinition"
>ibin ::</span
><span class="Normal NormalText"
> a -> i -> i,</span
><br
/><span class="Normal NormalText"
> </span
><span class="Function FunctionDefinition"
>stip ::</span
><span class="Normal NormalText"
> s, </span
><span class="Function FunctionDefinition"
>sbin ::</span
><span class="Normal NormalText"
> a -> s -> s -> s }</span
><br
/></code
></pre
>
<p>
You can now see why I was using <code>s</code> and <code>i</code> to distinguish the types of the attributes. Again, most of the <a href="http://github.com/spl/splonderzoek/blob/9b6c144e905fa1d8493a653620a9129c1f7beefc/IncrementalAttributes3SynthesizedAndInherited.hs">code</a> modifications are trivial, and the <code>bin</code> function needs special attention.
</p>
<pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>bin ::</span
><span class="Normal NormalText"
> Alg a i s -> i -> a -> Tree a i s -> Tree a i s -> Tree a i s</span
><br
/><span class="Normal NormalText"
>bin alg i x lt rt =</span
><br
/><span class="Normal NormalText"
> Bin x (update i lt) (update i rt) i (sbin alg x (sresult lt) (sresult rt))</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><span class="Normal NormalText"
> update i' t =</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>case</span
><span class="Normal NormalText"
> t </span
><span class="Keyword"
>of</span
><br
/><span class="Normal NormalText"
> Tip _ _ -></span
><br
/><span class="Normal NormalText"
> tip alg i'</span
><br
/><span class="Normal NormalText"
> Bin y ylt yrt _ s -></span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>let</span
><span class="Normal NormalText"
> j = ibin alg y i' </span
><span class="Keyword"
>in</span
><br
/><span class="Normal NormalText"
> Bin y (update j ylt) (update j yrt) j s</span
><br
/></code
></pre
>
<p>
Defining an algebra for both depth and height is no more difficult than defining each alone.
</p>
<pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>depthAndHeightAlg ::</span
><span class="Normal NormalText"
> Alg a </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Int</span
><br
/><span class="Normal NormalText"
>depthAndHeightAlg = Alg (+</span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
>) (</span
><span class="Function"
>const</span
><span class="Normal NormalText"
> (+</span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
>)) </span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
> (\_ x y -> </span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
> + </span
><span class="Function"
>max</span
><span class="Normal NormalText"
> x y)</span
><br
/></code
></pre
>
<h4>Feedback</h4>
<p>
You probably know where this is going by now. There's that famous saying, "<a href="http://vids.myspace.com/index.cfm?fuseaction=vids.individual&videoID=854575885">what goes down must come up</a>." We want more than just two separate directions of information flow. We want to utilize the information flowing toward the leaves to help determine that which flows up to the root or vice versa. A simple example of this is a counter that annotates each node with its rank in an in-order <a href="http://en.wikipedia.org/wiki/Tree_traversal">traversal</a>. This can't be done with just synthesized or inherited attributes, because it depends on a combination of input from the parent, children, and siblings for each node.
</p>
<p>
The <a href="http://github.com/spl/splonderzoek/blob/9b6c144e905fa1d8493a653620a9129c1f7beefc/IncrementalAttributes4Feedback.hs">code</a> is similar to the previous implementation, but the differences in <code>Alg</code> are important.
</p>
<pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Alg a i s</span
><br
/><span class="Normal NormalText"
> = Alg { </span
><span class="Function FunctionDefinition"
>ftip ::</span
><span class="Normal NormalText"
> i -> s, </span
><span class="Function FunctionDefinition"
>fbin ::</span
><span class="Normal NormalText"
> a -> i -> s -> s -> (i, i, s) }</span
><br
/></code
></pre
>
<p>
Each node now has a single <code>i</code>nherited attribute, because it has a single parent. We use the <code>s</code>ynthesized attributes to store a local result, so each constructor only has one as an output. For the <code>Bin</code> constructor, we have a pair of incoming synthesized values and a pair of outgoing inherited values. The left component in each pair is associated with the left child, and the right with the right child. This allows us to have information flow up from the synthesized attribute of the left child and down to the inherited attribute of the right or in the opposite direction.
</p>
<p>
The <code>bin</code> is again tricky to write correctly.
</p>
<pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>bin ::</span
><span class="Normal NormalText"
> Alg a i s -> i -> a -> Tree a i s -> Tree a i s -> Tree a i s</span
><br
/><span class="Normal NormalText"
>bin alg i x lt rt = update i (Bin x lt rt </span
><span class="Function"
>undefined</span
><span class="Normal NormalText"
> </span
><span class="Function"
>undefined</span
><span class="Normal NormalText"
>)</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><span class="Normal NormalText"
> update j t =</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>case</span
><span class="Normal NormalText"
> t </span
><span class="Keyword"
>of</span
><br
/><span class="Normal NormalText"
> Tip _ _ -></span
><br
/><span class="Normal NormalText"
> tip alg j</span
><br
/><span class="Normal NormalText"
> Bin y ylt yrt _ _ -></span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>let</span
><span class="Normal NormalText"
> (li, ri, s) = fbin alg y j (sresult zlt) (sresult zrt)</span
><br
/><span class="Normal NormalText"
> zlt = update li ylt</span
><br
/><span class="Normal NormalText"
> zrt = update ri yrt</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>in</span
><span class="Normal NormalText"
> Bin y zlt zrt j s</span
><br
/></code
></pre
>
<p>
Notice the circular programming here. The definition and uses of, for example, <code>li</code> and <code>zlt</code> show that we could easily loop infinitely. This depends on how the specific algebra functions are implemented. Here is the "counter example":
</p>
<pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>newtype CounterI = CI { </span
><span class="Function FunctionDefinition"
>cntI ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
> } </span
><span class="Keyword"
>deriving</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Show</span
><br
/><span class="Keyword"
>data</span
><span class="Normal NormalText"
> CounterS = CS { </span
><span class="Function FunctionDefinition"
>size ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
>, </span
><span class="Function FunctionDefinition"
>cntS ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
> } </span
><span class="Keyword"
>deriving</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Show</span
><br
/><br
/><span class="Function FunctionDefinition"
>counterAlg ::</span
><span class="Normal NormalText"
> Alg a CounterI CounterS</span
><br
/><span class="Normal NormalText"
>counterAlg = Alg ft fb</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><br
/><span class="Normal NormalText"
> </span
><span class="Function FunctionDefinition"
>ft ::</span
><span class="Normal NormalText"
> CounterI -> CounterS</span
><br
/><span class="Normal NormalText"
> ft i = CS { size = </span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
>, cntS = cntI i }</span
><br
/><br
/><span class="Normal NormalText"
> </span
><span class="Function FunctionDefinition"
>fb ::</span
><span class="Normal NormalText"
> a -> CounterI -> CounterS -> CounterS -> (CounterI, CounterI, CounterS)</span
><br
/><span class="Normal NormalText"
> fb _ i ls rs =</span
><br
/><span class="Normal NormalText"
> ( i </span
><span class="Comment"
>-- left</span
><br
/><span class="Normal NormalText"
> , CI { cntI = </span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
> + cntI i + size ls } </span
><span class="Comment"
>-- right</span
><br
/><span class="Normal NormalText"
> , CS { size = </span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
> + size ls + size rs</span
><br
/><span class="Normal NormalText"
> , cntS = cntI i + size ls }</span
><br
/><span class="Normal NormalText"
> )</span
><br
/><br
/><span class="Normal NormalText"
>t1 = fromList counterAlg (CI { cntI = </span
><span class="DecVal Decimal"
>0</span
><span class="Normal NormalText"
> }) </span
><span class="String"
>"azbycx"</span
><br
/></code
></pre
>
<p>
I've relied heavily on record syntax to document the flow of information. Notice in <code>fb</code> how the <code>i</code> is directly inherited by the left child and how the right child inherits the new count that depends on the size of the left subtree and the inherited count of its parent. As shown in this example, the dependency flow must be unidirectional for one desired result. But there's no reason we can't go up, down, and then up again (for example).
</p>
<h4>Revisiting the diff problem.</h4>
<p>
As I mentioned, Wouter wrote a good <a href="http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter">introduction to attribute grammars in Haskell</a> (which I highly recommend that you read). He focuses on the use of the <a href="http://www.cs.uu.nl/wiki/HUT/AttributeGrammarSystem">UUAG system</a> to generate code for solving problems that are harder to solve with traditional functional programming techniques. He describes the problem as follows:
</p>
<blockquote>
Suppose we want to write a function <code>diff :: [Float] -> [Float]</code> that given a list <code>xs</code>, calculates a new list where every element <code>x</code> is replaced with the difference between <code>x</code> and the average of <code>xs</code>. Similar problems pop up in any library for performing statistical calculations.
</blockquote>
<p>
Great problem! And we can solve it using incremental attributes in Haskell instead of in UUAG's attribute grammar syntax.
</p>
<pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>newtype DiffI = DI { </span
><span class="Function FunctionDefinition"
>avg ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Float</span
><span class="Normal NormalText"
> } </span
><span class="Keyword"
>deriving</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Show</span
><br
/><span class="Keyword"
>data</span
><span class="Normal NormalText"
> DiffS = DS { </span
><span class="Function FunctionDefinition"
>sumD ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Float</span
><span class="Normal NormalText"
>, </span
><span class="Function FunctionDefinition"
>len ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Float</span
><span class="Normal NormalText"
>, </span
><span class="Function FunctionDefinition"
>res ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Float</span
><span class="Normal NormalText"
> } </span
><span class="Keyword"
>deriving</span
><span class="Normal NormalText"
> </span
><span class="Keyword Class"
>Show</span
><br
/><br
/><span class="Function FunctionDefinition"
>diffAlg ::</span
><span class="Normal NormalText"
> Alg </span
><span class="DataType TypeConstructor"
>Float</span
><span class="Normal NormalText"
> DiffI DiffS</span
><br
/><span class="Normal NormalText"
>diffAlg = Alg ft fb</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><br
/><span class="Normal NormalText"
> </span
><span class="Function FunctionDefinition"
>ft ::</span
><span class="Normal NormalText"
> DiffI -> DiffS</span
><br
/><span class="Normal NormalText"
> ft i =</span
><br
/><span class="Normal NormalText"
> DS { sumD = </span
><span class="DecVal Decimal"
>0</span
><br
/><span class="Normal NormalText"
> , len = </span
><span class="DecVal Decimal"
>0</span
><br
/><span class="Normal NormalText"
> , res = </span
><span class="DecVal Decimal"
>0</span
><br
/><span class="Normal NormalText"
> }</span
><br
/><br
/><span class="Normal NormalText"
> </span
><span class="Function FunctionDefinition"
>fb ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Float</span
><span class="Normal NormalText"
> -> DiffI -> DiffS -> DiffS -> (DiffI, DiffI, DiffS)</span
><br
/><span class="Normal NormalText"
> fb x i ls sr =</span
><br
/><span class="Normal NormalText"
> ( i</span
><br
/><span class="Normal NormalText"
> , i</span
><br
/><span class="Normal NormalText"
> , DS { sumD = x + sumD ls + sumD sr</span
><br
/><span class="Normal NormalText"
> , len = </span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
> + len ls + len sr</span
><br
/><span class="Normal NormalText"
> , res = x - avg i</span
><br
/><span class="Normal NormalText"
> }</span
><br
/><span class="Normal NormalText"
> )</span
><br
/></code
></pre
>
<p>
The <a href="http://github.com/spl/splonderzoek/blob/9b6c144e905fa1d8493a653620a9129c1f7beefc/IncrementalAttributes4Feedback.hs">implementation</a> is not too much more difficult than the <a href="http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue4/Why_Attribute_Grammars_Matter#The_attribute_grammar_solution">attribute grammar solution</a>. We don't have the clean separation of concerns, but adding another attribute only means adding another field in <code>DI</code> or <code>DS</code> depending on whether it's inherited or synthesized.
</p>
<p>
Oh, but we're not done! Where's the actual average generated? Ah right, that's fed to the root inherited attribute.
</p>
<pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>t2 = </span
><span class="Keyword"
>let</span
><span class="Normal NormalText"
> val = fromList diffAlg (DI { avg = a }) [</span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
>,</span
><span class="DecVal Decimal"
>4</span
><span class="Normal NormalText"
>,</span
><span class="Float"
>1.5</span
><span class="Normal NormalText"
>,</span
><span class="Float"
>3.5</span
><span class="Normal NormalText"
>,</span
><span class="DecVal Decimal"
>2</span
><span class="Normal NormalText"
>,</span
><span class="DecVal Decimal"
>3</span
><span class="Normal NormalText"
>,</span
><span class="Float"
>2.5</span
><span class="Normal NormalText"
>]</span
><br
/><span class="Normal NormalText"
> s = sresult val</span
><br
/><span class="Normal NormalText"
> a = sumD s / len s</span
><br
/><span class="Normal NormalText"
> </span
><span class="Keyword"
>in</span
><span class="Normal NormalText"
> val</span
><br
/></code
></pre
>
<p>
Here's another example of circular programming. Due to the way we implemented the application of the algebra, we can take advantage of lazy evaluation to ensure that the sum and length (and thus average) are incrementally computed and, as a result, the difference (<code>res</code>) is determined as needed for each node.
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com2Padualaan 14, 3584 Utrecht, The Netherlands52.0848524 5.17044152.081555900000005 5.1631455000000006 52.0881489 5.1777365tag:blogger.com,1999:blog-8130326826065983217.post-26123462770676066722009-03-06T02:10:00.001+01:002009-03-30T11:51:49.195+02:00Experiments with EMGM: Emacs org files<p
>I've been meaning to write some things about <a href="http://www.cs.uu.nl/wiki/GenericProgramming/EMGM"
>EMGM</a
> for a while, but I hadn't found one of those <a href="http://en.wiktionary.org/wiki/round_tuit"
>round tuits</a
> as of yet. Until now.</p
><p
>David Miani is working on a Haskell library for interacting with emacs <a href="http://orgmode.org/"
>org files</a
>. "For those that do not know, an org file is a structured outline style file that has nested headings, text, tables and other elements," <a href="http://thread.gmane.org/gmane.comp.lang.haskell.cafe/54031"
>says David</a
>. He has a collection of datatypes for building and manipulating these files.</p
><p
>David seeks a better way to do what he's doing. (It's a noble goal. I hope you keep doing it.) To return to his words: "While writing an OrgFile is fairly easy, reading (and accessing inner parts) of an org file is very tedious, and modifying them is horrendous." He goes on to give an example that I'll describe more below.</p
><p
>When I read the above statement, I was expecting that <a href="http://www.haskell.org/haskellwiki/Research_papers/Generics"
>generic programming</a
> could help him out. When I saw his code, I knew it was a perfect use case. That's what inspired this entry, the first use case for EMGM from <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe"
>Haskell Café</a
>.</p
><p
>First, this is a <a href="http://www.haskell.org/haskellwiki/Literate_programming"
>literate Haskell</a
> post, so we run through the usual preliminaries.</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>{-# LANGUAGE TemplateHaskell #-}</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>{-# LANGUAGE MultiParamTypeClasses #-}</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>{-# LANGUAGE FlexibleContexts #-}</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>{-# LANGUAGE FlexibleInstances #-}</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>{-# LANGUAGE OverlappingInstances #-}</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>{-# LANGUAGE UndecidableInstances #-}</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>module</span
><span class="Normal NormalText"
> Org </span
><span class="Keyword"
>where</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Text.Regex.Posix</span
><br
/></code
></pre
><p
>We import <a href="http://hackage.haskell.org/packages/archive/emgm/0.3.1/doc/html/Generics-EMGM-Derive.html"
>Generics.EMGM.Derive</a
> for the deriving portion of EMGM. This is not exported from the main body of the library, because it has a lot of symbols only needed for building a representation. We'd rather not clog up your symbol list if possible.</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Generics.EMGM.Derive</span
><br
/></code
></pre
><p
>In general, I'd recommend doing the deriving in a separate module and only export the datatype and generated type class instances. Then, in other modules, you can use EMGM functions or write your own. However, this being a demonstration, we will also import <a href="http://hackage.haskell.org/packages/archive/emgm/0.3.1/doc/html/Generics-EMGM.html"
>Generics.EMGM</a
> here to use the available functions.</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> import qualified Generics.EMGM as G</span
><br
/></code
></pre
><p
>The following collection of types are copied from <a href="http://thread.gmane.org/gmane.comp.lang.haskell.cafe/54031"
>David's post</a
>. They describe the structure of an org file.</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>type</span
><span class="Normal NormalText"
> Line = </span
><span class="DataType TypeConstructor"
>Int</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>type</span
><span class="Normal NormalText"
> Column = </span
><span class="DataType TypeConstructor"
>Int</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> FilePosition = FilePosition Line Column</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> WithPos a = WithPos {</span
><span class="Function FunctionDefinition"
> filePos ::</span
><span class="Normal NormalText"
> FilePosition,</span
><span class="Function FunctionDefinition"
> innerValue ::</span
><span class="Normal NormalText"
> a }</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> OrgTableP = OrgTableP [WithPos OrgTableRow]</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> OrgFileElementP</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> = TableP OrgTableP</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> | ParagraphP </span
><span class="DataType TypeConstructor"
>String</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> | HeadingP OrgHeadingP</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> OrgHeadingP = OrgHeadingP </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>String</span
><span class="Normal NormalText"
> [WithPos OrgFileElementP]</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> OrgFileP = OrgFileP [WithPos OrgFileElementP]</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> OrgTableRow</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> = OrgTableRow [</span
><span class="DataType TypeConstructor"
>String</span
><span class="Normal NormalText"
>]</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> | OrgTableRowSep </span
><br
/></code
></pre
><p
>In order to use EMGM, we must generate the values and instances used by the library. This is simple with one Template Haskell (TH).</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> $(deriveMany </span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> [ </span
><span class="Char"
>''</span
><span class="Normal NormalText"
>FilePosition</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> , </span
><span class="Char"
>''</span
><span class="Normal NormalText"
>WithPos</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> , </span
><span class="Char"
>''</span
><span class="Normal NormalText"
>OrgTableP</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> , </span
><span class="Char"
>''</span
><span class="Normal NormalText"
>OrgHeadingP</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> , </span
><span class="Char"
>''</span
><span class="Normal NormalText"
>OrgFileElementP</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> , </span
><span class="Char"
>''</span
><span class="Normal NormalText"
>OrgFileP</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> , </span
><span class="Char"
>''</span
><span class="Normal NormalText"
>OrgTableRow</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> ])</span
><br
/></code
></pre
><p
>Note that in this case, we had to use <a href="http://hackage.haskell.org/packages/archive/emgm/0.3.1/doc/html/Generics-EMGM-Derive.html#v%3AderiveMany"
><code
>deriveMany</code
></a
> for a list of type names. For the most part, we'd probably use <a href="http://hackage.haskell.org/packages/archive/emgm/0.3.1/doc/html/Generics-EMGM-Derive.html#v%3Aderive"
><code
>derive</code
></a
>; however, the datatypes <code
>OrgHeadingP</code
> and <code
>OrgFileElementP</code
> are mutually recursive. If we use <code
>derive</code
> for each type, then some values are generated that are naturally also muturally recursive. Apparently, TH expects all symbols to be available on a per-splice basis. This means that we can't <code
>$(derive ''OrgFileElementP)</code
> and then <code
>$(derive ''OrgHeadingP)</code
> or vice versa. We have to derive them simultaneously, so that both sets of symbols are available at the same time.</p
><p
>David gives the example of reading "the description line for the project named 'Project14'" in the following file:</p
><pre
><code
>* 2007 Projects
** Project 1
Description: 1
Tags: None
** Project 2
Tags: asdf,fdsa
Description: hello
* 2008 Projects
* 2009 Projects
** Project14
Tags: RightProject
Description: we want this
</code
></pre
><p
>He then provides some messy code to perform it. (No offense meant. Mine would've looked no better.) I'll skip the code, since I couldn't get it to compile as provided.</p
><p
>Our solution using EMGM follows:</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Function FunctionDefinition"
> projDesc ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>String</span
><span class="Normal NormalText"
> -> OrgFileP -> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>String</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> projDesc name file = </span
><span class="Keyword"
>do</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> hdg <- G.firstr (headings name file)</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> para <- firstPara hdg</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>if</span
><span class="Normal NormalText"
> para =~ </span
><span class="String"
>"Description"</span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>then</span
><span class="Normal NormalText"
> </span
><span class="Function"
>return</span
><span class="Normal NormalText"
> para </span
><span class="Keyword"
>else</span
><span class="Normal NormalText"
> </span
><span class="Keyword DataConstructor"
>Nothing</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Function FunctionDefinition"
> headings ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>String</span
><span class="Normal NormalText"
> -> OrgFileP -> [OrgHeadingP]</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> headings name = </span
><span class="Function"
>filter</span
><span class="Normal NormalText"
> check . G.collect</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> check (OrgHeadingP _ possible _) = name == possible</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><br
/><span class="Char Special"
>></span
><span class="Function FunctionDefinition"
> firstPara ::</span
><span class="Normal NormalText"
> OrgHeadingP -> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>String</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> firstPara hdg = paraStr =<< G.firstr (G.collect hdg)</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> paraStr (ParagraphP str) = </span
><span class="Keyword DataConstructor"
>Just</span
><span class="Normal NormalText"
> str</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> paraStr _ = </span
><span class="Keyword DataConstructor"
>Nothing</span
><br
/></code
></pre
><p
>Primarily, we take advantage of the functions <code
>collect</code
> and <code
>firstr</code
>. Here, <a href="http://hackage.haskell.org/packages/archive/emgm/0.3.1/doc/html/Generics-EMGM-Functions-Collect.html#v%3Acollect"
><code
>collect</code
></a
> is the key. It's type is <code
>collect :: (Rep (Collect b) a) => a -> [b]</code
>, and it returns a list of <code
>b</code
>s stored somewhere in a value of type <code
>a</code
>. This allows us to collect the <code
>OrgHeadingP</code
>s in an <code
>OrgFileP</code
> (<code
>headings</code
>) and the <code
>OrgFileElementP</code
>s in an <code
>OrgHeadingP</code
> (<code
>firstPara</code
>). Now, we don't have to build a bunch of functions that break down each of these types to get to their components.</p
><p
>Our use of <a href="http://hackage.haskell.org/packages/archive/emgm/0.3.1/doc/html/Generics-EMGM-Functions-Crush.html#v%3Afirstr"
><code
>firstr</code
></a
> is simply the same as we would use the <code
>Prelude</code
> function <code
>head</code
>, except that <code
>firstr</code
> returns a <code
>Maybe</code
>: unlike <code
>head</code
>, it's a total function.</p
><p
>David's top-level function would now become this:</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Function FunctionDefinition"
> get14 ::</span
><span class="Normal NormalText"
> OrgFileP -> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>String</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> get14 = projDesc </span
><span class="String"
>"Project14"</span
><br
/></code
></pre
><p
>Well, this was a fun experiment with generic programming. I hope to do more in the future.</p
><p
>I want to thank David for bringing up this problem in the mailing list. Not only did I get to play more with EMGM, I also released <a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/emgm-0.3.1"
>an update to the library</a
> when I discovered the issue requiring <code
>deriveMany</code
>.</p
>
<p>
<strong>Update 2008-03-30:</strong> The <a href="http://github.com/spl/splonderzoek/blob/78170d399151b5fb72f46647c3e7c8c642f0a191/EmacsOrgWithEMGM.lhs">source code for this entry</a> is now available at GitHub.
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com0tag:blogger.com,1999:blog-8130326826065983217.post-36005430666184670332009-03-02T12:24:00.004+01:002009-03-02T21:32:50.580+01:00Template Haskell 2.3 or Cabal 1.2? EMGM can't have both!<p><a href="#update1"><strong>Updates</strong> below!</a></p>
<p
>I'm about ready to give up. I would like <a href="http://www.cs.uu.nl/wiki/GenericProgramming/EMGM"
>EMGM</a
> to support both <a href="http://www.haskell.org/ghc/"
>GHC</a
> 6.8 and 6.10 to allow for more potential uses. This effectively means it should build with <a href="http://www.haskell.org/cabal/"
>Cabal</a
> version 1.2 (which is distributed with GHC 6.8) and 1.6 (distributed with GHC 6.10). I didn't think this would be a difficult problem, — shows you what little I know — but it has turned into a reasonably sized annoyance.</p
><p
>As of <a href="http://article.gmane.org/gmane.comp.lang.haskell.cafe/51646"
>version 0.2</a
>, EMGM supports generating code for type representations using <a href="http://www.haskell.org/haskellwiki/Template_Haskell"
>Template Haskell</a
> (TH). Since TH is now a dependency, I thought it would be handy to provide the representation values and instances for it. And so I do that <a href="http://hackage.haskell.org/packages/archive/emgm/0.2/doc/html/src/Generics-EMGM-Data-TH.html"
>here</a
>. If you look at the linked file, you'll notice an <code
>#ifdef</code
> surrounding <code
>$(derive ''Loc)</code
>. This is because the <code
>template-haskell</code
> package includes a new <a href="http://hackage.haskell.org/packages/archive/template-haskell/2.3.0.0/doc/html/Language-Haskell-TH.html#t%3ALoc"
><code
>Loc</code
></a
> datatype in <a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/template-haskell-2.3.0.0"
>version 2.3</a
>, and in order to support versions 2.2 (for GHC 6.8) and 2.3 (for GHC 6.10), I needed to do some funky C preprocessor (CPP) stuff.</p
><p
>Well, I followed the advice given in <a href="http://thread.gmane.org/gmane.comp.lang.haskell.cafe/47760"
>this thread</a
> started by Jason Ducek with useful responses from Duncan Coutts. The result was <a href="http://hackage.haskell.org/packages/archive/emgm/0.2/emgm.cabal"
>this emgm.cabal file</a
> with a flag for determining which version of <code
>template-haskell</code
> was available and whether or not to define the necessary macro. I later learned that this <a href="http://code.google.com/p/emgm/issues/detail?id=23"
>does't work</a
> when attempting to <a href="http://hackage.haskell.org/trac/hackage/wiki/CabalInstall"
>cabal-install</a
> GHC 6.8, because <code
>template-haskell-2.3</code
> <a href="http://thread.gmane.org/gmane.comp.lang.haskell.cafe/47760/focus=51946"
>fails to correctly specify</a
> the version of base or GHC that it requires.</p
><p
>Now, to work around this problem, Duncan <a href="http://thread.gmane.org/gmane.comp.lang.haskell.cafe/47760/focus=51977"
>described how to hook into Cabal</a
> to get the actual package dependencies and insert the CPP option into the build info. It was not too difficult to figure this out. And in fact, the code for my <code
>Setup.lhs</code
> is in the appendix of this article in case it is later useful for me or someone else.</p
><p
>Unfortunately, as soon as I had this implemented, I discovered it didn't work in GHC 6.8.3/Cabal 1.2. There's a very minor difference in Cabal that simply breaks my code, and I don't know how to work around it. The difference is in <code
>PackageIdentifier</code
>:</p
><p
><a href="http://hackage.haskell.org/packages/archive/Cabal/1.2.1/doc/html/Distribution-Package.html#t%3APackageIdentifier"
>Cabal 1.2</a
>:</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> PackageIdentifier = PackageIdentifier {</span
><span class="Function FunctionDefinition"
> pkgName ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>String</span
><span class="Normal NormalText"
>,</span
><span class="Function FunctionDefinition"
> pkgVersion ::</span
><span class="Normal NormalText"
> Version }</span
><br
/></code
></pre
><p
><a href="http://hackage.haskell.org/packages/archive/Cabal/1.6.0.1/doc/html/Distribution-Package.html#t%3APackageIdentifier"
>Cabal 1.6</a
>:</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> PackageIdentifier = PackageIdentifier {</span
><span class="Function FunctionDefinition"
> pkgName ::</span
><span class="Normal NormalText"
> PackageName,</span
><span class="Function FunctionDefinition"
> pkgVersion ::</span
><span class="Normal NormalText"
> Version }</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> newtype PackageName = PackageName </span
><span class="DataType TypeConstructor"
>String</span
><br
/></code
></pre
><p
>I need <code
>PackageIdentifier</code
> to determine which version of <code
>template-haskell</code
> is being used as a dependency. But I either use a <code
>String</code
> or a <code
>PackageName</code
> depending on which version of Cabal is used. I don't think there's a way to know which version of Cabal is used when building a <code
>Setup.lhs</code
> file.</p
><p
>As far as I can tell, my options are the following:</p
><ol
><li
>Hack more on the <code
>Setup.lhs</code
> to figure out a different way of dealing with the <code
>template-haskell</code
> issue.</li
><li
>Release for GHC 6.10 only. Note that the problem only occurs when mixing <code
>cabal-install</code
> and <code
>template-haskell</code
>. EMGM builds fine with GHC 6.8 in general.</li
><li
>Remove the TH deriving code and the CPP macro.</li
><li
>Leave things as they are and warn people about the issue. If/when <code
>template-haskell</code
> gets patched, it may fix the problem.</li
></ol
><p
>I'm probably going to go with the last option for now.</p
><h3 id="appendix"
>Appendix</h3
><p
>This is a <a href="http://www.haskell.org/haskellwiki/Literate_programming"
>literate Haskell</a
> <code
>Setup.lhs</code
> containing a build hook for passing a CPP option when a version of the <code
>template-haskell</code
> package greater than or equal to 2.3 is specified as a dependency. You might find it a useful example of using part of the Cabal library.</p
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>module</span
><span class="Normal NormalText"
> Main (main) </span
><span class="Keyword"
>where</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> import System.Cmd</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> import System.</span
><span class="Function"
>FilePath</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Data.Version</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Distribution.Simple</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Distribution.Simple.LocalBuildInfo</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Distribution.Simple.Program</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Distribution.Simple.Setup</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Distribution.Package</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> import Distribution.PackageDescription</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Function FunctionDefinition"
> main ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>IO</span
><span class="Normal NormalText"
> ()</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> main = defaultMainWithHooks hooks</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> hooks = simpleUserHooks { buildHook = buildHook' }</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- Insert CPP flag for building with template-haskell versions >= 2.3.</span
><br
/><span class="Normal NormalText"
>></span
><span class="Function FunctionDefinition"
> buildHook' ::</span
><span class="Normal NormalText"
> PackageDescription -> LocalBuildInfo -> UserHooks -> BuildFlags -> </span
><span class="DataType TypeConstructor"
>IO</span
><span class="Normal NormalText"
> ()</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> buildHook' pkg lbi hooks flags =</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> buildHook simpleUserHooks pkg (lbi { localPkgDescr = newPkgDescr }) hooks flags</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>where</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- Old local package description</span
><br
/><span class="Normal NormalText"
>> oldPkgDescr = localPkgDescr lbi</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- New local package description</span
><br
/><span class="Normal NormalText"
>> newPkgDescr =</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>case</span
><span class="Normal NormalText"
> thVersion </span
><span class="Keyword"
>of</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword DataConstructor"
>Nothing</span
><span class="Normal NormalText"
> -></span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> oldPkgDescr</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword DataConstructor"
>Just</span
><span class="Normal NormalText"
> version -></span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>if</span
><span class="Normal NormalText"
> version >= Version [</span
><span class="DecVal Decimal"
>2</span
><span class="Normal NormalText"
>,</span
><span class="DecVal Decimal"
>3</span
><span class="Normal NormalText"
>] []</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>then</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> oldPkgDescr</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> { library = addThCppToLibrary (library oldPkgDescr)</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> , executables = </span
><span class="Function"
>map</span
><span class="Normal NormalText"
> addThCppToExec (executables oldPkgDescr)</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> }</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Keyword"
>else</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> oldPkgDescr</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- Template Haskell package name</span
><br
/><span class="Normal NormalText"
>> thPackageName = </span
><span class="String"
>"template-haskell"</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- template-haskell version</span
><br
/><span class="Normal NormalText"
>> thVersion = findThVersion (packageDeps lbi)</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- CPP options for template-haskell >= 2.3</span
><br
/><span class="Normal NormalText"
>> thCppOpt = </span
><span class="String"
>"-DTH_LOC_DERIVEREP"</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- Find the version of the template-haskell package</span
><br
/><span class="Normal NormalText"
>> findThVersion [] = </span
><span class="Keyword DataConstructor"
>Nothing</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> findThVersion (PackageIdentifier (PackageName name) version:ps)</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> | name == thPackageName = </span
><span class="Keyword DataConstructor"
>Just</span
><span class="Normal NormalText"
> version</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> | </span
><span class="Function"
>otherwise</span
><span class="Normal NormalText"
> = findThVersion ps</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- Add the template-haskell CPP flag to a BuildInfo</span
><br
/><span class="Normal NormalText"
>></span
><span class="Function FunctionDefinition"
> addThCppToBuildInfo ::</span
><span class="Normal NormalText"
> BuildInfo -> BuildInfo</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> addThCppToBuildInfo bi =</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> bi { cppOptions = thCppOpt : cppOptions bi }</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- Add the template-haskell CPP flag to a library package description</span
><br
/><span class="Normal NormalText"
>></span
><span class="Function FunctionDefinition"
> addThCppToLibrary ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> Library -> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> Library</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> addThCppToLibrary ml = </span
><span class="Keyword"
>do</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> lib <- ml</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Function"
>return</span
><span class="Normal NormalText"
> (lib { libBuildInfo = addThCppToBuildInfo (libBuildInfo lib) })</span
><br
/></code
></pre
><pre class="sourceCode literatehaskell"
><code
><span class="Char Special"
>></span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- Add the template-haskell CPP flag to an executable package description</span
><br
/><span class="Normal NormalText"
>></span
><span class="Function FunctionDefinition"
> addThCppToExec ::</span
><span class="Normal NormalText"
> Executable -> Executable</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> addThCppToExec exec =</span
><br
/><span class="Char Special"
>></span
><span class="Normal NormalText"
> exec { buildInfo = addThCppToBuildInfo (buildInfo exec) }</span
><br
/></code
></pre
><p
><strike><em
>P.S.</em
> I used the <a href="http://thread.gmane.org/gmane.comp.lang.haskell.general/16899"
>recently released</a
> <a href="http://johnmacfarlane.net/pandoc/"
>pandoc</a
> <a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/pandoc-1.2"
>1.2</a
> for this article. Nice highlighting, eh?</strike></p
>
<p><a name="update1"></a><strong>Update #1:</strong> Apparently, Blogger's feed and/or <a href="http://planet.haskell.org/">Planet Haskell</a> aren't ready for the games I played with pandoc. Thus, I have removed the syntax highlighting. That's unfortunate, because it looked good on the web.</p>
<p><a name="update2"></a><strong>Update #2:</strong> Thanks to the magic of the internets and the fact that there are people much smarter than I, there is a solution. In hindsight, it's obvious (of course): dynamically typed programming!</p>
<p><a href="http://www-users.cs.york.ac.uk/~ndm/">Neil Mitchell</a> sent me this little piece of code which does just the trick:</p><pre class="sourceCode literatehaskell"><code>
> mkPackageName :: (Read a) => String -> a
> mkPackageName nm =
> fst $ head $ reads shownNm ++ reads ("PackageName " ++ shownNm)
> where
> shownNm = show nm
</code></pre>
<p>So, I plugged this into <code>thPackageName</code>, removed <code>PackageName</code> from the pattern in <code>findThVersion</code>, and—voilà!—it worked.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com2Padualaan 14, 3584 Utrecht, The Netherlands52.0848524 5.17044152.081555900000005 5.1631455000000006 52.0881489 5.1777365tag:blogger.com,1999:blog-8130326826065983217.post-66199591919981872332009-02-19T17:38:00.001+01:002009-02-19T23:48:35.145+01:00The strict danger of switching from pure to monadic Template Haskell<p>
Due to <a href="http://thread.gmane.org/gmane.comp.lang.haskell.generics/64">several issues</a> with the <a href="http://www.haskell.org/haskellwiki/Template_Haskell">Template Haskell</a> (TH) <a href="http://hackage.haskell.org/packages/archive/emgm/0.2/doc/html/Generics-EMGM-Common-Derive.html">deriving</a> in <a href="http://www.cs.uu.nl/wiki/GenericProgramming/EMGM">EMGM</a> (which I knew were there, but needed significant motivation to fix), I realized it was time to convert much of my code from pure to monadic. From the beginning, I developed it to be as non-monadic (i.e. not in <code><a href="http://www.haskell.org/ghc/docs/latest/html/libraries/template-haskell/Language-Haskell-TH.html#t:Q">Q</a></code>) as possible for <a href="http://www.haskell.org/haskellwiki/Functional_programming#Purity">all the reasons</a> one is supposed to. This led to several challenges that were not too difficult to surmount at the time. Namely, <code><a href="http://www.haskell.org/ghc/docs/latest/html/libraries/template-haskell/Language-Haskell-TH.html#v:reify">reify</a></code> and <code><a href="http://www.haskell.org/ghc/docs/latest/html/libraries/template-haskell/Language-Haskell-TH.html#v:newName">newName</a></code> had to be used at the top level of my function hierarchy, and their values had be passed down. But now I really need <code>reify</code> in a few places in the depths of the code, and it is quite impractical to do otherwise. For example, I need to expand type synonyms, and if I do that at the top level, every name is now either a name or some adaptation of a type declaration.
</p>
<p>
Most of the refactoring was surprisingly easy. I simply changed uppercase constructors to their lowercase, monadic equivalents (see the <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/template-haskell/Language-Haskell-TH.html">docs</a> for the difference). However, I ran into a problem in which a function specific to bifunctor types was getting applied to monomorphic types. This lead to strange errors (compile-time of course, since it's TH) that told me something had changed in the way the functions were used. It was very likely not the programming logic itself, because I was carefully migrating individual functions a few at a time and testing as I went. But somehow, once I reached the point in the code where I needed <code>reify</code>, I started getting these error reports (my code, though it was for unexpected inputs).
</p>
<p>
After several hours of tracing through with <code><a href="http://www.haskell.org/ghc/docs/latest/html/libraries/template-haskell/Language-Haskell-TH.html#v:report">report</a></code>, I found the problem. Here is the blah-ified (and simplified) original code:
</p>
<pre>
-- Non-monadic:
blah :: ... -> ...
blah ... = ...
-- Monadic wrapper
blahM :: ... -> Q [...]
blahM ... = return [blah ...]
-- Exposed
fun :: ... -> Q ...
fun ... = do
a <- ...
b <- blahM ...
let x =
case ... of
1 -> a
2 -> b
_ -> []
return (... ++ x)
</pre>
<p>
Most of the logic lies under <code>blah</code>, so it follows that I monadicized (monadified?) <code>blah</code> which required a minor changed to <code>blahM</code>:
</p>
<pre>
blah :: ... -> Q ...
blah ... = ...
blahM :: ... -> Q [...]
blahM ... = do
x <- blah ...
return [x]
</pre>
<p>
Now, this didn't affect anything immediately. I kept converting my functions to the monadic religion, and at some point, I suppose I evangelized too much. Then, I believe that <code>blah</code>, which by the original design was meant to be called lazily, became too strict. It was getting called every time, instead of only when the <code>case</code> expression matched on 2. Once I realized this, it was evident that I needed to change <code>fun</code>.
</p>
<pre>
fun :: ... -> Q ...
fun ... = do
x <-
case ... of
1 -> ...
2 -> blahM ...
_ -> return []
return (... ++ x)
</pre>
<p>
Now, everything is strictly normal again. No strange errors to keep me up at night. I believe now that <code>blahM</code> was always getting evaluated even though <code>blah</code> was not. So, as I pushed the monad down into the code, more and more things were getting strictly evaluated.
</p>
<p>
I keep learning that I don't understand laziness as well as I think I do. Or maybe it's that I don't understand strictness. Or perhaps I'm too lazy to strictly learn both.
</p>
<p>
I also resolve never to write non-monadic Template Haske11 code again (excluding small and/or simple functions, of course). The amount of work required is not worth the benefits gained.
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com0Padualaan 14, 3584 Utrecht, The Netherlands52.0848524 5.17044152.081555900000005 5.1631455000000006 52.0881489 5.1777365tag:blogger.com,1999:blog-8130326826065983217.post-27142397740022862452009-02-15T00:13:00.006+01:002009-03-31T13:55:22.935+02:00Incremental fold, a design pattern<p>
I recently read the article "How to Refold a Map" by David F. Place in <a href="http://www.haskell.org/haskellwiki/The_Monad.Reader">The Monad.Reader</a> <a href="http://www.haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf">Issue 11</a>. I've been thinking about incremental algorithms in Haskell for some time, and I realized that Place has written a specific instance (and optimization) of a more general concept: the <em>incremental fold</em>.
</p>
<p>
In this article, I demonstrate a design pattern for converting a datatype and related functions into an incremental fold. The pattern is not difficult to comprehend, but it would be nice to improve upon it. I explore a few improvements and issues with those improvements. Ultimately, I'd like to see this functionality in a program instead of a design pattern.
</p>
<p>
<em>Note: This is a <a href="http://www.haskell.org/haskellwiki/Literate_programming">literate Haskell</a> article. You can copy the text of the entire article, paste it into a new file called <code>IncrementalTreeFold.lhs</code>, and load it into <a href="http://www.haskell.org/ghc/docs/latest/html/users_guide/ghci.html">GHCi</a>.</em>
</p>
<pre>
> {-# LANGUAGE MultiParamTypeClasses #-}
> {-# LANGUAGE FlexibleInstances #-}
> {-# LANGUAGE ScopedTypeVariables #-}
> module IncrementalTreeFold where
> import Prelude hiding (elem)
> import qualified Data.Char as Char (ord)
</pre>
<h4>Introducing a Typical Binary Tree</h4>
<p>
Before we get to the conversion, let's choose an appropriate datatype. Place adapted the <a href="http://hackage.haskell.org/packages/archive/containers/0.2.0.0/doc/html/src/Data-Map.html#Map">Map type</a> used in <a href="http://hackage.haskell.org/packages/archive/containers/0.2.0.0/doc/html/Data-Map.html">Data.Map</a> (or <a href="http://hackage.haskell.org/packages/archive/containers/0.2.0.0/doc/html/src/Data-Set.html#Set">Set</a> in <a href="http://hackage.haskell.org/packages/archive/containers/0.2.0.0/doc/html/Data-Set.html">Data.Set</a>). To simplify my presentation, I will use an ordered binary tree with labeled nodes.
</p>
<pre>
> data Tree a
> = Tip
> | Bin a (Tree a) (Tree a)
> deriving Show
</pre>
<p>
Next, let's introduce some useful functions. An incremental fold is not necessarily like applying a <a href="http://www.citeulike.org/user/spl/tag/fold">fold function</a> (a.k.a. a <a href="http://knol.google.com/k/edward-kmett/catamorphisms/3qi7x2qrdushx/2">catamorphism</a>, not a <a href="http://www.citeulike.org/user/spl/tag/crush">crush function</a> that has become known as a fold) to a value directly. Instead, as I will later show, it integrates into existing functions that manipulate values. That said, we should have some functions for building <code>Tree</code>s. Here is the beginning of a <code>Tree</code> API. (There are a number of other operations, e.g. <code>delete</code> and <code>lookup</code>, that can easily be added but do not contribute much to the discussion.)
</p>
<p>
<code>empty</code> builds a tree with no elements.
</p>
<pre>
> empty :: (Ord a) => Tree a
> empty = Tip
</pre>
<p>
<code>singleton</code> builds a tree with a single element.
</p>
<pre>
> singleton :: (Ord a) => a -> Tree a
> singleton x = Bin x Tip Tip
</pre>
<p>
<code>insert</code> puts a value in the appropriate place given a left-to-right ordering of values in the tree.
</p>
<pre>
> insert :: (Ord a) => a -> Tree a -> Tree a
> insert x t =
> case t of
> Tip ->
> singleton x
> Bin y lt rt ->
> case compare x y of
> LT -> Bin y (insert x lt) rt
> GT -> Bin y lt (insert x rt)
> EQ -> Bin x lt rt
</pre>
<p>
<code>fromList</code> creates a tree from a list of values.
</p>
<pre>
> fromList :: (Ord a) => [a] -> Tree a
> fromList = foldr insert empty
</pre>
<p>
<code>elem</code> determines if a value is an element of a tree.
</p>
<pre>
> elem :: (Ord a) => a -> Tree a -> Bool
> elem x t =
> case t of
> Tip ->
> False
> Bin y lt rt ->
> case compare x y of
> LT -> elem x lt
> GT -> elem x rt
> EQ -> True
</pre>
<p>
Now, using our library of sorts, we can create binary search tree and check if a value is in the tree.
</p>
<pre>
> test1 = 37 `elem` fromList [8,23,37,82,3]
</pre>
<h4>Tree Folds</h4>
<p>
Suppose that we now want the size of the tree. For good abstraction and high reuse, we create a <code>fold</code> function.
</p>
<pre>
> data Alg a b = Alg { ftip :: b, fbin :: a -> b -> b -> b }
> fold :: Alg a b -> Tree a -> b
> fold alg = go
> where
> go Tip = ftip alg
> go (Bin x lt rt) = fbin alg x (go lt) (go rt)
</pre>
<p>
<code>fold</code> allows us to write a simple <code>size</code> function.
</p>
<pre>
> size :: Tree a -> Int
> size = fold (Alg 0 (\_ lr rr -> 1 + lr + rr))
</pre>
<p>
I use the datatype <code>Alg</code> here to contain the <a href="http://www.alpheccar.org/en/posts/show/77">algebra of the fold</a>. In <code>size</code>, we simply replace each constructor in the algebra of <code>Tree</code> with a corresponding element from the algebra of integer addition. Since you're reading this article, you're probably a Haskell programmer and already familiar with the sorts of functions that can be written with folds. Here are a few others.
</p>
<pre>
> filter :: (a -> Bool) -> Tree a -> [a]
> filter f = fold (Alg [] (\x lr rr -> if f x then [x] else [] ++ lr ++ rr))
> ord :: Tree Char -> Tree Int
> ord = fold (Alg Tip (\x lt rt -> Bin (Char.ord x) lt rt))
</pre>
<h4>Incremental Change</h4>
<p>
Now that we have a grasp on using a fold on a datatype, I would like to show how to extend my binary tree "library" defined above to support an incremental fold. The incremental fold can (I believe) do everything a traditional fold can do, but it does it during <code>Tree</code> construction instead of externally in a separate function. This means that every time we produce a new <code>Tree</code> (via <code>singleton</code>, <code>insert</code>, or <code>fromList</code> for example), we get a new result of the incremental fold.
</p>
<p>
Transforming our library into an incremental calculating machine involves several steps. The first step is extending the datatype to hold the incremental result. Since we want to be polymorphic in the result type, we add a type parameter <code>r</code> to the <code>Tree</code> type constructor. And since each constructor may possibly have an incremental result, it must also be extended with a place holder for <code>r</code>.
</p>
<pre>
> data Tree' a r
> = Tip' r
> | Bin' a (Tree' a r) (Tree' a r) r
> deriving Show
</pre>
<p>
For convenience and possibly to hide the modified constructors from the outside world, we add a function for retrieving the increment result.
</p>
<pre>
> result' :: Tree' a r -> r
> result' (Tip' r) = r
> result' (Bin' _ _ _ r) = r
</pre>
<p>
As I mentioned earlier, the machinery of the fold is now in the construction. To implement this second step, we use <a href="http://splonderzoek.blogspot.com/2008/01/smart-constructors.html">smart constructors</a>.
</p>
<pre>
> tip' :: Alg a r -> Tree' a r
> tip' alg = Tip' (ftip alg)
> bin' :: Alg a r -> a -> Tree' a r -> Tree' a r -> Tree' a r
> bin' alg x lt rt = Bin' x lt rt (fbin alg x (result' lt) (result' rt))
</pre>
<p>
Both <code>tip'</code> and <code>bin'</code> construct new values of <code>Tree' a r</code> and using the algebra, calculate the incremental result to be stored in each value. Thus, the actual fold operation is "hidden" in the construction of values.
</p>
<p>
Now, in order to put the incremental fold to work in a function, we simply (1) add the algebra to the function's arguments, (2) add an wildcard pattern for the result field in constructor patterns, and (3) replace applications of the constructors with that of their incremental cousins. Here's an example of the <code>singleton</code> and <code>insert</code> functions modified for incremental folding.
</p>
<pre>
> singleton' :: (Ord a) => Alg a r -> a -> Tree' a r
> singleton' alg x = bin' alg x (tip' alg) (tip' alg)
> insert' :: (Ord a) => Alg a r -> a -> Tree' a r -> Tree' a r
> insert' alg x t =
> case t of
> Tip' _ ->
> singleton' alg x
> Bin' y lt rt _ ->
> case compare x y of
> LT -> bin' alg y (insert' alg x lt) rt
> GT -> bin' alg y lt (insert' alg x rt)
> EQ -> bin' alg x lt rt
</pre>
<p>
Comparing these functions with the initial versions, we see that the changes are readily apparent. Modify every other <code>Tree'</code>-hugging function in the same manner, and you have a design pattern for an incremental fold!
</p>
<h4>Improving the Incremental Implementation</h4>
<p>
Of course, you may complain that there's some amount of boilerplate work involved. For example, we have to add this <code>alg</code> argument everywhere. Let's try to replace that with a type class.
</p>
<pre>
< class Alg'' a r where
< ftip'' :: r
< fbin'' :: a -> r -> r -> r
</pre>
<p>
And we redefine our smart constructors.
</p>
<pre>
< tip'' :: (Alg' a r) => Tree' a r
< tip'' = Tip' ftip''
</pre>
<p>
But there's a problem here! GHC reports that it <code>Could not deduce (Alg'' a r) from the context (Alg'' a1 r)</code>. The poor compiler cannot infer the type of the parameter <code>a</code> since <code>ftip''</code> has only type <code>r</code>.
</p>
<p>
Let's try another version of the class. In this one, we add a dummy argument to <code>ftip'</code> in order to force GHC to correctly infer the full type.
</p>
<pre>
> class Alg'' a r where
> ftip'' :: a -> r
> fbin'' :: a -> r -> r -> r
> tip'' :: forall a r . (Alg'' a r) => Tree' a r
> tip'' = Tip' (ftip'' (undefined :: a))
> bin'' :: (Alg'' a r) => a -> Tree' a r -> Tree' a r -> Tree' a r
> bin'' x lt rt = Bin' x lt rt (fbin'' x (result' lt) (result' rt))
</pre>
<p>
This provides one (not very pretty) solution to the problem. I'm able to get around the need to require an argument for <code>tip''</code> by using <a href="http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensions.html#scoped-type-variables">lexically scoped type variables</a>. But it doesn't remove the ugly type from <code>ftip''</code>, and the user is forced to ignore it when writing an instance.
</p>
<p>
The functions can now be rewritten with the <code>Alg''</code> constraint.
</p>
<pre>
> empty'' :: (Ord a, Alg'' a r) => Tree' a r
> empty'' = tip''
> singleton'' :: (Ord a, Alg'' a r) => a -> Tree' a r
> singleton'' x = bin'' x tip'' tip''
> insert'' :: (Ord a, Alg'' a r) => a -> Tree' a r -> Tree' a r
> insert'' x t =
> case t of
> Tip' _ ->
> singleton'' x
> Bin' y lt rt _ ->
> case compare x y of
> LT -> bin'' y (insert'' x lt) rt
> GT -> bin'' y lt (insert'' x rt)
> EQ -> bin'' x lt rt
> fromList'' :: (Ord a, Alg'' a r) => [a] -> Tree' a r
> fromList'' = foldr insert'' empty''
</pre>
<p>
These versions look more like the non-incremental implementations above. To use them, we need to declare an instance of <code>Alg''</code> with an appropriate algebra for our desired incremental result. Here's how we would rewrite <code>size</code>.
</p>
<pre>
> newtype Size = Size { unSize :: Int }
> instance Alg'' a Size where
> ftip'' _ = Size 0
> fbin'' _ lr rr = Size (1 + unSize lr + unSize rr)
> size'' :: Tree' a Size -> Int
> size'' = unSize . result'
> test2 = size'' $ insert'' 's' $ insert'' 'p' $ insert'' 'l' $ fromList'' "onderzoek"
</pre>
<p>
<code>Size</code> is still defined as a fold, but the result is incrementally built with each application of a library function. This can have a nice performance boost as Place also found in his article.
</p>
<h4>Generic Thoughts</h4>
<p>
On reflecting over my implementation, I really don't like the dummy arguments required by constructors like <code>Tip</code>. There are other approaches to dealing with this, but I haven't yet found a better one. If you use a <a href="http://www.haskell.org/haskellwiki/Functional_dependencies">functional dependency</a> such as <code>r -> a</code> in the definition of <code>Alg''</code>, then <code>a</code> would be uniquely determined by <code>r</code>. In the case of <code>size''</code>, we would have to specify a concrete element type for <code>Tree'</code> instead of the parameter <code>a</code> (or use <a href="http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensions.html#undecidable-instances">undecidable instances</a>). Perhaps, dear reader, you might have a better solution?
</p>
<p>
The incremental fold pattern is great for documenting an idea, but it has several downsides: (1) The obvious one is that it requires modifying a datatype and code. This is not always desirable and often not practical. (2) Implementing an incremental fold can involve a lot of boilerplate code and many, small changes that are monotonous and boring. It's very easy to make mistakes. In fact, I made several copy-paste-and-forget-to-change errors while writing this article.
</p>
<p>
As <a href="http://www.comlab.ox.ac.uk/jeremy.gibbons/">Jeremy Gibbons</a> and others have shown us, <a href="http://www.comlab.ox.ac.uk/publications/publication1452-abstract.html">design patterns are better as programs</a>. Since the code is so regular, it seems very receptive to some <a href="http://www.cs.uu.nl/wiki/GenericProgramming">generic programming</a>. I plan to explore this further, possibly using one of the <a href="http://hackage.haskell.org/packages/archive/pkg-list.html#cat:generics">many generics libraries</a> available for Haskell or designing a new one. Suggestions and feedback are welcome.
</p>
<p>
<strong>Update 2008-03-30:</strong> The <a href="http://github.com/spl/splonderzoek/blob/36532fb9a116f30685e025aeccf5a03d151694eb/IncrementalTreeFold.lhs">source code for this entry</a> is now available at GitHub.
</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com5tag:blogger.com,1999:blog-8130326826065983217.post-24424945083100443392008-08-30T00:04:00.006+02:002008-08-30T19:38:21.745+02:00I git it now!<p>After a lot of <a href="http://thread.gmane.org/gmane.comp.lang.haskell.glasgow.user/14819">discussion</a> about <a href="http://www.haskell.org/ghc/">GHC</a> switching from darcs to git, I was tempted to try it out. Today was an experimentation day for me, and it turned out really well.</p>
<p>I come from the world of <a href="http://subversion.tigris.org/">Subversion</a>. It has been my primary VCS for a number of years, and that's mostly by circumstance. In my master's program, it was just easiest to get access to. At my last job, SVN was the main repository for everything. I became very familiar with it: it's quirks with moving files, it's problems with merging branches, and so on. Sure, it's not the best, but it worked well enough. In fact, my <a href="http://www.cs.uu.nl/">current place of employment</a> also uses SVN extensively.</p>
<p>As I gradually become more familiar with the <a href="http://www.haskell.org/">Haskell</a> community, I encountered <a href="http://darcs.net/">darcs</a>. I never really became comfortable with it, though. It was quite slow for basic things. The large number of commands and the many ways of doing things that are similar but slightly different was, truth be told, somewhat overwhelming. Of course, I only used darcs to pull source repositories for building. I never had my own repository or tried to send a patch to someone else.</p>
<p>Then, this thing with GHC and its libraries came up. They were looking for maintenance of the SYB library, and we volunteered. I presume that the GHC developers are going to set up git repositories for the libraries, so I figured I should get to know <a href="http://git.or.cz/">git</a>. In my reading, I had learned about several features of git that intrigued me. It was these features that lured me in and have pretty much captured me, too.</p>
<p>First, there's the concept of <a href="http://www.kernel.org/pub/software/scm/git/docs/git-branch.html">local branches</a>. I love it! I can't get enough. I generally make copies of directories and files to do my own form of local branching. Perhaps it's naive, but it is the best solution I had found up to now. I often don't want to check unstable code or unused code into the central repository. Either it's more effort than I want to spend at the time or it ends up in a branch that is forgotten about and gets out of date quickly. The git local branches are simple: I don't have to spend time copying. They are quick: <code>git checkout <branch></code>. And they stay in the same place as the master branch, so I don't have to search for them in my files. Wonderful!</p>
<p>Second, git has a very nice extension, <a href="http://www.kernel.org/pub/software/scm/git/docs/git-svn.html">git-svn</a>, for integrating with a Subversion repository. Since we use that at work, I can try out git <em>and</em> using it to actually do work. That's what today's experiment was about.</p>
<p>As for comparing VCS tools, I can't say I'm very qualified. My general (and limited) experience with darcs is that it is very slow and difficult to figure out how to use. My experience with git is that while it has a very large number of commands, it is thoroughly documented. There are a number of tutorials available to point out what I need to get started using. Plus, there's the page on <a href="http://git.or.cz/course/svn.html">git for Subversion users</a>.</p>
<p>So, I will continue to experiment with git, since I can do it without much difficulty. So far, I'm more happy than not. It's obviously not perfect, but I like the things it does best.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com2tag:blogger.com,1999:blog-8130326826065983217.post-49628695122134972542008-01-25T22:36:00.000+01:002008-01-26T02:08:22.790+01:00Smart constructors<p>[<abbr title="Editor">Ed</abbr>: <i>This being the inaugural post in my technical blog, I felt I should start with a topic that's rather introductory and... </i>constructive<i> as the case may be.</i>]</p><p>I recently found myself confronted with the following problem in my <a href="http://www.haskell.org/">Haskell</a> code. I needed to create elements of an <a href="http://www.haskell.org/haskellwiki/Algebraic_data_type">algebraic data type</a>; however, in order to store the intermediate results of a computation, part of each <a href="http://www.haskell.org/haskellwiki/Constructor">constructor</a> was generated from the other parts. It can be difficult to work with such a type, but there is a solution! Let me attempt to provide a scenario and explain both the naïve way and the <i>smart</i> way.</p><p>First, let's use the following data type as our <abbr title="in other words, example">pedagogical substrate</abbr>:</p><pre><b>data</b> Expr = Val Int | Add Expr Expr</pre><p>The above tells me that this <i>expression</i> type may be constructed as a value <code>Val</code> containing an integer <code>Int</code> or as an addition operation <code>Add</code> containing 2 subexpressions. With this fairly simple type, I might want to encode an arithmetic expression <code>e1</code> such as <code>(4 + 2) + 7</code>. The result might look like so:</p><pre>e1 = Add (Add (Val 4) (Val 2)) (Val 7)</pre><p>The canonical follow-up to this would be an evaluation mechanism for expressions:</p><pre>eval :: Expr -> Int<br/>eval (Val i) = i<br/>eval (Add e1 e2) = eval e1 + eval e2</pre><p>When I call <code>eval e1</code>, it recursively traverses the tree described in <code>e1</code> as evidenced by the calls to <code>eval</code> in the <code>Add</code> component.</p><p>Now, suppose I'm developing an application using the data type <code>Expr</code> [Ed: <i>What—a calculator?</i>], and I need to deal with very large expressions. The expression trees can be very deep and wide, requiring <code>eval</code> to spend time visiting every node. In order to remove the need for that potentially time-consuming traversal, I want to have expressions evaluated upon construction from the bottom up. So, given that the only real computation involved in our <code>eval</code> function is addition, let's append the result type <code>Int</code> onto the <code>Add</code> constructor for storing the result.</p><pre><b>data</b> Expr = Val Int | Add Expr Expr <u>Int</u></pre><p>Now, when we build our expression, we do the addition as well.</p><pre>e2 = Add (Add (Val 4) (Val 2) <u>(4+2)</u>) (Val 7) <u>(4+2+7)</u></pre><p>But wait... That doesn't really make sense. Shouldn't the computer be forming the addition operations for us? This seems very error-prone. Let's try breaking down our construction of <code>e2</code>, so that we're building a single expression at a time.</p><pre>e3 = Add (Val 4) (Val 2) (4+2)<br>e4 = Add e3 (Val 7) (<b>??</b>+7)</pre><p>That didn't really help much, either. I suppose we could extract out the <code>4+2</code> bit like so...</p><pre><u>i = 4+2</u><br>e5 = Add (Val 4) (Val 2) i<br>e6 = Add e3 (Val 7) (<u>i</u>+7)</pre><p>but then it seems like we're creating extra work. I mean, this is <i>functional</i> programming! There should be an easier way to do this! [Ed: <i>Fine. Now, will you please get to the point soon.</i>]</p><p>And indeed there is! It's called a <a href="http://www.haskell.org/haskellwiki/Smart_constructors">smart constructor</a>. [Ed: <i>Oh really? The title did </i>not<i> give that away at all, I swear!</i>] The process is as simple as replacing the actual <code>Add</code> constructor with a function. This function takes in the same arguments as <code>Add</code> with the exception of the result value, computes the result, and returns a complete <code>Add</code>. Here it is in all its glory.</p><pre>makeAdd :: Expr -> Expr -> Expr<br>makeAdd (Val i1) (Val i2) = Add (Val i1) (Val i2) (i1+i2)<br>makeAdd (Val i1) (Add e2a e2b s2) = Add (Val i1) (Add e2a e2b s2) (i1+s2)<br>makeAdd (Add e1a e1b s1) (Val i2) = Add (Add e1a e1b s1) (Val i2) (s1+i2)<br>makeAdd (Add e1a e1b s1) (Add e2a e2b s2) = Add (Add e1a e1b s1) (Add e2a e2b s2) (s1+s2)</pre><p>As you can see, there are no recursive calls in <code>makeAdd</code>. We are effectively hiding the computation as well as the fact that there is this third argument to the constructor. Consequently, <code>makeAdd</code> is just as easy to use as the constructor of the original <code>Add</code> (before appending the <code>Int</code>):</p><pre>e7 = makeAdd (makeAdd (Val 4) (Val 2)) (Val 7)</pre><p>In addition, we can rewrite <code>eval</code> so that it will simply fetch the precomputed value of an <code>Add</code>.</p><pre>eval :: Expr -> Int<br>eval (Val i) = i<br>eval (Add e1 e2 s) = s</pre><p>And that's the basics for smart constructors. There are a few more things to add, but I think I'll stop for now. Perhaps I'll revisit this subject in a later entry.</p>Anonymoushttp://www.blogger.com/profile/02951502639017426632noreply@blogger.com5