tag:blogger.com,1999:blog-79385639894003970042024-03-05T12:13:25.877-08:00In Clojure We TrustA piece of intertube about the Clojure programming language, algorithms and artificial intelligence.Unknownnoreply@blogger.comBlogger16125tag:blogger.com,1999:blog-7938563989400397004.post-30642992294477684142013-08-11T01:55:00.000-07:002013-08-11T01:55:28.351-07:00Migrating Away From Google BloggerThis blog is moving away from Google Blogger.
The new URL is <a href="http://dialectical-computing.de/blog/">http://dialectical-computing.de/blog/</a>
Please update your RSS reader.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7938563989400397004.post-5502336760160116772013-01-29T01:34:00.000-08:002013-01-29T01:34:04.922-08:00Searching in Clojure and ClojureScript files with Ack<p><a href="http://betterthangrep.com/">"Ack is a tool like grep, optimized for programmers"</a>. I knew the existence of Ack since a few years but I never gave it try. Now that I did, I'm positively surprised: it's easy to use and fast. </p>
<p>I was always fighting in Emacs between <b>grep</b> (what is the syntax?), <b>igrep-find</b> (why did it suddenly stopped to prompt for directories?), <b>tags-search</b> (ooops some of my files are not tagged) and <b>rgrep</b> (oh it did exist?). I installed <a href="https://github.com/jhelwig/ack-and-a-half">ack-and-a-half</a> for Emacs and its great. Ack-and-half tries to find automatically the root directory of your project but you can set ack-and-a-half-prompt-for-directory to true with <i>(setq ack-and-a-half-prompt-for-directory t)</i> for it to ask which directory to search in.</p>
<p>The Ack version on the <a href="http://betterthangrep.com/">website</a> provides support for Clojure files. For ClojureScript files, you need to add the following lines to your ~/.ackrc file:
<pre>
--type-add
clojure=.cljs
</pre>
</p>
<p>Et voilà, enjoy!</p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7938563989400397004.post-48425725611656744812013-01-15T05:40:00.000-08:002013-01-18T03:26:45.622-08:00Duplicating s-expressions on a line<p>Duplicating a line is extremely useful when editing text and specially when programming. There is no native command in Emacs to achieve that but <a href="http://stackoverflow.com/questions/88399/how-do-i-duplicate-a-whole-line-in-emacs">it's easy to add one</a>.
</p>
<p>
It's easy to get addicted to the use of this new command but a problem remains when programming in Lisp with <a href="http://emacswiki.org/emacs/ParEdit">paredit.el</a>: duplicating sometimes lead to invalid s-expressions being inserted.
</p>
<p>
I decided to give it a try and made an implementation that duplicate the s-expressions after the point (cursor).
For instance in Clojure if you are editing this code:
<pre class="brush: clojure" name="code">(ns myns
(:use [clojure.string :only [escape]]))
</pre>
You can duplicate the first vector by placing the cursor on the square bracket, invoking the command with one keystroke and then easily obtain this code:
<pre class="brush: clojure" name="code">(ns myns
(:use [clojure.string :only [escape]]
[clojure.set :only [union]]))
</pre>
Here is the code to duplicate the line; to my knowledge there is no such command in <a href="http://emacswiki.org/emacs/ParEdit">paredit.el</a>:
<p>
<script src="https://gist.github.com/4538617.js"></script>
</p>
Not really pretty but it does the work, feel free to provide a nicer implementation in the comments or add it to your ~/.emacs.d/init.el file with:
<pre class="brush: clojure" name="code">
(eval-after-load "paredit"
'(progn (define-key paredit-mode-map (kbd "C-S-d") 'paredit-duplicate-after-point)))
</pre>
<b>Edit:</b> <a href="https://github.com/kototama/.emacs.d/blob/master/elisp/setup-lisp.el#L51">Here a fix</a> for when the sexp is the last expression in the buffer.
</p>Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-7938563989400397004.post-60282268515198792832012-10-18T03:12:00.001-07:002012-10-18T03:12:44.976-07:00An Emacs minor mode for the ClojureScript compilation<p>When programming with ClojureScript, one has to lunch <b>"lein cljsbuild auto"</b> to automatically compiles its ClojureScript sources. It is convenient but a problem remains: the output of the compilation process must be manually read to see if any errors or warnings occur.
</p>
<p>
To solve this problem I programmed a simple minor mode for Emacs. If you start the <b>cljsbuild</b> command in a terminal buffer, it will watch the ouput and popup the window if an error or a warning occurs. It can also automatically hide the process when the compilation succeed, so that you are able to concentrate on what matters, the code.
</p>
<p>
It's available on <a href="http://marmalade-repo.org/">Marmalade</a> or <a href="https://github.com/kototama/cljsbuild-mode">Github</a>.
</p>
<p>
Feedback and patches are welcomed!
</p>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7938563989400397004.post-15703120992095365942012-05-02T09:06:00.000-07:002012-05-02T09:06:47.791-07:00Implementing a LispTo extend my knowledge and to have a better understanding of the Lisp's foundations, I implemented a simple Lisp in C. It supports symbols, integers, a few primitives, anonymous functions, closures, macros and garbage collection. The implementation follows the KISS principles and is around 1400 lines of code.
<br><br><br>
Discussion: <a href="http://news.ycombinator.com/item?id=3919685">http://news.ycombinator.com/item?id=3919685</a>
<br>
Code: <a href="https://github.com/kototama/kml">https://github.com/kototama/kml</a>
<br>Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-7938563989400397004.post-34697542869990683052012-02-23T06:27:00.001-08:002012-02-23T06:29:13.056-08:00Emacs key bindings for Lisp programming<p>I finished reading <a href="http://www.amazon.com/gp/product/0596006489/ref=as_li_ss_tl?ie=UTF8&tag=comprhegel-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0596006489">Learning GNU Emacs, Third Edition</a><img src="http://www.assoc-amazon.com/e/ir?t=comprhegel-20&l=as2&o=1&a=0596006489" width="1" height="1" border="0" alt="" style="border:none !important; margin:0px !important;" />
this week. The edition is from 2004 but the book has aged well. All essential concepts, modes and key bindings are presented. The Emacs documentation system is also explained, which is useful to know if you want to further extend your knowledge once you read the book. One chapter is an introduction to Emacs programming with Emacs Lisp. It gives the basis to start and explains how to implement a simple major mode. Of course since 2004, the Emacs ecosystem has changed so you won't find something on <a href="http://www.emacswiki.org/emacs/Magit">Magit</a> mode (for Git) or on the <a href="http://tromey.com/elpa/">Emacs Lisp Package Archive</a> but if you are not an expert Emacs user, you will learn from reading it.
</p>
<p>
One chapter is on programming modes and Lisp key bindings are presented. Even if you don't use <a href="http://www.emacswiki.org/emacs/ParEdit">paredit</a> (and really you should - just take a few minutes to learn its key binding) many commands are available to work with S-expressions. Here is one table of the book that illustrates them:
<br/>
<a target="_blank" href="http://min.us/mhs5wtNAH#1o"><img src="http://i.minus.com/jbizg3SIY3JTAL.png" border="0"/></a>
</p>
<p>
Structurally editing S-expressions gives an intense satisfaction and will make you regret Lisp syntax whenever you have to program with an another language family.
</p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7938563989400397004.post-41538695918043075752012-02-14T03:16:00.001-08:002012-02-14T03:19:45.999-08:00js2-mode fun<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhqHuVZbIGYiOZl004hSafHidtyI208e1W9U6ZVxS4rkXXDjpB9wYdRhFZN791OsrtuSMcYqgHkY4_6WmIfLcG7KR-fAF2oONppCKzkqE8rDplHzFPQWuStWmtqmAIVZQMGlc_zZyz59obD/s1600/noeffects.png" imageanchor="1"><img border="0" height="113" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhqHuVZbIGYiOZl004hSafHidtyI208e1W9U6ZVxS4rkXXDjpB9wYdRhFZN791OsrtuSMcYqgHkY4_6WmIfLcG7KR-fAF2oONppCKzkqE8rDplHzFPQWuStWmtqmAIVZQMGlc_zZyz59obD/s320/noeffects.png" width="320" /></a>
<br/><i>In Emacs with the JavaScript js2-mode...</i>
</div>
<br />
<br />
<br />
<div style="text-align: center;">
No side effects? How bad can <b>THAT</b> be :-) ?
</div>
<br />
<br />
<br />Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-7938563989400397004.post-67238643368632162552011-11-11T08:10:00.001-08:002011-11-11T08:21:25.414-08:00Updating Clojure namespacesContinuing my experimentations with Emacs Lisp, I created a function that automatically updates the namespace of a Clojure buffer in conformity with its pathname. This is useful after renaming a file, since changing a file pathname requires to change its namespace, which is sometimes annoying to do by hand.
<br/>
<script src="https://gist.github.com/1358405.js"> </script>
Once added to your .emacs file, you can call it with: <pre>M-x clojure-update-ns</pre>
<br/>It assumes clojure-mode is already loaded.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-7938563989400397004.post-78208178090595898892011-11-01T09:38:00.000-07:002011-11-01T09:38:37.914-07:00Earmuffs and variablesAccording to the <a href="http://dev.clojure.org/display/design/Library+Coding+Standards">Clojure coding standards for libraries</a>, variables names should be written with *earmuffs* only when they are intended to be rebind. <br />
<br />
Here and there I forget this rule and use earmuffs most of the time, so I decided to create an Emacs Lisp function to add/remove earmuffs to variable:<br />
<br />
<br />
<br />
<script src="https://gist.github.com/1331024.js"> </script><br />
<br />
Add it to your .emacs file and then place your cursor on a variable and call it with <pre>M-x earmuffy</pre>to add earmuffs, or type <pre>C-u M-x earmuffy</pre>to remove them.Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-7938563989400397004.post-32460115092947042442011-05-08T12:40:00.000-07:002011-05-08T12:40:28.415-07:00Dear language designers, do not forget AdaThese last days I took some time to refresh my old memories of the Ada language. While Ada, like all languages, has defaults on its own I'm still very impressed by some functionalities it offers and that current mainstream languages still don't have. Most of these functionalities are there since the first standardized version in 1983 (since then the language standard was extended in 1995, 2005 and the next version is expected for 2012).<br />
<br />
The first impressive future is about primitive types. Here are some of the types defined in Ada and their C equivalent (taken from <a href="http://www.blogger.com/post-create.g?blogID=7938563989400397004#foot1">[1]</a>):<br />
<br />
<table border="2" cellpadding="6" cellspacing="0" frame="hsides" rules="groups"><colgroup><col align="left"></col><col align="left"></col><col align="left"></col> </colgroup><thead>
<tr><th>Ada Type</th><th>Description</th><th>C Equivalent</th></tr>
</thead> <tbody>
<tr><td>Character</td><td>A single character</td><td>char</td></tr>
<tr><td>Integer</td><td>An integer (32-bit) number</td><td>int</td></tr>
<tr><td>Natural</td><td>Zero or positive integer</td><td>-</td></tr>
<tr><td>Positive</td><td>A positive integer</td><td>-</td></tr>
<tr><td>Long_Integer</td><td>A big integer (same as long in Gcc)</td><td>long (same as int in Gcc)</td></tr>
<tr><td>Long_Long_Integer</td><td>A really big (64-bit) integer</td><td>long long</td></tr>
<tr><td>Short_Integer</td><td>A small (16-bit) integer</td><td>short</td></tr>
<tr><td>Short_Short_Integer</td><td>A really small (8-bit) integer</td><td>char</td></tr>
<tr><td>Float</td><td>A real number</td><td>float</td></tr>
<tr><td>Long_Float</td><td>A big real number</td><td>double</td></tr>
<tr><td>Long_Long_Float</td><td>A really big real number</td><td>long double</td></tr>
<tr><td>Short_Float</td><td>A smaller real number</td><td>?</td></tr>
<tr><td>Fixed</td><td>A fixed-point real number</td><td>-</td></tr>
<tr><td>String</td><td>An Ada fixed-length string</td><td>char array</td></tr>
</tbody> </table><br />
Boolean types are also provided. New types are defined and type safety is guaranteed. Here we define a new type based on a Long_Float and a variable of this type:<br />
<pre class="brush:Clojure" name="code">type Speed is new Long_Float;
Speedy_Gonzales_Speed : Speed;
</pre><br />
Since Speed is a new type, it is not a Long_Float and thus assignment from a Long_Float value to a Speed variable is forbidden:<br />
<pre class="brush:Clojure" name="code">X : Long_float := 300.0;
Speedy_Gonzales_Speed := X;
</pre>The compiler effectively gives an error:<br />
<code><br />
expected type "Speed" defined at line 6<br />
found type "Standard.Long_Float"<br />
</code><br />
When it makes sense, we can define a subtype of another primitive type. Assignments between types and their subtypes is allowed. Here we define the type Degree which is a subtype of Float:<br />
<pre class="brush:Clojure" name="code">subtype Degree is Long_Float;
Oven_Temperature : Degree;
Y : Long_Float := 255.0;
Oven_Temperature := Y;
</pre><br />
Types can be constrained with a range definition (taken from <a href="http://www.blogger.com/post-create.g?blogID=7938563989400397004#foot2">[2]</a>):<br />
<pre class="brush:Clojure" name="code">type Degrees is new Float range -273.15 .. Float'Last;
</pre><br />
This allow a Degrees variable to range from -273.15 (absolute zero) to the last value allowed by a Float.<br />
<br />
This strong typing provides safety and contrasts with what is seen in current mainstream programming languages. Languages like Java don't provide rich primitive types (there are for instance no unsigned integer in Java!) and require the programmer to define its own cumbersome classes if he wants new types (which poses readability problems if the types are new number types and the language does not support operator overloading). Some languages like C don't even bother so much about type conversion: a float can be assigned to an integer. This leads to solutions which are far from being satisfying (see for instance <a href="http://c-faq.com/fp/round.html">C FAQ - round</a>).<br />
<br />
A lot of other possibilities are offered to the Ada programmer, for instance decimal types can be defined with their precision. The precision is then guaranteed by the compiler:<br />
<pre class="brush:Clojure" name="code">type money is delta 0.01 digits 18;
</pre>Ada also supports multidimensional arrays, bit-level memory access, definition of memory pool, concurrency programming in a task-oriented way, object-oriented programming, generic packages etc.<br />
<br />
At another level Scheme and Common Lisp supports a numeric towel. For example, 3 is an integer. Therefore 3 is also a rational, a real, and a complex (example from the <a href="http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.2.1">Scheme standard</a>).<br />
<br />
<pre class="brush:Clojure" name="code">;; in Scheme:
> (rational? (/ 1 5))
#t
> (rational? 3)
#t
> (real? 3)
#t
</pre>While this discussion may not make so much sense for dynamic languages such as Clojure, I think new languages being designed, which are not dynamically typed, could really benefit of having such rich primitives types. A complex type systems like the one from ML or Haskell is not needed for this purpose and primitives types is the most basic and most used feature of a programming language, so dear languages designers, next time, have a small thought for Ada.<br />
<br />
[1] <a href="http://www.pegasoft.ca/resources/boblap/book.html" id="foot1"> http://www.pegasoft.ca/resources/boblap/book.html</a><br />
[2] <a ahref="http://en.wikibooks.org/wiki/Ada_Programming" href="http://www.blogger.com/post-create.g?blogID=7938563989400397004" id="foot2">http://en.wikibooks.org/wiki/Ada_Programming</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7938563989400397004.post-13282504048825476122011-04-20T07:28:00.000-07:002011-05-06T02:58:21.656-07:00Fed up with typing ns declarations?While watching the demonstration video of the <a href="http://www.playframework.org/">Play framework</a>, I saw that the developer had some nice templates for its TextMate editor. A few Google searches tells us that it is also possible to have the same functionality in Emacs with the <a href="http://code.google.com/p/yasnippet/">YASnippet</a> template system.<br />
<br />
Typing all these long namespaces declarations in Clojure is quickly boring when you create a lot of files, so why not create a template for that?<br />
<br />
After having installed YASnippet, create a <i>clojure-mode</i> directory inside the <b>yasnippet/snippets/text-mode</b> directory and create a file named <i>ns</i> with <a href="https://gist.github.com/931439">this content</a>:<br />
<br />
<pre>(ns `(let* ((nsname '())
(dirs (split-string (buffer-file-name) "/"))
(aftersrc nil))
(dolist (dir dirs)
(if aftersrc
(progn
(setq nsname (cons dir nsname))
(setq nsname (cons "." nsname)))
(when (or (string= dir "src") (string= dir "test"))
(setq aftersrc t))))
(when nsname
(replace-regexp-in-string "_" "-" (substring (apply 'concat (reverse nsname)) 0 -5))))`
(:use $1)
(:require ))
</pre><br />
Now, when inside a Clojure buffer type "ns" and TAB to complete ; if you are for instance in the <b>src/mylib/utils/swing_stuff.clj</b> buffer, this will be expanded into the following text:<br />
<pre>(ns <b>mylib.utils.swing-stuff</b>
(:use )
(:require ))
</pre><br />
Isn't that handy?<br />
<br />
Note: this is my first hack with Emacs Lisp, and now that it is working I'm publishing it without any further improvements, so be indulgent regarding the implementation!Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-7938563989400397004.post-38764877494881255122011-01-23T08:40:00.000-08:002011-05-06T02:58:21.656-07:00Ray tracing, once againThere are already several implementations of simple raytracers in Clojure on the Web but I couldn't resist implementing one for myself! It is based on the one of the book Ansi Common Lisp by Paul Graham. <br />
<br />
Nothing particular, just perhaps the use of protocols for the dispatch of the normal, color and intersect functions and some code for displaying spirals.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnCrVZer-37d_aldXRyT6ttHLZbPj6ImSaybYSj7S05Sj1ZEVBpz6WmPuZa9WCjnctisYm4hgFTgu82qjucihm8QVYcWinXkuBxAVFOfXN3eVX2v04PHrN-yS_DS2QX-ppIe3mJu3Iw9MU/s1600/demo.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="320" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnCrVZer-37d_aldXRyT6ttHLZbPj6ImSaybYSj7S05Sj1ZEVBpz6WmPuZa9WCjnctisYm4hgFTgu82qjucihm8QVYcWinXkuBxAVFOfXN3eVX2v04PHrN-yS_DS2QX-ppIe3mJu3Iw9MU/s320/demo.png" /></a></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg0VoZIR1BEloYLAhpofxWXH94jVUN_b9RVW55uk98mT1ic-cj76wK72mcR6Q8NUEiVPbZHz_3gs_3OgMDtwq7Mixn5z7xHbaRATwjMRf1f7Vc4DKyQDiLvNTYLuRKuZmg-pbj8IuDJrioh/s1600/spiral1.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="320" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg0VoZIR1BEloYLAhpofxWXH94jVUN_b9RVW55uk98mT1ic-cj76wK72mcR6Q8NUEiVPbZHz_3gs_3OgMDtwq7Mixn5z7xHbaRATwjMRf1f7Vc4DKyQDiLvNTYLuRKuZmg-pbj8IuDJrioh/s320/spiral1.png" /></a></div><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgs-PUd1gycK2uwdDtzCM7yWDF6vcW7NkucG3XcPYTNTIaB6cFLWl3nDR3tvktq1zYg7WZFs3DAF-1VOtKihoxWaEmkHfKs-ulM7fyQ84X8KCFf-6Pi_UjuCytSzEwa1Qb0hFuESPSqlOhl/s1600/spheres3.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="320" width="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgs-PUd1gycK2uwdDtzCM7yWDF6vcW7NkucG3XcPYTNTIaB6cFLWl3nDR3tvktq1zYg7WZFs3DAF-1VOtKihoxWaEmkHfKs-ulM7fyQ84X8KCFf-6Pi_UjuCytSzEwa1Qb0hFuESPSqlOhl/s320/spheres3.png" /></a></div><br />
<br />
<br />
<br />
Code is available here: <a href="https://github.com/kototama/ansicommonlisp-book-clojure/tree/master/src/acl/ch09/raytracing">GitHub Kototama</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7938563989400397004.post-87983210840722715722010-12-07T13:50:00.000-08:002011-05-06T02:58:21.656-07:00when-let maybe?In this post we will see how to incrementally develop a macro similar to <a href="http://clojuredocs.org/clojure_core/clojure.core/when-let">when-let </a>but more flexible. <br />
<br />
<br />
When-let is useful to both bind one variable and do a test on the bind value in one operation. One common usage is:<br />
<br />
<pre class="brush: clojure" name="code">(when-let [something (get-something arg1 arg2)]
(do-stuff something))</pre><br />
<br />
This is equivalent to this code:<br />
<br />
<pre class="brush: clojure" name="code">(let [something (get-something arg1 arg2)]
(when something
(do-stuff something)))
</pre><br />
but with a more concise form.<br />
<br />
When-let only <b>executes the code</b> after the binding if the value assigned in the let form is logically true, that is <b>only if the value is not nil or false</b>. In our example, this means that if <i>get-something</i> returns false then <i>do-stuff</i> will not be executed. Sometimes this is not enough and we want to execute the code even for false values. For instance if we are getting our data from a database and false values are acceptable but nil values are not, or if our functions return nil on error. <br />
<br />
We could define a when-nlet macro which does what when-let does but executes the body whenever the binded value is not nil. By spying the code from <a href="https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L1625">clojure.core</a> we obtain:<br />
<br />
<pre class="brush: clojure" name="code">(defmacro when-nlet [bindings & body]
(when (not= (count bindings) 2)
(throw (IllegalArgumentException.
"when-nlet requires an even number of forms in binding vector")))
(let [form (bindings 0)
tst (bindings 1)]
`(let [temp# ~tst]
(when (not (nil? temp#))
(let [~form temp#]
~@body)))))
</pre><br />
This is fine. But what if we need multiple values to be bound and multiple checks on them?<br />
<br />
We could write:<br />
<br />
<pre class="brush: clojure" name="code">(when-nlet [val1 (get-something arg1 arg2)]
(when-nlet [val2 (get-something2 val1)]
(when-nlet [val3 (get-something3 val2]
(do-stuff val1 val2 val3))))
</pre><br />
This is not satisfying. What about writing a when-nlet* macro that does multiple binds? <br />
<br />
We could call it like that:<br />
<br />
<pre class="brush: clojure" name="code">(when-nlet* [val1 (get-something arg1 arg2)
val2 (get-something2 val1)
val3 (get-something3 val2)]
(do-stuff val1 val2 val3))
</pre><br />
and it would produce multiple calls to when-nlet.<br />
<br />
Here it is:<br />
<br />
<pre class="brush: clojure" name="code">(defmacro when-nlet* [bindings & body]
(when (not (even? (count bindings)))
(throw (IllegalArgumentException.
"when-nlet* requires an even number of forms in binding vector")))
(let [whenlets (reduce (fn [sexpr bind]
(let [form (first bind)
tst (second bind)]
(conj sexpr `(when-nlet [~form ~tst]))))
()
(partition 2 bindings))
body (cons 'do body)]
`(->> ~body ~@whenlets)))
</pre><br />
After the reduce the <i>whenlets</i> variable is assigned this list (we can see it by playing with macroexpand, macroexpand-1 and prn at the REPL): <br />
<br />
<pre class="brush: clojure" name="code">((when-nlet [val3 (get-something3 val2)]) (when-nlet [val2 (get-something2 val1)]) (when-nlet [val1 (get-something arg1 arg2)]))
</pre><br />
We then thread the body inside the <i>when-nlets</i> forms with the powerful <a href="http://clojuredocs.org/clojure_core/clojure.core/-%3E%3E">->></a> macro. We obtain:<br />
<br />
<pre class="brush: clojure" name="code">(when-nlet [val1 (get-something arg1 arg2)]
(when-nlet [val2 (get-something2 val1)]
(when-nlet [val3 (get-something3 val2)]
(do (do-stuff val1 val2 val3)))))
</pre><br />
So basically what we have done is creating a macro that does multiple binds, stops after the first bind returning a nil value and executes its body if no nil value has been encountered. It is nice and it shows us how much powerful Clojure is but... if we read this <a href="http://onclojure.com/2009/03/05/a-monad-tutorial-for-clojure-programmers-part-1/">tutorial</a> on how to use <a href="http://min.us/mbv5B0RWqYQTcI">monads</a> in Clojure we quickly see that there is a simpler way to do the same thing with the maybe monad!<br />
<br />
<pre class="brush: clojure" name="code">(domonad maybe-m [val1 (get-something "a" "b")
val2 (get-something2 val1)
val3 (get-somnil val2)]
(do-stuff val1 val2 val3))
</pre><br />
This code is equivalent to our usage of when-nlet*. Thus, if we still feel the need for our when-nlet* macro, we could write it simply like that (after :using <a href="http://richhickey.github.com/clojure-contrib/monads-api.html">clojure.contrib.monads</a>):<br />
<br />
<pre class="brush: clojure" name="code">(defmacro when-nlet* [binding & body]
(let [body (cons 'do body)]
`(domonad maybe-m ~binding ~body)))
</pre><br />
Is that not much better?<br />
<br />
Conclusion: we shall not write macros before learning more about monads ;-) !Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-7938563989400397004.post-38494782123880375312010-11-13T09:06:00.000-08:002011-05-06T02:58:21.657-07:00How to build a GUI with NetBeans and ClojureIn this post we show how to create a simple GUI with the powerful Swing GUI builder of NetBeans, use it from Clojure and deliver it as a self-executable JAR. The application is a text generator similar to the Henley program of the chapter 8 of <a href="http://paulgraham.com/acl.html">Ansi Common Lisp</a> by Paul Graham: it reads some input file to generate statistics and use them to generate a random text. Throughout the design of the application we emphasize on a clean separation between the presentation logic and the logic of the data model with a <a href="http://www.oracle.com/technetwork/articles/javase/mvc-136693.html">MVC </a>pattern.<br />
<br />
Here are the tools required to create and build the application:<br />
<br />
• <a href="http://www.oracle.com/technetwork/java/javase/downloads/index.html">Java 1.6</a><br />
• <a href="http://maven.apache.org/download.html">Apache Maven</a><br />
• <a href="http://netbeans.org/downloads/">NetBeans</a><br />
• <a href="https://github.com/technomancy/leiningen">Leiningen</a><br />
<br />
<br />
<h1>Creating the GUI</h1><br />
We use Leiningen as our Clojure build tool and it plays nicely with Maven, so we create a Maven project in NetBeans for the GUI. The project consists of Swing components, in our example just one JFrame. We do not write any Java code and we just use the NetBeans GUI builder to create components without any logic. The logic will be in the Clojure code. This Maven project will be a dependency of our Clojure project.<br />
<br />
First we make a new NetBeans project by clicking on <b>File/New Project.../Maven/Maven Project</b> and selects <b>Maven Quickstart Archetype </b>which is nearly an empty Maven project. We name our project <b>henleyuicomponents</b>. <a href="http://clojars.org/">Clojars</a> forces you to have lower-case JAR names, so we choose a lower-case name for our project, useful if we want to publish it later. We set the Group Id to <b>henley</b>, the version to <b>1.0.0-SNAPSHOT</b> and the package to <b>henley.uicomponents</b>.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgERK8VKMhu6Y89JlCxHm6P0VPoJTsf3t8geNVxqHEHtLuihUiwaXNj-csuy06bEbElm4z8fa7oQrbX8-wU0nHRXYoDtIvDANxu571XIWcbmtJ-m4PAbSEskXCmm8YheXWpZ9qDGNATw7bY/s1600/newproject-maveninfo.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg0LrXYXdMuXtAThrbHtz413xYh1Lynd2U2wKG7TD5FT8JOpthfEKnwSInn5WaoQMHfHDZUvWeJ825ipFf1lPtCC7arbwUG-uR4LRKLlbteYSNffgiXyM-auAYn27IvemXAKbRuQTQbKYoT/s1600/newproject.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="218" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg0LrXYXdMuXtAThrbHtz413xYh1Lynd2U2wKG7TD5FT8JOpthfEKnwSInn5WaoQMHfHDZUvWeJ825ipFf1lPtCC7arbwUG-uR4LRKLlbteYSNffgiXyM-auAYn27IvemXAKbRuQTQbKYoT/s320/newproject.png" width="320" /></a><img border="0" height="212" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgERK8VKMhu6Y89JlCxHm6P0VPoJTsf3t8geNVxqHEHtLuihUiwaXNj-csuy06bEbElm4z8fa7oQrbX8-wU0nHRXYoDtIvDANxu571XIWcbmtJ-m4PAbSEskXCmm8YheXWpZ9qDGNATw7bY/s320/newproject-maveninfo.png" width="320" /></div><br />
<br />
We create a new JFrame called <b>MainFrame</b> by right-clicking on the package name in the Projects tree, and selecting "<b>JFrame Form...</b>". We then design the application with the GUI builder and make it looks like this:<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgApYyhADj-83g-CB4U8mdv43y0QLhehOW8jWk_e2EWr1_-HnfZtunQqetRc5e2DBb6CN5cejmUW3fGoWZAHD1G7rJaKOFpBEhicqb6g8XUOZf3w0b2hAZ8XUs8dznj1xgqB-naJY6iyhx-/s1600/henleygui.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="317" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgApYyhADj-83g-CB4U8mdv43y0QLhehOW8jWk_e2EWr1_-HnfZtunQqetRc5e2DBb6CN5cejmUW3fGoWZAHD1G7rJaKOFpBEhicqb6g8XUOZf3w0b2hAZ8XUs8dznj1xgqB-naJY6iyhx-/s320/henleygui.png" width="320" /></a></div><br />
For each Swing components (JButton, JText etc.) that we need to access to from our Clojure code, we <b>right-click</b> on it in the GUI builder, select "<b>Customize code</b>", rename it with a meaningful name and set its <b>Access</b> to <b>public</b>. When we are finished designing the GUI we can build it by <b>right-clicking</b> on the project name and choosing "<b>build</b>". This will invoke Maven with the command "<b>mvn install</b>". Alternatively you can go in the project directory and invokes this command with a shell. Once build, the Maven artifact is installed in your local Maven repository (in ~/.m2 on Linux for instance).<br />
<br />
We now need to connect the Swing components to our Clojure code.<br />
<br />
<h1>Wiring the components</h1><br />
We create an "henley" project with Leiningen with "<b>lein new henley</b>" with the following content for the project.clj:<br />
<br />
<pre class="brush: clojure" name="code">(defproject henley "1.0.0-SNAPSHOT"
:description "A GUI for a text generator similar to the one
in the book Ansi Common Lisp, Paul Graham"
:dependencies [[org.clojure/clojure "1.2.0"]
[org.clojure/clojure-contrib "1.2.0"]
[henley/henleyuicomponents "1.0.0-SNAPSHOT"]]
:dev-dependencies [[swank-clojure "1.2.0"]
[lein-run "1.0.0-SNAPSHOT"]]
:main henley.core
)</pre><br />
The Maven component is listed as a dependency. The <b>:main option</b> specify where the main function is located. This is necessary to create a self-executable JAR.<br />
<br />
We follow a MVC pattern where the data of the model are pushed from the controller to the view. The view consists of the Swing components in the Maven component; for our simple example it is only the JFrame. Let us see how our project is organized, here is the project tree:<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjM6xBVxXi13ObHhw75sm0Fm2_AVAfoqb2ni2Q0jWTm4MQah8O94chTYDrXzcM1yhVLAEOxAlkJivuIeEEJJS72ewXUTwsNtfy4DKdVex_b8REe9HxRxXu5GfYg7wO8NBYkzs4Y3aHzQcwa/s1600/henleytree.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjM6xBVxXi13ObHhw75sm0Fm2_AVAfoqb2ni2Q0jWTm4MQah8O94chTYDrXzcM1yhVLAEOxAlkJivuIeEEJJS72ewXUTwsNtfy4DKdVex_b8REe9HxRxXu5GfYg7wO8NBYkzs4Y3aHzQcwa/s320/henleytree.png" width="268" /></a></div><br />
<br />
<ul><li>The <b>model</b> directory contains the logic of the application, in our case one namespace and its functions to generate some text.</li>
</ul><ul><li>The <b>view</b> directory contains all the code necessary to use the Swing components. We define two protocols, <b>View</b> and <b>SwingUI</b>: they are used by the controller and allow to abstract the details of the particular graphical implementation. The View protocols is for all functions that are totally independent of Swing from the point of view of the controller. The SwingUI is for all functions that are relative to Swing, like attaching a listener. They are defined in the files <i>view.clj</i> and <i>swingui.clj</i>. The Swing components inside the Maven artifact are referenced in the <i>uicomponents.clj</i> file. <i>Application.clj</i> provides an implementation for the two protocols.</li>
</ul><ul><li>The <b>controller</b> directory contains the <i>register.clj</i> function which uses the SwingUI interface to register Swing listeners defined in <i>swing_listeners.clj</i>. These listeners can use the SwingUI interface to get some information from the Swing components, for instance the number of words defined by the user in the JText field. This is indeed their purpose: extract the information and calls the function defined in <i>handlers.clj</i>. The functions in <i>handlers.clj</i> are callbacks and do not have access to the SwingUI interface, all the relevant information has been extracted by the swing_listeners and they only access the interface through the View protocol. The function in the handlers uses the model and informs the View of any changes.</li>
</ul><br />
<h1>Developing the application logic</h1><br />
In our case the logic of the application is just the text generation, a functional translation in Clojure of the Henley program available in the book <a href="http://www.amazon.com/gp/product/0133708756?ie=UTF8&tag=comprhegel-20&linkCode=as2&camp=1789&creative=390957&creativeASIN=0133708756">ANSI Common LISP</a><img alt="" border="0" class=" pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj pvlagmomjfjeaosethrj" height="1" src="http://www.assoc-amazon.com/e/ir?t=comprhegel-20&l=as2&o=1&a=0133708756" style="border: medium none ! important; margin: 0px ! important;" width="1" />.<br />
<br />
<h1>Building and using the application</h1><br />
We build and install the Swing components with the command "<b>mvn install</b>" launched from the <b>henleyuicomponents</b> directory. We then go in the <b>henley</b> directory and call "<b>lein deps</b>" to resolve all dependencies. If we want to build a self-executable we call "<b>lein uberjar</b>" and go outside for a walk; when we are back we should have a standalone JAR. If not, we may have more success by installing <a href="https://github.com/ninjudd/cake">cake</a> and do "<b>cake uberjar</b>". The JAR can be executed with "<b>java -jar <i>jarname</i></b>". <b> </b><br />
<b>If you have a problem</b> building the JAR you can <b>comment the :main option in the project.clj</b> file and type the command "<b>lein run henley.core -main</b>" from the <b>henley</b> directory to launch the application.<br />
How to use the application? We can for instance generate a french "poem" by using the <i>baudelaire.txt</i> file in the test directory as an input file:<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh2BBYBf_MxGIp-Z9TcQM4p3ma5AxgN7l7R3kX36hR9EluURgrwNMc8Pk-Vmfw-xuxcaTs4Pxb4CM-1ZPKRRMXG8BleM1BZyihGQAdsRxJWitgQZDRFqJGg9LS50B67ERpGBiF-k-B4Ap-W/s1600/henley-example2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="314" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh2BBYBf_MxGIp-Z9TcQM4p3ma5AxgN7l7R3kX36hR9EluURgrwNMc8Pk-Vmfw-xuxcaTs4Pxb4CM-1ZPKRRMXG8BleM1BZyihGQAdsRxJWitgQZDRFqJGg9LS50B67ERpGBiF-k-B4Ap-W/s320/henley-example2.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdD_0EGmqZDz-4Fj8m9bN3xes3sWwUBth-iEz9NEVWBrZyq5HyKNLW6e0NsxgAupNzLFwwy2AADdLzgb8XGZx-n5axWbPkcLRL3nHTui4UoM9mQcR42cIgtnOVnST05ClJHmahye-8_im7/s1600/henley-example.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br />
</a></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdD_0EGmqZDz-4Fj8m9bN3xes3sWwUBth-iEz9NEVWBrZyq5HyKNLW6e0NsxgAupNzLFwwy2AADdLzgb8XGZx-n5axWbPkcLRL3nHTui4UoM9mQcR42cIgtnOVnST05ClJHmahye-8_im7/s1600/henley-example.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br />
</a></div><br />
<h1>Abstraction levels</h1><br />
We have a lot of files and two protocols just for a simple project. What kind of abstraction do they defined?<br />
<br />
<ul><li><i>uicomponents.clj</i> allows us to access the Swing components independently of the way they are defined. They could be defined with code manually, with an Eclipse project etc. We choose the NetBeans GUI builder because it is the best free Swing builder available (to the extend of our knowledge).<br />
<br />
</li>
<li>the SwingUI protocol allows the controller to access the Swing components in an implementation-independent way. If for instance the <i>Number of words </i>JText field becomes later a JSpinner this will not affect the controller: the details of the implementation are already abstracted by the protocol.<br />
<br />
</li>
<li>The callbacks defined in <i>handlers.clj</i>, which are the heart of the controller, are independent of the GUI. The GUI could be written in <a href="http://www.eclipse.org/swt/">SWT</a>: this will not affect them. At this level, the View protocol abstracts the GUI implementation.<br />
<br />
</li>
<li>By pushing data from the controller to the View, the GUI is independent of the model data. It does not matter in a simple example as ours, but it will on a bigger project.</li>
</ul><br />
<h1>Conclusion</h1><br />
We have a clean and very flexible design but with one constraint: a lot of functions are defined just to do a few operations. <b>What do you think of this design?</b> Do you see a way to simplify it without losing flexibility?<br />
<br />
<h1>Links</h1><br />
The self-executable JAR can be download <a href="https://github.com/downloads/kototama/henley/henley-1.0.0-SNAPSHOT-standalone.jar">here</a><br />
The code is available on Git: <a href="https://github.com/kototama/henley">https://github.com/kototama/henley</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7938563989400397004.post-67733594267339747762009-11-08T06:07:00.000-08:002011-05-06T02:58:21.657-07:00Tail recursion and function compositionThe chapter four of the <a href="http://www.paulgraham.com/acl.html">ANSI Common Lisp</a> book has an interesting code to insert a node in a <a href="http://en.wikipedia.org/wiki/Binary_search_tree">binary search tree (BST)</a>. The code, ported to Clojure, is:<br />
<br />
<pre class="brush: clojure" name="code">(defstruct node :elt :l :r)
(defn bst-insert [bst x comp]
(if (nil? bst)
(struct node x)
(let [elt (:elt bst)]
(if (= x elt)
bst
(if (comp x elt)
(struct node
elt
(bst-insert (:l bst) x comp)
(:r bst))
(struct node
elt
(:l bst)
(bst-insert (:r bst) x comp)))))))
</pre><br />
The function is non-destructive. Creating a BST can be done like this: <br />
<br />
<pre class="brush: clojure" name="code">(def nums (reduce (fn [acc x] (bst-insert acc x <)) nil [5 8 4 2 1 9 6 7 3]))
</pre>Obviously the function does not use a tail recursion. The value of the recursive call to <verbatim>bst-insert</verbatim> is used by the <verbatim>struct</verbatim> function. How could we transform it to have a tail recursion? We need to store on a stack the information gained while doing the recursion: the branches we have visited and the branches taken. We store the information while we go from the root to the leaf. We can then unstack and reconstruct the tree from the leave to the root. This is done in the <verbatim>bst-insert-tc</verbatim> function: <br />
<pre class="brush: clojure" name="code">(defn bst-insert-tc [bst x comp]
(loop [bst bst
acc '()]
(if (nil? bst)
(loop [tree (struct node x)
stack acc]
(let [[lr elt branch] (first stack)]
(if (empty? stack)
tree
(if (= lr :l)
(recur (struct node elt branch tree) (rest stack))
(recur (struct node elt tree branch) (rest stack))))))
(let [elt (:elt bst)]
(if (= x elt)
bst
(if (comp x elt)
(recur (:l bst) (cons [:r elt (:r bst)] acc))
(recur (:r bst) (cons [:l elt (:l bst)] acc))))))))
</pre>This approach works but is a bit naive and the second loop can be simplified by using reduce: <br />
<pre class="brush: clojure" name="code">(defn bst-insert-tc2 [bst x comp]
(loop [bst bst
acc '()]
(if (nil? bst)
(reduce (fn [tree [lr elt branch]]
(if (= lr :l)
(struct node elt branch tree)
(struct node elt tree branch)))
(struct node x)
acc)
(let [elt (:elt bst)]
(if (= x elt)
bst
(if (comp x elt)
(recur (:l bst) (cons [:r elt (:r bst)] acc))
(recur (:r bst) (cons [:l elt (:l bst)] acc))))))))
</pre>Once I had the first tail recursive version, I asked my friend <a href="http://journal.batard.info/">Yogi</a> how he would transform the <verbatim>bst-insert</verbatim> code into a tail recursive version. He did find a really elegant <a href="http://journal.batard.info/post/2009/11/05/bst">solution</a>, in Haskell. Here is the idea: instead of stacking information about the tree and then performing at the end calls to reconstruct the tree in reverse order, we can build a function constructing a new tree as we go from the root to the leaf. When we are on a node, what we do is something like that (if the element to be inserted is smaller than the node's element): <br />
<pre class="brush: clojure" name="code">(struct node elt l (:r bst))
</pre>The problem is, when we are doing this operation, we do not know the value of <verbatim>l</verbatim>. <verbatim>l</verbatim> is a tree to be construct, and we can know its value only by doing a new recursive call. Since we do not know the value of it at this time, we will created an anonymous function that will be able to take this value as an argument later, when the value will be known. We thus construct anonymous functions at each level of the recursion, composing them into a unique function with <a href="http://clojure.org/api#toc151">comp</a>. Each anonymous function will return the appropriate tree for the left or right branches. At the end of the recursion, we know all the arguments. The last argument is the value of the element to be inserted. We can directly call the composed function which will create the whole tree. We do not even need to unstack anything: <br />
<pre class="brush: clojure" name="code">(defn bst-insert-tc3 [bst x cmp]
(loop [bst bst
f identity]
(if (nil? bst)
(f (struct node x))
(let [elt (:elt bst)]
(if (= x elt)
bst
(if (cmp x elt)
(recur (:l bst) (comp f (fn [l] (struct node elt l (:r bst)))))
(recur (:r bst) (comp f (fn [r] (struct node elt (:l bst) r))))))))))
</pre>The code shows how functional programming can be both elegant and efficient. <br />
The full code for the BST is available <a href="http://github.com/kototama/ansicommonlisp-book-clojure/blob/master/ch04/bst.clj"><bold>here</bold></a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7938563989400397004.post-31552850225204070482009-10-24T06:26:00.000-07:002011-05-06T02:58:21.657-07:00Dijkstra's algorithm in ClojureThe Dijkstra's algorithm is an efficient algorithm to compute the shortest path between two nodes of a directed graph with positives costs (distances). In this post we rely loosely on the <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">pseudo-code of Wikipedia</a> and on the nice illustrated example of the <a href="http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra">french version</a> to develop this algorithm in Clojure. The functions in the clojure.zip namespace will not be used.<br />
<br />
We represent the graph with a map. Keys are the nodes of the graph, values are another map mapping each child to its distance to its parent.<br />
<br />
Thus, the representation for this graph:<br />
<img src="http://dl.getdropbox.com/u/793068/blog/images/graphdijkstraone.png" alt="graph" /><br />
is:<br />
<pre name="code" class="brush: clojure">{:A {:B 85, :C 217 }, :B { :C 25 }, :C {} }
</pre><br />
Symbols (:A, :B etc.) are used to represent the nodes, but any type would be fine.<br />
<br />
We don't want our algorithms to rely on a particular graph structure so access to the graph is made via helper functions. The distance function return the distance between two nodes and the children function return a sequence containing the children for a given node.<br />
<br />
<pre name="code" class="brush: clojure">(defn distance [net nodesrc nodedst]
((net nodesrc) nodedst))
(defn children [net node]
(keys (net node)))
</pre><br />
In the Dijkstra's algorithm, nodes' distances to the initial node are progressively updated and the predecessor of a node, for its known shortest distance, is updated. We take the same approach but we don't store distances with a value of infinity, i.e. the distances to the initial node for nodes not yet explored are not kept. We call "root" the initial node in our code, and "rdistance" the distance to the root for a given node.<br />
<br />
The rdistances are stored in a sorted map, rdists. Each rdistance is mapped to another map mapping each node to their predecessor for this rdistance. This allow to efficiently implement the <pre class="code">u := vertex in Q with smallest dist[]</pre>operation describe in the pseudo-code: we just need to take the first element of the map. Once the smallest rdistance is found, we removed it from the map to save space. How do we keep the rdistance of a node if rdistances are removed from the rdists map? Predecessors and rdistances are kept together in the preds map. Rdists is only used for newly discovered rdistances. Note that with this scheme we don't need a Q set like in the pseudo-code, rdists acting like a one. When rdists is empty, that mean we have explored all reachable nodes.<br />
<br />
When the node with the smallest rdistance has been found, we need to update the rdistances of its children. This is done in the update-rdists function.<br />
<br />
<pre name="code" class="brush: clojure">(defn- update-rdists [rdists preds net node dist children distance]
"return [rdists preds] updated"
(reduce (fn [acc x]
(let [curdist (+ dist (distance net node x))
prevdist (second (preds x))
nrdists (first acc)
npreds (second acc)]
(if (nil? prevdist)
[(add-rdist nrdists x node curdist) (assoc npreds x [node curdist])]
(if (< curdist prevdist)
[(add-rdist nrdists x node curdist prevdist)
(assoc npreds x [node curdist])]
[nrdists npreds]))))
[rdists preds]
(children net node)))
</pre>
When true, the condition <verbatim> (nil? prevdist) </verbatim> means that the rdistance for the currently examined node is not known, i.e. infinite. The reduce function allows us to "iterate" on each child of the node with the smallest rdistance, and to update the values of rdists and preds. They are stored together in a vector, and pass via the accumulator between each iteration.
<p>Uncommenting the printf function in the code allows us to follow the steps of the algorithm.
<pre class="code">minnode = :A preds = {:E [:A 173], :C [:A 217], :B [:A 85], :A [:A 0]} rdists ={85 {:B :A}, 173 {:E :A}, 217 {:C :A}}
</pre>For instance, the previous line means that the node with the smallest rdistance was A, then its children' rdistances were updated. The rdistance from :B is 85 and its predecessor is A, the one from :E is 173 etc. In this case rdists and preds convey nearly the same information, this is because its one of the first iteration of the algorithm. Things change after when the exploration progress.
<p>Please feel free to criticize and improve the algorithm. One idea could be to use the memoize function to cach the result of the dijkstra function.
<p><b>If you know a good test suite for graph algorithms, please post a comment.</b>
<p><b>Full code is available <a href="http://snipplr.com/view/22183/dijkstras-algorithm-in-clojure/">here</a> </b>Unknownnoreply@blogger.com2