Free monads pentru Logo


#1

Prezentărea lui Ionuț de data trecută, An Applicative Application, m-a impulsionat să învăț mai mult despre ideea de freeness în programare. Și pentru a mă familiariza cu conceptul de free monads, am încercat să traduc un tutorial despre acest subiect din Scala în Haskell. Exemplul lor implementează un subset restrâns al limbajului Logo (cunoscut și sub numele de turtle graphics). Ideea e să definim un algebraic data type (ADT) care descrie sintaxa limbajului și apoi, cu ajutorul ideei de free monads, să reprezentăm și să interpretăm programe scrise folsoind sintaxa respectivă.

Din păcate, am întâlnit niște hopuri pe parcurs și mă gândeam că poate cineva de aici mă poate ajuta să le depășesc :slight_smile:

Prima mea încercare a fost o traducere relativ ad litteram:

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.Free
import Data.Functor.Identity

-- Alternativ, aș fi putut utiliza GADTs pentru a replica mai fidel codul
-- corespunzător de Scala, dar un simplu ADT ar trebui să funcționeze.
data InstructionF a = Forward      Position Int
                    | Backward     Position Int 
                    | RotateLeft   Position Degree
                    | RotateRight  Position Degree
                    | ShowPosition Position
    deriving (Eq, Functor, Show)

data Position = Pos { unPos :: (Double, Double, Degree) }
    deriving (Eq, Show)

data Degree   = Deg { unDeg :: Int }
    deriving (Eq, Show)

type Instruction = Free InstructionF

forward :: Position -> Int -> Instruction Position
forward pos len = liftF $ Forward pos len

backward :: Position -> Int -> Instruction Position
backward pos len = liftF $ Backward pos len

left :: Position -> Degree -> Instruction Position
left pos deg = liftF $ RotateLeft pos deg 

right :: Position -> Degree -> Instruction Position
right pos deg = liftF $ RotateRight pos deg

showPos :: Position -> Instruction ()
showPos pos = liftF $ ShowPosition pos

program :: Position -> Instruction Position
program start = do p1 <- forward start 10
                   p2 <- right p1 (Deg 90)
                   p3 <- forward p2 10
                   return p3

-- TODO
interpId :: InstructionF a -> Identity a
interpId = \case
    Forward      pos len -> undefined
    Backward     pos len -> undefined
    RotateLeft   pos deg -> undefined
    RotateRight  pos deg -> undefined
    ShowPosition pos     -> undefined

Dar apoi am observat că programele sunt incomplete – conțin doar prima instrucțiune:

*Main> program (Pos (0, 0, Deg 0))
Free (Forward (Pos {unPos = (0.0,0.0,Deg {unDeg = 0})}) 10)

Cred că problema apare pentru că instanța de Functor derivată automat pentru InstructionF nu e tocmai ce ar trebui să fie. De fapt, am observat că cineva ridicat o întrebare în această direcție pe pagina tutorialului:

Quick question: your trait Instruction[A] doesn’t seem to be a functor (in that there’s no way to construct anything other than Instruction[Position|Unit], so no way to write a polymorphic map). Other formulations of the free monad that I’ve seen seem to require the algebra to be a functor; is that not actually strictly required?

și i s-a răspuns:

scalaz utilizes Coyoneda to provide a functor for any algebra when you use it inside a Free, I suspect cats is doing the same. It’s there you just don’t have to define it.

Aceasta ar fi direcția în care să corectez codul de mai sus? Să folosesc o instanță de Functor bazată pe Coyoneda? :thinking:


#2

Salut,

Incep cu wall of code:

