20121229

CL-UNIFICATION and CL-ENUMERATION doc fixes


I just fixed the docs of CL-UNIFICATION and CL-ENUMERATION.  Mostly minor fixes and copyright updates, but I took the chance to go back and have a second look at the implementations.  A couple of nice tweaks are in my personal version and I will upload them to CVS "very soon now" (yes, I know! I should switch to git or something similar).


(Cheers)

20121210

Priority Queues in CL


There is a new CDR by Ingvar Mattsson proposing the specification of a simple heap (priority queue) interface for CL: CDR 12: Generic extendable heaps for Common Lisp.
The question in this case is how to support the INCREASE-KEY (or DECREASE-KEY) operation mentioned by CLRS.  It is known that such support is application-dependent, however, it would be nice to make it explicit.
Just to show my age, about 20 years ago, I did write a priority queue implementation that is still available in the CMU AI Repository.  In that ancient implementation, a hash table was used internally to support the INCREASE-KEY/DECREASE-KEY operation and I always wondered whether there is a better interface to aid the maintenance of the heap invariants while keeping the performance guarantees.
Any suggestions?




(Cheers)

20120416

ELS 2012 Zadar, Croatia: Call for Participation

European Lisp Symposium 2012, Zadar, Croatia, April 29th - May 1st, 2012

Call for Participation.

Web site: european-lisp-symposium.org

The purpose of the European Lisp Symposium is to provide a forum for the discussion and dissemination of all aspects of design, implementation and application of any of the Lisp and Lisp-inspired dialects, including Common Lisp, Scheme, Emacs Lisp, AutoLisp, ISLISP, Dylan, Clojure, ACL2, ECMAScript, Racket, SKILL, and so on. We encourage everyone interested in Lisp to participate.

The main theme of the 2012 European Lisp Conference is "Interoperability: Systems, Libraries, Workflows". Lisp based and functional-languages based systems have grown a variety of solutions to become more and more integrated with the wider world of Information and Communication Technologies in current use. There are several dimensions to the scope of the solutions proposed, ranging from "embedding" of interpreters in C-based systems, to the development of abstractions levels that facilitate the expression of complex context dependent tasks, to the construction of exchange formats handling libraries, to the construction of theorem-provers for the "Semantic Web". The European Lisp Symposium 2012 solicits the submission of papers with this specific theme in mind, alongside the more traditional tracks which have appeared in the past editions.

Registration:

Until April 15th the registration fee will be reduced. Use the form on european-lisp-symposium.org to register.

Preliminary Program schedule:

Sunday April 29.

  • 11:00 Sea & Sun & Coffee (meeting place: The Sea organ & Greeting to the Sun)
  • 19:30 - 21:30 Welcome Cocktail at the Garden Bar

Monday April 30.

  • 8:30 - 09:00 Registration
  • 09:30 - 10:00 Welcome
  • 10:00 - 11:00 Juan Jose Garcia-Ripoll, Instituto de Física Fundamental, CSIC, Spain
  • 11:00 - 11:30 Coffee Break
  • 11:30 - 13:00 Session 1
    • 11:30 - 12:15 Laurent Senta, Christopher Chedeau and Didier Verna. Generic Image Processing with Climb
    • 12:15 - 13:00 Giovanni Anzani, An iterative method to solve overdetermined systems of nonlinear equations applied to the restitution of planimetric measurements
  • 13:00 - 15:00 Lunch Break
  • 15:00 - 16:30 Session 2
    • 15:00 - 15:45 Alessio Stalla. Java interop with ABCL, a practical example
    • 15:45 - 16:30 Nils Bertschinger. Embedded probabilistic programming in Clojure
  • 16:30 - 17:30 Pascal Costanza, ExaScience Lab, Intel, Belgium
  • 17:30 - 18:00 Lightening Talk (1)
  • 18:00 - 20:00 Buffet at the University of Zadar

