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á f¹.

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ópria². 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)

> (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/keywords: LISP, self-reference, Godel

Criado/Created: NaN

Última actualização/Last updated: 10-10-2022 [14:25]

Voltar à página inicial.