Un parser monádico combinatorio en Clojure para enrutar URLs
Una parte básica de cualquier framework web es el router. El componente que se encarga de aceptar una petición desde el servidor web para una determinada URL y método HTTP y decide que código de la aplicación debe ejecutarse para satisfacer dicha petición.
Existen muchas soluciones, algunas más díficiles de usar como el mapeo que se realiza entre URLs y Servlets en una aplicación web Java y otras más elegantes como el router de rails. Últimamente, el router de Rails parece ser el paradigma que imitan la miriada de frameworks web que existen actualmente.
El router de Rails permite escribir código Ruby muy compacto que indica patrones de URL, asignando partes de esas URL a variables y condiciones sobre partes de la URL, así como el controlador y la acción que debe ejecutarse. Por ejemplo:
map.connect '/activation/:code',
:controller => 'users',
:action => 'activation',
:requirements => { :code => /\d+/}
En esa pequeña porción de código Ruby se está indicando que cualquier URL que siga el patrón "/activation/" seguido de lo que sea deberá enrutarse al controlador "users" y a la función "activation", siempre que la parte "lo que sea" de la ruta haga match de la expresión regular especificada. Además la parte "lo que sea" estará disponible para la funcion "activation" como el parámetro "code".
¿Podemos escribir la funcionalidad anterior en Clojure? o mejor aún, ¿podemos mejorarlo? Vamos a ver.
Si observamos desde un punto de vista de alto nivel que es lo que queremos construir nos damos cuenta que nos enfrentamos a un problema de parseo. Supongamos que tenemos un parser que dada una petición HTTP con la siguiente información: método, url, parámetros, lo transforma en una lista de tokens donde se indica el tipo de token (método, parte de la URL, parametros). Un posible parser podría ser el siguiente:
(defn parse-string-eq
"Parses a token checking for string equality"
{:monad :Maybe}
([string token state]
(if (is-token-url-part? token)
(if (= (token-value token) string)
(just state)
(nothing))
(nothing))))
Esta función comprueba que el token que recibe es igual que una cadena que le pasan como parámetro y en función de la comprobación devuelve o error si no hay coincidencia o acepta el tokeny devuelve el estado que le han pasado de parseo, en este caso sin modificar. Se puede observar como la función es monádica. El parseo de un token es un proceso que puede fallar o no, por eso la función envuelve su resultado en la mónada Maybe. Si el parseo falla, devuelve Nothing, si tiene éxito, devuelve Just el estado del proceso de parseo modifcado.
Vamos a probar como funcionaría este parser:
(deftest test-parse-string-eq-ok
(is (= (parse-string-eq "test" {:type :url-part :value "test"} {})
(just {}))))
Este test comprueba que el resultado de aplicar el parser para "test" del token "{:type :url-part :value "test"}" y el estado "{}" es correcto "(just {})". Sin embargo, hagamos un test para comprobar el fallo:
(deftest test-parse-string-eq-nok
(is (= (parse-string-eq "test" {:type :url-part :value "other"} {})
(nothing))))
En este caso el test falla, no ha coincidencia entre "test" y "other" y el parser devuelve Nothing.
Podemos escribir muchos más parsers, para distintas funciones y tipos de token:
Expresiones regulares:
(defn parse-regex
"Parses a token checking for a provided regular expression"
{:monad :Maybe}
([regex token state]
(if (is-token-url-part? token)
(if (re-matches regex (token-value token))
(just state)
(nothing)))))
;; test
(deftest test-parse-regex-ok
(is (= (parse-regex '#"[a-z]+" {:type :url-part :value "test"} {})
(just {}))))
Métodos HTTP:
(defn parse-http-method
"Parses a token looking for a HTTP method"
{:monad :Maybe}
([method token state]
(if (is-token-http-method? token)
(if (= (token-value token) method)
(just state)
(nothing))
(nothing))))
;; test
(deftest test-parse-method-eq-ok
(is (= (parse-http-method :get {:type :http-method :value :get} {})
(just {}))))
Almacenamiento de partes de la URL en variables:
(defn parse-variable
"Captures the token as a variable with the given name"
{:monad :Maybe}
([name token state]
(let [keyword-name (if (keyword? name) name (keyword name))]
(if (is-token-url-part? token)
(just (merge {keyword-name (token-value token)} state))
(nothing)))))
;; test
(deftest test-parse-var-ok
(is (= (parse-variable :test {:type :url-part :value "23"} {:a 1})
(just {:a 1 :test "23"}))))
Y muchos mas...
Como las funciones de parser son monádicas, podríamos combinarlas con el operador monádico de binding (>>=) con el fin de obtener un parser compuesto para una lista de tokens:
(deftest test-monadic-http-token-composition-ok-1
(let [request (list '({:value :get, :type :http-method}
{:value "google", :type :url-part}
{:value "es", :type :url-part})
{:test :a})]
(is (=
(do->>= (c_ parse-http-method :get) (just request)
(c_ parse-string-eq "google")
(c_ parse-variable :lang))
(just '(nil {:test :a :lang "es"}))))))
Como se puede ver hemos utilizado la macro (do->>=) para enlazar tres parsers currificados (c_ es una macro que aplica parcialmente la función) sobre la petición "GET /google.es".
En este punto, tenemos un parser con una notación bastante fea pero que esencialmente tiene las mismas capacidades que el router de Rails. A continucación, necesitamos hacer dos cosas: ofrecer una notación más simple y ofrecer una mayor potencia para parsear URLs.
Empecemos por esto último. Una forma sencilla de hacer parsers más potentes es usar combinadores que enlazan agregan parsers más simples para ofrecer una funcionalidad más compleja. Si conocéis la estupenda biblioteca Parsec de Haskell, sabéis a lo que me estoy refiriendo.
El combinador más sencillo es el combinador "run-one", que acepta un parser, una lista de tokens y un estado de la computación, aplica el parser al primer token y estado, y devuelve o Nothing si el parser falla, o Just el resto de tokens y el estado modificado por el parser, si el parseo tiene éxito:
(defn run-one
"Accepts a parser, a stream of tokens and a state
and runs the the parser on the first token of the
stream with the given state"
{:monad :Maybe}
([parser computation]
(let [tokens (first computation)
state (second computation)] ;; we extract the tokens and state
(if (nil? tokens) ;; no more tokens?
(nothing) ;; error, there should be something more to parse
(let [parsing-result (parser (first tokens) state)] ;; run the parser
(if (nothing? parsing-result) ;; parsing error
(nothing)
(just (list (rest tokens) ;; on success return rest of tokens and new state
(from-maybe parsing-result)))))))))
A partir de este combinador, se podrían escribir múltiples combinadores con funcionalidad cada vez más compleja. Por ejemplo:
run-many: que ejecuta el mismo parser sobre tantos tokens de la lista como sea posible:
(defn run-many
"Accepts a parser, a stream of tokens and a state
and runs the parser on every token of the stream
till the parser fails or there
are no more tokens left, returning success"
{:monad :Maybe}
([parser computation]
(loop [current-computation computation] ;; keep on looping till no more tokens or parser error
(let [tokens (first current-computation)]
(if (nil? tokens) ;; end of stream?
(just computation) ;; then success with the current state
(let [parsing-result (run-one parser current-computation)] ;; run parser one time
(if (nothing? parsing-result) ;; error?
(just current-computation) ;; return last successful state and stream
(recur (from-maybe parsing-result))))))))) ;; let's parse another token
run-and: que intenta ejecutar todos los parsers sobre el mismo token o falla
(defn run-and
"Accepts a list of parsers and run then sequentially on the
same token"
{:monad :Maybe}
([parsers computation]
(let [tokens (first computation)
state (second computation)]
(if (nil? tokens)
(nothing)
(loop [the-parsers parsers
current-state state]
(let [the-parser (first the-parsers)
result (the-parser (first tokens) current-state)]
(if (nothing? result)
(nothing)
(if (nil? (rest the-parsers))
(just (list (rest tokens)
(from-maybe result)))
(recur (rest the-parsers)
(from-maybe result))))))))))
run-or: que ejecuta una serie de parsers sobre el mismo token hasta que alguno tiene éxito
(defn run-or
"Accepts a list of parsers and returns the result of the first
successful parser or nothing if every parser fails"
{:monad :Maybe}
([parsers computation]
(let [tokens (first computation)
state (second computation)]
(if (nil? tokens)
(nothing)
(loop [the-parsers parsers]
(let [the-parser (first the-parsers)
result (the-parser (first tokens) state)]
(if (nothing? result)
(if (not (= nil (rest the-parsers)))
(recur (rest the-parsers))
(nothing))
(just (list (rest tokens) (from-maybe result))))))))))
Las posibilidades son inacabables.
Los combinadores son también funciones monádicas, por lo que podemos enlazarlas también por el operador de binding de mónadas, para construir parsers más sofísticados: Por ejemplo, parsear URLs del tipo (GET || POST) http://(google/)+other/google.es, guardando la última parte como el idioma deseado:
(deftest test-monadic-http-token-composition-ok-2
(let [request (list '({:value :get, :type :http-method}
{:value "google", :type :url-part}
{:value "google", :type :url-part}
{:value "google", :type :url-part}
{:value "other", :type :url-part}
{:value "google", :type :url-part}
{:value "es", :type :url-part})
{:test :a})]
(is (=
(do->>= (c_ run-or [(c_ parse-http-method :get)
(c_ parse-http-metho :post)]) (just request)
(c_ run-many (c_ parse-string-eq "google"))
(c_ run-one (c_ parse-string-eq "other"))
(c_ run-one (c_ parse-string-eq "google"))
(c_ run-and [(c_ parse-string-eq "es")
(c_ parse-variable :lang)]))
(just '(nil {:test :a :lang "es"}))))))
El único problema es que construir el parser combinado, con tantas funciones currificadas y tanto binding, puede ser un poco complicado, así que construiremos una macro que permita especificar parsers de una manera sencilla con unas pocas reglas:
- una coincidencia literal se expresa como: "parte"
- una coincidencia con una expresión regular: #"reg-ex"
- almacenar una parte en una variable: :nombre-variable
- aplicar or a una serie de parsers: (|| parsers)
- aplicar and a una serie de parsers: (&& parsers)
- aplicar many-times a un parser: (* parser)
- parseo de parámetros: (params parsers)
- existencia de un parámetro: (params :param-name)
- existencia y valor de un parámetro: (params (:param-name param-value))
- método http: METODO
La macro utiliza la función parser-factory, para devolver la función de parseo correcta según el lenguaje de dominio que hemos especificado:
(defn parser-factory [t]
"Looks for a correct parser for simplified token notation:
- \"string\" -> parser-string-eq \"string\"
- SYMBOL -> parser-http-method :symbol
- :keyword -> parser-variable :keyword
- #\"regex\" -> parser-regex #\"regex\"
- (* token) -> (run-many token)
- (&& tokens) -> (run-and (parser tokens))
- (|| tokens) -> (run-or (parser tokens))
- (params params) -> parsers combination for params token"
(if (= (class t) clojure.lang.Symbol)
(let [kw (keyword (. (str t) toLowerCase))]
(c_ run-one (c_ parse-http-method kw)))
(if (= (class t) java.lang.String)
(c_ run-one (c_ parse-string-eq t))
(if (= (class t) clojure.lang.Keyword)
(c_ run-one (c_ parse-variable t))
(if (= (class t) java.util.regex.Pattern)
(c_ run-one (c_ parse-regex t))
(if (= (class t) clojure.lang.PersistentList)
(let [symb (first t)
parsers (rest t)]
(if (= (str symb) "params")
(let [others (map (fn[x] (parser-factory-params x)) parsers)]
(c_ run-and others ))
(if (= (str symb) "*")
(let [nt (first parsers)]
(c_ run-many (parser-factory-inner nt)))
(if (= (str symb) "&&")
(let [others (map (fn[x] (parser-factory-inner x)) parsers)]
(c_ run-and others ))
(if (= (str symb) "||")
(let [others (map (fn[x] (parser-factory-inner x)) parsers)]
(c_ run-or others))
(c_ run-one (parse-anything t)))))))
(c_ run-one (parse-anything t))))))))
Con esta macro, ya podríamos reescribir el ejemplo anterior de la siguiente manera:
(c_ check-route [(|| GET POST) (* "google") "other" "google" (&& "es" :lang)])
Además, añadir nuevas funciones de parseo es trivial, simplemente hay que añadir parsers, combinadores y la traducción al DSL para especificar el nuevo parseo en la notación simplificada.
Algún ejemplo más (mock-request construye una lista de tokens de prueba):
(deftest test-check-route-7
(is (=
(check-route '[(|| GET POST) "google" (&& "es" :lang) (params :test (:b 2))]
(list (mock-request-http-tokens-with-params :get '("google" "es") '((:test 1) (:b 2)))
{}))
'{:monad-type :Maybe, :monad-subtype :Just, :content (nil {:lang "es"})})))
El código con los tests se puede encontrar en mi repositorio de Github
