Calculating π via Buffon’s Needle

Posted on by
2

(In honor of Pi Day)

Buffon’s needle is a mathematical problem posed by George-Louis Leclerc, Comte de Buffon, in the 18th century. It’s considered to be the first problem of geometric probability to be solved, and it can be used as a basis for a Monte Carlo method for calculating π. The resulting method is not one of the best ways to calculate π, but it is simple and illustrates the use of Monte Carlo methods.

The problem can be stated as such: (from the Wikipedia entry)

Suppose we have a floor made of parallel strips of wood, each the same width, and we drop a needle onto the floor. What is the probability that the needle will lie across a line between two strips?

Buffon's needle illustration

Two needles thrown on the floor, needle a crosses a line, needle b does not. Needles have length L and the floor strips have width d.

We will think about the experiment in a “probability as frequency of occurrence” way and consider n repetitions of throwing a needle on the floor. As the figure shows, we let L be the length of the needles and d the width of the floor strips. Consider a single needle thrown in the ground; we will call X the distance between the center of the needle and the nearest strip line, and \Theta the smallest angle between the needle and the floor lines.

Buffon's needle variables

A single needle making an angle from a floor line (shown as an horizontal line). X is the distance from the center of the needle to the nearest floor line.

Because \Theta is the smallest angle between the needle and the floor line, it will always be acute, so 0 \leq \Theta \leq {\pi}/{2}, and because X is the distance to the nearest floor line, it’s at most half the distance between lines (which is the strip width d), so 0 \leq X \leq d/2. The needle will cross a line if the center of the needle is closer to the nearest line than to the end of the needle in the direction perpendicular to the strip lines. X is the distance between the center of the needle and the nearest floor line, and the distance (in the direction perpendicular to the lines) between X and the end of the needle is given by (L/2)\sin\Theta (see figure). So the needle will cross a line if

X \leq \frac{L}{2} \sin\Theta.

Following the idea of the probability of an event as a measure of the event set in relation to the sample space, the probability of a needle crossing a line can be seen as the area under the curve y = (L/2)\sin\Theta for \Theta from 0 to π/2, divided by the whole space of values for y and \Theta. We want X < y and, as said before, X can be at most d/2, and \Theta is at most π/2, so the whole space of values is a rectangle with sides d/2 and π/2 (see figure below).

Area for values of X for a cross.

Graph of y=(1/2)sin\Theta. The shaded area shows values of X for which a cross occurs. The probability of a cross is this area divided by the area of the whole rectangle (here shown with d=1).

So the probability of a single cross is

P(C)=\frac{\int_{0}^{\pi/2} \frac{L}{2}\sin\Theta d\Theta}{\frac{d}{2}\frac{\pi}{2}},

which can be calculated to be

P(C) = \frac{2L}{\pi d}.

This last equation is valid only if d is not smaller than L, but this restriction makes sense for the experiment. Now comes the interesting part: make d = 2L and the probability of a cross becomes

P(C) = \frac{1}{\pi}.

The idea is to use a Monte Carlo method to estimate P(C), and this value is the reciprocal or our estimate for π. So, in Monte Carlo fashion, we will simulate the experiment many times, using any values for d and L such that d = 2L, and estimate the expected value of crosses in n repetitions of the experiment. The simulation draws samples from two uniform distributions: X from 0 to d/2 and \Theta from 0 to π/2, and then count the number of repetitions such that X \leq (L/2)\sin\Theta. Then, dividing the number of crosses in the simulation by the total number of repetitions, we get an estimate of the probability of a cross, which is the reciprocal of our estimate for π.

We have one last issue here: to sample \Theta, the usual way would be to get a sample from a Uniform[0,1] random number generator and then multiply by π/2, which requires us to know the value of π already. If we performed the actual experiment, with a real needle and a floor, we would not need the value of π. We will use a small cheat here and assume we have a function for computing the inverse of the sine function and create a variable halfpi that is equal to \sin^{-1}(1). Here’s the code in Julia for estimating π using this idea:

The results are not very good though. Even after millions of iterations, depending on the state of the RNG, I don’t get much more than one or two decimal places correct. In contrast to MATLAB, in Julia vectorized code doesn’t run faster, so here is an iterative version:

Finally, a version in OCaml. Of course, it would be easy to translate the iterative version to OCaml using imperative code, but just to do it differently here’s a pure functional version:

Results aren’t that great too. After almost 1 billion iterations I got π = 3.1415627. There are better ways to calculate π. There are even more efficient ways to use the idea of the Buffon’s needle experiment (see the end of the Wikipedia entry). A statistical analysis of the generated samples would also be beneficial, but this post is already running long. I any case, the idea is neat and serves as an illustration of an interesting application of Monte Carlo methods.

That’s a good classification of research problems

Quote

Posted on by
Reply

(As far as I know, Seymour Papert was the first to use the phrase “toy problem.” At a 1967 AI workshop I attended in Athens, Georgia, he distinguished among tau or “toy” problems, rho or real-world problems, and theta or “theory” problems in artificial intelligence. This distinction still serves us well today.)

Nils Nilsson, “The Quest for Artificial Intelligence“, Part II, p. 47.

Leituras sobre Teoria da Computação, Parte 1

Posted on by
Reply

Ensinar teoria da computação às vezes é difícil pelo grau de rigor matemático e o nível de abstração necessários, mas o assunto em si é fascinante. As características essenciais dos processos computacionais são uma parte inerente da realidade, independente de tecnologias específicas. Daqui a mil anos os computadores atuais serão curiosidades na história da tecnologia, mas quem lidar com computação provavelmente ainda estará falando sobre decidibilidade e classes de complexidade.

Apesar das dificuldades, de vez em quando alguns alunos se interessam pelo assunto além do que vemos em sala de aula. Talvez pela teoria ser universal e atemporal, talvez pela beleza matemática envolvida, ou talvez pelo valor prático de estudar sobre complexidade ou linguagens formais. De qualquer forma, existe um bom número de livros e outros materiais que podem servir para quem quer explorar um pouco mais do terreno da teoria, e cheguei à conclusão que seria melhor juntar todas as indicações e escrever sobre isso.

As indicações estão divididas em duas (ou talvez mais) partes. Neste post eu indico materiais sobre teoria da computação para um público geral; indicações sobre materiais mais técnicos sobre o assunto serão tópico de um post futuro.

