Lambda the Ultimate

i think my problem / beef is that i have no yet seen a language + syntax that does the best job of dealing with the inevitable problems of macros or laziness. my current straw-man idea is to have a mostly strict language w/out macros (although things like template haskell are interesting and i don't know enough to know how they relate, but some kinds of code generation seem to inevitably be desirable?) where some things do lazy evaluation but are typed and/or have to be named as such. so "if(a){true-body}{false-body}" would have to be named "if!" or "if'" or "if*" or i dunno what, but something.

You'd need "lazy macro expansion", which is probably how FEXPRs work.

The problem is that a macro works at compile time, turning a compile-time expression into another expression. (apply and [true false]) is trying to use the macro at runtime, and on runtime values.

See First-class Macros, though.

A fexpr works just like an "ordinary" procedure (the sort one finds in Scheme), except that there is no automatic evaluation of operands: the parameter tree of the fexpr is matched against the operand tree, i.e. the cdr of the calling combination. (In Kernel, which goes in heavily for uniform lack of restrictions, the operand tree doesn't even have to be a list, as long as it can be matched against the parameter tree.)

A fexpr differs from a traditional Lisp macro (never mind hygienic macros) in two ways.

• A macro must be preprocessed, while a fexpr is called at run-time (or rather, it has to act that way: a call to a fexpr could be partially or entirely processed at compile-time, if the compiler can prove that that will produce the same behavior; but the usual sort of undecidability guarantees that not all fexprs can be preprocessed).
• After the body of the traditional macro has been evaluated, the result of that evluation replaces the macro call, and will itself be evaluated at run-time. In contrast the result of evaluating the body of the fexpr is the run-time result of the combination.

See Fexpr.

Bawden's "first-class macros", as I understand them, simply replace the explicit restriction of macros to compile-time with an explicit type system. The fundamental restrictions on them, which require them to be preprocessed and prevent them from actually being first-class, are hidden behind the type system (which rather highlights that objects in Lisp are not first-class if they're subject to a static type discipline).

You've repeatedly talked of Bawden's first-class macros not being first class, but your arguments have simply invoked words such as "preprocessed" in a way that I find insubstantial. Have you written anything more substantial to back up this claim, perhaps towards part of your PhD?

ja, i was kinda thinking of fexprs when i first posted.

i think i fear clearly staged programming less / it sounds like a good idea, so when in other places i was saying get rid of macros i really mean only macros that are used to do things that could be (i think) better done with alternative explicit argument evaluation strategies.

Yes, for things that look like functions use different evaluation strategies (possibly together with opportunistic or just-in-time compiling)

For syntax extension use macros backed by "special evaluation" functions, really macros should do little more than rewriting.

I share this opinion. I am quite uncomfortable with a requirement to maintain a representation of source-code for correct run-time semantics. Among other things, it would hinder exploration of new ways to express old ideas, and it may hinder integration of code developed with different EDSLs or even with different stylistic conventions. (A result of this: I do not believe fexprs are a 'good thing'.)

Conceptually, macro expansion time is and should be distinct from (albeit sometimes interleaved with) run time; the objects of macro processing are text or syntax trees, not run-time objects. CL macros and Scheme R6RS syntax-case blur this distinction.

One problem with such a statement is that it makes quite difficult to speak clearly about the behavior of EVAL. With EVAL, syntax trees are (as is traditional in lisp) run-time objects. Macro expansion and other forms of evaluation become inter-mingled. The distinction you try to make there can not, at the very least, be expressed as you've put it.

You could try to fix your statement by saying "Ok, but we still can define EVAL to operate in two distinct phases: expand macros, then evaluate the macro-less code." You would still have problems, though:

First, let's suppose that we define EVAL in the most natural way and have it, by default, use the current dynamic instance of the lexical environment in which it is invoked as the top-level environment for the expression to be evaluated. (I'll explain later why this is the most "natural" way to define EVAL. You might object to this definition of EVAL but, for now, let's just suppose.) The form (lambda (x) (eval x)) should persuade you at once that macro expansion is inextricably linked to run-time objects - at least to environment contours known only at run-time. The form: (lambda (x) (eval (list x x (lambda (y) (eval y))))) should convince you that, in spite of your best efforts to resist them, you've given me a Scheme version of FSUBRs.

You might, however, as some have in the past, suggest limiting EVAL so that it does not use the current dynamic instance of its enclosing lexical environment, but instead uses only one of a few "special" top level environments. With a suitably restricted definition of which are the "special" top level environments, forms such as (lambda (x) (eval x)) present you with no special worries.

There are at least four worthy rebuttals to such a restriction:

1) You will have created an odd and seemingly arbitrary restriction on the composability of expressions in Scheme.

2) Your restriction fails to be strict for, if the macro language you propose is sufficiently powerful, I can certainly work around it in just about any implementation at no higher cost than an added tax on garbage collection. All you will have accomplished with your restriction is to force me to write portable code in an awkward way that favors a narrow subset of Scheme implementation strategies.

3) Your restriction ignores both history and a large segment of popular restrictions. The original report (AI Memo 349) and the revised report (AI Memo 452) as well as a great deal of other literature operationally and potently describe Scheme as a language in which code is data. Indeed, LAMBDA is explained as a form that closes over the syntax tree of a parameter list and body with a dynamic instance of a lexical environment. Popular implementations such as SCM and Guile actually work this way - and take good advantage of that fact.

4) Your restrictions (if they could actually be enforced) would foreclose on the implementation of interesting and promising paradigms. I tried to think of a very simple example of such a paradigm and one that came to mind was the notion of an "object" with a built-in interpreter: an object with an "eval" method. This would be a promising approach to a Scheme realization of concepts like Emacs' "buffer local" variables.

Having offered these various reasons why it is a mistake bordering on incoherence to restrict Scheme macros to "compile time" I owe you the opposite as well: to restate your original notion in a far better form (and briefly comment on what a standard ought to say, in my opinion):

Macros restricted in the way you describe are useful and important. They are a valuable programming paradigm which it should be easy to express in Scheme... at least if we can better state what that means.

I claim we can better state it this way:

(a) It is important that we be able to define macros in Scheme which can be statically expanded during batch compilation. That is an important programming paradigm. Just as it is important that Scheme be defined so as to allow (in some circumstances) the batch-compilation constant folding of (+ 3 2) into 5, so too it is desirable to support static evaluation of quite complex macro expansions.

(b) It is often best practice for programmers to stick to macros which can be statically analyzed in those ways for two reasons. (i) It aids compilation. (ii) As a rule of thumb, it often makes programs easier to reason about.

(c) To the extent which we agree that a Scheme standard should PERMIT an optimizing-compiler implementation without an (efficient) implementation of EVAL, the standard should not REQUIRE neither EVAL or any form of macros which can not be statically expanded.

