2.1 Sk-expressions

A Skribe document is a list of expressions (Sk-expression henceforth) that are extended S-expressions [11]. An Sk-expression is:

• An atom, including a string or a number, ex: "hello world!", 42.
• A list of Sk-expressions, ex: (list "hello" (bold "world") "!")
• A text, ex: [hello ,(bold [world])!]

Atomic expressions and lists are regular Scheme expressions. A text is a sequence of characters enclosed inside square brackets. This is the sole extension to the standard Scheme reader. The bracket syntax is similar to the standard quasiquote Scheme construction, which supports complex lists by automatically quoting the components of the list. It is to be used in conjunction of the comma operator that unquotes expressions. For instance, the Scheme form:

`(compute pi = ,(* 4 (atan 1)))

is equivalent to the expression:

(list 'compute 'pi '= (* 4 (atan 1)))

which evaluates to:

(compute pi = 3.1415926535898)

The Skribe bracket form collects all the characters between the brackets in a list of characters strings. Computation inside brackets is triggered by the character sequence ",(". For instance, the text:

[text goodies: ,(bold "bold") and ,(it "italic").]

is parsed by the Skribe reader as:

(list "text goodies: " (bold "bold") "and" (it "italic") ".")

The Skribe syntax is unobtrusive, and easy to type with an editor aware of Lisp-like syntax, such as Emacs. We have designed the Skribe syntax so that it as unobtrusive as possible. We have found of premium importance to minimize the weight of meta information when authoring documents. A complex syntax would prevent use by non computer scientists. Documents expressed in Skribe are also generally shorter than their counterpart expressed in classical formatting languages. For instance, the size of the Skribe source files of this paper is about 52,500 characters long, and running it through Skribe produces 76,200 characters in LaTeX and 0 characters in HTML. Although it is somehow unfair to compare hand-written code against generated ones, these statistics hint at the compactness of Skribe documents.

2.2 Skribe, a markup language

In this section, we present how to build a document using Skribe, and we show how programming skill is not needed to write a document. In fact, non-programmer authors can view Skribe as a simple document formatting system, such as HTML, LaTeX, or nroff [14].

Skribe provides an extensive set of pre-defined markups, which roughly correspond to HTML markups. The goal of this section is to give an idea of the look and feel of this system. It will avoid the tedious presentation of an extensive enumeration of all the markups available. Interested readers can refer to the complete manual of Skribe which is available at http://www.inria.fr/mimosa/fp/Skribe.

<elmt1 att1="v1" att2="v2">
   Some text <elmt2>for the example</elmt2>
</elmt1>

(elmt1 :att1 v1 :att2 v2 [Some text ,(elmt2 [for the example])])

(document :title <sk-expr> :author <sk-expr>
  (abstract <sk-expr>)
  ...
  (include "introduction-section.skb")
  ...
  (section :title <sk-expr> 
     ...
     (subsection :title <sk-expr>)
     ...
     (subsection :title <sk-expr>)
     ...)
   ...
   (section :title <sk-expr>)
   ...
   (include "conclusion-section.skb"))

(itemize (item [A first item.])
         (item [A ,(bold "second") one.])
         (item (description
                 (item :key (bold "foo") [is a usual Lisp identifier.])
                 (item :key (bold "bar") [is another one.])))
         (item (enumerate (item "One.") 
                          (item "Two."))))

(itemize 
   (item [A reference to the subsection 
          ,(ref :subsubsection "Skribe standard library").])
   (item [A reference to a URL:
          ,(tt (ref :url (skribe-url))).])
   (item [A reference to the 
          ,(ref :figure "skribe-eval").])
   (item [A footnote 
          ,(footnote [This is a ,(Skribe) footnote.]).]))

(program :language C :file "src/C-code.c")

1: int main(int argc, char **argv) {
2:   /* A variant of a classical C program */
3:   printf("Hello, Skribe\n"); 
4:   return 0;
5: }

3.1 Skribe functions

Functions are ubiquitous in Skribe. They are the only means for defining the syntactic Skribe elements. For instance, functions are used to define convenience macros like the ones supported by most typesetting systems. In its simplest form, a macro is just a name that is expanded into, or replaced with, a text that is part of the produced document. Macros are implemented in Skribe by the means of functions that produce Sk-expressions. For instance, a macro defining the typesetting of the word "Skribe" is used all along this paper. It is defined as follows:

(define (Skribe)
   (sc "Skribe"))

It can be used in a Sk-expression such as:

[This text has been produced by ,(Skribe).]

which produces the following output:

It may also happen that a Skribe function is used in a more complex way. Instead of replacing a source expression with another, it may introduce a complex data structure, called an Sk-ast (see Section The Skribe evaluator), representing a whole document or a fragment of a document. In this case, the function plays the same role as a markup in languages such as XML or HTML. The Skribe functions implementing the standard library (see Section Skribe standard library) fall in this category.

In addition to naturally implemeting markups and macros, Skribe functions have another strength: they expose a single formalism for specifying the static, (i.e., declared as-is) and dymamic, (i.e., computed) parts of the documents. This combination is the main originality and the main strength of Skribe in which it is particularly easy to merge texts and computations for authoring documents. Moreover, because Skribe is a full-fledged programming language, arbitrarily complex computations can be easily programmed. This expressiveness is illustrated by the next example, which is inspired by the Skribe Web page. The example generates a download table that contains the name of the tar files containing the Skribe source code. The table also contains the size of each file and an estimate of its download time depending on the network speed.

This text is automatically produced by the user-defined markup directory-download. The function implementing this markup selects the files with the suffix "tar.gz" in the dir directory. It then sorts the files into decreasing alphabetic order. Using the size of these sorted files, it computes the estimated download times, which are used for filling a table with the local function file-download.

(define (directory-download dir base)
   (define (eta size speed)
      (format "~as" (/ size (* speed 10))))
   (define (file-download file)
      (let ((sz (file-size file)))
         (tr (td (tt (basename file)))
            (td (/ sz 1024) "k")
            (td (eta sz 56)) (td (eta sz 512)) (td (eta sz 10240)))))
   (table :cellspacing 1 :border 1 :frame 'border :rules 'all
      (tr (td :colspan 2) (th :colspan 3 (it "Estimated download times")))
      (tr (td) (th "size") (th "56kb") (th "512kb") (th "10mb"))
      (map file-download
           (sort (filter (lambda (x) 
                            (and (prefix? x base) (suffix? x "tar.gz")))
                         (directory->list dir))
                 string>?))))

This example illustrates the strength of a full-fledged language for authoring documents, because it relies on computations that are familiar to general purpose languages (scanning files on disk, fetching files size, etc.) that are generally unavailable in domain-specific languages.

3.2 The Skribe evaluator

In this section, we detail how source programs are evaluated to produce output documents. In particular, we present the different execution times that take place during this process.

Most documents contain self-references. Self-references are references used in a document to point to subparts of itself. These references are used for indexes, bibliographic citations, table of contents, references to figures, chapters, and so on. On the one hand, these constructions can be built-in in an authoring system or, on the other hand, they can be implemented using a general mechanism that exposes the whole document as a data structure and that supports references to itself. The latter is Skribe's solution. In the rest of this text, we refer to any computation involving self-references as document introspection or introspection.

Self-references can be forward or backward. Hence, prior to introspection, the data structure representing the whole document must be built. To support this phasing, a Skribe program evaluates in two steps: one for building the data structure and one for resolving the self-references. Further, we have found it useful to add a third pass, which is devoted to the generation of the output document. Figure 1 illustrates the three stages for evaluating a Skribe program.

Fig. 1: Evaluation stages

The first stage (named eval in Figure 1) parses the source program a builds an abstract syntax tree (henceforth AST). This stage roughly corresponds to a Scheme evaluator augmented with additional library functions. Because of its proximity with Scheme, this stage is not detailed here.

The second stage (Resolve) is presented Section Resolve. The third stage (Write) is presented Section Write.

...
(section :title "Example of references"
   (p [Other examples can be found in Section 
,(ref :section "Other examples") and in Figure
,(ref :figure "A big example").]))
...

(define (ref-section sect)
   (let ((rho (lambda (node)
                 (let ((root (ast-root node)))
                    (section-number (find-section-from-title root sect))))))
      (unresolved rho)))

(define-writer 'bold 'html
   :before (lambda (n e) (display "<b>"))
   :action (lambda (n e) (emit (markup-body n) e))
   :after (lambda (n e) (display "</b>")))

(define-writer 'bold 'html :before "<b>" :after "</b>")

(define-writer 'emph 'html
   :before "<i>" 
   :action (lambda (n e)
              (let ((ne (extend-engine e
                            (writer 'emph :before "<b>" :after "</b>"))))
                 (emit (markup-body n) ne)))
   :after "</i>")

(define-writer 'emph 'html
   :before "<i>"
   :action (letrec ((rec (lambda (b)
                            (lambda (n e)
                               (let ((ne (extend-engine e 
                                            (writer 'emph 
                                               :before (if b "</i><b>" "</b><i>")
                                               :action (rec (not b))
                                               :after (if b "</b><i>" "</i><b>")))))
                                  (emit (markup-body n) ne))))))
              (rec #t))
   :after "</i>")

3.3 Programming examples

Among the Skribe programs of Section Skribe functions, the first one illustrates how functions can be used to implement text macros. The second one shows that this single mechanism can also be used for introducing computed texts. The computations involved in these examples take place during the first stage of the evaluation of Skribe programs. In this section, we present example of computations that take place during the later stages, namely Resolve and Write stages.

+-- Introduction
+-- Skribe overview
|   +-- Sk-expressions
|   +-- Skribe, a markup language
|   |   +-- Skribe Markups
|   |   +-- Document Structure
|   |   +-- Skribe standard library
+-- Skribe, a functional authoring language
|   +-- Skribe functions
|   +-- The Skribe evaluator
|   |   +-- Resolve
|   |   +-- Write
|   +-- Programming examples
|   |   +-- User programmed self-references
|   |   +-- Blending output formats
+-- Related work
|   +-- SGML and XML
|   +-- LAML
|   +-- BRL
|   +-- Wash
+-- Conclusion and future work

(define (show-container m s f)
  (list m
        "+-- "
        (f (container-title s))
        "\n"
        (map (lambda (x) (show-container (string-append m "|   ") x it))
             (containers-in s))))

(define (show-tree t)
  (map (lambda (x) (show-container "" x underline)) (containers-in t)))

(define (my-document-toc)
   (unresolved (lambda (n) (show-tree (ast-root n)))))

(define ast 
   (itemize 
      (item [foo])
      (item (bold [bar]))))

\begin{itemize}
 \item foo
 \item {\textbf{bar}}
\end{itemize} 

<ul class="itemize"><li>foo</li>
<li><strong>bar</strong></li>
</ul>

(define (proc body procedure)
   (make-markup 'proc procedure body))

(define-writer 'proc 'base
   :action (lambda (n e)
              (output ((markup-procedure n) (markup-body n) e) e)))

(define (LATEX body)
   (proc body (lambda (n engine)
                 (with-output-to-string 
                    (lambda () (output n latex-engine))))))

(define (HTML body)
   (proc body (lambda (n engine)
                 (with-output-to-string 
                    (lambda () (output n html-engine))))))

(LATEX ast)
(HTML ast)

$<$ul class="itemize"$>$$<$li$>$foo$<$/li$>$ %
$<$li$>$$<$strong$>$bar$<$/strong$>$$<$/li$>$ %
$<$/ul$>$

(LATEX (HTML ast))

\$$<$\$ul class="itemize"\$$>$\$\$$<$\$li\$$>$\$foo\$$<$\$/li\$$>$\$ \% %
\$$<$\$li\$$>$\$\$$<$\$strong\$$>$\$bar\$$<$\$/strong\$$>$\$\$$<$\$/li\$$>$\$ \% %
\$$<$\$/ul\$$>$\$

4.1 SGML and XML

XML is a means to specify external representations for data structures [3]. It is a mere formalism for specifying grammars. XML can be used to represent texts, but this is not its only purpose. The most popular XML application for representing texts (henceforth XML texts) is XHTML (a reformulation of HTML 4.0). XML can be thought as a simplification of SGML. They both share the same goals and syntax.

The fundamental difference between XML and Skribe is that the former is not a programming language. In consequence, any processing (formating, rendering, extracting) over XML texts requires one or more external tools using different programming languages such as Java, Tcl, C, XSLT, or XQuery. Most functional programming languages have tools for handling XML texts. Haskell has HaXml [18], Caml has Px and Tony, and Scheme has SSax [7].

In addition to parsers, Scheme has also SXML [6] which is either an abstract syntax tree of an XML document or a concrete representation using S-expressions. SXML is suitable for Scheme-based XML authoring. It is a term implementation of the XML document.

The Document Style Semantics and Specification Language (DSSSL) [4] defines several programming languages for handling SGML applications. The DSSSL suite plays approximatively the same role as XML XSLT, DOM and SSAX: it enables parsing and computing over SGML documents. The DSSSL languages are based on a simplified version of Scheme.

XEXPR [20] is a scripting language that uses XML as its primary syntax. It has been defined to easily embed scripts inside XML documents, and it overcomes the usage of an external scripting language in order to process a document. The language defines itself to be "very close to a typical Lisp or combinator-based language where the primary means of programming is through functional composition." XEXPR allows the definition of functions using the <define> element. Hereafter is a definition of the factorial function expressed in XEXPR:

<define name="factorial" args="n">
 <if> <eq><n/>0</eq> 
   1
   <multiply>
    <n/>
    <factorial> <substract><n/>1</substract> </factorial>
   </multiply>
 </if>
</define>

Obviously, writing by hand large scripts seems tedious in XEXPR. Furthermore, a careful reading of the report that defines this language seems to indicate that there is no way to manipulate the document itself inside an XEXPR expression. The language seems limited, therefore, to simple text generations inside an XML document.

XQuery [21] is a functional programming language for handling XML documents. It enables a mixture of dynamic XML constructions and static XML fragments. XQuery documents mix traditional programming syntax with XML syntax. A purely static XQuery document is also a XML document. This approach minimizes the learning curve of XQuery. The factorial table (Figure 3) could be implemented in XQuery as:

define function fac ($n) {
   if ($n = 0) 
      then 1 
      else $n * fac($n - 1)
}

define function makefactrow ($n) {
   <tr>
     <td align="center">{$n}</td>
     <td align="right">{fac($n)}</td>
   </tr>   
}

define function makefacttable ($n) {
  <table border="1">{
    <tr><th>n=</th><th>fact</th></tr>,
     for $x in 1 to $n
       return makefactrow($x)
  }</table>
}

<html>
  <head><title>Factorial</title></head>
  <body><font size="-1">{makefacttable(10)}</font></body>
</html>

The example shows the two different syntaxes used in XQuery documents. This approach is the opposite of the Skribe approach, which consists in a uniform syntax for the static and dynamic parts of the document.

4.2 LAML

LAML Lisp Abstracted Markup Language [13], is an attempt to use Scheme as a markup language. It mirrors the HTML markups in Scheme. That is, for each HTML markup there is a corresponding Scheme function in LAML. For the sake of the comparison, here is a possible implementation of the factorial table given figure 3 in LAML:

(define (fact n)
  (if (= 0 n)
      1
      (* n (fact (- n 1)))))

(define (make-fact-row n)
  (tr (td 'align "center" (b (as-string n)))
      (td 'align "right"  (i (as-string (fact n))))))

(define (make-fact-table n)
  (table 'border "1"
         (thead (tr (th (b "n=")) (th (b "fact"))))
         (tbody (map make-fact-row (upto 1 n)))))

(write-html '(pp)
 (html (head (title "Factorial in LAML"))
       (body (font 'size "-1" (make-fact-table 10)))))

As one may notice, LAML and Skribe are very close. They rely on Scheme's natural syntax, and they both consider a document as a program. However, there are two important differences between them. The first difference is about the syntax. In contrast with LAML that uses the regular Scheme syntax, Skribe uses an extended syntax. As presented Section Sk-expressions, it introduces the [...] notation that, as we have shown, enables compact source texts. The second difference between Skribe and LAML is the lake a structure for representing the document in LAML. The evaluation of a LAML function call directly produces an HTML expression. For instance, the definition of the LAML em function of the previous example is:

(define (em str) (string-append "<EM>" str "</EM>"))

• LAML sources cannot produce other formats than HTML.
• It is complex to implement efficiently a LAML interpreter. As reported in [12], the LAML evaluation process allocates many strings of characters. This allocation exercises intensively the memory manager (garbage collection and memory copies). These string manipulations are totally avoided by Skribe. One Skribe markup allocates one object that is a node of the Sk-ast. This node is used until the back-end has completed the file generation. It never happens that a node or the characters it contains are duplicated. In Skribe's model, building a large text from a smaller one is done by copying a pointer to the node, which is cheaper than building large strings from copies of smaller ones.
• Introspection over a LAML document is complex. In particular, introspection must take place before the string representing an HTML expression is built. That is, it has to take place before LAML functions are called. In other words, LAML is of no help for computing on documents. LAML users have to implement their own data representation before using LAML functions.

4.3 BRL

The Beautiful Report Language BRL [10] defines itself as a database-oriented language to embed in HTML and other markups. In some extent BRL approach is very similar to the PHP one: it mixes the text and the program that form the document in the same source file. For BRL, a document is a sequence of either strings or Scheme expressions. BRL displays strings as is and evaluates Scheme expressions. To alleviate document typesetting using this conventions, BRL has introduced a new syntax for character strings: there is no need to put a quote for a string starting a file or terminating a file. Furthermore, "]" and "[" can be used to respectively open and close strings. So,

]a string[

is a valid string in BRL. The interest of this notation seems more evident in a construction such as:

<html>
   <head><title>Pi</title></head>
   <body>The value of &pi; is [(* 4 (atan 1))].</body>
</html>

where we have the Scheme expression (* 4 (atan 1)) surrounded by two strings. However, this syntax can be sometimes complex, as shown in the following excerpt from the reference manual.

[(define rowcount 
   (sql-repeat st (color) 
 ("select distinct color from favcolor 
  order by color") 
   (brl ]<li><strong> 
<a href="p2.brl?[ 
(brl-url-args brl-blank? color) 
]">[(brl-html-escape color)]</a></strong> 
[)))]

The strength of the BRL syntax is more obvious on the BRL implementation of the factorial table given figure 3:

[
(define (fact n)
   (if (= n 0)
       1
       (* n (fact (- n 1)))))

(define (make-fact-row n)
   (brl ]<tr><td align="center"><b>[n]</b></td>
         <td align="right"><it>[(fact n)]</it></td></tr>[))

(define (make-fact-table n)
   (brl ]<table border="1"><tr><th>n=</th><th>fact</th></tr>
         [(for-each make-fact-row (upto 1 n))]</table[))
]
<font size="-1">[(make-fact-table 10)]</font>

The idea of extending a standard Scheme reader for text processing has inspired the Skribe Sk-expression syntax (see Section Sk-expressions).

As XQuery, BRL mixes two syntaxes: an XML syntax for static parts and Scheme for dynamic parts. This approach is the opposite of the one chosen for Skribe. In our opinion, providing a single syntax and a single formalism for expressing static and dynamic parts of documents is more elegant. On the other hand, BRL's approach makes sense when existing HTML documents must be augmented with few computed parts.

4.4 Wash

Wash [17] is a family of embedded domain specific languages for programming Web applications. Each language is embedded in the functional language Haskell, which means that it is implemented as a combinator library. The basic idea of Wash is to build a data structure that can be rendered to HTML text. Wash and Skribe ensure the well-formedness of produced documents. In addition, thanks to the type system of the Haskell type checker, Wash can guarantee the validity of the generated HTML pages which Skribe does not. Using a Haskell interpreter it is possible with Wash to interactively create and manipulate web pages. Wash shares with Skribe the construction of a data structure representing the text to be rendered. Here is a possible implementation of the Factorial table given figure 3 in Wash:

fact n = if n == 0 
     then 1
     else n * fact (n - 1)

makeFactRow n =
  tr $ do td (A.align "center" ## b (text (show n)))
          td (A.align "right"  ## i (text (show (fact n)))

makeFactTable n =
  table $ do A.border "1"
             tr (th (text "n=") ## th (text "fact"))
             mapM makeFactRow [1..n]

factTable = 
  font $ do A.size "-1"
            makeFactTable 10

Since this syntax is only accessible to programmers, Wash provides a pre-processor named wash2hs that enables a concise syntax. With this new syntax, the Factorial table could be written:

fact n =
  if n == 0
     then 1
     else n * fact (n - 1)

makeFactRow n =
  <tr>
    <td align="center"><b> <% text (show n) %> </b></td>
    <td align="right"><i> <% text (show (fact n)) %> </i></td>
  </tr>

makeFactTable n =
  <table border="1">
    <tr> <th>n=</th> <th>fact</th> </tr>
    <% mapM makeFactRow [1..n] %>
  </table>

factTable = 
  <font size="-1"> <% makeFactTable 10 %> </font>

Wash uses the strong typing of Haskell to ensure that all produced documents are well-formed. Skribe follows a different path. by relying on dynamic type checking. Unlike Wash and XML, it is not designed for supporting static verification of documents. We have chosen to explore this path because it eases the production of dynamic texts. If the underlying language imposes a stronger typing system, the source program (that is, the user text) would be cluttered with cast operations that transform all values into strings.