Personal tools

Diagrams/Dev/Fixpoint

From HaskellWiki

< Diagrams | Dev(Difference between revisions)
Jump to: navigation, search
m (fix module names)
(more design)
Line 1: Line 1:
This page describes the motivation and design for a refactoring of diagrams, to give them a semantics based on computing fixed points of functions from "context" information to raw tree of primitives together with some summary information.
+
This page describes the motivation and design for a refactoring of
 +
diagrams, to give them a semantics based on computing fixed points of
 +
functions from "context" information to raw tree of primitives
 +
together with some summary information.
  
 
== Reference ==
 
== Reference ==
  
See the original "manifesto" and ensuing mailing list discussion here: http://thread.gmane.org/gmane.comp.lang.haskell.diagrams/383
+
See the original "manifesto" and ensuing mailing list discussion here:
 +
http://thread.gmane.org/gmane.comp.lang.haskell.diagrams/383
  
See also later IRC discussion beginning here: http://ircbrowse.net/browse/diagrams?events_page=935
+
See also later IRC discussion beginning here:
 +
http://ircbrowse.net/browse/diagrams?events_page=935
  
 
== Detailed design ==
 
== Detailed design ==
  
Most of the changes should be in the <code>diagrams-core</code> package, though a few things in <code>diagrams-lib</code> may need to change as well.
+
Most of the changes should be in the <code>diagrams-core</code>
 +
package, though a few things in <code>diagrams-lib</code> may need to
 +
change as well.
  
 
=== diagrams-core ===
 
=== diagrams-core ===
  
No changes should be necessary to the following modules (all prefixed by <code>Diagrams.Core</code>): <code>Envelope</code>, <code>HasOrigin</code>, <code>Juxtapose</code>, <code>Names</code>, <code>Points</code>, <code>Query</code>, <code>Trace</code>, <code>Transform</code>, <code>V</code>.
+
No changes should be necessary to the following modules (all prefixed
 +
by <code>Diagrams.Core</code>): <code>Envelope</code>,
 +
<code>HasOrigin</code>, <code>Juxtapose</code>, <code>Names</code>,
 +
<code>Points</code>, <code>Query</code>, <code>Trace</code>,
 +
<code>Transform</code>, <code>V</code>.
  
 
I'm not sure about <code>Style</code> yet.
 
I'm not sure about <code>Style</code> yet.
Line 20: Line 31:
  
 
* Change the name of <code>UpAnnots</code> to <code>Summary</code>.
 
* Change the name of <code>UpAnnots</code> to <code>Summary</code>.
* Change the name of <code>DownAnnots</code> to <code>Context</code>, and change its definition to
+
* Change the name of <code>DownAnnots</code> to <code>Context</code>,
 +
* and change its definition to
  
   type Context b v m = Style v
+
   type Context b v m = Style v ::: Name ::: SubMap b v m ::: ()
                    ::: Name
+
                    ::: SubMap b v m
+
                    ::: ()
+
  
The addition of <code>SubMap</code> is so that we can use the positions of laid-out subdiagrams to compute the positions of others.
+
The addition of <code>SubMap</code> is so that we can use the
 +
positions of laid-out subdiagrams to compute the positions of others.
  
* <code>transfToAnnot</code> and <code>transfFromAnnot</code> can be deleted.
+
* <code>transfToAnnot</code> and <code>transfFromAnnot</code> can be
* <code>QDiaLeaf</code> and <code>withQDiaLeaf</code> can be deleted.
+
* deleted.  <code>QDiaLeaf</code> and <code>withQDiaLeaf</code> can be
 +
* deleted.
  
 
* Create new definitions
 
* Create new definitions
Line 38: Line 49:
 
   type Contextual b v q a = ContextualT b v q Identity a
 
   type Contextual b v q a = ContextualT b v q Identity a
  
One could imagine making <code>ContextualT</code> a <code>newtype</code> but that would necessitate writing lots of instances for things like <code>MonadState</code>, <code>MonadReader</code>, and so on.
+
One could imagine making <code>ContextualT</code> a
 +
<code>newtype</code> but that would necessitate writing lots of
 +
