Lenguaje de programación
Planner (a menudo visto en publicaciones como "PLANNER" aunque no es un acrónimo) es un lenguaje de programación diseñado por Carl Hewitt en el MIT y publicado por primera vez en 1969. Primero, se implementaron subconjuntos como Micro-Planner y Pico-Planner, y Luego , Julian Davies en la Universidad de Edimburgo implementó esencialmente todo el lenguaje como Popler en el lenguaje de programación POP-2 . [1] Derivaciones como QA4, Conniver, QLISP y Ether (ver metáfora de la comunidad científica ) fueron herramientas importantes en la investigación de inteligencia artificial en la década de 1970, que influyeron en desarrollos comerciales como Knowledge Engineering Environment (KEE) y Automated Reasoning Tool (ART).
Enfoque procedimental versus enfoque lógico
Los dos paradigmas principales para la construcción de sistemas de software semántico fueron el procedimental y el lógico . El paradigma procesal fue personificado por Lisp [2] , que presentaba procedimientos recursivos que operaban en estructuras de listas.
El paradigma lógico se personificó en los buscadores de derivación (prueba) basados en resolución de procedimiento de prueba uniforme . [3] Según el paradigma lógico, incorporar conocimientos procedimentales era “hacer trampa”. [4]
Incorporación procesal del conocimiento.
Planner se inventó con el propósito de incorporar conocimientos procedimentalmente [5] y fue un rechazo del paradigma del procedimiento de prueba uniforme de resolución , [6] que
- Convirtió todo a forma clausal. Convertir toda la información a forma clausal es problemático porque oculta la estructura subyacente de la información.
- Luego utilizó la resolución para intentar obtener una prueba por contradicción añadiendo la forma clausal de la negación del teorema a demostrar. Usar únicamente la resolución como regla de inferencia es problemático porque oculta la estructura subyacente de las pruebas. Además, utilizar la prueba por contradicción es problemático porque las axiomatizaciones de todos los dominios prácticos del conocimiento son inconsistentes en la práctica.
Planner era una especie de híbrido entre los paradigmas procedimental y lógico porque combinaba la programabilidad con el razonamiento lógico. Planner presentó una interpretación procedimental de oraciones lógicas donde una implicación de la forma (P implica Q) se puede interpretar procedimentalmente de las siguientes maneras utilizando la invocación dirigida por patrones:
- Encadenamiento directo (antecedentemente):
- Si afirma P, afirma Q
- Si afirma no Q, afirma no P
- Encadenamiento hacia atrás (en consecuencia)
- Si objetivo Q, objetivo P
- Si el objetivo no es P, el objetivo no es Q
En este sentido, el desarrollo de Planner estuvo influenciado por los sistemas lógicos deductivos naturales (especialmente el de Frederic Fitch [1952]).
Implementación del microplanificador
Gerry Sussman , Eugene Charniak y Terry Winograd [7] implementaron un subconjunto llamado Micro-Planner y se utilizó en el programa de comprensión del lenguaje natural SHRDLU de Winograd , el trabajo de comprensión de historias de Eugene Charniak, el trabajo de Thorne McCarty sobre razonamiento legal y algunos otros proyectos. Esto generó un gran entusiasmo en el campo de la IA. También generó controversia porque proponía una alternativa al enfoque lógico que había sido uno de los paradigmas fundamentales de la IA.
En SRI International , Jeff Rulifson, Jan Derksen y Richard Waldinger desarrollaron QA4, que se basó en las construcciones de Planner e introdujo un mecanismo de contexto para proporcionar modularidad a las expresiones en la base de datos. Earl Sacerdoti y Rene Reboh desarrollaron QLISP, una extensión de QA4 integrada en INTERLISP , que proporciona un razonamiento similar al de Planner integrado en un lenguaje procedimental y desarrollado en su rico entorno de programación. QLISP fue utilizado por Richard Waldinger y Karl Levitt para la verificación de programas, por Earl Sacerdoti para el monitoreo de la planificación y ejecución, por Jean-Claude Latombe para el diseño asistido por computadora, por Nachum Dershowitz para la síntesis de programas, por Richard Fikes para la recuperación deductiva y por Steven Coles por uno de los primeros sistemas expertos que guiaban el uso de un modelo econométrico.
Las computadoras eran caras. Sólo tenían un procesador lento y sus memorias eran muy pequeñas en comparación con las actuales. Entonces Planner adoptó algunos expedientes de eficiencia que incluyen los siguientes:
- Se adoptó el retroceso [8] para ahorrar en el uso de tiempo y almacenamiento al trabajar y almacenar solo una posibilidad a la vez al explorar alternativas.
- Se adoptó una suposición de nombre único para ahorrar espacio y tiempo, suponiendo que diferentes nombres se referían a diferentes objetos. Por ejemplo, se suponía que nombres como Pekín (anterior nombre de la capital de la República Popular China) y Beijing (transliteración actual de la capital de la República Popular China) se referían a objetos diferentes.
- Se podría implementar una suposición de mundo cerrado probando condicionalmente si un intento de demostrar un objetivo de manera exhaustiva fracasó. Más tarde, a esta capacidad se le dio el nombre engañoso de " negación como fracaso " porque para una meta G era posible decir: "si el intento de lograr G falla exhaustivamente, entonces afirma (No G) ".
La génesis de Prolog
Gerry Sussman , Eugene Charniak , Seymour Papert y Terry Winograd visitaron la Universidad de Edimburgo en 1971, difundiendo noticias sobre Micro-Planner y SHRDLU y poniendo en duda el enfoque del procedimiento de prueba uniforme de resolución que había sido el pilar de los lógicos de Edimburgo. En la Universidad de Edimburgo, Bruce Anderson implementó un subconjunto de Micro-Planner llamado PICO-PLANNER, [9] y Julian Davies (1973) implementó esencialmente todo Planner.
Según Donald MacKenzie, Pat Hayes recordó el impacto de una visita de Papert a Edimburgo, que se había convertido en el "corazón de Logicland de la inteligencia artificial ", según el colega de Papert en el MIT, Carl Hewitt. Papert expresó elocuentemente su crítica del enfoque de resolución dominante en Edimburgo "...y al menos una persona tomó medidas y se fue por culpa de Papert". [10]
Los acontecimientos anteriores generaron tensión entre los lógicos de Edimburgo. Estas tensiones se exacerbaron cuando el Consejo de Investigación Científica del Reino Unido encargó a Sir James Lighthill que escribiera un informe sobre la situación de la investigación de la IA en el Reino Unido. El informe resultante [ Lighthill 1973; McCarthy 1973] fue muy crítico aunque SHRDLU fue mencionado favorablemente.
Pat Hayes visitó Stanford donde conoció Planner. Cuando regresó a Edimburgo, intentó influir en su amigo Bob Kowalski para que tuviera en cuenta a Planner en su trabajo conjunto sobre la demostración automatizada de teoremas. "La demostración del teorema de resolución fue degradada de un tema candente a una reliquia del pasado equivocado. Bob Kowalski se mantuvo obstinadamente en su fe en el potencial de la demostración del teorema de resolución. Estudió cuidadosamente a Planner”. [11] Kowalski [1988] afirma " Recuerdo haber intentado convencer a Hewitt de que Planner era similar a la resolución SL". Pero Planner se inventó con el propósito de incorporar conocimientos procedimentalmente y fue un rechazo del paradigma del procedimiento de prueba uniforme de resolución. Colmerauer y Roussel recordaron su reacción al aprendizaje. sobre Planner de la siguiente manera:
"Mientras asistíamos a una convención del IJCAI en septiembre de 1971 con Jean Trudel, nos encontramos nuevamente con Robert Kowalski y escuchamos una conferencia de Terry Winograd sobre el procesamiento del lenguaje natural. El hecho de que no utilizara un formalismo unificado nos dejó perplejos. Fue en ese momento que supimos de la existencia del lenguaje de programación de Carl Hewitt, Planner. La falta de formalización de este lenguaje, nuestro desconocimiento de Lisp y, sobre todo, el hecho de que éramos absolutamente devotos de la lógica hicieron que este trabajo tuviera poca influencia en nuestro posterior. investigación." [12]
En el otoño de 1972, Philippe Roussel implementó un lenguaje llamado Prolog (una abreviatura de PRO grammation en LOG ique – en francés "programación en lógica"). Los programas Prolog tienen genéricamente la siguiente forma (que es un caso especial del encadenamiento hacia atrás en Planner):
- Cuando objetivo Q, objetivo P 1 y ... y objetivo P n
Prolog duplicó los siguientes aspectos de Micro-Planner:
- Invocación dirigida por patrones de procedimientos desde objetivos ( es decir, encadenamiento hacia atrás )
- Una base de datos indexada de procedimientos dirigidos por patrones y sentencias fundamentales.
- Renunciar al paradigma de completitud que había caracterizado el trabajo anterior sobre la demostración de teoremas y reemplazarlo con el paradigma de incorporación procesal del conocimiento del lenguaje de programación.
Prolog también duplicó las siguientes capacidades de Micro-Planner que fueron pragmáticamente útiles para las computadoras de la época porque ahorraron espacio y tiempo:
- Estructura de control de retroceso
- Nombre único Supuesto por el cual se supone que diferentes nombres se refieren a entidades distintas, por ejemplo , se supone que Pekín y Beijing son diferentes.
- Cosificación del fracaso. La forma en que Planner estableció que algo era demostrable fue intentarlo con éxito como meta y la forma en que estableció que algo no era demostrable fue intentarlo como meta y fallar explícitamente. Por supuesto, la otra posibilidad es que el intento de demostrar el objetivo dure para siempre y nunca arroje ningún valor. Planner también tenía una construcción (no expresión) que tenía éxito si la expresión fallaba, lo que dio lugar a la terminología de " Negación como fracaso " en Planner.
El uso de la asunción y negación del nombre único como fracaso se volvió más cuestionable cuando la atención se centró en los sistemas abiertos. [13]
Las siguientes capacidades de Micro-Planner se omitieron de Prolog:
- Invocación dirigida por patrones de planes de procedimiento a partir de afirmaciones ( es decir , encadenamiento directo )
- Negación lógica, por ejemplo , (no (Sócrates humano)) .
Prolog no incluyó la negación en parte porque plantea problemas de implementación. Considere, por ejemplo, si la negación se incluyera en el siguiente programa Prolog:
- no q.
- P:- P.
El programa anterior no podría demostrar que no es P aunque siga las reglas de la lógica matemática. Esto es una ilustración del hecho de que Prolog (al igual que Planner) pretende ser un lenguaje de programación y por lo tanto no prueba (por sí solo) muchas de las consecuencias lógicas que se derivan de una lectura declarativa de sus programas.
El trabajo en Prolog fue valioso porque era mucho más simple que Planner. Sin embargo, a medida que surgió la necesidad de un mayor poder expresivo en el lenguaje, Prolog comenzó a incluir muchas de las capacidades de Planner que quedaron fuera de la versión original de Prolog.
Referencias
- ^ Carl Hewitt Historia media de la programación lógica: resolución, planificador, prólogo y el proyecto japonés de quinta generación ArXiv 2009. arXiv :0904.3036
- ^ McCarthy y col. 1962
- ^ Robinson 1965
- ^ Verde 1969
- ^ Hewitt 1971
- ^ Robinson 1965
- ^ Sussman, Charniak y Winograd 1971
- ^ Golomb y Baumert 1965
- ^ Anderson 1972
- ^ MacKenzie 2001 pág.82.
- ^ Bruynooghe, Pereira, Siekmann y van Emden [2004]
- ^ Colmerauer y Roussel 1996
- ^ Hewitt y de Jong 1983, Hewitt 1985, Hewitt e Inman 1991
Bibliografía
- BruceAnderson. Documentación para la Escuela de Inteligencia Artificial LIB PICO-PLANNER, Universidad de Edimburgo. 1972
- Bruce Baumgart. Manual de referencia alternativo de Micro-Planner Nota operativa n.º 67 del Laboratorio de IA de Stanford, abril de 1972.
- Coles, Steven (1975), "La aplicación de la inteligencia artificial al modelado heurístico", 2.ª conferencia informática entre Estados Unidos y Japón.
- Fikes, Richard (1975), Mecanismos de recuperación deductivos para modelos de descripción de estados , IJCAI.
- Fitch, Frederic (1952), Lógica simbólica: una introducción , Nueva York: Ronald Press.
- Green, Cordell (1969), "Aplicación de la demostración de teoremas a la resolución de problemas", IJCAI.
- Hewitt, Carl (1969). "PLANNER: un lenguaje para demostrar teoremas en robots". IJCAI . CiteSeerX 10.1.1.80.756 .
- Hewitt, Carl (1971), "Incorporación procesal del conocimiento en el planificador", IJCAI.
- Carl Hewitt. "El Reto de los Sistemas Abiertos" Revista Byte. abril de 1985
- Carl Hewitt y Jeff Inman. "DAI entre y entre sí: de 'agentes inteligentes' a la ciencia de sistemas abiertos" Transacciones IEEE sobre sistemas, hombre y cibernética. Noviembre/diciembre de 1991.
- Carl Hewitt y Gul Agha. "Lenguajes de cláusulas de Cuerno Guardado: ¿son deductivos y lógicos?" Conferencia internacional sobre sistemas informáticos de quinta generación, Ohmsha 1988. Tokio. También en Inteligencia Artificial en el MIT , vol. 2. Prensa del MIT 1991.
- Hewitt, Carl (marzo de 2006), La repetida desaparición de la programación lógica y por qué se reencarnará: qué salió mal y por qué: lecciones de la investigación y las aplicaciones de la IA (PDF) , Informe técnico, AAAI Press, archivado desde el original (PDF) el 2017-12-10.
- William Kornfeld y Carl Hewitt. La metáfora de la comunidad científica MIT AI Memo 641. Enero de 1981.
- Bill Kornfeld y Carl Hewitt. "La metáfora de la comunidad científica" Transacciones IEEE sobre sistemas, el hombre y la cibernética. Enero de 1981.
- Bill Kornfeld. "El uso del paralelismo para implementar una búsqueda heurística" IJCAI 1981.
- Bill Kornfeld. "Paralelismo en la resolución de problemas" Tesis doctoral del MIT EECS. Agosto de 1981.
- Bill Kornfeld. "Algoritmos combinatoriamente implosivo" CACM. mil novecientos ochenta y dos
- Roberto Kowalski. "Las limitaciones de la lógica" Actas de la decimocuarta conferencia anual de la ACM de 1986 sobre informática.
- Roberto Kowalski. "Los primeros años de la programación lógica" CACM, enero de 1988.
- Latombe, Jean-Claude (1976), "Inteligencia artificial en diseño asistido por ordenador", CAD Systems , Holanda Septentrional.
- McCarthy, John; Abrahams, Pablo; Edwards, Daniel; Hart, Timoteo; Levin, Michael (1962), Manual del programador Lisp 1.5 , Centro de Computación y Laboratorio de Investigación en Electrónica del MIT.
- Robinson, John Alan (1965), "Una lógica orientada a máquinas basada en el principio de resolución", Communications of the ACM , 12 : 23–41, doi : 10.1145/321250.321253.
- Gerry Sussman y Terry Winograd. Manual de referencia del microplanificador AI Memo No, 203, Proyecto MAC del MIT, julio de 1970.
- Terry Winograd. Procedimientos como representación de datos en un programa informático para la comprensión del lenguaje natural MIT AI TR-235. Enero de 1971.
- Gerry Sussman, Terry Winograd y Eugene Charniak. Manual de referencia de Micro-Planner (actualización) AI Memo 203A, MIT AI Lab, diciembre de 1971.
- Carl Hewitt. Descripción y análisis teórico (mediante esquemas) de Planner, un lenguaje para demostrar teoremas y manipular modelos en un robot AI Memo No. 251, Proyecto MAC del MIT, abril de 1972.
- Eugenio Charniak. Hacia un modelo de comprensión de cuentos infantiles MIT AI TR-266. Diciembre de 1972.
- Julián Davies. Popler 1.6 Reference Manual Universidad de Edimburgo, Informe TPU No. 1, mayo de 1973.
- Jeff Rulifson, Jan Derksen y Richard Waldinger. "QA4, un cálculo procesal para el razonamiento intuitivo" Nota técnica 73 del SRI AI Center, noviembre de 1973.
- Scott Fahlman. "Un sistema de planificación para tareas de construcción de robots" MIT AI TR-283. junio de 1973
- James Lighthill. "Inteligencia artificial: un estudio general Inteligencia artificial: un simposio de artículos". Consejo de Investigación Científica del Reino Unido. 1973.
- John McCarthy. "Revisión de 'Inteligencia artificial: un estudio general sobre inteligencia artificial: un simposio de artículos". Consejo de Investigación Científica del Reino Unido. 1973.
- Robert Kowalski "La lógica de predicados como lenguaje de programación" Memo 70, Departamento de Inteligencia Artificial, Universidad de Edimburgo. 1973
- Pat Hayes. Fundamentos matemáticos de computación y deducción de la informática: actas del simposio y escuela de verano, Štrbské Pleso, Altos Tatras, Checoslovaquia, 3 al 8 de septiembre de 1973.
- Carl Hewitt, Peter Bishop y Richard Steiger. "Un formalismo de actor modular universal para la inteligencia artificial" IJCAI 1973.
- L. Thorne McCarty. "Reflexiones sobre TAXMAN: un experimento sobre inteligencia artificial y razonamiento jurídico" Harvard Law Review. vol. 90, núm. 5, marzo de 1977
- Drew McDermott y Gerry Sussman. El manual de referencia de Conniver MIT AI Memo 259A. Enero de 1974.
- Earl Sacerdoti, et al., "QLISP Un lenguaje para el desarrollo interactivo de sistemas complejos" AFIPS. 1976
- Sacerdoti, Earl (1977), Una estructura para los planes y el comportamiento , Elsevier Holanda Septentrional.
- Waldinger, Richard; Levitt, Karl (1974), Razonamiento sobre programas de inteligencia artificial.
enlaces externos
- Relato de 1992 de Alain Colmerauer y Philippe Roussel sobre el nacimiento de Prolog en Wayback Machine (archivado el 27 de julio de 2003)