Suppose you have a markup language that requires different lexers for different contexts (you have different verbatim environments, for instance). You can often solve this problem entirely within the lexer. This is the approach typically used for dealing with comments when parsing programming language source code, for example. What if, however, the markup language is complex enough that you need some help from the parser to know in which context you sit at any given moment, and therefore which lexer is the right one to call?

The situation above makes the familiar OCamllex (or Sedlex) + Menhir combination problematic. So much so that even if you otherwise have a strong preference for these tools and the grammar of your language is a nice fit for an LR(1) parser generator, you may be forced to adopt some scannerless parsing technique or some exotic parser generator. Nevertheless, I would like to share a couple of approaches which allow you to have your cake and eat it too. That is, perform on-the-fly lexer switching within a Ocamllex (Sedlex, actually) + Menhir framework.

The markup we want to parse is a very simplified sibling of Lambtex, supporting only paragraphs, quote environments, and two different kinds of verbatim-like environments (verbatim proper and source). Within paragraphs, only plain text, bold text, and hyperlinks are supported. Here you'll find a complete sample of our markup language. (Note that this dumbed-down Lambtex is indeed so simple that you could get away with parsing the verbatim-like environments entirely within the lexer context. You'll have to indulge me here!)

The first approach relies on Menhir's new Inspection API, which essentially allows for the current parser state to be inspected from the outside. This solution demands that Menhir be run in incremental mode, which in turn demands the use of the table-based back-end. As the Menhir manual notes, the table-based back-end is generally slower than the default code-based back-end. On the plus side, this solution does not require any hacks within the parser specification itself. It does, however, require a mildly complex Tokenizer layer between the Lexer and the Parser.

The second approach relies on a hack made practical by Menhir's ability to produce parameterised parsers, ie, parsers which are in fact OCaml functors. Suppose thus that we declared our parser to be parameterised by a module C obeying signature Context.S:

%parameter <C: Context.S>

The hack itself consists of using side-effects within the parser specification to set the current lexing context (note the set_general and set_literal rules below). The fact that the parser is parameterised allows us to contain the side-effects within each instantiation of the functor. Though the hack would also work without parser parameterisation, the resulting parser would not be reentrant and could not be safely used in a multi-threaded application. At last, note that this approach also inserts a Tokenizer layer between the Lexer and the Parser. It is however much simpler than the one required by the first approach.

block:
  | set_literal BEGIN_VERBATIM set_general TEXT END_VERBATIM  {Ast.Verbatim $4}
set_general:
  | /* empty */  {C.(set General)}
set_literal:
  | /* empty */  {C.(set Literal)}

You may have noticed the seemingly odd placement of the set_literal and set_general producers within the sole production of the block rule. These seem to be placed one position before where they should be. The reason is simple: remember that we have to take into account the lookahead token!

And that's it. Both of these approaches work and each has its advantages and disadvantages. I'm leaning towards the second approach for a cleaner reimplementation of Lambtex's current parser, though I can imagine that even hairier markups may require the extra flexibility afforded by the first approach. To conclude, note that I've been deliberately terse in explanation because the complete code is available on Github. Just bear in mind that it is littered with debug statements.

I'm happy to announce the release of version 1.0-beta3 of Lambdoc, a library providing support for semantically rich documents in web applications. Lambdoc was designed with Ocsigen/Eliom integration in mind, though you may of course use it with other frameworks (it does not actually depend on the Ocsigen server or Eliom). In fact, you may find it useful outside the web application domain altogether.

An overview of Lambdoc's features may be found in the post I wrote announcing the first beta of Lambdoc. The good news is that in the intervening months, some of the most pressing issues with the library have been fixed, and it is now much closer to completion. The bad news is that backward-incompatible changes were required. For most uses these amount to no more than a module renaming fixable by search-and-replace. The extension mechanism suffered a complete overhaul, however (more on that below), and is manifestly incompatible with the first beta. My apologies if anyone was inconvenience by this, and the caveat emptor regarding beta software remains.

Lambdoc 1.0-beta3 should hit the OPAM repos any moment now.

Salient changes since beta 1

• The module structure was reorganised, with the module packs being ditched in favour of flatter structure reliant on module aliases.
• OASIS is now used for the build system.

• Completely revamped extension mechanism. Extensions are now easily composable, and output raw AST values instead of Lambdoc_core values, allowing for greater flexibility. Within the examples directory are some illustrations of the power offered by the extension mechanism:

  • An extension that adds a banner command, which uses the SYSV banner utility to transform raw text into ASCII-art headlines.
  • An extension for inline notes, for declaring a new end-note and a reference to it with a single inlnote command.
  • An extension for embedding markups within markups. Though just a handful lines of code, this extension is enormously useful, as it allows the use of constructs only available in more expressive markups from within less expressive markups.
  • A version of Lambcmd with support for book references. This extension relies on Bookaml's facilities to implement book and bookpic commands which resolve ISBN references into links to a book page.

