Dialects of Pixley ================== As is probably inevitable with a project like this, several minor variations on Pixley exist. This document aims to descibe the significant ones, and their relationships with each other. Pixley 1.x ---------- *Pixley 1.x* was the original version of Pixley. It supported two extra forms from Scheme that the current version (2.0) of Pixley does not support: `null?` and `cadr`. P-Normal Pixley --------------- *P-Normal Pixley* is a subset of Pixley where each `cond` can have only one test branch before the `else`, and where each `let*` can only bind one value to one identifier. P-Normal Pixley is a strict subset of Pixley. All P-Normal Pixley programs are Pixley programs; all P-Normal Pixley programs are also Scheme programs. Pifxley ------- *Pifxley* is a language trivially related to Pixley. The only difference between the two is that Pifxley does not have Scheme's `cond` form. Instead, it has Scheme's `if` form. Like Pixley, Pifxley is a strict subset of Scheme. Pifxley is not a subset of Pixley, nor is Pixley a subset of Pifxley (hello, lattice theory!) `pifxley.pifx` is the Pifxley reference interpreter; it is written in Pifxley. It consists of 386 instances of 52 unique symbols in 615 cons cells. This is actually somewhat smaller than the Pixley self-interpreter, which means that if I was going for purely small size in the self-interpreter, `if` would have made a better choice, as a langauge form to support, than `cond`. However, I find `cond` expressions generally easier to write, and the self-interpreter has one big `cond` expression in the evaluation dispatching section. In the Pifxley interpreter, this section is more awkwardly written and a litte harder to follow (you have to pay more attention to how many close parentheses there are.) `pixley.pifx` is a Pixley interpreter written in Pifxley. Pifxlety -------- *Pifxlety* is a language trivially related to Pifxley. The only difference between the two is that Pifxlety does not have Scheme's `let*` form. Instead, it has Scheme's `let` form. No Pifxlety self-interpreter has yet been written as part of the Pixley project, but I will hazard that it would not be significantly smaller than the Pifxley self-interpreter, for two reasons: 1. Some places in the Pifxley interpreter do rely on the fact that previous bindings in a `let*` are visible in subsequent bindings. These occurrences would have to be rewritten to use nested `let`s. 2. Implementing `let` is not significantly easier than implementing `let*`; it is mainly a matter of retrieving the bindings visible to the current binding from an expression which is unchanging over the whole form, rather than "folded in" after each binding. Of course, I may be wrong; I won't know until I implement it. Pifxlety is neither a strict subset of Pifxley nor of Pixley, and neither is either of those two languages a strict subset of it. But Pifxlety is a strict subset of Scheme. For completeness, there must also be a Pixlety: a language just like Pixley except with `let` instead of `let*`. It is not a particularly interesting variation to me, so I won't get into it, except to say that it, too, is not a subset of any of these other languages, except of course Scheme. Pixl_y ------ Now it is of course possible to remove `let` or `let*` _altogether_ from the language. The remaining language, which I'll call *Pixl_y*, does not suffer in computational power, only expressivity. Because expressions in Pixley do not have side-effects, there is no semantic difference between binding an expression to an identifier and then using the identifier twice, and just using the expression twice. So `let*` is completely unnecessary. Even in the absence of `let*`, you're not forced to repeat yourself; you can use `lambda` as a way to bind expressions to identifiers. For instance, (let* ((a (cons b c))) (cons a a)) can be rewritten ((lambda (a) (cons a a)) (cons b c)) Pixl_y is a strict subset of Pixley, and of Pixlety. It is not a subset of Pifxley, but of course there could be a Pifxl_y if you like. P_xl_y ------ If you remove `cond` from Pixl_y you get *P_xl_y*. Without decision-making, you might think P_xl_y isn't Turing-complete; but you do still have `lambda`, and you can thus write expressions directly in the (eager) lambda calculus. It's just that you'll have to come up with your own representations for truth-values -- one common way is to make truth-values functions which take two arguments, with the true truth-value returning the first argument, and false returning the second. And, of course, none of the existing machinery (`equal?` and so forth) supports this, so you'll have to roll your own. P_xl_y *is* a strict subset of every language listed so far -- Pixl_y, Pifxl_y, Pifxley, Pifxlety, Pixlety, Pixley, and Scheme. You could of course continue down this road, removing other stuff from the language (and letters from the name) until you just had one- argument `lambda` and symbols remaining -- and I guess, to match the lambda calculus, you could just call this language *l*. Crabwell -------- Unlike the previous languages, *Crabwell* is a version of Pixley with one extra feature. In Crabwell, an arbitrary S-expression may occur instead of a symbol as the identifier in a binding in a `let*` expression. In addition, the form `(symbol x)`, where _x_ is any S-expression, evaluates to whatever _x_ is currently bound to in the environment. This allows arbitrary S-expressions to be used as identifiers. This variation was invented to overcome a limitation of Pixley, namely, that it lacks any way to create new symbols. This is a significant limitation for implementing program transformations which create new `let*` bindings, such as A-normalization. Crabwell is not a subset of Scheme, and therefore not a subset of Pixley either. However, Pixley is a subset of Crabwell, and there is a trivial mapping between (finite) Crabwell programs and (finite) Pixley programs -- simply rename each S-expression-based identifier to a symbol-based identifier not used elsewhere in the scope in which it resides. Again, Pixley per se cannot do this, because it cannot create new symbols, but a program in a language which can generate a program source text character-by-character could do so. And, I should note, it's not really necessary to translate Crabwell to Pixley, or even to evaluate Crabwell, to reap some benefits from it in the realm of static analysis. If a program translates a Pixley program to an equivalent Crabwell program, perhaps with new bindings generated in it, then proves some property of the Crabwell program, we know that property is true of the original Pixley program as well. `crabwell.pix` is a Crabwell interpreter written in Pixley.