Subject: Re: [lojban] word resolution algorithm

From: "Lionel Vidal" <[email-masked]>
Date: Sat, 30 Nov 2002 16:22:56 +0100

> Buried in my discussion with Pierre, I recalled that the word resolution
> algorithm was not proven in time to be included in CLL, though it was
> intended to be part of the baseline language definition. At the time, I
> said we could just add it into the dictionary, but the new policy does not
> specifically allow for that (though the byfy could probably include
> it). Updating and proving the word resolution algorithm would be a good
> project for one person with the sort of mathematical-proof-of-algorithm
> experience needed, and could be done independently, and a working
> algorithm could simply byfy deliberations over what could amount to a
> raft of corrections and change proposals in the orthography/morphology
> sections of the refgrammar, which has numerous sloppy wordings.

I did some work on that one year ago, though with slightly different
objectives. My idea was to use BRKWORDS.TXT as a basis for
an application project that would illustrate a teaching course in Haskell
(and would also give me an oportunity to present lojban to some patient
if not always receptive audience :-)

The main point was to implement the described algorithm, that is essentially
a backward parsing, in a single forward pass, using backtraking if needed:
this was not meant to be more computationally efficient (although it could
be, and deriving afterwards an efficient implementation from it might be
another nice project :-), but was perceived as much more natural, in the
sense that it is usually the method used by our personal carbon-based
computers in our daily language based communication (or so it seems).

Another point, which might be more interresting to you, is that, although
Haskell per-se is not a tool for "proving" algorithms, the functional
paradigms that it uses are well suited to write a weak formal description
of an algorithm, that also *is* running code, and so you get a validity
proof for free in a very practical sense.

IMO, a nice thing to do, would be to write a specification paper in the
spirit of M.P. Jones paper "Typing Haskell in Haskell", where he used some
heavilly commented Haskell code to to provide a mathematically rigorous
specification of the Haskell type system (which is, I think, more complex
than lojban words-breaking system). You can download that paper from
www.haskell.org to get an idea of what could be done.
Some knowledge of Haskell is obviously required to fully understand it, but
I think a patient lojban proficient reader could understand it very well if
it has dealt with lojban rather than with Haskell typing system.
Another language than Haskell could be used (ML, Scheme or even Prolog
come to mind), but in my experience, Haskell is the most readable for
people with no specific knowledge in algorithm formal specification.

Although I am almost sure I lost the samples of code I wrote, I still have
at hands my paper notes on the implementation. But I do not really volunteer
for the job, unless you're not in a hurry. I am really very busy now (sadly
to the point of stacking up most interresting messages of that list for
later reading), and I can not commit myself on a delay, unless
it is 3-4 months from now. (I do intend to write such a paper though).

In any cases, someone may find nonetheless my idea useful.

-- Lionel Vidal