PDF de programación - Capítulo 2. Valores y Tipos

LenguajesdeProgramación

Capítulo2.
ValoresyTipos
CarlosUreñaAlmagro
Curso2011-12

Contents
1 Introducción
2 TiposPrimitivos
.
.
.
.
.
.
2.1 TipoLógico .
.
.
.
.
.
.
2.2 Caracteres .
.
.
2.3 NaturalesyEnteros .
.
.
.
.
.
.
2.4 Reales .
.
.
.
.
2.5 Tiposenumerados
.
.
3 TiposCompuestos
.
3.1 ProductoCartesiano .
3.2 Uniónyunióndisjunta.
.
3.3 Aplicaciones .
.
.
.
.
4 Tiposrecursivos
.
.
.
.
.
.
.
.
4.1
.
Listas.
.
4.2 Árboles.
.
.
.
.
.
.
.
5 Equivalenciadetipos

.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

1

2
6
6
7
8
12
13
14
14
18
25
30
30
32
34

LP(11-12)2. ValoresyTipos
6 Elprincipiodecompletituddetipos

35

creadoOctober10,2011

página2.2/35

LP(11-12)2. ValoresyTipos
1 Introducción
ElconceptodeValor.
Unvaloresunaentidadque:
• Obtenemoscomoresultadodeevaluarunaexpresión,o
• Podamosalmacenar,o
• Incorporaraunaestructuradedatos,o
• Pasarcomoargumentoasubprogramas,o
• Obtenercomoresultadodeunafunción
ElconceptodeValor.
Endefinitiva, unvalorescualquierentidadquepuedaserprocesadadealgunamaneramediantelasin-
struccionesquecadalenguajesdeprogramaciónincorpore.
Ejemplos. ValoresenPascal(1)
• Valoresprimitivos(lógicos,caracteres,enumerados,enterosyreales)
• Valorescompuestos(registros,arrays,conjuntosyficheros)
• Punteros
Ejemplos. ValoresenPascal(2)
• Referenciasavariables(únicamentecomoparámetrosasubprogramas)
• Subprogramas(procedimientosyfunciones)
Ejemplos. ValoresenC.
• Valoresprimitivos(caracteres,enumerados,enterosyreales)
• Valorescompuestos(registros,arrays)
• Punteros
• Subprogramas(funciones)
creadoOctober10,2011

página2.3/35

LP(11-12)2. ValoresyTipos
Elconceptodetipo
Parahacermástratableelconjuntodetodoslosvaloresposiblesencadalenguaje,clasificamoslosvalores
entipos.
Enprincipio,untipoes,portanto,unconjuntodevalores.
Sinembargo,ycomoveremos,untipoesalgomás.
Elconceptodetipo
Normalmente,laagrupacióndevaloresparaformartipossehaceteniendoencuenta:
• unmodelomatemáticocomún
• laexistenciadeunconjuntocomúndeoperacionesaplicablesatodoslosvaloresdeltipo.
• la existencia de un método común para asociar una representación como secuencia de bits a cada
elementodelconjunto.
Elementosdeuntipo
Untipoesunconjuntodevalorescon:
• unmodelomatemáticoasociado(unconjunto S)
• unconjuntodeoperacionesbiendefinido,cadaunadeellasconunmodelomatemáticoasociado(una
función)
• unconjuntodealgoritmosqueoperansobrelassecuenciaseimplementanlasoperacionesanteriores.
• unafunción(matemática)derepresentaciónqueasociasecuenciasdebitsalosvaloresdelconjunto S
Representacióndevalores
Paracadatipo Aexistiráunafunciónmatemática,biunívoca,biendefinida,queasocia,acadavalorposible,
surepresentacióncomounaúnicasecuenciafinitadedígitosbinarios.
Representacióndevalores
• Alafunciónselellamará reprA,alconjuntoderepresentacionesposiblesselellamará RA
• Lafunciónesbiyectivaentre Ay RA

creadoOctober10,2011

página2.4/35

