Paradigmas de Programação -- 2014-Q3 -- Trabalho Prático

Você implementará um simulador de bolsa de valores. Implemente o descrito para cada fase, e depois da última fase, voce pode implementar uma das tarefas-bônus para obter mais pontos.

Pontuação:

• Fase zero: +0, +0.5 ou +1 ponto
• Até fase I: +0, +0.5 ou +1 ponto
• Até fase II: +0, +0.5 ou +1 ponto

Na fase final:

• Bônus C: +0, +0.5, +1 ou +1.5 ponto
• Bônus B: +0, +0.5, +1,ou +1.5 ponto
• Bônus A: +0, +1 ou +2 pontos

O trabalho poderá ser desenvolvido nas linguagens a seguir:

• Scheme
• Common Lisp
• Clojure
• Prolog
• Haskell
• Julia

Se houver interesse, partes do trabalho poderão ser feitas também em:

• Factor
• Forth (gforth recomendado; veja um exemplo de servidor)
• occam
• Emacs Lisp (só não dá pra fazer tudo porque não há suporte a threads)

Você pode misturar as linguagens (em módulos diferentes, se fizer sentido -- por exemplo, o programa que escreve os logs pode comunicar-se via TCP com o programa que executa as ordens de compra e venda).

IMPORTANTE:

• O trabalho NÃO poderá, em hipótese alguma, ser feito em C, C++, C# Pascal, Fortran, Matlab/Octave, Java, Scala, Python, Ruby, Javascript, ou PHP.

• NÃO é permitido usar sistema gerenciador de banco de dados, porque ao fazê-lo você evitaria trabalhar diretamente com os aspectos de representação e armazenamento de dados, e de controle de concorrência. É importante ter a exepriência de implementar tudo sem usar "caixas-pretas".

• NÃO é permitido usar interface com classes Java ou bibliotecas C que tornem o trabalho excessivamente fácil (consulte-me antes de usar bibliotecas externas).

Para testar a aplicação eu vou usar clientes que simulam ações de compra e venda. A partir da fase em que seu servidor aceitar conexões concorrentes via TCP, eu tentarei conectar milhares de clientes ao mesmo tempo!

Exemplos na descrição a seguir

Os agentes usarão um protocolo para comunicação com seu servidor. Para cada comando descrito nesta especificação, há um exemplo. Nos exemplos, o caracter > é usado para mostrar uma linha que é enviada do agente para o servidor, e o caracter < é usado para mostrar uma resposta do servidor.

DICAS

• Separe usuários, ordens, itens, etc, com APIs específicas. Para quem usar Scheme, recomendo usar a SRFI-9, mas você também pode usar listas e hash-tables se quiser -- só tente criar procedimentos específicos para criar, mudar e acessar partes desses objetos. De outra forma, o programa ficará muito complexo.

• Para quem usar Scheme: talvez você queira usar as hash tables da SRFI-69 ao invés de usar somente listas.

• Veja o arquivo trabalho.scm com um exemplo de servidor. Para usar threads em Scheme, use a SRFI-18. Para usar TCP no Chicken, use o módulo "tcp".

• Para quem estiver usando Common Lisp: há dois projetos úteis: Bordeaux threads e USOCKET.

Instruções para entrega

Faça exatamente como está nestas instruções, ou sua avaliação poderá demorar mais que a dos outros (boa parte do processo será automatizada).

Se usou Linux

Crie um arquivo RA.tar.gz ou RA.zip (onde obviamente "RA" é seu RA) contendo:

• um subdiretório cujo nome é seu RA
• nesse subdiretório, o arquivo fase0.sh que roda seu programa
• outros arquivos com o fonte de seu programa, usados pelo fase0.sh

Não precisa compilar o programa.

Veja exemplos com o RA fictício 123456:

• tar.gz
• ZIP

Envie o arquivo para

Se usou Windows

Faça o mesmo que nas instruções para Linux, mas:

• explique no corpo do email como executar o programa
• não precisa do fase0.sh

Fase zero

Seu servidor deve ler de um arquivo os nomes de ativos a serem negociados, no seguinte formato:

N
item1    qtde    valor
item2    qtde    valor
...
itemN    qtde    valor

A primeira linha diz quantos são, e as outras tem os nomes dos ativos, um por linha. qtde é a quantidade inicial de ativos que a empresa deixa à venda, e valor é o valor initário de cada ação.

