1 Tema 1: Introducció als llenguatges de programació i als seus paradigmes
2 Seccions Llenguatge de Programació Història i EvolucióParadigmes i models de còmput subjacents
3 Llenguatge de Programació
4 Llenguatge de ProgramacióUn llenguatge de programació és una notació per a escriure programes. (Sethi, 89) Un programa és una especificació d’un còmput. Per còmput entenem allò que pot fer una màquina de Turing.
5 Tesis de Church-TuringChurch’s Thesis: “Every effectively calculable function (effectively decidable predicate) is general recursive”. Turing’s Thesis: “Every function which would be naturally regarded as computable is computable by a Turing machine”.
6 Formalismes de còmput Lògica de Predicats Màquines de TuringGottlöb Frege ( ) Base formal de la teoria de la demostració i la demostració automàtica de teoremes Programació lògica Un còmput és una deducció lògica Màquines de Turing Alan Turing ( ) Programació imperativa Un còmput és l’evolució seqüencial d’estats mitjançant assignacions slide 6
7 Formalismes de còmput Lambda calculus Funcions recursives & automatesAlonzo Church ( ) Base formal per als llenguatges funcionals, la semàntica, la teoria de tipus, etc. Programació Funcional Un còmput és la reescriptura d’una expressió fins a una forma normal. No hi ha assignacions. Funcions recursives & automates Stephen Kleene ( ) Expressions regulars, màquines d’estats finits, PDAs slide 7
8 Sobre la Tesis de Church-TuringTuring-completesa: tenir la mateixa capacitat de còmput que les màquines de Turing. Per exemple: Lambda-càlcul, funcions recursives, lògica de predicats,… No serien Turing-complets: autòmates finits (DFAs), gramàtiques incontextuals, etc. No es coneix cap sistema Turing-complet que no sigui Turing-equivalent => reforça Tesis C-T
9 Llenguatge de ProgramacióNotació formal per a especificar còmputs: Lèxic (paraules permeses…) Sintaxis (regles de formació de programes…) Semàntica (significat i efecte de les diferents construccions…) Implementacions concretes… Normalment s’espera que el sistema notacional sigui intel·ligible per l’humà i fàcilment traduïble per a que la màquina l’“entengui”.
10 Perquè estudiar LP i Paradigmes?L’estructura d’un llenguatge de programació acota el procés intel·lectual del programador al programar. Aprendrem conceptes bàsics i de vegades ignorats les llenguatges: pas per valor, pas per paràmetre, tipus estàtics, funcions d’ordre superior, etc. Farà més fàcil aprendre nous llenguatges Farà més fàcil dissenyar nous llenguatges
11 Història i evolució
12 Primeres màquines amb “llenguatge”Teler de Jaquard, 1801. Permetia fer diferente tipus de teles en funció de les targetes perforades que contenien els patrons desitjats.
13 Primeres màquines amb “llenguatge”Màquina analítica de Charles Babbage per a càlcul (1816+-) Motor a vapor, programes amb targetes perforades, … No es va arribar a fabricar. Ada Lovelance, primera programadora.
14 Primers “ordinadors” ENIAC: Electronic Numerical Integrator And Computer. (1946 … 1955) Primer ordinador electronic de propòsit general. Dim: 2,4m x 0,9m x 30m, 167m^2, 27 Tonelades, vàlvules, 150kW, … Programar era complicat… per “passar al programa dins d’ENIAC”, s’havia de tocar interruptors i cables… Encara no havia implementat la idea de tenir memoria per al programa i memòria per a les dades
15 ENIAC: Altres ordinadors cohetanis durant WWII: Z3 (1941): targetes perforades Colossus (1943): criptoanàlisis …
16 Codis Màquina 40’s Els codis eren numèrics. Llenguatge de Programació?Poc llegibles Poc modificables Programar era molt complicat Problemes inherents al hardware com falta d’indexació, no existència d’aritmètica real, … Llenguatge de Programació?
17 Llenguatges ensambladorsPrincipis dels 50: per no haver de escriure/perforar directament codis binaris com a operacions del càlcul de les màquines, es va recorrer al mnemotècnics: Llenguatge ensamblador: push ebp mov ebp, esp sub esp, 4 push edi Introduia gestio de macros i subrutines.
18 Primer llenguatge algorísmicPlanKalkul per Conrad Zuse (dissenyador de Z3), 1948. No es va implementar… Permetia coherència de tipus int/bool, estructures condicionals, iteracions, assignacions, etc. Va dissenyar un programa per jugar a escacs.
19 FORTRAN (Formula Tranlator)per John Backus. Orientat al càlcul matemàtic. Característiques: Variables de fins a 6 caràcters Les que comencen per i, j, k, l, m o n eren enteres Les altres floats Assignacions amb expressions aritm. do … while Subrutines i funcions Formats d’entrada sortida Independència de la màquina (idea de compilar/interpretar)
20 Exemple de Fortran
21 Èxit de Fortran Dubtes d’eficiència degut al Alt nivell, cosa que implicava traduir… però, molt bon traductor. Facilitava l’aprenentatge (vs. Assemblador) IBM Eficiència al desenvolupar Moltes seqüeles i avui en dia encar utilitzat en cert àmbits científics… (Fortran 2003, OO)
22 ALGOL (ALGOrithmic Language)1958 Desenvolupat per comitè per a ser standard (acadèmic) per descriure càlculs en publicacions. Inclure notació matemàtica llegigle Fàcil de traduir a codi màquina Descripció gramàtica amb BNF, facilitat compiladors.
23 ALGOL (ALGOrithmic Language) (2)Aportacions: Variables amb nom qualsevol Estructurat. Blocks i visibilitat Arrays amb multiples dimensions Estructures de control riques: Seqüències, if-then-else, For-step-until-do, … Procediments recursius Modes al pas de parametres (e/s)
24 Exemple d’Algol
25 Èxit Algol? Tres anys després de Fortran.Era més ric i per tant més complicat d’aprendre. Els compiladors de Fortran eren més senzills de fer i més eficients. … D’altra banda: influència tota la programació estructurada: Pascal, C, JAVA, …
26 Program Stack Working space for Procedure P2program P0; var R1, T1: real; A1: array[0:5,0:20] of real; procedure P1( X: real; T: real; Y: array[0:5,0:20] of real;) procedure P2; R2, T2: real; A2: array[0:5,0:20] of real; begin R2 := 5; T2 := 25; P1(R2, T2, A2); /* calls P1 */ end;(* P2 *) P2; /* calls P2 */ end; (* P1 *) P1(R1, T1, A1); /* calls P1 */ end;(* program *) Working space for Procedure P2 Activation record for P2 Pointer to the elements of A2 Memory for the variable T2 Memory for the variable R2 Working space for Procedure P1 Reference to procedure P2 Activation record for P1 Indirect pointer to elements of A1 Pointer to variable T1 Memory for variable X Working space for Procedure P0, the main program Reference to procedure P1 Activation record for P0 Pointer to elements of A1 Memory for variable T1 Memory for variable R1 COP 4020 Programming Languages 1
27 COBOL (Common Business Oriented Language)1957 És bàsicament un llenguatge processador de dades, orientat a negoci. Aportacions: Dades i programes separats Llenguatge proper al natural (ops. en anglès) Fàcil implementació Noms de dades 30 caràcters Tipus registre Autodocumentat …
28 Exemple de COBOL ID DIVISION PROGRAM-ID. ACCEPT DATA DIVISION WORKING-STORAGE SECTION WS-FIRST-NUMBER PIC 9(3) WS-SECOND-NUMBER PIC 9(3) WS-TOTAL PIC ZZZ * PROCEDURE DIVISION MAINLINE DISPLAY 'ENTER A NUMBER: ' ACCEPT WS-FIRST-NUMBER * DISPLAY 'ANOTHER NUMBER: ' ACCEPT WS-SECOND-NUMBER * COMPUTE WS-TOTAL = WS-FIRST-NUMBER + WS-SECOND-NUMBER DISPLAY 'THE TOTAL IS: ', WS-TOTAL STOP RUN.
29 Èxit de COBOL Llenguatge simpleMolt arrelat en l’entorn financer, e.g. Bancs i Caixes. Entorns molt grans on els canvis són molt costosos…. (ex. cas de l’any 2000) Avui en dia… OO
30 LISP (List Processing Language)1959, MIT, McCarthy (T. Aw.) Basat en lambda-càlcul Aportacions Garbagge collector Tipatge dinàmic Identificació de manipulació entre codi i dades Pare de la programació funcional…
31 Frases sobre LISP “LISP being the most powerful and cleanest of languages, that's the language that the GNU project always prefer” -- Richard Stallman “Anyone could learn Lisp in one day, except that if they already knew FORTRAN, it would take three days” -- Marvin Minsky
32 Exemple LISP (defun list-nth (N L) "Return the N'th member of a list L." (if (null L) nil (if (zerop N) (first L) (list-nth (1- N) (rest L)) )
33 PL/1 1964 Desenvolupat per un comitee d’IBMMillorar el rendiment dels programadors de propòsit general (vs. Fortran i Cobol) Eclèctic: Pas de paràmetres, estructurat, registres, processament de llistes, excepcions, multi-tasca, punters, … Però: massa gran i complexe
34 Exemple de PL/1
35 BASIC (Beginner’s All-purpose Symbolic Instruction Code)1966 Característiques: Variables no es declaren. Els noms són lletres simples. S’inicialitzen a 0. Fàcil de fer servir i aprendre. GOTO…
36 Exemple de BASIC 10 REM THIS IS A BASIC PROGRAM FOR FINDING THE MEAN 20 DIM A(99) 30 INPUT N 40 FOR I = 1 TO N 50 INPUT A(I) 60 LET S = S + A(I) 70 NEXT I 80 LET M = S/N 90 LET K = FOR I = 1 TO N 110 IF A(I) < M THEN LET K = K NEXT I 140 PRINT “MEAN IS”, M 150 PRINT “NUMBER GREATER THAN MEAN IS”, K 160 STOP 170 END
37 PASCAL 71, Wirth (T. Aw.) Llenguatge educatiu. El més usat dels 70.Inclou “rut-time environment”: (Codi, dades estàtiques, pila -> … <- Heap) Permet definir nous tipus a l’usuari. Continua amb C, ADA, Java, …
38 Frases de Wirth “Power of a language lies in its regularity and not in its abundant of Features” “Character of a language is defined by what it prevents more than by what it allows to be expressed”
39 Exemple de Codi PASCAL (*Pascal program for finding the mean*) Program main (input, output); type intlist = array [ ] of integer; var a : intlist; i, n, number : integer; sum, mean : real; (*main program starts here *) begin number := 0; sum := 0; readln (n); for I := 1 to n do readln(a[i]); sum := sum + a[i] end; mean := sum/n; if (a[i] > mean) then number := number + 1; writeln (‘the number over mean is: ‘, number) end.
40 C 72, Dennis Ritchie (T. Aw.) Més baix nivell que PASCALFortament lligat a Unix Descomposició de mòduls i linkatge Sistema de tipus més permissiu. Clar condicionador de C++ i JAVA (sintaxi)
41 80s ADA: TAD, taskes, excepcions, paquets, …Smalltalk: OOP (Simula 67), entorn de desenvolupament visual Funcionals: ML, Miranda, … Fortament tipats, lazyness, … primes = sieve [2..] sieve (p:x) = p : sieve [n | n <- x; n mod p ~= 0] Prolog: Primer en programació lògica C++: C + classes, i herència múltiple, Templates/genèrics, excepcions, … Té molt èxit.
42 90’s JAVA: interfaces explítics, herència simple, garbagge collection (s’amaga la gestió de memòria), … Èxit per la conexió amb l’explosió WWW Compile once, run everywhere Màquina virtual +lent que C++ Sintaxi similar al C++ -> fàcil trànsit.
43 90’s Scripting: Perl, python, AWK,…senzills, dinàmics, estructures de tipus d’alt nivell, no fortament tipats, etc. Haskell: fortament tipat, lazy, pur, … Constraint Programming: SICSTUS Prolog, …
44 2000’s SCALA Web, Concurrencia, Funcional (alt nivell i modularitat) + JAVA MiniZinc Constraint programming declaratiu Model once solve everywhere
45 Què volem d’un bon llenguatge?Claritat, simplictat i unicitat Pocs conceptes fàcils de combinar (integritat) Llegibilitat Suport a l’abstracció Tipus Funcions Facilitat de raonar-ne la correctesa i de testejar Eficiència Portabilitat Entorna de desenvolupament Documentació …
46 Biblio Capítol: 1,2: “Concepts in programming languages”Capítol 1,2: “Lenguajes de programación: principios y prácticas” Wikipedia (fotos i demés…)