LP(11-12)2. ValoresyTipos
Representacionesambigüas
• Cadavalorde Atieneasociadounúnicovalorde RA
• Unarepresentaciónquenocumpleestoesambigua,yaqueexistiráalgúnvalorconunconjuntode
representacionesposibles.
Representacióndevalores
Valoresdistintosdebentenerrepresentacionesdistintas:
Estoimplicaqueexistelafunción repr−1
esunúnicovalorde A.
Ejemploderepresentación
Números naturales del 0 al 7: Cada uno se puede representar como una secuencia de tres bits, el más
significativoprimero.
EjemplodeRepresentación.
Númerosnaturalesdel 0al 7(A),ysuscorrespondientesrepresentaciones(RA)

A ,esdecir,quelainterpretacióndecadasecuenciadebitsen RA

x = y

=⇒ reprA(x) = reprA(y)

Númerodeelementosytamaño
Sea Aunconjuntocualquiera:
• Elnúmerodevaloresdistintosen Asenotacomo car(A)(porcardinalidad)
• Silasrepresentacionessontodasdelmismotamaño,elnúmerodebytesquetienecadarepresentación
senotacomo tam(A).
página2.5/35
creadoOctober10,2011

LP(11-12)2. ValoresyTipos
Operacionessobrelosvaloresysuimplementación
• Paracadatipo,existiráunconjuntodeoperacionesmatemáticas(funciones)biendefinidas,queactúan
sobredichosvalores.
• Cadaoperacióndefinidasobrelosvaloressecorresponde(biunívocamente)conunaoperaciónequiv-
alentedefinidasobrelasrepresentacionesdelosvalores.
EjemplodeOperación(sumar1)ysuimplementación

Ejemplodeoperación(sumar1).

f

: A → A

i → f (i) = (i + 1) mod 8

g : RA → RA

(a, b, c) → g(a, b, c) = (a, b, c)

a = a xor (b and c)
b = b xor c
c = no(c)

donde:

Implementaciónválida
creadoOctober10,2011

página2.6/35

f : A → A

g

una

reprA( f (x)) = g(reprA(x))

LP(11-12)2. ValoresyTipos
Dadaunaoperación
imple-
será
cualquiera,
mentación válida de f, si y solo si
paratodovalor xen Asecumpleque:
Clasificacióndelostipos
• Tiposprimitivos: lógicos,caracteres,naturalesyenteros,reales,tiposenumerados
• Tiposcompuestos: productocartesiano,unión,aplicaciones,conjuntosdepartes
• Tiposrecursivos
Descriptoresdetipo
• Undescriptordetipoesunafrase(untrozodetexto)dellenguajequedescribeuntipodedatos
• Haydescriptoresdeunasolapalabra(tipossimples)hastadescriptoresdecientosomilesdelíneas
(porejemplo,ladefinicióndeclases)
2 TiposPrimitivos
TiposPrimitivos
• Sonlostiposmássimples,enelsentidoquecontienenvaloresquenosepuedendescomponer
• Loanteriorimplicaquecadavalordeunodeestostiposestratadocomountodo,nosepuedeacceder
aunadesuspartesindependientementedelasotras.
2.1 TipoLógico
TipoLógico
• Eselmássencillodelostipossimples.
• Eseltipoformadoporlosdosvalorestrueyfalse
creadoOctober10,2011

página2.7/35