Os livros (e a história em quadrinhos) mostrados aqui são escritos para um público geral, que não necessariamente tem formação matemática ou exposição anterior à teoria da computação. Em geral, são mais sobre a história do tópico ou outros aspectos relacionados, com poucos detalhes sobre a teoria em si. Mesmo para quem quer aprender sobre os detalhes teóricos, entender o contexto em que a teoria foi estabelecida e as motivações das pessoas envolvidas dá uma visão mais ampla do tópico. Além disso, esses livros tendem a ser de leitura mais fácil e rápida que os livros teóricos.

Logicomix

Este quadrinho não é propriamente sobre teoria da computação, mas uma história do início da lógica matemática entre os Séculos XIX e XX, contada do ponto de vista de Bertrand Russell. Mas os fundadores do que hoje é chamado de teoria da computação eram matemáticos e lógicos, então as coisas acabam se relacionando. Não por acaso, um dos autores do quadrinho (Papadimitriou) é um importante autor na área da teoria da computação. Além disso, um dos grandes objetivos de Russell na lógica, o Principia Mathematica (escrito juntamente com Whitehead) tem muito a ver com a ideia da mecanização da matemática usando computadores que hoje é um projeto de parte da comunidade de pesquisa em teoria da computação.

Independente das conexões com a teoria da computação, é uma ótima leitura para quem tem qualquer interesse nessa parte da história da matemática e do pensamento humano. Muitos dos personagens principais dessa época aparecem, de Wittgenstein a Gödel.

Existe uma versão brasileira do quadrinho, editado aqui pela Martins Fontes.

Engines of Logic

Este livro de Martin Davis conta a história do desenvolvimento das ideias por trás da computação teórica, desde o sonho de Leibniz de criar uma linguagem composta por símbolos que representam conceitos e uma álgebra capaz de manipular tais símbolos de forma a automatizar o raciocínio, até as contribuições teóricas e práticas de Alan Turing. O livro é bem escrito e muito bem pesquisado, apresentando os temas envolvidos com leveza mas sem leviandade.

Infelizmente não tem edição brasileira, mas para quem lê em inglês é possível achar cópias usadas por um preço baixo na Amazon. Para quem for procurar cópias usadas, é bom saber que a versão em capa dura do mesmo livro tem um título diferente: “The Universal Computer: The Road from Leibniz to Turing”.

O Advento do Algoritmo

Escrito por David Berlinski, este livro cobre mais ou menos o mesmo terreno que o livro de Davis, “Engines of Logic”, com algumas diferenças. Provavelmente para se diferenciar do livro de Davis, Berlinski decidiu misturar capítulos expositivos com capítulos mais puxados para a ficção, com os personagens-chave da história (como Leibniz) contando alguns episódios em primeira pessoa. Na minha opinião isso não funcionou muito bem e, no geral, este livro é inferior ao “Engines of Logic”. A única vantagem de “O Advento do Algoritmo” é que ele foi editado no Brasil há alguns anos, então é uma alternativa para quem só lê em português. Pelo que pode se ver nas livrarias virtuais, o livro está esgotado na editora, mas deve ser possível encontra-lo em sebos.

Alan Turing: The Enigma

Alan Turing foi um dos personagens-chave no desenvolvimento da computação, tanto na teoria quanto na prática, além de ser um pensador original e de grande amplitude; além disso, a história da sua vida é complexa, interessante e mesmo controversa. Esta biografia de autoria de Alan Hodges é geralmente considerada o melhor registro sobre a vida de Turing, e um caso exemplar de biografia bem feita de um grande cientista. Extremamente bem pesquisada e sem se prender a ser apenas uma apologia de uma mente brilhante, minuciosa e detalhada sem ser maçante, o livro de Hodges é de leitura recomendada mesmo para quem não é da área da computação.

Mais uma vez, este é um livro sem edição brasileira. Até recentemente o livro estava fora de catálogo nos EUA também, mas como 2012 foi o ano do centenário de Turing, saiu uma nova edição em comemoração ao centenário, incluindo versões em ebook.

O Homem que Sabia Demais

Esta é uma outra biografia de Turing, escrita por David Leavitt. Serve como introdução à vida de Turing, até por ser um livro curto, e para alguns leitores pode ser o suficiente. Existe uma versão brasileira do livro, que é o maior motivo para ele aparecer nesta lista, já que como biografia ele é inferior ao livro de Hodges. Inclusive a biografia escrita por Hodges foi claramente a fonte primária para o livro de Leavitt, que a cita frequentemente ao longo do texto. Sendo mais direto, o livro de Leavitt parece um resumo de “Alan Turing: The Enigma”. Enquanto o livro de Hodges não estava disponível, ou para quem não consegue ler textos em inglês, esta biografia pode servir como substituto, mas quem tiver condições deve preferir o original ao resumo.

Gödel, Escher, Bach

Um clássico escrito por Douglas Hofstadter, “Gödel, Escher, Bach” não é exatamente sobre teoria da computação, mas passa por vários tópicos relacionados. Boa parte do livro serve como um tutorial não-convencional sobre lógica matemática, no meio das considerações sobre o papel da recursividade nas artes visuais, na música e na matemática. É um livro longo, cheio de ideias e de desvios interessantes, mas que eventualmente revela seu fio principal: apresentar os teoremas de incompletude de Gödel (daí o tutorial sobre lógica) e as ideias do autor sobre inteligência artificial e a consciência humana. Mais especificamente, uma das ideias principais é que os teoremas da incompletude de Gödel não inviabilizam a possibilidade de uma inteligência artificial “real” com características da inteligência humana. No meio da discussão sobre inteligência surge também um dos artigos famosos de Alan Turing, “Computing Machinery and Intelligence”, pelo qual ele é considerado como um dos pais da IA. Ao todo, um livro interessantíssimo e cheio de “caminhos que se bifurcam”, mesmo que não seja especificamente sobre computação.

Houve uma boa edição brasileira há alguns anos, que atualmente parece estar esgotada, mas deve ser possível de encontrar em sebos. As várias edições em inglês são bastante fáceis de encontrar para vender.

Incompletude

