Mark Biggar wrote:
Martin D Kealey wrote:
But if you have objects and nested functions, the exact inference rule
gets
a whole lot more complicated. With exceptions, threads and co-routines
it's a
nightmare. In the general case, if your language has both pure and impure
functions, proving (at compile time) that something is not impure is an
NP-complete problem.
Worse it's equivalent to the halting problem (I.e., not solvable). In
general any non-trivial
property of a program of the form "Does this program ever do ..." is
equivalent to the halting problem.
There are ways to get what you want if you're willing to trade for more
restrictiveness in the relevant contexts.
If we have a way of marking types/values and routines somehow as being pure, in
the types case marking it as consisting of just immutable values, and in the
routines case marking it as having no side effects, then we are telling the
compiler that it needs to examine these type/routine definitions and check that
all other types and routines invoked by these are also marked as being pure,
recursively down to the system-defined ones that are also marked as being pure.
Entities defined as being pure would be restricted in that they may not invoke
any other entities unless those are also defined as being pure. This may mean
that certain Perl features are off-limits to this code. For example, you can
invoke system-defined numeric or string etc operators like add, multiply,
catenate etc, but you can't invoke anything that uses external resources such as
check the current time or get a truly random number. The latter would have to
be fetched first by an impure routine and be given as a then pure value to your
pure routine to work with. Also, pure routines can't update or better yet can't
even read non-lexical variables.
If it is possible with all of Perl's flexibility to make it restrictive of
certain features' use within certain contexts, then we can make this work.
Note, I have a bunch of experience in dealing with these matters. The language
Muldis D that I designed has a lot in common with Perl ... and with SQL ... and
one of its features is that about 80-90% of the language is pure, with the
non-pure stuff being clearly separated ... generally pure is preferred, and
we're only non-pure where it makes sense to do so, such as the "main program",
interaction with users, interaction with the system clock, interaction with disk
files, with the network, with other processes, etc.
Now Perl in general would be different, with the majority of a typical Perl
program probably impure without problems, but I think it is possible and ideal
for users to be able to construct a reasonably sizeable pure sandbox of sorts
within their program, where it can be easier to get correct results without
errors and better performing auto-threading etc code by default. By allowing
certain markings and restrictions as I mention, this can work in Perl.
-- Darren Duncan
