Tradução: Lisp em Ruby

2008 January 27, 05:42 h - tags: lisp beginner ruby learning

Cá estou eu, trabalhando no meio da madrugada, quando apareceu este post de ninguém menos que Jim Weirich. Ele literalmente implementou um pequeno interpretador de Lisp … em Ruby!! Achei o feito tão interessante que resolvi traduzir o post para os interessados. Vamos lá:

Manual do Programador de Lisp 1.5

Eu esbarrei nisto no blog do Bill Clementson e lembrei de usar o manual do programador de Lisp 1.5 na época da faculdade. Tenho fortes memórias dessa página em particular no manual e eu tentando entender suas nuances.

Se você nunca leu o Manual do Programador de Lisp 1.5, a página 13 é a entranha de um interpretador Lisp, as funções “eval” e “apply”. É escrito em Lisp, embora a notação usada seja um pouco estranha. O interpretador inteiro (menos duas funções utilitárias) é apresentado em uma única página do livro. Isso que é definição concisa de linguagem!

Em Ruby?

Eu frequentemente penso sobre implementar um interpretador Lisp, mas antigamente, o pensamento de implementar um garbage collector e todo o runtime era um pouco demais. Isso foi numa época antes do C, então minha linguagem de implementação teria sido assembler … eca.

Mas enquanto eu revia a página, percebi que com as linguagens modernas de hoje eu provavelmente poderia simplesmente converter as estranhas Expressões-M usadas na página 13 diretamente em código. Então … por que não?

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))) ))

Comments

comentários deste blog disponibilizados por Disqus