Práticas sobre a linguagem Scheme: Abordagem funcional

U

N I V E R S I D A D E

L

U S A D A

D E

L

I S B O A

Faculdade de Cincias da Economa e da Empresa Mestrado em Cincias da Computao

Prticas sobre a linguagem Scheme: Abordagem funcional

Herclio Rui Dinis Duarte

Lisboa Maro 2012

U

N I V E R S I D A D E

L

U S A D A

D E

L

I S B O A

Faculdade de Cincias da Economa e da Empresa Mestrado em Cincias da Computao

Prticas sobre a linguagem Scheme: Abordagem funcional


Lisboa Maro 2012

LISTA DE ILUSTRAESIlustrao 1 Apresentao do interpretador DrScheme ..................................................... 11 Ilustrao 2 Apresentao da janela de interaces do interpretados DrScheme ............. 12 Ilustrao 3 Apresentao da janela de definies do interpretador DrScheme ................ 12 Ilustrao 4 Apresentao do programa sobre equaes do 2 grau ................................ 13 Ilustrao 5 Apresentao do resultado do programa sobre equaes do 2 grau ............ 14 Ilustrao 6 Apresentao do programa sobre nmeros complexos ................................. 14 Ilustrao 7 Apresentao do resultado do programa sobre nmeros complexos ............. 15 Ilustrao 8 Apresentao do programa sobre rea de objectos....................................... 16 Ilustrao 9 Apresentao do resultado do programa sobre rea de objectos .................. 17 Ilustrao 10 Apresentao do programa sobre cifra de Cesar ......................................... 17 Ilustrao 11 Resultado da apresentao do programa sobre cifra de Cesar ................... 18

LISTA DE TABELASTabela 1 Exemplificao de expresses na linguagem Scheme ................................ 9

PRTICAS SOBRE A LINGUAGEM SCHEME: ABORDAGEM FUNCIONAL

SUMRIO1. Introduo ...................................................................................................... 7 2. O Ambiente de programao Scheme ........................................................... 8 2.1. Abordagem sobre avaliao de expresses ............................................ 8 2.1.1. Expresses ........................................................................................ 9 2.1.1.1. Constantantes ........................................................................... 10 2.1.1.2. Combinaes ............................................................................ 10 2.1.1.3. Nomes ....................................................................................... 10 2.2. O Interpretador DrScheme..................................................................... 10 2.2.1. Janela de Interaces ..................................................................... 11 2.2.2. Janela de definies ........................................................................ 12 3. Programas em Scheme ............................................................................... 13 3.1. Equao do 2 grau ............................................................................... 13 3.1.1. Caractersticas do programa ........................................................... 13 3.1.2. Resultado esperado ........................................................................ 14 3.2. Nmeros complexos .............................................................................. 14 3.2.1. Caracterstica do programa ............................................................. 14 3.2.2. Resultado esperado ........................................................................ 15 3.3. Clculo da rea de objectos .................................................................. 15 3.3.1. Caractersticas do programa ........................................................... 16 3.3.2. Resultado esperado ........................................................................ 16 3.4. Mtodo de cifra de cesar como exemplo de manipulao de strings .... 17 3.4.1. Caractersticas do programa ........................................................... 17 3.4.2. Resultado esperado ........................................................................ 18 4. Concluso .................................................................................................... 19 Referncias ...................................................................................................... 20 Anexos ............................................................................................................. 21 Lista de anexos............................................................................................. 22 Anexo A Programa sobre equaes do 2 grau ..................................... 23 Anexo B Programa sobre nmeros complexos ..................................... 25 Anexo C Programa sobre rea de objectos ........................................... 27 Anexo D Programa sobre cifra de Cesar................................................ 29


6


1. INTRODUOA Linguagem de programao Scheme, originalmente tida como uma ramificao LISP. Em outras palavras, simplesmente um dialeto LISP. O LISP foi a primeira linguagem do paradigma funcional a surgir mas que ainda assim tida como uma das mais importantes pelo facto de obter um uso mais generalisado. (SEBESTA 2002) Existem outras linguagens funcionais, mas como vimos, estas so mesmo puramente funcionais, como o caso do Haskell. O LISP atravs de suas derivaes, foi ganhando outras caractersticas a nivel de paradigma que o tornaram bastante poderosa. Em Pragramao funcional, uma expresso a representao de uma funo. Neste trabalho, pretendo atravs de exemplos demonstrar algumas das potencialidade do Scheme visto como uma abordagem funcional embora tido tambm como uma abordagem multiparadigma. Mediante alguns exerccios, ser possvel ter uma noo abrangente de maneiras que, futuramente poderei ter esta linguagem como soluo em cincias da computao para a resoluo de problemas matemticos em vrias outras reas da cincia.


