module/language/brainfuck/parse.scm

   1 ;;; Brainfuck for GNU Guile.
   2
   3 ;; Copyright (C) 2009 Free Software Foundation, Inc.
   4
   5 ;; This library is free software; you can redistribute it and/or
   6 ;; modify it under the terms of the GNU Lesser General Public
   7 ;; License as published by the Free Software Foundation; either
   8 ;; version 3 of the License, or (at your option) any later version.
   9 ;;
  10 ;; This library is distributed in the hope that it will be useful,
  11 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 ;; Lesser General Public License for more details.
  14 ;;
  15 ;; You should have received a copy of the GNU Lesser General Public
  16 ;; License along with this library; if not, write to the Free Software
  17 ;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  18 ;; 02110-1301 USA
  19
  20 ;;; Code:
  21
  22 (define-module (language brainfuck parse)
  23   #:export (read-brainfuck))
  24
  25 ; Purpose of the parse module is to read in brainfuck in text form and produce
  26 ; the corresponding tree representing the brainfuck code.
  27 ;
  28 ; Each object (representing basically a single instruction) is structured like:
  29 ; (<instruction> [arguments])
  30 ; where <instruction> is a symbolic name representing the type of instruction
  31 ; and the optional arguments represent further data (for instance, the body of
  32 ; a [...] loop as a number of nested instructions).
  33 ;
  34 ; A full brainfuck program is represented by the (<brainfuck> instructions)
  35 ; object.
  36
  37
  38 ; While reading a number of instructions in sequence, all of them are cons'ed
  39 ; onto a list of instructions; thus this list gets out in reverse order.
  40 ; Additionally, for "comment characters" (everything not an instruction) we
  41 ; generate <bf-nop> NOP instructions.
  42 ;
  43 ; This routine reverses a list of instructions and removes all <bf-nop>'s on the
  44 ; way to fix these two issues for a read-in list.
  45
  46 (define (reverse-without-nops lst)
  47   (let iterate ((cur lst)
  48                 (result '()))
  49     (if (null? cur)
  50       result
  51       (let ((head (car cur))
  52             (tail (cdr cur)))
  53         (if (eq? (car head) '<bf-nop>)
  54           (iterate tail result)
  55           (iterate tail (cons head result)))))))
  56
  57
  58 ; Read in a set of instructions until a terminating ] character is found (or
  59 ; end of file is reached).  This is used both for loop bodies and whole
  60 ; programs, so that a program has to be either terminated by EOF or an
  61 ; additional ], too.
  62 ;
  63 ; For instance, the basic program so just echo one character would be:
  64 ; ,.]
  65
  66 (define (read-brainfuck p)
  67   (let iterate ((parsed '()))
  68     (let ((chr (read-char p)))
  69       (if (or (eof-object? chr) (eq? #\] chr))
  70         (reverse-without-nops parsed)
  71         (iterate (cons (process-input-char chr p) parsed))))))
  72
  73
  74 ; This routine processes a single character of input and builds the
  75 ; corresponding instruction.  Loop bodies are read by recursively calling
  76 ; back (read-brainfuck).
  77 ;
  78 ; For the poiner movement commands >< and the cell increment/decrement +-
  79 ; commands, we only use one instruction form each and specify the direction of
  80 ; the pointer/value increment using an argument to the instruction form.
  81
  82 (define (process-input-char chr p)
  83   (case chr
  84     ((#\>) '(<bf-move> 1))
  85     ((#\<) '(<bf-move> -1))
  86     ((#\+) '(<bf-increment> 1))
  87     ((#\-) '(<bf-increment> -1))
  88     ((#\.) '(<bf-print>))
  89     ((#\,) '(<bf-read>))
  90     ((#\[) `(<bf-loop> ,@(read-brainfuck p)))
  91     (else '(<bf-nop>))))