Hoje estamos finalizando nossa série de artigos sobre programação funcional. Acabou 11 partes. Eu acredito que isso é uma conquista. Neste artigo, implementamos uma calculadora simples de pilha (também conhecida como "notação polonesa reversa"). A implementação é quase completamente construída em funções, com apenas um tipo especial e geralmente sem comparação com a amostra, portanto, este é um excelente campo de teste para os conceitos abordados em nossa série.
Quero agradecer @kleidemos separadamente. Foi ele quem atuou como principal tradutor e gerente de toda a série de artigos. Obrigada
Se você não estiver familiarizado com essa calculadora, ela funcionará da seguinte maneira: números são empurrados para a pilha e operações, como adição e multiplicação, selecionam números da parte superior da pilha e, em seguida, retornam o resultado da operação.
Esquema de computação simples na pilha:
Antes de projetar esse sistema, considere como ele será usado. Seguindo uma sintaxe semelhante à quarta, atribuiremos a cada ação um rótulo apropriado para que, no exemplo acima, você possa escrever algo como:
EMPTY ONE THREE ADD TWO MUL SHOW
Talvez seja impossível obter exatamente essa sintaxe, mas vamos tentar chegar o mais próximo possível disso.
Tipo de dados da pilha
Primeiro, você precisa definir a estrutura de dados para a pilha. Para simplificar, você pode usar uma lista de números de ponto flutuante.
type Stack = float list
Mas é melhor agrupá-lo em um tipo de união de caso único para tornar o tipo mais visual, assim:
type Stack = StackContents of float list
Por que é melhor fazer exatamente isso, você pode ler aqui .
Agora crie uma nova pilha usando StackContents como construtor:
let newStack = StackContents [1.0;2.0;3.0]
Para extrair conteúdo de uma pilha existente, use o padrão correspondente a StackContents :
let (StackContents contents) = newStack // "contents" // float list = [1.0; 2.0; 3.0]
Empurre a função
Em seguida, precisamos de uma maneira de colocar números nessa pilha. Para fazer isso, basta adicionar um novo valor ao topo da lista usando " :: ".
Exemplo de função:
let push x aStack = let (StackContents contents) = aStack let newContents = x::contents StackContents newContents
Esse recurso possui vários recursos que vale a pena discutir.
Primeiro, você deve prestar atenção ao fato de que a estrutura da list é imutável, o que significa que a função deve pegar uma pilha existente e retornar uma nova. Isso não é apenas uma alteração em uma pilha existente. De fato, todas as funções neste exemplo terão um formato semelhante:
Input: Stack - Output: Stack
Em segundo lugar, por que os parâmetros estão nessa ordem? Por que a pilha deve ir primeiro ou por último? Na seção sobre o design de funções com aplicação parcial, foi dito que o parâmetro de mudança mais frequente deveria durar. Em breve será possível verificar se essas recomendações estão sendo seguidas.
Finalmente, a função pode ser mais concisa, combinando com o padrão no próprio parâmetro da função, em vez de let o corpo da função.
A versão reescrita:
let push x (StackContents contents) = StackContents (x::contents)
Muito melhor!
A propósito, veja sua assinatura graciosa:
val push : float -> Stack -> Stack
Como mencionado anteriormente , a assinatura nos diz muito.
Nesse caso, eu poderia adivinhar o que essa função faz, apenas por sua assinatura, sem nem mesmo saber que é chamada de "push".
Esse é outro motivo pelo qual foi uma boa idéia ter nomes de tipo explícitos. Se a pilha fosse apenas uma lista de números de ponto flutuante, a função não seria tão auto-documentada.
De uma forma ou de outra, verifique:
let emptyStack = StackContents [] let stackWith1 = push 1.0 emptyStack let stackWith2 = push 2.0 stackWith1
Works great!
Empilhar sobrescrito superior usando push
Com esta função simples, você pode definir facilmente uma operação que envia um número específico à pilha.
let ONE stack = push 1.0 stack let TWO stack = push 2.0 stack
Mas espere um minuto! Você vê que o parâmetro da stack é mencionado nos dois lados da expressão? De fato, não é necessário mencioná-lo duas vezes. Em vez disso, você pode omitir o parâmetro e escrever uma função com aplicação parcial:
let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0
Agora é óbvio que, se a função push tivesse uma ordem diferente de parâmetros, a stack teria que ser mencionada duas vezes.
Também vale a pena definir uma função que cria uma pilha vazia:
let EMPTY = StackContents []
Verifique as funções recebidas:
let stackWith1 = ONE EMPTY let stackWith2 = TWO stackWith1 let stackWith3 = THREE stackWith2
Essas pilhas intermediárias são irritantes? É possível se livrar deles? Claro! Observe que as funções ONE, DOIS e TRÊS têm a mesma assinatura:
Stack -> Stack
Então, eles estão perfeitamente conectados! A saída de uma função pode ser inserida no seguinte:
let result123 = EMPTY |> ONE |> TWO |> THREE let result312 = EMPTY |> THREE |> ONE |> TWO
Sair da pilha
Com a adição à pilha calculada, mas e a função pop ?
Ao recuperar da pilha, é obviamente necessário retornar o topo da pilha, mas é exatamente isso?
Em um estilo orientado a objetos, a resposta é sim . Mas, no caso de OOP, a pilha seria alterada nos bastidores, para que o item superior fosse removido.
No entanto, em um estilo funcional, a pilha é imutável. Há apenas uma maneira de remover o elemento superior - crie uma nova pilha sem esse elemento. Para que o chamador tenha acesso à nova pilha reduzida, ela deve ser retornada junto com o elemento superior.
Em outras palavras, a função pop deve retornar dois valores, o elemento top e a nova pilha. A maneira mais simples de fazer isso no F # é simplesmente usar uma tupla.
Implementação:
/// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack)
A função resultante também é muito simples.
Como antes, o contents extraído diretamente do parâmetro.
Em seguida, o conteúdo do contents verificado usando a match..with com a expressão.
Em seguida, o elemento superior é separado do restante da lista, uma nova pilha é criada com base nos elementos restantes e, finalmente, tudo isso é retornado como um par de tupla.
Tente executar este código e veja o que acontece. Você receberá um erro de compilação!
O compilador detectou um caso que não foi resolvido - o que acontece se a pilha estiver vazia?
Você tem que decidir como lidar com isso.
Normalmente, prefiro usar um estado especial para o erro, mas, nesse caso em particular, preferi lançar uma exceção. Versão corrigida do pop com manipulação de caixa vazia:
let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow"
Verifique:
let initialStack = EMPTY |> ONE |> TWO let popped1, poppedStack = pop initialStack let popped2, poppedStack2 = pop poppedStack
e teste de exceção:
let _ = pop EMPTY
Funções aritméticas
Agora que a adição e a exclusão estão em vigor, você pode começar a trabalhar com as funções "adicionar" e "multiplicar":
let ADD stack = let x,s = pop stack // let y,s2 = pop s // let result = x + y // push result s2 // let MUL stack = let x,s = pop stack // let y,s2 = pop s // let result = x * y // push result s2 //
Teste on-line:
let add1and2 = EMPTY |> ONE |> TWO |> ADD let add2and3 = EMPTY |> TWO |> THREE |> ADD let mult2and3 = EMPTY |> TWO |> THREE |> MUL
Isso funciona!
Tempo de refatoração ...
Obviamente, uma quantidade significativa de código é duplicada nessas duas funções. Como podemos consertar isso?
Ambas as funções extraem dois valores da pilha, aplicam uma certa função binária a eles e empurram o resultado de volta para a pilha. Você pode enviar o código geral para a função binária, que assume uma função matemática com dois parâmetros:
let binary mathFn stack = // let y,stack' = pop stack // let x,stack'' = pop stack' // let z = mathFn xy // push z stack''
Observe que nesta implementação, versões diferentes do objeto "mesmo" são marcadas com um número diferente de aspas. Isso ocorre porque os sufixos numéricos podem facilmente causar confusão.
Pergunta: por que os parâmetros têm exatamente essa ordem, em vez de mathFn vir depois da stack ?
Agora que você possui uma função binary , é muito mais fácil definir ADD e outras funções:
Primeira tentativa de implementar o ADD usando binary :
let ADD aStack = binary (fun xy -> x + y) aStack
Mas você pode se livrar do lambda, porque representa a definição exata da função + :
let ADD aStack = binary (+) aStack
Novamente, um aplicativo parcial pode ser usado para ocultar o parâmetro da pilha. Definição final:
let ADD = binary (+)
Definição de outras funções matemáticas:
let SUB = binary (-) let MUL = binary (*) let DIV = binary (../)
Experimente on-line:
let div2by3 = EMPTY |> THREE|> TWO |> DIV let sub2from5 = EMPTY |> TWO |> FIVE |> SUB let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB
Da mesma forma, você pode criar uma função auxiliar para operações unárias
let unary f stack = let x,stack' = pop stack push (fx) stack'
E defina algumas funções unárias:
let NEG = unary (fun x -> -x) let SQUARE = unary (fun x -> x * x)
Modo interativo:
let neg3 = EMPTY |> THREE|> NEG let square2 = EMPTY |> TWO |> SQUARE
Juntando tudo | Juntando tudo
Nos requisitos iniciais, foi mencionado que gostaríamos de poder mostrar os resultados, por isso vale a pena definir a função SHOW.
let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack //
Observe que, neste caso, a nova versão da pilha recebida via pop é ignorada. O resultado final é a pilha original, como se nunca tivesse mudado.
Por fim, você pode escrever o exemplo a seguir nos requisitos originais
EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW
Seguir em frente
É divertido, mas o que mais você pode fazer?
Você pode definir várias funções adicionais:
/// let DUP stack = // let x,_ = pop stack // push x stack /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let START = EMPTY
Usando essas funções adicionais, você pode escrever alguns exemplos elegantes:
START |> ONE |> TWO |> SHOW START |> ONE |> TWO |> ADD |> SHOW |> THREE |> ADD |> SHOW START |> THREE |> DUP |> DUP |> MUL |> MUL // 27 START |> ONE |> TWO |> ADD |> SHOW // 3 |> THREE |> MUL |> SHOW // 9 |> TWO |> SWAP |> DIV |> SHOW // 9 div 2 = 4.5
Usando composição em vez de pipelining
Mas isso não é tudo. De fato, existe outra maneira interessante de representar essas funções.
Como observado anteriormente, todos eles têm a mesma assinatura:
Stack -> Stack
Como entrada e saída são do mesmo tipo, essas funções também podem ser combinadas usando o operador de composição >> , e não apenas através de operadores em pipeline.
Alguns exemplos:
// let ONE_TWO_ADD = ONE >> TWO >> ADD START |> ONE_TWO_ADD |> SHOW // let SQUARE = DUP >> MUL START |> TWO |> SQUARE |> SHOW // let CUBE = DUP >> DUP >> MUL >> MUL START |> THREE |> CUBE |> SHOW // let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2 START |> THREE |> SQUARE |> SUM_NUMBERS_UPTO |> SHOW
Em cada um desses exemplos, uma nova função é definida usando uma composição de outras funções. Este é um bom exemplo de uma abordagem "combinatória" para criar funcionalidades.
Transportadores vs. Composição
Vimos duas maneiras diferentes de usar nosso modelo; usando transportadores e composição. Mas qual a diferença? E por que um deve ser preferido em detrimento de outro?
A diferença é que os pipelines são, em certo sentido, uma operação de "transformação em tempo real". No momento do uso do pipeline, as operações são executadas imediatamente, através da transferência de uma pilha específica.
Por outro lado, a composição é algo como um "plano" que queremos implementar, construindo funções a partir de um conjunto de componentes sem aplicação direta.
Por exemplo, você pode criar um "plano" para calcular o quadrado de um número por meio de uma combinação de pequenas operações:
let COMPOSED_SQUARE = DUP >> MUL
Não posso dar o equivalente com base em pipelines.
let PIPED_SQUARE = DUP |> MUL
Isso resultará em um erro de compilação. Eu preciso de alguma instância de pilha específica para a expressão funcionar:
let stackWith2 = EMPTY |> TWO let twoSquared = stackWith2 |> DUP |> MUL
E mesmo neste caso, posso obter uma resposta apenas para essa entrada específica, e não um plano de cálculo generalizado com base em qualquer entrada, como no exemplo de COMPOSED_SQUARE .
Outra maneira de criar um "plano" é passar explicitamente o lambda para funções mais primitivas:
let LAMBDA_SQUARE = unary (fun x -> x * x)
Essa é uma maneira mais explícita (e provavelmente mais rápida), mas todas as vantagens e clareza da abordagem composicional são perdidas.
Em geral, se possível, você deve procurar uma abordagem de composição!
Código completo
Código completo para todos os exemplos acima:
// ============================================== // // ============================================== type Stack = StackContents of float list // ============================================== // // ============================================== /// let push x (StackContents contents) = StackContents (x::contents) /// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow" // ============================================== // () // ============================================== // // // let binary mathFn stack = let y,stack' = pop stack let x,stack'' = pop stack' let z = mathFn xy push z stack'' // // // let unary f stack = let x,stack' = pop stack push (fx) stack' // ============================================== // () // ============================================== /// let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack // /// let DUP stack = let x,s = pop stack push x (push xs) /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let DROP stack = let _,s = pop stack // s // // ============================================== // , // ============================================== // // ------------------------------- let EMPTY = StackContents [] let START = EMPTY // // ------------------------------- let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0 // // ------------------------------- let ADD = binary (+) let SUB = binary (-) let MUL = binary (*) let DIV = binary (../) let NEG = unary (fun x -> -x) // ============================================== // , // ============================================== let SQUARE = DUP >> MUL let CUBE = DUP >> DUP >> MUL >> MUL let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2
Conclusão
Temos uma calculadora simples baseada em pilha. Vimos como, começando com algumas operações primitivas ( push , pop , binary , unary ) e outras, é possível criar uma DSL completa, fácil de implementar e usar.
Como você pode imaginar, este exemplo foi baseado na linguagem Forth. Eu recomendo o livro gratuito "Thinking Forth" , que fala não apenas sobre a linguagem Forth, mas também sobre outros métodos ( não orientados a objetos!) Para decompor tarefas que são igualmente aplicáveis à programação funcional em geral.
Eu tive a idéia para este artigo no blog lindo de Ashley Feniello . Se você quiser se aprofundar na emulação de uma linguagem baseada em pilha baseada em F #, comece com ela. Divirta-se!
Recursos Adicionais
Existem muitos tutoriais para F #, incluindo materiais para quem vem com experiência em C # ou Java. Os links a seguir podem ser úteis à medida que você avança no F #:
Várias outras maneiras de começar a aprender F # também são descritas.
Finalmente, a comunidade F # é muito amigável para iniciantes. Há um bate-papo muito ativo no Slack, suportado pela F # Software Foundation, com salas para iniciantes nas quais você pode participar livremente . É altamente recomendável que você faça isso!
Não se esqueça de visitar o site da comunidade de língua russa F # ! Se você tiver alguma dúvida sobre o aprendizado de um idioma, teremos prazer em discuti-los nas salas de bate-papo:
Sobre autores de tradução
Traduzido por @kleidemos
As mudanças de tradução e editoriais foram feitas pelos esforços da comunidade de desenvolvedores de F # de língua russa . Agradecemos também a @schvepsss e @shwars pela preparação deste artigo para publicação.