Assim como o anterior, este livro está na lista mais como bônus. Kurt Gödel foi um dos matemáticos mais geniais do Século XX, e sua vida pessoal também foi atribulada. Os teoremas de incompletude chocaram a comunidade matemática quando foram divulgados, acabando com o projeto formalista de David Hilbert; Gödel não tinha mais que 23 anos quando formulou e provou os teoremas. A incompletude foi fundamental nos questionamentos que levaram ao desenvolvimento da teoria da computação, e serviu como inspiração para a prova da indecidibilidade do problema da parada, descoberta por Turing. Não é à toa que praticamente todos os livros desta lista mencionam Gödel em algum momento.

“Incompletude” é um livro curto, que se divide entre traçar um esboço biográfico de Gödel e apresentar as ideias principais dos famosos teoremas que ele provou, assim como as correntes filosóficas por trás das ideias de Gödel e do Círculo de Viena, um grupo de lógicos matemáticos do qual ele fazia parte. No geral deixa a desejar em alguns pontos, mas é de leitura interessante principalmente para quem tem algum interesse em filosofia, já que a autora tem formação em filosofia e parece estar mais interessada nas questões filosóficas envolvidas na vida e trabalho de Gödel. Além disso, é um dos poucos livros sobre Gödel que possuem edição brasileira, que ainda pode ser encontrada para vender. Sobre os teoremas da incompletude e as provas de Gödel existem fontes melhores, entre elas “Gödel, Escher, Bach” e o famoso “Gödel’s Proof” de Nagel e Newman, que será um dos livros indicados na próxima parte.

QCon SP 2012

Posted on by
Reply

Este ano tive o prazer de ser convidado a palestrar no QConSP. O evento foi excelente e sem dúvida merece a fama de um dos melhores eventos de desenvolvimento de software do país. Além disso sempre tem o lado bom de encontrar as pessoas, algumas já conhecidas de outros eventos, outras já conhecidas pela internet mas não pessoalmente e algumas outras conhecidas por lá. Como estou na academia já há alguns anos, sempre aprendo muito nesses eventos com desenvolvedores, só ouvindo e participando das conversas.

Não pude assistir à todas palestras que queria mas as que eu vi foram boas. Destaco aqui duas que são de interesse geral, independente de detalhes tecnológicos específicos:

Duas outras eu não consegui assistir mas ouvi falar bem e gostei dos slides:

Tem mais outras que achei interessante e vou olhar os slides que foram divulgados depois (tem uma lista no post da Caelum sobre o evento).

Com relação à minha palestra, o tema era muito interessante, mas devo dizer que não fiquei totalmente satisfeito. As ideias para a palestra ficaram fermentando na minha cabeça por semanas, mas no final acredito que o nível e a abordagem utilizadas não foram as melhores para o evento e o tempo disponível. A sala estava lotada e pelo menos algumas pessoas (suspeito que todas sejam “programming language geeks” como eu) disseram que gostaram, mas acredito que podia ser melhor. De qualquer forma, os slides estão disponíveis no Slideshare. (O título inicialmente era “O Ser e o Tipo”, uma referência ao livro de Sartre, basicamente porque eu não tive nenhuma outra ideia; depois considerando a questão sobre verificação estática versus dinâmica, pensei que o tempo era parte importante da história, daí “O Tipo e o Tempo”).

I am an emacs-person

Posted on by
1

I’ve been using emacs as my main editor for a good number of years now, starting when I had to use and old version of Linux for a project. At the time there wasn’t much real choice for a programmer’s editor in Linux, beyond the usual: vi and emacs. I’ve never liked vi’s modal interface (got fed up with all the beeping while trying to use it), so I went with emacs. It’s decidedly old-school, and it’s not perfect, but  few other editors have what I need from it: features, easy portability and easy extendability. Among the newer editors I’ve tried (a lot of them) the only one that comes close to emacs is Sublime Text 2.

The ability to easily reprogram or extend your programming tools, especially your editor, is important and often underrated. After some time doing Java professionally, I’ve dabbled in extending Eclipse, even implementing a simple plugin to support OCaml. It’s an environment where the simplest extension or modification is a nightmare to do. Eclipse: write a lot of XML files, select classes to subclass, understand the design patterns and complex relationships between the classes you’re subclassing, write a lot of boilerplate code, compile, open a new instance of Eclipse, test, repeat. Emacs: write some lines of emacs lisp, eval, test, repeat. So much for OO. Other IDEs like Visual Studio aren’t much better than Eclipse, as far as I know.

Of course, this all comes at the cost of a steep learning curve. And to be able to effectively extend Emacs you have to learn Lisp. However, in both cases I think they are worthy investments for a programmer’s toolbelt. Not everyone has to like and use emacs, but a programmer should learn to Use a Single Editor Well, in the words of the pragmatic programmers. Do you truly command your editor, or do you only know how to type, copy & paste?

 

On typing

Posted on by
1

So I was reading this post by Rafael on his experience with Ruby and started writing a comment, mostly about the typing issue. I soon realized that there was too much I wanted to say in a comment, hence this post here.

I believe I have a good amount of experience both with static typing and dynamic typing (for simplicity, I’ll be sloppy with the terms here, for instance calling it “dynamic typing”, even though it may be more precise to talk about “dynamically-typed languages” or “unityped languages”). For a lot of time I programmed in C and C++ (and some Java), then I wrote a lot of Scheme and Common Lisp while learning about Lisp and functional programming, and later I discovered the statically-typed functional languages like OCaml and Haskell. The last two are my preferred languages currently, so I’d say I have a preference for static typing, or at least for more “modern” static typing systems. Between Java/C++ and Lisp, I think I’d prefer Lisp.

But although I have studied some programming language theory, mostly from the typed side, I don’t at all agree with the “statically-typed fundamentalist” view that dynamic typing is just a special case of static typing (like argued here by Robert Harper), and therefore you have nothing to gain by using a dynamically-typed language. The theoretical argument may be correct, but correctness does not translate to convenience in a real programming situation. I do think dynamic typing has its advantages, mostly for exploratory programming and prototyping.

Of course, if I still prefer to program in statically-typed languages, I must have reasons for it, and indeed I do. One of these is that types are a form of documentation: when writing a Lisp function I often put the typing constraints the function expects in a comment, so that callers know what to pass to it. Why not make these annotations verifiable by the compiler? This is also the reason many Haskell programmers write function types explicitly, even when the compiler can infer them most of the time. Having type inference is very good for rapid prototyping and to avoid excessive verbosity whenever needed. Also, even if I don’t write explicitly the types for a function in a language with type inference, a good programming environment can show the inferred types, thus fulfilling the documentation role of types in a way that’s not easy to do with dynamic typing.