Tuesday May 1.

  • 10:00 - 11:00 Ernst van Waning, Infometrics, Netherlands
  • 11:00 - 11:30 Coffee Break
  • 11:30 - 13:00 Session 3
    • 11:30 - 12:15 Marco Benelli. Scheme in Industrial Automation
    • 12:15 - 13:00 Gunnar Völkel, Johann M. Kraus and Hans A. Kestler Algorithm Engineering with Clojure
  • 13:00 - 15:00 Lunch Break
  • 15:00 - 16:30 Session 4
    • 15:00 - 15:45 Irène Anne Durand. Object enumeration
    • 15:45 - 16:30 Alessio Stalla. Doplus, the high-level, Lispy, extensible iteration construct
  • 16:30 - 17:00 Lightening Talk (2)
  • 17:00 - 18:00 Announcements & Wrap-up

Venue:

Zadar is one of the enchanting cities on the Adriatic coast rich in history. It still preserves a very old network of narrow and charming city streets, as well as a Roman forum dating back to the first century AD. In addition, Zadar region encompasses many natural beauties, most prominent among them is the Kornati National Park, the most unusual and indented set of small islands in the Mediterranean (89 islands, islets and reefs) located only 15 nautical miles south of Zadar – a visit to Kornati is planned as a part of the conference.

Accommodation:

Participants are responsible for their own accommodation arrangements. Reservations should be made directly to the hotels.

When making reservations in hotel Hotel Kolovare, please indicate that you are with ELS 2012 / University of Zadar and you will get a discount. Due to the popularity of the location in spring, an early reservations is recommended.

  • Hotel Kolovare * * * *: www.hotel-kolovare.com, +385 23 211 017, +385 203 200

Other accommodation options:

  • Hotel Bastion * * * *: www.hotel-bastion.hr, +385 23 / 494 950, info [at] hotel-bastion.hr
  • Falkenstiner Hotels & resorts – (Funimation)* * *: www.falkensteiner.com, +385 (0)23 206 400, +385 (0)23 332 065, sales.borik [at] falkensteiner.com
  • Hotel Mediteran * * *: www.hotelmediteran-zd.hr, info [at] hotelmediteran-zd.hr
  • Hotel Porto * * *: www.hotel-porto.hr, +385-(0)23-292300, hotel.porto [at] zd.t-com.hr
  • Hotel Villa Nico * * *: www.hotel-villanico.com, +385 23 331198, +385 23 331960, nico.moric [at] villanico.t-com.hr
  • Hotel President * * * *: www.hotel-president.hr, +385 23 337 500+385 (23) 333 696 , info [at] hotel-president.hr
  • Hostel Zadar: +385 331-145

20111117

European Lisp Symposium 2012, Zadar, Croatia, April 30th - May 1st, 2012

Site: http://european-lisp-symposium.org

The purpose of the European Lisp Symposium is to provide a forum for the discussion and dissemination of all aspects of design, implementation and application of any of the Lisp and Lisp-inspired dialects, including Common Lisp, Scheme, Emacs Lisp, AutoLisp, ISLISP, Dylan, Clojure, ACL2, ECMAScript, Racket, SKILL, and so on. We encourage everyone interested in Lisp to participate.

The main theme of the 2012 European Lisp Conference is "Interoperabilty: Systems, Libraries, Workflows". Lisp based and functional-languages based systems have grown a variety of solutions to become more and more integrated with the wider world of Information and Communication Technologies in current use. There are several dimensions to the scope of the solutions proposed, ranging from "embedding" of interpreters in C-based systems, to the development of abstractions levels that facilitate the expression of complex context dependent tasks, to the construction of exchange formats handling libraries, to the construction of theorem-provers for the "Semantic Web". The European Lisp Symposium 2012 solicits the submission of papers with this specific theme in mind, alongside the more traditional tracks which have appeared in the past editions.

We invite submissions in the following forms:

  • Papers: Technical papers of up to 15 pages that describe original results or explain known ideas in new and elegant ways.
  • Demonstrations: Abstracts of up to 4 pages for demonstrations of tools, libraries, and applications.
  • Tutorials: Abstracts of up to 4 pages for in-depth presentations about topics of special interest for at least 90 minutes and up to 180 minutes.
  • Lightning talks: Abstracts of up to one page for talks to last for no more than 5 minutes.

