Paradigmes de programació (Pla 97)

 

3105200736 - Paradigmes de programació (Pla 97)

 

 

Professor: Mateu Villaret

                  230, P-IV

                  972418838

            villaret -at- ima.udg.edu

 

 

 

NOTES 2a convocatòria:    NotesParadigmes1213b.pdf

 

 

 

 

Guió de les sessions (teoria i laboratori):

 

# Sessió

Data      

Descripció

Material

Exercicis

1

5 de febrer

Presentació del curs.

1.Introducció.

    Què és un LP?

    Computabilitat.

    Història i evolució dels Llenguatges de programació.

 

 

 

PiLdP-Tema1.pptx

 

Bib 2. Cap. 1,2

 

Bib 1. Cap. 2

diagramaLP

Bib 1. Cap. 1.3

 

2

8 de febrer

   

     Classificacions

       Paradigmes: Imperatiu, funcional i lògic

 

2. Programació Funcional

    Motivació

    Noció de Funció

    Lambda-càlcul

      El llenguatge     

 

 

 

 

 

 

Bib 5. Cap. 3

Transpes suport:

   sempf.pdf

 

Treu parèntesis als termes donats a classe, d’acord amb la notació.

3

12 de febrer

   

      Variables lliures/lligades

      Reemplaçament

      Substitució      

      Teoria del Lambda Càlcul

      Estratègies de reducció

 

Bib 5. Cap. 3

Transpes suport:

   sempf.pdf

 

Fes les substitucions demanades a la página 11 de les transpes.

4

13 de febrer

     

      Combinadors “famosos”

    Lambda-Càlcul com a Lleng. de Prog.

      Bool, Condicional, Tuples, Llistes, Naturals,...

   

Bib 5. Cap. 3

 

Transpes suport:

   sempf.pdf

Troba les formes normals fent les B-reduccions pas a pas de:

(\x. x(x(yz))x)(\u.uv)

(\x.\y.\z. x z (y z)) (\u. y \v.u)

Troba els \-termes M i N tals que (M N) tingui forma normal però

- M en tingui i N no

- N en tingui i  M no

- Ni M ni N en tinguin

Troba el combinador G’ tal que

(G’ M) es B-redueixi a (M G’)

5

19 de febrer

   

     ... el predecessor i la resta

     Demostracions d’adequació de les definicions

     

Bib 5. Cap. 4

 

Transpes suport:

   sempf.pdf

 

6

20 de febrer

            Combinadors de punt fixe

     

      Recursivitat

      LListes

Bib 5. Cap. 4

 

Transpes suport:

   sempf.pdf

- Defineix la funció resta. (no hi ha negatius, per tant es queda al zero). Pista utilitza prec.

- Demostra que T  és un combinador de punt fixe.

- Amb les definicions de llistes donades a classe, defineix la concatenació de llistes i la funció llargada (fes-ho recursivament).

- Dóna una definició alternativa per tal que poguem fer llargada sense recursivitat. Compte, esnula ha de seguir funcionant.

7

26 de febrer

HASKELL

-Programació funcional

   Funcions, sessions i declaracions,

   reducció d’expressions.

-Introducció al Haskell

   El Llenguatge, tipus simples

   predefinits, constructors de tipus

   predefinits, comentaris,

   definicions de funcions, ......

Bib 3. Cap. 1,2

tema1.pdf

tema2.pdf

 

 

 

Bib 3. Cap. 2

tema3.pdf

 

 

8

27 de febrer

Treball al laboratori

 

 

9

5 de marc

-Funcions d’ordre Superior

   Ordre superior

   Expressions Lambda

   Parcialització

   Polimorfisme

   Inferència de tipus de les funcions

 

-Definició de tipus abstractes de dades 

 

Bib 3. Cap. 3

tema4.pdf

 

Bib 3. Cap. 3

tema5.pdf

 

Bib 3. Cap. 4

tema6.pdf

 

 

10

6 de marc

- Llistes

 

Treball al laboratori

Bib 3. Cap. 6

tema8.pdf

 

 

11

12 de marc

- El sistema de classes de Haskell

 

- Arbres

 

- Entrada-Sortida

 

 

Bib 3. Cap. 5

tema7.pdf

 

Bib 3. Cap. 9

tema9.pdf

 

entradasortida.pdf

 

 

12

13 de març

- Llistes infinites i xarxes de processos

 

Treball al laboratori

