jueves, 20 de agosto de 2015

Propiedades de los Lenguajes de Programación

Como pensamos influencia en como nos comunicamos y viceversa. Similarmente, como pensamos la informática influencia en como programamos y viceversa. En las últimas décadas, los programadores han acumulado gran experiencia en el diseño y uso de los lenguajes de programación. Aún así, todavía no comprendemos del todo los aspectos del diseño de los lenguajes de programación, sus principios básicos y sus conceptos que forman parte del conocimiento estructural de la informática. No es suficiente para el programador con conocer C o Ruby, por ejemplo, si no que es necesario además tener un estudio de estos principios que son esenciales al programador. Esta integración añade una  mayor perspectiva a la solución de problemas.


UN LENGUAJE DE PROGRAMACIÓN ES....

una herramienta para el desarrollo de software. Por lo tanto, las características  de los lenguajes deben estar relacionados con la calidad del software.

                     




EL SOFTWARE DEBE SER DE FÁCIL ESCRITURA


Se refiere a la posibilidad de expresar un programa de modo tal que sea natural para el problema. El programador no debe distraerse por los detalles o trampas del lenguaje, si no mas bien el programador debe enfocarse en la solución del problema. Aún cuando la capacidad de escritura es un criterio subjetivo, podemos decir que los lenguajes de alto nivel son de más fácil escritura que los lenguajes de bajo nivel. ¿Por qué? Porque el programador de alto nivel se concentra en la resolución de problemas, mientras que el de bajo nivel se ve frecuentemente forzado a considerar los mecanismos de direccionamiento requeridos para el acceso a ciertos datos en memoria (lenguaje assembler).
Pero no perdamos de vista que la facilidad de escritura debe ser consideraba dentro del contexto del problema a resolver. Es necesario conocer el problema a resolver para poder determinar con que lenguaje vamos a abordar la solución. Sabemos que C fue diseñado para Sistemas Operativos en 1972; en cambio Ruby fue diseñado Yukihiro Matsumoto en 1995 para la productividad y la diversión del desarrollador.Es por esto que nos va resultar más complejo desarrollar un driver para periféricos con Ruby que con C.

En el siguiente post se describen las características que presenta un sotware de fácil escritura: 


1) SIMPLICIDAD
Un lenguaje simple es fácil de dominar, y permite que los algoritmos puedan ser expresados fácilmente. Al hablar de simplicidad, nos estamos refiriendo a la facilidad de capturar, para poder entender y recordar lo que se quiso expresar. Nos referimos a simplicidad de un lenguaje aquel mantiene un patrón de aprendizaje, de forma tal que sea necesario aprender y recordar un conjunto mínimo de instrucciones, y a medida que se va necesitando, ir deduciendo a partir de ese conjunto familiar de instrucciones.
Un ejemplo muy claro, son las formas que posee Ruby para listar objetos de un arreglo. Tanto each, map, select, collect, reject, detect, inject como reduce, son métodos para recorrer un array. 
Al aprender a usar each, los restantes deberían funcionar de igual forma:

Lenguaje Ruby
[1,2,3,4].map {|n| n*2}
# => [2,4,6,8] 
[1,2,3,4].each {|n| n*2}
# => [1,2,3,4] 

La segunda característica es tener mas de una manera de expresar algo. Por ejemplo, 

Lenguaje Java


count = count +1 
count += 1
count ++
++count 
Lenguaje Ruby

["eva", "peron", "cristina", "nestor"].map { |name| name.capitalize }
#=> ["Eva", "Peron", "Cristina", "Nestor"]
 

 ["eva", "peron", "cristina", "nestor"].map do |name| 
    name.capitalize
 end
#=> ["Eva", "Peron", "Cristina", "Nestor"]
 

["eva", "peron", "cristina", "nestor"].map &:capitalize
#=> ["Eva", "Peron", "Cristina", "Nestor"]


Otra característica es la sobrecarga de operadores, en la cual un solo operador tiene mas de un significado. Esto puede resultad util o puede incrementar la dificultad de lectura por parte del programador. Por ejemplo, es aceptable la sobrecarga del operador +, para ser usado en la suma con enteros y con punto flotante. De hecho, esta caracteristica le otorga simplicidad al lenguaje.

"Everything should be made as simple as possible, but not simpler" Einstein.

2) ORTOGONALIDAD
Empezando por 3 ejemplos:

Lenguaje C
C posee falta de ortogonalidad  si consideramos las siguientes reglas junto a sus excepciones:
C posee 2 clases de tipos de datos estructurados: arreglos (array) y registros (struct). Las funciones pueden retornar records pero no arrays.  
Tipos de datos que contiene un struct:
Un struct  puede estar compuesto de cualquier tipo de datos excepto del mismo struct o de void (vacio).
struct account {
     int account_number;
     char *first_name;
     char *last_name;
     float balance;
  }; 
Tipos de elementos que contiene un array:
un array puede contener cualquier tipo de datos excepto void o  function
  double balance[5] = {1000.0, 2.0, 3.4, 7.0, 50.0};
En las funciones, los parametros son pasados por valor, excepto los arreglos, en cuyo caso son pasados por referencia.

Lenguaje Ruby

En cambio en Ruby, por ejemplo, no existen excepciones para utilizar each, es decir, tanto las collections/ranges/arrays/files, todas aceptan el metodo each.
ARRAY 
["first", "middle", "last"].each { |i| puts i.upcase } 
HASH 
{ font_size: 10, font_family: "Arial" }.each {|v, k| puts "#{v}: #{k}" } 
RANGE("a".."z").each {|letter| puts letter.next } 
FILES
File.open('/etc/shadow').each do |line|
  puts "Esto es una linea del archivo shadow:  #{line}"
end 


Lenguaje Java
Un usuario del lenguaje Java se ve obligado a tener en cuenta que la asignacion funciona diferente con tipos de datos primitivos que con objetos, lo cual complica el aprendizaje y el uso del lenguaje.
boolean result = true; 
char capitalC = 'C';
int[] anArray = new int[10];
Point originOne = new Point(23, 94);
Cuando las características de un lenguaje son ortogonales, entonces es más fácil aprender el lenguaje y escribir los programas porque hay menos excepciones y casos especiales que recordar.
 
El usuario comprende mejor el lenguaje si tiene  un conjunto relativamente pequeño de constructores primitivos pueden ser combinados para construir el flujo y las estructuras de datos de todo el programa. Es decir, se refiere a la capacidad de combinar varias características de un lenguaje en todas las combinaciones posibles, de manera que todas ellas tengan significado. El aspecto negativo de la ortogonalidad es que un programa suele compilar sin errores a pesar de contener una combinación de características que son lógicamente incoherentes o cuya ejecución es en extremo ineficiente. A causa de estas cualidades negativas, la ortogonalidad como atributo de un diseño de lenguaje es todavía motivo de controversia, pues a ciertas personas les gusta y a otras no.
Por tanto, la ortogonalidad esta directamente conectada con la simplicidad: mientras mas ortogonal sea un lenguaje, menos excepciones requerirá el lenguaje. Esto hace que el lenguaje sea mas fácil de aprender, de leer y de comprender.

3) EXPRESIVIDAD

Expresar la naturaleza del problema, es decir, concentarse en el problema-solución.
Se refiere a la posibilidad de expresar un programa en la forma que mas natural sea para el problema. El programador no debería distraerse en los detalles del lenguaje, si no que debería prestarle mas atención en resolver el problema. Aunque la expresividad es un criterio subjetivo, podemos acordar que los lenguajes de alto nivel son mas expresivos que los de bajo nivel. 
Si queremos quedarnos con los nombres no repetidos:
 
Lenguaje Ruby
["Ana", "JUAN", "Luis", "horacio"].map(&:downcase) | ["ANA", "JUAN", "Luis", "HORACIO", "Laura"].map(&:downcase)
 

# => ["ana", "juan", "luis", "horacio", "laura"]

Lenguaje PHP
array_merge( array_map('strtoupper', array("ana", "JUAN", "Luis", "horacio"))array_map('strtoupper', array("ANA", "JUAN", "Luis", "HORACIO", "Laura")) );

# => ["ana", "juan", "luis", "horacio", "laura"]



4) SOPORTE DE ABSTRACCIÓN 
Se refiere a la habilidad de definir y luego utilizar estructuras complejas u operaciones de forma tal que permita ignorar gran parte de los detalles. Los lenguajes de programacion pueden soportar 2 tipos de categorías de abstracción: datos y procesos.

Un ejemplo muy claro repecto al proceso de abstracción es el uso de subprogramas para implementar, por ejemplo, un algoritmo de ordenación (sort algorithm). Cada vez que se requiere utilizar el algoritmo de ordenación, se convocara a dicho subprograma.