All submissions should be formatted following the ACM SIGS guidelines and include ACM classification categories and terms. For more information on the submission guidelines and the ACM keywords, see: http://www.acm.org/sigs/publications/proceedings-templates and http://www.acm.org/about/class/1998.

Important dates:

  • Jan 31st 2012: submission deadline
  • Feb 21st 2012: acceptance results
  • April 30th, 2012 Conference opens

Program Commitee:

Chair:
Marco Antoniotti, Università degli Studi di Milano Bicocca, Milan, ITALY

Local organizers:

  • Damir Ćavar, Eastern Michigan University
  • Franjo Pehar, University of Zadar
  • Damir Kero, University of Zadar

Members:

  • Giuseppe Attardi, Università degli Studi di Pisa, Pisa, ITALY
  • Pascal Costanza, Intel, Bruxelles, BELGIUM
  • Marc Feeley, Université de Montreal, Montreal, CANADA
  • Scott McKay, Google, U.S.A.
  • Kent Pitman, Hypermeta, U.S.A.
  • Christophe Rhodes, Department of Computing, Goldsmiths, University of London, London, UNITED KINGDOM
  • Robert Strandh, LABRI, Université de Bordeaux, Bordaux, FRANCE
  • Didier Verna, EPITA / LRDE, FRANCE

20111023

Mokum ECML 2011

I am in Amsterdam for the ECLM 2011 and I must say that I have a distinctive feeling that the CL world is somehow doing very well. The meeting (as many of the readers know) is by invitation and the people presenting are from actual companies. The presentations have given me a sense of solidity of the companies represented, which, in the very words of the people presenting their work, is a reflection of the goodness of the choices made both of "problem" and "technologies": Common Lisp always being in key nodes of the implementation. Many thanks to Edi Weitz and Arthur Lemmens for organizing the meeting.

(cheers)

20110616

CL-UNIFICATION system and package names aligned.

NS rightly complains here about system and package names for CL-UNIFICATION. I fixed the problem in CVS (it should take a little to propagate to Quicklisp) by adding the proper nickname to the package, i.e., "CL-UNIFICATION". My excuse is that this was a left over from a few years back when nomenclature had not been as settled. :)

20110614

Printing XHTMΛ

I finally bit the bullet! I swear I tried! I pestered people! I failed. I.e., I failed to like any of the "major" HTML-producing libraries "out there" and so I rolled up my own. In the process, I (re)learned a few things and I believe I made good use of parts of the language that are usually overlooked.

My problems with the other libraries

This section must start with an apology.

All the libraries I tried, are very fine and sophisticated pieces of software that do solve problems. Alas, myself being a rotten Lisper, I found that I "needed something different" (read: "something I wrote"). Therefore, the comments you'll read below are not to be intended as general statements about such libraries, but only as testimony of my whims.

The libraires I looked at are CL-HTTP, CL-WHO and variations of TFEB's htout and Franz htmlgen, especially in the XHTML-GENERATOR version that comes with CXML.

As I said, my idiosyncrasies with the the whole business of CL programming found problems with each of these otherwise fine libraries. More specifically, I found CL-HTTP too heavy to use just to generate HTML. One gripe I had with CL-WHO is that it did not handle pretty printing of HTML well (indentation is off in "recursive" use); more or less the same can be said of htout and htmlgen. CXML XHTML-GENERATOR is essentially a "round-trip" utilities and it makes your life quite unhappy if you are trying to use simple HTML entities like - surprise - λ and Λ.

CL-WHO, htout, htmlgen and XHTML-GENERATOR all take the approach summarized as I will compile a SExp representing "HTML" and will generate - in line - a set of specialized writing calls (yes: mostly WRITE and WRITE-STRING). (Cfr. the examples in CL-WHO documentation; .)

There is nothing wrong with this approach, but it makes the resulting library and overall implementation more monolithic and it does not leverage some of the bells and whistles that you have available in CL. Thus I rolled my own (and I called it XHTMΛ).

Yet anothern HTML generation library

