Introducing a deep embedding

[jbracker]

Hello,

I am currently trying to generalize diagrams so that a deep embedding is possible. The overall goal is to use diagrams as a JavaScript compiler [1] and translate every computation of a diagram into JavaScript to enable Animations and Rendering using the Canvas element within the Browser further down the road.

I have already generalized all types and am currently working on porting diagrams to generalized booleans [2,3]. When working on Diagrams.TwoD.Segment [4] I hit a problem
on line 112 to 128.

The first problem that arises is that the compiler wants 'BooleanOf (PosInf a)' and 'Bool' to be equal, because 'filter' needs a predicate that computes a 'Bool' which is not deeply embedded anymore. Besides that the 'BooleanOf [a]' has to be 'Bool' when it comes to the usage of the 'IfB' class for lists [6, line 184]. But that is not possible, because the generalised booleans we are working with can be arbitrarily long JavaScript expressions and we can not evaluate those within the Haskell environment (They are evaluated on client side). I tried to implement a generalized 'filter' function (filterB) [5], but that does not work, because you still need to know if the boolean returned by the predicate represents a true or a false in order to construct the resulting Haskell list. The only way I can think of to handle this problem in a good way is generalizing lists so they can also be evaluated on the JavaScript level.

Another way to solve this problem is by not changing the length of the list. In that case one can move the embedded pending JavaScript computation into the elements of the list like it is done for tuples [6, line 188]. My first attempt to do this was by mapping the list returned by '(cubForm a b c d)' to a list of tuples containing the their boolean condition '(liftA2 (&&*) (>=* 0) (<=* 1))' and the processed value '(fst . unp2 . fAtParam bez')'. Besides the fact that this is very hard to read and also is unintuitive to write for library developers (especially having to keep in mind the deep embedding), there is another major problem following this.

When it comes to line 126 to 128 there is a pattern match that tests if the list is empty. This pattern match again forces us to evaluate the boolean expressions or the generalized list in order to decide what Haskell value to return, which is not possible on the Haskell level.

Even with generalized lists where the test for a empty list could be moved to the JavaScript level there would remain the problem that we do not know which Haskell value to return. The only solution for this problem that I see is moving away from the currently used data type PosInf [7] and instead using a data type that encapsulates the generated JavaScript computation. Pattern matching on that type would not be possible anymore, since that would again break the embedding. One would have to access the values of that type with functions that generate deep embedded JavaScript that can be passed on further. I can not think of another solution for this problem and the solution is very inconvenient as it involves changing a great amount of code outside of Diagrams.TwoD and providing deep embedding of a custom data type and lists in JavaScript, which would raise the effort of writing a backend, as generalizing lists or that data type is not a straight forward task with a right or wrong solution.

Just for clarity the function 'minimumB' is not in the official release of Data.Boolean. I added it to my fork [5], because it was convenient. The problems discussed above does not appear for the functions provided there, because they do not return lists or custom data types. They just mingle the list into one big embedded JavaScript computation that is passed on using the embedding type as a return value instead of using pure Haskell types.

I hope someone has a good idea for this problem, because right now it seems to be a deal breaker.

[1] https://github.com/ku-fpg/sunroof
[2] http://hackage.haskell.org/package/Boolean-0.1.2
[3] https://github.com/jbracker/diagrams-lib/tree/boolean-generalisation/src/Diagrams/TwoD
[4] https://github.com/jbracker/diagrams-lib/blob/boolean-generalisation/src/Diagrams/TwoD/Segment.hs
[5] https://github.com/jbracker/Boolean/blob/master/src/Data/Boolean/List.hs
[6] https://github.com/jbracker/Boolean/blob/master/src/Data/Boolean.hs
[7] http://hackage.haskell.org/packages/archive/monoid-extras/latest/doc/html/Data-Monoid-PosInf.html

[Brent Yorgey]

One random thought -- this may be off base since I still don't
completely understand all the technical issues -- but why not carry
around a JSBool *paired with* a normal Bool? i.e. BooleanOf Canvas =
(JSBool, Bool) or something like that. Then when you need access to
an actual Haskell-level value to do filter or whatever, you can
project out the second component, and for doing the embedding you
project out the first component.

-Brent

> --
>
>

[Jan Bracker]

That would also not work. Think about when you are accessing
information that only exists during Runtime of the JavaScript, e.g.
some computation that finds out if the Screen has a certain size or if
the current Browser is Firefox. In that case you can write Sunroof
code that generates JavaScript that will deliver those values when
evaluated, but you do not know what those values evaluate to until
they are evaluated. Even if you could evaluate them in Haskell they
would still depend on the Browser.

The example might seem a bit to general just looking at Diagrams, but
this is exactly the problem that comes up here. Depending on what the
generated JavaScript evaluates to we want to return a certain Haskell
value. And even under the premise that there is no browser or context
dependent computation in the generated JavaScript, one would still
need to evaluate it to know the outcome.

Your approach would only work if all computation done in JavaScript
can also be done in Haskell, but this is not the case any more as soon
as you access the context the JavaScript is running in as we only know
that context when it is running.

I hope the problem and my thoughts about it become a little bit clearer.

By the way: I found another location where the same problem occurs:
Diagrams.TwoD.Arc.bezierFromSweep

2013/1/5 Brent Yorgey <byo...@seas.upenn.edu>:

> --
>
>

[Jan Bracker]

I have thought about this problem a lot and the only 'good' solution
that comes to my mind is to really deeply embed lists and the 'PosInf'
data structure. Up to now I could not find any other places where
custom data structures cause conflicts for the deep embedding.