EL SOFTWARE DEBE SER LEGIBLE

Uno de los criterios más importantes para evaluar los lenguajes de programación es la facilidad con la que los programas pueden ser leidos  y entendidos. Antes de 1970, el desarrollo de software era pensado en términos de la escritura del código. Una de las características más importantes de los lenguajes era la eficiencia. Los lenguajes habían sido diseñados más desde el punto de vista de la computadora que desde el usuario. Sin embargo, en los 70, se creó el concepto de ciclo de vida del software (Booch, 1987); la codificación  pasó a un segundo plano, y el mantenimiento del mismo tomó mayor importancia ya que el mantenimiento del código implicaba mayores costos que el desarrollo del mismo. Debido a que la facilidad de mantenimiento está determinada en gran medida por la legibilidad de los programas, esta llego a ser una medida importante de la calidad de los programas y de los lenguajes de programación.  

El software es legible si es posible seguir la lógica del programa y descubrir la presencia de errores mientras se examina el código. La legibilidad también es un criterio subjetivo, ya que es en gran medida una cuestión de gustos y estilos.

La legibilidad se debe considerar en el contexto del dominio del problema. Por ejemplo, si un programa está escrito en un lenguaje que no fue diseñado para su uso, el programa  puede ser de difícil lectura.

En el siguiente post se describen las características que determinan la legibilidad del software:

1) SEMÁNTICA

Las reglas semánticas de un programa nos dicen como construir expresiones significativas, declaraciones y programas

2) SINTÁXIS
Las reglas sintacticas de una lenguaje nos dice como formar expresiones, declaraciones y programas para que se vean bien
  • documentacion y comentarios
  • eleccion de nombres
  • uso de constantes
  • convenciones lexicas

3) DEFINICIÓN (falta explicar para que este bien, no asi a lo rapido)
Precision en la definicion de la sintaxis y de la semantica
  • Ambiguedad
  • definiciones formales
  • portabilidad

4) ESTRUCTURAS DE DATOS
Facilidades para expresar los datos del problema. Esto incluye:
  1. numero de componentes (tamaño fijo, tamaño variable)
  2. tipo de cada componente (homogéneo, heterogéneo)
  3. nombres para ser usados por los componentes seleccionados (se necesita un mecanismo de selección para la identificación individual de componentes de una estructura de datos)
  4. cantidad máxima de componentes
  5. organización de componentes

5) ESTRUCTURAS DE CONTROL



EL SOFTWARE DEBE SER CONFIABLE
Los usuarios deben ser capaces de confiar en el software. Las probabilidades de error debido a fallas en el prog
El sistema debe proveer soporte aun en presencia de eventos indeseables  (ante fallas de software como de hardware) 

1) CHEQUEO DE TIPOS
Chequeo estático o dinámico
 
2) ROBUSTO
Provee la habilidad de manejar eventos no deseados (arithmetic overflow, entrada invalida, etc). Estos eventos pueden ser captados y se brinda una respuesta adecuada. Des esta forma, el comportamiento del sistema se hace predecible ante situaciones anormales

3) RESTRICCIÓN DE ALIAS
Dos nombres que refieren a la misma posicion de memoria

EL SOFTWARE DEBE SER MANTENIBLE
Como los costes de software aumentan y los sistemas de software son cada vez mas complejos, nos es economicamente viable tirar el software existente y desarrollar aplicaciones desde cero que lo reemplazen. El software existente debe ser modificado para satisfacer los nuevos requerimientos. Es casi imposible obtener el 100% de los requerimientos en una primera instancia; para sistemas mas complejos solo nos queda esperar a que evolucione poco a poco el sistema.
1) LOCABILIDAD
El efecto de una caracteristica se restrinja a una posicion local y pequena del programa. De todas formas, si se extendiese a una mayor parte del programa, la tarea de realizar un cambio puede ser muy complejo.
Un ejemplo: en la programacion de tipos de datos abstractos, la modificacion a una estructura definida dentro de una clase garantiza que no afecta al resto del programa siempre que las operaciones que manipulan las estructura de datos sean invocados en la misma manera.

2) MODIFICABILIDAD
Facilidad de introducir cambios

