PDF de programación - Capítulo 1. Introducción

LenguajesdeProgramación

Capítulo1.
Introducción
CarlosUreñaAlmagro
Curso2011-12

Contents
1 ElconceptodeLenguajedeProgramación
2 Criteriosdediseño
3 ParadigmasdeProgramación
.
.
.
3.1
LenguajesImperativos .
.
.
.
LenguajesFuncionales.
3.2
.
.
.
3.3
LenguajesDeclarativos
4 Antecedentes
.
.
.
.
.
.
4.1 Plankalkül .
.
.
.
4.2 Shortcode .
.
.
.
.
.
.
.
.
.
4.3 A-0 .
.
.
.
.
5 Losprimeroslenguajesdeprogramación
.
.
.
.
.
5.1 Fortran .
.
.
.
.
.
.
.
.
.
.
.
5.2 Algol
.
.
.
.
.
.
.
5.3 Simula .
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

2
6
8
8
9
10
11
11
12
12
13
13
14
15

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
1

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

LP(11-12)1. Introducción
1 ElconceptodeLenguajedeProgramación
ElconceptodeLenguajedeProgramación
Unlenguajedeprogramaciónesunconvenioentrepersonasquepuededefinirseasí:

Conjuntodereglasonormasquepermitenasociaracadaprogramacorrectouncálculoqueserá
llevadoacaboporunordenador(sinambigüedades).
• portanto,unlenguajedeprogramaciónesunconveniooacuerdoacercadecomosedebedeinterpretar
elsignificadodelosprogramasdedicholenguaje
• muchas veces se confunden los lenguajes con los compiladores, interpretes o con los entornos de
desarrollodesoftware
Estándarizacióndeloslenguajes
El convenio suele estar reflejado en un documento (un libro) que se hace público y mediante el cual se
determinanlasreglasdeinterpretacióncorrectadelosprogramas
• algunoslenguajesestándefinidosporundocumentoestandarizadoenunorganismooficialcomoISO
(p.ej. C++eselestándardISO/IEC14882,de1998)
• enotroscasosladescripcióndellenguajenoestáoficialmenteestandarizada,ellenguajesedefinepor
eldocumentodereferenciaquelodescribe(pej.Java,descritoenestelibrohttp://java.sun.com/docs/books/jls/)
¿queesunprograma?
Enestecontexto,unprogramaesuna:
Secuenciafinitadedígitosycaracteres,directamentelegibleporlaspersonasyporelordenador
• estassecuenciassesuelenalmacenarenunoovariosarchivosdetextoASCIIoUNICODE.
• también es posible almacenar programas en formatos alternativos de archivos, como XML u otros,
aunque en stos casos los archivos no son directamente legibles por las personas, sí son legibles
medianteherramientasdetraducción.
¿queesunprogramacorrecto?
Cada lenguaje tiene asociado un conjunto (que debe estar bien definido en el lenguaje) de programas
correctos.
• Lasreglasdecadalenguajedebendefinireseconjuntosinambigüedades.
creadoOctober11,2011

página1.2/17

LP(11-12)1. Introducción
• Paraestosesuelenusarmétodosmasomenosformales. Lavalidezdeunprogramasedefineavarios
nivelescontécnicasdistintas:
– léxico: expresionesregulares
– sintaxis: gramáticaslibresdecontexto
– semántica: descripcionesoreglasnoformales

¿queesuncálculo?
Esnecesariodefiniradecuadamentequeseentiendeporcalculo,podemosverlodesdedosperspectivas:
• ensentidoamplio:
• ensentidoformal:

Cualquierprocesoautomáticoderecogida,manipulación,ydifusióndeinformación
Cualquierprocesoautomáticocuyosaspectosrelevantespuedansermodeladosmatemáti-
camenteconunamáquinadeturing
¿queeselsignificadodeunprograma?
Alcálculoasociadoporunlenguajeaunprogramacorrectoseleconsideraelsignificadodelprograma.
• a las metodologías para especificar el significado de los programas se les llama semántica de los
lenguajesdeprogramación.
• lasreglasdecadalenguajedebenpermitirestablecerelsignificadosinambigüedadalguna,deforma
clarayconcisa
¿queeselsignificadodeunprograma?
Ejemplodesignificado: consideremosesteprograma


int fact(int n)
{

if (n>0)
else

return n*fact(n-1) ;
return 1 ;

}
int main()
{

int n ;
while( cin >> n )

cout << fact(n) ;

}
creadoOctober11,2011

página1.3/17





LP(11-12)1. Introducción
¿queeselsignificadodeunprograma?
Elsignificadodelanteriorprogramaeselcálculonecesarioparaevaluarunadeterminadafunción f.
• Lafunción f eslaqueasocia, aunasecuenciadenúmerosenteros, otrasecuenciaquecontieneel
factorialdecadaunodeellos.
• Existenvariasaproximacionesalasemánticadeloslenguajesdeprogramación.
• Loquehemosvistosedenominasemanticadenotacional(unprogramadenotaunafunción)
Ellenguajecomounafunciónqueasignasignificado

(a1, . . . , an) → f (a1, . . . , an) = (a1!, . . . , an!)

f ∈ N∗

→ N∗

C1 = f (P1)
C2 = f (P2)

Programasequivalenes
Distintosprogramaspuedentenerelmismosignificado(seríanequivalentes)

creadoOctober11,2011

página1.4/17

Programas posiblesProgramas correctosSignificadosposibles fLenguaje deprogramaciónP1P2C1C2LP(11-12)1. Introducción

C = f (A) = f (B)




Ambigüedadenlosprogramas
Loslenguajesdebensernoambiguos:
• Encuantoalacorrección: debeserposiblecalcularsiunprogramaescorrectoono
• Encuantoalsignificado: elsignificadodeunprogramadebeserúnico.
UnejemplodeambiguedadeslasiguienteexpresiondeC/C++


Segúnelestándard,puededenotardoscalculosdistintos: sepuedeimprimir12o13comosalida.
¿paraquesirvenloslenguajesdeprogramación?
Esencialmente:

int a = 3 ;
cout << ((++a) + (a*=2)) ;

// 4+8 o 7+6

paracomunicaraunordenadorunprocesamientoquevaallevarseacaboendichodispositivo
(deformacómodaparalapersonaqueescribeelprograma).
Perotambién:
paracomunicarentrepersonasinformaciónnoambiguasobrealgoritmosmatemáticosoprocesos
reales

creadoOctober11,2011

página1.5/17

Programas correctosCálculosposiblesLenguaje de programaciónABCfLP(11-12)1. Introducción
¿comodebenserloslenguajesdeprogramación?
Comotodaactividaddediseñoeningeniería,unlenguajedeprogramacióndebeserdiseñadosiguiendounos
principiosbásicos.
2 Criteriosdediseño
CriteriosdediseñodeLL.PP.
Acontinuaciónseincluyenunaseriedecaracterísticasdeseablesdeloslenguajesdeprogramación:
• Casisiempre,lograrunadeellasnosacercaaotrascaracterísticasrelacionadas,peroinevitablemente
tambiénnosalejadeotrascaracterísticascontrapuestasalaprimera.
• Cadadiseñodeunlenguajesuponeuncompromisooequilibrioentrelascaracterísticasdeseables.
Facilidaddelecturayescritura
Facilidaddeescritura(writability)

Facilidadparaexpresaruncálculodeformaclara, correcta, concisa, yrápida.
terísticamuygenérica,queseconcretaenotras)
El diseño del lenguaje debe permitir que la lectura de los programas lleve fácilmente a una
compresióncorrectadelcálculoquesignifican.

