PDF de programación - Capítulo 5. Ordenes

Capítulo5. Órdenes
LenguajesdeProgramación
CarlosUreñaAlmagro
Curso2009-10

.
.

.
.

.
.

.
.

Contents
1 Semánticadenotacionaldelasórdenes
2 Órdeneselementales
.
.
.
2.1
Laórdenskip .
.
.
.
.
.
.
.
.
.
.
2.2 Asignaciones
.
.
.
Llamadasaprocedimiento.
2.3
3 Órdenescompuestas
.
.
.
.
3.1 ComposiciónSecuencial .
.
.
.
.
.
.
3.2 Composicióncolateral
.
.
.
.
3.3 Órdenesbloque .
.
.
.
.
.
.
.
.
.
.
3.4 Órdenescondicionales .
3.5 Ordenesiterativas .
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

2
4
4
5
6
7
8
9
11
13
17

1

1 SEMÁNTICADENOTACIONALDELASÓRDENES

1 Semánticadenotacionaldelasórdenes
Semánticadenotacional
Unaordenesunaconstrucciónsintácticaquedenotaunafuncióndetransiciónentreestadosdeejecución
durantelaejecucióndeunprograma.
Portanto,unaordenesformalmenteunaaplicacióndelconjuntodelosestadosdeejecuciónensímismo
Semánticadeunaorden
Ejemplo: Supongamoslaorden Osiguiente:
peso=peso+1
Estaordenseaplicaaestadosdondeexisteunavariabledenombre"peso",dealgúntipoentero,yproduce
estadosdondeesavariablevaleunomásqueeneloriginal.
Efectoenelestadodeejecución
Ejemplo: SupongamoselestadodeejecuciónS:
Sea f laaplicaciónasociadaalaorden Ovistaantes,secumplequeelestado T = f (S)(laimagenpor f
de S)eselsiguiente:

S = { (”x”, f loat, 1.2) , (”peso”, int, 62) }

f (S) = { (”x”, f loat, 1.2) , (”peso”, int, 63) }

Dominiodeunaorden
Algunosestadosdeejecuciónnopertenecenaldominiodealgunasórdenes,porejemplo,elestadosiguiente:
nopertenecerealmentealdominiodelaaplicación fasociadaa O,dadoquenoexisteenelningunavariable
denombre"peso". Enestoscasos,laejecucióndelaordenllevaelprogramaaunestadoespecialdeerror:

S = { (”x”, f loat, 1.2) }

f (S) = error

2

1 SEMÁNTICADENOTACIONALDELASÓRDENES

Finalizacióndeunaorden
• Cuando la ejecución de una orden no termina (por ejemplo, la orden es un bucle infinito), también
decimosquelaejecuciónfalla,yportantoelestadoenelqueseacabaeselestadodeerror
• Noesposibledeterminarmedianteunordenador(entiempofinito)siunainstruccióncualquiera,en
unestadocualquiera,acabarádeejcutarseenuntiempofinitoono.
Deteccióndeerrores
• Engeneral,sielprocesadordeunlenguaje(traductor,compilador,intérpreteointérpretedecódigo
intermedio)puededeterminarqueunainstrucciónvaafallarenalgunosotodoslosestadosdeejecución
enlosquesevaaejecutar,entonces:
• Sedebeinformardeello,yhacerlotanprontocomoseaposible,yaqueesobeneficialafiabilidaddel
programa(seevitanerroresnodescubiertosqueprovocanresultadoserróneosyalarganlostiempos
dedesarrollo).
• Esunprincipioimportanteyquesedeberíaseguirporloslenguajesdeprogramación
Lafunciónsemántica Sem
• La función Sem (por función semántica) asigna a cada orden posible su correspondiente función de
transición. Consideramosestafuncióncomoelsignificado(semántica)delaorden.
• Enelejemplovistoantes( O = peso = peso + 1)
Órdenesequivalentes
Dosordenes O1y O2seconsideranequivalentes(seescribe O1 ≡ O2)cuandosusemánticaeslamisma:
Unejemplodedosinstruccionesequivalenteses:
• O1 = y = x ; y = y + 1
• O2 = x = x + 1 ; y = x ; x = x − 1

O1 ≡ O2 ⇐⇒ Sem[O1] = Sem[O2]

f = Sem[O] = Sem[peso = peso + 1]

3