EL SOFTWARE DEBE SER EFICIENTE
La eficiencia ha sido el objetivo de cualquier sistema de software. Se trata de que el programa (ademas de realizar aquello por lo que fue creado) gestione de la mejor forma los recursos que utiliza. Se sabe que hoy en dia, el costo del hardware continua decreciendo, y a su vez el rendimiento del rendimiento continua creciendo (procesadores mas rapidos, mayor capacidad para almacenar datos)




referencias: 

https://es.wikipedia.org/wiki/Ruby

http://es.wikipedia.org/wiki/C_(programming_language)

martes, 5 de agosto de 2014

Las partes de un Compilador


Vemos a grandes rasgos, que tenemos un programa fuente o source program, este se compila y se traduce a un programa objeto o target program. Lo que analizaremos en este post, será el cuadradito verde oscuro que dice "compilador".

He aquí las diferentes fases de un compilador:



1) Lexical Analyzer o Analizador Léxico
Este proceso se denomina "SCANNING". Se escanean los símbolos de entrada y se agrupan en unidades llamadas tokens o words. Por ejemplo, el siguiente código escrito en Java contiene 5 tokens: 

               temp = x + 1 

token 1 :  "temp" (identificador)
token 2:  " = " (símbolo de asignación)
token 3:  " x " (variable)
token 4:  " + " (símbolo de suma)
token 5:  " 1 " (número)

2)  Syntax Analysis o Análizador Sintáctico
Este proceso se denomina "PARSING". Los tokens son agrupados en unidades sintácticas (como ser expresiones, sentencias y declaraciones) que conforman las reglas gramaticales de los lenguajes de programación.  El objetivo del "parsing" es generar una estructura de datos ( parse tree) que represente la estructura sintáctica del programa para luego obtener una respuesta: programas sintacticamente correctos (continua el análisis) o programas sintácticamente incorrectos (produce un error y la compilación finaliza). 

Ahora bien, veamos un ejemplo: dada una secuencia de tokens y utilizando la gramática BNF.




s: statement
v: variable
e: expression
b: boolean

Vamos definiendo una secuencia de pasos donde reemplazamos símbolos no terminales por otros símbolos no terminales hasta que finalmente resultan en un símbolo terminal ( x,y,z,0,1,2,3,4).

Este tipo de interpretación gráfica presenta una ambigüedad. Porque???
Porque depende del orden en el que leamos las sentencias. 
Sea 
                    s1 = "x := 1"
                    s2 = "y := 2"
                    s3 = "if x=y then y:=3"

Veamos que s1;s2;s3 es ambigüo. Es decir, que no resulta lo mismo si ejecutamos de la siguiente forma:
                a) ( s1 ; s2 ) ; s3
                b) s1 ; ( s2 ; s3 )

Como por ejemplo 

¿Qué sucedería si b1 es verdadera y b2 es falsa ? ¿Se ejecutará s2? Como se puede observar, esto depende en como la sentencia se "parsea" o analiza gramaticalmente. 


3) Semantic Analysis o Analizador Semántico (Estático)
Este tipo de análisis depende del contexto en el que se analiza una expresión.  Por ejemplo 

                                                                temp := x + 1

Opción 1: declaramos a los identificadores temp y x como números enteros; entonces el número 1 será un número entero y la suma (+) será una suma de enteros

Opción 2:  declaramos a x como un número decimal; el número 1 será marcado como un número decimal y la suma (+) será suma de decimales. Ahora bien, ¿qué valor obtiene temp? dependiendo de tipo de dato sea temp. Si temp fue declarado como un número entero, entonces la suma x+1 se redondeará a número entero. 

Se observa que el resultado de la suma depende del tipo de dato mediante los cuales fueron definidos tanto el identificador temp como el identificador x. 

El proceso de parsing anteriormente mencionado debe incluir información adicional, como ser los tipos de datos de los identificadores y el lugar en el programa donde cada identificador fue declarado.


4) Intermediate Code Generator o Generador de Código Intermedio 

Aunque es posible generar un programa destino o program target  con los análisis sintácticos y semánticos, resulta dificil generar un código eficiente en una fase. Aún así, muchos compiladores producen un código intermedio y luego optimizan este código para producir un programa destino más eficiente. La representación intermedia puede ser algún tipo de código genérico de bajo nivel que posee propiedades comunes a varias computadoras. ¿Cuál es la ventaja?

Permite la optimización generando código independiente de la máquina.

