assas

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �

Scheme

2

Índice

3

ÍNDICE

Capítulo 1 Introdução 07

Breve introdução histórica 08

Principais Características do Scheme 09

Comparação entre o Scheme e o Common Lisp 10

Sistemas Operativos Suportados 11

Livros e Anotações sobre Scheme 11

Capítulo 2 Instalação 13

Instalação em Windows 14

Instalação em Unix 14

Instalação em OS/2 15

Variáveis de Ambiente 16

Capítulo 3 O Editor do Scheme 17 Carregar Ficheiros 19

Compilar os Programas 20

Capítulo 4 Elementos da Linguagem 23 Maiúsculas e Minúsculas 24

Linhas de Comentário 24

Elementos Primitivos 24

Combinações 25

Avaliação de Combinações 27

Tipos de Dados 27

Definição de Funções 28

Símbolos 30

Capítulo 5 Expressões Condicionais 31 Predicados 32

Operadores Lógicos 33

Scheme

4

Selecção Simples 34

Selecção Múltipla 34

Formas Especiais 35

Outras Expressões Condicionais 37

Capítulo 6 Funções 39

Funções Recursivas 40

Variáveis Locais 41

Capítulo 7 Âmbito e Duração 43 Âmbito de uma Referência 44

Duração de uma Referência 45

Capítulo 8 Dados 47 Átomos 48

Combinações de Dados 49

Abstracção de Dados 50

Tipos Abstractos de Informação 51

Capítulo 9 Listas 53

Operações sobre Listas 54

Listas de Argumentos 56

Tipos de Aglomerados 56

Capítulo 10 Vectores 59

Construção de Vectores 60

Operações Sobre Vectores 61

Capítulo 11 Estruturas de dados 63

Índice

5

Capítulo 12 Programação Imperativa 67

Atribuição 68

Sequências de código 69

Repetição 70

Capítulo 13 Modelos de Ambiente 73

Âmbito Léxico 74

Âmbito Dinâmico 76

Capítulo 14 Parâmetros Especiais 79

Parâmetros Opcionais 80

Parâmetros de Resto 80

Capítulo 15 Macros 81

Escrita de Macros 82

Caracteres de Macro 83

Capítulo 16 Conclusão 85

Capítulo 17 Bibliografia 87

Agradecimentos 89

Scheme

6

Introdução

7

II nntt rr oodduuççããoo

Scheme

8

Introdução Uma linguagem de programação não é apenas um meio de indicar a um computador uma série de operações a executar. Uma linguagem de programação é, sobretudo, um meio de exprimirmos ideias acerca de metodologias.

Uma linguagem de programação deve possuir ideias simples, deve ser capaz de combinar ideias simples para formar ideias mais complexas e deve ser capaz de realizar abstracções de ideias complexas para as tornar simples.

Existe uma enorme diversidade de linguagens de programação, umas mais adaptadas a um determinado tipo de processos, outras mais adaptadas a outros. A escolha de uma linguagem de programação deve estar condicionada, naturalmente, pelo tipo de problemas que queremos resolver, mas não deve ser um comprometimento total. Para um programador é muito mais importante compreender os fundamentos e técnicas da programação do que dominar esta ou aquela linguagem.

O Scheme deriva da linguagem Lisp, e por isso herdou a maior parte das características do Lisp. Scheme é uma linguagem dinâmica, cujos programas são constituídos por pequenos módulos, de funcionalidade genérica e que cumprem um objectivo muito simples. É a sua combinação que produz um programa completo. Os módulos desenvolvidos em Scheme possuem, geralmente, uma funcionalidade que ultrapassa largamente os objectivos para que foram concebidos. A não tipificação de dados, a possibili dade de tratar dados e programas de um mesmo modo e a indistinção entre funções definidas pela linguagem e funções definidas pelo programador são algumas das razões da sua flexibili dade.

Scheme dá ao programador a capacidade de estender a linguagem como entender, permitindo incorporar outros estilos de programação, como programação orientada para objectos, programação orientada para regras, etc. Quando surgem novos paradigmas de programação, o Scheme incorpora-os facilmente enquanto as antigas linguagens morrem. Isto permite adaptar a linguagem ao problema que estamos a resolver em vez de termos de adaptar o problema à linguagem que estamos a usar.

Scheme é uma linguagem interactiva. Cada porção de um programa pode ser compilada, corrigida e testada independentemente das restantes. Deste modo, Scheme permite a criação, teste e correcção de programas de uma forma incremental, o que facil ita muito a tarefa do programador.

Quase todos as versões de Scheme possuem simultaneamente um compilador e um interpretador, permitindo misturar livremente código compilado e interpretado e permitindo realizar compilações incrementais.

Breve Introdução Histórica A primeira descrição do Scheme foi escrita em 1975 [Scheme75]. Em 1978 foi feita uma revisão [Scheme78] que descrevia a evolução da linguagem que foi actualizada para suportar um compilador inovador [Rabbit]. Três projectos distintos começaram em 1981 e 1982 que usavam variações do Scheme para cursos na MIT, Yale, e Universidade de

Introdução

9

Indiana [Rees82], [MITScheme], [Scheme311]. Em 1984 foi publicado um livro de ensino de introdução à linguagem Scheme [SICP].

À medida que o Scheme se tornava num dialecto mais difundido, os dialectos locais começaram a divergir até que os estudantes e os investigadores começaram achar difícil entender o código escrito noutros locais. Por isso quinze representantes das principais implementações de Scheme encontraram-se em Outubro de 1984 para em conjunto tentarem criar um Scheme comun.

O relatório desses representantes [RRRS] foi publicado na MIT e na Universidade de Indiana no verão de 1985. As revisões seguintes aconteceram na primavera de 1986 [R3RS], e na primavera de 1988 [R4RS] respectivamente. O relatório actual contém revisões que foram acordadas numa reunião em Xérox PARC em Junho de 1992.

Principais Características do Scheme • As variáveis têm abrangência estática “statically scoped” .

Scheme é uma linguagem de programação com abrangência estática, o que significa que cada utili zação de uma variável está associada com uma atribuição lexicamente aparente dessa variável. Algol é outra linguagem com abrangência estática.

• Os tipos são latentes.

Scheme tem tipos latentes (e não tipos manifestos), o que significa que a Scheme associa tipos com valores (ou objectos) e não com variáveis. Outras linguagens com tipos latentes (também referidas como linguagens com tipos "fracos" ou tipos dinâmicos) são APL, Snobol e outros dialectos de LISP. As linguagens com tipos manifestos (linguagens com tipos "fortes" ou estáticos) incluem Algol 60, Pascal e C.

• Os objectos têm duração ilimitada.

Todos os objectos criados durante um cálculo em Scheme, incluindo procedimentos e continuações, têm duração ili mitada; nenhum objecto de Scheme é jamais destruído. O sistema não fica sem memória porque o colector de lixo “garbage collector“ reclama a memória (o espaço) ocupado por um objecto quando esse objecto já não for de todo necessário a cálculos futuros. Outras linguagens nas quais os objectos têm duração il imitada incluem APL e outros dialectos do LISP.

• Recursividade de cauda <<tail>> apropriada.

Scheme tem recursividade de cauda apropriada, o que significa que cálculos iterativos podem ocorrer em espaço constante, mesmo se esse cálculo iterativo for descrito por um procedimento sintacticamente recursivo. Com uma implementação de recursividade de fim, podemos exprimir iterações usando a mecânica normal de chamada de procedimentos; expressões especiais de iteração são proporcionadas apenas por conveniência sintáctica.

Scheme

10

• As continuações são explícitas.

Na maioria das outras linguagens as continuações operam de forma oculta. No Scheme as continuações são objectos; podemos usar continuações para implementar uma variedade de elementos de controle avançado, incluindo saídas não locais, backtracking e co rotinas.

• Os procedimentos são objectos .

Os procedimentos do Scheme são objectos, o que significa que podem ser criados dinamicamente, poder ser armazenados em estruturas de dados, podem ser retornados como resultado de outros procedimentos, etc. O Common Lisp e o ML são outras linguagens nas quais os procedimentos são objectos.

• Os argumentos são passados por valor.

Os argumentos dos procedimentos em Scheme são passados por valor, o que quer dizer que o Scheme avalia as expressões dos argumentos antes do procedimento ganhar o controlo, quer seja necessário quer não. ML, C e APL são linguagens que também passam os argumentos por valor. Em linguagens como SASL e Algol 60, os argumentos não são avaliados a não ser que os valores sejam necessários pelo procedimento.

Comparação entre o Scheme e o Common Lisp A popularidade do Scheme como a primeira linguagem de programação tem aumentado gradualmente. Scheme foi desenhado com o intuito de ser uma linguagem de instrução (ensino) fácil de aprender, compreender, na qual possam ser aprendidos os conceitos de programação mais importantes. Mas talvez o Scheme seja muito mais que uma linguagem divertida e fácil de usar.

Existem argumentos a favor do Common Lisp. Common Lisp tem mais funções com utili dade que o Scheme. Common Lisp suporta argumentos do tipo chave o que permite uma maior flexibilidade, e facili ta a criação de programas mais sofisticados. Common Lisp permite a criação variáveis de abrangência dinâmica. Os Símbolos << Symbols>> em Common Lisp podem ter associados listas de propriedades e funções e não só valores com no Scheme.

Mas é claro que existem argumentos a favor do Scheme.

O Scheme foi criado com o intuito de ser um Lisp educacional, por isso é mais simples, consistente, elegante, conciso e mais fácil de aprender. Por exemplo o manual de Scheme feito por Guy Steele tem apenas 50 páginas, enquanto que o manual de Common Lisp tem 1000 páginas. Para além de tudo o Scheme necessita menos memória para correr num computador.

Introdução

11

Sistemas Operativos Suportados • Unix

GNU/Linux, *BSD, HP-UX, Ultrix, NeXT e SunOS.

• Windows

Windows 95, Windows 98, Windows ME, Windows NT, Windows 2000 e Windows XP.

• OS/2

Sistema Operativo IBM OS/2 versão 2.1 ou superior.

Livros e Anotações sobre Scheme Existe um grande número de apontamentos, anotações e livros sobre Scheme, aqui ficam alguns exemplos:

• "Scheme: An Interpreter for Extended Lambda Calculus" de Gerald J. Sussman e Guy L. Steele, Jr.

• "Lambda: The Ultimate Imperative" de Guy Lewis Steele, Jr. e Gerald Jay Sussman.

• "Lambda: The Ultimate Declarative"de Guy Lewis Steele, Jr.

• "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO” de Guy Lewis Steele, Jr.

• "The Art of the Interpreter of, the Modularity Complex (Parts Zero, One, and Two)" de Guy Lewis Steele, Jr. e Gerald Jay Sussman.

• "RABBIT: A Compiler for SCHEME" de Guy Lewis Steele, Jr.

• “Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode" de Guy Lewis Steele, Jr. e Gerald Jay Sussman.

• "The Scheme Programming Language, Second Edition" de R. Kent Dybvig.

• "The Scheme Programming Language" de Ken Dickey.

• "First-class Data-type Representations in SchemeXerox" de Adams, Curtis e Spreitzer.

• "Lambda-v-CS: An Extended Lambda-Calculus for Scheme" de Matthias Felleisen.

• "The Revised Report on the Syntactic Theories of Sequential Control and State" de Matthias Felleisen e Hieb.

• "Characterizing the Paralation Model using Dynamic Assignment" de Freeman and Friedman.

Scheme

12

• "Chez Scheme User's Guide" de R. Kent Dybvig.

• “A Denotational Approach to Flow Analysis and Optimization of SCHEME, A Dialect of LISP" de Uwe F. Pleban.

• “The Scheme of things: Streams versus Generators" de William Clinger.

• "Semantics of Scheme" de William Clinger.

Instalação

13

II nnssttaallaaççããoo

Scheme

14

Instalação O objectivo deste capítulo é mostrar como instalar e usar o Scheme nos sistemas operativos suportados. O programa usado foi o MIT Scheme release 7.7.

Será dada informação sobre, as opções a usar na linha de comandos e sobre as variáveis de ambiente que controlam o funcionamento do Scheme. Como usar o editor, como compilar e fazer o debug das aplicações também serão pontos a abordar.

Instalação em Windo ws Para instalar o MIT Scheme numa maquina basta executar o ficheiro scheme-7.7.1-ix86-win32.exe e seguir as instruções de instalação.

Para remover o software é necessário ir ao “Painel de Controlo” depois entrar em “Adicionar/remover programas” e por fim clicar em “MIT Scheme 7.7” .

Instalação em Unix Irá ser usado como exemplo a instalação para GNU/Linux. A instalação para outros sistemas em Unix é similar.

O MIT Scheme e distribuído num ficheiro tar comprimido. Este ficheiro contém dois directórios, um bin e outro lib. O directório bin contém dois ficheiros executáveis, o scheme e o bchscheme. O directório lib contém um sub-directório lib/mit-scheme, que é o directório usado pelo Scheme quando está a correr.

A localização aconselhável para instalar o programa é em /usr/local. No entanto pode ser instalado noutra localização à escolha do utili zador.

Para instalar o programa em /usr/local é necessário seguir os passos seguintes: cd /u sr/l oca l

r m - f bin / sch eme bin / bch sch eme

r m - r f li b/mi t - scheme

gzip - cd sc heme- 7. 7.1 - i x86- gnu- l i nux . tar . gz | t ar x vf -

Depois de executar estes comandos os ficheiros executáveis vão estar em /usr/local/bin e as librarias em /usr/local/lib/mit-scheme. Não é necessária mais nenhuma configuração.

Para instalar o programa numa localização à escolha é necessário seguir os passos seguintes:

• Descompactar o ficheiro mkdir tem p

cd tem p

gzip –cd sc heme- 7. 7.1 - i x86- gnu- l i nux . tar . gz | t ar x vf -

• Mover o conteúdo do directório bin para um directório à escolha que esteja no caminho de execução (execution path). Por exemplo se existir o directório ~/bin o comando a executar seria o seguinte:

Instalação

15

