Presentacion para el Foro de Innovacion Tecnologica de la Universidad Galileo
Compiladores y Computadoras
Este blog está orientado a la Ingeniería de Lenguajes de Programación y otros temas de interés en el área de ciencias de la computación y sistemas de información.
17 de julio de 2022
1 de febrero de 2021
Breve introducción a la programación en Prolog
PROLOG (PROgramming in LOGic) es un lenguaje de programación que se basa en el lenguaje de la Lógica de Primer Orden, diseñado por Alan Colmerauer en 1970, y que se utiliza para resolver problemas en los que entran en juego objetos y relaciones entre ellos. Por ejemplo, cuando decimos "Juan tiene un trompo", estamos expresando una relación entre un objeto (Juan) y otro objeto en particular (un trompo). Más aún, estas relaciones tienen un orden específico (Juan tiene el trompo y no al contrario).
Por otra parte, cuando realizamos una pregunta (¿Tiene Jorge una moto?) lo que estamos haciendo es averiguando sobre una relación. Además, también es posible usar reglas para describir relaciones: "dos personas son hermanos si ambos son hombres y tienen los mismos padres".
La programación en Prolog se clasifica como programación declarativa ya que se especifica qué se tiene que hacer, en contraposición con los lenguajes tradicionales que dicen cómo se debe hacer (programación imperativa). Asimismo, Prolog incluye algunos predicados predefinidos, ajenos la lógica formal, así como algunos extra-lógicos, que tienen un efecto lateral como write, read y otro grupo que sirve para expresar información de control. Por tanto, Prolog ofrece un sistema de programación práctico que tiene algunas de las ventajas de claridad y capacidad declarativa que ofrecería un lenguaje de programación lógica y, al mismo tiempo, nos permite un cierto control y operatividad.
Un programa en Prolog consiste en un conjunto de hechos (conocimiento) y un conjunto de reglas para manipular estos hechos. No hay declaraciones de tipo, inicializaciones u otras condiciones normales de los lenguajes de programación. Algunos ejemplos de hechos en Prolog son:
hombre(juan).
mujer(maria).
edad(juan,29).
edad(maria,25).
padre(juan,pedro).
padre(pedro,jaime).
oficina(maria, b3128).
amigo_de(maria,juan).
Los hechos consisten en:
Un nombre del predicado por ejemplo hombre, mujer, y oficina. Este debe comenzar con una letra minúscula.
Cero o más argumentos, tales como juan, b3128, y 29.
Observe que los hechos (y las reglas, y las preguntas) deben terminar con un punto.
Puede probar estos ejemplos de código en SWISH.
Un ejemplo de reglas en Prolog es:
abuelo(X,Y) :-
padre(X,Z),
padre(Z,Y).
El operador “:-'” se lee como “if'', mientras que la coma “,'' se lee como el operador “and”. La regla dice que “Y es abuelo del X si Z es el padre de X y Y es padre de Z”. Todos los argumentos que comienzan con una mayúscula (tal como X o Y) son variables. Las variables no se tratan como en lenguajes de programación convencionales - por ejemplo, no tienen que tener valores.
La ejecución de un programa en Prolog implica el hacer preguntas que se cargan del “programa” que consiste en un conjunto de hechos y de reglas. Por ejemplo, usted podría consultar:
? - abuelo(juan, jaime).
A lo cual Prolog daría la respuesta “Yes”. Si pedimos una secuencia de preguntas puede ser que obtengamos:
? - abuelo(juan, jaime).
Yes
? - abuelo(jaime, juan).
No
Las preguntas pueden tener variables en ellas, las que se pueden instanciar, es decir obtener un valor, cuando Prolog intenta contestar a la pregunta. Prolog mostrará todos los resultados de las instanciaciones que resultan de todas las variables en la pregunta. Esto resulta en un diálogo con el intérprete como el siguiente:
? - abuelo(juan,AbueloDeJuan).
AbueloDeJuan = jaime
Podemos también darle vuelta a la pregunta de la siguiente manera:
? - abuelo(Nieto, jaime).
Nieto = juan
Observe que las variables AbuelodeJuan y Nieto puede tomar valores de cualquier tipo. Asimismo, es posible consultar en la base de conocimiento (conjunto de hechos y reglas de Prolog), quien es abuelo de quien de la siguiente forma:
? - abuelo(Nieto, Abuelo).
Nieto = juan, abuelo = jaime;
no
Prolog pasa sistemáticamente por todos sus hechos y reglas e intenta encontrar todas las maneras que puede asociar variables a valores particulares para satisfacer la pregunta inicial. Con el siguiente ejemplo se ilustra otra característica importante del Prolog, dada esta base de conocimiento:
animal(león).
animal(cuervo).
tiene_plumas(cuervo).
ave(X) :-
animal(X),
tiene_plumas(X).
Luego de cargar este programa, si se hiciera la consulta ave(P), el sistema respondería P=cuervo.
El mecanismo que Prolog sigue internamente hace corresponder la pregunta anterior ave(P) con la cabeza de la regla ave(X), generando la nueva consulta animal(P) y luego tiene_plumas(P). Note que animal(P) puede ser satisfecho asignando (instanciando) P con el valor leon. Sin embargo, si Prolog continúa procesando con este valor llegará a la regla tiene_plumas(leon) la cual, de acuerdo al contenido de los hechos, no es verdad. Esto activa el mecanismo de backtracking (retroceso) en el cual el motor de inferencia de Prolog intenta buscar otro hecho del predicado animal que pudiera convertir en verdadera la pregunta, que corresponde a animal(cuervo). Esta prueba es cierta, así como tiene_plumas(cuervo), haciendo que toda la regla ave(P) sea cierta, con valor P = cuervo.
Estructuras de datos y sintaxis básica
Lo anterior mostró brevemente como los programas en Prolog consisten en hechos, reglas y preguntas. Los hechos declaran las cosas que siempre evalúan al valor lógico Verdadero. Las reglas declaran las cosas que evalúan a Verdadero dependiendo de algunas condiciones. Los hechos y/o las reglas se pueden utilizar para definir relaciones (o predicados). Éstos pueden contar con uno o más argumentos.
Las preguntas se utilizan para validar contra la base de conocimiento si ésta es Verdadera, incluyendo qué valores de variables asociadas se requieren para hacerlo verdad. Los hechos, las reglas y las preguntas son todas cláusulas de Prolog.
La estructura de datos fundamental en Prolog es el término. Los términos del Prolog incluyen:
Átomos o entidades simples, que no se pueden separar.
Números
Variables
Objetos estructurados, como
libro(titulo(cryptonomicon),autor(stephenson))
Las estructuras complejas como la mostrada previamente son útiles si deseamos agrupar información sobre una colección relacionada de objetos, o un objeto con componentes.
Correspondencia de términos (unificación)
La unificación (“matching”) aplicada junto con la regla de resolución es lo que nos permite obtener respuestas a las preguntas formuladas a un programa lógico. La unificación constituye uno de los mecanismos esenciales de Prolog, y consiste en buscar instancias comunes a dos átomos, uno de los cuales está en la cabeza de una cláusula y el otro en el cuerpo de otra cláusula. Prolog intentará hacerlos coincidir (unificarlos) mediante las siguientes reglas:
Una variable puede instanciarse con cualquier tipo de término, y naturalmente con otra variable. Si X es una variable no instanciada, y si Y está instanciada a cualquier término, entonces X e Y son iguales, y X quedará instanciada a lo que valga Y. Si ambas están no instanciadas, el objetivo se satisface y las dos variables quedan compartidas (cuando una de ellas quede instanciada también lo hará la otra).
Los números y los átomos sólo serán iguales a sí mismos. Evidentemente, también se pueden instanciar con una variable.
Dos estructuras son iguales si tienen el mismo nombre y el mismo número de argumentos, y todos y cada uno de estos argumentos son unificables.
El predicado de igualdad (=) es un operador infijo que intentará unificar ambas expresiones. Un objetivo con el predicado no igual (\=) se satisface si el = fracasa, y fracasa si el = se satisface.
Ejemplos:
?- X=juan, X=Y.
X=juan, Y=juan
?- juan=juan.
yes
?- juan=jose.
no
?- 1024=1024.
yes
?- “juan”=juan.
no
?- f(X,Y)=f(A).
no
Backtracking (reevaluación)
Al recibir una pregunta para que sea “probada”, Prolog recorre su lista de hechos y de reglas, en orden de arriba hacia abajo, buscando hechos o inicios de regla que hagan correspondencia con la pregunta. Cuando encuentra uno, almacena el lugar en la base de conocimiento hasta donde había llegado en su búsqueda, para que si la primera correspondencia no es satisfactoria pueda continuar y buscar más posibilidades. Como un ejemplo, suponga los siguientes hechos:
ave(tipo(loro), nombre(arturo))).
ave(tipo(canario), nombre(tweety))).
ave(tipo(canario), nombre(percy)).
A la base de conocimiento anterior se consulta la siguiente pregunta: ave(tipo(canario), nombre(X)). El motor de búsqueda de Prolog primero tratará de corresponder la pregunta con el primer hecho, pero falla porque loro no corresponde con canario. Entonces intentará hacer la correspondencia con el segundo hecho, y tiene éxito con X = tweety. Sin embargo, pondrá un indicador en el lugar donde fue encontró una solución, para que si una búsqueda subsiguiente falla, regresará a la posición marcada, para buscar más soluciones (por ejemplo, X = percy).
La reevaluación ("backtracking") consiste en volver a evaluar lo que se ha hecho e intentar resatisfacer los objetivos buscando una forma alternativa de hacerlo. Si se quieren obtener más de una respuesta a una pregunta dada, puede iniciarse la reevaluación pulsando la tecla «y» cuando Prolog acaba de dar una solución y pregunta «More (y/n) ?», con lo que se pone en marcha el proceso de generación de soluciones múltiples.
Vamos a ver dos conceptos ya utilizados y relacionados directamente con la reevaluación:
Satisfacer un objetivo: cuando Prolog intenta satisfacer un objetivo, busca en la Base de Conocimientos desde su comienzo, y:
- si encuentra un hecho o la cabeza de una regla que pueda unificar con el objetivo, marca el lugar en la base de conocimientos e instancia todas las variables previamente no instanciadas que coincidan. Si es una regla lo encontrado, intentará satisfacer los subobjetivos del cuerpo de dicha regla.
- si no encuentra ningún hecho o cabeza de regla que unifique, el objetivo ha fallado, e intentaremos resatisfacer el objetivo anterior.
Resatisfacer un objetivo: Prolog intentará resatisfacer cada uno de los subobjetivos por orden inverso, para ello intentará encontrar una cláusula alternativa para el objetivo, en cuyo caso, se dejan sin instanciar todas las variables instanciadas al elegir la cláusula previa. La búsqueda la empezamos desde donde habíamos dejado el marcador de posición del objetivo.
A continuación un ejemplo de una sesión interactiva de Prolog, que muestra los efectos del backtracking:
animal(mono).
animal(gallina).
animal(arana).
animal(mosca).
animal(cocodrilo).
gusta(mono,banana).
gusta(arana,mosca).
gusta(alumno,logica).
gusta(arana,hormiga).
gusta(cocodrilo,X) :- animal(X).
gusta(mosca,espejo).
regalo(X,Y) :- animal(X), gusta(X,Y).
?- regalo(X,Y).
X=mono, Y=banana
More (y/n)? y
X=arana, Y=mosca
More (y/n)? y
X=arana, Y=hormiga
More (y/n)? y
X=mosca, Y=espejo
More (y/n)? y
X=cocodrilo, Y=mono
More (y/n)? y
X=cocodrilo, Y=arana
More (y/n)? y
X=cocodrilo, Y=mosca
More (y/n)? y
X=cocodrilo, Y=cocodrilo
More (y/n)? y
no
Recursión
Las definiciones recursivas se encuentran frecuentemente en los programas Prolog, en los que algunos predicados están definidos recursivamente, es decir, el cuerpo de la cláusula se llama a sí mismo. En la recursividad debemos tener cuidado en que se cumplan las “condiciones de límite” (punto de parada cuando utilizamos recursividad). Podemos observar que en la llamada de la cláusula recursiva al menos uno de los argumentos crece o decrece, para así poder unificar en un momento dado con la cláusula de la condición de parada.
En la recursión encontramos dos partes:
la primera parte en la que descendemos y construimos el árbol hasta encontrar el valor que unifica con la condición de parada, y
una segunda parte en la que ascendemos por el árbol asignando valores a las variables que teníamos pendientes en las sucesivas llamadas.
Casi cualquier programa no trivial en Prolog implica el uso de predicados recursivos – o sea, predicados que se llaman a sí mismos. La idea básica es la misma de las funciones recursivas de los lenguajes de programación funcionales. Sin embargo, como Prolog no se basa en el uso de funciones o procedimientos, se utilizan los predicados recursivos.
Suponga que escribimos un predicado en Prolog para determinar si alguien es un antepasado de alguien más. Esto tiene una definición recursiva simple, expresada de la siguiente forma: X es antepasado de Y si X es padre de Y ó Z es padre de Y y X es antepasado de Z. Esto se escribe así:
ancestro(Persona, Antepasado):-
padre(Persona, Antepasado).
ancestro(Persona, Antepasado):-
padre(Persona, Padre), ancestro(Padre, Antepasado).
Note cómo el caso límite de la definición recursiva es una regla separada, precediendo el caso recursivo. Todos los predicados recursivos deben tener un caso límite, si no fallarían o entrarían en un lazo sin fin para siempre.
Asimismo, se debe tener cuidado de no escribir recursiones circulares (entrada en un loop infinito) y evitar la recursión izquierda (cuando una regla llama a un objetivo que es equivalente al objetivo original). Este tipo de problemas causarían que Prolog no termine nunca. A continuación un par de ejemplos sobre este tipo de condiciones:
Recursión circular:
padre(X,Y) :- hijo(Y,X).
hijo(A,B) :- padre(B,A).
Recursión izquierda:
persona(X) :- persona(Y), madre(X,Y).
persona(adan).
2 de abril de 2019
CPU stuck at 0.78 GHz (780 MHz)?
How to fix
Go into the BIOS and disable all settings related to CPU performance related to power management, including SpeedStep. After disabling this settings, computer now runs at maximum speed all the time.
Cause
In this case, the laptop had a dead battery. This forced the power management to keep the CPU at the minimum possible frequency.
Other effects
Unable to update BIOS due to battery unable to charge.
8 de septiembre de 2017
Annotating online presentations using an iPad Pro and the Apple Pencil, useful for a MOOC
Since the class meets remotely, I am connected through Skype to the class, and need to share what's on my screen, but also add some white slides to use as whiteboard. I've found a couple of different ways to do it:
1) Using Powerpoint for iOS to display the presentation and a Macbook for main screen. This is by far the best method, as the iPad Pro palm detection mechanism works beautifully here. I then mirror the iPad's screen to the computer, and then share it out of the call. To mirror the iPad screen, I use QuickTime.
2) Using Duet Pro for iOS, this essentially converts the iPad to something like a Cintiq tablet. Mac OS does not include any Ink support, so Powerpoint does not work adequately with the iPad. So this works best as a Windows setup. However, gesture detection gets in the way, palm detection is not very good and makes me advance to the next slide when I'm writing on top of a slide, so that gets annoying.
I'll keep trying, and maybe Duet Pro gets better on new releases, as I'll be using a Windows computer for the most part of the course.
15 de mayo de 2017
Guía rápida y sencilla para protegerse del virus ransomware WannaCry
Recomendaciones generales
- Básico, aplicar todas las actualizaciones (updates) de Windows Update
- No hacer click o abrir archivos adjuntos en mensajes de correo electrónico que suenan amenazadores: perderás tu saldo, te adjunto factura, no pagaste esto, te ganaste esto, el Ministro dice, etc.
- No descargar parches de otros sitios que no sean Microsoft directamente.
Para versiones obsoletas de Windows (XP, 2003, Vista)
Microsoft ha emitido un parche que debes aplicar manualmente, el cual está disponible en esta dirección Customer guidance for WannaCrypt attacks
Para Windows 7
Entonces, lo primero, es asegurarte de ejecutar Windows Update, y que todas las actualizaciones sean aplicadas.
Luego, para mayor seguridad, se debe desactivar el protocolo SMB1 siguiendo estos pasos:
1) Abrir un cmd con privilegios elevados:
2) En la ventana del cmd, ejecutar lo siguiente:
En conjunto con el parche, esto cierra toda avenida de infección por medio de este protocolo obsoleto y con fallas de seguridad.
Windows 8, 8.1 y 10
Para las versiones 8, 8.1 y 10 de Windows (incluyendo Windows RT), Microsoft lanzó en marzo pasado el parche que cierra la vulnerabilidad, por lo que debes asegurarte correr Windows Update en tu máquina. Si no has parchado desde marzo, la última versión de las actualizaciones (Rollup o Paquete Combinado) trae este parche.
Entonces, lo primero, es asegurarte de ejecutar Windows Update y que todas las actualizaciones sean aplicadas.
Luego, para mayor seguridad, se debe desactivar el protocolo SMB1 siguiendo estos pasos:
1) Ir al Control Panel, Programas and Features y luego a Turn Windows Features On or Off
En español: Panel de Control, Programas y Características y luego Activar o Desactivar Características de Windows.
2) Desactivar el protocolo SMB1 en las características de Windows:
En conjunto con el parche, esto cierra toda avenida de infección por medio de este protocolo obsoleto y con fallas de seguridad.
¿Qué pasa si desactivo el SMB1?
Conclusión
Espero que esto sea de utilidad. No incluí los servidores, porque eso ya es otro servicio ;-)
5 de septiembre de 2016
Possible fix for red LED blinking on Raspberry Pi B+
10 de junio de 2015
Planificación de la Continuidad de Negocios
- Administración de Crisis: Debemos tener una respuesta efectiva ante la ocurrencia de un evento catastrófico.
- Reanudación de Negocios: Cómo vamos a hacer la recuperación de las funciones críticas de nuestro negocio, y la reanudación de entrega de servicios a los clientes.
- Recuperación de desastres informáticos: Cómo se realiza el manejo de la recuperación de los activos informáticos críticos, incluyendo sistemas, aplicaciones, bases de datos y redes.