7


2. O AMBIENTE DE PROGRAMAO SCHEMEO Scheme utiliza um programa denominado REPL (Read-Eval-Print Loop). Este programa possibilita o interpretador ler expresses, avaliar e mostrar resultado. O REPL comporta-se como um computador ao ser requisitado atravs de linhas de comando.

2.1. ABORDAGEM SOBRE AVALIAO DE EXPRESSESUma das formas que permite-nos avaliar e classificar uma linguagem, a forma como o computador avalia e as entradas de dados. Para a avaliao de expresses, o interpretador Scheme basea-se em regras. Segundo MARTINS; CRAVO (2004), Podemos considerar estas regras baseando-se nas seguintes propriedades:

1. Se a expresso uma constante, o seu valor a prpria constante. 2. Se a expresso uma operao primitiva, o seu valor o procedimento interno associado a essa operao. 3. Se a expresso uma combinao, o seu valor calculado do seguinte modo: (a) Avaliam-se as subexpresses na combinao (por qualquer ordem). (b) Aplica-se o procedimento que o valor da primeira subexpresso (o operador) aos argumentos que correspondem aos valores das restantens subexpresses (os operandos). Dada a expresso (+ (* 3 2) (+ (* 2 4) 6) ). Esta ser avaliada ao ser que o seu valor inicial ser representado dentro de um rectngulo e fora um ponto de interrogao a questionar a sua estrutura sinttica. A cada subexpresso gerada, esta ser novamente questionada. Essa ordem vai se mantendo at obtermos ento a satisfao da nossa equao mediante as subformas geradas. Importante realar que nas listas em Scheme, os operadores so os primeiros valores a serem avaliados, s depois aplicado o valor desses operadores aos operandos.


8


(+ (* 3 2) (+ (* 2 4) 6) ) 2.1.1. EXPRESSES

?

MARTINS; CRAVO (2004), afirmam que uma expresso uma entidade computacional que tem valor. Em outras palavras podemos considerar uma expresso como uma construo que retorna um valor. Em Scheme, uma expresso pode ser uma constante, uma combinao ou um nome.

Em notao BNF, uma expresso pode ser representada pelo seguinte: ::= | |

Expresso 50 (* 4 5) (+ 3 4 6) (- 5 6 2) (/ 24 (* 2 4)) (* 5 (* (+ 3 2) (+ 2 1))) (/ 11223 (+ (* 100 100) (+ 234 989)))

Valor 50 20 13 -3 3 75 1

Tabela 1 Exemplificao de expresses na linguagem Scheme

Em scheme raro usar uma expresso nomeando-a atravs de Define. Um Define definido seguido do nome do procedimento e de seus argumentos. O corpo do programa que dita a forma como o procedimento ser avaliado. A forma geral de um Define pode ser expressa da seguinte forma: (define (nome arg1 arg2 arg3...) corpo)

Suponhamos que pretendemos elaborar um pequeno programa que contenha um nome e admite um argumento como um valor de entrada a partir do teclado. Iremos ento exibir como exemplo um conversor de graus Celcius para Farenheit. O Corpo do programa exibe exactamente o comportamento do processo. (define (temperatura temp) (+ 32 (* 1.8 temp))) (display "Celcius - Farenheit")


9


(newline) (temperatura (read)) (newline) No exemplo acima, alm de dependermos do valor a ser entrado pelo teclado, podemos chamar a funo (temperatura temp) a partir da Janela de Interaco do DrScheme, e atribumos um valor a ser calculado. Dessa forma poder ficar assim (temperatura 10). 2.1.1.1. CONSTANTANTES Em Scheme, ao entrarmos uma constant para ser avaliada, como resltado obteremos o valor dessa prpria constante. A constante poder ser nmeros, cadeia de caracteres ou valores lgicos. 2.1.1.2. COMBINAES Em Scheme, uma combinao pode ser vista como a aplicao de um procedimento primitivo (operador) a uma sequencia de operandos. ::= ( *) 2.1.1.3. NOMES A possibilidade de usar-se nomes para a designao de objectos um dos aspectos mais importantes na linguagem Scheme. Esta operao efectua-se atravs do primitivo chamado define, de maneira a que o nome atribuido possa ser reutilizado. Por outras palavras, utilizamos o processo de nomeao para associarmos um nome a uma determinada expresso, como vemos a seguir: (define )

