Re: [Gnu-arch-users] new language, arch, furth, etc.

[Tom Lord]

    > From: Phil Frost <address@hidden>

    > Every time someone suggests designing a new language, somewhere a fairy
    > dies. 

That's true.

    > I think it's a law of nature that no matter how simple the needs
    > may seem now, in the end all languages evolve to be turing
    > complete.

Well, yes and no and, anyway, that's not the most useful way to look
at it.  Consider `sed' for example.  Yes, it's turing complete, but
it's almost never used as anything more than a programmable finite
state machine.  Typical implementations are "accidentally" turing
complete: their code is simple ("programmable finite state machine")
and the turing completeness comes about by virtue of adding "goto"
plus the mutable line buffer (sed's conditional branch and "hold area"
sweeten the deal but aren't necessary to make sed turing complete;
anyway, none fo these features particularly complicate the
implementation).

Does `sed' need to evolve into a more expressive language?  Sure, more
expressive string processing languages are needed (hence awk, then
perl, etc).   But there's also a clear role for the tiny, simple,
easy-to-implement sed.

A question that interests me is whether or not we can make a kind of
"spectrum" of languages:  less expressive, perhaps even not turning
complete at one end;  fully general and maximally expressive at the
other.   Ideally the simple end of the spectrum should be
implementable very easily even if the fully general end of the
spectrum can not.   And ideally, even if the less general languages
aren't, strictly speaking, subsets of the more general -- at least
they should "fit together" in clean ways so that programs in the
smaller languages can be called by programs in the more general with a
minimum of fuss.

    > Since nobody likes writing in brain****, this means they also get pretty
    > complex.

The case in hand here is a configuration langauge for version
variables, and presumably also for other configuration data in arch.

I feel safe putting an upper bound on the amount of programmability
here.  For example, I think we can impose a rule: "version variable
programs must terminate after a finite number of steps".  That's an
important rule because it means, for example, that you won't be able
to send arch into an infinite loop by misdefining some version
variables.  (Under the definition I've posted so far, version variable
programs terminate after exactly 0 steps: once the program has been
successfully parsed, execution is complete.   This will change
shortly, however.)

So I don't ever expect the configuration language to be turning
complete.   I'm interested in seeing how far it can be pushed, in
terms of expressivity and generality, within the constraint that all
programs terminate after a finite number of steps.

On the other hand, as I'll explain a few posts down the road, there
are some interesting _extensions_ to the configuration language that
_do_ make it turing complete.   These, it will turn out, have
interesting properties that make them a (potentialy) attractive way to
program some kinds of application;  they can be combined with arch in
some interesting ways.   (You'll have to wait and see.... it's a few
more posts down the road).


    > Which begs the question, why not consider using an existing language
    > now? I suggest Python because it's easilly embedded and clean. Someone
    > might suggest lua, but I don't like it for its syntax. In any case, if a
    > decent language isn't picked *now*, I fear tla will "evolve" to have
    > configuration files with a syntax like Exim. An nobody wants that.

I'm not familiar with Exim but I'm not too foolish, I think, about
language design.  If Exim provides a good example of a bad
configuration language (with lots of complicated, special-case rules
and ad hoc features) --- then no, that won't happen.  The whole point
of this exercise in the first place is to prevent that from happening.

As for why not another language:

Are you sure I'm not using another language?  Well, I am: xl is
essentially a subset of "Scheme + Some Scheme Library Code".  It
happens to be a subset that's easily implemented yet has some
interesting properties, but it is a subset of an existing language
nonetheless.

Why Scheme rather than, say, Python or Lua?  Simply because Scheme is
(in a practical way) strictly more expressive than either of those
languages.  Programs in those languages have a direct and simple
translation into "Scheme + Some Libraries".  The reverse, translating
from Scheme into Python or Lua, is not so easy.  It can be done,
certainly, just as Scheme could (in principle) be translated into
"brain****" -- but you wouldn't want to do it that way.   In the
abstract, that one-way-practical-translatability might be unimportant
but in reality, any halfway-good Scheme programmer should be able to
tell you, the programs you can write in Scheme that are hard to
translate to Python or Lua are very useful:  the extra expressiveness
pays off with practical results.

-t