Login, logout, catálogo de itens

Nesta fase, o servidor só recebe instruções pela entrada padrão.

O agente envia as seguintes strings para o servidor (cada uma em uma linha -- o \n sinaliza o final do comando):

• LOGIN id senha -- entra no sistema.
• FUI -- sai do sistema.
• CATALOGO -- catálogo de ativos

Quando o agente usa seu id pela primeira vez, ele está se cadastrando, e determinando sua senha. Nas vezes seguintes, ele precisa se identificar ao conectar-se, antes de enviar outros comandos.

O servidor responde OK ou ERRO.

Exemplo:

> LOGIN usuario_xyz minhasenha
< OK

> LOGIN usuario_xyz senha_errada
< ERRO 001
(disconnect)

Se não houve erro, a conexão permanece aberta, e o usuário continua mandando comandos.

Exemplo:

> LOGIN usuario_xyz minhasenha
< OK
> CATALOGO
< XPTO
< ACME
< TABAJARA
< OK

Compra, venda, cancelamento

O usuário pode registrar no servidor ordens de compra e venda, e pode cancelar ordens.

• COMPRA item valor qtde -- põe uma ordem de compra.
• VENDE item valor qtde -- põe uma ordem de venda.
• CANCELA ordem -- cancela uma ordem.
• ATIVAS [item] -- vê ordens ativas do cliente, p/1 item.

Para ordens de compra, venda ou cancelamento, o servidor deve responder com uma das duas respostas a seguir:

• OK numero-da-ordem
• ERRO codigo-erro

Erros:

002: usuário não tem essa quantidade de ações para vender
003: erro interno do servidor
004: ordem inexistente
005: ativo inexistente

Uma ordem com sucesso:

> COMPRA XPTO 1.15 20
< OK 9023

Uma ordem sem sucesso:

> VENDA ACME 2.0 10
< ERRO 003

> CANCELA 9023
< OK
> CANCELA 1111
< ERRO 004

> COMPRA EMPRESA_IMAGINARIA 2.0 10
< ERRO 005

Se um agente posta duas ordens de compra ou venda iguais, variando apenas a quantidade de ações, transforme-a em uma única ordem.

Quantidade inicial de ações

Cada empresa deixa uma ordem de venda inicialmente, conforme descrito no arquivo inicial de configuração. Quando estas se esgotarem, as empresas "somem" do mercado, não mais vendendo nem comprando. A partir daí, o mercado flutua mais livremente, porque não há mais a empresa forçando um valor de venda.

Fase I

Agora o servidor não interage mais pela entrada e saída padrão. Ele recebe conexões TCP em uma porta. O servidor deve receber conexões simultâneas, usando threads para atendê-las.

Diferentes usuários registrarão no sistema ordens de compra e venda. Uma ordem de compra ou venda fica ativa até o final do pregão, ou até ser executada ou cancelada.

• LISTA item -- lista ordens de um item (de todos agentes).
• COTACAO item -- dá a cotação de um item.
• EXECUTADAS [item] -- vê ordens executadas do cliente, p/1 item.

Lista de ordens de outros

Para a ordem LISTA, o servidor envia ao cliente uma lista de ordens existentes (do cliente e de outros) para um determinado item, no seguinte formato:

numero TIPO item qtde valor

Se houver mais de 20 ordens, mande as 20 "melhores":

• as de venda com menor valor
• as de compra com maior valor

Exemplo:

> LISTA XPTO
< 00112 C 10 1.5
< 00231 C 50 1.3
< 01333 V 10 2.1
< OK

Consulta de cotação

Para a ordem COTACAO, mande os valores das melhores ordens e da última execução do item no seguinte formato:

item ultimo-valor volume quando

• ultimo-valor é o valor da mais recente negociação do item.
• volume indica a quantidade negociada na mais recente ordem executada para este item.
• quando indica quando a execução ocorreu.

Exemplo:

> COTACAO ACME
< ACME 1.13 25 20141011153021
< OK

Se o ativo não tiver sido negociado neste pregão, o servidor deve retornar -1 -1 0:

> COTACAO TABAJARA
< TABAJARA -1 -1 0
< OK

Neste exemplo, a última

Lista de ordens do próprio cliente

