Hi all,
Is there a way to get Lisp to output data about its own runtime
environment?
I want to write a function that can show that a given function does
not have any side-effects (or if so what they are) by checking the
state of the world before and after a run and doing some sort of diff.
I would suspect that this has already been implemented but I can't
find any information online.
Deech
From: Kent M Pitman
Subject: Re: Getting Lisp to reflect on its own environment
Date:
Message-ID: <uzluh643v.fsf@nhplace.com>
deech <············@gmail.com> writes:
> I want to write a function that can show that a given function does
> not have any side-effects (or if so what they are) by checking the
> state of the world before and after a run and doing some sort of diff.
This is like writing a function to show that a speech has no ill effects
(or that a lecture has only positive effects) on its audience by recording
the state of the audience going in and the state of the audience going out.
The problem is that the world, and to some extent the Lisp world, is
not something that's easy to finitely enumerate. The best thing you
could do would be to take a core dump before and after and then
compare them, but since the core dump after would reflect that the
program state before was about to run the test, or would reflect that
the program state after was about to do a comparison, you can see that
the state necessarily does change. It's a question of what counts as
change and what does not. And that's an exercise in philosophy at
that point--something that is different, and yet the same... or the
same, and yet different. Some degree of subjectiveness might be said to
be required.
Or, you might look at it this way: The problem is in the question, not
the answer. The evidence that there's a problem is all there in what
you asked: If you had world state that didn't know the program itself,
then the program can act capriciously, as Pascal's example has shown.
If you had a function that could deterministically examine the state
of the world including its own state and that could do something
different based on certain underestanding of that state, then that
function could deliberately make a different decision than what the
entire state of the program environment dictates it must make, because
it can basically look at its own future and decide to act in
contradiction with it. This is the basis of the dilemma which is the
halting problem.
> I would suspect that this has already been implemented but I can't
> find any information online.
You're right that it's been thought of. But the reason it's not implemented
is that there are proofs that it cannot be. ;)
deech wrote:
> Hi all,
> Is there a way to get Lisp to output data about its own runtime
> environment?
>
> I want to write a function that can show that a given function does
> not have any side-effects (or if so what they are) by checking the
> state of the world before and after a run and doing some sort of diff.
>
> I would suspect that this has already been implemented but I can't
> find any information online.
That won't help you: You can't find out whether a function is free of
side effects just by having one (or a few) sample runs.
Consider:
(defvar *x* 0)
(defun test (x)
(if (> x 10)
(1+ x)
(incf *x* x)))
For some arguments, test doesn't have side effects, whereas for others,
it does. What's worse, it's not clear whether test should be considered
to have side effects or not when you pass 0 to it.
Analyzing the code of a function doesn't help you either, because you
would first have to solve to halting problem.
What do you need this test for?
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Feb 3, 1:46 pm, Pascal Costanza <····@p-cos.net> wrote:
> deech wrote:
> > Hi all,
> > Is there a way to get Lisp to output data about its own runtime
> > environment?
>
> > I want to write a function that can show that a given function does
> > not have any side-effects (or if so what they are) by checking the
> > state of the world before and after a run and doing some sort of diff.
>
> > I would suspect that this has already been implemented but I can't
> > find any information online.
>
> That won't help you: You can't find out whether a function is free of
> side effects just by having one (or a few) sample runs.
>
> Consider:
>
> (defvar *x* 0)
>
> (defun test (x)
> (if (> x 10)
> (1+ x)
> (incf *x* x)))
>
> For some arguments, test doesn't have side effects, whereas for others,
> it does. What's worse, it's not clear whether test should be considered
> to have side effects or not when you pass 0 to it.
>
> Analyzing the code of a function doesn't help you either, because you
> would first have to solve to halting problem.
>
> What do you need this test for?
>
> Pascal
>
> --
> 1st European Lisp Symposium (ELS'08)http://prog.vub.ac.be/~pcostanza/els08/
>
> My website:http://p-cos.net
> Common Lisp Document Repository:http://cdr.eurolisp.org
> Closer to MOP & ContextL:http://common-lisp.net/project/closer/
Yikes! I didn't realize what I asked!
I wanted to create a gui that can be manipulated using user defined
functions. For example if my GUI consists of widget A B C and a text-
box. Widget A currently has '1'. I want to user to be able to write a
(lambda (x ..) ....) into the text-box that listens to A, add one and
output to B on-the-fly. But I want to be safe so my program approves
the user-defined function only if running (lambda (x ..) ...) does not
manipulate Widget C (and whatever other global variables etc).
But I had not thought of the scenario you presented.
Thanks for your quick response.
Deech
P� Sun, 03 Feb 2008 21:13:50 +0100, skrev deech <············@gmail.com>:
>
> Yikes! I didn't realize what I asked!
>
> I wanted to create a gui that can be manipulated using user defined
> functions. For example if my GUI consists of widget A B C and a text-
> box. Widget A currently has '1'. I want to user to be able to write a
> (lambda (x ..) ....) into the text-box that listens to A, add one and
> output to B on-the-fly. But I want to be safe so my program approves
> the user-defined function only if running (lambda (x ..) ...) does not
> manipulate Widget C (and whatever other global variables etc).
>
> But I had not thought of the scenario you presented.
>
> Thanks for your quick response.
>
> Deech
There is no general way to anticipate all ways to abuse a general purpose
language.
As such it might be better to define a sub language and use that.
Then you CAN control exactly what it sees and is allowed to do.
(If you choose to use the lisp reader remember to set *read-eval* to nil)
--------------
John Thingstad
deech wrote:
> I wanted to create a gui that can be manipulated using user defined
> functions. For example if my GUI consists of widget A B C and a text-
> box. Widget A currently has '1'. I want to user to be able to write a
> (lambda (x ..) ....) into the text-box that listens to A, add one and
> output to B on-the-fly. But I want to be safe so my program approves
> the user-defined function only if running (lambda (x ..) ...) does not
> manipulate Widget C (and whatever other global variables etc).
>
> But I had not thought of the scenario you presented.
Well, what you may be possible is to reuse ACL2: It defines a subset of
Common Lisp that is free of side effects. It's not designed to be used
in such a scenario, so I don't know how much work it would be to
integrate it, though.
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Feb 4, 12:28 am, Pascal Costanza <····@p-cos.net> wrote:
> deech wrote:
> > I wanted to create a gui that can be manipulated using user defined
> > functions. For example if my GUI consists of widget A B C and a text-
> > box. Widget A currently has '1'. I want to user to be able to write a
> > (lambda (x ..) ....) into the text-box that listens to A, add one and
> > output to B on-the-fly. But I want to be safe so my program approves
> > the user-defined function only if running (lambda (x ..) ...) does not
> > manipulate Widget C (and whatever other global variables etc).
>
> > But I had not thought of the scenario you presented.
>
> Well, what you may be possible is to reuse ACL2: It defines a subset of
> Common Lisp that is free of side effects. It's not designed to be used
> in such a scenario, so I don't know how much work it would be to
> integrate it, though.
Thanks for the link Pascal but ACL2 is under GPL.
Is there any other side effect free subset that is under more liberal
license?
cheers
Slobodan
http://tourdelisp.blogspot.com/
P� Mon, 04 Feb 2008 00:28:45 +0100, skrev Pascal Costanza <··@p-cos.net>:
>
> Well, what you may be possible is to reuse ACL2: It defines a subset of
> Common Lisp that is free of side effects. It's not designed to be used
> in such a scenario, so I don't know how much work it would be to
> integrate it, though.
>
>
> Pascal
>
Maybe.. but ACL2 is a program to verify a programs correctness. The
functional Lisp subset is just one side of it's abillity. Seems a bit
heavy handed.
That said ACL2 is worth studying in it's own right :)
(Thinking of appliying it to a (Lisp based) Prolog inference engine.)
--------------
John Thingstad
Pascal Costanza schrieb:
> Analyzing the code of a function doesn't help you either, because you
> would first have to solve to halting problem.
In principle analyzing the code of a function could be the most promising
thing that he can do. If he is doing it right this code analyzer can
at least come to the same results to which a human expert would come.
But as it would be automized and computers are getting faster his
program could in principle outperform humans.
The halting problem only states that programs exist about which humans
can't tell whether they will halt or not.
--
Andr�
Andr� Thieme wrote:
> Pascal Costanza schrieb:
>
>> Analyzing the code of a function doesn't help you either, because you
>> would first have to solve to halting problem.
>
> In principle analyzing the code of a function could be the most promising
> thing that he can do. If he is doing it right this code analyzer can
> at least come to the same results to which a human expert would come.
> But as it would be automized and computers are getting faster his
> program could in principle outperform humans.
> The halting problem only states that programs exist about which humans
> can't tell whether they will halt or not.
Yes, but determining other characteristics of the eventual behavior of a
function is at least as hard as the halting problem, due to Rice's
theorem. So your assumption that a code analyzer could do this job is wrong.
Consider the following function:
(defun foo ()
(maybe-loop)
(setf *var* 42))
This function only has a side effect if the call to maybe-look
eventually terminates: This is essentially the trick to show that
whatever may come after maybe-loop is as hard to show as it is to show
whether maybe-loop will eventually halt or not. [1]
So there is no way out here, unless you are willing to sacrifice Turing
completeness.
What ACL2 does, for example, is to restrict Common Lisp to a subset that
doesn't have side effects (which would directly help the OP), but also
to a subset that consists only of programs that are guaranteed to
terminate all the time. (This removes Turing completeness from that
subset.) This then allows you to prove all kinds of interesting
properties about the eventual behavior of such programs.
But in general, this is not possible.
Pascal
[1] You could now make the suggestion that you consider this function as
potentially having a side effect, because it contains an invocation of
setf. That's indeed a valid check, but it only works in a few cases. As
soon as a function calls other functions, it already becomes more
complicated, because you have to take the potential call graph into
account. This is especially hard for a language which has higher-order
functions and even allows you to change function definitions at runtime. ;)
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza schrieb:
> Andr� Thieme wrote:
>> Pascal Costanza schrieb:
>>
>>> Analyzing the code of a function doesn't help you either, because you
>>> would first have to solve to halting problem.
>>
>> In principle analyzing the code of a function could be the most promising
>> thing that he can do. If he is doing it right this code analyzer can
>> at least come to the same results to which a human expert would come.
>> But as it would be automized and computers are getting faster his
>> program could in principle outperform humans.
>> The halting problem only states that programs exist about which humans
>> can't tell whether they will halt or not.
>
> Yes, but determining other characteristics of the eventual behavior of a
> function is at least as hard as the halting problem, due to Rice's
> theorem. So your assumption that a code analyzer could do this job is
> wrong.
>
> Consider the following function:
>
> (defun foo ()
> (maybe-loop)
> (setf *var* 42))
>
> This function only has a side effect if the call to maybe-look
> eventually terminates: This is essentially the trick to show that
> whatever may come after maybe-loop is as hard to show as it is to show
> whether maybe-loop will eventually halt or not. [1]
>
> So there is no way out here, unless you are willing to sacrifice Turing
> completeness.
I agree.
However, here humans and computers have the same problem.
For some functions humans can tell if they have a side effect or not,
and so the computer can. If the OP can develop a program that has +/-
human intelligence then this program could probably do its best to say
at least about a good portion of given code if and where it has side
effects.
Although I don't see how anyone could write such a program today I don't
want to say that it will never be written.
> But in general, this is not possible.
Right.
--
Andr�
In article <···············@mid.individual.net>,
Pascal Costanza <··@p-cos.net> wrote:
> Yes, but determining other characteristics of the eventual behavior of a
> function is at least as hard as the halting problem, due to Rice's
> theorem. So your assumption that a code analyzer could do this job is wrong.
>
> Consider the following function:
>
> (defun foo ()
> (maybe-loop)
> (setf *var* 42))
>
> This function only has a side effect if the call to maybe-look
> eventually terminates: This is essentially the trick to show that
> whatever may come after maybe-loop is as hard to show as it is to show
> whether maybe-loop will eventually halt or not. [1]
>
> So there is no way out here, unless you are willing to sacrifice Turing
> completeness.
For most real world uses, it's not necessary to determine definitively
whether a function DOES have side effects, only whether it COULD have
side effects.
This can usually by done recursively. A well-known set of primitive
operations are declared to be side-effecting (SETQ, RPLACA, SETF, DEFUN,
etc.). A function has side effects if it uses any of these built-ins,
or if it calls any functions that have side effects.
Actually, this is too simple, since it will consider a function to have
side effects even if it only uses these operations on local temporaries.
So some data flow analysis has to be done to tell whether the target of
any of these operations is a global variable or a data structure passed
in as a parameter. And in the latter case, the calling function only
has side effects if it's passing a global or parameter as the parameter
being targeted.
This is basically a form of type inference, where the "type"
incorporates the manner of side effecting.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
From: Kent M Pitman
Subject: Re: Getting Lisp to reflect on its own environment
Date:
Message-ID: <u4pcpgkow.fsf@nhplace.com>
Barry Margolin <······@alum.mit.edu> writes:
> For most real world uses, it's not necessary to determine definitively
> whether a function DOES have side effects, only whether it COULD have
> side effects.
I'm glad someone made this point. I'd thought at one point to make it and
then had forgotten, and I think it's a good observation notwithstanding the
rest of my remarks here to follow.
I think the reason the discussion didn't go this way is just that the OP
had framed it in the reverse. As so often happens, a slight reformulation
of a stated problem can transform something that's hard or impossible into
the doable ... it just requires one to reconsider the options and say "is
this really what was needed?"
deech <············@gmail.com> had written:
> I want to write a function that can show that a given function does
> not have any side-effects
Reliably showing that a function does not have side-effects is hard,
in part because opaque functions may be called that one doesn't know
the nature of, and in part because functions as first-class data may be
passed around for a while before being used.
HOWEVER, writing a function that can exonerate some programs or that can
warn about suspicious functions is pretty straightforward.
Barry Margolin <······@alum.mit.edu> writes:
> This can usually by done recursively. A well-known set of primitive
> operations are declared to be side-effecting (SETQ, RPLACA, SETF, DEFUN,
> etc.). A function has side effects if it uses any of these built-ins,
> or if it calls any functions that have side effects.
> Actually, this is too simple, since it will consider a function to have
> side effects even if it only uses these operations on local temporaries.
It's slightly harder than this, even, as you surely know. For example,
figuring out that a certain function which passes #'rplacd as an argument
will definitely actually call that function is tricky. It might never
call it, or it might be hard to tell. But warning that it MIGHT is
straightforward, because the word "might" is such a flexible term, capable
of embracing both "has a nonzero probability" or even "might have a zero
probability but I can't tell" (note somewhat ironic recursive use of
"might" in that last option).
In article <·············@nhplace.com>,
Kent M Pitman <······@nhplace.com> wrote:
> Reliably showing that a function does not have side-effects is hard,
> in part because opaque functions may be called that one doesn't know
> the nature of, and in part because functions as first-class data may be
> passed around for a while before being used.
True. MAPCAR doesn't have side effects of its own, but calling MAPCAR
has side effects if the first argument is a function with side effects.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
From: Pertti Kellomäki
Subject: Re: Getting Lisp to reflect on its own environment
Date:
Message-ID: <fo6gd7$lnq$1@news.cc.tut.fi>
Pascal Costanza wrote:
> Consider the following function:
>
> (defun foo ()
> (maybe-loop)
> (setf *var* 42))
>
> This function only has a side effect if the call to maybe-look
> eventually terminates: This is essentially the trick to show that
> whatever may come after maybe-loop is as hard to show as it is to show
> whether maybe-loop will eventually halt or not. [1]
>
> So there is no way out here, unless you are willing to sacrifice Turing
> completeness.
But side-effects are not necessary for Turing completeness.
If one is willing to write everything in a functional style,
then it should be fairly easy (although somewhat tedious) to
write a code walker that checks for any references to potentially
side-effecting primitives. If there are none, then the code cannot
have any side-effects. Such a code walker would reject some
programs even though they do not have side-effects, but I don't
think that would affect the Turing completeness.
This of course requires that you can analyze the whole program,
not just a singe function.
--
Pertti
Pertti Kellom�ki wrote:
> Pascal Costanza wrote:
>> Consider the following function:
>>
>> (defun foo ()
>> (maybe-loop)
>> (setf *var* 42))
>>
>> This function only has a side effect if the call to maybe-look
>> eventually terminates: This is essentially the trick to show that
>> whatever may come after maybe-loop is as hard to show as it is to show
>> whether maybe-loop will eventually halt or not. [1]
>>
>> So there is no way out here, unless you are willing to sacrifice
>> Turing completeness.
>
> But side-effects are not necessary for Turing completeness.
> If one is willing to write everything in a functional style,
> then it should be fairly easy (although somewhat tedious) to
> write a code walker that checks for any references to potentially
> side-effecting primitives. If there are none, then the code cannot
> have any side-effects. Such a code walker would reject some
> programs even though they do not have side-effects, but I don't
> think that would affect the Turing completeness.
>
> This of course requires that you can analyze the whole program,
> not just a singe function.
That's what I wanted to hint at in the footnote of my previous posting,
but Barry and you stated it much clearer. So thanks for that.
Pascal
--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On 2008-02-03, in comp.lang.lisp, Andr� Thieme wrote:
> In principle analyzing the code of a function could be the most promising
> thing that he can do. If he is doing it right this code analyzer can
> at least come to the same results to which a human expert would come.
> But as it would be automized and computers are getting faster his
> program could in principle outperform humans.
> The halting problem only states that programs exist about which humans
> can't tell whether they will halt or not.
The halting problem states no such thing. Rather, it states that the
set of codes for (e,n) such that e is an index of a recursive function
that converges on n is not recursive. Of course, we have no reason to
suppose humans are capable of deciding the halting or non-halting of
arbitrary recursive functions -- e.g. because they might be so complex
we can make nothing of them -- but this depends on reflection on
contingent facts about humans.
Also, the idea that computers getting faster implies that general code
analysing functions outperform humans is ungrounded. What would be
needed would be some outbreak in AI research.
The obvious solution to the original problem is to restrict in some
way the allowed constructs in user-supplied code, for example not
allowing the code to call these or those functions. (We might note
in this context, as an example, that there are useful and interesting
systems in which only total functions can be defined).
--
Aatu Koskensilta (················@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
On Feb 3, 11:46 am, Pascal Costanza <····@p-cos.net> wrote:
> That won't help you: You can't find out whether a function is free of
> side effects just by having one (or a few) sample runs.
>
> Consider:
>
> (defvar *x* 0)
>
> (defun test (x)
> (if (> x 10)
> (1+ x)
> (incf *x* x)))
>
> For some arguments, test doesn't have side effects, whereas for others,
> it does.
The function has to be considered together with its input. I.e. it is
a function call expression which has effects or does not, not a
function.
You could make test depend on the prior value of *x* however. All
values other than 42 could mean ``test, please have no effects''.
> What's worse, it's not clear whether test should be considered
> to have side effects or not when you pass 0 to it.
Of course. The increment is not atomic, so if it isn't optimized away,
it could cause visible interference with some thread or interrupt.
But that brings up another problem with the environment-snapshot
approach. The environment can be changing due to concurent programming
effects, even though your function call is effect-free. You don't know
which effects are attributable to the code you are examining and which
are incidental.
> Analyzing the code of a function doesn't help you either, because you
> would first have to solve to halting problem.
Not at all. Your function would just not be able to decide this for
arbitrary code.
However, it could decide the problem for many examples of code, or
which it could report ``effect free'' or ``with effects''. For others,
after some time, it could report ``undecided''.
Tristate the output and lower the bar. Simple as that. :)
If halting problems scared us, many of the cool and useful things that
compilers do wouldn't be implemented.
From: Don Geddis
Subject: Re: Getting Lisp to reflect on its own environment
Date:
Message-ID: <87abmf54mp.fsf@geddis.org>
Kaz Kylheku <········@gmail.com> wrote on Mon, 4 Feb 2008 :
> The function has to be considered together with its input. I.e. it is a
> function call expression which has effects or does not, not a function.
That's hardly helpful. Figuring out what run-time values a function will
be called with is clearly a variant of the Halting Problem.
>> Analyzing the code of a function doesn't help you either, because you
>> would first have to solve to halting problem.
>
> Not at all. Your function would just not be able to decide this for
> arbitrary code. However, it could decide the problem for many examples of
> code, or which it could report ``effect free'' or ``with effects''. For
> others, after some time, it could report ``undecided''.
You've redefined the problem so far that it's almost meaningless. A program
which simply emits "undecided" for _all_ code would satisfy it.
> Tristate the output and lower the bar. Simple as that. :) If halting
> problems scared us, many of the cool and useful things that compilers do
> wouldn't be implemented.
If you simply mean "let's try writing the code and see how far we get, and
how useful the result is", then I suppose the answer is empirical.
But it's definitely the case that what you really want is provably not
possible, and it's hard to come up with a useful sharp specification that is
even theoretically possible, much less one that is also practical to work on.
The Halting Problem is all over this topic. Ready to trap you even when you
attempt approximations and simplifications. It would likely be extremely
difficult to construct meta-analysis software of this kind that is even
remotely useful.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
My friends tell me that I have a tendency to point out problems without
offering solutions, but they never tell me what I should do about it.
-- Daniel Gilbert, "Stumbling on Happiness"