What this leaves is the question of how best to define the kinds of macros you are speaking of. Given that a more FSUBR (but closure-considerate) paradigm is both the the historic and among the simplest ways to define Scheme; given that such a description accurately reflects a popular and successful implementation technique; given that such a description implemented in its full generality contains the fewest arbitrary restrictions and enables promising programming paradigms: I think it makes a lot of sense to define Scheme in terms of a far more general and losey goosey kind of macros - making sure to float the then defined concept of your kind "static" macros only as a minimal requirement, but not as "the whole point of" macros.

How much do we lose by keeping eval out of our languages?

It has always seemed to me that, long term, eval causes far more problems than it solves. It certainly seems a rather excessive authority.

I've never used it to any good effect, but I'm curious as to what might keep people from giving it up.

For example: I can't figure how to implement a good Emacs without it.

Huh? Which Emacs Lisp expressions require eval? Or if not there, then why would an Emacs Lisp expression ever need direct access to the implementation's environment or namespace, and why couldn't a first class function do the job?

If you don't require either of these things, then, AFAICT, you don't need eval.

You do need to interpret expressions provided by user at runtime, but that doesn't require eval (not unless you're weakening the definition of 'eval' to the point of including anything that ever interprets user input when deciding which actions to take...).

Well, let's see: There are commands like eval-buffer and eval-expression, there is lisp-mode (as in the default mode of the *scratch* buffer), there is the debugger, the command loop, a gazillion occurrences in the standard lisp library distributed with Emacs, several uses in the most excellent "calc" package (an arbitrary precision numeric + a symbolic calculator), some occurrences in my own packages I've relied on for years, etc. I don't think you understand Emacs very well other than superficially.

You ask: why couldn't a first class function do the job?: Because much of Emacs is written in Emacs lisp and because Emacs is an exploratory, incremental programming environment.

Nevermind Emacs per se: what do you think of the role of eval on lisp machines? (That's a rhetorical question.)

What you tell me is that it's used a lot. But that may be because it is available and convenient, not because it is necessary. Eval is a big enough hammer to pound in a wide variety of screws.

Of course an interpreter will need to 'evaluate' certain expressions - same as any programming environment or IDE. But that is not what is being discussed! 'eval' is a mechanism within the language that evaluates runtime-constructed expressions of the same language and within the same lexical and dynamic context of the call. One may write interpreters for languages that lack 'eval', and one may even do so within the language being interpreted.

I agree that I only know Emacs superficially. Thus, whatever it is you're expecting to be obvious to whatever small fraction of people who might have developed emacs is certainly escaping me. It similarly remains unclear why first-class functions are unsuitable for exploratory, incremental programming environments written mostly in themselves.

It similarly remains unclear why first-class functions are unsuitable for exploratory, incremental programming environments written mostly in themselves.

In an exploratory environment you need, at minimum, some way to associate arbitrary code with user interface events (button clicked, text field changed).

If you don't have eval, but a facility to call predefined functions (is that what you're referring to as first-class functions in this context?), then your user interface can only invoke functionality that has been included by the original programmer.

then your user interface can only invoke functionality that has been included by the original programmer.

Of course, that could include metacircular interpreter primitives, in which case you have full access to the language, but without use of an unstructured "eval".

What you tell me is that it's used a lot. But that may be because it is available and convenient, not because it is necessary. Eval is a big enough hammer to pound in a wide variety of screws.

I think that we have a fairly deep philosophical difference, here. For simplicity of discussion, I'll use GNU Emacs as the source of examples.

Historically, the presence of eval helped to simplify the development of Emacs. It is trivial to provide from the interpreter written in C. It's presence allows a lot more of the critical infrastructure to be written in Emacs Lisp. Its presence is also a constant boon to people learning Emacs Lisp and developing extension packages. It is also used in other ways in various packages such as a simple mechanism to introduce forms of extensibility not anticipated in "core" Emacs.

So, yes, it is "used a lot" but notice that it's use cost little in the implementation and accelerated the development of the application. Moreover, I don't recall there being ever, in over 20 years of history, any serious complaints about the effects of its presence. And it's not as if people are shy about complaining about Emacs Lisp language mis-features when they actually do cause annoyances - such as Emacs' pervasive use of dynamic scoping.

So, if you have a theory that says "eval is a hammer, pounding in screws," I have to wonder if maybe the real problem isn't in your theory, not in eval.

Of course an interpreter will need to 'evaluate' certain expressions - same as any programming environment or IDE. But that is not what is being discussed! 'eval' is a mechanism within the language that evaluates runtime-constructed expressions of the same language and within the same lexical and dynamic context of the call. One may write interpreters for languages that lack 'eval', and one may even do so within the language being interpreted.

It is true that 'eval' is for evaluating run-time constructed expressions within the dynamic and lexical context of its invocation. And, it is true that one can write interpreters for languages that lack eval.

It is also true that, given a simple but effective lisp interpreter, it is trivial to provide eval. In return you have no need to write a separate interpreter. You also get a powerful and flexible tool for exploring and tweaking the running image, and for implementing various programming paradigms that weren't anticipated by the core language.

Certainly the presence of eval limits what compilation can do. Certainly eval is a feature which can make some seemingly simple programs difficult to prove things about. Certainly the presence of eval makes it pragmatically trivial for a user to completely corrupt the running system in arbitrary ways. Yet, over 20 years of experience suggests that, in practice, none of those are serious problems crying out for a solution and all must be balanced against the demonstrated utility of having eval.

Thus, whatever it is you're expecting to be obvious to whatever small fraction of people who might have developed emacs is certainly escaping me.

Emacs, like Lisp machines, presents a "one big world" image of the lisp system. It is pragmatically simple to have eval around and its presence has demonstrably aided development of the application for decades, with no complaints.

I don't happen to disagree that there might, in theory, exist an equally pragmatic approach that (for whatever reasons of principle) avoids providing eval, per se. Yet, no such system has yet been demonstrated or convincingly described, and there is no evidence of any practical benefit from avoiding the presence of eval. As Larry Wall is often quoted: "There is more than one way to do it." I don't claim that eval is inescapable or that there aren't other approaches, yet to be discovered and proved, which might be agreeably better. Meanwhile, there's nothing particularly wrong with having eval and much good is seen to come of it.

It similarly remains unclear why first-class functions are unsuitable for exploratory, incremental programming environments written mostly in themselves.

Do you mean "unsuitable" or "insufficient"? I don't claim that they are unsuitable. I do claim that they are nicely complemented by eval. I don't claim, either, that they are "insufficient". I do claim that if you add in eval, though, then at very low implementation cost you get a more pragmatic system yet have introduced no serious problems or hardships.

I don't recall there being ever, in over 20 years of history, any serious complaints about the effects of [eval's] presence.

I'll admit that Emacs Lisp enjoys a relatively sheltered existence. People haven't stressed emacs nearly as much as they have stressed Web Browsers (with their Web Applications downloaded from not-quite-trusted sites).

The major problems with 'eval' in general are performance, safety, and security.

You have stated that "Emacs is an exploratory, incremental programming environment."

