Lambda the Ultimate

The language machine is written in the D language. Although my code doesn't directly use binary search, I think that the (extremely useful) associative arrays in D may do things that way, so you might like to take a look at them. There's been quite a bit of discussion about them in the D language newsgroup.

The language machine provides a single notation and a single mechanism that covers an extremely wide spectrum of language activity. In particular it demonstrates that analytical grammar of the most general kind is equivalent to a kind of macro substitution that deals directly in the structures and patterns of language.

Implementing the language machine involved tackling some very interesting problems, but binary search wasn't one of them.

Probably the reason people shy away from unrestricted grammars is because it is difficult to say anything useful about them. Spend a few days writing a bigger NL parser and you will begin to see the problems that arise. I wrote a simple parser that used parts of speech and a fairly small lexicon to create parse trees for short English sentences. My target sentence was the first line of Jane Austen's Mansfield Park. My program couldn't handle the whole sentence, because it was about 50 words long, and would probably have generated parse trees until the universe died of heat death. So I cut it in half, and it happily generated 8k+ parse trees, only one of which corresponds to the most logical semantics of the sentence.

In this case, the parsing problem is very hard because the semantics are defined by the English language, which is formally very nebulous, and because I didn't want to burden my small project with any semantics at all (I wanted to see how far a purely syntactic approach would get, and I found out that it isn't very far at all). However, a more interesting language is C++, because it does have well-defined semantics, and isn't context-free. I'm fairly sure that it would be quite tedious to implement a C++ parser with The Language Machine, even though C++ compilers do it regularly (though not without great difficulty, I might add). So I wonder how useful your TLM really is, considering that CS-languages are already here and being actively used, yet not really practical to implement in your framework.

The problem is that interesting languages are *very* complicated. Making something general might let you explore very tiny subsets of such languages, but to build anything really useful, you really have to choose a specific language and build a lot of infrastructure. And that's just for CS langs. For unrestricted grammars, I don't see how you could build anything useful at all, at least not for a grammar of interesting size.

Thanks for the comment - the 'NL' parser in my example is deliberately intended as absolutely minimal and simple-minded, as a way of demonstrating the diagram - it really is not proposed as having any other purpose.

However, previous implementations of the toolkit have been used to write a translator from C to a very different high-level language, front-ends for several FORTRAN compilers, and translators for strange dialects of COBOL and an obscure 4GL database reporting language. So the beast in its previous incarnations has had some exercise.

When tackling this kind of language, one certainly uses symbol tables and other non-syntactic devices to associate identifiers with types, values, addresses and so on - that's why the language machine has associative arrays, assignments, conditionals and external interfaces. But sometimes it's very helpful to have such information reappear so that it is analysed syntactically.

The point is not to be dogmatic, but to have wide range of techniques to suit the problem in hand. One of the delightful things about writing rules in this way, is that one doesn't even notice which kind of rule one is using.

This stuff was all developed for use in real projects - it was never (for me) any kind of academic research project - it was for real, as I never had the opportunity to live in that world. But I think that there are interesting angles for academic projects to pursue.

As for parse trees, they are really an obstacle in many cases. There are certainly trees lurking in the background of the language machine, but they aren't parse trees in the usual sense of the word, and most of the time it simply isn't necessary to think in that way. As I said, it's a different route, with a quite different outlook, and in my view, more fun.

Curiously, the simple-minded ways of building a tree are pretty inefficient in a parser that may need to backtrack.

By the way, what did you use for the Jane Austen exercise?

For the NL project I used an expert system shell called CLIPS. It's a reasonably mature OSS product. It seemed a bit cute to me, and perhaps not designed for heavy lifting, but it was very handy as an academic exercise.

As far as free-form parsing goes, I am interested in a language with a rich meta-language in which it is possible to configure the language dynamically, such that programming is as much about creating appropriate DSELs as it is about writing algorithms. I am a firm believer that syntactic sugar is everything, and that if the code is aesthetically pleasing, it's more likely to be correct. If beauty can guide physics, why not computer science?

