Scheme
Scheme es un lenguaje de programación funcional (si bien impuro pues sus estructuras de datos no son inmutables) y un dialecto de Lisp. Fue desarrollado por Guy L. Steele y Gerald Jay Sussman en la década de los setenta e introducido en el mundo académico a través de una serie de artículos conocidos como los Lambda Papers de Sussman y Steele.
| Scheme | ||
|---|---|---|
| ? | ||
| Información general | ||
| Extensiones comunes | scm y ss | |
| Paradigma | multi-paradigma | |
| Apareció en | 1975 | |
| Diseñado por | Guy L. Steele y Gerald Jay Sussman | |
| Sistema de tipos | Fuerte, dinámico | |
| Implementaciones | Scheme, Scheme 48, Chicken, Gambit, FLUENT, Guile, Bigloo, Chez Scheme, STk, STklos, Larceny, SCM | |
| Dialectos | T | |
| Influido por | Lisp | |
La filosofía de Scheme es minimalista. Su objetivo no es acumular un gran número de funcionalidades, sino evitar las debilidades y restricciones que hacen necesaria su adición. Así, Scheme proporciona el mínimo número posible de nociones primitivas, construyendo todo lo demás a partir de un reducido número de abstracciones. Por ejemplo, el mecanismo principal para el control de flujo son las llamadas recursivas.
Scheme fue el primer dialecto de Lisp que usó ámbito estático, también conocido como ámbito léxico, (en lugar de dinámico) de forma exclusiva. También fue uno de los primeros lenguajes de programación con continuaciones explícitas, un mecanismo para guardar y usar el estado entero de un programa en un momento determinado. Scheme ofrece también gestión automática de memoria (recolección de basura).
Las listas son la estructura de datos básica del lenguaje, que también ofrece arrays entre sus tipos predefinidos. Debido a su especificación minimalista, no hay sintaxis explícita para crear registros o estructuras, o para programación orientada a objetos, pero muchas implementaciones ofrecen dichas funcionalidades.
Scheme se llamaba originalmente "Schemer", siguiendo la tradición de los lenguajes Planner y Conniver. Su nombre actual es debido a que sus autores usaban el sistema operativo ITS, que limitaba la longitud de los nombres de fichero a 6 caracteres.
Ventajas de Scheme
Scheme, como todos los dialectos de Lisp, tiene una sintaxis muy reducida comparado con muchos otros lenguajes. No necesita reglas de precedencia en su gramática, ya que usa notación prefija para todas las llamadas a función. En el mundo de Lisp tales expresiones son conocidas como S-expressions.
El poder característico de los Lisp reside en la simpleza de su sintaxis homoicónica hecha de listas anidadas, que refleja la estructura del árbol de sintaxis abstracta del programa y lo pone a disposición del programador. Esto facilita la metaprogramación mediante macros. Las macros de Scheme permiten adaptarlo a nuevos dominios con facilidad, por ejemplo, para añadir soporte a la programación orientada a objetos. Existe por ejemplo una extensión que implementa un sistema de objetos escrito en menos de mil líneas de código de Scheme, incluyendo comentarios.[1] Scheme proporciona un sistema de macros higiénico que, aunque no tan potente como el de Common Lisp, es mucho más seguro y, con frecuencia, sencillo de utilizar. La ventaja de un sistema de macros de este tipo (que también se encuentra en otros lenguajes, como Dylan) es que evita automáticamente colisiones entre los nombres usados en la definición de la macro y en el contexto en que ésta se expande. En contrapartida, las macros higiénicas no pueden introducir nuevos símbolos.
Scheme facilita la programación funcional. Aunque Scheme es impuro porque permite la asignación destructiva, usarlo al estilo de la programación funcional pura evita variables globales y sufrir de efectos secundarios, haciéndolo más seguro en presencia de procesos concurrentes (thread-safe), amén de facilitar considerablemente la verificación de programas, al menos en comparación con el estilo imperativo.
En Scheme, los procedimientos o funciones son objetos de primera clase. Ello permite la definición de funciones de orden superior; funciones que reciben o devuelven otras funciones, que facilitan un mayor grado de abstracción en los programas. También es posible la creación de procedimientos anónimos (literales) mediante el primitivo (lambda (arg1 ...) (...)).
El estándar de Scheme es también minimalista. Ello conlleva ventajas e inconvenientes. Por ejemplo, escribir un compilador o intérprete de Scheme que sea fiel al estándar es más fácil que implementar uno de Common Lisp; empotrar Lisp en dispositivos con poca memoria será también más factible si usamos Scheme en lugar de Common Lisp. A los aficionados a Scheme les divierte mucho señalar que su estándar, con sólo 50 páginas, es más corto que el índice del libro de Guy Steele Common Lisp: The Language.
Desventajas de Scheme
El estándar de Scheme es realmente minimalista y específico en sí. Ello provoca que existan multitud de implementaciones diferentes, cada una de las cuales introduce extensiones y bibliotecas propias que las hace incompatibles entre sí. Los Scheme Requests for Implementation (SRFI) tratan de poner remedio a este problema.
Hay quien ve el hecho de que los procedimientos y variables compartan el mismo espacio de nombres como una desventaja, ya que algunas funciones tienen nombres que son de uso común para variables. Por ejemplo, list es el nombre de un procedimiento, así que es muy habitual ver lst o xs como nombres de variables, en lugar de "list".
Como hemos dicho, el espacio de nombres es único (Scheme es un LISP-1) y, por tanto, también incluye a las macros. Ello hace imposible distinguir el uso de una macro del de una función, así que, si no consultamos la definición de cada uno de los objetos usados, no será en general posible determinar el orden de evaluación en programas con los que no estemos familiarizados.
Estándares
Existen dos estándares que definen el lenguaje de programación Scheme: el de la IEEE, y un estándar de facto conocido como Revisedn-th Report on the Algorithmic Language Scheme, casi siempre abreviado como RnRS, donde n es el número de la revisión. El último RnRS es R6RS, y está displonible en línea.
Elementos del lenguaje
Comentarios
Para agregar un comentario en Scheme se inicia con un punto y coma (;) y continúan hasta el final de la línea.
Variables
Las variables son dinámicamente tipadas. Para asociarlas a un valor concreto, podemos usar define, una expresión let, o alguna de sus variantes. Las variables asignadas en el primer nivel usando define están en ámbito global (es decir, son visibles en el resto de programa).
(define var1 value) Las variables asignadas mediante let ven su ámbito reducido al cuerpo de dicho let:
(let ((var1 value)) ... ámbito de var1 ...) Procedimientos
Las funciones o procedimientos son objetos de primera clase en Scheme. Pueden ser asignados a variables. Por ejemplo, una función de dos argumentos arg1 y arg2 puede definirse como:
(define fun (lambda (arg1 arg2) ...)) o en la forma abreviada equivalente:
(define (fun arg1 arg2) ...) Las llamadas a función tienen la sintaxis siguiente:
(fun value1 value2) Como vemos, la función invocada se encuentra en primer lugar, seguida de los argumentos de la llamada, formando una lista. Podemos también utilizar el procedimiento apply, que toma dos argumentos: el primero es el procedimiento que queremos invocar, mientras que el segundo es la lista de argumentos. Así, la anterior llamada a función puede escribirse, de forma equivalente, como:
(apply fun (list value1 value2)) En Scheme, las funciones se dividen, básicamente, en dos categorías: los procedimientos definidos por el usuario y las primitivas. Las primitivas están pre-definidas en el lenguaje, e incluyen +, -, *, /, set!, car, cdr, y otros procedimientos básicos. Muchas implementaciones permiten al usuario redefinir algunas primitivas. Por ejemplo, el siguiente código:
(define + (lambda (x y) (- x y))) convierte la primitiva + en un procedimiento definido por el usuario que resta sus dos argumentos en lugar de sumarlos.
Listas
Scheme usa listas enlazadas de forma análoga a otros dialectos de Lisp.
Téngase en cuenta que la utilización de listas es mucho más sencilla que en otros lenguajes de programación tales como C, C++ y Pascal.
Tipos de datos
Otros tipos de datos en Scheme son los enteros, racionales, reales, complejos, símbolos, cadenas, y puertos, listas asociativas, tablas hash, vectores, arrays y estructuras.
La mayoría de implementaciones proporciona lo que se conoce como una torre numérica completa, así como aritmética exacta e inexacta.
Los valores booleanos se representan mediante los símbolos #t y #f. En realidad, cualquier valor distinto de #f (incluyendo la lista vacía) se interpreta como 'verdadero' en un contexto adecuado, mientras que en otros dialectos de Lisp la lista vacía es interpretada como el valor booleano falso.
Los símbolos pueden ser definidos de varias maneras, siendo
'symbol (string->symbol "symbol") las más comunes.
Igualdad
Scheme tiene tres tipos diferentes de igualdad:
eq?- Devuelve
#tsi los dos objetos son exactamente el mismo objeto, comprobando incluso dónde están guardados físicamente. eqv?- Normalmente igual que
eq?, pero trata algunos objetos (por ejemplo, caracteres y números) de forma especial para que los números que sean iguales seaneqv?incluso si no soneq?. equal?- Compara el contenido de las estructuras de datos tales como listas, vectores y cadenas para determinar si son iguales.
También existen en Scheme los operadores de equivalencia dependientes del tipo:
string=?- Compara dos cadenas
char=?- Compara dos caracteres
=- Compara números
Estructuras de control
Evaluación condicional
(cond (prueba1 expr1) (prueba2 expr2) ... (else exprn)) La primera expresión para la que la prueba resulte ser cierto (cualquier cosa salvo #f cuenta como cierto) será evaluada. Si todas las pruebas resultan ser #f, se evalúa la cláusula else.
Una variante de la cláusula cond es:
(cond... (test => expr) ...) En este caso, expr debe resultar en una función que toma un solo argumento. Si test resulta ser cierto, se llama a la función anterior con el valor devuelto por test.
Scheme también tiene:
(if test then-expr else-expr) pero se usa mucho menos porque cond es más general y normalmente resulta más legible.
Bucles
Los bucles en Scheme suelen tomar la forma de una recursión final o tail recursion en inglés. Este tipo de recursión es preferido porque dispensa la acumulación de tramas en la pila de llamadas y su subsecuente desbordamiento. El estándar exige a las implementaciones optimizar llamadas en posición de recursión final para generar código equivalente a un ciclo en lenguajes imperativos. Un ejemplo clásico es la función factorial, que puede definirse sin recursión final como:
(define (factorial n) (cond ((= n 0) 1) (else (* n (factorial (- n 1)))))) (factorial 5) ;; => 120 O con recursión final usando un procedimiento extra:
(define (factorial n) (fact-iter 1 n)) (define (fact-iter product n) (if (< n 2) product (fact-iter (* product n) (- n 1)))) (factorial 5) ;; => 120 Otra forma típica de bucle es una función de orden superior como map, que aplica una función a cada elemento de una lista, puede también definirse sin recursión final de la siguiente forma:
(define (map f lst) (cond ((null? lst) lst) (else (cons (f (car lst)) (map f (cdr lst)))))) (map (lambda (x) (* x x)) '(1 2 3 4)) ;; => (1 4 9 16) Podemos definir ambas usando la recursión final como sigue. La expresión let con nombre y la sentencia do son azúcar sintáctica que simplifica las definiciones con recursión final.
(define (factorial n) (let loop ((fact 1) (n n)) (cond ((= n 0) fact) (else (loop (* n fact) (- n 1)))))) (factorial 5) ;; => 120 (define (map f lst) (do ((lst lst (cdr lst)) (res '() (cons (f (car lst)) res))) ((null? lst) (reverse res)))) (map (lambda (x) (* x x)) '(1 2 3 4)) ;; => (1 4 9 16) Adviértase que en ambos casos se prefiere la versión con recursión final debido a su menor uso de espacio.
Entrada/salida
Scheme tiene el concepto de puertos de donde leer o a los que escribir. Scheme define tres puertos por defecto, accesibles con las funciones current-input-port, current-output-port y current-error-port.
Véase también
- Lisp
- Common Lisp
- Modelo de actor
- Guy L. Steele, Jr.
- Gerald Jay Sussman