Existen varios tipos de código intermedio:

  1. Específico al lenguaje (P-code para Pascal, Bytecodes para Java)
  2. Código de 3 direcciones ( ej: x := y op z )
  3. Código de 2 operaciones ( ej: x := op z  que es equivalente a x := x op z )
  4. Representación gráfica
Para mayor información, puede leer las siguientes diapositivas.


5) Code Optimizer o Optimización del Código
Se describen una lista de algunos estándares de optimización para que el programa sea más corto o más rapido en tiempo de ejecución o ambos.


  1. Eliminación de subexpresiones comunes: si un programa calcula el mismo valor más de una vez y el compilador lo detecta, entonces puede ser posible transformar el programa de manera que el valor sea calculado una sola vez y almacenado para su posterior utilización.
  2. Propagación de copia: si un programa contiene asignación como por ejemplo x := y, es posible modificar las sentencias posteriores para referirse a "y" en vez de a "x" y de esta forma eliminar la asignación.
  3. Eliminación de código muerto: si existe alguna secuencia de instrucciones que nunca va a ser ejecutada, entonces se elimina del programa.
  4. Optimización de bucles:  existen varias técnicas que pueden ser aplicadas para eliminar instrucciones de bucles. Por ejemplo, si una expresión aparece dentro de un bucle, pero tiene el mismo valor en cada entrada al bucle, entonces esta expresión se puede mover fuera del bucle.
  5. Llamadas a funciones: si un programa llama a una función "f", es posible sustituir el código de la llamada a la función por la función completa.
6)  Code Generation o Generación de Código
La última fase implica convertir el código intermedio en código de máquina. Esto significa elegir las ubicaciones de memoria, un registo o ambos, para cada variable que aparezca en el programa. Existe una gran cantidad de algoritmos de asignación de registros con el propósito de reusar los registros eficientemente. Esto es importante porque varios diseños de máquinas contienen un número fijo de registros, y las operaciones con registros son más eficientes que la transferencia de datos dentro y fuera de memoria.


Bibliografía:

. Concepts in Programming Languages - John C. Mitchell 







jueves, 31 de julio de 2014

Concepto sobre sintaxis y semántica de los lenguajes de programación


LENGUAJE, SINTAXIS, SEMÁNTICA, Y DEMÁS … CON UN POCO DE FILOSOFÍA


"That which can be said, can be said clearly" Wittgenstein

Antes de definir que son los lenguajes de programación junto con su sintaxis y su semántica, vamos a hacer una recorrida por los lenguajes mediante los cuales nos comunicamos día a día.

Si hacemos referencia al video "Mentira la verdad, el lenguaje" del programa de televisión Canal encuentro, podemos empezar con las siguientes preguntas:

Todo es texto, lo que digo, lo que pienso, incluso lo que hago. Como dice Jacques Derrida no hay nada por fuera del texto. Todo es texto, nada hay por fuera del lenguaje. Pero, si todo es texto y nada hay por fuera, ¿a qué se refieren las palabras? , ¿de qué habla el lenguaje? ¿habla de las cosas o habla de sí mismo? ¿hay algo que podamos pensar sustraído al lenguaje? ¿qué es el lenguaje? ¿cómo lo fuimos pensando a lo largo de la historia? ¿es cierto que el hombre es y además camina, además respira o además duerme? ¿o es al revés, y el habla nos hace hombres? ¿el hombre habla o el lenguaje nos constituye como hombres?

Estos  interrogantes se dan al inicio del video. En el mismo, se establece el debate desde el interrogante. 

Una vez que se plantea el interrogatorio para encontrarle una definición al lenguaje, nos seguimos preguntando sobre como lo adquirimos  …
¿cómo es el que hombre aprende su lenguaje ? ¿cuáles son las facultades de la mente?  ¿dicho lenguaje lo ha visto, leido o escuchado anteriomente? ¿está el lenguaje bien construido? ¿está mal construido? ¿qué conocimiento de su lengua tiene el hablante que le permite construir y entender oraciones que nunca antes ha leido?

La gramática tradicional divide  al estudio de todas las lenguas del mundo por convención, en dos secciones : morfología y sintaxis. 
 “la morfología explica la estructura interna de las palabras y el proceso de formación de las palabras,  mientras que la sintaxis describe como las palabras se combinan para formar sintagmas, oraciones y frases”
Noam Chomsky
Sin embargo, en el seno de la gramática generativa se ha sostenido que la morfología es insostenible como rama autónoma.  De esta forma surge la gramática generativa y transformacional. El iniciador de la teoría gramática generacional es Noam Chomsky, siendo uno de los campos de investigación más activos de la lingüística moderna. 