2.2. O INTERPRETADOR DRSCHEMEO DrScheme um interpretador da linguagem Scheme, e como visto anteriormente, o seu funcionamento esta na base leitura-calculo-resposta. Trata-se de uma ferramenta bastante poderosa e de dominio pblico. Pode encontrar-se como disponvel em http://download.plt-scheme.org/drscheme/ ou em http://mega.ist.utl.pt/~ic-fp/2003/.


10


Ilustrao 1 Apresentao do interpretador DrScheme

2.2.1. JANELA DE INTERACESA Janela de Interaces est directamente relacionada com o avaliador. Nesta, encontramos permanentemente num ciclo leitura-avaliao-escrita. (MARTINS; CRAVO, 2004)

Ilustrao 2 Apresentao da janela de interaces do interpretador DrScheme


11


Como vimos atravs da ilustrao, as formas so entradas e ao mesmo tempo so gerados os resultados. A Janela de interaco tambm que permite chamar as funes previamente definidas na Janela das definies.

2.2.2. JANELA DE DEFINIESA Janela de definies, permite escrevermos os nossos programas. Embora o comportamento de um Interpretador de interpretar uma linguagem e devolver logo um resultado, no implica que as suas funes no possam ser anteriormente definidas e chamadas apenas quando necessrio.

Ilustrao 3 Apresentao da janela de definies do interpretador DrScheme

Tambm tem por caracterstica a admisso de vrias equaes em simultneo, para que posteriomente possa haver interaco entre estas. O Scheme fica activo de maneira a verificar o que escrevemos no momento ao indicar as fronteiras de cada forma e aplica uma impresso elegante, mas sem avaliar as formas que escrevemos. (MARTINS; CRAVO, 2004)


12


3. PROGRAMAS EM SCHEME3.1. EQUAO DO 2 GRAUEste programa sobre equao do segundo grau ser importante, sendo que por caracterstica ir exibir 3 tipos de solues possiveis. Pois nessa ordem poderemos observar a utilidade do comando de deciso cond, e sua vantagem realtivamente ao if na linguagem Scheme. A abordagem do cond bem mais simplificada ao lhe dar com a listagem de formulas e testes de qual teste ir resultar em verdadeiro.

Ilustrao 4 Apresentao do programa sobre equaes do 2 grau

3.1.1. CARACTERSTICAS DO PROGRAMA Criao do valor do discriminante ((* b b) (* 4 a c) ): Este o

procedimento em Scheme que ir disponibilizar o comportamento do discrimintante. Se este for igual a zero, negativo ou positivo o programa atribuir um comportamento diferente. Clculo da raz dependentemente do discriminante ((numerador (- (sinal (sqrt delta)) b))) (/ numerador (* 2 a)): Este o procedimento que ir calcular a raz ou as razes caso o determinante no for negativo. Determinao da condio da soluo (raiz): Os procedimentos seguintes, iro determinar o valor da raz dependentemente da funo cond:


13


Quando discriminante > 0 (list (raiz a b c +) (raiz a b c -)): Este o procedimento de condio caso o discriminante for positivo.

Quando discriminante = 0 (list (- b) (* 2 a))): Este o procedimento de condio caso o discriminante for igual a zero. Quando discriminante < 0 (list): Este procedimento de condio caso o discriminante for negativo. 3.1.2. RESULTADO ESPERADO

Ilustrao 5 Apresentao do resultado do programa sobre equaes do 2 grau

3.2. NMEROS COMPLEXOSEste programa de nmeros complexos mostra a manipulao de vrios procedimentos previamente definidos. De uma forma geral, apenas este programa ir orientar-nos na forma como podemos manipular vrios procedimentos em um nico programa.

Ilustrao 6 Apresentao do programa sobre nmeros complexos

