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.

4 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

Hi @NoahStoryM and sorry for the delay with the answer. The times are busy for me right now, so I waited until I could invest serious thinking into this. I will comment on some of the points you are making, under the disclaimer that I am not a specialist in programming language theory, lambda calculus, category theory, or types. By the way, I am really enjoying this discussion :slight_smile:


I checked out Cartesian closed category - Wikipedia to refresh my memory, and incidentally it says:

These categories are particularly important in mathematical logic and the theory of programming, in that their internal language is the simply typed lambda calculus.

which is probably why you brought up the term in the discussion in the first place.

OK, I get your point and agree with it.

This makes me think of Hask - HaskellWiki, " the category of Haskell types and functions."

I don't know if I follow everything correctly, but I will assume that the objects in this category are the types (Boxof a) and that the morphisms are the functions with the types (-> (Boxof a) (Boxof b)).

I am more used to putting the whole of a language with all its types into a category and reasoning inside, but I guess you are right: a type constructor may be seen as inducing a subcategory of that big category, provided that you ensure the morphisms are properly conserved.

I don't think I follow. A functor between categories A and B is a pair of mappings, one between the objects of A and the objects B, and the other between the morphisms of A and B. In your case, A = B = Id. Consider a function f : a → b. What such pair of mappings between Id and Id does it induce?

I'm not sure what you mean. Morphism composability (associativity and identity element) is indeed part of the very definition of a category, but to me it is the higher-level concepts arising from those basic definitions which are more interesting.

Yeah, I agree. With community help, I threw together a couple of macros to make chaining multiple functions more practical, but getting from there to Qi is a long shot.

My impression on the other hand is that Typed Racket is getting a little bit of an unequal treatment, because it builds upon an existing language known for its high flexibility, which naturally makes things much harder to type than, say, in Haskell, whether the whole language was designed from the ground up to work well with a certain type system.

Good luck with that, and do give some feedback on the forum here :slight_smile:

2 Likes

Hi @countvajhula, and sorry for the late answer. I waited until I had enough time to properly read, think, and answer to your message.

EDIT: Sorry, I initially posted a half-finished message because my fingers slipped :smiley:


Yeah, Haskell is very dense, but I believe that programming in this language gave me some discipline and insight which I couldn't have got otherwise. Still, today Racket is my favorite language :smiley:

I think you are right: Qi has the goal of composing computation transparently (i.e., without unpacking the values too much), and it's exactly the goal of Arrows. Since both Qi and Arrows are designed in a functional programming context, it is probably not that surprising that there are a lot of coincidences.

I share that intuition as well. I think one of the reasons for some things being simpler in Qi goes down to the flexibility of Racket.

That's interesting, thank you for the reference! I even think that in Qi the need for the Maybe monad is lesser, because there seem to be other ways to deal with cases with which it deals in e.g. Haskell.

Very interesting! I'd be curious to discuss this with you, but probably on a different channel.

To me, monads in computing are a tool which allows to formally capture some aspects of composition of computation. Monads allow reasoning about the code without actually executing, which is sometimes really practical, especially when side effects are involved. There are other tools for composing computation which have less nice formal properties, but which on the other hand are way more practical. As a trivial example I like to cite is putting debug output in your code. In Racket it may be as simple as adding a print / display in your function, while in a strictly monad-focused language such as Haskell this taints the type of the function and the type of all calling functions with the IO monad. (There is of course Debug.Trace, but it kind of proves the point: you essentially have to escape the type system if you want to do debug output without too much refactoring.)

My opinion is that Qi should be able to easily generalize all interesting monad use cases (I speak here after having skimmed a Qi tutorial without actually doing the exercises :smiley: ), but will at the same type give up on some formal properties of the programs.

From what I remember, arrows generalize monads in some way, and as I stated above I believe that Qi has better compositional properties, and loses some formal properties (as often happens with generalizations).

Oh, I guess you are right! I have read some discussions about continuations here, some docs here and there, and listened to some presentations, but they have been systematically out of my use cases. I promised myself that the next time I need to exit a nested loop, I will definitely use continuations instead of some additional Boolean flags :smiley:

Woow, cool! Liked and subscribed :smiley:

Oh, I looked through the docs for Turnstile a couple of times, but I couldn't yet see an immediate application. But you are right, it does seem very relevant to the potential Typed Qi project!

3 Likes