2 ÓRDENESELEMENTALES

Órdenesnodeterministas
• Existenórdenesqueenalgunoscasosalejecutarsepuedenproducirunestadodesalidacualquiera
deentrevariosdeundeterminadoconjuntodeestados
• Encadaejecución,elestadoobtenidopuedeserdistinto,perosiemprepertenecealconjuntodeestados
desalida,queestábiendefinido,yqueengeneraldependedelestadodeentrada.
Órdenesdeterministasynodeterministas
Engeneral,podemosverlafuncióndetransicióncomounaaplicacióndeestadosenconjuntosdeestados:
• Unaordenesdeterministacuando, paracadaestadodeentrada, elconjuntosdeestadosdesalida
posiblestieneunúnicoelemento.
• Una orden es no determinista cuando existe al menos un estado de entrada para el cual la orden
conduceaunconjuntodeestadosdesalidaconmásdeunelemento.
2 Órdeneselementales
Órdeneselementales
Existenvariasclasesdeórdenes,yformasdecombinarlasentresiparaobtenernuevasórdenes. Distinguimos
doscategorías:
• Órdeneselementales: noestánobtenidascombinandootrasórdenes
• Órdenescompuestas: seobtienencombinandoentresíotrasórdenes,elementalesocompuestas.
enestaseccióncomenzaremosviendolasprimerasdeellas
2.1 Laórdenskip
Laórdenskip
• Laordenskipeslamássencillaposible.
• Nocomportaningunavariacióndelestadodeejecución(nohacenada)
• Lafuncióndetransiciónasociadaeslafunciónidentidad(aplicacadaestadoensimismo).

4

2 ÓRDENESELEMENTALES

2.2 Asignaciones
2.2 Asignaciones
Laórdendeasignación
• Unaasignaciónesunaordenqueindicaexplícitamenteelnuevovalordeunavariableenelestadode
ejecucióndedestino
• Laasignacióneslamásimportantedelasórdeneselementales,yconstituyelabasedetodoelresto
deórdenes.
• Laasignaciónincluyeinformaciónsobrelavariableamodificaryelnuevovalorqueseledebeasignar
Estructuradeunaórdendeasignación
Entodosloslenguajesdeprogramaciónlaasignacióntieneestasintaxis:
donde:
• exprizqesunaexpresión,enconcretounaccesoaunavariabledetipo T(alevaluarse,producecomo
resultadounareferenciaaunavariabledetipo T).
• exprderesunaexpresióndetipo T
• opasigeseltokendeasignación,normalmente =o :=
Ejecucióndelaordendeasignación
Paraejecutarlaasignaciónenunestado S,esnecesario:
1. Evaluar exprizq, interpretando la expresión como de tipo ref(T), y obteniendo una referencia a una
variable v = eval(exprizq, S) ∈ref(T)
2. Evaluar exprder,interpretandolaexpresióncomodetipo T,yobteniendounvalor x = eval(exprder, S) ∈
T3. Almacenarenlazonadememoriaasociadaalavariable velnuevovalor x
Fallosenlaejecucióndelaasignación
Laejecucióndelaasignaciónfallasisecumplealgunadeestascircunstancias:
• Noexisteningúntipo Ttalque exprizq sepuedeinterpretarcomodetiporef(T)y exprder sepueda
interpretarcomodetipo T

exprizq opasig exprder

5

2 ÓRDENESELEMENTALES

2.3 Llamadasaprocedimiento
• Fallalaevaluaciónde exprder
• Fallalaevaluaciónde exprizq
• Laevaluaciónde exprizqproduce NULL
Asignacionesmúltiples
Enalgunoslenguajessecontemplanlasasignacionesmúltiples:

expr − izq1 , expr − izq2 · · · expr − izqn
opasig expr − der1 , expr − der2 · · · expr − dern

