PDF de programación - Lisp - Herramientas para la programación Simbólica

Herramientas para la

programación Simbólica

Dr. Luis Alberto Pineda Cortés

Scheme: dialecto de Lisp

• Expresiones simples

– Literales, llamadas a procedimientos y variables

– Definiciones, programas y ciclo lee-evalúa-imprime

– Evaluación condicional

• Tipos de datos

– Números, boleanos, caracteres, cadenas y símbolos

– Listas

– Pares

– Vectores

• Procedimientos

– Expresiones lambda

– Procedimientos de primer orden

– Procedimientos con aridad variable

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Scheme: dialecto de Lisp

• Expresiones simples

– Literales, llamadas a procedimientos y variables

– Definiciones, programas y ciclo lee-evalúa-imprime

– Evaluación condicional

• Tipos de datos

– Números, boleanos, caracteres, cadenas y símbolos

– Listas

– Pares

– Vectores

• Procedimientos

– Expresiones lambda

– Procedimientos de primer orden

– Procedimientos con aridad variable

Expresiones simples

• Enunciados (statement):
– se avalúan por sus efectos

– asignaciones, input-output, control

• Expresiones

– Su evaluación “regresa” valores

– funciones: no hay efectos colaterales a la evaluación

• Scheme

– Lenguaje funcional

– No hay distinción entre “procedimientos” y funciones

– Construcciones: definiciones y expresiones

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Scheme: dialecto de Lisp

• Expresiones simples

– Literales, llamadas a procedimientos y variables

– Definiciones, programas y ciclo lee-evalúa-imprime

– Evaluación condicional

• Tipos de datos

– Números, boleanos, caracteres, cadenas y símbolos

– Listas

– Pares

– Vectores

• Procedimientos

– Expresiones lambda

– Procedimientos de primer orden

– Procedimientos con aridad variable

Literales, llamadas a procedimientos y variables

• Literales o constantes

– Símbolos y numerales: objetos representacionales (sintácticos)

– valores expresados: objetos representados (semántica)

– Ejemplo: evalua el numeral 2

• valor el número dos: 2 (en itálicas en el texto)

• representación externa: “2”

• Variables (permiten introducir abstracción)

– Son expresiones (identificadores: x, x3, foo, londid, +, /, zero?, etc.)

– Tienen valor o denotan un objeto (valores denotados).

– Pueden ser ligadas (bound to) y denotan valor de su “binding”.

•

Identificadores
– Keywords: define, if

– Procedimientos estándar: +, add, zero?

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

1

Literales, llamadas a procedimientos y variables

• Sintaxis

– (operador operando-1 ... operando-2)

– tanto operandos como operadores son expresiones

– la evaluación de operadores “regresa” procedimientos

– la evaluación de operandos “regresa” argumentos o parámetros

– el orden de evaluación de operandos no se especifica en Scheme

– ejemplos:
• (+ 2 3)

valor: 5

• (+ x (p 2 3))

valor: 9 is x vale 3 y p es el producto

• ((g 2) 3 4)

valor: 7 si (g 2) es la suma

Scheme: dialecto de Lisp

• Expresiones simples

– Literales, llamadas a procedimientos y variables

– Definiciones, programas y ciclo lee-evalúa-imprime

– Evaluación condicional

• Tipos de datos

– Números, boleanos, caracteres, cadenas y símbolos

– Listas

– Pares

– Vectores

• Procedimientos

– Expresiones lambda

– Procedimientos de primer orden

– Procedimientos con aridad variable

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Definiciones y programas

Ciclo lee-evalúa-imprime

• Un programa en Scheme consiste de:

– Definiciones

– expresiones

• Definiciones

– (define variable expresión)

– keywords tienen una secuencia de evaluación pre-establecida

– define: la expresión se evalúa primero y después el valor se liga a la

variable

• Ciclo lee-evalúa-imprime

• > 3

• 3

• > *

; el valor es el procedimiento de multiplicación

• #<procedure>

• > (* 2 3)

• 6

• > (define x 3)

• > x

• 3

• > (+ x (* 2 3))

• 9

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Scheme: dialecto de Lisp

• Expresiones simples

– Literales, llamadas a procedimientos y variables

– Definiciones, programas y ciclo lee-evalúa-imprime

– Evaluación condicional

• Tipos de datos

– Números, boleanos, caracteres, cadenas y símbolos

– Listas

– Pares

– Vectores

• Procedimientos

– Expresiones lambda

– Procedimientos de primer orden

– Procedimientos con aridad variable

Evaluación condicional

• Condicional (definición)

– (if test-exp then-exp else-exp)

– Si test-esp es verdad evalúa then-exp si es falso evalúa else-exp

• Ejemplo:

• > (if #t 1 2)

• 1

• > (zero? 5)

• #f

> (define false #f)

> (if (zero? 0) (if false 1 2) 3)

2

> (if (if true false true) 2 3)

• > (if (zero? 5) 1 (+ 1 2))

3

• 3

• > (define true #t)

• Guardias (secuencia de evaluación de if)

– (if (zero? a) 0 (/ x a))

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

2

Scheme: dialecto de Lisp

Tipos de datos

• Expresiones simples

– Literales, llamadas a procedimientos y variables

– Definiciones, programas y ciclo lee-evalúa-imprime

– Evaluación condicional

• Tipos de datos

– Números, boleanos, caracteres, cadenas y símbolos

– Listas

– Pares

– Vectores

• Procedimientos

– Expresiones lambda

– Procedimientos de primer orden

– Procedimientos con aridad variable

• Consideraciones para los tipos de datos

– El conjunto de valores del tipo de dato

– Los procedimientos que operan en el tipo de dato

– Las representaciones “internas” de los tipos de datos (como

literales) o “externas” como caracteres impresos

• Verificación del tipo de datos (type cheking)

– Verificación dinámica en tiempo de ejecución (Scheme)

– Verificación estática (en tiempo de compilación)

• Los errores se detectan antes y la ejecución es más eficiente

• Menos expresividad y complejidad del compilador

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Scheme: dialecto de Lisp

Números y boleanos

• Expresiones simples

– Literales, llamadas a procedimientos y variables

– Definiciones, programas y ciclo lee-evalúa-imprime

– Evaluación condicional

• Tipos de datos

– Números, boleanos, caracteres, cadenas y símbolos

– Listas

– Pares

– Vectores

• Procedimientos

– Expresiones lambda

– Procedimientos de primer orden

– Procedimientos con aridad variable

• Tipo númerico

– Valores: los números naturales (incluyendo el cero)

– Operaciones: +, -, *, /

– Predicados: number?, =

• Tipo boleano

– Valores: {#t, #f}

– Operaciones: se usan en condicionales

– Predicados: boolean?, eq?

– Ejemplos:

• > (eq? (boolean? #f) (not #f))

• #t

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Caracteres

• Tipo carácter (character)

– Valores: representación interna (e.g., ascii)

– Representación externa precediendo con “#\”

• (e.g., #\a, #\%, #\space, #\newline)

– Operadores: char-> integer

– Predicados: char?, char=?, char<?, char-alphabetic?, char-

numeric?, char-whitespace?

– Ejemplos:

• > (char? #\$)

• #t

• > (char=? #\space, #\newline)

• #f

• > (char<? #\a #\b)

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Cadenas

• Tipo cadena (string)

– Valores: secuencia de caracteres (e.g., ascii)

– Operadores: string-length, string-append, string->symbol, string-
>number, string->list, string (transf. secuencia de caracteres en una
cadena), string-ref (string e indice a caracter)

– Predicados: string?

– Ejemplos:

• > (define s “This is a.”)

> (string \#a \#b)

• > (define ss (string-append s “longer string”) > “ab”

• > (string? s)

• > #t

• > (string-length ss)

• > 23

• > (string-ref s 2)

• > #\i

> (string->symbol “abc”)

> abc

> (string->list s)

> (\#T \#h \#i \#s \#space ... \#.)

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

3

Símbolos o Indentificador (nombres de variable)

• Cual es la diferencia entre “luis” y luis en el discurso normal?

– prevenir la evaluación de símbols: (quote datum) o ’datum

• > (define x 3)

• > x

• > 3

• > (quote x)

• > x

> 99

> 99

> (quote 99)

> 99

– predicados: symbol?, eq?

• > (define x 3)

• > (number? x)

• > #\t

> (symbol ’x)

> \#t

> (eq? ’x ’x)

• > (symbol? x)

> \#t

• > \#f

> (eq? ’x ’y)

• > (number? ’x)

> \#f

• > \#f

>(define y ’apple)

> y

> apple

> (eq? y (quote apple))

>\#t

> (eq? y ’y)

> \#f

Scheme: dialecto de Lisp

• Expresiones simples

– Literales, llamadas a procedimientos y variables

– Definiciones, programas y ciclo lee-evalúa-imprime

– Evaluación condicional

• Tipos de datos

– Números, boleanos, caracteres, cadenas y símbolos

– Listas

– Pares

– Vectores

• Procedimientos

– Expresiones lambda

– Procedimientos de primer orden

– Procedimientos con aridad variable

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Listas

Listas

• Secuencia ordenada de elementos de tipos arbitrarios

– Ejemplos:
• (a 3 #3)

()

(a)

((b c d))

• Prevenir confusión entre listas y llamadas a procedimientos

– (quote (a b c) )

versus

(a b c)

• Constructores: list, cons, append

– Ejemplos con “list”

• > (list 1 2 3)

• > (1 2 3)

• > (define x 3)

> (define list-2 ’(a))

> (define list-3 ’((b)))

> (list list-1 list-2 list-3 ’(((c))))

• > (define y ’apple)

> (( ) (a) ((b)) (((c))) )

• > (list x y)

• > (3 apple)

• > (define list-1 ’( ))

> (list)

> ( )

• Constructores: list, cons, append

– Ejemplos con “cons” (cons valor lista) -> lista

• > (cons ’a ’(c d))

> (cons ’a ‘( ))

• > (a c d)

> (a)

> list-4

> ( ( ) a)

• > (list ’a ’(c d))

> (cons ’(a b) ‘( ))

> (cons list-4 list-3)

• > (a (c d))

> ((a b))

> (( ( ) a) (b))

• > (cons ’(a b) ’(c d))

> (define y ’apple)

• > ((a b) c d)

> (cons y list-2)

• > (cons ’( ) ’(c d ))

> (apple a)

• > (( ) c d)

> (define list-4 (cons list-1 list-2))

– Ejemplos con “append”
• > (append ’(a b) ’(c d))

> (append ’(a b) ’( ))

• > (a b c b)

> (a b)

• > (append ’( ) ’(c d))

• > (c d)

Dr. Luis A. Pineda, IIMAS, UNAM, 2000.

Dr. Luis A. Pi