Regarding tests, it’s true that tests can catch typing errors, and that type-checking by the compiler will catch only a fraction of the program’s bugs. If your specification is wrong, no typing system will help you, ever, unless it uses advanced artificial intelligence and, in this case, you’re not programming anymore because the machine is doing everything. However, saying only that tests can catch typing errors as well as the compiler for a static language misses one important point: the compiler does it automatically, while you, the programmer, have to write the tests. Using tests to catch type errors shifts the burden from the compiler to the programmer. Because type-checking can’t catch all program errors, it’s still necessary to write tests even in a static language, but the amount of tests you’d have to write is smaller as you don’t need to check for simple type constraints.

Statically-typed languages also tend to have better performance and better support for programming tools. I don’t believe this is inherent to static typing, but it seems to be easier to write better compilers and better tools if more analyses can be done with certainty because the language is designed to keep specific typing guarantees. Types also allow for nice techniques like typed compilation and typed intermediate languages, which I think could be better explored by compiler and tool writers.

All in all, programming in a modern statically-typed language with type inference gives me most of the convenience of dynamically-typed languages, with all the advantages of a static type system and associated compiler. There are some times when I miss the freedom of dynamic typing when programming in a static language, but so there are times when I miss the conveniences of type-checking when programming in a dynamic language.

I guess the solution is to integrate the best aspects of both sides, and this seems to be a research theme for many important people in the area of programming languages recently (examples: Visual Basic, Typed Racket, and the Types Considered Harmful presentation by Pierce). At least we can hope this holy war will, one day, be settled for all time.

Resolvendo Desafios mais Complicados com Prolog

Posted on by
1

No post anterior foi mostrado como resolver desafios de lógica no estilo do Teste de Einstein em Prolog. Entretanto, o processo de geração no esquema de geração e teste era bastante ineficiente para problemas mais complexos. O problema é que muitas possibilidades são geradas e descartadas quando é feita a verificação de diferença. Por que não gerar as possibilidades já todas diferentes, eliminando esse teste extra?

Em Prolog o predicado select(X, L, R) seleciona o elemento X na lista L, e retira X de L formando o resto R. Ou seja, R tem todos os elementos de L, menos o elemento selecionado X. Isso pode ser usado para, dada a lista de possibilidades para cada atributo (por exemplo, cores de casa), retirar uma possibilidade da lista para gerar uma casa, depois usar o resto da lista para gerar as cores para as outras casas. Assim, duas casas nunca serão geradas com a mesma cor.

Como exemplo, vamos usar o próprio teste de Einstein, porque ele tem mais possibilidades e não é possível de resolver eficientemente com o esquema do post anterior. O problema tem cinco casas, cada uma com cinco atributos: a cor da casa, a nacionalidade do morador, a bebida preferida do morador, o cigarro preferido e o animal de estimação. As dicas são:

  • O Norueguês vive na primeira casa.
  • O Inglês vive na casa Vermelha.
  • O Sueco tem Cachorros como animais de estimação.
  • O Dinamarquês bebe Chá.
  • A casa Verde fica do lado esquerdo da casa Branca.
  • O homem que vive na casa Verde bebe Café.
  • O homem que fuma Pall Mall cria Pássaros.
  • O homem que vive na casa Amarela fuma Dunhill.
  • O homem que vive na casa do meio bebe Leite.
  • O homem que fuma Blends vive ao lado do que tem Gatos.
  • O homem que cria Cavalos vive ao lado do que fuma Dunhill.
  • O homem que fuma BlueMaster bebe Cerveja.
  • O Alemão fuma Prince.
  • O Norueguês vive ao lado da casa Azul.
  • O homem que fuma Blends é vizinho do que bebe Água.

Das dicas podemos tirar as possibilidades de cada atributo. Para gerar as cores, usamos o predicado abaixo, que é só um wrapper mais conveniente para select, passando a lista de cores disponíveis e recebendo o resto das cores disponíveis na última posição:

Depois é só gerar os outros atributos da mesma forma:

Com isso, podemos gerar uma casa inteira e um conjunto de casas usando um mapeamento recursivo:

A estrutura atr guarda as listas com todos os atributos disponíveis, para simplificar o código.

Para resolver o teste de Einstein é preciso estabelecer quando dois moradores são vizinhos, como é mencionado em várias dicas. Considerando a lista de soluções S, como gerada pelo predicado gera_sol, acima, podemos criar predicados simples que testam (ou geram) moradores vizinhos na solução, inclusive separando vizinhos esquerdos de vizinhos direitos, pois uma dica especifica o lado:

Agora é só traduzir as dicas e fazer os testes para obter a solução. Aqui mais um truque pode ser usado: embora a ordem conceitual seja gerar as possibilidades e depois testa-las, no caso de muitas possibilidades (como neste desafio) o processo computacional pode se tornar ineficiente. Então usamos as propriedades do Prolog para resolver o desafio mais rapidamente. Em um predicado Prolog “puro” (sem cortes ou negação) podemos mudar a ordem dos objetivos em uma conjunção sem alterar o resultado. Todos os predicados usados até agora são puros, então podemos colocar os testes antes, para criar restrições sobre a solução, e chamar o predicado de geração depois para verificar as restrições e gerar o que falta. Isso feito, o resultado para o teste de Einstein sai bem rápido em um computador atual. Com essas considerações, o código que testa as dicas do problema e encontra a solução é:

E o resultado sai realmente rápido:

?- solucao(S).
S = [casa(amarela, noruegues, agua, dunhill, gato),
     casa(azul, dinamarques, cha, blends, cavalo),
     casa(vermelha, ingles, leite, pallmall, passaro),
     casa(verde, alemao, cafe, prince, peixe),
     casa(branca, sueco, cerveja, bluemaster, cachorro)] .

O programa completo pode ser visto aqui. A elaboração deste programa contou com a colaboração do aluno Josué Gomes (@jgomesj).

Resolvendo Desafios de Lógica com Prolog

Posted on by
1