essemejanteamultiplessentenciasdeasignación,exceptoenqueelordenenelqueseefectuanpuedeser
releveantesihayalgunavariablereferenciadatantoalaizquierdacomoladerecha(anoserqueseusen
variablestemporalesintermedias)
AsignacionesmúltiplesenPython
Estelenguajecontemplaasignacionesmúltiples,porejemplo:
x,y = 1,2
asignaelvalor 1a xyelvalor 2a y. Sihaycoincidenciasalaizquierdayladerecha,seusanvariables
intermedias,porejemplo:
x,y = y,x
intercambialosvaloresde xe y.
2.3 Llamadasaprocedimiento
Llamadasaprocedimiento
Unallamadaaprocedimientoesunaordenenlacualseincluye:
• Elnombredeunprocedimiento(subprogramaquenodevuelveunvalor).
• Unalistadeexpresiones(posiblementevacía)quesedenominanlosparámetrosactualesdelallamada
Ejecucióndellamadasaprocedimiento
Laejecucióndeunallamadaaprocedimientoconlleva:
• Laevaluacióndelosparámetrosactuales
6

3 ÓRDENESCOMPUESTAS
• Las inicialización de los parámetros formales con los valores obtenidos al evaluar los parámetros
actuales
• Laejecucióndelasórdenesqueformanelcuerpodelprocedimiento
Laejecuciónfallasifallaalgunadelasevaluacionesoejecucionescitadasenlalistaanterior.
Llamadasaprocedimiento
• Enloqueserefierealasintaxis,lasllamadasaprocedimientosonórdeneselementales.
• Desdeelpuntodevistasemántico,estasórdenessoncompuestas,pueslafuncióndetransiciónasociada
seobtieneporcomposiciónotrasfuncionesdetransición.
• Losprocedimientosseestudianconmásdetallemásadelanteeneltemario.
3 Órdenescompuestas
Órdenescompuestas
• Unaordencompuestaseconstruyecombinandovariasórdenesválidas,deacuerdocondeterminadas
reglassintácticaspropiasdecadalenguaje.
• Lasemánticadeunaordencompuestaesunaaplicaciónquedependelasaplicacionesasociadasalas
otrasórdenesqueformanlaprimera.
Clasificacióndelasórdenescompuestas
Veremoslossiguientestiposdeórdenescompuestas:
• Composicióndeórdenes
– Secuencial
– Colateral(concurrente)
• Órdenescondicionales
• Órdenesiterativas:
– Buclesindefinidos
– Buclesdefinidos
• Bloques

7

3 ÓRDENESCOMPUESTAS

3.1 ComposiciónSecuencial
3.1 ComposiciónSecuencial
Composiciónsecuencial: notación
Sean O1y O2dosórdenescualquiera,podemosescribirunanuevaorden Ocomosigue:
O = O1 ; O2
Decimosque Oeslacomposiciónsecuencialde O1y O2
Composiciónsecuencial: ejecución
Laejecución O1 ; O2sellevaacaboendospasos:
1. Seejecuta O1,siestaejecuciónfalla,tambiénfallalade O1 ; O2
2. Seejecuta O2,siestaejecuciónfalla,tambiénfallalade O1 ; O2
Semánticadelacomposiciónsecuencial
Encuantoalasemánticade O1 ; O2secumpleque:
Aquí,elsímbolo ◦denotalacomposicióndeaplicaciones,esdecir,paradosaplicaciones f y g,talesqueel
rangode f eseldominiode g,ytalque xesunelementodeldominiode f,secumpleque:

Sem[O1 ; O2] = Sem[O1] ◦ Sem[O2]

( f ◦ g)(x) = g( f (x))

Ejemplodecomposiciónsecuencial
Sean:
• O1 = x = x + 1
• O2 = x = x + 2
• O = O1 ; O2 = x = x + 1 ; x = x + 2
Entonces:

Sem[O] = Sem[x = x + 1 ; x = x + 2]

= Sem[x = x + 1] ◦ Sem[x = x + 2]
= Sem[x = x + 3]

8

3 ÓRDENESCOMPUESTAS
3.2 Composicióncolateral
Asociatividaddelacomposiciónsecuencial
Lacomposicióndeaplicacionesesasociativa,yportantotambiénloeslacomposiciónsecuencialdeórdenes:
Estaordensepuedeescribirsimplementecomo
O1 ; O2 ; O3
Lógicamente,lanotaciónquesepuedeextenderasecuencias:
O1 ; O2 ;
; On

(O1 ; O2) ; O3 ≡ O1 ; (O2 ; O3)

· · ·

· · ·

· · ·

; On
; On ;

O1 ; O2 ;
O1 ; O2 ;

ComposiciónsecuencialenlosLLPP
Enlamayoríadeloslenguajes,elsímbolo ; denotacomposiciónsecuencial,sibiensuelesernecesario
añadirlo también después de la última orden