Podemos decir que el lenguaje es  creativo porque se pueden producir y entender una cantidad infinita de nuevas expresiones que no nos fueron enseñadas. No nos limitamos a repetir frases que ya hemos escuchado, si no que las creamos en función de las necesidades cambiantes de cada momento. Entendemos las oraciones que los otros pronuncian, o escriben a pesar de no haberlas leido o escuchado antes. 
La gramática generativa presenta de forma explícita las reglas gramaticales que aplica implicitamente el hablante/oyente para construir/entender las oraciones. 
Para comprender la diferencia de significado entre las oraciones no es suficiente conocer el significado de las palabras que las componen, si no que es necesario ver también la información sintáctica que contienen. Esto es la información no lexical que es transmitida por medio de la estructura de la oración misma. 
Cuando conocemos un lenguaje sabemos que es un conjunto de palabras y reglas con  las cuales generamos cadenas de esas palabras.

Ahora bien, escribamos la definicipón etimológica de sintaxis: del griego “syn” con y “taxis” ordenLa sintaxis describe como las palabras se combinan para formar sintagmas, oraciones y frases. La sintaxis no se ocupa del estudio de las palabras, sino de las agrupaciones que éstas forman (tanto las de primer nivel o sintagmas, como las de segundo nivel u oraciones) y de las funciones que desempeñan. De esta forma, podemos decir que existen enunciados sintacticamente correctos como enunciados sintácticamente incorrectos. Los enunciados sintácticamente correctos son aquellos en los que los diferentes sintogmas estén bien construidos, bien posicionados y correctamente relacionados los unos a los otros. 


Y me gustaría continuarlo para adentrarlo a los lenguajes de programación...
¿Qué es lo que hace que un lenguaje sea diferente de otro? ¿Qué es lo que hace que un lenguaje sea parecido a otro? 

Un lenguaje de programación  es un lenguaje formal para la formulación de algoritmos y estructuras de datos, eso quiere decir, para formular reglas de cálculo que pueden ser ejecutados por una computadora. Cuando observamos un código escrito en un determinado lenguaje de programación, nos podemos preguntar ….
cómo sabemos si está bien escrito, cómo sabemos qué es lo que hace el programa, cómo sabemos si resuelve correctamente el problema planteado, cómo sabemos que significa, y cómo un compilador sabe como traducir el programa ???
Todo lenguaje de programación debe ser definido con suficiente detalle para que permita resolver casi cualquier tipo de problema. Entonces, la definición de un lenguaje de programación debe permitir determinar 

(1) si un supuesto programa es un hecho válido

(2) si el programa es válido, cuál es su significado o su efecto


Según el libro CONCEPTS IN PROGRAMMING LANGUAGES de John C. Mitchell, parte 4.1 ...
Un programa es una descripción de un proceso dinámico. El texto mismo de un programa es llamado SINTAXIS; las cosas que un programa realiza comprende la SEMÁNTICA. La función de la implementación de un lenguaje de programación es transformar la sintaxis de un programa en instrucciones de máquina que puedan ser ejecutadas.

El estudio de los lenguajes de programación, como así el estudio de las lenguas nativas, se pueden examinar desde la sintaxis y semántica. La sintaxis de los lenguajes de programación se refieren a sus expresiones, sentencias y unidades del programa. Su semántica se refiere al significado de aquellas expresiones, sentencias y unidades de programa. Por ejemplo, en Java la sentencia while  se describe como la siguiente:
  
        while (expr_booleana) sentencia

              
La semántica de esta expresión sintáctica, es ejecutar la sentencia cuando el actual valor de expr_booleana sea verdadero, y repetir el proceso. Si el valor actual de expr_booleana es falso, la linea de ejecución continua por debajo del bloque de sentencias while.


El siguiente post contiene la definición de sintaxis, junto con sus características, sus elementos, los tipos de sintaxis existentes, la estructura sintáctica y las diferentes formas de expresar la sintaxis (EBNF, árboles de derivación y árboles sintácticos, diagramas sintácticos)

Bibliografía:
. Programming language concepts - Carlo Ghezzi, Mehdi Jazayeri
. Concepts in programming languages - John C. Mitchell
Sintaxis - definiciones y su evolución
. Video canal encuentro, programa: "Mentira la verdad, el lenguaje"