mv bi n/* ~/b i n/.

• Mover ou copiar o directório mit-scheme para o directório à escolha. Por exemplo move-lo para o directório principal (home directory). mv li b/mi t - scheme ~/ .

Caso a drive onde queremos colocar o directório mit-scheme seja diferente da drive onde foi descompactada a distribuição ter-se-ia que usar o comando cp –pr em vez do mv. De seguida é necessário ‘dizer’ ao Scheme onde pode encontrar o directório mit-scheme, existem duas formas de o fazer:

• Colocar num dos ficheiros de arranque das shells (shells init files), por exemplo na .bashrc, o comando: expor t MITSCHEME_LIB RARY_PATH=~/mi t - scheme

• Usar o argumento -library ~/mit-scheme quando se arranca o Scheme: scheme - l i bra r y ~ / mi t - scheme

Instalação em OS/2 Depois de se descompactar o ficheiro os2.zip irão aparecer os seguintes directórios:

• Exe: contém os ficheiros executáveis scheme.exe e bchschem.exe.

• Dll : contém as dlls blowfish.dll, gdbm.dll e md5.dll .

• Doc: contém documentação em HTML.

• Lib: contém os ficheiros (librarias) necessários ao Scheme para correr.

De seguida é necessário seguir os seguintes passos:

1. Mover os ficheiros executáveis ‘scheme. exe’ and ‘bchsch em. exe’ do directório ‘exe’ para outro que conste na variável de ambiente PATH. Em alternativa também se pode adicionar o directório 'exe' á PATH, para tal basta editar o ‘conf ig . sys ’ e reiniciar o computador.

2. Mover as dll’s do directório ‘dl l ’ para um directório que esteja na variável de ambiente LI BPATH, como no ponto 1, também se pode adicionar o directório ‘dl l ’ à LI BPATH.

3. O directório ‘ l i b’ pode ser colocado em qualquer parte. Depois basta inserir a variável de ambiente MI TSCHEME_LIB RARY_PATH no ‘conf ig . sys ’ e atribuir-lhe o caminho onde se encontra o directório ‘ l i b’ .

Por exemplo, se o directório ‘ l i b’ estivesse no caminho ‘c: \ scheme\ l i b’ , tinha-se que adicionar ao ‘conf ig . sys ’ a seguinte linha:

SET MI TSCHEME_LI BRARY_PATH=C: \ SCHEME\ LI B

É possível sobrepor o valor da variável MI TSCHEME_LIB RARY_PATH com a opção –l i br ar y , quando se arranca o Scheme, basta fazer o seguinte:

scheme – l i bra r y d : \ myl i b

Scheme

16

Se se usar a opção - l i br ar y, não é necessário ter a variável de ambiente MI TSCHEME_LIB RARY_PATH definida.

Variáveis de Ambiente Existem algumas variáveis de ambientes que podem ser úteis e que convém identificar:

• MI TSCHEME_LIB RARY_PATH: diz ao Scheme onde estão as librarias e ficheiros de informação. Esta a única variável de ambiente necessária, excepto se se utili zar o opção –l i br ar y quando arrancamos o Scheme.

SET MITSCHEME_LIBRARY_PATH=C:\SCHEME\LIB

• MI TSCHEME_I NF_DI RECTORY: diz ao Scheme onde está a informação de debug, por defeito esta variável é o subdirectório ‘sr c ’ que está no directório ‘ l i b’ .

SET MITSCHEME_INF_DIRECTORY=C:\SCHEME\LIB\SRC

• TMPDIR : diz ao Scheme qual a directório onde pode colocar os ficheiros temporários.

SET TMPDIR=C:\TMP

• USER: diz ao Scheme o nome do utili zador. Esta opção serve para vários fins, inclusive para saber o nome que será usado no endereço de e-mail .

SET USER=henrique

• HOME: diz ao Scheme qual é o directório HOME. É neste directório procura por ficheiros de inicialização, é também para este directório que são expandidos os ficheiros com prefixo ‘~/ ’ (ou ‘~\ \ ’) . Se a variável HOME não for especificada o Scheme usa o raiz do disco da drive actual.

SET HOME=C:\CP

O Editor do Scheme

17

OO EEddii ttoorr ddoo SScchheemmee

Scheme

18

O Editor do Scheme Em Unix o interpretador é frequentemente instalado como ‘ /usr/local/bin/scheme’ nas máquinas em que é disponibilizado. Se se adicionar ‘ /usr/local/bin’ ao caminho de busca (search path) da shell do Unix torna-se possível iniciá-lo digitando : Scheme

Para iniciar o interpretador em ambiente Windows basta clicar com o rato no icon que se encontra no caminho: Iniciar->Programas->MIT Scheme->Scheme.

Quando se inicia o interpretador este imprime uma mensagem de boas vindas, informando a sua versão e uma nota legal de copyright antes de oferecer o primeiro prompt, ex.:

Em Scheme, qualquer expressão tem um valor. Este conceito é de tal modo importante que todas as implementações da linguagem Scheme apresentam um avaliador, i.e., um pequeno programa destinado a interagir com o utilizador de modo a avaliar expressões por este fornecidas. Assim, quando o utilizador começa a trabalhar com o Scheme, é-lhe apresentado um sinal e o Scheme fica à espera que o utilizador lhe forneça uma expressão:

]=>

O carácter “ ]=>” é a “prompt” do Scheme, à frente da qual vão aparecer as expressões que o utilizador escrever. O Scheme interage com o util izador executando um ciclo em que lê uma expressão, determina o seu valor e escreve o resultado. Este ciclo de acções designa-se, tradicionalmente, de ciclo read-eval-print (REPL).

Quando o Scheme lê uma expressão, constrói internamente um objecto que a representa. Esse é o papel da fase de leitura. Na fase de avaliação, o objecto construído é analisado de modo a produzir um valor. Esta análise é feita empregando as regras da linguagem que determinam, para cada caso, qual o valor do objecto construído. Finalmente, o valor

O Editor do Scheme

19

produzido é apresentado ao utilizador na fase de escrita através de uma representação textual desse valor.

Dada a existência do ciclo read-eval-print, em Scheme não é necessário instruir o computador a escrever explicitamente os resultados de um cálculo como, por exemplo, em Pascal. Isto permite que o teste e correcção de erros seja bastante facili tada. A vantagem de Scheme ser uma linguagem interactiva está na rapidez com que se desenvolvem protótipos de programas, escrevendo, testando e corrigindo pequenas funções de cada vez.

O número que fica por detrás dos caracteres da “prompt” “ ]=>” designa-se por número de nível. Este número é incrementado em certas circunstâncias, a mais comuns é quando é gerado um erro. Como exemplo podemos tentar digitar a palavra “ isep” na prompt do editor do Scheme e ver o que acontece:

1 ]=> ise p

; Unbound var i able : is ep

; To c onti nue, ca l l R ESTART wit h an opt i on num ber:

; (RE START 3) => Spe cif y a val ue t o us e i nste ad o f f oo.

; (RE START 2) => Def i ne foo to a gi ven va l ue.

; (RE START 1) => Ret urn to r ead- eval - pr int lev el 1.

2 err or>

Neste caso o número de nível foi incrementado para 2, o que indica que um novo ciclo read-eval-print (REPL) foi iniciado. A própria string de “prompt” foi alterada para “error” para lembrar que um novo REPL foi iniciado devido a um erro. O REPL original continua a existir, estando a espera que se torne para ele, para voltar ao REPL original basta digital (restart 1) ou usar a combinação de teclas ctl-g.

2 err or> ( re star t 1)

; Abor t !

1 ]=>

Para sair do editor do Scheme basta usar o comando (exit).

Carregar Ficheiros O Scheme permite carregar ficheiros que contenham código, para tal usa-se o procedimento l oad. A sintaxe do procedimento l oad é a seguinte:

load filename [environment [ syntax-table [purify?]]]

• filename pode ser uma string com o nome do ficheiro ou poder ser uma lista de string com os nomes de vários ficheiros.

• environment é uma parâmetro opcional que indica em que ambiente se deve avaliar o ficheiro, se esta variável não for preenchida e usado o ambiente do REPL actual.

• syntax-table esta opção já não é usada e se vier preenchida é ignorada.

Scheme

20

• O parâmetro opcional purify? é um boleano que diz se se deve ou não, colocar o conteúdo do ficheiro no espaço das constantes, depois de conteúdo ser carregado mas antes de ser avaliado.

Imagine-se existia um ficheiro “meucod.scm” na raiz do disco “C:” , e que nesse ficheiro existia uma procedimento com o nome teste. Para carregar esse ficheiro fazia-se o seguinte:

> (lo ad “ c:/ meuc od”)

; Load i ng “ meucod . scm” – done

; Valu e: t est e

Se o ficheiro a carregar tiver a extensão “ .com ou .scm” (como era o caso anterior), a extensão do ficheiro quando se chama o procedimento l oad pode ser omitida, caso contrário tem que ser colocada:

> (lo ad “ c:/ meuc od.t xt” )

Compilar os Programas Para o Scheme estar preparado para receber comandos de compilação e necessário inicial o Scheme com a opção –compil er assim na linha de comando teríamos que escrever: Scheme – compi ler

Agora o Sheme está preparado para receber os comandos de compilação. O procedimento usado para compilar ficheiros é o cf . A sua sintaxe é a seguinte:

cf nome_ficheiro [destino]

Sendo nome_ficheiro o nome do ficheiro a compilar e sendo destino o caminho onde queremos colocar os ficheiros compilados. Caso o parâmetro destino não venha preenchido os ficheiros de compilação irão ser gerados no sítio onde está o ficheiro a compilar.

Para compilar o ficheiro “meucod.scm” do exemplo anterior teria que se fazer o seguinte: > (cf “c: / meucod ” )

…

; Dumpi ng “ meucod . com” – done

O cf compilou o ficheiro “meucod.scm” e gerou o ficheiro “meucod.com” (por “deficiência” do compilador também são gerados os ficheiros “meucod.bin” , “meucod.bci” e possivelmente o “meucod.ext” ).

Agora em vez de carregarmos o ficheiro “meucod.scm” podemos carregar “meucod.com” pois como o ficheiro já está compilado é muito mais rápido e eficiente.

> (lo ad “ c:/ meuc od”)

; Load i ng “ meucod . com” – done

; Valu e: t est e

Para gerar noutro directório o ficheiro compilado bastava: > (cf “c: / meucod ” “c : /t emp/ ” )

O Editor do Scheme

21

…

; Dumpi ng “ meucod . com” – done

Assim o ficheiro “meucod.scm” é colocado em “c:\temp\meucod.com” .

Se o caminho destino não for um directório então o ficheiro copilado é gerado com esse nome:

> (cf “c: / meucod ” “c : /t emp”)

…

; Dumpi ng “ te mp.c om” – done

Agora teríamos na raiz do disco “C:” o ficheiro “ temp.com” .

Scheme

22

Elementos da linguagem

23

EElleemmeennttooss ddaa LL iinngguuaaggeemm

Scheme

24

Elementos da Lingu agem Qualquer linguagem de programação lida com duas espécies de objectos: dados e procedimentos. Os dados são os objectos que pretendemos manipular. Os procedimentos são descrições das regras para manipular esses dados.

Se considerarmos a linguagem da matemática, podemos identificar os números como dados e as operações algébricas como procedimentos e podemos combinar os números entre si usando aquelas operações. Por exemplo, 2 × 2 é uma combinação, tal como 2 × 2 × 2 e 2 × 2 × 2 × 2. No entanto, a menos que pretendamos ficar eternamente a resolver problemas de aritmética elementar, somos obrigados a considerar operações mais elaboradas que representam padrões de cálculos. Neste último exemplo, é evidente que o padrão que está a emergir é o da operação de potenciação, i.e, multiplicação sucessiva, tendo esta operação sido definida na matemática há já muito tempo.

Tal como a linguagem da matemática, uma linguagem de programação deve possuir dados e procedimentos primitivos, deve ser capaz de combinar quer os dados quer os procedimentos para produzir dados e procedimentos mais complexos e deve ser capaz de abstrair padrões de cálculo de modo a permitir tratá-los como operações simples, definindo novas operações que representem esses padrões de cálculo.

Maiúsculas e Minusculas Scheme não destingue letras maiúsculas e minúsculas excepto em caracteres que representam constantes, nas outras palavras o Scheme é (case-insensitive) por exemplo, ‘ Isep’ é o mesmo identificador que ‘ ISEP’ , e ‘#x1AB’ é o mesmo número que ‘#X1ab’ , mas ‘#\a’ e ‘#\A’ são diferentes caracteres.

Linhas de Comentário Para comentar uma linha é usado o caracter ponto e vírgula ‘ ;’ . Para comentar um bloco de informação usam-se: os caracteres ‘#|’ para marcar o início do bloco a comentar, e os caracteres ‘ |#’ para indicar os fim do comentário.

; Comentár i o

; à Li nha

#! Comentá r io

. . .

em

. . .

bl oco #!

Elementos Primitivos Elementos primitivos são as entidades mais simples com que a linguagem lida. Um número, por exemplo, é um dado primitivo.

Elementos da linguagem

25

Como foi dito anteriormente, o Scheme executa um ciclo read-eval-print. Isto implica que tudo o que escrevemos no Scheme tem de ser avaliado, i.e., tem de ter um valor, valor esse que o Scheme escreve no ecrãn.

Assim, se dermos um número ao avaliador, ele devolve-nos o valor desse número. Quanto vale um número? O melhor que podemos dizer é que ele vale aquilo que vale. Por exemplo, o número 1 vale 1.

> 1

1

> 123 45

12345

> 4.5

4. 5

Como se pode observar os números podem ser inteiros ou reais.

Combinações Combinações são entidades complexas feitas a partir de entidades mais simples. Por exemplo, na matemáticas os números podem ser combinados usando operações como a soma ou o produto. Como exemplo de combinações matemáticas, temos 1 + 2 e 1 + 2 * 3. A soma e o produto de números são exemplos de operações extremamente elementares consideradas procedimentos primitivos.

Em Scheme, criam-se combinação escrevendo uma sequência de expressões entre um par de parênteses. Uma expressão é um elemento primitivo ou uma outra combinação. A expressão ( + 1 2 ) é uma combinação dos elementos primitivos 1 e 2 através do procedimento +. Já no caso ( + 1 (* 2 3) ) a combinação ocorre entre 1 e ( * 2 3) , sendo esta última expressão uma outra combinação.

Não é difícil de ver que as únicas combinações com utili dade são aquelas em que as expressões correspondem a operadores e operandos. Por convenção, o Scheme considera que o primeiro elemento de uma combinação é um operador e os restantes são os operandos.

A notação que o Scheme utili za para construir expressões (operador primeiro e operandos a seguir) é designada por notação prefixa. Esta notação costuma causar alguma perplexidade a quem inicia o estudo da linguagem, que espera uma notação mais próxima da que aprendeu em aritmética e que é usada habitualmente nas outras linguagens de programação. Nestas, a expressão ( + 1 (* 2 3) ) é usualmente escrita na forma 1 + 2 *

3 (designada notação infixa) que, normalmente, é mais simples de ler por um ser humano. No entanto, a notação prefixa usada pelo Scheme tem largas vantagens sobre a notação infixa:

• É muito fácil usar operadores que têm um número variável de argumentos, como por exemplo: > (+ 1 2 3)

6

Scheme

26

> (+ 1 2 3 4 5 6 7 8 9 10)

55

Numa linguagem do tipo Pascal apenas existem operadores unários ou binários, e é necessário explicitar os operador binários entre cada dois operandos: 1+2+3 ou 1+2+3+4+5+6+7+8+9+10. Um operador deste tipo diz-se infixo (in significa entre). Se se pretender um operador ternário (ou outro) já não se consegue escrever do mesmo modo, sendo necessário implementá-lo como uma função.

• Não existe precedência entre os operadores. Em Pascal, a expressão 1+2* 3 tem de ser calculada como se se tivesse escrito 1+( 2*3 ) , e não ( 1+2) * 3, i.e., foi criada uma precedência que elimina as ambiguidades. Essa precedência pode ser alterada através do emprego de parênteses. Em Scheme, as expressões seriam necessariamente distintas, ( + 1 (* 2 3)) ou ( * ( + 1 2) 3) , não podendo haver qualquer ambiguidade.

• Os operadores que nós definimos usam-se exactamente da mesma maneira que os operadores da linguagem: operador primeiro e operandos a seguir. Em Pascal, os operadores são infixos, i.e., estão entre os operandos, e as funções e procedimentos por nós definidos são prefixos, i.e., primeiro a função ou procedimento e depois os operandos. Isto impede a extensão da linguagem de uma forma coerente.

Para exempli ficar este último aspecto, consideremos a operação de exponenciação em Pascal. Para ser coerente com o resto da linguagem, deveria existir um operador, por exemplo * * que permitisse escrever 3* * 4 para indicar a quarta potência de 3. Como esse operador não existe na linguagem (standard), somos obrigados a criar uma função que o substitua mas, neste caso, a sintaxe muda radicalmente. Esta função, como se usa de forma prefixa não se pode tornar coerente com as restantes operações do Pascal, como a soma e a multiplicação. Em Scheme, pelo contrário, tanto podemos escrever ( * 3 3 3 3) como definir uma função que permita escrever ( * * 3 4) .

A desvantagem da notação prefixa está na escrita de combinações complexas. A expressão Pascal 1+2* 3- 4/ 5* 6, equivale à expressão Scheme ( - ( + 1 (* 2 3)) ( * ( / 4

5) 6) ) que embora seja mais simples de ler para uma máquina, pode ser mais difícil de ler para um ser humano devido à acumulação de parênteses. No entanto, esta expressão pode ser escrita de forma mais clara usando indentação.

A regra para indentação de combinações Scheme é extremamente simples. Numa linha coloca-se o operador e o primeiro operando. Os restantes operandos vêm alinhados por debaixo do primeiro.

( - ( + 1

(* 2 3) )

(* (/ 4 5)

6))

Quando a regra de indentação não é suficiente, usam-se pequenas variações, como seja colocar o operador numa linha e os operandos por debaixo, por exemplo:

Elementos da linguagem

27

( umaopera caocomumnomemui tog r ande

1 2 3 4)

A indentação é fundamental em Scheme pois é muito fácil escrever código complexo. A grande maioria dos editores preparados para Scheme (Emacs, por exemplo) formatam automaticamente os programas à medida que os escrevemos e mostram o emparelhamento de parênteses. Desta forma, após algum tempo de prática, torna-se muito fácil escrever e ler os programas, por mais complexa que possa parecer a sua estrutura.

Avaliação de Combinações Como já vimos, o Scheme considera que o primeiro elemento de uma combinação é um operador e os restantes são os operandos.

O avaliador determina o valor de uma combinação como o resultado de aplicar o procedimento especificado pelo operador ao valor dos operandos. O valor de cada operando é designado de argumento do procedimento. Assim, o valor da combinação ( +

1 ( * 2 3) ) é o resultado de somar o valor de 1 com o valor de ( * 2 3) . Como já se viu, 1 vale 1 e ( * 2 3 ) é uma combinação cujo valor é o resultado de multiplicar o valor de 2 pelo valor de 3, o que dá 6, e que somado a 1 dá 7.

> (+ 1 2)

3

> (+ 1 (* 2 3))

7

Tipos de Dados Qualquer objecto satisfaz pelo menos um dos seguinte predicados:

bit-string?

environment?

port?

symbol?

boolean?

null?

procedure?

vector?

cell?

number?

promise?

weak-pair?

char?

Scheme

28

pair?

string?

condition? > (nu mber ? 1)

#t

>( number? “o l a”)

( )

Definição de Funções Tal como em matemática, pode-se definir numa linguagem de programação a operação de elevar um número ao quadrado. Assim, se pretendermos determinar o produto de um número por ele próprio, escrevemos a combinação ( * x x) sendo x o número, i.e.

> (* 5 5)

25

> (* 6 6)

36

Os números 5 e 6 e a operação * são elementos primitivos. As expressões ( * 5 5) e ( * 6 6) são combinações. À combinação genérica ( * x x) queremos associar um nome, por exemplo, quadrado. Isso equivale a acrescentar uma nova função à linguagem.

Para usar funções é necessário usar a expressão lambda.

Uma lambda é uma função que não está associada a nenhum símbolo. Pode ser vista como uma função sem nome. A sintaxe é: lambda <parâmetros> <corpo>.

A título de exemplo, vamos construir uma função que acha o quadrado de um numero: > (la mbda (x )

( * x x))

a pro cedu r e

> ((l ambda ( x)

( * x x)) 3)

9

Para se usarem funções em Scheme, é necessário criar uma combinação de quatro elementos. O primeiro elemento desta combinação é a palavra l ambda, que informa o avaliador que estamos perante uma função. O segundo elemento é uma combinação com os parâmetros da função e o terceiro elemento é a combinação que determina o valor da função para aqueles parâmetros.

Para se definir uma função com um determinado nome para se poder usar um qualquer parte do código teremos que fazer o seguinte:

> (de f ine qu adra do

( l ambda ( x)

Elementos da linguagem

29

( * x x)))

quadr ado

Quando se dá uma expressão desta forma ao avaliador, ele acrescenta a função ao conjunto de funções da linguagem, associando-a ao nome que lhe demos e devolve como valor da definição o nome da função definida.

A definição da função quadr ado diz que para se determinar o quadrado de um número x , devemos multiplicar esse número por ele próprio ( * x x) . Esta definição associa a palavra quadra do a um procedimento. Este procedimento possui parâmetros e um corpo de expressões. De forma genérica temos:

(define nome (lambda (parâmetro-1 ...parâmetro-n) corpo))

Os parâmetros de um procedimento são designados parâmetros formais e são os nomes usados no corpo de expressões para nos referirmos aos argumentos correspondentes. Quando escrevemos no avaliador de Scheme ( quadr ado 5 ) , 5 é o argumento. Durante o cálculo da função este argumento está associado ao parâmetro formal x . Os argumentos de uma função são também designados parâmetros actuais.

> (qu adra do 5)

25

> (qu adra do 6)

36

Note-se que a regra de avaliação de combinações é também válida para as funções por nós definidas. Assim, a avaliação da expressão ( quadr ado ( + 1 2) ) passa pela avaliação do operando ( + 1 2 ) . Este operando tem como valor 3, valor esse que é usado pela função no lugar do parâmetro x . O corpo da função é então avaliado, i.e., o valor final será o da combinação ( * 3 3) .

O seguinte exemplo mostra um caso um pouco mais complexo. Nele estão apresentadas as etapas de avaliação dos operandos e de avaliação do corpo da função.

>( quadr ado (qu adr ado ( + 1 2) ) )

81

>( quadrad o ( quad r ado 3) )

81

>( quadrad o ( * 3 3))

81

>( quadrad o 9)

81

>( * 9 9)

81

A definição de funções permite-nos associar um procedimento a um nome. Isto implica que o Scheme tem de possuir uma memória onde possa guardar o procedimento e a sua associação ao nome dado. Esta memória do Scheme designa-se ambiente.

Scheme

30

Note-se que este ambiente apenas existe enquanto estamos a trabalhar com a linguagem. Quando terminamos, perde-se todo o ambiente. Isto implica que, se não queremos perder o trabalho que estivemos a escrever, devemos escrever as funções num ficheiro e ir passando-as para o Scheme. A grande maioria das implementações do Scheme permite fazer isto de forma automática.

Símbolos A definição de funções em Scheme passa pela utilização dos seus nomes. Nomes para as funções e nomes para os parâmetros das funções.

Uma vez que o Scheme, antes de avaliar qualquer expressão, tem de a ler e converter internamente para um objecto, os nomes que criamos têm de ter um objecto associado. Esse objecto é designado por símbolo. Um símbolo é, pois, a representação interna de um nome.

Em Scheme, quase não existem limitações para a escrita de nomes. Um nome como quadra do é tão bom como + ou como 1+2* 3 pois o que separa um nome dos outros elementos de uma combinação são apenas parênteses e espaços em branco. Por exemplo, é perfeitamente correcto definir e usar a seguinte função:

> (de f ine x+ y*z

( lam bda (x y z)

( + (* y z) x) ))

x+y*z

> (x+ y*z 1 2 3)

7

Scheme atribui um significado muito especial aos símbolos. Reparemos que, quando definimos uma função, os parâmetros formais da função são símbolos. O nome da função também é um símbolo. Quando escrevemos uma combinação, o avaliador de Scheme usa a definição de função que foi associada ao símbolo que constitui o primeiro elemento da combinação. Quando, no corpo de uma função, usamos um símbolo para nos referimos a um parâmetro formal, esse símbolo tem como valor o respectivo parâmetro actual que lhe foi associado naquela combinação. Por esta descrição se vê que os símbolos constituem um dos elementos fundamentais da linguagem Scheme.

Expressões Condicionais

31

EExxpprr eessssõõeess CCoonnddiicciioonnaaiiss

Scheme

32

Expressões Cond icionais Existem muitas operações cujo resultado depende da realização de um determinado teste. Por exemplo, a função matemática abs (que calcula o valor absoluto de um número) equivale ao próprio número, se este é positivo, ou equivale ao seu simétrico se for negativo. Estas expressões, cujo valor depende de um ou mais testes a realizar previamente, permitindo escolher vias diferentes para a obtenção do resultado, são designadas expressões condicionais.

No caso mais simples de uma expressão condicional, existem apenas duas alternativas a seguir. Isto implica que o teste que é necessário realizar para determinar a via de cálculo a seguir deve produzir um de dois valores, em que cada valor designa uma das vias.

Seguindo o mesmo raciocínio, uma expressão condicional com mais de duas alternativas deverá implicar um teste com igual número de possíveis resultados. Uma expressão da forma “caso o valor do teste seja 1, 2 ou 3, o valor da expressão é 10, 20 ou 30, respectivamente” é um exemplo desta categoria de expressões que, embora seja considerada pouco intuitiva, existe nalgumas linguagens (Basic, por exemplo). Contudo, estas expressões podem ser facilmente reduzidas à primeira. Basta decompor a expressão condicional múltipla numa composição de expressões condicionais simples, em que o teste original é também decomposto numa série de testes simples. Assim, poderíamos transformar o exemplo anterior em: “se o valor do teste é 1, o resultado é 10, caso contrário, se o valor é 2, o resultado é 20, caso contrário é 30” .

Predicados Desta forma, reduzimos todos os testes a expressões cujo valor pode ser apenas um de dois, e a expressão condicional assume a forma de “se ...então ...caso contrário ...” . Nesta situação, a função usada como teste é denominada predicado e o valor do teste é interpretado como sendo verdadeiro ou falso. Nesta óptica, o facto de se considerar o valor como verdadeiro ou falso não implica que o valor seja de um tipo de dados especial, como o booleano ou lógico de algumas linguagens (como o Pascal), mas apenas que a expressão condicional considera alguns dos valores como representando o verdadeiro e os restantes como o falso.

Em Scheme, as expressões condicionais consideram como falso os valores () <<vazio>> ou #f. Qualquer outro valor diferente de #f é considerado como verdadeiro. Assim, do ponto de vista de uma expressão condicional, qualquer número é um valor verdadeiro. Contudo, não faz muito sentido para o utilizador humano considerar um número como verdadeiro ou falso, pelo que se introduziu uma constante na linguagem para representar verdade. Essa constante representa-se por #t.

Note-se que, se #t é diferente de ( ) , e diferente de #f e se ( ) e #f são os únicos valores que representam a falsidade, então #t representa verdade. Desta forma, existem muitos predicados em Scheme cujo valor é #t quando a expressão por eles designada é considerada verdadeira.

> (> 4 3)

#t

Expressões Condicionais

33

> (< 4 3)

( )

> (< 4 (+ 2 2))

( )

> (= 4 (+ 2 2))

#t

> #f

( )

> #t

#t

Apesar da adopção dos símbolos #t, #f,( ) , convém alertar que nem todos os predicados devolvem #t, #f,( ) exclusivamente. Alguns há que, quando querem indicar verdade, devolvem valores diferentes de #t.

Operadores Lógicos Para se poder combinar expressões lógicas entre si existem os operadores and, or e not . O and e o or recebem qualquer número de argumentos. O not só recebe um. O valor das combinações que empregam estes operadores lógicos é determinado do seguinte modo:

• O and avalia os seus argumentos da esquerda para a direita até que um deles seja falso, devolvendo este valor. Se nenhum for falso o and devolve o valor do último argumento.

• O or avalia os seus argumentos da esquerda para a direita até que um deles seja verdade, devolvendo este valor. Se nenhum for verdade o or devolve o valor do último argumento.

• O not avalia para verdade se o seu argumento for falso e para falso em caso contrário.

Note-se que embora o significado de falso seja claro pois corresponde necessariamente ao valor ( ) ou #f , o significado de verdade já não é tão claro pois, desde que seja diferente de ( ) ou #f , é considerado verdade.

> and (or (> 2 3) (n ot ( = 2 3) ) ) ( < 2 3))

#t

> (or () ( ) 1)

1

>( and #f 3 4)

( )

>( and 1 2 3)

3

>( or 1 2 3)

Scheme

34

1

> (no t () )

#t

Selecção Simples O i f é a expressão condicional mais simples do Scheme. O i f determina a via a seguir em função do valor de uma expressão lógica. A sintaxe do i f é:

(if condição consequente alternativa)

Para o i f , a condição é o primeiro argumento, o consequente no caso de a condição ser verdade é o segundo argumento e a alternativa no caso de ser falso é o terceiro argumento.

> (if (> 4 3)

5

6)

5

Uma expressão i f é avaliada determinando o valor da condição. Se ela for verdade, é avaliado o consequente. Se ela for falsa é avaliada a alternativa.

Selecção Múltipla Para além do i f , existem outras expressões condicionais em Scheme. O cond é uma versão mais potente que o i f . A sua sintaxe é:

(cond (condição-1 expressão-1)

(condição-2 expressão-2)

(condição-n expressão-n))

Designa-se o par ( condiç ão- i expr es são- i ) por cláusula. O cond testa cada uma das condições em sequência, e quando uma delas avalia para verdade, é devolvido o valor da expressão correspondente, terminando a avaliação. Um exemplo será:

> (co nd ( ( > 4 3) 5)

( #t 6))

5

O cond permite uma análise de casos mais simples do que o i f . > (de f ine te ste

( lam bda( x y z w )

(co nd ( (> x y) z)

( ( < ( + x w) ( * y z)) x)

(( = w z) ( + x y))

( #t 777 ) )) )

Expressões Condicionais

35

t este

> (te ste 1 2 3 4)

1

A função equivalente usando i f seria mais complicada. > (de f ine te ste

(l ambda ( x y z w)

( i f ( > x y)

z

( i f ( < (+ x w) ( * y z))

x

( i f ( = w z)

(+ x y)

777)) ) ))

t este

>( tes t e 1 2 3 4)

1

Formas Especiais Dada a semelhança entre o i f e o cond é lícito perguntar se precisaremos dos dois. Será que não é possível definir um em termos do outro ?

A seguinte definição parece ser uma resposta: > (de f ine ii f

( l ambda ( condica o co nse quen t e alte r nat i va )

( cond (co ndi cao cons equente )

( #t a l ter nat i va ) ) ))

i i f

> (ii f (> 4 3) 5 6)

5

> (ii f (> 3 4) 5 6)

6

Quando testamos o i i f , tudo parece bem. No entanto, se escrevermos um exemplo ligeiramente diferente, algo corre mal.

> (de f ine di vide

( l ambda d i vi de ( x y)

( i i f ( = 0 y)

0

( / x y))) )

di vid e

> (di vide 2 0)

Scheme

36

Di vis i on by zero sig nal l ed by / .

O que é que está a acontecer? Tentemos seguir as regras do avaliador para explicar a situação.

A avaliação de combinações implica a aplicação da função (que é o primeiro elemento da combinação) aos valores dos restantes elementos. No exemplo (divide 2 0), a aplicação da função divide ao valor de 2 e 0 é o valor da combinação ( i i f ( = 0 0) 0 ( / 2 0 ) ) , que é a aplicação da função i i f ao valor de ( = 0 0) que é #t , 0 que vale 0 e ( / 2 0 ) que é um erro pois não se pode dividir 2 por 0.

Desta forma, a função i i f avalia o seu último argumento cedo demais, não esperando pelo valor de ( = 0 0) para saber se pode avaliar ( / 2 0) .

Mas há situações piores. Consideremos a seguinte definição e aplicação da função factorial.

> (de f ine me u- f act

( l ambda ( n)

( i if ( = 0 n)

1

( * n ( meu- f act ( - n 1) ) ))) )

meu- f act

> (me u- f act 4)

Abort i ng! : maxim um r ecu r sio n depth exc eeded

Nesta situação, a avaliação de combinações implica a aplicação da função que é o primeiro elemento da combinação aos valores dos restantes elementos. No exemplo ( meu- f act 4 ) , a aplicação da função meu- f act ao valor de 4 é o valor da combinação ( i i f ( = 0 4) 1 (* 4 ( meu- f act ( - 4 1 ) )) ) , que é a aplicação da função i i f ao valor de ( = 0 4) que é ( ) , 1 que vale 1 e ( meu- f act 3 ) que é a aplicação da função meu- f act ao valor 3, que é o valor da combinação...

Desta forma, a função i i f não chega sequer a completar a avaliação dos seus argumentos, não podendo determinar qual dos valores, consequente ou alternativa, retornar, repetindo indefinidamente a aplicação da função meu- f act a argumentos sucessivamente decrescentes.

Suponhamos agora a seguinte interacção com o Scheme: > (if (> 4 3)

100

( i nex i st ente ) )

100

Segundo o modelo de avaliação que tínhamos apresentado, uma combinação é avaliada aplicando o procedimento que o primeiro elemento da combinação especifica ao valor dos restantes elementos. Nesta óptica, antes de se escolher a opção a seguir, o avaliador deveria avaliar todas elas, i.e., 100 cujo valor é 100 e a aplicação da função i nexis t ent e que devia produzir um erro pois a função ainda não foi definida. Porque será que quando testamos isto não é produzido nenhum erro?

Expressões Condicionais

37

É evidente que, de algum modo, o i f não seguiu as regras do modelo de avaliação de combinações, caso contrário, teria mesmo produzido um erro. Isto sugere que i f não é uma função normal mas sim algo que possui a sua própria regra de avaliação.

Uma forma especial é uma expressão da linguagem que possui a sua própria sintaxe e a sua própria regra de avaliação. É de salientar que uma forma especial não é uma função. Ela faz parte da estrutura do avaliador e não do seu ambiente.

O def i ne, o l ambda, o i f e o cond são algumas das formas especiais. Mas o and e o or também são, pois só avaliam os operandos que forem necessários para determinar o resultado. O and pára de avaliar quando um deles produzir falso, o or quando um deles produzir verdade.

Como uma forma especial possui a sua própria regra de avaliação, nem tudo o que se faz com uma função se pode fazer com uma forma especial, e nem tudo o que se faz com uma forma especial se pode fazer com uma função.

Ao contrário das outras linguagens que possuem muitas formas especiais, Scheme tem muito poucas. Desta forma, a linguagem possui uma regra de avaliação muito simples e muito bem definida, e em que as pequenas excepções são implementadas pelas formas especiais.

No entanto, e ao contrário do que acontece na maioria das outras linguagens, Scheme permite ao utili zador definir novas formas cujo comportamento é semelhante ao das formas especiais. Isso é feito através de macros, que são formas que são transformadas noutras formas (especiais ou não) durante a interpretação ou a compilação.

Outras Expressões Condicionais O case é outra expressão condicional presente no Scheme. A sua sintaxe é a seguinte:

case chave clausula clausula ...

Cada clausula tem a seguinte forma:

((objecto ...) expressão expressão ...)

A última clausula pode ser uma clausula senão <<clausula else>> e tem a seguinte forma:

(else expression expression ...)

Uma expressão case funciona da seguinte forma:

O case avalia a chave e compara o valor com cada objecto. Se o resultado dessa avaliação for equivalente a um objecto então são avaliadas da direita para a esquerda, as expressões da clausula correspondente, sendo retornado o valor da última expressão como sendo o resultado do case. Se o resultado da avaliação da chave for diferente de todos os objectos e se houver clausula senão, são avaliadas as expressões dessa clausula e é retornado o valor da última expressão como sendo o resultado do case. Se não houver clausula senão e o resultado e se o resultado da avaliação da chave for diferentes de todos os objectos, então o case retorna um valor não especificado.

> ( case (* 3 3)

Scheme

38

(( 2 4 6 8) 'p ar)

(( 1 3 5 7 9) ' imp ar) )

i mpar

> (ca se ( car '(c d))

( ( a e i o u) 'vo gal)

(( w y) 's emiv ogal )

(e l se ' co nsoa nte) )

conso ante

> (ca se ( * 3 3)

( ( 2 4 6 8 ) ' par)

( ( 1 3 5 7 ) ' i mpar ))

Unspecif i ed r et urn valu e

Funções

39

FFuunnççõõeess

Scheme

40

Funções

Funções Recursivas Uma função recursiva é uma função que se refere a si própria. A ideia consiste em utili zar a própria função que estamos a definir na sua definição.

Em todas as funções recursivas existe:

• Um passo básico (ou mais) cujo resultado é imediatamente conhecido.

• Um passo recursivo em que se tenta resolver um sub-problema do problema inicial. > (de f ine fa ct

( l ambda ( x)

( i f ( = 0 x)

1

( * x ( fac t ( - x 1) ) ))) )

f act

> fac t 3

6

Se analisarmos a função factorial, o caso básico é o teste de igualdade a zero ( = 0 n) , o resultado imediato é 1, e o passo recursivo é ( * n ( f act ( - n 1 )) ) .

Geralmente, uma função recursiva só funciona se tiver uma expressão condicional, mas não é obrigatório que assim seja. A execução de uma função recursiva consiste em ir resolvendo subproblemas sucessivamente mais simples até se atingir o caso mais simples de todos, cujo resultado é imediato. Desta forma, o padrão mais comum para escrever uma função recursiva é:

• Começar por testar os casos mais simples.

• Fazer chamada (ou chamadas) recursivas com subproblemas cada vez mais próximos dos casos mais simples.

Dado este padrão, os erros mais comuns associados às funções recursivas são, naturalmente:

• Não detectar os casos simples.

• A recursividade não diminuir a complexidade do problema.

No caso de erro em função recursivas, o mais usual é a recursividade nunca parar. O número de chamadas recursivas cresce indefinidamente até esgotar a memória (stack), e o programa gera um erro. No Scheme tal com em outras linguagens isto não é assim, e pode nunca ser gerado um erro. A recursividade infinita é o equivalente das funções recursivas aos ciclos infinitos dos métodos iterativos do tipo while-do e repeat-until.

Repare-se que uma função recursiva que funciona perfeitamente para os casos para que foi prevista pode estar completamente errada para outros casos. A função fact é um

Funções

41

exemplo. Quando o argumento é negativo, o problema torna-se cada vez mais complexo, cada vez mais longe do caso simples. ( f act - 1) = > ( f act - 2) = > ( f act - 3) = > …

Variáveis Locais Imagine-se que pretendemos escrever uma função que calcula a seguinte expressão:

Em Scheme, temos a seguinte tradução: (partindo do princípio que já existe uma função quadrado que devolve o quadrado de um número)

> (de f ine f

( l ambda ( x y)

( + (* (qu adr ado ( + 1 (* (qu adr ado x) y ) )) x)

( * (+ 1 ( * ( quad r ado x) y)) y) ) ))

f

> ( f 1 2)

15

Como se vê, a expressão ( + 1 ( * (q uadr ado x ) y )) aparece repetida duas vezes. Isto, para além de dificultar a leitura da função torna-a menos eficiente pois aquela expressão vai ter de ser calculada duas vezes.

Quase todas as linguagens de programação fornecem os meios para se criarem variáveis locais, temporárias, para guardarem resultados parciais que vão ser utili zados noutros sítios. Em Scheme, isso pode ser obtido definindo funções intermédias:

> (de f ine f

( l ambda ( x y)

( ( lam bda ( te mp)

( + (* (qu adr ado t emp) x)

( * te mp y ) ))

( + 1 ( * ( quadrad o x) y) ) )))

f

> (f 1 2)

15

Repare-se que dentro do corpo da lambda há referências quer aos parâmetros da lambda (t emp) quer aos parâmetros da função f em que a lambda está inserida.

Uma vez que não é muito conveniente separar os valores das variáveis, Scheme providencia uma forma especial designada l et que é convertida para uma lambda. A sua sintaxe é:

(let ((var-1 exp-1)

(var-2 exp-2)

(var-n exp-n))

Scheme

42

corpo)

Quando se avalia um l et , cada símbolo var - i é associado ao valor da expressão correspondente exp- i (em paralelo) e em seguida o corpo é avaliado como se as referências a var - i estivessem substituídas pelos valores correspondentes de exp- i . Esta forma especial é absolutamente equivalente a escrever:

((lambda (var-1 var-2 ...var-n)

corpo)

exp-1exp-2 ...exp-n)

Embora equivalentes, a utili zação da forma l et é mais fácil de ler. Este género de formas especiais que se limitam a ser uma tradução mais agradável para outras formas especiais são designadas por “ açúcar sintáctico” . O l et é “ açúcar sintáctico” para uma l ambda.

Definindo a função f usando o l et ficaria: > (de f ine f

( l ambda ( x y)

( l et ( (te mp ( + 1 (* ( quadra do x) y ) )))

( + (* (qu adr ado t emp) x)

( * te mp y ) )) ) )

f

> (f 1 2)

15

Âmbito e Duração

43

ÂÂmmbbii ttoo ee DDuurr aaççããoo

Scheme

44

Âmbito e Duração Quando uma determinada expressão que se dá ao avaliador faz referência a uma variável, ele precisa de saber qual é o valor dessa variável. Até agora, vimos que as lambdas eram o único meio de estabelecer variáveis. Os parâmetros de uma lambda definem um contexto em que as variáveis tomam um determinado valor. O contexto abarca todo o corpo da lambda.

Âmbito de uma Referência Designa-se por âmbito de uma referência, a zona textual em que ela pode ser correctamente referida. Assim, o âmbito de um parâmetro de uma lambda é a zona textual correspondente ao corpo da função. Isto implica que qualquer parâmetro da lambda pode ser referido dentro desse corpo, mas não fora dele.

> ( (la mbda (z ) (+ z z) ) 3)

6

> (+ z z)

Unbound v ari able z

Uma vez que o âmbito de um parâmetro é o corpo da lambda correspondente, é possível escrever:

> ((l ambda ( z) ( ( lam bda (w) (+ w z) ) 3 ) 4)

7

Reescrevendo o exemplo usando o l et , temos

> (let ((z 4))

(let ((w 3))

(+ w z)))

7

Neste exemplo, cada l ambda (ou cada l et ) estabelece um valor para uma variável. Quando se encontra uma referência a uma variável, o seu valor é dado pela ligação correspondente ao contexto mais pequeno. Se não existe qualquer ligação em nenhum dos contextos, a variável diz-se não ligada. A avaliação de variáveis não ligadas produz um erro.

Quando uma mesma variável aparece ligada repetidamente em contextos sucessivos, a ligação mais “ interior” obscurece todas as “exteriores”. Isto não quer dizer que as ligações exteriores sejam destruídas. Elas são apenas localmente substituídas durante a avaliação do corpo mais interior. Assim, temos o seguinte exemplo:

> (le t (( x 10))

( + (l et ( (x 20))

x)

x))

30

Âmbito e Duração

45

Diz-se que uma referência é de âmbito léxico quando ela só pode ser correctamente referida dentro da região textual da expressão que a criou.

Diz-se que uma referência é de âmbito vago (ou indefinido) quando ela pode ser correctamente referida a partir de qualquer região do programa.

Duração de uma Referência Designa-se por duração de uma referência o intervalo de tempo durante o qual ela pode ser correctamente referida.

Diz-se que uma referência é de duração dinâmica quando só pode ser correctamente referida no intervalo de tempo que decorre durante a avaliação da expressão que a criou.

Diz-se que uma referência é de duração vaga (ou indefinida) quando pode ser correctamente referida em qualquer instante após a avaliação da expressão que a criou.

Em Pascal, os parâmetros de uma função ou procedimento têm âmbito léxico e duração dinâmica. A ligação dos parâmetros formais aos parâmetros actuais existe apenas durante a execução da função ou procedimento.

Em Scheme, os parâmetros das lambdas têm âmbito léxico e duração vaga. Isto implica que é possível aceder a uma variável mesmo depois de a função que a criou ter terminado, desde que essa variável seja acedida dentro da região textual dessa função.

> ((l ambda ( x) ( + x y)) 10)

Unbound v ari able z

>( let ((y 5 ) ) (( l ambda ( x) ( + x y) ) 10) )

15

Repare-se que neste exemplo a função que estabelece o incremento refere-se à variável livre y . Uma das capacidades fundamentais das lambdas é a sua referência a variáveis livres. Uma variável diz-se livre numa lambda quando não é um dos parâmetros da lambda onde é referida.

Quando se aplica uma lambda aos seus argumentos, os parâmetros tomam como valor os argumentos correspondentes, enquanto que as variáveis livres tomam como valor o valor da primeira variável igual no contexto em que a lambda é definida. É por esse motivo que quando a lambda que realiza o incremento é aplicada a um número, ela sabe qual o valor correcto de y . Ele é dado pelo contexto léxico (i.e. textual) em que a lambda foi definida.

Scheme

46

Dados

47

DDaaddooss

Scheme

48

Dados Em todos os exemplos anteriores temos apresentado funções essencialmente numéricas. Os números são um exemplo dos dados que os procedimentos podem usar e produzir. Vamos agora apresentar outros tipos de dados que se podem util izar.

Átomos Já vimos que os números são um dos elementos primitivos do Scheme. Os símbolos (nomes de funções e variáveis) são outro dos exemplos. Estes elementos dizem-se atómicos, pois não podem ser decompostos.

Para que o Scheme possa considerar um símbolo por si só, i.e., sem o considerar uma variável, temos de usar a forma especial quot e, que devolve o seu argumento sem o avaliar.

> (a)

Unbound v ari able : a

>( quo t e a )

a

Existem várias funções para se testar a igualdade de elementos primitivos. Como já se viu, a igualdade de números é dada pela função =. Esta função compara números de todos os tipos.

> (= 1 1)

#t

> (= 1 1. 0)

#t

Em Scheme, existe unicidade de símbolos, i.e., dados dois símbolos com o mesmo nome, eles representam necessariamente o mesmo objecto, ou seja, o mesmo espaço da memória do computador. Isto permite que a comparação entre dois símbolos possa ser feita testando se eles representam o mesmo espaço, i.e., se apontam para a mesma zona da memória. A função eq? realiza essa operação.

> (eq ? (q uot e a) ( quot e a) )

#t

> (eq ? (q uot e a) (qu ote b))

( )

Note-se que a função eq? pode não funcionar correctamente quando aplicada a números. > (eq ? 1 1)

#t

> (eq ? 111111111111111111111111111111111111

111111111111111111111111111111111111)

( )

Dados

49

A razão do comportamento incoerente da função eq? em números deve-se ao facto de os números pequenos poderem ser representados como dados imediatos, enquanto os números grandes ocupam espaço na memória, em zonas diferentes.

Para se testar símbolos e números do mesmo tipo existe uma outra função designada equal? .

> ( equal? ( quo t e a ) ( quot e a) )

#t

> ( equal? 111111111111111111111111111111

111111111111111111111111111111)

#t

> ( equal? 1 1. 0)

( )

Combinações de Dados Para se combinar dados, é preciso que a linguagem possua uma “cola” que permita agrupar esses dados. Em Scheme, essa “cola” é implementada pela função cons .

A função cons cria um novo objecto que consiste na aglomeração de dois outros objectos, argumentos do cons . O cons é para o Scheme o mesmo que as tabelas (arrays) e estruturas (records, structs) são para as outras linguagens como Pascal ou C.

> (co ns 1 2)

( 1 . 2)

> (co ns ( cons 1 2) 3 )

( ( 1 . 2) . 3)

Dada uma combinação de objectos (um cons) podemos obter o primeiro elemento da combinação usando a função car e o segundo usando a função cdr .

> (ca r (c ons 1 2) )

1

> (cd r (c ons 1 2) )

2

Note-se que aplicar o car ou o cdr a um cons não destroi esse cons . O cons de dois objectos é designado um par com ponto (dotted pair). Como é natural, um cons não é um objecto atómico.

Note-se que para combinar dois quaisquer objectos é necessário arranjar espaço na memória para indicar qual o primeiro objecto e qual o segundo. É a função cons que arranja esse espaço. De cada vez que ela é chamada, mesmo que seja para juntar os mesmos objectos, ela arranja um novo espaço de memória. Isto implica que a função eq? é sempre falsa para o cons .

> (eq ?(c ons 1 2) (c ons 1 2) )

( )

Scheme

50

Abstracção de Dados A abstracção de dados é uma forma de aumentar a modularidade. Se decidirmos implementar números racionais, teremos de pensar em combinar dois números--o numerador e o denominador, e de os tratar como um todo. Se não fosse possível considerar aquela combinação de números como uma abstracção (um racional), toda a sua utili zação seria extremamente difícil . Por exemplo, para se somar dois números racionais, seria necessário usar uma operação para o cálculo do numerador, e outra operação para o cálculo do denominador, em vez de se pensar numa operação genérica, soma- r aci onal , que receberia dois argumentos “dois racionais” e calcularia um terceiro número “um racional” .

Para nos abstrairmos da complexidade de um número racional, devemos definir funções que os manipulam internamente. Podemos começar por definir uma função que constroi um número racional a partir do numerador e do denominador.

> (de f ine ra cion al

( lam bda ( numera dor denomin ador )

(c ons numerad or d enomina dor ) ))

r acio nal

Para sabermos qual é o numerador ou o denominador de um dado número racional podemos definir:

> (de f ine nu mera dor

( l ambda ( r ac i ona l )

(ca r ra cio nal) ) )

numerador

> (de f ine de nomi nado r

( lam bda ( ra cion al)

(cd r ra cio nal) ) )

denomi nador

Assim, já podemos escrever a função que calcula a soma de dois racionais. > (de f ine +r acio nal

(l ambda ( r 1 r 2)

( rac i onal ( + (* ( numer ado r r 1) ( denomin ador r2 ) )

( * (n umerador r2 ) (d enomina dor r1) ) )

( * ( denomin ador r1 ) (d enomi nador r 2)) ) ))

+r aci onal

Para simplificar a escrita de racionais, podemos definir uma função que escreve um racional de acordo com uma convenção qualquer.

> (de f ine es crev e- r acio nal

( lam bda ( ra cion al)

(fo r mat #t " ~S/ ~S" ( numer ador r acio nal )

( denomi nado r ra cio nal) ) ))

Dados

51

escre ve- r acio nal

Agora, já podemos calcular a seguinte expressão: > (es crev e- r acio nal ( +r aci onal ( rac i onal 1 2)

(ra cion al 1 3) ) )

5/ 6

Como se vê, tratamos um número racional como um só objecto, e separamos a parte do programa que usa racionais da parte que os implementa como pares de inteiros. Esta técnica designa-se por abstração de dados.

A abstração é a melhor maneira de lidar com a complexidade. A abstração de dados permite-nos isolar a util ização dos dados do modo como eles estão implementados, através da utili zação de barreiras de abstração. Essas barreiras consistem em limitar a utili zação dos dados a um pequeno conjunto de funções (r ac i onal , numera dor e denomi nador ) que escondem a maneira como eles estão implementados. Ao utili zador de um dado tipo de dados, apenas se diz quais as funções que ele pode usar para os manipular, e não qual o funcionamento das funções que implementam aquele tipo de dados.

Seguindo esta metodologia, se precisarmos de testar a igualdade de racionais, devemos escrever uma função que o faça usando apenas as funções de manipulação de racionais, i.e., r ac i onal , numera dor e denomi nador :

> (de f ine =r acio nal

( lam bda ( r1 r2)

(an d (= (n umerador r1 ) (n umer ado r r2 ) )

(= (d enomi nador r 1) ( denomi nado r r 2))) ) )

r acio nal

> (=r acio nal (ra cion al 4 6) (r acio nal 4 6) )

#t

Tipos Abstractos de Informação A teoria dos tipos abstractos de informação diz que o conceito fundamental para a abstracção de dados é a definição de uma interface entre a implementação dos dados e a sua utili zação. Essa interface é constituída por funções que se podem classificar em categorias: construtores, selectores, reconhecedores e testes. Estas funções são definidas em termos dos objectos mais primitivos que implementam o tipo de dados que se quer definir.

Os construtores são as funções que criam um objecto composto a partir dos seus elementos mais simples. Por exemplo, a função r ac i onal é um construtor para o tipo racional.

Os selectores são as funções que recebem um objecto composto e devolvem as suas partes. As funções numera dor e denomi nador são exemplos de selectores.

Os reconhecedores são as funções que reconhecem certos objectos especiais do tipo de dados que se está a definir.

Scheme

52

Finalmente, os testes são funções que comparam objectos do tipo que se está a definir. A função =r acio nal é um exemplo de uma função desta categoria. Como se pode verificar pela função =r acio nal , por vezes, os testes são implementados usando os próprios selectores.

Para que abstracção de dados seja correctamente realizada, é fundamental definir o conjunto de construtores, selectores, reconhecedores e testes. Todos os programas que pretenderem utili zar aquele tipo de dados são obrigados a usar apenas aquelas funções. Isso permite que se possa alterar a implementação do tipo de dados sem afectar os programas que o utili zam.

A implementação de estruturas de dados complexas só é correctamente realizada quando se segue esta metodologia com extremo rigor.

Quando um tipo abstracto de informação tem de interagir com um utilizador, quer para lhe pedir uma descrição de um elemento do tipo, quer para lhe apresentar uma descrição de um elemento do tipo, usa os denominados transformadores de entrada/saída. A função escr ev e- r aci onal é um exemplo de um transformador de saída para o tipo racional. Ela limita-se a apresentar uma representação compreensível de um número racional. O transformador de entrada realiza a operação inversa, i.e., constrói um elemento do tipo abstracto a partir de uma representação fornecida.

Listas

53

LL iissttaass

Scheme

54

Listas As listas são um dos componentes fundamentais da linguagem Scheme. Como iremos ver, as listas constituem uma estrutura de dados extremamente flexível.

Operações sobre Listas Em Scheme, quando o segundo elemento de um cons é outro cons, o Scheme escreve o resultado sob a forma de uma lista:

> (co ns 1 (c ons 2 (c ons 3 ( con s 4 5)) ) )

( 1 2 3 4 . 5)

Se o último elemento é a constante ( ) , o Scheme considera que ela representa a lista vazia, pelo que escreve:

> (cons 1 (cons 2 (cons 3 (cons 4 ()))))

(1 2 3 4)

Esta notação designa-se de lista e é esta que o Scheme usa para simplificar a leitura e a escrita. Uma lista é então uma sequência de elementos. Nesta óptica, a função car devolve o primeiro elemento de uma lista, enquanto a função cdr devolve o resto da lista. A função cons pode ser vista como recebendo um elemento e uma lista e devolve como resultado uma nova lista correspondente à junção daquele elemento no princípio daquela lista. Segundo esta abordagem, a função cons é um construtor do tipo abstracto de informação lista, enquanto as funções car e cdr são selectores.

Uma lista vazia é uma sequência sem qualquer elemento e pode ser escrita (). A lista vazia é o elemento mais primitivo do tipo lista. () é o construtor do elemento primitivo. Pode-se testar se uma lista é vazia com a função nul l ?. A função nul l ? é, portanto, um reconhecedor do tipo lista.

> (nu l l? ( ))

t

> (nu l l? ( co ns 1 (co ns 2 () ) ))

( )

Quando se pretendem construir li stas pode-se usar também a função l i s t . Esta função recebe qualquer número de argumentos e constrói uma lista com todos eles.

> (li st 1 2 3 4)

( 1 2 3 4)

> (li st 1 2 ( lis t 10 20 ) 3 4)

( 1 2 ( 10 20) 3 4)

Embora as listas não sejam mais do que uma estruturação particular de células cons , podendo por isso ser acedidas com as funções car e cdr , é considerado melhor estilo de programação usar as funções equivalentes f i r st e l i s t - t ai l . f i r st devolve o primeiro elemento da lista enquanto l i s t - t ai l devolve o resto da lista, i.e., sem o número de elementos que se colocar no 2 parâmetro.

Listas

55

> (fi r st ( li st 1 2 3 4)

1

> ( l i s t - t ai l ( lis t 1 2 3 4) 1)

( 2 3 4)

> ( l i s t - t ai l ( lis t 1 2 3 4) 2)

( 3 4)

É possível construir li stas dentro de listas. Scheme permite também a construção de listas directamente no avaliador. Idealmente, bastaria escrever (1 2 3 ...), só que isso seria avaliado segundo as regras de avaliação das combinações. O número 1 seria considerado um operador e os restantes elementos da lista os operandos. Para evitar que uma lista possa ser avaliada podemos usar a forma especial quot e, que devolve o seu argumento sem o avaliar.

> (qu ote ( 1 . (2 . ( 3 . ( ) ))) )

( 1 2 3)

> (qu ote ( 1 2 3 4 5 6 7 8 9 10 ) )

( 1 2 3 4 5 6 7 8 9 10)

Uma vez que a forma especial quot e é bastante util izada, Scheme fornece um meio de se simpli ficar a sua utilização. Se dermos ao avaliador uma expressão precedida por uma plica (quote em Inglês), é como se tivessemos empregue a forma especial quot e. A substituição é feita durante a leitura da expressão.

> '(1 2 3 4 5)

( 1 2 3 4 5)

Como é natural, as operações car e cdr podem ser encadeadas: > (ca r '( 1 2 3))

1

> (cd r '( 1 2 3))

( 2 3)

> (ca r (c dr ' (1 2 3) )

2

> (ca r (c dr ( cdr '(1 2 3))) )

3

Dado que aquele género de expressões é muito utili zado em Scheme, foram compostas as várias combinações, e criaram-se funções do tipo ( caddr exp) , que correspondem a ( car ( cdr ( cdr exp) ) ) . O nome da função indica quais as operações a realizar. Um “a” representa um car e um “d” representa um cdr .

> (ca dr ' ( 1 2 3) )

2

> (cd ddr ' (1 2 3) )

( )

Scheme

56

Listas de Argumentos Sendo as listas uma das estruturas básicas do Scheme, a linguagem permite aplicar funções directamente a listas de argumentos através da função appl y .

(apply func arg-1 arg-2 ...rest-args)

Nesta aplicação o último argumento r est - ar gs é uma lista com os restantes argumentos. Desta forma, pode-se escrever qualquer das seguintes equivalências:

(apply func (list arg-1 arg-2 ...arg-n)) <=>

(apply func arg-1 (list arg-2 ...arg-n)) <=>

(apply func arg-1 arg-2 ...(list arg-n)) <=>

(apply func arg-1 arg-2 ...arg-n ())) >( app l y + (l i st 3 4 5 6) )

18

>(ap ply + 3 4 ' ( 5 6 ) )

18

Tipos Aglomerados Um tipo aglomerado é um tipo abstracto de informação que é composto exclusivamente pela aglomeração de outros tipos abstractos. O conjunto dos racionais é um exemplo pois, como vimos, um racional não é mais do que uma aglomeração de dois inteiros. As operações fundamentais de um tipo aglomerado são os seus construtores e selectores, embora possam existir outras. Como vimos, para um racional, as operações mais utili zadas eram o construtor racional e os selectores numerador e denominador, mas também foram definidos alguns testes e os transformadores de entrada/saída.

Os tipos aglomerados são extremamente utili zados. Por este motivo é costume as linguagens de alto nível fornecerem ferramentas próprias para os tratar. Pascal, por exemplo, permite defini-los com a forma especial record, enquanto que a linguagem C usa, para o mesmo efeito, o struct.

Para exemplificarmos a utili zação de tipos aglomerados podemos considerar a definição de um automóvel. Um automóvel é caracterizado por uma marca, um modelo, um dado número de portas, uma cil indrada, uma potência, etc. Para simplificar, podemos considerar só as três primeiras. O construtor de um objecto do tipo automóvel não tem mais que agrupar as informações relativas a cada uma daquelas características. Para isso, podemos usar a função l i s t . Assim, criamos o construtor do tipo da seguinte forma:

> (de f ine no vo- automovel

(l ambda ( marc a model o por ta s)

( l ist ma r ca mode l o port as) ) )

novo - automovel

Os selectores do tipo automóvel limitam-se a determinar de que é que um dado objecto daquele tipo é composto:

Listas

57

> (de f ine au t omovel - marca

(l ambda ( auto move l )

( f irs t automovel ) ))

automovel - marca

> ( def i ne a ut omove l - modelo

( la mbda (a ut omovel )

( second a ut omovel) ) )

aut omovel - modelo

> ( def i ne a ut omove l - por t as

( la mbda ( aut omovel)

(t hi r d au t omov el ) ) )

aut omovel - por t as

Estando na posse destas funções, podemos criar um automóvel específico, por exemplo: > (no vo- automovel 'h onda 'ci vic 2)

( honda ci vic 2)

Dado aquele objecto do tipo automóvel, podemos estar interessados em alterar-lhe o número de portas, passando-as de 2 para 4, por exemplo. Contudo, para manipularmos um tipo abstracto devemos restringirmo-nos às operações desse tipo. Precisamos, portanto, de criar novas operações que nos permitem modificar um objecto. Para o tipo automóvel poderiamos definir:

> (de f ine mu da- automovel - marca

(l ambda ( auto move l nova - marca )

( muda - n- esimo 0 auto move l nova- marca ) ))

muda- automovel - marca

> ( def i ne muda- aut omovel - modelo

( la mbda( aut omov el n ovo - modelo )

(muda- n- esi mo 1 a ut omovel novo- modelo ) ) )

muda- aut omovel - modelo

> ( def i ne muda- aut omovel - por t as

( la mbda (a ut omovel n ov o- por t as )

(muda- n- esi mo 2 a ut omovel novo- por t as ) ) )

muda- aut omovel - por t as

A função muda- n- esi mo recebia um número n, uma lista e um novo elemento, e substituía o n-ésimo elemento da lista pelo novo elemento. Esta função não alterava a lista original, produzindo uma nova lista. Desta forma, qualquer destas funções do tipo automóvel deixa o automóvel a modificar absolutamente inalterado, produzindo um novo automóvel. Por este motivo, estas operações devem ser vistas como construtores do tipo automóvel, pois elas criam um novo automóvel a partir de um outro já existente. Elas não permitem alterar um automóvel já criado.

Scheme

58

Vectores

59

VVeeccttoorr eess

Scheme

60

Vectores Os vectores são estruturas heterogéneas cujos elementos estão indexados por números inteiros não negativos. Geralmente um vector ocupa menos espaço em memória que uma lista do mesmo tamanho, o tempo médio de acesso a um elemento é mais baixo nos vectores que nas listas.

O comprimento é o número de elementos que o vector tem. Este valor tem que ser um número inteiro não negativo. O índice de um vector corresponde à posição que ele ocupa no vector. Este valor também tem que ser um número inteiro não negativo e tem que ser inferior ao comprimento do vector. O primeiro elemento do vector tem índice 0.

Os vectores são escritos usando a notação # (objecto ...). Um exemplo de um vector de comprimento 3 com os valores 7, a string “ Isep” e a lista (1 2 3 4) é representado da seguinte forma:

> '#( 0 “I sep” (1 2 3 4) )

#( 0 “ I sep ” ( 1 2 3 4) )

Construção de Vectores Existem várias formas de criar um vector, das quais se destacam os procedimentos make-

vect or e o vect or . O make- vect or devolve um vector de n elementos, sendo também possível, caso pretendido, inicializar esses elementos com um valor por defeito. A sintaxe do make- vect or é a seguinte:

make-vector n [ valor_defeito]

O vector devolve um vect or cujos elementos são os argumentos do procedimento. O vect or é idêntico ao procedimento l i s t para as listas. A sua sintaxe é:

vector objecto ...

Os exemplos seguintes mostram algumas formas de criar vectores: > (ma ke- vecto r 3)

#( () ( ) ( ) )

> (ma ke- vecto r 3 0)

#( 0 0 0)

> (ma ke- vecto r 3 ‘ (a , b))

#( (a b) ( a b) (a b))

> vec t or 0 0 0)

#( 0 0 0)

> (ve ctor ‘( a,b) ‘(a , b) ‘(a , b) )

#( (a b) ( a b) (a b))

> (ve ctor 0 “ Ise p” ( 1 2 3 4) )

#( 0 “ I sep ” ( 1 2 3 4) )

Vectores

61

O procedimento make- i ni t ia l i zed- vect or é idêntico ao make- vect or com a diferença de os índices do vector serem inicializados não com uma valor constante mas por um procedimento cujo parâmetro de entrada é o próprio índice.

> (ma ke- i niti aliz ed- vecto r 5 ( la mbda (x) (* 2 x) ))

#( 0 2 4 6 8)

Existem outros procedimentos úteis que criam vectores, é o caso do vect or - copy do l i s t - >vecto r e do vect or - gr ow.

O vect or - copy devolve um novo vector que é a cópia de um vector inicial. A sua sintaxe é:

vector-copy vector

O l i s t - >vecto r cria um vector a partir de uma lista. Este procedimento é o procedimento antagónico do vect or - >l i st .

> (li st - >vect or ‘ (a b c d))

#( a b c d )

> (ve ctor - >l ist ‘# ( a b c d))

( a b c d)

O vect or - gr ow redimensiona o vector, mantendo os seus valores originais. É parecido com o redim preserve do Basic. A sintaxe do vect or - gr ow é a seguinte:

vector-grow vector n

O valor do parâmetro n tem que ser maior ou igual que o comprimento do vector. > (ve ctor - gr ow ‘ #(1 2 3) 4 )

#( 1 2 3 ( ) )

Operações Sobre Vectores Para verificarmos se um dado objecto é um vector basta executar o procedimento vect or ?.

> (ve ctor ? ‘ #(1 2))

#t

> (ve ctor ? ‘ ( 1 2 ) )

( )

O procedimento vect or - l ength serve para nos dizer qual é o comprimento de um vector.

> (ve ctor - l engt h ‘# ( ))

0

> (ve ctor - l engt h ‘# ( 1 2))

2

Se quisermos saber qual o valor de uma dada posição de um vector temos que usar o procedimento vect or - r ef . Este procedimento tem a seguinte sintaxe:

Scheme

62

vector-ref vector posição

O parâmetro posição tem que ser um índice válido. > (ve ctor - r ef ‘ #(9 8 7) 2 )

8

Se em vez de o valor de uma posição quisermos um subvector que se encontre entre uma dada posição inicial (inclusive) e uma posição final (exclusive), podemos usar o procedimento subvec t or :

> (su bvec t or ‘#( 1 2 3 4 5) 1 4)

#( 2 3 4)

O procedimento vect or - set ! serve para substituir o valor (objecto) de uma dada posição do vector por outro valor (objecto). A sua sintaxe é:

vector-set! vector posicao objecto

O parâmetro posição tem que ser um índice válido. > (le t (( vec (ve ctor 1 2 3) ) )

(v ecto r - set! vec 1 ' ( a b ) )

vec)

#( 1 ( a b) 3)

Se se quiser substituir todos os valores (objectos) do vector por um dado valor (objecto) pode-se usar o procedimento vect or - f i l l :

> (le t (( vec (ve ctor 1 2 3) ) )

(v ecto r - f i ll! vec '( a b) )

vec)

#( (a b) ( a b) (a b))

Estruturas de Dados

63

EEssttrr uuttuurr aass ddee DDaaddooss

Scheme

64

Estruturas de Dados O Scheme permite construir e manipular estruturas de dados <<structure>>. A função que permite criar as estruturas de dados é a função def in e- st r uct ur e.

A sintaxe da função def i ne- st r uct ur e é a seguinte:

define-structure (opções-estrutura ...) descrição-slot ...

Cada descrição-slot pode ter uma das seguintes formas:

nome-slot ou (nome-slot valor_por_defeito [opções_do_slot]

O campo nome e o nome-slot têm que ser símbolos. O campo valor_por_defeito é uma expressão que contém o valor inicial do slot. Sempre que uma instância da estrutura seja criada os slots são inicializados com esses valores iniciais. Se esse valor inicial não for especificado, o slot não fica com nenhum valor aquando da criação de uma nova instância da estrutura.

Quando é executada a função def i ne- st r uct ur e é definida uma estrutura de dados e são criados uma série de procedimentos para manipular as instâncias dessa estruturas que venham a ser criadas.

> (de f ine - st ruc t ure ca r ro marc a model o)

Neste momento foi criada um novo tipo de dados car r o, um construtor make- car r o, um predicado car r o?, procedimentos para aceder aos valores dos slots, car r o- mar ca e car r o- modelo e procedimentos para alterar os valores dos slots (modificadores), set -

car r o- mar ca! e set - car r o- modelo ! .

Como se pode observar o nome dos procedimentos criados segue uma determinada lógica. O nome do procedimento construtor é criado colocando make- antes do nome da estrutura. Para o nome do predicado basta acrescentar um ‘?’ ao nome da estrutura. O nome dos procedimentos para aceder aos valores dos slots é criado juntando o nome da estrutura ao nome do slot separados por um ‘ - ‘ . A criação do nome dos modificadores é feita acrescentado um ‘ ! ’ no fim e set - no início dos nome dos procedimentos de acesso aos slots.

O número de parâmetros do construtor make- car r o é igual ao numero de slots (dois neste caso), os seus argumentos são os valores que se quer atribuir a cada slot.

> (de f ine my carr o (make - carro “Op el” “Co r sa” ) )

mycar r o

> (ca r ro? mycar r o)

#t

> (ca r ro - marca myc arr o)

“ Opel ”

> (se t - carro - marca ! mycar r o “ Ford ” )

> (ca r ro - marca myc arr o)

“ Ford ”

Estruturas de Dados

65

Se quisermos que um slot seja <<read only>> podemos usar a opção de slot r ead- onl y . Se se colocar a opção r ead- onl y a #t o modificador desse slot não vai ser criado, não permitindo assim que se altere o valor do slot.

> (de f ine - st ruc t ure ca r ro ( marca “ Opel ” r ead- only #t) modelo)

> (de f ine my carr o (make - carro “Op el” “Co r sa” ) )

mycar r o

> (ca r ro? my carr o)

#t

> (se t - carro - marca ! mycar r o “ Ford ” )

Undound v ar iab l e: set - carro - marca !

Se quisermos alterar o nome do construtor, colocar parâmetros opcionais, ou alterar a ordem dos parâmetros do construtor podemos fazê-lo bastando para isso utili zar a opção de estrutura constr uct or . A sua sintaxe é:

constructor [nome [ lista-argumentos] ]

O nome é o nome com que vai ficar o construtor, se for omitido o nome será o nome por defeito. A li sta de argumentos, é a lista dos parâmetros do construtor. O número e o nome dos parâmetros tem que ser o mesmo dos slots.

> (de f ine - st ruc t ure (c arro

( cons t ruc t or new carr o ( mode l o #!op t ion al marc a)))

( marc a “Opel ” re ad- only #t)

( mode l o “ Cor sa”) )

> (de f ine my carr o (n ewcarro “V ectr a”))

mycar r o

> (ca r ro? my carr o)

#t

> (ca r ro - marca myc arr o)

“ Opel ”

> (ca r ro - model o mycar r o)

“ Vect r a”

Se quisermos atribuir valores aos slots através dos seus nomes podemos utili zar a opção de estrutura keywor d- constr uct or . A sintaxe do keywor d- const ru ct or é a seguinte

keyword-constructor [nome]

Como na opção constr uct or o nome é o nome pelo qual vai ficar designado o construtor, se for omitido, o nome será o nome por defeito.

> (de f ine - st ruc t ure (c arro

( keyword - const r uct or) )

( marc a “Opel ” )

( mode l o “ Cor sa”) )

> (de f ine my carr o (make - carro ‘mo del o “Mondeo” ‘ marca “ For d”))

Scheme

66

mycar r o

> (ca r ro? my carr o)

#t

> ( carr o- marca myc arr o)

“ Ford ”

> (ca r ro - model o mycar r o)

“ Mondeo”

Programação Imperativa

67

PPrr ooggrr aammaaççããoo II mmppeerr aatt iivvaa

Scheme

68

Programação Imperativa Todas as funções que apresentámos anteriormente realizam operações muito variadas e algumas são até relativamente complexas, mas nenhuma afecta os seus argumentos. Elas limitam-se a produzir novos objectos a partir de outros já existentes, sem alterar estes últimos seja de que forma for. Até as próprias variáveis que introduzimos nas funções e que se destinavam a guardar valores temporários não eram mais do que parâmetros de uma lambda, e a sua inicialização correspondia a invocar a lambda com os valores iniciais como argumentos, sendo por isso inicializadas uma única vez e nunca modificadas. Por este motivo, nem sequer foi apresentado nenhum operador de atribuição, tão característico em linguagens como C e Pascal.

Este estilo de programação, sem atribuição, sem alteração dos argumentos de funções, e em que estas se limitam a produzir novos valores, é designado programação funcional. Neste paradigma de programação, qualquer função da linguagem é considerada uma função matemática pura que, para os mesmos argumentos produz sempre os mesmos valores. Nunca nada é destruído. Uma função que junta duas listas produz uma nova lista sem alterar as listas originais. Uma função que muda o número de portas de um automóvel produz um novo automóvel.

A programação funcional tem muitas vantagens sobre outros estilos de programação, em especial no que diz respeito a produzir programas muito rapidamente e minimizando os erros. Contudo, tem também as suas limitações, e a sua incapacidade em modificar seja o que for é a maior. A partir do momento em que introduzimos a modificação de objectos, estamos a introduzir o conceito de destruição. A forma anterior do objecto que foi modificado deixou de existir, passando a existir apenas a nova forma. A modificação implica a introdução do conceito de tempo. Os objectos passam a ter uma história, e isto conduz a um novo estilo de programação.

Atribuição Para se alterar o valor de uma variável o Scheme possui um operador de atribuição. A forma especial set ! recebe uma variável e um valor e atribui o valor à variável.

> (le t (( x 2) )

( set! x ( + x 3))

( set! x ( * x x))

( set! x ( - x 5) )

x)

20

Cada vez que se realiza uma atribuição, perde-se o valor anterior que a variável possuía. Muito embora a forma especial set ! , como todas as funções e forma especiais, retorne um valor, esse valor não possui qualquer interesse. O operador de atribuição serve apenas para modificar o estado de um programa, neste exemplo, alterando o valor de x . Por este motivo, a atribuição assemelha-se mais a um comando do que a uma função. A atribuição é uma ordem que tem de ser cumprida e de que não interessa o resultado. A ordem é a operação fundamental da programação imperativa, em que um programa é composto por

Programação Imperativa

69

sucessivos comandos. Neste estilo de programação, os comandos funcionam por efeitos secundários. O valor de cada comando não tem interesse e muitas vezes nem sequer tem significado falar dele.

Sequências de código A forma especial begi n está especialmente vocacionada para este género de utili zação. Ela recebe um conjunto de expressões que avalia sequencialmente retornando o valor da última. Desta forma é possível incluir várias acções no consequente ou alternativa de um if, por exemplo.

>( if ( > 3 2)

(be gin

( writ e ' esto u- no- conse quen t e)

( + 2 3))

(be gin

( writ e ' esto u na al t ern ati va)

( * 4 5)))

estou - no- conse quen t e

5

> (d efin e x 0)

(b egi n (s et! x 5)

(+ x 1) )

6

Algumas das formas especiais do Scheme incluem um begi n implícito. Vimos atrás um exemplo de um l et que realizava quatro operações em sequência. Isto implica que o l et e, por arrastamento, as lambdas possuem também a capacidade de realizar operações em sequência. O cond está também nesta categoria. A sua sintaxe é, na realidade, a seguinte:

(cond (condição-1 expressão-11...expressão-1l)

(condição-2 expressão-21...expressão-2m)

(condição-n expressão-n1...expressão-nk))

O cond testa cada uma das condições em sequência, e quando uma delas avalia para verdade, são avaliadas todas as expressões da cláusula correspondente sendo devolvido o valor da última dessas expressões.

Usando o cond, o exemplo anterior ficará mais elegante: >( con d (( > 3 2)

(w r it e 'e stou - no- conse quen t e)

(+ 2 3))

(#t

(w r it e 'e stou na alt ern at iva )

Scheme

70

(* 4 5)))

estou - no- conse quen t e

5

As sequências de código são também suportadas por qualquer lambda. Em consequência, as formas especiais que implicam a criação de lambdas, como o l et e o próprio def i ne (na definição de funções) permitem também especificar mais do que uma expressão, sendo estas avaliadas em sequência e devolvido o valor da última.

Repetição Para além dos operadores de atribuição (set ! , etc.) e dos operadores que permitem sequências de código (begi n) a linguagem Scheme possui muitas outras formas especiais destinadas a permiti r o estilo de programação imperativa. De destacar são as estruturas de controle de repetição, tais como o ” named” l et , o do e ainda outras adequadas para iterar ao longo de listas.

A sintaxe do ” named” l et é a seguinte:

(let nome ((inicialização das variáveis) ...)

expressão

expressão ...)

O ” named” l et tem a mesma sintaxe e semântica que o normal l et , excepto no facto de o nome em vez de estar associado a uma expressão, estar associado a um procedimento, onde os argumentos formais são as variáveis e o corpo são as expressões. Assim a execução das expressões podem ser repetidas invocando o nome do procedimento.

> (le t lo op

( (nu mber s ' ( 3 - 2 1 6 - 5) )

(no nneg '( ) )

( neg '( ) ))

( co nd ( ( nul l ? numbers )

( lis t nonneg neg))

( ( >= ( ca r number s) 0)

( loo p ( cdr numbers )

( cons (c ar n umber s) non neg)

neg))

( el se

( loo p ( cdr numbers )

nonneg

( cons (c ar n umber s) neg ) ))) )

A forma especial do permite estabelecer variáveis, inicializá-las e incrementá-las automaticamente, testar condições de paragem com indicação do valor a retornar e repetir a execução de código. A sintaxe do do é a seguinte:

Programação Imperativa

71

do ((inicialização da variável a incremente e o tipo de incremento) ...)

(expressão de teste ...)

comandos ...

A seguinte expressão exemplifica um ciclo que escreve todos os números desde 0 até 100, retornando o símbolo f i m no final do ciclo.

>( do ( (n 0 ( 1+ n ) ))

( ( > n 100) ' f im)

(wr i te n))

01234567891011.. 9899100

f i m

Apesar do estilo mais utili zado na maioria das linguagens de programação ser o imperativo, ele é muito pouco natural em Scheme.

A falta de naturalidade resulta, por um lado, de os programas em Scheme se decomporem geralmente em pequenas funções que calculam valores, invalidando uma abordagem baseada em ciclos de alteração de variáveis, típica da programação imperativa.

Por outro lado, a grande maioria de tipos de dados existentes em Scheme são inerentemente recursivos, o que dificulta o seu tratamento segundo o estilo imperativo.

Apesar de muito pouco prático para usar em Scheme, a programação imperativa tem algumas vantagens, das quais a possibilidade de atribuição é a maior (e também a mais perigosa).

Scheme

72

Modelos de Ambiente

73

MM ooddeellooss ddee AAmmbbiieennttee

Scheme

74

Modelos de Ambiente Até agora vimos que as variáveis eram apenas designações para valores. Quando se avaliava uma expressão, as variáveis desapareciam, sendo substituídas pelos seus valores. A partir do momento em que podemos alterar o valor de uma variável, o seu comportamento torna-se menos claro.

Para se explicar correctamente este comportamento é necessário passar para um modelo de avaliação mais elaborado designado modelo de avaliação em ambientes.

Neste modelo, uma variável já não é uma designação de um valor mas sim uma designação de um objecto que contém um valor. Esse objecto pode ser visto como uma caixa onde se guardam coisas. Em cada instante, a variável designa sempre a mesma caixa, mas esta pode guardar coisas diferentes. Segundo o modelo de ambientes, o valor de uma variável é o conteúdo da caixa que ela designa. A forma especial set ! é a operação que permite meter valores dentro da caixa.

As variáveis são guardadas em estruturas denominadas enquadramentos. Por exemplo, cada vez que usamos a forma l et é criado um novo enquadramento para conter as variáveis estabelecidas pelo l et . Todas as expressões pertencentes ao corpo do l et serão avaliadas em relação a este enquadramento. Imaginemos agora a seguinte situação:

>( let ((x 1) )

(le t (( y 2)

( z 3) )

( + x y z) ))

6

Neste exemplo, o corpo do primeiro l et é um novo l et . Existem portanto dois enquadramentos. Estes enquadramentos estão organizados de modo a que o corpo do segundo l et consiga fazer referência às três variáveis x , y e z.

Para isso, os enquadramentos são estruturados sequencialmente, desde aquele que for textualmente mais interior até ao mais exterior. Essa sequência de enquadramentos é designada por ambiente.

Cada enquadramento é uma tabela de ligações, que associa as variáveis aos seus valores correspondentes. Uma variável nunca pode estar repetida num enquadramento, embora possa aparecer em vários enquadramentos de um ambiente. Cada enquadramento aponta para o ambiente envolvente, excepto o ambiente global, que é composto por um único enquadramento sem ambiente envolvente. É no ambiente global que estão guardadas todas as funções que usamos normalmente.

Âmbito Léxico A regra de avaliação de variáveis em ambientes diz que o valor de uma variável em relação a um ambiente é dado pela ligação dessa variável no primeiro enquadramento em que ela surja ao longo da sequência de enquadramentos que constituem esse ambiente. Se

Modelos de Ambiente

75

nenhum enquadramento possui uma ligação para essa variável ela diz-se não ligada. É um erro avaliar variáveis não ligadas.

Uma vez que os enquadramentos de um ambiente estão associados lexicamente às formas que os criaram, é possível determinar o âmbito de uma variável qualquer simplesmente observando o texto do programa.

Usando o modelo de avaliação em ambientes é muito fácil perceber o comportamento da forma especial l et (que não é mais do que uma simplificação de uma lambda) e da forma especial set ! . Cada l et aumenta o ambiente em que é avaliado com um novo enquadramento, estabelecendo ligações para as suas variáveis. Quando se pretende saber o valor de uma variável percorre-se o ambiente, começando pelo primeiro enquadramento até se encontrar a ligação correspondente. Se ela não aparecer, vai-se passando de enquadramento em enquadramento até se atingir o ambiente global, e se aí também não existir nenhuma ligação para aquela variável é gerado um erro de variável não ligada. O set ! altera o valor da variável que aparece estabelecida no enquadramento mais próximo do ponto onde o set ! é avaliado. Se se atingir o ambiente global, e se aí também não existir nenhuma ligação para aquela variável, é criada essa ligação no ambiente global.

> (le t (( x 10))

( + x y))

Unbound v ari able : y

> (de f ine y 0)

y

> (se t ! y 20)

20

> (le t (( x 10))

( + x y))

30

Como se vê pelo exemplo. A partir do momento em que se estabeleceu uma ligação no ambiente global para a variável y, já é possível avaliar aquele l et apesar de ele fazer referência a uma variável livre. No entanto, a utili zação da forma especial set ! para criar variáveis globais é considerada pouca correcta e o compilador emitirá um aviso se encontrar uma destas formas de util ização. A utili zação do set ! deve ser restringe a modificações do valor de variáveis previamente estabelecidas.

As regras de avaliação do modelo de ambientes são, em tudo, equivalentes às do modelo clássico, excepto no que diz respeito à aplicação de funções.

No modelo de ambientes todas as funções possuem um ambiente associado, que corresponde àquele que existia quando a função foi definida. Quando se aplica uma função aos seus argumentos, cria-se um novo ambiente, cujo primeiro enquadramento contém as ligações dos parâmetros formais da função aos seus argumentos e cujo ambiente envolvente é aquele em que a função foi definida. É em relação a este novo ambiente que se avalia o corpo da função.

Note-se que a forma especial def i ne define funções (i.e., cria uma ligação entre o nome da função e a lambda correspondente ao seu corpo) sempre no ambiente global, enquanto

Scheme

76

que set ! altera a ligação de uma variável no primeiro enquadramento do ambiente em que a forma especial é avaliada. Só se a variável não for encontrada na sequência de enquadramentos é que o set ! cria uma no ambiente global.

Âmbito Dinâmico A criação de variáveis globais em Scheme deve ser feita usando a forma especial def i ne.

> (de f ine ac elar acao - gr avi dade 9. 8)

acela r aca o- gr avi dade

> ace l ara cao- gr avi dade

9. 8

> (de f ine *y * )

* y*

> (de f ine *z * 10)

* y*

Note-se a convenção adoptada para as variáveis globais de usar nomes compreendidos entre um par de asteriscos. Quando se definem constantes essa convenção não se aplica.

O facto de podermos ter variáveis globais introduz uma alteração nas regras de avaliação. Tínhamos visto que as variáveis que eram parâmetros de funções (e, como tal, as variáveis introduzidas por um l et ) tinham âmbito léxico, ou seja, apenas podiam ser referidas dentro da região textual que as introduziu. No entanto, as variáveis globais como acel er acao- gr avid ade, * y* ou * z* podem ser referidas de qualquer ponto do programa, fazendo com que o seu âmbito passe a ser vago. No entanto, apesar de ser possível referênciar a variável * y* , será produzido um erro quando tentarmos determinar o seu valor, uma vez que ele ainda está indefinido. Será preciso ligarmos um valor àquela variável antes de a podermos avaliar e, para isso, podemos usar o f l ui d- l et .

A sintaxe do f l ui d- l et é a seguinte:

fluid-let ((inicialização da variável) ...) expressão expressão ...

A sintaxe deste do f l ui d- l et é similar à do l et , mas ao contrário do l et o f l ui d- l et

não cria uma nova associação apenas atribuí temporariamente o valor à variável correspondente.

> (de f i ne * y*)

* y*

> (de f ine te ste

( l ambda ( ) ( + *y * *y * )) )

t este

> (te ste)

Unass i gned varia ble: *y *

> (le t (( * y* 10) ) (t est e))

Unass i gned varia ble: *y *

> (fl uid - l et ( ( *y* 10 ) ) ( t est e))

Modelos de Ambiente

77

20

>* y*

Unass i gned varia ble: *y *

Repare-se que apesar de, momentaneamente, termos atribuído um valor à variável * y* por intermédio de um f l ui d- l et , ela perdeu esse valor assim que terminou o f l ui d-

l et . A duração da variável * y* é, assim, dinâmica. Apenas as variáveis léxicas possuem duração indefinida. Variáveis como * y* e * z* dizem-se especiais e possuem âmbito vago e duração dinâmica. Esta combinação dá origem a um comportamento que se designa de âmbito dinâmico.

Um dos aspectos mais críticos na utilização de variáveis de âmbito dinâmico é o facto de, geralmente, não ser suficiente ler o código de um programa para perceber o que é que ele vai fazer--é também preciso executá-lo. O seguinte exemplo explica este ponto.

Imaginemos as seguintes definições: > (le t (( x 2) )

( defi ne soma- 2

( la mbda (y)

( + x y)) ) )

soma- 2

> (le t (( x 1000) )

( soma- 2 1))

3

> (de f ine *x * 1)

* x*

> (le t (( * x* 2))

( defi ne soma- 2

(la mbda (y )

( + * x* y ) )))

soma- 2

> (fl uid - l et ( ( *x* 10 00))

( soma- 2 1))

1001

O primeiro exemplo envolve apenas variáveis léxicas. Daí que baste observar o texto da função soma- 2 para se perceber que a variável x usada em ( + x y ) toma sempre o valor 2.

No segundo exemplo, a única diferença está no facto de a variável * x* ser especial. Nesta situação a função soma- 2 não usa o valor de * x* que existia no momento da definição da função, mas sim o valor de * x* que existe no momento da execução da função. Desta forma, já não é suficiente observar o texto da função soma- 2 para perceber o que ela faz. Por este motivo, o uso excessivo de variáveis dinâmicas pode tornar um programa difícil de ler e, consequentemente, difícil de desenvolver e difícil de corrigir.

Scheme

78

Parâmetros Especiais

79

PPaarr ââmmeettrr ooss EEssppeecciiaaiiss

Scheme

80

Parâmetros Especiais

Parâmetros Opcionais Para definirmos funções que têm parâmetros opcionais temos de usar um quali ficador especial designado #! opti onal na lista de parâmetros formais. Esse qualificador indica que todos os parâmetros que se lhe seguem são opcionais e que, se os argumentos correspondentes forem omitidos, eles valem ( ) . Se pretendermos um valor diferente para um parâmetro, podemos inserir o parâmetro numa lista com o seu valor. A seguinte função mostra como se pode definir a função i ncr que incrementa o seu argumento de uma unidade, ou de uma quantidade que lhe seja fornecida.

> (de f ine in cr

( l ambda ( x # ! opt i onal ( i 1) )

(+ x i ) )

> ( i nc r 1 0)

11

> ( i nc r 1 0 5)

15

Parâmetros de Resto Para além do quali ficador #!opt i onal existem ainda o #!r est . O #!r est só pode quali ficar o último parâmetro de uma função, e indica que esse parâmetro vai ficar ligado a uma lista com todos os restantes argumentos. A título de exemplo, temos:

> ((lambda (x y #!rest z) (list x y z)) 1 2 3 4 5 6)

(1 2 (3 4 5 6))

O quali ficador #!r est permite assim construir funções com qualquer número de argumentos.

Macros

81

MM aaccrr ooss

Scheme

82

Macros Como referimos na apresentação da linguagem Scheme, existem certas formas da linguagem que não obedecem às regras de avaliação usuais. Essas formas designam-se formas especiais e o i f é um exemplo. Cada forma especial possui a sua própria regra de avaliação. Vimos que, por isso, era impossível definir o i f como se fosse uma função, pois todos os operandos (o teste, o consequente e a alternativa) seriam avaliados.

Embora a linguagem Scheme possua muitas formas especiais, é possível “criar” outras formas especiais através da util ização de macros. Uma macro é uma forma que a linguagem expande para outra forma, superando assim as dificuldades inerentes à avaliação dos argumentos que as funções realizam. Na realidade, Scheme possui muito poucas formas especiais reais. A grande maioria das formas especiais são implementadas através de macros, usando a forma especial def i ne- synt ax .

Escrita de Macros A escrita de uma macro é inerentemente mais complexa que a escrita de uma função, sendo decomposta em quatro fases:

1. Decidir se a macro é realmente necessária. Esta fase é de grande importância, pois cada vez que se define uma macro está-se a aumentar a linguagem com uma nova forma especial. Quem pretende ler um programa que usa a macro é obrigado a conhecer a sua sintaxe e semântica, e se o número de macros é muito grande, pode ser difícil perceber o código.

2. Escrever a sintaxe da macro. Nesta fase pretende-se definir qual vai ser a forma de utili zação da macro. A sintaxe deve ser o mais simples possível e o mais coerente possível com as restantes formas da linguagem para não complicar a sua leitura.

3. Escrever a expansão da macro. Nesta fase determina-se a expressão Scheme que a macro deve produzir quando expandida. A expansão é qualquer expressão Scheme, que pode inclusive fazer referência a outras macros.

4. Escrever a macro usando a forma especial def i ne- synt ax . É esta a fase mais delicada do processo, em que se programa um processo de transformar a forma especial que queremos definir numa expressão que use outras formas especiais já definidas.

A título de exemplo vamos definir a forma especial meu- i f cujo objectivo é simpli ficar o uso do cond quando só existe um teste, um consequente e uma alternativa.

A sintaxe da forma meu- i f é:

(meu-if teste consequente alternativa)

A expansão da macro será qualquer coisa da forma:

(cond (teste consequente)

(t alternativa))

Macros

83

A definição da macro é a seguinte: > (de f ine - synta x meu- i f

( sy ntax - r ules ()

( ( meu- i f t est e co nse quen t e a l te r nat i va )

( cond

( t est e co nse quen t e)

( #t a l ter nat i va) ) )))

meu- i f

> (me u- i f (> 3 2) #t #f )

#t

Caracteres de Macro Geralmente, a parte mais difícil na escrita de uma macro é a determinação das expressões Scheme que quando avaliadas produzem uma nova expressão Scheme que realiza o nosso objectivo. Para simpli ficar esta tarefa é usual utili zarem-se caracteres especiais que, à semelhança da plica (quot e) são transformados na leitura para outras expressões. Cada um dos caracteres especiais possui uma função Scheme associada que é avaliada quando a linguagem, durante a leitura das expressões, encontra um desses caracteres. Essa função Scheme pode então realizar mais leituras e retornar o que achar mais conveniente.

Estes caracteres especiais são designados caracteres de macro pois eles são transformados (são expandidos) na leitura em outras expressões, um pouco à imagem do que acontecia com as macros. A diferenção está no instante em que a expansão ocorre. Uma macro é expandida em tempo de compilação (ou, em algumas implementações de Scheme, em tempo de execução). Um carácter de macro é expandido na leitura de expressões.

A linguagem Scheme possui, definidos, vários caracteres de macro. A plica é um deles, o ponto e vírgula (que representa um comentário) é outro, etc. Alguns dos caracteres de macro são precedidos por um carácter especial, considerado o carácter de despacho, permitindo aumentar o número de possíveis caracteres de macro sem reduzir o número de caracteres normais utili záveis. O carácter de despacho mais usado é o cardinal, mas pode ser qualquer outro. Como exemplos destes caracteres de macro com despacho temos o cardinal-plica para indicar funções, o cardinal-barra para indicar caracteres, etc.

De todos os caracteres de macro, aqueles que são particularmente úteis para a escrita de macros são o plica para trás (` <<bac kquot e>>), a vírgula (, <<comma>>) e o vírgula-arroba (, @<<co mma- at >>).

O backquot e indica ao avaliador que não deve avaliar uma expressão excepto quando for indicado em contrário. Quando usado isoladamente, o backquot e funciona exactamente como o quot e. No entanto, a sua combinação com o comma e o comma- at permite simpli ficar imenso a escrita de expressões complexas. O comma só pode ser utili zado numa expressão (uma lista, tipicamente) precedida do backquot e, e informa o avaliador que a expressão que se segue é para avaliar e o seu resultado inserido na lista. O comma-

at é idêntico mas o resultado da avaliação tem de ser uma lista cujos elementos são inseridos.

Scheme

84

A título de exemplo, temos: > `(( + 1 2) , (+ 1 2) (l i st 1 2) ,( l ist 1 2) , @(li st 1 2) )

( ( + 1 2) 3 ( l ist 1 2) ( 1 2) 1 2)

Conclusão

85

CCoonncclluussããoo

Scheme

86

Conclusão O Scheme é uma linguagem de programação de alto nível, que suporta operações sobre tipos de dados estruturados como string, listas, vectores e também operações sobre tipos de dados mais tradicionais como números e caracteres. Embora o Scheme seja muitas vezes associado a aplicações simbólicas, as suas estruturas de dados flexíveis e os seus tipos de dados poderosos, fazem do Scheme uma linguagem versátil. Scheme tem sido usado para escrever editores de texto, optimização de compiladores, librarias gráficas, aplicações numéricas, análise financeira, e virtualmente todo outro tipo de aplicação imaginável.

Os programas em Scheme são altamente portáteis entre várias máquinas, porque as dependências das máquinas estão quase totalmente escondidas do programador. Embora alguns dos primeiros sistemas em Scheme fossem lentos e ineficientes, as novas implementações do Scheme baseadas em compiladores são rápidas, podendo mesmo ser comparadas com programas equivalentes escritos em linguagens de baixo nível.

Scheme trata os dados de uma maneira diferentemente da maioria das linguagens. Os dados, ou os objectos, são guardados numa pilha, onde permanecem até não serem mais necessários sendo libertados automaticamente. Os objectos são dados que são armazenados na pilha e aí são retidos indefinidamente, eles podem ser passados livremente como argumentos para procedimentos, devolvidos como valores de procedimentos, e podem ser combinados formar novos objectos novos.

No coração do Scheme está um pequeno grupo de formas sintácticas a partir das quais todas as outras formas são construídas. Este grupo de formas sintácticas e a biblioteca que contém os procedimentos primitivos compõem por inteiro a linguagem Scheme. Assim um interpretador e/ou um compilador para o Scheme pode ser bastante pequeno, rápido e altamente fiável.

O Scheme é uma linguagem fácil de aprender, pois tem uma sintaxe e uma semântica muito simples além disso a natureza interactiva das aplicações encorajam a experimentação. Estas características tornam a linguagem ideal para o ensino e para a inicialização na arte da programação A linguagem desafia-nos a usar todo o seu potencial, mas para isso acontecer é necessário um estudo mais profundo e muita prática.

Bibliografia

87

BBiibbll iiooggrr aaff iiaa

Scheme

88

Bibliografia A bibliografia e sites consultados para a realização deste trabalho foram os seguintes:

• "The Scheme Programming Language, Second Edition" de R. Kent Dybvig.

• Site http://www.swiss.ai.mit.edu/projects/scheme/index.html

• Site http://www.scheme.org/

• Site http://www.ai.mit.edu/projects/su/su.html

• Site http://www.cs.indiana.edu/scheme-repository/

• Site http://www.schemers.org/

• Site http://www-2.cs.cmu.edu/Groups/AI/html/faqs/lang/scheme/top.html

• Site http://www-2.cs.cmu.edu/Groups/AI/html/faqs/lang/scheme/top.html

• Site http://library.readscheme.org/

Agradecimentos

89

Agradecimentos Prevaleço-me da oportunidade para agradecer a todos os professores do ISEP pelos conhecimentos que, por sua via, me foram transmitidos, e de modo especial ao meu orientador de projecto, Sr. Eng. Paulo Ferreira, pela paciência, disponibili dade e compreensão que demostrou.