The Pixley Programming Language

Language version 2.0

Introduction

Pixley is a strict and purely functional subset of R5RS Scheme. All Pixley programs are also therefore Scheme programs.

Pixley was designed for "bootstrappability". I aimed to encompass a minimal subset of Scheme that was still expressive enough to permit writing a Pixley interpreter without too much pain.

Semantics

Pixley implements the following functions and forms from Scheme (listed in alphabetical order):

• car
• cdr
• cond / else
• cons
• equal?
• lambda
• let*
• list?
• quote

For the precise meanings of each of these forms, please refer to the Revised^5^ Report on the Algorithmic Language Scheme.

Pixley only understands the Scheme datatypes of lists, symbols, function values (lambdas), and booleans. Pixley's behaviour regarding any attempt to produce a value of any other type is undefined. Neither is its behaviour defined for s-expressions which result in errors when evaluated as Scheme programs.

Syntax

Pixley's syntax is a strict subset of Scheme's. The meanings of syntactical constructs which are valid in Scheme but not defined in Pixley (such as numbers, strings, comments, quasiquoting, or hygienic macros) are undefined.

Of literal values, only those of list type can be directly introduced through syntactical elements. Like Scheme, a literal null list can be denoted by (quote ()). (However, () by itself is considered to be an illegal, empty application.) Literal symbols may be introduced through the quote form, literal function values can be produced through the lambda form, and the two boolean values can be produced through the use of trivial tests such as (equal? (quote ()) (quote ())) and (equal? (quote a) (quote b)). (Note however that Pixley's test suite does generally require a Pixley implementation to be able to depict truth and falsehood in the output as #t and #f, respectively.)

Reference Implementation

The reference implementation of Pixley, pixley.pix, is written in 124 lines of Pixley (or, if you prefer, 124 lines of Scheme; and if you prefer more Scheme-ly metrics, it consists of 413 instances of 54 unique symbols in 684 cons cells.)

pixley.pix does not include a lexical processor: the Pixley program to be interpreted must be made available to the interpreter as a native s-expression. Since Pixley does not implement define, this is usually achieved by applying a textual copy of pixley.pix (a lambda expression) to the s-expression to be interpreted as a Pixley program.

Because pixley.pix is written in Pixley, multiple copies can be applied successively with equivalent semantics. For example, having pixley.pix interpret some program foo.pix should produce the same observable behaviour (modulo performance) as having pixley.pix interpret pixley.pix interpreting foo.pix, or having pixley.pix interpret pixley.pix interpret pixley.pix interpreting foo.pix, etc. etc. ad infinitum. The test suite for the Pixley reference interpreter does just that, running through the set of tests at successively higher "degrees". This is an example of a computational automorphism and is a property of any bootstrapped universal computer (or rather, of the Turing-complete language of that computer.)

The Pixley reference interpreter is highly meta-circular, implementing e.g. Pixley's car simply in terms of the underlying Pixley (or Scheme) car. The datatypes of Pixley are likewise directly represented by the corresponding datatypes in the underlying language.

Environments are represented as lists similar to association lists, except containing two-element sublists instead of pairs, because Pixley can't directly represent pairs. Each sublist's first element is a symbol naming the identifier, and the second is the value to which it is bound.

History

Note that this is only the history of the programming language itself; for history of its reference distribution, see HISTORY.md.

Pixley 1.0

Pixley 1.0 was released on May 1st, 2009, from Cupertino, California.

In addition to the 10 Scheme symbols listed above, Pixley 1.x also implemented the Scheme functions cadr and null?. However, it was found that the interpreter was actually shorter if those functions were defined only locally within the interpreter. They were thus removed from the Pixley language in version 2.0. It is easy enough to apply the same technique to any Pixley 1.x program to convert it to Pixley 2.0; simply wrap it in the following:

(let* ((cadr (lambda (alist)
         (car (cdr alist))))
       (null? (lambda (expr)
         (equal? expr (quote ())))))
  ...)

Pixley v1.1

Pixley 1.1 was released on November 5th, 2010, from Evanston, Illinois.

Funny story! So I was writing writing stuff in C to compile with DICE C under AmigaOS 1.3, right? And I was looking for something to write, and I decided to implement Pixley in C. And that was going pretty well; as I was implementing each command, I was making up ad-hoc test cases for it, and I was thinking "Hey, I should record these somewhere and make a test suite for the Pixley reference distribution!" Of course, I never did record those cases, but in the following weeks I started doing various other things with the Pixley project, and at one point, decided anew that it would be a good idea to bulk up the test cases.

So I started writing more test cases, right? And I got to testing list?. Well, (list? (lambda (x) x)) should be false, right? Sure. Except it wasn't.

Well, I went to the docs and saw that there was an easy explanation for this. This was for Pixley 1.0, mind you, and they've changed since then, but they told me that:

Some places where the underlying and interpreted representations must differ are in the data types, namely lists and lambda functions.

Each interpreted list is represented as a two-element underlying list. The first element is the atom __list__ and the second element is the (interpreted) list itself.

Each interpreted lambda function is represented by an underlying list of four elements: the atom __lambda__, a representation of the enclosing environment, a list of the formal arguments of the function, and the (interpreted) body of the function.

In other words, in the reference interpreter, both lists and function values are represented with lists; you tell them apart by looking at the first element, which is __lambda__ for a function value and __list__ for a list. And list? was probably just looking at the representation list and not checking the first element, right? Sure. Except, no, it was much more.

It turns out that while function values were in fact represented by lists with __lambda__ as the first element, lists were just represented by lists. Which means that there was an overlap between the types: a function value was, at the Pixley level, a kind of list, and could be treated just like one, for example with car and cdr. This is clearly not kosher R5RS, which has a whole section titled "Disjointness of types". (Of course, neither "list" nor "function value" is mentioned in that section, but I'd say the spirit of the law is pretty clear there or whatever.)

So this meant I had to fix the Pixley interpreter! But first, I had to make a decision: how to represent lists? Well, there were two general paths here: more meta-circular, or less. I could make the implementation conform to the documentation, making it less meta-circular, but then I'd have to be changing everything that built (or touched) a list to build (or check for) a list with __list__ at its head. Doable, but kind of distasteful. Alternatively, I could make it more meta-circular: keep lists represented as lists, and go one further by representing function values as function values. This is a little unilluminating, as it no longer lays bare how function values work; but this is made up for by the fact that most of the mechanics have to continue to exist in the implementation (just in different places) and there is a modest savings of space (because we can fall back on the implementing language's semantics for cases like trying to execute a non-function.) So that's what I did.

Now, this technically changed the semantics of the language, because gosh you could have been relying on the fact that (car (lambda (x) x)) evaluates to __lambda__, in your Pixley programs, and we can't have that, can we? So the language version was bumped up to 1.1.

Pixley 2.0

As previously mentioned, Pixley 2.0 removes the cadr and null? functions from the language.

Conclusion

The last main division of a discourse, usually containing a summing up of the points and a statement of opinion or decisions reached.

Keep Smiling! (I could never stand those "Home Sweet Home" folks.)
Chris Pressey
February 19th, 2012
Evanston, Illinois