On some level, such a meta-language might possibly be constructed as a context-sensitive language. However, I am prepared to consider an unrestricted grammar if I find that context sensitivity is too restrictive. Clearly, there are a lot of thorny issues to be tackled, like how to let the programmer specify precedence/associativity, add mostly consistent grammatical constructs, etc. But I think the modern proliferation of programming languages indicates that a refactoring is clearly in order, and it must occur on the level of languages, not programs. You know what they say...any intractable problem can be solved by adding a layer of indirection. ;>

So my question to you is, do you feel that your framework would be up to the task of building such a meta-compiler?

Yes, I think one could use the language machine for building a meta-compiler.

I forgot to mention yesterday that there is a d-to-d translator among the examples on the website and in the distribution.

A d-to-d translator is not in itself particualarly useful except as a pretty printer. But I was looking a ways of integrating the D language closely with the lmn metalanguage. So I wrote a frontend that does a pretty complete analysis of structure - the context-free part I suppose. I wanted to know that it was doing the right analysis, so I addded a backend (also written as lmn rules) that would regenerate code in D, and tested it by passing the whole of the D code for the engine through it, recompiling and using the result to repeat the process. I also tested it on the source of the dmdscript javascript system (also from digital mars), to get away from my own coding style and usage. You can find the d-to-d translator here.

I make no clains for the d-to-d translator as an example of anything in particular - it's just a part of the process of investigation and testing that I decided to leave in the distribution as an example of what rules look like when written in a hurry by someone who uses short identifiers to get lots of rules on each screen.

I was quite pleased to be able to add nested alternative rules to all versions of the lmn metalanguage using just 8 rules, of which 3 merely added recognisers for additional lexical atoms. See:

nested sequences and rules - the main rule for the ...{| nested rule || alternative nested rule || ... |} ... notation

detail for nested sequences and rules - four rules to deal with nested rules with and without explicit right sides

atoms and reserved words - see the rules that recognise '{|', '||' and '|}' as lexical atoms.

By the way these are links to the web page presentation of the lmn metalanguage source as used to build the lmn metalanguage compiler - the page is generated directly from the lmn surce text, which uses mediawiki markup conventions so that preformatted material with an initial space is treated as actual source text, while everything else is treated as comment.

First - I agree about the aesthetics of programming (but others may not)

Second - at present the metalanguage operates as a normal compiler - it compiles rules to some other form for subsequent use. But the system has always been designed to be capable of being extended dynamically - that's why if two rules are equally applicable, a new rule is tried before an old rule. It's just a matter of adding a built-in extension or two - it's on my list of things to be done.

I'll go and remind myself about CLIPS - I once looked at it briefly.

By the way, I've started to organise a wiki (link from the documentation page) - it was out of action because of some snarl-up with the mysql servers, but I think it's now back. My aim was to use that for examining ideas and sample rulesets.

This page says the following which confuses me... it seems like the arrow in the second rule example should be switched around? It seems to say the same thing as the one above...

"Unrestricted rewriting rules in a generative grammar go from sequences of symbols in the grammar towards the sentences of the language - they have this overall form:

sequence-of-symbols-in-the-grammar -> sequence-nearer-the-sentences-of-the-language;

Unrestricted rewriting rules in an analytic grammar go in the opposite direction, from the sentences of the language towards sequences of symbols in the grammar:

sequence-nearer-the-sentences-of-the-language 
"

The confusion arises from the fact that in this context I read both '->' and '<-' as meaning the same thing: 'can be rewritten as'. In the language machine metalanguage I use '<-' so as to emphasise the fact that substitution injects the substitution back into the input stream for further analysis.

I see that this was confusing in that context, and so I've changed that page so that it now reads

"Unrestricted rewriting rules in a generative grammar go from sequences of symbols in the grammar towards the sentences of the language - they have this overall form:

sequence-of-symbols-in-the-grammar => sequence-nearer-the-sentences-of-the-language;

sequence-nearer-the-sentences-of-the-language => sequence-of-symbols-in-the-grammar;

where '=>' means 'can be rewritten as'"

In both cases rewriting is the central concept: as can be seen from the diagram, rewriting involves a recognition phase and a substitution phase. Recognition logically precedes generation. That may partly be why the whole idea of rewriting tends to be reduced in generative accounts of grammar to the trivial cases where just one symbol is rewritten.

But thanks, that was observant, and just the kind of thing that my familiarity with this way of thinking prevents me from seeing.