Bib 3. Cap. 8

tema11.pdf

veributihaskpara.pdf

 

Opcional:

wxhaskell.pdf

13

19 de març

- Demostració de propietats de codi en Haskell, raonament equacional.   

 

 Lambda-Càlcul tipat, Sistema Curry

        Tipatge en els LP

        Inferència de tipus

Bib 3. Cap. 4

tema10.pdf

 

Transpes suport:

   sempf.pdf

Bib. 2, secció 6.3

 

14

20 de març

          Parse-tree

          Algorisme Hindley-Milner

          Unificació

          Equacions múltiple

          Recursivitat

Transpes suport:

   sempf.pdf

Bib. 2, secció 6.3

 

 Bib. 9: EXEMPLE

Exercici de Tipus

Exercici de demostracio:

length(xs++ys)=length xs + length ys

15

26 de març

 

 

16

27 de març

 

 

 

 

 

17

2 d’abril

 

Exàmen en grup

 

 

18

3 d’abril

Solucions Exercicis d’exàmen i altres

 

 

19

9 d’abril

3. Programació Lògica (amb restriccions - CLP)

    Introducció

    Lògica proposicional

      Sintaxis

      Semàntica

      Deducció/Resolució/Horn

      SLD-resolució

 

Bib. 6, Cap. 1,2

 

Transpes suport:

 

logica_breu.pdf

 

20

10 d’abril

    Lògica de primer ordre

      Sintaxis

      Semàntica

      Unificació

      Resolució

      

 

 

Bib. 6, Cap. 3

 

Transpes suport:

 

logica_breu.pdf

Exercicis:

- demostra si MT i MM són regles sòlides o no.

- troba totes les solucions de suma(A,B,s(s(zero))) utilitzant SLD-resolució, amb la teoria de la suma dels apunts.

- Fes exercicis de:

exercicisLiPdP-logic.pdf

concretament pel proper dia demanem: 6, 10 i 18.

21

16 d’abril

   PROLOG     (recordi Prolog en 2 hores)

prolog-breu.pdf

 

22

17 d’abril

   Constraint Programming

     - Cerca

     - Consistència

     - Cerca i propagació

  

 

constraints1011a.pdf

 

 

 

23

23 d’abril

CLP

     - extenent SLD-resolució amb gestió d’stores

 

constraintssicstus.pdf

indexicals.pdf

 

24

24 d’abril

     - exemples amb SICSTUS

bib. 7

 

25

30 d’abril

     - exemples amb SICSTUS

 

bib. 7

 

26

1 de maig

 

 

 

27

7 de maig

     - Modelització en CLP i exemples

constraints1011b.pdf

 

pracprol0607.pdf

actorspetit.pl

 

28

8 de maig

     Treball lab

 

 

 

Exercicis:

pracprol0506.pdf

ENUNCIAT de la PRÀCTICA

 

practicaCLP1213.pdf

 

instàncies:

 

inst0-pla.txt

inst1-pla.txt

inst2-pla.txt

inst3-pla.txt

inst4-pla.txt

 

29

14 de maig

 

 

 

30

15 de maig

 

 

 

 

 

 

Transpes LaTeX:

tema1p.pdf

tema2p.pdf

tema3p.pdf

tema4p.pdf

tema5p.pdf

tema6p.pdf

tema7p.pdf

tema8p.pdf

tema9p.pdf

tema10p.pdf

tema11p.pdf

tema12p.pdf

 

Exercicis de lambda-càlcul:

 

exercicis_lambda.pdf

 

Exercicis de Haskell (de José Enrique Gallardo, coautor del llibre “Razonando con Haskell”)

ejercicios.pdf

practicas.pdf

 

 

 

Bibliografia:

 

1.      “Lenguajes de programación” (Thomson),

2.      “Concepts in programming languages” (Cambridge press)

3.      “Razonando con Haskell” (Thomson)

o       Transpes dels autors (José Gallardo)

4.      “The art of Prolog” (MIT Press)

5.      Apunts de teoria de programació funcional: progfunc.pdf

o       Transpes: sempf.pdf

6.      Apunts de teoria de programació lògica: apuntspl.pdf

o       Transpes: sempl.pdf

7.      Apunts d’Ulf Nilsson sobre Sicstus i clpfd: clpfd.pdf

8.      Apunt de Programació lògica amb Constraints: introclp.pdf

9.      EXEMPLE d’inferència de tipus en HASKELL