Fundamentosde Programação
Soluçãodo Primeiroteste
19 de Novembrode 2005
1. (1.0) Utilizando a notação BNF, apresente a definição completa da forma
define. Explique cada um dos constituintes da sua definição.
Resposta:
<operação de nomeação> ::= (define <nome> <expressão>) |
(define (<nome> <parâmetros formais>) <corpo>)
A primeira forma associa o valor de <expressão> a <nome>.
A segunda forma só é usada para a definição e nomeação de procedimentos:
<nome> é o nome do procedimento, <parâmetros formais> (zero ou mais
<nomes>) são os parâmteros formais do procedimento, e <corpo> é o corpo do
procedimento.
2. (1.0) Diga o que entende por ambiente, ambiente global e ambiente local.
Resposta:
Ambiente- conjunto de associações entre nomes e objectos computacionais.
Ambiente global – contém todos os nomes conhecidos à partida pelo interpretador
de Scheme, bem como todos os nomes dados directamente ao interpretador do
Scheme.
Ambiente local – ambiente que existe apenas durante a avaliação de uma
combinação. Contém as associações entre parâmetros formais e parâmetros
concretos.
3. (1.0) Descreva sucintamente os passos a seguir na definição de um tipo abstracto de
informação.
Resposta:
Definição das operações básicas – definição abstracta das operações que vão
permitir manipular os elementos do tipo. Estas operações dividem-se em
Construtores (permitem construir elementos do tipo), Selectores (permitem
seleccionar componentes dos elementos do tipo), Reconhecedores (permitem
reconhecer elementos do tipo) e Testes (permitem comparar elementos do tipo).
Definição de uma representação externa para os elementos do tipo.
Axiomatização – definição das relações a verificar entre as operações básicas.
Escolha de uma representação interna – definição de como os elementos do tipo
vão ser representados a partir de tipos primitivos da LP usada, ou a partir de outros
tipos já definidos.
Implementação das operações básicas – concretização das operações básicas na
LP usada, tendo em atenção a representação escolhida.
4. (1.0) Explique o que é a barreira de abstracção criada pela definição de um tipo
abstracto de informação e quais os inconvenientes de não respeitar essa barreira.
Resposta: Quando definimos um TAI, ao especificarmos as suas operações básicas
estamos a criar uma barreira conceptual, que nos impede de manipular os elementos
do tipo, a não ser através destas operações básicas. É a esta barreira conceptual que
se chama barreira de abstracção. Os inconvenientes de não respeitar esta barreira,
ou seja, de manipular directamente a representação interna do tipo são: 1) Maior
dificuldade em escrever e compreender os programas que utilizam o tipo; 2) Os
programas ficam dependentes da representação usada.
5. Complete as frases:
1. (0.5) O domínio de uma variável significa a gama de formas onde a variável
pode ser utilizada.
2. (0.5) Em Scheme, o domínio de uma variável é o bloco onde a variável é
introduzida, e todos os blocos interiores a este, onde não seja introduzida uma
variável com o mesmo nome.
3. (0.5) Os nomes utilizáveis num bloco dividem-se em: locais (intoduzidos no
bloco), globais (introduzidos no ambiente global) e livres (todos os outros).
6. (1.0) Suponha que as seguintes formas são avaliadas pelo Scheme. Na linha
imediatamente a seguir a cada uma delas diga o que é escrito pelo interpretador do
Scheme (se a forma der origem a um erro, explique a razão do erro).
> (define a (+ 3 (- 10 5)))
nada
> (define b (/ a 2))
nada
> (define a 3)
nada
> b
4
> (and (zero? (- b 4)) (> a b))
#f
7. a) (1.0) Diga o que é devolvido pelo interpretador do Scheme, após a seguinte
interacção:
> (define x 4)
> (let* ((x (+ x 2))
(y (+ x 2)))
(let ((y (+ x y)))
(* 2 x y)))
Resposta: 168
b) (1.0) Escreva a expressão let* anterior usando expressões lambda.
Resposta:
((lambda (x)
((lambda (y)
((lambda (y)
(* 2 x y))
(+ x y)))
(+ x 2)))
(+ x 2))
8. Considere o seguinte procedimento:
(define (misterio
(cond ((= n 0)
((< n 0)
(else (+
n)
0)
(+ (misterio (- (+ n 1))) 1))
(misterio (- n)) 1))))
a) (1.0) O procedimento gera um processo iterativo ou recursivo? Justifique a
resposta.
Resposta:
(misterio 4)
(+ (misterio -4) 1)
(+ (+ (misterio 3) 1) 1)
(+ (+ (+ (misterio -3) 1) 1) 1)
(+ (+ (+ (+ (misterio 2) 1) 1) 1) 1)
(+ (+ (+ (+ (+ (misterio -2) 1) 1) 1) 1) 1)
(+ (+ (+ (+ (+ (+ (misterio 1) 1) 1) 1) 1) 1) 1)
(+ (+ (+ (+ (+ (+ (+ (misterio -1) 1) 1) 1) 1) 1) 1) 1)
(+ (+ (+ (+ (+ (+ (+ (+ (misterio 0) 1) 1) 1) 1) 1) 1) 1) 1)
(+ (+ (+ (+ (+ (+ (+ (+ 0 1) 1) 1) 1) 1) 1) 1) 1)
(+ (+ (+ (+ (+ (+ (+ 1 1) 1) 1) 1) 1) 1) 1)
(+ (+ (+ (+ (+ (+ 2 1) 1) 1) 1) 1) 1)
(+ (+ (+ (+ (+ 3 1) 1) 1) 1) 1) 1)
(+ (+ (+ (+ 4 1) 1) 1) 1)
(+ (+ (+ 5 1) 1) 1)
(+ (+ 6 1) 1)
(+ 7 1)
8
O processo é recursivo porque tem uma fase de expansão seguida de uma fase de
contracção.
b) (1.0) Se o procedimento gerar um processo recursivo, escreva um procedimento
que faz o mesmo e que gere um processo iterativo; se o procedimento gerar um
processo iterativo, escreva um procedimento que faz o mesmo e que gere um
processo recursivo.
Resposta:
(define (misterio-iter n)
(define (misterio-aux n acum)
(cond ((= n 0) acum)
((< n 0) (misterio-aux (- (+ n 1)) (+ 1 acum)))
(else (misterio-aux (- n) (+ 1 acum)))))
(misterio-aux n 0))
9. (2.0) Defina um procedimento chamado muda-digitos que, dado um inteiro
não negativo, devolve outro inteiro não negativo. Cada dígito do número
devolvido é obtido transformando o dígito correspondente do número original da
seguinte forma: se o dígito original for par, então o dígito transformado é obtido
somando 1 ao dígito original; se o dígito original for ímpar, então o dígito
transformado é obtido subtraindo 1 ao dígito original. Por exemplo, (mudadigitos 123456) --> 32547.
Resposta:
(define (muda-digito n)
(define (transforma-digito n)
(if (even? n)
(+ n 1)
(- n 1)))
(if (< n 10)
(transforma-digito n)
(+ (transforma-digito (remainder n 10))
(* (muda-digito (quotient n 10)) 10))))
10. (1.0) Considere as definições:
(define (g)
(lambda (x) (+ x 1)))
(define f
(lambda (x) (+ x 1)))
Diga o que é escrito pelo interpretador do Scheme a seguir a cada uma das
expressões. Se alguma der um erro, explique a razão.
> g
#<procedure:g>
> (g)
#<procedure:...>
argumento
> (g 1)
erro: g não tem argumentos
> ((g) 1)
2
> f
#<procedure:f>
> (f)
erro: f tem 1
> (f 1)
2
> ((f) 1)
erro: f tem 1 argumento
11. (1.0) Escreva um procedimento chamado duplica, que recebe um
procedimento de um argumento e devolve um procedimento que aplica o
procedimento original duas vezes.
Por exemplo, ((duplica quadrado) 2) devolve 16.
Resposta:
(define (duplica f)
(lambda (x) (f (f x))))
12. Um monómio numa variável x é caracterizado por um coeficiente (um real) e
uma ordem (um natural). Por exemplo, 3x2, é um monómio de coeficiente 3 e ordem 2.
a) (3.0) Defina o tipo abstracto de informação monómio, usando a metodologia
dos tipos abstractos de informação. Pode omitir a axiomatização.
Resposta:
1. Definição das operações básicas
Construtor:
cria-monomio: |R x |N -> monomio
cria-monomio(c,o) devolve o monómio cujo coeficiente é c e cuja ordem é o.
Selectores:
coeficiente: monomio -> |R
coeficiente(m) devolve o coeficiente de m.
ordem: monomio -> |N
ordem(m) devolve a ordem de m.
Reconhecedores:
monomio?: universal -> lógico
monomio?(x) devolve verdadeiro se e só se x for um monómio.
monomio-zero?: monomio -> lógico
monomio-zero?(m) devolve verdadeiro se e só se o coeficiente de m for zero.
Teste:
monomios=?: monomio x monomio -> lógico
monomios=?(m1, m2) devolve verdadeiro se e só se m1 e m2 forem iguais.
Representação externa: o monómio de coeficiente c e ordem o é representado por
cx^o.
Transformador de saída: escreve-monomio.
2. Representação interna: um monómio é representado por um par cujo primeiro
elemento é o coeficiente do monómio, e cujo segundo elemento é a ordem do
monómio.
3. Implementação das operações básicas
;;Construtor
(define (cria-monomio c o)
(cons c o))
;;Selector
(define (coeficiente m)
(car m))
(define (ordem m)
(cdr m))
;; Reconhecedores
(define (monomio? m)
(and (pair? m)
(integer? (ordem m))
(> (ordem m) 0)
(real? (coeficiente m))))
(define (monomio-zero? m)
(= (coeficiente m) 0))
;; Teste
(define (monomios=? m1 m2)
(and (= (ordem m1) (ordem m2))
(= (coeficiente m1) (coeficiente m2))))
;;Transformador de saída
(define (escreve-monomio m)
(let ((coef (coeficiente m)))
(display coef)
(if (not (= coef 0))
(begin
(display "x^")
(display (ordem m))))))
b) (2.5) Usando o tipo monómio, e respeitando a barreira de abstracção que criou,
escreva os procedimentos
● produto-monómios – recebe dois monómios e devolve o seu
produto.
● quociente-monómios– recebe dois monómios e devolve o seu
quociente.
● potência-monómios – recebe um monómio e um expoente
natural e devolve o monómio levantado ao expoente. Por exemplo,
potência-monómios( 3x2 , 3) = 27x6.
Resposta:
(define (produto-monomios m1 m2)
(cria-monomio (* (coeficiente m1) (coeficiente m2))
(+ (ordem m1) (ordem m2))))
(define (quociente-monomios m1 m2)
(if (monomio-zero? m2)
(error "Divisão por zero")
(cria-monomio (/ (coeficiente m1) (coeficiente m2))
(- (ordem m1) (ordem m2)))))
(define (potencia-monomios m e)
(cria-monomio (expt (ordem m) e)
(* (coef m) e)))