instances for things like <code>MonadState</code>,
 +
<code>MonadReader</code>, and so on.
  
* The definition of <code>QDiagram</code> should be changed to something like
+
* The definition of <code>QDiagram</code> should be changed to
 +
  something like
  
   type QDiagram b v m = Contextual b v m (RTree b v Annotation, Summary b v m)
+
   type QDiagram b v m = Contextual b v m (RTree b v Annotation,
 +
  Summary b v m)
  
It's important that this is NOT a newtype, so we can freely use the <code>Monad</code> instance for <code>Contextual</code> when working with diagrams.  This also means we don't need <code>Wrapped</code> or <code>Rewrapped</code> instances for it anymore.
+
It's important that this is NOT a newtype, so we can freely use the
 +
<code>Monad</code> instance for <code>Contextual</code> when working
 +
with diagrams.  This also means we don't need <code>Wrapped</code> or
 +
<code>Rewrapped</code> instances for it anymore.
  
* The implementation of <code>applyAnnotation</code> needs to change. All it needs to do is create a new <code>RTree</code> node (an <code>RAnnot</code> node), ignoring the context and having no effect on the summary.  So something like
+
* The implementation of <code>applyAnnotation</code> needs to change.
 +
  All it needs to do is create a new <code>RTree</code> node (an
 +
  <code>RAnnot</code> node), ignoring the context and having no effect
 +
  on the summary.  So something like
  
 
   applyAnnotation an = fmap (first (Node (RAnnot an) . (:[])))
 
   applyAnnotation an = fmap (first (Node (RAnnot an) . (:[])))
  
We may end up having to do similar things in other situations so it may make sense to factor out parts of this into general utilities (e.g. <code>addRoot :: RNode -> RTree -> RTree</code> etc.)
+
We may end up having to do similar things in other situations so it
 +
may make sense to factor out parts of this into general utilities
 +
(e.g. <code>addRoot :: RNode -> RTree -> RTree</code> etc.)
  
* Of course the implementation of almost all the rest of the functions in this module will need to change as well.  I'll walk through a few particular examples and then discuss more general principles. First, <code>pointDiagram</code>.  The current code is
+
* Of course the implementation of almost all the rest of the functions
 +
  in this module will need to change as well.  I'll walk through a few
 +
  particular examples and then discuss more general principles.
 +
  First, <code>pointDiagram</code>.  The current code is
  
   pointDiagram :: (Fractional (Scalar v), InnerSpace v)
+
   pointDiagram :: (Fractional (Scalar v), InnerSpace v) => Point v ->
              => Point v -> QDiagram b v m
+
              QDiagram b v m pointDiagram p = QD $ D.leafU (inj
  pointDiagram p = QD $ D.leafU (inj . toDeletable $ pointEnvelope p)
+
              . toDeletable $ pointEnvelope p)
  
This creates a point envelope, wraps it in <code>Deletable</code>, injects it into an <code>UpAnnots</code> value, and uses it to create a leaf <code>DUALTree</code>.  Everything up through <code>UpAnnots</code> still applies (though the name of <code>UpAnnots</code> has changed).  What's different is that we aren't creating an explicit tree with summary values at leaves; we simply return the summary value as part of the result of the diagram function.  So we can create a function <code>leafS</code> in parallel with <code>leafU</code>:
+
This creates a point envelope, wraps it in <code>Deletable</code>,
 +
injects it into an <code>UpAnnots</code> value, and uses it to create
 +
a leaf <code>DUALTree</code>.  Everything up through
 +
<code>UpAnnots</code> still applies (though the name of
 +
<code>UpAnnots</code> has changed).  What's different is that we
 +
aren't creating an explicit tree with summary values at leaves; we
 +
simply return the summary value as part of the result of the diagram
 +
function.  So we can create a function <code>leafS</code> in parallel
 +
with <code>leafU</code>:
  
 
   emptyTree = Node REmpty []
 
   emptyTree = Node REmpty []
  
   leafS :: Summary b v m -> QDiagram b v m
+
   leafS :: Summary b v m -> QDiagram b v m leafS s = return
  leafS s = return (emptyTree, s)
