Upload
sine
View
46
Download
0
Embed Size (px)
DESCRIPTION
Tema 1: Introducció als llenguatges de programació i als seus paradigmes. Seccions. Llenguatge de Programació Història i Evolució Paradigmes i models de còmput subjacents. Llenguatge de Programació. Llenguatge de Programació. - PowerPoint PPT Presentation
Citation preview
Tema 1:Introducció als llenguatges de programació i als seus paradigmes
Seccions
• Llenguatge de Programació• Història i Evolució• Paradigmes i models de còmput subjacents
LLENGUATGE DE PROGRAMACIÓ
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.
Tesis de Church-Turing
• Church’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”.
slide 6
Formalismes de còmput• Lògica de Predicats
• Gottlöb Frege (1848-1925)• 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 (1912-1954)• Programació imperativa
– Un còmput és l’evolució seqüencial d’estats mitjançant assignacions
slide 7
Formalismes de còmput• Lambda calculus
• Alonzo Church (1903-1995)• 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 (1909-1994)• Expressions regulars, màquines
d’estats finits, PDAs
Sobre la Tesis de Church-Turing
• Turing-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
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”.
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
HISTÒRIA I EVOLUCIÓ
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.
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.
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,
17468 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
• Altres ordinadors cohetanis durant WWII:• Z3 (1941): targetes perforades• Colossus (1943): criptoanàlisis• …
ENIAC:
Codis Màquina
• 40’s• Els codis eren numèrics.
– 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ó?
Llenguatges ensambladors
• Principis 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.
Primer llenguatge algorísmic
• PlanKalkul 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.
FORTRAN (Formula Tranlator) • 1954-57 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)
Exemple de Fortran
È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)
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.
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)
Exemple d’Algol
È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, …
program P0;var
R1, T1: real;A1: array[0:5,0:20] of real;
procedure P1(
X: real;
varT: real;Y: array[0:5,0:20] of real;)
procedure P2;
var R2, T2: real; A2: array[0:5,0:20]
of real;
begin R2 := 5; T2 := 25; P1(R2, T2, A2); /*
calls P1 */end;(* P2 *)
begin
P2; /* calls P2 */
end; (* P1 *)
begin
P1(R1, T1, A1); /* calls P1 */end;(* program *)
Program Stack
Working space for Procedure P0, the main program
Memory for variable T1
Pointer to elements of A1
Memory for variable R1
Reference to procedure P1
Working space for Procedure P2
Memory for the variable R2
Memory for the variable T2
Pointer to the elements of A2
Activation record for
P0
Activation record for
P1
Activation record for
P2
Working space for Procedure P1
Memory for variable X
Pointer to variable T1
Indirect pointer to elements of A1
Reference to procedure P2
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 – …
Exemple de COBOL 000100 ID DIVISION. 000200 PROGRAM-ID. ACCEPT1. 000300 DATA DIVISION. 000400 WORKING-STORAGE SECTION. 000500 01 WS-FIRST-NUMBER PIC 9(3). 000600 01 WS-SECOND-NUMBER PIC 9(3). 000700 01 WS-TOTAL PIC ZZZ9. 000800* 000900 PROCEDURE DIVISION. 001000 0000-MAINLINE. 001100 DISPLAY 'ENTER A NUMBER: '. 001200 ACCEPT WS-FIRST-NUMBER. 001300* 001400 DISPLAY 'ANOTHER NUMBER: '. 001500 ACCEPT WS-SECOND-NUMBER. 001600* 001700 COMPUTE WS-TOTAL = WS-FIRST-NUMBER + WS-SECOND-NUMBER. 001800 DISPLAY 'THE TOTAL IS: ', WS-TOTAL. 001900 STOP RUN.
Èxit de COBOL
• Llenguatge simple• Molt 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
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…
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
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)) ) ))
PL/1
• 1964• Desenvolupat per un comitee d’IBM
– Millorar 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
Exemple de PL/1
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…
Exemple de BASIC10 REM THIS IS A BASIC PROGRAM FOR FINDING THE MEAN20 DIM A(99)30 INPUT N40 FOR I = 1 TO N50 INPUT A(I)60 LET S = S + A(I)70 NEXT I80 LET M = S/N90 LET K = 0100 FOR I = 1 TO N110 IF A(I) < M THEN 130120 LET K = K + 1130 NEXT I140 PRINT “MEAN IS”, M150 PRINT “NUMBER GREATER THAN MEAN IS”, K160 STOP170 END
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, …
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”
Exemple de Codi PASCAL(*Pascal program for finding the mean*)Program main (input, output);
type intlist = array [1 . . 99] 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 begin readln(a[i]); sum := sum + a[i] end; mean := sum/n; for I := 1 to n do if (a[i] > mean) then number := number + 1; writeln (‘the number over mean is: ‘, number)end.
C
• 72, Dennis Ritchie (T. Aw.)• Més baix nivell que PASCAL• Fortament lligat a Unix• Descomposició de mòduls i linkatge• Sistema de tipus més permissiu.• Clar condicionador de C++ i JAVA (sintaxi)
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.
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.
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, …
2000’s
• SCALA– Web, Concurrencia, Funcional (alt nivell i
modularitat) + JAVA• MiniZinc
– Constraint programming declaratiu– Model once solve everywhere
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ó• …
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…)