Dado que em Prolog é fácil criar estruturas (termos compostos) e fazer buscas sujeitas a certas restrições, é fácil resolver os tais desafios de lógica usando a linguagem. O tipo de desafio de lógica em questão é similar aquele “teste de Einstein” que algumas correntes de email dizem que só meia-dúzia de pessoas no mundo conseguem resolver (o que é uma grande balela). Várias informações (mas não todas) são dadas sobre um conjunto de indivíduos, e é preciso deduzir as informações que faltam para chegar na solução. Resolver um problema desses em Prolog é uma forma de explorar várias características de linguagem e alguns padrões de uso.

A Coquetel publica uma linha de revistas de Desafios de Lógica desse tipo, usando uma tabela para ajudar a cruzar as informações e resolver o problema. Esses problemas são um pouco diferentes porque algumas informações não estão nas dicas, mas apenas nas listas de atributos nas tabelas, e porque às vezes é preciso raciocinar por exclusão (assumindo que não existem duas pessoas com o mesmo atributo). Para a solução (em Prolog) de um puzzle simples no estilo do teste de Einstein, veja esse post acolá. Aqui vou mostrar a solução para um problema de uma revista Desafios de Lógica (número 98). Sem colocar a tabela, aqui estão as informações dadas (espero que a Coquetel não me processe):

Desafio: Primeiro de Abril
Quatro pessoas que gostam de pregar peças decidiram tornar o primeirode abril inesquecível, ou seja, com muitas brincadeiras. Cada um pregou uma peça numa vítima diferente usando um objeto inofensivo.

  • Nomes: Ana, Ester, Pablo, Rodolfo
  • Sobrenomes: Fontes, Levis, Matoso, Salgado
  • Brincadeiras: Almofada de barulho, Aranha falsa, Foto alterada, Mosca falsa
  • Vítimas: Irmão, Mãe, Pai, Tia

Dicas:

  1. Ana deu risadas enquanto colocava uma aranha falsa na comida de sua vítima.
  2. A pessoa de sobrenome Salgado (que não é Ana) pregou uma peça em seu irmão.
  3. A pessoa de sobrenome Matoso colocou uma almofada de barulho na cadeira de sua vítima.
  4. Rodolfo pregou uma peça em sua tia, mas não foi ele que usou a almofada de barulho.
  5. A brincadeira feita por Levis incluía uma mosca falsa. A vítima de Ester foi seu pai.

Para garantir que todas as possibilidades são examinadas e são testadas posteriormente, incluindo as partes de dedução por exclusão, decidi usar o padrão “gerar e testar” (generate-and-test) que é comum em Prolog: gerar todas as possibilidades e ir restringindo (testando) até achar a solução.

Geração

Começando com a geração: o procedimento a seguir gera todas as configurações possíveis, se for usado backtracking. Para representar as informações de uma pessoa, usei uma estrutura p(Nome, Sobrenome, Brincadeira, Vítima).

/* p(Nome, Sobrenome, Brincadeira, Vitima) */
gera(p(N, S, B, V)) :- 
    member(N, [ana, ester, pablo, rodolfo]),
    member(S, [fontes, levis, matoso, salgado]),
    member(B, [almofada, aranha, foto, mosca]),
    member(V, [irmao, mae, pai, tia]).

O procedimento gera as possibilidades corretas usando o predicado pré-definido member, garantindo que o nome gerado será um entre [ana, ester, pablo, rodolfo], e por aí vai. Podemos testar a geração fazendo uma consulta como

?- gera(P).

O próximo passo é gerar não só um indivíduo, mas uma solução completa, que são quatro indivíduos. Se simplesmente usarmos

?- gera(P1), gera(P2), gera(P3), gera(P4).

serão gerados muitos grupos com indivíduos repetidos. Precisamos garantir a geração de quatro indivíduos diferentes em todos os atributos. Não funciona se tentarmos usar P1 \= P2 e por aí vai, porque o Prolog vai dizer que duas estruturas que diferem em apenas um dos termos são diferentes. Por exemplo,

?- p(ana, fontes, almofada, irmao) \=
     p(ana, fontes, almofada, mosca).
true.

Precisamos diferenciar todos os atributos. Além disso, é preciso ter quatro indivíduos diferentes dois a dois, pois se P1 é diferente de P2 e P2 é diferente de P3, é possível que P1 seja igual a P3, e por aí vai. Assim, definimos

dif(p(N1, S1, B1, V1), p(N2, S2, B2, V2)) :- 
    N1 \= N2, S1 \= S2, B1 \= B2, V1 \= V2.

todas_dif(P1, P2, P3, P4) :- 
    dif(P1, P2), dif(P1, P3), dif(P1, P4), 
    dif(P2, P3), dif(P2, P4), dif(P3, P4).

Agora, se testarmos uma consulta do tipo

?- gera(P1), gera(P2), gera(P3), gera(P4),
   todas_dif(P1, P2, P3, P4).

Só veremos soluções em que as quatro pessoas são diferentes em todos os atributos. Falta testar as possibilidades geradas com as dicas dadas no problema para encontrar a solução.

Testes

A solução consiste de quatro indivíduos, todos diferentes (usando o critério de diferença discutido), que se encaixem nas dicas dadas pelo problema. A ideia é capturada no procedimento que resolve o problema:

solucao(S) :- 
     S = [P1, P2, P3, P4], 
     gera(P1), gera(P2), gera(P3), gera(P4), 
     todas_dif(P1, P2, P3, P4), 
     member(p(ana, _, aranha, _), S),
     member(p(N, salgado, _, irmao), S), N \= ana, 
     member(p(_, matoso, almofada, _), S), 
     member(p(rodolfo, _, B, tia), S), B \= almofada,
     member(p(_, levis, mosca, _), S),
     member(p(ester, _, _, pai), S).

O primeiro objetivo da solução apenas diz que S (a solução) é uma lista de tamanho 4, formada por P1, P2, P3 e P4. Na segunda e terceira linha do corpo da cláusula, temos o padrão de geração discutido antes. Depois, cada linha é um teste que representa uma dica do problema. O primeiro teste diz que Ana usou a Aranha como brincadeira, mas não conhecemos seu sobrenome nem qual foi sua vítima; esse indivíduo faz parte da solução (usando o predicado pré-definido member). A segunda diz que a pessoa de sobrenome Salgado pregou uma peça no irmão; não conhecemos o nome dessa pessoa, mas sabemos que não é Ana, como expresso pela desigualdade seguinte. As outras linhas traduzem as outras dicas, sem maiores novidades.