My approach to HTML (or XML) generation is the following:

  1. HTML (or XML!) element need not be "lists" or "conses"; they can be bona-fide objects, i.e., structures.
  2. print-object, and, above all, the pretty printer are my friends.
  3. *print-pretty*, *print-readably* etc., are more than useful.

There are a few consequences from this choices and they should be exposed. Before doing that, let's see what happens in the basic case.

The basic definition in the implementation of XHTMΛ is the representation of a HTML (or XML!) "element". It is very simple and it does accommodate the HTML5 bits and pieces.


(defstruct (element (:constructor %element))
   (tag        nil :type symbol)
   (attributes ()  :type list)
   (content    ()  :type list))

tag is ... the tag, attributes is a p-list and content is a possibly empty list of other elements.

"Printing" an element

Let's forget a minute about the constructor and let's instead concentrate on an element "printing" process. The main entry point is a print-object method.


(defmethod print-object ((e element) (s stream))
  (let ((tag (element-tag e))
        (attributes (element-attributes e))
        (content (element-content e))
        )
    (cond (*print-pretty*
           (pprint-xhtml s e))

          (*print-readably*
           (format s "#S(~S :TAG ~S :ATTRIBUTES ~S :CONTENT ~S)"
                   (type-of e)
                   tag
                   attributes
                   content))

          (t
           ;; Format string showing-off!!!!
           (format s "<~A~{ ~A=\"~A\"~}~:[ />~;>~:*~{~S~^ ~}</~3:*~A>~]"
                   (string-downcase tag)
                   attributes
                   content
                   )
           ))
    ))

The method is rather straightforward (apart from the last format string, which does many things at once: (1) writes the attributes, (2) checks whether there is content and if not closes the tag, otherwise backs up to print it, and (3) finally it backs up again to the tag to print the proper closing element). Note that, in order to properly and nicely printing the element, if *print-pretty* is non-NIL, then the function pprint-xhtml is called.

Using the pretty printer

It may be just me, but I believe that the pretty printer is an under-used part of the CL standard. Therefore, I set out to use it heavily in order to get "properly indented" (meaning, the way I like it) (X)HTML. The function pprint-xhtml does that.