3.2.1. CARACTERSTICA DO PROGRAMA


14


Criao da parte real e imaginria (cria-compl

r

i): Este procedimento

permite receber como argumento dois nmeros reais, e cria nmero complexo em que a parte real r e a imaginria i. Criao da parte real (parte-real c): o procedimento que recebe como

argumento a parte real do nosso nmero complexo. Criao da parte imaginria (parte-imaginaria c): o procedimento que

recebe como argumento a parte imaginria do nosso nmero complexo. Exibio do nmero complexo (escreve-compl c): Este procedimento

permite exibir o nmero complexo definido no formato a + bi. Aplicao das operaes ([+] | [-] | [*] | [/]): Aps termos o conceito sobre os nmeros complexos aplicado, podemos ento fazer a sua manipulao mediante operadores aritimticos.

3.2.2. RESULTADO ESPERADO

Ilustrao 7 Apresentao do resultado do programa sobre nmeros complexos

3.3. CLCULO DA REA DE OBJECTOSEmbora nos outros programas deste trabalho temos entradas de dados atravs do teclado, neste subcaptulo haver uma maior ateno neste aspecto. Iremos ver como preparar o nosso programa de maneiras a efectuar calculos pura e simplesmente atravs de dados entrados atravs do teclado.


15


Ilustrao 8 Apresentao do programa sobre rea de objectos