(esunacarac-

Legibilidad

GeneralidadyOrtogonalidad
Generalidad

Ortogonalidad(independencia)

Lascaracterísticasoconstruccionesdellenguajedebenseraplicablesuniformementeyconla
mínimasrestriccionesentodosloscontextosposibles.
Lasdiferentescaracterísticasdebenserlomásindependientesposibleentreellas,enelsentido
dequeelusodeunanodebemodificar,limitaroimpedirelusosimultáneoocombinadodeotra.

creadoOctober11,2011

página1.6/17

LP(11-12)1. Introducción
UniformidadySimplicidad
Uniformidad
Simplicidad

Expresividadyfiabilidad
Expresividad
Fiabilidad

Característicasparecidasdeberíanteneraparienciasparecidas. Característicasdistintasnode-
beríantenerlamismaapariencia
Elnumerodecaracterísticasoposibilidadesdistintasoindependientesdeberíaserelmínimo
posible. Nodeberíahabercaracterísticasdistintasperomuyparecidas.

Ellenguajeesexpresivocuandopermiteexpresarconfacilidadprocesosoestructurascomplejos.
Ellenguajedebehacerfácillaconstruccióndeprogramasfiables,ydebeimpedirodificultadla
construccióndeprogramasnofiables.

Definicióncorrectayportabilidad
Definciónprecisayclara
IndependenciadelamáquinayelS.O.

Comoyasehacomentado,lacorrectitudyelsignificadodetodoprogramadebenestardefinidos
sinambigüedades,yademás,estasdefinicionesdebenfácilmentelegiblesycomprensibles.
Engeneral,ellenguajedebepermitirlaconstrucciónconlamáximafacilidadposibledeprogra-
masusablesenarquitecturashardwareySS.OO.distintasconunmínimodecambios.

Eficiencia
Eficienciaenlatraducción
Eficienciadeejecución

creadoOctober11,2011

Eldiseñodellenguajedebepermitirfácilmentelaconstruccióndetraductoreseintérpretesque
seaneficientesenusodetiempoymemoria
Eldiseñodellenguajenodebedarlugaraquelainterpretaciónoejecucióndelosprogramas
traducidosconlleveunaltogastoentiempoomemoria.

página1.7/17

LP(11-12)1. Introducción
3 ParadigmasdeProgramación
ParadigmasdeProgramación
Constituyentrescategoríasdeloslenguajesdeprogramación:
• Imperativos
• Funcionales(oaplicativos)
• Lógicos(odeclarativos)
¿queesunparadigmadeprogramación?
• Cadaunodeestosparadigmassecaracterizaporunmodeloformaldistintodeloqueconstituyeun
cálculo.
• Elconjuntodecálculosrealizablesesigualenlostrescasos(losquesepuedenhacerconmáquinas
deturing)
3.1 LenguajesImperativos
LenguajesImperativos
Uncálculoesunconjuntodeinstruccionesqueestablecenexplícitamentecomosedebemanipularlainforma-
cióndigitalpresenteenmemoria,y/ocomosedeberecogeroenviarinformacióndesde/hacialosdispositivos
Ejemplos:
• Ejemplosdelenguajesimperativos: Fortran,Algol,Pascal,C,Ada,C++,Java,C#
• Lamayoríadeloslenguajesusadosparadesarrollodesoftwarecomercialsonimperativos
EjemploenC(1/2)




int mcd( int x, int y )
{

if ( x == 0 && y == 0 )
{ printf("error!"); exit(1);
}
if ( x < 0 ) x = -x ;
if ( y < 0 ) y = -y ;
while( y != 0 )
{ int r = x % y ;
x = y ; y = r ;

creadoOctober11,2011

página1.8/17

LP(11-12)1. Introducción

}
return x ;

}
EjemploenC(2/2)


int main()
{

printf("%d\n",mcd(10,102));

}
3.2 LenguajesFuncionales
LenguajesFuncionales(oaplicativos)
Uncálculoeselprocesodeaplicarunafunciónrecursivaaunvalordesudominioparaobtenerelcorre-
spondientevalordelrango(elresultado).
Eltérminofunciónrecursivadebeentenderseaquísegúnseintroduceenlateoríadelacomputabilidad,es
decir,comounafuncióncalculableconunamáquinadeturing(nocomounsubprogramaqueseinvocaasi
mismo)
LosprogramasenlosLenguajesFuncionales
Unprogra