Download Introducción a Scheme

Tema 2: Introducción a Scheme
Sesión 4: Introducción a Scheme (2)
miércoles 16 de febrero de 2011
Referencias
• DrRacket (http://racket-lang.org/)
• A brief tour of DrScheme (http://www.plt-scheme.org/software/drscheme/
tour/)
• Structure and Interpretation of Computer Programs (http://mitpress.mit.edu/
sicp/full-text/book/book.html), Abelson y Sussman, MIT Press 1996 (pp.1-13),
en concreto los capítulos 1.1.1.-1.1.4, 1.1.6 SICP: The elements of
programming: Expressions, Evaluation Combinations, Conditional
Expressions and Predicates, Naming and Environment, Compound
procedures
• Teach yourself Scheme (versión HTML, versión PDF)
• Simply Scheme online
miércoles 16 de febrero de 2011
Más sobre símbolos
- Cuando definimos un identificador (símbolo), queda ligado o asociado (bind) al
resultado de la evaluación de la expresión de la parte derecha del define:
a
b
c
(define a (+ 1 2))
(define b ‘hola)
(define c “pp”)
3
hola
pp
- Una expresión en Scheme puede ser simplemente un símbolo, que Scheme evaluará y
devolverá su valor
- Los nombres de funciones también son símbolos y Scheme también los evalúa:
> a
3
> c
“pp”
sin
+
(define (cuadrado x)
(* x x))
cuadrado
sin
+
proc
miércoles 16 de febrero de 2011
proc
proc
Eval y quote
• Los símbolos son datos primitivos: pueden ligarse a otros símbolos o pasarse
como parámetro
• quote se utiliza para que su argumento no se evalúe (azúcar sintáctico del
lenguaje: tilde ‘)
• eval evalúa los argumentos que se le pasan (lenguaje Pretty Big en
DrRacket). Funcionamiento: eval evalúa el argumento que recibe (siguiendo el
modelo de evaluación de Scheme) y lo devuelve nuevamente evaluado
(define a ‘hola)
(define hola 5)
a --> hola
‘a --> a
(eval ‘a) --> hola
(eval a) --> 5
miércoles 16 de febrero de 2011
hola
a
hola
5
Recursión
No existen los bucles en programación funcional
(define (factorial x)
(if (= x 0)
1
(* x (factorial (- x 1)))))
(define (suma-hasta x)
(if (= 0 x)
0
(+ x (suma-hasta (- x 1)))))
miércoles 16 de febrero de 2011
Ejemplos con cadenas
; Funciones primero y resto de una cadena
(define (primero cad)
(string-ref cad 0))
(define (resto cad)
(substring cad 1 (string-length cad)))
; Función veces: devuelve el número de veces que aparece un caracter en una cadena
(define (veces cad elem)
(cond
((equal? "" cad) 0)
((equal? (primero cad) elem) (+ 1 (veces (resto cad) elem))
(else (veces (resto cad) elem)))))
miércoles 16 de febrero de 2011
Ejemplos con cadenas y caracteres
; Funciones siguiente y anterior de un caracter
(define (siguiente car)
(integer->char (+ 1 (char->integer car))))
(define (anterior car)
(integer->char (- (char->integer car) 1)))
; Función codifica una cadena aplicando siguiente a cada uno de sus caracteres
(define (codifica pal)
(if (equal? "" pal)
""
(string-append (string (siguiente (primero pal)))
(codifica (resto pal)))))
; Función descodifica una cadena aplicando anterior a cada uno de sus caracteres
(define (descodifica pal)
(if (equal? "" pal)
""
(string-append (string (anterior (primero pal)))
(descodifica (resto pal)))))
miércoles 16 de febrero de 2011
Listas: elemento fundamental de Scheme
(list 1 2 3 4)
; list crea una lista
'(1 2 3 4)
; otra forma de definir la misma lista
(car '(1 2 3 4))
; primer elemento de la lista
(cdr '(1 2 3 4))
; resto de la lista
(cons 1 '(2 3 4)) ; devuelve una nueva lista con un nuevo
elemento a su cabeza
(append '(1) '(2 3 4) '(5 6)) ; construye una lista nueva
concatenando
'()
; lista vacía
(cdr '(1))
; devuelve la lista vacía
(null? '(1))
; comprueba si una lista está vacía
‘(hola que tal)
; quote no evalúa los argumentos
(list hola que tal) ; list evalúa sus argumentos
miércoles 16 de febrero de 2011
Programas ejemplo
; Función (lista-hasta x) que devuelve una lista de números 1..x en orden decreciente
(define (lista-hasta x)
(if (= x 0)
'()
(cons x (lista-hasta (- x 1)))))
; Función (potencias-2 x) que devuelve una lista con las potencias de 2 hasta x
(define (potencias-2 x)
(if (= x 0)
'(1)
(append (list (* 2 (car (potencias-2 (- x 1)))))
(potencias-2 (- x 1)))))
miércoles 16 de febrero de 2011
Programas ejemplo
; Función (divisor? x y) que comprueba si un número es divisor de otro
(define (divisor? x y)
(= 0 (remainder y x)))
; Función (filtra-divisores lista x) que devuelve una lista con los números de la lista
original que son divisores de x
(define (filtra-divisores lista x)
(cond
((null? lista) '())
((divisor? (car lista) x) (cons (car lista)
(filtra-divisores (cdr lista) x)))
(else (filtra-divisores (cdr lista) x))))
;Función (divisores-n x n) que devuelve una lista con los divisores de un número n
(define (divisores-n x n)
(filtra-divisores (lista-hasta x) n))
miércoles 16 de febrero de 2011