Ligaduras y Backtracking

INTRODUCCION







El objetivo primordial de la Teoría de Ligamentos, fue el desarrollo de una teoría de la gramática universal. La TL afirma que muchos de los principios que integran esta teoría están parametrizados, en el sentido de que los valores varían dentro de un rango limitado. La TL afirma que todos los lenguajes son esencialmente semejantes, y que el conocimiento experimentalde un lenguaje particular o de otro es una especie de sintonización fina dentro de un rango determinado, es decir, con unos pocos parámetros restringidos de posible variación.

Con el Backtracking, la idea es encontrar la mejor combinación en un momento determinado, por eso se dice que este tipo de algoritmo es una búsqueda en profundidad. Durante la búsqueda, si se encuentra una alternativaincorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa. Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción. Si no hay más alternativas la búsqueda falla. De esta manera, se crea un árbol implícito, el en que cada nodo es un estado de la solución.


























Ligadura:Asociación entre un atributo y una entidad. El momento en el que se produce se denomina tiempo de ligadura.

Ejemplos:

• Tiempo de compilación → la ligadura de una variable de un programa en Pascal a su tipo de datos

• Tiempo de linkado → la ligadura de una llamada a un subprograma de biblioteca al código del subprograma

• Tiempo de carga → la ligadura de ciertas variables (ej:globales) a sus celdas de memoria (su dirección)

• Tiempo de ejecución → la ligadura de las variables locales (no estáticas) a sus celdas de memoria

• Ligadura estática: si ocurre antes del tiempo de ejecución y permanece inalterable durante la ejecución del programa

• Ligadura dinámica: si ocurre durante del tiempo de ejecución o puede cambiar en el transcurso de la ejecución del programa2.1. Ligadura de tipos

♦ Antes de que una variable pueda ser referenciada en un programa debe haber sido ligada a un tipo de dato. Aspectos importantes: cuándo se liga el tipo y cómo se especifica

A. Ligadura estática de tipos

♦ Puede hacerse mediante:

• Declaración explícita: se utiliza una sentencia que declara una lista de identificadores como de un tipo determinado

•Declaración implícita: forma de asociar variables con tipos a través de convenciones sintácticas. La primera aparición del identificador constituye su declaración implícita

− Ejemplos de LP: Fortran, Basic, Perl

− Problema: variables no declaradas explícitamente de manera accidental por el programador → toman un tipo por defecto

• Algoritmo de inferencia de tipos: determina los tipos delas variables que intervienen en las expresiones sin que sean declaradas de forma explícita por el programador o da un mensaje de error si no puede inferirse

Ej: Haskell

f x y | x == True = y * y | otherwise = y / 2

B. Ligadura dinámica de tipos

♦ El tipo no se especifica mediante una sentencia de declaración, sino cuando se le asigna un valor mediante una sentencia de asignación⇒se liga al tipo del valor, variable o expresión de la parte derecha de la asignación (APL, SNOBOL4)

♦ Ventaja: proporciona muchísima flexibilidad de programación

Ej: APL lista ← 3.5 8.3 0.7 10.1 (tipo: lista de reales de long. 4)lista ← 15 (tipo: variable entera)

♦ Desventajas:

• No se detectan incorrecciones de tipo en las asignaciones. El tipo de la parte izquierda simplemente secambia al de la derecha

Ej:

i, x almacenan valores de tipo entero y almacena un valor de tipo realsi por error escribimos i ← y
en lugar de i ← x ⇒ no se detecta el error, sino que el tipo de i se cambia a real.

En lenguajes con ligadura estática de tipos (Pascal, Ada) el compilador detectaría el error. Aunque en otros (C), en muchas ocasiones el tipo de la parte derecha se...