Você Poderia Ter Inventado Mônadas! [Dan Piponi]

Você Poderia Ter Inventado Mônadas! (E Talvez Já O Tenha)

Table of Contents

• 1. INTRO
• 2. Efeitos Colaterais: Depurando Funções Puras
• 3. Um Contêiner: Funções Multi-Valoradas
• 4. Um Efeito Colateral Mais Complexo: Números Aleatórios
• 5. Mônadas
• 6. Sintaxe da Mônada
• 7. Entrada&Saída
• 8. Teoria das Categorias
• 9. Apêndice: Um Exemplo de Código Completo Usando Números Aleatórios
• 10. META

1 INTRO

Se você ainda não sacou, isto é sobre mônadas como elas aparecem em linguagens de programação funcional pura como Haskell. Elas são fortemente relacionadas com as mônadas da teoria de categorias, mas não são exatamente as mesmas porque Haskell não garante as identidades satisfeitas pelas mônadas categóricas.

Escrever introduções sobre mônadas parecem ter-se tornado uma indústria. Existe uma introdução gentil, uma introdução para programadores Haskell com os dizeres "Não entre em pânico", uma introdução para o "programador Haskell em produção" e infindáveis outras que introduzem mônadas como tudo desde um funtor até um tipo de traje espacial. ¹

Mas todas elas introduzem mônadas como algo esotérico que necessita de explicação. Mas o que quero argumentar é que elas não são esotéricas afinal. De fato, diante de muitos problemas na programação funcional você já foi levado, inexoravelmente, a certas soluções, todas elas exemplos de mônadas. De fato, eu espero conseguir que você invente-as agora se é que já não as inventou. Será então um pequeno passo notar que todas essas soluções são de fato a mesma solução disfarçada. E depois de ler isto, você pode estar em uma posição melhor para entender outros documentos sobre mônadas porque você reconhecerá tudo que vê como algo que já inventou.

Muitos dos problemas que mônadas tentam resolver são relacionados com a questão dos efeitos colaterais. Então nós começaremos com eles. (Note que mônadas te permitem fazer mais que manipular efeitos colaterais, em particular muitos tipos de objetos-contêiner podem ser vistos como mônadas. Algumas das introduções a mônadas creem ser difícil reconciliar estes dois usos distintos das mônadas e concentram-se em apenas um ou outro.)

2 Efeitos Colaterais: Depurando Funções Puras

Numa linguagem imperativa como C++, funções não agem nada parecido com as funções da matemática. Por exemplo, suponha que tenhamos uma função C++ que toma um simples argumento em ponto flutuante e retorna um resultado em ponto flutuante. Superficialmente ela pode parecer uma pequena função matemática mapeando reais em reais, mas uma função C++ pode fazer mais que apenas retornar um número que depende de seus argumentos. Ela pode ler e escrever valores em variáveis globais bem como escrever saída para a tela e receber entrada do usuário. Numa linguagem funcional pura, porém, uma função só pode ler o que é suprido em seus argumentos e a única maneira pela qual ela pode ter um efeito no mundo é mediante o valor que retorna.

Então, considere este problema numa linguagem funcional pura: temos funções f e g que levam float s em float s, mas gostaríamos de modificar estas funções para que também emitam strings para fins de depuração. Em Haskell, f e g podem ter tipos dados por

f,g :: Float -> Float

Como podemos modificar os tipos de f e g para admitirem efeitos colaterais? Bem, realmente não existe escolha afinal. Se gostaríamos de ter f' e g' produzindo strings bem como números de ponto flutuante como saída, então a única forma possível é que estas strings sejam retornadas junto aos números de ponto flutuante. Em outras palavras, precisamos que f' e g' sejam do tipo

f',g' :: Float -> (Float,String)

Podemos desenhar isso diagramaticamente como

  x
  |
+---+
| f'|
+---+
 |  \ 
 |   |
f x  "f was called."

Podemos pensar nelas como 'funções depuráveis'.

Mas suponha agora que gostaríamos de depurar a composição de duas funções desse tipo. Nós poderíamos simplesmente compor nossas funções originais, f e g, para formar f . g. Mas nossas funções depuráveis não são tão imediatadas de se lidar. Nós gostaríamos que as strings retornadas por f' e g' fossem concatenadas numa grande string de depuração ( a de f' após a de g' ). Mas não podemos simplesmente compor f' e g' porque o valor de retorno de g' não é do mesmo tipo que o argumento de f'. Nós poderíamos escrever código num estilo como esse:

let (y,s) = g' x
    (z,t) = f' y in (z,s++t)

Eis a aparência diagramática disso:

     x
     |
   +---+
   | g'|
   +---+
    |   \   
  +---+  | "g was called."
  | f'|  |
  +---+  |
   | \   |
   |  \  |
   |  +----+
   |  | ++ |
   |  +----+
   |     |
f (g x) "g was called.f was called."

Isso é uma trabalheira toda vez que se precisa compor duas funções depuráveis, e se tivermos que implementar esse tipo de serviço de baixo nível ² ao longo de todo o código, seria um porre. O que precisamos é definir uma função de ordem superior para realizar este serviço para nós. Como o problema é que a saída de g' não pode ser simplesmente inserida na entrada de f', precisamos 'melhorar' f'. Então introduziremos uma função `bind` para fazer isso. Em outras palavras, queremos

bind f' :: (Float,String) -> (Float,String)

que implique em