Despite some similiarities between Rats! and LM, there are also minor and major differences.

Minor difference: in LM a double-quoted string represents a single unique non-terminal symbol, not a sequence of terminal symbols.

Major difference: in the Rats! system as I understand it a 'production' tends to take the form

Type-of-semantic-value Construct '=' alternatives-that-produce-that-value ';'

In other words it is essentially a context-free grammar with a simple tree structure, but with additional mechanisms for lexical matching and semantic effect.

By contrast, the general form of a rule in LM is

sequence-to-be-matched '<-' sequence-to-be-substituted ';'

where the sequences to be matched and substituted may be of any length, may contain terminal, non-terminal and lexical class symbols, and may include variable bindings, variable declarations and side-effect actions.

Even in a very simple case, it can be surprisingly useful to be able to combine grammatical analysis and substitution. For example I needed to add a '.include' directive to the metalanguage. The lexical convention for comments is that a line that starts with a space is actual source, while anything else is a comment. The single line rule that adds this directive is:

"." 'include' dquote :X ";" <- unit { include(X); } lmn '\n';

This treats the include directive as the symbols unit lmn followed by the terminal symbol '\n'. The side-effect that does the inclusion is executed between the braces. The effect is that at the end of the subsituted sequence the analyser returns to actual input at a new level of inclusion and after dealing with the prefixed newline, which triggers rules that are applicable in any context for skipping over lines that do not start with a space.

Another case where substitution combines with analysis appears in the direct evaluation of factorials in a forward polish calculator:

 'f' x :N        <- x - '*' x :(N) 'f' x :(N - 1) ;
 'f' x :1        <- x :1;
 'f' x :0        <- x :1;

The next two rules will be tried first, as they are the most recently defined. They deal with special cases, and the rule for the value 1 is used to end the recursion.

These rules for factorial are very like the rules you would find in a functional language, with the differences that the match phase of one function can be nested within the match phase of another, the pattern matched can contain any sequence of symbols, the match process relates to the analysis of an input stream, and the whole engine operates by explicit substitution.

In other words [referring to Rats!] it is essentially a context-free grammar with a simple tree structure, but with additional mechanisms for lexical matching and semantic effect.

No, the point is exactly that it's not a context-free grammar. The way I look at it, the idea behind PEGs is to recognize that while programmers routinely use a subset of CFGs to specify languages, the main advantage of CFGs (namely, their composability) is not enjoyed by this subset. The semantics of a PEG, on the other hand, explicitly specify that the listed order of alternatives/choices is significant. There is no possibility for syntactic ambiguity since any rule will either succeed or fail in a given context--it cannot succeed in multiple ways. Local ambiguity can be dealt with by employing syntactic and side-effect-free semantic predicates. Particular algorithms for parsing PEGs (such as packrat parsing, which Rats! uses) do so in linear time by employing dynamic programming in the obvious way (i.e. it uses a memoization table indexed by a (rule, token position) pair).

The main distinction I am making is between grammars in which rules (in recognition ordering) are restricted to the form

terminal-and-or-non-terminal-symbols-to-be-matched <- single-non-terminal-symbol

and grammars in which rules take the form

terminal-and-or-non-terminal-symbols-to-be-matched <- terminal-and-or-non-terminal-symbols-to-be-substituted

where there is no restriction on the number of terminal and/or non-terminal symbols on each side of a rule.

I had identified tree-structured grammars of the first kind with context free grammars, but I see that PEGs permit grammars that are essentially tree structured to go beyond context free grammars.

I have no doubt that PEGs have their own strong points and are extremely useful. My point is that there is a fundamental difference between these two approaches to grammar, and that when you think about unrestricted rewriting rules as going from the sentences towards the grammar, you enter a relatively unexplored region in which some things that always looked difficult turn out to make sense after all.

I think the most important thing your project is lacking is a compelling rationale. You need a killer example that shows why your tool is better than other more established tools. There's some vague hinting scattered all over your site, but no forceful, convincing story of how your tool slays giants and eats alien bugs for lunch.

Thanks for your kind remarks - but of course you scatter your opinions pretty wide, and some of them are bound to land somewhere.

