LISP: exercícios

Uma expressão especial em

Uma das diferenças fundamentais entre Scheme e Common Lisp está relacionada com a forma como os diferentes objectos são tratados como argumentos. Numa expressão do tipo (f a), a quantidade f é, ou está, na posição de operador e, tipicamente, é o nome de uma função. A quantidade a está na posição de argumento e é uma expressão de qualquer tipo. Se quisermos usar uma função como argumento, é necessário usar o prefixo #'. A expressão #'x não é mais do que a abreviatura para (function x), da mesma forma que 'x é uma abreviatura de (quote x). Quando queremos passar uma função como argumento temos de a passar com o prefixo: (f #'list) chama f com argumento a função list; para que f possa fazer alguma coisa com a função list temos que usar funcall. Por exemplo, a função

(defun f (x)
   (funcall x x))
dá 
> (f #'list)

(list)

Consideremos o exercício de encontrar uma função que, quando aplicada a si mesmo, retorna-se a si própria. Ou seja, (funcall f f) dá f1.

Consideremos então a função

> (lambda (x) x)

#<FUNCTION :LAMBDA (X) X>
e a função que soma uma unidade 
(defun plus1 (x)
  (+ 1 x))

Como é óbvio

> (plus1 2)

3
e como 
> ((lambda (x) x) #'plus1)

#<FUNCTION PLUS1 (X) (DECLARE (SYSTEM::IN-DEFUN PLUS1)) (BLOCK PLUS1 (+ 1 X))>
vem 
> (funcall ((lambda (x) x) #'plus1) '2)

3

Assim, a resolução do nosso exercício pode muito bem ser

> ((funcall (lambda (x) x) #'(lambda (x) x))

#<FUNCTION :LAMBDA (X) X>

Outro exercício interessante será o de encontrar uma função que quando avaliada, sem argumentos, retorna-se a si própria2. Isto é, (f) dá f.

Um exemplo trivial é o de definir uma função, chamada f, que tem como output f, i.e.,

(defun f ()
  'f)

> (f)

f

Um exemplo menos trivial pode ser obtido à custa da função diag que se define como

(defun diag (x)
  (list  x (list  'quote x)))
ou alternativamente 
(defun diag (x)
  (funcall (lambda (x) (list  x (list  'quote x))) x))

Com qualquer uma das definições obtém-se

> (diag 'list)

(list 'list)
e 
> (eval (diag 'list))

(list)

Notemos que

> (diag #'f)

(#<FUNCTION F NIL (DECLARE (SYSTEM::IN-DEFUN F)) (BLOCK F 'F)>
 '#<FUNCTION F NIL (DECLARE (SYSTEM::IN-DEFUN F)) (BLOCK F 'F)>)
e que, aplicando (diag (function diag)), ou, 
> (diag #'diag)

(#<FUNCTION DIAG (X) (DECLARE (SYSTEM::IN-DEFUN DIAG)) (BLOCK DIAG (LIST X (LIST 'QUOTE X)))>
 '#<FUNCTION DIAG (X) (DECLARE (SYSTEM::IN-DEFUN DIAG)) (BLOCK DIAG (LIST X (LIST 'QUOTE X)))>)
que parece resolver o exercício (f) = f.

Assim definindo

(defun fixed-point ()
  (diag  #'diag))
vem 
> (fixed-point)

(#<FUNCTION DIAG (X) (DECLARE (SYSTEM::IN-DEFUN DIAG)) (BLOCK DIAG (LIST X (LIST 'QUOTE X)))>
 '#<FUNCTION DIAG (X) (DECLARE (SYSTEM::IN-DEFUN DIAG)) (BLOCK DIAG (LIST X (LIST 'QUOTE X)))>)

1. Em análise uma função destas tem o nome de função identidade.

2. http://www.its.caltech.edu/~boozer/lisp/lisp.html#diagonalization

Palavras chave: LISP, self-reference, Godel

Última actualização/Last updated: 2012-02-26 [15:48]

1999-2011 (c) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.