What to expect before a 1.0 release

Though Lambdoc is perfectly useful right now, there are still some issues to resolve before I'm willing to tag a final 1.0 release. The Markdown support, in particular, is still far from complete. Other prominent issues include #24, #28, #29, #31, #32, and #33. Fortunately, though some of these issues may require backward incompatible changes, these are pretty minor.

Acknowledgements

Massive kudos to Gabriel "Drup" Radanne and Edwin Török for their feedback and code contributions.

I'm happy to announce release 3.0 of Camlhighlight, a library offering syntax highlighting and pretty-printing facilities for displaying code samples in Ocsigen applications. The library works by interfacing with the library portion of GNU Source-highlight, a popular application supporting the most common programming and markup languages.

This version features a smaller dependency set, now requiring Tyxml instead of forcing a dependency on Eliom. However, full compatibility with Eliom applications is maintained. The functorial interface used seems hairy at first glance, but it's actually not that complicated in practice. As an example, if your application uses only Tyxml and you wish to write a syntax-highlighted sample as a Html5.elt, you will first need to apply the Camlhighlight_write_html5.Make functor using Tyxml's Html5 and Svg modules as parameter:

module Html5_writer = Camlhighlight_write_html5.Make
(struct
include Html5.M
module Svg = Svg.M
end)

Similarly, if you intend the Html5_writer module to be Eliom compatible, then use Eliom's Html5.F.Raw and Svg.F.Raw modules as parameter:

module Html5_writer = Camlhighlight_write_html5.Make
(struct
include Eliom_content.Html5.F.Raw
module Svg = Eliom_content.Svg.F.Raw
end)

