summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Kraft <d@domob.eu>2009-05-23 09:58:54 +0200
committerAndy Wingo <wingo@pobox.com>2009-06-21 15:06:03 +0200
commite63d888ef64c9c96177d841fa9a1ee4e697db81d (patch)
tree8e08793a18bddf1cd85811d9362e91d397c33772
parent6370a6ad25ab0bc47e2f165937db8c7955b2b595 (diff)
downloadguile-e63d888ef64c9c96177d841fa9a1ee4e697db81d.tar.gz
added documenting comments to the brainfuck compiler and mention it in the VM documentation.
* doc/ref/compiler.texi: Mention the new brainfuck compiler as an example. * module/language/brainfuck/compile-scheme.scm: Add a lot of documentation comments. * module/language/brainfuck/parse.scm: Ditto. * module/language/brainfuck/spec.scm: Ditto.
-rw-r--r--doc/ref/compiler.texi14
-rw-r--r--module/language/brainfuck/compile-scheme.scm60
-rw-r--r--module/language/brainfuck/parse.scm43
-rw-r--r--module/language/brainfuck/spec.scm12
4 files changed, 124 insertions, 5 deletions
diff --git a/doc/ref/compiler.texi b/doc/ref/compiler.texi
index 0d68abfc6..06262b95a 100644
--- a/doc/ref/compiler.texi
+++ b/doc/ref/compiler.texi
@@ -1,6 +1,6 @@
@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
-@c Copyright (C) 2008
+@c Copyright (C) 2008, 2009
@c Free Software Foundation, Inc.
@c See the file guile.texi for copying conditions.
@@ -26,6 +26,7 @@ know how to compile your .scm file.
* GLIL::
* Assembly::
* Bytecode and Objcode::
+* Writing New High-Level Languages::
* Extending the Compiler::
@end menu
@@ -712,6 +713,17 @@ module, and @var{externals} should be a list of external variables.
@code{#f} is also a valid object code environment.
@end deffn
+@node Writing New High-Level Languages
+@subsection Writing New High-Level Languages
+
+In order to integrate a new language @var{lang} into Guile's compiler
+system, one has to create the module @code{(language @var{lang} spec)}
+containing the language definition and referencing the parser,
+compiler and other routines processing it. The module hierarchy in
+@code{(language brainfuck)} defines a very basic Brainfuck
+implementation meant to serve as easy-to-understand example on how to
+do this.
+
@node Extending the Compiler
@subsection Extending the Compiler
diff --git a/module/language/brainfuck/compile-scheme.scm b/module/language/brainfuck/compile-scheme.scm
index 1b37076ff..97c32d0b7 100644
--- a/module/language/brainfuck/compile-scheme.scm
+++ b/module/language/brainfuck/compile-scheme.scm
@@ -22,8 +22,36 @@
(define-module (language brainfuck compile-scheme)
#:export (compile-scheme))
+; Compilation of Brainfuck to Scheme is pretty straight-forward. For all of
+; brainfuck's instructions, there are basic representations in Scheme we
+; only have to generate.
+;
+; Brainfuck's pointer and data-tape are stored in the variables pointer and
+; tape, where tape is a vector of integer values initially set to zero. Pointer
+; starts out at position 0.
+; Our tape is thus of finite length, with an address range of 0..n for
+; some defined upper bound n depending on the length of our tape.
+
+
+; Define the length to use for the tape.
+
(define tape-size 30000)
+
+; This compiles a whole brainfuck program. This constructs a Scheme code like:
+; (let ((pointer 0)
+; (tape (make-vector tape-size 0)))
+; (begin
+; <body>
+; (write-char #\newline)))
+;
+; So first the pointer and tape variables are set up correctly, then the
+; program's body is executed in this context, and finally we output an
+; additional newline character in case the program does not output one.
+;
+; TODO: Find out and explain the details about env, the three return values and
+; how to use the options. Implement options to set the tape-size, maybe.
+
(define (compile-scheme exp env opts)
(values
`(let ((pointer 0)
@@ -36,6 +64,12 @@
env
env))
+
+; Compile a list of instructions to get a list of Scheme codes. As we always
+; strip off the car of the instructions-list and cons the result onto the
+; result-list, it will get out in reversed order first; so we have to (reverse)
+; it on return.
+
(define (compile-body instructions)
(let iterate ((cur instructions)
(result '()))
@@ -44,28 +78,50 @@
(let ((compiled (compile-instruction (car cur))))
(iterate (cdr cur) (cons compiled result))))))
+
+; Compile a single instruction to Scheme, using the direct representations
+; all of Brainfuck's instructions have.
+
(define (compile-instruction ins)
(case (car ins)
+ ; Pointer moval >< is done simply by something like:
+ ; (set! pointer (+ pointer +-1))
((<bf-move>)
(let ((dir (cadr ins)))
`(set! pointer (+ pointer ,dir))))
+ ; Cell increment +- is done as:
+ ; (vector-set! tape pointer (+ (vector-ref tape pointer) +-1))
((<bf-increment>)
(let ((inc (cadr ins)))
`(vector-set! tape pointer (+ (vector-ref tape pointer) ,inc))))
+ ; Output . is done by converting the cell's integer value to a character
+ ; first and then printing out this character:
+ ; (write-char (integer->char (vector-ref tape pointer)))
((<bf-print>)
'(write-char (integer->char (vector-ref tape pointer))))
+ ; Input , is done similarly, read in a character, get its ASCII code and
+ ; store it into the current cell:
+ ; (vector-set! tape pointer (char->integer (read-char)))
((<bf-read>)
'(vector-set! tape pointer (char->integer (read-char))))
+ ; For loops [...] we use a named let construction to execute the body until
+ ; the current cell gets zero. The body is compiled via a recursive call
+ ; back to (compile-body).
+ ; (let iterate ()
+ ; (if (not (= (vector-ref! tape pointer) 0))
+ ; (begin
+ ; <body>
+ ; (iterate))))
((<bf-loop>)
- `(let iter ()
+ `(let iterate ()
(if (not (= (vector-ref tape pointer) 0))
(begin
,@(compile-body (cdr ins))
- (iter)))))
+ (iterate)))))
(else (error "unknown brainfuck instruction " (car ins)))))
diff --git a/module/language/brainfuck/parse.scm b/module/language/brainfuck/parse.scm
index e272b61ac..54dbaeecc 100644
--- a/module/language/brainfuck/parse.scm
+++ b/module/language/brainfuck/parse.scm
@@ -22,9 +22,34 @@
(define-module (language brainfuck parse)
#:export (read-brainfuck))
+; Purpose of the parse module is to read in brainfuck in text form and produce
+; the corresponding tree representing the brainfuck code.
+;
+; Each object (representing basically a single instruction) is structured like:
+; (<instruction> [arguments])
+; where <instruction> is a symbolic name representing the type of instruction
+; and the optional arguments represent further data (for instance, the body of
+; a [...] loop as a number of nested instructions).
+;
+; A full brainfuck program is represented by the (<brainfuck> instructions)
+; object.
+
+
+; Read a brainfuck program from an input port. We construct the <brainfuck>
+; program and read in the instructions using (read-body).
+
(define (read-brainfuck p)
`(<brainfuck> ,@(read-body p)))
+
+; While reading a number of instructions in sequence, all of them are cons'ed
+; onto a list of instructions; thus this list gets out in reverse order.
+; Additionally, for "comment characters" (everything not an instruction) we
+; generate <bf-nop> NOP instructions.
+;
+; This routine reverses a list of instructions and removes all <bf-nop>'s on the
+; way to fix these two issues for a read-in list.
+
(define (reverse-without-nops lst)
(let iterate ((cur lst)
(result '()))
@@ -36,6 +61,15 @@
(iterate tail result)
(iterate tail (cons head result)))))))
+
+; Read in a set of instructions until a terminating ] character is found (or
+; end of file is reached). This is used both for loop bodies and whole
+; programs, so that a program has to be either terminated by EOF or an
+; additional ], too.
+;
+; For instance, the basic program so just echo one character would be:
+; ,.]
+
(define (read-body p)
(let iterate ((parsed '()))
(let ((chr (read-char p)))
@@ -43,6 +77,15 @@
(reverse-without-nops parsed)
(iterate (cons (process-input-char chr p) parsed))))))
+
+; This routine processes a single character of input and builds the
+; corresponding instruction. Loop bodies are read by recursively calling
+; back (read-body).
+;
+; For the poiner movement commands >< and the cell increment/decrement +-
+; commands, we only use one instruction form each and specify the direction of
+; the pointer/value increment using an argument to the instruction form.
+
(define (process-input-char chr p)
(case chr
((#\>) '(<bf-move> 1))
diff --git a/module/language/brainfuck/spec.scm b/module/language/brainfuck/spec.scm
index 9df1df699..a303984b2 100644
--- a/module/language/brainfuck/spec.scm
+++ b/module/language/brainfuck/spec.scm
@@ -25,10 +25,18 @@
#:use-module (system base language)
#:export (brainfuck))
+
+; The new language is integrated into Guile via this (define-language)
+; specification in the special module (language [lang] spec).
+; Provided is a parser-routine in #:reader, a output routine in #:printer
+; and one or more compiler routines (as target-language - routine pairs)
+; in #:compilers. This is the basic set of fields needed to specify a new
+; language.
+
(define-language brainfuck
#:title "Guile Brainfuck"
#:version "1.0"
#:reader (lambda () (read-brainfuck (current-input-port)))
- #:compilers `((scheme . ,compile-scheme))
- #:printer write
+ #:compilers `((scheme . ,compile-scheme))
+ #:printer write
)