I have looked at where 'PosInf' is actually used to find out how much
work it would cause to generalize it.
'diagrams-lib' only uses 'PosInf' in the file
'Diagrams/TwoD/Segment.hs'. So the work here is decently small.
'diagrams-core' only uses 'PosInf' in the file
'Diagrams/Core/Trace.hs'. So the work here is also decently small.
The packages 'diagrams-contrib', 'diagrams-cairo', 'diagrams-canvas'
and 'diagrams-svg' don't use 'PosInf' at all.
So there isn't really much work to do to chang from PosInf to a deep
embedded version of it.

I would approach a deep embedding of 'PosInf' like this:

{-# LANGUAGE FlexibleContexts #-}

import Data.Monoid.PosInf
import Data.Boolean
import Data.Deep.Error

class PosInfD p where
finiteD :: a -> p a
posInfinityD :: p a
deconsPosInfD :: (a -> b) -> b -> p a -> b

instance PosInfD PosInf where
finiteD = Finite
posInfinityD = PosInfty
deconsPosInfD f _ (Finite x) = f x
deconsPosInfD _ e PosInfty = e

isFiniteD :: ( PosInfD posinf
, Boolean (BooleanOf (posinf a))
) => posinf a -> BooleanOf (posinf a)
isFiniteD = deconsPosInfD (const true) false

isPosInftyD :: ( PosInfD posinf
, Boolean (BooleanOf (posinf a))
) => posinf a -> BooleanOf (posinf a)
isPosInftyD = notB . isFiniteD

getFiniteD :: (ErrorD a, PosInfD posinf) => posinf a -> a
getFiniteD = deconsPosInfD id (errorD "getFiniteD: Not finite")

My approach to embedded lists can be found in [1]. I think the
implementation is straight forward. All important list functions can
be implemented based on the 'ListD' class. So the deep embedding
should be convenient to use for other developers. One thing to note is
the 'ErrorD' class which provides a custom way of throwing an error.
This is needed, because compilers like Sunroof will evaluate the
complete deep embedded code and a normal call to 'error' will raise an
exception during the compilation process. With the custom 'ErrorD'
class the error that might occur during the runtime of the deep
embedded code can occur there without interfering with the compilation
process.

I think I still need to add a type function like 'BooleanOf' for the
embedded lists and 'PosInf' ('ListOf' amd 'PosInfOf'), because
otherwise the ambiguity that 'BooleanOf' solves might also occur in
code using these structures. I will look into that a little bit more.

I will try my approach this Weekend some time.

[1] https://github.com/jbracker/deep-embedded-data/blob/master/src/Data/Deep/List.hs

2013/1/8 Jan Bracker <jan.b...@googlemail.com>:

[Brent Yorgey]

My objection to this is a big one, and concerns the future of
diagrams. You say you have not found any other places where custom
data structures will cause problems for the deep embedding, and the
work to convert them is quite small, and I believe you. But that is
only the *current* state of things. It seems that switching to this
system to allow deep embedding may seriously hamstring future
development, for two reasons:

(1) one never knows when one might run into another situation where
a new data structure needs to be deeply embedded, leading to yet
more work to convert it (or contortions to avoid it).

(2) it will make it *even harder* for new contributors to get
involved (and it is already not very easy), since e.g. they
cannot even use normal lists but must work in terms of some
deeply embedded version.

I am really not sure what to do. I really want to see this succeed,
and I certainly don't want to see all your great work go to waste.
But the above points would make me really hesitant to merge it at this
point. If you think I've misunderstood something, or if anyone has a
counterpoint to either of the above two points, I'd love to hear it.

I wonder about the feasibility of maintaining a separate fork of
diagrams with the embedded features. Of course the work to maintain
the connection between the two might end up being a nightmare. But
the idea is to shift the burden onto the maintainers of the embeddable
version (me, you, others who want to help) instead of on all the
other people who wish to contribute to diagrams development.

-Brent

> --
>
>

[Andy Gill]

Thanks for calling this Brent. We will regroup and figure out the options here.
There may be another abstraction we can use, for example, or perhaps we
could use HERMIT to handle the shallow -> deep translation.

Andy

> --
>
>
>
>

[Brent Yorgey]

Hi Jan and Andy,

Just the other day it occurred to me---I had forgotten the forest for
the trees. The original goal of
https://github.com/diagrams/diagrams-lib/pull/65 was to generalize the
R2 type to make it parameterized. As far as I know Jan did in fact
accomplish that. All this stuff about generalizing booleans and lists
and PosInf, etc., which I objected to, was necessary for doing a deep
embedding but not for generalizing R2 in and of itself---which might
have other, independent benefits. If there is a way we can separate
out the changes for generalizing R2 from the changes which went beyond
that, I would be very interested to look at the feasibility of merging
the former. That would also provide a good base from which to
continue experimenting with ways to make a deep embedding work.

-Brent

[Brent Yorgey]

Oh, now that I'm looking at it more carefully, perhaps that's what
https://github.com/diagrams/diagrams-lib/pull/65 already is? I.e. it
doesn't contain any of the commits generalizing Bool and lists and so
on?

-Brent

> --
> You received this message because you are subscribed to the Google Groups "diagrams-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to diagrams-discu...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Brent Yorgey]

Ah, but I see it doesn't include the changes we made while hacking at
KU which eliminated the need for a ~ Scalar a constraints and so on.
So I suppose there would be some work to do disentangling that from
the other changes.

Sorry for the rapid stream-of-consciousness emails. =)

-Brent

[Jan Bracker]

I just cherry picked those changes into the 'master' branch (they were
in the 'boolean-generalisation'). They should now all be available. I
also tagged this state with 'types-generalized', just for future
reference. They should all be in the pull request.

2013/2/13 Brent Yorgey <byo...@seas.upenn.edu>:

[Brent Yorgey]

Awesome, thanks. I will take a look soon.

-Brent