Re: [MLton] Adding new primitive functions to MLton
Matthew Fluet <[email protected]> Wed, 28 Oct 2020 16:07:30 -0400
| Newsgroups | gmane.comp.lang.ml.mlton.devel |
|---|---|
| Message-ID | <CAMrhFL5d3aRaeMQedo+x2AQw7xy8sc3fj0ZpHA4gJGEX5sH8KA@mail.gmail.com> |
--===============1694419059299888098== Content-Type: multipart/alternative; boundary="000000000000419f1005b2c0b72d" --000000000000419f1005b2c0b72d Content-Type: text/plain; charset="UTF-8" On Mon, Oct 26, 2020 at 6:03 PM Morten Olsen Lysgaard <[email protected]> wrote: > Hi, I am doing some exploratory work on a synchronous programming > language. This is a follow up of my previous email about using an empty > basis. > In that work I have found MLton to have a very good fit as a frontend. > > Like other synchronous languages, eg. lucid synchrone, lustre, there are > primitive time operators. These are: > > pre : forall a. a -> a > when : forall a. a -> Bool -> a > fby : forall a. a -> a -> a > > These functions will have a special meaning for the runtime of my > language, and are thus not possible to implement as library functions. I > would like them to be built into the compiler. > > My first goal is to be able to write code using the functions, and have > them go all the way to core-ml. Not really having the function do anything, > just lexing, parsing, type checking. > > I started hacking in one end, but I quickly realized that I need to > understand more about the architecture and design choices that have been > made for MLton before I add my functions. > I would be very happy for pointers to the relevant places in the MLton > source for my ideas. > > * My thinking is that the functions may not need to be specially handled > during lexing and parsing, because they look like any other function calls > for the lexer/parser. Is this correct? > Most likely, so long as your primitives only depend on the values of their arguments, not on the expressions themselves. That is, while `Vector_sub` is a primitive, we cannot make `orelse` a primitive, because it depends on short-circuit evaluation, and we cannot make an `assert` primitive, because it wants the text of its argument to be printed on failure. To put it another way, with a primitive `p` of type `int -> string`, we must be prepared for a source expression `p (1 + 2 + 3)` to be translated to `let val x = 1 + 2 + 3 in p x end` during the early stages of the compiler. * They need to have a "hard-coded" type in the type checker. How to best > achieve this? > They do and they don't. With respect to the front-end type checking, primitives are imported into the environment with a declared type, which is "trusted" by the type checker. Somewhat later in the compilation, we type check applications of primitives in the intermediate languages, and there the compiler "knows" the types of primitives. > * How does MLton handle primitive functions like this? Does it use it's > own full fledged expression node for each primitive, is there a special > abstraction in the AST for primitives, or is it using some other solution? > More of the latter: an abstraction in the AST for primitives. Here's the general approach for adding primitives to MLton. Primitives are defined in the compiler via `structure Prim: PRIM`: - https://github.com/MLton/mlton/blob/master/mlton/atoms/prim.sig - https://github.com/MLton/mlton/blob/master/mlton/atoms/prim.fun You'd want to add new constructors to the `datatype `a t = ...` declaration and then add cases for the new primitives to most of the functions in the `prim.fun` file. Importantly, you need to define the `toString` name for the primitives and add them to the `all` value. This allows the primitives to be imported into the basis library via their name. Also you need to define the `checkApp` behavior for internal type checking of the primitive. Primitives are imported into source code via the `_prim "name": ty;` form. See, for example: - https://github.com/MLton/mlton/blob/master/basis-library/primitive/prim-seq.sml Technically, you don't need to be in the Basis Library implementation to import new primitives; you could define your own .mlb file like the following: ``` sync.mlb: ann "allowPrim true" in sync.sml end ``` ``` sync.sml: structure Sync = struct val pre = _prim "Sync_pre": 'a -> 'a; val when = _prim "Sync_when": 'a -> bool -> 'a; val fby = _prim "Sync_fby": 'a -> 'a -> 'a; end ``` With this, a program that uses `sync.mlb` and then the subsequently exposed primitive operations will type check the source and carry through to the CoreML (and probably even to the XML IR), ultimately erroring out somewhere with an "unexpected primitive" error. You can trace the representation of primitives through the compiler: * AST IR and Parser: - https://github.com/MLton/mlton/blob/master/mlton/ast/ast-core.sig#L119 - https://github.com/MLton/mlton/blob/master/mlton/ast/ast-core.sig#L153 - https://github.com/MLton/mlton/blob/master/mlton/front-end/ml.grm#L1067 * CoreML IR: - https://github.com/MLton/mlton/blob/master/mlton/core-ml/core-ml.sig#L99 * XML/SXML IR: - https://github.com/MLton/mlton/blob/master/mlton/xml/xml-tree.sig#L94 What you do with the primitives beyond this point somewhat depends on how you will implement them. Most of the MLton supported primitives are simple operations (like Vector_sub or Word32_add), which get carried through the whole compiler and then are handled specially by each code generator, possibly by just making a call to a C function to provide the implementation. Beware, though, that this may not work well with polymorphic operations. Other primitives are implemented during compilation itself; for example `MLton_equal` (which corresponds to SML's polymorphic equality operation) is expanded to code during the SSA IR optimization passes ( https://github.com/MLton/mlton/blob/master/mlton/ssa/poly-equal.fun). We also eliminate some primitives even earlier in the compiler. For example, the `TopLevel_{get,set}Suffix` primitives are expanded during the XML IR optimization passes ( https://github.com/MLton/mlton/blob/master/mlton/xml/implement-suffix.fun ). Best, -Matthew --000000000000419f1005b2c0b72d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div dir=3D"ltr"><div class=3D"gmail_default" style=3D"fon= t-family:courier new,monospace;font-size:large"><span style=3D"font-family:= Arial,Helvetica,sans-serif;font-size:small">On Mon, Oct 26, 2020 at 6:03 PM= Morten Olsen Lysgaard <<a href=3D"mailto:[email protected]" target=3D"= _blank">[email protected]</a>> wrote:</span><br></div></div><div class= =3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px = 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir= =3D"ltr"><div>Hi, I am doing some exploratory work on a synchronous program= ming language. This is a follow up of my previous email about using an empt= y basis.<br></div><div>In that work I have found MLton to have a very good = fit as a frontend.</div><div><br></div><div>Like other synchronous language= s, eg. lucid synchrone, lustre, there are primitive time operators. These a= re:</div><div><br></div><div>pre : forall a. a -> a</div><div>when : for= all a. a -> Bool -> a</div><div>fby : forall a. a -> a -> a</di= v><div><br></div><div>These functions will have a special meaning for the r= untime of my language, and are thus not possible to implement as library fu= nctions. I would like them to be built into the compiler.<br></div><div><br= ></div><div>My first goal is to be able to write code using the functions, = and have them go all the way to core-ml. Not really having the function do = anything, just lexing, parsing, type checking.</div><div><br></div><div>I s= tarted hacking in one end, but I quickly realized that I need to understand= more about the architecture and design choices that have been made for MLt= on before I add my functions.<br></div><div>I would be very happy for point= ers to the relevant places in the MLton source for my ideas.</div><div><br>= </div><div>* My thinking is that the functions may not need to be specially= handled during lexing and parsing, because they look like any other functi= on calls for the lexer/parser. Is this correct?<br></div><div></div></div><= /blockquote><div><br></div><div><div class=3D"gmail_default" style=3D"font-= family:"courier new",monospace;font-size:large">Most likely, so l= ong as your primitives only depend on the values of their arguments, not on= the expressions themselves.=C2=A0 That is, while `Vector_sub` is a primiti= ve, we cannot make `orelse` a primitive, because it depends on short-circui= t evaluation, and we cannot make an `assert` primitive, because it wants th= e text of its argument to be printed on failure.=C2=A0 To put it another wa= y, with a primitive `p` of type `int -> string`, we must be prepared for= a source expression `p (1=C2=A0+ 2=C2=A0+ 3)` to be translated to `let val= x =3D 1=C2=A0+ 2=C2=A0+ 3 in p x end` during the early stages of the compi= ler.</div></div><div><br></div><blockquote class=3D"gmail_quote" style=3D"m= argin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left= :1ex"><div dir=3D"ltr"><div>* They need to have a "hard-coded" ty= pe in the type checker. How to best achieve this?</div><div></div></div></b= lockquote><div><br></div><div><div class=3D"gmail_default" style=3D"font-fa= mily:"courier new",monospace;font-size:large">They do and they do= n't.=C2=A0 With respect to the front-end type checking, primitives are = imported into the environment with a declared type, which is "trusted&= quot; by the type checker.=C2=A0 Somewhat later in the compilation, we type= check applications of primitives in the intermediate languages, and there = the compiler "knows" the types of primitives.</div></div><div>=C2= =A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e= x;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"= ><div>* How does MLton handle primitive functions like this? Does it use it= 's own full fledged expression node for each primitive, is there a spec= ial abstraction in the AST for primitives, or is it using some other soluti= on?</div></div></blockquote><div><br></div><div class=3D"gmail_default" sty= le=3D"font-family:"courier new",monospace;font-size:large">More o= f the latter: an abstraction in the AST for primitives.</div><div class=3D"= gmail_default" style=3D"font-family:"courier new",monospace;font-= size:large"><br></div><div class=3D"gmail_default" style=3D"font-family:&qu= ot;courier new",monospace;font-size:large">Here's the general appr= oach for adding primitives to MLton.</div><div class=3D"gmail_default" styl= e=3D"font-family:"courier new",monospace;font-size:large"><br></d= iv><div class=3D"gmail_default" style=3D"font-family:"courier new"= ;,monospace;font-size:large">Primitives are defined in the compiler via `st= ructure Prim: PRIM`:</div><div class=3D"gmail_default" style=3D"font-family= :"courier new",monospace;font-size:large">=C2=A0- <a href=3D"http= s://github.com/MLton/mlton/blob/master/mlton/atoms/prim.sig">https://github= .com/MLton/mlton/blob/master/mlton/atoms/prim.sig</a><br></div><div class= =3D"gmail_default" style=3D"font-family:"courier new",monospace;f= ont-size:large">=C2=A0- <a href=3D"https://github.com/MLton/mlton/blob/mast= er/mlton/atoms/prim.fun">https://github.com/MLton/mlton/blob/master/mlton/a= toms/prim.fun</a><br></div><div class=3D"gmail_default" style=3D"font-famil= y:"courier new",monospace;font-size:large"><br></div><div class= =3D"gmail_default" style=3D"font-family:"courier new",monospace;f= ont-size:large">You'd want to add new constructors to the `datatype `a = t =3D ...` declaration and then add cases for the new primitives to most of= the functions in the `prim.fun` file.=C2=A0 Importantly, you need to defin= e the `toString` name for the primitives and add them to the `all` value.= =C2=A0 This allows the primitives to be imported into the basis library via= their name.=C2=A0 Also you need to define the `checkApp` behavior for inte= rnal type checking of the primitive.</div><div class=3D"gmail_default" styl= e=3D"font-family:"courier new",monospace;font-size:large"><br></d= iv><div class=3D"gmail_default" style=3D"font-family:"courier new"= ;,monospace;font-size:large">Primitives are imported into source code via t= he `_prim "name": ty;` form.=C2=A0 See, for example:</div><div cl= ass=3D"gmail_default" style=3D"font-family:"courier new",monospac= e;font-size:large">=C2=A0- <a href=3D"https://github.com/MLton/mlton/blob/m= aster/basis-library/primitive/prim-seq.sml">https://github.com/MLton/mlton/= blob/master/basis-library/primitive/prim-seq.sml</a><br></div><div class=3D= "gmail_default" style=3D"font-family:"courier new",monospace;font= -size:large"><br></div><div class=3D"gmail_default" style=3D"font-family:&q= uot;courier new",monospace;font-size:large">Technically, you don't= need to be in the Basis Library implementation to import new primitives; y= ou could define your own .mlb file like the following:</div><div class=3D"g= mail_default" style=3D"font-family:"courier new",monospace;font-s= ize:large"><br></div><div class=3D"gmail_default" style=3D"font-family:&quo= t;courier new",monospace;font-size:large">``` sync.mlb:</div><div clas= s=3D"gmail_default" style=3D"font-family:"courier new",monospace;= font-size:large">ann</div><div class=3D"gmail_default" style=3D"font-family= :"courier new",monospace;font-size:large">=C2=A0 "allowPrim = true"</div><div class=3D"gmail_default" style=3D"font-family:"cou= rier new",monospace;font-size:large">in</div><div class=3D"gmail_defau= lt" style=3D"font-family:"courier new",monospace;font-size:large"= >=C2=A0 sync.sml</div><div class=3D"gmail_default" style=3D"font-family:&qu= ot;courier new",monospace;font-size:large">end</div><div class=3D"gmai= l_default" style=3D"font-family:"courier new",monospace;font-size= :large">```</div><div class=3D"gmail_default" style=3D"font-family:"co= urier new",monospace;font-size:large"><br></div><div class=3D"gmail_de= fault" style=3D"font-family:"courier new",monospace;font-size:lar= ge">``` sync.sml:</div><div class=3D"gmail_default" style=3D"font-family:&q= uot;courier new",monospace;font-size:large">structure Sync =3D</div><d= iv class=3D"gmail_default" style=3D"font-family:"courier new",mon= ospace;font-size:large">struct</div><div class=3D"gmail_default" style=3D"f= ont-family:"courier new",monospace;font-size:large">=C2=A0 val pr= e =3D _prim "Sync_pre": 'a -> 'a;</div><div class=3D"g= mail_default" style=3D"font-family:"courier new",monospace;font-s= ize:large">=C2=A0 val when =3D _prim "Sync_when": 'a -> bo= ol -> 'a;</div><div class=3D"gmail_default" style=3D"font-family:&qu= ot;courier new",monospace;font-size:large">=C2=A0 val fby =3D _prim &q= uot;Sync_fby": 'a -> 'a -> 'a;</div><div class=3D"gm= ail_default" style=3D"font-family:"courier new",monospace;font-si= ze:large">end</div><div class=3D"gmail_default" style=3D"font-family:"= courier new",monospace;font-size:large">```</div><div class=3D"gmail_d= efault" style=3D"font-family:"courier new",monospace;font-size:la= rge"><br></div><div class=3D"gmail_default" style=3D"font-family:"cour= ier new",monospace;font-size:large">With this, a program that uses `sy= nc.mlb` and then the subsequently exposed primitive operations will type ch= eck the source and carry through to the CoreML (and probably even to the XM= L IR), ultimately erroring out somewhere with an "unexpected primitive= " error.</div><div class=3D"gmail_default" style=3D"font-family:"= courier new",monospace;font-size:large"><br></div><div class=3D"gmail_= default" style=3D"font-family:"courier new",monospace;font-size:l= arge">You can trace the representation of primitives through the compiler:<= /div><div class=3D"gmail_default" style=3D"font-family:"courier new&qu= ot;,monospace;font-size:large">* AST IR and Parser:</div><div class=3D"gmai= l_default" style=3D"font-family:"courier new",monospace;font-size= :large">=C2=A0- <a href=3D"https://github.com/MLton/mlton/blob/master/mlton= /ast/ast-core.sig#L119">https://github.com/MLton/mlton/blob/master/mlton/as= t/ast-core.sig#L119</a><br></div><div class=3D"gmail_default" style=3D"font= -family:"courier new",monospace;font-size:large">=C2=A0- <a href= =3D"https://github.com/MLton/mlton/blob/master/mlton/ast/ast-core.sig#L153"= >https://github.com/MLton/mlton/blob/master/mlton/ast/ast-core.sig#L153</a>= </div><div class=3D"gmail_default" style=3D"font-family:"courier new&q= uot;,monospace;font-size:large">=C2=A0- <a href=3D"https://github.com/MLton= /mlton/blob/master/mlton/front-end/ml.grm#L1067">https://github.com/MLton/m= lton/blob/master/mlton/front-end/ml.grm#L1067</a><br></div><div class=3D"gm= ail_default" style=3D"font-family:"courier new",monospace;font-si= ze:large">* CoreML IR:</div><div class=3D"gmail_default" style=3D"font-fami= ly:"courier new",monospace;font-size:large">=C2=A0-=C2=A0<a href= =3D"https://github.com/MLton/mlton/blob/master/mlton/core-ml/core-ml.sig#L9= 9">https://github.com/MLton/mlton/blob/master/mlton/core-ml/core-ml.sig#L99= </a></div><div class=3D"gmail_default" style=3D"font-family:"courier n= ew",monospace;font-size:large">* XML/SXML IR:</div><div class=3D"gmail= _default" style=3D"font-family:"courier new",monospace;font-size:= large">=C2=A0-=C2=A0<a href=3D"https://github.com/MLton/mlton/blob/master/m= lton/xml/xml-tree.sig#L94">https://github.com/MLton/mlton/blob/master/mlton= /xml/xml-tree.sig#L94</a></div><div class=3D"gmail_default" style=3D"font-f= amily:"courier new",monospace;font-size:large"><br></div><div cla= ss=3D"gmail_default" style=3D"font-family:"courier new",monospace= ;font-size:large">What you do with the primitives beyond this point somewha= t depends on how you will implement them.=C2=A0 Most of the MLton supported= primitives are simple operations (like Vector_sub or Word32_add), which ge= t carried through the whole compiler and then are handled specially by each= code generator, possibly by just making a call to a C function to provide = the implementation.=C2=A0 Beware, though, that this may not work well with = polymorphic operations.</div><div class=3D"gmail_default" style=3D"font-fam= ily:"courier new",monospace;font-size:large"><br></div><div class= =3D"gmail_default" style=3D"font-family:"courier new",monospace;f= ont-size:large">Other primitives are implemented during compilation itself;= for example `MLton_equal` (which corresponds to SML's polymorphic equa= lity operation) is expanded to code during the SSA IR optimization passes (= <a href=3D"https://github.com/MLton/mlton/blob/master/mlton/ssa/poly-equal.= fun">https://github.com/MLton/mlton/blob/master/mlton/ssa/poly-equal.fun</a= >).=C2=A0 We also eliminate some primitives even earlier in the compiler.= =C2=A0 For example, the `TopLevel_{get,set}Suffix` primitives are expanded = during the XML IR optimization passes (<a href=3D"https://github.com/MLton/= mlton/blob/master/mlton/xml/implement-suffix.fun">https://github.com/MLton/= mlton/blob/master/mlton/xml/implement-suffix.fun</a>).=C2=A0=C2=A0</div><di= v class=3D"gmail_default" style=3D"font-family:"courier new",mono= space;font-size:large"><br></div><div class=3D"gmail_default" style=3D"font= -family:"courier new",monospace;font-size:large">Best,</div><div = class=3D"gmail_default" style=3D"font-family:"courier new",monosp= ace;font-size:large">-Matthew</div><div class=3D"gmail_default" style=3D"fo= nt-family:"courier new",monospace;font-size:large"></div></div></= div> --000000000000419f1005b2c0b72d-- --===============1694419059299888098== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline --===============1694419059299888098== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ MLton-devel mailing list [email protected]; [email protected] https://lists.sourceforge.net/lists/listinfo/mlton-devel --===============1694419059299888098==--