I am quite interested in how programming environments might be taken to the next level - supporting open distributed collaboration with minimal reliance on 'trust', integrating and extending services and applications written by many independent developers, supporting markets and trade. When I evaluated Lisp and Scheme for this purpose (eight years ago), I ultimately dismissed them due to a myriad of security and performance issues (including ambient authority for 'eval' and pervasive mutability of the common data structures). Emacs Lisp only adds to these problems with its dynamic scoping. I didn't complain about Lisp. It serves its purpose; I'll just need to find something else to serve my purpose.

You need to be careful with measuring failure in terms of complaints. Not all failures are accompanied by an audible whine. People have a tendency to complain most loudly when a system is already close to what they feel they need, and it looks to take only a few small changes to fix it. For problems that look really big, people just adapt and learn to live with it. (Looks, of course, can be deceiving in either direction.)

The major problems with 'eval' in general are performance, safety, and security.

To the extent that that's true: those are reasonable trade-offs for a very wide variety of applications.

There is a large extent to which it isn't true that those are eval's problems. At least: it requires a conspiracy between eval and other features before those problems occur. Eval can't single-handedly pull off the crime.

All three problems come down to what can and what can not be statically determined about a piece of code in a given environment. For example, if a language affords eval, but makes it easy to write some code so that it is trivially statically apparent that eval can not impact that code, then a compiler can go to town optimizing the heck out of that code. (In principle, a compiler can still go to down on code where eval might come into play but usually at a sharp increase in complexity and with a big performance hit if and when eval is actually used.) For another example, eval can be used "securely" for untrusted code if it can be invoked within a suitable sandbox, depriving the untrusted code of access to state it ought not see or touch and limiting its space and time consumption. These examples are part of the reason that a lexically scoped lisp is often a superior environment in which to provide eval.

I am quite interested in how programming environments might be taken to the next level - supporting open distributed collaboration, integrating services and applications written by many independent developers. When I evaluated Lisp and Scheme for this purpose (eight years ago), I ultimately dismissed them due to a myriad of security and performance issues (including ambient authority for 'eval' and pervasive mutability of the common data structures).

Alas, as a pragmatic matter, I suspect that you made the right decision - but you shouldn't blame lisp or Scheme. For example, it was once and presumably still is true that in Guile Scheme, the module system can be manipulated so as to create sandbox environments in which untrusted code can be run and afforded only externally mediated access to shared data, memory, and CPU. That capability has not been especially polished or explored, to my knowledge, however (it has simply never been a priority). For almost as long as Guile has existed, other projects have existed that were better resourced and had those issues as a priority. Early on, for example, there was "safe Tcl" and (while it isn't a perfect match, is close) Java. Today, of course, Javascript is fairly heavily armored for such use, at least in the domain-specific environment of a browser. To the extent that you wanted an off-the-shelf language and mostly wanted to avoid hacking at the language or core library level - there were probably more convenient choices than Scheme, at least.

Emacs Lisp only adds to these problems with its dynamic scoping.

And it's "flat" top-level environment, yes.

You need to be careful with measuring failure in terms of complaints. Not all failures are accompanied by an audible whine. People have a tendency to complain most loudly when a system is already close to what they feel they need, and it looks to take only a few small changes to fix it.

It's (perhaps) unfortunate that internal politics at Netscape combined with early Java hype diverted an initial effort to provide a dialect of Scheme for scripting into the prototype-escaped-from-the-lab, Javascript. We'll never know for sure, of course.

eval can be used "securely" for untrusted code if it can be invoked within a suitable sandbox, depriving the untrusted code of access to state it ought not see or touch and limiting its space and time consumption

The idea that security can be achieved by use of a sandbox is one of those stubborn, dangerous memes that requires regular correction. So I'll do my part and note here: a service is not 'secure' if you are prevented from accessing it when you have the authority to do so. Indeed, a common security attack is denial of service. If some untrusted foreign code/object/user/etc. comes to your machine, and had authority to use a global service at its original location, it had darn well better be able to use that same service (literally the same service, such as access to the same database or filesystem) from its new location. Anything else is incorrect and insecure.

Sandboxes prevent use of non-local authorities. They only 'deny service'. Thus, they are only properly secure if the foreign, untrusted code does not represent a composition of non-local services - that is, its effect must be entirely local. A significant and interesting portion of not-fully-trustworthy code on any machine - including libraries and applications and plugins and web apps and mashups - involve composition of services. This makes sandboxes a very unfortunate choice as a security mechanism.

In practice, when untrusted code is too restricted to perform things it should have authority to do, it either cannot be distributed (which has issues for performance and for disruption-safety) or will be distributed anyway - but outside the sandbox (e.g. as an OS-layer application or library or plugin) thereby obtaining too much authority, risking the integrity of the host. If we're ever going to have a practical security solution - i.e. one that people won't feel a need to work around for every non-trivial composition - sandboxes in their common form cannot be a major part of it.

It isn't as though there aren't good alternatives. Capabilities offer a correct, compositional, and secure solution.

Be very skeptical of sandboxes. Spread the word.

it requires a conspiracy between eval and other features before those problems occur. Eval can't single-handedly pull off the crime.

Uh, strictly true I guess, but eval conspires with almost any other feature to cause the problem. Such as first-class functions. And set!. And plugins or libraries or extensions.

. If some untrusted foreign code/object/user/etc. comes to your machine, and had authority to use a global service at its original location, it had darn well better be able to use that same service (literally the same service, such as access to the same database or filesystem) from its new location.

Nonsense. The question is how certain I am about the code's purported authority, not its actual authority.

If the code that came to you from some machine wants to do what it did on that machine, from your machine, you can always restrict it to delegating back to the machine it came from to do that stuff.

There are all sorts of reasons why untrusted code won't be able to access that resource otherwise... perhaps the most aggressive and common is firewalls.

WCF actually does funky things with binding schemes to circumvent firewall problems. They have ways you can transfer requests from the edge of a network such as a proprietary SOAP binding into something more likely to reach a client machine, like HTTP binding. -- I can't think of examples off the top of my head since I have not used WCF for anything that complex. Tim Ewald just told me about it once when I asked the general question about it.

In order for a service to do what David suggests, it would have to do things like automatically analyze the addressability of endpoint machines. Solving addressability problems may not even be possible, at least not without the help of advanced protocol standards like IPv6 and Teredo.

It is best to think in terms of manipulating shadows instead...

Firewalls are themselves a symptom of insecure service design and would be unnecessary - and totally undesirable - if we favored secure protocols and service composition. Fortunately, there are ways to work around firewalls to allow alternative designs. Indirecting through an intermediate service on a common port (e.g. HTTPS or SSH) works on most networks.

I do not advocate 'analyzing' addressability. I would advocate getting rid of firewalls, or working around them wherever necessary.

An angle I'm pursuing involves overlay networks, allowing a logical addressing scheme. This greatly diminishes the need for physical addressing, and can also help in many other ways: scalable multi-cast, automated redundancy, survivable and disruption-tolerant networks, quick recovery (i.e. using an overlay, you can ask to be told when so-and-so is back online via asking his logical neighbors to notify you), a basis for an open 'cloud' of services and computational power (integrating with markets and trust: granting space and compute resources, earning credit, borrowing when an intense compute is needed), and so on. A 'web service' developed from a laptop could still be handling hits on the cloud even while disconnected, and could update pages on reconnect.