Carregando o código inteiro em um sistema Prolog como o SWI-Prolog, e fazendo a consulta

?- solucao(S).

A resposta deverá aparecer após algum tempo. Dependendo do computador, isso pode demorar alguns minutos, o que é ruim. Além disso, são retornadas soluções equivalentes, em que apenas a ordem dos indivíduos muda. Isso tudo demonstra que o sistema Prolog está buscando em um espaço de estados muito maior do que necessário. Podemos fazer isso de maneira mais eficiente.

Geração mais eficiente

Não afeta a resolução dizer que o primeiro indivíduo na solução tem nome Ana, o segundo Ester, o terceiro Pablo e o quarto Rodolfo. Isso restringe o espaço de busca sem eliminar a solução. Se gerarmos as possibilidades já prendendo esses atributos, a busca pela solução se torna muito mais rápida. Definimos um novo predicado para gerar as possibilidades mais eficientemente:

gera_ef(P1, P2, P3, P4) :- 
    P1 = p(ana, _, _, _), 
    P2 = p(ester, _, _, _), 
    P3 = p(pablo, _, _, _), 
    P4 = p(rodolfo, _, _, _), 
    gera(P1), gera(P2), gera(P3), gera(P4), 
    todas_dif(P1, P2, P3, P4).

Depois é só usar esse predicado na busca pela solução. Além disso, só precisamos de uma solução, então vamos incluir um corte no final para evitar cálculos inúteis. O resultado é

solucao2(S) :-
    S = [P1, P2, P3, P4],
    gera_ef(P1, P2, P3, P4),
    member(p(ana, _, aranha, _), S), 
    member(p(N, salgado, _, irmao), S), N \= ana, 
    member(p(_, matoso, almofada, _), S),
    member(p(rodolfo, _, B, tia), S), B \= almofada, 
    member(p(_, levis, mosca, _), S), 
    member(p(ester, _, _, pai), S),
    !.

E agora uma consulta do tipo

?- solucao2(S).

Vai achar a solução muito mais rápido. O código completo pode ser visto aqui.

P.S.: Agora que o github abriu o código para detecção de linguagens e syntax highlighting, queria ter tempo de implementar suporte decente a Prolog. O github acha que meus arquivos Prolog (extensão .pl) são Perl.

A (meta-)guide to CamlP4: Metaprogramming in OCaml

Posted on by
1

This post is meant to be a guide to the available documentation and tutorials about CamlP4, assuming no previous experience with it. The topics are presented in the best order (IMO, of course) for learning, under this assumption. Before attempting to learn CamlP4, it is recommended to learn how to program in OCaml reasonably well, and to have at least some familiarity with parsing and programming language tools. If you have the prerequisites, though, this guide should at least make learning CamlP4 a little easier than going blind after everything returned by a search for “CamlP4″. The intention is to give the Big Picture, so that the details can be worked out later.

Roadmap

  • Introduction: what is CamlP4.
  • Revised Syntax: CamlP4 uses an alternative concrete syntax for OCaml. To learn CamlP4, you must learn this alt syntax.
  • Quotations: CamlP4 is generally used to generate OCaml code, one way or another. With quotations this is easier. Quotations are customizable, so it can be used for other concrete syntaxes beyond OCaml’s.
  • Grammars and Extensible Parsers: CamlP4 has an embedded notation for parser generation. This can be used for defining parsers or extending existing ones.
  • Filters and Printers: the final output of CamlP4 is a syntax tree, printed in a chosen format. This tree can also be filtered before printing.
  • Putting it all together: the structure of a syntax extension for OCaml, and links to examples.
  • Sources: links to and comments on the CamlP4 tutorials and guides available in the Web. Most of them are linked in a previous part.

Introduction

CamlP4 is the Pre-Processor and Pretty-Printer for OCaml. Given textual input, CamlP4 parses the input into an abstract syntax tree, which is then printed in some format. Both the parser and the printer processes are customizable, so it’s a very flexible tool for programming language processors.

CamlP4 is mostly used as a metaprogramming tool for OCaml, but it can be used in many ways:

  • to quickly create small parsers in OCaml
  • to pretty-print OCaml programs (it probably could be used as the standard formatting tool for OCaml code, as gofmt is used in the Go Language)
  • to integrate external syntaxes via a quotation mechanism (SQL queries, for example)
  • to generate OCaml code from the output of a parser or a quotation (so you can compile a DS(E)L to OCaml code)
  • to change OCaml’s concrete syntax, adding new syntactic forms, removing existing forms or changing the existing forms. Of course, it is possible to completely change OCaml’s syntax using these mechanisms

As this list shows, it is a very powerful and useful tool for parsing and metaprogramming. It is often used to write syntax extensions to OCaml, like adding support for a notation for monads or for list comprehensions.

It’s also kind of a mess.

Many factors contribute to this. First of all, if you’re used to metaprogramming in Lisp languages (as I was before meeting CamlP4), there’s the increased complexity of metaprogramming with a statically-typed language with non-uniform syntax. Then there’s the fact that CamlP4 defines a different concrete syntax for OCaml, called Revised Syntax, and to effectively use CamlP4 you have to know this new syntax; not only that, but a non-trivial program using CamlP4 will probably use both syntaxes, in the same source files. So the first order of business if you want to learn to use CamlP4 is learning the Revised syntax.

Revised Syntax, or A Tale of Two Pre-Processors

Ok, how’s the Revised syntax then? This brings up another source of confusion: there are actually two Pre-Processor-Pretty-Printers for OCaml: CamlP4 and CamlP5 (which was CamlP4 before). The story, as far as I know (which isn’t much) is this: Daniel de Rauglaudre wrote the original CamlP4, which was available for OCaml since its early versions. For OCaml 3.10, however, the OCaml team wanted to make changes in CamlP4, and the original author didn’t agree with them. So a fork ensued: CamlP4 is the version included in the official OCaml distribution, maintained by the core team; CamlP4 is mostly compatible with the old CamlP4, but enough changes were made so that most code written for the old version does not work with the current one. CamlP5 is the “old” CamlP4, renamed and maintained by the original author, Daniel de Rauglaudre. It is (or was) completely compatible with the old versions of CamlP4, although apparently it is now introducing incompatible changes. In this post I’ll stick with CamlP4 for the current versions, mostly because it’s already there in the official OCaml distribution.

