Scheme

Scheme
Paradigma	Multiparadigma: funcional e procedural
Surgido em	1975
Última versão	R6RS (2007)
Criado por	Gerald Jay Sussman e Guy L. Steele, Jr.
Estilo de tipagem	dinâmica, forte
Principais implementações	MIT/GNU Scheme, Chez Scheme, SCM, GNU Guile, Ypsilon, PLT Scheme
Dialetos:	T
Influenciada por	ALGOL, Lisp, MDL
Influenciou	Common Lisp, EuLisp, JavaScript, R, Ruby, Dylan, Lua, Hop, Racket
Extensão do arquivo	.scm, .ss
Página oficial	www.scheme.org

Scheme é uma linguagem de programação multiparadigma que suporta programação funcional e procedural. Foi criada por Guy L. Steele e Gerald Jay Sussman no outono de 1975, a partir da linguagem Lisp com o intuito de estudar a teoria dos atores de Carl Hewitt. O modelo de Hewitt era orientado a objeto (e influenciado pelo Smalltalk). Os objetos eram chamados atores e as mensagens eram também atores. Sussman e Steele tiveram algum problema no entender algumas das consequências do modelo a partir dos artigos de Hewitt e decidiram construir uma implementação de brinquedo de uma linguagem de atores visando experimentá-la. Escreveram um pequeno interpretador Lisp e adicionaram os mecanismos necessários para a criação de atores e envio de mensagens. Existem dois padrões que definem a linguagem Scheme: o padrão oficial IEEE e um padrão popular chamado "Revisedⁿ Report on the Algorithmic Language Scheme", abreviado como RnRS, onde n é o número de revisões.

Scheme é uma linguagem multiparadigma baseado no cálculo lambda. Serão apresentadas as características marcantes e alguns exemplos de códigos, ilustrando sua eficiência. É uma das descendentes da linguagem Lisp, compartilhando a maior parte de sua sintaxe, mas fornece regras léxicas ao invés de regras de escopo dinâmico.

Características

Scheme adota uma filosofia minimalista, assim sendo, provê o mínimo de noções possíveis, e, na prática, qualquer outra noção pode ser adicionada via bibliotecas e, como todos os dialetos do Lisp, possui poucas regras sintáticas comparado à maioria das outras linguagens. Devido à sua sintaxe completamente aninhada, não existem regras de precedência de operadores e sua notação em parênteses é usada para todas as chamadas de função, desta forma não há ambiguidades como as que são encontradas nas linguagens de notação infixa. Porém, em procedimentos que existam muitos fatores a serem abordados, o programa pode ficar visualmente confuso e necessita ser analisado com mais cuidado.

Diferentemente de Common LISP, Scheme é mais simples e fácil de aprender por conter um pequeno grupo de regras e ter a possibilidade de fazer composições dessas regras. Scheme utiliza um sistema de recursão denominado recursão de cauda, que traduz código recursivo em iterativo, otimizando a execução. A linguagem foi inicialmente criada para fins industriais, uma vez que é fácil de aprender e extremamente poderosa.

Exemplos:

(5 3)   seria assim:  (  5 3)
(5 3)*2 seria assim:  (* (  5 3) 2)
(8/2)   seria assim:  (/ 8 2)

Exemplo de um procedimento composto:

((lambda (x) (  x x)) (* 3 4))

neste caso:

3*4 = 12;
x = 12;
x   x = 12   12 = 24;

Algumas notações da Linguagem

• . -: são usados em números e podem ocorrer em qualquer lugar, exceto como primeiro caracter
• (): parenteses são utilizados para agrupar e listas de dados
• ,: sozinho, é utilizado para indicar dados literais
• `: serve para indicar quase todos dados constantes
• ": delimitador de strings
• #t #f: constantes boleanas
• #\: serve para introduzir um caracter constante
• #e #i #o #d #x: utilizados na notação de números

História

O início da linguagem Scheme se deu entre os anos de 1975 e 1980, quando foi realizada a sua primeira descrição no Laboratório de Inteligência Artificial e Ciência da Computação do MIT, Massachusetts Institute of Technology. 1 Foi criada por Guy Steele e Gerald Sussman a partir da linguagem Lisp com o intuito de estudar a teoria dos atores de Carl Hewitt. 2 Sussman e Steele tiveram alguma dificuldade para entender alguns detalhes do modelo de Hewitt e suas consequências, então decidiram construir uma implementação de brinquedo de uma linguagem de atores visando experimentá-la. Escreveram um pequeno interpretador Lisp e adicionaram os mecanismos necessários para a criação de atores e envio de mensagens, surgindo então a linguagem Scheme, que inicialmente se chamaria Schemer, seguindo a tradição das linguagens Planner e Conniver, mas o sistema operacional usado na época, Incompatible Timesharing System (ITS) que foi desenvolvido principalmente pelo Laboratório de Inteligência Artificial do MIT, tinha uma limitação de seis caracteres para o nome dos arquivos, assim Schemer se tornou Scheme, Planner se tornou PLNR e Conniver se tornou CNVR.

Scheme é uma linguagem de programação multiparadigma que suporta programação funcional e procedural. (Ver seção Paradigma).

Em 1978, foi divulgado o primeiro relatório revisado Scheme 78, descrevendo a evolução da linguagem e posterior implementação a partir do inovador compilador Rabbit, no MIT. Como o Scheme começou a se espalhar, dialetos locais começaram a surgir, havendo divergências de implementação entre um lugar e outro. Para sanar os problemas e padronizar a implementação do Scheme, os cinquenta representantes das maiores implementações do Scheme fizeram uma conferência em outubro de 1984. E em 1985, foi divulgado e disponibilizado o "Revised n Report on the Algorithmic Language Scheme" (RnRS) da conferência citada anteriormente pelo MIT e pela Indiana University.

A linguagem é definida por dois padrões: o padrão oficializado em 1998 pelo Instituto de Engenheiros Elétricos e Eletrônicos (IEEE) 5 e o padrão popular chamado "Revised n Report on the Algorithmic Language Scheme", abreviado como RnRS, onde n é o número de revisões realizadas. 6

Em 1986, houve outra revisão da linguagem, R3RS. Em 1998, foi padronizado o R5RS, que ainda é bastante utilizado, assim como o relatório R4RS, e em 2007, foi realizado o último relatório da linguagem que é o R6RS.

É usada nas disciplinas introdutórias à programação, pois o alto nível de abstração ajuda na compreensão e aprendizado, como por exemplo, já foi trabalhada na disciplina de Introdução à Ciência da Computação (ICC) na Pontifícia Universidade Católica do Rio de Janeiro (PUC-RIO), onde são apresentados os conceitos fundamentais de programação.

Paradigma

Como citado anteriormente, Scheme é uma linguagem de programação multiparadigma que suporta programação funcional e procedural.

O paradigma funcional é um paradigma de programação que trata a computação como uma avaliação de funções matemáticas, ele evita estados mutáveis e enfatiza a aplicação de funções, em contraste da programação imperativa, que enfatiza mudanças no estado do programa.

O paradigma procedural é um paradigma de programação utilizado muitas vezes como sinônimo de programação imperativa, que especifica os passos que o programa deve seguir para atingir um estado esperado, mas o termo procedural indica que se baseia no conceito de chamadas de procedimentos, também conhecidos como rotinas, sub-rotinas ou funções (diferentes das funções matemáticas). Atenta-se que tais procedimentos são similares à avaliação realizada na programação funcional, sendo um conjunto de passos computacionais a serem executados, podendo ser chamado a qualquer hora durante a execução do programa, através de outros procedimentos e até por si mesmo.

Características Marcantes

A estrutura da linguagem consiste de um conjunto de definições de função. Não existe uma estrutura imposta sobre o programa e não há nenhuma função principal. Um programa Scheme é executado através da apresentação de uma expressão para avaliação. Funções e expressões são escritas na forma: (nome_da_função argumento). Esta sintaxe é diferente da sintaxe matemática usual em que o nome da função é movido dentro dos parênteses e os argumentos são separados por espaços em vez de vírgulas. 8

A notação da linguagem é bastante homogênea, pois, basicamente, existe uma única regra para escrever qualquer expressão. Os parênteses permitem o aninhamento de expressões, os operadores são pré-fixados, destacando que para a multiplicação utiliza-se o asterisco (*), como: 5 2, em notação matemática é: ( 5 2) na notação da linguagem; (5-3)x2, em notação matemática é: (*(-5 3) 2) na notação da linguagem. Para as operações de adição,subtração e multiplicação, ao trabalhar com números inteiros, sabe-se que o resultado sempre será outro número inteiro, mas para a operação de divisão, não se pode manter essa relação. Em Scheme, a divisão é representada por: (quotient a b), e a operação de mod é representada por: (remainder a b). 9 No item seguinte, será possível visualizar melhor através dos exemplos. Sobre a sintaxe da linguagem, tudo que é escrito é chamado, genericamente, de expressão S ou apenas expressão. As expressões podem ser classificadas como átomos e listas, sendo que as listas são as estruturas de dados que Scheme utiliza para trabalhar melhor com a criação de dados mais complexos. Por enquanto, átomos podem ser numerais, textos, e símbolos; e uma lista é uma sequência de expressões entre parênteses, separadas por espaços.

Para numerais é preciso utilizar ponto decimal ao invés de vírgula, sendo possível o uso de notação científica para números muito grandes ou muito pequenos. Ao quebrar uma expressão em várias linhas, a quebra de linha é interpretada com espaço, o que é bastante interessante para leitura de expressões mais complexas. Os comentários para Scheme são escritos após um ponto e vírgula, e assim são totalmente ignorados pelo interpretador.

Para cada expressão escrita é associado um valor, geralmente é escrito desta forma para que o interpretador avalie este valor. A cada passo de avaliação, uma parte da expressão é substituída por seu valor, seguindo as regras da linguagem, que precisam ser estudadas de acordo com a expressão a ser escrita.

Para dar nome às coisas, é o utilizado o operador define, que associa a expressão ao valor determinado. O valor definido pode ser usado em qualquer expressão após a execução do define, e assim temos as definições globais. O conjunto de associações de nomes com valores ativos para uma determinada expressão é chamado de ambiente. O operador let permite dar nomes locais a valores, ao contrário do define, os nomes definidos com talo perador são válidos dentro da expressão onde eles são definidos, sem interferir em outras partes do programa. O principal uso do operador let é para simplificar o uso de expressões muito complexas para colocar em evidência sub-expressões comuns.

E para definição de funções, é utilizada a construção do lambda, que atua sobre uma lista com os parâmetros da função e um corpo que calcula o valor da função. Uma vez definida, a função pode ser usada como qualquer outra, basta escrever uma lista com seu nome seguido dos argumentos. Scheme possui tipagem dinâmica, a verificação do tipo do dado é feita em tempo de execução, e é fortemente tipada, pois exige que o tipo do dado de um valor seja do mesmo tipo da variável ao qual este valor será atribuído.

Exemplos de código em Scheme

Programa Olá Mundo

Ver artigo principal: Programa Olá Mundo

(define ola-mundo
  (lambda ()
    (display "Olá, Mundo!")
    (newline)))
(ola-mundo)

ou, simplesmente:

(display "Olá, Mundo!")

Condicionais

(if (teste) (consequencia) (alternativa)) syntax
(if (teste) (consequencia)) syntax

Syntax: (Teste), (consequencia), e (alternativa) podem ser expressões arbitrárias.

Semantica: uma expressão if é validada da seguinte forma: primeiro (teste) é avaliado, se for verdadeiro, então (consequencia) é avaliado e seu valor é retornado. Caso contrário (alternativa) é avaliado e seu valor é retornado. Se o teste não possui (alternativa) especificado, então o resultado da expressão não é especificado.

(if (> 3 2) 'yes 'no)  --> yes
(if (> 2 3) 'yes 'no)  --> no
(if (> 3 2)
(- 3 2)
(  3 2)) --> 1

Recursividade

Cálculo do fatorial de um número:

(define (fatorial n)
  (cond ((= n 0)  1)
    (else (* n (fatorial (- n 1))))))

(fatorial 5)
;; => 120

Números Perfeitos

Exemplo de programa que mostra os n primeiros números perfeitos:

 (define inverteListax
  (lambda (lista1 lista2)
    (if (null? lista1) lista2
        (inverteListax (cdr lista1) (cons (car lista1) lista2)))))

 (define inverteLista
   (lambda (lista)
     (inverteListax lista '())))

 (define (perf n)
    (let loop ((i 1)
                (sum 0))
       (cond ((= i n)
              (= sum n))
             (
                (= 0 (modulo n i))
                (loop (  i 1) (  sum i)))
             (else
              (loop (  i 1) sum)))))

 (define aux
   (lambda (x n l)
     (if (= x 0) l
         (if (perf n) (aux (- x 1) (  n 1) (cons n l))
                      (aux x (  n 1) l)))))

 (define main
   (lambda (x)
     (aux x 1 '())))

 (define perfeitos
   (lambda (n)
     (inverteLista (main n))))

Compiladores

Alguns compiladores de Scheme:

• Bigloo
• Chez Scheme
• Chicken
• Gambit
• Gauche
• Guile
• Ikarus
• JScheme
• Kawa
• Larceny
• MIT/GNU Scheme
• Mosh
• A descontinuada PLT Scheme, absorvida pela Racket
• Pvts
• RScheme
• Scheme 48
• SCM
• SISC
• Stalin
• STk
• STklos
• TinyScheme
• Ypsilon

Ver também

• Lisp

Bibliografia

• DYBVIG, R. Kent (1996). The Scheme Programming Language. Ansi Scheme. Nova Jérsia: Prentice Hall PTR. ISBN 0-13-454646-6 
• ABELSON, Harold; SUSSMAN, Gerald Jay; SUSSMAN Julie (1996). Structure and Interpretation of Computer Programs. New York: McGraw-Hill. ISBN 0-07-000484-6  !CS1 manut: Nomes múltiplos: lista de autores (link)

Ligações externas

• «Sítio oficial» (em inglês) 
• «Schemers» (em inglês). Uma página de referência da linguagem 
• TimeLine