Re: [MLton] Adding new primitive functions to MLton
Morten Olsen Lysgaard <[email protected]> Sun, 1 Nov 2020 21:25:48 +0100
| Newsgroups | gmane.comp.lang.ml.mlton.devel |
|---|---|
| Message-ID | <CAOujwNHuzXYxLWp+MJX8RL+GGbAAGoocsCd3sNfCZiY-fBV99w@mail.gmail.com> |
--===============5231743338644209690== Content-Type: multipart/alternative; boundary="0000000000009200da05b31171d0" --0000000000009200da05b31171d0 Content-Type: text/plain; charset="UTF-8" Thanks for the detailed and well thought out answer. It helped me a lot! With it I was able to define my primitive and pass it all the way to SXML layer. The MLton code is quite easy to read, and well written compared to other compilers I've come across. To be able to express some of the crucial properties of the time operators in a synchronous language, it is required to have a first order program, without polymorphism. SXML is monomorphic, so my next goal is to get from the SXML to SSA to get a monomorphic first-order language. Right now, my primitives are erroring out with the following message: `Ssa.TypeCheck.primApp (Sync_pre(unit) (unit)) in val x_14685: bool = prim Sync_pre[unit] (x_14686) in L_0 in main_1` This error seems to be coming from type checking after the SSA code has been generated. But I suspect the real problem lies in the `closure-convert.fun` not having any special handling of my new `Sync_pre` primitive. I have been trying to figure out what the `ClosureConvert.convertPrimExp` function does, but I have still not figured it out. Do you have any details on how it works, and if it could be the root of my problem? Or maybe any other places in the conversion from SXML to SSA my code could go wrong? My `Sync_pre` function should behave like the identity function, `(a -> a)`, with respect to the type checking. Regards, Morten On Wed, Oct 28, 2020 at 9:08 PM Matthew Fluet <[email protected]> wrote: > 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 > _______________________________________________ > MLton-devel mailing list > [email protected]; [email protected] > https://lists.sourceforge.net/lists/listinfo/mlton-devel > --0000000000009200da05b31171d0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div>Thanks for the detailed and well thought out answer. = It helped me a lot!</div><div>With it I was able to define my primitive and= pass it all the way to SXML layer.</div><div><br></div><div>The MLton code= is quite easy to read, and well written compared to other compilers I'= ve come across.<br></div><div><br></div><div></div><div>To be able to expre= ss some of the crucial properties of the time operators in a synchronous la= nguage, it is required to have a first order program, without polymorphism.= </div><div>SXML is monomorphic, so my next goal is to get from the SXML to = SSA to get a monomorphic first-order language.</div><div><br></div><div>Rig= ht now, my primitives are erroring out with the following message:</div><di= v><span style=3D"font-family:monospace">`Ssa.TypeCheck.primApp (Sync_pre(un= it) (unit)) in val x_14685: bool =3D prim Sync_pre[unit] (x_14686) in L_0 i= n main_1`</span></div><div><br></div><div>This error seems to be coming fro= m type checking after the SSA code has been generated. But I suspect the re= al problem lies in the <span style=3D"font-family:monospace">`closure-conve= rt.fun`</span> not having any special handling of my new <span style=3D"fon= t-family:monospace">`Sync_pre`</span> primitive.</div><div><br></div><div>I= have been trying to figure out what the <span style=3D"font-family:monospa= ce">`ClosureConvert.convertPrimExp`</span> function does, but I have still = not figured it out. Do you have any details on how it works, and if it coul= d be the root of my problem? Or maybe any other places in the conversion fr= om SXML to SSA my code could go wrong?<br></div><div>My <span style=3D"font= -family:monospace">`Sync_pre`</span> function should behave like the identi= ty function, <span style=3D"font-family:monospace">`(a -> a)`</span>, wi= th respect to the type checking.<br></div><div><br></div><div>Regards, Mort= en<br></div><div><br> </div></div><br><div class=3D"gmail_quote"><div dir= =3D"ltr" class=3D"gmail_attr">On Wed, Oct 28, 2020 at 9:08 PM Matthew Fluet= <<a href=3D"mailto:[email protected]">[email protected]</a>= > wrote:<br></div><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 dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-fa= mily:courier new,monospace;font-size:large"><span style=3D"font-family:Aria= l,Helvetica,sans-serif;font-size:small">On Mon, Oct 26, 2020 at 6:03 PM Mor= ten Olsen Lysgaard <<a href=3D"mailto:[email protected]" target=3D"_bla= nk">[email protected]</a>> wrote:</span><br></div></div><div class=3D"g= mail_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"l= tr"><div>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 bas= is.<br></div><div>In that work I have found MLton to have a very good fit a= s a frontend.</div><div><br></div><div>Like other synchronous languages, eg= . lucid synchrone, lustre, there are primitive time operators. These are:</= div><div><br></div><div>pre : forall a. a -> a</div><div>when : forall a= . a -> Bool -> a</div><div>fby : forall a. a -> a -> a</div><di= v><br></div><div>These functions will have a special meaning for the runtim= e of my language, and are thus not possible to implement as library functio= ns. I would like them to be built into the compiler.<br></div><div><br></di= v><div>My first goal is to be able to write code using the functions, and h= ave them go all the way to core-ml. Not really having the function do anyth= ing, just lexing, parsing, type checking.</div><div><br></div><div>I starte= d 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 be= fore I add my functions.<br></div><div>I would be very happy for pointers t= o 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 hand= led during lexing and parsing, because they look like any other function ca= lls for the lexer/parser. Is this correct?<br></div><div></div></div></bloc= kquote><div><br></div><div><div class=3D"gmail_default" style=3D"font-famil= y:"courier new",monospace;font-size:large">Most likely, so long a= s your primitives only depend on the values of their arguments, not on the = expressions themselves.=C2=A0 That is, while `Vector_sub` is a primitive, w= e cannot make `orelse` a primitive, because it depends on short-circuit eva= luation, and we cannot make an `assert` primitive, because it wants the tex= t of its argument to be printed on failure.=C2=A0 To put it another way, wi= th a primitive `p` of type `int -> string`, we must be prepared for a so= urce 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 compiler= .</div></div><div><br></div><blockquote class=3D"gmail_quote" style=3D"marg= in:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1e= x"><div dir=3D"ltr"><div>* They need to have a "hard-coded" type = in the type checker. How to best achieve this?</div><div></div></div></bloc= kquote><div><br></div><div><div class=3D"gmail_default" style=3D"font-famil= y:"courier new",monospace;font-size:large">They do and they don&#= 39;t.=C2=A0 With respect to the front-end type checking, primitives are imp= orted into the environment with a declared type, which is "trusted&quo= t; by the type checker.=C2=A0 Somewhat later in the compilation, we type ch= eck 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.8ex;b= order-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><d= iv>* How does MLton handle primitive functions like this? Does it use it= 9;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?= </div></div></blockquote><div><br></div><div class=3D"gmail_default" style= =3D"font-family:"courier new",monospace;font-size:large">More of = the latter: an abstraction in the AST for primitives.</div><div class=3D"gm= ail_default" style=3D"font-family:"courier new",monospace;font-si= ze:large"><br></div><div class=3D"gmail_default" style=3D"font-family:"= ;courier new",monospace;font-size:large">Here's the general approa= ch for adding primitives to MLton.</div><div class=3D"gmail_default" style= =3D"font-family:"courier new",monospace;font-size:large"><br></di= v><div class=3D"gmail_default" style=3D"font-family:"courier new"= ,monospace;font-size:large">Primitives are defined in the compiler via `str= ucture Prim: PRIM`:</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/atoms/prim.sig" target=3D"_blan= k">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&qu= ot;,monospace;font-size:large">=C2=A0- <a href=3D"https://github.com/MLton/= mlton/blob/master/mlton/atoms/prim.fun" target=3D"_blank">https://github.co= m/MLton/mlton/blob/master/mlton/atoms/prim.fun</a><br></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">You'd want to add new co= nstructors to the `datatype `a t =3D ...` declaration and then add cases fo= r the new primitives to most of the functions in the `prim.fun` file.=C2=A0= Importantly, you need to define the `toString` name for the primitives and= add them to the `all` value.=C2=A0 This allows the primitives to be import= ed into the basis library via their name.=C2=A0 Also you need to define the= `checkApp` behavior for internal type checking of the primitive.</div><div= class=3D"gmail_default" style=3D"font-family:"courier new",monos= pace;font-size:large"><br></div><div class=3D"gmail_default" style=3D"font-= family:"courier new",monospace;font-size:large">Primitives are im= ported into source code via the `_prim "name": ty;` form.=C2=A0 S= ee, for example:</div><div class=3D"gmail_default" style=3D"font-family:&qu= ot;courier new",monospace;font-size:large">=C2=A0- <a href=3D"https://= github.com/MLton/mlton/blob/master/basis-library/primitive/prim-seq.sml" ta= rget=3D"_blank">https://github.com/MLton/mlton/blob/master/basis-library/pr= imitive/prim-seq.sml</a><br></div><div class=3D"gmail_default" style=3D"fon= t-family:"courier new",monospace;font-size:large"><br></div><div = class=3D"gmail_default" style=3D"font-family:"courier new",monosp= ace;font-size:large">Technically, you don't need to be in the Basis Lib= rary implementation to import new primitives; you could define your own .ml= b file like the following:</div><div class=3D"gmail_default" style=3D"font-= family:"courier new",monospace;font-size:large"><br></div><div cl= ass=3D"gmail_default" style=3D"font-family:"courier new",monospac= e;font-size:large">``` sync.mlb:</div><div class=3D"gmail_default" style=3D= "font-family:"courier new",monospace;font-size:large">ann</div><d= iv class=3D"gmail_default" style=3D"font-family:"courier new",mon= ospace;font-size:large">=C2=A0 "allowPrim true"</div><div class= =3D"gmail_default" style=3D"font-family:"courier new",monospace;f= ont-size:large">in</div><div class=3D"gmail_default" style=3D"font-family:&= quot;courier new",monospace;font-size:large">=C2=A0 sync.sml</div><div= class=3D"gmail_default" style=3D"font-family:"courier new",monos= pace;font-size:large">end</div><div class=3D"gmail_default" style=3D"font-f= amily:"courier new",monospace;font-size:large">```</div><div clas= s=3D"gmail_default" style=3D"font-family:"courier new",monospace;= font-size:large"><br></div><div class=3D"gmail_default" style=3D"font-famil= y:"courier new",monospace;font-size:large">``` sync.sml:</div><di= v class=3D"gmail_default" style=3D"font-family:"courier new",mono= space;font-size:large">structure Sync =3D</div><div class=3D"gmail_default"= style=3D"font-family:"courier new",monospace;font-size:large">st= ruct</div><div class=3D"gmail_default" style=3D"font-family:"courier n= ew",monospace;font-size:large">=C2=A0 val pre =3D _prim "Sync_pre= ": 'a -> 'a;</div><div class=3D"gmail_default" style=3D"fon= t-family:"courier new",monospace;font-size:large">=C2=A0 val when= =3D _prim "Sync_when": 'a -> bool -> 'a;</div><div= class=3D"gmail_default" style=3D"font-family:"courier new",monos= pace;font-size:large">=C2=A0 val fby =3D _prim "Sync_fby": 'a= -> 'a -> 'a;</div><div class=3D"gmail_default" style=3D"font= -family:"courier new",monospace;font-size:large">end</div><div cl= ass=3D"gmail_default" style=3D"font-family:"courier new",monospac= e;font-size:large">```</div><div class=3D"gmail_default" style=3D"font-fami= ly:"courier new",monospace;font-size:large"><br></div><div class= =3D"gmail_default" style=3D"font-family:"courier new",monospace;f= ont-size:large">With this, a program that uses `sync.mlb` and then the subs= equently exposed primitive operations will type check the source and carry = through to the CoreML (and probably even to the XML IR), ultimately errorin= g out somewhere with an "unexpected primitive" error.</div><div c= lass=3D"gmail_default" style=3D"font-family:"courier new",monospa= ce;font-size:large"><br></div><div class=3D"gmail_default" style=3D"font-fa= mily:"courier new",monospace;font-size:large">You can trace the r= epresentation of primitives through the compiler:</div><div class=3D"gmail_= default" style=3D"font-family:"courier new",monospace;font-size:l= arge">* AST IR and Parser:</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#L119"= target=3D"_blank">https://github.com/MLton/mlton/blob/master/mlton/ast/ast= -core.sig#L119</a><br></div><div class=3D"gmail_default" style=3D"font-fami= ly:"courier new",monospace;font-size:large">=C2=A0- <a href=3D"ht= tps://github.com/MLton/mlton/blob/master/mlton/ast/ast-core.sig#L153" targe= t=3D"_blank">https://github.com/MLton/mlton/blob/master/mlton/ast/ast-core.= sig#L153</a></div><div class=3D"gmail_default" style=3D"font-family:"c= ourier new",monospace;font-size:large">=C2=A0- <a href=3D"https://gith= ub.com/MLton/mlton/blob/master/mlton/front-end/ml.grm#L1067" target=3D"_bla= nk">https://github.com/MLton/mlton/blob/master/mlton/front-end/ml.grm#L1067= </a><br></div><div class=3D"gmail_default" style=3D"font-family:"couri= er new",monospace;font-size:large">* CoreML IR:</div><div class=3D"gma= il_default" style=3D"font-family:"courier new",monospace;font-siz= e:large">=C2=A0-=C2=A0<a href=3D"https://github.com/MLton/mlton/blob/master= /mlton/core-ml/core-ml.sig#L99" target=3D"_blank">https://github.com/MLton/= mlton/blob/master/mlton/core-ml/core-ml.sig#L99</a></div><div class=3D"gmai= l_default" style=3D"font-family:"courier new",monospace;font-size= :large">* XML/SXML 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/xml/xml-tree.sig#L94" = target=3D"_blank">https://github.com/MLton/mlton/blob/master/mlton/xml/xml-= tree.sig#L94</a></div><div class=3D"gmail_default" style=3D"font-family:&qu= ot;courier new",monospace;font-size:large"><br></div><div class=3D"gma= il_default" style=3D"font-family:"courier new",monospace;font-siz= e:large">What you do with the primitives beyond this point somewhat depends= on how you will implement them.=C2=A0 Most of the MLton supported primitiv= es are simple operations (like Vector_sub or Word32_add), which get carried= through the whole compiler and then are handled specially by each code gen= erator, possibly by just making a call to a C function to provide the imple= mentation.=C2=A0 Beware, though, that this may not work well with polymorph= ic operations.</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:= large">Other primitives are implemented during compilation itself; for exam= ple `MLton_equal` (which corresponds to SML's polymorphic equality oper= ation) 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" ta= rget=3D"_blank">https://github.com/MLton/mlton/blob/master/mlton/ssa/poly-e= qual.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.c= om/MLton/mlton/blob/master/mlton/xml/implement-suffix.fun" target=3D"_blank= ">https://github.com/MLton/mlton/blob/master/mlton/xml/implement-suffix.fun= </a>).=C2=A0=C2=A0</div><div class=3D"gmail_default" style=3D"font-family:&= quot;courier new",monospace;font-size:large"><br></div><div class=3D"g= mail_default" style=3D"font-family:"courier new",monospace;font-s= ize:large">Best,</div><div class=3D"gmail_default" style=3D"font-family:&qu= ot;courier new",monospace;font-size:large">-Matthew</div><div class=3D= "gmail_default" style=3D"font-family:"courier new",monospace;font= -size:large"></div></div></div> _______________________________________________<br> MLton-devel mailing list<br> <a href=3D"mailto:[email protected]" target=3D"_blank">MLto= [email protected]</a>; <a href=3D"mailto:[email protected]"= target=3D"_blank">[email protected]</a><br> <a href=3D"https://lists.sourceforge.net/lists/listinfo/mlton-devel" rel=3D= "noreferrer" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo= /mlton-devel</a><br> </blockquote></div> --0000000000009200da05b31171d0-- --===============5231743338644209690== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline --===============5231743338644209690== 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 --===============5231743338644209690==--