O Código
Aqui vai o código fonte completo em Ruby do interpretador Lisp da página 13 do manual do programador de Lisp:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 |
class Object def lisp_string to_s end end class NilClass def lisp_string "nil" end end class Array # Convert an Array into an S-expression # (i.e. linked list). # Subarrays are converted as well. def sexp result = nil reverse.each do |item| item = item.sexp if item.respond_to?(:sexp) result = cons(item, result) end result end end # The Basic Lisp Cons cell data structures. # Cons cells consist of a head and a tail. class Cons attr_reader :head, :tail def initialize(head, tail) @head, @tail = head, tail end def (other) return false unless other.class Cons return true if self.object_id other.object_id return car(self) car(other) && cdr(self) == cdr(other) end # Convert the lisp expression to a string. def lisp_string e = self result = “(” while e if e.class != Cons result << ”. ” << e.lisp_string e = nil else result << car(e).lisp_string e = cdr(e) result << ” ” if e end end result << “)” result end end # Lisp Primitive Functions. # It is an atom if it is not a cons cell. def atom?(a) a.class != Cons end # Get the head of a list. def car(e) e.head end # Get the tail of a list. def cdr(e) e.tail end # Construct a new list from a head and a tail. def cons(h,t) Cons.new(h,t) end # Here is the guts of the Lisp interpreter. # Apply and eval work together to interpret # the S-expression. These definitions are taken # directly from page 13 of the Lisp 1.5 # Programmer’s Manual. def apply(fn, x, a) if atom?(fn) case fn when :car then caar(x) when :cdr then cdar(x) when :cons then cons(car(x), cadr(x)) when :atom then atom?(car(x)) when :eq then car(x) cadr(x) else apply(eval(fn,a), x, a) end elsif car(fn) :lambda eval(caddr(fn), pairlis(cadr(fn), x, a)) elsif car(fn) :label apply(caddr(fn), x, cons(cons(cadr(fn), caddr(fn)), a)) end end def eval(e,a) if atom?(e) cdr(assoc(e,a)) elsif atom?(car(e)) if car(e) :quote cadr(e) elsif car(e) :cond evcon(cdr(e),a) else apply(car(e), evlis(cdr(e), a), a) end else apply(car(e), evlis(cdr(e), a), a) end end # And now some utility functions used # by apply and eval. These are # also given in the Lisp 1.5 # Programmer's Manual. def evcon(c,a) if eval(caar(c), a) eval(cadar(c), a) else evcon(cdr(c), a) end end def evlis(m, a) if m.nil? nil else cons(eval(car(m),a), evlis(cdr(m), a)) end end def assoc(a, e) if e.nil? fail "#{a.inspect} not bound" elsif a caar(e) car(e) else assoc(a, cdr(e)) end end def pairlis(vars, vals, a) while vars && vals a = cons(cons(car(vars), car(vals)), a) vars = cdr(vars) vals = cdr(vals) end a end # Handy lisp utility functions built on car and cdr. def caar(e) car(car(e)) end def cadr(e) car(cdr(e)) end def caddr(e) car(cdr(cdr(e))) end def cdar(e) cdr(car(e)) end def cadar(e) car(cdr(car(e))) end |
O Exemplo
E para provar, aqui vai um exemplo de programa em Lisp. Eu não me incomodei em escrever um parser de Lisp, então preciso escrever as listas em notação de Array padrão de Ruby (que é convertido em uma lista ligada via o método ‘sexp’).
Aqui vai o programa ruby usando o interpretador Lisp. O sistema Lisp é muito primitivo. A única maneira de definir uma função necessária é colocá-la em uma estrutura de ambiente, que é simplesmente uma lista de associação de chaves e valores.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
require 'lisp' # Create an environment where # the reverse, rev_shift and null # functions are bound to an # appropriate identifier. env = [ cons(:rev_shift, [:lambda, [:list, :result], [:cond, [[:null, :list], :result], [:t, [:rev_shift, [:cdr, :list], [:cons, [:car, :list], :result]]]]].sexp), cons(:reverse, [:lambda, [:list], [:rev_shift, :list, nil]].sexp), cons(:null, [:lambda, [:e], [:eq, :e, nil]].sexp), cons(:t, true), cons(nil, nil) ].sexp # Evaluate an S-Expression and print the result exp = [:reverse, [:quote, [:a, :b, :c, :d, :e]]].sexp puts "EVAL: #{exp.lisp_string}" puts " => #{eval(exp,env).lisp_string}" |
O programa imprime:
$ ruby reverse.rb
EVAL: (reverse (quote (a b c d e)))
=> (e d c b a)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Tudo que preciso fazer é escrever um parser Lisp e um REPL, e pronto! h3. O Exemplo em Notação Padrão Lisp Se achou o código Lisp "rubizado" difícil de ler, aqui vai a função reversa escrita em uma maneira mais "lispeira": --- lisp (defun reverse (list) (rev-shift list nil)) (defun rev-shift (list result) (cond ((null list) result) (t (rev-shift (cdr list) (cons (car list) result))) )) |