Back to the Revised syntax: it’s not very well documented. Actually, although the old CamlP4 had an official reference manual and tutorial, the new CamlP4 has neither. The current version of CamlP4 has a kind of official documentation in a wiki, but it’s quite incomplete. There’s a page in the wiki about the Revised syntax, but it’s missing a lot. The section about the Revised syntax in the latest official reference manual for the old CamlP4 (version 3.07) is complete, but inaccurate; some changes in the Revised syntax were made in version 3.10. For now, there are no better option, so the only way out is to read both sources and try to integrate them mentally. Or read the CamlP4 sources, in this case the OCaml parsers. The relevant files are pointed later, in the section about parsers.

However, there is a good source of examples of the revised syntax: CamlP4 itself is written in this syntax. So it’s possible to take a look at the sources (included in the OCaml source distribution) to look at how things are done.

If you know the revised syntax, you can start to use quotations to generate OCaml code.

Quotations and Abstract Syntax

Quotations allow the programmer to treat a piece of code as data instead of being part of the program itself. They are widely used in Lisp because of its uniform representation for code and data, and are widely used when programming in CamlP4 because they make it easier to generate code. Ultimately, CamlP4′s output is an abstract syntax tree, printed in some chosen format. The AST nodes are defined with algebraic data types, so it’s possible to generate code just by creating a value of the right type. However, this type is recursive (as expected for an AST) and trees for any non-trivial piece of code will be complicated to create as a value of the AST type. For example, this piece of code:

let f x = x * x in f 5

corresponds to this AST as a value:

It’s easy to see that it’s already unbearable to generate AST nodes creating values of the algebraic data type, even for a single line of code. If, instead, you simply quote the line of code above, CamlP4 will expand the quotation into the same AST. The only thing to be aware of is that OCaml code inside quotations must use the revised syntax. Support for the original syntax inside quotations was added in OCaml 3.10, but it is considered to be in beta, and it seems to be broken as of 3.12.

Quotations also allow for antiquotations, which are parts of a quotation that should be evaluated instead of directly transformed to AST nodes. This is basic in code generation: we use code templates for translation/generation, but the templates wouldn’t be very interesting if they were fixed pieces of code. Instead, each template has gaps that must be filled with data which depends on the situation. This is similar to the way format strings work in printf-like functions. It is also possible to have a quotation inside an antiquotation, and an antiquotation inside this quotation that is inside the antiquotation of the original quotation, and so on. I know this sounds confusing, as messing with quotations can often be, but in most cases it is easier to learn them by example.

As with most things in CamlP4, quotations are also customizable. It is possible to define new quotation expanders, in practice adding support for quoting pieces of code in a syntax different than OCaml’s. Expanders can also generate strings instead of AST nodes, although this is less useful.

To learn about quotations (and antiquotations), the reference manual for the old CamlP4 has a general overview that’s still applicable. To learn how to use quotations to generate OCaml AST nodes, you can look at this appendix from the same manual. The CamlP4 wiki has a page on quotations, and a page making an analogy between quotations and strings. Jake Donham has written a series of posts in his blog about CamlP4. Part 2 and part 3 are about quotations from the perspective of a user, while part 8 and part 9 are about implementing new quotations and antiquotations. Two warnings though: he sometimes writes as if you already knew this stuff, and parts 2 and 3 about quotations use OCaml quotations in original syntax; they mostly don’t work with OCaml 3.12. That’s one more situation where knowing the revised syntax comes in handy.

Grammars and Extensible Parsers

CamlP4 makes it easy to create parsers, because it includes an embedded notation for parser generation. The user defines a grammar using a special notation, and CamlP4 generates a parser for it. There’s a simple tutorial in the CamlP4 wiki about grammars; despite being titled “Syntax Extensions”, it is not about syntax extensions for OCaml, but about a parser for a simple external language for expressions. The reason for the title will be explained in a bit. There’s also a sequel tutorial showing how to generate code for the simple expression language, using quotations.

The good thing about grammars and parsers in CamlP4 is that they are extensible. Any loaded module can extend a grammar defined in another module, and an extension can not only add new productions, but also change existing ones or even delete them. That’s why the tutorial above is called “Syntax Extension”: it is extending the empty grammar to define the syntax for a simple expression language.

And now for the punchline: CamlP4 comes with parsers for the syntax of OCaml (revised and original variants, possibly others). So if you extend the OCaml grammar from CamlP4, you can change OCaml’s syntax. That’s the way to create syntax extensions for OCaml.

Besides the above-linked tutorials in the CamlP4 wiki, the section about grammars in the old manual is still very useful. Part 6 of Jake Donham’s series about CamlP4 is a good reference, and goes into quite some detail about the parsing methods used by CamlP4. You can ignore everything about streams and stream parsers if you want, it’s just a somewhat old notation for simple recursive descent parsers that are not needed for extending OCaml’s syntax.

Filters and Printers

So CamlP4 parses its input and then builds an abstract syntax tree out of it. This AST will be emitted, or printed, in a chosen format. Between parsing and printing, it is possible to define AST Filters that can transform the tree, including maps and folds over it.

From the point of view of syntax extensions for OCaml, CamlP4 parses OCaml code, most likely using an extended syntax, generates an AST that may be filtered, and then prints it. The generated AST can be emitted by a pretty-printer, showing code in a readable format for humans. You could feed the output of the pretty-printer to the OCaml compiler, thus effectively activating the syntax extension. However, this has some disadvanges:

  • The compiler would need to read and parse the input again, making the compiling process take longer
  • Errors detected by the compiler wouldn’t necessarily be reported at their original locations, but rather at the locations resulting from pre-processing (this is a common problem with pre-processors)

Fortunately, there’s a solution: CamlP4 has a printer that emits the AST in a binary, marshaled form for the OCaml compiler, which can then skip the parsing stages and use the tree directly. The marshaled tree also includes location information, which allows the compiler to report errors correctly for the input source.  To use this from the OCaml compilers, you just need to use the -pp command-line flag. This page in the CamlP4 wiki has a good overview about using CamlP4 by itself and together with a compiler.

It is also possible to define new printers, though most of the time this is not very useful.

Putting it all together: OCaml syntax extensions

