Lenguaje de Comandos Guardados

Lenguaje de Comandos Guardados

El Lenguaje de Comandos Guardados (GCL, Guarded Command Language), o de Órdenes Guardadas, es un modelo de lenguaje definido por Edsger Dijkstra para semántica de transformación de predicados (una extensión lógica diseñada para proporcionar una metodología para desarrollar programas "correctos por construcción" en un lenguaje imperativo).[1]

Tiene un conjunto especial de construcciones de condición y de bucle. El elemento más básico del lenguaje es el comando guardado ó comando con guarda.

Contenido

Comando guardado

Un comando guardado consiste en una orden —un enunciado— que está "guardada" (protegida) por una proposición llamada guarda, cuyo valor debe ser verdadero antes de que se ejecute el comando. Cuando el enunciado se ejecuta, puede asumirse que la proposición de guarda es verdadera. Si la proposición de guarda es falsa, no se ejecutará el enunciado.

El uso de comandos guardados facilita la comprobación de que el programa cumple la especificación.

Sintaxis

Un comando guardado es un enunciado de la forma G \rightarrow S, donde

Semántica

Cuando G se encuentra en un cálculo, se evalúa.

  • Si G es verdadero, se ejecuta S.
  • Si G es falso, lo que se hará dependerá del contexto.

Las sentencias G pueden cambiar estados:

x, z = y, y + 1 el nuevo valor de x es y y el nuevo valor de z es y + 1

o realizar entrada y salida:

print "Salida"

Naturalmente, una implementación de comandos guardados puede permitir cualquier anchura para las condiciones y sentencias.

Un comando guardado se puede presentar por sí sólo como una sentencia; en comandos que siempre se ejecutan, la guarda se puede omitir:

true \rightarrow print 5

es equivalente a:

print 5

Skip y Abort

Skip y Abort son enunciados simples pero importantes en el lenguaje de comandos guardados.

  • Abort es la instrucción indefinida: hacer cualquier cosa. El enunciado Abort no tiene por qué implicar la terminación (aborto) del programa; se usa para describir el programa al formular una demostración, en cuyo caso la demostración generalmente falla.
  • Skip es la instrucción vacía: no hacer nada. Se usa en el programa en sí mismo, cuando la sintaxis requiere un enunciado y el programador no quiere que la máquina cambie estados.

La construcción condicional if

La construcción condicional o de selección es una lista de comandos guardados, de los cuales uno es escogido para ser ejecutado. Si más de una guarda es verdadera, el enunciado que se ejecutará se escoge de forma aleatoria o de forma determinística. Si ninguna guarda es verdadera, el resultado es indefinido (semánticamente equivalente a una instrucción Abort). Ya que al menos una guarda ha de ser verdadera, es frecuente que se necesite la instrucción Skip.

Sintaxis

if
G_{0} \rightarrow S_{0}
[]\ G_{1} \rightarrow S_{1}
...
[]\ G_{n} \rightarrow S_{n}
fi

Semántica

  • Si ninguna de las guardas es verdadera: Abort;
  • Si solamente la guarda Gx es verdadera: ejecutar Sx;
  • Si las guardas G_{x_{0}}\ ...\ G_{x_{m}} son verdaderas: ejecutar cualquier S_{x_{y}}, donde 0 \leq y \leq m

Ejemplo

Dada la expresión en pseudocódigo:

if a \ge b then print "Mayor ó igual";
else if a < b then print "Menor";

El equivalente en comandos guardados es:

if
a \ge b \rightarrow print "Mayor ó igual"
a < b \rightarrow print "Menor"
fi

La potencia de los comandos guardados se ilustra en la siguiente expresión:

if
a \ge b\rightarrow print "Mayor ó igual"
a \le b \rightarrow print "Menor ó igual"
fi

Cuando a = b, el resultado del comando puede ser o bien "Mayor ó igual" o bien "Menor ó igual" (pero no los dos).

La construcción de bucle do

La construcción de repetición do se escribe así:

do
G_{0} \rightarrow S_{0}
[]\ G_{1} \rightarrow S_{1}
...
[]\ G_{n} \rightarrow S_{n}
od