+
  (emptyTree, s)
  
Then the implementation of <code>pointDiagram</code> only needs to change to
+
Then the implementation of <code>pointDiagram</code> only needs to
 +
change to
  
 
   pointDiagram p = leafS (inj . toDeletable $ pointEnvelope p)
 
   pointDiagram p = leafS (inj . toDeletable $ pointEnvelope p)
  
* The current type of <code>getU'</code> can't work anymore, since we can't escape the <code>Contextual</code> monad.  But we can have
+
* The current type of <code>getU'</code> can't work anymore, since we
 +
  can't escape the <code>Contextual</code> monad.  But we can have
  
   getU' :: (Monoid u', u :>: u') => QDiagram b v m -> Contextual b v m u'
+
   getU' :: (Monoid u', u :>: u') => QDiagram b v m -> Contextual b v m
   getU' = fmap (option mempty id . get . snd)
+
   u' getU' = fmap (option mempty id . get . snd)
  
* <code>setEnvelope</code>
+
* <code>setEnvelope</code>: the main issue here is to figure out
 +
  suitable replacements for <code>applyUPre</code> and
 +
  <code>applyUPost</code>.  We could do
  
* <code>envelope</code>
+
  applySPre :: Summary b v m -> QDiagram b v m -> QDiagram b v m
 +
  applySPre s = (fmap . second) (s<>)
 +
 
 +
But note we can also give this a much more general type signature like
 +
 
 +
  applyUPre :: (Functor f, Semigroup s) => s -> f (t,s) -> f (t,s)
 +
 
 +
Not sure which is better.
 +
 
 +
In any case, we don't need any of the <code>over _Wrapped</code> stuff
 +
any more.
 +
 
 +