(defun pprint-xhtml (s xhtml-element)
  (declare (type stream s)
           (type element xhtml-element))
  (let ((tag (string-downcase (element-tag xhtml-element)))
        (attrs (element-attributes xhtml-element))
        (content (element-content xhtml-element))
        )
    (pprint-logical-block (s content)  ; (1)
      (pprint-logical-block (s content)  ; (2)
        (format s "<~A~@<~{~^ ~A=\"~S\"~^~_~}~:>" tag attrs)  ; (3)
      
        (when content
          (write-char #\> s)
          (pprint-newline :mandatory s)
          (format s "~{~4,0:T ~:W~_~}" content)
          ))

      (if content
          (format s "~0I</~A>" tag)
          (format s " />"))
      )))

The function requires a few explanations (of course, if you are a "pretty printer black-belt" this may be a bit boring). First of all, a display of what I want to obtain.

<body style="color: red">
    <p>
        Some text here
        <ul>
            <li>
                Line 1
            </li>
        </ul>
    </p>
</body>

This indentation may not be the best possible and there are some pitfalls, but it is better than what you get with the other libraries. But how does the function pprint-xhtml achieve this result while interacting with the pretty printing machinery?

The function pprint-xhtml uses three logical blocks. Two for the element and a third for the attributes. The logical block for the attributes is introduced in the format string using the ~@< ... ~:> directive. Note also the conditional newline ~_ in the list iteration construction ~{ ... ~}. The other two pprint-logical-block establish the fence for the whole element and for the "inside" of the same. The outer pprint-logical block serves essentially to print the closing tag (if needed) correctly indented. The "inner" pprint-logical-block just serves to provide the correct indentation for the tag and the actual element content. The pprint-newline and the indentation directive in the format string, do the rest.

Once you wrap your head around it (it did take me some time!) it is very straightforward, and very powerful.

Bells and Whistles

The pretty printing machinery offers you more control over what you can do with it. For the time being my code just uses one simple hook into the pretty printer dispatch table in order to write strings "unquoted", but, potentially, this is the machine to provide fancier element layout.

The actual "printing" of an element is controlled by a specialized macro (provisionally) called with-html-syntax which calls write with an appropriately setup :pprint-dispatch argument.

The variable *xhtml-pd* holds the modified pretty print dispatch table, which it is initialized as follows (at a minimum):


(set-pprint-dispatch 'element
                     'pprint-xhtml
                     0
                     *xhtml-pd*)

(set-pprint-dispatch 'string
                     (lambda (s xhtml-string)
                        (write-string xhtml-string s))
                     0
                     *xhtml-pd*)

This is the result:


XHTMLAMBDA 29 > (with-html-syntax (*standard-output* :print-pretty t)
                  (body (:style "color: red")
                        (p ()
                           "Some text here"
                           (ul ()
                               (li () "Line 1")))))
<body style="color: red">
    <p>
        Some text here
        <ul>
            <li>
                Line 1
            </li>
        </ul>
    </p>
</body>
<body style="color: red"><p>"Some text here" <ul><li>"Line 1"</li></ul></p></body>  ; This is value returned!

XHTMLAMBDA 30 >

XHTMΛ Syntax

As you have noted in the previous example, the syntax of a XHTMΛ elements is


   (tag attributes . content)

where each tag is implemented as a macro, which is essentially in charge of delaying the evaluation of the content plus some other massaging, mostly flattening of the content lists, this is achieved by having each macro calling a first parsing step, which generates an "intermediate" form that eventually calls the element function (see below). The following example shows a pretty standard trick:


XHTMLAMBDA 33 > (with-html-syntax (*standard-output* :print-pretty t)
                  (body (:style "color: red")
                        (p ()
                           "Some text here"
                           (ul () (loop for i below 5
                                        collect (li () (format nil "Line ~D" i)))))))
<body style="color: red">
    <p>
        Some text here
        <ul>
             <li>
                 Line 0
             </li>
             <li>
                 Line 1
             </li>
             <li>
                 Line 2
             </li>
             <li>
                 Line 3
             </li>
             <li>
                 Line 4
             </li>
        </ul>
    </p>
</body>
<body style="color: red"><p>"Some text here" <ul><li>"Line 0"</li> <li>"Line 1"</li> <li>"Line 2"</li> <li>"Line 3"</li> <li>"Line 4"</li></ul></p></body>

XHTMLAMBDA 34 >

Thus XHTMΛ is unlike most other libraries which just discriminate on the first element of a SExp, usually a keyword. XHTMΛ wants more structure and it strives to be more easily extensible through "standard" and low-level machinery, cfr., the pretty printing machinery and CLOS. As an aside, the %element constructor is there just to be called by a "factory" generic function called - you guessed it - element.

Other Syntaxes and the HTMLIZE Macro

Yet there is value in the widely used alternative SExp syntax for HTML (and XML):


  (tag . content)

or


  ((tag . attributes) . content)

In order to accommodate such syntax (and also a "keyword-based" one), XHTMΛ provides a htmlize macro which does some more rewriting from the syntax just above (termed :compact) to the "operator-and-attributes" syntax (termed :standard).


XHTMLAMBDA 39 > (htmlize
                 ((body :style "color: red")
                  (p "Some text here"
                     (ul (loop for i below 5
                                  collect (li () (format nil "Line ~D" i))))))
                 )
<body style="color: red"><p>"Some text here" <ul><li>"Line 0"</li> <li>"Line 1"</li> <li>"Line 2"</li> <li>"Line 3"</li> <li>"Line 4"</li></ul></p></body>

Availability

The XHTMΛ library will be available "very soon"™ in common-lisp.net. Stay tuned!

References

[W93] Richard C. Waters, Some Useful Lisp Algorithms: Part 2, Mitsubishi Electric Research Laboratories Technical Report 93-17, August, 1993.

[S90] Guy L. Steele Jr., Common Lisp, the Language, 2nd Edition, Digital Press, 1990.