Para a ordem ATIVAS e EXECUTADAS, o servidor envia ao cliente uma lista de ordens postas pelo próprio cliente, uma por linha, no seguinte formato:

numero TIPO item qtde valor data-início [data-execução]

• TIPO é C ou V
• item é o nome do ativo
• valor é o valor da ordem
• quando-início é o momento em que a ordem foi posta
• quando-execução (somente para EXECUTADAS) é o momento em que a ordem foi executada

Exemplo:

> ATIVAS ACME
< 10111 ACME 30 C 2.00 20141011110001
< 10231 ACME 20 C 2.20 20141011120125
< OK

> EXECUTADAS XPTO
< 10123 C XPTO 15 1.15 20141011120103 20141011140425
< 10921 V XPTO 10 1.20 20141011141008 20141011152405
< OK

EXECUÇÃO

Nesta fase seu sevidor não executará ordens concorrentemente.

Embora o atendimento a clientes seja concorrente, a execução das ordens é feita sequencialmente, de forma a evitar problemas de controle de concorrência.

Quando há uma ordem de compra e uma de venda compatíveis -- ou seja, quando o valor proposto pelo comprador é igual ou maior* que o proposto pelo vendedor*, você decide que regra seu sevidor usa para determinar o valor da execução:

• o valor proposto pelo vendedor
• o valor proposto pelo comprador
• algum valor entre os dois (pode ser a média, ou pode ser um valor determinado aleatoriamente entre os propostos por comprador e vendedor)

Fase II

A compra e venda de itens agora poderá acontecer em paralelo (você deve necessariamente permitir que isso aconteça, usando mais de uma thread para realizar as execuções).

As transações são efetivada atomicamente, e a soma de vendas e compras devem ser iguais.

Se uma ordem pede venda de 20 e outra a venda de 10, e há uma ordem de compra de 15, depois da execução sobre somente uma ordem (parcial) de venda de 5.

BÔNUS (A)

Quando há ordens de venda e compra viáveis (ou seja, com valor que permitiria a execução) para um item, pode ser que haja ordens de venda para mais ou para menos do que ordens de compra. As ordens deve ser executadas por prioridade:

As ordens devem ser executadas de forma a minimizar o desvio-padrão da distância entre preços de venda e compra em cada execução.

Por exemplo,

1: C ACME $3.00
2: C ACME $7.00
3: V ACME $1.00
4: V ACME:$2.00

pode-se realizar duas execuções:

1. executar (1,3) e (2,4): com isso temos (3 − 1) = 2 e (7 − 2) = 5.
2. executar (1,4) e (2,3): com isso temos (3 − 2) = 1 e (7 − 1) = 6.

Nos dois casos, evidentemente, a média da distância é 3.5. Mas no caso (2) a variancia (e o desvio padrão) são maiores.

Colete as ordens por intervalos: a cada 5 segundos ou 100 ordens para o mesmo ativo (o que vier primeiro), agrupe e execute conforme esta política.

BÔNUS (B)

Seu servidor deverá produzir um log de eventos relevantes. Ele deve relatar:

• Quando o valor ou volume negociado de um item subir ou descer muito bruscamente;
• Quando um item tiver muito mais ordens de venda do que de compra, ou vice-versa;
• Quando a média de valor negociado (por 20 segundos) de um agente subir ou descer muito bruscamente (fica mais fácil se mantiver e atualizar a média a cada execução);
• Quando o tempo médio de resposta ao cliente (para cada comando) exceder um determinado limite (0.01s, por exemplo)

BÔNUS (C)

Implemente DESDOBRAMENTO e GRUPAMENTO, de forma que a visão do cliente sempre seja consistente para cada comando que ele executar.

• Quando uma ação tem o valor muito alto (defina um valor máximo), ela sofre um desdobramento: cada ação passa a ser 100 ações, com valor de um centésimo da original.

• Quando o valor de uma ação for muito pequeno (defina o mínimo -- por exemplo, 1, 2 ou 5 centavos), ela sofre um grupamento, e cada 100 ações tornam-se uma única, com preço 100 vezes maior. Se um acionista, após o grupamento, terminar com menos de uma ação (por exemplo, 2/5 de ação), presuma que a empresa o compensará em dinheiro, e portanto sua fração deixa de existir.