quinta-feira, 31 de julho de 2008

Copy & comment

Para quem seguidamente, como eu:

1. tem preguiça de criar uma revisão no VCS para alterar algo pequeno no código (só para ver se dá certo -- se não der, volta atrás rapidinho);

2. acha muito trabalhoso usar o editor de texto para duplicar um trecho de código (i.e., copiar & colar) e comentar uma das partes.

A função a seguir (em Elisp, para Emacs) faz as tarefas do item 2 para quem se enquadra no perfil do item 1:

(defun copy&comment (begin end)
(interactive "r")
(save-excursion
(copy-region-as-kill begin end)
(goto-char end)
(yank)
(comment-region begin end)))

terça-feira, 8 de julho de 2008

Interpretador de assembly em Scheme

Dando continuidade à série de programas inúteis que só servem para alimentar a procrastinação, a seguir estão a descrição e implementação (em Chicken Scheme) de um pequeno interpretador de uma linguagem assembly bem simples.

A linguagem possui apenas seis instruções e opera somente com números:

  • add <reg> <number | reg>: Soma um número ou o conteúdo do registrador usado como segundo argumento com o conteúdo do registrador usado como primeiro argumento. O resultado é armazenado no registrador usado como primeiro argumento.

  • mov <reg> <number | reg>: Armazena o número ou o conteúdo do registrador usado como segundo argumento no registrador usado como primeiro argumento.

  • lbl <label>: Associa um endereço de memória a um rótulo, o qual pode ser referenciado no programa pelas instruções jmp e jnz.

  • jmp <label>: Desvia o fluxo de execução para <label> (uma marca determinada através da instrução lbl).

  • jnz <reg> <label>: Desvia o fluxo de execução para <label> se o conteúdo do registrador usado como primeiro argumento for diferente de zero.

  • out <number | reg>: Imprime o número ou conteúdo do registrador usado como argumento.


A arquitetura hipotética considerada possui 8 registradores para leitura e escrita (r1 a r8), nenhum deles com função específica. Há também um registrador somente para leitura (ip) que armazena o endereço de memória da última instrução executada.

Por simplicidade, a sintaxe das instruções é semelhante à sintaxe de Scheme, ou seja, usa parênteses. Por exemplo:

(mov r1 3)

O código do interpretador está a seguir (tiny-assembly.scm):

;; Instrucoes:
;; add <reg> <number | reg>
;; mov <reg> <number | reg>
;; jmp <label>
;; jnz <reg> <label>
;; lbl <label>
;; out <number | reg>
;;
;; Registradores: r1..r8
;; Registrador "read-only": ip

(use srfi-1)

