haskell - reservadas - Cómo generar funciones aleatorias tipadas.

imprimir en haskell (3)

¡Gracias por las respuestas muy detalladas de arriba! Sin embargo, ninguna de las respuestas hizo lo que estaba buscando. Seguí la sugerencia de DarkOtter en el comentario de la pregunta y utilicé unsafeCoerce evitar el corrector de tipos. La idea básica es que creamos un GADT que empaqueta las funciones de Haskell con sus tipos; el sistema de tipos que utilizo sigue muy de cerca a Mark P. Jones en "Typing Haskell in Haskell". Siempre que quiero una colección de funciones de Haskell, primero las coacciono en Any tipo, luego hago lo que necesito hacer, uniéndolas al azar. Cuando voy a evaluar las nuevas funciones, primero las coacciono para que vuelvan al tipo que yo quería. Por supuesto, esto no es seguro; si mi verificador de tipos es incorrecto o anoto las funciones de haskell con tipos incorrectos, entonces termino con tonterías.

He pegado el código con el que he probado esto a continuación. Tenga en cuenta que se están importando dos módulos locales, Strappy.Type y Strappy.Utils . El primero es el sistema de tipos mencionado anteriormente. El segundo trae ayudantes para los programas estocásticos.

Nota: en el código a continuación estoy usando la lógica combinatoria como el lenguaje básico. Es por eso que mi lenguaje de expresión solo tiene aplicación y no tiene variables o abstracción lambda.

{-# Language GADTs, ScopedTypeVariables #-} import Prelude hiding (flip) import qualified Data.List as List import Unsafe.Coerce (unsafeCoerce) import GHC.Prim import Control.Monad import Control.Monad.State import Control.Monad.Trans import Control.Monad.Identity import Control.Monad.Random import Strappy.Type import Strappy.Utils (flip) -- | Helper for turning a Haskell type to Any. mkAny :: a -> Any mkAny x = unsafeCoerce x -- | Main data type. Holds primitive functions (Term), their -- application (App) and annotations. data Expr a where Term :: {eName :: String, eType :: Type, eThing :: a} -> Expr a App :: {eLeft :: (Expr (b -> a)), eRight :: (Expr b), eType :: Type} -> Expr a -- | smart constructor for applications a <> b = App a b (fst . runIdentity . runTI $ typeOfApp a b) instance Show (Expr a) where show Term{eName=s} = s show App{eLeft=el, eRight=er} = "(" ++ show el ++ " " ++ show er ++ ")" -- | Return the resulting type of an application. Run''s type -- unification. typeOfApp :: Monad m => Expr a -> Expr b -> TypeInference m Type typeOfApp e_left e_right = do t <- newTVar Star case mgu (eType e_left) (eType e_right ->- t) of (Just sub) -> return $ toType (apply sub (eType e_left)) Nothing -> error $ "typeOfApp: cannot unify " ++ show e_left ++ ":: " ++ show (eType e_left) ++ " with " ++ show e_right ++ ":: " ++ show (eType e_right ->- t) eval :: Expr a -> a eval Term{eThing=f} = f eval App{eLeft=el, eRight=er} = (eval el) (eval er) filterExprsByType :: [Any] -> Type -> TypeInference [] Any filterExprsByType (e:es) t = do et <- freshInst (eType (unsafeCoerce e :: Expr a)) let e'' = unsafeCoerce e :: Expr a case mgu et t of Just sub -> do let eOut = unsafeCoerce e''{eType = apply sub et} :: Any return eOut `mplus` rest Nothing -> rest where rest = filterExprsByType es t filterExprsByType [] t = lift [] ---------------------------------------------------------------------- -- Library of functions data Library = Library { probOfApp :: Double, -- ^ probability of an expansion libFunctions :: [Any] } cInt2Expr :: Int -> Expr Int -- | Convert numbers to expressions. cInt2Expr i = Term (show i) tInt i -- Some basic library entires. t = mkTVar 0 t1 = mkTVar 1 t2 = mkTVar 2 t3 = mkTVar 3 cI = Term "I" (t ->- t) id cS = Term "S" (((t2 ->- t1 ->- t) ->- (t2 ->- t1) ->- t2 ->- t)) $ /f g x -> (f x) (g x) cB = Term "B" ((t1 ->- t) ->- (t2 ->- t1) ->- t2 ->- t) $ /f g x -> f (g x) cC = Term "C" ((t2 ->- t1 ->- t2 ->- t) ->- t1 ->- t2 ->- t) $ /f g x -> (f x) g x cTimes :: Expr (Int -> Int -> Int) cTimes = Term "*" (tInt ->- tInt ->- tInt) (*) cPlus :: Expr (Int -> Int -> Int) cPlus = Term "+" (tInt ->- tInt ->- tInt) (+) cCons = Term ":" (t ->- TAp tList t ->- TAp tList t) (:) cAppend = Term "++" (TAp tList t ->- TAp tList t ->- TAp tList t) (++) cHead = Term "head" (TAp tList t ->- t) head cMap = Term "map" ((t ->- t1) ->- TAp tList t ->- TAp tList t1) map cEmpty = Term "[]" (TAp tList t) [] cSingle = Term "single" (t ->- TAp tList t) $ /x -> [x] cRep = Term "rep" (tInt ->- t ->- TAp tList t) $ /n x -> take n (repeat x) cFoldl = Term "foldl" ((t ->- t1 ->- t) ->- t ->- (TAp tList t1) ->- t) $ List.foldl'' cNums = [cInt2Expr i | i <- [1..10]] -- A basic library exprs :: [Any] exprs = [mkAny cI, mkAny cS, mkAny cB, mkAny cC, mkAny cTimes, mkAny cCons, mkAny cEmpty, mkAny cAppend, -- mkAny cHead, mkAny cMap, mkAny cFoldl, mkAny cSingle, mkAny cRep ] ++ map mkAny cNums library = Library 0.3 exprs -- | Initializing a TypeInference monad with a Library. We need to -- grab all type variables in the library and make sure that the type -- variable counter in the state of the TypeInference monad is greater -- that that counter. initializeTI :: Monad m => Library -> TypeInference m () initializeTI Library{libFunctions=es} = do put (i + 1) return () where go n (expr:rest) = let tvs = getTVars (unsafeCoerce expr :: Expr a) getTVars expr = tv . eType $ expr m = maximum $ map (readId . tyVarId) tvs in if null tvs then 0 else go (max n m) rest go n [] = n i = go 0 es ---------------------------------------------------------------------- ---------------------------------------------------------------------- -- Main functions. sampleFromExprs :: (MonadPlus m, MonadRandom m) => Library -> Type -> TypeInference m (Expr a) -- | Samples a combinator of type t from a stochastic grammar G. sampleFromExprs lib@Library{probOfApp=prApp, libFunctions=exprs} tp = do initializeTI lib tp'' <- freshInst tp sample tp'' where sample tp = do shouldExpand <- flip prApp case shouldExpand of True -> do t <- newTVar Star (e_left :: Expr (b -> a)) <- unsafeCoerce $ sample (t ->- tp) (e_right :: Expr b) <- unsafeCoerce $ sample (fromType (eType e_left)) return $ e_left <> e_right -- return application False -> do let cs = map fst . runTI $ filterExprsByType exprs tp guard (not . null $ cs) i <- getRandomR (0, length cs - 1) return $ unsafeCoerce (cs !! i) ---------------------------------------------------------------------- ---------------------------------------------------------------------- main = replicateM 100 $ do let out = runTI $ do sampleFromExprs library (TAp tList tInt) x <- catch (liftM (Just . fst) out) (/_ -> putStrLn "error" >> return Nothing) case x of Just y -> putStrLn $ show x ++ " " ++ show (unsafeCoerce (eval y) :: [Int]) Nothing -> putStrLn ""

Me gustaría generar mediante programación funciones aleatorias de Haskell y evaluarlas. Me parece que la única forma de hacer esto es básicamente generar el código de Haskell mediante programación y ejecutarlo mediante la API de GHC o un proceso externo, devolver una cadena y analizarla de nuevo en un tipo de datos de Haskell. ¿Es esto cierto?

Mi razonamiento es el siguiente. Las funciones son polimórficas, así que no puedo usar Typeable. Más importante aún, incluso si escribo mi propio verificador de tipos y anoto cada función con su tipo, no puedo demostrarle al compilador de Haskell que mi verificador de tipos es correcto. Por ejemplo, cuando saco dos funciones de una colección heterogénea de funciones y aplico una a la otra, necesito proporcionar al compilador una garantía de que la función que estoy usando para elegir estas funciones solo elige funciones con los tipos correspondientes. Pero no hay manera de hacer esto, ¿verdad?

¿Algo en esta línea satisfaría sus necesidades?

import Control.Monad.Random randomFunction :: (RandomGen r, Random a, Num a, Floating a) => Rand r (a -> a) randomFunction = do (a:b:c:d:_) <- getRandoms fromList [(/x -> a + b*x, 1), (/x -> a - c*x, 1), (/x -> sin (a*x), 1)] -- Add more functions as needed main = do let f = evalRand randomFunction (mkStdGen 1) :: Double -> Double putStrLn . show $ f 7.3

EDITAR: Basándonos en esa idea, podríamos incorporar funciones que tengan diferentes números y tipos de parámetros ... siempre que los apliquemos parcialmente para que todos tengan el mismo tipo de resultado.

import Control.Monad.Random type Value = (Int, Double, String) -- add more as needed type Function = Value -> String -- or whatever the result type is f1 :: Int -> Int -> (Int, a, b) -> Int f1 a b (x, _, _) = a*x + b f2 :: String -> (a, b, String) -> String f2 s (_, _, t) = s ++ t f3 :: Double -> (a, Double, b) -> Double f3 a (_, x, _) = sin (a*x) randomFunction :: RandomGen r => Rand r Function randomFunction = do (a:b:c:d:_) <- getRandoms -- some integers (w:x:y:z:_) <- getRandoms -- some floats n <- getRandomR (0,100) cs <- getRandoms -- some characters let s = take n cs fromList [(show . f1 a b, 1), (show . f2 s, 1), (show . f3 w, 1)] -- Add more functions as needed main = do f <- evalRandIO randomFunction :: IO Function g <- evalRandIO randomFunction :: IO Function h <- evalRandIO randomFunction :: IO Function putStrLn . show $ f (3, 7.3, "hello") putStrLn . show $ g (3, 7.3, "hello") putStrLn . show $ h (3, 7.3, "hello")

El comentario de DarkOtter menciona las clases Arbitrary y Arbitrary de QuickCheck, que ciertamente son lo primero que debe intentar. QuickCheck tiene esta instancia:

instance (CoArbitrary a, Arbitrary b) => Arbitrary (a -> b) where ...

Como sucedió, ayer estaba leyendo el código de QuickCheck para entender cómo funciona esto, así que puedo compartir lo que aprendí mientras estoy fresco en mi mente. QuickCheck se basa en un tipo que se ve así (y no será exactamente el mismo):

type Size = Int -- | A generator for random values of type @a@. newtype Gen a = MkGen { -- | Generate a random @a@ using the given randomness source and -- size. unGen :: StdGen -> Size -> a } class Arbitrary a where arbitrary :: a -> Gen a

El primer truco es que QuickCheck tiene una función que funciona así (y no entendí exactamente cómo se implementó):

-- | Use the given ''Int'' to /"perturb/" the generator, i.e., to make a new -- generator that produces different pseudorandom results than the original. variant :: Int -> Gen a -> Gen a

Luego lo usan para implementar varias instancias de esta clase CoArbitrary :

class CoArbitrary a where -- | Use the given `a` to perturb some generator. coarbitrary :: a -> Gen b -> Gen b -- Example instance: we just treat each ''Bool'' value as an ''Int'' to perturb with. instance CoArbitrary Bool where coarbitrary False = variant 0 coarbitrary True = variant 1

Ahora con estas piezas en su lugar, queremos esto:

instance (Coarbitrary a, Arbitrary b) => Arbitrary (a -> b) where arbitrary = ...

No escribiré la implementación, pero la idea es esta:

Usando la instancia CoArbitrary de a y la instancia Arbitrary de b podemos hacer que la función /a -> coarbitrary a arbitrary , que tiene el tipo a -> Gen b .
Recuerde que Gen b es un newtype para StdGen -> Size -> b , por lo que el tipo a -> Gen b es isomorfo a a -> StdGen -> Size -> b .
Podemos escribir de forma trivial una función que toma cualquier función de este último tipo y cambia el orden de los argumentos para devolver una función de tipo StdGen -> Size -> a -> b .
Este tipo reordenado es isomorfo a Gen (a -> b) , así que voilà, empaquetamos la función reordenada en un Gen , ¡y obtuvimos nuestro generador de funciones aleatorias!

Te recomendaría que leas la fuente de QuickCheck para ver esto por ti mismo. Cuando aborde eso, solo se encontrará con dos detalles adicionales que podrían ralentizarlo. Primero, la clase Haskell RandomGen tiene este método:

-- | The split operation allows one to obtain two distinct random generators. split :: RandomGen g => g -> (g, g)

Esta operación se utiliza en la instancia de Monad para Gen , y es bastante importante. Uno de los trucos aquí es que el StdGen es un generador de números pseudoaleatorios puro; la forma en que Gen (a -> b) funciona es que para cada valor posible de a perturbamos un generador b , usamos ese generador perturbado para generar el resultado b , pero nunca avanzamos el estado del generador perturbado ; básicamente, la función a -> b generada es un cierre sobre una semilla pseudoaleatoria, y cada vez que la llamamos con alguna a , usamos esa a específica para crear deterministicamente una nueva semilla, y luego la usamos para generar de manera determinística una b que depende en a y la semilla oculta.

El tipo abreviado Seed -> a -> b más o menos resume lo que está sucediendo: una función pseudoaleatoria es una regla para generar una b partir de una semilla pseudoaleatoria y una a . Esto no funcionará con generadores de números aleatorios de estado imperativo.

Segundo: en lugar de tener directamente una función (a -> StdGen -> Size -> b) -> StdGen -> Size -> a -> b como describí anteriormente, el código QuickCheck tiene promote :: Monad m => m (Gen a) -> Gen (ma) , que es la generalización de eso a cualquier Monad . Cuando m es la instancia de función de Monad , la promote coincide con (a -> Gen b) -> Gen (a -> b) , por lo que realmente es lo mismo que dibujé anteriormente.