Created
September 25, 2013 17:27
-
-
Save ijp/6703044 to your computer and use it in GitHub Desktop.
The thompson bug code from my blog post at http://shift-reset.com/blog/2013/9/25/Fun%20with%20Self-Reproducing%20Programs/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/local/bin/guile | |
!# | |
(define (bug? form) | |
(equal? form '((display "scheme sucks!\n")))) | |
(define buggy-code | |
'((display "scheme is great!\n"))) | |
(define safe-compiler | |
'((define (compile form) form) | |
(define (read-all in) | |
(define (loop curr lst) | |
(if (eof-object? curr) | |
(reverse lst) | |
(loop (read in) (cons curr lst)))) | |
(loop (read in) '())) | |
(define (write-all list) | |
(for-each (lambda (obj) (write obj)) list) | |
(newline)) | |
(define (main args) | |
(let ((from (list-ref args 1))) | |
(call-with-input-file from | |
(lambda (in) | |
(write-all (compile (read-all in))))))))) | |
(define (safe-compiler? form) | |
(equal? form safe-compiler)) | |
(define buggy-compiler | |
(let ((x '((define (bug? form) | |
(equal? form '((display "scheme sucks!\n")))) | |
(define buggy-code | |
'((display "scheme is great!\n"))) | |
(define safe-compiler | |
'((define (compile form) form) | |
(define (read-all in) | |
(define (loop curr lst) | |
(if (eof-object? curr) | |
(reverse lst) | |
(loop (read in) (cons curr lst)))) | |
(loop (read in) '())) | |
(define (write-all list) | |
(for-each (lambda (obj) (write obj)) list) | |
(newline)) | |
(define (main args) | |
(let ((from (list-ref args 1))) | |
(call-with-input-file from | |
(lambda (in) | |
(write-all (compile (read-all in))))))))) | |
(define (safe-compiler? form) | |
(equal? form safe-compiler)))) | |
(y (lambda (x y z) | |
(append x | |
`((define buggy-compiler | |
(let ((x ',x) | |
(y ,y) | |
(z ',z)) | |
(y x ',y z)))) | |
z))) | |
(z '((define (compile form) | |
(cond ((bug? form) buggy-code) | |
((safe-compiler? form) buggy-compiler) | |
(else form))) | |
(define (read-all in) | |
(define (loop curr lst) | |
(if (eof-object? curr) | |
(reverse lst) | |
(loop (read in) (cons curr lst)))) | |
(loop (read in) '())) | |
(define (write-all list) | |
(for-each (lambda (obj) (write obj)) list) | |
(newline)) | |
(define (main args) | |
(let ((from (list-ref args 1))) | |
(call-with-input-file from | |
(lambda (in) | |
(write-all (compile (read-all in)))))))))) | |
(y x '(lambda (x y z) | |
(append x | |
`((define buggy-compiler | |
(let ((x ',x) | |
(y ,y) | |
(z ',z)) | |
(y x ',y z)))) | |
z)) | |
z))) | |
(define (compile form) | |
(cond ((bug? form) buggy-code) | |
((safe-compiler? form) buggy-compiler) | |
(else form))) | |
(define (read-all in) | |
(define (loop curr lst) | |
(if (eof-object? curr) | |
(reverse lst) | |
(loop (read in) (cons curr lst)))) | |
(loop (read in) '())) | |
(define (write-all list) | |
(for-each (lambda (obj) (write obj)) list) | |
(newline)) | |
(define (main args) | |
(let ((from (list-ref args 1))) | |
(call-with-input-file from | |
(lambda (in) | |
(write-all (compile (read-all in))))))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
$ export GUILE_AUTO_COMPILE=0 | |
$ cd /tmp | |
$ cat sucks.scm | |
(display "scheme sucks!\n") | |
$ guile -e main safe.scm sucks.scm | |
(display "scheme sucks!\n") | |
$ guile -e main buggy.scm sucks.scm | |
(display "scheme is great!\n") | |
$ # as you can see, the buggy compiler miscompiles our target executable | |
$ guile -e main safe.scm safe.scm > safe2.scm | |
$ guile -e main safe.scm buggy.scm > buggy2.scm | |
$ # with our safe compiler, we are compiling both versions just to strip the whitespace, which makes it easier to perform source comparisons | |
$ guile -e main safe2.scm safe2.scm > safe3.scm | |
$ diff safe2.scm safe3.scm | |
$ # no diff output, so our safe compiler compiles itself just fine | |
$ guile -e main buggy2.scm buggy2.scm > buggy3.scm | |
$ diff buggy2.scm buggy3.scm | |
$ # again, no diff output, so our buggy compiler compiles itself just fine | |
$ # now the real magic | |
$ guile -e main buggy2.scm safe.scm > unsafe-safe.scm | |
$ diff buggy2.scm unsafe-safe.scm | |
$ # oh look, when we compile the safe compiler with our buggy compiler, we get the buggy compiler again |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(define (compile form) form) | |
(define (read-all in) | |
(define (loop curr lst) | |
(if (eof-object? curr) | |
(reverse lst) | |
(loop (read in) (cons curr lst)))) | |
(loop (read in) '())) | |
(define (write-all list) | |
(for-each (lambda (obj) (write obj)) list) | |
(newline)) | |
(define (main args) | |
(let ((from (list-ref args 1))) | |
(call-with-input-file from | |
(lambda (in) | |
(write-all (compile (read-all in))))))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(display "scheme sucks!\n") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment