Download APUNTES FUNDAMENTOS DE PROGRAMACIÓN

APUNTES
FUNDAMENTOS DE PROGRAMACIÓN
Primera parte
Grado en Ingeniería en Sistemas de Telecomunicación
Grado en Ingeniería Telemática
Área LSI
Curso 2010-2011
Índice
i
Índice
Introducción
1
Computadores y lenguajes de programación
5
Abstracción de datos
31
Abstracción de control
59
Estructuras estáticas de datos. Arrays.
81
Abstracción Funcional. Métodos.
99
Introducción
Introducción
1
Para empezar: lo que tienen entre manos no es un libro, sino unos apuntes, que transcriben,
completándolo ligeramente, el discurso de las clases teóricas de la asignatura. Escribir un libro es
una tarea abrumadora, sujeta a críticas no siempre constructivas y frecuentemente poco
agradecida. Por consiguiente está reservada a los más valientes y generosos. En los apuntes no se
cuenta nada que no esté contado en los libros, ni se cuenta mejor que en ellos. ¿Por qué entonces
unos apuntes y no un libro? En primer lugar, aunque hay excelentes libros de programación, la
mayor parte de ellos o no se adaptan al temario de la asignatura o no se adaptan a la forma elegida
para impartirla. En segundo lugar, cada libro trata a su manera los diferentes temas, siendo unos
más apropiados que otros para abordar según que parte de la asignatura. En cursos anteriores, bien
al principio del curso o bien cada vez que se impartía un tema, se facilitaban las referencias
bibliográficas más adecuadas para estudiarlo. Por supuesto, se va a seguir haciendo, porque es muy
conveniente y formativo que los alumnos consulten referencias bibliográficas. Sin embargo, la
experiencia demuestra que, salvo excepciones, de la forma en que se facilitaban tales referencias,
los alumnos no las consultaban en absoluto. No es algo sorprendente, habituados como están a un
libro de texto, el manejo de diferentes fuentes para estudiar una asignatura supone una dificultad
añadida, una piedra más en el camino. Los alumnos carecen todavía del entrenamiento necesario
para asimilar informaciones que explican lo mismo, pero desde diferentes puntos de vista, y para
discriminar lo que es esencial para aprobar la asignatura de lo que no lo es. Los alumnos (y el
profesor) prefieren un libro, pero puesto que aún no hemos encontrado ese libro se han facilitado
unos apuntes que explican de forma coherente toda la asignatura y que, ayudados en ocasiones por
referencias bibliográficas muy concretas, sirven para estudiarla de principio a fin. A falta de pan…
Los apuntes son, como ya se ha dicho, una transcripción de las clases de teoría y están
confeccionados a partir de las referencias bibliográficas utilizadas para preparar las clases. A veces
son transcripciones literales o resumidas de los párrafos de un libro. Cuando esto es así se informa
al alumno de la fuente o fuentes principales, para que pueda acudir a ellas si los apuntes no le
satisfacen. En clase se dirá cuando es conveniente acudir a las fuentes porque los apuntes no
alcancen el nivel suficiente. A veces, para introducir un tema hay que adelantar un poco de lo que
hay en otros temas posteriores. En un lenguaje de programación todos los elementos están muy
interrelacionados, los conceptos se van apoyando unos en otros y las distintas facetas del
conocimiento se van construyendo en paralelo adquiriendo todo su sentido cuando se ensamblan
entre sí. Pero como todo no puede explicarse al mismo tiempo, el que explica debe contenerse y el
que escucha debe tener paciencia.
Otro aspecto del que deben estar advertidos es que al principio la Programación se hace bastante
difícil a la mayoría de los alumnos. No es que sea más complicada o más abstracta que las
Matemáticas o la Física, de hecho es bastante más concreta y sencilla, pero al contrario que éstas es
una novedad. Para animarles, me permito incluirles el siguiente párrafo, que, siendo fiel al espíritu
de los apuntes, no es una aportación original, sino que está tomado literalmente de “Informática
Aplicada. Programación en Lenguaje C”. Este libro está disponible en la biblioteca digital de la UPCT.
El párrafo dice así:
Hay una recomendación clásica, que los profesores de programación repetimos
frecuentemente a los alumnos: en el aprendizaje de un lenguaje de programación hay que
programar: oír permite olvidar; estudiar permite entender; sólo programar permite
aprender. No basta con ir a clase. No basta con estudiar este ladrillo. Hay que instalar un
compilador y un editor de programas y ponerse delante de la pantalla. Y programar.
El aprendizaje de la programación es una tarea inicialmente ingrata. Las horas de trabajo y
estudio no parecen cundir. A una hora se sucede otra, en la que el aprendiz no entiende
apenas sobre qué se le está instruyendo. Y otra hora…, y otra…, y otra… Y uno se enfrenta al
primer programa —una auténtica simpleza—y no logra más que una colección de 26 errores.
Introducción
2
¡Veintiséis!: ¡en tan sólo cinco líneas de código! Hay que seguir. Y detectar el punto y coma que
falta en esa línea; y el paréntesis que en realidad debía ser una llave; y la biblioteca que no sé
bien para qué sirve y que para colmo el compilador no me la reconoce, porque la he
deletreado mal; y mil pedradas más que animan a cualquier cosa menos a seguir trabajando
con el dichoso lenguaje C 1. Todos hemos tenido que aprender a programar. Para todos, esos
primeros pasos han sido una personal pesadilla.
Cada año, en el primer con los nuevos alumnos, dibujo en la pizarra del aula una gráfica que
muestra el rendimiento del estudio de un lenguaje de programación. Es una curva a la que le
cuesta levantarse del eje de las abscisas. Muestra, en su primera fase, una desesperante
pendiente casi nula. Pero, en un entorno de valores determinado, distinto para cada
estudiante, esa gráfica sufre un cambio de pendiente. Casi de forma súbita: estudio y no
comprendo… estudio y no comprendo… estudio y… ¡ah!, ¡ahora lo veo!: un pequeño avance. Y
con el paso de las horas, de repente se clarifican un bloque de conceptos, casi de golpe. Y el
estudio cambia de cariz: el aprendiz se pica con la programación. Ha llegado el momento de
avanzar a buen ritmo. Se disfruta aprendiendo, porque se logran cosas nuevas, cada vez más
difíciles. Y se aprende a programar. Se caza el modo en que se deben plantear las cosas al
ordenador. Se coge la filosofía de cómo se construyen los programas. A uno se le ocurren
nuevos retos, y se atreve a intentar buscar una solución. Y se aprende entonces a programar.
Y, por supuesto, se aprueba la asignatura.
Lo que he contado en estas líneas previas es estadísticamente cierto. Porque el que no llega a
franquear el tiempo de estudio de inflexión, se queda en nada. Y el que lo supera, con poco
esfuerzo alcanza un buen nivel. Que programar no es difícil; pero el inicio es la más difícil de
las fases en su aprendizaje.
Fácil o difícil, deben ser conscientes de que aprender a programar requiere tiempo y esfuerzo. Para
realizar programas es necesario comprender los conceptos teóricos de la asignatura. Ciertamente,
la teoría y la práctica se realimentan entre sí: para aplicar un concepto hay que comprenderlo y
para comprenderlo casi siempre es necesario aplicarlo. Pero el alumno debe tener claro que su
proceso de aprendizaje comienza en el estudio de la teoría y termina en la comprensión de la teoría.
Es una base teórica sólida la que permite afrontar problemas diferentes y elegir en cada caso dónde,
cuándo y cómo aplicar las técnicas de programación que se presentan en el curso. Lo demás son
recetarios. Las prácticas y los problemas son necesarios para entender la teoría (“vi y recordé, hice y
comprendí”), pero el alumno debe estudiar la teoría y reflexionar sobre ella antes de aplicarla. Las
1
También vale para Java, pero hay que reconocer que C puede ser mucho más frustrante.
Introducción
3
prácticas y los problemas le permitirán después poner a prueba su conocimiento, revelarán
aspectos importantes no considerados en un primer estudio, pondrán en evidencia
interpretaciones equivocadas y suscitarán dudas que deberá consultar al profesor. Muchas veces,
los problemas con los que más se aprende son los que no han llegado a resolverse, pero han servido
para probar diferentes alternativas y para razonar sobre el uso y significado de los conceptos. El
aprendizaje requiere también reiteración: volver a aplicar una y otra vez los mismos principios, las
mismas técnicas, sobre problemas en apariencia muy diferentes. Prácticas y problemas ofrecen el
marco donde dicha reiteración es posible. Por último, tengan presente que el profesor puede
ayudarles a comprender, pero no puede liberarles de su obligación de estudiar, razonar y
preguntar.
Cartagena, 10 de septiembre de 2010
Tema 1: Computadores y lenguajes de programación.
Tema 1: Computadores
programación.
y lenguajes
5
de
Objetivos
Situar a la asignatura en el contexto de las tecnologías de la información y las comunicaciones.
Proporcionar conocimientos básicos sobre la informática, los sistemas informáticos, y los sistemas
operativos.
Introducir el concepto de programa, los lenguajes de programación y las herramientas para editar,
compilar, depurar y ejecutar programas.
Contenidos
Estructura y funcionamiento de un computador.
Lenguaje máquina y ensamblador.
Lenguajes de programación de alto nivel.
Paradigmas de programación.
Sistemas operativos.
Anexo: codificación de números enteros.
Tema 1: Computadores y lenguajes de programación.
¿Qué es programar?
6
El objetivo de la asignatura Fundamentos de Programación 1 es “transmitir conocimientos básicos
sobre el uso y programación de los ordenadores, sistemas operativos, bases de datos y programas
informáticos con aplicación en ingeniería”. La asignatura se centra casi en su totalidad en la
programación, puesto que el uso de los sistemas informáticos se aborda fundamentalmente desde la
perspectiva del programador. De hecho, se trata de que, al final del curso, el alumno conozca las
técnicas básicas de la programación para desarrollar programas correctos tanto desde el punto de
vista computacional como desde el punto de vista de su mantenimiento y uso. Esto implica conocer
y saber utilizar un lenguaje de programación concreto, siendo Java el lenguaje elegido.
El objetivo de la asignatura invita a comenzar esta introducción respondiendo a la pregunta ¿Qué es
programar? Ahí va una primera respuesta:
“Programar es decirle a un computador lo que tiene que hacer. “
Esta respuesta es tal vez demasiado simple para un proceso que, como iremos viendo, puede ser
muy complejo. No debemos tomarla demasiado en serio, sino como punto de partida para plantear
otras dos preguntas:
¿Qué es y cómo funciona un computador?
¿Cómo se le dice a un computador lo que tiene que hacer?
La primera pregunta se contesta con detalle en la asignatura Fundamentos de Computadores, pero
hace falta responderla brevemente para poder abordar la respuesta de la segunda en esta
asignatura. Por esta razón la asignatura comienza describiendo la estructura interna de un
computador y su funcionamiento.
1
Competencia específica B2 del plan de estudios de los grados que se imparten en la ETSIT.
Tema 1: Computadores y lenguajes de programación.
7
Estructura y funcionamiento de un computador1
Esquema básico de un computador
Empecemos con una definición:
“Un computador es una máquina automática programable que obtiene unos datos de
salida aplicando unas operaciones básicas predefinidas en él sobre unos datos de entrada”
Para poder realizar su función un computador dispone de diversos elementos que se muestran
esquemáticamente en la figura 1.
PROCESADOR
Unidad de Tratamiento
CPU Unidad de Control
rD
RT
RF
FF
reloj
Z
SP
S
rI
r0
ALU
C
V
AR
IR
MEMORIA
M
Lógica de
control
PC
Periférico
Entrada
Periférico
Salida
DR
Bus de direcciones
Bus de datos
Bus de control
Figura 1: Esquema básico de un computador
La figura 1 representa el esquema básico de la arquitectura típica de un computador. El elemento
principal es el procesador (CPU: Central Processing Unit) que a su vez se compone de una unidad de
tratamiento y una unidad de control. Además del procesador, el computador consta de memoria
interna, de diferentes tipos de buses (de datos, de direcciones y de control) y de elementos
periféricos.
La unidad de tratamiento (o camino de datos) está formada por la unidad aritmético-lógica (ALU:
Arithmetic and Logic Unit) y otros elementos auxiliares por donde se transmiten o almacenan
temporalmente los operandos de las operaciones aritméticas y lógicas. Suele contener un banco de
registros de propósito general (RF en figura 1) donde se almacenan los datos y resultados parciales
reduciéndose de esta manera los accesos a la memoria principal, que son siempre más lentos. La
longitud de estos registros suele ser la de una palabra de memoria o un múltiplo de ésta. Del
esquema de la figura 1 se puede deducir que la ALU opera con el contenido de uno de los registros
de RF y el contenido del registro RT y guarda el resultado en uno de los registros de RF. Además de
RT, en la figura 1 se representan otros dos registros con un significado especial 2:
Fuente principal [Prieto 06], capítulo 8.
En la figura 1 no se ha incluido uno de los registros más significativos de una ALU: el acumulador. Recuérdese que el
objetivo de este tema no es explicar de forma exhaustiva la arquitectura de un computador, sino preparar el terreno para
entender algunos conceptos que aparecen en temas posteriores. En otras asignaturas se explican con detalle los elementos
de los computadores.
1
2
Tema 1: Computadores y lenguajes de programación.
−
−
8
AR (Address Register): Registro de direcciones: Almacena la dirección del dato o instrucción
a leer o escribir.
DR (Data Register): Registro de datos: Almacena el dato a escribir en la memoria o en
puerto de salida o la información leída de la memoria o de un puerto de entrada.
La ALU dispone además de unos biestables de condición (FF: fip-flops) que se ponen a 1 ó a 0
dependiendo de la última operación realizada en la ALU. En la figura 1 se han representado algunos
de lo más típicos:
−
−
−
−
C: acarreo: indica si el resultado implica acarreo 1.
S: signo: indica el signo del resultado.
Z: cero: indica si el resultado es cero.
V: desbordamiento: indica si ha habido desbordamiento. El resultado es demasiado grande
para guardarse en una palabra.
La memoria está dividida en posiciones (denominadas también palabras de memoria) de un
determinado número de bits en las que se almacena la información. La entrada y salida de datos
puede hacerse a través de un único bus de datos bidireccional como en la figura 1 o a través de
buses de datos separados para la entrada y para la salida. Si la palabra de memoria tiene n bits los
buses de datos tendrán también n bits de forma que puedan leerse o escribirse en una sola
operación todos los bits de una posición de memoria. Además, la memoria dispone también de un
bus de direcciones de m bits, pudiendo direccionar 2m posiciones de memoria distintas. Como se ve,
el tamaño de la palabra determina el tamaño del bus de datos y el número de posiciones de
memoria el tamaño del bus de direcciones. También puede hacerse la interpretación inversa: la
capacidad máxima de la memoria viene determinada por el tamaño del bus de direcciones.
Capacidad
palabras =
bytes
Aunque los accesos a la memoria principal para leer o escribir una palabra son bastantes rápidos
(del orden de decenas de nanosegundos), son bastante más lentos que las operaciones que la ALU o
la unidad de control pueden realizar sobre el contenido de esa palabra (del orden de los
nanosegundos), por lo que estas unidades se ven frenadas muy considerablemente cuando tienen
que captar o escribir una palabra de memoria. Para paliar esto se utilizan los registros internos de
la ALU a pequeña escala y a mayor escala la memoria caché. La caché (no representada en la figura
1) es una memoria intermedia entre la memoria principal y la CPU unas 10 veces más rápida que la
memoria principal, pero mucho más cara y con unos consumos de energía mucho mayores. Por
estas razones la capacidad de la caché suele ser mucho menor que la de la memoria principal y se
usa para mantener las palabras más comúnmente usadas por la ALU y la unidad de control. Decidir
cuáles son estas palabras es un problema difícil de resolver de forma completamente satisfactoria y
cuyo estudio queda fuera del alcance de esta asignatura 2.
La unidad de control contiene la lógica de control, que está constituida por los circuitos que
decodifican las instrucciones para el computador (instrucciones máquina) y generan las distintas
señales de control para el resto de elementos del computador. La unidad de control dispone de un
reloj, que es un generador de pulsos, con los que se sincronizan todas las microoperaciones
implicadas en la ejecución de las distintas instrucciones máquina. Asimismo, en la unidad de control
vamos a encontrar siempre tres registros muy significativos:
−
−
1
2
IR (Instruction Register): Registro de instrucción. El IR almacena la instrucción que la
unidad de control está en ese momento interpretando o ejecutando.
PC (Program Counter): Contador de programa. El PC contiene la dirección en memoria
donde se encuentra la siguiente instrucción a ejecutar. Cuando termina de ejecutarse una
Acuérdense de cómo sumaban de pequeños. Por ejemplo: ocho más tres once y me llevo una… Esa una es el acarreo.
Se estudia en el contexto de los sistemas operativos.
Tema 1: Computadores y lenguajes de programación.
−
9
instrucción se carga en IR el contenido de la celda indicada en el PC y el PC cambia de valor
para indicar cuál será la nueva siguiente instrucción.
SP (Stack Pointer): Puntero de pila. El SP está relacionado con la gestión de las llamadas a
subrutinas y los retornos al punto de llamada 1.
La presentación de la unidad de control con su lógica de control, su reloj y sus registros especiales
nos permite abordar brevemente la ejecución de las instrucciones. El proceso, para el procesador
descrito en la figura 1, es en términos generales 2 como se explica a continuación:
Para iniciar la ejecución de un programa se almacena en el PC la dirección de memoria donde
comienza dicho programa.
−
Se transfiere el contenido del contador de programa al registro de direcciones. Lo
expresaremos así 3:
AR
−
−
← PC.
La unidad de control da orden de leer la instrucción almacenada en el AR
Pasado el tiempo de acceso a memoria la instrucción estará disponible en el bus datos y se
cargará en el registro de datos:
DR ← M(AR)
−
Posteriormente la instrucción se pasa al registro de instrucción:
IR ← DR
−
Y se incrementa el contador de programa para apuntar a la siguiente instrucción
PC ← PC + 1
Una vez que la instrucción se encuentra en el IR la unidad de control la decodifica y ejecuta. Si, por
ejemplo, la instrucción es: sumar el contenido de dos registros con un dato y dejar el resultado en
otro, la UC genera las señales de control para llevar el primer operando a RT , el otro a la entrada de
la ALU, realizar la suma y llevar el resultado al registro indicado.
Después de ejecutada la instrucción la unidad de control vuelve a repetir el ciclo anterior, es decir
capta una nueva instrucción, la lleva al IR y después la decodifica y ejecuta y así hasta que el
programa termina. Todas las instrucciones comienzan siempre con una fase de captación de la
instrucción y continúan con una fase de ejecución. El tipo de operaciones indicadas anteriormente
(carga de registros: AR ← PC, IR ← DR; lectura de memoria DR ← M(AR); incremento del contador
de programa PC ← PC + 1, y otras por el estilo) reciben el nombre de micro-operaciones o
microinstrucciones. Cada instrucción máquina implica la realización de un conjunto determinado
de micro-operaciones sincronizadas por las señales del reloj interno de la unidad de control.
Ejecución de un programa
Una vez que conocemos los componentes básicos de un computador estamos preparados para
entender su funcionamiento interno. Supongamos que tenemos un programa escrito en lenguaje
El SP es un elemento clave para la ejecución de programas, pero es pronto para explicar su funcionamiento. Cuando se
describan las subrutinas la función de este registro se hará evidente sin necesidad de grandes explicaciones.
2 Los detalles cambian de una máquina a otra y la figura 1 es tan esquemática que podría utilizarse para explicar secuencias
de funcionamiento un poco distintas a la elegida. Lo interesante es descubrir la lógica de la secuencia de funcionamiento y
hasta que punto pueden cambiar los detalles si cambia algún elemento de la arquitectura (p.e.: buses separados para entrada
y salida y para datos e instrucciones, segmentación de la unidad de control, longitud de la instrucción, etc.).
3 Diferentes autores utilizan diferentes convenciones para expresar la transferencia de información entre registros. La que
se emplea aquí es bastante común.
1
Tema 1: Computadores y lenguajes de programación.
10
máquina. Para simplificar supondremos que las instrucciones y datos son secuencias de ceros y
unos del tamaño de la palabra de memoria.
Lo primero que hay que hacer con el programa es cargarlo en memoria 1. Una vez cargado el
programa, se carga en el PC la dirección de su primera instrucción (podemos suponer que las
instrucciones del programa ocupan posiciones de memoria consecutivas). A partir de ese momento
la unidad de control repite sucesivamente las dos siguientes fases:
−
−
−
Fase de captación de instrucción: lleva la instrucción que está en la posición de memoria
almacenada en el PC de la memoria al registro IR e incrementa en 1 el PC.
Fase de ejecución de la instrucción: la unidad de control interpreta el código de la
instrucción y ejecuta las micro-operaciones correspondientes.
Ciertas instrucciones (instrucciones de salto y bifurcación y llamadas a subrutinas) pueden
alterar el orden secuencial del programa e implican saltar a una posición de memoria m. En
dicho caso se cambia el contenido del PC por el valor m, de forma que en la siguiente fase
de captación se ejecuta la instrucción que está en m.
Supongamos un lenguaje máquina con las siguientes instrucciones:
−
−
−
−
Entrada de información desde un dispositivo de entrada, IPv, a un registro, rx.
Código de la instrucción: 0100
Representación: IN rx, IPv
Salida de información desde un registro, rx, a un dispositivo de salida, OPv.
Código de la instrucción: 0101
Representación: OUT OPv, rx
Suma en la ALU de los registros ra y rd y ubica el resultado en rs.
Código de la instrucción: 0110
Representación: ADDS rs, ra, rd
Finalización del programa y espera de otra tarea.
Código de la instrucción: 1111
Representación: HALT
Con este repertorio de instrucciones se desea hacer un programa que sume dos números.
Supondremos que los números se introducen desde el teclado, dispositivo de entrada IP2, y que la
pantalla es el dispositivo de salida OP2. El programa resultante sería el mostrado en la tabla 1:
Tabla 1: Ejemplo de programa en código máquina.
Acciones
Instrucción máquina
Representación en
ensamblador
Introducir a través de teclado (IP2) el
primer dato y llevarlo al registro r0
0100 0000 0000 0010
IN r0, IP02
Idem segundo dato y llevarlo a r1.
0100 0001 0000 0010
IN r1, IP02
Sumar en la ALU los contenidos de los
registros r0 y r1 y llevar el resultado a
r3
0110 0011 0000 0001
ADDS r3, r0, r1
Sacar por la pantalla (OP2) el resultado,
que está en r3.
0101 0011 0000 0010
OUT OP2, r3
Fin del programa. Detención del
computador
1111 0000 0000 0000
HALT
Esta función la realiza el sistema operativo. Más adelante se darán algunas nociones sobre los sistemas operativos. De
momento confórmense con saber que es un programa o conjunto de programas que gestionan el software de un
computador.
1
Tema 1: Computadores y lenguajes de programación.
Instrucciones de control de flujo
11
Para acabar nuestro pequeño tour por la arquitectura de los computadores vamos a abordar un
último asunto. Hay dos tipos de instrucciones que provocan que se cambie el valor del contador de
programa alterando el orden secuencial de la ejecución del programa:
−
−
Bifurcaciones (o saltos condicionales) y saltos incondicionales.
Llamadas a subrutinas y retornos de las mismas.
Bifurcaciones y saltos.
Con estas instrucciones se puede alterar el orden de ejecución de un programa haciendo que el
contador de programa contenga la dirección de cualquier instrucción. El valor de esta dirección se
especifica en la propia instrucción de salto (direccionamiento directo) o en algún registro o
posición de memoria (direccionamiento indirecto).
−
Salto incondicional: Supóngase, por ejemplo, que en las posiciones de memoria 1A30 se tuviese
la instrucción de salto BR 32B7 (branch to 32B7) que significa saltar a la posición 32B7. La
ejecución de este tipo de instrucciones implica simplemente cambiar el contenido del contador
de programa por el valor indicado en la instrucción, en nuestro caso:
PC ← 32B7
−
Salto condicional: En las instrucciones de salto condicional, el salto sólo se produce si se cumple
una condición establecida por el valor de algún biestable o registro. Por ejemplo, la instrucción
BZ 32B7 (branch to 32B7 if Z=1) carga 32B7 en el contador de programa sólo si el valor del
biestable Z es uno).
Instrucciones de control de flujo que hacen referencia a subrutinas.
Una llamada a subrutina (también denominada rutina, subprograma o procedimiento) es una
ruptura de la secuencia normal de ejecución de las instrucciones de un programa de forma que tras
la ejecución de la instrucción de llamada se ejecuta otro programa, denominado subrutina. Una vez
ejecutada la subrutina se retorna, mediante la ejecución de una instrucción de retorno, al programa
desde el que se hizo la llamada. A su vez, una subrutina puede contener llamadas a otras subrutinas
y así sucesivamente.
Desde el punto de vista de la arquitectura del computador, la diferencia entre un salto y una
llamada a subrutina es que cuando una subrutina acaba debe retornarse al programa o subrutina
que llamó, concretamente a la instrucción inmediatamente posterior a la llamada. Esa instrucción
se encuentra en el PC y debe guardarse para ser utilizada en el momento oportuno. El
almacenamiento de las direcciones de retorno se realiza en una zona de memoria especial llamada
pila (stack). La pila funciona de tal manera que el último elemento en entrar es el primero en salir
(Estructura LIFO: Last in, First out). En la figura 2 pueden verse tres llamadas sucesivas a
subrutinas. Obsérvese que la recuperación de las direcciones se realiza en orden inverso a su
almacenamiento, lo que explica la utilización de una estructura LIFO para el mismo. Lo único que
debe hacer la unidad de control para producir un retorno es transferir la dirección almacenada en
la cabecera de la pila (dirección de retorno) al PC.
En algunos computadores la pila se implementa con circuitos específicos (pila hardware) lo cual
incrementa enormemente la velocidad de acceso. En la mayoría, la pila se gestiona en una zona de
la memoria principal y el procesador dispone de un registro específico llamado puntero de pila o SP
(stack pointer) que apunta a la cabecera de la pila, donde está almacenada la dirección de retorno.
Tema 1: Computadores y lenguajes de programación.
07CD
07CE
…
107A
107B
…
12
PC
10A3
PC
7CD9
PC
003C
Pila
107B
…
…
Pila
6FAC
107B
…
…
Pila
AB36
6FAC
107B
…
…
1
…
CALL 10A3
10A3
…
…
6FAB
6FAC
…
6FFF
2
…
CALL 7CD9
RET
6
2FFF
7CD9
…
…
AB35
AB36
…
AC55
3
…
CALL 003C
RET
4
5
PC
107B
PC
6FAC
PC
AB36
Pila
…
…
…
Pila
107B
…
…
Pila
6FAC
107B
…
…
Figura 2: Gestión de llamadas (CALL) y retornos (RET).
003C
…
…
…
05AC
RET
Tema 1: Computadores y lenguajes de programación.
13
Lenguajes máquina y ensamblador 1
Instrucciones máquina.
Comenzábamos esta lección con una definición y dos preguntas. La definición era:
“Programar es decirle a un computador lo que tiene que hacer. “
Y las preguntas:
¿Qué es y cómo funciona un computador?
¿Cómo se le dice a un computador lo que tiene que hacer?
La respuesta que hemos dado en la sección anterior a la primera pregunta nos permite empezar a
contestar la segunda. Lo que se le puede decir a un computador viene definido por sus repertorio de
instrucciones máquina. Estas instrucciones se pueden clasificar en cuatro grupos:
−
−
−
−
Instrucciones de transferencia de información.
Instrucciones de transferencia de control (saltos condicionales, bifurcaciones, llamadas
a subrutina y retornos).
Instrucciones aritmético-lógicas.
Misceláneas.
Las instrucciones se estructuran en campos, uno de los cuales identifica el código de operación, el
resto permite identificar a los operandos de forma directa o indirecta. Dependiendo del
computador, puede ser que en una instrucción se expliciten uno o más operandos, cada uno de los
cuales, como veremos en breve, puede direccionarse de una forma distinta. Los formatos de las
instrucciones máquina varían enormemente de unos computadores a otros. Por ejemplo:
Instrucciones de un procesador RISC.
Formato muy regular:
Sólo tres tipos de instrucciones.
Todas las instrucciones de 32 bits
rd ← rs op rt
shamt: número de desplazamientos.
func: extensión de codop.
Repertorio de instrucciones IA-32
para el Pentium 4.
Gran variedad de tamaños, desde 1 a 12
bytes.
Todas las instrucciones tienen codop,
pero la presencia y longitud del resto de
los campos depende del tipo de
instrucción
31
25
codop
rs
20
31
25
codop
rs
20
rt
rt
15
rd
10
shamt
5
func
15
Dirección o dato inmediato
31
25
codop
Dirección
codop
1 ó 2 bytes
dirección
1 ó 2 bytes
0
0
0
desplazam.
1 ó 2 bytes
valor
1 ó 2 bytes
Las instrucciones máquina suponen ya un primer nivel de abstracción, si bien muy pequeño: un
computador queda definido y descrito por su repertorio de instrucciones máquina. Estas
instrucciones permiten decirle al computador lo que tiene que hacer sin necesidad de conocerlo a
nivel de micro-máquina (microoperaciones).
1
Fuente: Introducción a la Informática, capítulo 8.
Tema 1: Computadores y lenguajes de programación.
14
Lenguaje ensamblador
La figura 3 resume el repertorio de instrucciones del computador didáctico CODE-2 1. Por supuesto
no hay que aprenderlo, la figura sólo trata de dar una idea de las instrucciones habituales en un
repertorio de instrucciones máquina e introducir una nueva forma de programar muy cercana a las
instrucciones máquina y sin embargo mucho más cómoda: el lenguaje ensamblador.
Representación en lenguaje ensamblador
de las instrucciones máquina
Figura 3: Lenguaje ensamblador
El lenguaje ensamblador es la representación simbólica de la codificación binaria del repertorio de
instrucciones máquina de un procesador. El uso de referencias simbólicas es una característica
básica del lenguaje ensamblador, que evita trabajar con la codificación binaria de las instrucciones
sustituyéndola por un nemónico. Un nemónico es un dato simbólico que identifica a un comando
generalmente numérico (binario, octal, hexadecimal) de una forma más sencilla que su numeración
original, facilitando enormemente el uso y la memorización de este comando para el programador.
Por ejemplo 2, un procesador x86 puede ejecutar la siguiente instrucción binaria como se expresa en
código de máquina:
Binario: 10110000 01100001 (Hexadecimal: 0xb061)
La representación equivalente en lenguaje ensamblador es más fácil de recordar:
MOV al, 061h
1
2
Descrito en “Introducción a la Informática”, capítulo 8.
Tomado de http://es.wikipedia.org/wiki/Lenguaje_ensamblador
Tema 1: Computadores y lenguajes de programación.
Esta instrucción significa: asigna el valor hexadecimal 61 (97 decimal) al registro "al".
15
El nemónico "MOV" es un código de operación u "opcode", elegido por los diseñadores de la
colección de instrucciones para abreviar "move" (mover, pero en el sentido de copiar valores de un
sitio a otro). El opcode es seguido por una lista de argumentos o parámetros, completando una
instrucción de ensamblador típica.
La palabra ensamblador tiene dos significados. Por un lado hace referencia al lenguaje ensamblador
y por otro a un programa ensamblador que realiza la interpretación del código escrito en lenguaje
ensamblador y genera el código máquina adecuado. Usualmente hay una correspondencia 1 a 1
entre las instrucciones simples del lenguaje ensamblador y el lenguaje de máquina. Sin embargo, en
algunos casos, un lenguaje ensamblador puede proveer pseudo-instrucciones que se expanden en
un código de máquina más extenso.
El lenguaje ensamblador supone un segundo nivel de abstracción. En este caso lo que se está
abstrayendo es el repertorio de instrucciones máquina. El lenguaje ensamblador permite decirle al
computador lo que tiene que hacer sin necesidad de conocer como se codifican sus instrucciones
máquina. La tabla 2 establece una comparación entre las características del lenguaje máquina y del
lenguaje ensamblador, en la que pueden apreciarse los beneficios aportados por este último. Aun
así, el lenguaje ensamblador está muy cercano al lenguaje máquina y es específico de un procesador
determinado. La complejidad de los programas en ensamblador aunque menor que la de los
programas escritos en código máquina sigue siendo exasperante 1. Véase el programa de la figura 4,
que realiza la enorme tarea de cambiar los puntos y coma por comas en una cadena de caracteres.
Tabla 2: Características lenguaje máquina y lenguaje ensamblador
Lenguaje máquina
Lenguaje ensamblador
Los datos se utilizan por medio de las direcciones
de memoria donde se encuentran.
Utilizan direcciones simbólicas de memoria en
lugar de direcciones binarias. Los datos pueden
recibir un nombre, ya que existen sentencias
declarativas que establecen correspondencias
entre direcciones simbólicas y direcciones binarias.
Las instrucciones son cadenas de ceros y unos.
Las instrucciones realizan operaciones muy
simples. Por ejemplo: algunos computadores no
tienen instrucciones específicas para multiplicar
o dividir.
Absolutamente ligado a un procesador. Los
programas escritos en lenguaje máquina son
intransferibles.
En un programa escrito en lenguaje máquina no
pueden incluirse comentarios que ayuden a
entenderlo.
1
Y desesperante.
Utilizan una notación simbólica o nemotécnica
Extienden las instrucciones máquina con otras de
mayor nivel (agrupaciones de instrucciones
máquina)
Ligado a un procesador. No obstante existe un
estándar notacional IEEE694
Es posible insertar comentarios. El programa
ensamblador
los
detecta
y
elimina
automáticamente, no incluyéndolos en el código
máquina.
Tema 1: Computadores y lenguajes de programación.
Modos de direccionamiento.
16
Con frecuencia en la instrucción no se dan las direcciones de memoria donde están los operandos,
sino información a partir de la cual el procesador puede obtenerlas. El significado de esta
información depende del modo de direccionamiento empleado en la instrucción.
Un modo de direccionamiento describe la forma con que el procesador determina, durante la ejecución
de una instrucción, el lugar donde se encuentra o donde se almacenará un operando o resultado o la
dirección a la que hay que saltar, en caso de una instrucción de transferencia de control.
Figura 4: Programa en ensamblador.
Los modos de direccionamiento más usuales se resumen en la tabla 3. Es interesante tener una idea
general de las diversas formas de direccionamiento para comprender, más adelante, porque ciertas
estructuras de datos de los lenguajes de programación de alto nivel (por ejemplo Java) son más
eficientes o más flexibles que otras. La implementación de cada una de estas estructuras de datos se
apoyará en el modo de direccionamiento que mejor se adapte a sus características y a su vez este
modo determinará sus propiedades en cuanto al espacio necesario para almacenar los datos y la
velocidad de acceso a los mismos.
Tema 1: Computadores y lenguajes de programación.
17
Tabla 3: Modos de direccionamiento
Direccionamiento
Significado
Implícito: El operando o su dirección se encuentran en un
registro que está implícitamente indicado en el código de
operación.
Inmediato: El operando forma parte de la propia
instrucción. Según el estándar
prefijo #.
SUB .0,#H’25
IEEE694 1,
se denota con el
Direccionamiento inmediato
32
Instrucción
codop
operando
ALU
R0 ← R0 – 25h
Directo o absoluto: La instrucción contiene la dirección de
memoria o el registro donde se encuentra el operando.
Según el IEEE694 si el direccionamiento se hace a un
registro, el número de orden va precedido por un punto (.), y
si corresponde a una posición de memoria por una barra
inclinada (/).
SUB .0,#H’25A3
A
Direccionamiento directo
32
Instrucción
codop
37
37
ALU
A
operando
R0 ← R0 – M(25A3h)
Indirecto: En la instrucción se indica el puntero o lugar
(posición de memoria o código de registro donde se
encuentra la dirección del operando. Puede ir acompañado
de una operación de incremento o decremento automático
que puede realizarse antes (pre) o después (pos) de la
captación del dato.
SUB .0,[.7]++
R1
R2
Direccionamiento indirecto
Instrucción
codop
…
A3B2
32
A3B2 operando
ALU
R0 ← R0 – M(R7), R7 ← R7 + n
Indexado: Interviene un registro especial o registro índice,
que almacena un desplazamiento. La instrucción contiene la
dirección de referencia (DIRR). La dirección efectiva (DIRF)
se obtiene sumando a DIRR el valor i contenido del registro
índice (DIRF ← DIRR + i). Este tipo de direccionamiento está
pensado para optimizar los accesos a tablas almacenadas en
memoria. Se denota como el direccionamiento indirecto pero
anteponiendo la dirección de referencia.
A
Direccionamiento indexado
Registro
índice
R3
R4
8
…
32
Instrucción
codop
A3B2
A3C0 operando
R7
+
ALU
A
SUB .0,#H’32[.7]
R0 ← R0 – M(32h + R7)
Direccionamientos relativos
Como en el caso del indexado, la dirección se obtiene
añadiendo un desplazamiento (offset) a una dirección de
referencia. Dependiendo de la ubicación de la dirección de
referencia se distingue direccionamiento relativo a base en el
que dicha dirección está contenida en un registro especial
(registro base) y direccionamiento relativo a contador de
programa en el que la dirección efectiva se obtiene sumando
al contenido del PC un desplazamiento incluido en la propia
instrucción.
Relativo a base: SUB .0,RB!.2
R0 ← R0 – M(RB + R2)
Relativo a programa: BR $9
PC ← PC + 9
Expresados en notación estándar IEEE 694. Si bien cada procesador tiene su propio lenguaje ensamblador existe un
estándar notacional.
1
R7
.7
Tema 1: Computadores y lenguajes de programación.
Lenguajes de programación de alto nivel 1
18
Nivel de abstracción de un lenguaje.
Abstraer:
1.
Separar por medio de una operación intelectual las cualidades de un objeto para considerarlas
aisladamente o para considerar el mismo objeto en su pura esencia o noción.
−
En filosofía, un acto mental en el que se aísla conceptualmente un objeto o una propiedad de un objeto.
2.
−
−
Prescindir, hacer caso omiso.
En psicología, un proceso que implica reducir los componentes fundamentales de información de un
fenómeno para conservar sus rasgos más relevantes.
En programación, la abstracción se aplica al control o a los datos. La abstracción de control es la
abstracción de las acciones e implica el uso de estructuras de selección y repetición de acciones y la
definición de subprogramas, en tanto que la abstracción de datos consiste en dotar de significado a las
secuencias de bits que manejan los computadores.
Como hemos visto, las instrucciones máquina proporcionan un nivel de abstracción: un computador
queda definido y descrito por su repertorio de instrucciones máquina. Estas instrucciones permiten
decirle al computador lo que tiene que hacer sin necesidad de conocerlo a nivel de micro-máquina
(micro-operaciones). Basta con conocer su arquitectura interna, sus registros, sus modos de
direccionamiento, etc. El lenguaje ensamblador supone un segundo nivel de abstracción que permite
decirle al computador lo que tiene que hacer sin necesidad de conocer como se codifican sus
instrucciones máquina. El lenguaje ensamblador está muy cercano al lenguaje máquina y como el
lenguaje máquina es específico de un procesador determinado. La construcción de programas
grandes y complejos exige disponer de lenguajes de programación que se alejen de la arquitectura
de los computadores y se acerquen al tipo de lenguaje que se utiliza para plantear los problemas.
Por ejemplo, si quisiéramos programar la solución a una ecuación nos gustaría usar un lenguaje de
programación en el que simplemente tuviéramos que escribir la ecuación en notación algebraica.
Para que esto sea posible los lenguajes de programación deben proporcionar mayor nivel de
abstracción.
Cuando hablamos del nivel de un lenguaje nos estamos refiriendo a su capacidad para proporcionar
abstracciones que permitan escribir programas sin necesidad de conocer la arquitectura del
computador subyacente. Un lenguaje de programación es de mayor nivel cuanto más se aleja de la
estructura del computador y más se acerca al lenguaje con el que expresamos los problemas. No
hay nada de más bajo nivel a disposición del programador que el repertorio de instrucciones
máquina. Al lenguaje máquina le sigue en nivel de abstracción el ensamblador, que sigue siendo un
lenguaje de muy bajo nivel. Lenguajes de programación como C o FORTRAN se consideran ya de
alto nivel pues proporcionan abstracciones que permiten ignorar muchas de las características del
hardware subyacente. Los lenguajes estructurados como Pascal y los orientados a objetos como
C++ o Java son lenguajes de muy alto nivel, pues proporcionan abstracciones muy flexibles que
facilitan extraordinariamente la realización de programas muy grandes y complejos sin saber
apenas nada de las características de los ordenadores donde se ejecutarán tales programas.
Hay un límite en el nivel de abstracción que puede proporcionar un lenguaje de programación. Este
límite viene dado por la necesidad de traducir los programas escritos en dicho lenguaje a
programas equivalentes en lenguaje máquina. Esta traducción es necesaria porque el único
lenguaje que entiende un computador es su lenguaje máquina. Traducir un programa escrito en
ensamblador es relativamente fácil, las instrucciones en ensamblador se corresponden uno a uno
con las instrucciones máquina y los nombres simbólicos se relacionan con su codificación binaria
1
Fuente principal: [Prieto 06], cáp. 14.
Tema 1: Computadores y lenguajes de programación.
19
en tablas de símbolos. Pero a medida que las abstracciones se alejan de la máquina, la traducción se
hace más difícil, hasta llegar a un punto en el que el esfuerzo no merece la pena. El límite es más
tecnológico que teórico y posiblemente surjan en el futuro lenguajes de programación de propósito
general y uso común de un nivel de abstracción que supere a los lenguajes orientados a objetos que
son, de momento, la tecnología dominante.
Podemos ahora retomar las dos preguntas que nos hacíamos al principio de tema (¿qué es y cómo
funciona un computador? y ¿cómo se le dice a un computador lo que tiene que hacer?) para terminar
este apartado con una pequeña reflexión: mientras utilicemos para programar un lenguaje máquina
o un lenguaje ensamblador la respuesta a la segunda pregunta está íntimamente ligada a la
respuesta a la primera ya que, utilizando dichos lenguajes, sólo podemos programar si conocemos
con todo detalle la estructura interna del computador al que se refieren. Sin embargo, utilizando un
lenguaje de programación de alto nivel, la respuesta a la segunda pregunta es independiente de la
primera. Puesto que los lenguajes de programación de alto nivel abstraen la arquitectura de los
computadores, a través de ellos podemos decirles a tales computadores lo que tienen que hacer sin
conocer su estructura ni su funcionamiento interno. Aunque estrictamente hablando el lenguaje
máquina y el lenguaje ensamblador son lenguajes de programación, a partir de ahora cuando
hablemos de lenguaje de programación nos estaremos refiriendo exclusivamente los lenguajes de
programación de alto nivel.
Características de los lenguajes de programación.
Los lenguajes de programación (como cualquier lenguaje) tienen un léxico, una sintaxis y una
semántica 1. El léxico es el vocabulario o conjunto de símbolos incluidos en el lenguaje. La sintaxis es
el conjunto de reglas que nos indican cómo escribir oraciones correctas en el lenguaje. A partir de
ahora llamaremos a esas oraciones sentencias 2. La semántica define el significado de las sentencias
y por tanto es la semántica la que determina “lo que tiene que hacer el computador”. En los lenguajes
de programación, la relación entre sintaxis y semántica es muy estrecha pues el significado del
programa está totalmente ligado a la estructura sintáctica de sus sentencias. El proceso de
traducción de un código fuente escrito usando un lenguaje de programación a código máquina es, en
esencia, la generación de un código en lenguaje máquina con el mismo significado que el código
fuente.
Las características principales de los lenguajes de programación son las siguientes:
−
−
−
Utilizan notaciones cercanas al ámbito en que se usan. El léxico es simbólico y las operaciones
se describen con sentencias muy cercanas al lenguaje matemático o al lenguaje natural, que se
expresan por medio de texto, que incluye palabras en lengua inglesa 3 y expresiones
matemáticas y pueden incluirse comentarios.
Son independientes de la arquitectura física del computador. Esto, como ya hemos visto,
significa que podemos programar sin conocer los detalles del computador, pero significa algo
más: significa que los programas así escritos son portables, es decir pueden ejecutarse en
computadores distintos. El programa se escribe una vez y se traduce de forma diferente para
cada plataforma de ejecución 4.
Una sentencia en un lenguaje de alto nivel da lugar al ser traducida a varias instrucciones en
lenguaje máquina.
Es decir, tienen una gramática.
Existen lenguajes específicos para definir la sintaxis de los lenguajes de programación (metalenguajes). Los más usuales
son la notación BNF (Backus-Naur Form) y los diagramas sintácticos.
3 La programación es un “invento americano”.
4 De momento consideraremos que la plataforma de ejecución es el computador. Más adelante generalizaremos el concepto
de plataforma de ejecución.
1
2
Tema 1: Computadores y lenguajes de programación.
El proceso de traducción.
20
Un traductor es un programa que recibe como entrada un texto en un lenguaje de
programación y produce como salida un texto equivalente en lenguaje máquina.
El programa inicial se denomina programa fuente y el programa obtenido programa objeto.
El traductor puede ser un compilador o un intérprete. En términos generales la diferencia estriba
en que un compilador toma el programa fuente entero y produce un programa objeto, en tanto que
un intérprete traduce el programa fuente sentencia a sentencia, de forma que el programa se va
ejecutando a medida que se va traduciendo.
La traducción por un programa compilador (compilación) consta de dos etapas fundamentales
(figura 5): análisis del programa fuente y síntesis del programa objeto.
Programa fuente
Análisis de léxico
El programa fuente se descompone en sus símbolos léxicos (tokens):
literales, palabras reservadas, nombres de variables y funciones, etc.
Se obtiene una representación del programa formada por tablas de
símbolos, se identifican comentarios, espacios en blanco, tabulaciones,
etc. y se eliminan.
Se detectan errores léxicos.
Análisis sintáctico
Se comprueba que el programa es sintácticamente correcto, es decir
que todas las sentencias están bien construidas.
Análisis semántico
Se obtiene el significado de las sentencias a partir de la identificación
de las construcciones sintácticas y de la información almacenada en la
tabla de símbolos.
Análisis
Síntesis
Generación de Código
Optimización
Se crea un archivo con un código en lenguaje objeto (normalmente
lenguaje máquina) con el mismo significado que el código fuente.
Es muy habitual que este archivo no sea directamente ejecutable, sino
que se requieran otros pasos previos a la ejecución como ensamblado,
encadenado y carga.
Programa objeto
Figura 5: El proceso de compilación.
Una vez traducido, el programa puede encontrarse ubicado en varios ficheros objeto. Esto requiere
buscar el código correspondiente al programa en dichos ficheros y enlazarlo para obtener el
programa. Un enlazador (linker) es un programa que:
−
Lee los archivos objeto del programa identificando las rutinas que utiliza.
Tema 1: Computadores y lenguajes de programación.
−
−
21
Busca el código objeto de las rutinas en un conjunto dado de ficheros objetos. Este conjunto
incluye los ficheros objeto obtenidos al compilar el programa y otros que se le hayan indicado,
por ejemplo los incluidos en bibliotecas software utilizadas para realizar el programa.
Recopila de los ficheros objetos el código que utiliza el programa y lo enlaza para obtener un
fichero ejecutable.
Paradigmas de programación.
Acabamos de ver que los lenguajes de alto nivel deben proporcionar abstracciones que nos
permitan programar sin conocer la estructura interna del computador. La naturaleza de estas
abstracciones puede variar mucho de unos lenguajes a otros definiéndose diferentes paradigmas de
programación. Un paradigma de programación representa un estilo de programación determinado
caracterizado por un conjunto de conceptos y abstracciones que sirven para representar los
elementos de un programa y la forma de combinarlos. Algunos lenguajes de programación soportan
un único paradigma de programación, otros pueden soportar varios (lenguajes multiparadigma).
El paradigma de programación más cercano a la arquitectura interna de los computadores es la
programación imperativa. En este estilo de programación una computación se describe en términos
de sentencias que el computador ejecuta de forma secuencial y que a medida que se ejecutan
cambian el estado del programa. Este es el estilo de programación que necesariamente se sigue
cuando se programa en lenguaje máquina o ensamblador y que siguen también los lenguajes de alto
nivel más antiguos.
Evolución de la programación imperativa.
La programación imperativa evolucionó hacia la programación procedural. En la programación
procedural el programa se construye a partir de uno o más procedimientos (también llamados
subrutinas o funciones). Algunos autores no hacen distinción entre programación procedural e
imperativa, sin embargo, la encapsulación de las acciones en procedimientos (abstracción funcional)
tiene un enorme efecto en la forma en que pueden diseñarse y construirse los programas. La
programación estructurada es, a su vez, una evolución de la programación procedural en la que se
restringe la forma en que pueden usarse las estructuras de control de flujo y los saltos y retornos de
los procedimientos. Como evolución de la programación procedural y estructurada aparece el
paradigma de programación dominante hoy en día: la programación orientada a objetos. La
programación orientada a objetos es, como la procedural, programación imperativa, pero no es sólo
programación imperativa. En la programación orientada a objetos la visión global del programa no
es la de una secuencia de sentencias ejecutándose de forma secuencial, sino la de un conjunto de
objetos que colaboran intercambiando datos y servicios. La programación del comportamiento
interno de cada objeto sigue las reglas de la programación estructurada 1, pero para entender el
programa en su conjunto debe aplicarse un modelo (paradigma) distinto.
La programación declarativa.
Existe una familia de paradigmas de programación cuya forma de entender los programas es muy
distinta a la programación imperativa y que recibe por tanto un nombre distinto, es la
programación declarativa. En los lenguajes declarativos no se le dice al computador cómo resolver
un problema, sino el problema que tiene que resolver junto con un conjunto de reglas que permiten
resolverlo. No existe o se restringen al máximo los cambios de valor en las variables a través de
asignaciones y se utiliza de forma exhaustiva la recursión (funciones que se llaman a sí mismas 2).
1
2
Aunque podría seguir cualquier otro estilo.
La recursión puede utilizarse también con lenguajes imperativos y de hecho se verá durante el curso,
Tema 1: Computadores y lenguajes de programación.
22
Los programas declarativos no son una secuencia de instrucciones, sino un conjunto de reglas que
deben aplicarse para conseguir un resultado. Ejemplos de lenguajes declarativos son los lenguajes
funcionales y lógicos. En la programación funcional los programas se construyen a base de funciones
matemáticas. La programación lógica ve los programas como un conjunto de formulas lógicas a
partir de la cuales se realizan razonamientos para llegar a un resultado o realizar una acción. El
problema se expresa mediante fórmulas lógicas y los programas consisten en la aplicación de reglas
de inferencia sobre dichas fórmulas hasta que se llega a la solución del problema o se prueba que el
conjunto de fórmulas utilizado es inconsistente.
Los lenguajes declarativos son tremendamente efectivos y de una concisión y elegancia imposibles
de conseguir con los lenguajes imperativos. Además, como alguno habrá sospechado, la
programación declarativa está íntimamente ligada con la inteligencia artificial. Aunque es fácil
percibir lo lejos que se encuentran de la arquitectura de los computadores es posible construir
compiladores eficientes para los mismos No obstante, no todos los problemas se adaptan bien al
paradigma declarativo. En la tabla 4 se resumen los principales paradigmas de programación y los
lenguajes más conocidos asociados a los mismos. Sobre la tabla habría que hacer las siguientes
observaciones:
−
−
−
−
Aparece un paradigma, la programación dirigida por eventos, que no se han comentado en el
texto y que puede considerarse como una variante de la programación procedural.
La tabla no incluye todos los paradigmas de programación que pueden encontrarse en la
literatura técnica.
Ninguno de los paradigmas tiene una definición precisa, ni hay un acuerdo general sobre cuál
de ellos es el más adecuado para desarrollar software. Se admite que el paradigma más
adecuado viene dado por el tipo de problema que se pretende resolver.
Algunos de los lenguajes que aparecen asociados a un paradigma soportan también otros. No se
ha intentado ser exhaustivo, sino poner algún ejemplo representativo.
Es pronto para que puedan entender todas las características de los paradigmas y sus
implicaciones. La mayor parte de las características de los lenguajes imperativos y orientados a
objetos se ven en este curso. Las características de la programación dirigida por eventos se verán
en la asignatura de 3º, Programación para Ingeniería Telemática, ciertas características de la
programación declarativa se verán al estudiar bases de datos al final de esta asignatura y con más
extensión en la asignatura de 3º Programación para Ingeniería Telemática.
Tabla 4: paradigmas de programación.
Paradigma
Características/abstracciones
Lenguajes
Programación imperativa: Los programas se
describen en términos de sentencias que se
ejecutan de forma secuencial cambiando el estado
del programa.
Sentencia de asignación.
C, COBOL,
FORTRAN
Pascal, Modula 2.
Programación dirigida por eventos:
Programación procedural en la que el flujo de
control del programa es determinado por eventos
(movimientos y click de ratón, entradas desde
teclado, llegada de mensajes, vencimiento de
temporizadores, etc.).
No hay instrucción GOTO.
Únicamente tres estructuras de control:
secuencia, selección e iteración.
Cada estructura tiene un punto de
entrada y uno de salida.
Manejadores de eventos.
Retrolladas (callbacks)
Procesamiento asíncrono, hilos
servidores.
Programación procedural estructurada.
Programación imperativa con encapsulación de
acciones en funciones y restricciones en el control
de flujo.
Programación orientada a objetos.
Encapsulación de datos y servicios en objetos. Los
objetos que colaboran intercambiando datos y
servicios
Estructuras de datos globales.
Inversión de control.
Clases, interfaces, objetos, métodos,
tipos abstractos de datos, polimorfismo.
Mensajes.
Los lenguajes
procedurales
pueden soportar la
programación
conducida por
eventos.
Simula, C++, ada95,
Java, C#, Eiffiel.
Tema 1: Computadores y lenguajes de programación.
23
Programación declarativa: expresa la lógica del
programa sin describir con detalle su flujo de
control. Se describe el problema a resolver junto
con el conjunto de reglas que permiten resolverlo.
Evita la modificación de los datos y los cambios de
estado.
Fórmulas
SQL
Programación lógica: El problema se expresa
mediante fórmulas lógicas y los programas
consisten en la aplicación de reglas de inferencia
sobre dichas fórmulas hasta que se llega a la
solución del problema o se prueba que el conjunto
de fórmulas utilizado es inconsistente.
Lambda Calculus.
Composicionalidad.
Recursion
Prueba de teoremas.
Scheme, Ocaml,
Haskell
Programación funcional: Los programas
consisten en la evaluación de funciones
matemáticas.
Reglas de inferencia.
Sin efectos colaterales.
Modelos, restricciones, reglas de
inferencia.
Prolog
Sistemas Operativos
Un sistema operativo 1 es un programa o conjunto de programas que:
−
−
Gestiona y asigna los recursos hardware y software que requieren los programas para poder
ejecutarse.
Proporciona a los usuarios una interfaz de acceso que define una máquina virtual más fácil de
entender y utilizar que la máquina real subyacente.
Los sistemas operativos más populares son aquellos que están dirigidos a los ordenadores
personales como Microsoft Windows, Mac OS X o Linux, pero puesto que el sistema operativo hace
de intermediario entre las aplicaciones y el hardware de la computadora, están presentes en casi
cualquier dispositivo que contenga un procesador (teléfonos móviles, video consolas, servidores
web, etc.). En muchas ocasiones los sistemas operativos para estos dispositivos son versiones
reducidas de los sistemas operativos usados en los ordenadores personales. Algunas de las
funciones típicas de un sistema operativo son:
−
−
−
−
−
−
Facilitar el uso del procesador y la comunicación computador/usuario.
Gestionar y asignar recursos a los distintos programas, principalmente tiempo de procesador,
memoria y periféricos.
Contabilizar los recursos utilizados por programas y usuarios.
Gestionar y mantener los archivos en dispositivos de almacenamiento secundario.
Proteger los datos y los programas, especialmente en sistemas multiusuario y distribuidos.
Proporcionar control de acceso, identificando y acreditando a los usuarios.
El sistema operativo establece una frontera (a veces muy difusa) entre dos tipos de software: los
programas de soporte que ofrece el propio sistema operativo y las aplicaciones que utilizan los
servicios del sistema operativo.
El nivel de máquina operativa 2.
El sistema operativo define un nivel de máquina virtual, que también se puede denominar de
máquina operativa, que permite utilizar el computador sin conocer los detalles internos del
computador. En este sentido, el sistema operativo proporciona, como hacen los lenguajes de
programación de alto nivel, un nivel de abstracción que permite ignorar la arquitectura interna del
Los sistemas operativos se estudian en Fundamentos de Computadores. Aquí sólo se pretende presentar algunas de sus
características más relevantes.
2 Tomado de Introducción a la Informática, capítulo 13.
1
Tema 1: Computadores y lenguajes de programación.
24
computador. El sistema operativo suele estar constituido por una serie de módulos que ejecutan
sus servicios en respuesta a las llamadas al sistema que realizan los clientes del sistema operativo
(figura 6). Estos clientes pueden ser los usuarios del computador, que lanzan las llamadas a través
de la interfaz de usuario del sistema operativo. Cualquier programa que tenga que interactuar con
un operador humano dispone de una interfaz de usuario, que se fundamenta en la utilización de un
lenguaje de comandos. Cuando en un computador introducimos una orden (por ejemplo, formatear
un disco), esta orden es captada por el intérprete de comandos (shell 1) que es un módulo o
programa independiente del sistema operativo. El intérprete se encarga de traducir los comandos
de usuario en llamadas al sistema. En los antiguos sistemas operativos la órdenes se introducían de
forma textual en una consola de texto, hoy en día la forma habitual es introducirlas a través de
ventanas y diálogos. No obstante, los clientes más habituales del sistema operativo no son los
operadores humanos, sino los propios programas de aplicación. A su vez, unos módulos del sistema
operativo son clientes de otros módulos del sistema operativo, hasta llegar a una parte del sistema
operativo conocida como núcleo o kernel que es el módulo del sistema operativo que interactúa
directamente con el hardware del computador.
Una característica muy importante del sistema operativo es que tiene que estar disponible en
cuanto se arranca el computador. Cuando se enciende un computador, se lanza a ejecución un
programa de autodiagnóstico (POST: Power On Self Test) que identifica la memoria disponible, los
discos, el teclado, la tarjeta de vídeo, el ratón y en general todos los dispositivos con los que cuenta
el computador. Posteriormente se lanza a ejecución el cargador inicial (bootstrap loader) que, a su
vez, carga un programa cargador más sofisticado, cuyo objetivo es buscar el sistema operativo y
cargar una parte de él (denominada comúnmente residente) en la memoria principal. Tanto el
programa de auto diagnóstico como el cargador inicial suelen estar grabados en la memoria ROM
del computador. Una vez arrancado, el sistema operativo presenta en pantalla una interfaz de
usuario que queda a la espera de las órdenes del usuario.
Usuarios y programas de aplicaciones
Sentencias de
lenguajes de alto
nivel
Instrucciones
de edición
Órdenes del
sistema
operativo
Interfaz de Usuario
Interfaz de Usuario
Interfaz de Usuario
Compiladores
Editores
Intérpretes del
lenguaje de comandos
Llamadas al sistema
Máquina operativa o
virtual
Instrucciones en
lenguaje
máquina
Núcleo del sistema operativo
Instrucciones en
lenguaje máquina
Máquina Real
Procesador
Figura 6: El sistema operativo dentro del contexto de los niveles conceptuales.
Shell significa literalmente cáscara y recibe ese nombre porque es (o forma parte de) la capa más externa del sistema
operativo.
1
Tema 1: Computadores y lenguajes de programación.
Plataforma de ejecución.
25
El conjunto computador-sistema operativo define una plataforma de ejecución de los programas.
Los sistemas operativos normalmente tienen versiones para distintos tipos de computadores de
forma que un mismo programa puede ejecutarse en computadores diferentes siempre que ambos
tengan instalado el mismo sistema operativo. Esto es así porque los programas acceden a los
recursos del computador a través de llamadas al sistema y la sintaxis y la semántica de las llamadas
no cambian en tanto no cambie el sistema operativo. De esta manera la plataforma de ejecución que
ve el programa es la misma aunque haya cambiado el computador subyacente. Esta idea ha tratado
de generalizarse definiendo un estándar para las llamadas al sistema (estándar POSIX). En teoría,
un programa podría ejecutarse sobre cualquier plataforma que siga dicho estándar aunque tanto el
computador como el sistema operativo sean distintos. A pesar de ello, en la práctica, si cambia el
computador, aunque se mantenga el mismo sistema operativo, es bastante habitual que haya que
recompilar el programa, ya que el código objeto generado por los compiladores puede asumir una
arquitectura hardware determinada. Por otro lado, no todos los sistemas operativos siguen el
estándar POSIX.
Como cambiar el sistema operativo de un computador no es una tarea trivial, una forma de
conseguir ejecutar en una plataforma programas compilados para otra plataforma es emular las
plataformas de ejecución. Por ejemplo, supongamos que tenemos instalado Windows y deseamos
ejecutar una aplicación sobre una versión de Linux. Una posibilidad es emular la plataforma Linux
sobre la plataforma Windows (también podría hacerse al revés). La potencia de los computadores
actuales permite realizar tipo de emulaciones y ejecutar los programas sobre los emuladores de
forma muy eficiente.
Tema 1: Computadores y lenguajes de programación.
26
Anexo: Codificación de números enteros 1
Existen muchas definiciones de “Información”, la que mejor viene para los propósitos de este
apartado es la siguiente 2:
Secuencia de símbolos que pertenecen a un alfabeto y que representan
algún hecho, concepto o idea.
La información en un ordenador va codificada en binario, (0, 1). Esta codificación, en el caso de los
números está basada en el uso del sistema de numeración en base 2.
Fundamentos matemáticos para un sistema de numeración. Bases, dígitos y
cifras.
Todo número viene expresado en una base
signos.
={
/
0=
0;
+1 =
> 1. Una base es un conjunto finito y ordenado de
+ 1, ∀ = 0, 1,…,
– 1} .
La expresión de arriba puede expresarse también de la siguiente manera:
1.
El primer elemento de la base es el cero.
3.
El máximo elemento de la base es igual al cardinal de la base menos uno.
2.
Los sucesivos elementos ordenados de la base son tales que cualquier elemento es igual a
su inmediato anterior más uno.
La base 10, B = 10, por ejemplo, está formada por los siguientes elementos:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
En cada base, todo número entero a > 0 puede ser escrito de modo único en la forma
a = ak · Bk + ak-1 · Bk-1 + ak-2 · Bk-2 + … + a1 · B1 + a0 · B0
(1)
donde k > 0 es un entero, y cada uno de los ai son enteros tales que:
0≤
≤
− 1, para i = 1, 2, 3, … , , y
Por ejemplo, en base 10, B = 10
≠0
71053 = 7 · 104 + 1 · 103 + 0 · 102 + 5 · 101 + 3 · 100
A los coeficientes
se les llama dígitos del número . A la expresión (1) se la llama expansión del
número. El número habitualmente se representa como:
=
−1
−2
…
1
0
Fuente: [Alcover 09], disponible en la biblioteca digital de la UPCT.
Una definición especialmente interesante es la de la “Teoría da la Información”, parte de la cual se estudia en el grado, que
caracteriza a la misma en términos probabilísticos. Dicha definición, que es complementaria al proporcionada en el cuadro,
está orientada al estudio de la capacidad de transmisión de los canales, la compresión de datos o la detección y corrección de
errores.
1
2
Tema 1: Computadores y lenguajes de programación.
27
De esta manera, cualquier número viene representado, en una base determinada, por una serie
única de coeficientes . A cada serie de coeficientes, que codifica un número de modo único en una
determinada base, se le llama cifra.
Supongamos ahora que queremos expresar un numéro a > 0 en binario, base 2. Tendríamos:
a = ak · 2k + ak-1 · 2k-1 + ak-2 · 2k-2 + … + a1 · 21 + a0 · 20
Por ejemplo
11011 = 1 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 1 · 20
Es fácil ver las correspondencias entre los primeros diez dígitos en base 10 y su representación en
base 2:
Base 10
0
1
Base 2
0
1
2
10
4
100
6
110
3
5
7
8
9
11
101
111
1000
1001
Cambios de base.
Paso de base dos a base diez: Para este cambio de base es suficiente con desarrollar la expansión
del número. Por ejemplo:
10011101 2 = 1 · 27 + 0 · 26 + 0 · 25 + 1 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 128 + 16 + 8 + 4 + 1
= 157 10.
Paso de base diez a base dos: Para este cambio se divide el entero por dos (división entera), y se
repite sucesivamente esta división hasta llegar a un cociente menor que la base. Simplemente
vamos dividiendo por la base el número original y vamos repitiendo el procedimiento para los
cocientes que vamos obteniendo. Los restos de estas divisiones, y el último cociente, son los dígitos
buscados. El último cociente es el dígito más significativo, y el primer resto el menos
significativo.Por ejemplo, en el ejemplo recogido en el cuadro de abajo vemos que el valor 157
expresado en base diez es, en base dos, 10011101.
Tema 1: Computadores y lenguajes de programación.
28
Las bases octal y hexadeximal facilitan el manejo de las cifras codificadas en base dos, que
enseguida acumulan gran cantidad de dígitos, todos ellos ceros o unos. Para pasar de base dos a
base dieciséis es suficiente con separar la cifra binaria en bloques de cuatro en cuatro dígitos,
comenzando por el dígito menos significativo. Al último bloque, si no tiene cuatro dígitos, se le
añaden tantos ceros a la izquierda como sean necesarios.
Complementos a la Base.
Vamos a introducir dos conceptos nuevos, muy sencillos, pero muy útiles para representar
números binarios con signo. Los de complemento a la base y complemento a la base menos uno.
Supongamos el número N expresado en una base B determinada. Y supongamos que ese número
tiene k dígitos.
Llamamos complemento a la base de ese número expresado en esa base determinada, a la
cantidad que le falta para llegar a la cifra de (k + 1) dígitos, en el que el dígito más significativo es el
uno y los demás son todos ellos iguales a cero. De una forma más precisa, definiremos el
complemento a la base de un número N codificado con k cifras en base B como:
CB,k(N) = Bk - N
Por ejemplo, en base diez, el complemento a la base del número (279)10 es la cantidad que hace falta
para llegar a (1000)10, que es (721)10.
En esta definición hay que destacar que, si el número N viene expresado de forma que a su
izquierda se tienen algunos dígitos iguales a cero, entonces el complemento a la base es diferente
que si estuviese sin esos dígitos, aunque la cantidad codificada sería la misma. Siguiendo con el
ejemplo anterior, el complemento a la base del número codificado como (0279)10 ya no es (721)10,
sino (9721)10, porque ahora no se trata de calcular lo que falta para llegar a (1000)10, sino para
llegar a (10000)10, puesto que ahora la cantidad numérica está codificado con cuatro dígitos.
El concepto de complemento a la base menos uno es muy semejante: es la cantidad que dista
entre el número N, codificado con k dígitos en la base B, y el número formado por k dígitos, todos
ellos con el valor del mayor elemento de la base B en la que se trabaja. De una forma más precisa,
definiremos el complemento a la base menos uno de un número N codificado con k cifras en base B
como
CB-1,k(N) = Bk – N - 1
Tema 1: Computadores y lenguajes de programación.
29
Por ejemplo el complemento a la base menos uno del número (541)10 expresado en base diez es la
cantidad que hace falta para llegar a (999)10, que es (458)10.
De nuevo aquí también cambia el complemento a la base menos uno de un número si ponemos en
su codificación más o menos ceros a su izquierda. Es inmediato también deducir que la relación
entre los dos complementos es que la diferencia entre ambos es igual a uno. De hecho se puede
definir el Complemento a la Base menos uno de un número N codificado con k dígitos en la base B,
como el Complemento a la Base de un número N codificado con k dígitos en la base B, menos 1.
CB,k(N) = CB-1,k(N) - 1
Una propiedad de los complementos es que, en cierta sentido, facilitan el cálculo de las restas. Se
pueden ver algunos ejemplos en base diez. Se cumple que la resta de dos enteros se puede también
calcular haciendo la suma entre el minuendo y el complemento a la base del sustrayendo,
despreciando el posible acarreo final. Por ejemplo:
Donde si, como se ha dicho, despreciamos el último acarreo, tenemos que se llega al mismo
resultado:127.
También se puede realizar un procedimiento similar si se trabaja con el complemento menos uno.
En ese caso, lo que se hace con el último acarreo, si se tiene, es eliminarlo del resultado intermedio
y sumarlo para llegar al resultado final. Por ejemplo:
Hasta ahora todo lo expuesto puede aparecer como un enredo algo inútil porque, de hecho, para el
cálculo del complemento a la base es necesario realizar ya una resta, y no parece que sea mejor
hacer la resta mediante uno de los complementos que hacerla directamente. Pero las cosas cambian
cuando se trabaja en base dos. Veamos algunos ejemplos de cálculo de los complementos en esa
base:
Si se compara la codificación de cada número N con su correspondiente complemento a la base
menos uno, se descubre que todos los dígitos están cambiados: allí donde en N corresponde el
dígito 1, en C1(N) se tiene un 0; y viceversa. Es decir, que calcular el complemento a la base menos
uno de cualquier número codificado en base dos es tan sencillo como cambiar el valor de cada uno
de los dígitos de la cifra. Y esta operación es muy sencilla de realizar con circuitos electrónicos. La
ventaja clara que aportan los complementos es que no es necesario incorporar un restador en la ALU,
puesto que con el sumador y un inversor se pueden realizar restas.
Tema 1: Computadores y lenguajes de programación.
Números binarios en complemento a 1 y en complemento a 2
30
Cuando se trabaja con números binarios la base es 2 y por tanto el complemento a la base se
denomina complemento a 2 y el complemento a la base menos 1 se denomina complemento a 1.
Como acabamos de ver, el uso de el complemento a 1 simplifica los circuitos electrónicos para
realizar las restas, sin embargo, existe una desventaja a la hora de utilizar el complemento a 1 para
representar números negativos que hace más adecuado el complemento a 2, y es que existen dos
posibles representaciones para el número cero (todo ceros o todo unos).
El cálculo del complemento a 2 es también muy fácil de realizar mediante puertas lógicas: basta con
invertir el valor de cada una de sus cífras, es decir realizar el complemento a 1, y sumarle 1 al
número obtenido (véase cuadro anterior).
Una forma rápida de hallar el complemento a dos es comenzar por la derecha (el dígito menos
significativo 1), copiando el número original (de derecha a izquierda) hasta encontrar el primer 1,
luego de haber copiado el 1, se niegan (complementan) los dígitos restantes (es decir, copia un 0 si
aparece un 1, o un 1 si aparece un 0). Este método es mucho más rápido para las personas, pues no
utiliza el complemento a uno en su conversión.
Por ejemplo, el complemento a dos de «0011 11010» es «1100 00110»-
1 Algunos procesadores codifican el bit más significativo a la izquierda y otros a la derecha (codificación little-endian o bigendian).
Tema 2: Abstracción de datos.
Tema 2: Abstracción de datos
Objetivos
•
•
•
Introducir la abstracción de datos de los lenguajes de alto nivel.
Presentar los tipos de datos primitivos de Java.
Introducir los elementos léxicos fundamentales del lenguaje Java.
Contenido
•
•
•
•
•
•
Tipos de datos.
Tipos de datos primitivos de Java.
Identificadores y palabras reservadas.
Variables y constantes.
Expresiones y asignación.
Tipos de operadores y reglas de asociatividad y precedencia.
31
Tema 2: Abstracción de datos.
Abstracción y lenguajes de programación 1.
32
Como se vio en el tema anterior, todos los lenguajes de programación proporcionan “abstracciones”,
estando la complejidad de los problemas que somos capaces de resolver con dichos lenguajes
directamente relacionada con el tipo y la calidad de tales abstracciones. El tipo de la abstracción
hace referencia a aquello que se está abstrayendo. Los lenguajes ensambladores son una pequeña
abstracción de la máquina subyacente. Los lenguajes de programación imperativos (como Fortran,
Basic y C) son a su vez abstracciones de los lenguajes ensambladores. Los lenguajes imperativos
suponen una enorme mejora sobre los lenguajes ensambladores, pero sus abstracciones todavía
requieren pensar en términos de la estructura de los computadores en lugar de en términos de los
problemas que se quieren resolver. Y esto es un grave problema. Veamos por qué.
Un conjunto de abstracciones define un espacio de modelado para plantear y resolver problemas.
Por ejemplo, el algebra puede verse como un lenguaje con abstracciones en las que es fácil plantear
y resolver un cierto tipo de problemas. Un matemático puede plantear un problema geométrico
utilizando las abstracciones del algebra (matrices, vectores, productos escalares y vectoriales, etc.)
y lo puede resolver utilizando las mismas abstracciones. Pero ¿qué ocurre cuando la solución se
quiere programar en un computador? Ocurre que hemos planteamos el problema en un espacio de
modelado (por ejemplo el algebra), pero tenemos que expresar la solución en un espacio de
modelado distinto (el lenguaje de programación). En términos de la Informática se dice que el
espacio del problema y el espacio de la solución no coinciden. El programador debe entonces
establecer una asociación entre el modelo de la máquina y el modelo del problema que se pretende
resolver. El esfuerzo que se requiere para realizar esta asociación produce programas difíciles de
escribir y aún más difíciles de mantener. Para evitar este esfuerzo algunos lenguajes de
programación adoptan una visión particular del mundo adaptada a un cierto tipo de problemas. Por
ejemplo, LISP reduce todos los problemas a manejo de listas de datos y APL reduce todos los
problemas a algoritmos, los lenguajes declarativos plantean los problemas en términos de fórmulas
lógicas y razonamientos. Cada uno de estos lenguajes es adecuado para el tipo de problema al que
está orientado, pero cuando se intenta usarlos para otros tipos de problemas se vuelven extraños y
difíciles de utilizar.
Los lenguajes de programación orientados a objetos (Java entre ellos) son una evolución de los
lenguajes imperativos que proporcionan herramientas para que el programador pueda definir las
abstracciones del espacio del problema y trabajar con ellas. La representación de estas
abstracciones se realiza de forma lo suficientemente general para no restringir al programador a un
determinado tipo de problemas. Tanto los elementos del espacio del problema como los del espacio
de la solución se modelan mediante objetos. La idea es permitir al programador adaptarse a
cualquier tipo de problema mediante la adición de nuevos tipos de objetos, de forma que cuando se
lea el código que describe la solución se estén leyendo los mismos términos en los que se ha
expresado el problema. Esta es una abstracción flexible y poderosa: la orientación a objetos permite
describir la solución en los mismos términos en que se ha descrito el problema, en lugar de en los
términos de la estructura interna de los computadores donde tal solución se ejecutará. No obstante,
existe todavía una conexión muy fuerte con la estructura interna de la máquina subyacente: el
comportamiento y las acciones de cada objeto se programan haciendo uso de las abstracciones de
los lenguajes imperativos. Los conceptos fundamentales de la programación orientada a objetos se
verán en el tema 6.
De todos los esfuerzos de abstracción que nos alejan del computador y nos acercan al espacio del
problema el primero que vamos a ver es la “abstracción de datos”. Mediante la abstracción de datos
se separan las propiedades abstractas de un determinado tipo de datos de los detalles de su
implementación en una máquina concreta. Sólo las propiedades abstractas son visibles para el
programador y para el resto del código, mientras que la implementación permanece enteramente
privada y puede cambiarse sin que el programa se vea afectado ya que el cambio de tal
implementación no implica ningún cambio en las propiedades abstractas de los datos.
1
Fuentes: Tomado [Eckel 02] y http://en.wikipedia.org/wiki/Abstraction_%28computer_science%29
Tema 2: Abstracción de datos.
Tipos de datos.
33
Tipos de datos.
Los lenguajes ensambladores utilizan los datos tal y como se codifican en las celdas de memoria de
un computador, como una simple colección de bits. Dichos lenguajes no tienen capacidad para
expresar el significado de los datos, toda la responsabilidad recae en el programador y los errores
son muy frecuentes. Hacen falta abstracciones más elaboradas para poder construir programas
grandes o incluso de tamaño moderado.
La mayoría de los lenguajes de programación incluyen un conjunto de tipos de datos simples
(números enteros y reales, caracteres y valores booleanos). Estos tipos de datos vienen definidos
como parte de los lenguajes de programación y se denominan tipos de datos primitivos o build-in
types. Los lenguajes de programación suelen definir asimismo mecanismos para construir nuevos
tipos de datos a partir de los ya existentes. Estos nuevos tipos pueden ser agrupaciones de datos de
un mismo tipo simple (por ejemplo, una tabla de enteros) o agrupaciones de datos de distintos
tipos simples. El mecanismo de construcción de tipos puede generalizarse para construir tipos de
datos complejos a partir de cualquier tipo definido con anterioridad, sea este simple o complejo.
Un tipo de datos es un conjunto de valores con ciertas propiedades y un
conjunto de operaciones que pueden realizarse sobre dichos valores
Una vez definidos los tipos de datos, todos los datos de un programa se clasifican de acuerdo a
dichos tipos. Un dato sólo podrá contener los valores definidos en su tipo y sólo podrá usarse en las
operaciones que permita su tipo. Los tipos de datos abstraen la representación interna de los datos
en el computador, ocultando 1 los detalles de su codificación y manipulación.
Tipado fuerte 2.
El tipado fuerte implica que el lenguaje de programación impone restricciones muy severas sobre
las operaciones que pueden realizarse entre datos de distinto tipo, evitando la compilación o
ejecución del código que viola tales restricciones (por ejemplo, no se permite sumar un número
entero con un carácter). La naturaleza de tales restricciones varía mucho de unos lenguajes a otros
por lo que no es posible dar una definición formal del tipado fuerte. Sin embargo, suele
considerarse que un lenguaje fuertemente tipado debe:
1.
2.
3.
Determinar en tiempo de compilación (análisis estático 3) si las operaciones que se realizan
sobre los datos son consistentes con su tipo. Un lenguaje que no realice esta comprobación no
se considera fuertemente tipado.
Proporcionar seguridad de tipos 4 tanto en tiempo de compilación como en tiempo de ejecución,
es decir rechazar todas aquellas operaciones que violen las restricciones impuestas a los tipos.
Garantizar que cuando se detecte una violación de tipos en tiempo de ejecución se llevará a
cabo una acción bien definida. La idea es que el programador sepa exactamente cómo se va a
comportar el programa si se detecta una violación de tipos.
Volveremos a menudo sobre este punto cuando hablemos del principio de ocultación de la información.
Tomado de http://en.wikipedia.org/wiki/Strongly_typed_programming_language
3 En general el término análisis estático se refiere a aquellas comprobaciones que se hacen antes de ejecutar el programa,
durante su compilación, mientras que el de análisis dinámico se reserva para aquellas comprobaciones que deben realizarse
durante la ejecución del programa. Obviamente cuantos más lejos puedan llevarse los análisis estáticos mejor, hasta el caso
ideal de poder garantizar que no se producirán violaciones de tipos en tiempo de ejecución, evitando así el análisis dinámico.
4 Traducción de type safety.
1
2
Tema 2: Abstracción de datos.
34
Normalmente se exigen estas tres condiciones, sobre todo la primera, para considerar a un lenguaje
fuertemente tipado. Algunos autores van todavía más lejos y exigen además que:
4.
5.
No exista ninguna forma de soslayar el sistema de tipos (por ejemplo, pudiendo trabajar
directamente con los bits almacenados en la memoria).
No se realicen conversiones implícitas de tipos (por ejemplo, muchos lenguajes permiten
sumar un entero y un real convirtiendo automáticamente el número entero en real). Todas las
conversiones de tipos deben ser explícitas (realizadas por el programador). Algunos autores
van todavía más lejos y exigen que no pueda realizarse ninguna conversión de tipos, ya sea
implícita o explícita.
Obsérvese que la mera existencia de tipos de datos en el lenguaje no implica que este sea
fuertemente tipado. Existen lenguajes con tipos de datos como Fortran, Cobol o C que no disponen
de tipado fuerte porque no cumplen las tres primeras condiciones. Estos lenguajes se denominan
débilmente tipados: disponen de un sistema de tipos y de mecanismos para definir tipos complejos,
pero no tienen un sistema que compruebe la consistencia de las operaciones respecto de dichos
tipos.
Lenguajes como Java, C++ y Ada, especialmente este último, son lenguajes fuertemente tipados.
Todos ellos cumplen las tres primeras condiciones, aunque permiten las conversiones de tipos en
determinadas circunstancias.
Beneficios de los tipos de datos 1.
El tipado fuerte es una ayuda inestimable para conseguir programas correctos y eficientes, ya que:
1.
La información de tipos estáticos permite a los compiladores:
−
−
2.
3.
4.
Asignar memoria con eficiencia y generar un código máquina que manipula los datos
también con gran eficiencia.
Reducir la cantidad de código es necesario compilar con lo cual mejora la eficiencia de
traducción.
La verificación de tipos estáticos permite detectar muchos errores de programación antes de
ejecutar los programas mejorando la seguridad y confiabilidad de un programa al reducir la
cantidad de errores que pueden ocurrir durante la ejecución.
Se mejora la legibilidad del código, ya que los tipos explícitos de datos permiten comprender el
papel que desempeñan los datos dentro de un programa.
Permite definir con precisión la forma en que puede utilizarse un código para construir
programas (definición de interfaces).
Tipos y lenguajes de programación.
A la hora de seleccionar (juzgar) un lenguaje de programación es necesario considerar:
−
−
1
El conjunto de tipos primitivos que proporciona.
Si permite combinar los tipos de datos primitivos para crear otros tipos de datos más complejos
(arrays, estructuras,…).
Tomado de [Louden 03].
Tema 2: Abstracción de datos.
−
−
35
Si permite definir nuevos tipos de datos y la manera en que serán tratados por el lenguaje
(¿serán tipos de datos de primera clase? ¿se les aplicará el tipado fuerte?).
Si pueden realizarse conversiones de tipos de forma segura.
Tipos de datos primitivos de Java.
La tabla 1 muestra los tipos de datos primitivos de Java y su tamaño en bytes. Como se puede
observar en la tabla, los tipos de datos primitivos modelan caracteres, valores numéricos (enteros y
reales) y valores lógicos (verdadero y falso). Los tipos de datos primitivos de Java presentan dos
peculiaridades:
1.
2.
Al contrario de lo que ocurre en otros lenguajes, el tamaño de los tipos de datos no cambia de
un computador a otro. Esta invariancia es una de las razones que hacen que los programas de
Java sean portables.
Los tipos de datos primitivos son en Java una “irregularidad”.
Tabla 1: Tipos de datos primitivos en Java.
Tipo de datos
primitivo
Tamaño
Mínimo
Máximo
16-bit
Unicode 0
Unicode 216-1
32-bit
-231
231 -1
boolean
char
byte
short
int
long
float
double
8-bit
16-bit
64-bit
32-bit
64-bit
-128
-215
-263
127
215 -1
263 -1
El tamaño de un tipo de datos numérico determina su rango (mínimo y máximo) y en el caso de los
tipos “reales” también determina su precisión (fracción más pequeña o número más grande que
pueden representarse sin redondeo). Muchos programas asumen un rango y una precisión
determinados. Si disminuye el tamaño de los datos, su rango y precisión también disminuyen y el
programa puede dejar de comportarse correctamente. Lenguajes como C++ o Ada permiten al
usuario definir sus propios tipos numéricos para asegurar la portabilidad de los programas.
Como se explicará más adelante, en Java todo es un objeto. En realidad esto no es del todo cierto ya
que en un programa Java hay algunos datos que no se tratan como objetos: los datos
correspondientes a los tipos de datos primitivos. Una de las propiedades más importantes de un
lenguaje de programación es su regularidad. La regularidad está relacionada con la simplicidad y
con la economía de conceptos y por tanto con la claridad de los programas resultantes. Por ello,
introducir una irregularidad en un lenguaje debe responder a una causa importante. En el caso de
Java esta causa es la eficiencia de los programas. Por razones que se verán más adelante la gestión
de los objetos, su creación y destrucción con la consiguiente reserva y liberación de memoria,
suponen una sobrecarga importante que, en el caso de los tipos de datos primitivos, los diseñadores
de Java prefirieron evitar. Esto supone que en Java hay que considerar dos clases de tipos de datos,
los tipos de datos primitivos y los tipos referencia que se usan con los objetos. De momento sólo nos
ocuparemos de los tipos de datos primitivos. En un apartado posterior hablaremos someramente
de los tipos referencia.
Tema 2: Abstracción de datos.
36
Los valores numéricos enteros se representan usando un bit de signo (0: positivo, 1: negativo) y se
almacenan en complemento a dos. El cálculo del complemento a dos es muy sencillo y muy fácil de
realizar mediante puertas lógicas, donde reside su utilidad:
−
−
Los números positivos se quedarán igual en su representación binaria.
En los números negativos deberemos invertir el valor de cada una de sus cifras, es decir
realizar el complemento a uno, y sumarle 1 al número obtenido.
Cabe recordar que debido a la utilización de un bit para representar el signo, el rango de valores
será diferente al de una representación binaria habitual; el rango de valores decimales para «n» bits
será:
-2n-1 ≤ rango ≤2n-1 - 1
Los valores reales son los más complicados de representar. Un valor real tiene una parte entera y
una parte fraccionaria. La parte fraccionaria provoca pérdida de precisión, ya que el ordenador
tiene precisión finita. Existen valores que no se pueden expresar, como 1/3. La forma de
representar los dos campos da lugar a dos tipos de representaciones: coma fija y coma flotante.
Puesto que Java utiliza la representación en coma flotante nos centraremos exclusivamente en esta
última que se basa en la notación científica de mantisa y exponente:
Número = signo · mantisa · 10exponente
El estándar IEEE754 utilizado por Java distribuye los bits entre signo, mantisa y exponente como se
resume en la tabla 2.
Tabla 2: Estándar IEEE754
TIPO
SIGNO
MANTISA
EXP
float
1 bit
23 bit
8 bit
double
1 bit
52 bit
11 bit
La representación en punto flotante se adapta muy bien a “cualquier” número, pero complica
operaciones aritméticas y algoritmos. La precisión depende de los bits de la mantisa y el rango de
los bits del exponente. Además, hay que tener en cuenta que la precisión de los números
representados en punto flotante no es constante en todo el rango (véase Ejemplo21 en el código
suministrado).
No entraremos en más detalles sobre la representación interna de los tipos numéricos. Por dos
razones. La primera, es que no deberíamos preocuparnos por ella ya que trabajamos a otro nivel de
abstracción, la segunda es que tales representaciones se ven en otras asignaturas. De estas dos
razones, sólo la segunda responde completamente a la verdad. Los tipos numéricos no son
exactamente los números que representan. En Matemáticas el conjunto de los enteros es un
conjunto infinito, mientras que los tipos enteros tienen un rango finito bien definido. La cantidad de
números enteros que pueden representarse es finita, porque el tamaño de la celda de memoria
donde tales números se guardan también lo es. Lo mismo puede decirse para los reales, y algo más.
En los números enteros no hay problemas de precisión, pero en los reales sí. Cualquier intervalo del
conjunto de los números reales es infinito, pero los números de los tipos reales tienen una precisión
finita. El programador en Java, o en cualquier lenguaje que proporcione tipos numéricos, si bien no
tiene que saber cada detalle de la representación interna de los datos numéricos, sí necesita saber
Tema 2: Abstracción de datos.
37
el rango y la precisión de los tipos de datos que maneja y el comportamiento del lenguaje cuando
tales rangos y precisiones son excedidos (véase nuevamente Ejemplo21).
Elementos léxicos del lenguaje Java 1
El léxico de un lenguaje determina su vocabulario, es decir el conjunto de palabras que pertenecen
a dicho lenguaje. En este apartado se presentarán resumidamente los elementos léxicos más
importantes del lenguaje Java, en concreto:
−
−
−
−
−
−
−
Conjunto de caracteres-Unicode Escapes
Comentarios
Identificadores
Palabras reservadas
Separadores
Literales
Operadores
Los literales y operadores se describen muy brevemente ya que se explicarán con mayor extensión
en otros apartados. La mayor parte de los lenguajes de programación definen elementos léxicos
semejantes, si bien con algunas diferencias entre unos y otros.
Conjunto de caracteres.
Los programas Java se escriben en el estándar Unicode. Unicode define tres formas de codificación
bajo el nombre UTF o Formato de Transformación Unicode (Unicode Transformation Format):
−
−
−
UTF-8 — codificación orientada a byte con símbolos de longitud variable.
UTF-16 — codificación de 16 bits de longitud variable optimizada.
UTF-32 — codificación de 32 bits de longitud fija, y la más sencilla de las tres.
De estos tres, Java utiliza la codificación de caracteres en dos bytes (UTF-16). Con 16 bits se pueden
representar 216 = 65536 caracteres, de modo que Unicode codifica los alfabetos de la mayoría de los
lenguajes que se usan en el mundo. Un subconjunto importante de Unicode es el estándar ASCII de
codificación de caracteres en 7 bits que se corresponde con los 128 primeros caracteres de
Unicode.
Se pueden realizar operaciones aritméticas con caracteres:
− ‘A’ se representa como 65 en Unicode
− ‘F’ se representa como 70 en Unicode
− ‘A’ + 5 da como resultado el carácter ‘F’
Pero el resultado no es de tipo char, sino de tipo entero. Para utilizar el resultado como char es
necesario realizar un cambio de tipo de entero a char. Más adelante veremos cómo se hace esto.
1
Puede verse una descripción más completa en
http://java.sun.com/docs/books/jls/second_edition/html/lexical.doc.html#44591 que es la fuente principal de este
apartado.
Tema 2: Abstracción de datos.
38
Comentarios.
Los comentarios son frases que el compilador ignora y que se incluyen para documentar el
programa. El lenguaje Java soporta tres tipos de comentarios (véase tabla 3 y ejemplo).
Tabla 3: Comentarios en Java.
Tipo de comentario
Descripción
/* texto */
El compilador ignora cualquier cosa entre /* y */
/** documentación */
Indica un comentario para generar documentación. Como antes, el
compilador ignora cualquier cosa entre /** y */, pero la
herramienta javadoc de JDK usa estos comentarios para generar
de forma automática documentación.
El compilador ignora cualquier cosa desde // hasta el final de la
línea
// texto
/**
* La clase HolaMundoApp implementa una aplicación que
* simplemente escribe "¡Hola Mundo!" en la salida
estándar.
*/
class HelloWorldApp {
public static void main(String[] args) {
System.out.println("¡Hola Mundo!"); //Escribe la
frase.
}
/* se acabó el programa. */
}
Identificadores en Java.
Cada vez que el programador define un nuevo elemento en el programa debe declararlo
asignándole un nombre. Este nombre es el identificador de ese elemento.
Identificador: secuencia de caracteres que puede ser usada como un
nombre en un programa
Un identificador en Java es una serie de caracteres que consiste en letras, números, subrayados ( _ )
y signos de dólar ($) que no empieza con un número. Las “letras” incluyen los caracteres de todos
los alfabetos de los lenguajes codificados en Unicode.
Se permiten identificadores de cualquier longitud:
Pero_Que$_variablemaslarga_es_la_NUMERO4
y se distingue entre mayúsculas y minúsculas (case-sensitive):
Mivariable
≠ mivariable
Tema 2: Abstracción de datos.
39
Identificadores válidos:
Identificadores no válidos:
VariableNumero1
variableNumero2
$variable_numero_3
Variable1.2
7_variable
.variable
Palabras reservadas en Java.
Existen algunas palabras que aunque son secuencias válidas para definir identificadores no pueden
usarse como tales, ya que son parte del propio lenguaje. Estas palabras se denominan palabras
reservadas y en Java son las de la tabla 4. En la tabla 5 se las clasifica según su función en el
lenguaje.
Tabla 4: Palabras reservadas en Java
abstract
do
if
package
synchronized
boolean
double
implements
private
this
break
else
import
protected
throw
byte
extends
instanceof
public
throws
case
false
int
return
transient
catch
final
interface
short
true
char
finally
long
static
try
class
float
native
strictfp
void
const
for
new
super
volatile
continue
goto
null
switch
while
default
asssert
Tabla 5: Clasificación de las palabras reservadas en Java
Palabras reservadas para
tipos de datos
boolean,
double
Palabras reservadas para
modificadores
abstract, final, native, private, protected,
public, static, transient, synchronized,
volatile, strictfp
Palabras reservadas para
control de flujo
break, case, continue, default, do, while, for,
switch, if, else
Palabras reservadas para
valores predefinidos
true, false, null
byte,
char,
int,
long,
short,
float,
Palabras reservadas para
control de acceso
private, protected, public
Palabras reservadas para
manejo de excepciones
try, catch, finally, throw
Palabras reservadas para
clases y funciones
class, extends, implements, import, instanceof,
new, package, return, interface, this, throws,
void, super
Otras palabras reservadas
const, goto
Tema 2: Abstracción de datos.
40
Literales en Java.
Un literal es la representación de un valor de un tipo primitivo, una cadena de caracteres (tipo
String 1) o el valor null 2. En consecuencia, se definen los siguientes tipos de literales:
−
−
−
−
−
−
Literales enteros.
Literales de punto flotante.
Literales booleanos.
Literales de caracteres.
Literales String
Literal null
Estos literales se describen más adelante en esta lección.
Separadores en Java
Los separadores tienen la función de signos de puntuación. Sirven para agrupar elementos léxicos
de forma que se formen sentencias correctas en Java. Java tiene los siguientes separadores:
(
)
{
}
[
]
;
,
.
El uso y significado de estos separadores se irá viendo durante el curso.
Operadores en Java
Java dispone de un conjunto de 37 operadores, cuyo uso y significado se explicarán más adelante.
=
>
<
!
~
?
:
==
<=
>=
!=
&&
||
++
--
+
-
*
/
&
|
^
%
<<
>>
>>>
+=
-=
*=
/=
&=
|=
^=
%=
<<=
>>=
>>>=
1
String es un tipo referencia que modela cadenas de caracteres. Volveremos sobre el más adelante. De
momento sólo hace falta saber que hay literales asociados a este tipo de datos.
2
null es un valor referencia. Volveremos sobre el más adelante. De momento sólo hace falta saber que hay un
literal asociado a este valor.
Tema 2: Abstracción de datos.
Declaración de variables y constantes
41
Variables
Una variable identifica la localización en memoria en la que se almacena un
valor determinado.
Toda variable tiene un tipo, un nombre y un valor. La variable recibe su nombre y su tipo cuando se
declara y, opcionalmente, recibe un valor mediante una sentencia de asignación. El valor contenido
en la variable debe ser uno de los definidos en su tipo y sólo podrá usarse en las operaciones que
permita su tipo.
Para declarar una variable se escribe su tipo seguido del nombre que vamos a asignarle y
opcionalmente su valor:
Tipo nombreVariable;
int number;
short num = 7;
En el primer ejemplo (int number;) declaramos una variable de tipo int a la que damos el
nombre de number. El compilador reservará una zona de memoria para ella (4 bytes). Puesto que
number no recibe ningún valor, pueden pasar dos cosas:
1.
2.
Que reciba un valor por defecto (si es variable de instancia)
Que su valor esté indefinido (si es variable local de un método).
Todavía no es momento para explicar qué es una variable de instancia y qué es una variable local.
Más adelante, cuando veamos nuestro primer programa completo en Java, volveremos sobre este
asunto. En la tabla 6 se muestran los valores por defecto de las variables de instancia.
En el segundo ejemplo (short num = 7;) declaramos una variable de tipo short a la que damos
el nombre de num y asignamos el valor de 7. El signo = no denota en Java comparación, sino la
asignación de un valor a una variable. El compilador reservará una zona de memoria para num (2
bytes) y guardará en ella el valor 7 codificado en binario en 2 bytes.
La sintaxis de Java permite declarar más de una variable del mismo tipo en la misma línea,
separando con comas los identificadores:
Tipo nombreVar1 [=valor1], nombreVar2 [=valor2] … ;
int nroAprobados, nroSuspensos, nroEstudiantes;
int nAprobados = 2, nSuspensos = 0, nEstudiantes = 2;
Tema 2: Abstracción de datos.
42
Constantes
Una constante identifica una localización en memoria en la que se almacena
un valor determinado que no puede cambiar en tiempo de ejecución.
La forma que tiene Java de definir una constante es anteponiendo la palabra reservada final en la
declaración de una variable. Las constantes deben inicializarse asignándolas un valor cuando se
declaran:
final float PI = 3.141592;
// declaración válida de constante
final float FACTORDECORRECION;
inicialización.
//
declaración
NO
válida.
Falta
Tabla 6: Valores por defecto de las variables de instancia
Tipo
Valor inicial por defecto
Tipos numéricos enteros: byte, short, int,
long
0
Tipos numéricos reales: float, double
boolean
false
char
\u0000
Tipos referencia
null
0.0
Asignación y expresiones en Java.
Sentencia de asignación
Sentencia de asignación: Sentencia mediante la cual se asigna un valor a una variable.
variable = valor
// Asignación en Java
El valor de la variable puede asignarse cuando se declara o diferirse a la ejecución del programa.
Las asignaciones de valores se realizan mediante el operador =. Su significado es el siguiente: toma
el valor que aparece a su derecha (llamado frecuentemente rvalue: right-value) y lo copia en la
variable que aparece a su izquierda (llamada frecuentemente lvalue: left value).
Un rvalue es cualquier constante, variable o expresión que produce un valor. Un lvalue debe ser el
identificador de una variable.
int
int
a =
b =
4 =
a = 1;
b = 2;
b;
1.0;
a;
//
//
//
//
//
Declara variable a y la inicializa a 1.
Declara variable b y la inicializa a 2.
Copia el contenido de b en a.
Error. Intento de asignar un real a un entero.
Error. Lvalue no es un identificador de variable.
// Consideremos la declaración de tres variables
int operando1;
int operando2;
float operando3;
Tema 2: Abstracción de datos.
43
// Asignaciones válidas
operando1 = 7;
operando2 = 9;
operando3 = 4.7;
// Asignaciones no válidas
suma = operando1 + operando2;
operando1 = 7.83;
operando1 = operando3;
entero
// variable suma no declarada
// 7.83 no es de tipo entero
// operando3 no es de tipo
Asignación y expresiones
Expresiones: Secuencia de operandos y operadores que unidos según ciertas
reglas producen un resultado.
// Consideremos la declaración de tres variables
int operando1 = 1;
int operando2 = 2;
float operando3;
// Conversiones implícitas:
// Asignación curiosamente válida: Java convierte el resultado de
la suma en
// float y después se lo asigna a operando3.
operando3 = operando1 + operando2;
// Uso de la misma variable como lvalue y rvalue:
// Primero se ejecuta operando1 + operando2.
// Después se efectúa la asignación.
operando1 = operando1 + operando2;
El uso de una misma variable a ambos lados de una asignación es muy habitual. En el ejemplo
de arriba:
−
−
−
Los valores de operando1 y operando2 son 1 y 2 antes de la asignación.
Se efectúa la suma con esos valores y el resultado se asigna a operando1.
Después de efectuar la asignación el valor almacenado en operando1 es 3 y en
operando2 2.
Tema 2: Abstracción de datos.
44
Conversión de tipos
Las operaciones determinan el tipo a devolver a partir de los operandos:
4 / 3 -> 1
(int, int) -> int
Pero a veces, no es el resultado deseado. En Java existen dos formas de conversión de tipos
−
−
Implícita (definida en el lenguaje) y realizada automáticamente.
Explícita (casting o promoción), forzada por el programador.
onversión explícita (casting)
(nombre de tipo) expresión
Convierten el valor de la expresión a un valor del tipo entre paréntesis.
(char)98
(int)10.0
(double)10
// devuelve ´b´
// devuelve el entero 10
// devuelve el double 10.0
Conversiones implícitas
Sólo se aplica a tipos de datos primitivos y de tipos “pequeños” a “grandes”:
−
−
−
byte a short, int, long, float, o double
short a int, long, float o double
char a int, long, float, o double
−
int
−
long a float o double
−
a long, float o double
float a double
Se puede perder información: LOS DÍGITOS MENOS SIGNIFICATIVOS PUEDEN PERDERSE
−
−
En el paso de long a float o double
En el paso de int a float
La promoción explícita tiene prioridad sobre la implícita.
int A = 5;
int B = 4;
int C = A / B;
float x = (float)(A/B);
x = (float)A / B;
// valor de C igual a 1
// valor de x igual a 1.0;
// valor de x igual a 1.25;
Tema 2: Abstracción de datos.
45
Literales1
Literales booleanos
Sólo hay dos valores booleanos: true y false.
Literales enteros
Un literal entero puede expresarse en decimal (base 10), hexadecimal (base 16) y octal (base 8).
Decimal:
Hexadecimal:
0xC0B0L
Octal:
−
0
2
0xDadaCafe
1996
0x00FF00FF
0x00FF00FF, 0x100000000L,
0372
0372, 0l
0777L
Un literal entero es de tipo int salvo que vaya precedido por el sufijo l o L
tipo int:
tipo long:
−
−
−
−
−
100, 0xC0B0, 0372
L100, l200, 0l
0777L, 0xC0B0L
Por defecto el literal se considera expresado en decimal.
Para indicar que un literal entero está en hexadecimal se pone delante 0x o 0X
Para indicar que un literal entero está en octal se comienza por 0:
Todos los literales enteros expresados en octal tienen al menos dos digitos.
Si en los literales aparecen caracteres no permitidos o exceden el valor máximo permitido para
el tipo se produce un error de compilación.
Literales de punto flotante.
Los literales en punto flotante se escriben como números decimales con un exponente opcional:
digitos.[digitos][(e|E)entero]
23.f
−
−
−
.5
0.0
3.1415
1e-9
1e9
1e+9
1E12
El tipo por defecto es double. Se puede indicar el tipo con un sufijo:
Las letras f y F indican que el literal es float:
Las letras d Y D indican que el literal es doublé:
1e-9f 1E12F
1e-9d 1E12D
Se produce un error de compilación si:
Un literal representa un número tan grande que su representación en el estándar IEEE754 es
infinito.
1
Tomado de http://java.sun.com/docs/books/jls/second_edition/html/lexical.doc.html
Tema 2: Abstracción de datos.
46
Un literal representa un número tan pequeño que su representación en el estándar IEEE754 es
cero.
Existen dos constantes predefinidas Float.NaN y Double.NaN (NaN: Not a Number) que
representan valores que resultan de expresiones aritméticas, pero que no se corresponden con un
número real (p.e: 0/0).
Literales de caracteres.
Los caracteres ASCII pueden escribirse tal cual entre comillas simples. Todos los caracteres (ASCII o
no) pueden escribirse utilizando su codificación en octal o en hexadecimal:
Caracteres ASCII: ‘1’, ‘a’, ‘%’
Caracteres en hexadecimal: \u seguido de 4 dígitos hexadecimales que representan los 4 bytes en
que se codifica el carácter: ‘\u5496’
Existen una serie de caracteres especiales que pueden escribirse utilizando “secuencias de escape”
(tabla 7)
Tabla 7: Secuencias de escape
Secuencia
de escape
Unicode
Descripción
\n
\u000A
Nueva línea
\b
\u0008
\f
\u000C
\’
\u0027
\t
\u0009
\r
\u000D
\\
\u005C
\”
\u0022
Tabulador
Retroceso (Backspace)
Retorno de carro
Nueva página (Form feed)
\ (Backslash)
Comilla simple
Comilla doble
Literales de cadenas de caracteres (literales String).
El tipo String no es un tipo primitivo de Java, sino un tipo referencia. String es una clase que
modela cadenas de caracteres. Cada cadena de caracteres es un objeto de la clase (o tipo) String.
A pesar de ello, las constantes de tipo String pueden escribirse como literales, cosa que no ocurre
con ningún otro tipo referencia en Java.
Un literal String consiste en una secuencia de caracteres, incluyendo secuencias de escape,
escrita entre comillas dobles:
“Soy un literal String”
“Soy \t un literal String\n con un salto de línea y un tabulador”
“\u5469 \u5561 Soy un String con dos caracteres chinos”
“\”Soy un literal String entre comillas \””
""
// the empty string
"\""
// a string containing " alone
Tema 2: Abstracción de datos.
"This is a string"
// a string containing 16 characters
"This is a " +
// actually a string-valued constant expression,
"two-line string"
// formed from two string literals
47
Operadores y expresiones 1
Operadores aritméticos
Los operadores aritméticos de la tabla 8 pueden aplicarse a todos los tipos numéricos (enteros y de
punto flotante). Los datos del tipo char pueden participar en las operaciones aritméticas (Java los
convierte en enteros). Todos los operadores de la tabla son operadores binarios (operan sobre dos
operandos).
Tabla 8: Operadores aritméticos
Operación
Operador
Expresión → Resultado
Suma
+
f + 7
Resta
-
p - c
Multiplicación
*
b * m
División
/
5 / 2 → 2
Módulo (Resto)
%
5.0/2 → 2.5
7 % 3 → 1
7.0 % 3 → 1
(-7) % 3 → -1
(-7.1) % 3 → -1,09999
Java aplica los operadores de las expresiones aritméticas en el mismo orden que en álgebra.
Reglas de precedencia de operadores aritméticos
1.
Las expresiones contenidas entre paréntesis se evalúan primero, aplicando primero los
operadores del par de paréntesis más interno.
3.
A continuación se aplican las operaciones de suma y resta de izquierda a derecha.
2.
1
A continuación se aplican las operaciones de multiplicación, división y residuo de izquierda a
derecha.
Apartado tomado en su mayoría de “Object Oriented Software Development Using Java. Principles,
Patterns and Frameworks”, Xiaoping Jia.
Tema 2: Abstracción de datos.
48
Cuando comentábamos las características de los lenguajes fuertemente tipados decíamos que si se
detectaba una violación de tipos en tiempo de ejecución se debía llevar a cabo una acción bien
definida. Al realizar operaciones aritméticas puede ocurrir que el resultado esté fuera de rango
(desbordamiento) o que se intenten realizar operaciones absurdas (p.e: 0/0). Veamos que hace Java
en estos casos.
Las operaciones aritméticas en Java nunca se desbordan ni por arriba ni por abajo: si un valor
excede el rango de su tipo, la operación devuelve un resultado que es el resultado que debería dar
la operación módulo el rango de su tipo:
Valor máximo de int: 2147483647
2147483647 + 1 → -2147483648
2147483647 + 2 → -2147483647
2147483647 * 2 → -2
Las operaciones aritméticas enteras x/y y x%y producen un error (excepción) llamado
ArithmeticException cuando y es igual a 0 1.
Las operaciones en punto flotante no producen errores (excepciones) en ninguna circunstancia. En
lugar de ello devuelven valores especiales definidos en el estándar IEEE754. El programa no dejará
de funcionar ni siquiera ante divisiones por cero. El estándar IEEE754 define dos números mágicos:
NaN (not a number) e infinito. Las reglas aplicables en la división y multiplicación de números en
punto flotante cuando ninguno de los operandos es NaN se resumen en la tabla 9.
Tabla 9: Casos especiales de multiplicación y división
de números en punto flotante
x
y
x/y
x*y
Finito
±0
±∞
±0
Finito
±∞
±0
±∞
±0
±0
±0
±∞
±∞
±∞
±∞
Finito
NaN
±∞
±0
±∞
NaN
±∞
±0
NaN
Cuando uno de los dos operandos en NaN el resultado es NaN.
1
La detección, captura y tratamiento de excepciones se verán en la lección [].
Tema 2: Abstracción de datos.
Operadores de incremento y decremento
49
Las operaciones en las que se resta o suma 1 a una variable son tan comunes que Java y otros
lenguajes definen operadores especiales para abreviar su escritura. La tabla 10 resume los
operadores de incremento y decremento de Java. Se pueden aplicar a todos los tipos numéricos.
Tabla 10: Operadores de incremento y decremento
Operador
Operación
Ejemplo
Significado
++
Preincremento
++a
Incrementa a en 1 y luego usa el valor de a en la
expresión donde a reside.
--
Predecremento
--a
Decrementa a en 1 y luego usa el valor de a en
la expresión donde a reside.
Posincremento
Posdecremento
a++
a--
Utiliza el valor de a en la expresión donde a
reside y después incrementa a en 1
Utiliza el valor de a en la expresión donde a
reside y después decrementa a en 1
Operadores de igualdad y relacionales
Los operadores relacionales se resumen en la Tabla 11:
Tabla 11: Operadores relacionales.
Operador
Ejemplo
Significado
==
x == y
x es igual a y
!=
x != y
x distinto de y
>
x > y
x mayor que y
<
X < y
x menor que y
>=
x >= y
x mayor o igual que y
<=
x <= y
x menor o igual que y
Todas las expresiones relacionales devuelven un valor booleano (true o false).
Los operadores == y != se pueden utilizar con cualquier tipo. Los operadores de comparación se
utilizan sólo con tipos numéricos y caracteres.
Tema 2: Abstracción de datos.
50
Operadores lógicos
Los operadores lógicos se resumen en la tabla 12. Se aplican siempre sobre operandos booleanos y
devuelven un resultado booleano.
Tabla 12: Operadores lógicos.
Operación
lógica
Operador/
Ejemplo
AND lógico
&&
A && B
OR lógico
||
A || B
NOT lógico
!
!A
Significado
true si ambas condiciones son verdaderas
false si una condición es falsa.
true si una de las condiciones es verdadera.
false si ambas condiciones son falsas.
true si A es falsa
false si A es verdadera.
Los operadores lógicos se evalúan en cortocircuito, es decir:
−
−
En exprA && exprB, exprB sólo se valúa si exprA es true
En exprA || exprB, exprB sólo se evalúa si ExprA es false
Como consecuencia de lo anterior es aconsejable:
−
No utilizar expresiones dependientes (la verdad o falsedad de una de ellas depende de la
verdad o falsedad de la otra). He aquí un ejemplo de lo que NO debe hacerse:
int counter = 0;
int media = 5;
if (counter != 0 && media/counter++ > 5) { ... }
−
No realizar operaciones en las expresiones a evaluar, ya que podrían no ejecutarse:
sexo == varon || ++edad > 65
−
1
En expresiones con && si las condiciones son independientes 1 colocar primero la que tenga
mayores probabilidades de ser falsa.
Deben procurar que siempre sea así.
Tema 2: Abstracción de datos.
−
51
En expresiones con || si las condiciones son independientes colocar primero la que tenga
mayores probabilidades de ser verdadera.
Operadores lógicos de bits (bitwise operators) y de desplazamiento de bits
(shift operators)
Operadores lógicos de bits.
Los operadores lógicos de bits (bitwise) se resumen en la tabla 13. Se aplican sobre operandos
booleanos o enteros.
Cuando se aplican a operandos booleanos devuelven un resultado booleano equivalente a la
operación lógica correspondiente, pero con una diferencia respecto de los operadores lógicos: no se
evalúan en cortocircuito. Por ejemplo, en una expresión exprA & exprB siempre se evalúan
ambos operandos, independientemente de si la primera expresión evaluada es true o false.
Cuando se aplican a operandos enteros operan sobre cada bit individual y devuelven un resultado
entero.
Tabla 13: Operadores lógicos de bits.
Operación
lógica
AND
OR
OR
Exclusivo
NOT
Operador/
Ejemplo
&
A & B
|
A | B
^
A ^ B
∼
∼A
Significado
A y B booleanos: como &&, pero sin evaluación en cortocircuito
A y B enteros. A = 0xff, B= 0x55 → A & B = 0x55
A y B booleanos: como || pero sin evaluación en cortocircuito
A y B enteros. A = 0xAA, B= 0x55 → A | B = 0xFF
A y B booleanos.
true si una condición es verdadera y la otra falsa.
false si ambas condiciones son verdaderas o ambas son falsas.
A y B enteros. A = 0xAA, B= 0x55 → A ^ B = 0xFF
A = 0xFF, B= 0x55 → A ^ B = 0xAA
A booleano: como !
A entero. A = 0x55 → ∼A = 0xAA
Tema 2: Abstracción de datos.
52
Operadores de desplazamiento de bits.
Los operadores lógicos de desplazamiento de bits se resumen en la tabla 14. Se aplican
exclusivamente sobre operandos enteros.
Tabla 14: Operadores de desplazamiento de bits.
Operación
Operador/
Ejemplo
Significado
Desplazamiento de bits a
la izquierda
x << k
Desplaza los bits de x k posiciones a la izquierda
rellenando con ceros la parte derecha:
0xff << 4 → 0xf0
Desplazamiento de bits a
la derecha con signo
x >> k
Desplaza los bits de x k posiciones a la derecha rellenando
la parte derecha con el valor del bit que está en el extremo
izquierda (bit de signo)
Ver ejemplo
Desplazamiento de bits a
derecha sin signo
x >>> k
Desplaza los bits de x k posiciones a la derecha rellenando
con ceros la parte izquierda:
Ver ejemplo
Desplazamientos de bits:
0xff << 4 = 0xff0 = 111111110000
0xff >> 4 = 0xf = 1111
0xff >>> 4 = 0xf = 1111
-0xf5 = 0xffffff0b =
-0xf5 << 4 = 0xfffff0b0 =
-0xf5 >> 4 = 0xfffffff0 =
11111111111111111111111100001011
11111111111111111111000010110000
11111111111111111111111111110000
Relleno a izquierda con bit de signo
-0xf5 >>> 4 = 0xffffff0 =
00001111111111111111111111110000
Relleno a izquierda con ceros
Tema 2: Abstracción de datos.
53
Operadores de asignación
Un operador de asignación puede ser el símbolo = o cualquiera de los que aparecen en la tabla 15.
Todos ellos están formados por el signo = y un operador binario.
Tabla 15: Operadores de asignación.
Operador
Expresión
Expresión equivalente
+=
X += 7
X = X + 7
-=
X -= 7
X = X - 7
*=
X *= 7
X = X * 7
/=
X /= 7
X = X / 7
%=
X %= 7
X = X % 7
<<=
X <<= k
X = X << k
>>=
X >>= k
X = X >> k
>>>=
X >>>= k
X = X >>> k
&=
X &= 0xff
X = X & 0xff
^=
X ^= 7
X = X ^ 7
|=
X |= Y
X = X | Y
Los operadores de asignación y los de incremento y decremento son lo que en la jerga de los
programadores se llama “syntactic sugar”. Realmente no son necesarios, basta con la sentencia de
asignación. En general, no está bien visto que en un programa una misma cosa pueda hacerse de
formas diferentes, pero estos operadores responden a un tipo de asignación tan común que su
inclusión en el lenguaje está plenamente justificada. Facilitan en gran medida la labor del
programador y la hacen más segura. Se recomienda su uso.
El operador condicional ?:
Condición ? Expresion1 : Expresion2
Tres operandos:
•
•
•
Condición:
Expresión booleana (verdadero o falso)
Expresión 2:
Resultado si Condición es falsa
Expresión 1:
Resultado si Condición es verdadera
Tema 2: Abstracción de datos.
Resumen de operadores. Asociatividad y precedencia
54
Finalmente, la tabla 16 resume los operadores, su predecedencia (está ordenada de mayor a
menor) y asociatividad.
Tabla 16: Precedencia y asociatividad de operadores.
Operadores
Asociatividad
Tipo
()
Izda Dcha
Paréntesis
++ -- !
Dcha Izda
Unarios
* / %
Izda Dcha
Multiplicativos
+ -
Izda Dcha
Aditivos
< <= > >=
Izda Dcha
Relacionales
== !=
Izda Dcha
De igualdad
&
Izda Dcha
And bitwise
^
Izda Dcha
Xor bitwise
|
Izda Dcha
Or bitwise
&&
Izda Dcha
And lógico
||
Izda Dcha
Or lógico
?:
Dcha Izda
Condicional
= += -= …
Dcha Izda
Asignación
Tema 2: Abstracción de datos.
Primer programa en Java.
55
Java es un lenguaje completamente orientado a objetos: todos los elementos de un programa Java
son objetos. Los objetos se definen mediante clases que, a su vez, son también objetos, aunque con
características especiales. Sin embargo, la asignatura está organizada de forma que hay que
programar en Java antes de saber siquiera lo que es un objeto. Esto, sin embargo, es un problema
mucho menor de lo que parece:
1.
2.
3.
Todo el código que necesitamos puede definirse en el interior de clases y definir una clase en
Java es muy sencillo.
Java posee un mecanismo para que parte o la totalidad del código definido en una clase pueda
utilizarse sin necesidad de crear objetos.
El tipo de ejemplos que van a verse hasta el tema 5 pueden encapsularse dentro de clases muy
simples.
Aún así algo tenemos que saber de las clases y de los objetos porque en Java son ineludibles.
Fijémonos en el cuadro de abajo que muestra en un ejemplo muy sencillo cómo serán nuestros
primeros programas en Java. A pesar de su sencillez, para poder entender el ejemplo hay que
adelantar, aunque de forma muy resumida, muchos de los conceptos que se verán en temas
sucesivos. Los detalles de edición, compilación y ejecución se explican en el manual de prácticas.
import java.util.*;
public class HelloDate {
static Date hoy;
static int x = 1;
public static void main(String[] args) {
hoy = new Date();
String s = “Hola, la fecha de hoy es:”;
System.out.println(s);
System.out.println(hoy);
}
}
Importación de paquetes: import java.util.*;
El código de un programa casi nunca está ubicado en un único fichero, sino que se organiza en
múltiples ficheros que a su vez se organizan en múltiples directorios. Cuando el código escrito en
un fichero necesita utilizar el código ubicado en otro fichero tiene que importarlo. En Java los
ficheros se importan mediante la sentencia import.
La primera línea del ejemplo indica que importamos todo el código incluido en el paquete
java.util. Aunque no es estrictamente cierto, podemos asimilar de momento los conceptos de
paquete y directorio. Si asumimos esto import java.util.* significa que importamos todo el
código visible definido en los ficheros del directorio java.util. Realmente, de todos los
elementos definidos en java.util sólo utilizamos la clase Date que modela fechas. Podríamos
haber importado exclusivamente este elemento cambiando el * por el nombre del elemento a
importar (import java.util.Date). Hacer esto clarifica las dependencias de nuestro código y
hace la compilación más rápida. El programa en sí es igual de eficiente tanto si importamos
paquetes completos como si sólo importamos los elementos que necesitamos.
Tema 2: Abstracción de datos.
56
Clases: public class HelloDate.
Con excepción de las sentencias import todo el código de un programa Java está encapsulado
dentro de clases. La forma de definir una clase en Java es:
modificadorAcceso class nombreDeLaClase {
}
códigoDelaClase
La palabra public es un modificador de acceso que indica que la clase es visible desde cualquier
otro paquete. class es una palabra reservada que indica que estamos definiendo una clase y
HelloDate es el nombre de nuestra clase.
Tipos referencia en Java: static Date hoy;
Date es un tipo de datos, pero no un tipo de datos primitivo, sino un tipo referencia. Los tipos
referencia proporcionan acceso a los objetos y por tanto son los tipos más comunes de Java y en
general de todos los lenguajes orientados a objetos. Los tipos referencia se van a estudiar con cierta
profundidad en el tema 6, sin embargo, puesto que en Java no se pueden eludir ni siquiera en los
ejemplos más sencillos, algo hay que saber ya de ellos. No se trata de dar ahora muchos detalles,
sólo algunas nociones básicas.
Consideremos las variables hoy y x. hoy identifica a un objeto de tipo Date que modela fechas y x
identifica a una variable de tipo primitivo int. Cuando en el programa utilizamos el identificador x
nos estamos refiriendo directamente a la celda de memoria que representa x y que contiene,
porque así se ha inicializado, el valor 1. Pero cuando utilizamos el identificador hoy NO nos
estamos refiriendo directamente al objeto al que identifica, porque hoy no contiene al objeto en sí,
sino una referencia al objeto. Si echáramos un vistazo a los contenidos de las posiciones de memoria
identificadas por x y hoy veríamos que en x guardamos el valor 1, y que hoy no contiene al objeto
sino una referencia a las celdas en las que realmente se encuentra el objeto.
x
1
objeto
20 sept 2010
hoy
Referencia al objeto
Cuando hacemos la declaración Date hoy estamos creando una referencia que no apunta a ningún
objeto. A partir de su declaración, la referencia ya existe, pero no hemos dicho a quien apunta y por
tanto no apunta a nada. Esto se expresa diciendo que la referencia es nula (null). Para que hoy
apunte a algo tenemos que decirle a que objeto apunta y para tener un objeto al que apuntar
primero hay que crearlo (new Date()). Una vez creado el objeto la sentencia de asignación hace
que hoy apunte a ese objeto (hoy = new date()).
Tema 2: Abstracción de datos.
57
Aunque la explicación que se ha dado de los tipos referencia es muy incompleta nos va a dar los
argumentos suficientes para entender algunas cosas de nuestros primeros programas en Java que
de otro modo serían un misterio.
Miembros estáticos: static
En una clase Java se pueden definir dos cosas: variables y métodos. En principio estas variables y
métodos pertenecen a los objetos de dicha clase, de modo que sólo podemos acceder a ellos a través
del objeto al que pertenecen. Pero ¿y si no queremos o no nos conviene utilizar objetos? ¿Podemos
definir variables y métodos que puedan utilizarse aunque no existan objetos? Sin entrar de
momento en más explicaciones, diremos que la respuesta es afirmativa y que la forma de hacerlo es
marcar a la variable o método como static. En nuestro ejemplo hay dos variables (int y hoy) y
un método (main) todos ellos marcados como static.
El método principal de un programa Java:
public static void main(String[] args)
Se acaba de decir que todo el código de un programa Java está encapsulado dentro de clases y que
en una clase Java se pueden definir dos cosas: variables y métodos. Un método encapsula un
fragmento de código ejecutable. Cada vez que se invoca un método se ejecuta el código encapsulado
en el mismo. El método principal de un programa es su método main. Desde el método main se
llama al resto del código del programa. Cuando en un programa hay más de una clase con un
método main habrá que indicar al compilador cuál es la clase principal del programa, para que
ejecute el método de dicha clase y no otro. Observemos que:
−
−
−
−
−
La clase principal, aquella que ubica el método main que representa al programa debe ser
pública public.
El método principal es público.
El método principal es static (independiente de los objetos)
El método principal no devuelve ningún resultado (ese es el significado de la palabra void)
Al método principal pueden pasársele datos (ese es el significado de String [] args)
aunque de momento no vamos a hacerlo.
Creación de objetos
En el código de main aparecen dos sentencias de creación de objetos:
hoy = new Date();
String s = “Hola, la fecha de hoy es:”;
Los objetos se crean a partir de “métodos constructores” que tienen el mismo nombre que su clase.
Hay una excepción a esta regla: los objetos de la clase String. La clase String modela cadenas de
caracteres y puede crearse un objeto de la clase String simplemente indicando a qué cadenas de
caracteres representa, tal y como se hace en el ejemplo.
Tema 2: Abstracción de datos.
Variables de instancia y locales
58
La variable s presenta una diferencia con hoy: ha sido declarada dentro del método main. Las
variables pueden ser locales, definidas dentro de un método, o de instancia definidas fuera de los
métodos. La diferencia estriba en que las variables locales sólo pueden utilizarse dentro del método
en el que han sido definidas y las de instancia pueden utilizarse en todos 1 los métodos de una clase.
Además, las variables de instancia reciben un valor por defecto (tabla 6) en tanto que las locales si
no se inicializan tienen un valor aleatorio.
Invocación de los métodos de un objeto.
En el código de main aparecen dos invocaciones a un método de un objeto:
System.out.println(s);
System.out.println(hoy);
El objeto en cuestión se identifica mediante la referencia System.out y el método es println.
Estas sentencias pueden (y deben) interpretarse como un mensaje que mandamos al objeto
System.out para que imprima en salida estándar un String y una fecha. El mensaje sería
println. De hecho cada método de un objeto representa un mensaje que dicho objeto puede
recibir. El código que hay dentro del método es la respuesta que da el objeto a ese mensaje.
El paquete java.lang
El alumno puede estar ahora preguntándose de que chistera nos hemos sacado System.out.
Podría estar en java.util puesto que hemos importado todo lo que hay en dicho paquete. Sin
embargo no es así. Hay un paquete cuyas clases se encuentran disponibles en todo fichero Java sin
necesidad de importarlo. Dicho paquete es java.lang. Para saber que hay en java.lang basta
con conectarse a la página de sun 2 y mirar la documentación del paquete 3. De igual manera pueden
verse los contenidos de cualquier paquete. Si mirásemos la documentación de java.util
veríamos que incluye la clase Date. Es fácil bajarse la documentación de todos los paquetes de Java
desde sun y es igualmente fácil consultarla remotamente on-line.
Volviendo al paquete java.lang, puede observase que contiene la clase System y que en dicha
clase hay definido un objeto out que pertenece a una clase PrintStream en la cual se define el
método println.
1
Matizaremos esto cuando veamos con mayor profundidad el significado de static.
2
Se asume que los alumnos dispone de un navegador y lo saben utilizar.
http://download.oracle.com/javase/1.4.2/docs/api/java/lang/package-summary.html
3
Tema 3: Abstracción de control.
Lección 3: Abstracción de control
59
Objetivos
Presentar la abstracción de control.
Describir las reglas de la programación estructurada y las estructuras de selección y repetición.
Introducir parte del vocabulario básico de la algoritmia y de los programas estructurados.
Aprender a utilizar las reglas de la programación estructurada para diseñar, implementar y probar
pequeños programas. Diseño mediante refinamientos sucesivos.
Contenido
Abstracción y lenguajes de programación.
Algoritmos.
Sentencias en Java.
Sentencias de selección en java.
Sentencias de iteración en Java.
Algoritmos y refinamientos sucesivos.
Construcción de programas estructurados.
Tema 3: Abstracción de control.
Abstracción y lenguajes de programación.
60
Abstracción de control 1
En las ciencias de la computación, el flujo de control se refiere al orden en el que se ejecutan las
sentencias de un programa. La regla general es que las instrucciones se ejecuten sucesivamente una
tras otra, pero dependiendo de que se cumpla alguna condición es posible que diversas partes del
programa se ejecuten o no. Las sentencias de control de flujo pueden clasificarse de la siguiente
manera:
−
−
−
−
−
−
Continuar con la siguiente sentencia.
Salto incondicional a una sentencia.
Salto condicional: ejecución de un conjunto de sentencias solo si se cumple una condición.
Bucle: ejecución de un conjunto de sentencias mientras se cumpla una determinada
condición.
Llamada a subrutina y retorno: salto a ejecución de un subprograma y retorno al punto de
llamada.
Parada del programa.
Habría que añadir un mecanismo adicional de alteración del flujo de un programa: las
interrupciones y señales. Las señales e interrupciones son mecanismos de bajo nivel que alteran el
flujo de control de forma similar a las llamadas a subrutina, pero que ocurren como respuesta a un
evento externo en lugar de cómo respuesta a la ejecución de una sentencia de control de flujo 2, por
lo que no se han incluido en la lista.
A nivel de código máquina o ensamblador, las instrucciones de control de flujo trabajan usualmente
alterando el valor del contador de programa. Sin la abstracción de control el programador tendría
que especificar a nivel de registros y posiciones de memoria cada una de las acciones de control
arriba enumeradas y tendría que hacerlo de forma diferente para cada computador, ya que
diferentes procesadores utilizan diferentes conjuntos de instrucciones para expresar saltos,
bifurcaciones y llamadas a subrutinas.
Los lenguajes de programación más antiguos solían apoyarse en una sola instrucción para
modificar la secuencia de ejecución de las instrucciones mediante una transferencia incondicional
de su control (con la instrucción goto, del inglés "go to", que significa "ir a"). Pero estas
transferencias arbitrarias del control de ejecución hacen los programas muy poco legibles y difíciles
de comprender. A finales de los años sesenta, surgió una nueva forma de programar que reduce a la
mínima expresión el uso de la instrucción goto y la sustituye por otras más comprensibles. Esta
forma de programar, llamada programación estructurada, se basa en un famoso teorema,
desarrollado por Edsger Dijkstra, que demuestra que todo programa puede escribirse utilizando
únicamente las tres estructuras básicas de control siguientes:
−
−
−
Secuencia: el bloque secuencial de instrucciones, instrucciones ejecutadas sucesivamente, una
detrás de otra.
Selección: la instrucción condicional con doble alternativa, de la forma "if condición then
instrucción-1 else instrucción-2".
Iteración: el bucle condicional "while condición do instrucción", que ejecuta la instrucción
repetidamente mientras la condición se cumpla.
Los programas que utilizan sólo estas tres instrucciones de control básicas o sus variantes, pero no
la instrucción goto, se llaman estructurados. Ésta es la noción clásica de lo que se entiende por
programación estructurada (llamada también programación sin goto) que hasta la aparición de la
programación orientada a objetos se convirtió en la forma de programar más extendida. Una
Fuentes principales: http://en.wikipedia.org/wiki/Control_flow y
http://www.mcgraw-hill.es/bcv/guide/capitulo/8448148703.pdf
2 La captura de interrupciones y la programación de las rutinas de servicio a las mismas queda fuera del
alcance de la asignatura.
1
Tema 3: Abstracción de control.
61
característica importante en un programa estructurado es que puede ser leído en secuencia, desde
el comienzo hasta el final, sin perder la continuidad de la tarea que cumple el programa. Este hecho
es importante porque es mucho más fácil comprender completamente el trabajo que realiza una
función determinada si todas sus instrucciones son contiguas y están encerradas por un bloque. La
facilidad de lectura, de comienzo a fin, es una consecuencia de utilizar solamente tres estructuras
de control, y de eliminar la instrucción de transferencia de control goto. De hecho, la programación
estructurada es una repuesta al “código spaghetti” en el que no hay una estructura lógica bien
definida. Con la programación estructurada cada bloque de código tiene un punto de entrada y un
punto de salida bien definidos y define un ámbito para declarar variables que sólo son accesibles
dentro de dicho ámbito, lo que incrementa la seguridad y legibilidad de los programas.
Algoritmos1.
La programación estructurada facilita el planteamiento de problemas que pueden ser resueltos
mediante la definición de algoritmos. Estos problemas son muy comunes en muchos dominios de
aplicación por lo que la algoritmia es una de las ramas más importantes de la informática. Puesto
que las estructuras de control nos van a permitir programar algoritmos, este es un buen tema para
introducirlos. Empecemos por una definición:
Algoritmo: conjunto de instrucciones o reglas bien definidas, ordenadas y finitas que permite
realizar una actividad mediante una serie de pasos sucesivos. Dados un estado inicial y una
entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución.
Los algoritmos son el objeto de estudio de la algoritmia
Expresión de los algoritmos.
Los algoritmos pueden ser expresados de muchas maneras, incluyendo entre otras a:
−
−
−
−
−
El lenguaje natural.
Los diagramas de flujo
El pseudocódigo.
Notaciones formales.
Los lenguajes de programación.
Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El pseudocódigo y los
diagramas de flujo evitan muchas ambigüedades del lenguaje natural. La descripción de un
algoritmo usualmente se hace en tres niveles:
−
−
−
Descripción de alto nivel. Se establece el problema, se selecciona un modelo matemático y
se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo
detalles.
Descripción formal. Se usa pseudocódigo, diagramas de flujo o una notación formal para
describir la secuencia de pasos que encuentran la solución.
Implementación. Se muestra el algoritmo expresado en un lenguaje de programación
específico.
También es posible incluir un teorema que demuestre que el algoritmo es correcto, un análisis de
complejidad o ambos. La complejidad de los algoritmos será comenta brevemente más adelante.
1
Tomado principalmente de http://es.wikipedia.org/wiki/Algoritmo
Tema 3: Abstracción de control.
62
Diagramas de flujo.
Los diagramas de flujo son descripciones que usan símbolos conectados con flechas para indicar la
secuencia de instrucciones. Los símbolos utilizados siguen un estándar ISO.
Los diagramas de flujo se usan para representar algoritmos pequeños, ya que abarcan mucho
espacio y su construcción es laboriosa. Por su facilidad de lectura se utilizan frecuentemente como
introducción a los algoritmos, para la descripción de las estructuras de un lenguaje y para la
descripción de procesos a personas ajenas a la computación. La figura 1 muestra un algoritmo para
calcular la raíz cuadrada de un número x. Se incluye el significado de los símbolos más utilizados.
Óvalo: Inicio y término (Abre y/o cierra el
diagrama).
Rectángulo: Actividad (Representa la ejecución de
una o más actividades o procedimentos).
Rombo: Decisión (Formula una pregunta o cuestión).
Círculo: Conector (Representa el enlace de
actividades con otra dentro de un procedimiento).
Triangulo boca abajo: Archivo definitivo (Guarda
un documento en forma permanente).
Triangulo boca arriba: Archivo temporal
(Proporciona un tiempo para el almacenamiento del
documento).
Figura 1: Diagrama de flujo
Pseudocódigo
El pseudocódigo (falso código) asemeja a un lenguaje de programación pero con algunas
convenciones del lenguaje natural. Tiene varias ventajas con respecto a los diagramas de flujo,
entre las que se destaca el poco espacio que se requiere para representar instrucciones complejas.
El pseudocódigo no está regido por ningún estándar. En este tema veremos algunos ejemplos de
expresión de algoritmos en pseudocódigo.
Notaciones formales
La manera más precisa de expresar un algoritmo es mediante un lenguaje formal. También es la que
requiere más esfuerzo y formación. Las notaciones formales quedan fuera del alcance de la
asignatura, no obstante, merece la pena mencionar algunas como los lenguajes lógicos formales, la
máquina de Turing 1, las máquinas de estados finitas 2 y las funciones recursivas. Estos modelos
eliminan toda ambigüedad y son independientes de cualquier computadora y de cualquier
implementación.
1
La máquina de Turing es uno de los artefactos más ingeniosos y curiosos utilizados en las ciencias de la
computación.
2
Las máquinas de estados finitas, incluidas en la teoría de autómatas, se utilizan para describir el comportamiento de
los circuitos electrónicos secuenciales, de modo que tendrán ocasionar de estudiarlas en otras asignaturas.
Tema 3: Abstracción de control.
Complejidad algorítmica.
63
La teoría de la complejidad computacional estudia los recursos requeridos durante el cómputo de
un algoritmo para resolver un problema. El objetivo de esta sección es fundamentalmente la
introducción de terminología. El estudio de la complejidad algorítmica, salvo para ejemplos muy
concretos, está mucho más allá del alcance de la asignatura.
Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se
resuelven en un tiempo que se relaciona linealmente con su tamaño. Hoy en día las computadoras
pueden resolver problemas mediante algoritmos que tienen como máximo una complejidad o coste
computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de
ejecución es polinómica. Los problemas se clasifican según esto en P y NP:
−
−
Problemas de la clase P: problemas de complejidad polinómica, que pueden ser resueltos por
un computador en un tiempo finito.
Problemas de la clase NP: problemas de complejidad superior a la polinómica, en general
complejidad factorial o combinatoria, que no pueden ser resueltos por nuestras computadoras.
Hay muchos problemas aparentemente sencillos que caen dentro de esta categoría 1. Los
problemas que pueden ser resueltos en teoría, pero no en práctica, se llaman intratables.
La complejidad temporal de un problema es el número de pasos que toma resolver una instancia
del problema utilizando el algoritmo más eficiente posible. Intuitivamente, si se toma una instancia
con entrada de longitud n que puede resolverse en n² pasos, se dice que ese problema tiene una
complejidad en tiempo de n² o cuadrática. Por supuesto, el número exacto de pasos depende de la
máquina en la que se implementa, del lenguaje utilizado y de otros factores. Para no tener que
hablar del coste exacto de un cálculo se utiliza la notación O. Cuando un algoritmo tiene un coste en
tiempo O(n²) en una configuración de computador y lenguaje dado, este coste será el mismo en
todos los computadores, de manera que esta notación generaliza la noción de coste
independientemente del equipo utilizado. Por ejemplo:
−
−
−
Acceder a un elemento de un vector mediante un índice es una operación de complejidad
constante O(1). El número de pasos a ejecutar es siempre el mismo independientemente del
tamaño del vector.
Buscar en un diccionario tiene complejidad logarítmica. Se puede iniciar la búsqueda de una
palabra por la mitad del diccionario. Inmediatamente se sabe si se ha encontrado la palabra o,
en el caso contrario, en cuál de las dos mitades hay que repetir el proceso hasta llegar al
resultado. En cada búsqueda el problema se ha reducido a la mitad, lo que se corresponde con
la función logarítmica. Este procedimiento de búsqueda (conocido como búsqueda binaria) en
una estructura ordenada tiene complejidad logarítmica O(log2 n).
El proceso más común para ordenar un conjunto de elementos tiene complejidad cuadrática: el
procedimiento es de orden cuadrático O(n²).
Cuando haya que comparar dos algoritmos que solucionan un mismo problema, un criterio será
comparar su coste en tiempo. Así, un algoritmo lineal O(n) será mejor que uno cuadrático O(n2),
porque implicará comparativamente mucho menos pasos de ejecución para obtener un mismo
resultado, pero peor que uno logarítmico O(log2 n).
Heurísticos
A menudo los problemas que no pueden ser abordados con una solución algorítmica se abordan
mediante heurísticos. Un heurístico es un algoritmo que no garantiza que se llegue a la solución en
todos los casos, pero sí en la mayoría de los casos.
1 Un ejemplo muy típico es el problema del viajante: Sean N ciudades de un territorio. El objetivo es encontrar
una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las
ciudades y minimice la distancia recorrida por el viajante.
Tema 3: Abstracción de control.
64
Los heurísticos se usan cuando no existe una solución algorítmica óptima bajo las restricciones
dadas (tiempo, espacio, etc.). Los heurísticos se basan en la experiencia, en el buen juicio y en las
probabilidades y no siempre funcionan de forma satisfactoria ni producen un resultado correcto.
En algunos casos el heurístico puede producir un mal resultado, consumir muchos más recursos de
los esperados o ejecutarse muy lentamente. Aún así, merece la pena utilizarlo cuando no existe
ningún algoritmo que pueda resolver el problema en un tiempo razonable, porque la experiencia o
el sentido común nos indican que las probabilidades de fallo son pequeñas. En muchos problemas
existe un algoritmo que no puede encontrar una solución en tiempo finito, pero puede comprobar
con gran eficiencia si una solución es correcta. Así, puede utilizarse un heurístico para hallar la
solución y después comprobarla mediante el algoritmo. Si el heurístico no da una solución correcta
o se ejecuta de forma muy lenta se puede probar con otro heurístico.
Sentencias en Java
Sentencias en Java
La secuencia de ejecución de un programa viene determinada por las sentencias. Una sentencia
expresa una acción o un conjunto de acciones que debe realizar el computador. Podemos distinguir
tres tipos de sentencias:
−
−
−
Expresiones: calculan y asignan valores a variables y pueden incluir llamadas a métodos.
Declaraciones: declaran variables.
Sentencias de control de flujo: determinan qué sentencias de un programa se ejecutan y el
orden en que se ejecutan.
Las sentencias de Java (y todos de los lenguajes estructurados) pueden ser sentencias simples y
compuestas. En el caso de Java:
−
−
Las sentencias simples incluyen expresiones, declaraciones de variables locales y las sentencias
break, continue y return que iremos viendo en este tema y en otros posteriores.
Las sentencias compuestas están compuestas de sentencias simples o de otras sentencias
compuestas. Incluyen bloques de código entre llaves, las sentencias de selección e iteración y
los bloques de captura y tratamiento de excepciones en aquellos lenguajes que las soportan
(Java entre ellos).
Bloques Java.
Un bloque Java consiste de una secuencia de sentencias encerradas entre un par de llaves { }. Las
sentencias de un bloque pueden ser simples o compuestas y se ejecutan secuencialmente.
{
{
Sentencia1
Sentencia2
…
SentenciaN
}
int i = 0;
int j = 2;
int k = i * j;
…
}
Tema 3: Abstracción de control.
Sentencias de control de flujo en Java.
65
En Java se definen las siguientes estructuras de control de flujo:
Sentencias de selección en Java 1.
Java tiene dos tipos de sentencias de selección: por un lado la sentencia if o if/else y por otro
la sentencia switch.
La sentencia if o if/else
La sentencia if condiciona la ejecución de otra sentencia al cumplimiento de una condición:
if (condición)
sentencia
true.
// Sentencia if
// sentencia que se ejecuta si condición evalúa a
Si se cumple la condición se ejecuta la sentencia, si no, se salta hasta la siguiente instrucción.
condición es una expresión lógica (booleana) cuyo resultado es verdadero (true) o falso
(false)
if (calificación >= 5)
System.out.println(“Aprobado”);
La sentencia if puede describirse mediante un diagrama de flujo de la siguiente forma:
1
Fuente principal: Dietel y Deitel
Tema 3: Abstracción de control.
Opcionalmente, la sentencia if puede tener una cláusula else
if (condición)
sentencia1
true.
else
sentencia2
false
66
// Sentencia if
// sentencia que se ejecuta si condición evalúa a
// Sentencia que se ejecuta si condición evalúa a
Si se cumple la condición se ejecuta la sentencia1, si no, se ejecuta la sentencia2.
if (calificación >= 5)
System.out.println(“Aprobado”);
else
System.out.println(“Suspenso”);
La sentencia if/else puede describirse mediante un diagrama de flujo de la siguiente forma:
Si se quiere indicar que se ejecuta más de una sentencia, hay que ponerlas entre llaves:
if (condicion){
sentencia_1;
sentencia_2;
}
else {
sentencia_3;
sentencia_4;
}
Cuando una sentencia o conjunto de sentencias están anidados en otra sentencia es muy
importante cuidar la edición sangrando un poco el bloque anidado. De esta forma se mejora mucho
la legibilidad del código.
En el caso de las sentencias if es bastante habitual que unas se aniden unas sentencias dentro de
otras en cascada. En este caso se prefiere la edición de la derecha porque evita sangrados excesivos
y es más legible:
if (calificacion >= 9)
System.out.println(“Sobresaliente”);
else
if (calificacion >= 7)
System.out.println(“Notable”);
else
if (calificacion >= 5)
System.out.println(“Aprobado”);
else
System.out.println(“Suspendido”);
if (calificacion >= 9)
System.out.println(“Sobresaliente”);
else if (calificacion >= 7)
System.out.println(“Notable”);
else if (calificacion >= 5)
System.out.println(“Aprobado”);
else
System.out.println(“Suspendido”);
Tema 3: Abstracción de control.
67
La sucesión de sentencias if/else da lugar a errores de programación, algunos de los cuales no
son detectados por el compilador pues no responden a errores de sintaxis, y, por tanto, hacen
perder mucho tiempo y desesperan al programador, sobre todo si es principiante. La mayoría de
estos errores pueden evitarse muy fácilmente adoptando un buen estilo de edición de los
programas. Veamos algunos ejemplos típicos:
− Un else siempre se refiere al if anterior:
if (x>5)
if (y>5)
System.out.println(“x e y son mayores que 5”);
else
System.out.println(“x es menor o igual que 5”);
Si x es mayor que 5 e y es menor que 5 imprime que “x es menor o igual que
5”, lo cual obviamente no es lo que queremos. El último else se refiere al último if.
Si queremos otro comportamiento tenemos que forzarlo con llaves:
if (x>5){
if (y>5)
System.out.println(“x e y son mayores que 5”);
}
else
System.out.println(“x es menor o igual que 5”);
De hecho, se considera una buena práctica de programación poner siempre llaves,
aunque el bloque conste de una única sentencia. Así el mejor estilo de edición para las
sentencias del ejemplo sería:
if (x>5){
if (y>5) {
System.out.println(“x e y son mayores que 5”);
}
}
else {
System.out.println(“x es menor o igual que 5”);
}
− Un punto y coma (;) mal colocado puede producir un error de sintaxis conocido como
“dangling else” (else colgante) o lo que es peor un error de lógica:
Error de lógica:
if (nota >= 5);
condición
System.out.println(“Aprobado”);
Error de sintaxis:
// No haría nada después de evaluar
// Siempre se ejecuta
if (calificacion>= 5);
// if acaba aquí
System.out.println(“Aprobado”);
// Siempre se ejecuta
else
System.out.println(“Suspendido”); // ¿A qué if se refiere?
Tema 3: Abstracción de control.
68
Los errores de sintaxis son detectados por el compilador por lo que son menos graves que
los de lógica. Pero no siempre es fácil detectar el else colgante en una estructura con
muchas sentencias if anidadas. Y lo que es peor puede arreglarse el error de sintaxis y dejar
un error de lógica. Nuevamente el uso de llaves hace mucho más difícil que ocurran estos
errores:
if (calificacion>= 5){
System.out.println(“Aprobado”);
}
else {
System.out.println(“Suspendido”);
}
Hay otra buena razón para el uso de llaves: es muy probable que lo que en principio iba a ser
una única sentencia se convierta a medida que el programa crece en un grupo de sentencias.
Poner las llaves desde el principio nos ahorra trabajo posterior y hace más difícil que la
adición de nuevas sentencias produzca uno de los errores que se han descrito.
La sentencia de selección switch
Aunque la sentencia if/else nos permite resolver todos los casos en los que necesitamos elegir
un camino de ejecución u otro 1, en algunas ocasiones nos interesa seleccionar las instrucciones a
ejecutar no en función de una condición booleana, sino en función del valor de una variable. Para
estos casos, Java proporciona la sentencia switch.
switch (expresión) {
case valor_1:
sentencia_1;
break;
case valor_2:
sentencia_21;
sentencia_22;
break;
...
case valor_i, valor j:
sentencia_i;
break;
default:
sentencia_por_defecto;
break;
}
valor_1, valor_2, … valor_i deben ser constantes enteras o constantes carácter. Una
constante de carácter se representa como el carácter en cuestión encerrado entre apóstrofos: ´A’
expresión debe ser una expresión entera constante, es decir, una combinación de constantes de
carácter y constantes enteras que al evaluarse produzca un valor entero constante.
La ejecución de una sentencia switch comienza con la evaluación de la expresión entera. El
resultado de la evaluación se va comparando secuencialmente con los valores de las cláusulas case
(puede haber más de un valor en cada cláusula case separados por comas). En cuanto se
encuentra un valor coincidente se ejecutan las sentencias asociadas al case correspondiente. Si
ninguno de los valores de las cláusulas case coincide con el evaluado se ejecuta el código de la
1
En realidad bastaría con el if, sin else.
Tema 3: Abstracción de control.
69
cláusula default. Esta cláusula es opcional, pero se considera una buena práctica de
programación incluirla siempre.
Obsérvese que después de cada caso (case) no se incluyen llaves { } aunque haya más de una
sentencia.
Debajo se muestra un ejemplo anterior resuelto ahora con la sentencia switch.
if (calificacion >= 9) {
System.out.println(“Sobresaliente”);
}
else if (calificacion >= 7){
System.out.println(“Notable”);
}
else if (calificacion >= 5){
System.out.println(“Aprobado”);
}
else {
System.out.println(“Suspendido”);
}
switch(calificación){
case 9:
System.out.println(“Sobresaliente”);
break;
case 8, 7:
System.out.println(“Notable”);
break;
case 6, 5:
System.out.println(“Aprobado”);
break;
default:
System.out.println(“Suspendido”);
break;
}
Sentencias de iteración en Java1.
Java tiene tres sentencias de iteración: por un lado las sentencias while y do/while y por otro
la sentencia for.
Las sentencias while y do/while
La sentencia while ejecuta una sentencia mientras se cumpla una condición:
while (condición)
// Sentencia while
sentencia
// sentencia que se
evalúa a false.
ejecuta
hasta
que
condición
// Encontrar la primera potencia de 2 mayor que 1000.
int producto = 2;
while (producto <= 1000){
// Uso de llaves recomendado con una
sola
producto = 2 * producto;
// sentencia
}
// Es necesario el uso de llaves cuando la sentencia while
// incluye más de una sentencia.
while (condición){
sentencia_1;
……
sentencia_n;
}
1
Fuente principal: [Deitel 99]
Tema 3: Abstracción de control.
70
La sentencia do/while permite al programador especificar que una acción se repita en tanto se
cumpla una condición.
do {
sentencia;
}
while (condicion);
// Encontrar la primera potencia de 2 mayor que 1000.
int producto = 2;
do {
producto = 2 * producto;
}
while (producto <= 1000)
Con la sentencia do/while la sentencia o sentencias del bucle se ejecutan al menos una vez. La
condición se comprueba después de haber realizado la primera iteración.
Ojo con los bucles infinitos: hay que asegurarse de que la condición deja de cumplirse.
La sentencia for
La sentencia for permite controlar el número de iteraciones mediante un contador.
for (inicialización del contador;
condición;
expresión de incremento del contador)
{
sentencia_1;
……
sentencia_n;
}
La semántica de la sentencia for es la siguiente:
1.
2.
3.
4.
5.
Se inicializa contador (sólo la primera vez).
Se evalúa condición.
− Si true → ejecutar sentencias.
− Si false → a paso 5 (salir del bucle).
Se incrementa contador según expresión de incremento.
Volver al paso 2.
Salir del bucle.
// Imprimir la tabla de multiplicar del 3 (del 0 al 10)
int i = 0;
for (i = 0; i <= 10; i++){
System.out.println(“3 x “ + i + “ = “ + (3 * i));
}
// Es mucho mejor declarar la variable en el propio bucle.
for (int i = 0; i <= 10; i++){
System.out.println(“3 x “ + i + “ = “ + (3 * i));
}
El bucle while equivalente sería
Tema 3: Abstracción de control.
71
Inicialización contador;
while(condicion){
sentencia_1;
…
sentencia_n;
incremento del contador
}
int i = 0;
while(i <= 10){
System.out.println(“3 x “ + i + “ = “ + (3 * i));
i++;
}
La variable de control puede modificarse de acuerdo con cualquier expresión aritmética:
// variable de control de 7 a 77 en incrementos de 7.
for (int i = 7; i <= 77; i += 7){…};
// variable de control de 99 a 0 en incrementos de
for (int i = 99; i >= 0; i = i - 11) {…};
-11
// Incrementos de 5 en 5
for ( int j = 2; j <= 80; j += 5 ){
System.out.println(j);
}
// Ejemplos de lo que NO se debe hacer
// Las expresiones de un for pueden contener expresiones aritméticas, pero
no
// utilice expresiones cuyo significado es difícil de entender.
int x = 2;
int y = 10;
for ( int j = x; j <= 4 * x * y; j += y / x ) {
System.out.println(j);
}
// Este bucle for
tardado en darse
// cuenta?
es
equivalente
al
anterior,
pero
¿cuánto
tiempo
ha
// NO modifique el valor de la variable de control dentro del bucle for.
for (int i = 7; i <= 77; i++){
i *= 7;
// No haga cosas de este estilo.
}
Las tres expresiones de la estructura for son opcionales:
−
Se puede omitir la inicialización del contador si se ha inicializado antes.
int i = 1;
for( ; i < 10; i++) { ... }
−
Si se omite la comprobación de la condición, Java supone que la condición para continuar el
ciclo se cumple, creándose un bucle infinito.
for( ; ; i++) { ... }
for( ; ; ) { ... }
−
// Bucle infinito. Posible desbordamiento de i.
// Bucle infinito.
La propia variable de control se puede utilizar dentro del cuerpo del for.
for( ; i < 10; i++ ) {
if ( i%2 == 0) { ... } // Se hace algo cuando i es par.
}
−
El incremento del contador puede omitirse si se hace dentro del cuerpo del for.
for( ; i < 10; ) { ...
i++ ... }
// Nada aconsejable.
Tema 3: Abstracción de control.
72
Elección de una estructura de repetición:
−
−
−
Si número fijo de veces, elegir for
Si 1 o más veces, elegir do { } while { }
Si 0 o más veces, elegir while ( ) { }
Las sentencias break y continue.
La palabra reservada break en el cuerpo de un ciclo causa la terminación inmediata de dicho ciclo.
int i = 0;
int s = 0;
while (i <= 5) {
s += 1;
if ( s == 7) break; // sale del bucle.
// otras sentencias …
i++;
}
// Se pasa aquí si i > 5 o s == 7
La palabra reservada continue causa el salto a la siguiente iteración del ciclo, pero sin salirse del
ciclo .
for (int i = 0; i < 100; i++) {
if (i % 2 == 1) continue;
// Sólo se pasa aquí si i es par
// otras sentencias ...
}
En las estructuras while y do/while la condición para continuar el ciclo se evalúa
inmediatamente después de ejecutarse continue. En la estructura for se incrementa el contador
y luego se evalúa la condición.
Las siguientes porciones de código son equivalentes:
for (int i = 1; i <= 10; i++ ) {
// sentencia 1
// sentencia n
}
Pero las dos siguientes NO son equivalentes:
// Incremento antes de continue
for (int i = 1; i <= 10; i++ ) {
// sentencia 1
continue;
// sentencia n
}
int i = 1;
while ( i <= 10 ) {
// sentencia 1
// sentencia n
i++;
}
// Incremento después de continue
int i = 1;
while ( i <= 10 ) {
// sentencia 1
continue;
// sentencia n
i++;
}
Tema 3: Abstracción de control.
break y continue etiquetados
73
El enunciado break sólo causa la salida de la estructura while, do/while o for que lo encierra
directamente. Para salirnos de una serie de estructuras anidadas se usa el enunciado break
etiquetado:
La ejecución del programa continúa con el primer enunciado después del enunciado compuesto
etiquetado, el cual consiste en una serie de enunciados encerrados en llaves y precedidos por una
etiqueta.
// Enunciado compuesto rotulado o etiquetado
stop:
for (int fila = 1; fila <= 10; fila++) {
for (int columna = 1; columna <= 5; columna++) {
if (fila == 5) {
break stop; // Se sale del bloque etiquetado.
}
System.out.println(“Fila es menor que 5”);
}
}
// Si se sale por break, continúa por aquí.
System.out.println(“La fila es 5”);
El enunciado continue continúa con la siguiente iteración de la estructura while, do/while o
for que lo encierra directamente. El enunciado continue etiquetado se salta el resto de los
enunciados del cuerpo de la estructura de iteración que lo contiene y cualquier cantidad de
estructuras de iteración que la encierren y continúa con la siguiente iteración de la estructura de
repetición etiquetada.
// Enunciado compuesto rotulado o etiquetado
stop:
for (int fila = 1; fila <= 10; fila++) {
for (int columna = 1; columna <= 5; columna++) {
if (fila == 5)
continue stop;
System.out.println(“Fila es distinta que 5”);
}
// Continúa por aquí.
}
System.out.println(“La fila es 10”);
break y continue suponen una violación de las reglas de la programación
estructurada.
El uso de break está justificado en pocas ocasiones. Si hay más de una salida del ciclo del programa
se hace más difícil de leer y analizar y se va en contra de los principios de la programación
estructurada. Puede evitarse con una escritura más cuidadosa de las condiciones de terminación
del ciclo:
Tema 3: Abstracción de control.
int i;
char s;
while (i <= 5) {
if (s == ´a´) break;
// Sentencias
i++;
}
74
int i;
char s;
while (i <= 5 && s != ´a´){
// Sentencias
i++;
}
El uso de continue puede evitarse con una escritura más cuidadosa del cuerpo del ciclo y de la
expresión de incremento de la variable de control.
for (int i = 0; i < 100; i ++) {
if (i%2 == 1) continue;
// Procesamiento según valor de i
}
for (int i = 0; i < 100; i += 2) {
// Procesamiento según valor de i
}
continue ayuda a reducir los niveles de anidado en el cuerpo de la estructura de iteración, pero es
peligroso si no se hacen explícitas las condiciones para ejecutar el resto del ciclo.
// int a, b (declaradas antes)
// posible bucle ∞ si b es cero al
// entrar
while (a < 5){
if (b == 0) continue;
// otras sentencias;
a++;
}
// int a, b (declaradas antes)
while (a < 5) {
if (b == 0){
a++;
continue;
}
// otras sentencias;
a++;
}
Algoritmos y refinamientos sucesivos 1
Supongamos que tenemos que hacer un programa para resolver el siguiente problema:
Diez alumnos se presentan a un examen. Se desea conocer la nota media de la clase.
Podríamos empezar por expresar la solución en pseudocódigo:
Poner la suma de notas a 0
Poner el contador de notas a 1
Mientras el contador de notas sea menor o igual que 10
Pedir y leer nota
Añadir la nota a suma
Incrementar en 1 el contador de notas
Calcular la media
Mostrar el resultado
Y posteriormente traducir el pseudocódigo a un programa Java (Cuadro 1).
1
Fuente: [Deitel 99]
Tema 3: Abstracción de control.
75
El programa del Cuadro 1 funciona bien si todo va bien y tiene grandes limitaciones. Por ejemplo, no
sirve para calcular la media si se presenta un número de alumnos distinto de 10, ni comprueba que
las notas están en el rango correcto. Vamos a tratar de mejorarlo independizándolo del número de
alumnos que se presenten al examen:
Desarrollar un programa de cálculo de la media de las notas de una clase que procese un
número arbitrario de notas.
CUADRO 1
public class ejemplo31 {
public static void main(String[] args) {
// Declaraciones e inicializaciones.
int total = 0;
// suma de notas
int contador = 0;
// contador de notas
int nota = 0;
// valor de la nota
int media = 0;
// media de todas las notas
// Inicialización variable de control del bucle.
contador = 1;
// Petición de notas y cálculo de suma de notas.
while (contador <= 10){
// Pedir nota y leerla.
System.out.print("Introduzca nota: ");
nota = Teclado.readInt();
// Incrementar el total.
total += nota;
// Incrementar variable de control.
contador++;
}
// Cálculo de la media.
media = total / 10;
// Muestra del valor de la media.
System.out.println("La media de la clase es: " + media);
}
}
Como no sabemos a priori el número de notas que van a ser introducidas debemos idear un
mecanismo que nos permita saberlo. Una posible solución es pedir al usuario cuántas notas va a
introducir y utilizar este número como utilizábamos el 10 en la solución anterior. Sin embargo,
vamos a proceder de otra manera: definiremos un valor especial para la nota que nos indique que el
usuario ya no va a introducir más notas (un centinela).
Como antes, empezamos por expresar la solución en pseudocódigo:
Poner la suma de notas a 0
Poner el contador de notas a 0
Pedir y leer la primera nota (posiblemente el centinela)
Mientras el usuario no haya introducido el centinela
Añadir la nota a la suma
Incrementar en 1 el contador de notas
Pedir y leer una nueva nota
Si el contador de notas es distinto de cero
Calcular la media
Tema 3: Abstracción de control.
Mostrar el resultado
76
Si no
Imprimir “no se han introducido notas”
El Cuadro 2 muestra la implementación de la solución en Java:
CUADRO 2
public class ejemplo32 {
public static final int Centinela = -1;
public static void main(String[] args) {
// Declaraciones e inicializaciones.
int total = 0;
// suma de notas
int contador = 0;
// contador de notas
int nota = 0;
// valor de la nota
double media = 0;
// media de todas las notas
// Petición de primera nota.
System.out.print("Introduzca nota: ");
nota = Teclado.readInt();
// Petición de notas y cálculo de suma de notas.
while (nota != Centinela){
// Incrementar el total.
total += nota;
// Incrementar variable de control.
contador++;
// Pedir nota y leerla.
System.out.print("Introduzca nota: ");
nota = Teclado.readInt();
}
// Cálculo e impresión de la media.
if (contador != 0){
media = (double)total / contador;
System.out.println("La media de la clase es: " + media);
}
else{
System.out.println("no se han introducido notas");
}
}
}
A parte de implementar una lógica diferente, la solución del cuadro 2 difiere de la del Cuadro 1 en
un par de aspectos que deben comentarse:
−
−
Se utiliza una constante Centinela para definir el valor de la nota que se utiliza para salir del
bucle. Utilizar en un programa números, como se utilizaba el 10 en el programa del Cuadro 1,
es una muy mala práctica de programación, que dificulta extraordinariamente la comprensión
y el mantenimiento de los programas. Estos números suelen dispersarse por diferentes lugares
del programa. Si hubiera que cambiar el valor a utilizar habría que inspeccionar el programa
entero. Además, al cabo de cierto tiempo (no mucho) el programador olvida el significado del
número, lo que hace muy difícil determinar en qué expresiones debe cambiarse y en qué
expresiones debe mantenerse. Moraleja: UTILICEN SIEMPRE CONSTANTES CON NOMBRES
SIGNIFICATIVOS EN LUGAR DE NÚMEROS.
La variable media se declara double. Parece lógico pensar que la media puede no ser un
número entero. Sin embargo, total y contador se mantiene como enteros. Eso obliga a
Tema 3: Abstracción de control.
77
hacer un cast en la expresión de cálculo de la media: media = (double)total /
contador;
La expresión total / contador; realiza una división entera puesto que ambos
operandos son int. La forma de forzar una división real es convertir uno de los operandos
en double antes de realizar la división.
Refinamientos Sucesivos.
Consideremos ahora un nuevo problema, aunque no muy diferente a los anteriores:
Un instituto desea saber qué porcentaje de sus alumnos pasan el examen de selectividad, para
lo cual solicita un programa que tome una lista con las notas de 10 estudiantes. Si la nota es
mayor o igual que cinco el estudiante ha pasado selectividad, si no ha suspendido. El
programa debe funcionar de la siguiente manera:
1.
2.
3.
4.
5.
Debe pedir las notas una tras otra, hasta la décima nota.
Debe contar el número de aprobados y de suspensos.
Debe mostrar los resultados absolutos y porcentuales.
Si más del 80% de estudiantes han pasado la prueba debe mostrar el mensaje “Por
encima de la media”.
Si menos del 25% estudiantes han pasado la prueba debe mostrar el mensaje “Por
debajo de umbral de calidad”.
Como antes, empezamos por expresar la solución en pseudocódigo, pero esta vez vamos a hacerlo
por refinamientos sucesivos. La técnica de refinamientos sucesivos puede describirse así 1:
1.
2.
3.
La construcción de un programa consiste en una secuencia de pasos consistentes en
refinamientos sucesivos. En cada paso una tarea dada se descompone en cierto número de
subtareas. Cada refinamiento en la descripción de la tarea puede acompañarse por un
refinamiento de la descripción de los datos de la tarea. Es decir, los refinamientos de la
descripción del programa y de las estructuras de datos se realizan en paralelo.
El grado de modularidad obtenido de esta manera determinará la facilidad o dificultad con
la que un programa podrá adaptarse a futuros cambios o extensiones.
Durante el proceso de refinamiento se utilizará la notación que mejor se adapte a la
naturaleza del problema. A medida que avancen los refinamientos, la notación puede irse
adaptando a las características del lenguaje de implementación.
Cada refinamiento implica un cierto número de decisiones de diseño basadas en un conjunto de
criterios de diseño. Entre estos criterios se encuentran la eficiencia, el ahorro de memoria y la
claridad y regularidad de la estructura resultante 2.
Vamos a aplicar esta técnica al problema de arriba. Nuestra primera descripción del programa
podría 3 ser la siguiente:
Inicializar variables
Introducir las notas contar aprobados y suspensos
Imprimir un informe con los resultados obtenidos.
Adaptación de conclusiones de “Program Development by Stepwise Refinement” , Niklaus Wirth, Communications of the
ACM, Vol. 14, No. 4, April 1971, pp. 221-227. Disponible en http://sunnyday.mit.edu/16.355/wirth-refinement.html#7. Se
recomienda su lectura.
2 Muchos diseños que producen programas igualmente correctos desde un punto de vista funcional pueden ser muy
diferentes cuando se les juzga también a la luz de esos criterios.
3 El condicional podría está usado con toda intención. Un programa puede diseñarse de muchas maneras en función de los
criterios que acaban de mencionarse.
1
Tema 3: Abstracción de control.
78
Es evidente que necesitamos detallar bastante más la solución para poder programarla.
Necesitamos refinar el programa y sus datos.
Inicializar aprobados a 0
Inicializar suspensos a 0
Inicializar contador de notas a 1
Inicializar variables
Mientras el contador de notas sea menor o igual a 10
Leer nota
Si la nota es aprobado
Añadir a aprobados
Si no
Añadir a suspensos
Incrementar contador de notas
Calcular porcentaje de aprobados.
Introducir las notas
contar aprobados y
suspensos
Imprimir número de aprobados
Imprimir número de suspensos
Imprimir porcentaje de aprobados
Imprimir un informe
con los resultados
obtenidos.
Si aprobados > 80%
Imprimir “Por encima de la media”
Si no, si aprobados < 25%
Imprimir “Por debajo de umbral de calidad”
El programa Java resultante se muestra en el cuadro 3.
CUADRO 3
public class ejemplo33 {
public static final int
public static final double
public static final double
NumeroDeNotas = 10;
UmbralExcelencia = 80.0;
UmbralCalidad = 25.0;
public static void main(String[] args) {
// Inicializar variables.
int aprobados = 0, suspensos = 0, contadorNotas = 1;
// Introducir las notas contar aprobados y suspensos
while (contadorNotas <= NumeroDeNotas){
// Pedir nota y leerla.
System.out.print("Introduzca nota: ");
int nota = Teclado.readInt();
if (nota >= 5){
aprobados++;
}
else if (nota < 5) {
suspensos++;
}
contadorNotas++;
}
double porcentajeAprobados =
100.0 * ((double)aprobados / NumeroDeNotas);
// Imprimir un informe con los
System.out.println("Aprobados:
System.out.println("Suspensos:
System.out.println("Porcentaje
resultados obtenidos.
" + aprobados);
" + suspensos);
aprobados: " + porcentajeAprobados);
if (porcentajeAprobados > UmbralExcelencia){
System.out.println("Por encima de la media");
}
else if (porcentajeAprobados < UmbralCalidad){
System.out.println("Por debajo de umbral de calidad");
}
}
Tema 3: Abstracción de control.
Construcción de programas estructurados
79
Un programa estructurado utiliza únicamente las tres estructuras básicas de control siguientes:
−
−
−
Secuencia: el bloque secuencial de instrucciones, instrucciones ejecutadas sucesivamente, una
detrás de otra.
Selección: la instrucción condicional con doble alternativa, de la forma "if condición then
instrucción-1 else instrucción-2".
Iteración: el bucle condicional "while condición do instrucción", que ejecuta la instrucción
repetidamente mientras la condición se cumpla.
Además, cada estructura tiene un punto de entrada y uno de salida perfectamente definidos. La
experiencia ha demostrado que los programas estructurados son más fáciles de escribir y de
entender y más fáciles de probar, depurar y modificar. La corrección de los programas
estructurados es incluso susceptible de ser probada formalmente como se prueba la corrección de
un teorema matemático 1.
Las reglas para construir programas estructurados pueden formularse de forma muy sencilla:
1.
Empezar con el diagrama de flujo más simple posible.
2.
Regla de apilamiento: Cualquier acción, incluyendo entrada y salida, (rectángulos) puede
ser reemplazada por dos acciones en secuencia.
4.
Las reglas 2 y 3 pueden aplicarse en cualquier orden.
3.
Regla de anidamiento: Cualquier acción puede ser reemplazada por una estructura de
control (en Java: secuencia, if, if/else, switch, while, do/while, for).
La aplicación de estas reglas siempre resulta en un diagrama de flujo estructurado con aspecto de
diagrama de bloques anidados. La aplicación sucesiva de la regla 2 da lugar a una secuencia de
acciones, generando una pila de estructuras de control, de ahí su nombre de regla de apilamiento.
La aplicación de la regla 3, regla de anidamiento, resulta en una serie de bloques anidados.
Regla 2
1
Regla 2
Cosa que, aunque casi nunca se realiza, es muy importante en ciertos casos.
Tema 3: Abstracción de control.
80
Regla 3
Regla 3
Regla 3
La elegancia de la programación estructurada reside en su simplicidad, sólo tres estructuras de
control y sólo cuatro reglas para combinarlas (estrictamente hablando sólo dos, apilamiento y
anidamiento). Obsérvese la relación entre estas reglas y el diseño en refinamientos sucesivos. Cada
paso de refinamiento da lugar a la aplicación de la regla de apilamiento o a la de anidamiento.
Tema 4: Arrays.
Tema 4: Estructuras estáticas de
datos. Arrays.
Objetivos
Presentar los arrays.
Conocer cómo se declara, inicializa y se accede a los elementos de un array.
Utilizar técnicas de ordenación y búsqueda de los elementos de un array.
Manejar arrays de múltiples dimensiones.
Contenidos
Arrays
Ordenación de arrays
Búsqueda en arrays
Arrays Bidimensionales
81
Tema 4: Arrays.
Arrays1.
82
Un array es estructura de datos que almacena una cantidad fija de elementos del mismo
tipo, a los cuales se puede acceder por medio de un índice que indica su posición dentro de
la estructura.
Hay dos aspectos de la definición que merece la pena resaltar:
−
−
Los arrays son estructuras de datos homogéneos: todos los datos son del mismo tipo.
Los arrays son estructuras de datos estáticas 2: los arrays contienen siempre el mismo
número de datos. En otras palabras el tamaño del array no puede cambiar durante la
ejecución del programa.
Podemos encontrar estructuras de datos con estas características en otros ámbitos, por ejemplo en
álgebra: vectores (1D), matrices (2D) o tensores (3D).
Declaración de arrays en Java.
La convención para declarar un array en Java es simplemente poner un par de corchetes antes o
después del nombre de la variable:
Tipo_de_los_elementos [] nombre_de_referencia_al_array;
O equivalentemente:
Tipo_de_los_elementos nombre_de_referencia_al_array [];
Por ejemplo:
int [] arrayDeEnteros;
char arrayDeCaracteres [];
Acabamos de decir que un array es una estructura de datos que almacena una cantidad de datos fija
de elementos del mismo tipo. Sin embargo, en las declaraciones de arriba no se ha especificado
ninguna cantidad de datos. No sabemos cuantos enteros se guardan en arrayDeEnteros ni
cuantos caracteres se guardan en arrayDeCaracteres. De hecho, en arrayDeEnteros no se
guarda ningún entero y en arrayDeCaracteres no se guarda ningún carácter. ¿Qué se guarda
entonces?
Los arrays en Java son objetos y a los objetos en Java no se accede nunca de forma directa,
sino a través de referencias.
Los arrays son tipos referencia y a un valor de un tipo referencia nunca se accede de forma directa,
sino a través de referencias. arrayDeEnteros y arrayDeCaracteres no guardan enteros ni
caracteres porque no son arrays de enteros ni arrays de caracteres, sino referencias, es decir
apuntadores, a dichos arrays.
Fuentes: [Deitel 99]
La palabra estático (static) está muy sobrecargada en las ciencias de computación, es decir puede significar muchas cosas
distintas, a veces con muy poca relación, dependiendo del contexto. Cuando vean que algo en informática se define como
estático no hagan suposiciones, estudien su significado en el contexto donde se usa la palabra.
1
2
Tema 4: Arrays.
83
En la declaración no se especifica el tamaño del array porque en la declaración no se crea el array,
sino la referencia que lo apunta. Así, por ejemplo, con la declaración:
int [] serie;
se obtiene una referencia llamada serie que puede apuntar a un array de enteros, pero de
momento, dependiendo de dónde se declare (dentro o fuera de un método 1) o bien no apunta a
nada o bien apunta a algo indefinido. Para que serie apunte a un array debemos crear dicho array.
Creación de arrays en Java.
Crear un array es asignarle un espacio de almacenamiento en memoria.
La creación de objetos en Java, y los arrays son objetos, se realiza mediante el operador new. En el
caso de los arrays el operador new se utiliza de la siguiente manera:
new tipo_elemento [n_elementos]
Por ejemplo:
new int[5];
mismo.
// Crea un array de 5 enteros y devuelve una referencia al
Es decir, se escribe el operador new seguido por el tipo de los elementos del array y el número de
elementos que va a contener entre corchetes. El operador new crea un array de n_elementos del
tipo tipo_elemento y devuelve una referencia al mismo. Crear el array significa reservar un
espacio en memoria suficiente para guardar los elementos del array. Este espacio se reserva de
forma contigua, lo cual facilita enormemente las operaciones de acceso al array. Obviamente, de
poco nos sirve la referencia que devuelve new si no la guardamos en alguna parte. La forma de
guardar dicha referencia es asignársela a una variable referencia previamente declarada:
int [] serie;
serie = new int[5];
En la figura 1 puede apreciarse que serie no es el array, sino un apuntador (referencia 2) a array.
Los arrays se pueden declarar y crear simultáneamente:
int [] serie = new int[5];
Se pueden declarar y crear varios arrays que contengan el mismo tipo de elementos en una sola
línea:
int a[] = new int[20], b[] = new int[100];
Conocemos ya el método main y los métodos se verán en profundidad en el tema siguiente, Abstracción Funcional.
Los términos apuntador, puntero y referencia no son exactamente equivalentes. En el contexto de Java el término que debe
utilizarse es referencia.
1
2
Tema 4: Arrays.
84
Figura 1: Acceso a arrays mediante referencias.
Entender que la diferencia entre objeto y referencia es clave para poder entender y manejar los
arrays de forma correcta. Por ello vamos a ver y comentar un par de ejemplos. Consideremos
primero el ejemplo de la figura 2. En (1) se realizan las siguientes acciones en el siguiente orden:
−
−
−
Declaramos la referencia serie1, que puede referenciar a cualquier array de enteros.
Creamos mediante new un array de 5 enteros.
Asignamos la referencia devuelta por new a serie1
En (2) se realizan las siguientes acciones:
−
−
−
Declaramos la referencia serie2, que puede referenciar a cualquier array de enteros.
Creamos mediante new un array de 3 enteros.
Asignamos la referencia devuelta por new a serie2
En (3) se asigna el valor de serie2 a serie1. La consecuencia de esto es que al array de tres
enteros le apuntan ahora dos referencias serie1 y serie2 y que al array de 5 elementos no le
apunta ninguna referencia. Java es capaz de detectar automáticamente cuando un objeto no es
apuntado por ninguna referencia. Cuando ocurre esto el objeto es borrado 1.
Figura 2: Objetos y referencias.
Supongamos ahora un ejemplo parecido (figura 3). Los tres primeros pasos son iguales a los de la
figura 2. De hecho, sólo hay una diferencia: el array que se crea en (2) es igual al que se crea en (1).
Esto se ha hecho así para poder razonar sobre el significado de la expresión:
Aunque no inmediatamente, sino transcurrido algún tiempo. El mecanismo de Java que revisa si hay objetos que no son
apuntados por ninguna referencia para eliminarlos se denomina recolector de basura (garbage collector). El recolector de
basura simplifica mucho la programación: si no existiera, la liberación de memoria debería gestionarla el programador.
1
Tema 4: Arrays.
85
serie1 == serie2
Si ponemos está expresión entre los pasos (2) y (3) evaluará a false, aunque los arrays a los que
apuntan serie1 y serie2 sean iguales, porque no estamos comparando arrays, sino referencias y
las referencias serie1 y serie2 son distintas porque apuntan a objetos distintos,
independientemente de que ambos objetos sean idénticos. Supongamos ahora que ponemos esa
expresión justo después de (3). En este caso la expresión evalúa a true ya que ambas apuntan al
mismo array.
Finalmente en (4) se hace que serie2 apunte a null, es decir a la nada. El array al que apuntaba
seguirá existiendo porque aun hay una referencia que lo apunta, serie1.
Figura 3: Comparación de referencias.
Inicialización de arrays en Java.
Llegados a este punto sabemos cómo declarar referencias a arrays, como crear arrays y como hacer
que las referencias apunten a los arrays, pero aun no sabemos cómo leer o escribir valores en el
array. De hecho, dada la sentencia:
int [] serie = new int[5];
¿Cuánto valen los enteros del array referenciado por serie? Hay dos posibilidades:
1.
Si serie ha sido declarada a nivel de clase tienen un valor por defecto:
−
−
−
−
2.
Cero, en el caso de tipos primitivos numéricos.
Carácter nulo en el caso de char
false en el caso de boolean
null en el caso de referencias
Si serie ha sido declarada dentro de un método su valor es indefinido.
Los arrays se pueden inicializar en el momento de la declaración, continuando ésta con un signo
igual y una lista separada por comas y encerrada entre llaves de inicializadores. Por ejemplo:
int [] serie = {1,2,3,4,5}; //Se ha creado implícitamente
Tema 4: Arrays.
86
En esta sentencia estamos declarando la referencia serie, creando un array de 5 enteros, asignando
una referencia al array recién creado a serie e inicializando los 5 enteros del array. El tamaño del
array queda determinado por el número de elementos de la lista.
Esta inicialización es muy útil en algunos casos, pero ¿y si necesitamos un array con 5000
elementos? O ¿y si nos interesa que todos los valores del array se inicialicen al mismo valor?
Necesitamos una forma sencilla y eficiente de acceder a cada una de las posiciones del array.
Acceso a los elementos de un array.
Nos podemos referir a cualquier elemento del array mediante el nombre del
array seguido de la posición del elemento entre corchetes.
El número de posición se denomina índice.
Consideremos la sentencia:
int [] serie = new int[10];
La siguiente porción de código que inicializa los elementos del array:
for (int i = 0; i < 10; i++){
serie[i] = i * i;
}
Los elementos del array ocupan posiciones de memoria contiguas (figura 4), que se numeran
empezando por cero. En nuestro ejemplo:
−
−
El primer elemento es serie[0] y el último serie[9].
Para referirnos al i-ésimo elemento escribimos serie[i-1].
Figura 4: Elementos de un array
Tema 4: Arrays.
87
Los subíndices pueden ser cualquier expresión entera que evalúe un valor dentro de los límites del
array. Por ejemplo:
int a = 4;
int b = 3;
serie[a + b] += 2;
// sumar dos a serie[7]
Los elementos de un array se comportan como cualquier otra variable de su tipo y pueden usarse
en expresiones.
int suma = serie[0] + serie[1];
No podemos acceder a posiciones del array inexistentes. Si tenemos:
int [] serie = new int[10];
E intentamos hacer:
int x = serie[17];
La máquina virtual de Java detecta que intentamos acceder a una posición no existente y lanza una
excepción que provoca (si no es tratada) que el programa aborte 1:
IndexOutOfBoundsException
El acceso a posiciones inexistentes es algo peligroso ya que en el mejor de los casos estamos
accediendo a algo indefinido y en el peor podemos destruir información útil. En el caso de Java esto
no puede ocurrir porque cualquier intento de sobrepasar los límites del array es detectado. No
obstante, es una situación que hay que evitar porque da lugar a que se aborte la ejecución del
programa. El límite inferior de un array es siempre 0, el superior se determina al crear el array.
Pero no siempre sabemos a qué array está apuntando una referencia. La cuestión es ¿podemos
preguntarle a un array su tamaño?
Longitud de un array.
Los arrays son objetos y, como veremos en el tema 6, los objetos tienen propiedades (atributos)
que pueden consultarse siempre que sean públicas. Java define para los arrays el atributo length
que guarda el número de elementos del array y que se consulta según la sintaxis:
nombre_array.length
Por ejemplo:
int serie[] = new int[10];
serie.length
// nos devuelve el valor 10
El subíndice no puede sobrepasar la posición del último elemento del array (length –1). Los
cuadros 1 y 2 muestran dos ejemplos completos de uso de arrays en los que se utiliza esta
propiedad.
1
Veremos parcialmente las excepciones en el tema 5 (métodos) y ampliaremos conocimientos en el tema
6 (orientación a objetos).
Tema 4: Arrays.
Cuadro 1: Inicialización y suma de los elementos de un array de enteros.
class Ejemplo41{
final int TamañoArray = 10;
int s[];
int total;
public static void main(String args[]){
s = new int[TamañoArray];
for (int i = 0; i < s.length; i++){
s[i] = 2 + 2 * i; // 2, 4, 6, ..., 20
}
// suma elementos
for ( int i= 0; i < s.length; i ++){
total += s[i];
}
}
} // Fin de clase Suma
Cuadro 2: Se ha realizado una encuesta a 20 personas acerca de la calidad de la comida de un
restaurante en una escala de 1 a 10. Se trata de colocar las 20 respuestas en un array de enteros
y resumir los resultados del sondeo.
class Ejemplo42{
int respuestas[ ] = {1, 2, 6, 4, 8, 5, 9, 7, 8, 10,
1, 6, 3, 8, 6, 10,3, 8, 2, 7};
int frecuencia[ ];
public static void main(String args[]){
frecuencia = new int[11];
// No utilizamos el primer elemento. Cada respuesta es
// el subíndice del array frecuencia.
for ( int i = 0; i < respuestas.length; i++) {
++frecuencia[respuestas[i]];
}
}
} // Fin de la clase Sondeo
88
Tema 4: Arrays.
89
Observaciones.
−
−
−
−
−
−
La palabra array se ha traducido de muchas maneras (arreglos, formaciones, vectores,
matrices,…) pero ninguna de ellas ha cuajado por completo.
Los arrays son objetos y por tanto accedemos a ellos usando referencias pero NO existe una
clase array ni métodos asociados a los arrays. Los arrays son una construcción del lenguaje.
La expresión serie.length es la lectura de un dato asociado al array (su tamaño).
No hay restricciones respecto del tipo de datos que puede contener un array (pueden ser tanto
tipos de datos primitivos como referencias a objetos de una clase).
Los arrays tienen un tamaño fijo por eso se dice que son estructuras estáticas de datos (en
contraposición con las estructuras dinámicas de datos que si pueden variar el tamaño).
Las referencias de arrays se pueden asignar a arrays de diferentes tamaños.
Ordenación de arrays.
Un array a está ordenado si se cumple que:
∀ pareja de subíndices i,j, si i ≤ j
⇒ a[i] ≤ a[j]
Algoritmo de la burbuja.
Uno de los algoritmos de ordenación más usuales es el llamado algoritmo de la burbuja, que dice
así:
Sea el array a.
Repetir (a.length – 1) veces:
1.
2.
Realizar una pasada por el array.
Comparar pares de elementos sucesivos.
→ Si un par está en orden se deja como está.
→ Si no se intercambian los valores.
Se compara en cada pasada a[0] con a[1] , a[1] con a[2] , a[2] con a[3] y así sucesivamente.
−
−
−
−
Un valor grande puede bajar varias posiciones de una sola pasada, pero uno pequeño sólo
puede subir una posición.
En la primera pasada el valor más grande quedará en la última posición del array (a.lenght –1)
En la segunda pasada el segundo valor más grande quedará en la penúltima posición.
Se puede comprobar que hacen falta un número de pasadas igual a la longitud del array menos
1.
Tema 4: Arrays.
90
int a[] = {4, 3, 2, 1}
Inicial
Pasada 1
Pasada 2
Pasada 3
4
3
2
1
2
1
3
3
3
1
2
4
1
4
2
4
La programación en Java del algoritmo se muestra en el cuadro 3.
Cuadro 3: Algoritmo de la burbuja.
public class Ejemplo43 {
final static int TamañoArray = 10;
static int [] a = new int [TamañoArray];
public static void main(String args[] ) {
// Inicializamos el array.
for (int i = 0; i < a.length; i++) {
a[i] = a.length - i;
}
// Traza. Imprimimos el array
System.out.print("Array Inicial\t");
for (int j = 0; j < a.length; j++){
System.out.print(a[j] + " ");
}
System.out.println();
int intercambio = 0;
for (int pasadas = 0; pasadas < a.length-1; pasadas++ ) {
for (int i = 0 ; i < a.length- 1- pasadas; i++) {
if (a[i] > a[i+1]){
intercambio = a[i];
a[i] = a[i+1];
a[i+1] = intercambio;
}
}
// Traza para ver cómo queda el array tras cada pasada.
// Imprimimos el array
System.out.print("Pasada " + (pasadas + 1) + " \t");
for (int j = 0; j < a.length; j++){
System.out.print(a[j] + " ");
}
System.out.println();
}
}
}
Tema 4: Arrays.
91
Un algoritmo de ordenación de arrays muy curioso es el denominado quick-short cuyo estudio se
deja como ejercicio. Existe una buena descripción en http://es.wikipedia.org/wiki/Quicksort.
Búsqueda en arrays.
Se trata de determinar si el array contiene un elemento que coincide con el valor de una clave.
Búsqueda lineal
La búsqueda lineal compara cada elemento del array con la clave de búsqueda. Si el array no está
ordenado es igualmente probable que el elemento buscado esté al principio o al final. El número
medio de comparaciones es igual a la mitad del tamaño del array.
La búsqueda lineal funciona bien en arrays pequeños, pero es muy poco eficiente en arrays grandes
y en arrays ordenados.
Orden de complejidad: O(n)
La programación de la búsqueda lineal es muy sencilla y se muestra en el cuadro 4.
Cuadro 4: Búsqueda lineal.
public class Ejemplo42 {
static int a[] = {2,3,6,1,4,7,9,4,3,5};
static int clave = 7;
public static void main(String[] args) {
for ( int n = 0; n < a.length; n++ ) {
if (a[n] == clave) {
System.out.println("La clave en" + n);
break;
}
}
}
}
Búsqueda binaria.
Si el array está ordenado, un algoritmo muy eficiente es el de búsqueda binaria. El algoritmo dice
así:
Comparar clave con el elemento situado en la mitad del array (elemento medio).
IF (clave == elemento medio) → Hemos terminado.
ELSE IF (clave < elemento medio) → buscar en la primera mitad del array,
ELSE → buscar en la segunda mitad del array.
El proceso se repite sucesivamente hasta que:
La clave sea igual al elemento medio del subarray que queda.
OR
El subarray que queda consta de un solo elemento distinto de la clave
Tema 4: Arrays.
92
El algoritmo de búsqueda binaria elimina de la búsqueda la mitad de los elementos que quedan en
el array después de cada comparación.
1024 elementos (1024 = 210) → 10 comparaciones como máximo.
→ 20 comparaciones como máximo
1.048.576 elementos (220)
El número máximo de comparaciones es el exponente de la primera potencia de 2 mayor que el
número de elementos del array.
Orden de complejidad: O(log2 n)
Es un algoritmo muy eficiente pero sólo funciona con arrays ordenados
int [] a = {2,4,6,8,10,12,14,16,18,20,22}
Clave = 20
Índice
0
1
2
3
4
5
6
7
8
9
10
Valor
2
4
6
8
10
12
14
16
18
20
22
Al aplicar el algoritmo:
Inicial
Pasada 1
Pasada 2
Pasada 3
20
2
4
6
8
10
12
14
14
16
16
18
18
20
20
20
22
22
22
La codificación en Java se muestra en el cuadro 5.
Tema 4: Arrays.
93
Cuadro 5: Búsqueda binaria
public class Ejemplo44 {
static int a[ ] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22};
public static void main (String args []) {
int
int
int
int
bajo = 0;
alto = a.length - 1;
medio;
clave = 20;
while (bajo <= alto) {
medio = (bajo + alto) / 2;
if (clave == a[medio]) { // se encontró
System.out.println ("Lo encontré en " + medio);
break;
}
else if (clave < a[medio]) {
alto = medio - 1;
}
else {
bajo = medio + 1;
}
}
}
}
Arrays Bidimensionales.
Estrictamente hablando en Java sólo pueden definirse arrays de una dimensión. Sin embargo, los
elementos de un array pueden ser a su vez referencias a arrays pudiéndose programar de este
modo tablas de dos o más dimensiones como un array de arrays. Las tablas que requieren dos
índices para identificar un elemento se llaman arrays con doble índice.
−
−
El primer índice se refiere a la fila. Este es el índice del array de arrays e identifica a un
array.
El segundo índice se refiere a la columna. Este es el índice de un array e identifica a un
elemento del array identificado por el primer índice.
Para simplificar hablaremos de arrays de dos o más dimensiones, aunque en Java esto supone un
cierto abuso del lenguaje 1. Por ejemplo, en la figura 5 se muestra la disposición de los elementos del
array:
int [][] a = new int[3][4];
No ocurre lo mismo en otros lenguajes donde los arrays multidimensionales están realmente definidos en el lenguaje. En
Java los definimos aprovechando los mecanismos del lenguaje.
1
Tema 4: Arrays.
94
Figura 5: Array de dos dimensiones.
Obsérvese que:
−
−
−
a es un array de 3 arrays de enteros .
Cada a[i] es un array de 4 enteros.
a[i][j] es un entero.
Los arrays de dos dimensiones (en general de cualquier dimensión) se pueden declarar e inicializar
de manera similar a los arrays de una dimensión. Por ejemplo:
int b [][] = { {1, 2}, {3, 4, 5} }
Los valores se agrupan por fila encerrados entre llaves (figura 6):
−
−
1 y 2 inicializan b[0][0] y b[0][1]
3, 4 y 5 inicializan b[1][0], b[1][1] y b[1][2]
Figura 6: int b [][] = { {1, 2}, {3, 4, 5} }
Obsérvese que en la declaración aparecen dos parejas de corchetes. Esto es porque, como ya se ha
mencionado, Java no soporta arrays multidimensionales, sino arrays de arrays. Hablar de arrays de
dos o más dimensiones no es estrictamente correcto. Lo que estamos declarando en el ejemplo es
un array cuyos elementos son dos arrays de enteros, uno conteniendo dos elementos {1, 2} y el
otro conteniendo tres elementos {3, 4, 5}.
Esto se muestra con más claridad en el ejemplo del cuadro 5 donde se inicializa cada elemento del
array de arrays explícitamente con un array diferente. En el ejemplo también se ve que no es
necesario especificar la longitud de cada array en la declaración del array bidimensional:
int triangulo [][] = new int[3][];
Cuando se recorren arrays “bidimensionales” hay que tener en cuenta que cada “fila” puede tener
una longitud diferente. Se evitan errores preguntando siempre a cada array su longitud:
triangulo[i].length representa la longitud del array i-ésimo de triangulo.
Tema 4: Arrays.
95
Cuadro 5: Arrays bidimensionales con filas diferentes longitudes
public class Ejemplo45 {
public static void main(String [] args){
int triangulo [][]
triangulo[0] = new
triangulo[1] = new
triangulo[2] = new
= new int[3][];
int[1];
int[2];
int[3];
// inicialización
for (int i = 0; i < triangulo.length; i++){
for (int j = 0; j < triangulo[i].length; j++){
triangulo[i][j] = j;
}
}
// imprimimos el array
for (int i = 0; i < triangulo.length; i++){
for (int j = 0; j < triangulo[i].length; j++){
System.out.print(triangulo[i][j] + " ");
}
System.out.println();
}
System.out.println();
int cornisa [][] = {{1, 2, 3}, {1, 2}, {1}};
for (int i = 0; i < cornisa.length; i++){
for (int j = 0; j < cornisa[i].length; j++){
System.out.print(cornisa[i][j] + " ");
}
System.out.println();
}
}
}
Cuadro 6: Suma de los elementos de un array bidimensional
public class Ejemplo46 {
public static void main(String[] args) {
int a [][] = { {1,2}, {4} };
int total = 0;
for (int fila = 0; fila < a.length; fila++){
for (int col = 0; col < a[fila].length; col++) {
total += a[fila][col];
}
}
System.out.println("Suma = " + total);
}
}
Tema 4: Arrays.
96
Cuadro 7: Encontrar la nota máxima y mínima de un array de calificaciones, donde cada fila
representa un estudiante y cada columna representa una calificación en diferentes exámenes.
public class Ejemplo47 {
static int notas[][] = {{77,68,86,73}, {96,87,89,81}, {70,90,86,81}};
public static void main (String args[]){
int notaBaja = 100;
int notaAlta = 0;
for (int i = 0; i < notas.length; i++ ) {
for (int j = 0; j < notas[i].length; j++ ) {
if (notas[i][j] < notaBaja) {
notaBaja = notas[i][j];
}
if (notas[i][j] > notaAlta){
notaAlta = notas[i][j];
}
}
}
System.out.println("La nota baja es: " + notaBaja);
System.out.println("La nota alta es: " + notaAlta);
}
}
Otras estructuras estáticas de datos.
Al principio del tema destacábamos dos características de los arrays:
−
−
Son estructuras de datos estáticas: su tamaño no cambia durante la ejecución del
programa.
Todos los datos son del mismo tipo.
En los programas suelen hacer falta estructuras de datos capaces de agrupar datos de distintos
tipos. Por ejemplo, imagínense el caso de tener que modelar una cuenta bancaria en la que hay
datos que se pueden representar mediante cadenas de caracteres (nombre del titular), otros
mediante números enteros (fondos) y otros mediante tipos de datos definidos por el programador
(fecha de de apertura). Los lenguajes de programación estructurados o los lenguajes orientados a
objeto que son una evolución de los estructurados (por ejemplo Ada05 o C++) proporcionan
estructuras de datos con estas características:
−
−
Son estructuras de datos estáticas: su tamaño no cambia durante la ejecución del
programa.
Sus datos pueden ser de diferentes tipos.
A modo de ejemplo se muestra una estructura (struct) de C y un registro (record) de Ada.
typedef struct Cuenta {
String titular;
int
fondos;
Date
fechaApertura;
}
type Cuenta is
record
titular: String;
fondos: Integer;
fecha_apertura: Date;
end record;
Tema 4: Arrays.
97
Este tipo de estructuras de datos no existen en java porque Java proporciona una estructura de
datos que realiza la misma función y que además es mucho más flexible: la clase, que se explicará en
el tema 6.
Tema 5: Abstracción funcional. Métodos.
Lección 5: Abstracción Funcional
99
Objetivos
Conocer la programación modular a partir del uso de métodos.
Ser capaces de crear nuevos métodos.
Manejar los mecanismos para pasar información entre métodos.
Conocer cómo la visibilidad de identificadores es limitada a regiones específicas. Escribir y
usar métodos recursivos.
Contenido
Abstracción funcional y programación modular.
Definición de métodos en Java.
Paso de parámetros.
Variables locales. Duración y alcance.
Recursión.
Librerías.
Tema 5: Abstracción funcional. Métodos.
Abstracción funcional y programación modular.
100
Funciones y llamadas a función.
Función: Sección de código (conjunto de instrucciones) que puede recibir datos de
entrada y producir datos de salida.
Abstracción funcional: las funciones se invocan para realizar una tarea, pero sin necesidad
de saber cómo la llevan a cabo.
En programación, una función 1 es una porción de código que realiza una tarea específica y que es
relativamente independiente del resto del código. Casi todos los lenguajes de programación
proporcionan algún tipo de mecanismo para la definición de funciones. Las funciones reciben un
nombre, pueden recibir datos de entrada a través de una lista de parámetros y pueden retornar un
resultado. El nombre de la función, su lista de parámetros y el resultado que produce constituyen la
interfaz de la función (figura 1).
Figura 1: Interfaz (cabecera) y cuerpo de una función.
Las funciones pueden ser invocadas desde cualquier punto del programa. Una función puede
invocar otras funciones e incluso invocarse a sí misma. La figura 2 muestra el mecanismo de
llamada o invocación de una función.
Figura 2: Invocación de una función.
También reciben el nombre de subrutina, procedimiento, método, etc. Según la denominación que se emplee puede haber
diferencias de matiz, pero la definición y el discurso del apartado y del tema se ajusta a todos ellos.
1
Tema 5: Abstracción funcional. Métodos.
101
Cada vez que se realiza una invocación de una función, el flujo de control del programa se desplaza
a la instrucción inicial de dicha función, pero antes es necesario almacenar en alguna parte la
información que necesita la función para ejecutarse y para retornar el control al llamante. Para
guardar dicha información, en el momento de la llamada se genera un registro de activación
(también reciben el nombre de stack frames) donde se guardan los parámetros de la función, sus
datos locales, la dirección de retorno y donde se reserva además un espacio para que la función
deposite los resultados que genera (valor de retorno). Este registro de activación se guarda a su vez
en una zona de memoria denominada pila o stack que funciona según un esquema LIFO (Last InFirst Out): último en entrar primero en salir. Cuando la función termina de ejecutarse el control
retorna al punto del programa inmediatamente posterior a la invocación de la función. La
estructura LIFO de la pila permite gestionar las llamadas a función anidadas con mucha facilidad.
Por ejemplo, en la figura 3 se asume que desde el programa principal se llama a la función A y desde
la función a la función B. Cuando B termina su ejecución se elimina su registro de activación y se
retoma la ejecución de A y cuando A termina su ejecución se elimina su registro de activación y se
retoma la ejecución de main.
4. Se retorna a
main y se
elimina el
registro de
activación de A
Código de main()
A()
1. Se crea registro
de activación de
A y se almacena
en Stack
STACK
Reg. Act. de B()
Código de A()
B()
Código de B()
3. Se retorna a A y
se elimina el
registro de
activación de B
2. Se crea registro
de activación de
B y se almacena
en Stack
STACK
STACK
Reg. Act. de A()
Valor de
t
Dir. de retorno
1
Valor de
t
Dir. de retorno
STACK
Reg. Act. de A()
Reg. Act. de A()
Valor de
t
Valor de
t
Dir. de retorno
2
STACK
Dir. de retorno
3
4
Figura 3: Anidamiento de llamadas.
Es muy importante darse cuenta de que lo único que debe conocerse de una función para poder usarla
es su interfaz. Para que esto sea posible, la porción del código encapsulada dentro de la función no
debe manipular más información que la que obtiene a través a de sus parámetros, es decir, las
funciones deben ser auto-contenidas. Si las funciones son auto-contenidas y se organizan en
bibliotecas pueden utilizarse para la construcción de programas que no tienen nada que ver entre
sí. En este sentido, las funciones son el mecanismo más inmediato para llevar a cabo una
programación modular.
Tema 5: Abstracción funcional. Métodos.
Las programación modular.
102
La programación modular es una técnica de diseño de software en la que los programas se
construyen ensamblando porciones de código independientes llamadas módulos. Cada módulo está
orientado a resolver un aspecto concreto del programa y se relaciona con otros módulos a través de
una interfaz que define los elementos provistos y requeridos por el módulo. La separación de
interfaz e implementación es un aspecto esencial que hace posible la programación modular:
−
−
La interfaz oculta la implementación del módulo y este ocultamiento permite cambiar la
implementación de un módulo sin afectar al resto.
Puesto que las interacciones entre los módulos se realizan a través de sus interfaces, una
vez que éstas han sido definidas, es posible asignar la implementación de cada módulo a un
programador diferente, es decir es posible la división del trabajo entre muchos
programadores. Todas las dependencias entre módulos deben poder resolverse a través de
sus interfaces, sin asumir ninguna implementación concreta de los mismos.
Principio de dependencia de interfaces e independencia de implementaciones: haga que su
código dependa de interfaces, pero no de implementaciones.
Es fácil percibir que el diseño modular promueve la reutilización del código, ya que los mismos
módulos pueden utilizarse para construir muchos programas. La consecución de módulos
reutilizables no es, sin embargo, un proceso inmediato. Módulos que se ajustan perfectamente a las
necesidades de un programa pueden ser completamente inconvenientes en otros programas
parecidos. Uno de los factores que más limita la reutilización de un módulo es su dependencia de
otros módulos. Supongamos que queremos usar un módulo A y que éste a su vez necesita usar los
módulos B, C y D. Si esto ocurre estamos obligados a incluir en nuestro programa los módulos B, C y
D 1. Las dependencias entre módulos definen su grado de acoplamiento mutuo. Cuantas más
dependencias hay entre dos o más módulos, mayor es su acoplamiento. Un buen diseño de los
módulos debe estar encaminado a reducir su acoplamiento. Idealmente, un módulo debería ser una
pieza de software independiente.
La definición de módulo software depende del paradigma de programación y del estilo de diseño.
En programación procedural un módulo puede ser una función, pero es más frecuente que sea una
agrupación de funciones altamente cohesionadas, por ejemplo una librería de funciones 2. El
concepto de cohesión aparece cuando un módulo es lo bastante grande como para distinguir en él
diferentes partes y es uno de esos conceptos fáciles de entender, pero difíciles de explicar con
precisión en pocas palabras 3. De forma muy simplificada puede decirse que un módulo está
cohesionado si todos sus elementos están enfocados hacia un mismo objetivo. Si el módulo es una
agrupación de funciones matemáticas no tiene sentido incluir en él funciones que procesan cadenas
de caracteres. Lo correcto sería definir una nueva librería y agrupar en ella a las funciones de
procesamiento de caracteres. Un buen diseño debe maximizar la cohesión interna de los módulos y
minimizar y si es posible eliminar el acoplamiento entre módulos. Existe una relación entre
acoplamiento y cohesión. Cuanto más cohesionados son los módulos, más sencillo es evitar sus
dependencias mutuas 4.
U otros que ofrecieran al menos los mismos elementos en sus interfaces.
Lo cual no quiere decir que la función deje de ser un módulo, simplemente sirve para definir otros elementos más grandes
que también pueden considerarse módulos.
3 Pueden echar un vistazo a http://latecladeescape.com/w0/ingenieria-del-software/acoplamiento-y-cohesion.html
4 Más sencillo, no quiere decir fácil, sino menos difícil.
1
2
Tema 5: Abstracción funcional. Métodos.
Las funciones como mecanismo de abstracción.
103
Llegados aquí, merece la pena recapitular el camino ya andado y ponerlo en el contexto del que
vamos andar en este tema. Mediante la abstracción de datos hemos dotado de significado a las
secuencias de bits que manejan los computadores y esto nos ha permitido ignorar los detalles de su
implementación en una máquina concreta. Sólo las propiedades abstractas de los datos son visibles
para el programador y para el resto del código, mientras que la implementación permanece
enteramente privada y puede cambiarse sin que el programa se vea afectado. La abstracción de
control nos ha provisto de mecanismos para la ejecución condicional o reiterada de una porción de
código sin tener que especificar a nivel de registros y posiciones de memoria cada una de las
acciones de control y sin necesidad de conocer los mecanismos de direccionamiento de la máquina
subyacente. La abstracción funcional nos permite ahora encapsular detrás de una interfaz bien
definida una porción de código que implementa un comportamiento o un algoritmo determinados.
Las funciones se utilizan como herramientas de abstracción (separación) porque su comportamiento
(lo que hacen) puede ser separado (abstraído) de su implementación (cómo lo hacen). Al igual que
ocurría con la abstracción de datos, pero a un nivel de abstracción superior, sólo las propiedades
abstractas de la función definidas a través de su interfaz son visibles para el programador y para el
resto del código, mientras que la implementación permanece enteramente privada y puede
cambiarse sin que el programa se vea afectado. De esta forma, la abstracción funcional nos abre la
puerta de la programación modular, que es la única manera de diseñar, codificar y mantener
grandes programas. La abstracción funcional está estrechamente ligada a las técnicas de diseño
funcional descendente y a la programación estructurada. Los problemas complejos pueden
descomponerse en subproblemas más sencillos 1, cada uno de los cuales puede expresarse como
una llamada a función.
La abstracción funcional permite llevar a cabo el concepto de modularidad:
−
−
−
Una función agrupa a un conjunto de instrucciones altamente cohesionadas
Una función realiza una tarea específica.
Para usar una función no es necesario conocer su implementación.
Las funciones similares se agrupan en bibliotecas (en java en clases, como veremos enseguida):
funciones matemáticas, funciones para el manejo de caracteres, funciones para el maneja de
estructuras de datos complejas, etc. De hecho, el éxito o fracaso de un determinado lenguaje de
programación depende en gran medida de las bibliotecas que lo acompañan. En los lenguajes
procedurales están bibliotecas son bibliotecas de funciones. En los lenguajes orientados a objetos
las bibliotecas son bibliotecas de clases, pero las clases están hechas, entre otras cosas, de
funciones.
Para que la abstracción funcional sea efectiva, es muy importante que la tarea asignada a la función
esté bien definida y que dicha finalidad esté descrita mediante su nombre. En caso de duda es
preferible definir varias funciones pequeñas que una grande. Mejor una función para ordenar un
array y otra para buscar un elemento en un array ordenado, que una única función que ordene el
array y luego busque el elemento. Las funciones sin un objetivo concreto son difíciles de reutilizar.
Las funciones demasiado extensas hacen difícil su comprensión y depuración. Observe como esta
concreción en el objetivo está relacionada con los principios de alta cohesión y bajo acoplamiento:
cuántas más responsabilidades tenga una función menor será su cohesión interna y más llamadas
tendrá que realizar a otras funciones, aumentando de esta forma su acoplamiento. Otro punto
importante es que la función no manipule más datos que aquellos que recibe a través de su interfaz.
Aunque a partir de aquí se va a utilizar el lenguaje Java como vehículo para la explicación de la
abstracción funcional, los conceptos que se van a ver en este tema aparecen en todos los lenguajes
de alto nivel modernos, si bien con considerables diferencias sintácticas entre unos y otros. Se
tratará de separar en la medida de lo posible lo que es general y lo que es específico del lenguaje
Java.
1
En programación se suele aludir a este principio mediante el aforismo “Divide y vencerás”.
Tema 5: Abstracción funcional. Métodos.
Definición de métodos en Java.
104
Métodos y clases.
Para empezar vamos a dejar de hablar de funciones y vamos a empezar a hablar de métodos, porque
ese es el nombre que reciben las funciones en Java y en general en los lenguajes orientados a
objetos. El cambio de nombre está relacionado con el cambio de paradigma de programación (de
procedural a orientado a objetos) y tiene algunas implicaciones semánticas. En este tema vamos a
trabajar con la definición de función dada en el punto anterior. En el siguiente tema se dará una
definición de método que extiende la definición de función y se ampliarán de acuerdo con ella
algunos de los conceptos que se presentan en este tema.
Hablar de métodos en Java significa inevitablemente hablar de clases, ya que en Java no existen
métodos fuera de las clases 1. Sin embargo, no es necesario saber mucho de las clases para poder
abordar este tema. De momento, podemos ver las clases de Java como un ámbito donde agrupar
datos y métodos. Aplicando los principios de alta cohesión y bajo acoplamiento podemos esperar
que si la clase está bien diseñada todos los métodos de una clase tengan un objetivo o finalidad
común (cohesión) y que sus dependencias con los métodos de otras clases sean las imprescindibles
(acoplamiento). Sabemos además que en una clase puede haber un método especial, el método
main, que representa a un programa.
class UnaClase {
// variables
// métodos
}
Las clases también encapsulan datos. Estos datos son globales a la clase y visibles desde el interior
de los métodos. Es decir, un método definido en una clase puede utilizar cualquier variable definida
en dicha clase sin necesidad de que se le pase como parámetro 2. Esto a primera vista parece una
violación de la interfaz del método, ya que el método manipula datos no definidos en su interfaz. Sin
embargo, desde el punto de vista de Java no lo es, porque en Java la unidad de diseño no es el
método, sino la clase. Es decir, los métodos ven y utilizan las variables de su clase, pero los usuarios
del método no ven dichas variables, ni siquiera saben de su existencia, salvo que se hagan
explícitamente visibles (ya veremos cómo). No obstante, hay que ser cuidadoso en la forma de
manipular dentro de los métodos las variables que se definen fuera de los mismos. Finalmente está
el tema de los objetos, que tampoco queremos abordar hasta el siguiente tema. En todos los
ejemplos de este tema las variables y métodos están marcados como static. Cuando un método o
variable de una clase se marca como static es independiente de los objetos de esa clase. Hechas
estas observaciones estamos en disposición de hablar de los métodos en Java sin echar mano, por el
momento, del paradigma de la orientación a objetos. La sintaxis de los métodos en Java es la
siguiente:
[Modificadores] tipoDevuelto identificadorMetodo([argumentos]){
// cuerpo del método
}
Por ejemplo:
public static int maximoDosNumeros(int n1, int n2) // interfaz
{
return n1 > n2? n1:n2;
// cuerpo con la implementación.
}
Hay lenguajes de programación en los que las funciones y las clases pueden existir por separado
Esto no es del todo cierto. Hay una restricción que depende de si variables y métodos son static o no, pero no lo veremos
hasta el siguiente tema.
1
2
Tema 5: Abstracción funcional. Métodos.
105
Los modificadores son las palabras reservadas public, protected, private, final y static,
cuyo significado se verá en el siguiente tema.
En Java no es posible definir un método dentro de otro método.
Tipo del valor devuelto por el método.
El tipo del valor devuelto por un método puede ser un tipo primitivo Java, una referencia a un
objeto o void. void es una palabra reservada de Java que indica que un método no devuelve
ningún valor.
Figura 2: Valores devueltos por los métodos Java.
Terminación de un método.
Existen dos posibilidades para terminar un método:
1. Si el método devuelve void (nada) el método termina cuando llega al final (cierra llaves) o
cuando aparece return:
public static void pintaCirculo(float r){
// código para pintar el círculo
}
// este es el final del método
public static void saluda(String mensaje){
if (!primeraVez){
return; // aquí termina
}
else {
System.out.println(mensaje);
}
}
2. Si el método devuelve algo distinto de void entonces se devuelve el control mediante:
return expresión
donde expresión produce un valor cuyo tipo es el declarado en la cabecera del método.
int potencia(int x, int y){
int contador = 0, resultado = 1;
while (contador != y){
resultado = resultado * x;
contador++;
}
return resultado; //aquí se devuelve el resultado.
}
Cuando se hace return se devuelve el control al invocador del método.
Tema 5: Abstracción funcional. Métodos.
106
Es un error de compilación cuando se devuelve siendo void el tipo de retorno.
public void saluda(String mensaje){
if ((primeraVez))
return false; // error
else
System.out.println(mensaje);
}
Es un error de compilación no hacer return cuando hay que devolver un valor de un tipo.
int potencia(int x, int y){
int contador =0, resultado = 1;
while (contador != y){
resultado = resultado * x;
contador++;
}
// Error: No se retorna valor
}
Lista de parámetros
La lista de parámetros (argumentos) es una lista de las declaraciones de parámetros que se pasan al
método para su ejecución. La lista puede estar vacía pero los paréntesis son obligados:
public void suficiente()
public void pocaCosa
// Correcto
// Error de sintaxis.
Es obligatorio indicar el tipo de cada parámetro:
double potencia (double x, double y)
double potencia (double x, y)
// Correcto
// Error de sintaxis
Parámetros formales y parámetros reales
Se denominan parámetros formales a aquellos que aparecen en la cabecera de la función y
parámetros reales a los que aparecen en la llamada a la función. Los parámetros reales deben
coincidir con los parámetros formales declarados en la interfaz del método.
public static void main(String [] args){
int k = 3;
boolean flag = true;
int x = f(7, false);
int y = f(0, flag);
int z = f(k, flag);
// Llamadas incorrectas: No hay concordancia entre parámetros
formales
f(true, d, flag); // Debería haber dos parámetros
f(false, 7);
// El primer parámetro debería ser int.
}
reales
y
Tema 5: Abstracción funcional. Métodos.
107
A los parámetros también se les llama argumentos. En algunos lenguajes de programación
parámetro y argumento se utilizan como sinónimos. En C y en Java (aunque no todos los autores)
cuando se habla de parámetros nos estamos refiriendo de los parámetros formales y cuando
hablamos de argumentos nos estamos refiriendo a los parámetros reales. En lo sucesivo
seguiremos esta regla.
Promoción de argumentos. Coerción.
Consideremos la siguiente cabecera de un método:
public static double sqrt(double d)
Y el siguiente uso del método:
int numero = 4;
System.out.println(sqrt(numero));
Java promociona implícitamente el argumento de int a double antes de pasarlo a sqrt(),
pasando 4.0 en lugar de 4. A esto se le llama coerción de argumentos y sigue determinadas reglas
de promoción, que especifican cómo los tipos pueden convertirse a otros sin que haya pérdida de
información.
Las reglas de promoción de Java son las siguientes:
Tipo
double
Promociones permitidas
float
double
long
float o double
int
long, float o double
char
int, long, float o double
short
int, long, float o double
byte
short, int, long, float o double
boolean
ninguna (ni true ni false son números)
ninguna (no hay tipo más grande que double)
Estas reglas se aplican en la coerción de argumentos y en las expresiones que contienen dos o más
tipos de datos. Hay que hacer dos observaciones:
−
−
Los valores originales de las variables no se modifican: temporalmente se promocionan.
Las conversiones a tipos más pequeños sólo es posible haciendo conversión explícita
mediante casting. Puede perderse información.
Paso de parámetros por valor y por referencia.
Los métodos obtienen la información que necesitan a través de los argumentos que se les pasa al
invocarlos. Existen dos formas de pasar los argumentos a los métodos: paso por valor y paso por
referencia (figura 3).
Paso de parámetros por valor: se le pasa al método una copia del valor del argumento. El paso
por valor ofrece una gran seguridad. El método no trabaja con el argumento original, sino con una
Tema 5: Abstracción funcional. Métodos.
108
copia, y por ello los cambios realizados dentro del método no afectan a la variable que se utilizó
como argumento.
Paso de parámetros por referencia: se le pasa al método una referencia a los datos. El método
puede modificar los datos que se le pasan como argumento. El paso por referencia ahorra memoria
(no se copian los datos), pero es menos seguro que el paso por valor (el método puede modificar los
datos que se le pasan).
Figura 3: Paso de argumentos por valor y por referencia.
Se dice que en Java, los tipos primitivos siempre se pasan por valor y los objetos siempre por
referencia. Lo mismo puede decirse de la sentencia return, aunque en este caso el sentido en el
que fluye la información es el contrario, del método al código llamante. Si el tipo de retorno es
primitivo la sentencia return devuelve una copia del valor producido en el método, si es un objeto
devuelve una referencia al objeto que retorna el método.
Variables locales en los métodos.
Es posible declarar variables locales dentro de los métodos. La sintaxis que se sigue es la ya
conocida.
[modificador] tipoValorDevuelto nombre([argumentos]){
// declaración de variables locales
// enunciados
}
public static void intercambio(int x, int y){
int auxiliar;
auxiliar = y;
y = x;
x = auxiliar;
}
Con la declaración de variables locales tenemos que en un método puede manipularse información
que puede ser:
−
−
−
Argumentos pasados en la llamada. Para evitar ambigüedades las variables locales no
pueden recibir el mismo nombre que un parámetro formal.
Variables locales.
Variables declaradas en la clase fuera de los métodos. Recordemos que las clases también
encapsulan datos. Estos datos, llamados variables de instancia, son globales a la clase y
visibles desde el interior de los métodos. Es decir, un método definido en una clase puede
utilizar cualquier variable definida en dicha clase sin necesidad de que se le pase como
parámetro. Un método puede usar variables locales y aquellas definidas fuera del método.
Puede haber coincidencia de nombres. ¿Cómo distinguirlas? La respuesta viene dada por la
duración y el alcance de las variables.
Tema 5: Abstracción funcional. Métodos.
109
Los parámetros y variables locales a un método son variables automáticas. Las diferencias entre las
variables definidas en la clase y las variables automáticas se resumen en la tabla 1.
Duración y alcance de las variables
La duración y reglas de alcance se aplican a todos los identificadores de un programa Java y definen
dónde y cómo pueden usarse los identificadores.
La duración o tiempo de vida de un identificador es el tiempo durante el cual la información está
accesible.
El alcance o ámbito de un identificador determina qué parte del programa ve dicho identificador.
Las variables locales sólo son visibles dentro del método en el que son declaradas y a partir del
lugar en el que son declaradas. Si una variable local se declara dentro de un bloque de código, sólo
es visible en dicho bloque y en los bloques anidados dentro de él. Las variables locales sólo existen
desde el momento en que se declaran hasta el momento en que se sale del bloque en el que han sido
declaradas. Puesto que las variables locales se crean y se destruyen dinámicamente durante la
ejecución del programa reciben el nombre de variables automáticas (creación y eliminación
automáticas).
public static void f(){
int x = 10;
while (x > 0){
int y = x*x + 2*x;
System.out.println(y);
x--;
}
}
// x existe desde aquí
// y existe desde aquí
// Aquí deja de existir y
// Aquí deja de existir x
Tabla 1: Variables de instancia y variables automáticas
Variables de instancia (o de ejemplar)
Variables automáticas (argumentos y variables
locales)
Se definen en una clase, no en un método.
Se definen dentro de un método o de un bloque
(porción de código entre llaves) definido dentro de un
método.
Si son static existen desde que se carga la
clase en memoria hasta el final del programa.
Si no son static existen mientras existe el
objeto que las alberga.
Son visibles en toda la clase.
Si no tienen valores iniciales asignados el
compilador los asigna por defecto (véase
tabla [] del tema 2).
Existen desde que se declaran y mientras se está en el
bloque en el que se declaran.
Son visibles sólo dentro del bloque en el que se
declaran y en los bloques anidados en él.
Deben inicializarse explícitamente antes de ser usadas.
Veamos ahora algunos ejemplos relacionados con el paso de parámetros y las variables locales.
Tema 5: Abstracción funcional. Métodos.
110
Cuadro 1: Paso de parámetros por valor. ¿Qué valor tienen x e y después de la llamada?
class Ejemplo51 {
static int x = 5;
static int y = 3;
public static void intercambio(int x, int y){
int auxiliar;
auxiliar = y;
y = x;
x = auxiliar;
}
public static void main(String args){
intercambio(x, y);
System.out.println(“x = “ + x + “, y = “ + y);
}
}
Cuadro 2: Alcance de las variables. ¿Qué se imprime en la consola?
public class Ejemplo52 {
static int x = 0;
private static int f1(int x){
x *= 2;
System.out.println("f1
-> x = " + x);
return x;
}
public static void main (String []
int x = 5;
System.out.println("main -> x =
f1(x);
System.out.println("main -> x =
x = f1(x);
System.out.println("main -> x =
}
}
main
f1
main
f1
main
->
->
->
->
->
x
x
x
x
x
=
=
=
=
=
5
10
5
10
10
args){
" + x );
" + x );
" + x );
Tema 5: Abstracción funcional. Métodos.
111
Cuadro 3: Alcance de las variables. ¿Qué se imprime en la consola?
public class Ejemplo53 {
static int x = 0;
private static int f2(){
System.out.println("f2
-> x =
return x;
}
public static void main (String []
int x = 5;
System.out.println("main -> x =
f2();
System.out.println("main -> x =
x = f2();
System.out.println("main -> x =
}
}
main
f2
main
f2
main
->
->
->
->
->
x
x
x
x
x
=
=
=
=
=
" + x);
args){
" + x );
" + x );
" + x );
5
0
5
0
0
Paso de arrays como parámetros
En todos los ejemplos vistos hasta ahora los argumentos han sido de tipos de datos primitivos, que,
como sabemos, se pasan por valor. Nos falta por ver ejemplos en los que los parámetros se pasen
por referencia. Para ello tenemos que trabajar con objetos y por el momento los únicos objetos que
conocemos con cierta profundidad son los arrays. Consideremos el código del cuadro 4.
Cuadro 4: Paso de arrays como argumentos a métodos.
public class Ejemplo54 {
static int a[] = {0, 1, 2, 3, 4};
public static void imprimirArray(int a []){
if (a == null){
System.out.println("Array nulo");
return;
}
for (int i = 0; i < a.length; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void modificarArray(int b[]){
for (int j = 0; j< b.length; j++ ) {
b[j] *= 2;
}
}
// Por referencia
public static void modificarElemento(int e){
e *= 2;
}
// Por valor
public static void main(String[] args) {
imprimirArray(a);
modificarArray(a);
imprimirArray(a);
modificarElemento(a[3]);
imprimirArray(a);
}
}
0 1 2 3 4
0 2 4 6 8
0 2 4 6 8
Tema 5: Abstracción funcional. Métodos.
112
El método imprimirArray no realiza ninguna modificación sobre los datos de entrada,
simplemente imprime los elementos del array que se le pasa como argumento.
El método modificarArray modifica los elementos del array. En concreto sustituye cada uno de
los enteros almacenados en el array por el doble de ese entero. Puesto que los arrays se pasan por
referencia es posible modificar los valores contenidos en el array.
El método modificarElemento toma como argumento un tipo de datos primitivo. En este caso,
el argumento se pasa por valor y la variable original no es modificada.
Hasta aquí todo funciona como se ha descrito, los tipos primitivos siempre se pasan por valor y los
objetos siempre por referencia. En consecuencia, los argumentos de tipos de datos primitivos no
pueden modificarse en el interior de los métodos y los objetos si pueden modificarse. Pero hay que
tener cuidado con lo que significa exactamente lo que estamos haciendo. Veamos ahora el ejemplo
del cuadro 5.
Cuadro 5: Paso de arrays como argumentos a métodos.
public class Ejemplo55 {
static int a[] = {1, 2, 3};
public static void modificarArray(int a[]){
int [] b = {4, 5, 5};
a[0] = b[0];
a = b;
// ¿qué se imprime?
System.out.println("Valores de a ANTES de salir del método ");
Ejemplo54.imprimirArray(a);
}
public static void main(String [] args){
System.out.println("Valores de a ANTES de invocar el método ");
Ejemplo54.imprimirArray(a);
modificarArray(a);
// ¿qué se imprime?
System.out.println("Valores de a DESPUÉS de salir del método ");
Ejemplo54.imprimirArray(a);
}
}
Valores de a ANTES de invocar el método
1 2 3
Valores de a ANTES de salir del método
4 5 5
Valores de a DESPUÉS de salir del método
4 2 3
Antes de empezar a comentar la salida que produce el código del cuadro 5 merece la pena que se
den cuenta de que estamos utilizando el código del ejemplo anterior para imprimir el resultado.
Esta es una forma muy desorganizada de reutilizar el código existente, pero lo importante era
resaltar la posibilidad de invocar los métodos de una clase en otra, no la forma en que se ha
organizado el código. Veamos ahora que ocurre con el array a.
En el método modificarArray asignamos a a[0] el valor de b[0] (a[0] = b[0]). La
asignación parece absurda porque posteriormente asignamos la referencia b a a (a = b), es decir
hacemos que a deje de apuntar al array al que apuntaba para apuntar ahora al array al que apunta
b. Cualquier cambio que hubiéramos hecho en el array al que apuntaba la referencia a
anteriormente es inútil porque después de hacer a = b, a dicho array ya no le apunta nadie.
Obsérvese que el array que se imprime antes de abandonar el método contiene {4, 5, 5}.
Tema 5: Abstracción funcional. Métodos.
113
Inmediatamente después de salir del método modificarArray volvemos a imprimir el contenido
del array al que se refiere a y en este caso se imprime {4, 2, 3} es decir el contenido del array al que
apuntaba a, antes de hacer a = b. ¿Qué ha pasado? Lo que ha pasado es que las referencias de los
objetos se pasan por valor. Dentro de un método, podemos cambiar los valores del objeto usando la
referencia pasada como argumento, pero no podemos cambiar la referencia misma. Las referencias
no se cambian dentro de los métodos porque no utilizamos las referencias originales, sino una
copia de las mismas. Los cambios realizados dentro del método se realizan sobre la copia, no sobre
el original. El ejemplo del cuadro 6 ilustra el mismo principio, pero en este caso utilizando
referencias a cadenas de caracteres.
Cuadro 6: Las referencias se pasan por valor.
package ejemplos;
public class Ejemplo56 {
static String s1 = "Aitor";
static String s2 = "Menta";
public static void intercambio2 (String s1, String s2){
String auxiliar;
auxiliar = s2;
s2 = s1;
s1 = auxiliar;
System.out.println("s1 = " + s1 + ", s2 = " + s2);
}
public static void main(String [] args){
intercambio2(s1, s2);
System.out.println("s1 = " + s1 + ", s2 = " + s2);
}
}
s1 = Menta, s2 = Aitor
s1 = Aitor, s2 = Menta
Sobrecarga de métodos: firma y prototipo
Sobrecarga de métodos: Java permite definir métodos con el mismo nombre siempre que difieran
en los argumentos de entrada.
Se denomina firma del método a su nombre y a sus argumentos de entrada. Puesto que los
métodos sobrecargados tienen el mismo nombre, los métodos sobrecargados se diferencian por el
número, tipo y orden de los argumentos en su lista de parámetros.
public class utilidadesMatematicas{
int
square(int x) { return x*x; }
double square(double x) { return x*x; }
}
El prototipo de un método es la firma más el tipo devuelto, lo que hemos venido llamando hasta
ahora la interfaz del método. Los métodos sobrecargados no se distinguen por el prototipo sino por
la firma.
Tema 5: Abstracción funcional. Métodos.
Funciones y procedimientos.
114
Aunque hasta ahora sólo hemos hablado de funciones, en algunos lenguajes de programación (no
en Java) se suele distinguir entre funciones y procedimientos. Las funciones se corresponden con la
noción matemática de función: producen un resultado que es función de los datos de entrada:
−
−
−
y = f(x1, x2,...xn)
Una función bien definida no modifica los parámetros de entrada.
Se utilizan en expresiones.
Los procedimientos agrupan sentencias que realizan una tarea bien definida, pero no tienen por
qué devolver un resultado.
−
−
Se corresponden con el concepto de instrucción.
Los procedimientos actúan sobre el entorno y pueden modificar los parámetros de entrada
(efectos colaterales → side effects).
Los procedimientos pueden verse como una forma de extender las sentencias del lenguaje,
mientras que las funciones pueden verse como una extensión de los operadores. Cuando se invoca
una función se obtiene un valor a través de un valor de retorno. Cuando se invoca un procedimiento
el efecto es una modificación del entorno del llamante, de la cual éste es advertido a través de los
valores de los parámetros de salida.
Recursión.
La recursión es una técnica de programación mediante la cual las funciones se llaman a sí
mismas.
La recursión puede emplearse si:
1.
Existe un caso base que tiene solución no recursiva (el caso del cero).
por ejemplo: 0! = 1, por definición.
Si el método recursivo ha llegado al caso base devuelve un resultado: if(numero == 0)
return 1;
2.
Si no se ha llegado al caso base, el método se llama a sí mismo, pero considerando un problema
más pequeño.
(n!= n * (n-1)!) → return numero * factorial(numero-1);
La parte del problema que no se sabe resolver debe ser más pequeña que la actual:
3.
n - 1 es más pequeño que n.
Los problemas pequeños en los que se va dividiendo el más grande deben converger (como las
series matemáticas) al caso base, si no, su ejecución será infinita.
La recursión se utiliza cuando es difícil encontrar o implementar una solución basada en bucles.
Ciertos problemas tienen una solución más fácil y elegante cuando en su solución se emplea un
método que se llama a sí mismo.
Tema 5: Abstracción funcional. Métodos.
Por ejemplo, el cálculo del número factorial de un número entero n:
115
// Definición recursiva del método factorial.
public long factorial(long numero){
if (numero == 0){
return 1;
}
else {
return numero * factorial(numero-1);
}
}
Otro ejemplo típico es el cálculo de la serie de Fibonacci. La serie de Fibonacci comienza en 0 y 1 y
tiene la propiedad de que cada número de Fibonacci es la suma de los dos números de Fibonacci
previos. Cada llamada recursiva particiona el problema de tamaño n en dos de tamaño menor que
convergen al caso base pues n-1, n-2, n-3, ... convergen a 1 y a 0.
Casos base:
fibonacci(0) = 0
fibonacci(1) = 1
División del problema:
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
long fibonacci(long n){
if(n == 0 || n == 1){
return n;
}
else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
Tanto la recursión como la iteración hacen uso de estructuras de control: la recursión usa el
condicional y la iteración usa un bucle. Ambas requieren una condición de terminación y ambas se
aproximan gradualmente a su din: la iteración conforme se acerca al cumplimiento de una
condición y la recursión conforme se divide el problema en otros más pequeños. Ambas pueden
tener (por error) una ejecución potencialmente infinita.
Tema 5: Abstracción funcional. Métodos.
116
La solución recursiva se emplea cuando refleja de manera natural la solución a un problema. Sin
embargo, si existe versión recursiva entonces existe versión iterativa equivalente. La recursión
requiere más memoria que la iteración. Por ejemplo:
−
−
Calcular fibonacci(20) requiere 21.891 llamadas.
Calcular fibonacci(30) requiere 2.692.537 llamadas.
Cada vez que se invoca un método se guardan en la pila las variables locales de la función, copias
locales de los parámetros y la dirección de retorno.
Librerías de métodos. Paquetes.
Librerías software y paquetes Java.
Una librería software es una colección de funciones o de clases que se usan para desarrollar
software. Las librerías contienen código y datos que proporcionan servicios a diferentes programas,
permitiendo la construcción modular de las aplicaciones. Las librerías que acompañan a un
lenguaje de programación constituyen APIs (Application Programming Interfaces). La cantidad y
calidad de las APIs que acompañan a un lenguaje de programación son un elemento clave para
determinar su éxito o su fracaso.
Las librerías hacen referencia a otras librerías mediante enlaces (links) que son usados por un
programa llamado enlazador (linker o binder) para ensamblar los programas. Según como se realice
el ensamblado de los elementos de las librerías, éstas pueden ser estáticas o dinámicas. Los
elementos de las librerías estáticas se enlazan antes de la carga y ejecución el programa, los
elementos de las librerías dinámicas se enlazan durante la carga o incluso durante la ejecución del
programa. Ejemplos de librerías dinámicas son las DLL (dynamic link libraries) de Windows y las
DSO (dynamic shared object) de Unix 1.
En lenguajes orientados a objetos la unidad de abstracción no es la función, sino la clase y por tanto
las librerías contienen fundamentalmente clases. En Java se proporcionan bibliotecas de clases e
interfaces, cada una de las cuales expone o define un conjunto de métodos. Existen lenguajes mixtos
(C++) en los que se proporcionan bibliotecas de funciones y de clases. En Java las librerías se
denominan paquetes. Los paquetes (packages) definen unidades de software que se pueden
distribuir independientemente y combinar con otros paquetes para formar aplicaciones. Los
paquetes pueden contener:
−
−
−
−
Clases,
Interfaces
Otros paquetes.
Archivos con recursos adicionales (p.e: ficheros de imágenes)
Los paquetes permiten crear agrupaciones de clases e interfaces relacionadas, crean espacios de
nombres que evitan conflictos de nombrado (p.e.. dos clases pueden recibir el mismo nombre
siempre que se ubiquen en paquetes distintos) y proporcionan un dominio de protección para el
desarrollo de aplicaciones (desde un paquete sólo se puede acceder a los elementos públicos de
otro paquete).
1
Más información en http://slurp.doc.ic.ac.uk/pubs/observing/linking.html.
Tema 5: Abstracción funcional. Métodos.
117
Importación de clases y paquetes.
Si queremos utilizar una clase definida en un paquete necesitamos, o bien importarla:
import java.applet.Applet;
O bien calificar el nombre de la clase inluyendo el nombre del paquete en que se encuentra:
java.applet.Applet myApp;
La API de Java 1 provee una gran cantidad de clases. Antes de lanzarse a implementar una clase, es
conveniente inspeccionar si existe ya una clase en la API que provea los servicios que necesitamos
(don’t reinvent the wheel). Para importar todos los elementos de un paquete utilizamos el “*”.
import java.applet.*;
La sentencia import no implica que el compilador lea toda la información relativa al paquete. Sólo
le indica dónde puede mirar si no encuentra en su alcance algún elemento declarado. Sólo los
elementos declarados como públicos (public) son visibles mediante la importación de los
paquetes. Aquellos que no lleven etiqueta de acceso sólo son visibles dentro del propio paquete en
el que se declaran 2. Las clases e interfaces que pertenecen al paquete java.lang se disponen por
defecto, por lo que no es necesario importarlas.
Cuando importamos un paquete obtenemos acceso a las clases e interfaces públicas que dicho
paquete contiene directamente, pero no a las que contienen sus subpaquetes. El anidamiento de
paquetes no ofrece más funcionalidad a quienes importan los paquetes. Es únicamente un
agrupamiento lógico.
Creación de un paquete.
Para crear un paquete lo único que hay que hacer es poner en el mismo una clase o interface. Para
ello basta con poner la sentencia package al inicio del fichero fuente que incluya dicha clase o
interfaz.
// Fichero Circulo.java
package Graficos;
sentencia
public class Circulo{
Graficos.
// Esta sentencia debe ser la primera
}
// La clase Circulo pertenece al paquete
Lo que llamamos API de java es en realidad un conjunto de APIs cada una de ellas formada por un conjunto de paquetes con
un propósito determinado (construcción de interfaces gráficas, software de comunicaciones, entrada y salida, estructuras de
datos, etc).
2 En la jerga informática se dice que los elementos definidos en un mismo paquete son amigos y dejan que otros elementos
del mismo paquete accedan a sus servicios.
1
Tema 5: Abstracción funcional. Métodos.
118
Dentro de un fichero fuente puede haber varias clases o interfaces, pero sólo una puede ser pública
y el nombre del fichero fuente debe coincidir con el nombre de la clase o interfaz pública que
contiene.
Aunque la especificación de Java no dice nada al respecto, en la mayor parte de los sistemas la
estructura de los paquetes debe corresponderse con la estructura de directorios en la que se
guardan los ficheros fuente:
En la tabla de abajo se enumeran algunos de los paquetes más representativos de la API de Java y
en la de más abajo algunos de los métodos de la clase Math ubicada en el paquete java.lang
Tema 5: Abstracción funcional. Métodos.
119
En Java, las librerías de paquetes se distribuyen en ficheros JAR (Java ARchive). Las clases,
interfaces y recursos que constituyen un paquetes se comprimen y agrupan en un fichero JAR del
que después puede extraerse usando el comando jar del JDK. Los archivos JAR llevan asociados
meta-datos, que explican y validan el contenido del fichero JAR 1.
1
Más información en http://download.oracle.com/javase/tutorial/deployment/jar/
Tema 5: Abstracción funcional. Métodos.
Bibliografía
121
[Prieto 06]
Introducción a la Informática, Prieto Espinosa Alberto et al, ISBN 84-481-46247, McGraw Hill,2006
[Louden 03]
“Informática Aplicada. Programación en lenguaje C”, Pedro Alcover,
“Lenguajes de Programación. Principios y Práctica”, Kenneth C. Louden,
ISBN 970-686-284-6, Thomson, 2003
[Eckel 02]
“Piensa en Java”, Bruce Eckel, ISBN 84-205-3192-8, Prentice Hall, 2002
[Deitel 08]
Harvey M. Deitel (Universidad Nova Deitel y Asociados) , Paul J. Deitel
(Universidad Nova Deitel y Asociados), 9789702611905, 7ª edición
Prentice Hall
[Alcover 09]