Download modelos computacionales - escuela de informática UTEM

MODELOS
COMPUTACIONALES
Alejandro Aguilar García
Natalia Domínguez Corbacho
Jerónimo Valverde Martínez
Manuel Chacón Martín
María Cuevas Rodríguez
Carlos Porta Gómez
Elementos de Programación
1º C E. T. S. I. Telecomunicaciones
INDICE
INTRODUCCIÓN...............................................................................pág. 3
MÁQUINA DE TURING....................................................................pág. 5
MODELO DE JOHN VON NEUMANN.............................................pág. 7
MODELO HARVARD........................................................................pág. 8
SISTEMAS DE PROGRAMACIÓN FUNCIONAL ..........................pág. 11
SISTEMAS FORMALES FUNCIONALES ......................................pág. 13
BIBLIOGRAFÍA ...............................................................................pág. 15
2
INTRODUCCIÓN
NATURALEZA DE LOS COMPUTADORES
-------------------------------------------------------Para abordar el tema de los modelos computacionales hay que tener más o
menos claras algunas definiciones básicas:
¿Qué es un COMPUTADOR?
Aunque una definición exacta sería muy difícil de encontrar se podría definir como un
sistema al que se le suministra información en forma de datos para luego devolvernos
unos resultados acordes con la resolución de un determinado problema. Por lo tanto
podríamos decir que el objetivo del computador es básicamente resolver problemas.
Para ello hace uso de los programas.
¿Qué es un PROGRAMA?
Es una secuencia de instrucciones que resuelven determinados problemas planteados.
¿Qué es la INFORMACIÓN?
En general es cualquier conjunto de noticias, informes o datos que nos aportan algún
nuevo conocimiento. En informática más concretamente estos datos se transmiten en
forma de señales.
Antecedentes históricos
---------------------------La Computación tiene su origen en el cálculo, es decir, en la preocupación del
ser humano por encontrar maneras de realizar operaciones matemáticas de forma cada
vez más rápida y más fácilmente. Pronto se dio cuenta que con ayuda de aparatos y
máquinas las operaciones podían realizarse de forma más rápida y automática.
El primer ejemplo que encontramos en la historia es el ábaco, aparecido hacia el
500 AC en Oriente Próximo, que servía para agilizar las operaciones aritméticas
básicas.
También es digno de señalar el conocido Mecanismo de Antikythera, recuperado
en 1900, construido alrededor del año 80 a.C., en la isla griega de Rodas. Era un
artefacto de cálculo astronómico con mecanismos de precisión. El usuario, por medio de
una perilla, podía accionar un simulador en miniatura del movimiento del sol, la luna y
varios planetas, teniendo a la vista la fecha en que se había dado, o se daría, tal
combinación.
La historia de la computación es muy extensa por que a continuación citaremos
los acontecimientos más relevantes hasta la primera generación de computadores, donde
surgieron los primeros modelos computacionales:
1623.Shickard construye la primera calculadora, basada en ruedas dentadas y capaz de
sumar y multiplicar.
3
1642.Pascal a la edad de 19 años inventa para su padre (un contable) una máquina que
suma y resta.
1671.Leibnitz mejora la máquina de Pascal, siendo capaz de multiplicar y dividir.
1777.Mahon construye una máquina aritmética y otra lógica, "Demostrador de
Stanhope".
1820.Charles Babbage construye en parte la máquina analítica, considerándose el
primer computador digital de próposito general. Sus características eran: trabajaba con
una aritmética de 50 digitos decimales, tardaba 1 segundo en hacer sumas y restas y
alrededor de un minuto con las multiplicaciones y divisiones, utilizaba tarjetas
perforadas para las operaciones y las variables.
1854.Boole publica "Las leyes del pensamiento" sobre las cuales son basadas las teorías
matemáticas de Lógica y Probabilidad. Empezaba asi el Álgebra Booleana, que consiste
en un método para resolver problemas de lógica que recurre solamente a los valores
binarios 1 y 0 y a tres operadores: AND, OR y NOT.
1890.Hollerith construye una máquina para tabular el censo.
1914.Torres Quevedo con tecnología electromagnética diseña los esquemas de una
calculadora digital.
1936.Alan Turing contestó a la cuestión de si las matemáticas son "decidibles",
planteada años atras, construyendo un modelo formal de computador, la Máquina de
Turing, y demostrando que había problemas tales que una máquina no podía resolver.
Al mismo tiempo en Estados Unidos contestaba a la misma cuestión Alonzo Chuch,
basándose en una notación formal, que denominó cálculo lambda, para transformar
todas las fórmulas matemáticas a una forma estándar.
1938.Stibitz crea MODEL I, el primer sistema con terminales remotos, que empleaba
números complejos para cálculos balísticos.
1941.Basándose en los resultados de Turing y de Chuch, Zuse diseñó y construyó su
serie de computadores electromecánicos binarios, desde el Z1 hasta el Z3.
1942.Atanasoff construye una máquina de propósito general con tubos de vacío. Fue la
primera computadora electrónica digital.
1943.Mauchy y Eckert construyen el ENIAC (Electronic Numeric Integrator and
Calculator). Sus características: empleaba 18000 tubos de vacío; consumía 150 kW;
tenía una medidas de 30x2,5 metros; utilizaba 20 registros de 10 dígitos decimales;
tardaba 200 microsegundos en la suma, 2,8 milisegundos en la multiplicación y 6
milisegundos en la división; seguía utilizando el sistema de tarjetas perforadas.
1945.Von Neumann tiene una idea innovadora que es almacenar en una memoria rápida
datos e instrucciones para que para modificar un programa baste con modificar las
instrucciones almacenadas en la memoria. A este modelo se le conoce como "Modelo
de von Neumann" y es el que aún en día emplean los computadores.
4
MÁQUINA DE TURING
Alan Mathison Turing, matemático y computador científico inglés, desarrolló en
torno a 1935 y 1945 un modelo computacional hipotético que permite en teoría resolver
cualquier problema matemático siempre y cuando se reduzca a un algoritmo (conjunto
ordenado y finito de operaciones que permiten la resolución de un problema, como por
ejemplo la extracción de raíces cuadradas o el cálculo de una suma, producto o división
de números, etc). De esta forma será posible calcular funciones dadas a partir de las
operaciones más simples posibles y, aunque sea un algoritmo muy complejo, será
posible descomponerlo en una mayor cantidad de pasos hasta resolverlo. Este modelo,
que en principio vino a llamarse Máquina de computación lógica (“Logical Computing
Machine”), pero que en honor a su ideador se le acabó llamando máquina de Turing, es
considerada la precursora de la computación digital moderna a pesar de su sencillez
estructural. Según la Tesis de Church-Turing (llevada a cabo por Alan Turing y Alonzo
Churh a mediados del siglo XX de forma independiente), se demuestra que un problema
es computable si se puede construir una máquina de Turing capaz de llevar a cabo el
procedimiento para resolverlo y que para cualquier otra máquina alternativa a ésta, se
puede crear una Máquina de Turing equivalente capaz de resolver cualquier
computación que se realice en la otra máquina.
Un esquema básico de lo que puede ser una Máquina de Turing es el siguiente:
Los componentes de esta máquina y sus descripciones son:
• Memoria: se trata de una cinta infinitamente larga dividida en celdas cuadradas
en cada una de las cuales hay un símbolo de un código (por ejemplo, un símbolo del
código binario, es decir, un 1 o un 0, por lo que la cinta ocupa un bit). Este conjunto de
símbolos, o código, es lo que se conoce como alfabeto de la máquina. En esta memoria
se permite el almacenamiento tanto de la información introducida y de los datos de
salida, como de los pasos intermedios que se han llevado a cabo para resolver el
algoritmo, lo que permite algo muy útil: hacer un seguimiento del proceso llevado a
cabo. Debido al múltiple uso que se le da a la memoria y a la imposibilidad de conocer
el número de pasos intermedios que la máquina va a necesitar, es por lo que la cinta
debe ser ilimitada. Es precisamente este detalle de memoria sin fin lo que le otorga tanta
importancia a la máquina de Turing.
5
• Cabezal de lectura-escritura: es un dispositivo capaz de realizar cuatro
operaciones: desplazarse una posición a la derecha respecto a la celda actual,
desplazarse una posición a la izquierda, leer el contenido de la celda en la que se
encuentra y escribir un símbolo distinto al que había sido leído por el cabezal o escribir
nuevamente el que había en la celda.
• Procesador: es un dispositivo digital que puede dividirse en dos partes atendiendo
a las distintas funciones que cumple cada una dentro de la máquina. Por un lado existe
un registro de estado que contiene un número determinado de posibles estados internos
de la máquina y que almacena el estado concreto en el que se encuentra el procesador.
Por otra parte existe una tabla de acción que contiene las instrucciones de lo que realiza
la máquina en cada instante de tiempo. Esta última parte del procesador es la encargada
de decidir cuál será el nuevo estado, el símbolo que se va a escribir en la cinta y la
dirección que tomará el cabezal dependiendo del carácter que se acaba de leer y del
estado actual interno. Por así decirlo, esta parte contendría todo el programa posible de
la máquina.
La máquina de Turing funciona de la siguiente forma para realizar una computación
Z=f(x): el dato de entrada x se codifica de forma que se pueda almacenar en la memoria,
entonces se comienza el proceso con los pasos para resolver la función, escribiéndolos
en la memoria. Cuando termine la última operación, la máquina reflejará en la cinta el
resultado.
Por este mismo hecho de que la propia máquina, como si de una mente humana se
tratara, es la que toma las decisiones dependiendo del estado interno del procesador y de
la información externa que el cabezal lee en la cinta, este modelo computacional es
considerado una máquina autómata capaz de alterar su propio programa. Es más, Turing
estaba más interesado en la posibilidad de crear modelos lógicos cuyas acciones se
asemejaran al funcionamiento de la mente, que en las aplicaciones prácticas de un
modelo de computación.
A pesar de ser sólo un modelo teórico, a la máquina de Turing se la considera una
máquina por el hecho de que su funcionamiento se reduce a operaciones tan simples y
reales que se ajustan a la definición de dispositivo. Esto ha hecho que existan numerosas
versiones prácticas de este modelo, aunque no se trata de máquinas de Turing completas
porque sus memorias están limitadas al ser imposible construir modelos reales con
memoria ilimitada. Es más, es tan importante en el mundo de la computación que hoy
en día, numerosos trabajos de computación toman como referencia este modelo
computacional.
6
MODELO DE JOHN VON NEUMANN
Desde tiempos muy antiguos el hombre ha necesitado hacer cálculos. Para ello se ha
buscado maquinas que lo ayudasen, como el ábaco, las hileras de John Napier… La
primera maquina interesante es la “La Maquina Analítica” de Charles Babbage.
En 1945John Von Neumann (1903 – 1957) creó un modelo computacional que se
caracteriza por disponer de una única memoria principal en la que se almacenan los
datos y las instrucciones. A esta memoria se accede a través de un sistema de buses
único: bus de datos, de direcciones y de control. Este modelo se usa hoy día para
describir los lenguajes de programación convencionales y es la base de prácticamente
todos los modelos de ordenadores.
Modelo de Von Neumann
Este modelo tiene varias características clave que se muestran de una manera u otra
en todos los sistemas actuales:
.
Una Unidad de Memoria (a memory unit) que almacena valores e instrucciones en
unos lugares específicos denominados celdillas, los cuales forman la memoria y son de
un tamaño prefijado.
Una Unidad Central de Proceso, UCP (a central processing unit, CPU) que accede a
la memoria de forma secuencial.
Una Instrucción (an instruction) que especifica alguna secuencia particular de
actividades en la CPU que modifican los contenidos de las localizaciones de la memoria
o los registros de la CPU.
Un Programa (a program) que consiste en una secuencia ordenada de instrucciones
colocada en la memoria.
Un Controlador de Programa (a Program Counter) en la CPU para seleccionar la
siguiente instrucción de la memoria
Un Lenguaje de Programación (a programming language) que especifica como y
que instrucciones se pueden colocar en la memoria.
7
Los sistemas basados en el modelo de Von Neumann tienen un solo bus para acceder
tanto a datos como a instrucciones y esto es una de las características más incomodas de
este sencillo modelo. Diremos que un microcontrolador es de 4 bit cuando el bus de este
sea de 4 bit, será de 8 bit cuando el bus sea de 8 bit...
Aunque por otra parte se puede considerar una ventaja, ya que al haber un único
cableado (bus) para el acceso a datos e instrucciones, se facilita en gran medida la
conexión de memoria externa a través de las líneas de entrada salida con una mínima
implementación extra de hardware.
Por contra, tenemos que una instrucción puede ocupar más de unbyte con lo que
para poder leer la instrucción completa tendremos que hacer varias lecturas en la
memoria con lo que debemos de emplear varios ciclos de reloj para extraer una
instrucción.
Otra desventaja es que es posible que el contenido del contador del programa (PC) se
corrompa con lo que se podría estar leyendo un dato y tratar de interpretarlo como
instrucción pudiendo producirse como consecuencia un deterioro y caída del sistema.
Normalmente un microprocesador debe de controlar que el PC no haga cosas raras.
La principal característica del modelo de Von Neumann es que durante su ejecución,
los programas únicamente pretenden “modificar la memoria”. Debemos conocer las
localizaciones de los datos antes de ejecutar los programas para recoger después los
resultados. Esto es internamente patente en el funcionamiento y la semántica de los
lenguajes de programación convencionales. En estos lenguajes de programación la
instrucción más importante es la de asignación. Todos los lenguajes de programación
convencionales disponen de modos de asignación más o menos significativos.
Otra de las características que poseen los microcontroladores basados en este tipo de
arquitectura es que suelen tener un repertorio de instrucciones bastante grande. Este tipo
de repertorio se llama CISC del inglés Complex Instruction Set Computer. La
característica principal que este tipo de conjunto de instrucciones que suele ser bastante
elevado y las instrucciones están microcodificadas, es decir, que una instrucción será
decodificada por la CPU en varias instrucciones básicas.
MODELO DE HARVARD
La arquitecturaHarvard se caracteriza por tener la memoria de datos separada de la
memoria del programa y estas a su vez están unidas a la CPU a través de buses
independientes, luego, pueden tener distintos contenidos en la misma dirección.
La arquitectura deHarvard permite a la CPU acceder silmutáneamente a las dos
memorias. Además propicia numerosas ventajas al funcionamiento del sistema.
Arquitectura del modelo de Harvard
8
El que la información se almacene en palabras tiene una gran ventaja y es que tanto
el codop como el dato asociado a este están en la misma posición por lo que su lectura
es mucho más rápida. Esta es una gran ventaja ya que dota al microcontrolador de gran
agilidad. La técnica de procesar varias instrucciones al mismo tiempo se conoce como
pipelining o segmentación. Con esta técnica se dividen las instrucciones en distintas
etapas de modo que el procesador puede procesar distintas instrucciones en estas etapas.
Una desventaja de este sistema es que la adición de memoria externa es mucho mas
compleja en incluso a veces imposible.
Este modelo presenta más rapidez de ejecución de código, incluso en algoritmos de
división que vienen implementados con más código en los RISC que el los CISC, la
velocidad de ejecución es mayor en los primeros. Menor número de instrucciones es una
ventaja a la hora de elegir este tipo de microcontroladores para determinadas tareas, no
hace falta aprender tantas instrucciones cuando queremos programar un mcu para una
tarea simple.
Por contra usaremos en general más memoria en un pic que en un HC11 para realizar
una misma función, aunque depende de ésta, hablamos en general.
Comparación Von Neumann – Harvard
Harvard y Von Neumann son dos arquitecturas que se caracterizan por la forma en la
que distribuyen la memoria de datos y de programa dentro de un microcontrolador.
Modelo de Von Neumann
Modelo Harvard
En la arquitectura
Harvard, la memoria de datos y de programa están separadas,
usando para almacenar las instrucciones lo que se llaman palabras. Palabras las hay de
muchos tamaños como por ejemplo en los microcontroladores PIC. Los PIC de gama
baja usan palabras de 12 bit, los de gama media 14 bit y los de gama alta 16 bit.
Por otro lado esta la arquitectura
Von Neumann que se caracteriza por tener la
memoria de programa y la de datos implementada en un mismo bloque de memoria
compartiendo datos e instrucciones en un mismo bus.
En este tipo de microcontroladores se usan
bytes para almacenar datos e
instrucciones.
Un ejemplo de estos microcontroladores son losZilog, National Semiconductors o
los de Motorola.
Ambas arquitecturas tienen ventajas e inconvenientes, como hemos enumerado en
apartados anteriores, y como siempre en el mundo de la electrónica, dependiendo de la
aplicación en la que vayamos a usar el microcontrolador, frecuencia de trabajo,
conexión a otros periféricos etc, deberemos de elegir un microcontrolador u otro.
9
En esta tabla podemos ver una comparación de ambos modelos.
Microcontrolador Arquitectura Conjunto de instrucciones Nº de instrucciones
Pic 16Cxxx
Hardvard
RISC
35
Pic 17Cxxx
Hardvard
RISC
58
Motorola HC11
Von Newman
CISC
109
Intel 8051
Von Newman
CISC
40
Así pues podemos decir que la principal ventaja de usar
mcu´s con conjunto de
instrucciones CISC es que para una instrucción compleja solo usaremos una posición de
memoria al contrario que ocurre con RISC que para realizar por ejemplo una división
debemos de usar varias instrucciones consumiendo más memoria.
Frente a esta ventaja de los repertorios CISC, se nos presenta una desventaja con
respecto a los RISC, y es que el ancho de banda se va reducido considerablemente
debido a que una instrucción va a consumir varios ciclos de instrucción para ejecutarse,
ya lo vimos antes, estos microcontroladores son más lentos que los que usan repertorios
RISC y además puede ser que el conjunto de instrucciones sea bastante grande, véase
Motorola HC11 lo que no es una gran pega pero si mas trabajo para aprendérselo y
aprender a usarlo.
10
SISTEMA DE PROGRAMACIÓN FUNCIONAL
(FP system)
Descripción
Un modelo funcional se caracteriza por tener simplemente funciones sin
variable, en este tipo de sistemas la descripción esta seguida por algunos ejemplos y por
una discusión de varias propiedades del sistema
En este tipo de sistemas encontramos que se usan un número fijo de formularios
llamados formularios funcionales. Esto añadiéndole algunas definiciones simples son
usadas para construir funciones nuevas desde algunas existentes. Todas las funciones de
un sistema funcional son de un solo tipo (enlazan objetos con objetos).
Los formularios funcionales, al contrario que la mayoría de las construcciones
de programación, están asociadas al álgebra lo que ofrece poderosas construcciones de
programación pero también tienen propiedades algebraicas atractivas:
Una lección de ellas para maximizar la fuerza y utilidad de las leyes del álgebra que las
relacionan con otros formularios de este sistema.
En la siguiente descripción nosotros debemos ser imprecisos en no distinguir
entre una función símbolo o expresión, y la función que denota. Debemos indicar el
símbolo y la expresión para denotar funciones por ejemplo y uso.
Un sistema funcional se compone de lo siguiente:
a) Un conjunto O de objetos
b) Un conjunto F de funciones
c) Una operación (aplicación)
d) Un conjunto F de formularios funcionales que se usan para combinar funciones
existentes u objetos para formar nuevas funciones en F
e) Un conjunto D de definiciones que definen algunas funciones en F y asignan un
nombre a cada una
Observaciones acerca del sistema de programación funcional
Los sistemas de programación funcional son tan simples que algunos usuarios
pueden encontrarlo difícil de ver como un lenguaje de programación.
Este sistema contiene un cierto numero de limitaciones, al tener un lenguaje fijo
no son capaces de modificar la librería del programa
Un sistema de programación funcional no puede computar un programa cuando
las expresiones funcionales no son objetos. Ni tampoco puede definir nuevos
11
formularios funcionales sin un sistema funcional (estas limitaciones no se encuentra en
los sistemas funcionales formales, “FFP”)
El poder expresivo de este tipo de sistemas suponga dos sistemas funcionales,
ambos tienen el mismo conjunto de objetos y el mismo conjunto de funciones
primitivas, pero el conjunto de formularios del primero incluye correctamente al
segundo. Suponga también que otros sistemas pueden expresar todas las funciones
computables de objetos, sin embargo podemos decir que el primero es mas expresivo
que el primero cuando todas las funciones expresadas en el segundo pueden ser
duplicadas en el primero, pero usando un formulario no perteneciente al segundo, el
primero puede expresar mas directamente y fácilmente algunas funciones que el
segundo.
La principal razón por la que los sistemas funcionales están considerados mas
simples que otros lenguajes convencionales es que solo usan un sistema fijo y elemental
de nombramiento. Lo más importante es que trata los nombres como funciones que
pueden ser combinadas con otras funciones sin tratamiento especial. Esto le permite la
oportunidad de desarrollar a un nivel más alto las técnicas para manipular y producir
programas superando en este aspecto al sistema de Von Neumann.
Otros problemas interesantes son encontrar algoritmos par expandir y analizar el
comportamiento de las funciones para varias clases de argumentos y explorar caminos
de uso de leyes y teoremas como reglas básicas de un esquema formal.
El álgebra del sistema de programación funcional
Este sistema requiere un conocimiento moderado de matemáticas y lógica, pero
el nivel teórico necesario lo puede alcanzar cualquiera que trabaje fuera del campo de
las matemáticas.
Una ventaja de esta álgebra sobre otras técnicas, es que el programador puede
usar su propio lenguaje como un lenguaje de pruebas derivadas.
En el corazón de este álgebra hay leyes y teoremas, las cuales son fáciles de
entender y de justificar, y poderosas para usar. Posiblemente nosotros también
deseamos usar dichas leyes para resolver ecuaciones en las cuales desconocemos si una
ecuación tiene función aparente en ambos lados de la ecuación.
El objetivo es desarrollar una fundación para el álgebra de programa que
disponga de problemas teóricos, así el programador puede usar leyes algebraicas
simples y uno o dos teoremas de fundaciones para resolver problemas y crear problemas
del mismo estilo como los que nosotros nos encontrábamos en el instituto.
En el álgebra usado en este tipo de sistema de programación, para unas
variables, aumenta el rango de funciones del sistema. Las operaciones de álgebra se
realizan mediante formularios funcionales.
Este álgebra necesita mucho trabajo para proporcionar expansiones para tipos de
ecuaciones largas y para extender sus leyes y teoremas.
12
SISTEMAS FORMALES FUNCIONALES
(FFP System)
Como ya hemos visto, un sistema de programación funcional tiene un conjunto
de funciones que depende de un conjunto de funciones primitivas, un conjunto de
formularios funcionales y un conjunto de definiciones. En particular, es un conjunto de
formularios funcionales fijados en un principio y para todos, y este conjunto determina
el poder del sistema en el principal camino. Por ejemplo, si este conjunto de formularios
funcionales está vacío, entonces el conjunto de funciones se reduce apenas al conjunto
de funciones primitivas.
En un sistema funcional formal uno pude crear nuevos formularios funcionales. Los
formularios funcionales están representados por secuencias de objetos; El primer
elemento de una secuencia de objetos determina que forma lo representa, mientras que
el resto de los elementos son los parámetros del formulario.
La capacidad para definir nuevos formularios funcionales en sistemas
funcionales formales es una consecuencia de la diferencia principal entre estos sistemas
y otros sistemas:
En los sistemas funcionales formales los objetos se usan para “representar”
funciones en un camino sistemático. En este sentido los sistemas funcionales formales
se parecen bastante a los sistemas de programación funcional.
En estos sistemas se parte de una sintaxis simple, discutiendo su semántica
informalmente, dando ejemplos y finalmente obteniendo su semántica formal
Sintaxis
Describimos un conjunto O de objetos y el conjunto E de expresiones en un
sistema funcional formal. Estos dependen de la opción de cierto conjunto A de átomos,
cuál tomamos según lo dado.
Asumimos que T (verdadero), F (falso), ø (secuencia vacía) y # (defecto) pertenecen a
A, así como números de varias clases, etc.
a) Fondo, _, es un objeto pero no un átomo.
b) Cada átomo es un objeto.
c) Cada objeto es una expresión
d) Si x e y son expresiones, entonces (x:y) es una expresión llamada aplicación. x es
el operador e y es el operando. Ambos son elementos de la expresión.
e) Todos los objetos y expresiones están formados por las infinitas combinaciones
y usos de estas reglas.
13
Observaciones informales acerca de los sistemas funcionales
formales
Significado de expresiones; la función semántica _
Cada expresión de los sistemas funcionales formales del tipo e, tiene un
significado, _e, que siempre es un objeto; _e se encuentra en varias ocasiones
sustituyendo cada uso intimo de e por este significado.
Si el proceso es “no terminado”, el significado de e es _. El significado de una aplicaron
intima (x:y) es el resultado de aplicar la función representada por x en y, como en los
sistemas de programación funcional, excepto que en los sistemas funcionales formales
están representados por objetos, mas bien por funciones expresiones, con átomos
representado funciones primitivas y definidas, y con secuencias representado las
funciones de programación funcional denotadas por formularios funcionales.
Objetos representado funciones; la función representación
Como hemos visto, algunos átomos (átomos primitivos) pueden representar
funciones primitivas de un sistema. Otros átomos pueden representar funciones
definidas como los símbolos lo hacen en los sistemas de programación funciona. Si un
átomo no es primitivo ni definido, éste representa _.
Las secuencias también representan funciones y son análogas a los formularios
funcionales de los sistemas de programación funcional. La función representada por una
secuencia viene dada por la regla de metacomposición (“metacomposition rule”)
Definiciones en sistemas funcionales formales
La semántica de sistemas funcionales formales de programación depende de un
conjunto fijo ‘D’ de definiciones, como en el sistema de programación funcional
depende del conjunto de definiciones dado informalmente. Así la función semántica _
depende de D, alterando D se obtiene una nueva _’ que refleja la alteración de
definiciones.
Semánticas formales para los sistemas funcionales formales
Asumimos que el conjunto A de átomos, el conjunto D de definiciones, el
conjunto P perteneciente a A de átomos primitivos y las funciones primitivas
representan haber sido escogidos. También asumimos que _a es la función primitiva
representada por a si a pertenece a P, que _a = _ si a pertenece a Q, el conjunto de
átomos en P-A que no está definido en D. Aunque _ esté definido por todas las
expresiones, las semánticas formales usan estas definiciones solo en P y Q. Las
funciones que _ asigna a otras expresiones x son determinadas implícitamente y
aplicadas en las siguientes reglas de semántica para su evaluación _(x:y). Las opciones
antedichas de A y D, y de P y las funciones primitivas asociadas determinan los objetos,
expresiones y la función semántica _ para un sistema funcional formal. (Miramos D
como fijo y escribimos _ por _ .) Asumimos que D es una secuencia y que _y:D puede
ser computada por algún átomo y.
D
D
14
BIBLIOGRAFÍA
“Fundamentos de los Computadores”, Pedro de Miguel Anasagasti. Ed. Paraninfo
“Fundamentos de los Computadores”, Rafael Asenjo Plaza, Eladio Gutiérrez, Julián
Ramos Cózar. Universidad de Málaga / Manuales.
“Turing’s World 3.0. An Introduction to Computability Theory”, Jon Barwise y John
Etchemendy. CSLI Publications, Standford, California.
“Introducción a la Arquitectura de Computadores”, Javier Bastida Ibáñez, Universidad
de Valladolid.
“Programming Languages, A Grand Tour”, Ellis Horowitz. Ed. Computer Science Press
“Introducción a la teoría de la Computabilidad”, Hans Hermes, Edit. Tecnos.
http://www.terra.es/personal/fremiro/arquitectura.htm
http://www.eurobotics.org/hardvardvsvon.html
15