[ALGORITMOS EM GRAFOS: MAC328]
Página preparada por Paulo
Feofiloff para a disciplina MAC0328 Algoritmos em Grafos, versão 2001.
O endereço original desta página é http://www.ime.usp.br/~pf/mac0328-2001/aulas/cweb.html.
CWEB
"Programming is best regarded as the process of creating works of literature,
which are meant to be read."
- D.E. Knuth, Literate Programming
"If you are in the software industry and do not use CWEB
but your competitors do,
your competitors will soon overtake you--
and you'll miss out on a lot of fun besides."
- D.E. Knuth
O que é CWEB? O CWEB é um software que permite escrever programas C bem documentados, em pequenos pedaços interligados.
De onde vem o sigla? C é o nome da linguagem de programação e WEB significa teia (de pequenos pedaços interligados). O sistema WEB foi criado por Donald Knuth; Silvio Levy adaptou o sistema à linguagem C.
Exemplo? Preparei uma amostra de documentos CWEB. Se você tiver dificuldade em entender a amostra, veja a nota Como ler programas CWEB. [Não envie esses arquivos para a impressora: há cópias em papel de todo o material na pasta 6 da loja de reprografia no bloco B do IME.]
O que isso tem a ver com a teoria dos grafos? Quase nada. Eu só preciso do CWEB para entender os programas de manipulação de grafos do Stanford GraphBase.
Quanto CWEB será preciso aprender? Pouco. Basta aprender a ler um documento CWEB, o que é muito fácil. Mas encorajo todos os alunos a aprender mais que esse mínimo, e a usar CWEB nos projetos de MAC328 e também nos projetos de todas as outras disciplinas que envolvam programação C. Consulte minha página sobre programação letrada.
Arquivos .w, .c, .tex, .dvi
O "código-fonte" de todo programa CWEB fica em um arquivo com sufixo ".w". Tomemos isort.w como exemplo. Esse arquivo será submetido a dois programas diferentes:
- O programa ctangle (to tangle = entrelaçar, embaraçar) transforma isort.w em um arquivo isort.c, que está pronto para ser submetido a um compilador C.
- O programa cweave (to weave = tecer) transforma isort.w em um arquivo isort.tex, que será transformado em um arquivo isort.dvi pelo programa TeX. O arquivo isort.dvi (que pode ser facilmente transformado em isort.ps ou isort.pdf) contém o documento CWEB pronto para sem impresso.
Exercícios
- Escreva um pequeno ensaio criticando meu programa isort.
- Escreva um pequeno ensaio criticando meu programa mdp.
- Faça uma copia do arquivo mdp.w. Em seguida, use um editor do texto para simular o efeito de ctangle sobre o arquivo.
Algumas observações sobre documentação de programas
O CWEB é uma ferramenta que ajuda o programador a escrever programas legíveis e bem documentados. Mas o que é "bem documentado"? Para produzir uma boa documentação, basta fazer o seguinte:
para cada função do seu programa, escreva, de maneira curta, grossa e exata, o que a função faz: diga o que a função recebe, o que devolve, e qual a relação entre as duas coisas.Em outras palavras, escreva um pequeno manual-do- usuário para cada função do seu programa. Exemplo: Digamos que meu programa tem uma função ord que ordena vetores. Digamos que o protótipo da função é
void ord (int a[], int p, int r);Eis uma boa documentação: "A função ord recebe um vetor a[p..r] e rearranja os seus elementos de modo que eles fiquem em ordem crescente, ou seja, de modo que a[p]<=a[p+1]<=...<=a[r]; a função supõe que p<=r."
É muito mais importante dizer o que a função faz de que explicar como ela faz o que faz. Assim, não é obrigatório explicar se ord usa o método heapsort, ou o quicksort, ou outro qualquer, para fazer o serviço.