diff options
author | Daniel Kraft <d@domob.eu> | 2009-05-23 09:58:54 +0200 |
---|---|---|
committer | Andy Wingo <wingo@pobox.com> | 2009-06-21 15:06:03 +0200 |
commit | e63d888ef64c9c96177d841fa9a1ee4e697db81d (patch) | |
tree | 8e08793a18bddf1cd85811d9362e91d397c33772 | |
parent | 6370a6ad25ab0bc47e2f165937db8c7955b2b595 (diff) | |
download | guile-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.texi | 14 | ||||
-rw-r--r-- | module/language/brainfuck/compile-scheme.scm | 60 | ||||
-rw-r--r-- | module/language/brainfuck/parse.scm | 43 | ||||
-rw-r--r-- | module/language/brainfuck/spec.scm | 12 |
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 ) |