From: Ben Crowell <luacrowell04@lightandmatter.com>
Reply-To: Lua list <lua@bazar2.conectiva.com.br>
To: lua@bazar2.conectiva.com.br
Subject: Turing-incomplete Lua?
Date: Tue, 30 Nov 2004 18:05:18 -0600
Is there any reasonably easy way to use Lua as a data-
description language, while disallowing the features
that make it a Turing-complete language? For instance,
Unix and the apps that run on it have traditionally had
lots and lots of configuration files, each of which had
its own idiosyncratic syntax. It would be nice to be able
to standardize them in terms of syntax. I believe MacOS X
uses XML for a lot of its config files, for instance.
However, sometimes it's nice to have a real programming
language, and XML isn't a programming language per se.
For instance, it would be nice to be able to use conditional
constructs in a config file: if the operating system is
FreeBSD, then X, else if it's Linux, ... But you probably
don't want a Turing-complete language for this purpose,
for reasons of reliability and trust; it's fundamentally
impossible for a computer program to verify or manipulate
another program written in a Turing-complete language.
This is why I'm much more willing to accept an
e-mail written in HTML (a Turing-incomplete language) than
one that contains an executable program. Another interesting
example is TeX, which is Turing-complete; spell-checkers for
TeX are always full of weird heuristics for attempting to
determine what should be spell-checked and what shouldn't,
and the problem is fundamentally impossible to solve because
of the Turing-complete nature of the language.
So if you can see what I'm getting at --- is there a way
to read a data description written in Lua, but make sure it's
sufficiently limited in what it does that we know it's
limited to a Turing-incomplete subset of Lua? A couple of
possibilities present themselves to my mind:
1. Have a separate parser that verifies that the program is
really written only in the Turing-incomplete subset. Once
this has been verified, feed the program to Lua.
2. Make a crippled version of the Lua interpreter that doesn't
support anything outside the Turing-incomplete subset.
Both of these have obvious drawbacks.
It's also not obvious to me whether there is a unique or optimal
subset of the language that should be defined. For instance,
any language is probably Turing-complete if it has (a) looping
constructs, and (b) the ability to break out of the loop based on
condition that's not known at compile time. Well, which should be
disallowed, the loops or the conditionals? Or is it possible to
allow some loops and some conditionals, but not all combinations
of them?
Maybe I should just be looking at some other language rather than Lua,
one that's purely a data description language, and Turing-incomplete
by design. The thing is, it would be really sweet IMO to have
both available: a nice Turing-complete language *and* a Turing-
incomplete subset. Working with a language that's purely meant
to be Turing-incomplete, there would always be cases where I would
find myself at a dead end: unable to do something I want to do,
because the language is Turing-incomplete. Using the e-mail analogy,
it's not that I'm *never* willing to run software written by someone
else. It's just that I have to make that decision on a case-by-case
basis.
