Robert Rotstein wrote:
> Is there a simple way to determine whether a given list represents an
> executable form?
There may be an easier way, but you might consider looking at the CAR
of the list and checking if 1) is it a symbol and 2) is that symbol
bound to a function?
(defun executable-form-p (list)
(let ((obj (car list)))
(when (symbolp obj)
(not (null (fboundp obj))))))
Of course, this won't tell you if it's a well-formed executable form,
though (eg checking number of arguments, argument types, etc).
Jeff
Jeff <···@nospam.insightbb.com> wrote:
> (when (symbolp obj)
> (not (null (fboundp obj))))))
You've been doing too much Scheme lately -- no need to watch out for
the wrath of #f here! ;)
(and (symbolp obj) (fboundp obj))
... or better yet,
(or (and (symbolp obj) (fboundp obj))
(and (listp obj) (eq 'lambda (car obj))))
Cheers,
-- Nikodemus "Not as clumsy or random as a C++ or Java.
An elegant weapon for a more civilized time."
·········@random-state.net wrote:
> (or (and (symbolp obj) (fboundp obj))
> (and (listp obj) (eq 'lambda (car obj))))
Still insufficient. You need another clause for the null list, which
is both a list and an executable form.
What if obj is a function object? Your predicate evals to nil.
What if obj is the list (lambda)? Your predicate evals to non-nil.
Steven M. Haflich wrote:
> ·········@random-state.net wrote:
>
>> (or (and (symbolp obj) (fboundp obj))
>> (and (listp obj) (eq 'lambda (car obj))))
>
>
> Still insufficient. You need another clause for the null list, which
> is both a list and an executable form.
Jim Newton wrote:
> What if obj is a function object? Your predicate evals to nil.
> What if obj is the list (lambda)? Your predicate evals to non-nil.
The original question was a predicate for _lists_. Every non-symbol
non-cons object in CL is self-evaluating. Functions are no different
from arrays and readtables and numbers in this regard.
As for a list beginning with lambda, remember that lambda is fbound
as a macro. It has already been discussed in this thread that there
is no guarantee possible whether a form will execute without error
without solving the Turing problem. In that sense, the original
question was not well formed. Surely (lambda) will signal
error when it is executed, but execution does start with the
expansion of the macro and the macro signals error. An argument
could be made that this qualifies as "execution", whereas something
like (((fnargle . foo) 22/7 snort!)) is not a form that can executed.
"Robert Rotstein" <·········@verizon.net> writes:
> Is there a simple way to determine whether a given list represents an
> executable form?
No. No. Yes.
No, it's not possible unless you precise the interpreter you're
considering. Given any random form, you can design an interpreter that
will execute it. That is, given any _form_, you can _invent_ a
sematic to apply to this form.
No, there's no algorithm that is able to determine for all form if
it's executable. This is the G�del theorem or the termination problem.
Yes, just try to execute it and see if you get a result in a given
time. If you do, it's definitely executable. If you get an error,
it's definitely non executable. If you reach the given time, try a
longer time or you won't know (see previous answers).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Voting Democrat or Republican is like choosing a cabin in the Titanic.
"Robert Rotstein" <·········@verizon.net> writes:
> Is there a simple way to determine whether a given list represents an
> executable form?
As pointed out already, these are in fact several different
questions. A "simple" way to obtain an answer to one of them is to
observe the outcome of
(compile nil `(lambda () ,candidate-executable-form))
and for another one, the outcome of
(eval candidate-executable-form)
(as Pascal Bourguignon pointed out, make sure you don't wait forever
in the latter case). Here "outcome" includes any errors that may be
signalled. (And I assume that the question is about forms in Common
Lisp...)
Writing one's own code walker is much more interesting, of course,
but I don't think it would qualify as simple, if all Common Lisp
forms are to be covered.
---Vassil.
--
Vassil Nikolov <········@poboxes.com>
Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.
Vassil Nikolov <········@poboxes.com> writes:
> "Robert Rotstein" <·········@verizon.net> writes:
>
> > Is there a simple way to determine whether a given list represents an
> > executable form?
>
> As pointed out already, these are in fact several different
> questions. A "simple" way to obtain an answer to one of them is to
> observe the outcome of
>
> (compile nil `(lambda () ,candidate-executable-form))
>
> and for another one, the outcome of
>
> (eval candidate-executable-form)
>
> (as Pascal Bourguignon pointed out, make sure you don't wait forever
> in the latter case). Here "outcome" includes any errors that may be
> signalled. (And I assume that the question is about forms in Common
> Lisp...)
Even in the former. IIRC, CLHS does not expect (compile nil #1=(lambda
() #1#)) to terminate. Well sbcl and clisp return an out of stack error.
Also, sbcl loops on: (compile nil '(lambda () . #1=(:x . #1#))) until:
set_auto_gc_trigger: tried to set gc trigger too high! (0x82046f8)
fatal error encountered in SBCL pid 15499:
lost
The system is too badly corrupted or confused to continue at the Lisp
level. If the system had been compiled with the SB-LDB feature, we'd drop
into the LDB low-level debugger now. But there's no LDB in this build, so
we can't really do anything but just exit, sorry.
So, I would not say that one can observe the outcome of a compile
call, if you meant to do it _programmatically_, inside lisp. At least
you'd have to fork a sub lisp process... You could also launch the
process on another computer and detect with a webcam if that puts it
on fire... If you see what I mean.
> Writing one's own code walker is much more interesting, of course,
> but I don't think it would qualify as simple, if all Common Lisp
> forms are to be covered.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Voting Democrat or Republican is like choosing a cabin in the Titanic.
Pascal Bourguignon <····@mouse-potato.com> writes:
> Vassil Nikolov <········@poboxes.com> writes:
>
>> "Robert Rotstein" <·········@verizon.net> writes:
>>
>> > Is there a simple way to determine whether a given list represents an
>> > executable form?
>>
>> As pointed out already, these are in fact several different
>> questions. A "simple" way to obtain an answer to one of them is to
>> observe the outcome of
>>
>> (compile nil `(lambda () ,candidate-executable-form))
>>
>> and for another one, the outcome of
>>
>> (eval candidate-executable-form)
>>
>> (as Pascal Bourguignon pointed out, make sure you don't wait forever
>> in the latter case). Here "outcome" includes any errors that may be
>> signalled. (And I assume that the question is about forms in Common
>> Lisp...)
>
> Even in the former. IIRC, CLHS does not expect (compile nil #1=(lambda
> () #1#)) to terminate. Well sbcl and clisp return an out of stack error.
Leaving any bugs and unfinished parts of the compiler aside, I
believe the compiler must always terminate (unlike the evaluator).
As to circular lists, I don't think that they can ever be valid code
(or am I missing something?), and then I don't see any fundamental
reasons why the compiler shouldn't be able to handle them. More
generally, is it not decidable whether a sequence of characters is a
valid Common Lisp program? Or, for that matter, is there any
programming language for which that is undecidable, or for which
there might be a valid program that would make compilation
non-terminating?
(A precise formulation of these statements would probably be much
longer, since we would need to exclude cases such as the file
compiler seeing (EVAL-WHEN (:COMPILE-TOPLEVEL) (LOOP)) at top
level, but I think the essence is clear.)
> [...]
> So, I would not say that one can observe the outcome of a compile
> call, if you meant to do it _programmatically_, inside lisp.
Well, I did not, but primarily because much of the information
contained in that outcome may well be in human-only-readable form.
---Vassil.
--
Vassil Nikolov <········@poboxes.com>
Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.
From: Matthew Danish
Subject: Re: Is a given list an executable form
Date:
Message-ID: <87oej7ywwe.fsf@mapcar.org>
Vassil Nikolov <········@poboxes.com> writes:
> More generally, is it not decidable whether a sequence of
> characters is a valid Common Lisp program?
Definitely not in the general case. The power of macros,
reader-macros and compiler-macros ensures that. The only way to
determine this is to compile and run it; and, anyway, validity can
only be determined as far as the formal definition of the language
is specified, which for CL is not always enough.
--
;; Matthew Danish -- user: mrd domain: cmu.edu
;; OpenPGP public key: C24B6010 on keyring.debian.org
Matthew Danish <··········@cmu.edu> writes:
> Vassil Nikolov <········@poboxes.com> writes:
>> More generally, is it not decidable whether a sequence of
>> characters is a valid Common Lisp program?
>
> Definitely not in the general case. The power of macros,
> reader-macros and compiler-macros ensures that.
True, of course; I was wrong to ignore/dismiss this part of it. I
suppose I would be able to make a correct statement along the lines
of, "COMPILE always terminates, provided that all user compiler
macro expansions and all user macro expansions involved terminate"
(and something even more elaborate for the file compiler, to also
cover character macros, EVAL-WHEN forms with compile-time
evaluation, MAKE-LOAD-FORM methods (etc.?)), but I am not sure how
interesting such a statement would be.
I must have been thinking about "well-formed". I'm not sure if
there is an "official" definition of "well-formed Common Lisp
program", but I conjecture, if I may, that it is possible to produce
a reasonable definition such that "being well-formed" is decidable.
Then one might argue that "well-formed" is yet another possible
meaning of "executable".
> The only way to
> determine this is to compile and run it; and, anyway, validity can
> only be determined as far as the formal definition of the language
> is specified, which for CL is not always enough.
You mean that such a determination of validity is not always
sufficient for Common Lisp, or that the extent to which Common Lisp
is formally defined is not always sufficient? I'll appreciate it if
you would elaborate or rephrase that (even if it is just I who
doesn't get it...).
---Vassil.
--
Vassil Nikolov <········@poboxes.com>
Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.
From: Matthew Danish
Subject: Re: Is a given list an executable form
Date:
Message-ID: <87brf5z3wo.fsf@mapcar.org>
Vassil Nikolov <········@poboxes.com> writes:
> You mean that such a determination of validity is not always
> sufficient for Common Lisp, or that the extent to which Common Lisp
> is formally defined is not always sufficient?
The latter, noting in particular LOOP, logical pathnames, wherever it
says `unspecified', and the other dark corners of the spec. Of
course, it would be exceedingly difficult to actually come up with a
complete formal definition.
--
;; Matthew Danish -- user: mrd domain: cmu.edu
;; OpenPGP public key: C24B6010 on keyring.debian.org
·········@random-state.net writes:
> > there might be a valid program that would make compilation
> > non-terminating?
>
> Since compilation of a CL program can invoke arbitrary code, solving
> termination of compilation for CL reduces to solving the halting problem.
That said, you can ensure the compilation terminates.
For example, in clisp:
(defun compile-file-with-timeout (file timeout &rest args)
(ext:shell
(format nil "ulimit -t ~D ; clisp -x '(compile-file ~S ~{ ~S~})'"
timeout file args)))
[6]> (print (compile-file-with-timeout "/home/pascal/src/lisp/encours/compile-loop.lisp" 1))
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2004
;; Loading file /home/pascal/.clisprc.lisp ...
Compiling file /home/pascal/src/lisp/encours/compile-loop.lisp ...
137
137 = compilation timed out.
[7]> (print (compile-file-with-timeout "/home/pascal/src/public/common/common-lisp/browser.lisp" 1))
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2004
;; Loading file /home/pascal/.clisprc.lisp ...
Compiling file /home/pascal/src/public/common/common-lisp/browser.lisp ...
Wrote file /home/pascal/src/public/common/common-lisp/browser.fas
0 errors, 0 warnings
#P"/home/pascal/src/public/common/common-lisp/browser.fas" ;
NIL ;
NIL
Bye.
0
0 = compilation terminated (with or without error).
Unfortunately, that cannot be done portably because there's no timer
in Common-Lisp... (I should write a CLRFI).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Voting Democrat or Republican is like choosing a cabin in the Titanic.
From: Joe Marshall
Subject: Re: Is a given list an executable form
Date:
Message-ID: <brf6buaw.fsf@ccs.neu.edu>
Pascal Bourguignon <····@mouse-potato.com> writes:
> ·········@random-state.net writes:
>> > there might be a valid program that would make compilation
>> > non-terminating?
>>
>> Since compilation of a CL program can invoke arbitrary code, solving
>> termination of compilation for CL reduces to solving the halting problem.
>
> That said, you can ensure the compilation terminates.
That said, you can ensure that all strings of characters are valid
programs.
Joe Marshall <···@ccs.neu.edu> writes:
> Pascal Bourguignon <····@mouse-potato.com> writes:
>
> > ·········@random-state.net writes:
> >> > there might be a valid program that would make compilation
> >> > non-terminating?
> >>
> >> Since compilation of a CL program can invoke arbitrary code, solving
> >> termination of compilation for CL reduces to solving the halting problem.
> >
> > That said, you can ensure the compilation terminates.
>
> That said, you can ensure that all strings of characters are valid
> programs.
Yes, the universe works.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Voting Democrat or Republican is like choosing a cabin in the Titanic.
"Robert Rotstein" <·········@verizon.net> writes:
> Is there a simple way to determine whether a given list represents an
> executable form?
Good question actually. Do you mean one that executes without error?
You can /try/ to execute any old S-expression. What does in your eyes
make it executable/not executable?