viernes, 27 de junio de 2014

Tiempo de Ejecución - de código JAVA a expresión matemática

Objetivo: descubrir que dos algoritmos diferentes tienen el mismo orden de ejecución, es decir, que comparten el mismo comportamiento asintótico.


LES PRESENTO A LOS DOS ALGORITMOS:


 


Cuando analizamos el tiempo de ejecución de un algoritmo,se toma en cuenta las estructuras de control (while, for, if-then-else, do). En este caso, en ambos códigos, prestamos atención a la sentencia "while". Las demás sentencias se consideran constantes. ¿Por qué? Por ejemplo las sentencias "int c=N" o "c=c/2" contienen: alocación de memoria y utilización de la ALU para calcular "c/2". Esto se resuelve en tiempo constante.



VOLVIENDO A ALGUNAS CLASES DE MATEMÁTICA ...

Primero definamos el concepto de función matemática.

DEFINICIÓN DE FUNCIÓN [1]

Sean A y B dos conjuntos no vacíos, que llamaremos dominio y codominio respectivamente. Entenderemos por función de A en B toda regla que hace corresponder a cada elemento del dominio un único elemento del codominio. Más precisamente, una función es un conjunto de pares ordenados tales que la primera componente pertenece a A y la segunda componente pertenece a B, es decir, un subconjunto de A X B, de modo que todo elemento de A sea primera componente de un par y sólo de uno. Esto nos dice que toda función de A en B es una relación especial entre A y B. 
Se escribe de la siguiente forma:


"f es una función con dominio en A y codominio en B"

En particular, 
f es la relación definida por 
entonces se tiene 
ya que la segunda componente es el cuadrado de la primera. 

EL diagrama de Venn correspondiente es 
Tanto en la definición de f por extensión como en el diagrama de Venn es fácil advertir que todo elemento del dominio tiene un correspondiente o imagen en el codominio y; además tal correspondiente es único. 

Observemos la siguiente situación: elementos distintos de pueden tener la misma imágen en B. Es decir, f(-1)=1 y f(1)=1. 

Ahora bien, pero que tiene que ver esto con el análisis de tiempo de ejecución de los dos algoritmos arriba mencionados?
Debemos de ser capaces de identificar quien es f, A, y B respecto al código arriba mencionado. Es la misma analogía.

SI ANALIZAMOS EL PRIMER CÓDIGO....

                    
Sea N=32, entonces entramos al bloque while cuando c=32, c=16, c=8, c=4, c=2. Pero cuando c=1, ya no entra al while. Entonces nos preguntamos, ¿Cuántas veces entre al bloque while? ¿Cuántas veces se ejecuta el while para N=32? 5 veces. ¿Que tuvimos en cuenta para concluir que se ejecuta 5 veces? Es decir, de que depende que el bloque while se ejecute 5 veces? Depende del valor de "N" y del cálculo "c = c / 2". 

Ahora debemos relacionar N con la cantidad de veces que se ejecuta el algoritmo. En este caso, relacionamos N=32 con 5, y esto nos lleva a pensar que



Si  entonces

                   el "while" se va a ejecutar 5 veces. 


Si  entonces

                   el "while" se va a ejecutar 6 veces. 
       
Observen que existe un intervalo donde el bloque while se ejecuta  la misma cantidad de veces. Esos intervalos son los siguientes:

  

Podemos concluir que N se ejecuta la misma cantidad de veces para  un determinado intervalo, y que dicho intervalo varía en potencias de 2 para el ejemplo del "código 1".

¿Y para que me servía la definición de función?

Sea  f:N->M , N y M naturales / f(N)=log2(N)  

¿Qué significa N, M y f(N)?

NEs el valor de entrada que recibe el código. Dependiendo del valor de N, el algorítmo se va a ejecutar más o menos veces.

M: Es el valor aproximado que determina la cantidad de veces que se ejecuta el algoritmo. M depende del valor que tenga N. M no es un número entero cualquiera. M es una unidad de tiempo.

f(N): Es lo que tenemos que descubrir nosotros mismos. Pudimos encontrar que f es de la forma f(N)=log2(N).

Sea f(N)=M=20, siginifica que el algorítmo tarda en ejecutarse 20 unidades de tiempo. ¿Porque la imagen de f son unidades de tiempo y no horas, minutos y segundos? La unidad de tiempo sirve para comparar algoritmos sin depender de la arquitectura subyacente (un algoritmo "tarda" más que otro en ejecutarse). Si uno desea en la práctica estimar el tiempo real, es necesario definir a la unidad de tiempo en horas minutos y segundos.  

