LISP - Notas de Aula -------------------- Linguagens Funcionais (Ex: LISP) Principais caracter'isticas de uma linguagem funcional: - fun,c~oes que n~ao modificam seus argumentos - uso limitado de vari'aveis globais - uso limitado de atribui,c~ao - fun,c~ao pode retornar o que quiser Outras caracter'isticas importantes, especificas de LISP - dados e programas t^em o mesmo formato (listas) - input / output fica bastante simplificado - MUITAS fun,c~oes pr'e-definidas ----------------------------------------------------------------------------- Tudo em LISP 'e S-express~ao ('unico tipo). Qualquer vari'avel aceita qualquer S-express~ao como valor ! Contudo, h'a alguns subtipos. S-express~oes: - 'atomos: - num'ericos - strings - s'imbolos - par-com-ponto: - listas - n~ao-listas Representa,c~ao de S-express~oes: . representa,c~ao gr'afica: caixinhas . representa,c~ao textual: caracteres ----------------------------------------------------------------------------- 'Atomos t^em representa,c~ao gr'afica IGUAL `a representa,c~ao textual Gr'afica | Textual ------------------------- n'umero 1 | 1 string "casa" | "casa" s'imbolo CASA | CASA Dentro da string faz diferen,ca Mai'usculas / Min'usculas. Em s'imbolos tanto faz. O interprestador sempre imprime s'imbolos usando mai'usculas. Outros exemplos de 'atomos: +1 (n'umero); 1+ (s'imbolo); ganhei! (s'imbolo) "(" e ")" (abre- e fecha-par^enteses) s~ao caracteres especiais em LISP. N~ao podem ser usados em s'imbolos. ----------------------------------------------------------------------------- Par-com-Ponto: estrutura formada por um par de S-express~oes. Ou seja, duas S-express~oes s~ao usadas para formar uma. Ex: podem ser dois 'atomos; uma pode ser 'atomo e a outra par-com-ponto; ambas podem ser pares-com-pontos; etc (e assim sucessivamente / recursivamente :) ) A ordem em que aparecem as duas S-express~oes componentes 'e relevante. Na represenat,c~ao gr'afica, colocamos uma caixa com dois compartimentos, cada um deles com um apontador para uma componente do par-com-ponto. Na representa,c~ao textual, colocamos as duas componentes separadas por um ponto (caracter ".") e envolvemos com um par de par^entesis. Observe que o ponto (".") deve vir com um branco de cada lado, sen~ao pode ser considerado parte do nome de um s'imbolo. GR'AFICA | TEXTUAL ----------------------------------------------- +-------+ | | | | | ( A . B ) +-------+ | / \ | A B | | ----------------------------------------------------------------- +-------+ | | | | | +-------+ | / \ | +-------+ +-------+ | | | | | | | | +-------+ +-------+ |( ( A . 1 ) . ( "ca" . ( x . 10.0 ) ) ) / \ / \ | A 1 "ca" +-------+ | | | | | +-------+ | / \ | x 10.0| ----------------------------------------------------------------------------- Listas: admitem forma textual alternativa (elimina muitos dos par^enteses e pontos). Observe que par^enteses em LISP nunca s~ao "de gra,ca". Por exemplo, em Pascal, tanto faz escrever a:= 8 ou a:= (8). Em LISP, (A . B) e' diferente de ((A) . B) ou de ((A . B)). Cada par de par^enteses significa uma caixa a mais! 'Atomo especial: NIL (do latim nada) Representa a lista vazia Gr'afica | Textual -------------------------- NIL | NIL ou () -> formas equivalentes NIL: representa tamb'em o valor booleano falso. Qualquer outro valor 'e verdadeiro Par-com-ponto: tem dois componentes que podem ser 'atomos ou pares-com-ponto Listas (defini,c~ao): Uma lista 'e NIL ou um par-com-ponto cujo segundo elemento 'e uma lista. Lista tem representa,c~ao textual simplificada: Gr'afica | Textual ------------------------------------- +---------+ | ( A . NIL ) ou ( A ) | A | NIL | | +---------+ | Gr'afica: +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ | S1 | |-->| S2 | |-->| S3 | |-->| S4 | |-->| S5 | |-->| S6 | |-->NIL +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ | | | | | | qq coisa qq coisa qq coisa qq coisa qq coisa qq coisa Textual: ( S1 S2 S3 S4 S5 S6 ) ao inv'es de ( S1 . ( S2 . ( S3 . ( S4 . ( S5 . ( S6 . NIL ) ) ) ) ) ) Outro exemplo: Gr'afica: +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ | | |-->| | |-->| | |-->| | |-->| | |-->| | |-->NIL +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ | | | | | | A B +-------+ +-------+ D E | | |-->| | |-->NIL +-------+ +-------+ | | A B Textual: ( A B ( A B ) D E ) ----------------------------------------------------------------------------- LISP n~ao 'e compilado, 'e INTERPRETADO Voc^e entra com uma S-express~ao e ele avalia essa S-express~ao Veremos isso na aula 2. ----------------------------------------------------------------------------- O interpretador LISP Dads uma S-express~ao, o interpretador a avalia, isto 'e, calcula o seu valor. Embora ele fa,ca isso para qualquer S-express~ao que seja dada, na pr'atica s'o usamos 'atomos ou listas, por isso concentraremos nossa discuss~ao em 'atomos e listas. Valor de 'atomos . num'ericos: o valor 'e o pr'oprio 'atomo . strings: o valor 'e o pr'oprio 'atomo . s'imbolos: t^em dois valores independentes - valor como dado - valor como fun,c~ao Dependendo da posi,c~ao do s'imbolo na express~ao, seu valor como dado ou como fun,c~ao ser'a usado. Isso ficar'a mais claro quando falarmos de valores de listas. Valor de listas . Lista tem que ter um s'imbolo como primeiro elemento Exemplo: ( soma 2 5 1 ) ---> correto ( (a) b c) ---> errado, 1o. elemento n~ao 'e s'imbolo . Este s'imbolo deve ter valor como fun,c~ao . O valor da lista 'e o resultado da chamada desta fun,c~ao tendo como argumentos os valores dos elementos restantes da lista Exemplos de avalia,c~ao: (nota: o caracter ">" que aparece no in'icio de certas linas abaixo indica o "prompt" do interpretador; linhas iniciadas com ">" cont'em o qe digitamos para o interpretador; linhas n~ao iniciadas com ">" indicam a resposta do interpretador, ou seja, o valor do que digitamos) > 10 10 > "babacas" "babacas > NIL NIL > ( + 2 3 8) 13 > + Erro: + n~ao tem valor como dado > ( 1 2 3) Erro: Primeiro elemento n~ao 'e s'imbolo > ((+ 1 2)) Erro: Primeiro elemento n~ao 'e s'imbolo Nota,c~ao funcional ------------------- Uma das grandes diferen,cas entre LISP e outras linguagens 'e a forma como se faz a chamada de fun,c~oes. Em Pascal, C e outras as chamadas s~ao da forma f(x,y,z), por exemplo. Isto vem da forma como escrevemos em matem'atica. Por'em, em LISP esta mesma chamada seria escrita assim: (F X Y Z) Note que, al'em de as v'irgulas serem subtitu'idas por brancos, o nome da fun,c~ao entra dentro dos par^enteses junto com os argumentos! Os alunos devem estar sempre alertas para evitar escrever F (X Y Z), que est'a errado. Como modificar os valores de s'imbolos -------------------------------------- Valor como dado Use a macro pre'-definida SETF (nota: macros s~ao como fun,c~oes, mas n~ao podem ser chamadas de fun,c~oes por uma s'erie de motivos, por exemplo, elas n~ao avaliam todos os seus argumentos). Formato geral de SETF: (setf ) A,c~ao: a S-expressao 'e avaliada. Seu valor fica sendo o valor como dado do s'imbolo Exemplo: (setf x 5) modifica o valor como dado do s'imbolo X para 5 Valor como fun,c~ao Use a macro pre'-definida DEFUN Formato geral de DEFUN: (defun ) A,c~ao: 'e o s'imbolo que vai receber um novo valor como fun,c~ao. A fun,c~ao ter'a lista de argumentos especificada por . O corpo da fun,c~ao, especificado por , e' uma sucess~ao de zero ou mais S-express~oes, possivelmente envolvendo os argumentos, que ser~ao avaliadas uma a uma quando a fun,c~ao for chamada. O valor retornado pela fun,c~ao 'e o valor da 'ultima S-espress~ao avaliada. Os valores das S-express~oes anteriores s~ao descartados. Exemplo: (defun x (a b c) (+ a b c)) coloca valor como fun,c~ao no s'imbolo X. A fun,c~ao X recebe tr^es argumentos e retorna sua soma. A fun,c~ao X foi definida a partir da fun,c~ao pre'-definida +. Mais exemplos modificando valores de s'imbolos: > (setf x (a b)) Erro: A n~ao tem valor com fun,c~ao Deu erro quando o interpretador foi avaliar (A B). > (setf x '(a b)) (A B) > (setf a 1) 1 > x (A B) Observe que, mesmo mudando o valor de A para 1, o valor de X, que cont'em o s'imbolo A, n~ao mudou para (1 B). Isto porque o valor de X 'e uma lista contendo A e B, e n~ao o valor de A e o valor de B. Um s'imbolo e seu valor s~ao coisas diferentes. Fun,c~oes pr'e-definidas ------------------------ CAR . Esta fun,c~ao retorna o primeiro elemento de um par-com-pronto . D'a erro se argumento for 'atomo, exceto CAR de NIL, que 'e NIL > (CAR '(a b)) A > (CAR 10) Erro > (CAR '(a.b)) A > (CAR ()) NIL CDR . Retorna o segundo elemento de um par-com-ponto . D'a erro se argumento for 'atomo, exceto que CDR de NIL 'e NIL > (CDR '(a b)) B > (CDR 10) Erro > (CDR '(a.b)) B > (CDR ()) NIL CONS : 2 argumentos . Retorna um par-com-ponto cujo primeiro elemento 'e o primeiro argumento e o segundo elemento 'e o segundo argumento > (CONS 1 2) (1 . 2) > (CONS 'A (CONS 'B (CONS 'C NIL))) (A B C) Nota: Os 'atomos 1 e 2 t^em valor que 'e o pr'oprio. Mas 'atomos simb'olicos como A, B e C devem ser precedidos de ap'ostrofe ("'") para evitar que sejam avaliados. O ap'ostrofe 'e abrevia,c~ao da macro pr'e-definida QUOTE que retorna seu argumento sem avalia,c~ao. Mais explicitamente, 'A equivale a (QUOTE A) cujo valor 'e A. Observe que NIL n~ao precisa de QUOTE pois seu valor j'a vem pr'e-definido como NIL. LENGTH : 1 argumento . D'a erro se argumento n~ao for lista . Retorna o n'umero de elementos da lista > (LENGTH '(a (b c) d)) 3 REVERSE : 1 argumento . D'a erro se argumento n~ao for lista . Retorna uma lista com os mesmos elementos em ordem inversa > (REVERSE '(a (b c) d)) (D (B C) A) + : n'umero arbitr'ario de argumentos . Retorna a soma deles todos . D'a problema se algum dos argumentos n~ao tiver valor num'erico . Se forem dados zero argumentos, o resultado ser'a zero > (+ -3 4 5) 6 > (+) 0 - : 2 argumentos . Retorna o primeiro menos o segundo argumento . D'a problema se algum dos argumentos n~ao tiver valor num'erico Obs: Existe uma vers~ao de - com um argumento. Neste caso, retorna o oposto num'erico do valor de seu argumento. Por exemplo, (- 3) d'a -3. * : n'umero arbitr'ario de argumentos . Retorna o produto deles todos . D'a problema se algum dos argumentos n~ao tiver valor num'erico . Se forem dados zero argumentos, o resultado ser'a 1 / : 2 argumentos . Retorna o primeiro dividido pelo segundo argumento . D'a problema se algum dos argumentos n~ao tiver valor num'erico > (/ 3 4) 0.75 > (/ 1 2 3) Erro: / requer 2 argumentos Obs: Existe uma vers~ao de / com um argumento. Neste caso, retorna o inverso num'erico do valor de seu argumento. Por exemplo, (/ 2) d'a 0.5. Condicionais ------------ Condicionais n~ao s~ao exatamente fun,c~oes, pois nem sempre avaliam todos os seus argumentos e `as vezes avaliam-nos de maneira diferente, como COND abaixo. S~ao chamados de formas por causa disso. Mas sempre retornam um valor, como as fun,c~oes normais. IF : 3 argumentos . Retorna o valor do segundo ou o valor do terceiro argumento dependendo do valor do primeiro . Se o primeiro argumento for NIL, If retorna o valor do terceiro argumento e nem sequer avalia o segundo argumento . Se o valor do primeiro for diferente de NIL, IF retorna o valor do segundo e n~ao avalia o terceiro > (defun max (a b) ( IF (> a b) a b ) ) MAX > (max 1 2) 2 COND : N'umero qualquer de argumentos . Cada argumento tem que ser uma lista de 2 elementos . Se o primeiro elemento tiver valor diferente de NIL, 'e retornado o valor do segundo elemento . A avalia,c~ao procede do primeiro ao 'ultimo argumento, parando quando for encontrado um argumento com valor do primeiro elemento diferente de NIL. Neste caso retorna o valor do segundo elemento deste argumento. . Se os primeiros elementos de todos os argumentos tiverem valor NIL, a forma retorna NIL. Formato geral: ( COND ( primeiro_elemento segundo_elemento) ( primeiro_elemento segundo_elemento) ... ( primeiro_elemento segundo_elemento) ( primeiro_elemento segundo_elemento) ) ----------------------------------------------------------------------------- LET - 'e uma forma que permite introduzir vari'aveis locais. Formato do LET: (let ( ( ) ( ) . . . ( ) ) ) ) O valor retornado por LET 'e o valor da S-express~ao , na qual podem aparecer os s'imbolos , , ..., . Os s'imbolos , ..., t^em valores especificados na primeira parte do LET. Estes s'imbolos encobrem outros s'imbolos de mesmo nome que porventura existam em escopos externos ao bloco formado pelo LET. Ao terminar a avalia,c~ao do LET, estes s'imbolos externos de mesmo nome que , ..., , se houver, n~ao s~ao alterados em nada. Em particular seus valores se mant'em. LIST - recebe um numero arbitrario de S-express~oes e retorna uma lista contendo seus valores. Exemplo: C'alculo do valor das ra'izes de uma equa,c~ao do segundo grau (usando B'ascara [n~ao tenho certeza de como se escreve o nome deste sujeito]) Suponha que a equa,c~ao 'e ax^2 + bx + c. Os argumentos da fun,c~ao s~ao os valores a, b e c. Ser'a retornada uma lista com as duas ra'izes. (defun solucao (a b c) (list (x1 a b c) (x2 a b c) ) ) Note a intodu,c~ao de duas fun,c~oes auxiliares X1 e x2 para calcular cada raiz. Tanto x1 como x2 devem receber os tr^es argumentos a, b e c. (defun x1 (a b c) (/ (+ (- 0 b) (sqrt (- (* b b) (* 4 a c))) (* 2 a)) ) ) (defun x2 (a b c) (/ (- (- 0 b) (sqrt (- (+ b b) (* 4 a c))) (* 2 a)) ) ) Note que express~oes aritm'eticas s~ao todas escritas em nota,c~ao prefixa, devido ao car'ater funcional de LISP. > (solucao 1 2 1) (1 1) Agora usando o LET (defun solucao (a b c) (let ((delta (sqrt(-(* b b) (* 4 a c)) ) ) (list (/(+(- 0 b) delta) (* 2 a)) (/(-(- 0 b) delta) (* 2 a)) ) ) \ OBS: (let ((delta **A**)) | **B** > bloco LET ) | / sendo **A** um valor e **B** um conjunto de S-express~oes Voc^e pode usar "delta" dentro de **B**, porem n~ao fora do bloco LET. A vari'avel "delta" 'e local no bloco LET. Como separar seu programa em arquivos ------------------------------------- Em LISP voc^e pode ter seus programas gravados em mais de um arquivo. O que se deve fazer 'e "carregar" cada arquivo para que o interpretador possa interpret'a-lo: > (load "arquivo.lsp") T Recurs~ao --------- Em programas funcionais (principalmente em LISP) usa-se muita recurs~ao. Por exemplo, imaginem uma fun,c~ao chamada MEMBER que recebe dois argumentos. O segundo argumento 'e uma lista e o primeiro pode ser qualquer coisa. A fun,c~ao retorna T se o primeiro elemento est'a na lista (que 'e o segundo argumento) e NIL se n~ao estiver. Exemplo de funcionamento desejado: > (member 'a '(a b c)) T > (member 'a '((a) (b) (c))) NIL > (member '(a b) '(b (a b) (a c))) T A funcao MEMBER j'a existe em LISP, por'em vamos defini-la para ilustrar recurs~ao: (defun member (x l) (cond ((null l) nil) ((equal x (car l)) t) (t (member x (cdr l))) ) ) Observe as fun,c~oes novas que foram usadas aqui: NULL - fun,c~ao que retorna T se o argumento 'e NIL e NIL se o argumento 'e diferente de NIL. Serve para testar se uma lista 'e vazia. EQUAL - testa igualdade entre duas S-express~oes ----------------------------------------------------------------------------- Notas tomadas por Cristina Zanini - RA 950369 Edvaldo Oliveira - RA 950496 Melissa Gigliotti - RA 951822 e editadas por Jo~ao Meidanis