Scala Através
de Exemplos
DRAFT
January 31, 2013
Martin Odersky
P ROGRAMMING M ETHODS L ABORATORY
EPFL
S WITZERLAND
T RADUZIDO POR : V INICIUS M IANA E A NTONIO B ASILE
Índice
1 Introdução
1
2 Um primeiro exemplo
3
3 Programando com Atores e Mensagens
7
4 Expressões e Funções Simples
11
4.1 Expressões e Funções Simples . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 Expressões Condicionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.4 Exemplo: Raiz Quadrada pelo Método de Newton . . . . . . . . . . . . . 15
4.5 Aninhamento de Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.6 Recursão de Cauda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Funções de Primeira Classe
21
5.1 Funções Anônimas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3 Exemplo: Encontrando Pontos Fixos de Funções . . . . . . . . . . . . . 25
5.4 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.5 Elementos da Linguagem Vistos Até Aqui . . . . . . . . . . . . . . . . . . 28
6 Classes e Objetos
31
7 Classes Case e Casamento de Padrões
43
7.1 Classes Case e Objetos Case . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.2 Casamento de Padrões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
8 Tipos Genéricos e Métodos
53
8.1 Parâmetros Tipo Ligados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
8.2 Anotações de Variância . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
iv
ÍNDICE
8.3 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
8.4 Tipos Minimais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
8.5 Tuplas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
8.6 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
9 Listas
65
9.1 Usando Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
9.2 Definição da classe List I: Métodos de Primeira Ordem . . . . . . . . . . 67
9.3 Exemplo: Merge sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
9.4 Definição da classe List II: Métodos de Alta Ordem . . . . . . . . . . . . 72
9.5 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
10 For-Comprehensions
81
10.1 O Problema das N-Rainhas . . . . . . . . . . . . . . . . . . . . . . . . . . 82
10.2 Pesquisando com For-Comprehensions . . . . . . . . . . . . . . . . . . . 83
10.3 Tradução de For-Comprehensions . . . . . . . . . . . . . . . . . . . . . . 84
10.4 Laços For . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
10.5 Generalizando For . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
11 Estados Mutáveis
89
11.1 Objetos Mutáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
11.2 Estruturas Imperativas de Controle . . . . . . . . . . . . . . . . . . . . . 93
11.3 Exemplo Estendido: Simulação de Eventos Discretos . . . . . . . . . . . 94
11.4 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
12 Computando com Streams
101
13 Iteradores
105
13.1 Métodos dos Iteradores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
13.2 Construindo Iteradores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
13.3 Usando Iteradores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
14 Valores Preguiçosos (Lazy)
111
15 Parâmetros Implícitos e Conversões
115
ÍNDICE
v
16 Inferência de Tipos de Hindley/Milner
119
17 Abstracões para Concorrência
127
17.1 Sinais e Monitores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
17.2 SyncVars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
17.3 Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
17.4 Computação Paralela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
17.5 Semáforos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
17.6 Leitores/Escritores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
17.7 Canais Assíncronos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
17.8 Canais Síncronos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
17.9 Trabalhadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
17.10Caixas Postais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
17.11Actors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Capítulo 1
Introdução
Scala facilita a integração entre a programação orientada a objetos e a programação
funcional. Foi criada para expressar padrões de programação comuns de forma
concisa, elegante e fortemente tipada. Scala introduz diversas construções de
linguagem inovadoras. Por exemplo:
• Tipos abstratos e composições mixin unificam conceitos de objetos e
módulos de sistema.
• Casamento de padrões sobre hierarquias de classe unificam o acesso a dados
funcional e orientado a objetos, simplificando bastante o processamento de
árvores XML.
• Sintaxe flexível e sistema de tipos que habilitam a construção de avançadas
bibliotecas e um novas linguagens específicas a um domínio.
Ao mesmo tempo, Scala é compatível com Java. Bibliotecas Java e frameworks
podem ser usados sem código extra ou declarações adicionais. Este documento
introduz Scala de um modo informal, através de uma sequência de exemplos.
Os capítulos 2 e 3 salientam alguns dos aspectos que tornam Scala interessante. Os
capítulos seguintes introduzem as construções da linguagem Scala de um modo
mais completo, começando com expressões e funções simples, e desenvolvendo
até objetos e classes, listas e streams, estado mutável, casamento de padrões até
exemplos mais completos que mostram interessantes técnicas de programação.
A presente exposição informal pretende ser complementada por um Manual de
Referência da Linguagem Scala, que especificarão Scala de modo mais detalhado
e preciso.
Reconhecimento. Temos um grande débito ao maravilhoso livro de Abelson e
Sussman “Structure and Interpretation of Computer Programs”[ASS96]. Muitos
exemplos e exercícios deles também estão presentes aqui. Naturalmente a
2
Introdução
linguagem utilizada em cada caso foi mudada do Scheme para o Scala. Além disso,
os exemplos fazem uso de construções da orientação a objetos do Scala onde isto
foi considerado apropriado.
Capítulo 2
Um primeiro exemplo
Para começar, apresentamos um primeiro exemplo, a implementação de Quicksort
em Scala.
def sort(xs: Array[Int]) {
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
}
def sort1(l: Int, r: Int) {
val pivot = xs((l + r) / 2)
var i = l; var j = r
while (i <= j) {
while (xs(i) < pivot) i += 1
while (xs(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (j < r) sort1(i, r)
}
sort1(0, xs.length - 1)
}
A implementação se parece muito com a que você faria em Java ou C. Nós
usamos os mesmos operadores e estruturas de controle. Existem também algumas
pequenas diferenças sintáticas, particularmente:
• As declarações começam usando palavras reservadas. Particularmente,
declarações de funções são iniciadas com a palavra def, declarações de
4
Um primeiro exemplo
variáveis são iniciadas com a palavra var e declaração de constantes
(chamadas de valores) são iniciadas com a palavra val.
• O tipo de um parâmetro em uma função é declarado após o nome do
parâmetro seguido de dois pontos(:). O tipo pode ser omitido quando o
compilador for capaz de inferi-lo pelo contexto.
• A declaração de vetores do tipo T é feita usando a expressão Array[T] ao invés
de T[]. O i-ésimo elemento de um vetor a é acessado usando a(i) ao invés de
a[i].
• Funções podem ser aninhadas umas dentro das outras. Funções aninhadas
podem acessar parâmetros e variáveis locais de suas funções externas. Por
exemplo, o nome do vetor xs é visível nas funções swap e sort1, e portanto
não precisam ser passadas como um parâmetro para elas.
Pelo que vimos, Scala se parece com uma linguagem bem convencional com
algumas peculiaridades sintáticas. De fato é possível escrever programas em estilo
imperativo ou orientado a objetos. Isto é importante, porque é uma das coisas que
facilitam combinar componentes Scala com componentes escritos em linguagens
convencionais, tais como Java, C# ou Visual Basic. Entretanto, também é possível
escrever programas num estilo completamente diferente. Aqui está o Quicksort
novamente, desta vez escrito em estilo funcional.
def sort(xs: Array[Int]): Array[Int] = {
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}
O programa funcional captura a essência do algoritmo quicksort de modo conciso:
• Se o vetor está vazio ou consiste de um único elemento, já está ordenado,
então retorne imediatamente.
• Se o vetor não está vazio, escolha um elemento do meio do vetor como pivô.
• Particione o vetor em dois subvetores contendo, respectivamente os
elementos que são menores que o elemento pivô, maiores que, e um terceiro
vetor que contém elementos iguais ao pivô.
• Ordene os dois primeiros subvetores por uma chamada recursiva da função
de ordenação.1
1
Isso não é exatamente o que o algoritmo imperativo faz; este último particiona o vetor em dois
subvetores contendo elementos menores que ou maiores ou iguais ao pivô.
5
• O resultado é obtido pela concatenação dos três subvetores.
Tanto a implementação imperativa quanto a funcional tem mesma complexidade
assintótica – O(N l og (N )) no caso médio e O(N 2 ) no pior caso. Mas onde
a implementação imperativa opera localmente, modificando o vetor original, a
implementação funcional retorna um novo vetor ordenado e deixa o vetor original
inalterado. A implementação funcional, portanto, requer mais memória transiente
que a imperativa.
A implementação funcional faz parecer que Scala é uma linguagem especializada
para operações funcionais sobre vetores. De fato, não é; todas as operações usadas
no exemplo são simples métodos de biblioteca de uma classe sequência Seq[T]
que é parte da biblioteca padrão Scala, e onde ela mesma é implementada em
Scala. Como vetores são instâncias de Seq, todos os métodos de sequência estão
disponíveis para eles.
Em particular, há o método filter que recebe como argumento uma função
predicado. Esta função predicado deve mapear elementos do vetor para valores
boleanos. O resultado de filter é um vetor consistindo de todos os elementos do
vetor original para o qual a função predicado é verdadeira. O método filter de um
objeto tipo Array[T] portanto tem a assinatura.
def filter(p: T => Boolean): Array[T]
Aqui, T=>Boolean é o tipo das funções que recebem um elemento do tipo T e
retornam um valor booleano do tipo Boolean. Funções como filter que recebem
uma outra função como argumento ou retornam uma função como resultado são
chamadas funções de alta ordem.
Scala não faz distinção entre nomes de identificadores e nomes de operadores. um
identificador pode ser ou uma sequência de letras ou digitos que começam com
uma letra, ou podem ser uma sequência de caracteres especiais, tais como “+”, “*”,
ou “:”. Qualquer identificador pode ser usado como operador infixo em Scala.
A operação binária E op E 0 é sempre interpretado como a chamada de método
E .op(E 0 ). Isso vale também para operadores binários infixos que iniciam com
uma letra. Consequentemente, a expressão xs filter (pivot >) é equivalente
à chamada de método xs.filter(pivot >).
No programa quicksort, filter é aplicado três vezes a um argumento de função
anônima. O primeiro argumento, pivot >, representa uma função que recebe um
argumento x e retorna o valor pivot > x. Este é um exemplo de uma função
parcialmente aplicada. Um outro modo, equivalente de se escrever esta função,
que torna o argumento oculto explicito é x => pivot > x. A função é anônima,
ou seja, não é definida com um nome. O tipo do parâmetro x é omitido porque
um compilador Scala pode inferí-lo automáticamente a partir do contexto onde a
função é usada. Resumindo, xs.filter(pivot >) retorna uma lista consistindo de
todos os elementos da lista xs que são menores que pivot.
6
Um primeiro exemplo
Olhando novamente em detalhes para a primeira, implementação imperativa do
Quicksort, percebemos que muitos dos construtores da linguagem usados na
segunda solução estão presentes, embora de modo distinto.
Por exemplo, operadores binários padrão, tais como +, -, ou < não são tratados de
modo especial. Assim como append, são métodos de seus operandos esquerdos.
Consequentemente, a expressão i+1 é vista como a invocação de i.+(1) do método
+ do valor inteiro de i. De fato, um compilador é livre (se moderadamente esperto,
ainda que esperado) para reconhecer o caso especial da chamada de método +
sobre argumentos inteiros e para gerar código inline eficiente para isso.
Por eficiência e melhor detecção de erros o laço while é um construtor primitivo
em Scala. Mas em princípio, poderia do mesmo modo ser uma função predefinida.
Aqui está uma possível implementação para ele:
def While (p: => Boolean) (s: => Unit) {
if (p) { s ; While(p)(s) }
}
A função While recebe como primeiro parâmetro uma função teste, que não recebe
parâmetros e produz um valor boleano. Como segundo parâmetro recebe uma
função comando que também não recebe parâmetros e produz como resultado
o tipo Unit. While invoca a função comando enquanto a função teste produzir
verdadeiro.
O tipo Scala Unit corresponde grosseiramente ao void no Java; é usado sempre
que uma função não retornar um resultado interessante. De fato, porque Scala
é uma linguagem orientada a expressões, cada função retorna algum resultado.
Se nenhuma expressão de retorno é explicitamente fornecida, o valor (), que é
pronunciado “unit”, é assumido. Este valor é do tipo Unit. Funções que retornam
“unit” são também chamadas procedimentos. Aqui está uma formulação mais
“orientada a expressão” da função swap na primeira implementação do quicksort,
que explicita isto:
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
()
}
O valor resultante desta função é simplesmente sua última expressão—uma palavra
chave return não é necessária. Observe que funções que retornam um valor
explícito sempre precisam de um “=” antes de seus corpos ou expressões de
definição.
Capítulo 3
Programando
Mensagens
com
Atores
e
Aqui está um exemplo que mostra uma área de aplicação para a qual Scala é
particularmente indicada. Considere a tarefa de implementar um serviço de
leilão eletrônico. Podemos usar um modelo de processo no estilo actor do Erlang
para implementar os participantes do leilão. Actors são objetos para os quais as
mensagens são enviadas. Cada actor tem uma caixa de correio para suas mensagens
de entrada que é representada para uma fila. Pode trabalhar sequencialmente nas
mensagens da sua caixa de correio, ou buscar por mensagens que casam com algum
padrão.
Para cada item negociado há um actor leiloeiro que publica a informação sobre o
item negociado, que aceita ofertas de clientes e que se comunica com o vendedor
e com o vencedor do leilão para fechar a transação. Apresentamos uma visão
superficial de uma implementação aqui.
Como primeiro passo, definimos as mensagens que são trocadas durante um leilão.
Há duas classes base abstratas AuctionMessage para mensagens de clientes do
serviço de leilão, e AuctionReply para respostas do serviço aos clientes. Para ambas
as classes base há um número de casos definidos na Figura 3.1.
Para cada classe base, há um número de classes case que definem o formato de
mensagens particulares dentro da classe. Estas mensagens podem em último caso
ser mapeadas a pequenos documentos XML. Esperamos que hajam ferramentas
automáticas que convertam entre documentos XML e estruturas de dados internas,
tais como as definidas acima.
A Figura 3.2 apresenta uma implementação Scala para a classe Auction para actors
do leilão que coordenam os lances sobre um item. Objetos para esta classe são
criados pela indicação
• Um actor vendedor que precisa ser notificado quando o leilão terminou,
8
Programando com Atores e Mensagens
import scala.actors.Actor
abstract class AuctionMessage
case class Offer(bid: Int, client: Actor)
case class Inquire(client: Actor)
extends AuctionMessage
extends AuctionMessage
abstract class AuctionReply
case class Status(asked: Int, expire: Date) extends AuctionReply
case object BestOffer
extends AuctionReply
case class BeatenOffer(maxBid: Int)
extends AuctionReply
case class AuctionConcluded(seller: Actor, client: Actor)
extends AuctionReply
case object AuctionFailed
extends AuctionReply
case object AuctionOver
extends AuctionReply
Listagem 3.1: Definição das Mensagens de um serviço de leilão
• o lance mínimo,
• a data de quando o leilão foi fechado.
O comportamento do actor é definido por seu método act. Este método seleciona
repetidamente (usando receiveWithin) uma mensagem e reage a ela, até que
o leilão seja fechado, o que é sinalizado por uma mensagem TIMEOUT. Antes
de finalmente parar, permanece ativo para um outro período determinado pela
constante timeToShutdown e replica para ofertas posteriores que o leilão está
fechado.
Aqui estão algumas explicações extras sobre os construtores usados neste
programa:
• O método receiveWithin da classe Actor recebe como parâmetro um prazo
dado em milisegundos e uma função que processa mensagens na caixa de
correio. A função é dada por uma sequência de cases que especificam um
padrão e uma ação para mensagens que casam com o padrão. O método
receiveWithin seleciona a primeira mensagem da caixa de correio que casa
com um destes padrões e aplica a ação correspondente a ele.
• O último case de receiveWithin é guardado por um padrão TIMEOUT. Se
nenhuma outra mensagem foi recebida nesse meio tempo, este padrão é
disparado após o prazo que foi passado como argumento para o método
envolvente receiveWithin. TIMEOUT é uma mensagem especial, que é
disparada pela própria implementação do Actor.
• Mensagens
de
resposta
destino ! AlgumaMensagem.
são
enviadas
usando
sintaxe
da
forma
! é usado aqui como um operador binário
9
class Auction(seller: Actor, minBid: Int, closing: Date) extends Actor {
val timeToShutdown = 36000000 // msec
val bidIncrement = 10
def act() {
var maxBid = minBid - bidIncrement
var maxBidder: Actor = null
var running = true
while (running) {
receiveWithin ((closing.getTime() - new Date().getTime())) {
case Offer(bid, client) =>
if (bid >= maxBid + bidIncrement) {
if (maxBid >= minBid) maxBidder ! BeatenOffer(bid)
maxBid = bid; maxBidder = client; client ! BestOffer
} else {
client ! BeatenOffer(maxBid)
}
case Inquire(client) =>
client ! Status(maxBid, closing)
case TIMEOUT =>
if (maxBid >= minBid) {
val reply = AuctionConcluded(seller, maxBidder)
maxBidder ! reply; seller ! reply
} else {
seller ! AuctionFailed
}
receiveWithin(timeToShutdown) {
case Offer(_, client) => client ! AuctionOver
case TIMEOUT => running = false
}
}
}
}
}
Listagem 3.2: Implementação do Serviço de Leilão
10
Programando com Atores e Mensagens
com um actor e uma mensagem como argumentos. Isto é equivalente
em Scala ao chamado de método destino.!(AlgumaMensagem), ou seja,
a invocação do método ! do actor destino com a mensagem dada como
parâmetro.
A discussão precedente deu uma idéia de programação distribuída em Scala. Isso
dá a sensação que Scala tem um rico conjunto de construtores que suportam
processos actor, envio e recebimento de mensagens, programação com timeouts
etc. De fato, o oposto é verdadeiro. Todos os construtores discutidos acima são
oferecidos como métodos na classe biblioteca Actor. Aquela classe é ele mesma
implementada em Scala, baseado no modelo thread subjacente à linguagem
hospedeira (Java ou .NET). A implementação de todas as características da classe
Actor usada aqui é dada na Seção 17.11.
As vantagens da abordagem baseada em biblioteca são a relativa simplicidade
da linguagem núcleo e a flexibilidade para os criadores de biblioteca. Como a
linguagem núcleo não precisa especificar detalhes da comunicação dos processos
de alto nível, pode ser mantida mais simples e geral. Como um modelo particular
de mensagens numa caixa de correio é um módulo biblioteca, pode ser modificado
livremente se um diferente modelo for necessário em algumas aplicações. A
abordagem requer, entretanto, que a linguagem núcleo seja expressiva o suficiente
para prover as abstrações linguísticas necessárias de um modo conveniente. Scala
foi criada com isto em mente; um de seus maiores objetivos de design foi deixá-la
flexível o suficiente para atuar como uma conveniente linguagem hospedeira para
domínios de linguagens específicos implementados por módulos de biblioteca.
Por exemplo, a construção de comunicação actor apresentada acima pode ser
vista como um desses domínios específicos de linguagem, que conceitualmente
estendem o núcleo Scala.
Capítulo 4
Expressões e Funções Simples
Os exemplos anteriores deram uma ideia do que pode ser feito com Scala. Agora,
introduzimos as suas construções de linguagem uma a uma de uma maneira mais
sistemática. Vamos começar com os menores elementos: expressões e funções.
4.1
Expressões e Funções Simples
Scala vem com um interpretador que pode ser visto como uma calculadora
sofisticada. O usuário interage com a calculadora digitando expressões. A
calculadora retorna o resultado do cálculo e o seu tipo de dado. Por exemplo:
scala> 87 + 145
unnamed0: Int = 232
scala> 5 + 2 * 3
unnamed1: Int = 11
scala> "hello" + " world!"
unnamed2: java.lang.String = hello world!
Também é possível dar nome a uma sub-expressão e usar o nome, ao invés da
expressão, nas expressões seguintes:
scala> def scale = 5
scale: Int
scala> 7 * scale
unnamed3: Int = 35
scala> def pi = 3.141592653589793
pi: Double
12
Expressões e Funções Simples
scala> def radius = 10
radius: Int
scala> 2 * pi * radius
unnamed4: Double = 62.83185307179586
Definições começam com a palavra reservada def. Elas introduzem um nome que
representa a expressão que vem depois do símbolo =. O intepretrador responde
com o nome introduzido e o seu tipo de dado.
Executando uma definição tal como def x = e não avaliará a expressão e. Ao invés
e é avaliado sempre que x for usado. Alternativamente, Scala oferece um valor
definição val x = e, o qual avalia o lado direito de e como parte da avaliação da
definição. Se x é então usado subsequentemente, é imediatamente substituído pelo
valor pré-computado de e, logo a expressão não precisa ser avaliada novamente.
Como as expressões são avaliadas? Uma expressão consistindo de operadores e
operandos é avaliada pela repetida aplicação dos seguintes passos de simplificação:
• escolha a operação mais a esquerda.
• avalie seu operando
• aplique o operador aos valores do operando.
Um nome definido por def é avaliado substituindo o nome pela definição do lado
direito (não avaliada). Um nome definido por val é avaliado pela substituição do
nome pelo valor da definição do lado direito. O processo de avaliação pára assim
que encontrarmos um valor. Um valor é algum dado, tal como uma cadeia de
caracteres, um número, um vetor, ou uma lista.
Exemplo 4.1.1 Aqui está uma avaliação de uma expressão aritmética.
→
→
→
→
(2 * pi) * radius
(2 * 3.141592653589793) * radius
6.283185307179586 * radius
6.283185307179586 * 10
62.83185307179586
O processo de simplificar gradualmente expressões para valores é chamado
redução.
4.2
Parâmetros
Usando def, pode-se também definir funções com parâmetros. Por exemplo:
4.2 Parâmetros
13
scala> def square(x: Double) = x * x
square: (Double)Double
scala> square(2)
unnamed0: Double = 4.0
scala> square(5 + 3)
unnamed1: Double = 64.0
scala> square(square(4))
unnamed2: Double = 256.0
scala> def sumOfSquares(x: Double, y: Double) = square(x) + square(y)
sumOfSquares: (Double,Double)Double
scala> sumOfSquares(3, 2 + 2)
unnamed3: Double = 25.0
Parâmetros de funções seguem o nome da função e sempre são envolvidos por
parênteses. Cada parâmetro vem com um tipo que segue o nome do parâmetro
e dois pontos. Até aqui, só precisamos de tipos numéricos, tal como o tipo
scala.Double dos números de precisão dupla. Scala define tipos aliases para alguns
tipos básicos, logo podemos escrever tipos numéricos como em Java. Por exemplo,
double é um tipo alias de scala.Double e int é um tipo alias para scala.Int.
Funções com parâmetros são avaliadas analogamente a operadores em expressões.
Primeiro, os argumentos da função são avaliados (da esquerda para direita). Então,
a aplicação da função é substituído pelo lado direito da função, e ao mesmo tempo
todos os parâmetros formais são substituídos pelos seus argumentos atuais.
Exemplo 4.2.1
sumOfSquares(3, 2+2)
→ sumOfSquares(3, 4)
→ square(3) + square(4)
→ 3 * 3 + square(4)
→ 9 + square(4)
→ 9 + 4 * 4
→ 9 + 16
→ 25
O exemplo mostra que o interpretador reduz argumentos de funções a valores antes
de reescrever a aplicação da função. Pode-se ao invés escolher aplicar a função a
argumentos não reduzidos. Isto levará a seguinte sequência de redução:
sumOfSquares(3, 2+2)
→ square(3) + square(2+2)
14
Expressões e Funções Simples
→ 3 *
→ 9 +
→ 9 +
→ 9 +
→ 9 +
→ 9 +
→ 25
3 + square(2+2)
square(2+2)
(2+2) * (2+2)
4 * (2+2)
4 * 4
16
A segunda ordem de avaliação é conhecida como chamada por nome, e a primeira
por chamada por valor. Para expressões que se utilizam apenas de funções e que
portanto podem ser reduzidas com o modelo de substituição, ambos os esquemas
levam ao mesmo valor final.
Chamada por valor tem a vantagem de evitar avaliações repetidas de argumentos.
Chamada por nome tem a vantagem de evitar avaliações de argumentos quando o
parâmetro não é usado pela função. Chamada por valor é geralmente mais eficiente
que chamada por nome, mas uma avaliação de chamada por valor pode entrar em
laço infinito, enquanto uma avaliação de chamada por nome termina. Considere:
scala> def loop: Int = loop
loop: Int
scala> def first(x: Int, y: Int) = x
first: (Int,Int)Int
Então first(1, loop) é reduzido com uma chamada por nome a 1, enquanto o
mesmo termo, através de uma chamada por valor reduz a si mesmo repetidamente,
logo a avaliação não termina.
first(1, loop)
→ first(1, loop)
→ first(1, loop)
→ ...
Scala usa chamada por valor por default, mas muda para avaliação de chamada por
nome se o tipo do parâmetro for precedido por =>.
Exemplo 4.2.2
scala> def constOne(x: Int, y: => Int) = 1
constOne: (Int,=> Int)Int
scala> constOne(1, loop)
unnamed0: Int = 1
scala> constOne(loop, 2)
^C
// leva a laco infinito
// para a execucao com Ctrl-C
4.3 Expressões Condicionais
4.3
15
Expressões Condicionais
O if-else do Scala leva a uma escolha entre duas alternativas. Sua sintaxe é
a mesma do if-else do Java. Mas onde o if-else do Java pode ser usado
somente como uma alternativa entre comandos, Scala permite a mesma sintaxe
para escolher entre duas expressões. Isso porque o if-else do Scala serve também
como um substituto para a expressão condicional do Java ... ? ... : ....
Exemplo 4.3.1
scala> def abs(x: Double) = if (x >= 0) x else -x
abs: (Double)Double
Expressões boleanas em Scala são similares as em Java; são formadas a partir de
constantes. true e false, operadores de comparação, negação boleana ! e os
operadores boleanos && and ||.
4.4
Exemplo: Raiz Quadrada pelo Método de Newton
Agora ilustraremos elementos da linguagem intruduzidos até aqui na construção
de um programa mais interessante. A tarefa é escrever um função
def sqrt(x: Double): Double = ...
que computa a raiz quadrada de x.
Um modo comum de se computar raizes quadradas é pelo método das
aproximações sucessivas de Newton. Inicia-se com um palpite inicial y (digamos:
y = 1). Então melhora-se repetidamente o atual palpite y tomando-se a média de y
e x/y. Como um exemplo, as próximas três colunas indicam
p o palpite y, o quociente
x/y, e suas médias para as primeiras aproximações para 2.
1
1.5
1.4167
1.4142
2/1 = 2
2/1.5 = 1.3333
2/1.4167 = 1.4118
...
y
x/y
1.5
1.4167
1.4142
...
(y + x/y)/2
Este algoritmo pode ser implementado em Scala por um conjunto de pequenas
funções, onde cada uma representa um dos elementos do algoritmo.
Primeiro definimos uma função para iterar do palpite para o resultado:
def sqrtIter(guess: Double, x: Double): Double =
if (isGoodEnough(guess, x)) guess
16
Expressões e Funções Simples
else sqrtIter(improve(guess, x), x)
Observe que sqrtIter chama a si mesmo recursivamente. Laços em programas
imperativos podem sempre ser modelados por recursão em programas funcionais.
Observe também que a definição de sqrtIter contém um tipo retorno, que segue
o seção de parâmetros. Tais tipos de retorno são mandatórios para funções
recursivas. Para uma função não recursiva, o tipo de retorno é opcional; se estiver
faltando o verificador de tipos o computará a partir do tipo do lado direito da
função. Entretanto, mesmo para funções não recursivas é sempre boa idéia incluir
um tipo de retorno para melhor documentação.
Como segundo passo, definimos as duas funções chamadas por: sqrtIter: uma
função para melhorar (improve) o palpite e um teste de terminação isGoodEnough.
Aqui estão suas definições.
def improve(guess: Double, x: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double, x: Double) =
abs(square(guess) - x) < 0.001
Finalmente, a própria função sqrt é definida como uma aplicação de sqrtIter.
def sqrt(x: Double) = sqrtIter(1.0, x)
Exercício 4.4.1 O teste isGoodEnough não é muito preciso para pequenos números
e podem levar a não terminação para números muito grandes (por que?). Crie uma
versão diferente para isGoodEnough que não tenham esses problemas.
Exercício 4.4.2 Simule a execução da expressão sqrt(4).
4.5
Aninhamento de Funções
A programação funcional encoraja a construção de muitas pequenas funções
auxiliares. Nos últimos exemplos, a implementação de sqrt faz uso da funções
auxiliares sqrtIter, improve e isGoodEnough. Os nomes destas funções são
relevantes somente para a implementação de sqrt. Normalmente não queremos
que os usuários de sqrt acessem estas funções diretamente.
Nós podemos reforçar isto (e evitar poluição de nomes) incluindo funções auxiliares
dentro das próprias funções:
def sqrt(x: Double) = {
def sqrtIter(guess: Double, x: Double): Double =
if (isGoodEnough(guess, x)) guess
4.5 Aninhamento de Funções
17
else sqrtIter(improve(guess, x), x)
def improve(guess: Double, x: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double, x: Double) =
abs(square(guess) - x) < 0.001
sqrtIter(1.0, x)
}
Neste programa, as chaves { ... } envolvem um bloco. Blocos em Scala são eles
mesmos expressões. Cada bloco termina com um expressão resultado o qual define
seu valor. A expressão resultado pode ser precedida por definições auxiliares, as
quais são visíveis somente no próprio bloco.
Cada definição no bloco pode ser seguida para um ponto e vírgula, o qual separa
esta definição das definições subsequentes ou a expressão resultado. Entretanto,
um ponto e vírgula é inserido implicitamente ao final de cada linha, a não ser que
uma das condições a seguir seja verdadeira.
1. Ou a linha em questão termina com uma palavra tal que um ponto ou um
operador infixo não são legais ao final da expressão.
2. Ou a próxima linha inicia com uma palavra que não pode iniciar uma
expressão.
3. Ou estamos dentro de parênteses (...) ou chaves , porque estes não podem
conter multiplos comandos de qualquer modo.
Entretanto, os seguintes são legais:
def f(x: Int) = x + 1;
f(1) + f(2)
def g1(x: Int) = x + 1
g(1) + g(2)
def g2(x: Int) = {x + 1};
/* ‘;’ mandatorio */ g2(1) + g2(2)
def h1(x) =
x +
y
h1(1) * h1(2)
def h2(x: Int) = (
x
// parenteses mandatorio, senao um ponto e virgula
+ y
// sera inserido apos o ‘x’.
)
h2(1) / h2(2)
18
Expressões e Funções Simples
Scala usa as regras usuais de escopo de bloco estruturado. Um nome definido em
algum outro bloco é também visível em algum bloco interno, desde que não tenha
sido redefinido lá. Esta regra nos permite simplificar nosso exemplo sqrt. Não
precisamos passar x como parâmetro adicional de funções aninhadas, dado que
está sempre visível nelas como um parâmetro da função externa sqrt. Aqui está o
código simplificado:
def sqrt(x: Double) = {
def sqrtIter(guess: Double): Double =
if (isGoodEnough(guess)) guess
else sqrtIter(improve(guess))
def improve(guess: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double) =
abs(square(guess) - x) < 0.001
sqrtIter(1.0)
}
4.6
Recursão de Cauda
Considere a seguinte função para calcular o maior divisor comum entre dois
números dados.
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
Usando nosso modelo de substituição da função de avaliação, gcd(14, 21)
evaluates as follows:
gcd(14, 21)
→
if (21 == 0) 14 else gcd(21, 14 % 21)
→
if (false) 14 else gcd(21, 14 % 21)
→
gcd(21, 14 % 21)
→
gcd(21, 14)
→
if (14 == 0) 21 else gcd(14, 21 % 14)
→ → gcd(14, 21 % 14)
→
gcd(14, 7)
→
if (7 == 0) 14 else gcd(7, 14 % 7)
→ → gcd(7, 14 % 7)
→
gcd(7, 0)
→
if (0 == 0) 7 else gcd(0, 7 % 0)
→ → 7
Contraste isto com a avaliação de uma outra função recursiva, factorial:
def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)
4.6 Recursão de Cauda
19
A aplicação de factorial(5) é reescrita como segue:
→
→
→
→ ... →
→ ... →
→ ... →
→ ... →
→ ... →
→ ... →
factorial(5)
if (5 == 0) 1 else 5 * factorial(5 - 1)
5 * factorial(5 - 1)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * (1 * factorial(0))))
5 * (4 * (3 * (2 * (1 * 1))))
120
Há uma importante diferença entre as duas sentenças reescritas: Os termos na
sequência reescrita de gcd tem repetidamente a mesma forma. Conforme a
avaliação prossegue, seu tamanho é limitado por uma constante. Diferentemente,
na avaliação do fatorial obtemos cadeias cada vez mais longas de operandos que
são então multiplicados na última parte da sequência de avaliação.
Ainda que as atuais implementações de Scala não trabalhem reescrevendo termos,
elas contudo devem ter o mesmo comportamento de espaço que nas sequências
reescritas. Na implementação de gcd, nota-se que a chamada recursiva para gcd é
a última ação realizada na avaliação do seu corpo. Pode-se também dizer que gcd é
uma recursão de cauda (tail-recursive). A última chamada numa função recursiva
de cauda pode ser implementada por um salto ao início da função. Os argumentos
dessa chamada pode sobrescrever os parâmetros da atual instanciação de gcd,
portanto nenhum espaço na pilha é necessário. Consequentemente, funções
recursivas de cauda são processos iterativos, que podem ser executados em espaço
constante.
Em contraste, a chamada recursiva em factorial é seguida por uma multiplicação.
consequentemente, um novo espaço na pilha é alocado para a instância recursiva
de fatorial, e é desalocada após o término daquela instância. A formulação dada
para a função fatorial não é recursiva de cauda; precisa de espaço proporcional aos
seus parâmetros de entrada para sua execução.
Genericamente, se a última ação da função é uma chamada a outra função
(possivelmente a mesma), apenas um único espaço na pilha é requerido para
ambas funções. Tais chamadas são denominadas “tail call”. Em princípio, tail calls
sempre podem reutilizar o espaço da pilha da função de chamada. Entretanto,
alguns ambientes de execução (tais como Java VM) carecem das primitivas para
fazer um espaço de pilha reutilizável para tail calls eficientes. A produção de uma
implementação Scala de qualidade é, portanto, requerida somente para reutilizar
o espaço de pilha de uma função recursiva de cauda cuja última ação é chamar
a si mesma. Outras chamadas de cauda podem ser otimizadas também, mas não
deve-se confiar nisso ao longo das implementações.
20
Expressões e Funções Simples
Exercício 4.6.1 Escreva uma implementação recursiva de cauda de factorial.
Capítulo 5
Funções de Primeira Classe
Uma função em Scala é um valor de primeira classe. Como qualquer outro valor,
pode ser passado como um parâmetro ou retornado como um resultado. Funções
que recebem outras funções como parâmetros ou as retornam como resultados
são denominadas funções de alta ordem. Este capítulo introduz funções de alta
ordem e mostra como elas fornecem um mecanismo flexível para a composição de
programas.
Como um exemplo de motivação, considere as três tarefas relacionadas a seguir:
1. Escreva uma função que some todos os inteiros entre dois dados números, a
e b:
def sumInts(a: Int, b: Int): Int =
if (a > b) 0 else a + sumInts(a + 1, b)
2. Escreva uma função para somar os quadrados de todos os inteiros entre dois
dados números, a e b:
def square(x: Int): Int = x * x
def sumSquares(a: Int, b: Int): Int =
if (a > b) 0 else square(a) + sumSquares(a + 1, b)
3. Escreva uma função para somar as potências 2n de todos os n inteiros entre
dois dados números a e b:
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x - 1)
def sumPowersOfTwo(a: Int, b: Int): Int =
if (a > b) 0 else powerOfTwo(a) + sumPowersOfTwo(a + 1, b)
P
Estas funções são todas instâncias de ba f (n) para diferentes valores de x. Podemos
obter o padrão comum definindo uma função sum:
22
Funções de Primeira Classe
def sum(f: Int => Int, a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f, a + 1, b)
O tipo Int => Int é o tipo de funções que recebem argumentos do tipo Int e
retornam resultados do tipo Int. Então sum é uma função que recebe uma outra
função como parâmetro. Em outras palavras, sum é uma função de alta ordem.
Usando sum, podemos formular as três funções de soma como segue:
def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumSquares(a: Int, b: Int): Int = sum(square, a, b)
def sumPowersOfTwo(a: Int, b: Int): Int = sum(powerOfTwo, a, b)
onde
def id(x: Int): Int = x
def square(x: Int): Int = x * x
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x - 1)
5.1
Funções Anônimas
Parametrização por funções tende a criar várias pequenas funções. No exemplo
anterior, definimos id, square e power como funções separadas, de tal modo que
pudessem ser passadas como argumentos para sum.
Ao invés de usarmos definições de funções nomeadas para estas pequenas funções
argumentos, podemos formulá-las de um modo abreviado como funções anônimas.
Uma função anônima é uma expressão que é avaliada para uma função; a função
é definida sem receber um nome. Como exemplo considere a função anônima
quadrado:
(x: Int) => x * x
A parte anterior a flecha ‘=>’ são os parâmetros da função, ao passo que a parte
seguinte a ‘=>’ é o seu corpo. Por exemplo, aqui está uma função anônima que
multiplica seus dois argumentos.
(x: Int, y: Int) => x * y
Usando funções anônimas, podemos reformular as duas funções soma sem funções
auxiliares nomeadas:
def sumInts(a: Int, b: Int): Int = sum((x: Int) => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum((x: Int) => x * x, a, b)
Frequentemente, o compilador Scala pode deduzir o tipo do parâmetro a partir
do contexto da função anônima nos casos em que foram omitidos. Por exemplo,
5.2 Currying
23
no caso de sumInts ou sumSquares, sabe-se a partir do tipo de sum que o primeiro
parâmetro deve ser uma função de tipo Int => Int. Consequentemente, o tipo do
parâmetro Int é redundante e pode ser omitido. Se houver um único parâmetro
sem um tipo, também podemos omitir os parâmetros a sua volta.
def sumInts(a: Int, b: Int): Int = sum(x => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum(x => x * x, a, b)
Em geral, o termo em Scala (x1 : T1 , ..., xn : Tn ) => E define uma função que
mapeia seus parâmetros x1 , ..., xn ao resultado da expressão E (onde E pode
referir-se a x1 , ..., xn ). Funções anônimas não são elementos essenciais da
linguagem Scala, dado que sempre podem ser expressos em termos de funções
nomeadas. De fato, a função anônima
(x1 : T1 , ..., xn : Tn ) => E
é equivalente ao bloco
{ def f (x1 : T1 , ..., xn : Tn ) = E ; f _ }
onde f é um novo nome que não é utilizado em qualquer outro lugar do programa.
Também dizemos que funções anônimas são “syntactic sugar”.
5.2
Currying
A última formulação das funções de soma já são bem compactas. Mas podemos
fazer ainda melhor. Observe que a e b aparecem como parâmetros e argumentos
de cada função, mas não parecem tomar parte de combinações interessantes. Há
algum modo de nos livrarmos delas?
Vamos tentar reescrever sum de tal modo que não receba os limites a e b como
parâmetros:
def sum(f: Int => Int): (Int, Int) => Int = {
def sumF(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sumF(a + 1, b)
sumF
}
Nessa formulação, sum é uma função que retorna uma outra função,
especificamente a função especializada soma sumF. Esta última função realiza
todo o trabalho; recebe os limites a e b como parâmetros, aplica a função f,
parâmetro de sum, a todos os inteiros entre eles, e soma os resultados.
Usando esta nova formulação de sum, podemos agora definir:
def sumInts
=
sum(x => x)
24
Funções de Primeira Classe
def sumSquares = sum(x => x * x)
def sumPowersOfTwo = sum(powerOfTwo)
Ou, equivalentemente, com definições de valores:
val sumInts = sum(x => x)
val sumSquares = sum(x => x * x)
val sumPowersOfTwo = sum(powerOfTwo)
sumInts, sumSquares, e sumPowersOfTwo podem ser aplicados como qualquer outra
função. Por exemplo,
scala> sumSquares(1, 10) + sumPowersOfTwo(10, 20)
unnamed0: Int = 2096513
Como funções que retornam funções são aplicadas? Como exemplo, na expressão
sum(x => x * x)(1, 10) ,
a função sum é aplicada a função quadrada (x => x * x). O função resultante é
então aplicada ao segunda lista de argumentos, (1, 10).
Essa notação é possível porque aplicações de funções são associativas à esquerda.
Ou seja, se args1 e args2 são listas de argumentos, então
f (args1 )(args2 )
é equivalente a
( f (args1 ))(args2 )
Em nosso exemplo, sum(x => x * x)(1, 10) é equivalente a seguinte expressão:
(sum(x => x * x))(1, 10).
O estilo “funções que retornam funções” é tão útil que Scala tem sintaxe especial
para ele. Por exemplo, a próxima definição de sum é equivalente a anterior, porém
mais curta:
def sum(f: Int => Int)(a: Int, b: Int): Int =
if (a > b) 0 else f(a) + sum(f)(a + 1, b)
Genericamente, uma definição de função currificada
def f (args1 ) ... (argsn ) = E
onde n > 1 expande para
def f (args1 ) ... (argsn−1 ) = { def g (argsn ) = E ; g }
onde g é um novo identificador. Ou, menor, usando uma função anônima:
def f (args1 ) ... (argsn−1 ) = ( argsn ) => E .
Realizando este passo n vezes dá aquela
5.3 Exemplo: Encontrando Pontos Fixos de Funções
25
def f (args1 ) ... (argsn ) = E
é equivalente a
def f = (args1 ) => ... => (argsn ) => E .
Ou, equivalentemente, usando uma definição valor:
val f = (args1 ) => ... => (argsn ) => E .
Este estilo de definição de função e aplicação é chamado currificado depois que seu
divulgador, Haskell B. Curry, um lógico do século 20, mesmo que a idéia nos leve de
volta a Moses Schönfinkel e Gottlob Frege.
O tipo de uma função que retorna função é expresso de modo análogo a sua lista de
parâmetros. Tomando a última formulação de sum como exemplo, o tipo para sum é
(Int => Int) => (Int, Int) => Int. Isso é possível porque tipos de funções são
associativos à direita. Ou seja,
T1 => T2 => T3
is equivalent to
T1 => (T2 => T3 )
Exercício 5.2.1 1. A função sum usa uma recursiva linear. Você poderia alterá-la
para uma função recursiva de cauda, preenchendo as lacunas marcadas com ’??’
abaixo?
def sum(f: Int => Int)(a: Int, b: Int): Int = {
def iter(a: Int, result: Int): Int = {
if (??) ??
else iter(??, ??)
}
iter(??, ??)
}
Exercício 5.2.2 Escreva uma função produto que computa o produto de valores de
funções em pontos sobre um dado intervalo.
Exercício 5.2.3 Escreva fatorial em termos de produto.
Exercício 5.2.4 Escreva uma função ainda mais genérica que generaliza ambos sum
e produto.
5.3
Exemplo: Encontrando Pontos Fixos de Funções
Um número x é chamado um ponto fixo de uma função f se
26
Funções de Primeira Classe
f(x) = x .
Para algumas funções f podemos encontrar os pontos fixos iniciando com um
palpite inicial e então aplicando f repetidamente, até que o valor não mude mais
(ou a mudança seja tolerável). Isso é possível na sequência
x, f(x), f(f(x)), f(f(f(x))), ...
converge para pontos fixos de f . Essa idéia é captada na “função achadora de
pontos fixos” a seguir:
val tolerance = 0.0001
def isCloseEnough(x: Double, y: Double) = abs((x - y) / x) < tolerance
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}
Agora aplicaremos esta idéia na reformulação da função raiz quadrada. Vamos
começar pela especificação de sqrt:
sqrt(x)
=
=
the y such that
the y such that
y * y = x
y = x / y
Consequentemente, sqrt(x) é um ponto fixo da função y => x / y. Isso sugere
que sqrt(x) pode ser computado por uma iteração de ponto fixo:
def sqrt(x: double) = fixedPoint(y => x / y)(1.0)
Mas se tentarmos isso, percebemos que aquela computação não converge. Vamos
agregar à função de ponto fixo um comando print que mostra o valor corrente de
guess:
def fixedPoint(f: Double => Double)(firstGuess: Double) = {
def iterate(guess: Double): Double = {
val next = f(guess)
println(next)
if (isCloseEnough(guess, next)) next
else iterate(next)
}
iterate(firstGuess)
}
5.3 Exemplo: Encontrando Pontos Fixos de Funções
27
Então, sqrt(2) dá:
2.0
1.0
2.0
1.0
2.0
...
Um modo de controlar tais oscilações é prevenir guess de mudar muito. Isso
pode ser obtido pela média (função averaging) de sucessivos valores da sequência
original:
scala> def sqrt(x: Double) = fixedPoint(y => (y + x/y) / 2)(1.0)
sqrt: (Double)Double
scala> sqrt(2.0)
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.4142135623746899
De fato, expandindo a função fixedPoint dá exatamente nossa prévia definição de
ponto fixo da Seção 4.4.
Os exemplos anteriores mostraram que o poder de expressividade de uma
linguagem é consideravelmente aumentado se funções puderem ser passadas
como argumentos. O próximo exemplo mostra que funções que retornam funções
também podem ser muito úteis.
p
Considere novamente iterações de ponto fixo. Começamos observando que (x) é
um ponto fixo da função y => x / y. Então fazemos a iteração convergir tirando a
média de sucessivos valores. Essa técnica de amortecimento da média é tão genérica
que pode ser denotada em outra função.
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
Usando averageDamp, podemos reformular a função da raiz quadrada como segue.
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
Isto expressa os elementos do algoritmo tão claramente quanto possível.
Exercício 5.3.1 Escreva uma função para a raiz cúbica usando fixedPoint e
averageDamp.
28
Funções de Primeira Classe
5.4
Sumário
Vimos no capítulo anterior que funções são abstrações essenciais porque
nos permitem introduzir métodos genéricos de computação como explícitos,
elementos nomeados em nossa linguagem de programação. O presente capítulo
mostrou que tais abstrações podem ser combinados por funções de alta ordem para
criar mais abstrações. Como programadores, devemos procurar por oportunidades
de reuso e abstração. O mais alto nível possível de abstração nem sempre é o
melhor, mas é importante saber técnicas de abstração, de modo que possamos
usá-las quando apropriado.
5.5
Elementos da Linguagem Vistos Até Aqui
Os capítulos 4 e 5 trataram elementos da linguagem Scala para expressar tipos e
expressões relacionados a tipos primitivos e funções. A sintaxe livre de contexto
desses elementos da linguagem são dados abaixo em formato Backus-Naur
estendido, onde ‘|’ denotam alternativas, [...] denotam opção (0 ou 1 ocorrência),
e {...} denotam (0 ou mais ocorrências).
Caracteres
Programas em Scala são sequência de caracteres (Unicode).
seguintes conjuntos de caracteres.
Distinguimos os
• espaço em branco, tal como ‘’, tabulação, ou caracter de mudança de linha
(newline),
• letras ‘a’ a ‘z’, ‘A’ a ‘Z’,
• digitos ‘0’ a ‘9’,
• caracteres delimitadores
.
,
;
(
)
{
}
[
]
\
"
’
• caracteres operadores, tal como ‘#’, ‘+’ e ‘:’. Essencialmente, há caracteres
imprimíveis que não estão em nenhum dos conjuntos de caracteres acima.
Lexemas:
ident
literal
=
|
|
=
letter {letter | digit}
operator { operator }
ident ’_’ ident
“como em Java”
5.5 Elementos da Linguagem Vistos Até Aqui
29
Literais são como em Java. Eles definem números, caracteres, cadeias de
caracteres, ou valores boleanos. Exemplos de literais tais como 0, 1.0e10, ’x’,
"ele disse "oi!"", ou true.
Identificadores podem ter duas formas. Eles ou iniciam por uma letra, que é seguida
por uma sequência (possivelmente vazia) de letras ou símbolos, ou podem iniciar
com um caracter operador, seguido por uma sequência (possivelmente vazia) de
caracteres operadores. Ambas as formas podem conter caracteres “underscore” ‘_’.
Além disso, um caracter underscore pode ser seguido por quaisquer identificadores.
Consequentemente, todos a seguir são identificadores legais:
x
Room10a
+
--
foldl_:
+_vector
Segue desta regra que identificadores operadores subsequentes precisam ser
separados por espaço em branco. Por exemplo, a entrada x+-y é entendida como
a sequência de três “tokens” x, +- e y. Se desejamos expressar a soma de x com o
valor negativo de y, precisamos acrescentar no mínimo um espaço, ou seja, x+ -y.
O caracter $ é reservado para identificadores gerados pelo compilador; não devem
ser usados em programas fontes.
Os seguintes são palavras reservadas, e não devem ser usadas como identificadores:
abstract
do
finally
match
package
sealed
try
while
_
:
case
else
for
new
private
super
true
with
=
=>
catch
extends
if
null
protected
this
type
yield
<<:
<%
class
false
implicit
object
requires
throw
val
>:
def
final
import
override
return
trait
var
#
@
Types:
Type
FunctionType
SimpleType
=
=
=
Types
=
SimpleType | FunctionType
SimpleType ’=>’ Type | ’(’ [Types] ’)’ ’=>’ Type
Byte | Short | Char | Int | Long | Float | Double |
Boolean | Unit | String
Type {‘,’ Type}
Tipos podem ser:
• tipos numéricos Byte, Short, Char, Int, Long, Float and Double (com em
Java),
• o tipo Boolean com valores true e false,
• o tipo Unit com o único valor (),
30
Funções de Primeira Classe
• o tipo String,
• tipos função, tal como (Int, Int) => Int ou String => Int => String.
Expressões:
Expr
InfixExpr
Operator
PrefixExpr
SimpleExpr
FunctionExpr
Bindings
Binding
Block
=
=
=
=
=
=
=
=
=
InfixExpr | FunctionExpr | if ’(’ Expr ’)’ Expr else Expr
PrefixExpr | InfixExpr Operator InfixExpr
ident
[’+’ | ’-’ | ’!’ | ’~’ ] SimpleExpr
ident | literal | SimpleExpr ’.’ ident | Block
(Bindings | Id) ’=>’ Expr
‘(’ Binding {‘,’ Binding} ‘)’
ident [’:’ Type]
’{’ {Def ’;’} Expr ’}’
Expressões podem ser:
• identificadores tais como x, isGoodEnough, *, ou +-,
• literais, tais como 0, 1.0, ou "abc",
• Seleções de campo e método, tal como System.out.println,
• aplicações de função, tal como sqrt(x),
• aplicações de operador, tais como -x ou y + x,
• condicionais, tal como if (x < 0) -x else x,
• blocos, tal como { val x = abs(y) ; x * 2 },
• funções anônimas, tais como x => x + 1 ou (x: Int, y: Int) => x + y.
Definições:
Def
FunDef
ValDef
Parameters
Parameter
=
=
=
=
=
FunDef | ValDef
’def’ ident {’(’ [Parameters] ’)’} [’:’ Type] ’=’ Expr
’val’ ident [’:’ Type] ’=’ Expr
Parameter {’,’ Parameter}
ident ’:’ [’=>’] Type
Definições podem ser:
• definições de função tal como def square(x: Int): Int = x * x,
• definições de valor tal como val y = square(2).
Capítulo 6
Classes e Objetos
Scala não tem um tipo primitivo para números racionais, mas é fácil definir um,
usando uma classe. Aqui está uma possível implementação.
class Rational(n: Int, d: Int) {
private def gcd(x: Int, y: Int): Int = {
if (x == 0) y
else if (x < 0) gcd(-x, y)
else if (y < 0) -gcd(x, -y)
else gcd(y % x, x)
}
private val g = gcd(n, d)
val numer: Int = n/g
val denom: Int = d/g
def +(that: Rational) =
new Rational(numer * that.denom + that.numer * denom,
denom * that.denom)
def -(that: Rational) =
new Rational(numer * that.denom - that.numer * denom,
denom * that.denom)
def *(that: Rational) =
new Rational(numer * that.numer, denom * that.denom)
def /(that: Rational) =
new Rational(numer * that.denom, denom * that.numer)
}
Isso define Rational como uma classe que recebe dois argumentos construtores n
e d, contendo as partes numéricas do numerador e denominador. A classe provê
campos que retornam estas partes, bem como métodos para a aritmética sobre
números racionais. Cada método aritmético recebe como parâmetro o operando
direito da operação. O operando esquerdo da operação sempre é o número racional
32
Classes e Objetos
do método cujo é membro.
Membros Privados. A implementação dos números racionais define um método
privado gcd que computa o maior denominador comum de dois inteiros, bem
como um campo privado g que contém o gcd dos argumentos construtores.
Esses membros são inacessíveis de fora da classe Rational.
São usados
na implementação da classe para eliminar fatores comuns nos argumentos
construtores para garantir que o numerador e o denominador estejam sempre em
forma normalizada.
Criando e Acessando Objetos. Como um exemplo de como os números racionais
podem ser usados, aqui está um programa que imprime a soma de todos os
números 1/i onde i está no intervalo de 1 a 10.
var i = 1
var x = new Rational(0, 1)
while (i <= 10) {
x += new Rational(1, i)
i += 1
}
println("" + x.numer + "/" + x.denom)
O + recebe como operando esquerdo uma cadeia de caracteres e como operando
direito um valor de tipo arbitrário. Retorna o resultado de converter seu operando
direito em uma cadeia de caracteres e concatená-la a seu operando esquerdo.
Herança e Sobrecarga. Cada classe em Scala tem uma superclasse que ela
estende. Se uma classe não menciona sua superclasse em sua definição, o tipo
básico scala.AnyRef é implicitamente assumido (para implementações Java, este
tipo é um apelido (alias) para java.lang.Object. Por exemplo, a classe Rational
pode ser equivalentemente definida como
class Rational(n: Int, d: Int) extends AnyRef {
... // como antes
}
Uma classe herda todos os membros de sua superclasse.
Pode também
redefinir (ou: sobrescrever) alguns membros herdados. Por exemplo, a classe
java.lang.Object define um método toString que retorna uma representação do
objeto como cadeia de caracteres (string):
class Object {
...
def toString: String = ...
}
33
A implementação de toString em Object forma uma string que consiste do nome
da classe do objeto e um número. Faz sentido redefinir este método para objetos
que são números racionais:
class Rational(n: Int, d: Int) extends AnyRef {
... // como antes
override def toString = "" + numer + "/" + denom
}
Observe que, diferentemente de Java, definições que redefinem precisam ser
precedidas por um modificador override.
Se a classe A estende a classe B , então objetos do tipo A podem ser usados sempre
que objetos do tipo B são esperados. Nesse caso dizemos que o tipo A está em
conformidade com o tipo B . Por exemplo, Rational está em conformidade com
AnyRef, logo é legal atribuir um valor Rational à variável do tipo AnyRef:
var x: AnyRef = new Rational(1, 2)
val r = new Rational(1,2)
System.out.println(r.toString);
// imprime ‘‘1/2’’
Distintamente de Java, métodos em Scala não necessariamente precisam receber
uma lista de parâmetros. Um exemplo é o método abaixo square. Este método é
invocado simplesmente mencionando seu nome.
class Rational(n: Int, d: Int) extends AnyRef {
... // como antes
def square = new Rational(numer*numer, denom*denom)
}
val r = new Rational(3, 4)
println(r.square)
// imprime ‘‘9/16’’*
Ou seja, métodos sem parâmetros são acessados como campos valor, tais como
numer são. A diferença entre valores e métodos sem parâmetros reside em suas
definições. O lado direito de um valor é avaliado quando o objeto é criado, e o valor
não muda depois. Um lado direito de um método sem parâmetros, por outro lado,
é avaliado cada vez que o método é chamado. O acesso uniforme dos campos de
métodos sem parâmetros resulta em crescente flexibilidade para o implementador
de uma classe. Frequentemente, um campo em uma versão da classe torna-se um
valor computado na próxima versão. O acesso uniforme garante que clientes não
tenham de ser reescritos por conta desta mudança.
34
Classes e Objetos
Classes Abstratas. Considere a tarefa de escrever uma classe para conjuntos de
números inteiros com duas operações, incl e contains. (s incl x) deve retornar
um novo conjunto que contém o elemento x juntamente com todos os elementos
do conjunto s. (s contains x) deve retornar true se o conjunto s contiver o
elemento x, e deve retornar false, caso contrário. A interface para tais conjuntos é
dada por:
abstract class IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
}
IntSet é tido como uma classe abstrata. Isso tem duas consequências. Primeiro,
classes abstratas podem ter membros protelados (deferred) que são declarados,
mas que não tem uma implementação. No nosso caso, ambos incl e contains
são tais membros. Segundo, porque uma classe abstrata pode ter membros não
implementados, nenhum objeto daquela classe pode ser criado usando new. Em
contraste, uma classe abstrata pode ser usada como uma classe base de alguma
outra classe, que implementa os membros que foram postergados.
Traits.
Ao invés de classe abstrata frequentemente usa-se a palavra chave
trait em Scala. Traits são classes abstratas que desejamos adicionar a alguma
outra classe. Isso pode ser porque um trait adiciona alguns métodos ou campos
para uma classe pai desconhecida. Por exemplo, um trait Bordered pode ser usado
para adicionar uma borda a vários componentes gráficos. Um outro cenário de
uso ocorre quando o trait coleta assinaturas de alguma funcionalidade provida por
diferentes classes, do mesmo modo que uma interface Java faria.
Como IntSet pertence a esta categoria, pode-se alternativamente definí-la como
um trait:
trait IntSet {
def incl(x: Int): IntSet
def contains(x: Int): Boolean
}
Implementando Classes Abstratas. Vamos dizer que planejamos implementar
conjuntos como árvores binárias. Há duas possíveis formas de árvores. Uma árvore
para o conjunto vazio, e uma árvore consistindo de um inteiro e duas subárvores.
Aqui estão suas implementações:
class EmptySet extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
}
35
class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
def contains(x: Int): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: Int): IntSet =
if (x < elem) new NonEmptySet(elem, left incl x, right)
else if (x > elem) new NonEmptySet(elem, left, right incl x)
else this
}
Ambos EmptySet e NonEmptySet estendem a classe IntSet. Isso implica que tipos
EmptySet e NonEmptySet estão em conformidade com o tipo IntSet – um valor do
tipo EmptySet ou NonEmptySet pode ser usado sempre que um valor do tipo IntSet
é requerido.
Exercício 6.0.1 Escreva os métodos uniao e intersecao para formar a união e
interseção entre dois conjuntos.
Exercício 6.0.2 Adicione um método
def excl(x: Int)
para retornar um dado conjunto sem o elemento x. Para isso, é interessante
também implementar um método teste
def isEmpty: Boolean
para conjuntos.
Ligação Dinâmica. Linguagens orientadas a objetos (inclusive Scala) usam
despacho dinâmico para invocações de métodos. Ou seja, o código invocado por
uma chamada de método depende do tipo em tempo de execução do objeto que
contém o método. Por exemplo, considere a expressão s contains 7 onde s é
um valor do tipo declarado s: IntSet. Qual código para contains é executado
depende do tipo do valor de s em tempo de execução. Se for um valor EmptySet, é
a implementação de contains na classe EmptySet que é executada, e analogamente
para valores NonEmptySet. Este comportamento é consequência direta do nosso
modelo de substituição da avaliação. Por exemplo,
(new EmptySet).contains(7)
->
(substituindo contains pelo seu corpo na classe EmptySet)
36
Classes e Objetos
false
Ou,
new NonEmptySet(7, new EmptySet, new EmptySet).contains(1)
(substituindo contains pelo seu corpo na classe NonEmptySet)
->
if (1 < 7) new EmptySet contains 1
else if (1 > 7) new EmptySet contains 1
else true
(reescrevendo o condicional)
->
new EmptySet contains 1
(substituindo contains pelo seu corpo na classe EmptySet)
->
false .
Envio dinâmico de métodos é análogo a chamadas para funções de alta ordem. Em
ambos os casos, a identidade do código a ser executado é conhecida somente em
tempo de execução. Essa similaridade não é apenas superficial. Na verdade, Scala
representa cada valor de função como um objeto (veja Seção 8.6).
Objetos. Na implementação prévia de conjuntos de inteiros, conjuntos vazios
eram expressos com new EmptySet; então um novo objeto era criado a cada vez que
um valor conjunto vazio era requerido. Podemos evitar criações desnecessárias de
objetos definindo um valor empty uma vez e então, usando este valor ao invés de
cada ocorrência de new EmptySet. Por exemplo:
val EmptySetVal = new EmptySet
Um problema com esse tratamento é que uma definição de valor tal como a anterior
não é uma definição top-level legal em Scala; tem de ser parte de uma outra classe
ou objeto. Ainda, a definição de classe EmptySet agora parece um pouco exagerada
– por que definir uma classe de objetos, se somente estamos interessados em um
único objeto dessa classe? Um tratamento mais direto é usar uma definição de
objeto. Aqui está uma alternativa mais adequada para a definição de conjunto vazio:
object EmptySet extends IntSet {
def contains(x: Int): Boolean = false
def incl(x: Int): IntSet = new NonEmptySet(x, EmptySet, EmptySet)
}
37
A sintaxe de uma definição de objeto segue a sintaxe da definição de uma classe;
tem uma cláusula opcional extends, bem como um corpo opcional. Assim como
em classes, a cláusula extends define membros herdados do objeto considerando
que o corpo define novos membros ou sobrecarga. Entretanto, uma definição de
objeto denota um único objeto somente se não for possível criar outros objetos com
a mesma estrutura usando new. Então, definições de objeto também carecem de
parâmetros construtores, que podem estar presentes nas definições das classes.
Definições de objetos podem aparecer em qualquer lugar em um programa Scala;
incluindo o top-level. Como não há ordem fixa de execução de entidades top-level
em Scala, pode-se questionar quando exatamente o objeto definido pela definição
de objeto é criado e inicializado. A resposta é que o objeto é criado assim que seus
membros são acessados. Esta estratégia é chamada avaliação preguiçosa.
Classes Padrão. Scala é uma linguagem orientada a objetos pura. Isso significa
que cada valor em Scala pode ser visto como um objeto. De fato, mesmo tipos
primitivos tais como int ou boolean não são tratados de modo especial. São
definidos como apelidos de tipos de classes Scala no módulo Predef.
type boolean = scala.Boolean
type int = scala.Int
type long = scala.Long
...
Por eficiência, o compilador geralmente representa valor de tipo scala.Int por
inteiros de 32 bits, valores de tipo scala.Boolean por boleanos Java etc. Mas
converte essas representações especializadas para objetos quando requeridos,
por exemplo, quando um valor primitivo Int é passada a uma função com
um parâmetro de tipo AnyRef. Consequentemente, a representação de valores
primitivos é apenas uma otimização, não muda o significado de um programa.
Aqui está a especificação da classe Boolean.
package scala
abstract class Boolean {
def && (x: => Boolean): Boolean
def || (x: => Boolean): Boolean
def !
: Boolean
def
def
def
def
def
def
}
==
!=
<
>
<=
>=
(x:
(x:
(x:
(x:
(x:
(x:
Boolean)
Boolean)
Boolean)
Boolean)
Boolean)
Boolean)
:
:
:
:
:
:
Boolean
Boolean
Boolean
Boolean
Boolean
Boolean
38
Classes e Objetos
Boleanos podem ser definidos usando somente classes e objetos, sem referência ao
tipos básicos para boleanos ou números. Uma possível implementação da claro
Boolean é dada abaixo. Esta não é a implementação atual na biblioteca padrão
Scala. Por razões de eficiência a implementação padrão usa boleanos primitivos.
package scala
abstract class Boolean {
def ifThenElse(thenpart: => Boolean, elsepart: => Boolean)
def && (x: => Boolean): Boolean
def || (x: => Boolean): Boolean
def !
: Boolean
def
def
def
def
def
def
==
!=
<
>
<=
>=
(x:
(x:
(x:
(x:
(x:
(x:
Boolean)
Boolean)
Boolean)
Boolean)
Boolean)
Boolean)
:
:
:
:
:
:
Boolean
Boolean
Boolean
Boolean
Boolean
Boolean
=
=
=
ifThenElse(x, false)
ifThenElse(true, x)
ifThenElse(false, true)
=
=
=
=
=
=
ifThenElse(x, x.!)
ifThenElse(x.!, x)
ifThenElse(false, x)
ifThenElse(x.!, false)
ifThenElse(x, true)
ifThenElse(true, x.!)
}
case object True extends Boolean {
def ifThenElse(t: => Boolean, e: => Boolean) = t
}
case object False extends Boolean {
def ifThenElse(t: => Boolean, e: => Boolean) = e
}
Aqui está uma especificação parcial da classe Int.
package scala
abstract class Int extends AnyVal {
def toLong: Long
def toFloat: Float
def toDouble: Double
def
def
def
def
+
+
+
+
(that:
(that:
(that:
(that:
Double): Double
Float): Float
Long): Long
Int): Int
// analogo para -, *, /, %
def << (cnt: Int): Int
// analogo para
def & (that: Long): Long
def & (that: Int): Int
// analogo para |, ^
def == (that: Double): Boolean
def == (that: Float): Boolean
>>, >>>
39
def == (that: Long): Boolean
// analogo para !=, <, >, <=, >=
}
A classe Int pode em princípio também ser implementada usando apenas objetos
e classes, sem referência a um tipo construído para inteiros. Para ver como,
vamos considerar um problema um pouco mais simples, especificamente como
implementar um tipo Nat de números naturais, ou seja, inteiros não negativo. Aqui
está uma definição para uma classe abstrata Nat:
abstract class Nat {
def isZero: Boolean
def predecessor: Nat
def successor: Nat
def + (that: Nat): Nat
def - (that: Nat): Nat
}
Para implementar as operações da classe Nat, nós definimos um sub-objeto Zero
e uma subclasse Succ (para sucessor). Cada número N é representado como N
aplicações do construtor Succ até zero:
new Succ( ... new Succ (Zero) ... )
{z
}
|
N times
A implementação do objeto Zero é direta:
object Zero extends Nat {
def isZero: Boolean = true
def predecessor: Nat = error("negative number")
def successor: Nat = new Succ(Zero)
def + (that: Nat): Nat = that
def - (that: Nat): Nat = if (that.isZero) Zero
else error("negative number")
}
A implementação das funções predecessor e subtração sobre Zero leva a um Erro,
que aborta o programa com uma mensagem de erro.
Aqui está uma implementação da classe sucessor:
class
def
def
def
def
def
}
Succ(x: Nat) extends Nat {
isZero: Boolean = false
predecessor: Nat = x
successor: Nat = new Succ(this)
+ (that: Nat): Nat = x + that.successor
- (that: Nat): Nat = if (that.isZero) this
else x - that.predecessor
40
Classes e Objetos
Observe a implementação do método successor. Para criar o sucessor de um
número, precisamos passar o próprio objeto como um argumento para o construtor
Succ. O próprio objeto é referenciado por uma palavra reservada this.
As implementações de + e -, cada uma contém uma chamada recursiva com o
argumento do costrutor como destinatário. A recursão terminará assim que o
destinatário for o objeto Zero (o que é garantido de acontecer eventualmente dado
o modo com que os números são formados).
Exercício 6.0.3 Escreva uma implementação Integer dos números inteiros. A
implementação deve suportar todas as operações da classe Nat e mais dois
métodos.
def isPositive: Boolean
def negate: Integer
O primeiro método deve retornar true se o número for positivo. O segundo método
deve negativar o número. Não utilize qualquer classe numérica padrão Scala em
sua implementação. (Dica: Há duas formas para implementar Integer. Uma pode
ou fazer uso da implementação existente de Nat, representando um inteiro como
um número natural e um sinal. Ou pode-se generalizar a implementação dada
de Nat para Integer, usando as três subclasses Zero para 0, Succ para números
positivos e Pred para números negativos.
Elementos da Linguagem Introduzidos Neste Capítulo
Types:
Type
= ...
|
ident
Tipos podem agora ser identificadores arbitrários que representam classes.
Expressões:
Expr
= ...
|
Expr ’.’ ident
|
’new’ Expr
|
’this’
Uma expressão pode agora ser uma criação de objeto, ou uma seleção E.m de um
membro m a partir de uma expressão valorada objeto E, ou pode ser a palavra
reservada this.
Definições e Declarações
Def
ClassDef
TraitDef
ObjectDef
= FunDef | ValDef | ClassDef | TraitDef | ObjectDef
= [’abstract’] ’class’ ident [’(’ [Parameters] ’)’]
[’extends’ Expr] [‘{’ {TemplateDef} ‘}’]
= ’trait’ ident [’extends’ Expr] [’{’ {TemplateDef} ’}’]
= ’object’ ident [’extends’ Expr] [’{’ {ObjectDef} ’}’]
41
TemplateDef
ObjectDef
Modifier
Dcl
FunDcl
ValDcl
=
=
=
=
=
=
[Modifier] (Def | Dcl)
[Modifier] Def
’private’ | ’override’
FunDcl | ValDcl
’def’ ident {’(’ [Parameters] ’)’} ’:’ Type
’val’ ident ’:’ Type
Uma definição pode agora ser uma definição de classe, trait ou objeto, tal como
class C(params) extends B { defs }
trait T extends B { defs }
object O extends B { defs }
As definições defs na classe, trait ou objeto podem ser precedidas pelos
modificadores private ou override.
Classes abstratas e traits podem também conter declarações. Isso introduz funções
deferred (postergadas) ou valores com seus tipos, mas não dão uma implementação.
Membros deferred devem ser implementados nas subclasses antes que objetos de
uma classe abstrata ou trait sejam criados.
Capítulo 7
Classes Case e Casamento de
Padrões
Digamos, queremos escrever um interpretador para expressões aritméticas. Para
deixar as coisas simples inicialmente, vamos nos restringir somente a números e
operações +. Tais expressões podem ser representadas como hierarquia de classes,
com uma classe abstrata base Expr como raiz, e duas subclasses Number e Sum.
Então, uma expressão 1 + (3 + 7) é representada como
new Sum(new Number(1), new Sum(new Number(3), new Number(7)))
Agora, um avaliador de uma expressão como esta precisa saber de qual forma ela
é (ou Sum ou Number) e também precisa acessar os componentes da expressão. A
implementação a seguir provê todos os métodos necessários.
abstract class Expr {
def isNumber: Boolean
def isSum: Boolean
def numValue: Int
def leftOp: Expr
def rightOp: Expr
}
class Number(n: Int) extends Expr {
def isNumber: Boolean = true
def isSum: Boolean = false
def numValue: Int = n
def leftOp: Expr = error("Number.leftOp")
def rightOp: Expr = error("Number.rightOp")
}
class Sum(e1: Expr, e2: Expr) extends Expr {
def isNumber: Boolean = false
44
Classes Case e Casamento de Padrões
def
def
def
def
isSum: Boolean = true
numValue: Int = error("Sum.numValue")
leftOp: Expr = e1
rightOp: Expr = e2
}
Com esta classificação e métodos de acesso, escrever uma função avaliador é
simples:
def eval(e: Expr): Int = {
if (e.isNumber) e.numValue
else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
else error("unrecognized expression kind")
}
Entretanto, definir todos esses métodos dentro das classes Sum e Number é um tanto
quanto tedioso. Além do mais, o problema fica ainda pior se desejarmos adicionar
novas formas de expressões. Por exemplo, considere adicionar uma nova forma
de expressão Prod para produtos. Não apenas teremos de implementar uma nova
classe Prod, com todos os métodos de acesso e classificação prévios; também
teremos de introduzir um novo método abstrato isProduct dentro da classe Expr
e implementar aquele método na subclasse Number, Sum, e Prod. Ter de modificar
código existente quando um sistema cresce é sempre problemático, pois introduz
problemas de versão e manutenção.
A promessa da programação orientada a objetos é que tais modificações são
desnecessárias, dado que podem ser evitadas pela reutilização de código existente
e não modificado, através da herança. De fato, uma decomposição mais orientada
a objetos para nosso problema resolve a questão. A idéia é tornar a operação de alto
nível eval um método para cada classe expressão, ao invés de implementá-lo como
uma função fora da hierarquia de classes expressões, como fizemos anteriormente.
Como eval é agora um membro de todos os nós de expressão, quaisquer métodos
de classificação e acesso tornam-se supérfluos, e a implementação é simplificada
consideravelmente:
abstract class Expr {
def eval: Int
}
class Number(n: Int) extends Expr {
def eval: Int = n
}
class Sum(e1: Expr, e2: Expr) extends Expr {
def eval: Int = e1.eval + e2.eval
}
45
Além disso, adicionar uma nova classe Prod não leva a qualquer mudança ao código
existente:
class Prod(e1: Expr, e2: Expr) extends Expr {
def eval: Int = e1.eval * e2.eval
}
A conclusão que tiramos deste exemplo é que a decomposição orientada a objetos
é a técnica de escolha para a construção de sistemas que devem ser estensíveis
com novos tipos de dados. Mas há também um outro possível modo para
estender a expressão exemplo. Podemos querer adicionar novas operações sobre
expressões. Por exemplo, podemos querer adicionar uma operação que imprime
uma árvore-expressão para a saída padrão.
Se definimos todos os métodos de classificação e acesso, tal operação pode ser
facilmente escrita como uma função externa. Aqui está um exemplo:
def print(e: Expr) {
if (e.isNumber) Console.print(e.numValue)
else if (e.isSum) {
Console.print("(")
print(e.leftOp)
Console.print("+")
print(e.rightOp)
Console.print(")")
} else error("unrecognized expression kind")
}
Entretanto, se optamos por uma decomposição orientada a objetos das expressões,
precisaremos adicionar um novo procedimento print para cada classe:
abstract class Expr {
def eval: Int
def print
}
class Number(n: Int) extends Expr {
def eval: Int = n
def print { Console.print(n) }
}
class Sum(e1: Expr, e2: Expr) extends Expr {
def eval: Int = e1.eval + e2.eval
def print {
Console.print("(")
print(e1)
Console.print("+")
print(e2)
Console.print(")")
46
Classes Case e Casamento de Padrões
}
}
Consequentemente, decomposição orientada a objetos clássica requer modificação
de todas as classes existentes quando um sistema for estendido com novas
operações.
Ainda como uma outra forma, podemos querer estender o interpretador. Considere
a simplificação de expressões. Por exemplo, podemos querer criar uma função que
reescreve expressões da forma a * b + a * c para a * (b + c). Esta operação
requer inspeção de mais de um nó para a árvore de expressões ao mesmo tempo.
Consequentemente, não pode ser implementada por um método dentro de cada
tipo de expressão, a não ser que tal método também possa inspecionar outros nós.
Portanto somos forçados a ter métodos de acesso e classificação neste caso. Isto
parece nos levar para a casa inicial, com todos os problemas de estensibilidade e
expressividade.
Olhando mais de perto, observa-se que o único propósito das funções de acesso
e classificação é reverter o processo de construção de dados. Elas nos permitem
determinar, primeiro, qual subclasse de uma classe base abstrata foi usada e,
segundo, quais foram os argumentos construtores. Como essa situação é bem
comum, Scala tem um modo de automatizá-lo para classes case.
7.1
Classes Case e Objetos Case
Classes Case e objetos case são definidos como classes e objetos normais, exceto que
a definição é prefixada com um modificador case. Por exemplo, as definições:
abstract class Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr
introduzem Number e Sum como classes case. O modificador case em frente a uma
definição de classe ou objeto tem os seguintes efeitos.
1. Classes case implicitamente vem com uma função construtora, com o mesmo
nome da classe. No nosso exemplo, as duas funções
def Number(n: Int) = new Number(n)
def Sum(e1: Expr, e2: Expr) = new Sum(e1, e2)
serão adicionadas.
Consequentemente, pode-se agora
árvores-expressões de modo um pouco mais conciso, como em
Sum(Sum(Number(1), Number(2)), Number(3))
construir
7.1 Classes Case e Objetos Case
47
2. Classes case e objetos case implicitamente vem com implementações dos
métodos toString, equals e hashCode, que sobrescrevem os métodos com
o mesmo nome na classe AnyRef. A implementação desses métodos leva
em consideração em cada caso a estrutura de um membro de uma classe
case. O método toString representa uma árvore expressão do modo como
foi construída. Então,
Sum(Sum(Number(1), Number(2)), Number(3))
será convertida exatamente naquela cadeia de caracteres, onde a
implementação default dentro da classe AnyRef retornará uma cadeia
de caracteres consistindo construtor Sum mais externo e um número. O
método equals trata dois membros case da classe case do mesmo modo, caso
eles tenham sido construídos com o mesmo construtor e com argumentos
que são par a par iguais. Isso também afeta a implementação de == e !=, que
são implementados em termos de equals em Scala. Então,
Sum(Number(1), Number(2)) == Sum(Number(1), Number(2))
dará true. Se Sum ou Number não fossem classes case, a mesma expressão
seria false, pois a implementação padrão de equals na classe AnyRef sempre
trata objetos criados por diferentes chamadas de construtores como sendo
diferentes. O método hashCode segue a mesmo princípio dos outros dois
métodos. Computa um código hash a partir do nome do construtor da classe
case e os códigos hash dos argumentos do construtor, ao invés de o fazer
a partir do endereço do objeto, que é o que a implementação default de
hashCode faz.
3. Classes case implicitamente vem com métodos de acesso nulos que
recuperam os argumentos do construtor. Em nosso exemplo, Number obteria
um método de acesso
def n: Int
que retorna o parâmetro n do construtor, onde Sum obterá dois métodos de
acesso
def e1: Expr, e2: Expr
Consequentemente, para um valor s de tipo Sum, digamos, podemos escrever
s.e1 para acessar o operando esquerdo. Entretanto, para um valor e de tipo
Expr, o termo e.e1 será ilegal, pois e1 é definido em Sum; não é um membro
da classe base Expr. Então, como determinar o construtor e os argumentos
do construtor de acesso para valores cujo tipo estático é a classe base Expr?
48
Classes Case e Casamento de Padrões
Isso é resolvido pela quarta e última particularidade das classes case.
4. Classes case permitem construções de padrões que se referem ao construtor
da classe case.
7.2
Casamento de Padrões
O casamento de padrões é uma generalização do comando switch do C ou Java para
hierarquias de classes. Ao invés de um comando switch, há um método padrão
match, que é definido na classe raíz Scala Any, e portanto está disponível para todos
os objetos. O método match recebe como argumento um número de cases. Por
exemplo, aqui está uma implementação de eval usando casamento de padrões.
def eval(e: Expr): Int = e match {
case Number(n) => n
case Sum(l, r) => eval(l) + eval(r)
}
Neste exemplo, há dois cases. Cada case associa um padrão a uma expressão.
Padrões são casados contra o valor do seletor e. O primeiro padrão do nosso
exemplo, Number(n), casa todos os valores da forma Number(v), onde v é um valor
arbitrário. Naquele caso, a variável padrão n é ligada ao valor v. Similarmente, o
padrão Sum(l, r) casa com todos os valores do seletor da forma Sum(v1 , v2 ) e liga
as variáveis padrão l e r a v1 e v2 , respectivamente.
Em geral, padrões são construídos a partir
• Construtores de classes case, por exemplo Number, Sum, cujos argumentos são,
novamente, padrões,
• variáveis padrão, por exemplo n, e1, e2,
• o padrão “coringa” _,
• literais, tal como 1, true, "abc",
• identificadores constantes, tais como MAXINT, EmptySet.
Variáveis padrão sempre iniciam com uma letra minúscula, para que possamos
distinguí-las de identificadores constantes, que iniciam com uma letra maiúscula.
Cada nome de variável pode ocorrer somente uma vez em um padrão. Por exemplo,
Sum(x, x) seria ilegal como padrão, pois a variável padrão x ocorre duas vezes
dentro dele.
Significado do Casamento de Padrões.
Uma expressão de casamento de padrões
e match { case p1 => e1 ... case pn => en }
7.2 Casamento de Padrões
49
casa os padrões p 1 , . . . , p n na ordem em que eles são escritos contra o valor seletor
e.
• Um construtor padrão C (p 1 , . . . , p n ) casa com todos os valores que são do tipo
C (ou um subtipo dele) e que foram construídos com argumentos C casando
com padrões p 1 , . . . , p n .
• Uma variável padrão x casa com qualquer valor e liga o nome da variável
àquele valor.
• O caracter padrão ‘_’ casa com qualquer valor, mas não liga um nome àquele
valor.
• Um padrão constante C casa um valor que é igual (em termos de ==) para C.
A expressão de casamento de padrões reescreve no lado direito do primeiro
case cujo padrão casa com o valor seletor. Referências as variáveis padrão são
substituídas pelos correspondentes argumentos construtores. Se nenhum dos
padrões casar, a expressão de casamento de padrões é abortada com um erro
MatchError.
Exemplo 7.2.1 Nosso modelo de substituição de avaliação de programa estende
de modo natural o casamento de padrões. Por exemplo, aqui temos como eval
aplicado a uma única expressão é reescrito:
eval(Sum(Number(1), Number(2)))
->
(através da reescrita da aplicação)
Sum(Number(1), Number(2)) match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
}
->
(através da reescrita do casamento de padrões)
eval(Number(1)) + eval(Number(2))
->
(através da reescrita da primeira aplicação)
Number(1) match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
} + eval(Number(2))
->
(através da reescrita do casamento de padrões)
50
Classes Case e Casamento de Padrões
1 + eval(Number(2))
->∗ 1 + 2 -> 3
Casamento de Padrões e Métodos. No exemplo anterior, usamos casamento
de padrões numa função que era definida fora da hierarquia de classes da qual
pertencia. De fato, é também possível definir uma função de casamento de padrões
na sua própria hierarquia de classes. Por exemplo, podíamos ter definido eval
como um método da classe base Expr, e ainda assim usar o casamento de padrões
na sua implementação:
abstract class Expr {
def eval: Int = this match {
case Number(n) => n
case Sum(e1, e2) => e1.eval + e2.eval
}
}
Exercício 7.2.2 Considere as seguintes definições representando árvores de
inteiros. Estas definições podem ser vistas como uma representação alternativa
para IntSet:
abstract class IntTree
case object EmptyTree extends IntTree
case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
Complete as implementações a seguir da função contains e insert para IntTree.
def contains(t: IntTree, v: Int): Boolean = t match { ...
...
}
def insert(t: IntTree, v: Int): IntTree = t match { ...
...
}
Funções Anônimas e Casamento de Padrões. Até aqui, expressões case sempre
apareceram conjuntamente com uma operação match. Mas é também possível usar
expressões case por elas mesmas. Um bloco de expressões case tal como
{ case P 1 => E 1 ... case P n => E n }
é visto como uma função que casa seus argumentos contra os padrões P 1 , . . . , P n ,
e produz o resultado de um dos E 1 , . . . , E n . (Se nenhum padrão casar, a função
7.2 Casamento de Padrões
51
produzirá uma exceção MatchError. Em outras palavras, a expressão acima é vista
como um atalho para a função anônima
(x => x match { case P 1 => E 1 ... case P n => E n })
onde x é uma variável nova que não é usada a não ser dentro da expressão.
Capítulo 8
Tipos Genéricos e Métodos
Classes em Scala podem ter tipos como parâmetros. Demostraremos o uso de tipos
parâmetros com pilhas funcionais como exemplo. Digamos, desejamos escrever
um tipo de dados para pilhas de inteiros, com métodos push, top, pop, e isEmpty.
Isso é conseguido pela seguinte hierarquia de classes:
abstract class IntStack {
def push(x: Int): IntStack = new IntNonEmptyStack(x, this)
def isEmpty: Boolean
def top: Int
def pop: IntStack
}
class IntEmptyStack extends IntStack {
def isEmpty = true
def top = error("EmptyStack.top")
def pop = error("EmptyStack.pop")
}
class IntNonEmptyStack(elem: Int, rest: IntStack) extends IntStack {
def isEmpty = false
def top = elem
def pop = rest
}
De fato, faz sentido definir uma abstração para uma pilha de Strings. Para isso,
pode-se tomar a abstração existente para IntStack, renomeá-la para StringStack
e ao mesmo tempo renomear todas as ocorrências do tipo Int para String.
Um modo melhor, que não leva a duplicação de código, é parametrizar as definições
da pilha com o tipo do elemento. Parametrizações nos levam a generalizar a
partir de uma instância específica de um problema para uma mais genérica. Até
aqui, usamos parametrização somente para valores, mas também está disponível
para tipos. Para obtermos uma versão genérica de Stack, a equiparemos com um
54
Tipos Genéricos e Métodos
parâmetro tipo.
abstract class Stack[A] {
def push(x: A): Stack[A] = new NonEmptyStack[A](x, this)
def isEmpty: Boolean
def top: A
def pop: Stack[A]
}
class EmptyStack[A] extends Stack[A] {
def isEmpty = true
def top = error("EmptyStack.top")
def pop = error("EmptyStack.pop")
}
class NonEmptyStack[A](elem: A, rest: Stack[A]) extends Stack[A] {
def isEmpty = false
def top = elem
def pop = rest
}
Nas definições acima, ‘A’ é um parâmetro tipo da classe Stack e suas subclasses.
Parâmetros tipo são nomes arbitrários; eles são envolvidos por chaves ao invés de
parênteses, portanto podem facilmente distinguidos de parâmetros valor. Aqui está
um exemplo de como classes genéricas são usadas:
val x = new EmptyStack[Int]
val y = x.push(1).push(2)
println(y.pop.top)
A primeira linha cria uma nova pilha vazia de Int. Observe o tipo argumento [Int]
que substitui o tipo parâmetro formal A.
Também é possível parametrizar métodos com tipos. Como um exemplo, aqui está
um método genérico que determina se uma pilha é um prefixo de outra.
def isPrefix[A](p: Stack[A], s: Stack[A]): Boolean = {
p.isEmpty ||
p.top == s.top && isPrefix[A](p.pop, s.pop)
}
Os parâmetros do método são chamados polimórficos. Métodos genéricos são
também chamados polimórficos. O termo tem origem no Grego, onde significa
“que tem muitas formas”. Para aplicar um método polimórfico tal como isPrefix,
passamos parâmetros tipo, bem como parâmetros valor para ele. Por exemplo,
val s1 = new EmptyStack[String].push("abc")
val s2 = new EmptyStack[String].push("abx").push(s1.top)
println(isPrefix[String](s1, s2))
8.1 Parâmetros Tipo Ligados
Inferência de Tipos Local.
55
Passar parâmetros de tipo tais como [Int] ou
[String] o tempo todo pode tornar-se enfadonho em aplicações onde funções
genéricas são muito utilizadas. Frequentemente, a informação dentro de um
parâmetro de tipo é redundante, porque o parâmetro tipo correto pode também
ser determinado pela inspeção dos parâmetros valores da função ou do tipo
esperado do resultado. Tomando a expressão isPrefix[String](s1, s2) como um
exemplo, sabemos que seus parâmetros valor são ambos do tipo Stack[String],
portanto podemos deduzir que o parâmetro tipo deve ser String. Scala tem um
poderoso mecanismo de inferência que nos permite omitir parâmetros tipo para
funções polimórficas e construtores em situações como esta. No exemplo acima,
poderíamos ter escrito isPrefix(s1, s2) e o tipo do argumento omitido [String]
seria inserido pelo mecanismo de inferência de tipos.
8.1
Parâmetros Tipo Ligados
Agora que sabemos como criar classes genéricas é natural generalizarmos algumas
das classes escritas anteriormente. Por exemplo, a classe IntSet poderia ser
generalizada para conjuntos com tipos arbitrários de elementos. Vamos tentar. A
classe abstrata para conjuntos genéricos é facilmente escrita.
abstract class Set[A] {
def incl(x: A): Set[A]
def contains(x: A): Boolean
}
Entretanto, se ainda quisermos implementar conjuntos como árvores binárias
de busca, encontraremos um problema. Os métodos contains e incl, ambos
comparam elementos usando métodos < e >. Para IntSet isto está OK, pois o
tipo Int tem estes dois métodos. Mas para um tipo arbitrário de parâmetro a,
não podemos garantir isso. Logo, a implementação anterior de, digamos, contains
levará a um erro de compilação.
def contains(x: Int): Boolean =
if (x < elem) left contains x
^ < não é membro do tipo A.
Um modo de resolver o problema é restringir os tipos legais que podem ser
substituídos pelo tipo A àqueles que contenham os métodos < e > do tipos corretos.
Na biblioteca de classes padrão do Scala há o trait Ordered[A] que representa
valores que podem ser comparados (via < e >) a valores do tipo A. Esse trait é
definido como segue:
/** Uma classe com todos os dados ordenados. */
trait Ordered[A] {
56
Tipos Genéricos e Métodos
/**
*
*
*
*
*/
def
Resultado da comparacao de ‘this’ com o operando ‘that’.
returna ‘x’ onde
x < 0
iff
this < that
x == 0
iff
this == that
x > 0
iff
this > that
def
def
def
def
def
< (that: A): Boolean =
> (that: A): Boolean =
<= (that: A): Boolean =
>= (that: A): Boolean =
compareTo(that: A): Int
compare(that: A): Int
(this compare that)
(this compare that)
(this compare that)
(this compare that)
= compare(that)
<
>
<=
>=
0
0
0
0
}
Podemos forçar a compatibilidade de um tipo demandando que esse tipo seja
subtipo de Ordered. Isto é feito dando um limite superior ao parâmetro tipo de
Set:
trait Set[A <: Ordered[A]] {
def incl(x: A): Set[A]
def contains(x: A): Boolean
}
A declaração de parâmetro A <: Ordered[A] introduz A como um parâmetro
tipo que deve ser um subtipo de Ordered[A], ou seja, seus valores devem ser
comparáveis a valores de mesmo tipo.
Com esta restrição, podemos agora implementar o restante da abstração genérica
de conjunto como fizemos anteriormente no caso de IntSet.
class EmptySet[A <: Ordered[A]] extends Set[A] {
def contains(x: A): Boolean = false
def incl(x: A): Set[A] = new NonEmptySet(x, new EmptySet[A], new EmptySet[A])
}
class NonEmptySet[A <: Ordered[A]]
(elem: A, left: Set[A], right: Set[A]) extends Set[A] {
def contains(x: A): Boolean =
if (x < elem) left contains x
else if (x > elem) right contains x
else true
def incl(x: A): Set[A] =
if (x < elem) new NonEmptySet(elem, left incl x, right)
else if (x > elem) new NonEmptySet(elem, left, right incl x)
else this
}
8.1 Parâmetros Tipo Ligados
57
Observe que deixamos de fora o tipo argumento na criações dos objetos
new NonEmptySet(...). Do mesmo modo que para métodos polimórficos, tipos de
argumentos faltantes nas chamadas de contrutores são inferidos a partir do valor
dos argumentos e/ou o tipo esperado do resultado.
Aqui está um exemplo que usa a abstração genérica de conjunto. Vamos primeiro
criar uma subclasse de Ordered, como esta:
case class Num(value: Double) extends Ordered[Num] {
def compare(that: Num): Int =
if (this.value < that.value) -1
else if (this.value > that.value) 1
else 0
}
Então:
val s = new EmptySet[Num].incl(Num(1.0)).incl(Num(2.0))
s.contains(Num(1.5))
Isto está OK, pois o tipo Num implementa o trait Ordered[Num]. Entretanto, o
exemplo seguinte está errado.
val s = new EmptySet[java.io.File]
^ java.io.File não implementa o tipo
Ordered[java.io.File] definido no tipo do parâmetro.
Um problema com ligações para parâmetros tipo é que elas requerem antecipação:
se não declaramos Num uma subclasse deOrdered, não estaremos aptos a usar
elementos Num dentro dos conjuntos. A partir do mesmo token, tipos herdados
do Java, tais como Int, Double, ou String não são subclasses de Ordered, portanto
valores destes tipos não podem ser usados como elementos de conjuntos.
Um desenho mais flexível, que admite elementos destes tipos, usam ligações de
visão ao invés de ligações plenas a tipos como temos visto. A única mudança que
isto no leva no exemplo abaixo está nos parâmetros tipo:
trait Set[A <% Ordered[A]] ...
class EmptySet[A <% Ordered[A]] ...
class NonEmptySet[A <% Ordered[A]] ...
Ligações visão <% são mais fracas que ligações plenas <:: Uma ligação visão da
cláusula do tipo parâmetro [A <% T] somente especifica que o tipo ligado A deve
ser convertido ao tipo ligado T, usando uma conversão implícita.
A biblioteca Scala predefine conversões implícitas para vários tipos, incluindo os
tipos primitivos e String. Entretanto, o redesenho da abstração conjunto pode ser,
do mesmo modo, instanciada com estes tipos. Mais explicações sobre conversões
58
Tipos Genéricos e Métodos
implicitas e ligações visão são dadas na Seção 15.
8.2
Anotações de Variância
A combinação de tipos parâmetros e subtipos levantam algumas questões
interessantes. Por exemplo, Stack[String] deve ser um subtipo de Stack[AnyRef]?
Intuitivamente, isto parece OK, pois uma pilha de Strings é um caso especial
de uma pilha de AnyRefs. Mais genericamente, se T é um subtipo do tipo S,
então, Stack[T] deve ser um subtipo de Stack[S]. Essa propriedade é chamada
subtipificação co-variante.
Em Scala, tipos genéricos tem por padrão subtipificação não variante. Ou seja, com
Stack definido conforme acima, pilhas com tipos de elementos diferentes nunca
estarão numa relação de subtipo. Entretanto, podemos forçar a subtipificação
co-variante das pilhas mudando a primeira linha da definição da classe Stack como
segue.
class Stack[+A] {
Prefixando um parâmetro tipo formal com um + indica que aquela subtipificação
é covariante naquele parâmetro. Além do +, há também um prefixo - que indica
subtipificação contravariante. Se Stack foi definida class Stack[-A] ..., então T,
um subtipo do tipo S, poderia implicar que Stack[S] é um subtipo de Stack[T] (o
que no caso de pilhas seria um tanto quanto surpreendente!).
Em um mundo puramente funcional, todos os tipos podem ser covariantes.
Entretanto, a situação muda quando introduzimos dados mutantes. Considere o
caso de vetores em Java ou .NET. Tais vetores são representados em Scala por uma
classe genérica Array. Aqui está uma definição parcial desta classe.
class Array[A] {
def apply(index: Int): A
def update(index: Int, elem: A)
}
A classe acima define o modo que vetores em Scala são vistos a partir de
programas Scala do usuário. O compilador Scala mapeará esta abstração aos
vetores subjacentes do sistema hospedeiro sempre que possível.
Em Java, vetores são, de fato, covariantes; ou seja, para os tipos referenciados T e S,
se T é um subtipo de S, então Array[T] é um subtipo de Array[S]. Isso pode parecer
natural, mas leva a problemas de segurança que requerem checagem especial em
tempo de execução. Aqui está um exemplo:
val x = new Array[String](1)
val y: Array[Any] = x
y(0) = new Rational(1, 2) // isto é syntactic sugar para
8.2 Anotações de Variância
59
// y.update(0, new Rational(1, 2))
Na primeira linha, um novo vetor de strings é criado. Na segunda linha, este vetor é
ligado a uma variável y, de tipo Array[Any]. Assumindo vetores como covariantes,
isto está OK, pois Array[String] é um subtipo de Array[Any]. Finalmente, na
última linha, um número racional é guardado no vetor. Isso também está OK, pois
o tipo Rational é um subtipo do tipo do elemento Any do vetor y. Acabamos por
guardar um número racional em um vetor de strings, o que claramente viola a
integridade do tipo.
Java resolve este problema introduzindo checagem em tempo de execução na
terceira linha que testa se o elemento guardado é compatível com o tipo de
elemento para o qual o vetor foi criado. Vimos no exemplo que este tipo de
elemento não é necessariamente o tipo estático de elemento do vetor que está
sendo atualizado. Se o teste falhar, é dado um ArrayStoreException.
Ao invés disto, Scala resolve este problema estáticamente, rejeitando a segunda
linha em tempo de compilação, porque vetores em Scala tem subtipificação não
variante. Isso nos leva a questão de como o compilador Scala verifica que anotações
de variância são corretas. Se simplesmente declararmos vetores como covariantes,
como detectar este potencial problema?
Scala usa uma aproximação conservadora para verificar a integridade de anotações
de variância. Um parâmetro tipo covariante de uma classe pode somente aparecer
em posições covariantes dentro da classe. Apesar de posições covariantes serem
tipos de valores na classe, o tipo resultante dos métodos na classe, e tipos
argumentos para outros tipos covariantes. Não covariantes são tipos de parâmetros
formais de métodos. Logo, a seguinte definição de classe seria rejeitada
class Array[+A] {
def apply(index: Int): A
def update(index: Int, elem: A)
^ o tipo parâmetro covariante A
aparece na posição contravariante.
}
Até aqui tudo bem. Intuitivamente, o compilador estava correto rejeitando o
procedimento update na classe covariante, porque update potencialmente muda
estado, e portanto mina a integridade da subtipificação covariante.
Entretanto, há também métodos que não mudam estado, mas onde um parâmetro
tipo ainda aparece contravariantemente. Como exemplo temos o push no tipo
Stack. Novamente o compilador Scala rejeitará a definição deste método para
pilhas covariantes.
class Stack[+A] {
def push(x: A): Stack[A] =
^ o tipo parâmetro covariante A
60
Tipos Genéricos e Métodos
aparece na posição contravariante.
Isto é uma pena, porque diferente de vetores, pilhas são estruturas de dados
puramente funcionais e portanto devem habilitar a subtipificação covariante.
Entretanto, há um modo de resolver o problema usando um método polimórfico
com uma baixa ligação para tipos de parâmetros.
8.3
Lower Bounds
Nós temos visto ligações fortes para tipos de parâmetros. Em uma declaração de
tipo parâmetro tal como T <: U, o tipo parâmetro T é restrito ao intervalo somente
sobre subtipos do tipo U. Simetrico a isso estão as ligações fracas em Scala. Em uma
declaração de tipo parâmetro T >: S, o tipo parâmetro T está restrito ao intervalo
somente sobre supertipos do tipo S. (Pode-se também combinar ligações fracas e
fortes, como em T >: S <: U.)
Usando ligações fracas, podemos generalizar o método push dentro de Stack como
segue.
class Stack[+A] {
def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)
Tecnicamente isso resolve nosso problema de variância, pois agora o tipo
parâmetro A não mais aparece como um tipo parâmetro do método push. Ao invés,
aparece como ligação fraca para um outro tipo parâmetro de um método, que é
classificado como uma posição covariante. Logo, o compilador Scala aceita a nova
definição de push.
De fato, não apenas resolvemos o problema técnico da variância, mas também
generalizamos a definição de push. Antes, só podíamos efetuar push em elementos
com tipos que estivessem em conformidade com o tipo do elemento declarado da
pilha. Agora, também podemos efetuar push sobre elementos de um supertipo
deste tipo, mas o tipo da pilha retornada será alterado de acordo. Por exemplo,
podemos agora efetuar push de AnyRef sobre uma pilha de Strings, mas a pilha
resultante será uma pilha de AnyRefs ao invés de uma pilha de Strings!
Em resumo, não devemos hesitar em adicionar anotações de variância às estruturas
de dados, pois isso enriquece naturalmente relacionamentos de subtipificação.
O compilador detectará problemas de integridade potenciais. Mesmo se a
aproximação do compilador for muito conservadora, frequentemente sugerirá uma
generalização útil do método contestado.
8.4 Tipos Minimais
8.4
61
Tipos Minimais
Scala não nos permite parametrizar objetos com tipos. Este é o motivo pelo qual
originalmente definimos uma classe genérica EmptyStack[A], ainda que um único
valor denotando pilhas vazias de tipos arbitrários o fizesse. Para pilhas covariantes,
entretanto, pode-se usar o seguinte idioma:
object EmptyStack extends Stack[Nothing] { ... }
O tipo base Nothing não contém valor, portanto o tipo Stack[Nothing] expressa
o fato que uma EmptyStack não contém elementos. Além disso, Nothing é um
subtipo de todos os outros tipos. Consequentemente, para pilhas covariantes,
Stack[Nothing] é um subtipo de Stack[T], para qualquer outro tipo T. Isso torna
possível usar um único objeto pilha vazia no código do usuário. Por exemplo:
val s = EmptyStack.push("abc").push(new AnyRef())
Vamos analisar a atribuição de tipo para esta expressão em detalhes. O objeto
EmptyStack é do tipo Stack[Nothing], o qual tem um método
push[B >: Nothing](elem: B): Stack[B] .
A inferência local de tipos determinará que o tipo parâmetro B deve ser instanciado
para String na aplicação EmptyStack.push("abc"). O tipo resultado desta
aplicação é, consequentemente, Stack[String], que por sua vez tem um método
push[B >: String](elem: B): Stack[B] .
A parte final da definição do valor acima é a aplicação deste método a
new AnyRef(). A inferência local de tipos determinará que o tipo parâmetro b
deve desta vez ser instanciado para AnyRef, com tipo resultado Stack[AnyRef].
Consequentemente, o tipo atribuído ao valor s é Stack[AnyRef].
Além de Nothing, que é um subtipo para cada outro tipo, há também o tipo Null,
que é um subtipo de scala.AnyRef, e de cada classe derivada dele. O literal Null em
Scala é o único valor deste tipo. Isto torna null compatível com cada tipo referência,
mas não com um valor de tipo tal como Int.
Concluímos esta seção com a definição completa melhorada de pilhas. Pilhas tem
agora subtipificação covariante, o método push foi generalizado, e a pilha vazia é
denotada por um único objeto.
abstract class Stack[+A] {
def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)
def isEmpty: Boolean
def top: A
def pop: Stack[A]
}
62
Tipos Genéricos e Métodos
object EmptyStack extends Stack[Nothing] {
def isEmpty = true
def top = error("EmptyStack.top")
def pop = error("EmptyStack.pop")
}
class NonEmptyStack[+A](elem: A, rest: Stack[A]) extends Stack[A] {
def isEmpty = false
def top = elem
def pop = rest
}
Muitas classes na biblioteca Scala são genéricas. Agora apresentaremos duas
comumente usadas famílias de classes genéricas, tuplas e funções. A discussão de
uma outra classe bem comum, listas, é postergada para o próximo capítulo.
8.5
Tuplas
Vez por outra, uma função precisa retornar mais de um resultado. Por exemplo,
suponha a função divmod que retorna o quociente inteiro e o resto de dois
argumentos inteiros dados. De fato, pode-se definir uma classe para pegar os dois
resultados de divmod, como em:
case class TwoInts(first: Int, second: Int)
def divmod(x: Int, y: Int): TwoInts = new TwoInts(x / y, x % y)
Entretanto, ter que definir uma nova classe para cada possível par de tipos de
resultados é bastante tedioso. Em Scala pode-se usar, ao invés, uma classe genérica
Tuple2, que é definida como segue:
package scala
case class Tuple2[A, B](_1: A, _2: B)
Com Tuple2, o método divmod pode ser escrito como segue.
def divmod(x: Int, y: Int) = new Tuple2[Int, Int](x / y, x % y)
Como sempre, parâmetros tipos para construtores podem ser omitidos se forem
dedutíveis a partir dos valores dos argumentos. Há também classes tuplas para cada
outro número de elementos (a implementação Scala atual limita isto a tuplas de
algum número razoável de elementos).
Como os elementos de tuplas são acessados? Como tuplas são classes case, há
duas possibilidades. Pode-se ou acessar os campos da tupla usando os nomes dos
parâmetros dos construtores _i , como no seguinte exemplo:
val xy = divmod(x, y)
8.6 Funções
63
println("quotient: " + xy._1 + ", rest: " + xy._2)
Ou usa-se casamento de padrões sobre tuplas, como no seguinte exemplo:
divmod(x, y) match {
case Tuple2(n, d) =>
println("quotient: " + n + ", rest: " + d)
}
Observe que tipos parâmetros nunca são usados nos padrões; seria ilegal escrever
case Tuple2[Int, Int](n, d).
Tuplas são tão convenientes que Scala define uma sintaxe especial para elas. Para
formar uma tupla com n elementos x 1 , . . . , x n pode-se escrever (x 1 , . . . , x n ). Isto é
equivalente a Tuplen (x 1 , . . . , x n ). A sintaxe (...) funciona de modo equivalente para
tipos e para padrões. Com esta sintaxe para tuplas, o exemplo divmod é escrito como
segue:
def divmod(x: Int, y: Int): (Int, Int) = (x / y, x % y)
divmod(x, y) match {
case (n, d) => println("quotient: " + n + ", rest: " + d)
}
8.6
Funções
Scala é uma linguagem funcional na qual funções são valores de primeira classe.
Scala é também uma linguagem orientada a objetos na qual cada valor é um
objeto. Segue daí que funções são objetos em Scala. Por exemplo, uma função
do tipo String para o tipo Int é representada como uma instância do trait
Funciton1[String, Int]. O trait Function1 é definido como segue.
package scala
trait Function1[-A, +B] {
def apply(x: A): B
}
Ao lado de Funciton1, há também definições para funções de todas as outras
aridades (a implementação corrente implementa isto somente até um limite
razoável). Ou seja, há uma definição para cada possível número de parâmetros de
funções. Sintaxe para tipos de funções em Scala (T1 , . . . , Tn ) => S é apenas uma
abreviatura para o tipo parametrizado Functionn [T1 , . . . , Tn , S ] .
Scala usa a mesma sintaxe f (x) para aplicações de funções, não importa se f é
um método ou um objeto função. Isto é possível pela seguinte convenção: Uma
aplicação de função f (x) onde f é um objeto (em contraste com um método) é
tomado para ser um atalho para f .apply(x ). Consequentemente, o método apply
64
Tipos Genéricos e Métodos
de um tipo de função é inserido automaticamente onde isso é necessário.
Isso justifica o porquê definimos subscritos de vetores na Seção 8.2 através de um
método apply. Para cada vetor a, a operação subscritora a(i) é tomada como um
atalho para a.apply(i).
Funções são exemplos em que uma declaração de um parâmetro tipo
contravariante é útil. Por exemplo, considere o seguinte código:
val f: (AnyRef => Int)
val g: (String => Int)
g("abc")
=
=
x => x.hashCode()
f
É correto ligar o valor g de tipo String => Int a f, que é do tipo AnyRef => Int. De
fato, tudo o que se pode fazer com uma função do tipo String => Int é passar-lhe
uma string para se obter um inteiro. Isso demonstra que subtipificar funções é
contravariante nos tipos dos argumentos, enquanto é covariante no tipo do seu
resultado. Em resumo, S ⇒ T é um subtipo de S 0 ⇒ T 0 , desde que S 0 seja um subtipo
de S e T seja um subtipo de T 0 .
Exemplo 8.6.1 Considere o código Scala
val plus1: (Int => Int)
plus1(2)
=
(x: Int) => x + 1
Isso é expandido no seguinte código objeto.
val plus1: Function1[Int, Int] = new Function1[Int, Int] {
def apply(x: Int): Int = x + 1
}
plus1.apply(2)
Aqui, a criação do objeto new Function1[Int, Int]{ ... } representa uma
instância de uma classe anônima. Combina a criação de um novo objeto Function1
com uma implementação do método apply (que é abstrato dentro de Function1).
Equivalentemente, mas mais prolixo, podería-se usar uma classe local:
val plus1: Function1[Int, Int] = {
class Local extends Function1[Int, Int] {
def apply(x: Int): Int = x + 1
}
new Local: Function1[Int, Int]
}
plus1.apply(2)
Capítulo 9
Listas
Listas são uma importante estrutura de dados em muitos programas Scala. Uma
lista contendo os elementos x1 , . . . , xn é escrita List(x1 , ..., xn ). Alguns
exemplos:
val
val
val
val
fruit
nums
diag3
empty
=
=
=
=
List("apples", "oranges", "pears")
List(1, 2, 3, 4)
List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
List()
Listas são similares a vetores em linguagens tais como C ou Java, mas há também
três importantes diferenças. Primeiro, listas são imutáveis. Ou seja, elementos de
uma lista não podem ser mudados por meio de atribuição. Segundo, listas tem
uma estrutura recursiva, enquanto vetores são triviais. Terceiro, em geral, listas
suportam um conjunto muito mais rico de operações que vetores.
9.1
Usando Listas
O tipo lista. Do mesmo modo que com vetores, listas são homogêneas. Ou seja, os
elementos de uma lista têm todos o mesmo tipo. O tipo de uma lista com elementos
de tipo T é escrito List[T] (compare com T[] em Java).
val
val
val
val
fruit:
nums :
diag3:
empty:
List[String]
List[Int]
List[List[Int]]
List[Int]
=
=
=
=
List("apples", "oranges", "pears")
List(1, 2, 3, 4)
List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
List()
Construtores de listas. Todas as listas são construídas a partir de dois
construtores fundamentais, Nil e :: (lê-se “cons”). Nil representa uma lista vazia.
66
Listas
O operador infixo :: expressa a extensão da lista. Ou seja, x :: xs denota uma
lista cujo primeiro elemento é x, e que é seguido pela (os elementos da) lista xs.
Consequentemente, os valores da lista acima podem também ter sido definidos
como segue (de fato essa definição prévia é apenas um facilitador sintático para
as definições abaixo).
val fruit
val nums
val diag3
val empty
= "apples" :: ("oranges" :: ("pears" :: Nil))
= 1 :: (2 :: (3 :: (4 :: Nil)))
= (1 :: (0 :: (0 :: Nil))) ::
(0 :: (1 :: (0 :: Nil))) ::
(0 :: (0 :: (1 :: Nil))) :: Nil
= Nil
A operação ‘::’ é associativa à direita: A :: B :: C é interpretada como
A :: (B :: C). Por essa razão, podemos retirar os parênteses das definições acima.
Por exemplo, podemos escrever de modo resumido
val nums
=
1 :: 2 :: 3 :: 4 :: Nil
Operações básicas sobre listas. Todas as operações sobre listas podem ser
expressas em termos das três a seguir:
head
tail
isEmpty
retorna o primeiro elemento de uma lista,
retorna a lista que consiste de todos os elementos exceto o
primeiro elemento,
retorna true se e só se a lista for vazia.
Estas operações são definidas como métodos de objetos listas. Portanto as
invocamos escolhendo da lista aqueles que sofrerão a operação. Exemplos:
empty.isEmpty
fruit.isEmpty
fruit.head
fruit.tail.head
diag3.head
=
=
=
=
=
true
false
"apples"
"oranges"
List(1, 0, 0)
Os métodos head e tail são definidos somente para listas não vazias. Quando
selecionados para uma lista vazia, eles lançam uma exceção.
Como um exemplo de como listas podem ser processadas, considere ordenar os
elementos de uma lista de números em ordem crescente. Um modo simples de
fazer isso é usar o insertion sort, que trabalha da seguinte maneira: Para ordenar
uma lista não vazia com primeiro elemento x e resto xs, ordene o restante xs e insira
o elemento x na posição correta do resultado. Ordenar uma lista vazia dará uma
lista vazia. Em Scala temos o código:
def isort(xs: List[Int]): List[Int] =
9.2 Definição da classe List I: Métodos de Primeira Ordem
67
if (xs.isEmpty) Nil
else insert(xs.head, isort(xs.tail))
Exercício 9.1.1 Escreva a função faltante insert.
Listas e padrões. De fato, :: é definido como uma classe case na biblioteca
padrão Scala. Consequentemente, é possível decompor listas através de casamento
de padrões, usando padrões compostos a partir dos construtores Nil e ::. Por
exemplo, isort pode ser escrito aternativamente como segue.
def isort(xs: List[Int]): List[Int] = xs match {
case List() => List()
case x :: xs1 => insert(x, isort(xs1))
}
onde
def insert(x: Int, xs: List[Int]): List[Int] = xs match {
case List() => List(x)
case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
}
9.2
Definição da classe List I: Métodos de Primeira Ordem
Listas não são construídas em Scala; elas são definidas por uma classe abstrata
List, que vem com duas subclasses para :: e Nil. A seguir apresentaremos um
tour através da classe List.
package scala
abstract class List[+A] {
List é uma classe abstrata, logo não pode-se definir elementos chamando
o construtor de List vazia (ou seja, através de new List).
A classe tem
uma tipo parâmetro a. É covariante nesse parâmetro, o que significa que
List[S] <: List[T] para todos os tipos S e T tal que S <: T. A classe está no
pacote scala. Este pacote contém as mais importantes classes Scala. List define
um número de métodos, que são explicados a seguir.
Decompondo listas. Primeiro, há os três métodos básicos isEmpty, head, tail.
Suas implementações em termos de casamento de padrões são diretas:
def isEmpty: Boolean = this match {
case Nil => true
68
Listas
case x :: xs => false
}
def head: A = this match {
case Nil => error("Nil.head")
case x :: xs => x
}
def tail: List[A] = this match {
case Nil => error("Nil.tail")
case x :: xs => xs
}
A próxima função computa o tamanho de uma lista.
def length: Int = this match {
case Nil => 0
case x :: xs => 1 + xs.length
}
Exercício 9.2.1 Escreva uma versão recursiva de cauda de length.
As próximas duas funções são o complemento para head e tail.
def last: A
def init: List[A]
xs.last retorna o último elemento da lista xs, enquanto xs.init retorna todos
os elementos de xs exceto o último. Ambas as funções tem de atravessar toda a
lista, e são, portanto, menos eficientes que seus análogos head e tail. Aqui está a
implementação de last.
def last: A = this
case Nil
=>
case x :: Nil =>
case x :: xs =>
}
match {
error("Nil.last")
x
xs.last
A implementação de init é análoga.
As próximas três funções retornam um prefixo da lista, ou um sufixo, ou ambos.
def take(n: Int): List[A] =
if (n == 0 || isEmpty) Nil else head :: tail.take(n-1)
def drop(n: Int): List[A] =
if (n == 0 || isEmpty) this else tail.drop(n-1)
def split(n: Int): (List[A], List[A]) = (take(n), drop(n))
9.2 Definição da classe List I: Métodos de Primeira Ordem
69
(xs take n) retorna os primeiros n elementos da lista xs, ou a lista inteira, caso seu
tamanho seja menor que n. (xs drop n) retorna todos os elementos de xs exceto
os n primeiros. Finalmente, (xs split n) retorna um par consistindo das listas
resultantes de xs take n e xs drop n.
A próxima função retorna um elemento de uma dada posição na lista. É, portanto,
análoga ao subscrito de vetor. Índices começam em 0.
def apply(n: Int): A = drop(n).head
O método apply tem um significado especial em Scala. Um objeto com um método
apply pode ser aplicado a argumentos como se fosse uma função. Por exemplo,
para pegar o terceiro elemento de uma lista xs, pode-se escrever ou xs.apply(3)
ou xs(3)—a última expressão expande na primeira.
Com take e drop, podemos extrair sublistas consistindo de elementos consecutivos
da lista original. Para extrair a sublista xs m , . . . , xs n−1 da lista xs, use:
xs.drop(m).take(n - m)
Zipando listas. A próxima função combina duas listas em uma lista de pares.
Dadas duas listas
xs = List(x1 , ..., xn )
ys = List(y1 , ..., yn )
,e
,
xs zip ys constrói a lista List((x1 , y1 ), ..., (xn , yn )).
Se as duas listas
tiverem tamanhos diferentes, a maior das duas é truncada. Aqui está a definição
de zip—observe que trata-se de um método polimórfico.
def zip[B](that: List[B]): List[(a,b)] =
if (this.isEmpty || that.isEmpty) Nil
else (this.head, that.head) :: (this.tail zip that.tail)
Consing listas.. Como qualquer outro operador infixo, :: também é
implementado como um método de um objeto. Neste caso, o objeto é a lista
que é estendida. Isto é possível porque operadores terminados com um caracter ‘:’
são tratados de modo especial em Scala. Todos esses operadores são tratados como
métodos de seus operandos direitos. Ou seja,
x :: y = y.::(x)
enquanto que
x + y = x.+(y)
Observe, entretanto, que operandos de uma operação binária são em cada caso
avaliados da esquerda para a direita. Logo, se D e E são expressões com possíveis
efeitos colaterais, D :: E é traduzido para {val x = D; E.::(x)} de modo a
manter a ordem esquerda-para-direita da avaliação dos operandos.
70
Listas
Outra diferença entre operadores terminando com um ‘:’ e outros operadores é
concernente à associatividade. Operadores terminados com ‘:’ são associativos à
direita, enquanto outros operadores são associativos à esquerda. Isto é,
x :: y :: z = x :: (y :: z)
enquanto que
x + y + z = (x + y) + z
A definição de :: como um método na classe List é a seguinte:
def ::[B >: A](x: B): List[B] = new scala.::(x, this)
Observe que :: é definido para todos os elementos x de tipo B e listas do tipo
List[A] tais como o tipo B de x é um supertipo dos elementos da lista de tipo A.
O resultado neste caso é uma lista de Bs. Isto é expresso pelo tipo parâmetro B com
ligação fraca A na assinatura de ::.
Concatenando listas. Uma operação similar a :: é a concatenação de listas,
escrita ‘:::’. O resultado de (xs ::: ys) é uma lista consistindo de todos os
elementos de xs, seguidos para todos os elementos de ys. Como termina em dois
pontos, ::: é associativo à direita e é considerado método de seu operando direito.
Por isso,
xs ::: ys ::: zs
=
=
xs ::: (ys ::: zs)
zs.:::(ys).:::(xs)
Aqui está a implementação do método ::::
def :::[B >: A](prefix: List[B]): List[B] = prefix match {
case Nil => this
case p :: ps => this.:::(ps).::(p)
}
Invertendo listas. Outra operação útil é a inversão de lista. Há um método
reverse em List que tem esse efeito. Vamos tentar dar a implementação:
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case x :: xs => reverse(xs) ::: List(x)
}
Esta implementação tem a vantagem de ser mais simples, mas não é muito
eficiente. Na verdade, uma concatenação é feita para cada elemento da lista.
Concatenação de listas leva tempo proporcional ao tamanho do seu primeiro
operando. Consequentemente, a complexidade de reverse(xs) é
n + (n − 1) + ... + 1 = n(n + 1)/2
9.3 Exemplo: Merge sort
71
onde n é o tamanho de xs. Pode-se implementar reverse mais eficientemente?
Veremos mais tarde que há uma outra implementação que tem complexidade
linear.
9.3
Exemplo: Merge sort
O insertion sort apresentado anteriormente neste capítulo é simples de formular,
mas também não é muito eficiente. Sua complexidade média é proporcional ao
quadrado do tamanho de sua lista de entrata. Agora escreveremos um programa
para ordenar os elementos de uma lista que é mais eficiente que o insertion sort.
Um bom algoritmo para isso é merge sort, que trabalha do seguinte modo.
Primeiro, se a lista tem zero ou um elementos, já está ordenada, logo retornamos
a lista sem modificações. Listas mais longas são divididas em duas sublistas, cada
uma contendo por volta de metade dos elementos da lista original. Cada sublista é
ordenada através de uma chamada recursiva para a função de ordenação, e as duas
listas ordenadas resultantes são então combinadas em uma operação merge.
Para uma implementação geral do merge sort, ainda temos que especificar o
tipo dos elementos da lista a ser ordenada, bem como a função a ser usada
na comparação dos elementos. Obtemos uma função de generalidade maximal
passando estes dois itens como parâmetros. Isto leva a seguinte implementação.
def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {
def merge(xs1: List[A], xs2: List[A]): List[A] =
if (xs1.isEmpty) xs2
else if (xs2.isEmpty) xs1
else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)
else xs2.head :: merge(xs1, xs2.tail)
val n = xs.length/2
if (n == 0) xs
else merge(msort(less)(xs take n), msort(less)(xs drop n))
}
A complexidade do msort é O(N l og (N )), onde N é o tamanho da lista de entrada.
Para ver porque, observe que dividir uma lista em duas e intercalar as duas listas
ordenadas leva tempo proporcional ao tamanho das listas argumentos. Cada
chamada recursiva de msort reduz a metade o número de elementos na sua entrada,
logo há O(l og (N )) chamadas recursivas consecutivas, até que o caso base das
listas de tamanho 1 seja alcançado. Entretanto, para listas mais longas, cada
chamada gera duas outras chamadas. Somando tudo acima obtemos que a cada
nível O(l og (N )) de chamada, cada elemento da lista original toma parte em uma
operação de divisão e em uma operação merge. Consequentemente, cada nível
de chamada tem um custo proporcional total de O(N ). Como há O(l og (N )) níveis
de chamada, obtemos um custo total de O(N l og (N )). Este custo não depende da
72
Listas
distribuição inicial dos elementos na lista, portanto o pior caso tem o mesmo custo
que o caso médio. Isto torna o merge sort um algoritmo atraente para ordenação de
listas.
Aqui está um exemplo de como msort é usado.
msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
A definição de msort está currificada para tornar sua especialização com funções de
comparação. Por exemplo,
val intSort = msort((x: Int, y: Int) => x < y)
val reverseSort = msort((x: Int, y: Int) => x > y)
9.4
Definição da classe List II: Métodos de Alta Ordem
Os exemplos encontrados até aqui mostram que funções sobre listas
frequentemente tem estruturas similares. Podemos identificar vários padrões
de computação sobre listas, tais como:
• transformar cada elemento de uma lista de algum modo.
• extrair de uma lista todos os elementos que satisfaçam uma critério.
• combinar os elementos de uma lista usando algum operador.
Linguagens de programação funcional habilitam programadores a escrever funções
genéricas que implementam padrões como estes por meio de funções de alta
ordem. Agora discutiremos um conjunto comumente usado em funções de alta
ordem, que são implementados como métodos dentro da classe List.
Mapping sobre listas. Um operação comum é transformar cada elemento de uma
lista e então retornar a lista de resultados. Por exemplo, para multiplicar cada
elemento de uma lista por um dado fator.
def scaleList(xs: List[Double], factor: Double): List[Double] = xs match {
case Nil => xs
case x :: xs1 => x * factor :: scaleList(xs1, factor)
}
Este padrão pode ser generalizado para o método map da classe List:
abstract class List[A] { ...
def map[B](f: A => B): List[B] = this match {
case Nil => this
case x :: xs => f(x) :: xs.map(f)
}
9.4 Definição da classe List II: Métodos de Alta Ordem
73
Usando map, scaleList pode ser mais concisamente escrito como segue.
def scaleList(xs: List[Double], factor: Double) =
xs map (x => x * factor)
Como outro exemplo, considere o problema de retornar uma dada coluna de uma
matriz que é representada como uma lista de linhas, onde cada linha é novamente
uma lista. Isto é feito através da seguinte função column.
def column[A](xs: List[List[A]], index: Int): List[A] =
xs map (row => row(index))
Um método similar a map é o método foreach que aplica uma dada função a todos
os elementos de uma lista, mas não constrói uma lista de resultados. A função é
assim aplicada somente por seu efeito colateral. foreach é definido como segue.
def foreach(f: A => Unit) {
this match {
case Nil => ()
case x :: xs => f(x); xs.foreach(f)
}
}
Esta função pode ser usada para imprimir todos os elementos de uma lista, por
exemplo:
xs foreach (x => println(x))
Exercício 9.4.1 Considere uma função que eleva ao quadrado todos os elementos
de uma lista e retorna uma lista com os resultados. Complete as duas definições a
seguir de squareList.
def squareList(xs: List[Int]): List[Int] = xs match {
case List() => ??
case y :: ys => ??
}
def squareList(xs: List[Int]): List[Int] =
xs map ??
Filtrando Listas. Outra operação comum seleciona de uma lista todos os
elemento que satisfazem um dado critério. Por exemplo, para retornar uma lista
de todos os elementos positivos de algumas listas dadas de inteiros:
def posElems(xs: List[Int]): List[Int] = xs match {
case Nil => xs
case x :: xs1 => if (x > 0) x :: posElems(xs1) else posElems(xs1)
74
Listas
}
Este padrão é generalizado para o método filter da classe List:
def filter(p: A => Boolean): List[A] = this match {
case Nil => this
case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
}
Usando filter, posElems pode ser mais concisamente escrito como segue.
def posElems(xs: List[Int]): List[Int] =
xs filter (x => x > 0)
Uma operação relacionada a filtering é testar se todos os elementos de uma lista
satisfazem uma dada condição. Dualmente, pode-se também estar interessado na
questão se há um elemento em uma lista que satisfaz uma dada condição. Estas
operações são incorporadas nas funções de alta ordem forall e exists da classe
List.
def forall(p: A => Boolean): Boolean =
isEmpty || (p(head) && (tail forall p))
def exists(p: A => Boolean): Boolean =
!isEmpty && (p(head) || (tail exists p))
Para ilustrar o uso de forall, considere a questão se um número é primo. Lembre
que um número n é primo se puder ser dividido, sem resto, somente por um e por
ele mesmo. A tradução mais direta desta definição testará se n dividido por todos os
números de 2 até, mas excluindo, ele mesmo dá resto diferente de zero. Esta lista de
números pode ser gerada usando uma função List.range que é definida no objeto
List como segue.
package scala
object List { ...
def range(from: Int, end: Int): List[Int] =
if (from >= end) Nil else from :: range(from + 1, end)
Por exemplo, List.range(2, n) gera a lista de todos os inteiros de 2 até, excluindo,
n. A função isPrime pode agora ser defida como segue.
def isPrime(n: Int) =
List.range(2, n) forall (x => n % x != 0)
Vemos que a definição matemática de primalidade pode ser traduzida diretamente
em código Scala.
Exercício: Defina forall e exists em termos de filter.
9.4 Definição da classe List II: Métodos de Alta Ordem
75
Desdobrando (folding) e Reduzindo Listas. Uma outra operação comum é
combinar os elementos de uma lista com algum operador. Por exemplo:
sum(List(x1 , ..., xn ))
product(List(x1 , ..., xn ))
=
=
0 + x1 + ... + xn
1 * x1 * ... * xn
De fato, podemos implementar ambas as funções por meio de um esquema
recursivo:
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case y :: ys => y + sum(ys)
}
def product(xs: List[Int]): Int = xs match {
case Nil => 1
case y :: ys => y * product(ys)
}
Mas também podemos usar a generalização deste esquema de programa
incorporado no método reduceLeft da classe List. Este método insere um dado
operador binário entre elementos adjacentes de uma dada lista. Ou seja,
List(x1 , ..., xn ).reduceLeft(op) = (...(x1 op x2 ) op ... ) op xn
Usando reduceLeft, podemos tornar o padrão comum emas sum e product
aparente:
def sum(xs: List[Int])
def product(xs: List[Int])
=
=
(0 :: xs) reduceLeft {(x, y) => x + y}
(1 :: xs) reduceLeft {(x, y) => x * y}
Aqui está a implementação de reduceLeft.
def reduceLeft(op: (A, A) => A): A = this match {
case Nil
=> error("Nil.reduceLeft")
case x :: xs => (xs foldLeft x)(op)
}
def foldLeft[B](z: B)(op: (B, A) => B): B = this match {
case Nil => z
case x :: xs => (xs foldLeft op(z, x))(op)
}
}
Vemos que o método reduceLeft é definido em termos de um outro método,
geralmente útil, foldLeft.
O último pega como parâmetro adicional um
acumulador z, que é retornado quando foldLeft é aplicado sobre uma lista vazia.
Ou seja,
(List(x1 , ..., xn ) foldLeft z)(op)
=
(...(z op x1 ) op ... ) op xn
76
Listas
Os métodos sum e product podem ser defidos alternativamente usando foldLeft:
def sum(xs: List[Int])
def product(xs: List[Int])
=
=
(xs foldLeft 0) {(x, y) => x + y}
(xs foldLeft 1) {(x, y) => x * y}
FoldRight e ReduceRight. Aplicações de foldLeft e reduceLeft expandem para
árvores inclinadas à esquerda. . Eles têm duals foldRight e reduceRight que
produzem árvores inclinadas à direita.
List(x1 , ..., xn ).reduceRight(op)
=
(List(x1 , ..., xn ) foldRight acc)(op) =
x1 op ( ... (xn−1 op xn )...)
x1 op ( ... (xn op acc)...)
Estes são definidos como segue.
def reduceRight(op: (A, A) => A): A = this match {
case Nil => error("Nil.reduceRight")
case x :: Nil => x
case x :: xs => op(x, xs.reduceRight(op))
}
def foldRight[B](z: B)(op: (A, B) => B): B = this match {
case Nil => z
case x :: xs => op(x, (xs foldRight z)(op))
}
A classe List define também duas abreviaturas simbólicas para foldLeft e
foldRight:
def /:[B](z: B)(f: (B, A) => B): B = foldLeft(z)(f)
def :\[B](z: B)(f: (A, B) => B): B = foldRight(z)(f)
Os nomes dos métodos ilustram a inclinação à esquerda/direita das árvores das
operações fold através de barra simples ou invertida. O : aponta em cada caso para
a lista de argumentos enquanto o fim da barra aponta para o acumulador (ou: zero)
argumento z. Ou seja,
(z /: List(x1 , ..., xn ))(op) = (...(z op x1 ) op ... ) op xn
(List(x1 , ..., xn ) :\ z)(op) = x1 op ( ... (xn op z)...)
Através de operadores associativos e comutativos, /: e :\ são equivalentes (mesmo
sabendo que podem ser diferentes em eficiência).
Exercício 9.4.2 Considere o problema de escrever uma função flatten, que
recebe uma lista de listas como argumentos. O resultado de flatten deve ser a
concatenação de todos os elementos listas em uma única lista. Aqui está uma
implementação deste método em termos de :\.
def flatten[A](xs: List[List[A]]): List[A] =
9.4 Definição da classe List II: Métodos de Alta Ordem
77
(xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}
Considere substituir o corpo de flatten por
((Nil: List[A]) /: xs) ((xs, x) => xs ::: x)
Qual a diferença na complexidade assintótica entre as duas versões de flatten?
De fato flatten é predefinido junto com um conjunto de outras funções úteis
no objeto chamado List na biblioteca padrão Scala. Pode ser acessado de um
programa usuário chamando List.flatten. Observe que flatten não é um
método da classe List—não faz sentido, pois aplica-se somente a listas de listas,
não a todas as listas em geral.
Novamente Inversão de Lista. Vimos na Seção 9.2 uma implementação do
método reverse cujo tempo de execução era quadrático para o tamanho da lista
a ser invertida. Agora desenvolveremos uma nova implementação de reverse, cujo
custo é linear. A idéia é usar uma operação foldLeft baseada no seguinte programa
scheme.
class List[+A] { ...
def reverse: List[A] = (z? /: this)(op?)
Agora falta preencher z? e op?. Vamos tentar deduzir a partir dos exemplos.
=
=
=
=
Nil
Nil.reverse
(z /: Nil)(op)
(Nil foldLeft z)(op)
z
//
//
//
//
pela
pelo
pela
pela
especifica\c{c}\~{a}o
template para reverse
defini\c{c}\~{a}o de /:
defini\c{c}\~{a}o de foldLeft
Consequentemente, z? deve ser Nil. Para deduzir o segundo operando, vamos
estudar o inverso de uma lista de tamanho um.
=
=
=
=
List(x)
List(x).reverse
(Nil /: List(x))(op)
(List(x) foldLeft Nil)(op)
op(Nil, x)
//
//
//
//
pela
pelo
pela
pela
especifica\c{c}\~{a}o
template para reverse, com z = Nil
defini\c{c}\~{a}o de /:
defini\c{c}\~{a}o de foldLeft
Consequentemente, op(Nil, x) é igual a List(x), o que é o mesmo que
x :: Nil. Isto sugere pegar como op o operador :: com seus operandos trocados.
Consequentemente, chegamos a seguinte implementação para reverse, que tem
complexidade linear.
def reverse: List[A] =
((Nil: List[A]) /: this) {(xs, x) => x :: xs}
78
Listas
(Obs: O tipo de anotação para Nil é necessário para que a inferência de tipos
funcione.)
Exercício 9.4.3 Preencha as expressões faltantes para completar as seguintes
definições de algumas operações básicas de manipulação de listas como operações
fold.
def mapFun[A, B](xs: List[A], f: A => B): List[B] =
(xs :\ List[B]()){ ?? }
def lengthFun[A](xs: List[A]): int =
(0 /: xs){ ?? }
Mapeamentos Aninhados. Podemos empregar funções de processamento de
listas de alta ordem para expressar muita computação que, normalmente é expressa
através de aninhamento de laços nas linguagens imperativas.
Como exemplo, considere o seguinte problema: Dado um inteiro positivo n,
encontre todos os pares de inteiros positivos i e j , onde 1 ≤ j < i < n tal que i + j
seja primo. Por exemplo, se n = 7, os pares são
i
j
i+j
2 3 4 4 5 6 6
1 2 1 3 2 1 5
3 5 5 7 7 7 11
Um modo natural de resolver este problema consiste em dois passos. Num primeiro
passo, gera-se a sequência de todos os pares (i , j ) de inteiros tal que 1 ≤ j < i < n.
Num segundo passo filtra-se, a partir desta sequência, todos os pares (i , j ) tal que
i + j é primo.
Examinando o primeiro passo em detalhe, um modo natural de gerar a sequência
de pares consiste de três sub-passos. Primeiro, gera-se todos os inteiros entre 1 e n
para i .
Segundo, para cada inteiro i entre 1 e n, gera-se a lista de pares (i , 1) up to (i , i − 1).
Isso pode ser conseguido através de uma combinação de range e map:
List.range(1, i) map (x => (i, x))
Finalmente, combina-se todas as sublistas usando foldRight com :::. Juntando
tudo dá a seguinte expressão:
List.range(1, n)
.map(i => List.range(1, i).map(x => (i, x)))
.foldRight(List[(Int, Int)]()) {(xs, ys) => xs ::: ys}
.filter(pair => isPrime(pair._1 + pair._2))
9.5 Sumário
79
Flattening Maps. A combinação entre mapeamento e a concatenação das
sublistas resultantes do mapeamento é tão comum que há um método especial para
isto na classe List:
abstract class List[+A] { ...
def flatMap[B](f: A => List[B]): List[B] = this match {
case Nil => Nil
case x :: xs => f(x) ::: (xs flatMap f)
}
}
Com flatMap, os expressão dos “pares cuja soma dá um primo” pode ser escrita de
modo mais sucinto como segue.
List.range(1, n)
.flatMap(i => List.range(1, i).map(x => (i, x)))
.filter(pair => isPrime(pair._1 + pair._2))
9.5
Sumário
Este capítulo introduziu listas como uma estrutura de dados fundamental na
programação. Como listas são imutáveis, elas são um tipo de dado comum
na programação em linguagens funcionais. Elas têm importância comparável
a vetores nas linguagens imperativas. Entretanto, o padrão de acesso é bem
diferente entre os dois. Enquanto o acesso em vetores é sempre feito através de
indexação, isto é muito incomum em listas. Nós vimos que scala.List define um
método chamado apply para a indexação, entretanto, esta operação é muito mais
custosa que no caso dos vetores (linear em comparação a tempo constante). Ao
invés da indexação, listas são geralmente percorridas recursivamente, onde passos
recursivos são em geral baseados em casamento de padrões sobre a lista percorrida.
Há também um rico conjunto de combinadores de alta ordem que permitem
a instanciação de um conjunto de padrões pré-definidos de computações sobre
listas.
Capítulo 10
For-Comprehensions
O capítulo anterior mostrou que funções de alta ordem, tais como map, flatMap,
filter provém poderosas construções para lidar com listas. Mas algumas vezes
o nível de abstração requerido por estas funções tornam um programa difícil de
entender.
Para ajudar a inteligibilidade, Scala tem uma notação especial que simplifica
padrões comuns de aplicações de funções de alta ordem. Esta notação cria uma
ponte entre abrangência de conjuntos (set-comprehensions) na matemática e laços
for em linguagens imperativas tais como C ou Java. Também lembram de perto a
notação de pesquisa em bases de dados relacionais.
Como um primeiro exemplo, digamos que nos é dada uma lista persons de pessoas
com campos name e age (idade). Para imprimir os nomes de todas as pessoas na
sequência para idades acima de 20, pode-se escrever:
for (p <- persons if p.age > 20) yield p.name
Isto é equivalente à seguinte expressão, que usa as funções de alta ordem filter e
map:
persons filter (p => p.age > 20) map (p => p.name)
A abrangência for (for-comprehension) parece um pouco com um laço for nas
linguagens imperativas, exceto que constrói uma lista de resultados de todas
iterações.
Geralmente, um for-comprehension tem a forma
for ( s ) yield e
Aqui, s é uma sequência de geradores, definições e filtros. Um gerador tem a forma
val x <- e, onde e é uma expressão avaliada como lista. Liga x a sucessivos valores
na lista. Uma definição tem a forma val x = e. Introduz x como um nome para o
82
For-Comprehensions
valor de e no restante da abrangência. Um filtro é uma expressão f do tipo Boolean.
Omite da consideração todas as ligações para as quais f é falso. A sequência s
começa em caad case com um gerador. Se houver vários geradores na sequência,
os geradores subsequentes variarão mais rapidamente que os anteriores.
A sequência s pode também ser envolvida em chaves ao invés de parênteses, e os
dois pontos entre geradores, definições e filtros podem ser omitidos.
Aqui estão dois exemplos que mostram como for-comprehensions são usados.
Primeiro, vamos refazer um exemplo do capítulo anterior: Dado um inteiro positivo
n, encontre todos os pares de inteiros positivos i e j , onde 1 ≤ j < i < n such that
i + j é primo. Com um for-comprehension este problema é resolvido como segue:
for { i <- List.range(1, n)
j <- List.range(1, i)
if isPrime(i+j) } yield {i, j}
Isto é discutivelmente mais claro que a solução usando map, flatMap e filter que
desenvolvemos previamente.
Como segundo exemplo, considere calcular o produto escalar de dois vetores xs e
ys. Usando um for-comprehension, isto pode ser escrito como segue.
sum(for ((x, y) <- xs zip ys) yield x * y)
10.1
O Problema das N-Rainhas
For-comprehensions são especialmente úteis para resolver puzzles combinatórios.
Um exemplo é o problema das 8-rainhas: Dado um tabuleiro de xadrez padrão,
coloque 8 rainhas, tal que nenhuma rainha esteja atacada por nenhuma outra
(uma rainha pode atacar qualquer outra peça se estiver na mesma coluna,
linha ou diagonal que a mesma). Desenvolveremos agora uma solução para
este problema, generalizando para tabuleiros de xadrez de tamanho arbitrário.
Consequentemente, o problema é colocar n rainhas em um tabuleiro de xadrez de
tamanho n × n.
Para resolver este problema, observe que precisamos colocar uma rainha em cada
linha. Logo podemos colocar rainhas em linhas sucessivas, cada vez checando que
uma rainha recentemente colocada não esteja atacada por qualquer outra rainha
que já se encontra no tabuleiro. No curso desta busca, pode acontecer que uma
rainha a ser colocada na linha k esteja atacada em todas as casas desta linha por
rainhas rainhas das linhas 1 até k −1. Neste caso, precisamos interromper esta parte
da busca e continuar com uma configuração diferente de rainhas nas colunas 1 até
k − 1.
Isso sugere um algoritmo recursivo. Assuma que já geramos todas as soluções para
colocar k − 1 rainhas em um tabuleiro de tamanho n × n. Podemos representar tal
10.2 Pesquisando com For-Comprehensions
83
solução por uma lista de tamanho k − 1 de números das colunas (no intervalo de
1 a n). Tratamos estas listas de soluções parciais como pilhas, onde o número da
coluna da rainha na linha k − 1 vem primeiro dentro da lista, seguido pelo número
da coluna da rainha na linha k − 2 etc. O fundo da pilha é o número da coluna da
rainha colocada na primeira linha do tabuleiro. Todas as soluções juntas são então
representadas como uma lista de listas, com um elemento para cada solução.
Agora, para colocar a k-ésima rainha, geramos todas as possíveis extensões para
cada solução prévia com uma rainha a mais. Isto leva a uma outra lista de listas
soluções, desta vez de tamanho k. Continuamos o processo até atingirmos soluções
do tamanho n do tabuleiro de xadrez. Esta idéia algorítmica é incorporada na
função placeQueens abaixo:
def queens(n: Int): List[List[Int]] = {
def placeQueens(k: Int): List[List[Int]] =
if (k == 0) List(List())
else for { queens <- placeQueens(k - 1)
column <- List.range(1, n + 1)
if isSafe(column, queens, 1) } yield column :: queens
placeQueens(n)
}
Exercício 10.1.1 Escreva a função
def isSafe(col: Int, queens: List[Int], delta: Int): Boolean
que testa se uma rainha numa dada coluna col está segura com respeito às queens
já colocadas. Aqui, delta é a diferença entre a linha da rainha a ser colocada e a
linha da primeira rainha da lista.
10.2
Pesquisando com For-Comprehensions
A notação for é essencialmente equivalente a operações comuns de linguagens de
pesquisa de bases de dados. Por exemplo, digamos que temos uma base de dados
books, representada como uma lista de livros, onde Book é definido como segue.
case class Book(title: String, authors: List[String])
Aqui está um pequeno exemplo de base de dados:
val books: List[Book] = List(
Book("Structure and Interpretation of Computer Programs",
List("Abelson, Harold", "Sussman, Gerald J.")),
Book("Principles of Compiler Design",
List("Aho, Alfred", "Ullman, Jeffrey")),
Book("Programming in Modula-2",
84
For-Comprehensions
List("Wirth, Niklaus")),
Book("Introduction to Functional Programming"),
List("Bird, Richard")),
Book("The Java Language Specification",
List("Gosling, James", "Joy, Bill", "Steele, Guy", "Bracha, Gilad")))
Então, para encontrar os títulos de todos os livros cujos autores tenham sobrenome
“Ullman”:
for (b <- books; a <- b.authors if a startsWith "Ullman")
yield b.title
(Aqui, startsWith é um método dentro em java.lang.String). Ou, para encontrar
os títulos de todos os livros que tenham a cadeia de caracteres “Program” em seu
título:
for (b <- books if (b.title indexOf "Program") >= 0)
yield b.title
Ou, para encontrar os nomes de todos os autores que escreveram pelo menos dois
livros, na base de dados.
for (b1 <- books; b2 <- books if b1 != b2;
a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
yield a1
A última solução ainda não é perfeita, porque autores aparecerão diversas vezes
na lista de resultados. Ainda precisamos remover autores duplicados das listas
resultantes. Isto pode ser obtido através da seguinte função.
def removeDuplicates[A](xs: List[A]): List[A] =
if (xs.isEmpty) xs
else xs.head :: removeDuplicates(xs.tail filter (x => x != xs.head))
Observe que a última expressão no método removeDuplicates pode ser
equivalentemente expresso usando um for-comprehension.
xs.head :: removeDuplicates(for (x <- xs.tail if x != xs.head) yield x)
10.3
Tradução de For-Comprehensions
Cada for-comprehension pode ser expresso em termos de três funções de
alta-ordem: map, flatMap e filter. Aqui está o esquema de tradução, que também
é usado pelo compilador Scala.
• Um for-comprehension simples
10.3 Tradução de For-Comprehensions
85
for (x <- e) yield e’
é traduzido para
e.map(x => e’)
• Um for-comprehension
for (x <- e if f; s) yield e’
onde f é um filtro e s é uma (possivelmente vazia) sequência de geradores ou
filtros, é traduzida para
for (x <- e.filter(x => f); s) yield e’
e então, a tradução continua com a última expressão.
• Um for-comprehension
for (x <- e; y <- e’; s) yield e’’
onde s é uma (possivelmente vazia) sequência de geradores ou filtros é
traduzida para
e.flatMap(x => for (y <- e’; s) yield e’’)
e então, a tradução continua com a última expressão.
Por exemplo, tomando nosso exemplo “pares de inteiros cuja soma é um primo”:
for { i <- range(1, n)
j <- range(1, i)
if isPrime(i+j)
} yield {i, j}
Aqui está o que obtemos quando traduzimos esta expressão:
range(1, n)
.flatMap(i =>
range(1, i)
.filter(j => isPrime(i+j))
.map(j => (i, j)))
De modo inverso, também seria possível expressar as funções map, flatMap e filter
usando for-comprehensions. Aqui estão as três funções novamente, desta vez
implementadas usando for-comprehensions.
object Demo {
def map[A, B](xs: List[A], f: A => B): List[B] =
86
For-Comprehensions
for (x <- xs) yield f(x)
def flatMap[A, B](xs: List[A], f: A => List[B]): List[B] =
for (x <- xs; y <- f(x)) yield y
def filter[A](xs: List[A], p: A => Boolean): List[A] =
for (x <- xs if p(x)) yield x
}
Não surpreendentemente, a tradução do for-comprehension no corpo de Demo.map
produzirá uma chamada para map na classe List. Similarmente, Demo.flatMap e
Demo.filter são traduzidos para flatMap e filter na classe List.
Exercício 10.3.1 Defina a seguinte função em termos de for.
def flatten[A](xss: List[List[A]]): List[A] =
(xss :\ (Nil: List[A])) ((xs, ys) => xs ::: ys)
Exercício 10.3.2 Traduza
for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title
for (b <- books if (b.title indexOf "Program") >= 0) yield b.title
para funções de alta ordem.
10.4
Laços For
For-comprehensions lembram os laços for das linguagens imperativas, exceto que
eles produzem uma lista de resultados. Algumas vezes, uma lista de resultados
não é necessária, mas ainda gostaríamos da flexibilidade dos geradores e filtros
nas iterações sobre listas. Isso é possível por uma variante da sintaxe dos
for-comprehensions, os quais expressam laços for:
for ( s ) e
Esta construção é a mesma da sintaxe padrão do for-comprehension, exceto que
a palavra chave yield está faltando. O laço for é executado pela execução da
expressão e para cada elemento gerado da sequência de geradores e filtros s.
Como um exemplo, a seguinte expressão imprime todos os elementos de uma
matriz representada como uma lista de listas:
for (xs <- xss) {
for (x <- xs) print(x + "\t")
println()
}
10.5 Generalizando For
87
A tradução de laços for para métodos de alta ordem da classe List é similar à
tradução de for-comprehensions, mas mais simples. Onde for-comprehensions são
traduzidos para map e flatMap, laços for traduzem em cada caso para foreach.
10.5
Generalizando For
Temos visto que a tradução de for-comprehensions somente ocorre na presença
dos métodos map, flatMap, e filter. Portanto é possível aplicar a mesma notação
para geradores que produzam outros objetos além de listas; tais objetos somente
tem de atender as três funções-chave map, flatMap, e filter.
A biblioteca padrão Scala tem diveras outras abstrações que suportam estes
três métodos e com eles suportam for-comprehensions. Encontraremos alguns
deles nos capítulos seguintes. Como programador você também pode usar este
princípio para habilitar for-comprehensions para tipos que você definiu—estes
tipos somente precisam suportar os métodos map, flatMap, e filter.
Há muitos exemplos onde isto é útil: interfaces de base de dados, árvores XML, ou
valores opcionais. Uma advertência: não há garantia automática que a tradução
resultante de um for-comprehension seja bem tipada. Para garantir isso, os tipos
de map, flatMap, e filter tem de ser essencialmente similares aos tipos desses
métodos na classe List. Para tornar isto preciso, assuma que você tenha uma classe
parametrizada C[A] para a qual você deseja habilitar for-comprehensions. Então C
deve definir map, flatMap, e filter com os seguintes tipos:
def map[B](f: A => B): C[B]
def flatMap[B](f: A => C[B]): C[B]
def filter(p: A => Boolean): C[A]
Seria atrativo forçar estes tipos estáticamente dentro do compilador Scala,
por exemplo, requerendo que qualquer tipo que suporte for-comprehensions
implemente um trait padrão com estes métodos 1 . O problema é que tal trait padrão
tem de abstrair sobre a identidade da classe C, por exemplo tomando C como um
tipo parâmetro. Observe que este parâmetro deve ser um tipo construtor, que
é aplicado a diversos diferentes tipos nas assinaturas dos métodos map e flatMap.
Infelizmente, o sistema de tipos Scala é muito fraco para expressar este construtor,
desde que pode lidar somente com tipos parâmetros que são tipos totalmente
aplicados.
1
Na linguagem de programação Haskell, que tem construtores similares, esta abstração é
chamada um “monada com zero”
Capítulo 11
Estados Mutáveis
A maioria dos programas apresentados até o momento não possui efeitos colaterais.
1
. Portanto, a noção de tempo não importou.
Para um programa que termina, qualquer sequência de ações levará ao mesmo
resultado! Isso também é refletido pelo modelo de computação de substituição,
onde um passo de reescrita pode ser aplicado em qualquer lugar de um termo, e
todas as reescritas que terminam levam a mesma solução. De fato, esta propriedade
de confluência é um profundo resultado do cálculo λ, a teoria que embasa a
programação funcional.
Neste capítulo, introduziremos funções com efeitos colaterais e estudaremos seu
comportamento. Veremos que como consequência temos fundamentalmente que
modificar o modelo de substituição de computação empregado até aqui.
11.1
Objetos Mutáveis
Normalmente vemos o mundo como um conjunto de objetos, alguns dos quais
com estado que muda através do tempo. Normalmente, o estado é associado com
um conjunto de variáveis que podem ser alteradas no curso de uma computação.
Há também uma noção mais abstrata de estado, que não se refere a construções
particulares de uma linguagem de programação: um objeto tem estado (ou: é
mutável) se seu comportamento é influenciado por sua história.
Por exemplo, uma objeto conta de banco tem estado, porque a questão “Eu posso
sacar R$ 100?” pode ter diferentes respostas durante o tempo de vida da conta.
Em Scala, todos os estados mutáveis são em última análise criados a partir das
variáveis. Uma definição de variável é escrita como uma definição de valor, mas
1
Ignoramos o fato de que algums dos programas imprimem na tela, o que, tecnicamente, é um
efeito colateral.
90
Estados Mutáveis
começa com var ao invés de val. Por exemplo, os duas definições seguintes
introduzem e inicializam duas variáveis x e count.
var x: String = "abc"
var count = 111
Como uma definição de valor, uma definição de variável associa um nome com
um valor. Mas no caso da definição de variável, esta associação pode ser alterada
posteriormente através de uma atribuição. Tais atribuições são escritas em C ou
Java. Exemplos:
x = "hello"
count = count + 1
Em Scala, cada variável definida tem de ser inicializada no ponto de sua definição.
Por exemplo, a declaração var x: Int; não é tida como uma definição de variável,
porque o inicializador está ausente2 . Se não se sabe, ou não é importante, o
inicializador apropriado, pode-se usar um caracter coringa no lugar. Ou seja,
val x: T = _
inicializará x para algum valor default (null para tipos referência, false para
boleanos, e a versão apropriada de 0 para valores de tipos numéricos).
Objetos do mundo real com estado são representados em Scala através de objetos
que tem variáveis como membros. Por exemplo, aqui está uma classe que
representa contas bancárias.
class BankAccount {
private var balance = 0
def deposit(amount: Int) {
if (amount > 0) balance += amount
}
def withdraw(amount: Int): Int =
if (0 < amount && amount <= balance) {
balance -= amount
balance
} else error("insufficient funds")
}
A classe define uma variável balance que contém o balanço corrente de uma conta.
Métodos deposit e whithdraw mudam o valor desta variável através de atribuições.
Observe que balance e private na classe BankAccount – consequentemente não
2
Se uma declaração como esta aparece numa classe, é tida como uma declaração de variável,
que introduz métodos de acesso abstratos para a variável, mas não associa estes métodos com um
pedaço do estado.
11.1 Objetos Mutáveis
91
pode ser acessado diretamente fora da classe. Para criar contas bancárias, usamos
a notação usual para criação de objeto:
val myAccount = new BankAccount
Exemplo 11.1.1 Aqui está uma sessão scalaint que lida com contas bancárias.
scala> :l bankaccount.scala
Loading bankaccount.scala...
defined class BankAccount
scala> val account = new BankAccount
account: BankAccount = BankAccount$class@1797795
scala> account deposit 50
unnamed0: Unit = ()
scala> account withdraw 20
unnamed1: Int = 30
scala> account withdraw 20
unnamed2: Int = 10
scala> account withdraw 15
java.lang.Error: insufficient funds
at scala.Predef$error(Predef.scala:74)
at BankAccount$class.withdraw(<console>:14)
at <init>(<console>:5)
scala>
O exemplo mostra que aplicando a mesma operação (withdraw 20) duas vezes
para uma conta gera resultados diferentes. Então, claramente, contas são objetos
dinâmicos.
Constância e Alteração. Atribuições colocam novos problemas na decisão de
quando duas expressões são “a mesma”. Se atribuições são excluídas, e escrevemos
val x = E; val y = E
onde E é alguma expressão arbitrária, então x e y podem ser assumidos
razoavelmente como sendo o mesmo. Ou seja, poderia-se equivalentemente
escrever
val x = E; val y = x
(Esta propriedade é geralmente chamada transparência referencial). Mas uma
vez que admitimos atribuições, as duas sequências de definições são diferentes.
Considere:
val x = new BankAccount; val y = new BankAccount
92
Estados Mutáveis
Para responder a questão se x e y são o mesmo, precisamos ser mais precisos sobre
o que significa constância. Este significado é capturado na noção de equivalência
operacional, a qual, de modo um tanto quanto informal, é descrita como segue.
Suponha que temos duas definições para x e y. Para testar se x e y definem o mesmo
valor, proceda como segue.
• Execute as definições seguidas para uma sequência arbitrária S de operações
que envolvam x e y. Observe o resultado (se houver).
• Então, execute as definições com uma outra sequência S’ resultante de S pela
renomeação de todas as ocorrências de y em S para x.
• Se os resultados da execução de S’ forem diferentes, então certamente x e y
são diferentes.
• Por outro lado, se todos os possíveis pares de sequências {S, S’} dão os
mesmos resultados, então x e y são o mesmo.
Em outras palavras, equivalência operacional levam duas definições x e y como
definindo o mesmo valor, se nenhum experimento possível puder distinguir entre
x e y. Um experimento neste contexto são duas versões de um programa arbitrário
que usa ou x ou y.
Dada esta definição, vamos testar se
val x = new BankAccount; val y = new BankAccount
definem valores x e y que são o mesmo. Aqui estão as definições novamente,
seguidas por uma sequência de testes:
> val x = new BankAccount
> val y = new BankAccount
> x deposit 30
30
> y withdraw 20
java.lang.RuntimeException: insufficient funds
Agora, renomeie todas as ocorrências de y naquela sequência para x. Obtemos:
> val x = new BankAccount
> val y = new BankAccount
> x deposit 30
30
> x withdraw 20
10
Como os resultados finais são diferentes, estabelecemos que x e y não são o mesmo.
Por outro lado, se definimos
11.2 Estruturas Imperativas de Controle
93
val x = new BankAccount; val y = x
então nenhuma sequência de operações pode distiguir entre x e y, portanto x e y
são o mesmo neste caso.
Atribuição e o Modelo de Substituição. Estes exemplos mostram que nosso
modelo de substituição computacional não mais pode ser usado. Afinal de contas,
sob este modelo nem sempre podemos substituir um valor de nome por sua
expressão definida. Por exemplo em
val x = new BankAccount; val y = x
o x na definição de y pode ser substituído por new BankAccount. Mas vimos que
esta alteração leva a programas distintos. Então o modelo de substituição deve ser
inválido, uma vez que adicionemos atribuições.
11.2
Estruturas Imperativas de Controle
Scala tem construções de laços while e do-while derivadas das linguagens de
programação C e Java. Também há uma ramificação única if que deixa de
fora a parte “else”, bem como uma declaração return que aborta uma função
prematuramente. Isso torna possível programar no estilo imperativo convencional.
Por exemplo, a seguinte função, que computa a enésima potência de um dado
parâmetro x, é implementada usando while e um if simples.
def power(x: Double, n: Int): Double = {
var r = 1.0
var i = n
var j = 0
while (j < 32) {
r = r * r
if (i < 0)
r *= x
i = i << 1
j += 1
}
r
}
Estas construções de controle imperativo estão na linguagem por conveniência.
Poderiam ser deixadas de fora, pois as mesmas construções podem ser
implementadas usando apenas funções. Como exemplo, vamos desenvolver uma
implementação funcional para o laço while. whileLoop deve ser uma função que
recebe dois parâmetros: uma condição, de tipo Boolean, e um comando, de tipo
94
Estados Mutáveis
Unit. Ambos, condição e comando, devem ser passados por nome, dado que serão
avaliados repetidamente para cada iteração do laço. Isso leva a seguinte definição
para whileLoop.
def whileLoop(condition: => Boolean)(command: => Unit) {
if (condition) {
command; whileLoop(condition)(command)
} else ()
}
Observe que WhileLoop é uma recursão de cauda, logo opera em um espaço de pilha
constante.
Exercício 11.2.1 Escreva uma função repeatLoop, que deve ser aplicada como
segue:
repeatLoop { command } ( condition )
Há também um modo de se obter uma sintaxe de laço como a seguinte?
repeatLoop { command } until ( condition )
Algumas outras construções de controle conhecidas do C e do Java estão ausentes
em Scala: não há break e continue. Também não há laços “for” similares ao Java –
estes foram substituídos por uma construção de laço “for” mais geral, discutida na
Seção 10.4.
11.3
Exemplo Estendido: Simulação de Eventos Discretos
Agora discutiremos um exemplo que demonstra como atribuições e funções de
alta ordem podem ser combinados de maneiras interessantes. Construiremos um
simulador para circuitos digitais.
O exemplo é emprestado do livro do Abelson e Sussman [ASS96]. Nós expandimos o
código básico (Scheme-) através de uma estrutura orientada a objetos que permite
reuso de código por meio de herança. O exemplo também mostra como programas
de simulação de eventos discretos em geral são estruturados e construídos.
Começamos com uma pequena linguagem para descrever circuitos digitais. Um
circuito digital é criado a partir de fios e caixas função. Fios carregam sinais que
são transformados por caixas função. Representaremos sinais pelos boleanos true
e false.
Caixas função básicas (ou: portas) são:
• Um inversor, o qual nega seu sinal.
11.3 Exemplo Estendido: Simulação de Eventos Discretos
95
• Uma porta E, o qual determina sua saída com base na conjunção da sua
entrada.
• Uma porta OU, o qual determina sua saída com base na disjunção da sua
entrada.
Outras portas lógicas pode ser construídas pela combinação das portas básicas.
Portas tem delays, portanto a saída de uma porta somente mudará algum tempo
após a mudança da sua entrada.
Uma Linguagem para Circuitos Digitais. Descrevemos os elementos de um
circuito digital através do seguinte conjunto de classes e funções Scala.
Primeiro, há uma classe Wire para fios. Podemos construir fios como segue.
val a = new Wire
val b = new Wire
val c = new Wire
Segundo, há procedimentos
def inverter(input: Wire, output: Wire)
def andGate(a1: Wire, a2: Wire, output: Wire)
def orGate(o1: Wire, o2: Wire, output: Wire)
que “criam” as portas lógicas básicas que precisamos (como efeitos colaterais).
Portas mais complicadas pode agora ser construídas a partir destas. Por exemplo,
para construir um circuito meia soma, podemos definir:
def halfAdder(a: Wire, b: Wire, s: Wire, c: Wire) {
val d = new Wire
val e = new Wire
orGate(a, b, d)
andGate(a, b, c)
inverter(c, e)
andGate(d, e, s)
}
Esta abstração pode ela mesma ser usada, por exemplo, na definição de um circuito
soma completo:
def fullAdder(a: Wire, b: Wire, cin: Wire, sum: Wire, cout: Wire) {
val s = new Wire
val c1 = new Wire
val c2 = new Wire
halfAdder(a, cin, s, c1)
halfAdder(b, s, sum, c2)
96
Estados Mutáveis
orGate(c1, c2, cout)
}
A classe Wire e as funções inverter, andGate, e orGate representam, portanto, uma
pequena linguagem na qual usuários podem definir circuitos digitais. Agora damos
implementações destas classes e funções, que nos permite simalar circuitos. Essa
implementações são baseadas numa API simples e geral para simulação de eventos
discretos.
A API Simulação. A simulação de eventos discretos realiza ações definidas pelo
usuário em tempos específicos. Uma ação é representada como uma função que
não recebe parâmetros e retorna um resultado Unit:
type Action = () => Unit
O tempo é simulado; não é o horário atual do “relógio de parede”.
Uma simulação concreta será efetuada dentro do objeto que herda a classe abstrata
Simulation. Esta classe tem a seguinte assinatura:
abstract class Simulation {
def currentTime: Int
def afterDelay(delay: Int, action: => Action)
def run()
}
Aqui, currentTime retorna o tempo corrente como um número inteiro, afterDelay
agenda uma ação para ser realizada com um atraso específico após currentTime, e
run executa a simulação até que não haja mais ações a serem realizadas.
A Classe Fio (Wire).
Um fio precisa atender a três ações básicas.
getSignal: Boolean retorna o sinal corrente sobre o fio.
setSignal(sig: Boolean) atualiza o sinal do fio para sig.
addAction(p: Action) junta o procedimento especificado p nas ações do fio.
Todos os procedimentos juntados às ações serão executados toda vez que o
sinal do fio mudar.
Aqui está uma implementação da classe Wire (fio):
class Wire {
private var sigVal = false
private var actions: List[Action] = List()
def getSignal = sigVal
def setSignal(s: Boolean) =
11.3 Exemplo Estendido: Simulação de Eventos Discretos
97
if (s != sigVal) {
sigVal = s
actions.foreach(action => action())
}
def addAction(a: Action) {
actions = a :: actions; a()
}
}
Duas variáveis privadas compõem o estado de um fio. A variável sigVal denota o
sinal corrente, e a variável actions denota os procedimentos de ação atualmente
juntados ao fio.
A Classe Inversor. Implementamos um inversor instalando uma ação ao seu fio
de entrada, ou seja, a ação que coloca a entrada negada sobre o sinal de saída.
A ação precisa ter efeito nas unidades de tempo simulado InverterDelay após a
entrada mudar. Isso sugere a seguinte implementação:
def inverter(input: Wire, output: Wire) {
def invertAction() {
val inputSig = input.getSignal
afterDelay(InverterDelay) { output setSignal !inputSig }
}
input addAction invertAction
}
A Classe And-Gate (Porta E). Portas E são implementadas analogamente a
inversores. A ação de uma andGate é criar na saída a conjunção dos seus sinais
de entrada. Isso deve ocorrer nas unidades de tempo simulado AndGateDelay após
qualquer de suas duas entradas mudar. Consequentemente, temos a seguinte
implementação:
def andGate(a1: Wire, a2: Wire, output: Wire) {
def andAction() {
val a1Sig = a1.getSignal
val a2Sig = a2.getSignal
afterDelay(AndGateDelay) { output setSignal (a1Sig & a2Sig) }
}
a1 addAction andAction
a2 addAction andAction
}
Exercício 11.3.1 Escreva a implementação da porta lógica OU (orGate).
98
Estados Mutáveis
Exercício 11.3.2 Um outro modo de se definir uma porta OU é pela combinação de
inversores e portas E. Defina uma função orGate em termos de andGate e inverter.
Qual o tempo de atraso desta função?
A Classe Simulação. Agora, só falta implementar a classe Simulation. A idéia é
manter dentro de um objeto Simulation uma agenda de ações a serem realizadas.
A agenda é representada como uma lista de pares de ações e os tempos a serem
executadas. A lista agenda é ordenada, portanto ações que devem ocorrer mais cêdo
precedem as que devem ocorrer depois.
abstract class Simulation {
case class WorkItem(time: Int, action: Action)
private type Agenda = List[WorkItem]
private var agenda: Agenda = List()
Há também uma variável privada curtime para acompanhar o tempo simulado
corrente.
private var curtime = 0
Uma aplicação do método afterDelay(delay, block) insere o elemento
WorkItem(currentTime + delay, () => block) dentro da lista agenda no lugar
apropriado.
private def insert(ag: Agenda, item: WorkItem): Agenda =
if (ag.isEmpty || item.time < ag.head.time) item :: ag
else ag.head :: insert(ag.tail, item)
def afterDelay(delay: Int)(block: => Unit) {
val item = WorkItem(currentTime + delay, () => block)
agenda = insert(agenda, item)
}
Uma aplicação para o método run remove sucessivos elementos da agenda e realiza
suas ações. Continua até que a agenda esteja vazia:
private def next() {
agenda match {
case WorkItem(time, action) :: rest =>
agenda = rest; curtime = time; action()
case List() =>
}
}
def run() {
afterDelay(0) { println("*** simulation started ***") }
11.4 Sumário
99
while (!agenda.isEmpty) next()
}
Executando o Simulador. Para executar o simulador, ainda precisamos de um
modo de inspecionar mudanças de sinais sobre os fios. Para este propósito,
escrevemos uma função probe (sonda).
def probe(name: String, wire: Wire) {
wire addAction { () =>
println(name + " " + currentTime + " new_value = " + wire.getSignal)
}
}
Agora, para vermos o simulador em ação, vamos definir quatro fios, e colocar duas
sondas sobre dois deles:
scala> val input1, input2, sum, carry = new Wire
scala> probe("sum", sum)
sum 0 new_value = false
scala> probe("carry", carry)
carry 0 new_value = false
Agora vamos definir um circuito meia soma conectando os fios:
scala> halfAdder(input1, input2, sum, carry)
Finalmente, setamos um após o outro os sinais sobre os dois fios de entrada para
true e rodamos a simulação.
scala> input1 setSignal true; run
*** simulation started ***
sum 8 new_value = true
scala> input2 setSignal true; run
carry 11 new_value = true
sum 15 new_value = false
11.4
Sumário
Vimos neste capítulo as construções que nos permitiram modelar estados em Scala
– que são variáveis, atribuições, e estruturas de controle imperativo. Estados e
Atribuições complicam nosso modelo mental de computação. Em particular, a
100
Estados Mutáveis
transparência referencial é perdida. Por outro lado, atribuição nos dá novos meios
para formular programas elegantemente. Como sempre, isso depende de qual
funciona melhor para uma dada situação: programas puramente funcionais ou
programas com atribuições.
Capítulo 12
Computando com Streams
Os capítulos anteriores apresentaram variáveis, atribuição e objetos com estado.
Vimos como objetos no mundo real mudam com o tempo e podem ser modelados
através da mudança de estado das suas variáveis durante a computação. Desta
maneira, mudanças no tempo no mundo real são modeladas por mudanças no
tempo durante a execução do programa. Obviamente, usa-se uma escala e estas
mudanças no tempo são alargadas ou comprimidas, mas sua ordem relativa
permanece a mesma. Isto pode parecer natural, mas existe um preço a se pagar:
o modelo de substituição usado na computação funcional não pode ser aplicado ao
se introduzir variáveis e atribuições.
Será que não existe uma outra maneira? Não seria possível modelar mudanças de
estado no mundo real usando somente funções imutáveis? Tomando matemática
como um guia, a resposta claramente é sim: um quantidade que muda no tempo
é modelada através da função f(t) que tem como parâmetro t para representar
o tempo. O mesmo pode ser feito na computação. Ao invés de sobre-escrever
uma variável com sucessivos valores, podemos representar estes valores como
sucessivos elementos em uma lista. Desta forma, a variável mutável var x: T
pode ser substituída por uma variável imutável val x: List[T]. De certa maneira,
troca-se espaço por tempo – os diferentes valores da variável agora existem
concorrentemente como diferentes elementos da lista. Uma das vantagens do
modelo baseado em lista é a possibilidade de “viajar no tempo”, ou seja, de ver
sucessivos valores da variável ao mesmo tempo. Uma outra vantagem é que
podemos fazer uso da poderosa biblioteca de funções processamento de listas, que
normalmente simplifica a computação. Por exemplo, considere a forma imperativa
de computar a soma de todos os primos em um intervalo:
def sumPrimes(start: Int, end: Int): Int = {
var i = start
var acc = 0
while (i < end) {
102
Computando com Streams
if (isPrime(i)) acc += i
i += 1
}
acc
}
Note que a variável i “passa por” todos os valores do intervalo [start .. end-1].
Uma forma mais funcional, é representar a lista de valores da variável i diretamente
como range(start, end). Então a função pode ser re-escrita da seguinte maneira:
def sumPrimes(start: Int, end: Int) =
sum(range(start, end) filter isPrime)
Não dúvida que o programa é mais curto e mais claro! Porém, o programa funcional
é também consideravelmente menos eficiente, uma vez que ele constrói a lista de
todos os número no intervalo e, posteriormente, constrói uma outra lista com os
números primos. Ainda pior sob o ponto de vista da eficiência é o seguinte exemplo:
Para encontrar o segundo número primio entre 1000 e 10000:
range(1000, 10000) filter isPrime at 1
Aqui, a lista de todos os números entre 1000 e 10000 é construída, mas a maior parte
da lista nunca é usada!
No entanto, pode-se obter uma execução eficiente para exemplos como este usando
um truque:
Nunca compute o resto (tail) de uma sequência a não ser que o resto
seja realmente necessário para a computação.
Para isso, definimos uma nova classe para sequências, que é chamada Stream.
Streams são criados usando a constante empty e o construtor cons, ambos definidos
no módulo scala.Stream. Por exemplo, a seguinte expressão constrói um stream
como os elementos 1 e 2:
Stream.cons(1, Stream.cons(2, Stream.empty))
Como um outro exemplo, este é o análogo de List.range, mas que retorna um
stream ao invés de uma lista:
def range(start: Int, end: Int): Stream[Int] =
if (start >= end) Stream.empty
else Stream.cons(start, range(start + 1, end))
(Esta função também foi definida como mostrado anteriormente no módulo
Stream). Embora Stream.range e List.range se pareçam, seu comportamento em
tempo de execução é completamente diferente:
103
Stream.range retorna imediatamente um objeto do tipo Stream cujo primeiro
elemento é start. Todos os outros elementos são computados somente quando
eles são demandados através da chamada do método tail (o que pode nunca
acontecer).
Streams são acessados exatamente como listas. Similarmente às listas, os métodos
básicos de acesso são isEmpty, head e tail. Por exemplo, podemos imprimir todos
os elementos de um stream da seguinte maneira.
def print(xs: Stream[A]) {
if (!xs.isEmpty) { Console.println(xs.head); print(xs.tail) }
}
Streams também oferecem praticamente todos os outros métodos definidos nas
listas (veja a seguir onde os conjuntos de métodos são diferentes). Por exemplo,
podemos encontrar o segundo número primo entre 1000 e 10000 através do uso
dos métodos filter e apply no stream que fornece o intervalo:
Stream.range(1000, 10000) filter isPrime at 1
A diferença entre a implementação anterior que usada lista, é que agora não
construímos nem testamos se é primo nenhum número maior que 1013.
Retorno e concatenação de streams. Há dois métodos na classe List que não
estão presentes na classe Stream. São eles :: e :::. O motivo é que estes métodos
são chamados pelo argumento da direita, o que significa que este argumento
precisa ser computado antes que o método seja chamado. Por exemplo, no caso
de x :: xs nas listas, o resto xs precisa ser computado antes de :: ser chamado
e a nova lista ser construída. Isto não funciona para streams, onde queremos que
o resto de um stream não seja computado até que seja demandado pela chamada
ao método tail. O argumento pelo qual a concatenação de listas ::: não pode ser
adaptado para streams é análogo.
Ao invés de x :: xs, pode-se usar Stream.cons(x, xs) para construir um stream
com o primeiro elemento x e o resto (não computado). Ao invés de xs ::: ys,
pode-se usar xs append ys.
Capítulo 13
Iteradores
Iteradores são uma versão imperativa dos streams. Assim como streams, iteradores
descrevem listas potencialmente infinitas. No entanto, não existe uma estrutura
de dados que contenha os elementos de um iterador. Ao invés disso, os iteradores
permitem que se ande somente um passo na sequência de cada vez, usando os
métodos abstratos next e hasNext.
trait Iterator[+A] {
def hasNext: Boolean
def next: A
O método next retorna sucessivos elementos. O método hasNext indica se existem
mais elementos a serem retornados por next. Iteradores também possuem outros
métodos que serão explicados posteriormente.
Como exemplo, esta é uma aplicação que imprime os quadrados de todos os
números de 1 à 100.
val it: Iterator[Int] = Iterator.range(1, 100)
while (it.hasNext) {
val x = it.next
println(x * x)
}
13.1
Métodos dos Iteradores
Os iteradores possuem um conjunto de métodos além de next e hasNext, que
são descritos a seguir. Muitos destes métodos oferecem uma funcionalidade
correspondente à do método equivalente em uma lista.
106
Iteradores
Append. O método append constrói uma iterador que começa com o código dado
de iteração it depois que o iterador atual tem terminado.
def append[B >: A](that: Iterator[B]): Iterator[B] = new Iterator[B] {
def hasNext = Iterator.this.hasNext || that.hasNext
def next = if (Iterator.this.hasNext) Iterator.this.next else that.next
}
Os termos Iterator.this.next e Iterator.this.hasNext na definição de append
chamam os métodos correspondentes definidos na classe Iterator que contém o
método append. Se o prefixo Iterator não fosse adicionado ao this, hasNext e next
chamariam recursivamente os métodos definidos no resultado de append, o que não
era o efeito desejado.
Map, FlatMap, Foreach. O método map constrói um iterador que retorna todos os
elementos do iterador original transformados por uma dada função f.
def map[B](f: A => B): Iterator[B] = new Iterator[B] {
def hasNext = Iterator.this.hasNext
def next = f(Iterator.this.next)
}
O método flatMap é similar ao método map, exceto que a função de transformação f
retorna um iterador ao invés de um elemento. O resultado de flatMap é um iterador
resultante da anexação (append) de todos os iteradores resultantes das sucessivas
chamadas de f.
def flatMap[B](f: A => Iterator[B]): Iterator[B] = new Iterator[B] {
private var cur: Iterator[B] = Iterator.empty
def hasNext: Boolean =
if (cur.hasNext) true
else if (Iterator.this.hasNext) { cur = f(Iterator.this.next); hasNext }
else false
def next: B =
if (cur.hasNext) cur.next
else if (Iterator.this.hasNext) { cur = f(Iterator.this.next); next }
else error("next on empty iterator")
}
Também relacionado à map, temos o método foreach que aplica uma dada função
a todos elementos de um iterador, mas não constrói uma lista de resultados
def foreach(f: A => Unit): Unit =
while (hasNext) { f(next) }
13.1 Métodos dos Iteradores
107
Filter. O método filter constrói um iterador que retorna todos os elementos do
iterador original que satisfazem um dado critério p.
def filter(p: A => Boolean) = new BufferedIterator[A] {
private val source =
Iterator.this.buffered
private def skip =
{ while (source.hasNext && !p(source.head)) { source.next } }
def hasNext: Boolean =
{ skip; source.hasNext }
def next: A =
{ skip; source.next }
def head: A =
{ skip; source.head }
}
Na prática, filter retorna uma instância de uma sub-classe dos iteradores que
trabalha com um “buffer”. Um objeto do tipo BufferedIterator é um iterador que
tem adicionalmente um método head. Este método retorna um elemento que seria
retornado pelo método next, porém não avança além daquele elemento. Com isso,
o elemento retornado por head é retornado novamente pela próxima chamada de
head ou next. Esta é a definição do trait BufferedIterator:
trait BufferedIterator[+A] extends Iterator[A] {
def head: A
}
Como map, flatMap, filter e foreach existem para iteradores, como consequência
for-comprehensions e loops de for também podem ser usados em iteradores. Por
exemplo, a aplicação que imprime os quadrados dos números entre 1 e 100 poderia
ter sido expressada da seguinte forma:
for (i <- Iterator.range(1, 100))
println(i * i)
Zip. O método zip recebe um outro iterador e retorna um iterador que consiste
de pares dos respectivos elementos retornados pelos dois iteradores.
def zip[B](that: Iterator[B]) = new Iterator[(A, B)] {
def hasNext = Iterator.this.hasNext && that.hasNext
def next = (Iterator.this.next, that.next)
}
}
108
Iteradores
13.2
Construindo Iteradores
As classes concretas de iteradores precisam implementar os dois métodos abstratos
next e hasNext definidos na classe Iterator.
O iterador mais simples é
Iterator.empty que sempre retorna uma sequência vazia:
object Iterator {
object empty extends Iterator[Nothing] {
def hasNext = false
def next = error("next on empty iterator")
}
Um iterador um pouco mais interessante enumera todos os elementos de um vetor.
Este iterador é construído a partir do método fromArray, que também foi definido
no objeto Iterator
def fromArray[A](xs: Array[A]) = new Iterator[A] {
private var i = 0
def hasNext: Boolean =
i < xs.length
def next: A =
if (i < xs.length) { val x = xs(i); i += 1; x }
else error("next on empty iterator")
}
Um outro iterador enumera um intervalo de inteiros. A função Iterator.range
retorna o iterador que caminha em um intervalo dado de valores inteiros. Sua
definição é a seguinte:
object Iterator {
def range(start: Int, end: Int) = new Iterator[Int] {
private var current = start
def hasNext = current < end
def next = {
val r = current
if (current < end) current += 1
else error("end of iterator")
r
}
}
}
Todos os iteradores mostrados até agora tem um fim. Também é possível definir
iteradores que nunca terminam. Por exemplo, o iterador a seguir retorna inteiros
sucessivos a partir de um valor inicial. 1 .
1
Como a representação do tipo int é finita, os números acabaram em 231 .
13.3 Usando Iteradores
109
def from(start: Int) = new Iterator[Int] {
private var last = start - 1
def hasNext = true
def next = { last += 1; last }
}
13.3
Usando Iteradores
Existem mais 2 exemplos de como os iteradores são usados. Primeiro, para
imprimir todos os elementos de um vetor xs: Array[Int], uma pessoa pode
escrever:
Iterator.fromArray(xs) foreach (x => println(x))
Ou, usando for-comprehension:
for (x <- Iterator.fromArray(xs))
println(x)
Como um segundo exemplo, considere o problema de encontrar os índices de todos
os elementos de um vetor de doubles maiores que um dado limit. Os índices
devem ser retornado na forma de um iterador. Isto pode ser obtido pela expressão:
import Iterator._
fromArray(xs)
.zip(from(0))
.filter(case (x, i) => x > limit)
.map(case (x, i) => i)
Ou usando for-comprehension:
import Iterator._
for ((x, i) <- fromArray(xs) zip from(0); x > limit)
yield i
Capítulo 14
Valores Preguiçosos (Lazy)
Valores preguiçosos oferecem uma maneira de postergar a inicialização de um valor
até o primeiro momento em que seja acessado. Isto pode ser útil quando estiver
lidando com valores que podem não ser necessários durante a execução e cujo
custo computacional seja significativo. Como primeiro exemplo, vamos considerar
um banco de dados de empregados contendo cada empregado e seu gestor e sua
equipe.
case class Employee(id: Int,
name: String,
managerId: Int) {
val manager: Employee = Db.get(managerId)
val team: List[Employee] = Db.team(id)
}
A classe Employee dada anteriormente irá tentar inicializar todos os seus campos,
carregando todoa a tabela de empregados na memória. Isto certamente não é
o ideal e pode ser melhorado como facilidade tornando os campos preguiçosos.
Desta forma, atrasamos o acesso ao banco de dados até o momento em que ele seja
realmente necessário, se isto ocorrer.
case class Employee(id: Int,
name: String,
managerId: Int) {
lazy val manager: Employee = Db.get(managerId)
lazy val team: List[Employee] = Db.team(id)
}
Para ver o que realmente está acontecendo, podemos usar este banco de dados
mock que mostra quando os registros são acessados:
object Db {
112
Valores Preguiçosos (Lazy)
val table = Map(1
2
3
4
5
->
->
->
->
->
(1,
(2,
(3,
(4,
(5,
"Haruki Murakami", -1),
"Milan Kundera", 1),
"Jeffrey Eugenides", 1),
"Mario Vargas Llosa", 1),
"Julian Barnes", 2))
def team(id: Int) = {
for (rec <- table.values.toList; if rec._3 == id)
yield recToEmployee(rec)
}
def get(id: Int) = recToEmployee(table(id))
private def recToEmployee(rec: (Int, String, Int)) = {
println("[db] fetching " + rec._1)
Employee(rec._1, rec._2, rec._3)
}
}
Ao rodar o programa, a saída confirma que ele retorna um empregado e que o banco
somente é acessado quando é feita uma referência ao valor preguiçoso.
Um outro uso dos valores preguiçosos é para resolver a ordem de inicialização de
aplicações compostas de muitos módulos. Antes dos valores preguiçosos serem
criados, o mesmo efeito era conquistado usando definições do tipo object. Como
um segundo exemplo considere um compilador composto de diversos módulos.
Olhamos primeiro para uma tabela de símbolos que definie uma classe para
símbolos e duas funções pré-definidas.
class Symbols(val compiler: Compiler) {
import compiler.types._
val Add = new Symbol("+", FunType(List(IntType, IntType), IntType))
val Sub = new Symbol("-", FunType(List(IntType, IntType), IntType))
class Symbol(name: String, tpe: Type) {
override def toString = name + ": " + tpe
}
}
O módulo Symbols é parametrizado com uma instância de Compiler que permite
o acesso a outros serviços, tais como o módulo de tipos. Em nosso exemplo,
há somente duas funções pré-definidas, adição e subtração e suas definições
dependem do módulo types.
class Types(val compiler: Compiler) {
import compiler.symtab._
113
abstract class Type
case class FunType(args: List[Type], res: Type) extends Type
case class NamedType(sym: Symbol) extends Type
case object IntType extends Type
}
Para conectar os dois componentes, um objeto do tipo compilador é criado e
passado com parâmetro para os dois componentes.
class Compiler {
val symtab = new Symbols(this)
val types = new Types(this)
}
Infelizmente, esta abordagem falha em tempo de execução, pois o módulo symtab
depende do módulo types. De maneira geral, a dependência entre os módulos
pode ficar complicada e conseguir a ordem correta de inicialização é difícil ou,
até mesmo, impossível, quando existem dependências cíclicas. A maneira mais
simples de corrigir este erro é tornar estes campos lazy e deixar o compilador
descobrir qual é a ordem correta de inicialização.
class Compiler {
lazy val symtab = new Symbols(this)
lazy val types = new Types(this)
}
Aogra os dois módulos são inicializados no primeiro acesso e o compilador pode
executar da forma esperada.
Sintaxe
O modificador lazy é permitido apenas na definição de valores concretos. Todas
as regras válidas para definição de valores se aplicam também para valores do tipo
lazy, com uma restrição a menos: valores locais recursivos são permitidos.
Capítulo 15
Parâmetros
Conversões
Implícitos
e
Parâmetros implícitos e conversões são ferramentas poderosas para personalizar
bibliotecas existentes e para criar abstrações de alto-nível. Como exemplo, vamos
começar com uma classe abstrata SemiGroup que contém uma operação não
especificada chamada add.
abstract class SemiGroup[A] {
def add(x: A, y: A): A
}
Aqui está a sub-classe abstrata Monoid que herda de SemiGroup e inclui um novo
elemento unit.
abstract class Monoid[A] extends SemiGroup[A] {
def unit: A
}
Aqui estão duas implementações de Monoid:
object stringMonoid extends Monoid[String] {
def add(x: String, y: String): String = x.concat(y)
def unit: String = ""
}
object intMonoid extends Monoid[Int] {
def add(x: Int, y: Int): Int = x + y
def unit: Int = 0
}
116
Parâmetros Implícitos e Conversões
O método sum, que funciona com monoids arbitrários pode ser escrito em Scala da
seguinte forma:
def sum[A](xs: List[A])(m: Monoid[A]): A =
if (xs.isEmpty) m.unit
else m.add(xs.head, sum(m)(xs.tail)
O método sum pode ser chamado da seguinte forma:
sum(List("a", "bc", "def"))(stringMonoid)
sum(List(1, 2, 3))(intMonoid)
Embora tudo isso funcione, o código não fica muito limpo. O problema é que as
implementações de monoid tem que ser passada para todo o código que as usa. Nós
gostaríamos que o sistema conseguisse descobrir os argumentos de forma correta e
automática, semelhante ao que é feito quando o tipo de parâmetros é inferido. Isto
é o que os parâmetros implícitos permite.
Noções Básicas sobre Parâmetros Implícitos
Na versão 2 de Scala, há uma nova palavra-chave (implicit) que pode ser usada no
início de uma lista de parâmetros. Sintaxe:
ParamClauses ::= {‘(’ [Param {‘,’ Param}] ’)’}
[‘(’ implicit Param {‘,’ Param} ‘)’]
Se esta palavra chave estiver presente, todos os parâmetros da lista serão implícitos.
Por exemplo, a versão de sum a seguir tem m como um parâmetro implícito.
def sum[A](xs: List[A])(implicit m: Monoid[A]): A =
if (xs.isEmpty) m.unit
else m.add(xs.head, sum(xs.tail))
Como pode ser visto no exemplo, é possível combinar parâmetros normais e
implícitos. No entanto, pode haver apenas uma lista de parâmetros implícitos e
ela deve vir por último.
implicit também pode ser usado como um modificador de declarações e
definições. Exemplos:
implicit object stringMonoid extends Monoid[String] {
def add(x: String, y: String): String = x.concat(y)
def unit: String = ""
}
implicit object intMonoid extends Monoid[Int] {
def add(x: Int, y: Int): Int = x + y
def unit: Int = 0
}
117
A principal ideia por trás de parâmetros implícitos é que argumentos para eles
podem ser omitidos em uma chamada de método. Se os argumentos estiverem
ausentes, eles serão inferidos pelo compilador de Scala.
Os argumento atuais que são elegíveis a serem passados implicitamente por
parâmetro são todos os identificadores X que puderem ser acessado no ponto em
que o método é chamado sem o uso de prefixo e que denotem uma definição
implícita ou parâmetro.
Se existem mais do que um argumento elegíveis que casam com o tipo do
parâmetro, o compilador Scala vai escolher o mais específico usando as regras
padrâo para resolução de sobrecarga. Por exemplo, dada a chamada
sum(List(1, 2, 3))
está em um contexto onde stringMonoid e intMonoid estão visíveis. Nós sabemos
que o tipo genérico A do método sum precisa ser instanciado usando int. O único
valor elegível que casa com o parâmetro implícito Monoid[Int] é o intMonoid e por
isso este objeto será passado como parâmetro implícito.
A discussão mostra também que parâmetros implícitos são inferidos depois que o
tipo dos outros parâmetros são inferidos.
Conversões Implícitas
Digamos que você tenha uma expressão E do tipo T onde é esperado um tipo
S. T não é um sub-tipo de S e nem é conversível para S por alguma conversão
pré-definida. Nesse caso, o compilador Scala irá tentar como um último recurso
uma conversão implícita I (E ). Onde, I é um identificador que denota a definição
implícita ou parâmetro que seja acessível sem prefixo no ponto da conversão e que
contenha uma função ao qual podem ser usados como argumentos valores do tipo
T e cujo resultado seja do tipo S ou sub-tipo do mesmo.
Conversões Implícitas podem também ser usadas na seleção de membros. Dada
a chamada E .x onde x não é um membro do tipo E , o compilador Scala irá tentar
inserir uma conversão implícita I (E ).x, de maneira que x seja um membro de I (E ).
Aqui está um exemplo de uma função de conversão implícita que converte inteiros
em instâncias da classe scala.Ordered:
implicit def int2ordered(x: Int): Ordered[Int] = new Ordered[Int] {
def compare(y: Int): Int =
if (x < y) -1
else if (x > y) 1
else 0
}
118
Parâmetros Implícitos e Conversões
Parâmetros de Tipos Delimitados
Parâmetros de Tipos Delimitados1 são uma sintaxe simplificada2 e conveniente
para parâmetros implícitos. Considere por exemplo, um método de ordenação
genérico:
def sort[A <% Ordered[A]](xs: List[A]): List[A] =
if (xs.isEmpty || xs.tail.isEmpty) xs
else {
val {ys, zs} = xs.splitAt(xs.length / 2)
merge(ys, zs)
}
O parâmetros de tipo delimitado [A <% Ordered[A]] expressa que sort pode
ser usado com listas do tipo A onde exista uma conversão implícita de A para
Ordered[A]. A definição é tratada como um atalho para a seguinte assinatura de
método com parâmetro implícito:
def sort[A](xs: List[A])(implicit c : A => Ordered[A]): List[A] = ...
(Aqui o nome do parâmetro c foi escolhido arbitrariamente, garantindo-se que não
era um nome já usado no programa.)
Como um exemplo mais detalhado, considere o método merge que vêm com o
método sort citado anteriormente:
def merge[A <% Ordered[A]](xs: List[A], ys: List[A]): List[A] =
if (xs.isEmpty) ys
else if (ys.isEmpty) xs
else if (xs.head < ys.head) xs.head :: merge(xs.tail, ys)
else if ys.head :: merge(xs, ys.tail)
Depois de expandir os parâmetros de tipo delimitado e inserir as conversões
implícitas a implementação deste método ficaria assim:
def merge[A](xs: List[A], ys: List[A])
(implicit c : A => Ordered[A]): List[A] =
if (xs.isEmpty) ys
else if (ys.isEmpty) xs
else if (c(xs.head) < ys.head) xs.head :: merge(xs.tail, ys)
else if ys.head :: merge(xs, ys.tail)(c)
As duas últimas linhas da definição do método ilustram dois diferentes usos do
parâmetro implícito c. Ele é usado na conversão da condição na penúltima linha e
passado como parãmetro implícito na chamada recursiva de merge na última linha.
1
2
View bounds
Syntactic sugar
Capítulo 16
Inferência
de
Hindley/Milner
Tipos
de
Este capítulo demonstra os tipos de dados Scala e o casamento de padrôes
através do desenvolvimento de um sistema de inferência de tipos no estilo de
Hindley/Milner [Mil78]. A linguagem fonte para a inferência de tipos é o cálculo
lambda com uma construção chamada Mini-ML. As árvoes de sintaxe abstrata para
o Mini-ML são representadas através do tipo de dados Terms.
abstract class Term {}
case class Var(x: String) extends Term {
override def toString = x
}
case class Lam(x: String, e: Term) extends Term {
override def toString = "(\\" + x + "." + e + ")"
}
case class App(f: Term, e: Term) extends Term {
override def toString = "(" + f + " " + e + ")"
}
case class Let(x: String, e: Term, f: Term) extends Term {
override def toString = "let " + x + " = " + e + " in " + f
}
Há quatro construtores de termos: Var para variáveis, Lam para abstrações lambda,
App para aplicação e Let para expressões de atribuição. Cada uma destas classes
sobrescreve o método toString da classe Any, de forma que os termos podem ser
impressos de forma legível.
A seguir, definimos os tipos que serão computados pelo sistema de inferência.
sealed abstract class Type {}
case class Tyvar(a: String) extends Type {
120
Inferência de Tipos de Hindley/Milner
override def toString = a
}
case class Arrow(t1: Type, t2: Type) extends Type {
override def toString = "(" + t1 + "->" + t2 + ")"
}
case class Tycon(k: String, ts: List[Type]) extends Type {
override def toString =
k + (if (ts.isEmpty) "" else ts.mkString("[", ",", "]"))
}
Há três construtores de tipos: Tyvar para o tipo variável, Arrow para o tipo função e
Tycon para o tipo construtor como, por exemplo, Boolean ou List. O tipo construtor
tem como componente uma lista de tipos que contem seus parâmetros. Esta lista é
vaiz para tipos constantes como Boolean. Assim como nos construtores de termos,
implementamos o método toString para mostrar os tipos de forma legível.
Note que Type foi declarada com o modificador sealed. Isto significa que nenhuma
sub-classe ou construtores de dados que extendam Type podem ser declarados
fora da sequência de definições em que Type foi definida. Isto torna Type um tipo
algébrico fechado com exatas três alternativas. Em contraste, o tipo Term is um tipo
algébrico aberto onde mais alternativas poderâo ser definidas.
As principais partes da inferência de tipos estão contidas no objeto typeInfer.
Começamos com uma função utilitária que cria novos tipos variáveis:
object typeInfer {
private var n: Int = 0
def newTyvar(): Type = { n += 1; Tyvar("a" + n) }
Em seguinda, definimos uma classe para substituições. A substituição é uma
função idempotente de tipos variáveis para tipos. Ela mapeia um número finito
de tipos variáveis para alguns tipos e não modifica todos os outros tipos. O
significado de uma substituição é extendido a partir de um mapeamento de tipos
para tipos. Também extendemos o significado da substituição para ambientes que
serão definidos posteriormente.
abstract class Subst extends Function1[Type,Type] {
def lookup(x: Tyvar): Type
def apply(t: Type): Type = t match {
case tv @ Tyvar(a) => val u = lookup(tv); if (t == u) t else apply(u)
case Arrow(t1, t2) => Arrow(apply(t1), apply(t2))
case Tycon(k, ts) => Tycon(k, ts map apply)
}
def apply(env: Env): Env = env.map({ case (x, TypeScheme(tyvars, tpe)) =>
121
// assume que tyvars nao ocorre nesta substituicao
(x, TypeScheme(tyvars, apply(tpe)))
})
def extend(x: Tyvar, t: Type) = new Subst {
def lookup(y: Tyvar): Type = if (x == y) t else Subst.this.lookup(y)
}
}
val emptySubst = new Subst { def lookup(t: Tyvar): Type = t }
Representamos substituições como funções do tipo Type => Type. Isto pode
ser obtido fazendo com que a classe Subst herde da tipo função unária
Function1[Type, Type]1 . Para ser uma instância de Subst, uma substituição s
tem que implementar o método apply que recebe como argumento um Type e
retorna um outro Type como resultado. A função aplicação s(t) é interpretada
como s.apply(t).
O método lookup é abstrato na classe Subst. Existem duas formas concretas de
substituição que diferem em como elas implementam este método. Uma forma é
definida pelo valor emptySubst e a outra é definida pelo método extend na classe
Subst.
O próximo tipo de dado descreve esquemas de tipos, que consistem de um tipo e
uma lista de nomes de tipos variáveis que aparecem universalmente quantificados
no esquema de tipos. Por exemplo o esquema de tipos ∀a∀b.a → b seria
representado no checador de tipos como:
TypeScheme(List(Tyvar("a"), Tyvar("b")), Arrow(Tyvar("a"), Tyvar("b"))) .
A definição da classe esquema de tipos não contém uma cláusula extends; isso quer
dizer que um esquema de tipos herda diretamente da classe AnyRef. Embora exista
apenas uma única maneira de construir um esquema de tipos, uma representação
usando classe case foi escolhida, pois oferece formas convenientes de acessar as
partes de uma instância deste tipo.
case class TypeScheme(tyvars: List[Tyvar], tpe: Type) {
def newInstance: Type = {
(emptySubst /: tyvars) ((s, tv) => s.extend(tv, newTyvar())) (tpe)
}
}
Os objetos de esquemas de tipos vem com o método newInstance, que retorna
o tipo contido no esquema depois de todos os tipos variáveis tiverem sido
renomeados para novas variáveis. A implementação deste método reduz (com /:)
1
A classe herda do tipo função como um mixin, ao invés de uma super-classe direta. Isto ocorre
porque na implementação atual de Scala, o tipo Function1 é uma interface Java que não pode ser
uma super-classe de uma outra classe.
122
Inferência de Tipos de Hindley/Milner
os tipos variáveis do esquema de tipos com uma função que extende uma dada
substituição s renomeando um dado tipo variável tv em um novo tipo variável. A
substituição resultante renomeia todos os tipos variáveis do esquema em novos.
Esta substituição é então aplicada o tipo do esquema de tipos.
O último tipo que necessitamos no sistema de inferência de tipos é Env, um tipo
para os ambientes, que associa nomes de variáveis à esquema de tipos. Eles são
representados pelo tipo Env no módulo typeInfer:
type Env = List[(String, TypeScheme)]
Existem duas operações nos ambientes. A função lookup retorna o esquema de
tipos associado com um dado nome ou null se o nome não foi registrado no
ambiente.
def lookup(env: Env, x: String): TypeScheme = env match {
case List() => null
case (y, t) :: env1 => if (x == y) t else lookup(env1, x)
}
A função gen retorna um esquema de tipos dado um tipo, quantificando todos os
tipos variáveis que estão livres no tipo, mas não no ambiente.
def gen(env: Env, t: Type): TypeScheme =
TypeScheme(tyvars(t) diff tyvars(env), t)
o conjunto de tipos variáveis livres é simplesmente o conjunto de todos os tipos
variáveis que ocorrem no tipo. É representado por uma lista de tipos variáveis
construído da seguinte maneira.
def tyvars(t: Type): List[Tyvar] = t match {
case tv @ Tyvar(a) =>
List(tv)
case Arrow(t1, t2) =>
tyvars(t1) union tyvars(t2)
case Tycon(k, ts) =>
(List[Tyvar]() /: ts) ((tvs, t) => tvs union tyvars(t))
}
Note que a sintaxe tv @ ... no primeiro padrão introduz a variável que está ligada
ao padrão seguinte. Note também que o tipo parâmetro [Tyvar] explícito na
expressão da terceita cláusula é necessário para que a inferência de tipos locais
funcione.
O conjunto de tipos variáveis livres de um esquema de tipos é o conjunto de
tipos variáveis livre do seu tipo componente, excluíndo-se quaisquer tipos variáveis
quantificáveis.
123
def tyvars(ts: TypeScheme): List[Tyvar] =
tyvars(ts.tpe) diff ts.tyvars
Finalmente, o conjunto tipos variáveis livres de um ambiente é a união de todos os
tipos variáveis livres de todos os esquemas de tipos registrados neste ambiente.
def tyvars(env: Env): List[Tyvar] =
(List[Tyvar]() /: env) ((tvs, nt) => tvs union tyvars(nt._2))
A principal operação da checagem de tipos de Hindley/Milner é a unificação, que
computa a substituição para fazer que dois tipos dados se tornem iguais (esta
subsituição é chamada um unificador2 ). A função mgu computa o unificador mais
geral de dois tipos dados t e u sob um substituição pre-existente s. Isto é, ele retorna
a substituição mais geral s 0 que herda de s, e que faz com que s 0 (t ) e s 0 (u) retornem
tipos iguais.
def mgu(t: Type, u: Type, s: Subst): Subst = (s(t), s(u)) match {
case (Tyvar(a), Tyvar(b)) if (a == b) =>
s
case (st @ Tyvar(a), su) if !(tyvars(su) contains st) =>
s.extend(st, su)
case (_, Tyvar(a)) =>
mgu(u, t, s)
case (Arrow(t1, t2), Arrow(u1, u2)) =>
mgu(t1, u1, mgu(t2, u2, s))
case (Tycon(k1, ts), Tycon(k2, us)) if (k1 == k2) =>
(s /: (ts zip us)) ((s, tu) => mgu(tu._1, tu._2, s))
case _ =>
throw new TypeError("cannot unify " + s(t) + " with " + s(u))
}
A função mgu lança uma exceção do tipo TypeError se não existir uma substituição
unificadora.
Isto pode ocorrer quando os dois tipos tem diferentes tipos
construtores em seus lugares correspondentes ou quando um tipo variável é
unificado com um tipo que contém um tipo variável dele mesmo. Estas exceções
foram modeladas como instâncias de classe case que herdam um classe Exception
pré-definida.
case class TypeError(s: String) extends Exception(s) {}
A principal tarefa do checador de tipos é implementada pela função tp. Esta
função recebe como parâmetro um ambiente env, um termo e, um tipo t , e uma
substituição pre-existente s. A função retorna uma substituição s 0 que herda de s e
que torna s 0 (env) ` e : s 0 (t ) num julgamento de tipos derivável de acordo com as
regras de derivação do sistema de tipos de Hindley/Milner[Mil78]. Uma exceção do
2
unifier
124
Inferência de Tipos de Hindley/Milner
tipo TypeError é lançada se não existe uma substituição com estas características.
def tp(env: Env, e: Term, t: Type, s: Subst): Subst = {
current = e
e match {
case Var(x) =>
val u = lookup(env, x)
if (u == null) throw new TypeError("undefined: " + x)
else mgu(u.newInstance, t, s)
case Lam(x, e1) =>
val a, b = newTyvar()
val s1 = mgu(t, Arrow(a, b), s)
val env1 = {x, TypeScheme(List(), a)} :: env
tp(env1, e1, b, s1)
case App(e1, e2) =>
val a = newTyvar()
val s1 = tp(env, e1, Arrow(a, t), s)
tp(env, e2, a, s1)
case Let(x, e1, e2) =>
val a = newTyvar()
val s1 = tp(env, e1, a, s)
tp({x, gen(s1(env), s1(a))} :: env, e2, t, s1)
}
}
var current: Term = null
Para auxiliar no diagnóstico de erros, a função tp guarda o sub-termo que está
sendo analisado na variável current. Com isso, se a checagem de tipos for
iterrompido por uma exceção do tipo TypeError, esta variável conterá o sub-termo
que causou o problema.
A última função do módulo de inferência de tipos , typeOf, é uma façade
simplificada para tp. Ela computa o tipo de um dado termo e em um dado ambiente
env. Ela o faz através da criação de um novo tipo variável a, e da computação da
substituição de tipos que faz env ` e : a se tornar um tipo derivado e retorna o
resultado da aplicação da subsituição em a.
def typeOf(env: Env, e: Term): Type = {
val a = newTyvar()
tp(env, e, a, emptySubst)(a)
}
}// fim typeInfer
125
Para usar o sistema de inferência de tipos, é conveniente ter um ambiente
pré-definido que contém as definições das constantes mais comumente usadas.
O módulo predefined define um ambiente env que contém as definições dos
tipos booleanos, números e listas assim como algumas operações primitivas sobre
eles. Também define um operador de ponto fixo fix, que pode ser usado para
representar uma recursão.
object predefined {
val booleanType = Tycon("Boolean", List())
val intType = Tycon("Int", List())
def listType(t: Type) = Tycon("List", List(t))
private def gen(t: Type): typeInfer.TypeScheme = typeInfer.gen(List(), t)
private val a = typeInfer.newTyvar()
val env = List(
{"true", gen(booleanType)},
{"false", gen(booleanType)},
{"if", gen(Arrow(booleanType, Arrow(a, Arrow(a, a))))},
{"zero", gen(intType)},
{"succ", gen(Arrow(intType, intType))},
{"nil", gen(listType(a))},
{"cons", gen(Arrow(a, Arrow(listType(a), listType(a))))},
{"isEmpty", gen(Arrow(listType(a), booleanType))},
{"head", gen(Arrow(listType(a), a))},
{"tail", gen(Arrow(listType(a), listType(a)))},
{"fix", gen(Arrow(Arrow(a, a), a))}
)
}
Aqui está um exemplo de como o sistema de inferência de tipos pode ser
usado. Vamos definir a função showType que retorna os tipos de um dado termo
computado em um dado ambiente Predefined.env:
object testInfer {
def showType(e: Term): String =
try {
typeInfer.typeOf(predefined.env, e).toString
} catch {
case typeInfer.TypeError(msg) =>
"\n cannot type: " + typeInfer.current +
"\n reason: " + msg
}
Então a aplicação
> testInfer.showType(Lam("x", App(App(Var("cons"), Var("x")), Var("nil"))))
126
Inferência de Tipos de Hindley/Milner
retornará a resposta
> (a6->List[a6])
Exercício 16.0.1 Extenda o Mini-ML e o sistema de inferência de tipos com uma
construção letrec que permita a definição recursiva de funções. Sintaxe:
letrec ident "=" term in term .
Os tipos de letrec devem ser como os de let, exceto que os identificadores
definidos são visíveis na expressão que está sendo definida. Usando letrec, a
função length para listas seria definida da seguinte maneira.
letrec length = \xs.
if (isEmpty xs)
zero
(succ (length (tail xs)))
in ...
Capítulo 17
Abstracões para Concorrência
Esta seção revisa padrôes comuns de concorrência e mostra como eles podem ser
implementados em Scala.
17.1
Sinais e Monitores
Exemplo 17.1.1 Um monitor provê mecanismos básicos para processos
mutuamente exclusivos em Scala. Toda instância de AnyRef pode ser usada
como um monitor através da chamada de um ou mais dos métodos apresentados
a seguir.
def
def
def
def
def
synchronized[A] (e: => A): A
wait()
wait(msec: Long)
notify()
notifyAll()
O método synchronized computa e em modo mutuamente exclusivo – em um
dado momento qualquer, somente uma thread pode executar um argumento
synchronized em um dado monitor.
Threads podem ser paradas dentro de um monitor e esperar por um sinal. Threads
podem chamar o método wait e esperar até que o método notify do mesmo objeto
seja chamado por alguma outra thread. Chamadas ao método notify quando não
existam threads esperando por um sinal são ignoradas.
Existe também uma forma do método wait baseada em tempo em que a execução
é bloqueada enquanto nenhum sinal seja recebido ou um dado espaço de tempo
(dado em milisegundos) tenha passado. Além disso, há o método notifyAll
que desbloqueia todas as threads que estejam esperando por um sinal. Estes
métodos, assim como a classe Monitor são primitivos em Scala, ou seja, eles
128
Abstracões para Concorrência
são implementados usando os mecanismos internos do sistema de execução dos
programas.
Tipicamente, uma thread espera até que um certa condição ocorra. Se esta
condição não ocorrer até o tempo definido na chamada do método wait, a thread
fica com execução suspensa até que alguma outra thread estabeleça tal condição
ou que o tempo definido tenha passado. É responsabilidade desta outra thread
reiniciar os processos que estavam esperando através da chamada dos métodos
notify ou notifyAll. Note que não existe garantia de que um processo em espera
execute imediatamente após a chamada do método notify. Pode ocorrer de outros
processos que executem antes invalidem novamente esta condição, deixando as
threads suspensas. Portanto, a forma correta de esperar uma condição C usa um
laço do tipo while:
while (!C ) wait()
Como um exemplo de como os monitores são usados, aqui está uma
implementação de uma classe de buffer com limites.
class BoundedBuffer[A](N: Int) {
var in = 0, out = 0, n = 0
val elems = new Array[A](N)
def put(x: A)
while (n >=
elems(in) =
if (n == 1)
}
= synchronized {
N) wait()
x ; in = (in + 1) % N ; n = n + 1
notifyAll()
def get: A = synchronized {
while (n == 0) wait()
val x = elems(out) ; out = (out + 1) % N ; n = n - 1
if (n == N - 1) notifyAll()
x
}
}
E aqui está um programa usando esta classe para comunicar entre processos
consumidores e produtores.
import scala.concurrent.ops._
...
val buf = new BoundedBuffer[String](10)
spawn { while (true) { val s = produceString ; buf.put(s) } }
spawn { while (true) { val s = buf.get ; consumeString(s) } }
}
17.2 SyncVars
129
O método spawn dispara uma nova thread que executa a expressão passada como
parâmetro. Foi definida no objeto concurrent.ops da seguinte maneira:
def spawn(p: => Unit) {
val t = new Thread() { override def run() = p }
t.start()
}
17.2
SyncVars
Uma variável sincronizada (ou syncvar) oferece as operações get e put para ler e
escrever na variável. As operações get bloqueiam a execução até que o valor da
variável tenha sido definido. Um operação unset coloca o valor da variável em um
valor indefinido.
Aqui segue uma implementação padrão de variáveis sincronizadas:
package scala.concurrent
class SyncVar[A] {
private var isDefined: Boolean = false
private var value: A = _
def get = synchronized {
while (!isDefined) wait()
value
}
def set(x: A) = synchronized {
value = x; isDefined = true; notifyAll()
}
def isSet: Boolean = synchronized {
isDefined
}
def unset = synchronized {
isDefined = false
}
}
17.3
Futuros
Um futuro (future) é um valor que será computado em paralelo com alguma outra
thread do cliente e que será usado pelo cliente em algum momento no futuro.
Futuros são usados para utilizar melhor os recursos de processamento paralelo. O
uso típico é:
import scala.concurrent.ops._
130
Abstracões para Concorrência
...
val x = future(someLengthyComputation)
anotherLengthyComputation
val y = f(x()) + g(x())
O método future é definido no objeto scala.concurrent.ops da seguinte maneira.
def future[A](p: => A): Unit => A = {
val result = new SyncVar[A]
fork { result.set(p) }
(() => result.get)
}
O método future recebe como parâmetro uma computação p que precisa ser
calculado. O tipo da computação é arbitrário e é representando pelo tipo genérico A.
O método future define um guarda result, que recebe o parâmetro que representa
o resultado da computação. Ao chegar neste ponto, ele abre uma nova thread que
computa o resultado e invoca o guarda result quanto o processo terminar. Em
paralelo à esta thread, a função retorna uma função anônima do tipo A. Quando
chamada, esta função espera que o guarda resultado tenha sido chamada, e,
quando isso ocoore, retorna o resultado. Ao mesmo tempo, a função re-invoca o
guarda result com o mesmo argumento, de forma que, futuras chamadas à função
possam retornar o resultado imediatamente.
17.4
Computação Paralela
O próximo exemplo apresenta a função par que recebe um par de computaçoes
como prarâmetros e retorna o resultado destas computações em um outro par. As
duas computações são executadas paralelamente.
A função estã definida no objeto scala.concurrent.ops da seguinte forma:
def par[A, B](xp: => A, yp: => B): (A, B) = {
val y = new SyncVar[B]
spawn { y set yp }
(xp, y.get)
}
Definida no mesmo objeto está a função replicate que executa um número de
réplicas de uma computação em paralelo. Cada instância replicada é passada como
um número inteiro que a identifica.
def replicate(start: Int, end: Int)(p: Int => Unit) {
if (start == end)
()
else if (start + 1 == end)
17.5 Semáforos
131
p(start)
else {
val mid = (start + end) / 2
spawn { replicate(start, mid)(p) }
replicate(mid, end)(p)
}
}
A função a seguir usa replicate para realizar uma computação paralela em todos
os elementos de um vetor.
def parMap[A,B](f: A => B, xs: Array[A]): Array[B] = {
val results = new Array[B](xs.length)
replicate(0, xs.length) { i => results(i) = f(xs(i)) }
results
}
17.5
Semáforos
Um mecanismo comum para sincronização de processos é o uso de travas (lock) ou
semáforo. Uma trava oferece duas operações atômicas: acquire e release. Aqui está
a implementação de uma trava en Scala:
package scala.concurrent
class Lock {
var available = true
def acquire = synchronized {
while (!available) wait()
available = false
}
def release = synchronized {
available = true
notify()
}
}
17.6
Leitores/Escritores
Uma forma mais complexa de sincronização distingue leitores (readers) que
acessam um recurso comum sem modificá-lo e escritores (writers) que podem
acessar e modificar esse recurso. Para sincronizar leitores e escritores, precisamos
132
Abstracões para Concorrência
implementar as operações startRead, startWrite, endRead, endWrite, de tal forma
que:
• podem haver múltiplos leitores concorrentemente;
• só pode haver um único escritor em um dado instante;
• solicitações de escrita pendentes tem prioridade sobre solicitações de
leitura pendentes, mas não interrompem operações de leitura que estejam
ocorrendo.
A implementação de travas para leitores/escritores a seguir é baseada no conceito
de caixa postal (mailbox) (ver Seção 17.10).
import scala.concurrent._
class ReadersWriters {
val m = new MailBox
private case class Writers(n: Int), Readers(n: Int) { m send this }
Writers(0); Readers(0)
def startRead = m receive {
case Writers(n) if n == 0 => m receive {
case Readers(n) => Writers(0); Readers(n+1)
}
}
def startWrite = m receive {
case Writers(n) =>
Writers(n+1)
m receive { case Readers(n) if n == 0 => }
}
def endRead = m receive {
case Readers(n) => Readers(n-1)
}
def endWrite = m receive {
case Writers(n) => Writers(n-1); if (n == 0) Readers(0)
}
}
17.7
Canais Assíncronos
Um modo fundamental de comunicação entre processos é o canal assíncrono. Sua
implementação faz usa da seguinte classe para listas-ligadas:
class LinkedList[A] {
var elem: A = _
var next: LinkedList[A] = null
17.8 Canais Síncronos
133
}
Para facilitar a inserção e remoção de elementos nas listas ligadas, cada referência
na lista ligada aponta para o nó que precede o nó que conceitualmente forma o
topo da lista. Listas ligadas vazias começam com um nó fantasma, cujo o sucessor
é null.
A classe canal usa a lista ligada para armazenar dados que foram enviados, mas
ainda não foram lidos. No lado oposto, threads que necessitam ler de um canal
vazio, registram sua presença incrementando o campo nreaders e esperando serem
notificadas.
package scala.concurrent
class Channel[A] {
class LinkedList[A] {
var elem: A = _
var next: LinkedList[A] = null
}
private var written = new LinkedList[A]
private var lastWritten = written
private var nreaders = 0
def write(x: A) = synchronized {
lastWritten.elem = x
lastWritten.next = new LinkedList[A]
lastWritten = lastWritten.next
if (nreaders > 0) notify()
}
def read: A = synchronized {
if (written.next == null) {
nreaders = nreaders + 1; wait(); nreaders = nreaders - 1
}
val x = written.elem
written = written.next
x
}
}
17.8
Canais Síncronos
Aqui está uma implementação de canais síncronos, onde quem envia uma
mensagem tem sua execução bloqueada até que esta mensagem seja recebida.
Canais síncronos precisam apenas de uma única variável para armazenar as
134
Abstracões para Concorrência
mensagens em trânsito, mas de três sinais para coordenar os processos de leitura
e escrita.
package scala.concurrent
class SyncChannel[A] {
private var data: A = _
private var reading = false
private var writing = false
def write(x: A) = synchronized {
while (writing) wait()
data = x
writing = true
if (reading) notifyAll()
else while (!reading) wait()
}
def read: A = synchronized {
while (reading) wait()
reading = true
while (!writing) wait()
val x = data
writing = false
reading = false
notifyAll()
x
}
}
17.9
Trabalhadores
Aqui está uma implementação de um servidor de computação em Scala. O servidor
implementa um método future que computa uma dada expressão paralelamente
com quem chamou o método. Diferenmente da implementação de futuros da
seção 17.3 o servidor computa os futuros somente com um número pré-definido de
threads. Uma possível implementação do servidor poderia executar cada thread em
um processador separado, e com isso evitar o custo inerente à mudança de contexto
entre muitas threads em um único processo.
import scala.concurrent._, scala.concurrent.ops._
class ComputeServer(n: Int) {
private abstract class Job {
17.9 Trabalhadores
135
type T
def task: T
def ret(x: T)
}
private val openJobs = new Channel[Job]()
private def processor(i: Int) {
while (true) {
val job = openJobs.read
job.ret(job.task)
}
}
def future[A](p: => A): () => A = {
val reply = new SyncVar[A]()
openJobs.write{
new Job {
type T = A
def task = p
def ret(x: A) = reply.set(x)
}
}
() => reply.get
}
spawn(replicate(0, n) { processor })
}
Expressões a serem computadas (ex.: parâmetros da chamada de um future) são
escritos no canal openJobs . Um job é um objeto em que:
• Um tipo abstrato T descreve o resultado de sua computação.
• Um método sem parâmetros (task) do tipo t representa a expressão a ser
computada.
• Um método ret consome o resultado, quando este tiver sido computado.
O servidor de computação cria n processos no processador como parte de sua
inicialização. Cada um destes processos repetidamente consome um trabalho
em aberto no canal openJobs, computa o métodotask e passa o resultado para o
método ret. O método polimórfico future cria um novo job quando o método ret
é implementado por um guarda chamado reply e insere este job no conjunto de
trabalhos em aberto. Este espera até que o método guarda reply correspondente
for chamado.
136
Abstracões para Concorrência
O exemplo mostra o uso de tipos abstratos. Um tipo abstrato t mantém controle
do tipo do resultado de um job que pode variar entre diferentes jobs. Sem os
tipos abstratos seria impossível implementar a mesma classe para o usuário de
uma forma que garantisse a segurança do sistemas de tipos estaticamente. Seriam
necessários testes de tipos dinâmicos e o uso de casts.
Aqui um trecho de código que usa o servidor de computação para calcular a
expressão 41 + 1.
object Test with Executable {
val server = new ComputeServer(1)
val f = server.future(41 + 1)
println(f())
}
17.10
Caixas Postais
Caixas postais são construções flexíveis de alto nível para comunicação e
sincronização de processos. Elas permitem enviar e receber mensagens. Um
mensagem neste contexto é um objeto arbitrário. Há uma mensagem especial,
chamada TIMEOUT que é usada para sinalizar um time-out.
case object TIMEOUT
Caixas postais implentam os seguintes métodos
class
def
def
def
}
MailBox {
send(msg: Any)
receive[A](f: PartialFunction[Any, A]): A
receiveWithin[A](msec: Long)(f: PartialFunction[Any, A]): A
O estado de uma caixa postal consiste de vários conjuntos de mensagens. As
mensagens são adicionadas à caix postal através do método send. As mensagens
são removidas usando o método receive, que passa um processador de mensagens
f como parâmetro. O processador de mensagens é uma função parcial que tenha
como resultado um tipo arbitrário. Normalmente, esta função é implementada
usando uma expressão de casamento de padrôes. O método receive suspende
sua execução até que exista uma mensagem na caixa postal para o qual o seu
processador de mensagens foi definido. A mensagem que casa com um processador
é então removida da caixa postal e a thread suspensa é reiniciada aplicando o
processador de mensagens à mensagem. Tanto mensagens enviadas e receptores
são ordenados cronologicamente. Um receptor r é aplicado à uma mensagem m
se for capaz de recebê-la (tipo) e somente se não existe um outro par {message,
receiver} que preceda m, r no ordenamento cronológico parcial destes pares.
17.10 Caixas Postais
137
Como um simples exemplo de como caixas postais são usadas, considere o buffer
de uma posição:
class OnePlaceBuffer {
private val m = new MailBox
// Caixa postal interna
private case class Empty, Full(x: Int) // Tipo das mensagens que pode tratar
m send Empty
// Inicializa\c{c}\~{a}o
def write(x: Int)
{ m receive { case Empty => m send Full(x) } }
def read: Int =
m receive { case Full(x) => m send Empty; x }
}
Aqui como uma classe caixa postal pode ser implementada:
class MailBox {
private abstract class Receiver extends Signal {
def isDefined(msg: Any): Boolean
var msg = null
}
Definimos um classe interna para receptores com um método de teste isDefined,
que indica se o receptor pode tratar uma dada mensagem. O receptor herda da
classe Signal o método notify que serve para "acordar" a thread para receptora.
Quanto a thread receptora é reiniciada, a mensagem que precisa ser aplicada é
armazenada na variável msg do Receiver.
private
private
private
private
val
var
val
var
sent = new LinkedList[Any]
lastSent = sent
receivers = new LinkedList[Receiver]
lastReceiver = receivers
Um classe caixa postal mantém duas lista ligadas, uma para mensagens enviadas e
não consumidas e outra para mensagens esperando receptores.
def send(msg: Any) = synchronized {
var r = receivers, r1 = r.next
while (r1 != null && !r1.elem.isDefined(msg)) {
r = r1; r1 = r1.next
}
if (r1 != null) {
r.next = r1.next; r1.elem.msg = msg; r1.elem.notify
} else {
lastSent = insert(lastSent, msg)
}
}
138
Abstracões para Concorrência
Inicialmente, o método send verifica se há um receptor que pode ser aplicado à
mensagem enviada. Se sim, o receptor é notificado. Se não, a mensagem é anexada
à lista ligada de mensagens enviadas.
def receive[A](f: PartialFunction[Any, A]): A = {
val msg: Any = synchronized {
var s = sent, s1 = s.next
while (s1 != null && !f.isDefinedAt(s1.elem)) {
s = s1; s1 = s1.next
}
if (s1 != null) {
s.next = s1.next; s1.elem
} else {
val r = insert(lastReceiver, new Receiver {
def isDefined(msg: Any) = f.isDefinedAt(msg)
})
lastReceiver = r
r.elem.wait()
r.elem.msg
}
}
f(msg)
}
Inicialmente, o método receive verifica se existe uma função processadora de
mensagens f que pode ser aplicada à mensagem que já foi enviada, mas ainda
não foi consumida. Se sim, a thread continua imediatamente aplicando a função
f à mensagem. Se não, um novo receptor é criado adicionado à lista receivers e
a thread esperará por uma notificação neste receptor. Uma vez que a thread seja
reiniciada, ela continua aplicando a função f que foi armazenado no receptor à
mensagem. O método insert na lista ligada é definido da seguinte maneira:
def insert(l: LinkedList[A], x: A): LinkedList[A] = {
l.next = new LinkedList[A]
l.next.elem = x
l.next.next = l.next
l
}
A classe caixa postal também oferece o método receiveWithin que suspende
a execução por um tempo máximo especificado. Se nenhuma mensagem for
recebida no intervalo de tempo especificado (dado em milissegundos), o parâmetro
do processador de mensagens f será desbloqueado com a mensagem especial
TIMEOUT. A implementação de receiveWithin é bastante parecida com a de
receive:
17.11 Actors
139
def receiveWithin[A](msec: Long)(f: PartialFunction[Any, A]): A = {
val msg: Any = synchronized {
var s = sent, s1 = s.next
while (s1 != null && !f.isDefinedAt(s1.elem)) {
s = s1; s1 = s1.next
}
if (s1 != null) {
s.next = s1.next; s1.elem
} else {
val r = insert(lastReceiver, new Receiver {
def isDefined(msg: Any) = f.isDefinedAt(msg)
})
lastReceiver = r
r.elem.wait(msec)
if (r.elem.msg == null) r.elem.msg = TIMEOUT
r.elem.msg
}
}
f(msg)
}
} // fim MailBox
A única diferença é a chamada ao método wait que recebe o tempo de espera e a
linha de código que vem em seguida, onde a mensagem TIMEOUT é aplicada.
17.11
Actors
O capítulo 3 apresentou um programa como exemplo de implementação de
um serviço de leilão eletrônico. Este serviço foi baseado em atores quue
representam processos de alto nível e trabalham inspecionando as mensagens
em sua caixa-postal usando casamento de padrões. Uma implementação mais
refinada e otimizada de atores pode ser encontrada no pacote scala.actors. Agora
mostraremos um rascunho de uma versão simplificada da biblioteca de atores.
O código apresentado a seguir é diferente da implementação presente no pacote
scala.actors e, portanto, deve ser vista como um exemplo de como uma versão
simplificada dos atores poderia ser implementada. Ela não descreve como os atores
foram definidos e implementados na biblioteca padrão de Scala. Caso deseje essa
informação, por favor consulte a documentação da API de Scala.
Um ator simplificado é apenas uma thread cujas primitivas de comunicação são
aquelas de uma caixa postal. Tal ator pode ser definido como uma composição
mixin da extensão da classe Java padrão Thread com a classe MailBox. Nós também
sobre-escrevemos o método run da classe Thread, de tal forma que ele execute
o comportamento de um ator que é definido pelo método act. O método !
140
Abstracões para Concorrência
simplesmente chama o método send da classe MailBox:
abstract class Actor extends Thread with MailBox {
def act(): Unit
override def run(): Unit = act()
def !(msg: Any) = send(msg)
}
Bibliografia
[ASS96] Harold Abelson, Gerald Jay Sussman, and Julie Sussman. The Structure and
Interpretation of Computer Programs, 2nd edition. MIT Press, Cambridge,
Massachusetts, 1996.
[Mil78] Robin Milner. A Theory of Type Polymorphism in Programming. Journal
of Computer and System Sciences, 17:348–375, Dec 1978.