P2 - Linguagens de Programação 2021-2

DCC024 Linguagens de Programa¸c˜ao Prova 2 21 de fevereiro, 2022 Nome: Matr´ıcula: 1. Na primeira p´agina das suas respostas deve constar seu nome. Todas as respos- tas dever˜ao ser manuscritas com suas pr´oprias palavras. N˜ao ser˜ao aceitas respostas digitadas. 2. O exame dever´a ser conclu´ıdo e entregue em at´e 24h. As respostas devem ser enviadas via Moodle em ´unico arquivo PDF digitalizado. Vocˆe deve se certificar de que o arquivo enviado esteja completamente leg´ıvel. Para isto as respostas devem ser feitas de caneta. 3. A prova ´e individual, feita apenas por vocˆe, sem consultas a outras pessoas pre- sencial ou virtualmente. Qualquer ind´ıcio de fraude ser´a comunicado `as instˆancias competentes da UFMG. 4. Se vocˆe acredita que alguma pergunta esteja subespecificada, anote as suposi¸c˜oes que vocˆe teve que fazer para chegar `a sua resposta e justifique-as como parte de sua resposta `a pergunta. 5. Suas respostas ser˜ao avaliadas em sua clareza e concis˜ao. Cada resposta deve ser completa e devidamente justificada, e todas as etapas intermedi´arias de suas solu¸c˜oes devem ser apresentadas com clareza. Note que as quest˜oes abaixo n˜ao neces- sariamente pedem justificativas, mas deixar de provˆe-las acarretar´a na quest˜ao ser zerada. 1. (10 points) Escreva duas fun¸c˜oes em SML, f e g, que demonstrem que SML n˜ao faz passagem de parˆametros por expans˜ao de macros. A fun¸c˜ao f deve chamar apenas a fun¸c˜ao g, e a fun¸c˜ao g n˜ao deve chamar nenhuma outra fun¸c˜ao. Explique os resultados que a chamada por expans˜ao de macros produziria e porque eles n˜ao diferentes dos resultados que SML produziria. 2. (10 points) Considere um sistema de gerenciamento de mem´oria capaz de fazer aloca¸c˜oes com a estrat´egia first-fit e com a estrat´egia best-fit. A estrat´egia best-fit ´e implementada tal que o primeiro bloco na lista de blocos livres que melhor se adequa `a requisi¸c˜ao ´e escolhido. A mem´oria representa os blocos de mem´oria alocados e a lista ligada de blocos livres em um vetor. Cada bloco de mem´oria alocado para n posi¸c˜oes tem em sua primeira posi¸c˜ao seu tamanho n + 1 e mais n posi¸c˜oes para armazenar dados. Blocos livres tamb´em tem em sua primeira posi¸c˜ao seu tamanho e na posi¸c˜ao seguinte o ´ındice no vetor da posi¸c˜ao inicial do bloco livre seguinte na lista ligada de blocos vazios. O sistema de gerenciamento de mem´oria mant´em um ponteiro para o primeiro bloco livre na lista. Ao alocar n posi¸c˜oes em um bloco de tamanho compat´ıvel, se o bloco livre resultante da quebra tiver apenas uma posi¸c˜ao, a quebra n˜ao ocorre. Dada a especifica¸c˜ao acima, considere que mm ´e um sistema de gerenciamento de mem´oria com 11 posi¸c˜oes dispon´ıveis. A opera¸c˜ao allocate(n) faz aloca¸c˜ao de n posi¸c˜oes na mem´oria e retorna o endere¸co desde bloco, adicionando `a lista de blocos livros o resto da mem´oria n˜ao alocada do bloco livre escolhido (que ´e por sua vez retirado da lista). A opera¸c˜ao deallocate(a) recebe um endere¸co de um bloco alocado e faz a desaloca¸c˜ao deste bloco, colocando-o no fim da lista ligada de blocos livres. Considere a seguinte lista de opera¸c˜oes em mm (com a estrat´egia first-fit): a = mm.allocate(4); b = mm.allocate(1); c = mm.allocate(3); mm.deallocate(c); mm.deallocate(a); Apresente uma sequˆencia de opera¸c˜oes allocate que, a partir do estado da mem´oria ap´os as opera¸c˜oes acima, falha com a estrat´egia first-fit mas seria bem-sucedida com a estrat´egia best- fit. 3. (10 points) Considere a seguinte consulta em Prolog: ?- append(X,Y,[1,2,3,4]),length(X,L1),length(Y,L2),L1+L2=<4. Em que append ´e o predicado para concatena¸c˜ao de duas listas, length o de medir o tamanho de uma lista. i. Quantas solu¸c˜oes ´unicas a consulta acima possui? Isto ´e, diferentes unifica¸c˜oes para as vari´aveis X e Y tais que a consulta ´e v´alida. (a) 1 (b) 3 (c) 4 (d) 5 ii. Explique em termos da refuta¸c˜ao que Prolog constr´oi, utilizando unifica¸c˜ao e resolu¸c˜ao, por que a consulta tem exatamente esse n´umero de solu¸c˜oes. Note que vocˆe n˜ao precisa escrever as refuta¸c˜oes, s´o argumentar em termos delas. 4. (10 points) Considere, em Prolog, um predicado ordered(L) que seja verdadeiro quando a lista L estiver em ordem crescente. Defina, usando fatos e regras, o predicado ordered. Page 2