CLASS #3 - LISP
__________________

# Funções de Ordem Superior

-> As funções de ordem superior permitem aplicar uma função a cada elemento
 de uma lista. Exemplos de funções de ordem superior são o MAPCAR, APPLY, REDUCE.
 

# 1. MAPCAR -------------------------------------------------------------
 
 -> vamos imaginar que queremos definir uma função que soma 1 a cada 
  elemento da lista;
  
 > (setf my_list '(1 2 3 4 5))
 > (mapcar #'1+ my_list)
 (2 3 4 5 6)

-> A função MAPCAR também pode ser muito útil para atribuir valores a variáveis.

-> Imaginemos que queremos fazer SET de cada elemento da lista ARGLIST num conjunto de variávies A, B, C, D.

> (setf arglist '(12.0 145.8 67.2 "M20"))
> (mapcar #'set '(a b c d) arglist)

> a
12.0

> b
145.8

> c 
67.2

> d
"M20"

Sem a função MAPCAR, teríamos de fazer esta função usando:

(setf a (nth 0 arglist))
(setf b (nth 1 arglist))
(setf c (nth 2 arglist))
(setf d (nth 3 arglist))

-> Outro exemplo de aplicação do MAPCAR é na tarefa de converter cada elemento
de uma lista de Strings em inteiros

> (setf my_list '("0" "1" "2" "3"))
> (mapcar #'parse-integer '("1" "2" "3"))
(1 2 3)

-> Também podemos utilizar funções definidas pelo utilizador no MAPCAR.

> (defun converte-fahr-cel (far)
	(/ (- far 32) 1.8) )
	
> (setf temperaturas '(200.0 150.0 300.0))

> (mapcar #'converte-fahr-cel temperaturas)
(93.333336 65.55556 148.88889)

; EXERCISE 1.25. ==========================================================================

(defun mapeia ( func my_list )
"função mapeia que recebe uma função de um argumento e uma lista e devolve uma lista
que contém os resultados de aplicar a função a cada um dos elementos da lista."
	(mapcar func my_list))

(format t "[EX 1.25.] (mapeia #'1+ '(1 2 3)) = ~a~%~%" (mapeia #'1+ '(1 2 3)) )

#2. APPLY ---------------------------------------------------------------

APPLY calls function with arguments, just like funcall but with one difference: the last of arguments is a list of objects, which are passed to function as separate arguments, rather than a single list. We say that apply spreads this list so that each individual element becomes an argument.

(apply #'max 3 -1 '(2 1 2 5 7) )

(defun profundidade ( my_list )
"Defina a função profundidade que recebe uma lista e devolve um número que indica qual é o
nivel mais profundo de listas dentro dessa lista, aumentando de um sempre que se entra para dentro
de uma lista. Se a lista não contém listas devolve 0."
	(cond ((null my_list) 0) 
		  ((atom my_list) -1)
		  ('otherwise
      		(1+ (apply #'max (mapcar #'profundidade my_list))))))
	  
(format t "[EX 1.23.] (profundidade '(1 2 3)) = ~a~%" (profundidade '(1 2 3)) )
(format t "[EX 1.23.] (profundidade '(1 2 (3 ((4)(5 (6)))))) = ~a~%~%" (profundidade '(1 2 (3 ((4) (5 (6)))))) )

#1 (profundidade '(1 2 (3 ( (4) (5 (6)) ))))
* A função mapcar vai aplicar a função profundidade a cada elemento da lista

#1ª ITERACAO: (profundidade '(1 2 (3 ( (4) (5 (6)) )))) ---------- APPLY #'MAX( 0 4 ) -> 4

	#1.1. (1+ (profundidade '1)) -> (1+ -1) -> ( 0 )
	#1.2. (1+ (profundidade '2)) -> (1+ -1) -> ( 0 )
	#1.3. (1+ (profundidade '(3 ((4) (5 (6))))))
	
#2ª ITERACAO: (1+ (1+ (profundidade '(3 ((4) (5 (6))))))) -------- APPLY #'MAX( 1 4) -> 4

	#2.1. (1+ (1+ (profundidade '3)))	-> (+2 -1) -> ( 1 )
	#2.2. (1+ (1+ (profundidade '((4) (5 (6))) ))) 
	
#3ª ITERACAO: (1+ (1+ (1+ (profundidade '((4) (5 (6))) ))) ) -------- APPLY #'MAX( 3 4 ) -> (4)
	
	#3.1. (1+ (1+ (1+ (profundidade '(4) ))) )
	#3.2. (1+ (1+ (1+ (profundidade '(5 (6)) ))))
	
#4ª ITERACAO: (1+ (1+ (1+ (1+ (profundidade '(4) ))) ))	
	
	#4.1. (1+ (1+ (1+ (1+ (profundidade '(4) ))) )) -> (4 -1) -> (3)
	
#5ª ITERACAO: (1+ (1+ (1+ (1+ (profundidade '(5 (6)) )))))	--------- APPLY #'MAX (3 4) -> 4
	
	#5.1. (1+ (1+ (1+ (1+ (profundidade '5 ))))) -> (4 -1) -> (3)
	#5.2. (1+ (1+ (1+ (1+ (profundidade '(6) )))))
	
#6ª ITERACAO: (1+ (1+ (1+ (1+ (1+ (profundidade '(6) ))))))	-> (4)
	
	#6.1. (1+ (1+ (1+ (1+ (1+ (profundidade '6 )))))) -> (5 - 1) -> (4)

-> Podem usar a função TRACE para fazer DEBUG ao programa
> (trace profundidade)
;; Tracing function PROFUNDIDADE
(PROFUNDIDADE)

-> Após o comando TRACE é só chamar a função:
> (profundidade '(1 2 (3 ( (4) (5 (6)) ))))

1. Trace: (PROFUNDIDADE '(1 2 (3 ((4) (5 (6))))))
2. Trace: (PROFUNDIDADE '1)
2. Trace: PROFUNDIDADE ==> -1
2. Trace: (PROFUNDIDADE '2)
2. Trace: PROFUNDIDADE ==> -1
2. Trace: (PROFUNDIDADE '(3 ((4) (5 (6)))))
3. Trace: (PROFUNDIDADE '3)
3. Trace: PROFUNDIDADE ==> -1
3. Trace: (PROFUNDIDADE '((4) (5 (6))))
4. Trace: (PROFUNDIDADE '(4))
5. Trace: (PROFUNDIDADE '4)
5. Trace: PROFUNDIDADE ==> -1
4. Trace: PROFUNDIDADE ==> 0
4. Trace: (PROFUNDIDADE '(5 (6)))
5. Trace: (PROFUNDIDADE '5)
5. Trace: PROFUNDIDADE ==> -1
5. Trace: (PROFUNDIDADE '(6))
6. Trace: (PROFUNDIDADE '6)
6. Trace: PROFUNDIDADE ==> -1
5. Trace: PROFUNDIDADE ==> 0
4. Trace: PROFUNDIDADE ==> 1
3. Trace: PROFUNDIDADE ==> 2
2. Trace: PROFUNDIDADE ==> 3
1. Trace: PROFUNDIDADE ==> 4

-> Para parar o DEBUG, podem usar a função UNTRACE
> (untrace profundidade)

# 3. REDUCE ------------------------------------------------------------

Faz o mesmo que a função APPLY. A única diferença resume-se a eficiência, mas não é muito significativo.
A nível conceptual, as diferenças resumem-se a isto:

> (reduce #'+ (list 1 2 3 4 5))
; translates to: (+ (+ (+ (+ 1 2) 3) 4) 5)

> (apply #'+ (list 1 2 3 4 5))
; translates to: (+ 1 2 3 4 5)

Exemplo:

> (reduce #'+ '(1 2 3 4 5) )
15

> (apply #'+ '(1 2 3 4 5) )
15

> (mapcar #'+ '(1 2 3 4 5) )
(1 2 3 4 5)

; EXERCISE 1.28. ==========================================================================

(defun reduza (func my_list)
"função reduza que recebe uma função e uma lista. A lista deve ter pelo menos dois elementos. 
A função é chamada inicialmente para os dois primeiros elementos da lista, depois entre esse 
resultado e o elemento seguinte da lista e assim sucessivamente"
	(when (< (length my_list) 2)
		(return-from reduza nil))
	
	(let ((res nil))
		  
		  	(setf res (apply func (list (first my_list) (second my_list))))
			(loop for i from 2 to (1- (length my_list)) do
				(setf res (apply func (list res (nth i my_list)))))
	res))

(format t "[EX 1.28.] (reduza #'+ '(1 2 3 4 5 6 7 8)) = ~a~%" (reduza #'+ '(1 2 3 4)) )
(format t "[EX 1.28.] (reduza #'* '(1 2 3 4)) = ~a~%" (reduza #'* '(1 2 3 4)) )
(format t "[EX 1.28.] (reduza #'intersection '((b l a d) (b a d) (r a t))) = ~a~%~%"  (reduza #'intersection '((b l a d) (b a d) (r a t))) )

; EXERCISE 1.26. ==========================================================================

(defun remove-se ( func my_list )
"função remove-se que recebe uma função de teste (de um argumento) e uma lista e retorna a lista que 
 corresponde à lista argumento à qual foram retirados todos os elementos que verificam a função de 
 teste."
	(cond ((null my_list) nil)
	  	  ((funcall func (car my_list)) (remove-se func (cdr my_list)))
	   	  ('otherwise 
			  (cons (car my_list) (remove-se func (cdr my_list))))))

(format t "[EX 1.26.] (remove-se #'(lambda (n) (> n 5)) '(1 2 3 4 5 6 7 8 9)) = ~a~%~%" (remove-se #'(lambda (n) (> n 5)) '(1 2 3 4 5 6 7 8 9)) )

# 4. LAMBDA -------------------------------------------------------------
 
-> Por vezes, existem situações onde queremos utilizar uma função dentro
de um programa. No entato, essa função é tão trivial que não faz sentido
criar uma função nova.

-> Para estas situações, o LISP permite a utilização da função LAMBDA.
O LAMBDA pode ser visto como uma função que é definida dentro de outra e que
apenas pode ser utilizada dentro da função onde está definida.

-> Podem ver o Lambda como uma função encapsulada noutra função.

-> A sintax da função LAMBDA e a seguinte:

(lambda (parameters) body)

Exemplo:

-> Podemos definir uma função lambda que calcula o quadrado de um número:

> (lambda (x) (* x x))
#<FUNCTION :LAMBDA (X) (* X X)>

-> Para chamar a função LAMBDA com um determinado argumento, basta utilizar a função FUNCALL:

> (FUNCALL (lambda (x) (* x x)) 7 )
49

; EXERCISE 1.27. ==========================================================================

(defun todos? ( my_list func )
"função todos? que recebe uma lista de elementos e uma função de teste (de uma argumento)
e retorna verdade se todos os elementos da lista verificam a função e falso em caso contrário."
	(loop for i in my_list do
		(when (not (funcall func i))
			(return-from todos? nil)))
	t)

(format t "[EX 1.27.] (todos? '(1 2 3 4 5 6 7 8 9) #'(lambda (n) (> n 5)) ) = ~a~%~%" (todos? '(1 2 3 4 5 6 7 8 9) #'(lambda (n) (> n 5))) )
(format t "[EX 1.27.] (todos? '(6 7 8 9) #'(lambda (n) (> n 5)) ) = ~a~%~%" (todos? '(6 7 8 9) #'(lambda (n) (> n 5))) )

-> Exemplo (TESTE de 2008 / 2009): -------------------------------------------------

> (defun R ( x y z )
	(if (null z)
		()
		(if (eq x (car z))
			(cons y (R x y (cdr z)))
			(cons (car z) (R x y (cdr z))))))
			
> (defun Y (y)
	#'(lambda (x) (R (car y) x y)))
	
> (setf F (Y '(A B A)))

* Qual o resultado depois de avaliar por ordem as seguintes expressões
> (funcall F 'B)
> (funcall F 'C)

-> Na primeira expressão, vamos chamar a função Y com argumentos '(A B A) e com
lambda X = 'B.

(R (car '(A B A) 'B '(A B A)))
	(R 'A 'B '(A B A))
		(cons 'B (R 'A 'B '(B A)))
			(R 'A 'B '(B A))
				(cons 'B (R 'A 'B '(A)))
					(R 'A 'B '(A))
						(cons 'B (R 'A 'B nil ))
							(R 'A 'B nil)
								nil
								
(cons 'B (cons 'B (cons 'B nil))) -> '(B B B)

-> Na segunda expressão, vamos chamar a função Y com argumentos '(A B A) e com
lambda X = 'C.

(R (car '(A B A) 'C '(A B A)))
	(R 'A 'C '(A B A))
		(cons 'C (R 'A 'C '( B A )))
			(R 'A 'C '( B A ))
				(cons 'B (R 'A 'C '(A) ))
					(R 'A 'C '(A) )
						(cons 'C (R 'A 'C nil ))
							nil
							
(cons 'C (cons 'B (cons 'C nil))) -> '(C B C)

-> Podiam ter resolvido o exercicio mais depressa se percebessem o que a função R faz.
-> Basicamente, substitui o primeiro e último elementos da lista da função Y pela variável dada no FUNCALL.

; EXERCISE 1.35. ==========================================================================

(defun misterio (n1)
	#'(lambda (x n2)
		(cond ((eql x 'd) (setf n1 (+ n1 n2)))
			  ((and (eql x 'l) (<= n2 n1)) (setf n1 (- n1 n2)))
			  ((and (eql x 'l) (> n2 n1)) 'nao-tem-suficiente)
			  (t 'operacao-desconhecida))))
			  
(defvar MINHA)

(setf minha (misterio 200))		; inicia conta a 200
(format t "[EX 1.35.2.1] (funcall minha 'l 100) = ~a~%" (funcall minha 'l 100) )	; 100			
(format t "[EX 1.35.2.2] (funcall minha 'lav 0) = ~a~%" (funcall minha 'lav 0) )	; OPERACAO-DESCONHECIDA
(format t "[EX 1.35.2.3] (funcall minha 'l 0) = ~a~%" (funcall minha 'l 0) )		; 100
(format t "[EX 1.35.2.4] (funcall minha 'l 200) = ~a~%" (funcall minha 'l 200) )	; NAO-TEM-SUFICIENTE
(format t "[EX 1.35.2.5] (funcall minha 'd 100) = ~a~%" (funcall minha 'd 100) )	; 200
(format t "[EX 1.35.2.6] (funcall minha 'd 0) = ~a~%" (funcall minha 'd 0))			; 200
(format t "[EX 1.35.2.7] (funcall minha 'd 200) = ~a~%~%" (funcall minha 'd 200) )	; 400

# OUTROS EXERCÍCIOS ----------------------------------------------------------------------

; EXERCISE 1.36. ==========================================================================
	
(defun eleva (base &optional (exp 2))
"função eleva, que eleva um número a uma determinada potência. Se a potência não for
indicada deverá ser considerada 2."
	(if (= exp 0)
		1
		(* base (eleva base (1- exp)))))

(format t "[EX 1.36] (eleva 3) = ~a~%" (eleva 3) )
(format t "[EX 1.36] (eleva 3 4) = ~a~%~%" (eleva 3 4) )

; EXERCISE 1.37. ==========================================================================

(defun eleva* (&key base expoente)
"função eleva* que eleva um número a uma determinada potência
em que deixa de ser necessário saber a ordem dos seus argumentos"
	(if (= expoente 0)
		1
		(* base (eleva base (1- expoente)))))

(format t "[EX 1.37] (eleva* :base 3 :expoente 4) = ~a~%" (eleva* :base 3 :expoente 4) )
(format t "[EX 1.37] (eleva* :expoente 4  :base 3) = ~a~%~%" (eleva* :expoente 4  :base 3) )

; EXERCISE 1.38. ==========================================================================

(defun faz-lista ( &rest args )
"função faz-lista que recebe qualquer número de argumentos e devolve uma lista com
todos eles."
	args)

(format t "[EX 1.38] (faz-lists 1 2 3 4) = ~a~%~%" (faz-lista 1 2 3 4) )

# AGENTES -------------------------------------------------------------------------------------

-> é tudo o que é capaz de captar / perceber o ambiente onde se encontra 
 através de sensores e actua nesse ambiente através de actuadores. Os agentes
 devem ser autónomos.
 
 
-> Exercícios da secção de AGENTES

; EXERCISE 1. ==============================================================================
; AGENTE DE REFLEXOS SIMPLES

-> Neste tipo de agentes, o agente reage directamente a um estímulo. Não há necessidade de 
memória ou de guardar um estado interno.

-> Não precisa de ter variáveis definidas.


-> As percepcoes de um agente são geralmente definidas numa estrutura:

(defstruct aspirador
	lixo-p toque-p)

-> Depois é só definir que acções o agente vai realizar para cada percepção:

(defun agente_aspirador (p)
	(cond ((aspirador-lixo-p p) 'ASPIRAR)
		  ((aspirador-toque-p p) 'RODAR)
		  (t 'ANDAR)))

-> Para chamar o agente, no CLISP, temos de definir uma percepcao:			   
> (setf percepcao (make-aspirador :lixo-p nil :toque-p nil))

-> E só depois podemos chamar o agente
> (agente_aspirador percepcao)	; ANDAR

(setf percepcao (make-aspirador :lixo-p t :toque-p nil))
(agente_aspirador percepcao)	; ASPIRAR

(setf percepcao (make-aspirador :lixo-p nil :toque-p t))
(agente_aspirador percepcao)	; RODAR

; EXERCISE 2. ==============================================================================
; AGENTE DE REFLEXOS COM MODELO

-> REGRA DE OURO: um agente é de reflexos com estado interno SE HOUVER NECESSIDADE DE GUARDAR ALGUMA INFORMACAO!
-> A função do agente contem sempre um LET com as variáveis que precisa de guardar. No agente anterior (reflexos simples)
já não era necessário! 
-> Neste exercicio precisamos de saber a posicao e a rotacao do robot!

-> Mais uma vez, primeiro definimos as percepções do agente
(defstruct aspirador2
	lixo-p)

-> E depois todas as acções que ele faz perante cada percepção

(defun agente_aspirador2 ()
	(let ((posicao 0)
		   (rodou-p 0))
		#'(lambda (p)
			(let ((lixo (aspirador2-lixo-p p)))
				(cond ((and (not lixo) (= posicao 0)) (incf posicao) 
						'ANDAR)
					  ((and (not lixo) (= posicao 1) (= rodou-p 0)) 
					  	(incf rodou-p) 'RODAR)
					  ((and (not lixo) (= posicao 1) (= rodou-p 1))
					    (incf posicao) (decf rodou-p) 'ANDAR)
					  ((and (not lixo) (= posicao 2) (= rodou-p 0))
					   (incf rodou-p) 'RODAR)
					  ((and (not lixo) (= posicao 2) (= rodou-p 1))
						(incf posicao) (decf rodou-p) 'ANDAR)
					  ((and (not lixo) (= posicao 3) (= rodou-p 0))
					   (incf rodou-p) 'RODAR)
					  ((and (not lixo) (= posicao 3) (= rodou-p 1))
					   (incf posicao) (decf rodou-p) 'ESPERAR)
					  ((= posicao 4) 
					  	'ESPERAR)
					  (t 'ASPIRAR))))))

-> Para chamar este agente no CLISP, procedemos da seguinte forma:

-> Definimos a percepção:
(defparameter *percep* (make-aspirador2 :lixo-p t ))

-> Criamos uma instância do agente aspirador2. Vamos-lhe chamar ROBOT:
> (setf ROBOT (agente_aspirador2))
				  
-> Depois é só chamar o ROBOT usando a função FUNCALL
> (funcall ROBO *percep*)	; ASPIRAR

-> Podemos alterar a percepção:
(defparameter *percep* (make-aspirador2 :lixo-p nil ))

-> E chamar o agente ROBOT N vezes:

> (funcall ROBOT *percep*)	; ANDAR
> (funcall ROBOT *percep*)	; RODAR
> (funcall ROBOT *percep*)	; ANDAR
> (funcall ROBOT *percep*)	; RODAR
> (funcall ROBOT *percep*)	; ESPERAR
> (funcall ROBOT *percep*)	; ESPERAR

; EXERCISE 3. TESTE 2008 / 2009 ===============================================================

A Fofoca é uma foca que trabalha num circo. A tarefa da Fofoca é responder a diferentes
indicações do seu treinador. Assim:

1. sempre que apanha 4 peixes (recebidos um de cada vez e não necessariamente consecutivos),
a Fofoca bate palmas (acção PALMAS);

2. sempre que apanha uma bola, a Fofoca deve equilibrá-la no focinho (acção EQUILIBRA);

3. sempre que o treinador lhe toca na cabeça, a Fofoca deve fazer o pino (acção PINO).

Assuma ainda que:
4. Quando o treinador não lhe dá nenhuma indicação, a Fofoca faz “AOHAOH”;

5. Faz igualmente “AOHAOH” quando recebe mais do que uma indicação do treinador ao
mesmo tempo (por exemplo, recebe uma bola e faz o pino). Nestes casos fica confusa e faz
apenas “AOHAOH”;

6. Apenas de 4 em 4 peixes é que a Fofoca bate palmas, manifestando-se com o “AOHAOH”,
enquanto não chegar ao 4º elemento de cada grupo de peixes (por exemplo, recebe o segundo
peixe e faz “AOHAOH”).

Considere agora que vários circos virtuais encomendaram agentes focas com a mesma
funcionalidade da Fofoca.

#1. Defina o tipo percepcao para este agente

(defstruct percepcao
	peixe
	bola
	toque)

#2. Implemente o agente-foca em Lisp.
(defun agente-foca ()
	(let ((num_peixes 0))
		#'(lambda (percep)
			(cond ( (or 
  					  (and (percepcao-peixe percep) (percepcao-bola percep))
  					  (and (percepcao-peixe percep) (percepcao-toque percep))
  					  (and (percepcao-bola percep) (percepcao-toque percep))) 'AOHAOH )
				   ( (percepcao-bola percep) 
				   	'EQUILIBRA )
				   ( (percepcao-toque percep) 
				   	'PINO )				  
				   ((percepcao-peixe percep)
				   		(if (= 3 num_peixes)
						(progn
							(setf num_peixes 0)
							'PALMAS)
						(progn
							(incf num_peixes)
							'AOHAOH)))
		  				 
				  (t 'AOHAOH)))))

-> Para testar a função, podemos criar uma percepcao onde há peixe		  
> (defparameter *percep* (make-percepcao :peixe t :bola nil :toque nil))

-> Criamos uma instância do agente FOFOCA
> (setf FOFOCA (agente-foca))

-> E basta chamar a função 4x para a FOFOCA retornar PALMAS 
> (funcall FOFOCA *percep*)	; AOHAOH
> (funcall FOFOCA *percep*) ; AOHAOH
> (funcall FOFOCA *percep*) ; AOHAOH
> (funcall FOFOCA *percep*) ; PALMAS
	
-> Podemos testar as outras percepções:
> (defparameter *percep* (make-percepcao :peixe nil :bola t :toque nil))
> (funcall FOFOCA *percep*) ; EQUILIBRA

> (defparameter *percep* (make-percepcao :peixe nil :bola nil :toque t))
> (funcall FOFOCA *percep*) ; PINO

-> ATENÇÂO: PORQUE É QUE SE DEFINIU PRIMEIRO A CONDIÇÂO OR?
-> Porque o COND é uma função sequencial: quando encontra uma condição onde se verifica o argumento, não são avaliadas
 as restantes condições do programa.
-> Ou seja, se colocassemos primeiro a condição: ((percepcao-bola percep) 'EQUILIBRA )) ou ((percepcao-toque percep) 'PINO))
o que aconteceria no programa era que sempre que houvesse uma bola, a FOFOCA iria retornar sempre 'EQUILIBRA. Ou se houvesse 
sempre um toque, a FOFOCA iria retornar sempre 'PINO. 
-> Nunca seria verificada a condição "se a FOFOCA receber mais do que uma percepção, retorna 'AOHAOH".	
 	
#3. Que tipo de agente deve ser o agente-foca? Justifique.
-> É um agente de reflexos com estado interno, dado que necessita de manter informações obre o estado
(nomeadamente sobre o número de peixes apanhados) de modo a poder tomar decisões.