Las guardas de los comandos guardados se evalúan. Si una de ellas es verdadera, se ejecuta el enunciado correspondiente. Si más de una es verdadera, se ejecuta sólo un enunciado escogido de entre los correspondientes de forma aleatoria o no-determinística. El proceso se repite hasta que ninguna de las guardas evalúe como verdadera (es decir, después de ejecutar un comando se vuelve a evaluar las guardas desde el principio).

Ejemplo

A continuación se da una implementación del algoritmo de Euclides para hallar el máximo común divisor.

x, y = X, Y
do de nuevo, terminación cuando x = y
x > y \rightarrow x:= x-y
y > x \rightarrow y:= y-x
od
print x

Aplicaciones

Circuitos Asíncronos

Los comandos guardados son adecuados para diseño de circuitos QDI porque la construcción do-od permite retrasos relativos arbitrarios para la selección de comandos diferentes. En esta aplicación, una puerta lógica manejando un nodo y en el circuito consiste en dos comandos guardados, como sigue:

PulldownGuard \rightarrow y := 0
PullupGuard \rightarrow y := 1

PulldownGuard y PullupGuard son funciones de la entrada de la puerta lógica, que describen las acciones de salida pull down y pull up respectivamente.

Al contrario que modelos clásicos de evaluación de circuitos, el modelo do-od para un conjunto de comandos guardados (correspondiendo a un circuito asíncrono) puede describir con precisión todos los posibles comportamientos dinámicos del circuito.

Implementaciones

Algunas implementaciones de lenguaje de comandos guardados:

  • GaCeLa es una aproximación a un compilador verificante que genera programas que deben cumplir con su especificación, de lo contrario son interrumpidos durante su ejecución. Esta notación (y su correspondiente traductor al lenguaje Java) está siendo desarrollada en la Universidad Simón Bolívar en Venezuela.

Referencias

  1. Dijkstra, Edsger W. «EWD472: Guarded commands, non-determinacy and formal. derivation of programs.».

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Comandos Guardados — Saltar a navegación, búsqueda Comandos guardados (GCL) órdenes guardadas es un modelo de lenguaje definido por Edsger Dijkstra para semántica de transformación de predicados (una extensión lógica diseñada para proporcionar una metodología para… …   Wikipedia Español

  • Semántica de transformación de predicados — La semántica de transformación de predicados es una extensión de Lógica de Floyd Hoare ideada por Edsger Dijkstra y extendida y refinada por otros investigadores. Esta extensión fue presentada por Dijkstra en sus artículos titulados Guarded… …   Wikipedia Español

  • Lotus Symphony — Saltar a navegación, búsqueda Lotus Symphony Desarrollador Lotus Software Lotus Symphony Información general …   Wikipedia Español

  • IBM Lotus Symphony — Lotus Symphony Desarrollador Lotus Software http://www.ibm.com/software/lotus/symphony Información general Última versión estable …   Wikipedia Español

  • Estructuras de control — En lenguajes de programación, las estructuras de control permiten modificar el flujo de ejecución de las instrucciones de un programa. Con las estructuras de control se puede: De acuerdo a una condición, ejecutar un grupo u otro de sentencias (If …   Wikipedia Español

  • Kernel Language 1 — o KL1 es un lenguaje de programación desarrollado en 1987 por el Institute for New Generation Computer Technology (Instituto para la Nueva Generación de Tecnologías de Computación, o ICOT por su siglas en inglés) en el marco del proyecto japonés… …   Wikipedia Español

  • Edsger Dijkstra — Saltar a navegación, búsqueda Edsger Wybe Dijkstra …   Wikipedia Español

  • Historia de los lenguajes de programación — Anexo:Historia de los lenguajes de programación Saltar a navegación, búsqueda Algunos de los lenguajes de programación más importantes por año son: 1943 Plankalkül (Konrad Zuse) 1943 ENIAC 1949 C 10 1951 Regional Assembly Language 1952 Autocode… …   Wikipedia Español

  • Anexo:Historia de los lenguajes de programación — Algunos de los lenguajes de programación más importantes por año son: 1943 Plankalkül (Konrad Zuse) 1943 ENIAC 1949 C 10 1951 Regional Assembly Language 1952 Autocode 1954 FORTRAN 1958 LISP 1958 ALGOL 1959 COBOL 1962 APL 1962 Simula 1964 BASIC …   Wikipedia Español

  • MSX BASIC — Desarrollador(es) microsoft.com Información general Paradigma Imperativo …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”