Curso de ScriptVox Intermediário - Aula 7 - Prof. Oswaldo Vernet - iNCE/UFRJ

Talvez a principal novidade nesta versão 6.0 do interpretador ScriptVox tenha sido
a introdução de três novos tipos de dados, além do tipo cadeia, que era o único 
suportado até então na linguagem.

O tipo revela a natureza do dado e está intimamente relacionado ao conceito matemático 
de conjunto: se um dado tem determinado tipo, isto quer dizer que ele é um elemento 
do conjunto constituído por todos os dados daquele tipo.

Assim, por exemplo, se uma variável armazena um valor inteiro, ela armazena um certo
elemento do conjunto de números inteiros que podem ser manipulados na linguagem.
É claro que, computacionalmente, existe um limite na representação interna dos dados,
e o conjunto dos inteiros em uma determinada linguagem não coincide com o conjunto 
dos números inteiros em matemática, porque este último é infinito.

Numa linguagem como C ou Java, precisamos DECLARAR variáveis antes de usá-las e, 
no ato da declaração, informamos ao compilador o tipo de dados que ela pode armazenar.
Isto significa que, enquanto aquela variável durar, ela só armazenará dados daquele tipo. 
Se for declarada como inteira, só poderá armazenar números inteiros; se for declarada como 
cadeia, só poderá armazenar cadeias; e assim por diante.

Em diversas linguagens interpretadas, as variáveis não precisam ser declaradas: 
uma variável é criada no momento exato em que ela é mencionada pela primeira vez.
Quando uma variável tem seu conteúdo modificado, o dado que está sendo atribuído a ela
é de determinado tipo e, enquanto a variável armazenar este dado, diremos que a variável 
é também daquele tipo. Assim, após a seguinte atribuição:

x := "uma frase não muito longa"

a variável "x" será do tipo CADEIA, porque ela armazenará, até segunda ordem, a cadeia
"uma frase não muito longa". Se, em outro ponto posterior da execução do script, fizermos 
a seguinte atribuição:

x := 2

a variável "x" deixará de ser do tipo CADEIA e passará a ser do tipo INTEIRO, porque,
a partir de agora, e até segunda ordem, o valor que ela armazena é inteiro.

Pelo fato de as variáveis herdarem os tipos dos conteúdos que armazenam, a tipagem em
ScriptVox é dita DINÂMICA. O mesmo acontece em outras linguagens interpretadas,
como PHP, Python e Javascript.

Até este ponto do curso, já examinamos dois TIPOS suportados pelo ScriptVox: INTEIRO e
CADEIA. Vamos, nesta aula, estudar o tipo LISTA.

O texto que se segue é uma obra de ficção. Qualquer semelhança com a realidade é mera
coincidência.

Mamãe quer ir ao mercado fazer compras e pede a seu filho que tome nota, num pedacinho
de papel, dos itens a serem comprados. O filho, bom aluno de computação e acostumado à
tarefa que se repete toda semana, percebe logo que mamãe deseja construir uma LISTA de 
coisas a comprar. Esta lista começará vazia, sem nenhum item, até que mamãe pronuncie 
o primeiro item a ser comprado. 

Mamãe começa então: 

"arroz, feijão, alho, cebola, patinho cortado pra bife, tomate, chuchu."

O que o filho faz?  Vai escrevendo uma linha depois da outra no seu pedacinho de papel,
enquanto mamãe vai ditando. Cada item que mamãe fala vai para o último lugar da lista. 

O filho interrompe: 

"Mãe, pra que comprar chuchu?  Não tem gosto de nada."

Mamãe ignora completamente a intervenção, olha na cesta e verifica que tem alho de sobra. 
Então, manda o filho riscar o alho da lista. 

Depois desta exclusão, mamãe pergunta:
 
"Meu anjo, eu já falei cebola?".

O filho, de pronto, responde: 

"Falou, mãe, cebola é o quarto item".

Mamãe então continua:

"Bom, cebola eu já falei. E qual foi o segundo item que eu ditei?"

O filho examina e lista e responde:

"Foi feijão, mãe".

E mamãe muda de ideia:

"Em vez de feijão, troca o segundo item por lentilha, seu pai disse que tá com saudade de
comer lentilha". 

O filho faz uma careta, porque detesta lentilha. Mas cumpre a ordem da mãe e troca "feijão" 
por "lentilha". Mamãe finaliza: 

"espinafre, abóbora, carne moída". E pronto. 

Para conferir, mamãe pede a seu filho que diga tudo o que vai ser comprado. O rapaz,
então, lê tudo o que escreveu no papelzinho, na ordem que mamãe ditou; menos o alho,
que foi retirado e o feijão que foi trocado por lentilha. Assim:

arroz, lentilha, cebola, patinho cortado pra bife, tomate, chuchu, espinafre, abóbora, carne moída.

Aí mamãe reclama: 

"Menino, assim eu fico doida no mercado! Bota as coisas em ordem: carne perto de carne, legume
perto de legume, senão fico zanzando igual uma barata tonta". 

O filho obediente atende, rearrumando os itens da seguinte maneira: 

arroz, lentilha, patinho cortado pra bife, carne moída, cebola, tomate, chuchu, espinafre, abóbora.

Aí mamãe pergunta: 

"Falei cheiro verde?" 

O filho examina a lista e diz: 

"Não, mamãe, cheiro verde não tá na lista não". 

Mamãe ordena: 

"Então bota cheiro verde, mas vê se bota no lugar certo". 

O filho, intrigado, indaga: 

"E tem lugar certo do cheiro verde?".  

Mamãe, irritada, responde: 

"Claro que tem, peste: é depois da cebola, porque a banca do cheiro verde fica logo depois da banca da cebola".

E a lista final de compras fica assim: 

arroz, lentilha, patinho cortado pra bife, carne moída, cebola, cheiro verde, tomate, chuchu, espinafre, abóbora.

O filho, por último, pergunta: 

"Mãe, e as quantidades de casa coisa? Você nunca diz."

Mamãe silencia por alguns segundos, reflete e retruca: 

"Isso não é receita, seu lesado, isso é lista de compras. Quantidade a gente bota na receita".

Sem discutir, o filho entrega o papelzinho a mamãe e corre pro computador, para tuitar que já fez a lista
de compras da semana e que mamãe só diz quantidades em receitas. 1191 comentam.

Apesar de ingênuo, o diálogo ilustra aproximadamente o que se entende, do ponto de vista computacional,
por uma LISTA SEQUENCIAL. Uma lista sequencial (que aqui chamaremos apenas de LISTA) é uma estrutura 
constituída por posições consecutivas, que são ocupadas por elementos. 

A LISTA VAZIA é aquela que não tem nenhuma posição ocupada. Se uma lista tem elementos, ela não é vazia,
e dizemos que ela está POVOADA. Numa lista povoada, não podem existir posições vagas: o primeiro elemento 
é seguido do segundo, que é seguido do terceiro, e assim sucessivamente, até o último elemento da lista. 
Portanto, numa lista povoada, não pode haver buracos: se existem o primeiro e o terceiro elementos, 
obrigatoriamente entre eles deve existir o segundo.

O diálogo também ilustra as operações que costumamos efetuar sobre listas.

Quando mamãe pede ao filho que tome nota, ele parte de uma folha em branco, sem nenhum item.
Isto corresponde à operação de PRODUZIR UMA LISTA VAZIA, sem elementos.

Quando mamãe dita os itens e o filho os acrescenta ao final da lista, isto corresponde a
ANEXAR elementos ao final da lista.

Quando mamãe pergunta qual foi o segundo item ditado, isto corresponde a INDEXAR a lista,
obtendo o elemento armazenado em uma certa posição.

Pode ser necessário verificar se um determinado item já foi ou não incluído na lista,
ou seja, sele ele PERTENCE à lista. Isto corresponde a BUSCAR um elemento na lista e a resposta
pode ser SIM ou NÃO. No caso da resposta positiva (ou seja, o elemento pertence à lista), é usual
informar também em que posição ele está armazenado; assim, além de sabermos que o elemento está
na lista, ficamos sabendo onde ele está.

Quando mamãe pede ao filho que leia tudo o que ela já ditou, isto corresponde a PERCORRER a
lista, executando uma determinada ação para cada elemento. No caso, a ação é FALAR cada elemento. 

Quando mamãe mandou riscar o alho, pois já havia de sobra em casa, o que o filho fez, na verdade, 
foi verificar em que posição da lista estava o elemento "alho". Conhecida esta posição, ele 
moveu todos os elementos das posições seguintes de uma posição para trás, mas sem tirar da ordem. 
Portanto, este desejo de mamãe correspondeu a duas operações sobre a lista: uma BUSCA, para 
saber em qual posição está o elemento, seguida de uma REMOÇÃO, que consiste em retirar 
o elemento de uma certa posição da lista e mover os seguintes de uma posição para trás,
para não deixar buracos.

Por fim, mamãe manda o filho acrescentar o cheiro verde à lista de compras na posição seguinte
à posição em que se encontra a cebola. Isto corresponde a BUSCAR o elemento "cebola", descobrindo
sua posição, e depois INSERIR "cheiro verde" na posição seguinte. Para isto, o elemento daquela
posição os das posições seguintes e devem ser movidos de uma posição para frente, de modo a
abrir espaço para o elemento que vai entrar.