Pastry or Tapestry or Chord look like good starting points, and at least one paper (Secure routing for structured peer-to-peer overlay networks by Miguel Castro, Peter Druschel, Ayalvadi Ganesh, Antony Rowstron and Dan S. Wallach) explores how to secure them against conspiracy and such.

Secure logical addressing based on - for example - an SHA-1 hash of an RSA public key - allows for easy integration with capability systems. The 'secure' address allows one to build a challenge before sharing a capability - prevents others from 'pretending' to be a system - and does so without requiring a certificate authority or trusted intermediary of any sort. (Redundant capabilities distributed to the cloud are a bit more expensive to use without accidentally sharing them, involving a challenge to prove that the remote host of the redundant cap already holds the specific capability without ever saying what it is. But that can be done, too. Multi-homed caps are another alternative.)

[Edit: Are we seven degrees from 'more consistent macros', yet?]

The question is how certain I am about the code's purported authority, not its actual authority.

That's a good question. Capabilities (including object capability model for online work, and SPKI or certificate capabilities for offline work) offer a fine answer to that question - a solution to the problem of proving authority. Capabilities do not depend on "trust".

To say that trust is not transitive is correct and true. But it need not be an issue. If a foreign service doesn't trust you with an authority, it may choose to not distribute the authority - or the code or object that requires it - to your machine. This results in a normal client/server style architecture, where certain authorities (such as direct access to a database) are carefully hoarded on the 'server'.

But you shouldn't be too concerned if the foreign service grants you too much authority. That's their problem, not yours. No, in the role of a user - of a host of foreign code - your concern is that you might grant too much authority to an untrusted foreign service!

Sandboxes are an attempt to prevent granting too much authority to foreign services. Unfortunately, they also block the authorities actually possessed by the local component of a foreign service, which is a problem. This forces us to breach sandboxes for most 'interesting' applications. But, unfortunately, these breaches are not precise (i.e. an application with any need to access a network tends to grant access to the whole darn network, plus offer any untrusted plugins and such access to the same network). And even if they could be made precise, you'd run into the problem you describe: "how certain am I about the code's purported authority?". Sandboxes put that onus on the sandbox manager - which, at least in Microsoft Vista, means the user. Capabilities put that burden of proof on the foreign service.

Anyhow, to bring this back to the thread topic: eval offers too much authority to the code it evaluates, quite similarly to how OS's offer too much authority to the applications they run (and applications offer too much authority to the libraries and plugins, etc.). Eval wouldn't introduce security problem if it didn't grant any default authorities to the code being evaluated (i.e. no ambient authority, no access to lexical or dynamic or global contexts).

If the host language and its libraries were designed with security in mind it may even be okay to explicitly provide authorities to eval. Lisp doesn't qualify here, nor do many other languages. In languages not designed for security, offering rights to a banana may grant control of the whole darn jungle, e.g. with Ruby or JavaScript or SmallTalk where classes are mutable and contain upwards references to parents mutable global space. Some languages, such as JavaScript (through implicit arg) and SmallTalk and Java (through stack inspection), also grant access to the caller of a method... which is a similar security problem if you don't fully trust the callee (which might be a foreign object).

But if you removed all the security problems from 'eval', you don't need 'eval' to be part of the language at all. Modulo type-safety issues, it could be a plain old library function that translates inputs into first-class functions then executes them. Or it could be provided as a capability (which might be provided by a foreign service, which might be hosted by a local component for performance...). Either way, there'd be no access to scope of the caller except as explicitly forwarded. And if it was a capability, then libraries wouldn't be so likely to depend upon it, would only demand an 'evaluator' as a dependency if there was real need.

Most of the performance issues (excepting any related to repeated evaluations or reactivity) would also be cleaned up, since eval would just be another call. There'd be no relationship between eval and macro expansion; any macros in the 'evaluated' code would also need to be defined (or imported from a recognized resource) by the evaluated code. One could handle repeated-evaluations and reactivity performance issues by (instead of immediate evaluation) compiling into an first-class function or thunk or FRP expression or whatever. This result could then be used normally.

This is the approach I favor - keep eval outside the language, and reduce to a first-class function or procedure or FRP expression ASAP rather than distributing or importing 'evaluate' capabilities all over the place. I don't need eval or first-class lexical contexts to be part of the language to support runtime introduction of code. The needs of an 'exploratory, incremental' programming environment can make do with a much more constrained and structured evaluator.

And if I want a "a powerful and flexible tool for exploring and tweaking the running image", those also could also be provided as a set of debugging and system administration capabilities, rather than an ambient authority of the language. They can be provided fully separate from evaluation.

Not sure why capabilities and sandboxes aren't dual? In case of sandboxes all services are accessible except of those which are not ( e.g. general file system operations ) whereas in case of capabilites no service is accessible except of those which are granted by having object references.

Stable sandboxes whitelist the legal ambient authorities, rather than blacklisting the illegal ones. Many sandboxes are implemented in this manner. Thus your above characterization of sandboxes isn't correct.

In a sandbox, all authority you possess is ambient. This includes such mundane authorities as allocating memory or adding two and two to get four. It also might include access to a network, or filesystem. Services are represented by source code (procedures, frameworks, libraries, modules, plugins, applications, etc.) that intelligently combine these ambient authorities to a useful effect. For example, if you have authority to the TCP/IP service, and you have authority for display, mouse, and keyboard, you might create a web browser. Given access to a persistence service (usually a filesystem, but you could leverage the TCP/IP service to access a database), you could even add caching, bookmarks, customizations, etc. The authorities are (with very few exceptions) generic, which is a source of danger: it is very difficult to specify how those services may be used. For example, how do you prevent a system with network access from sniffing your local network and firing messages off to we-love-spyware.com? This results in painful hacks to further limit rights in the sandbox, such as the same origin policy in JavaScript.

