dab@asylum.SF.CA.US (Dave Bridgham) (03/05/91)
I'm afraid that I'm about to display some very fundmental ignorance about how scheme works but this stuff with implementing EVAL by writing to a file and LOADing the file back in has me puzzled. Why is (eval s) not equivalent to ((lambda () s)) ? David Bridgham
hayes@jazz.concert.net (Brian Hayes - Sigma Xi) (03/06/91)
In Article 268 in comp.lang.scheme Marc Feeley (feeley@chaos.cs.brandeis.edu) writes: > However, it is not possible to write a portable EVAL procedure because there > is no way in standard Scheme (R4RS or IEEE) to access global variables > through their names. We would like the following code to print 100: > (define x 50) > (EVAL '(set! x (+ x x))) > (write x) > EVAL would be possible given procedures to reference and set global variables > (and perhaps define them), for example (global-var-ref name) and > (global-var-set! name val). Think of global-var-ref as: > (define (global-var-ref name) > (case name > ((a) a) > ((b) b) > ... etc for all possible variable names! > and similarly for global-var-set!. Feeley's example seems to suggest there is something uniquely weird about the global environment. But if I understand what's going on here--and admittedly my confidence is not terribly high on that point--the same problem would arise with an attempt to access a variable in *any* lexically enclosing environment. For example, (let ((z 50)) (begin (EVAL '(set! z (+ z z))) (write z))) ought to cause the same trouble. We can teach our EVAL how to bind variables that are created within its own scope, but it doesn't know where to look for the values of variables anywhere outside that scope. Doesn't this line of reasoning lead to the conclusion that EVAL is inextricably part of the interpreter, rather than something we can add on to an existing interpreter? EVAL has to know how environments are represented internally. Hence it seems the only way to write EVAL within Scheme is to write an entire Scheme within Scheme. Facilities for finding global variables--but not local variables introduced in enclosing scopes--would not be enough. As it happens, in at least some implementations of Scheme, the global environment is the only enclosing scope where EVAL *can* find variables. For instance, when I run Feeley's sequence of expressions through MacScheme or through TI's PC Scheme--using the versions of EVAL supplied in those interpreters--the result is the expected (correct?) one: the interpreter writes "100". But both MacScheme and PC Scheme choke on the example with the (let ...) expression, complaining of an undefined variable z. The reason is that both EVALs choose, unless told otherwise, to evaluate an expression in the global, top-level environment. They can find x there, but the let- bound z is invisible from the top-level vantage. Incidentally, I tried this experiment in one more version of Scheme: Pixie Scheme, an interpreter available for a fee of $1.00 from Jay Reynolds Freeman. Pixie Scheme also complains of an unbound variable, but the variable is not x or z; it is EVAL. No environmental ambiguities in Pixie Scheme. Brian Hayes hayes@concert.net
freeman@argosy.UUCP (Jay R. Freeman) (03/06/91)
In article <1991Mar5.160735.24566@rock.concert.net> hayes@jazz.concert.net (Brian Hayes - Sigma Xi) writes: > [discussion of what Scheme ought to do with the following > expressions, and of what various implementations actually do] >> (define x 50) >> (EVAL '(set! x (+ x x))) >> (write x) > (let ((z 50)) > (begin > (EVAL '(set! z (+ z z))) > (write z))) >Incidentally, I tried this experiment in one more version of Scheme: >Pixie Scheme, an interpreter available for a fee of $1.00 from Jay >Reynolds Freeman. Pixie Scheme also complains of an unbound variable, >but the variable is not x or z; it is EVAL. No environmental >ambiguities in Pixie Scheme. Lest anyone be misled, I should point out that Pixie Scheme runs only on the Apple Macintosh. I didn't put in "eval" because I thought it was poorly named: Since there are several ways to do it, the name should indicate which is being used, or should at least be sufficiently mystifying to prompt users to look it up in the documentation. So Pixie Scheme has an enhancement, "e::cons-with-continuation" that ought to result in "100" being written in either case if used instead of "eval". (That "e::" is *not* a package system, it is just my convention for how I name built-in enhancements in Pixie Scheme.) I thought Pixie Scheme should provide some form of "eval", and decided to punt controversial semantic issues by implementing a more suggestively-named (for those of you familiar with the notion of an SECD machine) instance of one popular variation; namely, the one where evaluation is performed in the nest of environments in which the call to "e::cons-with-continuation" was made. Pixie Scheme isn't quite an SECD machine internally, but "e::cons-with-continuation" is describable in terms of one: It evaluates its single argument, then conses the result onto the current contents of the "C" register, and puts the cons back into "C", all without changing "S", "E", or "D". Thus when execution resumes, it finds that continuation magically contains a new form, that was created at run-time, to be evaluated with the current environment list; and it is the result of that latter evaluation that will be returned as the result of the call to "e::cons-with-continuation". "e::cons-with-continuation" is a handful to type, but it can of course easily hide behind "call-with-current-continuation", if necessary. And users may of course evaluate (define eval e::cons-with-continuation) to save subsequent keystrokes. I thought about putting in a "two-argument eval" as well -- the other argument being an environment -- but I was too lazy (being lazy about evaluation is a virtue, right?) to put in other paraphernalia necessary to make environments first-class objects. And besides, I was fearful that there might be additional variants on "eval" lurking in the wings, which I would then have to provide as well, in the interest of fairness to one and all. (Isn't trying to be all things to all users how PL1 got started?) And, based on comments in this thread, I was right; for there seem to be "eval"s that only know about the top-level environment. *Sigh* -- Jay "Pixie Scheme" Freeman PS: Does anyone know when the R4 report will be out? Perhaps it will say some more about these interesting issues. Perhaps it will at least indicate how to evaluate numbers ... <canonical disclaimer -- I speak only for myself>
jinx@zurich.ai.mit.edu (Guillermo J. Rozas) (03/06/91)
Feeley's example seems to suggest there is something uniquely weird
about the global environment. But if I understand what's going on
here--and admittedly my confidence is not terribly high on that
point--the same problem would arise with an attempt to access a
variable in *any* lexically enclosing environment. For example,
(let ((z 50))
(begin
(EVAL '(set! z (+ z z)))
(write z)))
ought to cause the same trouble. We can teach our EVAL how to bind
variables that are created within its own scope, but it doesn't know
where to look for the values of variables anywhere outside that
scope.
Doesn't this line of reasoning lead to the conclusion that EVAL is
inextricably part of the interpreter, rather than something we can
add on to an existing interpreter? EVAL has to know how environments
are represented internally. Hence it seems the only way to write EVAL
within Scheme is to write an entire Scheme within Scheme. Facilities
for finding global variables--but not local variables introduced in
enclosing scopes--would not be enough.
Some implementations of Scheme have first-class environments. That
is, they provide a way to reify an existing environment into an object
that can be used later. They also provide some procedures for
accessing variables, assigning variables, and defining variables in
environment objects.
In these implementations, EVAL typically takes two arguments, namely
the expression to evaluate and the environment with respect to which
the evaluation should be done. A common extension is to default the
second argument to the environment where the current read-eval-print
loop is evaluating.
In MIT Scheme, for example,
(let ((z 50))
(begin
(EVAL '(set! z (+ z z)))
(write z)))
would request evaluation with respect to the read-eval-print loop's
environment, which would probably result in an error, while
(let ((z 50))
(begin
(EVAL '(set! z (+ z z)) (the-environment))
(write z)))
would request evaluation with respect to the environment where the
form (THE-ENVIRONMENT) is evaluated, and would therefore print 100.
Besides the special form (THE-ENVIRONMENT), MIT Scheme has some
procedures for manipulating environments:
(lexical-reference <environment object> <symbol>)
is equivalent to
(EVAL <symbol> <environment object>)
(lexical-assignment <environment object> <symbol> <value>)
is equivalent to
(EVAL `(SET! ,<symbol> ',<value>) <environment object>)
and
(local-assignment <environment object> <symbol> <value>)
is equivalent to
(EVAL `(DEFINE ,<symbol> ',<value>) <environment object>)
Environment objects are otherwise opaque, ie. their representation is
hidden, and CAR, VECTOR-REF, etc. do not work on them.
The EVAL provided by MIT Scheme is provided primitively, but it need
not be. Given these primitives (and a way to obtain the current
read-eval-print loop's evaluation environment), EVAL can be written in
user code.
T has similar procedures for manipulating environments, but the way to
reify environments is different and somewhat better suited to
compilation.
PS: This is not a plug for first-class environments, just a description
of one of the options.manis@cs.ubc.ca (Vincent Manis) (03/06/91)
In article <13781@asylum.SF.CA.US> dab@asylum.SF.CA.US (Dave Bridgham) asks, apologetically: >Why is (eval s) not equivalent to ((lambda () s)) ? Two reasons: a) first, (lambda () s) is a procedure, which, when called, simply returns the value of the [free] variable s. No evaluation is implied here. Thus (define s '(list 'foo 'bar)) (lambda () s) => (list (quote foo) (quote bar)) b) Scheme, as defined in R^3.9999999999999S, has semantics which do not require an implementation to maintain the names of bindings, or to allow environments to be manipulated by the programmer. This was deliberately done, to allow Scheme programs to be compiled efficiently. There is *no* way to "trick" Scheme into evaluating lists as programs, unless the implementation provides an eval procedure. I generally regard a request from a programmer for eval with the same degree of suspicion that I would give a request from a civil engineer for a little bit of chewing gum to prop up one end of a bridge. eval is extremely dangerous in real programs, as the following hypothetical dialogue (from a system written in Scheme, but using eval) might demonstrate: Welcome to the nuclear reactor control system! You have been given VISITOR privileges. > Blow up reactor You are not authorized to do that. > -debug- Enter expression: (blow-up-nuclear-reactor!) Initiating destruct sequence... When you eval something, you are letting that expression have full access to the internal state of your program. If the form being evaled was typed in by a user, that user gets to do what s/he likes to your program. If the form being evaled wasn't written by a user, then you most likely can trivially restructure your program to eliminate eval, given Scheme's rich procedure composition facilities. eval allows people to do to your program what Robert Morris did to sendmail, using exactly the same technique as he used, namely "smuggling" a command into a system. I regard eval as the computational equivalent of unprotected sex, and treat it accordingly. Not including eval could potentially make an implementation much more efficient. However, almost all implementations do include eval, for such things as writing top levels, and loading in code (an implementation which really didn't want eval would have to be non-compliant in not supporting load and friends). The arguments against eval in these special circumstances are weak (if a user types in commands to wreck her/his session, then s/he will get what s/he deserves). Finally, if you really want to use eval in a portable program, write your own. Abelson and Sussman, as well as my forthcoming book, describe the subject of writing evaluators in great detail; a custom evaluator can do all sorts of error checking, and can restrict the user, in whatever ways you want. -- \ Vincent Manis <manis@cs.ubc.ca> "There is no law that vulgarity and \ Department of Computer Science literary excellence cannot coexist." /\ University of British Columbia -- A. Trevor Hodge / \ Vancouver, BC, Canada V6T 1W5 (604) 228-2394
jinx@zurich.ai.mit.edu (Guillermo J. Rozas) (03/06/91)
In article <1991Mar6.004022.26316@cs.ubc.ca> manis@cs.ubc.ca (Vincent Manis) writes: b) Scheme, as defined in R^3.9999999999999S, has semantics which do not require an implementation to maintain the names of bindings, or to allow environments to be manipulated by the programmer. This was deliberately done, to allow Scheme programs to be compiled efficiently. There is *no* way to "trick" Scheme into evaluating lists as programs, unless the implementation provides an eval procedure. You are confusing the issues of efficiency and flexibility. It is perfectly possible to have first-class environments and EVAL, and have efficient compilation. The ORBIT T compiler, and the MIT Scheme Liar compiler accomodate both, and I am quite confident in claiming that none of the performance problems that either implementation has are due to first-class environments or EVAL. In other words, it is feasible (and not too hard) to build an implementation where you only pay for the cost of these features if you use (or ``abuse'') them, and you don't when you don't use them at all. It does make the implementor's job a little harder, however. I generally regard a request from a programmer for eval with the same degree of suspicion that I would give a request from a civil engineer for a little bit of chewing gum to prop up one end of a bridge. eval is extremely dangerous in real programs, as the following hypothetical dialogue (from a system written in Scheme, but using eval) might demonstrate: Welcome to the nuclear reactor control system! You have been given VISITOR privileges. > Blow up reactor You are not authorized to do that. > -debug- Enter expression: (blow-up-nuclear-reactor!) Initiating destruct sequence... When you eval something, you are letting that expression have full access to the internal state of your program. If the form being evaled was typed in by a user, that user gets to do what s/he likes to your program. If the form being evaled wasn't written by a user, then you most likely can trivially restructure your program to eliminate eval, given Scheme's rich procedure composition facilities. eval allows people to do to your program what Robert Morris did to sendmail, using exactly the same technique as he used, namely "smuggling" a command into a system. I regard eval as the computational equivalent of unprotected sex, and treat it accordingly. Aren't you exagerating a bit? You are confusing the issues of modularity and dynamic access to the name space. Perhaps what you are saying is that the application program did not hide its internal state sufficiently given that it was making EVAL available. Consider the following two options: - On a Scheme with first-class environments, an environment can be created with only those bindings that we want users to see, and use EVAL exclusively with respect to that. Thus if this environment does not provide access to BLOW-UP-NUCLEAR-REACTOR! or to any other environment from which it is reachable, there is no danger. - On a Scheme without them, presumably EVAL evaluates with respect to the global environment. You can always write an application to export a limited set of procedures to the global environment, and if you do not export the ``dangerous'' procedures, there is still no way to get them. This, of course, also works in a Scheme with first-class environments, but is cruder than needed there. In other words, you can break poorly organized programs in many ways. Don't impose a straight jacket on all programmers just because bad programmers exist. Finally, if you really want to use eval in a portable program, write your own. Abelson and Sussman, as well as my forthcoming book, describe the subject of writing evaluators in great detail; a custom evaluator can do all sorts of error checking, and can restrict the user, in whatever ways you want. I have no objection against writing your own evaluators, and often EVAL is used out of laziness, but there is nothing wrong with that. One of the great features of Lisp is that interactive applications don't have to write their own parsers, output routines, or even evaluators for extension languages, so you can concentrate on the core of the application and not on accidental details. In other words, your argument is like saying that you should use your own parser instead of READ, and your own output routines instead of WRITE (and FORMAT). You can certainly do that, but you can get a program up much more quickly if you use the more powerful facilities available in Lisp than if you have to write them from scratch as you would have to in C or Pascal.
feeley@chaos.cs.brandeis.edu (Marc Feeley) (03/07/91)
In hayes@jazz.concert.net's message of 5 Mar 91 16:07:35 GMT Brian Hayes writes: > (let ((z 50)) > (begin > (EVAL '(set! z (+ z z))) > (write z))) > >ought to cause the same trouble. We can teach our EVAL how to bind >variables that are created within its own scope, but it doesn't know >where to look for the values of variables anywhere outside that >scope. Unfortunately, if you want EVAL to behave this way you are in for trouble... EVAL should not take the current environment as its evaluation environment. To see why, consider: (define y 1) (define (foo f x y) (f x)) and assume that foo is called by the form (let ((y 50)) (foo EVAL '(+ y y) 3)) It isn't clear what should happen... Should 100, 6 or 2 be returned? What does 'y' refer to anyway in (+ y y)? The 'y' in the let, the 'y' in the parameter list of foo or the global y? If you are a fan of lexical scoping, maybe you will vote for 100. Clearly the most recent binding to 'y' when EVAL is called is the one where y=3, so 6 should be the right answer. On the other hand, notice that 'f' is called in a tail position so that the frame containing f, x and y has been popped off the environment when f is jumped to. Note also that the let binding frame has been popped (when foo was called)! From this one infers that the right answer should be 2, because 'y' refers to the global variable. I don't think this semantic for EVAL is particularly elegant... My main concern with EVAL is one of efficiency. If it is put into Scheme without carefully thinking about all the implications then it might well be impossible to compile efficiently. Some Scheme compilers generate code that outperforms C on some benchmarks and it would be ashame to loose that. When we think of EVAL in an interpreter based system, it all seems trivial to implement. Let's think twice, it may not be that easy to implement efficiently. Marc -- feeley@cs.brandeis.edu
gyro@cymbal.reasoning.COM (Scott Layson Burson) (03/07/91)
Date: 6 Mar 91 13:53:15 GMT
From: "Guillermo J. Rozas" <jinx@zurich.ai.mit.edu>
In article <1991Mar6.004022.26316@cs.ubc.ca> manis@cs.ubc.ca (Vincent Manis) writes:
eval allows people to do to your program what Robert Morris did to
sendmail, using exactly the same technique as he used, namely
"smuggling" a command into a system. I regard eval as the computational
equivalent of unprotected sex, and treat it accordingly.
Aren't you exagerating a bit? You are confusing the issues of
modularity and dynamic access to the name space. Perhaps what you are
saying is that the application program did not hide its internal state
sufficiently given that it was making EVAL available.
Vincent's language is colorful, but having seen what an incredible mess novices
(especially, intelligent novices) can make using macros and EVAL (especially
when they use them in combination!), I personally feel that his warning about
EVAL is not too strong. I would go farther and suggest that all Lisp courses
should include material on the proper use of the various features of Lisp. It
is true that Lisp is wonderfully hackable, and a fertile source of shortcuts to
get your program running, but it is also true that quick hacks have a way of
growing into systems that somebody has to maintain.
In other words, your argument is like saying that you should use your
own parser instead of READ, and your own output routines instead of
WRITE (and FORMAT). You can certainly do that, but you can get a
program up much more quickly if you use the more powerful facilities
available in Lisp than if you have to write them from scratch as you
would have to in C or Pascal.
I wouldn't myself go so far as to suggest that one should always write one's
own evaluator (I once wrote a C interpreter that parsed C into list structure
which was full of macros so that I just had to call EVAL to get an expression
interpreted! -- obviously, the parser had to be specially built). I would very
definitely say, however, that the only proper use of EVAL is in the
implementation of some sort of interpreter. If the high-level description of
the module being written does not specify that it interprets expressions in a
language, then that module has no business calling EVAL, *period*. In my
experience, this rule very nicely distinguishes appropriate uses from abuses of
EVAL, and I would recommend its inclusion in any Lisp course.
I don't know of any single rule that so simply and neatly guides one as to
appropriate use of macros, but one rule that does suggest itself is, Don't
violate referential transparency without somehow indicating this in the syntax.
(The indication could be something as simple as the -F convention in Common Lisp
(as in SETF, INCF, etc.); it could be by making the syntax look like an
existing well-known macro, such as LET or COND; and no doubt there are other
ways.)
-- Scott