O único detalhe que não está presente neste diálogo é que, computacionalmente, uma lista pode
conter elementos repetidos. Isto numa lista de compras talvez não faça muito sentido; mas uma
lista constituída por informações em um script pode conter repetições.

Vejamos, então, em ScriptVox, como trabalhar com listas. 

Por analogia com outras linguagens de programação, convencionamos que as posições em uma
lista começam de 0, diferentemente das cadeias, em que o primeiro caractere está na posição 1.
Assim, o primeiro elemento de uma lista é o da posição 0, o segundo elemento é o da posição 1, 
e assim por diante. 

O tamanho (ou cardinalidade) de uma lista é o número de elementos armazenados nela. Portanto, a
lista vazia tem tamanho zero e, se uma lista povoada tem tamanho N, sabemos que as posicões de 
zero até N menos 1 estão ocupadas por elementos.

Vamos enumerar, a seguir, algumas ações sobre listas:

1. A lista vazia é simbolizada por um abre colchete seguido de um fecha colchete, sem nenhum
   elemento entre eles. Assim, se quisermos produzir a lista vazia e atribuí-la à variável 
   "itens", usamos a seguinte atribuição:
   
   itens := []
   
2. Se quisermos produzir uma lista e já conhecemos os elementos a serem guardados nela, basta
   colocá-los por ordem de posição entre o abre e o fecha colchetes, separados por vírgulas, 
   como no exemplo:
   
   itens := [ "arroz", "vinagre", "cebola", "alho" ]
   
   Após esta atribuição, o conteúdo da variável "itens" será uma lista constituída por quatro
   elementos, todos eles cadeias. O elemento da posição zero é a cadeia "arroz", o da posição
   1 é "vinagre", o da posição 2 é "cebola" e o da posição 3 é "alho". Esta lista tem tamanho 4,
   estando ocupadas as posições de 0 a 3, sem buracos.
   
3. Se desejamos saber qual o elemento da posição 2, basta mencionarmos

   x := itens[2]
   
   No nosso exemplo, a variável "x" conterá, após a atribuição, a cadeia "cebola".
   
   Observe que a sintaxe é a mesma usada para indexar cadeias. O índice pode ser qualquer expressão
   que tenha como resultado um número inteiro entre 0 e o tamanho da lista menos um.
   
4. Para substituir o elemento em uma dada posição da lista por outro valor, basta usarmos a
   indexação do lado esquerdo do sinal de atribuição:
   
   itens[2] := "cominho"
   
   No exemplo, a variável "itens" passaria a conter a lista
   
   [ "arroz", "vinagre", "cominho", "alho" ]
   
   após esta atribuição. Da mesma forma, o índice utilizado entre colchetes deve ser uma expressão 
   que tenha como resultado um número inteiro entre 0 e o tamanho da lista menos um.
   
5. Para anexar um elemento ao final da lista, aumentando em uma unidade o seu tamanho, não é
   preciso especificar o índice do lado esquerdo da atribuição; basta abrir e fechar colchetes. Assim:
   
   itens[] := "leite"
   
   tem o efeito de acrescentar a cadeia "leite" ao final da lista, que passa a ter, então, 5 elementos:
   
   [ "arroz", "vinagre", "cominho", "alho", "leite" ]
   
6. Se a questão é descobrir a posição que um certo elemento ocupa na lista, a mesma função POS, que
   estudamos para cadeias, serve também para listas, mas com uma diferença: quando o elemento não
   estiver na lista, a função retornará menos um, em vez de zero, já que zero, para listas, é uma
   posição válida. Assim

   p := POS ("alho", itens)

   vai atribuir à variável "p" o inteiro 3, já que a cadeia "alho" está na posição 3 da lista
   armazenada em "itens". Porém, se o comando fosse:

   p := POS ("banana", itens)

   a variável "p" teria o valor menos um após a atribuição. O inteiro menos um não corresponde a
   nenhuma posição válida da lista e isto significa que o elemento "banana"  não pertence a ela.

7. Para remover o elemento de uma dada posição em uma lista, usamos a função RETIRA, passando como
   parâmetros a lista e a posição. Assim:

   RETIRA (itens, 1)
   
   A função modifica a própria lista passada como primeiro parâmetro, excluindo dela o elemento da
   posição passada como segundo parâmetro. Vale lembrar que os elementos das posições seguintes
   são movidos de uma posição para trás, de modo que lista continue íntegra, sem buracos. Após esta
   chamada, no nosso exemplo, a variável "itens" conterá a lista:
   
   [ "arroz", "cominho", "alho", "leite" ]
   
   Repare que o elemento "vinagre", que ocupava a posição 1, foi removido.
   