The package should be hitting the OPAM repository soon. Eliom users should beware that Camlhighlight requires Tyxml >= 3.2, whereas Eliom 4.0.0 requires Tyxml < 3.2. Therefore, should you want to use Camlhighlight in an Eliom application, you are advised to install the development version of Eliom (please see the Ocsigen site for instructions regarding Ocsigen's development repo for OPAM).

I'm happy to announce version 2.0 of PG'OCaml, a library offering type-safe access to PostgreSQL databases for OCaml applications.

This version no longer depends on Batteries, which hopefully will entice more Core users to give it a spin. Below is the list of the remaining changes, straight from the changelog:

• Dario Teixeira and Jacques-Pascal Deplaix: fixing issues with arrays. This requires all array types to change from 'a array to 'a option array, which breaks backward compatibility.
• Dario Teixeira's patch making PostgreSQL's NUMERIC type be converted to/from OCaml strings. This change is not backward's compatible, requiring a bump in the major version number (though there seems to be no actual code in the wild relying on the previous behaviour).
• Dario Teixeira's patch adding function 'uuid', which exposes the unique connection handle identifier.
• Jacques-Pascal Deplaix's patches adding 'catch', 'transact', 'alive', 'inject', and 'alter' functions.

Note that a couple of changes break backward compatibility, hence the new major version number. These changes were required to fix some long-standing issues, so I trust you'll be understanding.

This new release should be hitting OPAM soon. Alternatively, you can grab the source from the project's homepage. Happy hacking!

CCSS is a preprocessor/pretty-printer for CSS (Cascading Style Sheets), extending the language with support for variables and arithmetic. Version 1.5 of is out now, and is already available in OPAM, for your convenience.

This version features support for @keyframes (CSS3 animations). And of course, you may take advantage of CCSS's variables to make your keyframe declarations easier to maintain. Consider, for example, the source below:

Inflexion_point: 50%;
@keyframes test
{
from                    {opacity: 0;}
Inflexion_point         {opacity: 0.5;}
Inflexion_point + 1%    {opacity: 0.6;}
to                      {opacity: 1;}
}

And the corresponding output from CCSS:

@keyframes test
{
from
{
opacity: 0;
}
50%
{
opacity: 0.5;
}
51%
{
opacity: 0.6;
}
to
{
opacity: 1;
}
}

This version also brings a change to the internal AST representation that though minor, is bound to raise a few eyebrows, and thus requires a brief explanation. In CSS, the @charset at-rule is special in the sense that if present, it may only appear at the very start of the file. In previous versions, CCSS's AST encoded this requirement by treating @charset differently than other at-rules. In this new version, this is no longer the case. The end result is a cleaner and more concise AST, but it does mean that CCSS will now accepted @charset statements beyond the start of the file.

Before you cry "regression", bear in mind that CCSS was never meant to be a standards compliant CSS parser nor a CSS lint. The tool will happily accept semantically meaningless CSS while simultaneously rejecting perfectly valid CSS (it requires declaration blocks to always be terminated by a semicolon, for example, which the standard does not). Therefore, making CCSS slightly less standards-compliant is a viable option if the upside is a simpler, saner, and easier to maintain grammar. Having said that, in practice you won't find many incompatibilities, and I'll happily fix any egregious ones.

OCaml-bitcoin is a library offering an OCaml interface to the original Bitcoin client API. It is a small and straightforward library, whose announcement would normally warrant nothing more than a quick post on the caml-list. However, given the controversy surrounding Bitcoin and my own conflicted view on the subject, I reckon some extra words are in order.

The problem with Bitcoin

TL;DR: it's the deflation thing.

Economics is still, at best, a protoscience. This remark is not meant to be snarky or dismissive of the entire discipline, however. Quite on the contrary — it is simply the acknowledgement that grounding Economics on the great edifice of science is a tremendously complex effort, which in all likelihood will require several more decades before the prefix proto even begins to lose its relevance. There are two main factors at play. First, the foundation upon which Economics must be grounded — Psychology — is also still in the early stages of shedding its own proto prefix. Second, one must consider the enormous difficulty of conducting controlled experiments in Economics, particularly as the scale moves into the realm of Macroeconomics.

Take for example the seemingly simple problem of determining whether an electronic commodity with a fixed and finite supply can function as a viable currency — the Bitcoin problem, essentially. Some decades from now (for sufficiently large values of "some"), Behavioural economics will have developed to the point that we are able to construct a highly sophisticated simulated human that models actual human economic behaviour to a close degree, and we should also have the computing power to simulate the interaction of many millions of these "individuals". With such a tool in hand we will be able to grasp all manners of emergent phenomena that arise in an economy under different currency regimes. The Bitcoin problem and all its variations will become experimentally testable, and the current bickering over the feasibility of Bitcoin should become a settled matter.

We are very far from the sci-fi scenario described above, however, which is mostly why there are several different schools of economic thought with often diametrically opposed predictions and solutions (perhaps I'm being overly charitable towards economists as a class, though; I reckon their most significant disagreements have more to do with the blinders of ideology than the genuine fog of a protoscience). Personally, I find that the most compelling argument is made by those who argue against the viability of a deflationary currency. The reasoning is fairly simple: suppose Bitcoin starts to gain some traction, and becomes useful beyond the need to buy Alpaca socks. Being limited in supply, one should expect Bitcoins to increase sharply in value. However, Bitcoins are more than just run-of-the-mill scarce, as total production is hard-capped at about 21 million coins (a number which should be reached around 2140, though close to 90% of those coins will be generated before this decade is out). Moreover, once attrition is factored in, the number of usable Bitcoins will even slowly decrease from a maximum. Now, if you have in hands a commodity which is increasing in value and has a fixed supply, you could not be faulted for guessing its value can only continue to rise, and therefore you would choose to hold on to your Bitcoins instead of spending them. In addition, this commodity becomes an attractive choice for speculation — people will acquire Bitcoins for the sole purpose of later selling them at a higher price, without any intention of actually spending them to buy goods or services. To give a concrete example, suppose you have acquired some Bitcoins and find yourself in a future where Bitcoin is gaining traction and increasing in value. Furthermore, you intend to purchase socks from some website offering either Bitcoins or Euros as payment options. Which would you choose? I reckon most people would opt to spend the currency that slowly decreases in value (the Euro) over the one that is gaining value every day.

Why is the above scenario a bad thing for Bitcoin? First, because if people are stashing Bitcoins under the mattress instead of actually using them as the preferred means of payment on the Internet, then Bitcoin will have failed one its primary goals, that of revolutionising online payments. I realise there may be some for whom Bitcoin's primary goal is instead that of providing a convenient store of value. For them, Bitcoin failing as a currency is not much of an issue, since they see Bitcoin's usefulness as a currency merely as a welcome side-effect. Besides this being a minority view (seriously, who wasn't attracted to Bitcoin primarily because of its potential as a truly revolutionary currency?), I think its premisse lies on very shaky ground. Which brings me to my second point: I think it will be impossible to dissociate Bitcoin's value from its usefulness as a currency. If people aren't actually using Bitcoins for online purchases, fewer websites will have an incentive to keep supporting it, and Bitcoin's usefulness as a currency will decrease. Moreover, a currency whose value is fast changing — even if that change is positive — is a pain to handle. The overall likely result would be a crash in confidence in Bitcoin, and consequent sudden loss in value. Obviously, supporters of Bitcoin's economic model argue against this outcome. For them, if Bitcoin's value were to start rising so fast as to endanger its usefulness as a currency, then the counteracting force would quickly nip the bubble in the bud, forcing a correction and ensuring a fairly stable valuation over time (though still slowly increasing over the long term).

At its heart, the disagreement about Bitcoin can therefore be reduced to different estimations about the nature of the forces acting to push up or bring down the value of the currency. Bitcoin supporter's argue that the forces form a negative feedback loop, and thus Bitcoin should enjoy the stability required to become a feasible currency and store of value. On the opposite corner, Bitcoin's detractors argue that once we factor in the "madness of crowds" and the human tendency towards herding behaviour, the Bitcoin system has an inherent tendency towards positive feedbacks, sudden state reversals, and therefore anything but stability. In other words, boom-bust cycles are part of the nature of deflationary currencies.

As I've already stated, I find the detractor's argument more compelling. Therefore, should Bitcoin start to get some traction and mainstream attention, I expect we will see the formation of an impressive bubble followed by a spectacular crash. Also to be expected during the ramp up stage are pronouncements that "this time is different" and the customary denials of the existence of a bubble. In many ways a repeat of the events of the Summer of 2011, but larger in size. We humans are a sorry lot.

At this point the reader may be asking, “If you really think Bitcoin has such a serious flaw, why support it at all? Moreover, you cannot fault people for construing the release of this library as a tacit endorsement, now can you?”. My answer is that the Bitcoin idea has enough potential to warrant support, even if in its current incarnation it may be doomed. Moreover, it is crucial that if Bitcoin should fail, that it fails by its own (dis)merit. The alternative — Bitcoin failing due to being outlawed, for example — would rob us of a valuable lesson in economics. Finally, I still hope that more mainstream visibility and the influx of newcomers may tip the balance of the Bitcoin community in such a way that those who take seriously the potential fatal flaw of a deflationary currency are no longer a minority.

Even if you disagree about my assessment, I hope I have at least conveyed the reason why I'm genuinely curious about the outcome of the great Bitcoin experiment, and thus why I would very much like to see it played out in full. Though I may be leaning towards the "Bitcoin cannot work" camp, I've also made clear that I'm fully aware of how difficult it is to predict the behaviour of billions of complex entities interacting with each other. In other words, it would not surprise me greatly if it turned out that I was wrong and that Bitcoin could work after all.

On the upside: Bitcoin is transparency friendly

One underappreciated advantage of Bitcoin is the transparency it enables. Suppose an organisation wanted to open its books to public scrutiny; the aim might be to give donours an assurance that any donation is in fact received, or to give tax authorities the guarantee that all income is accounted for. With Bitcoin, the organisation simply has to make public a master address through which all incoming payments are forwarded. Any donour or client can then use the blockchain to verify that their payment reached the intended destination. Similarly, tax authorities can verify compliance by making random anonymous purchases and checking whether those transactions are properly forwarded to the public master address.

The scheme outlined above does not even require that all payments use the same address (which would be an accounting nightmare). Instead, the organisation can generate a different receiving address for each transaction, with the extra provision that after a certain period (say, one day), all the coins received in that transaction would be used as inputs to another transaction whose target address is the public master address. Though this adds one extra layer of indirection, it still makes it trivial to verify that any given payment is accounted for.

(Note that the low-level control over which transaction outputs are used as inputs for new transactions is a feature introduced by the Raw Transactions API in the recently released Bitcoin 0.7. OCaml-bitcoin has full support for this new API, though users are advised to stand clear of it unless they have a good understanding of the Bitcoin system.)

To say that there is an (infantile) level of anti-tax and anti-government sentiment on the main Bitcoin Forum would be an understatement. So yes, the irony that Bitcoin could become the tax authority's best friend has not escaped me, and this is a realisation that I find most amusing.

Technical notes concerning OCaml-bitcoin

Behind the scenes, OCaml-bitcoin works by making JSON-RPC calls over the network to a running Bitcoin daemon offering the official client API. The obvious alternatives would have been to bind to a C library such as Libbitcoin, or to build in OCaml a full-blown implementation of a Bitcoin node. The former is an uncomfortable proposition until such third-party libraries have been vetted by time, whereas the latter — though without question a very interesting project which I hope someone will embark on — would have required a time investment orders of magnitude higher than what I had alloted to this side project.

Parsing and outputing JSON is handled via Yojson. For the most part, the fact that JSON-RPC is the method of interfacing with the Bitcoin client is hidden from users of OCaml-bitcoin. Ideally, it ought to be completely hidden, and the only reason it's not is because this first release does not convert all complex JSON objects into proper OCaml records. This seemed a prudent choice given that the official client's API is still in flux, but it may be fixed in a future release.

The API offered by OCaml-bitcoin is nearly identical to the original Bitcoin client API. The function names are the same, and so is the set of mandatory/optional parameters. The main difference is that a couple of calls have been split into two separate calls each. Namely, getrawtransaction is split into getrawtransaction proper and getrawtransaction_verbose, whereas getwork is split between getwork_with_data and getwork_without_data. The reason for splitting is that the original calls have very different behaviour and result depending on the presence of an optional parameter, and therefore in my opinion these should have been different calls to start with. Note that OCaml-bitcoin's API documentation includes a fairly complete description of each call, and fixes some of the mistakes and ambiguities found in the Bitcoin wiki. You may find it a useful resource even if you have no intention of using OCaml-bitcoin.

It should be noted that the official Bitcoin client parses incoming JSON-RPC calls in a brain-damaged manner. Essentially, all parameters are parsed by position, including optional parameters. This means that if you want to provide the optional parameter at position n, then you are obliged to also provide the optional parameter at position n-1, even if you are happy with the latter's default value. I tried to hide this brain damage from the OCaml-bitcoin API by internally using default values equal to those assigned by the Bitcoin client. There are however two calls where this is simply not possible: listsinceblock and signrawtransaction. If you wish to provide optional parameters to these functions make sure you obey the n requires n-1 rule, or you'll get a runtime error.

A minor rant concerning the use of floats for monetary values is also in order. Though internally the official Bitcoin client uses 64-bit integers for amounts (the integer value being the multiple of the base BTC unit, which is equal to 10 nanoBTC and informally called a "Satoshi"), the designer of the JSON-RPC API decided to convert these amounts into floats. Though there may be enough precision for this not to be much of an issue if proper care is taken, it still opens the door to improper use. Moreover, since users of the API are bound to use internally either 64-bit integers (the choice I made for OCaml-bitcoin) or some special fixed-decimal type, the floats will have to be converted back into some sensible format anyway. Therefore, the decision to choose floats for serialising BTC amounts strikes me as a poor one.

The actual communication with the Bitcoin client requires an implementation of HTTP's POST method on the OCaml side. While for many applications it would be convenient if OCaml-bitcoin were to provide a Lwt-friendly API, for others being forced to live under Lwt's monad would be an unwelcome outcome (for the purposes of this discussion, you may replace all references to "Lwt" with "Async"). For this reason, I decided not to impose any actual HTTP client implementation. Instead, the module offering the API is available as the result of a functor which takes as parameter a module implementing the basic POST method (of module type Bitcoin.HTTPCLIENT). This module must also define the monad under which the API calls are wrapped. Should no actual monad be required, then the identity monad can be declared, and thus users of the API need not be burdened by having to "live inside the monad".

For convenience sake, OCaml-bitcoin ships with two concrete implementations of Bitcoin.HTTPCLIENT. The module Bitcoin_ocamlnet is based on OCamlnet's Http_client, whereas Bitcoin_ocsigen makes use of Ocsigen's Ocsigen_http_client module. Note that this latter implementation uses the Lwt monad.

As for keeping track of connections, the usual solution is to have a function that creates a new connection handle, and have this handle be a mandatory parameter to any subsequent calls. This is not the solution used by OCaml-bitcoin. Instead, there are two different mechanisms by which you can configure the connection. First, since the module offering the API is already created via a functor, it makes sense to use this same mechanism to also indicate the connection endpoint. Obligingly, the functor that creates the API module actually takes two parameters: the previously described Bitcoin.HTTPCLIENT, and a Bitcoin.CONNECTION declaring a single value default of type conn_t option which if set defines the default connection. Second, each call accepts an optional parameter conn containing the connection endpoint information. If present, this parameter overrides any default connection, and is mandatory if no default connection was provided upon the functor invocation.

To conclude, note that the test directory contains OUnit-based unit tests. The tests are not comprehensive — the nature of the Bitcoin network requires a fairly long wait before one can be certain a transaction did occur as intended — but do cover a fair amount of important functionality. Obviously, the tests expect to be run using Bitcoin's Testnet, and will abort on startup if they find themselves being used on the main network. Just make sure you have at least a half-dozen coins on your Testnet balance, as these will be sent around (but back towards your wallet; you may lose some change due to fees, though). You can obtain Testnet coins for free from the faucet.