[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Guile-commits] GNU Guile branch, master, updated. release_1-9-0-13-g5c2
|
From: |
Andy Wingo |
|
Subject: |
[Guile-commits] GNU Guile branch, master, updated. release_1-9-0-13-g5c27902 |
|
Date: |
Sun, 21 Jun 2009 13:05:49 +0000 |
This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU Guile".
http://git.savannah.gnu.org/cgit/guile.git/commit/?id=5c27902e5e01a94b22ebc51288500a3d36253293
The branch, master has been updated
via 5c27902e5e01a94b22ebc51288500a3d36253293 (commit)
via fe2400b2141fbde17eab517794773203fc19f952 (commit)
via 4e432dab1f02f5d497a352c1ea9392fc6db0f1f2 (commit)
via e63d888ef64c9c96177d841fa9a1ee4e697db81d (commit)
via 6370a6ad25ab0bc47e2f165937db8c7955b2b595 (commit)
via cf6d8d344c8717629279f01acbb785e0d35a12a5 (commit)
via c60be0404dd07fb9e9747c02fabc45d38380ed17 (commit)
from 4574ec212aad4df9571463ee4d45beb2607e51ad (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 5c27902e5e01a94b22ebc51288500a3d36253293
Author: Andy Wingo <address@hidden>
Date: Sun Jun 21 14:53:33 2009 +0200
add brainfuck->tree-il compiler
* module/Makefile.am (BRAINFUCK_LANG_SOURCES): Compile at the end. Add
compile-tree-il.scm.
* module/language/brainfuck/compile-tree-il.scm: New compiler, compiles
to tree-il instead of scheme. I thought it would be more illustrative,
though there are some uncommented bits.
* module/language/brainfuck/parse.scm: Modify not to put a header on the
scheme representation. After all, we don't put <scheme> before scheme
code, do we? :)
* module/language/brainfuck/spec.scm: Add tree-il compiler.
* module/language/tree-il.scm: Understand (set! (lexical foo) ...).
* module/system/base/language.scm: Update license. Actually, updates
licenses on all these.
commit fe2400b2141fbde17eab517794773203fc19f952
Author: Andy Wingo <address@hidden>
Date: Sun Jun 21 13:36:39 2009 +0200
formatting changes to (language brainfuck compile-scheme)
* module/language/brainfuck/compile-scheme.scm: Standalone comments
should have more than one semicolon, and update copyright to LGPLv3+.
commit 4e432dab1f02f5d497a352c1ea9392fc6db0f1f2
Author: Andy Wingo <address@hidden>
Date: Sun Jun 21 13:10:56 2009 +0200
link to brainfuck wikipedia page
* doc/ref/compiler.texi: Point to more info on Brainfuck. Patch by
Daniel Kraft.
commit e63d888ef64c9c96177d841fa9a1ee4e697db81d
Author: Daniel Kraft <address@hidden>
Date: Sat May 23 09:58:54 2009 +0200
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.
commit 6370a6ad25ab0bc47e2f165937db8c7955b2b595
Author: Daniel Kraft <address@hidden>
Date: Sat May 23 09:58:54 2009 +0200
basic brainfuck -> scheme example compiler.
* module/Makefile.am: Install the brainfuck compiler modules.
* module/language/brainfuck/spec.scm: New file.
* module/language/brainfuck/parse.scm: New file.
* module/language/brainfuck/compile-scheme.scm: New file.
commit cf6d8d344c8717629279f01acbb785e0d35a12a5
Author: Andy Wingo <address@hidden>
Date: Sun Jun 21 12:57:55 2009 +0200
remove obsolete guile-vm.texi
* doc/guile-vm.texi: Remove, has been folded into the Guile manual for a
while now.
* doc/Makefile.am: Remove guile-vm.texi.
commit c60be0404dd07fb9e9747c02fabc45d38380ed17
Author: Andy Wingo <address@hidden>
Date: Sun Jun 21 12:51:16 2009 +0200
update .gitignore
* .gitignore: Update.
-----------------------------------------------------------------------
Summary of changes:
.gitignore | 17 +
doc/Makefile.am | 4 +-
doc/guile-vm.texi | 1042 -------------------------
doc/ref/compiler.texi | 16 +-
module/Makefile.am | 7 +
module/language/brainfuck/compile-scheme.scm | 126 +++
module/language/brainfuck/compile-tree-il.scm | 153 ++++
module/language/brainfuck/parse.scm | 91 +++
module/language/brainfuck/spec.scm | 44 +
module/language/tree-il.scm | 3 +
module/system/base/language.scm | 24 +-
11 files changed, 469 insertions(+), 1058 deletions(-)
delete mode 100644 doc/guile-vm.texi
create mode 100644 module/language/brainfuck/compile-scheme.scm
create mode 100644 module/language/brainfuck/compile-tree-il.scm
create mode 100644 module/language/brainfuck/parse.scm
create mode 100644 module/language/brainfuck/spec.scm
diff --git a/.gitignore b/.gitignore
index ec59e5e..29f29be 100644
--- a/.gitignore
+++ b/.gitignore
@@ -91,3 +91,20 @@ INSTALL
*.pgs
*.rn
*.rns
+/meta/gdb-uninstalled-guile
+/meta/guile
+/meta/uninstalled-env
+/examples/box-module/box
+/examples/box/box
+/lib/alloca.h
+/lib/charset.alias
+/lib/configmake.h
+/lib/ref-add.sed
+/lib/ref-del.sed
+/lib/stdlib.h
+/lib/string.h
+/lib/strings.h
+/lib/sys/file.h
+/lib/time.h
+/lib/unistd.h
+/lib/unistr/.dirstamp
diff --git a/doc/Makefile.am b/doc/Makefile.am
index 712ece3..0a6b14e 100644
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -1,6 +1,6 @@
## Process this file with Automake to create Makefile.in
##
-## Copyright (C) 1998, 2002, 2006, 2008 Free Software Foundation, Inc.
+## Copyright (C) 1998, 2002, 2006, 2008, 2009 Free Software Foundation,
Inc.
##
## This file is part of GUILE.
##
@@ -43,5 +43,3 @@ include $(top_srcdir)/am/maintainer-dirs
guile-api.alist: guile-api.alist-FORCE
( cd $(top_builddir) ; $(mscripts)/update-guile-api.alist )
guile-api.alist-FORCE:
-
-info_TEXINFOS = guile-vm.texi
diff --git a/doc/guile-vm.texi b/doc/guile-vm.texi
deleted file mode 100644
index 927c09e..0000000
--- a/doc/guile-vm.texi
+++ /dev/null
@@ -1,1042 +0,0 @@
-\input texinfo @c -*-texinfo-*-
address@hidden %**start of header
address@hidden guile-vm.info
address@hidden Guile VM Specification
address@hidden end
address@hidden odd
address@hidden %**end of header
-
address@hidden EDITION 0.6
address@hidden VERSION 0.6
address@hidden UPDATED 2005-04-26
-
address@hidden Macro for instruction definitions.
address@hidden insn{}
-Instruction
address@hidden macro
-
address@hidden For Scheme procedure definitions.
address@hidden scmproc{}
-Scheme Procedure
address@hidden macro
-
address@hidden Scheme records.
address@hidden scmrec{}
-Record
address@hidden macro
-
address@hidden
address@hidden Scheme Programming
address@hidden
-* Guile VM: (guile-vm). Guile's Virtual Machine.
address@hidden direntry
-
-This file documents Guile VM.
-
-Copyright @copyright{} 2000 Keisuke Nishida
-Copyright @copyright{} 2005 Ludovic Court`es
-
-Permission is granted to make and distribute verbatim copies of this
-manual provided the copyright notice and this permission notice are
-preserved on all copies.
-
address@hidden
-Permission is granted to process this file through TeX and print the
-results, provided the printed document carries a copying permission
-notice identical to this one except for the removal of this paragraph
-(this paragraph not being relevant to the printed manual).
-
address@hidden ignore
-Permission is granted to copy and distribute modified versions of this
-manual under the conditions for verbatim copying, provided that the
-entire resulting derived work is distributed under the terms of a
-permission notice identical to this one.
-
-Permission is granted to copy and distribute translations of this manual
-into another language, under the above conditions for modified versions,
-except that this permission notice may be stated in a translation
-approved by the Free Software Foundation.
address@hidden ifinfo
-
address@hidden
address@hidden Guile VM Specification
address@hidden for Guile VM @value{VERSION}
address@hidden Keisuke Nishida
-
address@hidden
address@hidden 0pt plus 1filll
-Edition @value{EDITION} @*
-Updated for Guile VM @value{VERSION} @*
address@hidden @*
-
-Copyright @copyright{} 2000 Keisuke Nishida
-Copyright @copyright{} 2005 Ludovic Court`es
-
-Permission is granted to make and distribute verbatim copies of this
-manual provided the copyright notice and this permission notice are
-preserved on all copies.
-
-Permission is granted to copy and distribute modified versions of this
-manual under the conditions for verbatim copying, provided that the
-entire resulting derived work is distributed under the terms of a
-permission notice identical to this one.
-
-Permission is granted to copy and distribute translations of this manual
-into another language, under the above conditions for modified versions,
-except that this permission notice may be stated in a translation
-approved by the Free Software Foundation.
address@hidden titlepage
-
address@hidden
-
address@hidden
*********************************************************************
address@hidden Top, Introduction, (dir), (dir)
address@hidden Guile VM Specification
-
-This document would like to correspond to Guile VM @value{VERSION}.
-However, be warned that important parts still correspond to version
-0.0 and are not valid anymore.
-
address@hidden
-* Introduction::
-* Variable Management::
-* Instruction Set::
-* The Compiler::
-* Concept Index::
-* Function and Instruction Index::
-* Command and Variable Index::
-
address@hidden
- --- The Detailed Node Listing ---
-
-Instruction Set
-
-* Environment Control Instructions::
-* Branch Instructions::
-* Subprogram Control Instructions::
-* Data Control Instructions::
-
-The Compiler
-
-* Overview::
-* The Language Front-Ends::
-* GHIL::
-* Compiling Scheme Code::
-* GLIL::
-* The Assembler::
-
address@hidden detailmenu
address@hidden menu
-
address@hidden
*********************************************************************
address@hidden Introduction, Variable Management, Top, Top
address@hidden What is Guile VM?
-
-A Guile VM has a set of registers and its own stack memory. Guile may
-have more than one VM's. Each VM may execute at most one program at a
-time. Guile VM is a CISC system so designed as to execute Scheme and
-other languages efficiently.
-
address@hidden Registers
-
address@hidden
address@hidden pc - Program counter ;; ip (instruction poiner) is better?
address@hidden sp - Stack pointer
address@hidden bp - Base pointer
address@hidden ac - Accumulator
address@hidden itemize
-
address@hidden Engine
-
-A VM may have one of three engines: reckless, regular, or debugging.
-Reckless engine is fastest but dangerous. Regular engine is normally
-fail-safe and reasonably fast. Debugging engine is safest and
-functional but very slow.
-
address@hidden Memory
-
-Stack is the only memory that each VM owns. The other memory is shared
-memory that is shared among every VM and other part of Guile.
-
address@hidden Program
-
-A VM program consists of a bytecode that is executed and an environment
-in which execution is done. Each program is allocated in the shared
-memory and may be executed by any VM. A program may call other programs
-within a VM.
-
address@hidden Instruction
-
-Guile VM has dozens of system instructions and (possibly) hundreds of
-functional instructions. Some Scheme procedures such as cons and car
-are implemented as VM's builtin functions, which are very efficient.
-Other procedures defined outside of the VM are also considered as VM's
-functional features, since they do not change the state of VM.
-Procedures defined within the VM are called subprograms.
-
-Most instructions deal with the accumulator (ac). The VM stores all
-results from functions in ac, instead of pushing them into the stack.
-I'm not sure whether this is a good thing or not.
-
address@hidden Variable Management, Instruction Set, Introduction, Top
address@hidden Variable Management
-
-FIXME: This chapter needs to be reviewed so that it matches reality.
-A more up-to-date description of the mechanisms described in this
-section is given in @ref{Instruction Set}.
-
-A program may have access to local variables, external variables, and
-top-level variables.
-
address@hidden Local/external variables
-
-A stack is logically divided into several blocks during execution. A
-"block" is such a unit that maintains local variables and dynamic chain.
-A "frame" is an upper level unit that maintains subprogram calls.
-
address@hidden
- Stack
- dynamic | | | |
- chain +==========+ - =
- | |local vars| | |
- `-|block data| | block |
- /|frame data| | |
- | +----------+ - |
- | |local vars| | | frame
- `-|block data| | |
- /+----------+ - |
- | |local vars| | |
- `-|block data| | |
- /+==========+ - =
- | |local vars| | |
- `-|block data| | |
- /|frame data| | |
- | +----------+ - |
- | | | | |
address@hidden example
-
-The first block of each frame may look like this:
-
address@hidden
- Address Data
- ------- ----
- xxx0028 Local variable 2
- xxx0024 Local variable 1
- bp ->xxx0020 Local variable 0
- xxx001c Local link (block data)
- xxx0018 External link (block data)
- xxx0014 Stack pointer (block data)
- xxx0010 Return address (frame data)
- xxx000c Parent program (frame data)
address@hidden example
-
-The base pointer (bp) always points to the lowest address of local
-variables of the recent block. Local variables are referred as "bp[n]".
-The local link field has a pointer to the dynamic parent of the block.
-The parent's variables are referred as "bp[-1][n]", and grandparent's
-are "bp[-1][-1][n]". Thus, any local variable is represented by its
-depth and offset from the current bp.
-
-A variable may be "external", which is allocated in the shared memory.
-The external link field of a block has a pointer to such a variable set,
-which I call "fragment" (what should I call?). A fragment has a set of
-variables and its own chain.
-
address@hidden
- local external
- chain| | chain
- | +-----+ .--------, |
- `-|block|--+->|external|-'
- /+-----+ | `--------'\,
- `-|block|--' |
- /+-----+ .--------, |
- `-|block|---->|external|-'
- +-----+ `--------'
- | |
address@hidden example
-
-An external variable is referred as "bp[-2]->variables[n]" or
-"bp[-2]->link->...->variables[n]". This is also represented by a pair
-of depth and offset. At any point of execution, the value of bp
-determines the current local link and external link, and thus the
-current environment of a program.
-
-Other data fields are described later.
-
address@hidden Top-level variables
-
-Guile VM uses the same top-level variables as the regular Guile. A
-program may have direct access to vcells. Currently this is done by
-calling scm_intern0, but a program is possible to have any top-level
-environment defined by the current module.
-
address@hidden Scheme and VM variable
-
-Let's think about the following Scheme code as an example:
-
address@hidden
- (define (foo a)
- (lambda (b) (list foo a b)))
address@hidden example
-
-In the lambda expression, "foo" is a top-level variable, "a" is an
-external variable, and "b" is a local variable.
-
-When a VM executes foo, it allocates a block for "a". Since "a" may be
-externally referred from the closure, the VM creates a fragment with a
-copy of "a" in it. When the VM evaluates the lambda expression, it
-creates a subprogram (closure), associating the fragment with the
-subprogram as its external environment. When the closure is executed,
-its environment will look like this:
-
address@hidden
- block Top-level: foo
- +-------------+
- |local var: b | fragment
- +-------------+ .-----------,
- |external link|---->|variable: a|
- +-------------+ `-----------'
address@hidden example
-
-The fragment remains as long as the closure exists.
-
address@hidden Addressing mode
-
-Guile VM has five addressing modes:
-
address@hidden
address@hidden Real address
address@hidden Local position
address@hidden External position
address@hidden Top-level location
address@hidden Constant object
address@hidden itemize
-
-Real address points to the address in the real program and is only used
-with the program counter (pc).
-
-Local position and external position are represented as a pair of depth
-and offset from bp, as described above. These are base relative
-addresses, and the real address may vary during execution.
-
-Top-level location is represented as a Guile's vcell. This location is
-determined at loading time, so the use of this address is efficient.
-
-Constant object is not an address but gives an instruction an Scheme
-object directly.
-
-[ We'll also need dynamic scope addressing to support Emacs Lisp? ]
-
-
-Overall procedure:
-
address@hidden
address@hidden A source program is compiled into a bytecode.
address@hidden A bytecode is given an environment and becomes a program.
address@hidden A VM starts execution, creating a frame for it.
address@hidden Whenever a program calls a subprogram, a new frame is created
for it.
address@hidden When a program finishes execution, it returns a value, and the VM
- continues execution of the parent program.
address@hidden When all programs terminated, the VM returns the final value and
stops.
address@hidden enumerate
-
-
address@hidden Instruction Set, The Compiler, Variable Management, Top
address@hidden Instruction Set
-
-The Guile VM instruction set is roughly divided two groups: system
-instructions and functional instructions. System instructions control
-the execution of programs, while functional instructions provide many
-useful calculations.
-
address@hidden
-* Environment Control Instructions::
-* Branch Instructions::
-* Subprogram Control Instructions::
-* Data Control Instructions::
address@hidden menu
-
address@hidden Environment Control Instructions, Branch Instructions,
Instruction Set, Instruction Set
address@hidden Environment Control Instructions
-
address@hidden @insn{} link binding-name
-Look up @var{binding-name} (a string) in the current environment and
-push the corresponding variable object onto the stack. If
address@hidden is not bound yet, then create a new binding and
-push its variable object.
address@hidden deffn
-
address@hidden @insn{} variable-ref
-Dereference the variable object which is on top of the stack and
-replace it by the value of the variable it represents.
address@hidden deffn
-
address@hidden @insn{} variable-set
-Set the value of the variable on top of the stack (at @code{sp[0]}) to
-the object located immediately before (at @code{sp[-1]}).
address@hidden deffn
-
-As an example, let us look at what a simple function call looks like:
-
address@hidden
-(+ 2 3)
address@hidden example
-
-This call yields the following sequence of instructions:
-
address@hidden
-(link "+") ;; lookup binding "+"
-(variable-ref) ;; dereference it
-(make-int8 2) ;; push immediate value `2'
-(make-int8 3) ;; push immediate value `3'
-(tail-call 2) ;; call the proc at sp[-3] with two args
address@hidden example
-
address@hidden @insn{} local-ref offset
-Push onto the stack the value of the local variable located at
address@hidden within the current stack frame.
address@hidden deffn
-
address@hidden @insn{} local-set offset
-Pop the Scheme object located on top of the stack and make it the new
-value of the local variable located at @var{offset} within the current
-stack frame.
address@hidden deffn
-
address@hidden @insn{} external-ref offset
-Push the value of the closure variable located at position
address@hidden within the program's list of external variables.
address@hidden deffn
-
address@hidden @insn{} external-set offset
-Pop the Scheme object located on top of the stack and make it the new
-value of the closure variable located at @var{offset} within the
-program's list of external variables.
address@hidden deffn
-
address@hidden @insn{} make-closure
-Pop the program object from the stack and assign it the current
-closure variable list as its closure. Push the result program
-object.
address@hidden deffn
-
-Let's illustrate this:
-
address@hidden
-(let ((x 2))
- (lambda ()
- (let ((x++ (+ 1 x)))
- (set! x x++)
- x++)))
address@hidden example
-
-The resulting program has one external (closure) variable, i.e. its
address@hidden is set to 1 (@pxref{Subprogram Control Instructions}).
-This yields the following code:
-
address@hidden
- ;; the traditional program prologue with NLOCS = 0 and NEXTS = 1
-
- 0 (make-int8 2)
- 2 (external-set 0)
- 4 (make-int8 4)
- 6 (link "+") ;; lookup `+'
- 9 (vector 1) ;; create the external variable vector for
- ;; later use by `object-ref' and `object-set'
- ...
- 40 (load-program ##34#)
- 59 (make-closure) ;; assign the current closure to the program
- ;; just pushed by `load-program'
- 60 (return)
address@hidden example
-
-The program loaded here by @var{load-program} contains the following
-sequence of instructions:
-
address@hidden
- 0 (object-ref 0) ;; push the variable for `+'
- 2 (variable-ref) ;; dereference `+'
- 3 (make-int8:1) ;; push 1
- 4 (external-ref 0) ;; push the value of `x'
- 6 (call 2) ;; call `+' and push the result
- 8 (local-set 0) ;; make it the new value of `x++'
- 10 (local-ref 0) ;; push the value of `x++'
- 12 (external-set 0) ;; make it the new value of `x'
- 14 (local-ref 0) ;; push the value of `x++'
- 16 (return) ;; return it
address@hidden example
-
-At this point, you should know pretty much everything about the three
-types of variables a program may need to access.
-
-
address@hidden Branch Instructions, Subprogram Control Instructions,
Environment Control Instructions, Instruction Set
address@hidden Branch Instructions
-
-All the conditional branch instructions described below work in the
-same way:
-
address@hidden
address@hidden They take the Scheme object located on the stack and use it as
-the branch condition;
address@hidden If the condition if false, then program execution continues with
-the next instruction;
address@hidden If the condition is true, then the instruction pointer is
-increased by the offset passed as an argument to the branch
-instruction;
address@hidden Finally, when the instruction finished, the condition object is
-removed from the stack.
address@hidden itemize
-
-Note that the offset passed to the instruction is encoded on two 8-bit
-integers which are then combined by the VM as one 16-bit integer.
-
address@hidden @insn{} br offset
-Jump to @var{offset}.
address@hidden deffn
-
address@hidden @insn{} br-if offset
-Jump to @var{offset} if the condition on the stack is not false.
address@hidden deffn
-
address@hidden @insn{} br-if-not offset
-Jump to @var{offset} if the condition on the stack is false.
address@hidden deffn
-
address@hidden @insn{} br-if-eq offset
-Jump to @var{offset} if the two objects located on the stack are
-equal in the sense of @var{eq?}. Note that, for this instruction, the
-stack pointer is decremented by two Scheme objects instead of only
-one.
address@hidden deffn
-
address@hidden @insn{} br-if-not-eq offset
-Same as @var{br-if-eq} for non-equal objects.
address@hidden deffn
-
address@hidden @insn{} br-if-null offset
-Jump to @var{offset} if the object on the stack is @code{'()}.
address@hidden deffn
-
address@hidden @insn{} br-if-not-null offset
-Jump to @var{offset} if the object on the stack is not @code{'()}.
address@hidden deffn
-
-
address@hidden Subprogram Control Instructions, Data Control Instructions,
Branch Instructions, Instruction Set
address@hidden Subprogram Control Instructions
-
-Programs (read: ``compiled procedure'') may refer to external
-bindings, like variables or functions defined outside the program
-itself, in the environment in which it will evaluate at run-time. In
-a sense, a program's environment and its bindings are an implicit
-parameter of every program.
-
address@hidden object table
-In order to handle such bindings, each program has an @dfn{object
-table} associated to it. This table (actually a Scheme vector)
-contains all constant objects referenced by the program. The object
-table of a program is initialized right before a program is loaded
-with @var{load-program}.
-
-Variable objects are one such type of constant object: when a global
-binding is defined, a variable object is associated to it and that
-object will remain constant over time, even if the value bound to it
-changes. Therefore, external bindings only need to be looked up once
-when the program is loaded. References to the corresponding external
-variables from within the program are then performed via the
address@hidden instruction and are almost as fast as local variable
-references.
-
-Let us consider the following program (procedure) which references
-external bindings @code{frob} and @var{%magic}:
-
address@hidden
-(lambda (x)
- (frob x %magic))
address@hidden example
-
-This yields the following assembly code:
-
address@hidden
-(make-int8 64) ;; number of args, vars, etc. (see below)
-(link "frob")
-(link "%magic")
-(vector 2) ;; object table (external bindings)
-...
-(load-program #u8(20 0 23 21 0 20 1 23 36 2))
-(return)
address@hidden example
-
-All the instructions occurring before @var{load-program} (some were
-omitted for simplicity) form a @dfn{prologue} which, among other
-things, pushed an object table (a vector) that contains the variable
-objects for the variables bound to @var{frob} and @var{%magic}. This
-vector and other data pushed onto the stack are then popped by the
address@hidden instruction.
-
-Besides, the @var{load-program} instruction takes one explicit
-argument which is the bytecode of the program itself. Disassembled,
-this bytecode looks like:
-
address@hidden
-(object-ref 0) ;; push the variable object of `frob'
-(variable-ref) ;; dereference it
-(local-ref 0) ;; push the value of `x'
-(object-ref 1) ;; push the variable object of `%magic'
-(variable-ref) ;; dereference it
-(tail-call 2) ;; call `frob' with two parameters
address@hidden example
-
-This clearly shows that there is little difference between references
-to local variables and references to externally bound variables since
-lookup of externally bound variables if performed only once before the
-program is run.
-
address@hidden @insn{} load-program bytecode
-Load the program whose bytecode is @var{bytecode} (a u8vector), pop
-its meta-information from the stack, and push a corresponding program
-object onto the stack. The program's meta-information may consist of
-(in the order in which it should be pushed onto the stack):
-
address@hidden
address@hidden optionally, a pair representing meta-data (see the
address@hidden procedure); [FIXME: explain their meaning]
address@hidden optionally, a vector which is the program's object table (a
-program that does not reference external bindings does not need an
-object table);
address@hidden either one immediate integer or four immediate integers
-representing respectively the number of arguments taken by the
-function (@var{nargs}), the number of @dfn{rest arguments}
-(@var{nrest}, 0 or 1), the number of local variables (@var{nlocs}) and
-the number of external variables (@var{nexts}) (@pxref{Environment
-Control Instructions}).
address@hidden itemize
-
address@hidden deffn
-
address@hidden @insn{} object-ref offset
-Push the variable object for the external variable located at
address@hidden within the program's object table.
address@hidden deffn
-
address@hidden @insn{} return
-Free the program's frame.
address@hidden deffn
-
address@hidden @insn{} call nargs
-Call the procedure, continuation or program located at
address@hidden with the @var{nargs} arguments located from
address@hidden to @code{sp[-nargs + 1]}. The
-procedure/continuation/program and its arguments are dropped from the
-stack and the result is pushed. When calling a program, the
address@hidden instruction reserves room for its local variables on the
-stack, and initializes its list of closure variables and its vector of
-externally bound variables.
address@hidden deffn
-
address@hidden @insn{} tail-call nargs
-Same as @code{call} except that, for tail-recursive calls to a
-program, the current stack frame is re-used, as required by RnRS.
-This instruction is otherwise similar to @code{call}.
address@hidden deffn
-
-
address@hidden Data Control Instructions, , Subprogram Control Instructions,
Instruction Set
address@hidden Data Control Instructions
-
address@hidden @insn{} make-int8 value
-Push @var{value}, an 8-bit integer, onto the stack.
address@hidden deffn
-
address@hidden @insn{} make-int8:0
-Push the immediate value @code{0} onto the stack.
address@hidden deffn
-
address@hidden @insn{} make-int8:1
-Push the immediate value @code{1} onto the stack.
address@hidden deffn
-
address@hidden @insn{} make-false
-Push @code{#f} onto the stack.
address@hidden deffn
-
address@hidden @insn{} make-true
-Push @code{#t} onto the stack.
address@hidden deffn
-
address@hidden
address@hidden %push
address@hidden %pushi
address@hidden %pushl, %pushl:0:0, %pushl:0:1, %pushl:0:2, %pushl:0:3
address@hidden %pushe, %pushe:0:0, %pushe:0:1, %pushe:0:2, %pushe:0:3
address@hidden %pusht
address@hidden itemize
-
address@hidden
address@hidden %loadi
address@hidden %loadl, %loadl:0:0, %loadl:0:1, %loadl:0:2, %loadl:0:3
address@hidden %loade, %loade:0:0, %loade:0:1, %loade:0:2, %loade:0:3
address@hidden %loadt
address@hidden itemize
-
address@hidden
address@hidden %savei
address@hidden %savel, %savel:0:0, %savel:0:1, %savel:0:2, %savel:0:3
address@hidden %savee, %savee:0:0, %savee:0:1, %savee:0:2, %savee:0:3
address@hidden %savet
address@hidden itemize
-
address@hidden Flow control instructions
-
address@hidden
address@hidden %br-if
address@hidden %br-if-not
address@hidden %jump
address@hidden itemize
-
address@hidden Function call instructions
-
address@hidden
address@hidden %func, %func0, %func1, %func2
address@hidden itemize
-
address@hidden Scheme built-in functions
-
address@hidden
address@hidden cons
address@hidden car
address@hidden cdr
address@hidden itemize
-
address@hidden Mathematical buitin functions
-
address@hidden
address@hidden 1+
address@hidden 1-
address@hidden add, add2
address@hidden sub, sub2, minus
address@hidden mul2
address@hidden div2
address@hidden lt2
address@hidden gt2
address@hidden le2
address@hidden ge2
address@hidden num-eq2
address@hidden itemize
-
-
-
address@hidden The Compiler, Concept Index, Instruction Set, Top
address@hidden The Compiler
-
-This section describes Guile-VM's compiler and the compilation process
-to produce bytecode executable by the VM itself (@pxref{Instruction
-Set}).
-
address@hidden
-* Overview::
-* The Language Front-Ends::
-* GHIL::
-* Compiling Scheme Code::
-* GLIL::
-* The Assembler::
address@hidden menu
-
address@hidden Overview, The Language Front-Ends, The Compiler, The Compiler
address@hidden Overview
-
-Compilation in Guile-VM is a three-stage process:
-
address@hidden intermediate language
address@hidden assembler
address@hidden compiler
address@hidden GHIL
address@hidden GLIL
address@hidden bytecode
-
address@hidden
address@hidden the source programming language (e.g. R5RS Scheme) is read and
-translated into GHIL, @dfn{Guile's High-Level Intermediate Language};
address@hidden GHIL code is then translated into a lower-level intermediate
-language call GLIL, @dfn{Guile's Low-Level Intermediate Language};
address@hidden finally, GLIL is @dfn{assembled} into the VM's assembly language
-(@pxref{Instruction Set}) and bytecode.
address@hidden enumerate
-
-The use of two separate intermediate languages eases the
-implementation of front-ends since the gap between high-level
-languages like Scheme and GHIL is relatively small.
-
address@hidden guilec
-From an end-user viewpoint, compiling a Guile program into bytecode
-can be done either by using the @command{guilec} command-line tool, or
-by using the @code{compile-file} procedure exported by the
address@hidden(system base compile)} module.
-
address@hidden @scmproc{} compile-file file . opts
-Compile Scheme source code from file @var{file} using compilation
-options @var{opts}. The resulting file, a Guile object file, will be
-name according the application of the @code{compiled-file-name}
-procedure to @var{file}. The possible values for @var{opts} are the
-same as for the @code{compile-in} procedure (see below, @pxref{The Language
-Front-Ends}).
address@hidden deffn
-
address@hidden @scmproc{} compiled-file-name file
-Given source file name @var{file} (a string), return a string that
-denotes the name of the Guile object file corresponding to
address@hidden By default, the file name returned is @var{file} minus
-its extension and plus the @code{.go} file extension.
address@hidden deffn
-
address@hidden self-hosting
-It is worth noting, as you might have already guessed, that Guile-VM's
-compiler is written in Guile Scheme and is @dfn{self-hosted}: it can
-compile itself.
-
address@hidden The Language Front-Ends, GHIL, Overview, The Compiler
address@hidden The Language Front-Ends
-
-Guile-VM comes with a number of @dfn{language front-ends}, that is,
-code that can read a given high-level programming language like R5RS
-Scheme, and translate it into a lower-level representation suitable to
-the compiler.
-
-Each language front-end provides a @dfn{specification} and a
address@hidden to GHIL. Both of them come in the @code{language}
-module hierarchy. As an example, the front-end for Scheme is located
-in the @code{(language scheme spec)} and @code{(language scheme
-translate)} modules. Language front-ends can then be retrieved using
-the @code{lookup-language} procedure of the @code{(system base
-language)} module.
-
address@hidden @scmrec{} <language> name title version reader printer read-file
expander translator evaluator environment
-Denotes a language front-end specification a various methods used by
-the compiler to handle source written in that language. Of particular
-interest is the @code{translator} slot (@pxref{GHIL}).
address@hidden deftp
-
address@hidden @scmproc{} lookup-language lang
-Look for a language front-end named @var{lang}, a symbol (e.g,
address@hidden), and return the @code{<language>} record describing it
-if found. If @var{lang} does not denote a language front-end, an
-error is raised. Note that this procedure assumes that language
address@hidden exists if there exist a @code{(language @var{lang} spec)}
-module.
address@hidden deffn
-
-The @code{(system base compile)} module defines a procedure similar to
address@hidden but that is not limited to the Scheme language:
-
address@hidden @scmproc{} compile-in expr env lang . opts
-Compile expression @var{expr}, which is written in language @var{lang}
-(a @code{<language>} object), using compilation options @var{opts},
-and return bytecode as produced by the assembler (@pxref{The
-Assembler}).
-
-Options @var{opts} may contain the following keywords:
-
address@hidden @code
address@hidden :e
-compilation will stop after the code expansion phase.
address@hidden :t
-compilation will stop after the code translation phase, i.e. after
-code in the source language @var{lang} has been translated into GHIL
-(@pxref{GHIL}).
address@hidden :c
-compilation will stop after the compilation phase and before the
-assembly phase, i.e. once GHIL has been translated into GLIL
-(@pxref{GLIL}).
address@hidden table
-
-Additionally, @var{opts} may contain any option understood by the
-GHIL-to-GLIL compiler described in @xref{GLIL}.
address@hidden deffn
-
-
address@hidden GHIL, Compiling Scheme Code, The Language Front-Ends, The
Compiler
address@hidden Guile's High-Level Intermediate Language
-
-GHIL has constructs almost equivalent to those found in Scheme.
-However, unlike Scheme, it is meant to be read only by the compiler
-itself. Therefore, a sequence of GHIL code is only a sequence of GHIL
address@hidden (records), as opposed to symbols, each of which
-represents a particular language feature. These records are all
-defined in the @code{(system il ghil)} module and are named
address@hidden<ghil-*>}.
-
-Each GHIL record has at least two fields: one containing the
-environment (Guile module) in which it is considered, and one
-containing its location [FIXME: currently seems to be unused]. Below
-is a list of the main GHIL object types and their fields:
-
address@hidden
-;; Objects
-(<ghil-void> env loc)
-(<ghil-quote> env loc obj)
-(<ghil-quasiquote> env loc exp)
-(<ghil-unquote> env loc exp)
-(<ghil-unquote-splicing> env loc exp)
-;; Variables
-(<ghil-ref> env loc var)
-(<ghil-set> env loc var val)
-(<ghil-define> env loc var val)
-;; Controls
-(<ghil-if> env loc test then else)
-(<ghil-and> env loc exps)
-(<ghil-or> env loc exps)
-(<ghil-begin> env loc exps)
-(<ghil-bind> env loc vars vals body)
-(<ghil-lambda> env loc vars rest body)
-(<ghil-call> env loc proc args)
-(<ghil-inline> env loc inline args)
address@hidden example
-
-As can be seen from this examples, the constructs in GHIL are pretty
-close to the fundamental primitives of Scheme.
-
-It is the role of front-end language translators (@pxref{The Language
-Front-Ends}) to produce a sequence of GHIL objects from the
-human-readable, source programming language. The next section
-describes the translator for the Scheme language.
-
address@hidden Compiling Scheme Code, GLIL, GHIL, The Compiler
address@hidden Compiling Scheme Code
-
-The language object for Scheme, as returned by @code{(lookup-language
-'scheme)} (@pxref{The Language Front-Ends}), defines a translator
-procedure that returns a sequence of GHIL objects given Scheme code.
-Before actually performing this operation, the Scheme translator
-expands macros in the original source code.
-
-The macros that may be expanded can come from different sources:
-
address@hidden
address@hidden core Guile macros, such as @code{false-if-exception};
address@hidden macros defined in modules used by the module being compiled,
-e.g., @code{receive} in @code{(ice-9 receive)};
address@hidden macros defined within the module being compiled.
address@hidden itemize
-
address@hidden macro
address@hidden syntax transformer
address@hidden define-macro
address@hidden defmacro
-The main complexity in handling macros at compilation time is that
-Guile's macros are first-class objects. For instance, when using
address@hidden, one actually defines a @emph{procedure} that
-returns code; of course, unlike a ``regular'' procedure, it is
-executed when an S-exp is @dfn{memoized} by the evaluator, i.e.,
-before the actual evaluation takes place. Worse, it is possible to
-turn a procedure into a macro, or @dfn{syntax transformer}, thus
-removing, to some extent, the boundary between the macro expansion and
-evaluation phases, @inforef{Internal Macros, , guile}.
-
-[FIXME: explain limitations, etc.]
-
-
address@hidden GLIL, The Assembler, Compiling Scheme Code, The Compiler
address@hidden Guile's Low-Level Intermediate Language
-
-A GHIL instruction sequence can be compiled into GLIL using the
address@hidden procedure exported by the @code{(system il compile)}
-module. During this translation process, various optimizations may
-also be performed.
-
-The module @code{(system il glil)} defines record types representing
-various low-level abstractions. Compared to GHIL, the flow control
-primitives in GLIL are much more low-level: only @code{<glil-label>},
address@hidden<glil-branch>} and @code{<glil-call>} are available, no
address@hidden, @code{if}, etc.
-
-
address@hidden @scmproc{} compile ghil environment . opts
-Compile @var{ghil}, a GHIL instruction sequence, within
-environment/module @var{environment}, and return the resulting GLIL
-instruction sequence. The option list @var{opts} may be either the
-empty list or a list containing the @code{:O} keyword in which case
address@hidden will first go through an optimization stage of
address@hidden
-
-Note that the @code{:O} option may be passed at a higher-level to the
address@hidden and @code{compile-in} procedures (@pxref{The
-Language Front-Ends}).
address@hidden deffn
-
address@hidden @scmproc{} pprint-glil glil . port
-Print @var{glil}, a GLIL sequence instructions, in a human-readable
-form. If @var{port} is passed, it will be used as the output port.
address@hidden deffn
-
-
-Let's consider the following Scheme expression:
-
address@hidden
-(lambda (x) (+ x 1))
address@hidden example
-
-The corresponding (unoptimized) GLIL code, as shown by
address@hidden, looks like this:
-
address@hidden
-(@@asm (0 0 0 0)
- (@@asm (1 0 0 0) ;; expect one arg.
- (@@bind (x argument 0)) ;; debugging info
- (module-ref #f +) ;; lookup `+'
- (argument-ref 0) ;; push the argument onto
- ;; the stack
- (const 1) ;; push `1'
- (tail-call 2) ;; call `+', with 2 args,
- ;; using the same stack frame
- (@@source 15 33)) ;; additional debugging info
- (return 0))
address@hidden example
-
-This is not unlike the VM's assembly language described in
address@hidden Set}.
-
address@hidden The Assembler, , GLIL, The Compiler
address@hidden The Assembler
-
address@hidden code->bytes
-
-The final compilation step consists in converting the GLIL instruction
-sequence into VM bytecode. This is what the @code{assemble} procedure
-defined in the @code{(system vm assemble)} module is for. It relies
-on the @code{code->bytes} procedure of the @code{(system vm conv)}
-module to convert instructions (represented as lists whose @code{car}
-is a symbol naming the instruction, e.g. @code{object-ref},
address@hidden Set}) into binary code, or @dfn{bytecode}.
-Bytecode itself is represented using SRFI-4 byte vectors,
address@hidden, SRFI-4 homogeneous numeric vectors, guile}.
-
-
address@hidden @scmproc{} assemble glil environment . opts
-Return a binary representation of @var{glil} (bytecode), either in the
-form of an SRFI-4 @code{u8vector} or a @code{<bytespec>} object.
-[FIXME: Why is that?]
address@hidden deffn
-
-
-
address@hidden
*********************************************************************
address@hidden Concept Index, Function and Instruction Index, The Compiler, Top
address@hidden Concept Index
address@hidden cp
-
address@hidden Function and Instruction Index, Command and Variable Index,
Concept Index, Top
address@hidden Function and Instruction Index
address@hidden fn
-
address@hidden Command and Variable Index, , Function and Instruction Index,
Top
address@hidden Command and Variable Index
address@hidden vr
-
address@hidden
-
address@hidden Local Variables:
address@hidden ispell-local-dictionary: "american";
address@hidden End:
-
address@hidden LocalWords: bytecode
diff --git a/doc/ref/compiler.texi b/doc/ref/compiler.texi
index 0d68abf..f8d0895 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.
address@hidden Copyright (C) 2008
address@hidden 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,19 @@ module, and @var{externals} should be a list of external
variables.
@code{#f} is also a valid object code environment.
@end deffn
address@hidden Writing New High-Level Languages
address@hidden 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
address@hidden(language brainfuck)} defines a very basic Brainfuck
+implementation meant to serve as easy-to-understand example on how to
+do this. See for instance @url{http://en.wikipedia.org/wiki/Brainfuck}
+for more information about the Brainfuck language itself.
+
+
@node Extending the Compiler
@subsection Extending the Compiler
diff --git a/module/Makefile.am b/module/Makefile.am
index 2df0232..a904a8f 100644
--- a/module/Makefile.am
+++ b/module/Makefile.am
@@ -50,6 +50,7 @@ SOURCES =
\
$(OOP_SOURCES) \
$(SYSTEM_SOURCES) \
$(ECMASCRIPT_LANG_SOURCES) \
+ $(BRAINFUCK_LANG_SOURCES) \
$(SCRIPTS_SOURCES)
## test.scm is not currently installed.
@@ -112,6 +113,12 @@ ECMASCRIPT_LANG_SOURCES = \
language/ecmascript/compile-ghil.scm \
language/ecmascript/spec.scm
+BRAINFUCK_LANG_SOURCES = \
+ language/brainfuck/parse.scm \
+ language/brainfuck/compile-scheme.scm \
+ language/brainfuck/compile-tree-il.scm \
+ language/brainfuck/spec.scm
+
SCRIPTS_SOURCES = \
scripts/PROGRAM.scm \
scripts/autofrisk.scm \
diff --git a/module/language/brainfuck/compile-scheme.scm
b/module/language/brainfuck/compile-scheme.scm
new file mode 100644
index 0000000..86bc35f
--- /dev/null
+++ b/module/language/brainfuck/compile-scheme.scm
@@ -0,0 +1,126 @@
+;;; Brainfuck for GNU Guile
+
+;; Copyright (C) 2009 Free Software Foundation, Inc.
+
+;; This library is free software; you can redistribute it and/or
+;; modify it under the terms of the GNU Lesser General Public
+;; License as published by the Free Software Foundation; either
+;; version 3 of the License, or (at your option) any later version.
+;;
+;; This library is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+;; Lesser General Public License for more details.
+;;
+;; You should have received a copy of the GNU Lesser General Public
+;; License along with this library; if not, write to the Free Software
+;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+;;; Code:
+
+(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)
+ (tape (make-vector ,tape-size 0)))
+ ,@(if (not (eq? '<brainfuck> (car exp)))
+ (error "expected brainfuck program")
+ `(begin
+ ,@(compile-body (cdr exp))
+ (write-char #\newline))))
+ 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 '()))
+ (if (null? cur)
+ (reverse result)
+ (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 iterate ()
+ (if (not (= (vector-ref tape pointer) 0))
+ (begin
+ ,@(compile-body (cdr ins))
+ (iterate)))))
+
+ (else (error "unknown brainfuck instruction " (car ins)))))
diff --git a/module/language/brainfuck/compile-tree-il.scm
b/module/language/brainfuck/compile-tree-il.scm
new file mode 100644
index 0000000..c991631
--- /dev/null
+++ b/module/language/brainfuck/compile-tree-il.scm
@@ -0,0 +1,153 @@
+;;; Brainfuck for GNU Guile
+
+;; Copyright (C) 2009 Free Software Foundation, Inc.
+
+;; This library is free software; you can redistribute it and/or
+;; modify it under the terms of the GNU Lesser General Public
+;; License as published by the Free Software Foundation; either
+;; version 3 of the License, or (at your option) any later version.
+;;
+;; This library is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+;; Lesser General Public License for more details.
+;;
+;; You should have received a copy of the GNU Lesser General Public
+;; License along with this library; if not, write to the Free Software
+;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+;; 02110-1301 USA
+
+;;; Commentary:
+
+;; Brainfuck is a simple language that mostly mimics the operations of a
+;; Turing machine. This file implements a compiler from Brainfuck to
+;; Guile's Tree-IL.
+
+;;; Code:
+
+(define-module (language brainfuck compile-tree-il)
+ #:use-module (system base pmatch)
+ #:use-module (language tree-il)
+ #:export (compile-tree-il))
+
+;; Compilation of Brainfuck is pretty straight-forward. For all of
+;; brainfuck's instructions, there are basic representations in Tree-IL
+;; 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 Tree-IL
+;; code equivalent to Scheme code like this:
+;;
+;; (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.
+;;
+;; Note that we're generating the S-expression representation of
+;; Tree-IL, then using parse-tree-il to turn it into the actual Tree-IL
+;; data structures. This makes the compiler more pleasant to look at,
+;; but we do lose is the ability to propagate source information. Since
+;; Brainfuck is so obtuse anyway, this shouldn't matter ;-)
+;;
+;; 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-tree-il exp env opts)
+ (values
+ (parse-tree-il
+ `(let (pointer tape) (pointer tape)
+ ((const 0)
+ (apply (primitive make-vector) (const ,tape-size) (const 0)))
+ ,(compile-body exp)))
+ env
+ env))
+
+
+;; Compile a list of instructions to a Tree-IL expression.
+
+(define (compile-body instructions)
+ (let lp ((in instructions) (out '()))
+ (define (emit x)
+ (lp (cdr in) (cons x out)))
+ (cond
+ ((null? in)
+ ;; No more input, build our output.
+ (cond
+ ((null? out) '(void)) ; no output
+ ((null? (cdr out)) (car out)) ; single expression
+ (else `(begin ,@(reverse out)))) ; sequence
+ )
+ (else
+ (pmatch (car in)
+
+ ;; Pointer moves >< are done simply by something like:
+ ;; (set! pointer (+ pointer +-1))
+ ((<bf-move> ,dir)
+ (emit `(set! (lexical pointer)
+ (apply (primitive +) (lexical pointer) (const ,dir)))))
+
+ ;; Cell increment +- is done as:
+ ;; (vector-set! tape pointer (+ (vector-ref tape pointer) +-1))
+ ((<bf-increment> ,inc)
+ (emit `(apply (primitive vector-set!) (lexical tape) (lexical pointer)
+ (apply (primitive +)
+ (apply (primitive vector-ref)
+ (lexical tape) (lexical pointer))
+ (const ,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>)
+ (emit `(apply (primitive write-char)
+ (apply (primitive integer->char)
+ (apply (primitive vector-ref)
+ (lexical tape) (lexical 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>)
+ (emit `(apply (primitive vector-set!)
+ (lexical tape) (lexical pointer)
+ (apply (primitive char->integer)
+ (apply (primitive read-char))))))
+
+ ;; For loops [...] we use a letrec 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> . ,body)
+ (let ((iterate (gensym)))
+ (emit `(letrec (iterate) (,iterate)
+ ((lambda () ()
+ (if (apply (primitive =)
+ (apply (primitive vector-ref)
+ (lexical tape) (lexical
pointer))
+ (const 0))
+ (void)
+ (begin ,(compile-body body)
+ (apply (lexical ,iterate))))))
+ (apply (lexical ,iterate))))))
+
+ (else (error "unknown brainfuck instruction" (car in))))))))
diff --git a/module/language/brainfuck/parse.scm
b/module/language/brainfuck/parse.scm
new file mode 100644
index 0000000..0a71638
--- /dev/null
+++ b/module/language/brainfuck/parse.scm
@@ -0,0 +1,91 @@
+;;; Brainfuck for GNU Guile.
+
+;; Copyright (C) 2009 Free Software Foundation, Inc.
+
+;; This library is free software; you can redistribute it and/or
+;; modify it under the terms of the GNU Lesser General Public
+;; License as published by the Free Software Foundation; either
+;; version 3 of the License, or (at your option) any later version.
+;;
+;; This library is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+;; Lesser General Public License for more details.
+;;
+;; You should have received a copy of the GNU Lesser General Public
+;; License along with this library; if not, write to the Free Software
+;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+;; 02110-1301 USA
+
+;;; Code:
+
+(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.
+
+
+; 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 '()))
+ (if (null? cur)
+ result
+ (let ((head (car cur))
+ (tail (cdr cur)))
+ (if (eq? (car head) '<bf-nop>)
+ (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-brainfuck p)
+ (let iterate ((parsed '()))
+ (let ((chr (read-char p)))
+ (if (or (eof-object? chr) (eq? #\] chr))
+ (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-brainfuck).
+;
+; 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))
+ ((#\<) '(<bf-move> -1))
+ ((#\+) '(<bf-increment> 1))
+ ((#\-) '(<bf-increment> -1))
+ ((#\.) '(<bf-print>))
+ ((#\,) '(<bf-read>))
+ ((#\[) `(<bf-loop> ,@(read-brainfuck p)))
+ (else '(<bf-nop>))))
diff --git a/module/language/brainfuck/spec.scm
b/module/language/brainfuck/spec.scm
new file mode 100644
index 0000000..a4ba60f
--- /dev/null
+++ b/module/language/brainfuck/spec.scm
@@ -0,0 +1,44 @@
+;;; Brainfuck for GNU Guile.
+
+;; Copyright (C) 2009 Free Software Foundation, Inc.
+
+;; This library is free software; you can redistribute it and/or
+;; modify it under the terms of the GNU Lesser General Public
+;; License as published by the Free Software Foundation; either
+;; version 3 of the License, or (at your option) any later version.
+;;
+;; This library is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+;; Lesser General Public License for more details.
+;;
+;; You should have received a copy of the GNU Lesser General Public
+;; License along with this library; if not, write to the Free Software
+;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+;; 02110-1301 USA
+
+;;; Code:
+
+(define-module (language brainfuck spec)
+ #:use-module (language brainfuck compile-tree-il)
+ #:use-module (language brainfuck compile-scheme)
+ #:use-module (language brainfuck parse)
+ #: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 `((tree-il . ,compile-tree-il)
+ (scheme . ,compile-scheme))
+ #:printer write
+ )
diff --git a/module/language/tree-il.scm b/module/language/tree-il.scm
index da483b3..0f8448a 100644
--- a/module/language/tree-il.scm
+++ b/module/language/tree-il.scm
@@ -94,6 +94,9 @@
((lexical ,name ,sym) (guard (symbol? name) (symbol? sym))
(make-lexical-ref loc name sym))
+ ((set! (lexical ,name) ,exp) (guard (symbol? name))
+ (make-lexical-set loc name name (retrans exp)))
+
((set! (lexical ,name ,sym) ,exp) (guard (symbol? name) (symbol? sym))
(make-lexical-set loc name sym (retrans exp)))
diff --git a/module/system/base/language.scm b/module/system/base/language.scm
index 8ae4d96..3670c53 100644
--- a/module/system/base/language.scm
+++ b/module/system/base/language.scm
@@ -1,21 +1,21 @@
;;; Multi-language support
-;; Copyright (C) 2001 Free Software Foundation, Inc.
+;; Copyright (C) 2001, 2009 Free Software Foundation, Inc.
-;; This program is free software; you can redistribute it and/or modify
-;; it under the terms of the GNU General Public License as published by
-;; the Free Software Foundation; either version 2, or (at your option)
-;; any later version.
+;; This library is free software; you can redistribute it and/or
+;; modify it under the terms of the GNU Lesser General Public
+;; License as published by the Free Software Foundation; either
+;; version 3 of the License, or (at your option) any later version.
;;
-;; This program is distributed in the hope that it will be useful,
+;; This library is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
-;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-;; GNU General Public License for more details.
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+;; Lesser General Public License for more details.
;;
-;; You should have received a copy of the GNU General Public License
-;; along with this program; see the file COPYING. If not, write to
-;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-;; Boston, MA 02111-1307, USA.
+;; You should have received a copy of the GNU Lesser General Public
+;; License along with this library; if not, write to the Free Software
+;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+;; 02110-1301 USA
;;; Code:
hooks/post-receive
--
GNU Guile
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Guile-commits] GNU Guile branch, master, updated. release_1-9-0-13-g5c27902,
Andy Wingo <=