LP(11-12)2. ValoresyTipos
• Elconjuntoestádotadodelasoperadoreslógicosand,or,not
• Presenteenlamayoríadeloslenguajes(Pascal,Ada,C++,Java,C#,python)
RepresentaciónambiguadevaloreslógicosenC
• EllenguajeCnocontemplaestetipo
• EsusualenCelrecurriraotrostipos(enteros),pararepresentarlosvaloreslógicos.
• Larepresentaciónbasadaenenterosesambigua,locualhacefácilcometererrores.
RepresentaciónambiguadevaloreslógicosenC
Existevaloresquenosonnitruenifalse.
typedef
const
const
logico a = 5 ;
....
( a != true )
if
printf("a es
false");
Eltipológicoenvarioslenguajes:

int
logico true = 1 ;
logico false = 0 ;

logico ;

Leng.
Ada
C++
Java
C#
Python

Nombre
Valores
Boolean True, False
true, false
boolean true, false
true, false
bool
True, False

bool

bool

2.2 Caracteres
Caracteres
• Losvaloresdeestetiposonelconjuntodecaracteresimprimiblesenpantalla,impresora,ocualquier
dispositivodesalida.
creadoOctober10,2011
página2.8/35

LP(11-12)2. ValoresyTipos
• UsualmenteserecurrealcódigoASCII,quedefineunconjuntode128caracteresbásicos,ysuforma
derepresentarlosen1byte. LoslenguajesAda,Pascal,CusanelcódigoASCII
CódigosASCIIyUnicode
• ElcódigoASCIIestalimitado: solocontienecaracteresoccidentales. Además,hay128códigos(del
128al255)convariasinterpretacionesposibles,segúnelcontexto.
• Loslenguajesmodernos(Java,C#)recurrenalarepresentaciónporelestándarUNICODE,de2bytes
porcarácter,yconcaracteresarábigos,chinos,cirílicos,etc..
Eltipocarácterenvarioslenguajes

Leng. Nombre
Ada
C++ char
Java
C#

char
char

Character

(enpythonnoexisteestetipo)
2.3 NaturalesyEnteros
NaturalesyEnteros
• Estostipossonsubconjuntosfinitosdelosenterosynaturales.
• Estossubconjuntoscontienenrangosdevaloresconsecutivos,normalmenteincluyendoalcero.
• Larepresentaciónsuelesersimplementeenbinario(naturales)oencomplementoados(enteros).
Longitudpredeterminada
• Algunoslenguajesfijanlalongitud(enbits)delarepresentacióndeestostipos
• Seprimaantetodolaportabilidad,sepierdeeficiencia.
Longitudpredeterminada
En estos lenguajes, los rangos de valores de los tipos de datos enteros son conocidos a priori y fijos,
determinadosenlaespecificacióndellenguaje.
creadoOctober10,2011
página2.9/35

LP(11-12)2. ValoresyTipos
Longituddependientedelaimplementación
• Otros lenguajes no predeterminan la longitud de la representación (se permite que dependa de la
implementación,S.O.,hardware,etc?)
• Sepermitemejorarlaeficiencia,acostademáscomplicadolograrportabilidad.
Longituddependientedelaimplementación
Enestoscasos,paralograrportabilidaddebendeexistirconstruccionesdellenguajequepermitenaveriguar
elrangodevaloresasociadoacadatipo.
(normalmenteestoocurreentiempodecompilación)
Longitudyformatodelarepresentación:
• LoslenguajesAda,CyC++nofijanlalongitud(aunqueseestablecenalgunasrestricciones)
• Loslenguajesmodernos(JavayC#)fijanlalongitud.
TiposenterosenC/C++
Nombre
R.mín.
R.(C)
SCHAR_MIN- SCHAR_MAX (−27, 27)
[signed] short [int] SHRT_MIN- SHRT_MAX
INT_MIN- INT_MAX
LONG_MIN- LONG_MAX
• Elnúmerodebitsdelarepresentacióndebesernodecreciente
• Elrangodevaloresdebeconteneralrangomínimoindicado
TiposnaturalesenC/C++

[signed] int
[signed] long [int]

(−215, 215)
(−215, 215)
(−231, 231)

signed char

página2.10/35

unsigned char

R.(C)
R.mín.
Nombre
0- UCHAR_MAX [0, 28)
unsigned short [int] 0- USHRT_MAX [0, 216)
0- UINT_MAX
0- ULONG_MAX [0, 231)
• Elnúmerodebitsdelarepresentacióndebesernodecreciente
• Elrangodevaloresdebeconteneralrangomínimoindicado
creadoOctober10,2011

unsigned [int]
unsigned long [int]

[0, 216)

LP(11-12)2. ValoresyTipos
TiposenterosynaturalesenC/C++
• char puede ser equivalente a unsigned char o a signed char, dependiendo de la imple-
mentación
• Elvalormínimoymáximoindicadosonconstantesdefinidasen limits.h.
• EnC++,sepuedeaccedermediantefuncionesalosvaloresmínimoymáximo:
– std::