OBSERVACIÓN: Valores distintos de N pueden tener la misma imagen.



SI ANALIZAMOS EL SEGUNDO CÓDIGO ....

                                                   

Si N=47entonces entramos al while cuando c=2, c=4, c=8, c=16, c=32 y cuando c=64 ya no entra al while. Entonces, nos preguntamos, ¿Cuántas veces se ejecuta el while teniendo en cuenta a N y el cálculo c*2? Se ejecuta 5 veces. Ahora debemos relacionar N con la cantidad de veces que se ejecuta el algoritmo. En este caso relacionamos N=45 con 5, y esto nos lleva a pensar que
 Tomamos la parte entera de 

CONCLUSIÓN

Pudimos analizar que ambos algoritmos tienen el mismo comportamiento asintótico. Es decir, que ambos tardan aproximadamente el mismo tiempo de ejecución para un valor de N dado. Observen que no es de interés obtener un resultado exacto de tiempo de ejecución, ya que es una estimación del mismo. 


Bibliografía:
[1] Algebra I, Armando Rojo ( Funciones: Capítulo 4 Página 102 )


jueves, 12 de junio de 2014

Para que estudiar los Conceptos de los Lenguajes de Programación

"The limits of my language are the limits of my word" Wittgenstein



Un Lenguaje de Programación es ....

un lenguaje formal para la formulación de algoritmos y estructuras de datos, eso quiere decir, para formular reglas de cálculos que pueden ser ejecutados por una computadora.[1]

Los lenguajes de programación son una herramienta para escribir software.   Pueden ser utilizados para crear programas que controlen el comportamiento de una máquina o para expresar un algoritmo.



Los primeros lenguajes de programación estaban orientados a las propiedades de determinadas computadoras. Hoy en día se utilizan mayormente lenguajes orientados a problemas, los así llamados lenguajes de alto nivel, los cuales  son más abstractos y permiten una expresión más entendible del mundo real. [2]




Estudiamos los conceptos de los lenguajes de programación con el propósito de ...



tener la habilidad de elegir, diseñar, implementar o utilizar un lenguaje. 

Podremos identificar sus alcances y sus limitaciones  para:



1) Aumentar la capacidad para producir software
Conociendo las características de los lenguajes permite minimizar su esfuerzo, evitar errores y aprovechar su potencia. Por ejemplo, no es lo mismo C que Smalltalk. El primero es un lenguaje estructurado mientras que el segundo es orientado a objetos


2) Mejorar el uso del lenguaje
Si se comprende como se implementa cada característica, se mejora la capacidad de escribir programas más eficientes. Por ejemplo, entender la diferencia entre List y Set en Java. List es una secuencia ordenada de elementos mientras que Set es una lista de elemento sin ningún orden.

3) Incrementar el vocabulario 
A veces es necesario expresar un concepto que el lenguaje no lo provee. Por ejemplo, Assembler no posee estructuras de control, por lo tanto debemos simularla.

4) Elegir adecuadamente un lenguaje
Si conocemos las características de los lenguajes, tenemos la posibilidad de elegir el adecuado de acuerdo al área del problema, y de esta forma reducimos el esfuerzo de codificación. Por ejemplo, si queremos programar artefáctos electrónicos utilizaremos PROLOG, en cambio si queremos programar cálculo numérico utilizaremos FORTRAN.

5) Facilitar el aprendizaje de nuevos lenguajes
Un lingüista que conoce profundamente la estructura subyacente del lenguaje natural aprende muchísimo más rápido un nuevo lenguaje o idioma que aquella persona que desconoce la estructura lingüística

6) Escoger el diseño e implementación de lenguajes 
Conocer el conjunto de símbolos que lo conforman, sus reglas sintácticas y semánticas, el significado de sus elementos y de sus expresiones  facilitará la escritura, la depuración, la compilación y el mantenimiento de un programa informático.





Bibliografía:
[1] Duden Informatik, ISBN 3-411-024-21-6
otras
. Apuntes de la Cátedra "Conceptos y Paradigmas de los Lenguajes de Programación" de la Facultad de Informática, UNLP (Universidad Nacional de La Plata)
. Programing language concepts - Third Edition -  Carlo Ghezzi.