Skip to content

Instantly share code, notes, and snippets.

@ehaliewicz
Created July 30, 2018 17:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ehaliewicz/25e75035705f267f9daa5bd875b7385f to your computer and use it in GitHub Desktop.
Save ehaliewicz/25e75035705f267f9daa5bd875b7385f to your computer and use it in GitHub Desktop.
brainfuck compiler to low-level lisp code
(defun compile-bf (program)
(let ((loop-stack (list)))
(let ((translated (loop for char across program appending
(case char
(#\> '((incf pointer)))
(#\< '((decf pointer)))
(#\+ '((incf (aref memory (wrap-pointer pointer)))))
(#\- '((decf (aref memory (wrap-pointer pointer)))))
(#\. '((format t "~a" (code-char (aref memory (wrap-pointer pointer))))))
(#\, '((setf (aref memory (wrap-pointer pointer)) (char-code (read-char)))))
(#\[ (let ((start-lbl (gensym "start")) ;; generate labels for jumping
(end-lbl (gensym "end")))
;; save them on a stack
(push (cons start-lbl end-lbl)
loop-stack)
;; generate loop header code
`((if (zerop (aref memory (wrap-pointer pointer)))
(go ,end-lbl))
,start-lbl)))
(#\] (let ((labels (pop loop-stack))) ;; pop labels off stack, causes error if stack is empty as a result of unbalanced brackets
(destructuring-bind (start-lbl . end-lbl) labels
;; generate loop footer code
`((if (plusp (aref memory (wrap-pointer pointer)))
(go ,start-lbl))
,end-lbl))))))))
;; run lisp compiler on generated lisp code
(compile nil `(lambda () (let ((memory (make-array 30000 :initial-element 0))
(pointer 0))
(labels ((wrap-pointer (ptr)
(mod ptr 30000)))
(tagbody
,@translated))))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment