Realidades Paralelas

First contact with Coq

2007-12-07T20:11:00.000-08:00

I've started to look a bit into Coq, beginning with Coq in a Hurry. It begins nice enough, but then in section 3 there's a proof that for all propositions a and b, a and b implies b and a. I didn't understand a thing. Well, one bit or another, judging by previous contacts with systems for first order logic, but the tactics, and the organization of the proof, it all flew over my head. Just by reading the material it was hard to discern what was I supposed to input to get the same result. Then there are two paragraphs about the tactics, and a table. I can't imagine how I would use it right now.

But that's ok, I'm sure I'll understand it better later. There's the Coq Tutorial and a bit more of material to get into. Then I'll post about it later, if I don't get lazy. It's bound to be truly exciting stuff about the Calculus of Inductive Constructions and dependent type theory. Great subject to draw upon for chitchat at cocktail parties.

In search of good mind-mapping software

2007-07-06T15:27:00.000-07:00

So I recently started to create mind maps to summarize studies and come up with new ideas. It's better to start a map on paper than to use a computer program, granted. But then, after the initial session is over, it would be good to make a digital version of it to be consulted and edited later. A mind-mapping tool is thus a good idea.

I tried some programs on this list. FreeMind is one of the best free software tools for mind mapping, but it still has lots of usability problems, and it runs on the JVM, which means slow startup and eats-lots-of-memory. Mind42.com is interesting exactly because it is a web application, no need to install anything, available anywhere, etc. But I couldn't try it; after signing up for a free account more than 24 hours ago, I still haven't received the confirmation email, so I can't login. I guess I won't bother trying to register again.

But it gets worse: both of them doesn't seem to support links between nodes in different parts of the tree (cross-links). Does everyone that does mind maps manage to categorize everything hierarchically? To me, in any non-trivial map there'll be lots of relations which are not hierarchical in nature, and I think that not allowing these cross links is a serious limitation. Maybe I should consider creating semantic networks, but there doesn't seem to be tools for that.

Great Works in Programming Languages

2007-04-19T21:00:00.000-07:00

I guess I never linked to this before, even though I was certain I had. It's a list of papers selected by a community of programming language researchers as the most important and representative of the field. The collection is called Great Works in Programming Languages. Worth taking a look.

I have read and reviewed "An axiomatic basis for computer programming" by C.A.R. Hoare, here (in portuguese). I've read "A theory of type polymorphism in programming" by Milner more than once, and never finished "Towards a theory of type structure" by Reynolds. I also read the one by Landin ("The next 700 programming languages") and Plotkin's "Call-by-name, call-by-value, and the λ-calculus" is on my queue. Maybe someday I'll get back to them and post reviews.

Another new acquisition

2007-04-19T20:36:00.000-07:00

I just got the book Proof, Language and Interaction: Essays in Honour of Robin Milner by mail. It's a hefty tome that's over 700 pages long, containing essays in various topics related to the work of Robin Milner. The best part is that while it costs around 80 dollars, I got it for 9 dollars plus shipping. This should be a rule: if you're a starving student in a third-world university and no institutional budget for buying expensive technical books, you can buy them for 10 dollars or so. There's always hope.

Anyway, my main interest in the book lies in the essays related to the π-calculus, especially the one on Pict, but the Harper-Stone paper on the semantics of Standard ML is also on my list, as is the essay by Mike Gordon "From LCF to HOL: A Short History". I'll probably look at many others, but I doubt I'll be able to understand much of some of them, like "From Banach to Milner: Metric Semantics for Second Order Communication and Concurrency".

All in all, a good acquisition, at a very good price.

Classic Texts in Computer Science

2007-02-24T21:59:00.000-08:00

A selection of classic texts in the discipline, by Babar K. Zafar, with links to electronic versions of each one.

Choosing which texts are classic can certainly be controversial, although in this case I think only texts with electronic versions available were considered. Even so, there are many good things in there, some of which I have already read, some I plan to read soon.

An Introduction to the Bird-Meertens Formalism

2007-02-22T10:53:00.000-08:00

by Jeremy Gibbons (link to paper).

Introduces the BMF, also called Squiggol, by using an example: a derivation of a linear algorithm to compute the Maximum Segment Sum of a list of numbers. The problem is presented in the book Programming Pearls by Bentley, and the derivation of the linear solution using Horner's rule apparently was first suggested by Bird. The paper first presents some motivation to using the formalism, then takes care of notation, proving some theorems by the way, then presents Horner's rule for polynomials and a generalization of the rule for arbitrary operations (that satisfy certain conditions). When the groundwork is completed, it presents a clear specification of the MSS problem that would take cubic time to compute; from this specification, using the theorems presented earlier and the generalized Horner's rule, it is derived an efficient linear algorithm based on list scans.

The paper is also interesting for showing the properties of catamorphisms and folds. Folds are more general than catamorphisms, but if the fold operation is associative, it can be expressed as catamorphism as well.

The paper makes the claim that "creativity is not needed" when deriving an efficient program from a simple specification. This doesn't seem to hold up well. Sure there is creativity somewhere in it, and although the derivation itself seems simple, it depends on the available theorems. So the choice of which theorems to state and prove, a priori (that is, when you don't know the answer beforehand) seems to involve a lot of creativity. Of course, the paper does not claim that you don't need creativity there, only in the derivation itself. Even so, the example presented is quite small. It uses only a handful of theorems, all of them stated earlier. So how does one go about choosing which theorems to use in a derivation? Is it trial and error? Isn't there some creativity involved? In a realistic formalism to derive programs from specifications, you'd probably end with lots of theorems. It seems to me that it is far from trivial to decide which one to use in each step. Maybe a experienced practitioner can decide where to go based on previous sessions of trial and error, by considering the "look" of the current expression.

Another problem is where to stop. How do you know you got an interesting, efficient implementation of your specifications? You must be able to recognize good implementations somehow. This isn't different from how you can express mathematical expressions in many ways, some more useful than others depending on circumstance. But the properties of good implementations are not clear.

All in all, claiming that "creativity is not needed" in the derivation process mostly makes me think it can be automated without resorting to AI techniques. But if you think about how to do it -- trial and error amounts to exponential search, lack of clear goals or evaluation criteria for results makes termination difficult to specify -- it becomes clear that implementing an automatic tool for derivating programs from specifications would be quite difficult. My doubts are mostly concerned with how a formalism like this would scale to the derivation of realistic programs, instead of small toys.

I've found the book by Bird and de Moor at a very good price in an online bookstore and ordered it. If it ever gets to me, we'll see how the formalism scales.

Código funcional

2007-02-17T09:38:00.000-08:00

Enquanto eu não volto a postar neste blog, aproveito para linkar aqui um outro que criei: Code Miscellany, dedicado principalmente a postagem de código-fonte em linguagens funcionais. Na verdade está servindo mais, atualmente, para postar minha tradução do código e exercícios do livro Essentials of Programming Languages para F#, a linguagem funcional parecida com OCaml da Microsoft. Mas sempre pode ter alguma coisa diferente por lá. E depois outros livros podem ser traduzidos para outras linguagens.

Quanto a este blog aqui, sugiro que alguém que porventura tenha interesse nele assine o feed em algum agregador, por exemplo o Bloglines ou o Google Reader. Mais fácil de saber quando tem post novo.

Teias de aranha

2006-11-25T15:33:00.000-08:00

Mais um post apenas para comentar que o alto nível de atividade e estresse me impediram de postar por um tempo. Também faltou ter o que comentar aqui, em termos. Mas agora que o que tinha de ser defendido foi defendido, posso voltar a escrever mais. Tenho pensado em algumas direções de pesquisa, e depois posso comentar sobre isso. Por enquanto fiquem com esse link bem legal:

Writing a Lisp Interpreter in Haskell

Mais um bug da Microsoft

2006-08-03T11:58:00.000-07:00

Mas calma, nao é a deste blog malhar a Microsoft, um esporte popular por aí mas bastante irracional. O bug é em um sistema de reconhecimento de voz, veja o vídeo.

Aí tem a explicação de um desenvolvedor da Microsoft, Larry Osterman. E aqui uma passagem do post:

If you've worked with analog audio, it's pretty clear what's happening here - there's a timing issue that is causing a positive feedback loop that resulted from a signal being fed back into an amplifier.

It turns out that one of the common causes of feedback loops in software is a concurrency issue with notifications - a notification is received with new data, which updates a value, updating the value causes a new notification to be generated, which updates a value, updating the value causes a new notification, and so-on...

The code actually handled most of the feedback cases involving notifications, but there were two lower level bugs that complicated things. The first bug was that there was an incorrect calculation that occurred when handling one of the values in the notification, and the second was that there was a concurrency issue - a member variable that should have been protected wasn't (I'm simplifying what actually happened, but this suffices).

As a consequence of these two very subtle low level bugs, the speech recognition engine wasn't able to correctly control the gain on the microphone, when it did, it hit the notification feedback loop, which caused the microphone to clip, which meant that the samples being received by the speech recognition engine weren't accurate.

Vejamos: um bug de concorrência. O problema não é a Microsoft, porque bugs como esse ocorrem por todo lugar. Será que realmente devemos ficar contentes com o atual estado da programação concorrente?

Sua linguagem pode fazer isso?

2006-08-01T18:10:00.000-07:00

Mais um texto de Joel Spolsky sobre as limitações de um programador que só aprende Java.

Cyclone: primeiras impressões

2006-06-01T13:41:00.000-07:00

Long time no see, dear blog. Depois de vários desvios estou me concentrando de novo no tema da dissertação, até porque falta pouco. E depois de muito suspense o tema é gerenciamento de memória concorrente/paralelo, o que foi bom porque integrou bem dois temas que eu vinha pesquisando em paralelo, com o perdão do trocadilho. Depois, quem sabe, eu escrevo mais sobre o que estou fazendo.

Mas o assunto agora é Cyclone, a linguagem derivada de C mas mais segura (safe). Além das adições necessárias para tornar a linguagem segura, outras coisas interessantes também acabaram entrando na linguagem: polimorfismo paramétrico, pattern matching, tipos-soma mais interessantes (as unions em C são muito ruins), etc.

O gerenciamento de memória é feito principalmente usando regiões, mas de forma mais manual e com menos inferência do que no caso do MLKit. Além das regiões, os ponteiros possuem vários qualificadores para separar os ponteiros que podem ser nulos ou não, os que apontam para um array terminado com um byte 0 (caso das strings) e etc.

Onde entra Cyclone no meu projeto? A plataforma de testes será um compilador para uma linguagem funcional lazy simples, que inclui obviamente um coletor de lixo. Dessa forma será possível observar o comportamento do coletor em situações reais, ao invés de simplesmente gerar grafos de memória aleatórios. E nesse caso o runtime seria feito em Cyclone, como alternativa a usar C para a mesma tarefa. Não existem muitas escolhas aqui: as linguagens funcionais que eu gosto não servem para esse tipo de system programming. Never mind that, o compilador está sendo escrito em Haskell.

Por enquanto só escrevendo alguns programas para me acostumar com a linguagem (Cyclone), mas a maior dificuldade são os ponteiros. Tanto os qualificadores quanto as regiões me fazem parar para pensar em várias decisões que não me ocorreriam se eu estivesse programando em C, pelo menos não inicialmente. Isso é interessante, mas me faz consultar o manual o tempo todo. Os próprios criadores da linguagem já revelaram na lista a possibilidade de simplificar o sistema, que realmente é bem complexo. De certa forma isso reflete a complexidade inerente do gerenciamento de memória, mas a coisa não precisa ser necessariamente assim para o programador. A visão que o programador tem pode ser outra, caindo para o nível mais baixo quando necessário. Esse é um tema interessante que acontece em outros contextos, mas a discussão sobre isso fica para outra vez.

Um pouco de crítica

2006-04-22T16:16:00.000-07:00

Duas observações não muito lisonjeiras sobre a linguagem C:

Henry Baker lembra que alguns problemas recorrentes na linguagem têm soluções conhecidas pelo menos desde a década de 60;
Dave Herman discute sobre os problemas de aprender controle de fluxo nas linguagens de programação apenas baseado em C.

Os dois são boa leitura, e aí podemos terminar com o conhecido ensaio de Richard Gabriel que estabelece que Worse is Better (mais contexto aqui).

Grafos e C++

2006-03-29T17:12:00.000-08:00

Postando muito pouco por aqui, prazos abundam. Prazos tipo deadlines, entende?

Trabalhando em artigos para enviar, e trabalhando mais com teoria dos grafos, os testes principalmente sendo feitos em C++.

Houve uma época em que eu programava muito em C++, lia livros, entendia vários dos detalhes esotéricos da linguagem -- sabia que uma classe com membros virtuais e cujo destrutor não é virtual pode causar vazementos de memória? Pois é, essa é C++.

Depois eu subi na vida e passei a usar linguagens mais decentes. Agora, voltando a usar C++, dá para ver de maneira mais isenta como a linguagem é brain damaged. Os exemplos são muitos, mas só para ficar com um probleminha menor da biblioteca padrão: fstream::open recebe um parâmetro que é o nome do arquivo para abrir; seria de se esperar que a função aceitasse uma string C++ como nome do arquivo, mas não: só strings char* em estilo C.

Enfim, grafos por todos os lados e C++, infelizmente. Eventualmente eu devo voltar a estudar implementação paralela de linguagens funcionais. Algum dia.

Resenhas

2006-03-03T08:34:00.000-08:00

Escrevi duas resenhas na Amazon.com, estão nas páginas dos respectivos livros:

Programming Language Pragmatics
Modern Compiler Design (por aqui traduzido com o título "Projeto Moderno de Compiladores")

Foi bom porque eu finalmente entendi os motivos porque eu não gosto do Projeto Moderno de Compiladores, e muito tem a ver com a péssima diagramação dele. E fica pior na versão traduzida, porque esse formato de livro-texto brasileiro (mais largo e alto que o americano) leva a linhas mais longas e páginas maiores, o que torna a leitura ainda mais cansativa.

Também por motivos de qualidade da tradução e diagramação eu vendi o meu exemplar nacional do Essentials of Programming Languages e comprei o importado. Bem melhor. Já o Organização e Projeto de Computadores: A Interface-Hardware Software eu comprei traduzido mesmo. Apesar de alguns deslizes e de não ser colorido (o original é preto, cinza e azul), a versão brasileira é muito boa.

Ainda sobre livros, tá faltando ou eu não encontrei um que seria "Assembly Intel x86 Moderno para Escritores de Compiladores". Todos os livros de assembly que eu vi têm alguma falha: ou são superficiais demais, ou são livros-texto e incluem até a parte 16 bits, ou usam uma notação maluca (o AoA de Randall Hyde) ou etc. Livros até sobre como gerar código para a JVM e o CLR .NET, mas não para a plataforma mais usada na atualidade. Que por sinal também é uma das mais complicadas para gerar código. O jeito por enquanto é ficar com os manuais da Intel e AMD.

E a AMD agora só tem no site os manuais da arquitetura AMD64. 32 bits morreu por eles. Bom, vou parar de reclamar.

Algumas notas soltas

2006-02-19T17:45:00.000-08:00

Apenas para registrar coisas que estive pensando hoje.

A questão é: o que é um pesquisador em linguagens de programação, o que ele deve resolver? A primeira pergunta não vai ter resposta aqui, mas a segunda remete ao conselho de Richard Hamming de sempre se perguntar qual é o problema mais importante na sua área; eu já pensei sobre isso algumas vezes, e quase sempre fico de postar os pensamentos aqui e não faço. Agora vai.

O papel da pesquisa em linguagens de programação é desenvolver novas formas de expressar a parte de software dos sistemas computacionais. Com a tendência do hardware se tornar mais genérico, o peso nos sistemas computacionais recai quase todo sobre o software; portanto, ganhos de produtividade nas linguagens de programação se refletem como melhorias na construção e manutenção de todos os sistemas computacionais futuros (e mesmo, graças a técnicas de análise, a sistemas legados). Ou pelo menos deveria ser assim. As coisas avançam na indústria no campo das linguagens, mas a inércia é considerável. De toda forma, acho que isso está mudando; a discussão não cabe aqui. O fato é que eu considero a pesquisa em linguagens como uma parte fundamental e praticamente central da computação; é o pólo ao redor do qual todas as sub-áreas relacionadas a software se acomodam. Mesmo que não seja assim que a indústria vê a coisa.

Quais são os problemas mais importantes em linguagens hoje? Pode-se dizer que concorrência, mobilidade e verificação (incluindo verificações de segurança, mas não restrito a isso) estão entre os principas. É interessante se concentrar nesses problemas hoje em dia.

