View
1.552
Download
2
Category
Preview:
DESCRIPTION
Conceitos da linguagem ML (apresentação utilizada durante a disciplina "Modelagem e Validação usando Redes de Petri", do mestrado em Ciência da Computação)
Citation preview
Standard ML e CPN ML
Modelagem e Validação de Sistemas Usando Redes de Petri
Professor: Jorge AbrantesAluno: Dalton Cézane
Programação funcional e SML
• Funções são valores de primeira ordem e são tratadas como tipos básicos;
• Computação realizada através da avaliação das expressões, não pela seqüência de passos fazendo modificações em referências de memória (programação imperativa);
• Polimorfismo;• Recursão ao invés de iterações;
Programação funcional e SML
• Tipos determinados em tempo de compilação (fortemente tipada);
• Possui garbage collection (limpa memória);
• Avaliação dos parâmetros antes da avaliação da função;
• Meta programming Language;• Aplicações: verificação e lógica aplicada (prova
de teoremas), análise de programas, e compiladores avançados.
Compilador SML/NJ
• Prompt loop, lendo, avaliando e exibindo:
Tipos primitivos
• Int;• IntInf;• Boolean;• Real;• Char;• String;• List;• TextIO.
Constantes
Inteiros:
Reais:
Constantes
Booleans:
Strings:
Caracteres:
Operadores
• Aritméticos: +, -, *, / (divisão de reais), div, mod, ~;
• String: ^ (concatenação);
• Relacionais: =, >, <, >=, <=, <>
• Lógicos: andalso, orelse, not
• Exemplos...
Expressão condicional IF
• Sintaxe: if A then B else C
• Obrigatoriamente usa-se o else
Consistência de tipos
• Sempre um único tipo é associado a toda expressão;
• Exemplo:– Aplicando um operador a um tipo errado;– Aplicando um operador a tipos mistos.
Coerção entre tipos
• Entre inteiros e reais (real);
• Entre caracteres e inteiros (ord e chr);
• Entre caracteres e strings (str);
Declarações de variáveis
• val <identificador> = <expressão>;
• Variáveis podem ser redeclaradas e não precisam ser do mesmo tipo;
• Exemplo...
Tuplas
• Importante para construção de tipos complexos;• Construídas através de uma lista não vazia de
expressões de algum tipo, separadas por vírgula, entre parêntes: (E1, E2, E3, ..., Em);
• O tipo de uma tupla é um produto: tipo[E1] * tipo[E2] * ... * tipo[En];
• Para obter o i-ésimo componente de uma tupla: #i(tupla).
Listas
• Também importantes, como tuplas, para tipos complexos;
• Construídas com uma lista de expressões do mesmo tipo, separadas por vírgulas, entre colchetes: [E1, E2, ..., En];
• O tipo de uma lista é: “tipoDasExpressões” list;
• Notações e operadores: [], nil, hd, tl, @, ::
String x list x char
• explode(“string”);
• implode([#”char1”, #”char2”,..., #”charn”]);
• concat([“a”, “bcd”, “ef”])
Funções
• Linguagem funcional: definição de funções e aplicação destas a parâmetros;
• Declaração: fun <identificador>(<lista de parâmetros>) = <expressão>;
• Aplicação de função: <identificador>(lista de parâmetros>).
Funções
• Exemplos...
• Funções possuem maior precedência que operadores aritméticos;
• Sobrecarga do operador *:
Funções
• O binding do valor ao qual uma variável refere pode ser determinado estaticamente antes do programa ser executado (lexically scoped).
• Exemplo: fun addx(y) = y + x;
Funções recursivas
• Recursão é usado ao invés de iterações;• Lógica da recursão: caso base + passos
indutivos com “menores” parâmetros;
• Expressões de parâmetros são avaliadas antes de serem passadas para a função.
• Obs.: A função reverse é polimórfica (mas apresenta problema com lista de reais).
Recursão mútua
• SML suporta funções mutuamente recursivas;
• Funções mutuamente recursivas são agrupadas com o “and”.
Casamento de padrão
• Casamento de padrão nos parâmetros das funções;
• A forma de uma função definida por padrões:
fun <identificador>(padrão1)=<expressão1>
| <identificador> (padrão2) = <expressão2>
...
|<identificador> (padrãon) = <expressãon>
Casamento de padrão
• Elimina grande parte dos “if”s;• Merge de duas listas ordenadas:
• Pode explicitar o “casamento de padrão” com o “as”:
Casamento de padrão
• O símbolo _ pode ser usado para denotar uma variável anônima;
• Com o uso deste símbolo, pode-se evitar a repetição de variáveis:
Expressão case
• Generalização da expressão if-then-else;
• Forma: case E of
<padrão1> => <expressão1>
| <padrão2> => <expressão2>
...
| <padrãon> => <expressãon>
Expressão case
• Exemplos:
Obs.: O lado direito das expressões devem ser do mesmo tipo, assim como os valores resultantes da expressão if.
CPN ML
• Uma extensão de Standard ML;
• Facilita o uso da linguagem para quem não tem prática com SML (tipos = cores);
• Permite declaração de variáveis “tipadas”;
• Permite declaração de variáveis por “referência”, que não é característica funcional.
Declarações – Colour Sets
• Unit colset nome = unit [with new_unit];– colset U = unit;– colset E = unit with e;
• Boolean colset nome = bool [with (new_false, new_true)];
– colset B = bool; (Operações: not, andalso, orelse)– colset B2 = bool with (no, yes);
• Integer colset nome = int [with int-exp1..int-exp2];
– colset I = int; – colset I2 = int with 0..9;– Operadores: ~, +, -, *, div, mod, abs, Int.min(i1,i2), Int.max(i1,i2).
Declarações – Colour Sets
• String colset nome = string [with string-exp1..string-exp2 [and int-exp1..int-exp2]];– colset lowerstring = string with “a” .. “z” and 1..3;– Operações: s1^s2, String.size s, substring(s, i, len),
explode s, implode l
• Enumerated colset nome = with id0|id1| … | idn;
– colset dwarfs = Dopey | Doc | Sleepy | Bashful | Happy | Grumpy | Sneezy;
• Index colset nome = index id with int1..int2;– colset ALUNO = index aluno with 1..11;
Compondo Colour Sets
• Product colset nome = product nome1*nome2*...*nomen;
– colset CASAIS = product HOMEM * MULHER;– Operações: #i (extrai elemento “i” da tupla), _ (omite
elemento - ex. (Bob,_) – Não permitido em CPN).
• Record colset nome = record id1:nome1 * id2:nome2 * ... * idn:nomen;– colset ID = record n:NOME, s:SOBRENOME,
i:IDADE;– Operações: #idi rec (extrai elemento idi do
record rec: ex: #s rec), … (omite elemento - Não permitido em CPN).
Compondo Colour Sets
• Lists colset nome = list nome0 [with int1..int2];
– colset MinhaLista = list INT with 1..3;
• Union colset nome = union id1[:nome1] + id2[:nome2] + ... + idn[:nomen];
– colset Digito = int with 0..9;– colset Uniao = union NUM:Digito + NONE;
Compondo Colour Sets
• Subset colset nome = subset nom0 by subset-function; ou colset nome = subset nom0 with subset-list;
– fun even i = ((i mod 2) = 0);
– colset evenInt = subset INT by even;– colset int2to4 = subset INT with [2,3,4];
• Alias colset nome = nome0;– colset Naturais = POSINT;
Variáveis, constantes e referências
• var id1[, id2, …, idn]: tipo;– var x: int;
• val id = exp;– val maxValor = 5;
• globref id = exp;– globref i = 10;– Operações:
• !a conteúdo da r.v. a• a := b atribui o valor b to r.v. a• ref b reference constructor• inc a/dec a in-/decrementa o valor int da r.v. a
Funções
• fun id pat1 = exp1 id pat2 = exp2 ... id patn = expn;
– fun ehPos(x) = (x>0);– fun diff(x,y) = (x<>y);– fun Divide(x,y) = (x div y) Divide(_,0) = error;
Declarações locais
let
val pat1=exp1;
val pat2=exp2;
…
val patn=expn;
in
exp;
end;
let
fator=5;
in
mult(num, fator);
end;
Estruturas de controle
• if boolexp then
exp1
else
exp2
• case exp ofpat1 => exp1
pat2 => exp2
…
patn => expn;
Multi-sets
• Construtor: `;
• Sintaxe: i`c (i não-negativo, c é cor – tipo);– “Adição” e “subtração” de multi-sets;– 3`true++2`false (3 instâncias true + 2 false);
Multi-sets - Operações
empty define um multi-set vazio;== igualdade;<><> desigualdade;>> maior que (>>= ou igual a)<< menor que (<<= ou igual a)++ adição-- subtração** multiplicação escalar
Multi-sets - Operações
size ms tamanhorandom ms retorna uma cor pseudo-radômicacf(c, ms) retorna o n° de itens da cor c em msfilter p ms filtra ms pelo predicado pext_col f ms pega i1`c1++…++in`cn e retorna
i1`f(c1)++…++in`f(cn)ext_ms f ms pega i1`c1++…++in`cn e retorna
i1*f(c1)++…++in*f(cn)ms_to_col ms retorna um multi-set de tamanho 1 como
um elemento simples em ms (size ms=1, raises no_singleton exception)
Inscrições
Nome
[Initial Marking[@+Delay]]
Cor (tipo)
Inscrições de lugares
Início
INT
1`0 ++ 1`1 ++ 1`21`0++1`1++1`2 3
Início
INT
(1`0 ++ 1`1 ++ 1`2)@+31`0@3++1`1@3++1`2@3 3
Incrições de transições
Nome
[Guarda] [Delay]
[Código]
Incrições de transições
Par
m>0 @+2
input(m)output(n,b)let val par = (m mod 2)=0in (m+1,par)end;
Numero Resultadom
n
bINT BOOL
3
Inscrições de arcos
ParNumero Resultadom b
INT BOOL
31`3
1
m é “vinculado a 3
ParNumero Resultadom bINT
1`3++1`5
1`3++1`5
2
m é “livre” (3 ou 5)BOOL
Inscrições de arcos
ParNumero Resultadom b@+2INT
BOOL
1`3++1`5
1`3++1`5
2
Delay: arco de saída tem delay 2
ParNumero Resultadom@+2 bINT BOOL
(1`3++1`5)@+6
1`3@6++1`5@6
2
Preemptying time stamps (on input arcs):
“Par” can use tokens from “Numero”
• Incrições de arcos não podem:– conter I/O ou usar comandos;– atualizar ou usar variáveis de referências;– usar funções randômicas. (CPNTools não checa isto)
ParNumero Resultadom if par mthen 1`trueelse 1`false
INT BOOL
1`3++1`5
1`3++1`5
2
Referências
• http://wiki.daimi.au.dk/cpntools-help/cpn_ml.wiki
• Standard ML Programming for Design/CPN Users
• Introduction to Standard ML
Recommended