O Paradoxo de Monty Hall diz que, em se descartando algumas escolhas erradas, as desconhecidas restantes combinam as probabilidades daquelas descartadas.
O exemplo clássico desse paradoxo são três portas fechadas, uma com um carrozero e as outras duas com bodes. O convidado precisa escolher uma porta, e receberá como prêmio o que estiver atrás dela.
Então o convidado escolhe uma porta. O mestre de cerimônia em vez de abrira porta escolhida, abre uma das outras duas portas, mostrando um bode atrás dela. Então ele pergunta se o convidado quer continuar com a porta escolhida ou se prefere trocar para a outra porta ainda fechada.
Segundo o Paradoxo de Monty Hall, o convidado tem 33% (uma chance em três)de ganhar o carro se mantiver a escolha inicial, mas 67% (duas em três) se trocar para a outra porta. Isso porque se a possibilidade dele ganhar era 33%, ela não se altera, portanto a possibilidade do carro estar em uma das outras duas portas – agora apenas uma – é de 67%.
Nesta sequência de artigos escreveremos um código para colocar à prova esse paradoxo. No processo aprenderemos um pouco sobre OTP, o framework de serviços de Erlang. Neste primeiro artigo, faremos funcionar o primeiro ator: o mestre de cerimônias.
Vamos começar com um boilerplate OTP para o mestre de cerimônia. Será um arquivo chamado mh_mc.erl
. Usaremos o gen_server
:
-module(mh_mc).
-behavior(gen_server).
-export([start_link/0, stop/0]).
-export([init/1, handle_call/3, handle_cast/2, handle_info/2, terminate/2,
code_change/3]).
%% API
-spec start_link() -> {ok, Pid} when Pid :: pid().
-spec stop() -> ok.
start_link() -> gen_server:start_link({local, ?MODULE}, ?MODULE, null, []).
stop() -> gen_server:cast(?MODULE, stop).
%% Behavior
init(null) -> {ok, []}.
code_change(_OldVsn, State, _Extra) -> {ok, State}.
handle_call(_Request, _From, State) -> {reply, ok, State}.
handle_cast(stop, State) -> {stop, normal, State};
handle_cast(_Request, State) -> {noreply, State}.
handle_info(_Info, _State) -> ok.
terminate(_Reason, _State) -> ok.
Nosso código é dividido em duas partes: API (interface com outros atores) ecomportamento (interface com OTP).
A API por enquanto tem apenas duas funções, descritas nas declarações -spec
: start_link/0
, que inicia o mestre de cerimônias, e
stop/0
, que encerra o processo.
Já podemos testá-o, aliás:
sh$ erlc mh_mc.erl
sh$ erl
Erlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:4:4] [async-threads:10]
[hipe] [kernel-poll:false] [dtrace]
Eshell V7.3 (abort with ^G)
1> mh_mc:start_link().
{ok, <0.35.0>
2> processes().
[<0.0.0>,<0.3.0>,<0.6.0>,<0.7.0>,<0.9.0>,<0.10.0>,<0.11.0>,
<0.12.0>,<0.14.0>,<0.15.0>,<0.16.0>,<0.17.0>,<0.18.0>,
<0.19.0>,<0.20.0>,<0.21.0>,<0.22.0>,<0.23.0>,<0.24.0>,
<0.25.0>,<0.26.0>,<0.27.0>,<0.28.0>,<0.29.0>,<0.33.0>,
<0.35.0>]
3> mh_mc:stop().
ok
4> processes().
[<0.0.0>,<0.3.0>,<0.6.0>,<0.7.0>,<0.9.0>,<0.10.0>,<0.11.0>,
<0.12.0>,<0.14.0>,<0.15.0>,<0.16.0>,<0.17.0>,<0.18.0>,
<0.19.0>,<0.20.0>,<0.21.0>,<0.22.0>,<0.23.0>,<0.24.0>,
<0.25.0>,<0.26.0>,<0.27.0>,<0.28.0>,<0.29.0>,<0.33.0>]
5>
As funções de comportamento são:
init/1
: função chamada pelo OTP para inicializar o processo, configurando o estado inicial.code_change/3
: diz ao OTP o que fazer quando o módulo é atualizado. No caso, apenas continua rodando o código novo com o mesmo
estado.handle_call/3
: diz ao OTP o que fazer quando outro processo faz uma chamada, aguardando retorno. Em nosso boilerplate, apenas
responde ok
.handle_cast/2
: diz ao OTP o que fazer quando outro processo lança uma chamada assíncrona. Se o requisição for stop
, usada pela
função stop/0
, encerra o processo normalmente, caso contrário,
não responde nada e continua com o estado atual.handle_info/2
: diz ao OTP o que fazer em caso de timeout.terminate/2
: função chamada pelo OTP quando o processo encerra.A primeira coisa a se fazer é inicializar o sistema criando as portas e colocando os bodes e o carro atrás de cada uma aleatoriamente.
O método que inicializa o processo é init/1
. Ele pode continuar recebendo null
. O processo deve cuidar pessoalmente de configurar
as portas.
Vamos representar as portas usando uma lista de possibilidades. Podemos chamar as possibilidades de prize()
:
-type prize() :: car | goat.
Podemos também definir que as portas são a
, b
e c
:
-type door() :: a | b | c.
[update 2016-05-23]Colocamos as declarações de tipo no arquivo
mh.hrl
, que deve ser importando usando:[/update]-include("mh.hrl").
A primeira coisa que precisamos fazer é resetar o sistema de aleatoriedade:
init(null) ->
random:seed(now()),
{ok, []}.
Vamos agora colocar bodes atrás de todas as portas:
init(null) ->
random:seed(now()),
Doors = [{a, goat}, {b, goat}, {c, goat}],
{ok, Doors}.
Agora precisamos escolher uma porta para coloca o carro:
init(null) ->
random:seed(now()), % inicializa o gerador de números aleatórios
Doors = [{a, goat}, {b, goat}, {c, goat}], % inicializa as três portas com bodes
CarDoor = lists:nth(random:uniform(3), [a, b, c]), % escolhe uma porta pra colocar o carro: a, b ou c
{ok, lists:keyreplace(CarDoor, 1, Doors, {CarDoor, car})}. % inicia o processo com as portas configuradas
O estado inicial do mestre de cerimônias consiste em uma lista de três portas, a
, b
e c
, cada uma com um bode
(goat
) ou o carro (car
) atrás. Nós não conhecemos essa
formação, mas processo conhece.
Merece atenção especial a última linha:
ok
informa ao OTP que tudo correu bem.lists:keyreplace/4
faz a substituição de um elemento de uma lista
de tuplas baseada em uma posição das tuplas:CarDoor
é a porta escolhida;1
indica que a substituição é feita pelo primeiro elemento de cada tupla;Doors
é a list original (apenas bodes);{CarDoor, car}
é o novo elemento carro na porta CarDoor
.Não faz sentido termos as portas se não pudermos obter seus valores ao final.Para obter o prêmio atrás de um porta, precisamos configurar o método de
comportamento handle_call/3
.
No momento, a função é:
handle_call(_Request, _From, State) -> {reply, ok, State}.
Imediatamente antes, acrescente outra assinatura:
handle_call({door, Door}, _From, State) ->
case lists:keyfind(Door, 1, State) of
{_, Prize} -> {reply, {prize, Prize}, State};
false -> {reply, null, State}
end;
Agora, se o processo receber uma chamada síncrona no formato {door, Door}
, retornará o conteúdo daquela porta. Precisamos apenas
de uma interface. Primeiro vamos exportá-la e definir sua especificação:
-export([start_link/0, stop/0, get_prize/1]).
...
-spec get_prize(Door :: door()) -> {ok, Prize} when Prize :: prize() | {error, _}.
Podemos implementar a função get_prize/1
, que apenas faz a chamada para OTP:
get_prize(Door) ->
case gen_server:call(?MODULE, {door, Door}) of
{prize, Prize} -> {ok, Prize};
Other -> {error, Other}
end.
A última coisa é oferecer a outra porta para abertura. Esse processo tem doisfluxos:
Imediatamente acima da implementação de falha de handle_call/3
, crieuma nova implementação tratando do pedido de outra porta para troca:
handle_call({other, Door}, _From, State) ->
case lists:keyfind(Door, 1, State) of
{_, goat} ->
% convidado escolheu um bode (67%)
{OtherDoor, _} = lists:keyfind(car, 2,
lists:keydelete(Door, 1, State));
{_, car} ->
% convidado escolheu o carro (33%)
{OtherDoor, _} = lists:nth(random:uniform(2),
lists:keydelete(Door, 1, State));
false -> OtherDoor = null
end,
{reply, OtherDoor, State};
[update 2016-05-23]A linha que encontra a porta com o carro merece uma explicação maisprofunda.
{OtherDoor, _} = lists:keyfind(car, 2, lists:keydelete(Door, 1, State));
A primeira função avaliada é:
lists:keydelete(Door, 1, State)
Ela retorna uma nova lista a partir de
State
, removendo a tupla cujo primeiro elemento éDoor
, ou seja, a porta escolhida pelo convidado. Assim, restam duas portas, uma com um bode, outra com o carro. É preciso retornar a porta com o carro.Então entra o outro
lists:keyfind/3
, cujo primeiro parâmetro écar
e o segundo2
. Ele retorna a tupla cujo segundo elemento écar
.Finalmente o partern matching seleciona apenas a letra da porta, armazenando-a em
[/update]OtherDoor
.
Também precisamos aqui criar uma interface, da mesma forma:
-export([start_link/0, stop/0, get_prize/1, suggest_another_door/1]).
...
-spec suggest_another_door(Door :: door()) -> {ok, OtherDoor} when OtherDoor :: door() | {error, _}.
...
suggest_another_door(Door) ->
case gen_server:call(?MODULE, {other, Door}) of
null -> {error, null};
OtherDoor -> {ok, OtherDoor}
end.
Precisamos testar agora pra ver se funciona!
sh$ erlc mh_mc.erl
sh$ erl
Erlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:4:4] [async-threads:10]
[hipe] [kernel-poll:false] [dtrace]
Eshell V7.3 (abort with ^G)
1> mh_mc:start_link().
{ok,<0.35.0>}
2> mh_mc:get_prize(a).
{ok,goat}
3> mh_mc:get_prize(b).
{ok,goat}
4> mh_mc:get_prize(c).
{ok,car}
5> mh_mc:suggest_another_door(a).
{ok,c}
6> mh_mc:suggest_another_door(b).
{ok,c}
7> mh_mc:suggest_another_door(c).
{ok,b}
8> mh_mc:suggest_another_door(a).
{ok,c}
9> mh_mc:suggest_another_door(b).
{ok,c}
10> mh_mc:suggest_another_door(c).
{ok,a}
11> mh_mc:stop()
ok
12>
No próximo artigo criaremos o segundo ator, o convidado, que deve escolher uma das três portas e depois decidir se troca de porta ou não.
Erlang | Functional | Logical