Ao meu ver, um ponto importante com relação aos três problemas e com a própria natureza da programação de computadores é a questão dos efeitos colaterais. Efeitos colaterais devem ser evitados ao máximo e, quando isso não é possível, controlados. Linguagens imperativas cheias de estado se mostram cada vez mais problemáticas; toda análise que se faz de programas é complicada pela presença de efeitos colaterais arbitrários, e isso atrapalha tanto a concorrência quanto a mobilidade de código e a verificação (especialmente de segurança). Muita gente na indústria e pesquisa estão constatando a mesma coisa. Isso é uma prova que, assim como eu, muita gente acredita nos princípios da programação funcional; aliás, não só funcional, como de qualquer paradigma declarativo. A programação por restrições (constraint programming) é muito promissora para algumas aplicações.

O problema é similar à controvérsia do goto nas décadas de 70 e 80: o programador que pode usar gotos é mais "livre" mas seu código se torna mais difícil de ser entendido e, por contrapartido, analisado automaticamente. Algumas coisas eram mais fáceis, principalmente na década de 70, usando um goto ao invés das construções estruturadas. Com o desenvolvimento das linguagens em uma direção cada vez mais longe dos gotos, isso se tornou completamente irrelevante. É muito difícil, hoje, justificar a necessidade de usar um goto; surgiram algumas alternativas estruturadas e semi-estruturadas a ele, e a própria forma de pensar sobre software atualmente (que é, por bem ou por mal, a orientação a objetos) passa longe de saltos arbitrários.

Com efeitos colaterais é parecido. Reclamava-se que era muito mais complicado programar sem eles, e realmente era, se for considerado, por exemplo, o uso de continuações para modelar efeitos colaterais. Com o desenvolvimento de novas idéias, a situação foi melhorando: as mônadas em Haskell conseguem simplificar pelo menos os casos mais básicos, e em muitas situações escondem boa parte da complexidade envolvida. O problema é que ainda não dá para programar bem em Haskell sem entender as mônadas. E, sendo realista, mônadas são mais complicadas do que qualquer coisa que um programador médio queira entender.

Duas direções parecem possíveis: com o avanço das linguagens de programação e os sistemas relacionados, o aumento de produtividade pode ser suficiente para reduzir o número de programadores necessários. Isso causaria uma divisão parecida com a que ocorre na eletrônica: um pequeno grupo teria o conhecimento altamente especializado para programar componentes gerais, enquanto que a maioria apenas usaria esses componentes. Isso em parte já está acontecendo (vide linguagens de script e bibliotecas gigantescas) mas ainda não na escala desejada. A tendência histórica não parece apoiar a idéia que sobrarão poucos programadores: os ganhos de produtividade obtidos nas últimas décadas serviram para aumentar a demanda de software, e a complexidade do que é requerido, de forma que a demanda por programadores também acabou aumentando, ao invés de diminuir. Imagino que isso não mude tão cedo, com a necessidade cada vez maior de automatizar e informatizar. Parece que eventualmente o mundo inteiro será controlado, medido e modelado por software; como ainda estamos longe disso, a demanda só deve aumentar. Uma possibilidade é uma divisão de trabalho menos rígida, que acredito que é parecido com o que está acontecendo: a maioria programaria em linguagens de domínio específico, enquanto que os especialistas criariam as linguagens e o ferramental necessário. Idéia parecida com a Language Oriented Programming proposta por alguns, mas admitindo que nem todo mundo tem condições de criar linguagens efetivas, por mais que as ferramentas ajudem.

A outra possibilidade não é tão diferente: as idéias como mônadas e sistemas de tipos e efeitos podem ser refinadas e desenvolvidas a ponto que um programador possa usar efeitos colaterais (provavelmente não de forma tão livre como nas linguagens atuais) sem se dar conta nos detalhes que estão por baixo. Claro que alguns precisarão conhecer os detalhes para desenvolver os compiladores e projetar as linguagens, mas isso já acontece hoje. Em relação aos que trabalham programando, só uma minoria conhece em detalhes as técnicas envolvidas no projeto de linguagens e criação de compiladores.

É possível também que, assim como o advento da programação orientada a objetos tornou praticamente irrelevante a discussão de nível mais baixo sobre gotos, o uso cada vez maior de paradigmas declarativos (como a programação lógica e a programação por restrições) torne um tanto quanto irrelevante pensar em usar efeitos colaterais diretamente, exceto para uma pequena parcela de system programmers (sempre achei meio estranho traduzir isso). Isso depende do avanço das implementações para tentar garantir maior eficiência, mas também do avanço do poder computacional do hardware, que é o que tem, historicamente, tornado atrativas construções menos eficientes mas de nível mais alto. Se os processadores multi-núcleo realmente se tornarem dominantes, a simplicidade de modelos declarativos como a concorrência por passagem de mensagens e a programação por restrições pode desalojar de vez o estilo imperativo altamente dependente de efeitos colaterais.

Ora, os programadores costumam reclamar que é "difícil" pensar de maneira funcional (ou outro paradigma declarativo). Mas isso acontece somente porque eles foram treinados para usar efeitos colaterais. Da mesma forma, programadores que aprenderam a programar com muitos gotos tiveram problemas para passar à programação estruturada, e vários dos que aprenderam a estruturada sentiram o choque para mudar para a POO. O que interessa aos pesquisadores é o futuro, e para a indústria o importante é a produtividade; o paradigma no qual a maioria dos programadores é treinada hoje em dia tem algum peso na inércia total, mas isso pode ser mudado (vide as mudanças já ocorridas nessas poucas décadas de computação).

A questão que resta aí é quanto ao modelo de nível mais baixo. Lá no processador o modelo ainda é o da máquina de von Neumann: estado compartilhado e efeitos colaterais são essenciais. Não sei se isso pode mudar, mesmo que os paradigmas dominantes se tornem declarativos. Mas se isso acontecer a arquitetura dos processadores com certeza será influenciada.

Uma idéia interessante nesse sentido é tentar achar meios eficientes de definir construções fundamentais como mônadas. E isso tem uma intersecção com outros assuntos como Typed Assembly Language e Proof-Carrying Code. Tudo indica que as plataformas de software do futuro sejam cada mais virtuais, continuando o que já acontece hoje com a JVM e o .NET CLR. Podemos chegar a um ponto que praticamente todo código de aplicação rodando em uma máquina será código gerenciado por algum grande runtime. Isso abre possibilidades para usar linguagens intermediárias tipadas e proof-carrying code, além de ter plataformas virtuais que não sigam o mesmo modelo computacional do hardware. O CLR se torna cada vez mais "amigável" às linguagens funcionais, e a estratégia da Microsoft promete incluir os princípios funcionais cada vez mais no mainstream. Talvez não seja a melhor estratégia ter apenas poucas plataformas que tentam abarcar tudo, mas isso foi o que aconteceu com o hardware, principalmente hoje em dia, quando cada vez mais o mundo roda sobre a plataforma x86 (mesmo que nem sempre da Intel).

Resumindo: formalizar a concorrência e achar novas formas de expressa-la nas linguagens de programação é interessante e importante, assim como estudar efeitos colaterais, como controla-los e especifica-los. Técnicas formais que chegam aos níveis mais baixos, como Typed Assembly Language e Proof-Carrying Code, também são. São essas as coisas que me ocorrem quando eu penso na pesquisa. Concorrência agora pode se tornar central à minha dissertação, embora que obviamente em uma fatia bem mais modesta: algoritmos para coleta de lixo paralela. Mas estudar o particular é uma forma de observar o geral.

Nice quote

2006-02-17T18:40:00.000-08:00

To make a literary analogy, mathematics produces the equivalent of one-liners – equations that are pithy, insightful, brilliant. Computer science is more like a novel by Tolstoy: it is messy and infuriatingly complex. But that is exactly what makes it unique and appealing – computer algorithms are infinitely more capable of capturing nuances of complex reality in a way that pure mathematics cannot.

A entrevista inteira é interessante, ao menos para pensar sobre o assunto da natureza da ciência da computação. Via A Neighborhood of Infinity.

Velozes e Furiosas... aliás, Rápidas e Curtas

2006-02-13T07:30:00.000-08:00

Um post rápido só para tirar a poeira aqui.

Muito ocupado ultimamente, sendo compiladores um dos motivos. Livros, livros e mais livros. E ainda mais alguns livros. Mas calma, ainda não acabou. No final das contas é bom que eu releio e reviso muita coisa, além de ler muita coisa nova que eu já pretendia há tempos.

A pesquisa anda por aí também, mas não exatamente no mesmo lugar. Tentando desenvolver idéias e me concentrar em alguns pontos, ao invés de dispersar demais (que é o meu hábito).

Ironicamente, talvez o primeiro artigo com meu nome seja sobre teoria dos grafos. Mas não tô reclamando, se acontecer será muito bem-vindo.

Outra hora, dando certo algumas coisas e surgindo tempo, eu escrevo sobre as idéias e o desenvolvimento delas. Ou outro post meio inútil como esse.

Tony Hoare, um rapaz simples, um homem do povo

2006-01-11T22:16:00.000-08:00

Born in 1934, C. A. R. Hoare [...] graduated in Ancient Greats (Latin, Greek, Philosophy, and Ancient History) from Oxford University in 1956. While at Oxford, he also pursued extracurricular interests in the theory of probability and in mathematical logic[...]. Conscripted into the Royal Navy after his graduation, Hoare took the opportunity to study Russian, gaining an interpreter's qualification, and then spent a year at Moscow State University, attending lectures by the famous probability theorist A. N. Kolmogorov. At the end of his stay in Moscow, Hoare was asked to be an interpreter at an industrial exhibition. One of the exhibitors was the British firm Elliott Brothers, and Hoare was fascinated by the computer they had on display. [...]

In 1961 Hoare, now working for Elliott Brothers, attended a course on ALGOL 60 taught by [Peter] Naur, [Edsger] Dijkstra, and the British computer scientist Peter Landin. The course was a revelation. During it Hoare suddenly realized how to use ALGOL's elegant features to implement a new, fast sorting algorithm that he had thought up. Hoare's Quicksort, published in 1962, began to establish his reputation as a computer scientist.

Mechanizing Proof: Computing, Risk and Trust de Donald MacKenzie

Como programar em Java

2006-01-04T17:26:00.000-08:00

Na plataforma Java, digo, não na linguagem. E a minha resposta é: programando em Scala. É uma linguagem orientada a objetos e funcional, que mistura muito bem os dois paradigmas, gera código para rodar na máquina virtual Java e se integra facilmente com as outras partes da plataforma.

Scala tem funções como cidadãos de primeira classe da linguagem, polimorfismo paramétrico, uma espécie de híbrido de tipos algébricos e hierarquias de classes, tudo bem misturado e consistente. Tem atribuição e a parte imperativa também, de forma que é possível escrever código quase idêntico ao que seria em Java -- mas quem vai querer isso? O importante dessa decisão de projeto é a facilidade de usar classes Java em código Scala: é imediato e não requer nenhum processo, nada de marshalling, pré-processamento, nada. Não é Haskell (a maior falta são tipos de ordem superior; embora seja possível definir mônadas específicas, não é possível definir o conceito de mônadas) mas é muito melhor do que Java. A sintaxe C-like perde um pouco de concisão, mas foi uma decisão consciente para atrair programadores, e não chega a atrapalhar muito. Eu só acho estranho, depois de uns 2 anos programando em OCaml e Haskell, escrever um if sem then.

A partir de agora, sempre que eu precisar criar algum programa para a plataforma Java, será em Scala. Java não é uma linguagem ruim, só é extremamente chata. Sem graça. Além de muito prolixa.

(Na plataforma .NET eu usaria F#. Uma vantagem de F# é a sintaxe, mais agradável para meu gosto atual; uma desvantagem é que a integração com as classes da plataforma .NET é bem menos descomplicada que em Scala.)

Novos livros

2006-01-02T09:52:00.000-08:00

Engineering a Compiler

The Reasoned Schemer

darcs

2005-12-09T18:29:00.000-08:00

Pensei em comentar um pouco sobre o darcs, um sistema de controle de versão bem recente e elogiado, principalmente para reclamar, mas eis que o problema era de BIOS mesmo e agora isso ficou para trás. Mas ainda assim vou comentar um pouco.

Nos últimos anos surgiram vários sistemas de controle de versão FOSS que tentam substituir o CVS, o programa-padrão nesse domínio. Daí vieram o Subversion e o Arch, só para citar dois dos mais famosos. As falhas do CVS são bem conhecidas, sendo que uma particularmente chata é que ele não controla diretórios (apenas arquivos dentro de diretórios) e não trata muito bem arquivos que são renomeados ou movidos. Todos esses novos sistemas sanam este e outros dos problemas mais importantes.

O darcs tem alguns diferenciais, como ser um sistema distribuído. Cada cópia de trabalho é um repositório completo. Isso significa que você pode fazer tudo com o sistema mesmo sem estar conectado a um repositório central -- até porque não existe repositório central. Depois é só enviar os patches para o(s) outro(s) repositório(s) para sincronizar. E isso pode ser feito via SSH, ou email, ou você pode até levar o patch num disquete ou pendrive e aplicar manualmente lá. Muito mais prático que o CVS.

Existem mais duas diferenças que não aparecem muito para o usuário, uma importante, outra apenas interessante. A importante é que o autor do darcs elaborou toda uma teoria dos patches como modelo conceitual do sistema. Isso permite uma série de otimizações e uma visão integral do funcionamento do darcs em um nível mais alto, o que é muito bom. O autor diz ter se inspirado na mecânica quântica para elaborar a teoria, mas isso não vem ao caso. Em geral, os usuários não precisam aprende-la para usar o sistema, só para os usos mais avançados ou para quem pretende ler ou mexer no código. E aí vem a deixa para a segunda diferença: o darcs foi escrito em Haskell. Aliás, acho que foi a primeira aplicação feita em Haskell a "pegar" assim fora do universo das linguagens funcionais; inclusive já vi por aí gente instalando o GHC só para compilar o darcs. E David Roundy, o autor do darcs, já declarou que a linguagem favoreceu a concepção da teoria dos patches e do sistema todo.

Pode não ser uma killer application que vai tornar a linguagem famosa e popular, mas é uma demonstração de aplicação prática de uma linguagem funcional muito recente e das mais avançadas. Outra é o pugs, que eu já mencionei aqui.

Ubuntu, controle de versão e afins

2005-11-24T10:34:00.000-08:00

Uma nota mais administrativa, mas enfim.

Finalmente, após muito planejamento, substituí o servidor que cuidava aqui da sala da pós-graduação. É um Pentium II meio antigo, que estava rodando Windows XP muito mal, cheio de problemas e que caía constantemente. Instalei o Ubuntu 5.10, só o sistema básico para funcionar como servidor. Aproveitei e coloquei Apache, Zope, cvs e darcs, só por enquanto. Pensei em instalar Ruby on Rails também, para brincar um pouco, mas deixei para depois.

Instalar sistemas de controle de versão era importante. Estou trabalhando atualmente em 4 máquinas diferentes, e às vezes é complicado saber onde está a versão mais nova de algum programa ou texto (será que a versão mais nova está no pendrive? ou esqueci de copiar?). Primeiro instalei o darcs que é um novo concorrente na praça, feito em Haskell e muito elogiado por aí pela sua teoria dos patches. Instalei o cvs depois porque achei mais prático para outros alunos aqui que queiram usar controle de versão, já que é um sistema mais antigo, tem integração com Eclipse, ferramentas GUI interessantes como o TortoiseCVS e por aí vai.

Também coloquei o ubuntu rodando em mais duas máquinas aqui (sendo uma para meu uso). Até agora tudo muito bem, e sem dúvida ele é infinitamente mais prático de instalar que o Gentoo. A única experiência traumática parece ser fazer um dist-upgrade, coisa que ainda não tentei. No geral, é uma das distros linux que eu mais recomendo hoje em dia, uma que tem o poder da Debian mas muito mais facil de usar.

Sobre o darcs, comecei a usar já e estou mantendo alguns projetos com ele. Depois eu comento sobre minhas experiências.

Será?

2005-11-17T07:44:00.000-08:00

If I were a Springer-Verlag Graduate Text in Mathematics, I would be J.L. Doob's Measure Theory.

I am different from other books on measure theory in that I accept probability theory as an essential part of measure theory. This means that many examples are taken from probability; that probabilistic concepts such as independence, Markov processes, and conditional expectations are integrated into me rather than being relegated to an appendix; that more attention is paid to the role of algebras than is customary; and that the metric defining the distance between sets as the measure of their symmetric difference is exploited more than is customary.

Which Springer GTM would you be?
The Springer GTM Test

Brincando com Haskell, parte 1

2005-11-06T09:21:00.000-08:00

Estou experimentando agora com sistemas de inferência de tipos, começando com um Hindley-Milner clássico, escrevendo o código em Haskell. Claro que para experimentar eu precisava de uma linguagem funcional simples, mas desta vez resolvi não ficar apenas na sintaxe abstrata: criar um parser e coisa e tal para poder escrever programas num formato razoável. Isso me levou a usar o Parsec, biblioteca de combinadores de parsers. Já tinha ficado impressionado antes vendo alguns exemplos, mas nunca tinha usado de verdade. E, realmente, é muito bom de usar, pelo menos para uma linguagem simples. O trabalho é feito definindo parsers algebricamente, de uma forma que espelha quase perfeitamente a forma da gramática em BNF. A documentação no site também ajuda bastante, tendo exemplos e casos de uso interessantes. Nada de usar um processador separado para gerar um parser quase incompreensível.

Como um pequeno exemplo, aqui está a definição que analisa a expressão condicional:


conditional :: Parser Exp
conditional = do reserved "if"
              e1 <- expr
              reserved "then"
              e2 <- expr
              reserved "else"
              e3 <- expr
              return (If e1 e2 e3)

Isso significa que o parser vai procurar pela palavra reservada if, depois chamar o parser para expressões para analisar a expressão booleana do condicional, depois procura a palavra reservada then, e por aí vai. Outro exemplo interessante é um analisador parcial para expressões básicas (que podem aparecer como fatores de expressões com operadores):


baseExp :: Parser Exp
baseExp = letexpr <|> conditional <|> variable <|> numberLiteral <|> 
          booleanLiteral <|> parens expr
           "basic expression"

Isso mostra de maneira bem clara que uma expressão de base é uma expressão let, um condicional, uma variável, um literal (numérico ou booleano) ou uma expressão entre parênteses. Cada um desses como letexpr que são operados com <|> são parsers de algum tipo de expressão. O operador <?> permite que o parser seja descrito, para ajudar na composição de mensagens de erro significativas.

Notas sobre lógica e a correspondência Curry-Howard

2005-10-24T19:28:00.000-07:00

Todos fatos conhecidos, mas que eu estou entendendo um pouco melhor somente há pouco tempo. Senão vejamos: na lógica de primeira ordem a sintaxe é estratificada em duas camadas: termos e fórmulas. Os termos representam os valores sobre alguma estrutura sobre a qual se fala; as fórmulas tratam de propriedades sobre os termos. Pode-se interpretar a lógica intuicionista de primeira ordem no λ-cálculo tipado de primeira ordem: os termos são os valores (não necessariamente em sua forma normal, ou seja, não necessariamente avaliados) e as fórmulas são tipos, que são propriedades dos termos. Então um tipo é como se fosse um predicado sobre um termo, o que faz todo sentido. Isso é mais ou menos a essência da correspondência Curry-Howard.

Mas a coisa fica melhor. Na lógica de primeira ordem só podemos quantificar sobre variáveis, que são parte de termos. Na lógica de segunda ordem pode-se quantificar sobre predicados também. O correspondente no λ-cálculo é o Sistema F de Girard, que é um λ-calculo tipado de segunda ordem, no qual pode-se estabelecer abstrações de tipos e aplicações de tipos. Girard utilizou o Sistema F para estudar o PA₂, a aritmética de Peano de segunda ordem, e provar sua consistência. De forma similar temos a lógica de ordem superior e o Sistema F de ordem superior (Fω). A quantificação no caso da lógica é sobre predicados e predicados de predicados e por aí vai; no sistema Fω os tipos de ordem superior são como funções de tipos em tipos (no Sistema F de segunda ordem existem apenas funções de tipos em termos), em qualquer nível. Mais uma vez, Girard utilizou esse sistema para estudar o PA_ω, a aritmética de Peano de ordem superior, e provar sua consistência pela propriedade de normalização dos termos no sistema Fω.

Já na lógica de ordem superior a formulação mais utilizada é devida a Alonzo Church e, como esperado, envolve o λ-cálculo. É utilizado um cálculo tipado pois o cálculo sem tipos é inconsistente, graças ao paradoxo de Russell. Lógica de ordem superior também é utilizada como base para provadores de teoremas, por exemplo o sistema Isabelle/HOL. Um outro provador de teoremas famoso, o Coq, utiliza um cálculo baseado em tipos dependentes, que estabelecem uma conexão entre termos e tipos. Mas isso fica para outra hora.

Mônadas são valores

2005-10-08T12:32:00.000-07:00

Lendo uma série de artigos sobre mônadas (os de Philip Wadler, especificamente). Atualmente estou no "Imperative Functional Programming" de Peyton-Jones e Wadler. Esse trecho bateu com o que eu já tinha redescoberto recentemente:

Notice the distinction between an action and its performance. Think of an action as a "script", which is performed by executing it. Actions themselves are first-class citizens.

As ações a que ele se refere, obviamente, são valores monádicos.

Outra idéia importante é que mônadas não necessariamente precisam exprimir ação. No geral, são um mecanismo para capturar diferentes estratégias de computação. Por exemplo, listas podem ser encaradas como mônadas que refletem uma estratégia de computação baseada no uso de vários valores por expressão, ao invés de apenas um. Isso também pode ser interpretado como não-determinismo. Aliás, existe um exemplo bem interessante de não-determinismo expresso por mônadas em "Comprehending Monads", de Wadler. Mas tratar uma lista como mônada, sem efeitos colaterais impuros, é bem diferente da mônada IO, que delimita partes do código que são imperativos. E isso se reflete no fato que é possível sair de uma mônada de lista, mas nunca de uma imperativa como IO ou State.

Alguns comentários soltos

2005-09-24T11:59:00.000-07:00

Voltando a estudar e praticar Haskell, o que me fez voltar a ler sobre mônadas. Uma coisa que eu ainda não tinha entendido direito é que, apesar da aparência imperativa da notação usando do, um valor envolto em uma mônada é apenas um valor, não é a execução da ação em si. Algo tem que executar as ações. Minha intenção em estudar mônadas é entender suas relações com sistemas de tipos e efeitos, o que leva a regiões para gerenciamento de memória.

E por falar em Haskell, é interessante ver como DSLs como Fran (ou outras que utilizam a idéia da reatividade funcional) são expressivas e só são possíveis em Haskell. Elas utilizam exatamente o conjunto que distingue a linguagem: avaliação preguiçosa, type classes e mônadas.

Sim, também tenho lido sobre uso de código carregado dinamicamente em uma linguagem com verificação estática de tipos (Haskell, novamente), um interesse antigo pois tem tudo a ver com sistemas distribuídos e código móvel. O hs-plugins faz o possível mas algumas coisas ainda são impossíveis, e talvez menos flexíveis do que deveriam. Por exemplo, uma aplicação que tenha plugins deve definir a priori as interfaces que os plugins devem obedecer, algo similar aos pontos de extensão da plataforma Eclipse. Por que não ter plugins que não necessariamente sigam (ou nao estritamente) a API delimitada pela aplicação? O maior problema é, como verificar os tipos de um plugin arbitrário, o que já é significantemente difícil no cenário com uma interface definida. Uma idéia poderia ser usar proof-carrying code para isso, de fato um uso talvez simplório, mas realizável, da idéia. É uma das coisas que eu espero investigar em breve. E Typed Assembly Language é o futuro.

Pesquisa em linguagens de programação e espeficicações formais

2005-09-16T11:03:00.000-07:00

Ainda não veio a inspiração (ou foi a preguiça que não deu trégua) para escrever sobre a correspondência de Church-Turing. Enquanto isso, este post, já antigo, de Erik Meijer em seu blog e os comentários discutem muito bem sobre o uso de definições precisas da semântica de uma linguagem de programação. O ponto mais importante, na minha opinião, está nesse parágrafo de Erik:

Of course the question is why smart language designers do not write formal specifications, and why equally brilliant researchers do not cover the complete design of real languages. The simple, recursive, answer I believe is that despite decades of research (van Wijngaarden grammars, attribute grammars, denotational semantics, operational semantics, axiomatic semantics, VDM, ASF/SDF, theorem provers, abstract state machines, ...........................) we still lack the proper programming language to describe real programming languages at the right level of abstraction.

E é ecoado no comentário de Neel Krishnaswami:

Our formal descriptions don't evolve as quickly as our code, for reasons I don't really understand. Eg, SML has evolved much more slowly than Ocaml or Haskell have, AFAICT because it has a formal semantics and they don't. So when a change is made to Ocaml, the implementors don't feel obligated to redo all of the soundness proofs -- which is good, because the proofs are sufficiently unmodular that even small changes can involve lots of work to fix. (Bob Harper and Chris Stone complain about this problem in so many words in their type-theoretic semantics of SML.)

Por enquanto fiquemos com um pouco de Dó sustenido

2005-09-15T13:00:00.000-07:00

Aqui um post que eu escrevi no Googletron sobre as novas características que aparecerão na versão 3 da linguagem C#, que pelo jeito está praticamente se tornando objeto-funcional. I mean, inferência de tipos? Expressões lambda? (Inclusive sem inventar algum nome mais "marketeiro" para substituir "lambda").

Lembrando que C# já tem suporte a polimorfismo paramétrico desde a versão 2... ora, inventem logo uma versão puramente funcional do CLR. Haskell para as massas!

Promessas

2005-09-06T16:14:00.000-07:00

Ok, eu tinha ficado de publicar um artigo sobre prova de teoremas na programação aqui, há um bom tempo já. Mas vieram as provas de final de semestre, e vieram as curtas férias, e isso foi ficando para depois. Em breve a atividade no blog deve aumentar, aproveitando que as disciplinas acabaram e eu vou me dedicar mais à pesquisa. E o artigo prometido ainda vai aparecer.

Em breve

2005-08-03T12:38:00.000-07:00

Motivos de força maior (Jânio diria "forças terríveis") me impediram de postar ultimamente. Mas eu tenho pensado em um texto sobre programação e prova de teoremas. Espero mostrar que todo mundo que já programou em Java usou um provador automático de teoremas, mesmo que não tenha consciência disso. Isso nos levará em direção à correspondência de Church-Howard e algumas considerações defendendo a tese que programar é, basicamente, praticar uma forma de matemática construtiva. Ou quase.

Depois disso devem voltar mais alguns posts específicos sobre minha pesquisa atual e assuntos relacionados. Até.

Solução ?

2005-07-27T17:04:00.000-07:00

Nos últimos posts eu apresentei argumentos para sustentar a idéia que a engenharia de software atual é insuficiente (e na verdade mal merece o nome). Mas qual seria a solução então ?

A idéia é simples de conceber, embora não de realizar: colocar a atividade de criação de software em sólidas bases científicas, assim como as outras engenharias. Fazer com que um projetista de software não apenas desenhe diagramas bonitos com a última moda em confecção de diagramas, mas que também possa provar propriedades sobre o projeto dele, de forma a garantir que as especificações iniciais são satisfeitas. Especificações, aliás, que devem ser expressas formalmente também. Nesse ponto das especificações aparece uma crítica comum: provar que o programa obedece às especificações é inútil se estas não capturam os requerimentos reais do sistema. E como provar que as especificações capturam os requerimentos ? Esse é um problema complicado que poderia, em primeira análise, ser uma repetição do primeiro (coerência do software com especificações), mas a especificação é bem mais simples e de alto nível, o que ajuda a fazer a verificação.

Encontrar essas bases científicas não é coisa que se faz do dia para a noite: os métodos formais atuais ainda são inadequados para as escalas de sistemas construídos. Mas, ao invés de abandonar a idéia de vez, me parece mais lógico trabalhar para melhorar os métodos até que eles se tornem suficientes. E o interessante é que isso já está acontecendo, como eu exemplifiquei neste post. Minha crença é que essa tendência deve continuar, mas ela aconteceria mais rápido se a indústria, como um todo, se preocupasse mais com a qualidade. E essa falta de preocupação vem principalmente da tolerância dos clientes. A verificação que se faz hoje em dia é através de testes, mas todo mundo sabe que testes não podem provar a ausência de erros, apenas sua presença; você confiaria sua vida num sistema que foi apenas testado ?

Em uma de suas frases famosas, Alan Perlis disse "I think that it's extraordinarily important that we in computer science keep fun in computing", com o que eu concordo plenamente. A formalização não vai tornar a criação de software mais chata; programação como artesanato e atividade técnica vai continuar existindo -- eu mesmo junto umas linhas de código para fazer algo que eu quero (ou por diversão) de vez em quando, sem grande preocupação com corretude, e não pretendo deixar de fazer isso. Mas sempre que for necessário um nível de confiabilidade maior, teremos ferramentas para garantir que os programas se comportarão como esperamos.

E isso, por incrível que pareça para quem está muito acostumado com software, é apenas o mínimo que as pessoas costumam exigir de qualquer artefato... que ele funcione.

Mais sobre lógica e formalização

2005-07-27T16:40:00.000-07:00

During the last 10 years we have seen a number of failures in these kind of systems. I just mention four well-known examples.

The first example is the Ariadne rocket, a common European space project. The rocket exploded a few seconds after takeoff, due to a software error.

Another well known example is the baggage-handling system of the Denver International Airport. Errors in the software that controls the system required postponement of the official opening (Oct. 1993). By June 1994 the $193 million system was still not functioning, but costing $1.1 million per day in interest and other costs. In early 1995 a manual baggage system was installed in order to open the airport.

Some cancer patients in the USA have received fatal radiation overdoses from the Therac-25, a computer-controlled radiation-therapy machine.

The last example is the Sizewell B nuclear power plant in England. Some years ago it was decided to test the subsystem which is used to close down the reactor if a dangerous situation occurs. The results were not comforting: the software failed almost half of them. They were not able to find the errors in the 100,000 lines of code. Instead, they reduced the overall expectation of the plant's performance from one failure every 10,000 years to one every 1,000 years.

Bengt Nordstrom, Constructivism: A Computing Science Perspective

Esses são exemplos de sistemas críticos, nos quais foi investido muito dinheiro e que mesmo assim foram fracassos consideráveis. Não são os únicos exemplos: Larry Paulson menciona, nas notas de um de seus cursos, um sistema de controle de ambulâncias na Inglaterra que causou a morte de vários pacientes por atraso de atendimento. Tendo em vista isso, é fácil concordar que essa tal engenharia de software deixa muito a desejar. Será que eu sou o único a achar loucura confiar em sistemas assim ?

O trecho é de uma palestra proferida por Bengt Nordstrom em um evento no Vaticano. Sigam o link e leiam a coisa toda, é interessante.

Continuando a discussão

2005-07-16T09:47:00.000-07:00

Depois do post passado, Herval escreveu no Geek4Life um post sobre "computação úbiqüa", computação pervasiva ou como queira chamar. Por acaso, essa é justamente uma das minhas maiores preocupações com a questão de computação confiável; quando se tem software em todo lugar, em todos aspectos da vida, é de extrema importância que tudo funcione bem. Então escrevi um comentário:

Relacionado ao meu post sobre engenharia de software, não dá medo usar software em todos esses lugares, considerando a qualidade média do que se produz hoje ? :)

Ao que Herval respondeu:

Acho que desenvolvimento de software hoje é meio que um artesanato com gerência e prazos.

ps.: software embarcado, imho, é uma das áreas menos problemáticas da tecnologia (talvez pelo pequeno tamanho da coisa). Meu celular costuma travar bem menos que meu PC. Meu cartão de crédito com 'chipinho inteligente' nunca travou durante uma compra ou autorização de crédito. Só não sei como vai ser quando a casa toda começar a ficar automatizada e inteligente... :)

E eu, por fim, fiz como resposta um outro comentário que tem mais alguns exemplos:

Sim, concordo que software embutido dá muito menos problema, não por que sabemos fazer esse tipo de software melhor, mas porque ele é menos complexo. Como você disse, seu celular "trava bem menos" que o PC, mas ainda trava :)

E o problema é, cada vez mais nossas vidas vão dependendo de software, em muitos aspectos. Esse nível de qualidade é claramente inaceitável quando coisas mais críticas começam a depender de software que é essencialmente imprevisível.

Uma coisa que pouca gente tem idéia é que desde o fiasco do bug de divisão do Pentium, a Intel investe pesado em métodos formais para verificação do projeto dos seus chips; as concorrentes, obviamente, seguiram a mesma direção e hoje em dia nenhum chip sai da sala de projeto para a planta da fábrica sem ter sido verificado formalmente, com provas matemáticas que ele funciona como especificado.

Outro ponto onde métodos formais são usados corriqueiramente é no projeto de protocolos. Um conhecido meu está trabalhando na Microsoft Research atualmente nesse ramo.

E por falar em Microsoft, existe uma ferramenta desenvolvida internamente pelo pessoal da MSR que verifica drivers. Usa essas técnicas de métodos formais e verificação de modelos (model checking) e foi escrita em OCaml.

Esses exemplos seriam quase impensáveis há meros 10 anos. Imagine o que pode acontecer 10 anos para frente...

Lógica, computação e engenharia de software

2005-07-12T15:41:00.000-07:00

Existe uma verdade básica sobre engenharia de software: não existe engenharia de software. Não no sentido das outras engenharias; o que se rotula de "engenharia de software" hoje em dia é parte gerência de projetos, parte coleção de métodos ad hoc para tentar assegurar que as coisas continuem nos trilhos. E os métodos frequentemente falham.

Por outro lado, vinda lá da década de 60, existe a idéia de escrever provas matemáticas de corretude de programas. O assunto foi exaustivamente pesquisado na época, mas logo se viu que o esforço necessário era muito alto para programas não-triviais. As demandas econômicas e a expectativa relativamente baixa dos clientes acabaram impulsionando a atividade de criação de software como um artesanato ao invés de engenharia. E esta é, mais ou menos alguns detalhes, a situação até hoje. Existe uma legião de "programadores" profissionais com formação deficiente, e mesmo muitas universidades que oferecem cursos de ciência da computação se contentam em dar um verniz teórico muito superficial, acompanhado por incontáveis horas de treinamento vocacional em Java ou qualquer que seja a linguagem da moda no momento.

O resultado é visível: bugs e falhas de segurança permanecem abundantes mesmo em software considerado de "alta qualidade". Os clientes se acostumaram a isso como se fosse a única forma, mas não precisa ser assim. O mesmo cliente que simplesmente balança a cabeça ao ver um bug do Word ou uma falha de segurança no seu Windows voltaria correndo para a concessionária devolver um carro que apresentasse o menor defeito. E software livre, sinceramente, não resolve este problema: eu uso Linux diariamente, em casa, mas o número de bugs e incompatibilidades nas aplicações é considerável, embora a base do sistema operacional seja sólida.

Baixas expectativas + altíssima demanda + profissionais incompetentes = software de má qualidade.

Mas as outras engenharias não nasceram da forma que são hoje; elas primeiro passaram por um período de ensino vocacional e técnico antes de chegarem ao estágio atual de assumir uma base científica. O cálculo, a análise matemática, se tornou a base das engenharias entre os séculos XIX e XX.

Pode-se ter esperança, então, que a engenharia de software siga o mesmo caminho. A lógica matemática se mostrou, nestas décadas de desenvolvimento da computação, ser uma base extremamente adequada para a atividade. Por que não dizer que a lógica está para a engenharia de software assim como a análise está para as outras ? Por que não basear a criação de software em uma fundação científica sólida ? Os problemas de gerenciamento de projetos vão continuar existindo, claro, como existem nas outras engenharias. Mas pelo menos quem precisa criar software que funcione terá um conjunto de métodos para garantir que as especificações são satisfeitas, assim como um engenheiro civil garante que uma ponte sustenta uma carga de até X toneladas, mais ou menos um porcentual de erro conhecido e controlado.

Ao ler este artigo de John Allen, eu tive vontade muitas vezes de simplesmente balançar a cabeça em concordância; os argumentos dele sintetizam muito do que eu já acreditava sobre o assunto. A teoria está se tornando cada vez mais relevante, embora a maioria dos praticantes ainda não se dê conta; por exemplo, a adição de genéricos em Java utiliza partes muito avançadas e recentes da teoria dos tipos (quantificação limitada de tipos polimórficos, alguém já ouviu falar?). Mesmo que o resultado não tenha sido excelente, a linguagem foi aumentada de forma significativa sem quebrar a compatibilidade. Esse tipo de cirurgia em linguagens já existentes há anos é quase impossível de ser feita sem deixar alguns efeitos colaterais. E quem fez isso ? Um grupo de teóricos conhecidos, entre eles o famoso Philip Wadler.

A Microsoft, por sua vez, emprega uma verdadeira legião de pesquisadores em linguagens de programação, alguns dos quais trabalharam e ainda trabalham em várias extensões para o CLR (o runtime da plataforma .NET) e para a linguagem C#. A extensão do CLR para usar genéricos, por exemplo. Mas existem várias outras coisas sendo feitas.

A questão é quando a teoria e o rigor vão atingir o Joe-Sixpack-Programmer, o programador comum que está "nas trincheiras". Isso eu não sei, mas desconfio que quem quiser trabalhar no ramo daqui a uns 20 anos deve se preparar para aprender uma boa quantidade de matemática, especialmente lógica...

Type-Based Analysis and Applications

2005-06-26T09:26:00.000-07:00

Artigo de Jens Palsberg

Um survey paper que apresenta uma visão geral da área de análises estáticas de programas baseadas em tipos. Após introduzir o assunto e definir análise baseada em tipos (uma análise baseada em tipos assume que o programa é aprovado pelo verificador de tipos, e a análise toma proveito deste fato), o artigo mostra um exemplo simples de análise para determinação do fluxo de controle, primeiro usando um sistema que não se baseia em tipos (0-CFA), depois três técnicas baseadas em tipos. Neste exemplo as análises baseadas em tipos são divididas em sistemas de tipos e efeitos e tipos-como-discriminadores.

A próxima seção discorre sobre as vantagens das análises baseadas em tipos, resumidas nos tópicos simplicidade, eficiência, corretude e competitividade (com outras formas de análise estática). Em seguida são dados exemplos de várias ferramentas e técnicas já desenvolvidas utilizando análise baseada em tipos, e uma breve seção sobre outros tipos de análises já experimentadas. Um comentário interessante é o que diz respeito às diferenças entre as ferramentas implementadas e as técnicas pesquisadas: a maioria das ferramentas usa a técnica tipos-como-discriminadores, que parece mais simples, enquanto a maior parte da pesquisa se concentra no uso de sistemas de tipos e efeitos. A sugestão é que mais sistemas práticos devem ser formalizados, e mais sistemas pesquisados devem ser implementados.

Das aplicações apresentadas duas bem interessantes e que eu já estava de olho são gerenciamento de memória e detecção de condições de corrida em sistemas concorrentes. Por que não pensar em gerenciamento de recursos baseados em tipos ? Análise de efeitos colaterais me parece interessante também, principalmente para o projeto de linguagens de programação. Nesse sentido, é uma boa ver o artigo de Wadler, "The Marriage of Effects and Monads".

Palsberg mantém um site sobre o assunto.

Gerenciamento de recursos em sistemas distribuídos

2005-06-22T19:00:00.000-07:00

Preciso elaborar um projeto de pesquisa para dar entrada na PROPESQ que pode ser aproveitado como o projeto da minha dissertação, e aí eu já aproveito e apresento isso como planejamento na disciplina de metodologia.

O ponto de partida é usar os estudos sobre gerência de memória e tentar generalizar para gerência de recursos em grids e clusters. Eu prefiro enfocar nos primeiros. O interessante é que tem muito espaço para explorar e tentar técnicas avançadas: tipos lineares, tipos dependentes, etc etc.

Espero que saia um bom projeto daí.

Comparação, round 2

2005-06-15T10:27:00.000-07:00

Para tirar um pouco da poeira aqui, vão os números finais da comparação informal C versus OCaml.

Recaptulando: eu precisei alterar os algoritmos de gerenciamento de memória de um interpretador de uma linguagem funcional simples. A estrutura do programa é a seguinte:

um frontend traduz o programa fonte em uma estrutura de grafos; aqui estão o lexer e o parser;
essa estrutura é compilada para um grafo de combinadores básicos (SKI);
o grafo de combinadores é otimizado para usar os combinadores de Turner;
o grafo é avaliado (reduzido), efetivamente executando o programa fonte;
o runtime consiste de algumas funções pré-definidas e um coletor de lixo modular, que deve usar diferentes estratégias (mark-scan, coletor de cópia ou contagem de referências)

O interpretador original tinha sido escrito em C. Não muito bem, diga-se de passagem. Quando eu tentei alterar o que eu queria, core dumps e ponteiros nulos pularam de todos os recantos escuros para me atingir. Em pouco tempo descobri o modo atroz que o programa tratava os ponteiros, e decidi que demoraria muito consertar. O melhor seria fazer de novo. Então decidi fazer em OCaml, depois de ver que Haskell não seria legal (vide posts anteriores).

Há umas semanas isso ficou pronto. Funcionando melhor que a versão C, e feito em aproximadamente um mês de trabalho. Os resultados final da contagem de linhas:

C - 11486 linhas de código
OCaml - 1964 linhas de código

Ou seja, o programa em C é uma ordem de magnitude maior. Bem, a comparação não é completamente justa por um motivo: o programa C inclui lexer e parser, enquanto que o similar OCaml trata diretamente com uma sintaxe abstrata; faltaria implementar um frontend que traduzisse da sintaxe concreta para a abstrata. Para deixar a história um pouco mais justa: a parte do frontend no programa em C usa umas 2 mil linhas; mesmo que fosse retirada, ainda seria uma economia de quase 5 vezes. Mas recentemente eu implementei um frontend simples em SML; acredito que para a linguagem em questão, e usando OCaml, não seria muito diferente: lexer + parser em 200 linhas de código, apenas.

Características principais em OCaml que ajudaram a fazer tanta diferença: pattern-matching em estruturas de dados, funções de ordem superior e tipos de dados algébricos.

Análise baseada em tipos

2005-05-28T09:25:00.000-07:00

Da idéia de fazer gerenciamento de memória e gerenciamento de recursos baseados em tipos, generalizando um pouco, aparece a idéia de análise de programas baseada em tipos. Resumindo, é analisar certas propriedades de programas através dos tipos de dados empregados, possivelmente em conjunto com análise de fluxo de controle e de fluxo de dados. O gerenciamento de memória baseado em regiões é um exemplo de análise baseada em tipos, onde o compilador procura identificar os objetos que têm tempo de vida limitado a algum escopo e os aloca em uma disciplina de pilha.

Agora achei uma página bem interessante para pesquisar sobre o assunto: Type-Based Analysis and Applications.

Vamos ver o que vai sair.

Comparação

2005-05-26T20:34:00.000-07:00

Há algum tempo terminei de reescrever o programa de teste dos algoritmos de contagem de referências (como mencionado em outro post); a versão anterior era escrita em C, a atual foi escrita em OCaml.

Claro que eu já vinha percebendo que a nova versão era mais compacta que a anterior, mas só para ter uma idéia eu comparei o número de linhas de código apenas na parte do interpretador (responsável por reduzir os grafos e obter os resultados dos programas). O Resultado:

Versão anterior (C): 1600 linhas de código
Versão atual (OCaml): 200 linhas de código

E não é manipulação: essas 200 linhas de OCaml fazem exatamente o mesmo, nada menos, que as 1600 linhas de C. Além do poder de expressão da linguagem, a tarefa também é bem adequada à linguagem: a família ML se dá muito bem para a escrita de compiladores e interpretadores de linguagens de programação. E uma coisa que ajudou muito a reduzir o tamanho foi utilizar funções de ordem superior. Functional programming rules.

Depois eu pretendo levantar o tamanho completo das duas versões e postarei aqui.

Gerando texto

2005-05-05T18:36:00.000-07:00

Na última parte da disciplina de Métodos Matemáticos, estudamos processos aleatórios e técnicas relacionadas à teoria das probabilidades. As tarefas foram preparar seminários demonstrando aplicações dos tipos de processos aleatórios estudados.

Para demonstrar cadeias de Markov, eu escolhi uma aplicação na geração de textos aleatórios. É algo que eu vi há algum tempo e achei interessante, mas não sabia como funcionava; quando estudei sobre o assunto juntei as idéias e pensei nisso: fazer um programa que gera textos, a partir de um outro texto que serve de base.

É como aquela história, junte alguns macacos digitando aleatoriamente e, dado tempo suficiente, devem surgir até as obras completas de Shakespeare :) Aliás, os macacos fariam toda a Biblioteca de Babel, mas isto é outra história.

Enfim, para quem se interessar, aqui está a apresentação (PDF, PPT) e o programa utilizado.

Um exemplo de texto gerado com base em Dom Casmurro, de Machado de Assis, está neste post do outro blog.

Sobre software

2005-04-28T19:03:00.000-07:00

The problem is that software is different from other merchandise. Computer programs are the most intricate, delicately balanced and finely interwoven of all the products of human industry to date. They are machines with far more moving parts than any engine: the parts don't wear out, but they interact and rub up against one another in ways the programmers themselves cannot predict.

James Gleick, Chasing Bugs in the Electronic Village

Gleick é jornalista científico, autor do premiado livro Caos - A Criação de uma Nova Ciência, entre outros.

O destino de Perl 6

2005-04-21T17:49:00.000-07:00

Às vezes as coisas tomam um rumo engraçado: há séculos que a comunidade Perl promete a versão 6 da linguagem, e que ela vai ser a melhor coisa desde pão fatiado. Enquanto isso, a maior parte do desenvolvimento se arrasta interminavelmente no trabalho com a VM Parrot, e nada de ter um compilador disponível para Perl 6. E isso porque a nova versão foi anunciada há uns 4 anos...

Aí um cara teve a idéia de fazer um protótipo do interpretador. Escrevendo em Haskell. Aí começaram a aparecer hackers tanto da comunidade Haskell quanto da comunidade Perl interessados em ajudar e, em menos de dois meses, existe um protótipo disponível. Ele se chama Pugs. O progresso tem sido incrivelmente rápido, e pelo andar da carruagem eu não duvido nada que o Pugs, que começou como um projeto de uma pessoa só (Autrijus Tang) e totalmente sem o apoio da equipe Perl 6, seja promovido a oficial. Isso acontecendo seria uma ótima notícia para Haskell, que ganharia popularidade em uma comunidade mais mainstream. Mas eles provavelmente reescreveriam o interpretador em C, aos poucos.

Tipos e regiões

2005-04-12T10:25:00.000-07:00

No embalo dos estudos sobre garbage collection, estou estudando gerenciamento de memória baseado em regiões. E teoria dos tipos também. A idéia é tentar generalizar algumas técnicas relacionadas a regiões e pensar em gerenciamento de memória baseado em tipos (type-directed memory management). Não sei se vai sair algo daí, talvez nada, talvez minha dissertação, mas é uma investigação. Veremos.

Redução de grafos de combinadores e outros efeitos colaterais

2005-04-12T10:16:00.000-07:00

A atividade agora é implementar uma máquina de Turner de redução de grafos de combinadores para implementação de linguagens funcionais. O objetivo real não é implementar linguagens funcionais, até porque uma máquina de Turner pura é uma tećnica muito antiga, mas observar o comportamento de várias estratégias de garbage collection. E nem é uma implementação nova, mas uma reimplementação, porque isso já existia mas numa versão completamente horrenda, em C. É a versão que veio direto do poço da menina de O Chamado, e eu estou tentando envia-la de volta ao limbo.

A nova versão é em OCaml, claro. Pensei em fazer em Haskell mas como uma parte do programa simula um heap imperativo, isso só me deixaria duas opções: fazer tudo de forma funcional, o que seria extremamente ineficiente; ou espalhar mônadas na maior parte do programa, o que não agrada muito meu senso estético. Nesse caso, as características interativas em OCaml resolvem tudo de forma simples e elegante, logo é a ferramenta mais adequada para a situação.

Ah, e o coletor de lixo usa contagem de referências. Por incrível que pareça. Mas as técnicas utilizadas permitem coleta de ciclos e tudo, embora eu ainda não veja muitas vantagens com relação a utilizar um coletor de cópia generacional, ou as abordagens híbridas comuns atualmente.

Há quase 30 anos...

2005-03-23T08:44:00.000-08:00

Dijkstra advertia, no seu livro A Discipline of Programming:

Historically speaking, this last aspect, viz. the fact that programming languages could be used as a vehicle for instructing existing automatic computers, has for a long time been regarded as their most important property. The efficiency with which existing automatic computers could execute programs written in a certain language became the major quality criterion for that language ! As a regrettable result, it is not unusual to find anomalies in existing machines truthfully reflected in programming languages, this at the expense of the intellectual manageability of the programs expressed in such a language (as if programming without such anomalies was not already difficult enough!).

CiteULike

2005-03-19T22:27:00.000-08:00

Sitezinho útil esse CiteULike.

Por falar no assunto, aqui vai a minha página lá.

Wadler

2005-03-16T07:25:00.000-08:00

Nao "Linkei" para o blog de Philip Wadler antes. O blog é principalmente sobre Links...

Concorrência, round 1

2005-03-05T13:32:00.000-08:00

Lendo os capítulos do Theories of Programming Languages de John Reynolds que tratam de concorrência, é interessante ver como a característica imperativa complica ainda mais as coisas que já são complicadas nessa área. No caso, a concorrência por variáveis compartilhadas, que é o paradigma mais utilizado hoje em dia, graças às threads popularizadas pela linguagem Java. Supostamente mais eficientes, mas são uma grande bagunça para trabalhar.

Uma coisa que me ocorreu: quando os modelos formais para uma linguagem ou técnica se complicam, é um sinal que é difícil raciocinar direito sobre ela. Dijkstra basicamente resolveu isso de uma vez por todas no caso do goto e da programação estruturada; ocorre uma simplificação no modelo conceitual que ajuda a concepção de sistemas formais, mas isso também se reflete em um modelo mental mais simples para os programadores.

Com o estado explícito acontece a mesma coisa. As técnicas de programação modular e orientação a objetos não são formas de limitar o escopo das alterações de estado ? Dessa forma, o estado explícito fica um pouco mais contido, mais sob controle, mas ainda não totalmente. Uma linguagem funcional tem uma semântica formal muito mais simples que uma linguagem imperativa equivalente; isso se reflete na forma de pensar, e também nas ferramentas que manipulam código, incluindo aí compiladores.

Ah, e um dos engenheiros importantes da Adobe reconhece que 70% do código de interface usado hoje em dia (na Adobe) poderia ser declarativo. E ele postula que a porcentagem seria aproximadamente a mesma no resto da indústria.

Com isso e projetos como Links, e como aparentemente a indústria está acordando do mito da orientação a objetos como panacéia, será que a programação funcional vai pegar ?

Olhando por aí...

2005-02-28T17:15:00.000-08:00

O blog do Google.

A página de Steven Pinker.

Uma matéria no MathWorld sobre os testes de aptidão para candidatos a um emprego no Google.

Um artigo antigo de Bill Joy na Wired sobre o avanço da tecnologia e uma possível extinção da raça humana.

Um ensaio de Thomas Pynchon sobre os "Luddites" (existe tradução para o termo?).

Connection Machine

2005-02-26T19:04:00.000-08:00

Tentando reduzir a pilha de leitura, terminei hoje o The Connection Machine de Daniel Hillis. A connection machine é um misto de computador maciçamente paralelo e "memória ativa", no sentido que apesar da máquina ter poder de processamento, ela não é um sistema computacional completo; é preciso um computador host para comandar a máquina, que fica funcionando praticamente como uma memória. De qualquer forma, é uma arquitetura completamente diferente das máquinas de von Neumann que usamos até hoje.

O livro é baseado na tese de doutorado de Hillis no MIT; não sei o quanto mudou da tese para o livro, porque o texto em geral entra em poucos detalhes para uma tese (na minha opinião). O mais interessante é o primeiro capítulo, onde ele explica as motivações para fazer uma máquina dessa forma, a idéia principal sendo replicar o modelo de processamento do cérebro humano: ao invés de ter um grande processador central, ter milhares, ou talvez milhões, de pequenos processadores simples. Além disso, se aproveitar do fato de que processadores e memória hoje em dia são feitos do mesmo material para "esquecer" a barreira que os separa na arquitetura tradicional de von Neumann. Assim, o componente principal da máquina é uma célula processador/memória, que é agrupada pelo programador em "estruturas de dados ativos", ou seja, estruturas que possuem o próprio poder de processamento. O processamento não está apenas nas células em si, mas também na comunicação (ou conexão) entre elas; daí o nome "máquina de conexões".

Os capítulos seguintes tratam de como programar a máquina (usando um dialeto Lisp), considerações sobre o projeto de uma máquina real seguindo esses princípios arquitetonicos, alocação de memória e uma visão geral sobre o protótipo da máquina que estava sendo construída na época. Acho que faltaram mais detalhes nesses capítulos, exceto o sobre programação. O último capítulo é um sermão confuso sobre como as ciências da computação deveriam se parecer mais com a física; não entendi muito bem onde o autor queria chegar, mas não concordo com a maioria do que entendi. Esse capítulo provavelmente foi resultado da influência de Richard Feynman sobre o pessoal da Thinking Machines (a empresa criada por Hillis para construir e vender a Connection Machine).

Enfim, o mercado dos supercomputadores afundou, a Thinking Machines foi pro saco, e a Connection Machine não existe mais. Fico pensando se essa arquitetura era realmente vantajosa em relação ao que ainda usamos hoje em dia; se sim, porque ninguém mais tentou algo do tipo. Parece que vivemos condenados à arquitetura de von Neumann, criada quando os computadores eram feitos com válvulas e memórias de núcleos magnéticos. Uma arquitetura que, por sinal, favorece as linguagens imperativas... as pessoas acham que a computação, como um campo do conhecimento humano, avança muito rápido; eu já acho, às vezes, que ela avança devagar demais.

Aliás...

2005-02-11T21:54:00.000-08:00

Qualquer pessoa aprende em poucos minutos o que é um isomorfismo. O nome parece feio mas a idéia é simples, basta explicar de uma forma adequada ao contexto. Pouca gente vai absorver uma definição formal: "dado um morfismo f de A para B, diz-se que f é um isomorfismo se existe um morfismo g de B para A tal que g o f = I(A) e f o g = I(B)".

A notação matemática, assim como o jargão especializado e convenções de qualquer área, é ao mesmo tempo uma poderosa ferramenta de comunicação e uma ótima forma de esconder das pessoas "de fora" o significado do discurso.

O que é "natural" ?

2005-02-11T21:24:00.000-08:00

Estou lendo o "Conceptual Mathematics: A First Introduction to Categories" de Lawvere e Schanuel; postarei uma resenha depois, mas em suma o livro tem a intenção de ensinar teoria das categorias para qualquer pessoa que tenha tido uma exposição mínima às idéias da teoria dos conjuntos e funções, incluindo aí gente do ensino médio. É uma exposição totalmente voltada para as categorias, desde o começo, com muitos exemplos ilustrativos que ajudam muito na formação de uma intuição sobre o assunto. Na minha opinião muitas idéias do livro poderiam ser aproveitadas para reformulações futuras dos cursos de matemática no ensino básico, mas aí é história para outro dia.

O que eu achei interessante é que na discussão sobre isomorfismos os autores mencionam os conceitos primitivos de contagem (coisa que eu já considerei muito, principalmente quando estudava sobre Cantor, diagonalização e álgebra transfinita), e chamam a atenção para algo que eu não tinha pensado: isomorfismo é o conceito primitivo, número é o conceito abstrato derivado dele. O engraçado é que se você chegar para alguma pessoa na rua falando sobre isomorfismo, é capaz dela sair correndo com medo, ou ficar olhando pra você estranho, pensando se foi um xingamento. Mas número todo mundo conhece, todo mundo sabe.

Pra quê eu comentei isso tudo mesmo ? Ah, sim, para falar sobre linguagens de programação. De vez em quando aparece alguém que fala que "o estilo interativo é mais natural para as pessoas", afirmação puramente baseada nos seus próprios pré-conceitos: claro, para qualquer programador que tenha sido educado em um paradigma imperativo, linguagens imperativas parecem mais naturais. Não necessariamente que seja mais natural do que uma linguagem funcional para alguém que nunca aprendeu nada sobre programação. O exemplo mostra que algumas idéias que parecem mais 'complicadas' ou 'abstratas' são, na verdade, mais fundamentais, por sua própria generalidade.

Links e a volta dos que não foram

2005-02-02T11:44:00.000-08:00

O projeto Links pretende criar uma nova linguagem funcional, voltada para aplicações Web. À frente estão Philip Wadler e outros nomes importantes (Xavier Leroy, Benjamin Pierce, Simon P-J).

Wadler explica melhor do que eu. Vejam a introdução e os slides, ou antes, veja a mensagem introdutória no newsgroup comp.lang.functional.

Mas a idéia de ter uma linguagem puramente funcional largamente usada é muito interessante, e pode ajudar a mudar algumas coisas nessa indústria. Sem falar que o projeto promete trazer inovações interessantes, numa linguagem que deve misturar aspectos de ML e Haskell. Mais ou menos como seria minha linguagem dos sonhos atualmente.

(Ah, e o artigo que ele cita sobre efeitos e mônadas é o primeiro nesta página)

Compiladores

2005-02-01T06:53:00.000-08:00

Primeiro estava olhando a documentação do projeto Tree SSA do GCC, que consiste na geração de código na forma Static Single Assignment para o suporte a passes de otimização. O interessante é que a árvore SSA é processada sem efeitos colaterais; ou seja, é uma parte funcional do compilador GCC que está entrando em operação agora nas versões a partir da 3.4. Parece que o mainstream está aprendendo algo com a comunidade funcional.

E por falar em GCC, descobri que eles estão com um Wiki, incluindo informações sobre a estrutura do compilador e outras informações interessantes.

E sim, ainda estou com meu projeto de compilador. Terminei o parser, tarefa mais agradável do que eu esperava, já que o MLYacc é menos "imperativo" que o ML-Lex; agora estou fazendo parte da análise semântica, mais especificamente a verificação de tipos. Nada difícil, nem inferência de tipos tem, mas é meio trabalhoso. A análise semântica trabalha em cima da árvore sintática gerada pelo parser, e aí é só fazer um punhado de funções recursivas e tá tudo resolvido. Quando isso estiver terminado, vai ser a vez da geração de código intermediário. Daí pra frente, não sei se vou ter paciência para fazer geração de código nativo não; há muito o que fazer e o tempo é curto.

Em breve: semântica e formalismos para concorrência.

Novas arquiteturas

2005-01-25T16:46:00.000-08:00

Eu comecei lendo comentários no LtU sobre a nova "arquitetura celular" que o trio Toshiba/IBM/Sony está desenvolvendo para uso no Playstation 3. Daí segui para a análise desta proposta (mas lendo as observações no ars technica). Então surgiu um link para um artigo sobre o conceito da ISA (Instruction Set Architecture) e suas tendências atuais.

Tudo muito interessante; e juntando com o advento dos processadores de múltiplos núcleos (multicore), há muito o que se pensar sobre as arquiteturas do futuro, e como isso deverá afetar o lado do software.

Sofrendo com o ML-Lex

2005-01-09T11:55:00.000-08:00

Ok, como eu disse, estou brincando um pouco com compiladores; fazendo um compilador para uma linguagem pequena com sintaxe parecida com ML em duas versões: uma imperativa e a outra funcional. O compilador está sendo escrito em SML, um tipo de tarefa bastante adequado para a linguagem.

O problema começa nas ferramentas do front-end: o gerador de analisadores léxicos ML-Lex e o gerador de analisadores sintáticos MLYacc. O que atrapalha é que eles seguem muito de perto as ferramentas tradicionais lex e yacc do Unix, que foram feitas em C para gerar código C. Com isso, é impossível fugir de um estilo muito imperativo na criação dos analisadores. A situação não parece ser muito melhor em OCaml, o que é uma pena, já que compiladores e outros processadores de linguagens ficam condenados a esse estilo imperativo nessas linguagens que, a princípio, promovem um estilo de programação mais funcional. Um projeto interessante, mas para o qual eu não tenho tempo, seria pesquisar maneiras de fazer geradores de analisadores de maneira mais funcional, sem perdas significativas de eficiência. Uma idéia possível é usar monadic parser combinators ao estilo do parsec (feito em Haskell). Apesar das linguagens ML não suportarem mônadas nativamente, é possível criar construções baseadas em mônadas do mesmo jeito; talvez a falta de suporte sintático deixe uma ferramenta dessas bem menos prática de usar do que no caso do Haskell, mas só investigando.

Enfim, o lexer está pronto, incluindo seqüências de escape em strings, comentários aninhados e outros detalhes que dão um pouco mais de trabalho. Agora, de volta ao trabalho no parser...

Férias e tal

2005-01-03T09:24:00.000-08:00

Tirei uma semana de férias completas, passadas numa praia paradisíaca daqui do nordeste.

Mas antes eu estudei um pouco de teoria das categorias, e agora estou de volta à carga. O interesse no momento é estudar formalismos para modelar concorrência. Encontrei a lógica dinâmica de David Harel, pena que eu não tenha como comprar o livro; mas a tese de doutorado dele (na versão editada pela Springer) está disponível na biblioteca da UPFE. Tem lógica linear também, outro assunto com pouquíssimos livros disponíveis. Teoria de jogos está no bolo; alguns formalismos usando jogos e categorias existem por aí.

Enquanto isso, meus dedos coçam por um pouco de ação prática. Escrevendo código, quero dizer. Acho que vou mexer um pouco com compiladores.

E assim caminha a minha busca... In the land of Mordor where Shadows Lie.

Mais um desejo aos ventos

2004-12-12T08:29:00.000-08:00

Eu realmente queria que existisse uma tecnologia barata de impressão com qualidade razoável. São tantos artigos, manuais, documentação, livros e etc... Tem hora que dá vontade de imprimir e ir estudar na biblioteca, longe do monitor. Mas se for fazer isso sempre, eu gasto minha bolsa inteira com tinta e papel.

E aí, Papai Noel, desenrola uma impressora boa e com baixissimo custo de impressão ?

Grupóides, Monóides, Herculóides

2004-12-08T11:46:00.000-08:00

Resenha do livro Matemática Discreta para Computação e Informática, de Paulo Blauth Menezes.

Eu costumo reclamar por aí que livro técnico brasileiro é uma desgraça. Os livros ruins quase sempre têm sido maioria, embora a situação tenha melhorado um pouco nos últimos tempos. Que fique claro que eu estou falando de livros de autores brasileiros, e não necessariamente traduções de livros técnicos importados (embora algumas traduções sejam deploráveis também). E a culpa não é tanto dos autores; pelo que eu sei, as editoras impõem prazos curtíssimos. Enquanto nos livros de fora é normal você ler que o autor passou anos preparando um livro didático, aqui na Terra Brasilis o tempo médio é por volta de 6 meses. Isso é mais sentido nos livros das ciências básicas, que requerem um cuidado de elaboração que normalmente não cabe em 6 meses. Ainda por cima, muitos livros são porcamente tipografados e mal escritos.

Uma vantagem dos livros do Paulo Blauth Menezes é que são bem escritos. Mesmo assim, fica a sensação que o livro é pouco mais que notas de aula. Os assuntos são tratados corretamente, mas de forma muito superficial. Além disso, existe uma quantidade enorme de assuntos para um livro deste tamanho; existe até uma introdução à teoria das categorias que serve de muito pouco. Os exercícios são interessantes, mas pouco desafiantes, na maioria. Os exemplos de aplicações também são muito simples, embora nesse caso exista uma justificativa, já que é comum que estudantes de ciência da computação façam uma matéria de matemática discreta logo no primeiro semestre.

Para mim foi proveitoso ler sobre reticulados, e ver como alguns conceitos da matemática como relações e homomorfismo são vistos pelo ponto de vista da computação. Por exemplo, funções parciais dificilmente são tratadas em livros de matemática, mas são muito importantes na computação.

Enfim, o material é bom, mas o livro poderia se aprofundar mais, talvez reduzindo o escopo dos assuntos cobertos ou dividindo em dois volumes. A tipografia do livro também poderia ser bem melhor, principalmente em relação à notação matemática. Seria interessante ver outra edição, de preferência com alguns desses problemas resolvidos.

Salada

2004-12-01T20:23:00.000-08:00

Ok, agora eu estou estudando zilhões de coisas e tentando construir algumas idéias. Na verdade, eu tive idéias, alguns palpites, e estou correndo atrás da teoria para ver o que é viável, onde eu posso desenvolver alguma coisa.

Decidi estudar mesmo teoria dos jogos, lógica da computabilidade e computação interativa. Mas é bom estudar lógica linear também, que é um formalismo alternativo para mais ou menos o tipo de coisa. Estou até lendo sobre a Web Semântica, porque acho que algumas coisas nela podem ser relevantes, mesmo que eu não vá trabalhar diretamente com RDF ou OWL ou o que seja.

Sistemas reativos também, reflexão, mutação, avaliação em múltiplos estágios (programação generativa, meta-programação, MOPs), avaliação parcial, transformações... a lista não tem fim. Mas estou em estágio de exploração mesmo, e espero que dessa bagunça surja alguma idéia interessante para desenvolver. Espero mesmo...

How to Solve Mathematical Problems

2004-11-23T18:56:00.000-08:00

Livro de Wayne A. Wickelgren.

Seguindo os passos de Polya com seu aclamado clássico "A Arte de Resolver Problemas" (How to Solve It), Wickelgren estuda os métodos utilizados para resolver problemas de raciocínio, incluindo puzzles recreativos e problemas lógico-matemáticos. Enquanto o livro de Polya é bastante conciso nos princípios, sendo principalmente formado por exemplos de problemas a resolver e as soluções dos problemas, o livro de Wickelgren detalha várias técnicas sistemáticas para encontrar as soluções: representar as informações, fazer inferências, definir funções de avaliação de estados, hill climbing, trabalhar de trás para frente, etc. Muitas técnicas seguem idéias consagradas na área de Inteligência Artificial para resolução automatizada de problemas, principalmente as que usam uma função de avaliação de estados para navegar por um espaço de estados. Ao longo do texto vários problemas são colocados como exemplos das técnicas expostas; vale a pena parar e ao menos tentar resolver os problemas, e o livro vai dando dicas para quem não consegue de cara. Os problemas em geral são do tipo puzzle e não requerem conhecimento matemático especializado.

Assim como Polya, Wickelgren afirma que as mesmas técnicas são úteis para escrever demonstrações, embora praticamente nenhum exemplo seja dado. Existem outros livros com enfoque em técnicas para demonstrações.

É interessante ficar consciente de várias técnicas usadas na solução de problemas, mas alguns métodos apresentados no livro são bem trabalhosos; seguir um procedimento metódico em cada problema pode ser mais lento do que simplesmente intuir a solução. Os métodos ajudam naqueles casos em que não se consegue achar facilmente uma saída. Mas na minha experiência os métodos mais úteis são os mais diretos: representar as informações disponíveis e realizar inferências. Isso já encaminha a solução da maioria dos problemas. Somado a isso, o texto é muito longo; dá para resumir as idéias e técnicas em umas duas ou três páginas.

E é o que eu tenho pensado em fazer, após ter terminado: fazer um resumo para consulta fácil, juntando idéias deste livro e do Polya. Mais um, entre inúmeros projetos...

Google Scholar

2004-11-20T22:18:00.000-08:00

Mais um produto das organizações Google.

O Google Scholar é um serviço de busca voltado especificamente para artigos científicos. Também retorna resultados de citações em livros, e indica um índice de citações para cada artigo.

Testei hoje, e é bem interessante. Mas ainda não é melhor que o CiteSeer porque

Não apresenta o artigo em uma página com informações contextuais: abstract, links para artigos citados, links para citações; e
não mostra links para artigos similares, uma coisa que já me ajudou muito a descobrir artigos relacionados.

A vantagem do Google Scholar é que ele não é limitado à literatura das ciências da computação, ao contrário do CiteSeer. Mas talvez eles ainda melhorem a apresentação dos resultados, vamos ver.

De volta à ativa: sai Debian, entra Mandrake

2004-11-12T10:29:00.000-08:00

Finalmente com Internet no novo apartamento, fica mais fácil voltar a postar. E, por enquanto, a única coisa digna de nota é que eu desisti do Debian: a stable é muito desatualizada, e a unstable é, bem, instável. Por consenso com a outra alma que vai trabalhar no cluster, decidimos tentar o Mandrake. Eu usei até o Mandrake 9, mas desisti por ser instável demais, muitos bugs; mas o comentário geral é que a versão 10 estava bem melhor. Peguei a 10.1, instalei e não me arrependi: o bicho tá redondo. E olhe que eu estou usando a Community Edition que, para todos os propósitos, é uma beta. A Official Edition sai em uma ou duas semanas, mas para isso serve o urpmi; por falar nisso, ele é bem melhor que o yum, que eu estava usando no Fedora.

Agora, com o cluster reestabelecido, vamos começar a rodar as aplicações e testes.

Finalmente, o cluster

2004-10-30T07:16:00.000-07:00

Fui apresentado ao cluster menor que deve ser minha plataforma de testes; apenas 16 máquinas. Infelizmente, algumas máquinas estão mal configuradas ou nem dando boot (kernel panic). E as que funcionam estão com RedHat 8, então o primeiro passo vai ser instalar Debian em todas. Pena o Debian estar tão desatualizado, mas para essa aplicação, não será problema. A parte mais interessante, para não usar outra palavra, é que o compilador Haskell# (a linguagem funcional paralela criada pelo grupo de pesquisa do qual eu faço parte) não está disponível em lugar nenhum. Que ótimo. Vamos ver no que dá.

Hiatus Prolongadus

2004-10-21T13:34:00.000-07:00

O blog está parado, é o tipo da coisa que uma mudança faz com a pessoa... Fora o início do mestrado, estou lendo alguns livros interessantes sobre os quais comentarei em breve. Além disso, uma nova versão do plugin OCaml para Eclipse também está no forno.

Semestre 1/3 - Disciplinas

2004-10-07T21:55:00.000-07:00

Só duas: Métodos Matemáticos 1C (processos estocásticos, transformada de Fourier e transformada Z) e Teoria da Informação. Poucas aulas, muito trabalho; mas os assuntos não são totalmente novos. Espero que sobre um bom tempo para pesquisa.

Leituras iniciais

2004-10-03T10:18:00.001-07:00

Como início da investigação, uma lista de leituras e assuntos que pretendo pesquisar de início, por ordem de prioridade.

1. Fundamentos

2. Bases matemáticas

Lógica (lambda-calculus, etc)
Álgebra
Topologia (domínios, lattices)
Teoria das categorias
Teoria da computação

3. Acessórios

Compiladores (dragão, Grune et al., Gough, etc)
Fundamentos de Linguagem de Programação (Essentials of Programming Languages)
Foundations for Programming Languages
Programação funcional (Paulson, Reade, Okasaki, etc)

Eu sei que é muita coisa (principalmente na parte matemática), e que provavelmente não vai dar tempo de estudar tudo, quando começarem as obrigações formais do mestrado. Mas para isso servem as prioridades e leitura rápida.

Ordem !

2004-10-01T21:48:00.000-07:00

Hora de começar a por ordem nesta birosca. Comecei falando sobre processamento paralelo, a coisa se desviou para alguns artigos sobre linguagens de programação, e aqui estamos. As aulas começam em duas semanas, mas só na quarta eu saberei quais serão as disciplinas. Meu programa de pesquisa pessoal não precisa depender disso.

A área de pesquisa é processamento paralelo. Ainda não sei em que tópico, exatamente. A minha idéia é desenvolver um trabalho na área de processamento paralelo, de preferência relacionado a linguagens de programação. Ainda não sei se será algo teórico ou aplicado, embora a ênfase em um lado não exclua o outro. O que eu preciso fazer, em termos gerais:

estudar a teoria da concorrência e computação paralela
estudar a teoria e aspectos práticos das linguagens de programação
procurar um problema interessante e relevante para resolver na área de processamento paralelo; isso pode ou não já envolver linguagens de programação
buscar uma solução para o problema; a solução poderá ser no nível das linguagens e usar métodos e técnicas da área

Por que estudar a teoria das linguagens de programação ? Porque é um objetivo relacionar minha dissertação com essa área; estudando a teoria eu vou saber que soluções e técnicas estão disponíveis, e onde ir para saber mais sobre elas.

Os passos 1 e 2 são para construir a fundação, e o 3 e 4 para "executar" o plano em si. Em seguida vou detalhar melhor o que eu já tenho planejado, principalente para os passos 1 e 2.

Schizoid Classes

2004-09-29T11:37:00.000-07:00

Artigo na ACM Queue.

Através dos métodos (e variáveis) de instância e de classe, as classes em Java e C++ misturam o conceito de tipo com o de módulo, criando uma crise de múltipla personalidade. Em contraste, na linguagem Smalltalk os métodos e variáveis de instância e de classe são conceitualmente unificados através do uso de metaclasses e metaobjetos. Em outras linguagens, classes e módulos coexistem, reconhecendo o fato que nenhum dos dois pode substituir o outro.

Artigo curto e de boa leitura; é uma demonstração do que acontece quando você tenta construir linguagens sem uma visão geral de projeto; Smalltalk tem essa visão, C++ e Java não. C++ é um frankenstein ao qual foram adicionadas características (por vezes conflitantes) ao longo dos anos, e Java é uma "linguagem política" que foi feita para tentar satisfazer a gregos e troianos. Não se pode dizer que nenhuma das duas tenha "integridade conceitual".

An Axiomatic Basis for Computer Programming

2004-09-29T07:56:00.000-07:00

Um artigo clássico de C. A. R. Hoare, datado de 1969. Esse artigo lançou as bases para provas axiomáticas de corretude de programas e para a semântica axiomática.

O método axiomático foi usado com sucesso na matemática desde que Euclides publicou uma axiomatização da geometria nos seus Elementos. Com o tempo, o método foi aperfeiçoado e hoje é a base de praticamente todas as teorias matemáticas; Aristóteles já chamava a atenção para o fato que uma cadeia de demonstrações deve começar em algum lugar, algumas verdades que são assumidas. Estes são os axiomas.

A tese de Hoare é que é possível estabelecer axiomas básicos para a programação de computadores, e a partir deles, usando regras de inferência também estabelecidas, provar propriedades dos programas, especialmente a sua corretude. Um programa é correto se ele realiza as especificações que foram determinadas para ele, ou seja, se ele faz o que deve fazer. Além disso, os axiomas podem ser utilizado na definição formal de linguagens de programação.

Para exemplificar a plausibilidade do método axiomático na programação, o artigo apresenta alguns axiomas relacionados aos números inteiros e a construções básicas de programação: atribuição, sequenciamento, iteração. Com isso, prova-se que um programa que calcula o máximo divisor comum de dois números é correto, satisfazendo as propriedades matemáticas necessárias para o cálculo.

A seção 5 discute provas de corretude para programas; a idéia, já antiga, de que erros de programação custam caro e que testes nunca podem provar completamente que um programa está correto. Um trecho é interessante:

The practice of supplying proofs for nontrivial programs will not become widespread until considerably more powerful proof techniques become available, and even then will not be easy.

Coisa que até hoje não aconteceu; ainda é trabalhoso demais provar a corretude de programas além dos mais triviais. Entretanto, em alguns casos mais críticos isso já foi feito, principalmente com a ajuda de theorem provers especializados. Muitos microprocessadores também passam por processos de prova formal atualmente; é possível que os métodos formais realizem, um dia, os benefícios visualizados por pioneiros como Hoare e Dijkstra. No artigo, Hoare também menciona como as provas de corretude podem ajudar na documentação e portabilidade de programas.

A seção 6 termina o artigo falando do uso do método axiomático na definição formal de linguagens de programação. Dado que sejam estabelecidos os axiomas e regras de inferência da linguagem, eles servem de definição da própria linguagem: uma implementação só é válida se tornar válidos os axiomas e regras de inferência definidos. Ao mesmo tempo, os axiomas servem automaticamente como base para a prova de corretude da implementação. Hoare fala de Algol 60 e de como a definição formal da sua sintaxe ajudou na formulação de regras sintáticas coerentes, advogando a mesma vantagem para uma definição formal da semântica (tema antigo: simplicidade da definição formal da sintaxe versus complexidade na definição formal da semântica). A semântica axiomática, cuja pesquisa se aprofundou nos anos seguintes, anda meio em desuso, mas os princípios são sólidos.

Faz você pensar no que a computação poderia ser se mais atenção fosse dada às bases teóricas.

Idéias

2004-09-28T15:00:00.000-07:00

Relendo o paper sobre Haskell#, e pensando na especificação estática do paralelismo, me perguntei: por que não codificar a informação de configuração no sistema de tipos ? Atualmente, é utilizada uma linguagem separada para isso, a HCL (Haskell Configuration Language), o que traz os problemas de casamento de impedância e coisa e tal. Uma solução integrada ao sistema de tipos poderia manter a especificação dinâmica, a separação das preocupações de coordenação e computação e ainda eliminar os problemas de impedância. Além de codificar os componentes e a configuração, é necessário codificar os skeletons também. Templates ? Meta-programação ? É preciso verificar que outras técnicas já foram tentadas (Eden, GpH, etc)...

Lambda: the Ultimate Declarative

2004-09-27T12:16:00.000-07:00

Outro artigo da "série Lambda" de Guy Steele e Gerald Sussman.

Este abre caminho para o projeto do compilador RABBIT que foi o objeto de estudo do mestrado de Steele. O foco é na definição de primitivas para estruturas de controle e operadores de ambiente, usando expressões-lambda como base sempre que possível; e em como compilar estas primitivas eficientemente para código de máquina (o PDP-10 é usado como plataforma-alvo).

Logo no começo há uma explicação bastante didática sobre recursividade final, porque ela é eficiente e como o interpretador Scheme apresentado no artigo "SCHEME: An Interpreter for Extended Lambda Calculus" implementa essa otimização (exatamente o que eu comentei em um post anterior).

Então são apresentadas duas primitivas fundamentais: a aplicação de funções como uma primitiva de controle fundamental (juntamente com expressões condicionais) e as expressões-lambda como operadores de renomeamento de quantidades de um ambiente. Seguem as propriedades dessas primitivas (controle e ambiente) que permitem uma compilação eficiente do código; há um exemplo de compilação mostrando como uma função recursiva é compilada para código de máquina iterativa.

A próxima seção trata de fechamentos e estilo de passagem de continuações. A continuação é apresentada como um parâmetro explícito que guarda o endereço de retorno, em contraste ao endereço de retorno implícito nas chamadas de função habituais. Também se mostra como o uso do CPS facilita o suporte a funções que retornam múltiplos valores. O uso de CPS em todo lugar acaba com o problema de ter primitivas que tiram o endereço de retorno da pilha, mas criam a necessidade de converter código para o CPS, e usar todas as primitivas em CPS.

A seção 3 é a que é mais fiel ao título do artigo: falando de estruturas de dados definidas proceduralmente, expõe técnicas para usar fechamentos e expressões lambda na representação de tipos de dados. Nisso, toca-se no assunto dos ADTs (Abstract Data Types), mencionando inclusive CLU, e em formas eficientes de compilar fechamentos que representam dados. Apenas sugestões mostrando o que é possível, mas nada concreto (lembrando que o artigo é uma proposta de tese).

Enfim, fala-se da estrutura proposta para o compilador Scheme que é o objeto da tese de mestrado de Guy Steele. Resumem-se as técnicas necessárias, requisitos e resultados esperados com o compilador. Interessante que a visão dos autores era a de usar Scheme como uma linguagem intermediária universal, pela facilidade de expressar as operações gerais das linguagens de programação com construções simples, a maioria baseada nas expressões lambda. Apesar de não ser o uso corrente da linguagem, isso se reflete em algumas linhas de trabalho, como a do livro Essentials of Programming Languages e do pessoal do PLT da universidade de Indiana.

A conclusão reapresenta as idéias principais do memo, com a parte mais interessante para mim sendo as analogias entre definição e aplicação de funções (eval/apply). Os dois apêndices tratam da conversão de código arbitrário para CPS.

No geral é um tanto heterogêneo para um artigo, já que é mais uma proposta de tese. Também inclui muitas referências específicas a trabalhos do AI Lab e ao PDP-10, mas ainda assim o memo vale a pena por condensar várias idéias sobre Scheme, focalizando na construção de um compilador.

Curtas

2004-09-27T07:01:00.000-07:00

Computação interativa leva ao estudo da teoria dos jogos. von Neumann, John Nash, etc
O mlton está avançando bastante; pode ser uma boa alternativa de um sistema ML prático, concorrendo com OCaml
O PLT Scheme está com um sistema de módulos interessante, o PLaneT. PLT ficando cada vez melhor
Não é muita novidade, mas saíram os resultados do ICFP Contest desse ano. Haskell na frente, OCaml no prêmio especial do juri.

Computação Interativa

2004-09-23T15:56:00.000-07:00

Vários trabalhos de pesquisa, ultimamente, têm se concentrado no conceito de computação interativa: focalizar, na teoria da computabilidade, não mais o algoritmo como peça central, mas a interação. Isso torna os modelos clássicos (máquinas de Turing, lambda-calculus, etc) inadequados para descrever os sistemas computacionais atuais. A idéia é desenvolver novos fundamentos que levem em conta interação, distribuição, mobilidade e concorrência.

Um dos tipos de formalismo desenvolvido são as álgebras de processo, como o pi-calculus; assuntos que pretendo estudar em breve (os livros já estão aqui). A busca dos fundamentos para computação interativa me interessa muito, e é algo que eu posso relacionar com a minha pesquisa de mestrado.

A conferência Foundations of Interactive Computation é sobre isso. O call for papers apresenta alguma contextualização para os motivos dessa busca.

References for Beginners in Programming Language Theory

2004-09-23T11:39:00.000-07:00

Thread no LtU. Vou observar se aparecem indicações interessantes (além das que já estão lá).

Hiato...

2004-09-20T05:55:00.000-07:00

É, as coisas andam paradas por aqui mesmo. Prazo apertado no trabalho, um rapido desvio pelo mundo da criptografia e muito código Java (eca). Se tudo der certo, em duas semanas estarei livre disso e aí vai ser só Haskell e clusters.

Lambda the Ultimate

2004-09-14T13:35:00.000-07:00

Lembrando que no LtU Imperative os modelos semânticos se baseiam apenas em:

expressões lambda
expressões condicionais
atribuição

Se tivermos avaliação em ordem normal, até mesmo as expressões condicionais podem ser modeladas usando expressões lambda. Assim, teríamos apenas a necessidade de 1 e 3. O problema é que, como notado no paper original sobre Scheme, a ordem normal de avaliação complica a implementação correta da recursividade final. Mas, se usarmos o estilo de passagem de continuações sempre, obtemos independência da ordem de avaliação específica, como observado por Reynolds e Steele & Sussman; assim podemos ter uma linguagem em ordem normal e com recursividade final, eliminando a necessidade de ter expressões condicionais como primitivas.

Agora acabei de reler essa parte no AIM-349 (o "Scheme: an Interpreter for Extended Lambda Calculus") e vi que esta observação também está lá. Enfim, é difícil ser original, ainda mais considerando que esses artigos têm em média 30 anos de idade.

Seria possível eliminar a atribuição, ficando apenas com expressões lambda para tudo ? Aparentemente não, até porque o lambda-calculus puro é livre de efeitos colaterais, e nós queremos modelar estruturas que apresentam efeitos colaterais. Será que não dá para colocar uma mônada aí no meio ? E mais, fazer isso sem passar para uma extensão do lambda-calculus puro ?

(Nota: se não me engano alguém já provou que ter continuações e atribuição em uma linguagem é equivalente a ter mônadas numa linguagem sem efeitos colaterais, mas qualquer conjunto menor é menos expressivo; depois vou procurar esse artigo)

Lambda: the Ultimate Imperative

2004-09-14T09:46:00.000-07:00

Mais um artigo de Steele e Sussman.

São apresentados modelos semânticos de algumas estruturas de linguagens de programação. A linguagem usada para especificar a semântica é Scheme (claro). O título vem do fato da maioria das estruturas serem consideradas imperativas, e os modelos utilizarem expressões lambda quase que exclusivamente ("o poder do lambda-calculus"). As estruturas são:

recursão simples
iteração
sequenciamento de expressões (comandos compostos)
saltos com goto
atribuição
passagem de continuações
expressões de escape (saídas não-locais)
variáveis fluidas (escopo dinâmico)
convenções de passagem de parâmetros: call by name, call by need e call by reference

O mote do artigo é que essas estruturas são modeladas usando apenas expressões lambda, expressões condicionais (if) e, em alguns poucos casos, atribuição. Na maior parte dos casos os modelos são realizados a partir de transformações sintáticas locais, mantendo a mesma estrutura do programa original.

Os dois primeiros itens são gratuitos em Scheme. O sequenciamento consegue-se pelo aproveitamento da ordem de avaliação aplicativa em expressões lambda. Assim, a sequência S1; S2 vira ((lambda (dummy) S2) S1). Neste exemplo, S1 é executada apenas pelos efeitos colaterais. Os saltos também são consequência da recursividade final, que garante que uma chamada de função seja apenas uma transferência de controle direto (ver últimos posts). A atribuição pode ser modelada também com expressões lambda, usando uma chamada de função para cada novo valor da variável. Expressões compostas são consequência de como o sequenciamento é implementado; nada de novo. Continuações também ficam simples graças à recursividade final; expressões de escape são modeladas com CATCH ou com continuações.

A parte mais longa e elaborada do artigo são os modelos para escopo dinâmico e as convenções de chamada. Para escopo dinâmico utiliza-se um ambiente fluido que é transmitido entre todas as funções que podem fazer atribuições a variáveis dinâmicas. É preciso alguma convenção sintática para diferenciar as variáveis léxicas das fluidas. Se a implementação usa o estilo de passagem de continuações em todas as funções, o ambiente fluido pode ser incorporado na mesma função da continuação.

Para as convenções de chamada, o call-by-name da linguagem ALGOL é simulado usando thunks, que são expressões lambda sem argumentos: uma expressão E1 é transformada para (lambda () E1). Pode-se adicionar memoização permantente, chegando ao esquema call-by-need. Embora semelhante, o call-by-need é diferente do call-by-name, mas mesmo assim pode-se utilizar algumas formas de memoização para tornar o call-by-name mais eficiente. O problema da atribuição de parametros passador por nome e por referência é tratado por último, incluindo algumas considerações gerais de como, por exemplo, tornar o car de uma lista, ou qualquer outra localização de valor, atribuível. Assim, discute-se sobre convenções de atribuição em outras linguagens.

A conclusão nota que Landin e Reynolds já tinham realizado modelos de algumas das mesmas estruturas usando técnicas similares; entretanto, eles utilizaram formalismos mais complexos do que a linguagem Scheme utilizada neste artigo. Além disso, os modelos para expressões de escape, escopo dinâmico e chamada por nome não tinham sido apresentados antes.

Em seguida: Lambda, the Ultimate Declarative.

Mais Reflexões Recursivas

2004-09-14T07:16:00.000-07:00

O fato de ser mais difícil implementar a recursividade final corretamente em linguagens imperativas, por causa do sequenciamento de instruções principalmente, deve explicar a falta deste aspecto em linguagens como C e Java. Também para explicar por que isso foi "descoberto" no âmbito da programação funcional. Mas hoje já se sabe como fazer isso em linguagens imperativas, então não deveria haver desculpas. Ou deveria ?

Enfim

2004-09-14T07:05:00.000-07:00

Sobre a tail recursion no interpretador Scheme, a resposta é simples e engenhosa; está nas entrelinhas do interpretador. É só não salvar o estado na hora de avaliar (executar) uma combinação.

Mas não tem que voltar ? Nem sempre, só se a combinação for uma subcombinação de outra combinação. E aí o interpretador salva: antes de avaliar cada argumento de uma combinação, ele salva o estado, para restaurar quando a avaliação do argumento tiver sido terminada.

Ou seja, o controle de uma função para outra é simplesmente transferido (goto mesmo). Lembrando do artigo de Reynolds, isso é o interessante do estilo de passagem de continuações: uma função no CPS nunca retorna, apenas transferindo o controle para a próxima continuação.

Dá para ver que isso é possível em uma linguagem orientada a expressões como Scheme, sem sequenciamento de instruções e outras características imperativas. É preciso refletir como seria possível fazer isso em C, por exemplo (sim, eu sei que já foi feito).

Agora posso terminar o LtU Imperative.

Tail Recursion ?

2004-09-13T15:06:00.000-07:00

Já estava quase terminando o Lambda: the Ultimate Imperative quando me veio uma dúvida à cabeça, sobre a implementação Scheme que é mostrada no artigo anterior: como são implementadas as tail calls (chamadas finais) ?

Eu não analisei a implementação apresentada a fundo, até porque é MacLisp, um dialeto de mais de 30 anos de idade. Mas agora fiquei curioso com isso.

Em uma olhada superficial, a função EVLIS é a responsável pela avaliação de combinações, então aparentemente é aí que o controle deve ser transferido. Mas como diferenciar quando salvar e quando não salvar um quadro de ativação (CLINK, na notação do artigo) ?

A transferência entre as funções que implementam o interpretador é por meio de tail calls forçadas, utilizando a variável do contador de programa (**PC**); mas ainda não percebi como isso se reflete nas funções da linguagem interpretada... bom, verificarei isso.

SCHEME: An Interpreter for Extended Lambda Calculus

2004-09-13T06:39:00.000-07:00

O artigo original de Steele e Sussman que define a linguagem Scheme. Na verdade, é um memo interno do laboratório de inteligência artificial do MIT; mas uma publicação respeitada mesmo assim.

Muitas informações históricas interessantes, mas alguma parte das informações técnicas ainda é relevante também. O memo é de 1975; tanto Landin quanto Reynolds já tinham publicado artigos importantes sobre o lambda-calculus e sua relação com as linguagens de programação, tanto que ambos são citados no memo. Mesmo assim, Scheme foi a primeira linguagem prática a implementar o lambda-calculus e ser explicitamente baseada nele (a LISP original chega perto, mas tem o problema de funções não serem valores).

A primeira parte é um manual de referência da linguagem Scheme; bastante primitiva se comparada com as versões atuais. O operador call/cc (call-with-current-continuation) se chamava CATCH. A definição original também incluía primitivas de multiprogramação: operações para criar e gerenciar processos, coisas que foram retiradas da linguagem para sempre, posteriormente. A parte é curta e vai direto ao ponto.

A segunda parte tem exemplos de programas em Scheme, começando com a tradicional função fatorial recursiva, depois tratando de funções iterativas implementadas recursivamente (usando recursão final, ou tail recursion se preferir), estilo de passagem de continuações, e dois exemplos maiores: a função SAMEFRINGE e uma função de reconhecimento de padrões, ambas usando continuações e CATCH extensivamente. No final, um exemplo de multi-processamento. Os exemplos são interessantes principalmente como uso de continuações e call/cc.

Na parte 3 discute-se a semântica da linguagem, utilizando o lambda-calculus de maneira um tanto quanto informal para basear a discussão. Fala-se da semântica de substituição típica da teoria de Church. A semântica de substituição é utilizada para justificar como programas com recursividade final são iterativos, pois não necessitam de uma pilha proporcional ao tamanho da entrada. Da mesma forma, analisa-se a execução de funções no estilo de passagem de continuações.

Em seguida, a quarta parte discute sobre a implementação da linguagem, destacando as principais dificuldades e como contorná-las. Steele e Sussman definem como principal dificuldade a eficiência da implementação. Aqui é apresentada a técnica de utilizar ambientes (environments) como forma eficiente de implementar a semântica de substituição do lambda-calculus; uma implementação ingênua, utilizando substituição textual, é bem mais complexa. Apresenta-se também a noção de fechamentos (closures), que são o resultado da avaliação de uma expressão lambda; o fechamento inclui a própria expressão lambda e o ambiente na qual ela foi avaliada, resultando numa das principais características da linguagem Scheme: o escopo léxico (as variantes Lisp da época utilizavam escopo dinâmico). Os autores chamam a atenção para a semelhança com ALGOL e o uso do conceito de fechamento em outros sistemas. Uma consequência importante é que o escopo léxico garante que os axiomas do lambda-calculus são válidos na linguagem. Por fim, discute-se os problemas relacionados ao fluxo de controle do interpretador e dos programas interpretados, o que traz à tona o assunto da ordem de avaliação (normal vs. aplicativa). Chama-se a atenção para o fato que a ordem normal, que é a tradicional no lambda-calculus, evita a implementação eficiente de algoritmos iterativos, e por isso Scheme usa a ordem aplicativa. Mesmo assim, formas especiais usadas como macros usam uma forma de ordem normal, efetivamente misturando as duas formas na mesma linguagem. Fala-se também sobre como o uso do estilo de passagem de continuações pode eliminar a dependência da ordem de avaliação específica; o mesmo já foi tratado por Reynolds em seu "Definitional Interpreters for Higher-Order Programming Languages" de 1972. Mais alguns detalhes são considerados, como extensões para constantes e operações primitivas.

A seção 5 conclui o artigo apresentando uma implementação "didática" (não totalmente otimizada) da linguagem, usando MacLisp como linguagem de implementação. O fato de MacLisp ser um tanto diferente do Common Lisp atual atrapalha um pouco o entendimento, mas nada que não possa ser superado. A principal idéia da implementação é pensar em baixo nível; não utilizar a recursividade da linguagem de implementação para expressar a recursividade na linguagem implementada, pois isso atrelaria as estruturas de controle desta às daquela. Uma parte interessante é a implementação da forma LABELS, que apresenta um ambiente recursivo no qual as expressões podem se referir umas às outras; o efeito é conseguido utilizando-se alterações destrutivas na estrutura do ambiente, cujos fechamentos são alterados para apontar para o próprio ambiente criado.

No final, os agradecimentos dão uma idéia das origens da linguagem Scheme. Isso termina o primeiro artigo da série dos "lambda papers" de Steele e Sussman. Os próximos já estão na fila de leitura.

Enquanto isso, na programação funcional...

2004-09-10T07:29:00.000-07:00

Na programação funcional não existem valores parciais, então não dá para fazer o mesmo truque. Também seria estranho ver procedimentos em uma linguagem funcional. Mas ainda dá para conseguir recursividade final (já vi em algum lugar a tradução recursão de cauda ou algo similarmente horrendo) através de outra transformação. A idéia é utilizar uma convenção idiomática comum, através de acumuladores. Vejamos como isso fica em Scheme. A função mapl (map já existe em Scheme) é uma versão direta da função em Oz:

(define (mapl f l)

(if (null? l)

   ()

   (cons (f (car l)) (mapl f (cdr l)))))

Ela claramente não apresenta recursividade final. Agora vamos passar utilizar um acumulador como parâmetro adicional:

(define (mapla f l a)

(if (null? l)

    a

    (mapla f (cdr l)

           (cons (f (car l)) a))))

E voilà: tail recursion. Mas aqui temos um problema: a lista resultante está invertida com relação ao resultado esperado, pois a operação de construção de lista não é comutativa. Resolve-se isso adicionando uma chamada a reverse:

(define (mapla f l a)

(if (null? l)

    (reverse a)

    (mapla f (cdr l)

           (cons (f (car l)) a))))

Pode testar que dá o mesmo resultado (recomendo o DrScheme); como acumulador inicial usa-se a lista vazia, segundo a equação de equivalência (mapl f l) = (mapla f l ()). Pode-se criar uma função wrapper que faça isso automaticamente.

Eine Kleine Nachtmusik

2004-09-10T06:57:00.000-07:00

Oz é uma linguagem estranha. Seus conceitos fundamentais são uma mistura de programação imperativa, funcional e lógica, além de programação concorrente e distribuída. Intrinsecamente multi-paradigma.

Terminei os dois primeiros capítulos do CTMCP e ainda fica um certo estranhamento, até porque no começo parece tanto com uma linguagem funcional. Mas tem unificação, valores parciais e outras coisas estranhas que parecem Prolog.

Para exemplificar, vamos começar com algum background: Oz é dividida em uma kernel language que abriga os conceitos fundamentais, e uma full language que inclui sintaxe extra e outras conveniências. A kernel language é simples e é nela que se define a semântica da linguagem; além disso, especifica-se formalmente como traduzir programas na full language para a kernel language, e assim é possível especificar a semântica de qualquer programa na linguagem completa.

Pois bem, a kernel language define procedimentos, e não funções, como conceitos primitivos. Funções são uma abstração sintática da linguagem completa, que são traduzidas para procedimentos na kernel language. Como exemplo, a função

fun {Times2 N}

  N * 2

end

é traduzida para o procedimento

proc {Times2 N ?R}

  R = N * 2

end

O ?R é um parâmetro de saída que é atribuído com o resultado de retorno do procedimento (se houver um). O que era funcional vira imperativo na kernel language. O que é realmente interessante é a forma como isso interage com valores parciais e estruturas de dados. Vamos definir uma função Map que aplica uma função F a cada elemento de uma lista L. O operador | é o construtor de lista (cons em Scheme/Lisp, :: em ML, : em Haskell); {F H} é uma chamada da função F com argumento H; case faz pattern matching. Logo após a função tem a tradução dela para a kernel language.

fun {Map F L}

  case L of H | T then {F H} | {Map F T}

  else nil end

end



proc {Map F L ?R}

  case L of H | T then

    local Rr in

      R = {F H} | Rr

      {Map F T Rr}

    end

  else nil end

end

Note-se aí a atribuição do resultado (R) a um valor parcial, pois Rr (o "resto" do resultado) ainda não possui valor. O efeito disso é transformar uma função que não é tail recursive em um procedimento que é. O programador ganha automaticamente os benefícios da recursão final (tradução tentativa para tail recursion), sem se preocupar com isso.

Estranho, mas interessante.

Outras relações

2004-09-08T10:16:00.000-07:00

Ainda sobre o artigo de Reynolds, algumas observações adicionais.

O método de usar interpretadores meta-circulares na definição de linguagens de programação começa, como é conhecido, com John McCarthy e o artigo original sobre a linguagem Lisp. A mesma abordagem é utilizada em um dos capítulos do influente livro "Structure and Interpretation of Computer Programs" de Abelson e Sussman; o uso de interpretadores para explicar características de linguagens de programação também é a idéia central no livro Essentials of Programming Languages de Friedman, Wand e Haynes.

Steele e Sussman definem, em Scheme, um conceito similar ao escape de Reynolds no artigo Lambda, the Ultimate Imperative. Ambos são muito parecidos ao operador J de Peter Landin. A mesma idéia aparece no operador call-with-current-continuation, ou call/cc, das versões recentes da linguagem Scheme.

A notação utilizada, sendo influenciada pelos trabalhos de Landin, lembra uma forma primitiva da linguagem ML. O uso de referências como entidades explicitamente separadas dos outros tipos de variáveis também apareceu em ML.

A adaptação do interpretador para incluir atribuições de variáveis, com o estado sendo propagado por todas as funções, lembra o uso de mônadas na linguagem Haskell.

O artigo de follow-up "Definitional Interpreters Revisited" fala sobre essas relações também (ainda não tinha lido quando escrevi isso aqui).

Enfim, é fácil de ver o quanto esse artigo foi bem sucedido em reunir uma série de idéias fundamentais da área; e a abordagem de mostrar as idéias construtivamente, a partir de interpretadores para elas, foi a maior inovação dele.

Definitional Interpreters for Higher-Order Programming Languages

2004-09-08T08:24:00.000-07:00

Artigo de John C. Reynolds.

O seu propósito é sumarizar o estado-da-arte (da época, 1972) na construção de interpretadores utilizados para definir a semântica de linguagens de programação. Basicamente, ele classifica os interpretadores conhecidos, e demonstra como um interpretador de uma classe pode ser transformado em um de outra classe, clarificando as relações entre as classes. As classes são definidas em dois eixos: se a linguagem definida depende ou não da ordem de avaliação (normal ou aplicativa) da linguagem definidora; e se o interpretador usa funções de alta ordem ou não.

Começando com um interpretador meta-circular que depende da ordem de avaliação da linguagem definidora e com funções de alta ordem, o artigo mostra como retirar as dependências, assim informando como construir uma linguagem com funções de alta ordem com base em outra linguagem que não as possui, e como tornar a linguagem definida independente da ordem de avaliação da linguagem definidora.

Um aspecto interessante é como um tipo de interpretador é transformado em outro através de transformações locais que preservam o significado do programa. Esta idéia é muito presente na literatura produzida pelo grupo do PLT Scheme.

Interessantíssimo para quem quer aprender mais sobre a natureza das linguagens, especialmente as funcionais. Podem-se perceber as influências do artigo em várias partes, por exemplo nas linguagens funcionais atuais (tanto Scheme quanto ML) . Claro que as idéias no artigo em si não eram novas (embora a abordagem seja), já que ele resume idéias de vários outros trabalhos. Por isso mesmo, serve como um excelente guia para a literatura da época sobre o assunto. E é fácil de entender para quem tem alguma exposição a linguagens aplicativas ou ao lambda-calculus.

Vale a pena ver também o follow-up "Definitional Interpreters Revisited".

Paralelismo para todos

2004-09-08T05:41:00.000-07:00

Sim, chips dual-core estão vindo de vez. E o futuro é quad-core; oito e até mesmo 16 núcleos num chip só estão sendo tentados. Paralelismo fundamental nas máquinas de todos, em poucos anos.

Veja-se, por exemplo, a cobertura do Intel Developer Forum deste ano.

O problema é que não adianta o quanto nossos chips são potentes, se o software não foi feito para aproveitar essas novas tecnologias. Normalmente estima-se em anos o tempo necessário para que uma parte significativa do software utilizado aproveite as inovações do hardware. É possível que isso ficaria mais fácil se tivéssemos tecnologias de criação de software mais adaptáveis ?

Outra coisa: concorrência e paralelismo vieram para ficar, desta vez. Qual o impacto que isso trará para as tecnologias de programação ? Será que linguagens e tecnologias mais apropriadas ao meio (erlang, por exemplo) serão utilizadas, em detrimento das que lidam muito mal com concorrência (java) ? Difícil de acreditar, mas tenhamos esperança...

OCaml e o eclipse

2004-09-04T11:32:00.000-07:00

Fiz essa semana o primeiro release oficial do plugin para usar o Eclipse como uma IDE OCaml. Versão alfa e tal, ainda bem primitiva. Mas deu um alívio liberar isso e tirar uns dias de folga. Muito trabalho braçal, e ainda mais em Java. Agora vem as partes mais interessantes: modelo da linguagem, análise sintática, melhorar a análise de depedências, trabalhar com o interfaceamento entre a JVM e OCaml, etc...

Supercomputer Seeks Comeback

2004-08-30T12:34:00.000-07:00

Artigo na Wired.

Mais um livro que chega

2004-08-26T07:06:00.000-07:00

Agora foi Concepts, Techniques and Models of Computer Programming de Peter Van Roy e Seif Haridi, considerado o novo SICP.

A falta de posts reflete o fato que ultimamente não tenho estudado muito, mas espero voltar à ativa em breve.

The Role of the Study of Programming Languages in the Education of a Programmer

2004-08-20T11:57:00.000-07:00

Transcrição de uma palestra proferida por Dan Friedman (pdf, ps).

Defende que todo programador deve estudar ao menos o essencial sobre os mecanismos utilizados pelas linguagens de programação, apresentando exemplos de transformações e testemunhos de ex-alunos. A idéia é que entendendo os mecanismos básicos das linguagens, de forma independente das sintaxes específicas, pode-se trabalhar com os programas como dados, realizando transformações que preservam a semântica a fim de melhorar propriedades do código. E que para entender os mecanismos, é importante ver implementações dos mesmos; implementar as idéias em outra linguagem (no caso, Scheme).

É a abordagem utilizada no Essentials of Programming Languages.

Parallel and Distributed Programming Using C++

2004-08-18T07:13:00.000-07:00

Livro de 2003, de autoria de Cameron Hughes e Tracey Hughes.

Superficial e sem foco, apesar de ter alguns exemplos que podem ser úteis para a implementação de sistemas usando PVM, pthreads ou MPI. Os primeiros capítulos são mais conceituais, e possivelmente a parte mais útil do livro (embora seja também superficial). Os capítulos "aplicados" tratam mais de C++ e UML do que do tópico do livro. E os capítulos finais, que deveriam ser os grandes exemplos e estudos de caso, se limitam a discutir um pouco sobre a arquitetura dos sistemas e mostrar meia dúzia de linhas de código. Vagamente interessante, mas nada muito proveitoso.

Novos livros

2004-08-17T13:09:00.000-07:00

Chegaram hoje:

Introduction to Process Algebra, de Wan Fokkink

Communicating and Mobile Processes: the Pi-calculus, de Robin Milner

Postarei resenhas quando estiver lendo e/ou terminado de ler.

Motivações

2004-08-17T10:14:00.000-07:00

Em algum post anterior eu fiz a pergunta "Por que usar processamento paralelo/concorrente?". A resposta que eu dei no mesmo post se baseou em ganhos de eficiência. Esta talvez seja, sim, a principal motivação para usar processamento paralelo, especialmente em aplicações científicas. Mas não é a única possibilidade.

Além de alta eficiência, pode-se usar sistemas paralelos para alta disponibilidade. A idéia, neste caso, é ter uma rede com nós redundantes de forma que, mesmo se alguns nós falharem o sistema inteiro continua executando suas funções sem maiores problemas. É o mesmo tipo de redundância-como-tolerancia-a-falhas que encontramos em sistemas de disco RAID, servidores de bancos de dados e sondas espaciais da NASA. A questão aí, quando se lida com informações e processamento, é como manter os nós redundantes em sincronia para que a falha não seja percebida externamente: o nó redundante que entra em ação para substituir o nó problemático deve continuar exatamente onde ele parou.

Essa noção de redundância também encontra analogias na biologia. Os sistemas biológicos normalmente contem redundâncias, do código genético a partes macroscópicas de corpos que se regeneram, passando pelos neurônios no cérebro (de novo). Parece ser uma forma óbvia de criar sistemas robustos e tolerantes a falhas.

O que mais podemos levantar como motivos ? Alguns (por ex. Joe Armstrong, criador da linguagem Erlang) defendem que alguns sistemas são mais naturalmente modelados por tarefas concorrentes, ao invés de uma única sequencial. Além disso, podemos pensar em modularidade: se temos tarefas isoladas que se comunicam com as outras, mas cada uma fazendo seu trabalho, temos fronteiras de abstração mais administráveis e interfaces mais definidas, reduzindo o acoplamento; isso pensando em um modelo de concorrência com passagem assíncrona de mensagens. Componentes concorrentes com estado compartilhado (shared state) se tornam mais acoplados do que se fossem realizados sequencialmente. Essa é a diferença de abordagem de Erlang e outros versus o modelo de concorrência encontrado em linguagens populares como Java e C#.

Além do mais, do jeito que as coisas vão, em pouco tempo ninguém precisará mais pensar muito em motivos para usar o paralelismo: a tendência é realmente usar sistemas multi-processados e com processamento paralelo mesmo em equipamentos domésticos e consoles de video-game. Sistemas paralelos e distribuídos parecem ser o futuro da computação, em escalas e instâncias variadas.

Paralelismo e o cérebro humano

2004-08-14T10:03:00.000-07:00

No cérebro temos dezenas de bilhões de neurônios, e eles operam paralelamente. Os sinais são transmitidos em cadeias de neurônios, mas isso acontece em várias cadeias ao mesmo tempo.

A analogia com processadores paralelos é óbvia, e também nada nova. O projetista da connection machine, Daniel Hillis, pensou em criar uma máquina que funcionasse de forma similar à mente humana. Tanto que o nome da empresa que ele fundou era Thinking Machines Corporation, e até hoje fala-se da connection machine relacionada à Inteligência Artificial. Paralelismo massivo para simular o processamento realizado pelo cérebro.

O interessante, ao meu ver, é que apesar do cérebro, fisiologicamente, funcionar de maneira paralela, nosso pensamento se aproxima mais de algo sequencial. Não é linear, em geral, mas só conseguimos pensar em uma coisa de cada vez, mesmo que numa sucessão tão rápida que às vezes nem lembramos de tudo. O processamento sequencial faz parte de como pensamos.

O que isso implica para as pessoas que querem construir sistemas paralelos/concorrentes ? E será possível ter paralelismo nas camadas inferiores, mas um modelo sequencial na superfície (que é mais fácil de entender, portanto), de forma similar ao cérebro ?

Idéias soltas

2004-08-12T11:28:00.000-07:00

Hierarquias de sistemas concorrentes (threads, processos, nós, redes, clusters, grids)
Formalismos: CSP, CCS, pi-calculus
Linguagens: Occam, Erlang, Oz, Alice, CML, Concurrent Haskell, etc
Abordagem: o problema do paralelismo/concorrência como um problema de linguagens de programação/expressividade do programador
Especificações explícitas (Haskell#)
Impedance mismatch entre linguagens de computação e coordenação
Grids e clusters: o panorama arquitetural dos sistemas computacionais do futuro

Execução sequencial ?

2004-08-12T07:46:00.000-07:00

Em oposição à execução concorrente. Imagine seu computador doméstico (garden-variety), que deve ser um Pentium qualquer, ou Athlon, Duron, Celeron, K6, o que seja. Digamos que seja um Pentium III: este é o processador, ou CPU do computador; como o próprio nome diz, é a unidade central de processamento. Tudo que a CPU faz é obedecer ordens, ou seja, executar as instruções que recebe. As instruções estão na memória, e são códigos que dizem "some estes dois números e me dê o resultado", ou coisas similares. O interessante é que, apenas com as operações aritméticas e operações para mover dados na memória de um lugar para o outro, o computador consegue fazer tudo que faz...

Mas estou me desviando do assunto. O importante aqui é que temos apenas um processador nos nossos computadores caseiros usuais. E, a rigor, um processador só pode executar uma instrução de cada vez (*). Por isso dizemos que a execução é sequencial.

E a multitarefa ? E o editor de texto, navegador web, programa de email e campo minado rodando ao mesmo tempo ? Truque simples: tendo vários programas para executar, o processador alterna entre eles o tempo todo, de forma muito rápida. Por exemplo, digamos que existam apenas 5 programas executando. O processador pode executar cada um deles por 2 décimos de segundo de cada vez; em cada segundo, todos os 5 programas serão executados durante algum tempo. Para o usuário, não dá para perceber essas trocas, porque elas são muito rápidas, normalmente mais rápidas que 2 décimos de segundo. E os processadores atuais executam milhares ou milhões de instruções em apenas 2 décimos de segundo. Assim, cria-se a ilusão de vários programas rodando ao mesmo tempo, apesar do processador continuar executando apenas uma instrução de cada vez.

* Isso é uma simplificação. Nos processadores atuais as instruções são executadas em pipelines superescalares; isso significa que, a rigor, mais de uma instrução é executada simultaneamente. Mas com restrições: as instruções devem estar em fases diferentes de execução e são obtidas (fetch) sequencialmente. Os detalhes são complicados, mas em suma isso significa que não é concorrência arbitrária; no fundo, é apenas uma forma de acelerar a execução sequencial.

Antes que eu me esqueça...

2004-08-11T17:15:00.000-07:00

Vou comentar mais sobre a Connection Machine assim que chegar o livro que eu encomendei. Também pretendo definir, de maneira tentativa, o que são sistemas de processamento paralelo e o que são sistemas distribuídos, quais as diferenças entre eles, e outras considerações taxonômicas. E então chegar num ponto onde eu vou tentar responder, principalmente para mim mesmo, qual é a relevância desses assuntos, hoje e no futuro.

Mas vai ser assim, aos pedaços, e tudo diretamente da minha cabeça, sem edição. Então não me culpe se você copiar o que eu digo aqui em um trabalho e o professor expressar a frustração dele com muita tinta vermelha. De resto, a caixa de comentários está aí, logo abaixo dos posts.

Novidade

2004-08-11T17:01:00.000-07:00

Não são assuntos realmente novos. As idéias por trás do processamento paralelo são quase tão antigas quanto os computadores em si (lembrando que os computadores analógicos operavam de maneira paralela, por assim dizer). Computação distribuída, apesar de estar na moda, também não é novidade. Sobre processamento maciçamente paralelo existem trabalhos pioneiros como a connection machine, com a qual até o lendário físico Richard Feynman esteve envolvido.

Por que usar arquiteturas que realizam processamento paralelo ? Intuitivamente, sempre pareceu que ter vários processadores colaborando para uma tarefa comum deveria ser mais eficiente que um único processador trabalhando sequencialmente na mesma tarefa. Imagine, então, se pudéssemos ter dezenas, centenas, quem sabe milhares de processadores trabalhando em conjunto... teríamos um poder de processamento além da imaginação, e poderíamos calcular (computar) várias coisas que são impossíveis hoje em dia.

Essa foi exatamente a idéia por trás da Connection Machine. Mas aí de cara surgiram as dificuldades: a comunicação e coordenação dos processadores se tornaram tão complicadas que o esforço realizado para realiza-las praticamente inviabilizou o projeto. Os projetistas da connection machine tiveram de baixar a bola e pensar mais com os pés no chão, abandonando as idéias iniciais.

E assim foi a história do processamento paralelo, aparentemente. A promessa é tentadora mas os custos altos demais, o que sobe o nível dos problemas para os quais compensa pagar. Por décadas, os supercomputadores usados em aplicações científicas e militares de ponta utilizaram o processamento paralelo como base para sua eficiência. Mas quem pode pagar por um deles ? Apenas um punhado de gente nos países muito ricos.

Mas aí apareceram os clusters na história.