* <code>envelope</code> is problematic.  We had
 +
 
 +
  envelope :: forall b v m. (OrderedField (Scalar v), InnerSpace v ,
 +
                            HasLinearMap v, Monoid' m) => Lens'
 +
                            (QDiagram b v m) (Envelope v)
 +
 
 +
But this type won't work any more, because e.g. we can't simply
 +
extract an <code>Envelope</code> from a <code>QDiagram</code>.  I
 +
suppose we could do
 +
 
 +
  ... Lens' (QDiagram b v m) (Contextual b v m (Envelope v))
 +
 
 +
?
  
 
* <code>trace</code> and <code>setTrace</code> are similar.
 
* <code>trace</code> and <code>setTrace</code> are similar.
  
* Name stuff: think about monad, etc. <code>subMap</code>, <code>names</code>, <code>nameSub</code>, <code>lookupName</code>, <code>localize</code>
+
* Name stuff: think about monad, etc. <code>subMap</code>,
 +
  <code>names</code>, <code>nameSub</code>, <code>lookupName</code>,
 +
  <code>localize</code>
  
* <code>withName</code>, <code>withNameAll</code>, <code>withNames</code>: should be able to simplify these to take advantage of monad.  Don't need to have them in CPS anymore.
+
* <code>withName</code>, <code>withNameAll</code>,
 +
  <code>withNames</code>: should be able to simplify these to take
 +
  advantage of monad.  Don't need to have them in CPS anymore.
  
 
* <code>query</code>, <code>sample</code>, <code>value</code>
 
* <code>query</code>, <code>sample</code>, <code>value</code>

Revision as of 03:14, 25 May 2014

This page describes the motivation and design for a refactoring of diagrams, to give them a semantics based on computing fixed points of functions from "context" information to raw tree of primitives together with some summary information.

Contents

1 Reference

See the original "manifesto" and ensuing mailing list discussion here: http://thread.gmane.org/gmane.comp.lang.haskell.diagrams/383

See also later IRC discussion beginning here: http://ircbrowse.net/browse/diagrams?events_page=935

2 Detailed design

Most of the changes should be in the diagrams-core package, though a few things in diagrams-lib may need to change as well.

2.1 diagrams-core

No changes should be necessary to the following modules (all prefixed by Diagrams.Core): Envelope, HasOrigin, Juxtapose, Names, Points, Query, Trace, Transform, V.

I'm not sure about Style yet.

2.1.1 Diagrams.Core.Types

  • Change the name of UpAnnots to Summary.
  • Change the name of DownAnnots to Context,
  • and change its definition to
 type Context b v m = Style v ::: Name ::: SubMap b v m ::: ()

The addition of SubMap is so that we can use the positions of laid-out subdiagrams to compute the positions of others.

  • transfToAnnot and transfFromAnnot can be
  • deleted. QDiaLeaf and withQDiaLeaf can be
  • deleted.
  • Create new definitions
 type ContextualT b v q m a = ReaderT (Context b v q) m a
 type Contextual b v q a = ContextualT b v q Identity a

One could imagine making ContextualT a newtype but that would necessitate writing lots of instances for things like MonadState, MonadReader, and so on.

  • The definition of QDiagram should be changed to
 something like
 type QDiagram b v m = Contextual b v m (RTree b v Annotation,
 Summary b v m)

It's important that this is NOT a newtype, so we can freely use the Monad instance for Contextual when working with diagrams. This also means we don't need Wrapped or Rewrapped instances for it anymore.

  • The implementation of applyAnnotation needs to change.
 All it needs to do is create a new RTree node (an
 RAnnot node), ignoring the context and having no effect
 on the summary.  So something like
 applyAnnotation an = fmap (first (Node (RAnnot an) . (:[])))

We may end up having to do similar things in other situations so it may make sense to factor out parts of this into general utilities (e.g. addRoot :: RNode -> RTree -> RTree etc.)

  • Of course the implementation of almost all the rest of the functions
 in this module will need to change as well.  I'll walk through a few
 particular examples and then discuss more general principles.
 First, pointDiagram.  The current code is
 pointDiagram :: (Fractional (Scalar v), InnerSpace v) => Point v ->
              QDiagram b v m pointDiagram p = QD $ D.leafU (inj
              . toDeletable $ pointEnvelope p)

This creates a point envelope, wraps it in Deletable, injects it into an UpAnnots value, and uses it to create a leaf DUALTree. Everything up through UpAnnots still applies (though the name of UpAnnots has changed). What's different is that we aren't creating an explicit tree with summary values at leaves; we simply return the summary value as part of the result of the diagram function. So we can create a function leafS in parallel with leafU:

 emptyTree = Node REmpty []
 leafS :: Summary b v m -> QDiagram b v m leafS s = return
 (emptyTree, s)

Then the implementation of pointDiagram only needs to change to

 pointDiagram p = leafS (inj . toDeletable $ pointEnvelope p)
  • The current type of getU' can't work anymore, since we
 can't escape the Contextual monad.  But we can have
 getU' :: (Monoid u', u :>: u') => QDiagram b v m -> Contextual b v m
 u' getU' = fmap (option mempty id . get . snd)
  • setEnvelope: the main issue here is to figure out
 suitable replacements for applyUPre and
 applyUPost.  We could do
 applySPre :: Summary b v m -> QDiagram b v m -> QDiagram b v m
 applySPre s = (fmap . second) (s<>)

But note we can also give this a much more general type signature like

 applyUPre :: (Functor f, Semigroup s) => s -> f (t,s) -> f (t,s)

Not sure which is better.

In any case, we don't need any of the over _Wrapped stuff any more.

  • envelope is problematic. We had
 envelope :: forall b v m. (OrderedField (Scalar v), InnerSpace v ,
                           HasLinearMap v, Monoid' m) => Lens'
                           (QDiagram b v m) (Envelope v)

But this type won't work any more, because e.g. we can't simply extract an Envelope from a QDiagram. I suppose we could do

 ... Lens' (QDiagram b v m) (Contextual b v m (Envelope v))

?

  • trace and setTrace are similar.
  • Name stuff: think about monad, etc. subMap,
 names, nameSub, lookupName,
 localize
  • withName, withNameAll,
 withNames: should be able to simplify these to take
 advantage of monad.  Don't need to have them in CPS anymore.
  • query, sample, value

2.1.2 Diagrams.Core.Compile

2.2 diagrams-lib