{-# language DeriveFunctor #-}

module Instruction where

import Control.Monad.Free

data InstructionF next
    = Forward Position Int (Position -> next)
    | Backward Position Int (Position -> next)
    | RotateLeft Position Degree (Position -> next)
    | RotateRight Position Degree (Position -> next)
    | ShowPosition Position next
    deriving (Functor)

data Position = Position
    { _x :: Int
    , _y :: Int
    , _rot :: Degree
    }
    deriving (Eq, Show)

newtype Degree = Degree Int
    deriving (Eq, Show)

type Instruction = Free InstructionF

forward :: Position -> Int -> Instruction Position
forward pos len = liftF $ Forward pos len id

program :: Instruction Position
program = do
  pos <- forward (Position 0 0 (Degree 0)) 10
  forward pos 10

interpret :: Instruction Position -> Position
interpret = iter go
    where
      go :: InstructionF Position -> Position
      go (Forward p i next) = next (p { _x = _x p + i })
      go _ = error "not implemented yet"

Ideea principala ar fi ca data type-ul tau trebuie sa reflecte faptul ca este un interpretor. In codul tau, parametrul a era phantom type, ceea ce nu este suficient. L-am redenumit in next sa fie mai evident.

Urmatorul lucru ar fi ca “input”-urile trebuie sa fie pe pozitii pozitive (cum sunt Position si Int in Forward Position Int, dar “output”-ul trebuie sa fie pe pozitie negativa (cum este Position in Position -> next). (din pacate, asta inseamna ca pierdem Show si Eq, pentru ca nu pot fi definite pe functii)

Mai departe, putem defini smart constructors (cum ai facut si tu) pentru a ne fi mai usor sa-i folosim; ideea fiind ca folosim identitate (id) pentru functiile introduse (practic punem Position -> Position in locurile cu Position -> next).

Programul ramane relativ neschimbat. Nu am implementat restul de constructori, dar ar trebui sa mearga similar. Nu sunt sigur ce faci cu ShowPosition daca oricum fiecare pas intoarce pozitia.

Interpretorul nu face decat sa trimita mai departe input-ul modificat corespunzator.

La ceva de genul astsa te refereai?

Edit: Nice read: http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html


#3

Super! Mulțumesc mult @cvlad!

Într-adevăr, asta era direcția în care doream să mă întrept. Și da, au sens acele continuations, Position → next și next (sau () → next), care permit un nou pas în execuție și, astfel, construirea unui program. Cred că am încercat o traducere prea mot a mot a codului din Scala :slight_smile:

Între timp, am mai lucrat și am ajuns la o variantă care folosește un tip de date apropiat de cel din tutorial. Peste acesta am aplicat Coyoneda :scream_cat: , care cred că “adaugă” automat continuations-urile din tipul tău de date.

{-# LANGUAGE GADTs #-}                                     
{-# LANGUAGE Rank2Types #-}                                

import Control.Monad.Free                                  
import Data.Functor.Coyoneda                               
import Data.Functor.Identity                               

data InstructionF a where                                  
        Forward      :: Position -> Int    -> InstructionF Position                                                   
        Backward     :: Position -> Int    -> InstructionF Position                                                   
        RotateLeft   :: Position -> Degree -> InstructionF Position                                                   
        RotateRight  :: Position -> Degree -> InstructionF Position                                                   
        ShowPosition :: Position -> InstructionF ()        

data Position = Position                                   
    { _x :: Int                                            
    , _y :: Int                                            
    , _rot :: Degree                                       
    }                                                      
    deriving (Eq, Show)                                    

newtype Degree = Degree Int                                
    deriving (Eq, Show)                                    

type Instruction = Free (Coyoneda InstructionF)            

forward :: Position -> Int -> Instruction Position         
forward pos len = liftF $ liftCoyoneda $ Forward pos len   

program :: Instruction Position                            
program = do                                               
  pos <- forward (Position 0 0 (Degree 0)) 10              
  forward pos 10                                           

interpId :: InstructionF a -> Identity a                   
interpId (Forward p i) = Identity $ p { _x = _x p + i }    
interpId _             = error "not implemented yet"       

run :: Monad m => (forall x. InstructionF x -> m x) -> Instruction a -> m a                                           
run interp = foldFree (lowerCoyoneda . hoistCoyoneda interp)                                                          

-- *Main> run interpId program                             
-- Identity (Position {_x = 20, _y = 0, _rot = Degree 0})

O altă diferență este faptul că tu ai folosit iter, pe când eu am utilizat foldFree pentru a parcurge free monad. Nu sunt sigur care variantă ar trebui preferată (sau dacă e vreuna).

Bănuiesc că pentru interpretorul curent, la monada Identity, ar trebui să fie un no-op:

go (ShowPosition _ next) = next                            

dar îmi imaginez situații, de exemplu, un interpretor în IO, când ShowPosition ar putea face ceva – putStrLn la poziția curentă.


Și mulțumesc și pentru referință! Am frunzărit articolul la un moment dat, dar acum cred că e un moment bun să-l revizuiesc :+1:


#4

Interesant! Chiar vroiam sa ma uit la Coyoneda si eu. Tot mi se pare putin fishy acel phantom a. O sa ma joc cu exemplul asta si revin. :slight_smile:

Tipul pentru iter mi s-a parut mai util, pentru ca nu vroiam sa wrap-uiesc tot in Identity sau alt Monad. Evident, daca interpretarea free monad-ului presupune lucru in alt monad (spre exemplu acel ShowPosition ar putea sa faca un print in IO), atunci trebuie foldFree sau iterM.


#5

Mie-mi pare, așa la prima vedere, că “it defeats the purpose” să pui continuation-ul în InstructionF. Free monad trebuie se ocupe de partea de continuation.


#6

Mda, am citit articolul lui Gonzales și trebuie să trag concluzia că m-am obișnuit cu ce fac cei din Scala — aplică co-Yeneda pe GATDs.


#7

Weakly realted, ati dat peste un tutorial practic/util despre Yoneda si/sau Coyoneda? Simt ca sunt aproape sa inteleg ceva daca ma holbez suficient la tipuri, desi…


#8

Defapt cred ca Coyoneda este relativ simplu, este free Functor. Yoneda in schimb pare mai complicat putin, cel putin momentan pentru mine.


#9

Da, așa este. Cu ajutorul Coyoneda putem trece de la un constructor arbitrar de tipuri, kind * → *, la un Functor (adică îi putem atașa operația de fmap). Dar eu încă nu-l “simt”, cred că din cauza tipului existențial, pe care nu-l înțeleg:

data Coyoneda f a = forall b. Coyoneda (f b) (b -> a)

Și eu aș fi interesat de ceva referințe pe tema asta. Momentan, legat de co-Yoneda m-am oprit la secțiunea 3.4 din What You Needa Know about Yoneda de Boisseau și Gibbons (ICFP’18), care are câteva perspective interesante, printre care (i) o derivare a tipului Coyoneda, pornind de la Yoneda, (ii) și un paragraf cu referințe:

This is sometimes called ‘the co-Yoneda trick’ [Manzyuk 2013]. It can be used to make a generalized algebraic datatype a functor when the type parameter is used only as an index, so cannot be varied freely; for example, Gibbons [2016] uses it to enable do notation on a GADT representing monomorphic typed commands. Even when the f parameter is already a functor, this change of representation can be an efficiency-improving transformation, because it turns a traversal over each of the elements of the payload x into a simple composition with one function h [Avramenko 2017]—that is, it implements the map fusion rule for free. New [2017] shows that the closure conversion of a function of type a → b yields one of type a → ∃e . e × (e → b), the result of which is a closure with hidden environment type e. That is, the closure conversion of function type a → b is a → CoYo Id b; New describes closure conversion itself as a kind of dual to CPS, both being applications of the Yoneda Lemma for the identity functor.