In an object capability system, very little authority is ambient; without any designated authority, one can do such things as adding two and two to get four or allocate new objects. In a generous system you might get access to estimated wall-clock time, random numbers, or support for delayed or periodic events (read 'generous' with some degree of derision; even ambient authorities for time and random numbers can later prove a hassle, as for testing). But all significant authority (for someone's definition of 'significant') is provided from the outside in the form of references to objects. These references are called 'capabilities'; possessing a capability designates authority - both a right and the ability to exercise it. Some capabilities may hook external systems, such as actuators or sensors or Oracle databases. Unlike the sandbox, capabilities usually represent specific authorities, such as a specific file, a specific console, or HTTP access to a specific URI. Services in a capability system are represented mostly by these external capabilities, but new services may be developed that combine other capabilities in intelligent ways. New services are usually represented by new capabilities.

The differences between sandboxes and capabilities are especially significant when it comes to foreign code.

In a sandbox, remote or foreign code - which in essence includes all libraries, applications, and extensions that you downloaded rather than wrote yourself - must also rebuild its authorities by intelligently combining ambient authorities. Thus, foreign code must be granted excessive authority lest the authority prove insufficient to combine into the required services. The sandboxes help only a little in curbing this vastly excessive authority. Therefore, you are forced to develop a trust relationship with every little bit of foreign code. In practice, that means just about everything on your machine. Unfortunately, not everything on your machine is worthy of that trust; even if you trust the developers, you should expect errors.

In an object capability system, however, foreign code just directly embeds whichever authorities it needs^*. It doesn't reproduce these using ambient authority^**. Since foreign code in an object capability system doesn't embed any local authorities that you don't specifically provide it, you can run it with confidence that it never has more authority than it would have gained if it were running remotely. This is a very powerful security guarantee, assuring that distribution is purely for performance, disruption tolerance, to leech your CPU resources, and other relatively benign reasons. (You can cover the leeching-resources angle later, via integration with a market and associated reduction of ambient authority to repeatedly add two and two to get four.) On the other hand, while object capabilities fully protect you from the foreign code, they don't readily protect the foreign code from you. You might gain more authority than you would have obtained if the foreign code was being run remotely. It's up to the distributor of the foreign code to protect his own interests (i.e. by controlling distribution of the more sensitive capabilities). The fact that capabilities tend to be very specific helps this purpose a great deal, since it minimizes any abuse you might perform with foreign capabilities you hold.

_{*: Since foreign code includes various roles currently held by libraries and applications in ambient-authority systems, it is interesting to note that persistence is a far more important feature for scalable performance in a capability-system. Persistence enables the capabilities embedded in distributed code to be long-term stable, which means that distributed code can go much longer without becoming invalidated. Various mechanisms for invalidating distributed code also pave the way for runtime upgrades.}

_{**: for certain 'harmless' object capabilities - such as wall-clock time, or a random number generator, or a subscription to a periodic 10Hz callback - the language runtime is, of course, free to optimize by providing a fully local implementation. I once called these 'ambient capabilities', but the object capability community didn't like the risk of confusion with ambient authority and object capability. This also relates to the Unum pattern.}

Anyhow, I do not believe one can find a proper duality between sandboxes and capabilities. You may, perhaps, find one between ambient authority and capabilities in the most general sense, but even that would likely be a false duality if one looks at the resulting practices (such as sandboxes).

There is, however, a capability design pattern that acts as 'dual' to the ambient authority Sandbox pattern. It is called the 'Powerbox': an object that provides access to all the interesting things you might need: filesystem, network, etc. The powerbox is passed as an argument to 'main'. A powerbox, however, is not an ambient authority; you can obtain from the powerbox a capability to a specific file, for example, then pass just that forward. Thus you have a lot of control over how authority is distributed, and presumably you would leverage this control to use capability design patterns and build high-level services from the lower-level services in the powerbox. But you could treat a Powerbox just like a Sandbox by dropping the whole box (or just the whitelisted pieces of it) into a dynamic scope then doing everything else as per the Sandbox design.

To be clear: I don't recommend use of the powerbox design pattern. It might be useful and convenient for translating applications designed for ambient-authority into an object capability system, but a powerbox still represents the same wildly excessive authority that sandboxes grant. They also fail to capture the high level and specific services that really define capability patterns.

Rather than a powerbox, the proper 'capability-oriented' solution is to simply deprecate the idea of starting 'applications' via a 'main' function. That whole 'start from main' design is a symptom of ambient authority construction, where all the services must be intelligently rebuilt from scratch, loading the appropriate libraries and plugins to help out in the rebuilding process. Since we don't need to waste effort rebuilding 'external' services, we can focus on composing them. We can think in terms of integrating and maintaining 'live' services from a capability-aware IDE or command shell in much the same way we, in Unix, create pipes and filters services between specific files and commands. One might examine Lotus Mashups (was QEDWiki) to see what such an IDE might look like.

Let's assume they are dual for a moment. Constructing capability-secure programs corresponds to structural inductive reasoning with authority. What sort of proof method is the dual of induction, and is it usable? By the above assumed duality of capabilities and sandboxing, this proof method will correspond to sandbox-style reasoning.

I think the 'dual' often depends on which characteristics of the system you're emphasizing in your model; given that there may be more than one model or emphasis, there may be more than one dual.

The common dual to structural induction is coinduction (which, appropriately, destructures things). In this case you might describe the relevant coinduction in terms of narrowing and extracting specific authorities from a larger pool of 'ambient' authorities. This duals well with the act of constructing higher level (potentially generic) authorities by combining specific authorities.

The sandbox, however, represents the pool of ambient authorities available for exatraction, which is just one element of the ambient authority 'coinduction' model. (In particular, sandboxen provide a mechanism to control the size of that initial pool.) Thus, from the above, one might say the 'ambient authority design' as a whole (which is a de-facto standard) is the dual of the 'capability design'.

The dual of a sandbox is not capability model, but rather a set of initial capabilities available for combination. But because the implicit comparison above is software development to a product with common final authority, the 'dual' to the sandbox in the above sense is a set of initial capabilities that are just enough to combine into the same resulting final authority (with very few or no intermediate 'narrowing' patterns, such as facet pattern). The authorities embodied by the set of initial capabilities is necessarily much smaller, fine-grained, and more specific set than is represented by the sandbox!

OTOH, one could instead focus one's attention to initial authorities. If one pools capabilities to precisely match a sandbox's ambient authority, the result is a powerbox. We can produce a direct relationship between sandboxen and powerboxen.

Constructing code with a powerbox tends to follow ambient-authority style patterns, except that the 'pool' of initial authorities is reified and must be explicitly passed about (which offers considerably more control over its distribution).

Thus, from the above, one might say the 'ambient authority design' as a whole (which is a de-facto standard) is the dual of the 'capability design'.

This largely agrees with my understanding as well: ambient authority is the only property separating a capability design from a non-capability design. The rest of capability principles follow naturally from trying to make a usable system once you remove ambient authority.

Sandboxing takes another approach entirely to mitigating the problems with ambient authority. I would liken it to the Haskell vs. Worlds approach to side-effects, where capabilities are the "pure" Haskell approach, and Worlds are a sandboxing approach.

Worlds paper is a bit misleading. There are of course side effects in the Worlds model; moving the program counter is a side effect!

I wouldn't say that capabilities and sandboxes are dual so much as the former is built atop the latter.

As I understand (perhaps incorrectly, of course), dmbarbour's notion is that access to services should be via the resolution of logical names and require the presentation of a suitable cryptographic authority. I think that that's a reasonable position to take for many services. That part is all good.

Now, let us consider a lisp-style system in which we apply such policies. Let's consider the components that go into its construction:

Logical addresses don't magically resolve themselves. Resolving such a name and accessing the service ultimately requires some low-level capability such as putting packets on a wire or taking a system trap to invoke a file system call.

Taken as a whole, our system has components which are privileged to enjoy such low-level, open-ended access and other components whose access to those low-level components must be mediated through a trusted capabilities enforcement layer.

In a lisp-style world, we would often want these low-level and restricted components to reside within a single "universe" - a single system image. The Ultimate Authority lies (figuratively speaking) with the privileged operator sitting at the console and this single image approach consolidates that legitimate authority in an integrated environment.

How, then, do we restrict *some* of the components in this image solely to their capability-based access? Well: by sandbox. (In a non-lisp version of the scenario - say, a unix-like kernel hosting the capabilities-constrained components - we still have a sandbox. The only difference is that we have made it more awkward for the console operator to hack at all levels of the system.) One way or another, sandboxes are *necessary* to implementing a capabilities-based environment.

(This answers/unasks naasking's question of "what is the dual of the structural induction used to prove things about capabilities systems?" We don't need a dual - we only need our sandbox functionality to be capable of constructing capabilities-based sandboxes. The same forms of induction are used without translation with respect to those particular sandboxes.)

I wouldn't say that capabilities and sandboxes are dual so much as the former is built atop the latter.

This is incorrect as a universal, unqualified statement. Capability systems can be built atop sandboxes, but they do not intrinsically require sandboxes in all cases. Taking the notion of "sandbox" loosely, a capability system might require a sandbox to run atop current commodity systems, but only because such systems export ambient authorities by design, which by itself requires a sandbox in order to simulate any other type of access control. In other words, it's the design of the underlying system that requires the use of a sandbox, not capabilities themselves.

I see what you are saying (I think) but - well, no. At the bottom of the stack I'm pretty sure we want rather open disk controllers, network controllers, etc. under software control. Even if the HW is helping to enforce cryptographic barriers around, say, device registers I still think we don't want to create stupidly dangerous machines in which there isn't a software end-around of that.

In other words, it isn't (only) the design of the underlying software system that requires a sandbox: ultimately, it's the design space of "reasonable" hardware.

You're logically correct in a narrow way that I should in principle include "sane hardware" as a qualifier. And, yes, that does open an unresolvable debate about what hw is objectively "sane". But, really....

Even if the HW is helping to enforce cryptographic barriers around, say, device registers [...]

Crypto isn't required. Memory-safety right down to the addressable byte is all that's required for capability secure hardware on a single host. Crypto is only required to establish an equivalent safety property for programs running on different machines.

I don't see why such memory safe hardware isn't "reasonable". Current hardware provides ambient authority, in that you can forge addresses and such, but most hardware now provides sandboxes via segmentation hardware or the MMU. Capability hardware would be the equivalent of something like a memory safe lisp machine or a typed assembly language.

Neither sandboxes nor capabilities are more "fundamental", except as a function of the current context in which they are running, ie. OS, CPU instruction set, etc. However, I will simply note that as far access control systems go, capabilities can simulate ambient authority systems without extensions, but ambient authority systems require the addition of sandbox-like mechanisms to simulate capabilities; such extension are outside the scope of typical access control list systems. This implies that capabilities are more expressive, which says to me, that we want capabilities at the core.

I've nothing against either memory protection or even hardware assist with crypto barriers. Memory safe hardware *is* reasonable.

What would not be reasonable is hardware that prevents privileged software (such as a kernel) from bypassing memory protections wherever the console operator (so to speak) chooses. And in a "single image" view of the world (a lispish view, in some ways) - the code with control over how the memory protection is used and the code running subjugated to memory protection are both part of the same image, properly under full control of the console operator. In the lisp aesthetic, we tend to consolidate that control in a single system image and expect suitable features from the language for such purpose.

Suppose that this were not the case. In that event, the "console operator" - who's authority over the machine ought to be absolute - may be forced to cede authority to a software vendor who provides the kernel. By gosh, then you would have a DRM system and before you knew it some momentarily popular vendor would be insisting on editorial control over what programs users are permitted to run on their own hardware. For example, such a vendor might create an "app store" and maintain exclusive and arbitrary control over its inventory, permitting no wide-spread dissemination of programs for the platform other than those of which they approve, regardless of their reasons for picking and choosing.

I disagree with the thrust of your last paragraph but mainly in nitpicking ways that aren't especially interesting or enlightening to rehearse so I'll skip the "expressiveness" and "which is more fundamental" issues other than what I said above.

So what you're saying is that you don't want hardware that only listens to you if you can provide a proof that you know its personal secret (may have many secrets for different caps, too).

I'm not so sure I agree. That level of security - and safety - would be useful for a lot of features. Operators of hardware aren't always the owners. When dealing with a weapons platform, I think this sort of security would be extremely useful.

But I would object to not getting my keys for commodity computer hardware! And I can totally see the scenario you describe happening. I can see why you'd worry.

So what you're saying is that you don't want hardware that only listens to you if you can provide a proof that you know its personal secret (may have many secrets for different caps, too).

I'm not so sure I agree. [....]

I'll answer slightly "mystically" and then (please) let's let the subject drop in these particular LtU threads (where, indeed - we've drifted too far from the interesting topic of macros). So, please indulge me once more; last word is yours if you like; let it drop (here in the threads of this particular post).

There is an old half joke about why the DEC PDP series of computers were named "PDP". You see, it stood for "peripheral data processor". A peripheral data processor allows for a user-configurable transformation of electronic input signals to electronic output signals using a turing complete configuration mechanism and a digital interpretation of I/O signals. They are handy little boxes. A peripheral data processor is distinct from a computer mainly because while many firms impose a central authority over budgeting for computers, purchases of peripheral equipment may come from any departmental budget. A department might purchase, say, a PDP-11 without having to go through the executive approval process for the purchase of a computer.

DRM is about political and economic subjugation. The only questions are (a) who is to be master and (b) who is to blame when, in an emergency, the hardware that could save the day turns into a brick because the people on the scene lack access to a built-in random number. The only right answer is "no" - even in life-critical applications. For example, I doubt but could only hope that in the classic "two key" systems for launching nuclear missiles, if only the two attendants are left standing over the missile, that either is free to shoot the other, crawl under the console, cross two wires, and launch. It should go without saying that it's even much, much better if every missile is secretly a dud. Even if you tone down the rhetoric and limit consideration to just cultural artifacts like books and video, you quickly find that DRM is well down a slippery slope towards an Orwellian dystopia (c.f. RMS' prescient "Freedom to Read" essay from years ago).

But I would object to not getting my keys for commodity computer hardware!

The only reasonable key you should hold is the simple and by-passable key to the door of your equipment room, if you ask me. If you accept the more pernicious keys you suggest you will also be forced to accept legal restrictions on how you may use them. And in a life-critical emergency where you are not present or able to give out the keys, you'll be regarded as a tragically paranoid villain. And meanwhile, you'll be reinforcing the creation of a Ministry of Truth. There's no excuse for DRM. There's no excuse for hardware that is *that* hard to seize control of, even for the purpose of manipulating digital cultural artifacts.

I think you underestimate the utility of secure hardware. Unencrypted HDDs and flash drives are subject to theft of massive amounts of private data. Encrypted keyboards might allow one secure integration with a remote desktop. In competitive multi-player gaming, honesty isn't a resource you should rely upon when attempting to achieve fairness, so you might want some security devices to help out [1] [2].

Pervasive computer security will create a 'law' of its own, complete with markets and trade. You are correct that the question is: whose interests will this law protect.

With few exceptions (mostly that involve information theft or specific anti-cheat devices) I'd want physical control over hardware to equal ability (even if not legal authority) to fully use it.

What would not be reasonable is hardware that prevents privileged software (such as a kernel) from bypassing memory protections wherever the console operator (so to speak) chooses.

It's unclear that privileged kernels are ultimately needed where it's "capabilities all the way down". An OS like EROS is very much built like a Smalltalk image, and the only responsibility of the microkernel is to manage memory mappings which enforce the "memory safety" property for capabilities via process granularity sandboxes, and to provide a safe communication channel between sandboxes.

If loads and stores are themselves controlled by capabilities, ie. are memory safe, then the microkernel becomes superfluous. This requires some changes to the instruction set obviously.

Ultimately, the operator can only perform actions for which he has permission, which are subject to any space or time use policies enacted by the machine owner. You assume in your post that operator and owner are synonymous, but of course this need not be true. The owner allocates to an operator, a schedule and an account which is charged for space use, and the operator can do anything he likes with that time and space. Essentially the approach used by hypervisors like Xen, but capabilities allow finer accounting.

In that event, the "console operator" - who's authority over the machine ought to be absolute - may be forced to cede authority to a software vendor who provides the kernel. By gosh, then you would have a DRM system

Indeed, and this has been discussed on cap-talk once or twice. This is essentially a situation in which the operator is not the owner of the machine. However, I don't think such scenarios are worth worrying over, since buying a machine and not owning it flies in the face of so much property law that it's inconceivable you'd have no right to replace what it's running.

Combined with the inevitable open source counterculture to any such monopolistic approach, I don't think DRM will ever be successful, but I agree that the further down you push capabilities, the more technically viable this approach becomes. I think only social rather than technical solutions are needed, since social forces would be driving their adoption. Open source is the social solution to software monopolies for instance.

Capability systems intended for humans would probably want to follow Capability User Interface principles (for Secure Interaction Design Ka-Ping Yee).

In essence, "the privileged operator sitting at the console" would - as you suggest - be "The Ultimate Authority". The operator has a large registry of powers - of capabilities - both foreign and domestic. The 'console' provides a User Interface that supports the operator in developing and maintaining services and in executing tasks that integrate his or her capabilities. Many actions produce new capabilities - for maintenance, for interaction, for execution - that would automatically be stored for further composition or later sharing.

The new mantra becomes every thing is a set of fine-grained capabilities. But a lot of meta-data is associated with these capabilities, which helps the UI support the operator (i.e. allowing for useful searches, automated suggestions, tab-completion, type-safety analysis, minimal sensitivity and pervasiveness annotations for varying automated-distribution properties, etc.).

But there is no need for a sandbox! A sandbox suggests that these tasks execute in an 'environment' (a box, with sand) and that the tasks themselves are responsible for picking and choosing, based on their meta-data (name, purpose, type, etc.), which capabilities to actually utilize for the task. In general, the operator should be capable of providing the exact (or near-exact) set of specific capabilities the task requires. The 'inputs' to the task are first-class capabilities rather than names of capabilities in the environment. If it's really convenient, the operator is of course free to provide a registry/factory of caps and meta-data that can serve as a powerbox (not really a sandbox since it isn't ambient), but this can be discouraged except where it is truly necessary.

A sort of balance to reduce operator burden would be to provide moderately fine-grained 'packages' of capabilities (i.e. records of fine-grained caps) identified based on the 'roles' in which a task or new service is taking part [note 1]. For example, one might provide a cap package that has fine-grained caps to both control motion of and receive information from a particular webcam (separate caps), thus diminishing risk of accidentally specifying control for the wrong webcam.

Anyhow, some differences I believe differentiate capability systems and sandboxes:

• Unlike in a sandbox, foreign objects (messages, first-class functions, actors, etc.) represented in a capability system can generally [note 2] carry foreign authorities.
• In a sandbox system, an object or message that contains a foreign capability (object reference) often does not guarantee the ability to exercise it. The same origin policy offers example of this failure.
• Also unlike a sandbox, foreign code in a capability system is granted no special ambient authorities. Capabilities it obtains from you are the same ones you might have sent across the network if the foreign code happened to be executing remotely under perfect network conditions.

A sandbox is historically defined by how it manages ambient authority for foreign code. Taking away all significant ambient authority is only the most degenerate form of sandbox, and is also a property of capability systems, so can't be used to distinguish between them.

Some modern sandbox implementations are hybrid capability systems allowing objects from 'different' sandboxes to interact within a common runtime image, each possessing a local set of ambient authorities. A pure object-capability implementation of this pattern is straightforward enough: every object has a reference to its own personal powerbox of ambient authorities. This reference is provided as an implicit constructor argument by the object that created it. All the calls that would normally be ambient are instead exercised through this powerbox. Message passing, thus, also triggers an implicit 'context switch' between ambient authorities. This implementation is efficient enough, but I disfavor the ambient authority based design.

_{[note 1]: while tempting, one should resist thinking in terms of packages for UI caps such as (mouse,keyboard,display). It's a really bad idea to grant access directly to keyboard, mouse, joystick, video, etc. to arbitrary tasks, because this utterly fails to capture such issues as: transfer of operator focus, scalability to multiple UI tasks, caching, remote accessibility - ability for operator to move a UI to a new host, collaborative UIs - linking and mashups, etc. I believe pursuit of document-based designs for UI would be a better place to start. One could provide caps to 'specific' consoles, log files, etc., which may themselves be displayed at multiple locations with multiple operators...}

_{[note 2]: there are a few 'confinement' patterns developed to support the ambient authority 'applications and libraries' design in capability systems. These necessarily involve inspecting an object containing foreign code and rejecting it (or transforming it) if the object contains any 'unapproved' capabilities. Transforms may include injection of intermediate objects for auditing, or blanking them (replace with nil). These patterns aren't nearly so useful in a world that moves every year closer to 'web applications' and 'clouds' of services. They were designed for KeyKOS, for an era when most interesting authorities were local.}

But there is no need for a sandbox! A sandbox suggests that these tasks execute in an 'environment' (a box, with sand) and that the tasks themselves are responsible for picking and choosing, based on their meta-data (name, purpose, type, etc.), which capabilities to actually utilize for the task.

That you find yourself saying "suggests" should suggest something to you.

The sandbox metaphor simply means that the unemancipated subjects placed in the box have, for the duration of their stay, no access to certain significant resources outside of the box except those to which the privileged supervisors see fit to give them access. In that sense, "capabilities" is the name of a family of protocols by means of which the unemancipated occupants of a sandbox may negotiate with the world outside the sandbox.

Again, consider a (typical) machine on which the execution of certain instruction sequences permits arbitrary content to be transmitted to a network by directly manipulating the control ports of an I/O device. And consider the (typical, and necessary to have to implement capabilities as you seem to mean them) situation wherein it is possible to run arbitrary code while enforcing the restriction that that subjugated code can not possibly manipulate those control ports arbitrarily. The subjugated code subject to those constraints is running "in a sandbox".

You appear to be setting up a strawman by insisting that "sandbox" is a far more specific term of art than it actually is, then attacking that strawman, and getting confused in the ensuing melee.

execution of certain instruction sequences permits [...] it is possible to run arbitrary code while enforcing the restriction

You assume that the 'code' is inherently capable of expressing the restricted ambient authority.

In capability languages, one removes the ability to even express significant ambient authorities. All significant authorities are expressed in terms of capabilities. And the ability to express a capability is equivalent to authority to use it. Thus, in capability languages, it is impossible to express security-restricted behavior. (One may express safety-restricted behavior, but the static or dynamic type-system or higher layer consistency management can handle that.)

Since there is no expression of restricted behavior, there is no need for a sandbox to subjugate such expressions. No supervisor is involved in deciding which instructions a 'sandbox' should allow or forbid. No permissions are checked. There is no analysis or rejection of well-formed code on the basis of it potentially violating a security policy. In every sense that matters, there is no sandbox.

Of course 'typical' machine-code is a language designed around ambient authorities. Thus, we don't use typical machine-code as trade language for capability systems.

The sandbox metaphor simply means that the unemancipated subjects placed in the box have, for the duration of their stay, no access to certain significant resources outside of the box except those to which the privileged supervisors see fit to give them access.

This is correct. It is also why sandboxes are not at the base of capability systems. A capability system can obtain considerable authority beyond that allowed by a sandbox: (1) Foreign objects in a capability system (actors, messages, modules, whatever) can embody capabilities when they are distributed (including via download or install), independently of the supervisor. (2) Capabilities can be obtained through communications with arbitrary resources, not just the supervisors.

Just because capability systems without any capabilities are the same as sandboxes without any privileges does not mean you could say one is implemented atop the other. (Using that basis, you'd have an equal argument in asserting that sandboxes are implemented atop capability systems!)

Guile does not work this way any more, Tom. First-class environment representation is simply too slow. It inhibits all kinds of optimizations.

As a consequence, Guile is now much faster.

Eval has nothing to do with Emacs. I know. I am actually working on getting Guile to implement Elisp in a way that will be faster than Emacs' implementation. Properly optimized lexical scoping will always be faster though, because the compiler has a much better understanding about where things will be.

Andy, if it sounded like I claimed that Guile presented first-class environments in Scheme, I'm sorry - I certainly did not mean that it did.

Rather, my claim is simply that SCM and Guile both construct a closure in much the manner described in the first two Scheme reports: by combining the s-exp code of a procedure with a run-time environment and parameter list description. To the run-time system, the environment is (in the general case, at least) an ordinary heap object but I (trivially) agree that neither Guile or SCM has a (the-environment) form or anything like it. (It is also, of course, the case that both interpreters then incrementally rewrite the s-exp of the code during execution. Historically, as far as I can tell, this rewriting was the main innovation and performance improvement over SIOD. The rewriting doesn't essentially change the notion of a closure as a run-time syntax tree combined with a parameter list description and environment.)

Incidentally, I don't see how any optimization you might have added to Guile could or should have precluded adding a reasonable implementation of (the-environment). No functionality necessarily implied by such a form is not also necessary for, say, an interactive debugger. If I am missing something, please tell me what either (as you prefer) here or via email (user: lord, host: emf.net).

Eval has nothing to do with Emacs. I know.

In what sense? For example lisp-interaction-mode and emacs-lisp-mode seem pretty of the essence to me. As does the fact that I double checked the symbol names of those modes by using the eval-expression command to check the value of the buffer-local major-mode variable.

I am actually working on getting Guile to implement Elisp in a way that will be faster than Emacs' implementation. Properly optimized lexical scoping will always be faster though, because the compiler has a much better understanding about where things will be.

Alas, we topic drift. Perhaps this is a discussion to move off LtU. My last word on that here: How is the elisp implementation effort going? We started down that path years and years ago in the earliest days of Guile. I was never very happy with any of the proposed ways to reconcile Guile's distinction of #f from '() with Emacs' equivocation of the analogous values. I eventually came to regard the effort as part of a pattern of "mission creep" the plagued the early days - but if you are actually getting somewhere with it that sounds like possibly good news. My suspicion "back then" (and still today) is that not worrying too much about elisp compatibility but, instead, redesigning Emacs as if it had used Scheme from the start would be better - especially if the resulting architecture was "similar enough" to GNU Emacs to afford simple implementation of program-assisted manual translation of elisp packages to Scheme. If you go the route, instead, of just trying two "swap out" elisp for Guile Scheme in GNU Emacs, I think that the inevitable demands for quite strict C API and emacs lisp compatibility are likely to keep the project mired in the mud for years and years to come.

Hi Tom,

We're in the forum already, so I'll reply briefly here :) Briefly because I hate these durn text boxes.

Guile's compiled procedures don't have s-expressions in them. Free variables are stored in a flat vector. I wrote something about this here, after the bit about brainfuck.

Eval'd code still uses s-expressions and dynamic environments, but it's much slower. But it is written in Scheme now; see http://wingolog.org/archives/2009/12/09/in-which-our-protagonist-forgoes-modesty, for example.

Regarding Emacs, we have nil, #f, and '() working well, I think. See http://thread.gmane.org/gmane.lisp.guile.devel/8853, for example. Also see my talk, http://www.archive.org/details/ghm2009-wingo-small, from a couple months ago. I'm fairly optimistic that a "swap-out" could work; after all, we've already done it for Guile itself. I'm estimating 12-24 months to get a viable branch.

Ciao,

Andy

Your improvements to Guile sound great but they don't contradict the points I was making. Looking at the posts you mentioned and the current Guile beta release (1.9.7):

If I understand correctly, Guile has gained a nice byte-code VM and in ordinary operation loaded code and expressions from the REPL are first compiled and then interpreted. For the purposes of "clean bootstrapping" (i.e., without needing mysterious pre-compiled images), the coded-in-C graph interpreter is retained but is quite slow (in exchange for being easier to maintain). For the purposes of run-time-eval, a graph-interpreter coded in Scheme (and compiled to the VM) is used. Running code compiled for the VM is generally the fastest available option except where the latency of compilation is an issue.

These appear to be skilled and thoughtful improvements to an extent, long overdue in some respects, and so I think that far from forgoing modesty it is quite appropriate for you to be proud of them. We would not be convinced if you tried to demure. I am vicariously proud for you.

Nevertheless, nothing in your changes to Guile does anything other than give evidence consistent with my thesis that macro expansion is inextricably intermingled with run-time as evidenced by the implications of a form like (lambda (x) (eval x)) for a properly lexical-scope sensitive EVAL or even for the more limited kind of top-level-only EVAL that Guile offers.

[The talk you linked to is interesting but too wildly off topic to respond to here.]

In that case, so does LINQ on .NET.