Блог

Я пишу интерпретатор Brainfuck в Scheme (схема Chez). Похоже, что независимо от того, какую программу Brainfuck я запускаю, она никогда не работает, и я не могу понять почему. Я решил, что попробую это с кодом для треугольника Серпинского (отсюда, протестировано здесь) и привет, мир:

 (define hello-world " [-[<<[ [--->]-[<<<]]]>>>-]>-.---.>..>.<<<<-.< .>>>>>.>.<<.<-.")
(define sierpinski "        [> >    <<-]>  >> <[-[>> <<-] >>]> [-<<<[->[ [-] >  >>>-<<]<[<]>>      [<<     >>-] <<  .[-]<<]>.> [>>]> ]")
 

(entry-point hello-world 100) сбой, подобный этому:

 |#<
|(elem-at
   -1
   (255 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0))
Exception: failed assertion (>= i 0) at line 7, char 10 of interpret.scm
 

Когда я использую elem-at , аргумент index всегда является указателем инструкции или указателем данных. Тогда так странно, что указатель здесь оказывается меньше 1.

(entry-point sierpinski 20) сбой, подобный этому:

 |# 
|(elem-at 20 (0 10 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 19 (10 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 18 (1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 17 (1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 16 (1 0 1 0 1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 15 (0 1 0 1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 14 (1 0 1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 13 (0 1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 12 (1 0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 11 (0 1 0 1 0 1 0 1 0 31 0))
|(elem-at 10 (1 0 1 0 1 0 1 0 31 0))
|(elem-at 9 (0 1 0 1 0 1 0 31 0))
|(elem-at 8 (1 0 1 0 1 0 31 0))
|(elem-at 7 (0 1 0 1 0 31 0))
|(elem-at 6 (1 0 1 0 31 0))
|(elem-at 5 (0 1 0 31 0))
|(elem-at 4 (1 0 31 0))
|(elem-at 3 (0 31 0))
|(elem-at 2 (31 0))
|(elem-at 1 (0))
|(elem-at 0 ())
Exception in car: () is not a pair
 

Опять же, есть еще одна проблема, связанная, в частности, с указателем data-ptr . Это меня совершенно озадачило. Мой код приведен ниже. Кто-нибудь знает, что не так с моим интерпретатором?

 (define (token-list chars)
    (filter 
        (lambda (c) (memq c (list #> #< #  #- #. #, #[ #])))
        (string->list chars)))

(trace-define (elem-at i lst)
    (assert (>= i 0))
    (if (zero? i) (car lst)
        (elem-at (sub1 i) (cdr lst))))

(define (change-byte! i cells modifier)
    (if (zero? i)
        (set-car! cells (modifier (car cells)))
        (change-byte! (sub1 i) (cdr cells) modifier)))

(define (print-status! cells instr instr-ptr data-ptr)
    (format #t "Cells = ~a, instr = ~a, instr ptr = ~a, data ptr = ~an"
        cells instr instr-ptr data-ptr))

(define (update-data-ptr instr data-ptr)
    (case instr
        (#> (add1 data-ptr))
        (#< (sub1 data-ptr))
        (else data-ptr)))

(define (ptr-after-jump program instr-ptr mover end)
    (if (eq? (elem-at instr-ptr program) end)
        instr-ptr
        (ptr-after-jump program (mover instr-ptr) mover end)))

(define (update-instr-ptr instr-ptr instr program cell)
    (add1
        (cond
            ((and (eq? instr #[) (zero? cell))
                (ptr-after-jump program instr-ptr add1 #]))
            ((and (eq? instr #]) (not (zero? cell)))
                (ptr-after-jump program instr-ptr sub1 #[))
            (else instr-ptr))))

(define (interpret program instr-ptr data-ptr cells)
    (when (not (= instr-ptr (length program)))
        (let ((instr (elem-at instr-ptr program)))
            (begin
                (print-status! cells instr instr-ptr data-ptr)
                (case instr
                    (#  (change-byte! data-ptr cells
                        (if (= (elem-at data-ptr cells) 255)
                            (lambda (_) 0) add1)))
                    (#- (change-byte! data-ptr cells
                        (if (zero? (elem-at data-ptr cells))
                            (lambda (_) 255) sub1)))

                    (#. (display (integer->char (elem-at data-ptr cells))))
                    (#, (change-byte! data-ptr cells (lambda (_) (char->integer (read-char))))))

                (interpret
                    program
                    (update-instr-ptr instr-ptr instr program (elem-at data-ptr cells)); the problem may be around here
                    (update-data-ptr instr data-ptr)
                    cells)))))


(define (init-cells length buf)
    (if (zero? length) buf
        (init-cells (sub1 length) (cons 0 buf))))

(define (entry-point code tape-length)
    (interpret
        (token-list code)
        0 0; (floor (/ tape-length 2))
        (init-cells tape-length '())))