git @ Cat's Eye Technologies Pixley / rel_1_0
Initial import of Pixley 1.0 sources. catseye 9 years ago
3 changed file(s) with 413 addition(s) and 0 deletion(s). Raw diff Collapse all Expand all
0 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/2002/REC-xhtml1-20020801/DTD/xhtml1-strict.dtd">
1 <html xmlns="http://www.w3.org/1999/xhtml" lang="en">
2 <head>
3 <title>The Pixley Programming Language</title>
4 </head>
5 <body>
6
7 <h1>The Pixley Programming Language</h1>
8
9 <h2>Introduction</h2>
10
11 <p><dfn>Pixley</dfn> is a strict subset of R<sup>5</sup>RS Scheme.
12 All Pixley programs are also therefore Scheme programs.</p>
13
14 <p>Pixley was designed for "bootstrappability". I aimed to encompass a
15 minimal subset of Scheme that was still expressive enough to
16 permit writing a Pixley interpreter without too much pain.</p>
17
18 <h2>Semantics</h2>
19
20 <p>Pixley implements the following commands from Scheme
21 (listed in alphabetical order:)</p>
22
23 <ul>
24 <li><code>cadr</code></li>
25 <li><code>car</code></li>
26 <li><code>cdr</code></li>
27 <li><code>cond</code> / <code>else</code></li>
28 <li><code>cons</code></li>
29 <li><code>equal?</code></li>
30 <li><code>lambda</code></li>
31 <li><code>let*</code></li>
32 <li><code>list?</code></li>
33 <li><code>null?</code></li>
34 <li><code>quote</code></li>
35 </ul>
36
37 <p>For the precise meanings of each of these forms,
38 please refer to the Revised<sup>5</sup> Report on the Algorithmic Language Scheme.</p>
39
40 <p>Pixley only understands the Scheme datatypes of lists, symbols, function values (lambdas),
41 and booleans. Pixley's behaviour regarding any attempt to produce a value of any other type is undefined.
42 Neither is its behaviour defined for s-expressions which result in errors
43 when evaluated as Scheme programs.</p>
44
45 <h2>Syntax</h2>
46
47 <p>Pixley's syntax is identical to Scheme's. The meanings of
48 syntactical constructs which are valid in Scheme but not defined in Pixley (such as
49 numbers, strings, comments, quasiquoting, or hygienic macros) are undefined.</p>
50
51 <p>Of literal values, only those of list type can be directly introduced through syntactical
52 elements. Like Scheme, a literal null list can be denoted by <code>(quote ())</code>.
53 (However, <code>()</code> by itself is considered to be an illegal, empty application.)
54 Literal symbols may be introduced through the <code>quote</code> form,
55 literal function values can be produced through the <code>lambda</code>
56 form, and the two boolean values can be produced through the use of trivial
57 tests such as <code>(equal? (quote ()) (quote ()))</code>
58 and <code>(equal? (quote a) (quote b))</code>.</p>
59
60 <h2>Reference Implementation</h2>
61
62 <p>The reference implentation of Pixley is written in
63 Pixley (and therefore also in Scheme) and is 140 lines long.
64 It is called <code>pixley.pix</code>.</p>
65
66 <p><code>pixley.pix</code> does not include a lexical processor:
67 the Pixley program to be interpreted
68 must be made available to the interpreter as a native s-expression.
69 Since Pixley does not implement <code>define</code>, this is
70 usually achieved by applying a textual copy of <code>pixley.pix</code>
71 (a <code>lambda</code> expression)
72 to the s-expression to be interpreted as a Pixley program.</p>
73
74 <p>Because <code>pixley.pix</code> is written in Pixley, multiple
75 copies can be applied successively with equivalent semantics.
76 For example, having <code>pixley.pix</code> interpret some
77 program <code>foo.pix</code> should produce the same
78 observable behaviour (modulo performance) as having
79 <code>pixley.pix</code> interpret <code>pixley.pix</code> interpreting
80 <code>foo.pix</code>, or having
81 <code>pixley.pix</code> interpret <code>pixley.pix</code>
82 interpret <code>pixley.pix</code> interpreting
83 <code>foo.pix</code>, etc. etc. ad infinitum.</p>
84
85 <p>The unit tests for the Pixley reference interpreter do just that,
86 running through the set of tests at successively higher "degrees".
87 This is an example of a <dfn>computational automorphism</dfn>
88 and is a property of any bootstrapped universal computer (or rather,
89 of the Turing-complete language of that computer.)</p>
90
91 <p>The Pixley reference interpreter is highly meta-circular,
92 implementing e.g. Pixley's <code>car</code> simply in terms of the
93 underlying Pixley (or Scheme) <code>car</code>.
94 Some places where the underlying and interpreted representations must
95 differ are in the data types, namely lists and lambda functions.</p>
96
97 <p>Each interpreted list is represented as a two-element underlying list. The
98 first element is the atom <code>__list__</code> and the second
99 element is the (interpreted) list itself.</p>
100
101 <p>Each interpreted lambda function is represented by an underlying list
102 of four elements: the atom <code>__lambda__</code>,
103 a representation of the enclosing environment, a list of the formal
104 arguments of the function, and the (interpreted) body of the function.
105 Environments are represented as lists of two-element sublists, where
106 each sublist's first element is a symbol naming the identifier and the
107 second is a term giving the value.</p>
108
109 <h2>Conclusion</h2>
110
111 <p>The last main division of a discourse,
112 usually containing a summing up of the points
113 and a statement of opinion or decisions reached.</p>
114
115 <p>Keep Smiling! (I could never stand those "Home Sweet Home" folks.)
116 <br/>Chris Pressey
117 <br/>May 1<sup>st</sup>, 2009
118 <br/>Cupertino, California, USA</p>
119
120 </body>
121 </html>
0 (lambda (interpret program env)
1 (let* ((find (lambda (self elem alist)
2 (cond
3 ((null? alist)
4 (quote nothing))
5 (else
6 (let* ((entry (car alist))
7 (key (car entry))
8 (rest (cdr alist)))
9 (cond
10 ((equal? elem key)
11 entry)
12 (else
13 (self self elem rest))))))))
14 (interpret-args (lambda (interpret-args args env)
15 (cond
16 ((null? args)
17 args)
18 (else
19 (let* ((arg (car args))
20 (rest (cdr args)))
21 (cons (interpret interpret arg env) (interpret-args interpret-args rest env)))))))
22 (expand-args (lambda (expand-args formals argvals)
23 (cond
24 ((null? formals)
25 formals)
26 (else
27 (let* ((formal (car formals))
28 (rest-formals (cdr formals))
29 (argval (car argvals))
30 (rest-argvals (cdr argvals)))
31 (cons (cons formal (cons argval (quote ()))) (expand-args expand-args rest-formals rest-argvals)))))))
32 (concat-envs (lambda (concat-envs new-env old-env)
33 (cond
34 ((null? new-env)
35 old-env)
36 (else
37 (let* ((entry (car new-env))
38 (rest (cdr new-env)))
39 (cons entry (concat-envs concat-envs rest old-env))))))))
40 (cond
41 ((null? program)
42 program)
43 ((list? program)
44 (let* ((tag (car program))
45 (args (cdr program))
46 (entry (find find tag env)))
47 (cond
48 ((list? entry)
49 (interpret interpret (cons (cadr entry) args) env))
50 ((equal? tag (quote lambda))
51 (let* ((formals (car args))
52 (body (cadr args)))
53 (cons (quote __lambda__) (cons env (cons formals body)))))
54 ((equal? tag (quote cond))
55 (cond
56 ((null? args)
57 args)
58 (else
59 (let* ((branch (car args))
60 (test (car branch))
61 (expr (cadr branch)))
62 (cond
63 ((equal? test (quote else))
64 (interpret interpret expr env))
65 (else
66 (cond
67 ((interpret interpret test env)
68 (interpret interpret expr env))
69 (else
70 (let* ((branches (cdr args))
71 (newprog (cons (quote cond) branches)))
72 (interpret interpret newprog env))))))))))
73 ((equal? tag (quote let*))
74 (let* ((bindings (car args))
75 (body (cadr args)))
76 (cond
77 ((null? bindings)
78 (interpret interpret body env))
79 (else
80 (let* ((binding (car bindings))
81 (rest (cdr bindings))
82 (ident (car binding))
83 (expr (cadr binding))
84 (value (interpret interpret expr env))
85 (new-bi (cons ident (cons value (quote ()))))
86 (new-env (cons new-bi env))
87 (newprog (cons (quote let*) (cons rest (cons body (quote ()))))))
88 (interpret interpret newprog new-env))))))
89 ((equal? tag (quote null?))
90 (let* ((subject (car args)))
91 (null? (interpret interpret subject env))))
92 ((equal? tag (quote list?))
93 (let* ((subject (car args)))
94 (list? (interpret interpret subject env))))
95 ((equal? tag (quote quote))
96 (let* ((subject (car args)))
97 subject))
98 ((equal? tag (quote car))
99 (let* ((subject (car args)))
100 (car (interpret interpret subject env))))
101 ((equal? tag (quote cdr))
102 (let* ((subject (car args)))
103 (cdr (interpret interpret subject env))))
104 ((equal? tag (quote cadr))
105 (let* ((subject (car args)))
106 (car (cdr (interpret interpret subject env)))))
107 ((equal? tag (quote cons))
108 (let* ((a (car args))
109 (b (cadr args)))
110 (cons (interpret interpret a env) (interpret interpret b env))))
111 ((equal? tag (quote equal?))
112 (let* ((a (car args))
113 (b (cadr args)))
114 (equal? (interpret interpret a env) (interpret interpret b env))))
115 ((null? tag)
116 tag)
117 ((list? tag)
118 (let* ((type (car tag))
119 (rest (cdr tag)))
120 (cond
121 ((equal? type (quote __lambda__))
122 (let* ((closure-env (car rest))
123 (formals (cadr rest))
124 (body (cdr (cdr rest)))
125 (arg-vals (interpret-args interpret-args args env))
126 (arg-env (expand-args expand-args formals arg-vals))
127 (new-env (concat-envs concat-envs arg-env closure-env)))
128 (interpret interpret body new-env)))
129 (else
130 (quote execute-list-error)))))
131 (else
132 (quote unbound-command-error)))))
133 (else
134 (let* ((entry (find find program env)))
135 (cond
136 ((list? entry)
137 (cadr entry))
138 (else
139 (quote illegal-program-error))))))))
0 ; A Pixley interpreter, implemented in R5RS Scheme.
1 ; April 2009, Chris Pressey, Cat's Eye Technologies.
2
3 ; This is really just a Scheme wrapper for the Pixley interpreter
4 ; written in Pixley. Because Pixley is a strict subset of R5RS Scheme,
5 ; this is scarcely an astounding feat.
6
7 ; Load an S-expression from a named file.
8 (define load-sexp
9 (lambda (filename)
10 (display "loading ") (display filename) (display "...") (newline)
11 (with-input-from-file filename (lambda () (read)))))
12
13 ; Return an S-expression representing a Pixley interpreter.
14 ; For convenience, it is loaded from its file.
15 (define pixley-interpreter-sexp
16 (load-sexp "pixley.pix"))
17
18 ; Return a Scheme procedure value denoting an executable Pixley interpreter,
19 (define pixley-interpreter
20 (eval pixley-interpreter-sexp (scheme-report-environment 5)))
21
22 ; Interpret a given Pixley program represented as an S-expression.
23 (define interpret-pixley
24 (lambda (program-sexp)
25 (pixley-interpreter pixley-interpreter program-sexp '())))
26
27 ; Interpret a given Pixley program contained in a specified named file.
28 (define interpret-pixley-file
29 (lambda (filename)
30 (interpret-pixley (load-sexp filename))))
31
32 ; There's something just plain unwholesome about quasiquote, don't you think?
33 ; Sure it's useful, but it makes your beautiful Scheme program start to look
34 ; something awful, with little hairs and the like strewn about. Ugly, what.
35 ; Sometimes downright Perlish.
36
37 ; To remedy this, I have devised a cute little hygienic macro called
38 ; 'let-symbol' which does essentially the same task, but (IMO) in a cleaner way.
39 ; let-symbol, like let, takes a set of bindings. Also like let, it evaluates the
40 ; values in those bindings exactly once. Unlike let, it binds those values to
41 ; symbols. The body of the let-symbol is interpreted as a literal s-expression,
42 ; except that every place one of the bound symbols is encountered, the
43 ; evaluated value that it is bound to is inserted instead.
44
45 ; Our replacement for quasiquote.
46 (define-syntax let-symbol
47 (syntax-rules ()
48 ((let-symbol bindings body)
49 (let-symbol bindings () body))
50 ((let-symbol ((key val) . rest) defn body)
51 (let ((key val)) (let-symbol rest (key . defn) body)))
52 ((let-symbol () defn (a . b))
53 (cons (let-symbol () defn a) (let-symbol () defn b)))
54 ((let-symbol () (key . rest) sym)
55 (let-syntax
56 ((is-bound
57 (syntax-rules (key)
58 ((is-bound key) sym)
59 ((is-bound _) (let-symbol () rest sym)))))
60 (is-bound sym)))
61 ((let-symbol () () sym)
62 (quote sym))))
63
64 ; A version of let-symbol which evaluates the symbol-bound expressions
65 ; lazily, at the point when they are inserted in the final S-expression.
66 ; Included for the sake of comparison only.
67 (define-syntax let-symbol-lazy
68 (syntax-rules ()
69 ((let-symbol env ())
70 ())
71 ((let-symbol env (a . b))
72 (cons (let-symbol env a) (let-symbol env b)))
73 ((let-symbol () sym)
74 (quote sym))
75 ((let-symbol ((key val) . rest) sym)
76 (let-syntax
77 ((is-key
78 (syntax-rules (key)
79 ((is-key key) val)
80 ((is-key _) (let-symbol rest sym)))))
81 (is-key sym)))))
82
83 ; Create a Pixley program which applies the Pixley interpreter (written in Pixley)
84 ; to the given S-expression (a Pixley program).
85 (define wrap-pixley-interpreter
86 (lambda (sexp)
87 (let-symbol ((interpreter-val (load-sexp "pixley.pix"))
88 (sexp-val sexp))
89 (let* ((interpreter interpreter-val)
90 (sexp (quote sexp-val)))
91 (interpreter interpreter sexp '())))))
92
93 ; Here's the quasiquote version of the above, just for comparison.
94 (define wrap-pixley-interpreter-quasiquote
95 (lambda (sexp)
96 (let* ((interpreter (load-sexp "pixley.pix")))
97 `(let* ((interpreter ,interpreter)
98 (sexp (quote ,sexp)))
99 (interpreter interpreter sexp '())))))
100
101 ; Create an n-level Pixley program that applies n Pixley interpreters to the
102 ; given S-expression.
103 (define wrap-pixley-interpreter-nth
104 (lambda (degree sexp)
105 (cond
106 ((zero? degree)
107 sexp)
108 (else
109 (wrap-pixley-interpreter-nth (- degree 1) (wrap-pixley-interpreter sexp))))))
110
111 ; A list of test cases to exercise.
112 (define test-cases
113 '(
114 ( (let* ((a (quote hello))) a) .
115 hello
116 )
117 ( (let* ((a (lambda (x y) (cons x y)))) (a (quote foo) (quote ()))) .
118 (foo)
119 )
120 )
121 )
122
123 ; Our test harness.
124 (define run-tests
125 (lambda (degree all-tests tests)
126 (cond
127 ((null? tests)
128 (run-tests (+ 1 degree) all-tests all-tests))
129 (else
130 (let* ((test-prog (caar tests))
131 (expected (cdar tests))
132 (rest (cdr tests))
133 (sexp (wrap-pixley-interpreter-nth degree test-prog))
134 (result (interpret-pixley sexp)))
135 (begin
136 (display "Degree: ") (display degree) (display " ")
137 (display test-prog) (display "...")
138 (cond
139 ((equal? result expected)
140 (begin (display "PASS") (newline)
141 (run-tests degree all-tests rest)))
142 (else
143 (begin (display "FAIL") (newline)
144 (display "Expected: ") (display expected) (newline)
145 (display "Actual: ") (display result) (newline))))))))))
146
147 ; Top-level driver for the test harness.
148 (define test
149 (lambda ()
150 (run-tests 0 test-cases test-cases)))