Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: A Category for DSLs?

Davi Sales Barreira (Aug 10 2023 at 19:37):

I've been trying to understand how the concept of a domain-specific language fits within Category Theory. More specifically, here is the situation I have.

Consider a set $\mathbf{Prim}$, from which I construct a free monoid $[\mathbf{Prim}]$. Now, a DSL defined over this set $\mathbf{Prim}$ would be a functor (or something) such that one could manipulate values of $\mathbf{Prim}$ and apply an
$eval: DSL \mathbf{Prim} \to [\mathbf{Prim}]$.

This looked very similar to $F$-algebras, but the caveat is that my $eval$ function is not evaluating to the carrier, but to the free monoid over the carrier. Moreover, I'm interested in understanding if fixing the "carrier" and varying the functors (DSL?) I could define a terminal DSL, from which the other DSL could be derived. Does any of this makes any sense?

Kevin Arlin (Aug 10 2023 at 19:42):

A DSL is a kind of programming language. Do you know anything about denotational semantics of programming languages?

Davi Sales Barreira (Aug 10 2023 at 19:47):

Yeah, I know a bit about denotational semantics, mostly from functional programming. Not an expert though

Steve Huntsman (Aug 10 2023 at 20:53):

I recall Alan Jeffrey did some _very_ interesting work on semantics and monoidal stuff in the late nineties but I don't know where to find it anymore: it was a webpage, now just a glorified citation as far as I can tell under the title "Premonoidal categories and flow graphs." Some more recent stuff in this vein is (e.g.) https://arxiv.org/abs/2202.02061

Ben Logsdon (Aug 31 2023 at 20:00):

@Davi Sales Barreira Could you give an example of such a DSL you're interested in?

Jencel Panic (Sep 03 2023 at 08:04):

Primer on F-algebras: https://www.schoolofhaskell.com/user/bartosz/understanding-algebras

@Davi Sales Barreira, why did you choose the free monoid datastructure? Structures like lists are often the basis of the DSL, not the result.

Davi Sales Barreira (Sep 04 2023 at 11:45):

What I'm trying to understand is the following. I have $\mathbf{Prim}$ which is a collection of primitives. To describe complex objects, I want to generate collections of primitive. For example, in my case, I have primitives which are basic geometric objects which I use to describe a scene. Thus, a complex scene is just a collection of these basic geometric objects, i.e. an element of the free monoid over primitives. The thing is, how do I then construct these collections? Here is where a DSL comes in. The DSL incremenets some syntax/operations that I can use over my primitives in order to more "easily" create this scene. For example, a DSL can give a tree-like structure, which could then be flattened into a list of primitives. Before flattening, I have an expression in the DSL. Makes sense?

What I'm therefore trying to understand is if this notion of a DSL has a categorical analogue.

Jencel Panic (Sep 04 2023 at 15:00):

I think that this will be an F-algebra with $[Prim]$ as a carrier.

Davi Sales Barreira (Sep 04 2023 at 16:36):

@Jencel Panic , in fact, if we consider the "DSL" over $[Prim]$ so that $eval(DSL [Prim]) -> [Prim]$, than that would be an algebra... But using $[Prim]$ as the carrier is not so natural. It is more natural to think of $DSL$ over $Prim$.

Davi Sales Barreira (Sep 04 2023 at 16:36):

Hence why the more "natural" construction is not directly an F-Algebra.

Davi Sales Barreira (Sep 04 2023 at 16:37):

But perhaps there is some isomorphism hidden somewhere, and we can use $DSL$ over $[Prim]$ and there is some natural extension to a $D Prim$.

Ben Logsdon (Sep 04 2023 at 17:59):

@Davi Sales Barreira Based on your example, I'm wondering if the free commutative monoid would be better for your application than the free monoid. Free commutative monoids capture the idea of "finite collection with multiplicity and without order", while free monoids capture the idea of "finite collection with multiplicity and with order". Perhaps the former makes more sense in this case?

Ben Logsdon (Sep 04 2023 at 18:01):

Anyway, what you're describing sounds vaguely like a morphism of monads. I'm far from an expert on monads, so take everything I say with a grain of salt. But if you had some monad $T$ capturing some tree-like structure encoding the abstract syntax of your language, then I would expect there to be a monad morphism $T \Rightarrow M$, where $M$ is the free (commutative) monoid functor. This is the "flattening" operation you described. (I know this can be done in simple cases, such as flattening binary trees to lists. What you want might be a bit more complicated.)

Ben Logsdon (Sep 04 2023 at 18:03):

So, if you're willing to make your syntax as simple as, "a scene consists of either A) a primitive, or B) a pair of scenes", then that would be represented by a monad morphism as I described above.

Ben Logsdon (Sep 04 2023 at 18:04):

In that simple case, I believe the DSL over $Prim$ would be the free algebra of the endofunctor $X \mapsto X^2$ generated by $Prim$, and it would indeed come with a canonical map to the free (commutative) monoid generated by $Prim$.

Ben Logsdon (Sep 04 2023 at 18:09):

If you want more complicated syntax, the endofunctor you would choose would change in ways that I'd be happy to elaborate on if you'd like more detail.

Ben Logsdon (Sep 04 2023 at 18:11):

One thing to keep in mind, though, is that the actual language is probably more complicated than the simple version you're describing. I'm guessing that you have some primitives such as "translate", "rotate", "reflect", and "dilate" that are involved as well. In order to have a full account of what you're doing, you would need to take those into account as well.

Davi Sales Barreira (Sep 05 2023 at 11:37):

@Ben Logsdon , thanks for the answer. I actually want non-commutative, as the order is the order of the rendering of the objects.

Davi Sales Barreira (Sep 05 2023 at 11:42):

If I understood you, the idea is that we have free algebras over $Prim$, and there is a canonical way to go to the free monoid... Is that it?

Davi Sales Barreira (Sep 05 2023 at 11:43):

Since you said I needed monads, would it be Free Monad?

Steve Huntsman (Sep 18 2023 at 17:18):

I just noticed https://arxiv.org/abs/2302.00744

Ben Logsdon (Oct 10 2023 at 21:45):

@Davi Sales Barreira sorry for the delay...I've been buried in teaching recently, so I'm just now coming back to this!

Yes, it sounds like you understood what I said correctly. The monad which generates free monoids is called the "free monoid monad", because the monad takes as an input an object $X$ and returns the free monoid generated by $X$. And the key operation I think you're looking for is a natural transformation (i.e. a monad morphism) from some other monad $T$ to the free monoid monad.

And yes, what you said about the non-commutativity makes sense :)