bind :: (Float -> (Float,String)) -> ((Float,String) -> (Float,String))

`bind` deve servir a dois propósitos:

1. aplicar f' na parte correta de g' x, e
2. concatenar a string retirnada por g' com a string retornada por f'.

Exercício 1

Escreva a função bind.

Solução

bind f' (gx,gs) = let (fx,fs) = f' gx in (fx,gs++fs)

Dado um par de funções depuráveis, f' e g', agora podemos compô-las juntas para fazer uma nova função depurável bind f' . g'. Escreva essa composição como f' * g' . Mesmo que a saída de g' seja incompatível com a entrada de f', nós ainda temos uma maneira fácil de concatenar suas operações. E isto sugere outra questão: existe uma função depurável 'identidade'? A função identidade ordinária tem as seguintes propriedades: f . id = f e id . f = f. Assim, estamos procurando uma função depurável, chamemo-la unidade (unit), tal que unit * f = f * unit = f. Obviamente esperamos que ela produza a string de depuração vazia e em outros casos aja como a identidade.

Exercício 2

Defina a unidade.

Solução

unit x = (x,"")

A unidade nos permite 'elevar' qualquer função em uma depurável. De fato, defina

lift f x = (f x,"")

ou mais simplesmente lift f = unit . f. A versão elevada faz basicamente o mesmo da original e, bem razoavelmente, produz a string vazia como efeito colateral.

Exercício 3

Mostre que lift f * lift g = lift (f.g)

Em suma: as funções bind e unit nos permitem compor funções depuráveis de maneira direta, e compor funções ordinárias com funções depuráveis de uma maneira natural.

Acredite ou não, fazendo estes dois exercícios você já definiu sua primeira mônada. Neste ponto, provavelmente não está claro qual das estruturas que observamos é a mônada em si, ou com o que outras mônadas se parecem. Mas em vez de definir mônadas agora eu vou te deixar com mais alguns exercícios fáceis que te introduzirão a outras mônadas de tal maneira que você verá por si mesmo que esta é uma estrutura comum digna de um nome próprio. Também estou confiante que a maioria das pessoas, quando de frente com o problema original, eventualmente chegarão à função bind como uma forma de colar suas funções depuráveis. Então estou certo que você poderia ter inventado esta mônada mesmo que não notasse que era uma mônada.

---

3 Um Contêiner: Funções Multi-Valoradas

Considere as funções sqrt e cbrt que computam as raízes quadrada e cúbica, respectivamente, de um número real. Elas são funções comuns do tipo Float -> Float (apesar de que sqrt atirará uma exceção para argumentos negativos, algo que ignoraremos).

Agora considere uma versão dessas funções que trabalhe com números complexos. Cada complexo, além do zero, tem duas raízes quadradas. Da mesma forma, cada complexo não-nulo tem três raízes cúbicas. Então gostaríamos que sqrt' e cbrt' retornassem listas de valores. Em outras palavras, queremos

sqrt',cbrt' :: Complex Float -> [Complex Float]

Vamos chamá-las de funções multi-valoradas.

Suponha que queremos determinar a raiz sexta de um número real. Nós podemos simplesmente concatenar as funções de raiz quadrada e raiz cúbica. Em outras palavras podemos definir sixthroot x = sqrt (cbrt x).

Mas como definimos uma função que encontra todas as raízes sextas de um número complexo usando sqrt' e cbrt'? Não podemos simplesmente concatenar estas funções. O que queremos é primeiro computar as raízes cúbicas de um número, e então encontrar as raízes quadradas de cada um destes números por vez, combinando os resultados em uma lista maior. O que precisamos é de uma função, vamos chamá-la bind, para compor estas funções, com declaração

bind :: (Complex Double -> [Complex Double]) -> ([Complex Double] -> [Complex Double])

Eis um diagrama mostrando como é o processo. Nós queremos escrever cbrt' apenas uma vez mas ainda assim tê-lo aplicado a ambos os valores de sqrt'.

       64
       |
    +------+
    + sqrt'+
    +------+
  +8 /    \ -8
+------+  +------+
| cbrt'|  | cbrt'|
+------+  +------+
 | | |      | | |
 2 . .     -2 . .

Exercício 4

Escreva uma implementação para bind.

Solução

bind f x = concat (map f x)

Como escrevemos a função identidade na forma multi-valorada? A identidade retorna um argumento, então uma versão multi-valorada deve retornar uma lista de tamanho 1. Chamemos esta função unit.

Exercício 5

Defina unit.

Solução

unit x = [x]

Novamente, defina f * g = bind f . g and lift f = unit . f. lift faz exatamente o que você poderia esperar. Ele transforma uma função ordinária em uma multi-valorada da maneira óbvia.

Exercício Seis

Mostre que f * unit = unit * f = f and lift f * lift g = lift (f.g)

Novamente dado o problema original, somos inexoravelmente levados a esta função bind.

Se você lidou com estes exercícios então você definiu sua segunda mônada. Você talvez esteja notando um padrão a se desenvolver. É curioso que estes dois problemas aparentemente tão diferentes tenham levado a construções similares.

4 Um Efeito Colateral Mais Complexo: Números Aleatórios

A função random em Haskell tem essa forma:

random :: StdGen -> (a,StdGen)

A ideia é que para que se gere um número aleatório é necessário uma semente, e após ter gerado o número atualizar a semente com um novo valor. Em uma linguagem impura, a semente pode ser uma variável global, assim o usuário não precisa lidar diretamente com ela. Mas numa linguagem pura a semente precisa ser passada e recuperada explicitamente - e é isso que a assinatura de tipo de random descreve. Note que isto é similar ao caso da depuração acima porque estamos retornando dados extras usando um par. Mas desta vez estamos recebendo dados extras também.

Então uma função que é conceitualmente uma função randomizada a -> b pode ser escrita como uma função a -> b a -> StdGen -> (b,StdGen) onde StdGen é o tipo da semente.

Agora deveremos trabalhar como compor duas funções randomizadas, f e g. O primeiro elemento do par que f retorna precisa ser passado como uma entrada para g. Mas a semente passada de g também precisa ser passada para f. Enquanto isso o 'real' valor de retorno de g precisa ser passado como primeiro argumento de f. Assim nós podemos dar esta assinatura para bind:

bind :: (a -> StdGen -> (b,StdGen)) -> (StdGen -> (a,StdGen)) -> (StdGen -> (b,StdGen))

Exercício 7

Implemente bind.

Solução

bind f x seed = let (x',seed') = x seed in f x' seed'

Agora precisamos encontrar a função randomizada 'identidade'. Ela precisa ser do tipo

unit :: a -> (StdGen -> (a,StdGen))

e deve deixar a semente intocada.

Exercício 8

Implemente unit.

Solução

unit x g = (x,g)
# ou também
unit = (,)

Mais uma vez, defina f * g = bind f . g e lift f = unit . f . lift faz exatamente o que você poderia esperar - transforma uma função ordinária em uma randomizada que deixa a semente intocada.

Exercício 9

Mostre que f * unit = unit * f = f e lift f * lift g = lift (f.g).

5 Mônadas

Agora é hora de retornar e discernir a estrutura comum.

Defina

type Debuggable a = (a,String)
type Multivalued a = [a]
type Randomised a = StdGen -> (a,StdGen)

Use a variável m para representar Debuggable, Multivalued ou Randomised. Em cada caso acabamos no mesmo problema. Nos é dada uma função a -> m b mas precisamos de alguma maneira aplicar esta função a um objeto do tipo m a em vez de um do tipo a. Em cada caso fazemos isso definindo uma função de nome bind com tipo (a -> m b) -> (m a -> m b) e introduzindo um tipo de função identidade unit :: a -> m a. Além disso, nós descobrimos que estas identidades valem: f * unit = unit * f = f e lift f * lift g = lift (f.g), onde * e lift foram definidas em termos de unit e bind.

Então agora eu posso revelar o que é uma mônada. A tripla de objetos (m,bind,unit) é a mônada, e para ser mônada deve satisfazer um punhado de leis como as que estivemos demonstrando. E eu penso que em cada um destes três casos você eventualmente viria com uma solução como bind, mesmo que possa não ter notado imediatamente que todos esses casos compartilham uma estrutura comum.

Pois agora eu preciso fazer algum contato com a definição usual das mônadas Haskell. A primeira coisa é que eu troquei a definição de bind e a escrevi com o nome 'bind', ao passo que normalmente escrita como o operador >>=. Então bind f x normalmente é escrito como x >> f=. A segunda é que unit geralmente é chamada return. E em terceiro lugar, a fim de sobrescrever os nomes >>= e return, precisamos fazer uso de classes de tipo. Em Haskell, Debuggable é a mônada Writer, Multivalued é a mônada List e Randomised é a mônada State. Se você conferir as definições dessas,

• Control.Monad.Writer
• Control.Monad.List
• Control.Monad.State

você notará que, excetuando algum floreio sintático, elas são essencialmente as definições que você escreveu para os exercícios acima. A depuração usou a mônada Writer, as funções multi-valoradas usaram a mônada List, e o gerador de números aleatórios usou a mônada State. Você poderia ter inventado mônadas!

6 Sintaxe da Mônada

Não quero perder tempo demais nisso (e você pode saltar esta seção) porque existem muitas excelentes introduções por aí.

Você já viu como a função bind pode prover uma bela forma de unir funções para te livrar de escrever um bom tanto de código feio. Haskell vai um passo além, você nem precisa usar a função bind explicitamente, você pode fazer que o Haskell a insira automaticamente em seu código.

Vamos retornar ao exemplo original de depuração, exceto que agora usaremos as classes de tipo oficiais de Haskell. Onde anteriormente nós usamos um par como (a,s) agora usaremos Writer (a,s) do tipo Writer Char. E para recuperar o par de um destes objetos usamos a função runWriter. Suponha que desejamos incrementar, duplicar e então decrementar 7, a cada estágio registrando o que fizemos. Nós podemos escrever

return 7
  >>= (\x -> Writer (x+1,"inc."))
  >>= (\x -> Writer (2*x,"double."))
  >>= (\x -> Writer (x-1,"dec."))

Se aplicarmos runWriter a isso obteremos (15,"inc.double.dec."). Mas ainda está bem feio. Em vez disso podemos usar a sintaxe do de Haskell. A ideia é que

do x <- y
   mais-codigo-aqui

é automaticamente reescrito pelo compilador para

y >>= (\x -> do
          mais-codigo-aqui)

Similarmente,

do
  let x = y
      mais-codigo-aqui

é reescrito como

(\x -> do
    mais-codigo-aqui) y

E

do
  expression

é deixado somente como expression.

Podemos agora reescrever o código acima como:

do
    let x = 7
    y <- Writer (x+1,"inc\n")
    z <- Writer (2*y,"double\n")
         Writer (z-1,"dec\n")

A notação é bastante sugestiva. Quando escrevemos y <- ... é como se fingíssemos que a expressão do lado direito é meramente x+1 e que o efeito colateral simplesmente cuida de si mesmo.

Outro exemplo. Escreva o exemplo da raiz sexta na forma inconveniente:

return 64 
  >>= (\x -> sqrt' x) 
  >>= (\y -> cbrt' y)

Agora podemos reescrever isso da forma legível

do
    let x = 64
    y <- sqrt' x
    z <- cbrt' y
         return z

Nós podemos escrever o que parece um código ordinário não multi-valorado e as funções bind implícitas que Haskell insere automaticamente o tornam multi-valorado.

Inventar esta sintaxe foi um trabalho de gênio. Talvez você pudesse tê-la inventado, mas eu tenho certeza que eu não teria. Mas este material extra é mero açúcar sintático em cima das mônadas. Eu ainda afirmo que você poderia ter inventado as mônadas subjacentes.

7 Entrada&Saída

Existe agora uma última coisa a ser observada antes de você estar completamente qualificado em monadicidade. Interação com o mundo exterior. Até agora tudo o que eu tenho dito pode aplicar-se a qualquer linguagem funcional pura. Mas agora considere linguagens funcionais puras preguiçosas. Em uma tal linguagem, você não tem ideia de que ordem as coisas serão evaluadas. Então se você tem uma função para imprimir a mensagem "Insira um número" e outra para inserir o número, você pode não ser capaz de garantir que a mensagem será impressa antes da entrada ser requerida! Volte ao exemplo da função randomizada. Note como a semente randomizada acaba costurada ao longo das suas funções de modo que ela pode ser usada cada vez que random é chamada, Existe um tipo de ordenamento acontecendo. Suponha que tenhamos x >> f >>= g=. Como g usa a semente retornada por f, sabemos com certeza que f gerará seu número aleatório antes de g. Isto mostra que, em princípio, mônadas podem ser usadas para ordenar computações.

Agora considere a implementação de random no compilador. Ela é tipicamente uma rotina C ou ASM ligada no executável Haskell final. Se esta rotina fosse modificada de forma a realizar E/S poderíamos garantir que a E/S em f foi realizada antes daquela em g. Isto é exatamente como E/S funciona em Haskell, nós realizamos toda a E/S numa mônada. Neste caso, uma função que conceitualmente é do tipo a -> b mas também tem um efeito colateral no mundo real é na realidade do tipo a -> IO b. O tipo IO é uma caixa-preta, não precisamos saber como ela é. (Talvez ema funcione como o exemplo random, talvez não.) Nós apenas precisamos saber que x >> f >>= g= executa a E/S em f antes de g.

8 Teoria das Categorias

Uma última coisa. Mônadas são originalmente desenvolvidas no contexto da teoria das categorias. Vou deixar esta conexão para outro dia.

Oh!… e eu devo mencionar… ainda não estou convencido de que eu poderia inventar Sequências Espectrais. Mas ainda estou trabalhando nisso graças a Tim Chow.

9 Apêndice: Um Exemplo de Código Completo Usando Números Aleatórios

Primeiro, eis o código correspondente às definições acima:

import Random

bind :: (a -> StdGen -> (b,StdGen)) -> (StdGen -> (a,StdGen)) -> (StdGen -> (b,StdGen))
bind f x seed = let (x',seed') = x seed in f x' seed'
unit x g = (x,g)
lift f = unit . f

Então eis o que faremos: queremos construir um número aleatório de dois dígitos em três passos. Começando de 0, nós vamos:

1. adicionar um inteiro aleatório de 0 a 9
2. multiplicá-lo por 10
3. adicionar outro inteiro aleatório de 0 a 9

Conceitualmente esta operação é uma composição similar a addDigit . (*10) . addDigit. Mas nós sabemos que precisamos costurar a semente aleatória ao longo desse código. Primeiro, repare a real definição de addDigit:

addDigit n g = let (a,g') = random g in (n + a `mod` 10,g')

Isto retorna um par consistindo de n+digitoAleatorio e a nova semente. Note como isto também recebe a nova semente como argumento. Pode-se dizer que 'conceitualmente' esta função é addDigit n = let a = random in n + a `mod` 10 e numa linguagem estrita e impura adequada isto seria considerado um código válido.

Agora considere a operação de multiplicar por 10. Esta é uma operação ordinária que podemos 'melhorar' usando lift. Então obtemos

shift = lift (*10)

Agora o ponto crucial. Não podemos simplesmente compor, mas em vez disso devemos usar bind para converter nossas funções em uma forma que podem ser compostas. Então o conceitual addDigit . (*10) . addDigit torna-se

test :: Integer -> StdGen ->  (Integer,StdGen)
test = bind addDigit . bind shift . addDigit

Agora criamos a semente usando meu número favorito e rodamos o código:

g = mkStdGen 666
main = print $ test 0 g

Note que eu decidi não usar a classe de tipos Monad nativa de forma que nada ficasse oculto e que tudo estivesse explícito.

Atualização: Agradeço pelos comentários! Eu fiz uma série de consertos e adicionei um apêndice com um exemplo de números aleatórios. A maioria dos fragmentos de código agora foi copiada para o texto final em código real, então deve haver apenas alguns erros de digitação. Desculpas por qualquer confusão causada!

Para uma abordagem diferente sobre mônadas, eu escrevi um, pouco sobre as flechas de Kleisi. E se você estiver interessado em empilhar mônadas para obter mais funcionalidades, você pode tentar isso.

10 META

Table 1: META

Autor	Dan Piponi
Título Original	You Could Have Invented Monads! (And Maybe You Already Have.)
Link Original	http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html
Link Arquivado	http://archive.is/Jox0z

Footnotes:

¹

Existe até uma página na Haskell Wiki dedicada a isso!

²

Não conheço termo melhor para plumbing - "encanamento", no sentido de "serviço de encanador/pedreiro"…

Created: 2018-08-28 ter 09:42

Validate

O Horror Glorioso de TECO [markcc]

O Horror Glorioso de TECO

Table of Contents

• 1. Intro
• 2. História
• 3. Um Gostinho de Programação TECO
  • 3.1. Comandos TECO
  • 3.2. Exemplo de Código TECO
• 4. META

1 Intro

Em meu tão abundante tempo livre, eu tenho trabalhado no meu próprio editorzinho de texto. E uma das minhas motivações é o TECO: um dos mais antigos, e dos melhores, já feito. Ele é ao mesmo tempo um editor de texto e uma linguagem de programação - e, de fato, é exatamente isto o que fez dele uma ferramenta tão brilhante. Muito do enfado da programação são coisas que poderiam realmente ser feitas por um programa. Mas gastamos tanto tempo aprendendo extravagâncias que perdemos o fio da meada. Hoje em dia, você pode escrever um programa em emacs lisp que faz as coisas que você costumava fazer em TECO; é apenas bem estranho que você geralmente não o faça.

O problema, porém, com meramente reimplementar TECO com uma interface moderna é que ele foi projetado numa época diferente. Quando TECO foi escrito, cada byte era crítico. E portanto a linguagem, a sintaxe, a estrutura, era completamente ridícula. E, como resultado, ela tornou-se a mais útil linguagem de programação patológica já escrita. É uma peça gloriosa, hedionda, maravilhosa, horripilante da história da computação.

TECO é uma das peças mais influentes de software já feita. Se, por um acaso, você ouvir falar de um editorzinho chamado "emacs"; bem, ele era originalmente um conjunto de macros de edição para o TECO (EMACS = Editor MACroS). Como linguagem, ela é tanto poderosa quanto medonha. Do lado bom, o conceito central da linguagem é maravilhoso: é uma linguagem poderosa para processar texto, que funciona basicamente repetidamente procurando texto que casa algum tipo de padrão, tomando algum tipo de ação quando o encontra, e daí selecionando o próximo padrão de procura. Esta é uma maneira de escrever programas de processamento de texto bastante natural e fácil de entender. Do lado mau, ela tem a mais horrenda e macabra sintaxe já imaginada

2 História

TECO merece uma discussão da sua própria história - sua história é basicamente a de como os editores para programadores foram desenvolvidos. Esta é uma versão bastante curta, mas boa o bastante para esta postagem.

Antigamente os computadores PDP usavam uma fita de papel para alimentá-lo com programas. (Mainframes usavam cartões perfurados, enquanto minicomputadores como os PDPs usavam fita.) O grande problema com fitas de papel é que se ocorre um erro, você tem que ou criar uma fita inteira contendo a correção, ou cuidadosamente cortar e emendar a fita com novos segmentos a fim de criar uma nova fita (e emendar era algo bem propenso a erros).

Isto era ruim. E por isso, TECO nasceu. TECO era o "Tape Editor and COrrector" ¹. Ele era uma linguagem de programação Turing-completa na qual se podia escrever programas para fazer correções. Assim você colocaria o programa TECO no computador primeiro, e então alimentaria a fita original (com erros) na máquina; o programa TECO faria as edições especificadas, e então você alimentaria o programa para o compilador. Era necessário que TECO fosse Turing-completo, porque você estava escrevendo um programa para encontrar coisas que precisam ser modificadas

Uma linguagem projetada para viver num mundo de fitas de papel tinha que ter alguns limitantes principais. Primeiro, fita de papel é lenta. Muito lenta. E perfurar fita é um processo miserável. Então você realmente desejaria manter as coisas o mais curtas possível. Portanto a sintaxe do TECO era, para dizer delicadamente, absolutamente incompreensível. Cada caractere é um comando. E não estou dizendo "cada pontuação" ou "cada letra". Cada caractere é um comando. Letras, números, pontuação, preenchimento de linha (linefeed), caracteres de controle … tudo.

Mas apesar de sua natureza absolutamente críptica, era bom. TECO era muito bom. Então quando as pessoas começaram a usar teletipos interativos (a 110 baud), elas ainda queriam usar TECO. Então ele evoluiu. Mas a sintaxe básica baseada em fita permaneceu.

Quando terminais de tela endereçável apareceram - VT52 e coisa do tipo - de repente, era possível escrever programas que usavam controle de cursor! A ideia de um editor de tela cheia surgiu. Claro, adoradores do TECO queriam que seu editor de tela cheia preferido fosse o TECO. Para máquinas VAX, um dos primeiros editores de tela cheia foi uma versão de TECO que exibia uma tela de texto, e executava os comandos à media em que eram digitados; e para comandos que necessitavam de uma entrada extra (como busca de texto), ele usava uma linha-de-modo no inferior da tela (exatamente da mesma maneira que o emacs faz hoje em dia).

Não muito depois disso, Richard Stallman e James Gosling escreveram o emacs - o editor de macros para TECO. Originalmente ele nada mais era além de macros para o TECO a fim de tornar o editor de tela cheia mais fácil de usar. Mas eventualmente eles o reescreveram do zero, baseado em LISP. E não muito depois disso, TECO se esvaneceu, apenas para ser lembrado por um punhado de geeks idosos. A sintaxe de TECO o matou; o fato é que se você tem uma alternativa para a incompreensível repulsividade que é a sintaxe TECO, você estaria disposto a ficar com uma linguagem menos poderosa que pudesse realmente ler. Então quase todo mundo preferiria escrever seus programas em emacs lisp que em TECO, mesmo que TECO fosse uma melhor linguagem.

A desgraça da morte do TECO é que ele era mesmo uma bela linguagem de programação. Hoje em dia eu ainda encontro coisas que preciso fazer que são melhor adaptadas para o TECO que para qualquer linguagem de programação moderna que eu conheço. O problema, porém, e a razão para que ele tenha desaparecido tão drasticamente é que a sintaxe de TECO é tão incompreensivelmente ruim que ninguém, nem mesmo alguém tão insano quanto eu, tentaria escrever código nela quando há outras opções disponíveis.

3 Um Gostinho de Programação TECO

Antes de pular de cabeça e explicar o básico do TECO mais detalhadamente, vamos observar rapidamente um programa TECO simples. Este programa é absoluta e notavelmente claro e legível para um código-fonte TECO. Ele até mesmo usa um truque para permitir o uso de comentários. As coisas que parecem comentários na verdade são alvos de desvio "goto".

0uz                      ! limpa a flag de repeticao !
<j 0aua l                ! carrega o 1o. caractere no registrador A !
<0aub                    ! carrega o 1o. caractere da proxima linha no registrador B !
qa-qb"g xa k -l ga-1uz ' ! se A>B, troca as linhas e ativa a flag !
qbua                     ! carrega B em A !
l .-z;>                  ! volta o laco se há outra linha no buffer !
qz;>                     ! repete se uma troca foi feita na ultima passada !

A ideia básica da programação TECO é bastante simples: procure por algo que case certo tipo de padrão; realize algum tipo de operação de edição na localização encontrada; e então escolha a nova pesquisa para encontrar a próxima coisa a fazer.

O programa de exemplo acima é uma versão bastante sofisticada para um programa tão pequeno. Ele procura pelo começo de linhas consecutivas. Para cada par de linhas, se elas não estão na ordem devida, ele as troca, e então procura pelo próximo par de linhas consecutivas. Isto é enclausurado num laço que continua repetindo a varredura ao longo do arquivo até que cada par consecutivo de linhas esteja ordenado. Em outras palavras, um swap-sort.

A estrutura de dados fundamental (a única?) em TECO é o buffer de texto. Todos os programas TECO são baseados na ideia de que você tem um buffer cheio de texto, e quer fazer algo para modificá-lo. A maneira que se acessa o buffer é mediante um cursor, que é um ponteiro no buffer, que representa a posição na qual quaisquer operações de edição serão realizadas. Assim as operações TECO funcionam ou lendo o texto no cursor, ou editando o texto no cursor, ou movendo o cursor. No jargão TECO, a posição do cursor é chamada ponto. O ponto está sempre entre dois caracteres.

3.1 Comandos TECO

Não me é possível explicar todo o TECO em uma postagem, então eu vou simplesmente passar pelo suficiente para te dar uma ideia, e tornar possível que você possa acompanhar um programa de exemplo. Se quiser, você pode olhar a lista completa de comandos, ou até mesmo ler o manual do TECO.

Comandos TECO geralmente são de um caractere. Mas existe alguma estrutura adicional para permitir argumentos. Existem dois tipos de argumentos: os numéricos e os textuais. Argumentos numéricos aparecem antes do comando; os textuais aparecem depois do comando. Valores numéricos usados como argumentos podem ser ou números literais, ou comandos que retornam valores numéricos, ou . (para o índice do ponteiro do buffer) ou valores numéricos junto a operadores aritméticos como +,=-=, etc.

Então, por exemplo, o comando C move o ponteiro um caractere para frente. Se for precedido de um argumento numérico N, ele moverá N caracteres. O comando J salta o ponteiro para uma localização específica do buffer: o argumento numérico é o deslocamento do início do buffer até a posição em que o ponteiro deva ser posicionado.

Argumentos string vêm depois do comando. Cada argumento string pode ser delimitado de uma ou duas formas. Por padrão, um argumento string continua até ver um caractere de escape (ESC), que marca o fim da string. Como alternativa (e mais fácil de ler), se o comando é prefixado por um caractere @, então o primeiro caractere após o comando será usado como delimitador da string, de taç forma que a string-parâmetro continuará até a próxima instância daquele caractere.

Então, por exemplo, a primeira coisa que a maioria dos comandos TECO faz é especificar o que é que eles querem editar - isto -e, o que eles querem ler no buffer. O comando para fazer isso é ER. Ele precisa de um argumento string para lhe informar o nome do arquivo a ser lido - então o comando para ler o arquivo foo.txt é ERfoo.txt (seguido por pressionar ESC duas vezes para informar ao TECO para ler o comando). Alternativamente, você poderia usar uma das outras variantes para argumentos string. Por exemplo, poderia usar aspas de de citação, usando @ER'foo.txt'. Ou poderia usar a citação de uma forma deliberadamente frívola: =@ER foo.txt =. (Isto é, usando espaço como caractere de citação, te dando uma citação quase invisível).

Além dos argumentos padrão, você também pode modificar os comandos, colocando um : na frente deles. Para a maioria, : os faz retornar ou um 0 (indicando que o comando falhou) ou um -1 (indicando sucesso). Para outros, o dois-pontos faz outra coisa. A única maneira de saber é conhecendo o comando.

Pois bem, agora que sabemos basicamente como os comandos e argumentos se parecem, podemos começar a observar os comandos que criam a besta chamada TECO.

É claro, existe um punhado de comandos para imprimir parte do buffer. Lembre-se, TECO originalmente veio de uma época anterior a editores de tela cheia, então você precisa ser capaz de pedir a ele para mostrar como o texto estava antes de uma sequência de edições, a fim de se certificar que ele esteja bem do jeito que você queria e salvá-lo. O comando básico para impressão é T , que imprime a linha atual. Para imprimir uma string, você usaria o comando ^A (significando Control-A; eu disse que tudo era um comando!).

Isto significa que agora podemos enfim dizer como escrever o bom e velho clássico "Hello, World!" em TECO! É bem simples:

@^A'Hello, World!'

Isto é, argumento de string entre quotes, imprimir, seguido da string entre quotes. Perfeitamente claro, não?

Existem também, naturalmente, comandos para editar o texto de diversas maneiras:

D

Deleta o caractere após o cursor

FD

Find-delete. Recebe um argumento string, encontra a próxima ocorrência, e a deleta

K

Deleta o texto do cursor até o fim da linha

HK

Deleta o buffer inteiro

I

Insere texto. Obviamente, precisa de um argumento string, que é o texto que ele insere.

<TAB>

Um segundo comando de inserção; a única diferença é que o <TAB> também é inserido no texto.

Agora alguns comandos que movem o ponto pelo buffer.

C

Move o ponteiro adiante um caractere se nenhum argumento é fornecido; se recebe um argumento numérico N, avança N caracteres. Pode ser precedido por um : para retornar um valor sucesso.

J

Salta para uma localização especificada por seu argumento numérico. Se não é especificada nenhuma localização, ele salta para a posição 0. J pode ser precedido de um : para verificar se houve sucesso.

ZJ

Pula para a posição após o último caractere do arquivo.

L

Bem semelhante a C exceto que se move por linhas em vez de caracteres.

R

Move um caractere para trás - é basicamente o mesmo que C com argumento negativo.

S

Procura por seu argumento string, e posiciona o cursor após o último caractere da string de busca que ele encontrou, ou na posição 0 se a string não foi encontrada.

número,númeroFB

Procura pelo argumento string entre as posições do buffer especificadas pelos argumentos numéricos. As strings de busca podem incluir algo quase similar a expressões regulares, mas com uma sintaxe muito pior. Eu não quero destruir demais o teu cérebro, então não vou entrar em detalhes.

TECO tinha variáveis; em seu próprio estilo inimitável, elas não eram chamadas variáveis; eram chamadas registradores Q, ou Q-registradores. Existem 36 Q-registradores globais, com nomes de A a Z ² e de 0 a 9. Também há 36 Q-registradores locais (locais a uma macro em particular, também conhecida como sub-rotina), que têm um caractere . na frente dos seus nomes.

Registradores Q são usados para duas coisas. Primeiro, você pode usá-los como variáveis: cada registrador Q armazena uma string e um inteiro. Segundo, qualquer string armazenada em um registrador Q pode ser usado como sub-rotina; de fato, esta é a única maneira de criar uma sub-rotina. Os comandos para trabalhar com registradores Q incluem:

nUq

n é um argumento numérico; q é o nome de um registrador. Isto salva o valor m como o valor numérico do registrador q.

m,nUq

ambos m e n são argumentos numéricos, e q é o nome de um registrador. Isto guarda n como valor numérico do registrador q, e então retorna m como parâmetro para o próximo comando.

n%q

adiciona o número n ao valor numérico salvo no registrador q.

^Uqstring

Armazena a string como valor string do registrador q.

:\^Uqstring"

Anexa o parâmetro string ao valor string do registrador q.

nXq

limpa o valor texto do registrador q, e copia as próximas n linhas em seu valor string.

m,nXq

copia o intervalo de caracteres da posição m até a posição n no registrador q.

.,.+nXq

copia n caracteres seguindo o ponteiro do buffer no registrador q.

*Qq

usa o valor inteiro do registrador q como parâmetro para o próximo comando.

nQq

usa o valor ascii do n-ésimo caractere do registrador q como parâmetro para o comando seguinte.

:Qq

usa o comprimento do texto armazenado no registrador q como parâmetro para o comando seguinte.

Gq

copia o conteúdo textual do registrador q para a posição corrente do ponteiro do buffer.

Mq

invoca o conteúdo do registrador q como uma sub-rotina

E por último, mas definitivamente não menos importante, temos o controle de fluxo. Primeiro, há laços. Um laço é n<comandos>, que executa o trecho entre a as chaves angulares n vezes. Dentro do laço, ; sai do laço se o último comando de busca falhou; n; sai do laço se o valor de n é maior que ou igual a zero. :; sai do laço se a última busca foi bem-sucedida. F> salta para a chave angular de fechamento (pense como no continue de C), F< salta para o início do laço.

Condicionais são escritas geralmente n"Xcomandos-se|comandos-senao'. As aspas de quote fazem parte do comando! O caractere de aspa dupla introduz a condicional, o de aspa simples marca o fim. No comando, o X é um de uma lista de testes condicionais, que definem como o argumento numérico n deve ser testado. Alguns valores possíveis de X incluem:

A

testa se n é o código de caractere de um alfabético

D

testa se n é o código de caractere de um dígito

E

testa se n é zero ou falso

G

testa se n é maior que zero

N

testa se n é diferente de zero

L

testa se n é um valor numérico indicando que o último comando foi bem-sucedido

3.2 Exemplo de Código TECO

Então, é hora para um par de programas TECO de verdade.

Vamos começar reparando o programa de swapsort do topo deste post.

1. 0uz: atribui ao Q-registrador z o valor 0
2. <j: inicia um laço, e posiciona o ponto no início do arquivo.
3. 0aua: lê o caractere no início da linha, e o passa como argumento numérico para ua, que atualiza o valor do registrador a. Assim o registrador a contém o primeiro caractere da linha
4. l: avança uma linha.
5. <0aub: inicia um novo laço, e atribui o primeiro caractere da nova linha ao registrador b.
6. qa-qb"g: subtrai o valor do registrador b do registrador a. Se o resultado é maior que zero, então faça o seguinte:
   1. xa: carrega a linha atual (a segunda dessas duas linhas consecutivas) no registrador a.
   2. k: deleta esta linha.
   3. -l: retrocede uma linha.
   4. ga: insere o conteúdo de a (o que costumava ser a última linha) na linha. Então agora nós tínhamos ... L1 L2 ...; deletamos L2, nos dando ... L1 ... e agora saltamos o cursor de volta a L1, e inserimos, portanto nós obtivemos ... L2 L1 ... - portanto as linhas estão trocadas
   5. -1uz: atribui ao registrador z o valor -1. Isto está simplesmente fixando uma flag dizendo "eu fiz uma troca de linhas".
   6. ': fim da condicional.
7. qbua: coloca o que estava no registrador b no registrador a.
8. l .-z;>: se existirem mais linhas n buffer, então vá para o começo do laço (o mais interno)
9. qz;>: se a flag z não é nula então repete o laço externo.

Nossa, não parece simples? Brincadeiras à parte, é mesmo. Uma vez que você se acostuma à ideia de editar um buffer de texto, é realmente bastante natural. É quase impossível ler esta coisa … mas não é tão ruim assim semanticamente.

Então agora você deve estar preparado para algo que seja um pouco menos claramente escrito. Ninguém escreve um código como o daquele exemplo, com toda essa documentação! Este é um exemplo de como um programa TECO funcionando se parece. É um programa realmente útil: ele sonda o arquivo contendo uma mistura de espaços e tabulações, e substitui todas as tabulações, assumindo que espaçamentos de tabulação aparecem a cada oito colunas.

  FEB  :XF27: F H M Y<:N   ;'.U 0L.UAQB-QAUC<QC-9"L1;'-8%C>9-QCUD
S    DQD<I >>EX

Agora está perfeitamente claro, não?

OK, já que essa foi fácil, que tal algo desafiador?

Esta belezinha aqui recebe um buffer e executa seu conteúdo como um programa Brainfuck. Sim, é um interpretador Brainfuck em TECO!

@^UB#@S/{^EQQ,/#@^UC#@S/,^EQQ}/@-1S/{/#@^UR#.U1ZJQZ^SC.,.+-^SXQ-^SDQ1J#
@^U9/[]-+<>.,/<@:-FD/^N^EG9/;>J30000<0@I//>ZJZUL30000J0U10U20U30U60U7
@^U4/[]/@^U5#<@:S/^EG4/U7Q7; -AU3(Q3-91)"=%1|Q1"=.U6ZJ@i/{/Q2@i/,/Q6@i/}
/Q6J0;'-1%1'>#<@:S/[/UT.U210^T13^TQT;QT"NM5Q2J'>0UP30000J.US.UI
<(0A-43)"=QPJ0AUTDQT+1@I//QIJ@O/end/'(0A-45)"=QPJ0AUTDQT-1@I/
/QIJ@O/end/'(0A-60)"=QP-1UP@O/end/'(0A-62)"=QP+1UP@O/end/'(0A-46)"=-.+QPA
^T(-.+QPA-10)"=13^T'@O/end/'(0A-44)"=^TUT8^TQPJDQT@I//QIJ@O/end/'(0A-91)
"=-.+QPA"=QI+1UZQLJMRMB    -1J.UI'@O
/end/'(0A-93)"=-.+QPA"NQI+1UZQLJMRMC-1J.UI'@O/end/'
!end!QI+1UI(.-Z)"=.=@^a/END/^c^c'C>

Se você é realmente insano o bastante para tentar esta monstruosidade masoquística, você pode obter um interpretador TECO, com documentação e exemplos de programas, aqui.

---

4 META

Table 1: META

Autor	markcc
Título Original	The Glorious Horror of TECO
Link Original	http://www.goodmath.org/blog/2010/11/30/the-glorious-horror-of-teco/
Link Arquivado	http://archive.is/Jox0z

Footnotes:

¹

Em português, Editor e Corretor de Fita.

²

Sim, contando K, W e Y.

Created: 2018-08-21 ter 07:09

Validate