eval and (infinite) recursion

I'm implementing an "eval" function in a scripting language... or at least contemplating it.

I can envision the infinite recursion from as simple a thing as the sequence:

set a to "a"
set evalA to eval(a)

if by eval I mean do variable lookup for strings, and the eval is a "deep" eval. Is one always obliged to make the eval a 1-level shallow eval?

Or is eval() generally not a variable-lookup operator? I could provide a separate one, an explicitly shallow evalWithLookup() or something...

Environments

If you implemented a "deep eval", how would you ever know to stop?

I don't immediately see a useful, sensible definition for a "deep eval"; but there is a way to get infinite recursion from the standard "shallow" eval.

set a to "eval(a)"
set evalA to eval(a)

The question about looking up variables is good; R6RS scheme for example has moved away from a one-argument eval to a two-argument eval with an environment. This is basically a subset of Chez Scheme's first-class environments. Neither solution offers a way to reify the current environment into a first-class environment, however.

The Essentials of Programming Languages has more discussion of environment passing interpreters.

By Leon P Smith at Thu, 2010-01-28 21:47 | login or register to post comments

Implementation of first-class environments?

[Intended as reply to Leon P Smith]

I've always ignored (mutable) first-class environments so far, because I thought they would be prohibitively expensive, performance-wise.

Any pointers to how Chez or other compilers implement these?

By Manuel J. Simoni at Thu, 2010-01-28 22:54 | login or register to post comments

chez's mutable first class environments

Chez only implements a tiny subset of what is usually meant by mutable first-class environments and, at least if their documentation is accurate, Chez's aren't fully "first class" in the usual way.

The customary trick (in Scheme) for fully fledged first class mutable environments that are still compiler friendly is to make the only way to capture an environment is to invoke a special form like (the-environment) within the lexical scope of the environment in question. Then the compiler can statically prove that many environment frames are never manifest at run-time as first-class objects, and can optimize them away in all the usual ways. I believe but I'm not absolutely certain that MIT Scheme is an example of a system that does this (and that includes an optimizing compiler, even though there has been no effort to keep MIT Scheme performance-competitive with the likes of Chez).

By Thomas Lord at Thu, 2010-01-28 23:25 | login or register to post comments

Thanks

I was thinking that something like this was going on.

Alice ML has this interesting notion of modules (which share some similarities with environments (?)), which can be linked at runtime into another module.

One could probably do some optimizations at link-time there, so that the runtime costs of e.g. looking up a variable can be reduced significantly. (Somewhat similar to how Go does its "semi-virtual" method lookups.)

More thinking and investigation needed. ;)

By Manuel J. Simoni at Fri, 2010-01-29 12:21 | login or register to post comments

strange definition of eval

if by eval I mean do variable lookup for strings

Then it sounds like you are implementing the C pre-processor, not a scripting language.

In CPP, expansion (the closest thing to "eval") is what I guess you might call "semi-deep". By that I mean that if it expands a string that contains the token A, it will go ahead and replace that with the definition of A and then recursively expand the result - but with an exception: during that recursion, any further occurences of A are treated as literal text, not variable names.

By Thomas Lord at Thu, 2010-01-28 23:29 | login or register to post comments

Lambda the Ultimate

User login

Navigation