(define (run code)
(define memory (map cons (iota (length code)) code))
(define labels '())
(define registers
'((r1 . 0) (r2 . 0) (r3 . 0) (r4 . 0)
(r5 . 0) (r6 . 0) (r7 . 0) (r8 . 0)))
(define ip 0)
(define code-len (length code))

(define (die . msg)
(print "Error: "
(string-intersperse (map ->string msg) ""))
(exit 1))

(define (next-ip)
(set! ip (add1 ip)))

(define (reg-get register)
(alist-ref register registers))

(define (val-get thing)
(if (eq? thing 'ip)
ip
(if (number? thing)
thing
(reg-get thing))))

(define (reg-set! reg val)
(set! registers
(alist-update! reg (val-get val) registers)))

(define (label-address label)
(alist-ref label labels))

(define (add reg val)
(reg-set! reg (+ (reg-get reg) (val-get val))))

(define (mov reg val)
(reg-set! reg (val-get val)))

(define (jmp label)
(let ((address (or (reg-get label)
(label-address label))))
(if address
(set! ip address)
(die "label " label " not found."))))

(define (jnz reg label)
(if (zero? (reg-get reg))
(next-ip)
(jmp label)))

(define (lbl label)
(set! labels (alist-update! label ip labels)))

(define (finished? ip) (>= ip code-len))

(set! labels
(map (lambda (label)
(cons (caddr label) (car label)))
(filter (lambda (expr)
(eq? (cadr expr) 'lbl))
memory)))
(let loop ()
(if (finished? ip)
(exit)
(begin
(let* ((expr (alist-ref ip memory))
(op (car expr))
(arg1 (cadr expr))
(arg2 (and (not (null? (cddr expr)))
(caddr expr))))
(case op
((mov) (mov arg1 arg2))
((add) (add arg1 arg2))
((jmp) (jmp arg1))
((jnz) (jnz arg1 arg2))
((lbl) (noop))
((out) (print
(or (reg-get arg1)
(if (eq? arg1 'ip)
ip
arg1))))
(else (die op ": unknown command.")))
(unless (memq op '(jmp jnz))
(next-ip)))
(loop)))))

;;; Command line parser
(let ((args (command-line-arguments)))
(when (null? args)
(print "Usage: " (program-name) " <input-file>")
(exit 1))
(let ((file (car args)))
(unless (file-exists? file)
(print "Could not open " file)
(exit 1))
(run (handle-exceptions
exn
(die "parse error.")
(with-input-from-file file read-file)))))

A seguir estão alguns exemplos de código assembly e uso com o interpretador:

Multiplicação


A linguagem não possui uma instrução para multiplicação. Abaixo está a implementação de uma rotina para multiplicar dois números (7 x 4):

(mov r1 7)
(mov r2 4)
(mov r4 ip)
(jmp mul)
(jmp end)

;; Multiplicacao (x * y)
;; x -> r1
;; y -> r2
;; produto -> r3
;; endereco de retorno -> r4
(lbl mul)
(jnz r1 not-zero)
(jmp end)
(lbl not-zero)
(mov r3 0)
(lbl loopmul)
(add r3 r2)
(add r1 -1)
(jnz r1 loopmul)
(add r4 2)
(jmp r4)

(lbl end)
(out r3)

$ csi -s tiny-assembly.scm multiplicacao.asm
28

Fatorial


Toda e qualquer implementação de linguagem inútil deve mostrar uma implementação de fatorial como exemplo. Abaixo está a implementação usando o assembly descrito neste texto (where's your god now?!):

(mov r5 7) ;; entrada de dados

;; Fatorial
;; entrada -> r5
;; resultado -> r6
(lbl fatorial)
(mov r6 1)
(lbl fat-loop)
(jnz r5 fat-not-0)
(jmp end)
(lbl fat-not-0)
(add r5 -1)
(jnz r5 fat-not-1)
(jmp end)
(lbl fat-not-1)
(add r5 1)
(mov r1 r6)
(mov r2 r5)
(mov r4 ip)
(jmp mul)
(mov r6 r3)
(add r5 -1)
(jmp fat-loop)

;; Multiplicacao (x * y)
;; x -> r1
;; y -> r2
;; produto -> r3
;; endereco de retorno -> r4
(lbl mul)
(jnz r1 mul-not-0)
(jmp end)
(lbl mul-not-0)
(mov r3 0)
(lbl loopmul)
(add r3 r2)
(add r1 -1)
(jnz r1 loopmul)
(add r4 2)
(jmp r4)

(lbl end)
(out r6) ;; imprime o resultado

$ csi -s tiny-assembly.scm fatorial.asm
5040

quarta-feira, 2 de julho de 2008

Contagem de definições no toplevel

Dando início a uma série de programas para geração de estatísticas inúteis, abaixo está um pequeno código para contagem de definições feitas no toplevel (em Chicken Scheme).

(use srfi-1)

(define count-defines
(let* ((definers '(define define-macro define-constant
define-inline define-syntax))
(count-defines
(lambda (file)
(cons file
(length
(filter
(lambda (form)
(and (pair? form)
(memq (car form) definers)))
(with-input-from-file
file read-file)))))))
(lambda (files)
(let ((defines-count (map count-defines files)))
(for-each (lambda (file/defcount)
(print (car file/defcount) ": "
(cdr file/defcount)))
defines-count)
(print "Total: "
(reduce + 0 (map cdr defines-count)))))))

(let ((files (command-line-arguments)))
(if (null? files)
(exit 0)
(count-defines files)))

Exemplos de uso:


$ csi -s count-defines.scm count-defines.scm
count-defines.scm: 1
Total: 1


$ csi -s count-defines.scm spiffy/trunk/*.scm
spiffy/trunk/cgi-handler.scm: 5
spiffy/trunk/simple-directory-handler.scm: 4
spiffy/trunk/spiffy-base.scm: 70
spiffy/trunk/spiffy.scm: 1
spiffy/trunk/ssp-handler.scm: 10
spiffy/trunk/web-scheme-handler.scm: 4
Total: 94

Embora este programa não diga muita coisa de útil sobre o código que analisa, serve para mostrar um dos aspectos mais interessantes de Lisp: a possibilidade de se tratar, naturalmente, código como dados. Basicamente, a contagem de definições no toplevel consiste em ler todas as expressões de um arquivo e verificar se o car de cada expressão é um dos símbolos define, define-macro, define-constant, define-inline ou define-syntax (se a expressão for um par).

Este tipo de análise não é muito útil porque, pelo menos em Chicken, é possível especificar o que deve ser "visível" ou não no código compilado. Isto pode ser feito com as declarações export e hide. Outros motivos são que este programa não consegue inferir as definições de toplevel que serão geradas através da expansão de macros (web-scheme, por exemplo, usa esta estratégia) e que não computa definições feitas dentro de blocos cond-expand.