Construct monad in `sicp-pict`?

In the current sicp-pict, we treat a picture as a painter, which is a procedure that takes a frame and then draws the picture to a bitmap (so we don't care about its return value, any type is ok).

I tried to define a procedure called apply-painter, which takes a painter and a frame and returns a bitmap:

(define (apply-painter painter frame #:width [width 200] #:height [height 200])
  (define-values (bm dc) (make-painter-bitmap width height))
  (begin0 bm
    (parameterize ([current-bm bm]
                   [current-dc dc])
      ;; TODO Apply frame's transformation to bitmap.
      (send dc scale 0.99 0.99) ; make the entire unit square visible
      (painter frame))))

(define unit-frame (frame (vect 0. 0.) (vect 1. 0.) (vect 0. 1.)))
(define (paint painter #:width [width 200] #:height [height 200])
  (make-object image-snip%
               (apply-painter painter  unit-frame
                              #:width  width
                              #:height height)))

With apply-painter, we can treat a painter as a procedure that takes a frame and returns a bitmap.
If we regard the type of painter as follow:

(define-type (Bitmap A) ((Instance Bitmap%)))
(define-type Painter (-> Frame (Bitmap Frame)))

Things seem to get interesting:
We can define a transformation f between Frames (marked F),
and define a transformation b between (Instance Bitmap%)s (marked B),
what if we then define a procedure fmap that maps f to b?

        p
    F -----> B(F) = B
    |        |
    | fmap   |
  f | -----> | b = fmap(f)
    |        |
    |        |
    ∨        ∨
    F -----> B(F) = B
        p


        p
    F -----> B(F) = B
    |        |
    | fmap   |
  p | -----> | fmap(p)
    |        |
    |        |
    ∨        ∨
    B -----> B(B) = B
      fmap(p)

I'm not familiar with purely functional languages, but I guess we defined a functor this way?
Then we may be able to construct monad:

(define-type (Bitmap A) (Instance Bitmap%))
(define-type Painter (-> Frame (Bitmap Frame)))

(: fmap (case->
         [-> (-> Frame Frame)
             (-> (Bitmap Frame) (Bitmap Frame))]
         [-> (-> Frame (Bitmap Frame))
             (-> (Bitmap Frame) (Bitmap (Bitmap Frame)))]))
(define fmap #;TODO)

(: return Painter)
(define return (compose))

(: join (-> (Bitmap (Bitmap Frame)) (Bitmap Frame)))
(define join identity)

(: compose (-> Painter * Painter))
(define compose superpose)

(: bind (-> (Bitmap Frame) Painter (Bitmap Frame)))
(define bind (λ (bm p) (join ((fmap p) bm))))

2 Likes

That's an interesting question, which in my head relates rather specifically to Haskell, as other (purely) functional languages do not elevate monads to so high an esteem.

Technically speaking, you need more than a functor to construct a monad. In Haskell, the Monad type class derives from the Applicative type class. The page Applicative functor - HaskellWiki summarizes quite nicely the relationship between Functor, Applicative, and Monad. On the immediate technical side, being able to define certain functions (e.g. bind) is not sufficient for your type to qualify for a monad; you also have to ensure that some additional identities hold (which I didn't verify for your example).


On the paradigm level, I currently have the impression that monads are particularly useful and respected in Haskell because the type system of the language is intentionally very rigid. As one consequence, mixing a debug println into your code is quite non-trivial because of the side-effects, and in particular taints the type of the whole function with the IO monad. Now monads have the cool advantage of being very explicit, and the rigid type system in Haskell ensures that you must use a monad if you want any side-effect, which allows you to reason quite a long way about the code without actually running it (unless you put everything in IO, which many people actually do, sometimes for the valid reason of reducing code complexity). Hovewer, I have the impression that it's not necessarily or generally a Rackety way of seeing or doing things. In Racket, if I want to do a displayln in my function, I just do it, and it doesn't need to influence the return type. That gives me weaker guarantees about my code, but is less intrusive in many subtle ways. This is, by the way, one of the main reasons why I dropped Haskell for Racket, and why I don't regret the move.

I hope people with more experience with Racket will chime in and give their opinion on the matter.


By the way, I am quite interested in Qi: A Functional, Flow-Oriented DSL which allows threading data through computation in ways which I find highly superior to monads. Qi looks a little bit like Arrows: A General Interface to Computation , but without the rigid type system burden. To me, one ultimate thing to do is to build Typed Qi, which should be possible, but probably highly non-trivial. Still, I find that Qi is a more Rackety way to thread computation than monads.

3 Likes

Hi @scolobb, thanks a lot for recommend me qi! qi is really excellent! I've read its document and lots of ideas come to me! I'd like to share them. :slight_smile:


Start with the thoughts I experienced when I tried construct monad in sicp-pict:

At first I noticed that a painter is essentially a side effect of drawing on a bitmap, and I wondered if I could convert it to a function that returns a bitmap. Inspired by Cartesian closed category, I realized that I needed an apply function. With this apply, I could regard painter as a mapping from frame to bitmap, which is composable (by superpose) and there is an identity element of superpose -- blank (draw nothing)! Which means it's monoid! It drives me to construct monad.

Based on it, I defined fmap, etc. and to my surprise, I thought I knew their semantics (even if I didn't prove that it's monad, I just tried to write them).

  • fmap:
    Map the transformation between frames to the transformation between bitmaps,
    or map the procedure of drawing on a frame to the procedure of drawing directly on a bitmap.
  • compose: superpose pictures together.
  • return: blank picture.
  • join: the picture drawn on a bitmap is also a bitmap.
  • bind: like apply-painter treats painter as a mapping from frame to bitmap, bind treats painter as a mapping from bitmap to bitmap.

Proving "painter is monad" seems not to be so important -- we've defined these useful operator based on the idea.

Thinking back, in the original design of sicp-pict, we regard picture as a process of drawing something with a frame. By this way, we only need to transform the frame to get the corresponding bitmap (similar to regard vector as the linear combination of bases in linear algebra).

We transform bitmap by transforming frame, but don't forget that we can transform bitmap directly! There must be some kind of connection between frame transformation and bitmap transformation! On the other hand, we can regard painter as a function that paints picture on a frame to get a bitmap. Can we let the painter paint directly on a bitmap? Wow, that's the bind I defined at the beginning!


Here are some thoughts I got while studying category theory:

Can we move the abstraction and combinations in category theory to programming languages? If we can, to what category corresponding?

My answer to the 2nd question is that each type constructor (such as Boxof) corresponds to a category, whose object is the Values ​​composed of the Box type, and morphism is the mapping between these Values.

We can construct 2 special type constructors, one of them is identity type constructor:

(define-type (Id A) A)

With Id, we can regard any type A as (Id A), which is an object in Id category! And the type of any function not only can be regarded as a morphism between Values in Id, but also an endofunctor from Id to Id!

Another one is constant constructor (bitmap as an example):

(define-type (Bitmap) Frame)
(define-type (Bitmap A) (Instance Bitmap%))

And if we regard any constant b with type B as a function of type (-> (Values 1) (Values B)) (marked (-> 1 B)), which is an endofunctor in Id, then original morphism in Id (like f : (-> B C)) become a natural transformation (-> (-> 1 B) (-> 1 C)).

So that any value of Frame can be regard as an endofunctor I = T^0 (mean no picture),
of (Instance Bitmap%) can be regard as T(I) = T^1 (mean paint something in a frame T^0),
and T(T(I)) = T^2 (mean paint something in a bitmap T^1), etc.

Then we can define η : I → T as blank (a painter that paint nothing on frame), μ : T × T → T as identity (a bitmap painted something is also a bitmap), and they satisfy these laws:

μ ∘ Tμ = μ ∘ μT
μ ∘ Tη = μ ∘ ηT = 1

I'm not sure how category is used in purely functional language like Haskell, but I believe the essence of category theory is compose. qi provides a very elegant and intuitive way to compose! I'd like to build typed qi too, but I suspect it's not that easy. In fact, I tried something and found that the existing type system has many restrictions on composition, see TR issues: 1172, 1175, 1176, 1218.

I think that the implementation of qi is based on the assumption that functions are mappings between Values, but unfortunately TR's type system (and contract system) doesn't see it that way. TR has done a lot to the argument types in -> rather than to Values, thus it restricts the return types.

I plan to study how contract system works and try to define contract for values, and then based on it to improve Values in TR, so that we can construct something like (Values (Values Symbol String) *), which can be used as argument type or return type. And I guess Values can also guide how to extend the Read and Write type in the future.

3 Likes

Oh man, there's a lot here -- this is going to be a long, multi-part response. This will cover (1) Arrows, (2) Monads in Haskell vs Qi, (3) Typed Qi.

@NoahStoryM I'm loving the thought process that went into your characterization above, thank you for sharing and for taking such care to draw diagrams.

First off, I'd love to learn more about Haskell but it is dense and I haven't had the opportunity to use it for anything before. This thread has inspired me to resume my learning of it :slight_smile:

I looked into Arrows and found this great description in the Typeclassopedia to supplement the link you sent @scolobb . I'm frankly a bit mindblown by the correspondence between Qi and Arrows here -- to me there doesn't seem to be any special reason why they ought to correspond so exactly, and yet:

  • The arr method corresponds to Qi's "base case" of treating any function as a flow.
  • (>>>) is equivalent to ~>
  • first, second, and their composite (***) is the relay -- i.e. (== a _), (== _ b), and (== a b), respectively.
  • (&&&) referred to as "fanout composition" is exactly the tee junction, (-< f g)

I suppose the reason for this close correspondence might be that, in designing these combinators, I couldn't think of any other ways to compose functions, and perhaps these really are all of the foundational (in whatever sense) ones. I did at one time also consider a "diamond" composition, <>, since it was the only shape missing in ~> -< >< ==, but I forget now what it did (or maybe I couldn't think of what it ought to do!). It probably was reducible to one of these other combinators and was not truly distinct (for that matter, while >< is reducible to == when the number of values is known, this is often not the case since the number varies at runtime -- so >< may be a distinct primitive that isn't possible in statically typed languages).

Thank you for making this connection - it is valuable! This will surely provide some clarity on the theoretical underpinnings, scope, and limitations of Qi (some of which we will return to on the subject of monads, below).

For some time now I've had the vague suspicion that some language features that are arcane in other languages could be simple in Qi (and vice versa). Arrows is clearly one of these, and I've also felt that monads would be, too, where for instance, Qi's treatment of Maybe in terms of presence or absence of values rather than annotations like Just and reified absence values like Nothing, seems to me to be more elegant (and, incidentally, this approach was inspired by buddhist sunyata logic -- what could be called "logical zero"). I suspect, but don't know for sure as my category theory is rudimentary, that this approach can generalize in a natural way to at least some other monads -- for instance, just as Maybe is presence or absence of a value, the State monad could be represented as the presence and persistence of additional values (fulfilling, of course, the necessary formal properties). IO may be the spontaneous addition of new values (functions with outputs but no inputs) in some form, and grounded side effects (functions with inputs but no outputs) that produce no values. The unifying theme here being the creation, existence or absence (and consequently also the number), and the termination of values. Of course, the monad laws would need to be proved in each case, and it would be interesting to see whether in fact every monad could be expressed in this way. If indeed Qi is Arrows, then this SO post seems to suggest that the answer is in the negative here. On the other hand, I found the original paper on Arrows, which concludes, "We have seen that any monadic library can be given an arrow interface instead (via Kleisli arrows), and so the arrow interface is strictly more general." In any case, as Qi also has a lot of features that don't necessarily reduce to the combinators discussed above, perhaps it is not "only" Arrows, and this would in that case be a theoretical lower bound on expressiveness.

To digress further on this subject, another language feature that is potentially "natural" in Qi is delimited continuations. I think in Qi they manifest simply as a "potential difference" between two points in a flow (like the concept in physics for electromagnetic fields), which is itself expressible as a flow, i.e. a function. It may be that Qi would be a good language for studying continuations as this manifestation is very natural and easy to think about -- maybe even affording a mathematical formulation that maps directly to Qi code. Just a vague idea at this stage!

Finally, returning to Typed Qi, that would indeed be an interesting project, and one that I incidentally created an issue for when you first mentioned it a little while back :slight_smile: . I recently came across this project called Turnstile that may be relevant :person_shrugging:

3 Likes