On a more serious note. I've just waited for about an hour and a half for the ghc haskell compiler to build pugs, a compiler for perl6, which although already a bit bloated as a language cannot really warrant that effort. I took a look at parser.hs, which accounts for about 10% of about 24000 lines of haskell source in the Pugs directory alone, and frankly, I wouldn't much want to maintain it. The same applies, unfortunately, to most of the compiler source texts I've looked at.

So when you've published five metalanguage compilers that take about three minutes to rebuild themselves from a minimal bootstrap, a d-to-d translator, a web-page generator and a dozen or so examples using less than 8000 lines of metalanguage source text, I might find your remarks a bit more compelling.

My posting referred to a web page in which I use a diagram to make a close and direct connection between functional replacement and grammatical substitution. Of course I didn't attempt to arrive at a mathematical measure of the 'expressivity' of this diagram, as I thought I could probably rely on you to come up with that kind of stuff.

But if you can show me a more expressive representation of the connection between computation and grammar, this is your chance.

So when you've published five metalanguage compilers that take about three minutes to rebuild themselves from a minimal bootstrap, a d-to-d translator, a web-page generator and a dozen or so examples using less than 8000 lines of metalanguage source text, I might find your remarks a bit more compelling.

I would think that information on these projects would be prominently featured as examples of how the tool has been used in practice. I certainly would feel more motivated to examine the tool in detail after seeing that it has successfully been used in a method that is similar to something I want to work on. On the other hand, bemoaning the source of other compilers really doesn't mean anything to me if you don't provide a replacement that demonstrates improvement. Yes, compilers have icky innards. No, they are probably not all written as elegantly as they could be. But I don't really think it's a fair criticism of their source unless you also provide some kind of superior alternative. So if, for instance, you were to write a minimal Haskell parser using your framework, not only would that demonstrate the superiority of your tool, it would also provide a point of interest to a lot of people. That is, something they can directly relate to.

On the other hand, the graphical depictions of the parsing process were fine as far as a graphic design layout is concerned; but my simple brain did not find them particularly enlightening as a pedagogical tool. My problem is this: I've read a little about parsing in the context of compiler design, and I've read a little about PL theory (like lambda calculus, etc.), and your framework appears to be somewhere in that general region. However, you seem to disregard whatever formalities exist in favor of your own view on how parsing and computation ought to be done. That would be fine, but it would be more helpful if you gave a side-by-side comparison saying: "This is the traditional way to parse grammar X; this is my way. See how my way makes the process simpler?" Or even: "You wouldn't even want to try parsing this grammar, because it's not LL(k) or even context-free; but look how easy it is to do using this tool!"

The problem is one of scale. There are many ways to solve small problems, all of which look good on the small problems. But convincing people that a solution works well in the large requires a large demonstration. I think a Haskell compiler would be a great such demonstration. I think a more elegant implementation of a Haskell compiler would provide a quite compelling demonstration that your framework provides real benefits over traditional parser/compiler designs. I don't think people would even mind if you only implemented some useful subset of the language. But it would give them a handle by which to grab hold of the ideas in a way that's already familiar to them.

That was a helpful reply, for which many thanks. I have now restructured the front page, and made some other changes, and I hope that it will now be clearer what the language machine can do, and what it did in its previous incarnations.

The distinction between LL(K) and LR(K) has never been very important to me, as I have always been able to use whichever style of analysis seemed most appropriate to any particular part of a language.

Equally, it was a very early decision that parse trees are redundant and even unhelpful if you have an effective way of creating, recombining and propagating transformed representations so that they are available at any time either to modify the way input is analysed, or for output or further analysis. The structure of the analysis is reflected in the structure of variable bindings and reference scopes, but there's no need to make it explicit in the form of a parse tree unless that is in fact the strucure you want.

I do take your point about creating relevant examples - and that's why I have been looking at perl6, where there is a great deal of activity. My feeling about the source of the pugs parser was mainly that it did not suggest that haskell was providing much help, and the extreme slowness of the ghc compiler (which itself is written in haskell) confirmed the impression. I think that in general 'icky innards' result to a large extent from conlict between the tools and the task.

The motto for free software is 'release early, release often' - I dithered for some time before plunging back into this stuff - implementing the engine and redesigning and bootstrapping the metalanguage can be pretty hard work. So there are lots of things I would have liked to have finished before ever releasing a line.