3.3.1. CARACTERSTICAS DO PROGRAMA Mostrar informao no ecr (display "mostrar no ecr): O comando display equivalente ao write em Pascal e printf em C.

Ler informao do teclado (variavel (read)): Esta funo, permite ler informao e atribu-la em uma determinada varivel.

Determinao da rea de

um tringulo (/

(*

base

altura)

2): Este

procedimento, permite calcular a rea do tringulo desejado. Determinao da rea de um quadrado (* lado lado): Este procedimento, permite calcular a rea de um quadrado desejado. Determinao da rea de um crculo (* Pi raio raio): Este procedimento permite calcular a rea do crculo desejado.



16


Ilustrao 9 Apresentao do resultado do programa sobre rea de objectos

3.4. MTODO DE CIFRA DE CESAR COMO EXEMPLO DE MANIPULAO DESTRINGS

Este subcaptulo vem mostrar a forma como o Scheme capaz de manipular strings atravs de procedimentos especficos.

Ilustrao 10 Apresentao do programa sobre cifra de Cesar

3.4.1. CARACTERSTICAS DO PROGRAMA Transformao de caracteres e retorno de uma nova string atravs do String-map: Este procedimento recebe um procedimento proc e que trasnforma caracteres, strings e retorna uma nova string. Definio de uma caixa alta Utilizando o String-upcase: As mensagens que iremos cifrar, so convertidas para uma caixa alta.


17


Converso de caracteres para valores inteiros utilizando o procedimento char-> Integer: Para este programa importante a converso de valores em char para integer de maneira a efectuar as nossas operaes.

Converso de caracteres para ndices entre 0 e 25 utilizando os procedimentos char->ceasar-idx e ceasar-idx->char: Este procedimento importante para posteriomente ser possvel efectuar as operaes de deslocamento em nossa lista de caracteres.

Deslocamento de um caracter atravs do procedimento ceasar-translatechar: Apes efectuar-se a converso em ndeces entre 0 e 25, aplicada a operao que permite efectuar o deslocamento em nossa lista de caracteres.


Ilustrao 11 Apresentao do resultado do programa sobre cifra de Cesar


18


4. CONCLUSOCom este trabalho, foi possivel ter noo sobre os potencias da linguagem Scheme como paradigma funcional. As minhas pesquisas sobre esta linguagem no ficaram por aqui, sendo que existe um mundo sobre esta. Mas importa realar que os exerccios propostos j possibilitaram ter conhecimentos suficientes para avanar com outros projectos. Embora as linguagens funcionais so pouco usuais de uma forma geral, mas deixouse claro que para reas especificas que lidam com expresses matemticas, estas so as mais eficientes tendo em conta ao tempo de resposta ao utilizador. Como vimos que em scheme essa abordagem torna-se possvel, isso porque as suas operaes actuam sobre estruturas de dados em lista.


19


REFERNCIASMARTINS, Joo; CRAVO, Mara (2004) Programao em Scheme Introduo programao utilizando mltiplos paradigmas. 2 ed. Lisboa: IST Press. SEBESTA, Robert (2002) Concepts of programming languages. 5 ed. Colorado: Addison Wesley Higher Education.


20

ANEXOS


LISTA DE ANEXOSAnexo A - Programa sobre equaes do 2 grau Anexo B - Programa sobre nmeros complexos Anexo C - Programa sobre rea de objectos Anexo D - Programa sobre cifra de Cesar


22

ANEXO APrograma sobre equaes do 2 grau

(define discriminante (lambda (a b c) (- (* b b) (* 4 a c))))

(define raiz (lambda (a b c delta sinal) (let ((numerador (- (sinal (sqrt delta)) b))) (/ numerador (* 2 a)))))

(define raizes-grau-2 (lambda (a b c) (let ((delta (discriminante a b c))) (display delta) (newline) (cond ((positive? delta) (list (raiz a b c delta +) (raiz a b c delta -))) ((zero? delta) (list (/ (- b) (+ 2 a)))) (else (list))))))

ANEXO BPrograma sobre nmeros complexos

PRTICAS SOBRE A LINGUAGEM SCHEME: ALGUMAS DEMONSTRAES

(define (compl+ c1 c2) (cria-compl (+ (parte-real c1) (parte-real c2)) (+ (parte-imag c1) (parte-imag c2))))

(define (compl- c1 c2) (cria-compl (- (parte-real c1) (parte-real c2)) (- (parte-imag c1) (parte-imag c2))))

(define (cria-compl r i) (lambda (p) (if (= p 1) r i))) (define (parte-real c) (c 1)) (define (parte-imag c) (c 2)) (define (escreve-compl c) (display (parte-real c)) (if (>= (parte-imag c) 0) (display "+") (display "-")) (display (abs (parte-imag c))) (display "i"))


26


ANEXO CPrograma sobre rea de objectos


27


(define (triangulo_area base altura) ;; Definio das variaveis para a area de um triangulo (/ (* base altura) 2)) (display "Escreva o valor da base e da altura ") (triangulo_area (read) (read)) (newline)

"Continuar para a area de um quadrado"

(newline) (define (quadrado_area lado) (* lado lado)) (display "Escreva o valor do lado do quadrado") (newline) (quadrado_area (read)) (newline)

"Continuar para a area de um circulo"

(newline) (define Pi 3.141592654) (define (area_circulo raio) (* Pi raio raio)) (display "Escreva o valor do raio de um circulo")

(newline) (area_circulo (read)) (newline)

"Fim do nosso ambiente de calculos"


28


ANEXO DPrograma sobre cifra de Cesar


29


( define string-map (lambda (proc s) (let ((l (string - > list s))) (let (( new-list (map proc l))) (list - > string new-list)))))

(define string-upcase (lambda (s) (string-map char-upcase s)))

(define char->ceasar-idx (lambda (x) (let ((a (char->integer #\A))) (- (char->integer x) a))))

(define ceasar-idx->char (lambda (x) (let ((a (char->integer #\A))) (let ((b (+ x a))) (integer->char b)))))

(char->ceasar-idx #\B)

(define ceasar-translate-char (lambda (c k) (ceasar-idx->char ( modulo (+ (char->ceasar-idx c) k) 26))))

(display "DADO ENCRIPTADO NUMA DESLOCAO=3 A CADA CARACTER DO ALFABETO") (newline)


30


(ceasar-translate-char #\K -3) (ceasar-translate-char #\H -3) (ceasar-translate-char #\U -3) (ceasar-translate-char #\F -3) (ceasar-translate-char #\L -3) (ceasar-translate-char #\O -3) (ceasar-translate-char #\L -3) (ceasar-translate-char #\R -3)

(newline) (newline) (display "DADO DESENCRIPTADO PELO MTODO DE CIFRA DE CESAR NUMA DESLOCAO = 3") (newline) (ceasar-translate-char #\H 3) (ceasar-translate-char #\E 3) (ceasar-translate-char #\R 3) (ceasar-translate-char #\C 3) (ceasar-translate-char #\I 3) (ceasar-translate-char #\L 3) (ceasar-translate-char #\I 3) (ceasar-translate-char #\O 3)


31

Documents

Práticas sobre a linguagem Scheme: Abordagem funcional