8. Para acrescentar um elemento em uma dada posição da lista, a função INSERE espera como parâmetros
   a lista, a posição e o elemento a ser acrescentado, nesta ordem. O que ela faz é mover todos os
   elementos a partir da posição dada (e inclusive o elemento situado nela) de uma posição para frente,
   abrindo espaço para adicionar o elemento dado como terceiro parâmetro. Este elemento ficará
   exatamente na posição indicada pelo segundo parâmetro. Assim, se usarmos a chamada:

   INSERE (itens, 2, "orégano")

   a lista armazenada na variável "itens" terá o seguinte conteúdo:

   [ "arroz", "cominho", "orégano", "alho", "leite" ]

   O novo elemento "orégano" ficou exatamente na posição 2 da lista e o elemento antigo que ocupava
   a posição 2 (no caso, "alho") e o seguinte ("leite") foram movidos de uma posição para frente.   

9. A função TAMANHO (a mesma usada para cadeias) pode também ser aplicada a uma lista, quando
   desejamos obter o número de elementos nela armazenados. Assim, seguindo o exemplo, se usarmos o comando:
   
   escreve TAMANHO(itens)
   
   será escrito, na tela, o inteiro 5.
   
  

EXERCÍCIOS

Perguntas de Estudo Dirigido

1.  Defina, com suas palavras, o que é uma lista.
2.  Dê um exemplo de lista, na vida quotidiana, em que elementos podem estar repetidos.  
3.  Como se produz uma lista vazia?
4.  Como se anexa um elemento ao final de uma lista?
5.  Como se verifica se um elemento pertence ou não a uma lista?
6.  O que signifca PERCORRER uma lista?
7.  Por que alguns elementos precisam ser movidos numa operação de inserção ou de remoção em
    uma lista?
8.  Se mamãe pedisse ao filho: "Confere aí se eu coloquei sal. Se não coloquei, acrescenta".
    Como você executaria este pedido com as operações que estudamos sobre listas?
9.  Uma cadeia é um caso particular de lista?  Se isto for verdade, então reflita: 
    quais são os elementos de uma cadeia?


Exercício de programação

Escreva em ScriptVox e execute no interpretador o script que implementa exatamente a historinha 
entre mamãe e seu filho, excluindo, é claro, as partes que não se referem à lista 
(por exemplo, o garoto não gostar de chuchu).

Comece com a lista vazia e vá traduzindo, em ScriptVox, as ordens de mamãe. A cada ordem cumprida,
escreva na tela a lista do jeito que ela ficou. Use o comando escreve (ele sabe escrever listas).


Exercício de avaliação (enviar para scriptvox@gmail.com até o meio-dia de 9 de fevereiro de 2012)

Sua tarefa será implementar um script para manipular uma lista através de comandos digitados
pelo usuário.

O script inicia com uma lista vazia, guardada em alguma variável. O usuário digita comandos,
que são lidos pelo seu script, e esses comandos realizam operações sobre a lista.

Cada comando digitado pelo usuário é constituído por um verbo no imperativo, que indica o comando,
seguido de um complemento, que é sempre um elemento. Entre o verbo e o complemento
pode haver um número qualquer de brancos. O script termina quando o usuário tecla enter na
hora de digitar a linha de comando.

Implemente apenas três comandos:

1. ANEXA elemento
   O elemento digitado logo após o comando ANEXA deve ser anexado ao final da lista.
   
2. BUSCA elemento
   Obtém a posição do elemento na lista, caso ele pertença à lista. Se não pertencer, deverá
   ser escrito na tela: "O elemento não pertence à lista".
   
3. RETIRA elemento
   O elemento deve ser buscado e retirado da lista.
   
Para facilitar a sua vida na hora de quebrar uma linha em verbo e complemento, utilize a
função nativa "SEPARA", que funciona da seguinte maneira: ela espera como parâmetro uma cadeia
e retorna como resultado uma lista contendo as palavras encontradas na cadeia. Por exemplo,
sejam as duas atribuições seguintes:

le linha
palavras := SEPARA (linha)

A variável "linha" armazena a linha digitada pelo usuário. Suponhamos que ele tenha digitado

RETIRA salsa

Após a segunda atribuição, a variável "palavras" terá como conteúdo a lista 

[ "RETIRA", "salsa" ]

em que o elemento da posição zero é o verbo e o elemento da posição 1 é o elemento.

Antes de ler o próximo comando, escreva na tela o conteúdo atual da lista. E tenha cuidado com
usuários maldosos, que digitam comandos errados ou digitam comandos certos sem especificar
o elemento. Não confie em usuários.

Bom estudo!

Oswaldo Vernet