Conceptually, the plan is simple: extend the OCaml parser in CamlP4, generate code for the extensions using quotation, then feed the generated tree to the compiler. To extend the OCaml parser, it may be useful to take a look at how it is defined for the standard syntax(es). In the OCaml sources, the parsers are available in the directory camlp4/CamlP4Parsers. CamlP4OCamlRevisedParser.ml is the parser for the revised syntax, while CamlP4OCamlParser.ml is for the original syntax. The latter one is defined as an extension of the former, so you may need to consult both.

A good idea is to look at examples of simple syntax extensions. The wiki has a page with a simple extension for float expressions (this extension uses a map over the AST to avoid having to rewrite many grammar productions). Richard Jones posted an example in the official Caml-list for wrapping pattern matching in a predicate. Part 11 in Jake Donham’s series includes a sequence of examples, starting with a very simple one. More examples can be found in the recommended sources below.

Sources and Final Thoughts

CamlP4 gives OCaml programmers much of the power of metaprogramming available in Lisp languages, added with static type checking and customizable components. Some things CamlP4 can do, like integration of external syntaxes in OCaml programs, are not easy to replicate in Lisp. However, it is a quite complex piece of software and this is sometimes exposed to users. Furthering the difficulties, it is now fragmented (CamlP4 and CamlP5) and not very well documented. I hope this post helps people get up to speed in using this handy tool.

As I mentioned, this is not a tutorial on CamlP4. A proper tutorial would be quite useful, but it would also demand much more time from me, so I decided to do the next best thing: give some pointers and commentary on the documentation and tutorials that are available out there. So here’s a list of other good sources about CamlP4, with commentary:

  • The old CamlP4 manual is outdated, but still useful because there’s no equivalent for the new CamlP4.
  • The series of posts on CamlP4 over at Ambassador at the Computers is a good source, with some caveats. Jake Donham probably knows a lot more about this stuff than me, but sometimes he seems to be writing to people who already know about CamlP4, especially in the first few posts. The sequence could start better. He also uses quotations in original syntax in the earlier parts, rendering the example code unusable in current versions of OCaml (in some cases he linked to newer versions that work). On the other hand, the posts often go deeper than what is available elsewhere, so it’s worth it.
  • The new CamlP4 wiki has useful stuff, although it is incomplete both as a tutorial and as a reference.
  • This CamlP5 tutorial by Martin Jambon is very good. I just found out about it as I was almost finished writing this post. It is the kind of tutorial I think is missing for CamlP4, but unfortunately, it is targeted to CamlP5, aka the old CamlP4. Still very useful.

Besides that, there are always the sources.

P ?= NP como um problema de decisão (POSCOMP 2010)

Posted on by
Reply

O post abaixo foi publicado inicialmente em uma lista de discussão, em resposta ao email de outro participante, que estava em dúvida se a resposta do gabarito de uma questão do POSCOMP 2010 estava correta. A questão está na imagem abaixo, com a resposta do gabarito indicada em vermelho.

Questão 50 POSCOMP 2010

A questão aí é mais sutil do que parece à primeira vista. O enunciado não fala diretamente sobre como decidir se P != NP é verdade ou não, mas pede para considerar a hipótese P != NP como um problema de decisão a ser resolvido por um algoritmo, ou seja, por algum autômato. Um problema de decisão é uma questão para a qual um algoritmo deve responder apenas uma das duas possibilidades: ou SIM ou NÃO.

Normalmente, problemas de decisão são esquemas gerais para uma coleção de problemas particulares que são instâncias do caso geral; por exemplo, veja o problema da parada: decidir se uma máquina de Turing (ou seja, um programa) específica sempre termina sua computação com uma resposta definitiva, ou não. Esse é um problema geral. Uma instância desse problema seria pegar uma máquina de Turing M1 (que basicamente contém um programa específico) e perguntar: essa máquina M1 sempre pára e chega a uma resposta? Veja que para alguns casos a decisão é bem simples; imagine por exemplo uma máquina de Turing que desconsidera a entrada e apenas imprime uma sequência qualquer de símbolos na fita (digamos, a sequência “Hello, world!”). Essa máquina de Turing obviamente sempre pára e dá uma resposta. Seria fácil fazer uma algoritmo que, sempre que vê uma máquina de Turing que apenas imprime na fita (ou, digamos, um programa C que só contém printfs), responde SIM ao problema da parada, ou seja, essa máquina (ou programa) sempre vai parar.

A dificuldade do problema da parada não está em instâncias específicas, mas sim no problema geral: ter um algoritmo que consiga decidir isso para qualquer instância, para qualquer máquina de Turing, para qualquer programa de computador.

Mudando a discussão de indecibilidade para P e NP: se pensarmos no problema SAT, o problema de satisfatibilidade de fórmulas proposicionais, é fácil fazer um programa que responde a algumas dessas instâncias em tempo polinomial (por exemplo, fórmulas que só tem uma proposição, sem conectivos), mesmo que o problema geral seja NP (porque algumas instâncias nunca poderão ser resolvidas em tempo polinomial, se P != NP).

Agora vamos pensar em P != NP como um problema de decisão para ser resolvido por um algoritmo. O importante é que esse problema não tem instâncias. Ou P != NP é verdade, ou não é. É um problema único, e não um conjunto de instâncias de problemas, como os exemplos anteriores.

Com isso, vamos observar a afirmação IV: imagine que um algoritmo é “responda SIM” (ou seja, apenas imprimir a resposta “SIM”) e o outro é “responda NÃO”. É claro que, para o problema P != NP, um dos dois vai acertar. Não sabemos ainda qual dos dois é o certo, mas ou P != NP, ou não é verdade que P != NP (e portanto P = NP). Então acho que é fácil ver que a afirmativa IV está correta. Agora, quanto à III: desses 2 algoritmos da afirmativa IV, um dos dois está correto (embora não saibamos qual). Mas eles são de tempo polinomial? Claro que sim, eles apenas respondem imediatamente SIM ou NÃO, sem nenhum processamento. Ou seja, existe um algoritmo que responde ao problema de decisão P != NP em tempo polinomial (na verdade tempo constante, mas todo algoritmo O(1) também é O(n) e por aí vai), e, embora nós não saibamos que algoritmo é esse, sabemos que é um dos dois acima. Então a alternativa III está correta também. I e II obviamente não podem estar corretos se IV está, e na verdade não estão, exatamente porque os algoritmos mencionados em IV são suficientes.