Hoy estamos terminando nuestra serie de artículos sobre programación funcional. Resultó 11 partes. Creo que esto es un logro. En este artículo, implementamos una calculadora de pila simple (también conocida como "notación polaca inversa"). La implementación se basa casi por completo en funciones, con un solo tipo especial y, en general, sin comparación con la muestra, por lo que este es un excelente campo de pruebas para los conceptos cubiertos en nuestra serie.
Quiero agradecer a @kleidemos por separado. Fue él quien actuó como el principal traductor y gerente de toda la serie de artículos. Gracias
Si no está familiarizado con dicha calculadora, funciona de la siguiente manera: los números se insertan en la pila y las operaciones, como la suma y la multiplicación, seleccionan los números desde la parte superior de la pila y luego vuelven a colocar el resultado de la operación.
Esquema de cálculo simple en la pila:
Antes de diseñar dicho sistema, debe considerar cómo se usará. Siguiendo una sintaxis similar a Forth, le daremos a cada acción una etiqueta apropiada para que en el ejemplo anterior pueda escribir algo como:
EMPTY ONE THREE ADD TWO MUL SHOW
Quizás sea imposible obtener exactamente esta sintaxis, pero tratemos de acercarnos lo más posible.
Tipo de datos de pila
Primero, debe definir la estructura de datos para la pila. Para simplificar, puede usar una lista de números de coma flotante.
type Stack = float list
Pero es mejor envolverlo en un tipo de unión de mayúsculas y minúsculas para que el tipo sea más visual, así:
type Stack = StackContents of float list
Por qué es mejor hacer eso, puedes leer aquí .
Ahora cree una nueva pila usando StackContents como constructor:
let newStack = StackContents [1.0;2.0;3.0]
Para extraer contenido de una pila existente, use el patrón que coincide con los contenidos de StackContents :
let (StackContents contents) = newStack // "contents" // float list = [1.0; 2.0; 3.0]
Función de empuje
A continuación, necesitamos una forma de poner números en esta pila. Para hacer esto, simplemente agregue un nuevo valor a la parte superior de la lista usando " :: ".
Ejemplo de funcion:
let push x aStack = let (StackContents contents) = aStack let newContents = x::contents StackContents newContents
Esta característica tiene una serie de características que vale la pena discutir.
Primero, debe prestar atención al hecho de que la estructura de la list es inmutable, lo que significa que la función debe tomar una pila existente y devolver una nueva. Esto no es solo un cambio en una pila existente. De hecho, todas las funciones en este ejemplo tendrán un formato similar:
Input: Stack - Output: Stack
En segundo lugar, ¿por qué los parámetros van en ese orden? ¿Por qué la pila debe ir primero o último? En la sección sobre el diseño de funciones con aplicación parcial, se dijo que el parámetro que cambia con más frecuencia debería ser el último. Pronto será posible verificar que se sigan estas recomendaciones.
Finalmente, la función se puede hacer más concisa haciendo coincidir con el patrón en el parámetro de la función en sí, en lugar de let el cuerpo de la función.
La versión reescrita:
let push x (StackContents contents) = StackContents (x::contents)
Mucho mejor!
Por cierto, mira su elegante firma:
val push : float -> Stack -> Stack
Como se mencionó anteriormente , la firma nos dice mucho.
En este caso, podría adivinar qué hace esta función, solo por su firma, sin siquiera saber que se llama "push".
Esta es otra razón por la que fue una buena idea tener nombres de tipo explícitos. Si la pila fuera solo una lista de números de coma flotante, entonces la función no sería tan autodocumentada.
De una forma u otra, verifique:
let emptyStack = StackContents [] let stackWith1 = push 1.0 emptyStack let stackWith2 = push 2.0 stackWith1
Funciona muy bien!
Apila el superíndice superior usando push
Con esta función simple, puede definir fácilmente una operación que empuja un número específico en la pila.
let ONE stack = push 1.0 stack let TWO stack = push 2.0 stack
¡Pero espera un minuto! ¿Ves que el parámetro de stack se menciona en ambos lados de la expresión? De hecho, no es necesario mencionarlo dos veces. En cambio, puede omitir el parámetro y escribir una función con aplicación 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
Ahora es obvio que si la función push tuviera un orden diferente de parámetros, la stack tendría que mencionarse dos veces.
También vale la pena definir una función que cree una pila vacía:
let EMPTY = StackContents []
Verifique las funciones recibidas:
let stackWith1 = ONE EMPTY let stackWith2 = TWO stackWith1 let stackWith3 = THREE stackWith2
¿Son molestas estas pilas intermedias? ¿Es posible deshacerse de ellos? Por supuesto! Tenga en cuenta que las funciones ONE, TWO y THREE tienen la misma firma:
Stack -> Stack
Entonces, ¡están perfectamente conectados entre sí! La salida de una función se puede ingresar a lo siguiente:
let result123 = EMPTY |> ONE |> TWO |> THREE let result312 = EMPTY |> THREE |> ONE |> TWO
Saliendo de la pila
Con la adición a la pila descubierta, pero ¿qué pasa con la función pop ?
Cuando se recupera de la pila, obviamente es necesario devolver la parte superior de la pila, pero ¿es solo eso?
En un estilo orientado a objetos, la respuesta es sí . Pero en el caso de OOP, la pila se cambiaría detrás de escena, de modo que se eliminaría el elemento superior.
Sin embargo, en un estilo funcional, la pila es inmutable. Solo hay una forma de eliminar el elemento superior: crear una nueva pila sin este elemento. Para que la persona que llama tenga acceso a la nueva pila reducida, debe devolverse junto con el elemento superior.
En otras palabras, la función pop debería devolver dos valores, el elemento superior y la nueva pila. La forma más sencilla de hacer esto en F # es simplemente usar una tupla.
Implementación
/// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack)
La función resultante también es muy simple.
Como antes, los contents extraen directamente del parámetro.
Luego, el contenido de los contents verifica usando la expresión match..with .
Luego, el elemento superior se separa del resto de la lista, se crea una nueva pila basada en los elementos restantes, y finalmente todo esto se devuelve como un par de tuplas.
Intente ejecutar este código y vea qué sucede. Obtendrá un error de compilación!
El compilador ha detectado un caso que no se ha resuelto: ¿qué sucede si la pila está vacía?
Tienes que decidir cómo manejarlo.
Por lo general, prefiero usar un estado especial para el error, pero en este caso particular, preferí lanzar una excepción. Versión fija de pop con manejo de mayúsculas y minúsculas vacío:
let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow"
Comprobar:
let initialStack = EMPTY |> ONE |> TWO let popped1, poppedStack = pop initialStack let popped2, poppedStack2 = pop poppedStack
y prueba de excepción:
let _ = pop EMPTY
Funciones aritméticas
Ahora que la adición y eliminación están en su lugar, puede comenzar a trabajar con las funciones "agregar" y "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 //
Pruebas en línea:
let add1and2 = EMPTY |> ONE |> TWO |> ADD let add2and3 = EMPTY |> TWO |> THREE |> ADD let mult2and3 = EMPTY |> TWO |> THREE |> MUL
Funciona!
Tiempo de refactorización ...
Obviamente, una cantidad significativa de código se duplica en estas dos funciones. ¿Cómo podemos arreglar esto?
Ambas funciones extraen dos valores de la pila, les aplican una determinada función binaria y luego vuelven a colocar el resultado en la pila. Puede enviar el código general a la función binaria, que toma una función matemática con dos parámetros:
let binary mathFn stack = // let y,stack' = pop stack // let x,stack'' = pop stack' // let z = mathFn xy // push z stack''
Tenga en cuenta que en esta implementación, las diferentes versiones del "mismo" objeto se marcan con un número diferente de comillas. Esto se debe a que los sufijos numéricos pueden conducir fácilmente a la confusión.
Pregunta: ¿por qué los parámetros tienen exactamente este orden, en lugar de que mathFn venga después de la stack ?
Ahora que tiene una función binary , es mucho más fácil definir ADD y otras funciones:
Primer intento de implementar ADD usando binary :
let ADD aStack = binary (fun xy -> x + y) aStack
Pero puedes deshacerte de lambda, porque representa la definición exacta de la función incorporada + :
let ADD aStack = binary (+) aStack
Una vez más, se puede usar una aplicación parcial para ocultar el parámetro de pila. Definición final:
let ADD = binary (+)
Definición de otras funciones matemáticas:
let SUB = binary (-) let MUL = binary (*) let DIV = binary (../)
Pruébalo en línea:
let div2by3 = EMPTY |> THREE|> TWO |> DIV let sub2from5 = EMPTY |> TWO |> FIVE |> SUB let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB
Del mismo modo, puede crear una función auxiliar para operaciones unarias
let unary f stack = let x,stack' = pop stack push (fx) stack'
Y defina algunas funciones unarias:
let NEG = unary (fun x -> -x) let SQUARE = unary (fun x -> x * x)
Modo interactivo:
let neg3 = EMPTY |> THREE|> NEG let square2 = EMPTY |> TWO |> SQUARE
Poniendo todo junto | Poniendo todo junto
En los requisitos iniciales se mencionó que nos gustaría poder mostrar los resultados, por lo que vale la pena definir la función SHOW.
let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack //
Tenga en cuenta que en este caso, se ignora la nueva versión de la pila recibida a través de pop . El resultado final es la pila original, como si nunca hubiera cambiado.
Finalmente, puede escribir el siguiente ejemplo de los requisitos originales
EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW
Seguir adelante
Es divertido, pero ¿qué más puedes hacer?
Puede definir varias funciones adicionales:
/// 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
Con estas funciones adicionales, puede escribir algunos ejemplos 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
Usar composición en lugar de canalizar
Pero eso no es todo. De hecho, hay otra forma interesante de representar estas funciones.
Como se señaló anteriormente, todos tienen la misma firma:
Stack -> Stack
Dado que la entrada y la salida son del mismo tipo, estas funciones también se pueden combinar usando el operador de composición >> , y no solo a través de operadores canalizados.
Algunos ejemplos
// 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
En cada uno de estos ejemplos, se define una nueva función utilizando una composición de otras funciones. Este es un buen ejemplo de un enfoque "combinatorio" para la funcionalidad del edificio.
Transportadores vs. Composición
Vimos dos formas diferentes de usar nuestro modelo; utilizando transportadores y composición. Pero cual es la diferencia? ¿Y por qué debería preferirse uno sobre otro?
La diferencia es que las tuberías son, en cierto sentido, una operación de "transformación en tiempo real". Al momento de usar la tubería, las operaciones se realizan de inmediato, a través de la transferencia de una pila específica.
Por otro lado, la composición es algo así como un "plan" que queremos implementar, construyendo funciones a partir de un conjunto de componentes sin aplicación directa.
Por ejemplo, puede crear un "plan" para calcular el cuadrado de un número mediante una combinación de pequeñas operaciones:
let COMPOSED_SQUARE = DUP >> MUL
No puedo dar el equivalente basado en tuberías.
let PIPED_SQUARE = DUP |> MUL
Esto dará como resultado un error de compilación. Necesito alguna instancia de pila específica para que la expresión funcione:
let stackWith2 = EMPTY |> TWO let twoSquared = stackWith2 |> DUP |> MUL
E incluso en este caso, puedo obtener una respuesta solo para esta entrada en particular, y no un plan de cálculo generalizado basado en ninguna entrada, como en el ejemplo con COMPOSED_SQUARE .
Otra forma de crear un "plan" es pasar explícitamente el lambda a funciones más primitivas:
let LAMBDA_SQUARE = unary (fun x -> x * x)
Esta es una forma más explícita (y muy probablemente más rápida), pero se pierden todas las ventajas y la claridad del enfoque compositivo.
En general, si es posible, ¡debe luchar por un enfoque compositivo!
Código completo
Código completo para todos los ejemplos anteriores:
// ============================================== // // ============================================== 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
Conclusión
Tenemos una calculadora simple basada en pila. Vimos cómo, comenzando con algunas operaciones primitivas ( push , pop , binary , unary ) y otras, puede construir un DSL completo, fácil de implementar y usar.
Como puede suponer, este ejemplo se basó en gran medida en el lenguaje Forth. Recomiendo el libro gratuito "Thinking Forth" , que habla no solo del lenguaje Forth, sino también de otros métodos (¡ no orientados a objetos!) Para descomponer tareas que son igualmente aplicables a la programación funcional en general.
Se me ocurrió la idea de este artículo del hermoso blog de Ashley Feniello . Si desea profundizar en la emulación de un lenguaje basado en pila basado en F #, comience con él. Diviértete!
Recursos Adicionales
Hay muchos tutoriales para F #, incluidos los materiales para aquellos que vienen con experiencia en C # o Java. Los siguientes enlaces pueden ser útiles a medida que profundiza en F #:
También se describen varias otras formas de comenzar a aprender F # .
Finalmente, la comunidad F # es muy amigable para principiantes. Hay un chat muy activo en Slack, respaldado por la F # Software Foundation, con salas para principiantes a las que puedes unirte libremente . ¡Recomendamos encarecidamente que haga esto!
¡No te olvides de visitar el sitio de la comunidad de habla rusa F # ! Si tiene alguna pregunta sobre el aprendizaje de un idioma, estaremos encantados de discutirlo en las salas de chat:
Sobre autores de traducción
Traducido por @kleidemos
La traducción y los cambios editoriales fueron realizados por los esfuerzos de la comunidad de desarrolladores de F # de habla rusa . También agradecemos a @schvepsss y @shwars por preparar este artículo para su publicación.