I've been in fact thinking more along the lines of creating lots of small tools, sometimes embedding the engine in other languages, not because the engine can't deal with large problems, but because I think that the space between the awk-perl-python-ruby world and fully-fledged heavyweight compiler projects is one where a lot of time and effort is spent learning the hard way how just how tricky language can be. The idea is to have tools and ideas that you can just pick up and use straight 'out of the box'.

But one of the reasons for publishing was to see just where it would go, and help it along, 'in the hope that it will be useful'.

As for the pictures - they really are much more than design.

I've added another image to the picturebook to show how variables, bindings and variable reference scopes relate to the lm-diagram.

In doing this I realised that my comments about parse trees were incomplete. It's not only that I found that they were unhelpful, but also that once you allow the substitution phase of a rule to produce more than one symbol, you get the overlapping and interlocking structures that you see in the lm-diagram, and there is no way that a single parse tree can represent them.

That's why it was so useful to discover that I could use what I call the ghost of the parse tree to make sense of variable references even when they occur in substitution phases which nest in counterpoint to and out of phase with the nesting structure of recognition phases.

I hope that helps.

I am the kind of person who will probably never fully grok using the Language Machine (as in, I would have to study a lot to learn all about parsing etc.), but I'm still interested in learning from the picturebook!

My feedback so far is that I find the horizontal nature of the pictures to be kind of 'busy' and I think hard to follow. Might the vertical reprsentation be more clear?

Thanks for your work!

The original format was the horizontal one - I think I must have had immense amounts of old mainframe core dump printouts that the children hadn't yet scribbled on. I only recently started to use the veritcal format when I first implemented the diagram output feature in the current implementation.

I think in many ways I agree with you - but I still tend to use the horizontal form where I want to get a lot into one image, and I think it these cases it's likely to look busy whatever I do.

As for not grokking the Language Machine until you've learnt about parsing, I sometimes think it's the other way round - if you do learn about parsing the 'proper' way, you have to unlearn a certain amount to grok the Language Machine.

I've put together very small ruleset for turning assignments and expressions into a lispy brackety format, with notes that try to explain what's going on. If you have managed to install the software, you could try changing it. I don't think I've ever understood anything in computing until I've actually tried it. The text of the ruleset is here - I use kde's kate as editor, with word-wrap so that the annotation comes out looking reasonable.

Also I find that almost any kind of syntax highlighting mode helps - I seem to be highlighting it as if it were ruby just now.

In any case thanks for your positive comments - that's always very encouraging.

If you look at the output that the language machine generates in this kind of case, you will see that it does come out nested on the right- (substitution) side as shown in the diagram that puzzles you.

It is true that where just one symbol is substituted, that is not strictly necessary. The reason that it comes out like that is that the engine treats substitution of one symbol as not particularly different from substitution of many symbols. The substitution phase can't advance until the symbol it produced has been matched. In these cases, matching a symbol causes a new level of substitution to be started, and this happens before the existing level can exit. Substitution of just one symbol is a special case, and it could be optimised. But if you consider the overlap that occurs in left-recursive rules, and then think about trying alternative left-recursive rules, you will see that this is potentially a tricky area to tinker in.

Also it is fairly rare for a rule to produce just one symbol and nothing else - rules are usually being used to acquire, recombine and propagate fragments of a transformed representation. So rules tend to look something like this

 one damn thing :X after another :Y
  <- thing :{ doSomethingWith X andWith Y };

and in that case the right-side certainly contributes just one symbol to the grammatical analysis, but it also contributes something to a transformed representation that is being constructed from the analysis.

Incidentally, I've modified the grok examples again - now there's also a new version of the translator in which a few small changes and 5 additional code generator rules produce code in a 3-address notation, allocating registers as necessary:

 [user@machine web]$ ./grokreg.lm
 a = x = b + c / (x - 5) * (p * q - z);
  sub %r4 x 5
  div %r3 c %r4
  mul %r6 p q
  sub %r5 %r6 z
  mul %r2 %r3 %r5
  add %r1 b %r2
  sto %r1 x
  sto %r1 a

I think it's quite a good demonstration of how useful it is to be able to substitute more than one symbol.