[MLton-devel] A CM replacement for MLton
Stephen Weeks
MLton@mlton.org
Fri, 11 Jul 2003 18:31:33 -0700
> My thoughts on the whole thing revolve around the fact that what the scoping
> is is REALLY a new language.
I completely agree.
> I don't disagree that the changes are needed for programming in the
> large (although C has survived without them and also needs them).
C at least has #include and linking. These express dependencies at
both the interface and implementation level to some extent. SML has
*nothing* like this, so one must add something.
> Given that point of view, I would rather that the scoping in the
> large NOT be tied to file structure quite so intimately, but to
> actual language constructs.
What follows are some rough thoughts.
Here is a new scoping language not tied at all to file structure.
Create a new class of identifiers, "basis identifiers"
b in Bid
Here are the grammars for basis declarations and basis expressions.
<bdec> ::= basis <bid> = <bexp>
| clean <bdec> end
| functor <fctid> = <fctid>
| local <bdec> in <bdec> end
| open <bexp>
| prog <program> end
| <bdec> <bdec>
<bexp> ::= <bid>
| bas <bdec> end
In order to give a semantics, we need to extend the usual SML notion
of Basis with an extra component that maps a basis identifier to a
basis.
B in Basis = (Bid -> Basis) x FunEnv x SigEnv x Env
We can now define the elaboration of basis declarations and
expressions.
B |- <bdec> --> B'
B |- <bexp> --> B
Here are the rules for expressions.
---------------
B |- b --> B(b)
B |- d --> B'
---------------------
B |- bas d end --> B'
Here are the rules for declarations.
B |- e --> B'
----------------------------------------
B |- basis b = e --> [b |-> B'] in Basis
|- d --> B'
-----------------------
B |- clean d end --> B'
----------------------------------------------
B |- functor F = F' --> [F |-> B(F')] in Basis
B |- p1 --> B1 B + B1 |- p2 --> B2
------------------------------------
B |- local p1 in p2 end --> B2
B |- e -> B'
------------------
B |- open e --> B'
B |- p => B'
----------------------
B |- prog p end --> B'
B |- d1 --> B1 B + B1 |- d2 --> B2
------------------------------------
B |- d1 d2 --> B1 + B2
With this in place, we can now define some abbreviations
<bdec> ::= ...
| functor (<fctid> [= <fctid>])*
| signature (<sigid> [= <sigid>])*
| structure (<strid> [= <strid>])*
shorthand expansion
-------------- ---------------------
functor F ... functor F functor ...
functor F functor F = F
signature S ... signature S signature ...
signature S signature S = S
signature S = S' prog signature S = S' end
structure S ... structure S structure ...
structure S structure S = S
structure S = S' prog structure S = S' end
We can't quite treat functors the same as signatures and structures
because SML doesn't allow "functor F = F'" as a program.
Now, we can define how the file system ties in with some more
abbreviations.
<bdec> ::= ...
| <file>.{fun|sig|sml}
| <file>.mlb
We can now define how to expand a basis declaration in the extended
language into a basis declaration in the core language, assuming a
mapping for filesystem contents. This is easier to do with SML code
than informal notation.
----------------------------------------------------------------------
functor F (structure Bid:
sig
type t
val new: unit -> t
end
structure Fctid:
sig
type t
end
structure FctClos:
sig
type t
end
structure Basis:
sig
type t
val + : t * t -> t
val empty: t
val fct: Fctid.t * FctClos.t -> t
val lookupBid: t * Bid.t -> t
val lookupFctid: t * Fctid.t -> FctClos.t
end
structure Program:
sig
type t
val elab: t * Basis.t -> Basis.t
end
structure CoreBdec:
sig
datatype ('bdec, 'bexp) t =
Bind of Bid.t * 'bexp
| Clean of 'bdec
| Empty
| Functor of Fctid.t * Fctid.t
| Local of 'bdec * 'bdec
| Open of 'bexp
| Program of Program.t
| Seq of 'bdec * 'bdec
end
structure CoreBexp:
sig
datatype 'bdec t =
Dec of 'bdec
| Id of Bid.t
end
structure Core:
sig
datatype bdec = Bdec of (bdec, bexp) CoreBdec.t
and bexp = Bexp of bdec CoreBexp.t
end
structure MLBFile:
sig
type t
val equals: t * t -> bool
end
structure SMLFile:
sig
type t
end
structure Extended:
sig
datatype bdec =
Core of (bdec, bexp) CoreBdec.t
| MLBFile of MLBFile.t
| SMLFile of SMLFile.t
and bexp = Bexp of bdec CoreBexp.t
end
val contentsSML: SMLFile.t -> Program.t
val contentsMLB: MLBFile.t -> Extended.bdec
): sig
val expand: Extended.bdec -> Core.bdec
end =
struct
structure List =
struct
open List
fun foldl (l: 'a list, b: 'b, f: 'a * 'b -> 'b): 'b = List.foldl f b l
end
datatype z = datatype CoreBdec.t
datatype z = datatype CoreBexp.t
val rec elabExp: Core.bexp * Basis.t -> Basis.t =
fn (Core.Bexp e, B) =>
case e of
Dec d => elabDec (d, B)
| Id b => Basis.lookupBid (B, b)
and elabDec: Core.bdec * Basis.t -> Basis.t =
fn (Core.Bdec d, B) =>
case d of
Bind (b, e) => elabExp (e, B)
| Clean d => elabDec (d, Basis.empty)
| Empty => Basis.empty
| Functor (f, f') => Basis.fct (f, Basis.lookupFctid (B, f'))
| Local (d1, d2) =>
let
val B1 = elabDec (d1, B)
val B2 = elabDec (d2, Basis.+ (B, B1))
in
B2
end
| Open e => elabExp (e, B)
| Program p => Program.elab (p, B)
| Seq (d1, d2) =>
let
val B1 = elabDec (d1, B)
val B2 = elabDec (d2, Basis.+ (B, B1))
in
Basis.+ (B1, B2)
end
val rebind: Bid.t list -> Core.bdec =
fn bs =>
List.foldl (bs, Core.Bdec Empty, fn (b: Bid.t, d: Core.bdec) =>
Core.Bdec (Seq (d, Core.Bdec (Bind (b, Core.Bexp (Id b))))))
val expand: Extended.bdec -> Core.bdec =
fn d =>
let
type lookup = (MLBFile.t -> Bid.t option)
type res = Bid.t list * lookup
datatype z = datatype Extended.bdec
val rec expandDec: Extended.bdec * lookup -> Core.bdec * res =
fn (d, lookup) =>
case d of
Core d =>
let
val (d, z) =
case d of
Bind (b, e) =>
let
val (e, z) = expandExp (e, lookup)
in
(Bind (b, e), z)
end
| Clean d =>
let
val (d, z) = expandDec (d, lookup)
in
(Clean d, z)
end
| Empty => (Empty, ([], lookup))
| Functor ff' => (Functor ff', ([], lookup))
| Local (d, d') =>
let
val (d, (bs, lookup)) = expandDec (d, lookup)
val (d', (bs', lookup)) = expandDec (d', lookup)
in
(Local (d, Core.Bdec (Seq (rebind bs, d'))),
(bs @ bs', lookup))
end
| Open e =>
let
val (e, z) = expandExp (e, lookup)
in
(Open e, z)
end
| Program p => (Program p, ([], lookup))
| Seq (d, d') =>
let
val (d, (bs, lookup)) = expandDec (d, lookup)
val (d', (bs', lookup)) = expandDec (d', lookup)
in
(Seq (d, d'), (bs @ bs', lookup))
end
in
(Core.Bdec d, z)
end
| MLBFile f =>
let
val (bid, make, z) =
case lookup f of
NONE =>
let
val (d, (bs, lookup)) =
expandDec (contentsMLB f,
fn f' =>
if MLBFile.equals (f, f')
then raise Fail "Cycle"
else lookup f')
val bid = Bid.new ()
val lookup =
fn f' =>
if MLBFile.equals (f, f')
then SOME bid
else lookup f'
in
(bid,
fn d' => (Core.Bdec
(Seq (Core.Bdec
(Bind (bid,
Core.Bexp
(Dec
(Core.Bdec (Clean d'))))),
d))),
(bid :: bs, lookup))
end
| SOME bid => (bid, fn d => d, ([], lookup))
in
(make (Core.Bdec (Open (Core.Bexp (Id bid)))), z)
end
| SMLFile f => (Core.Bdec (Program (contentsSML f)),
([], lookup))
and expandExp: Extended.bexp * lookup -> Core.bexp * res =
fn (Extended.Bexp e, lookup) =>
let
val (e, z) =
case e of
Dec d =>
let
val (d, z) = expandDec (d, lookup)
in
(Dec d, z)
end
| Id b => (Id b, ([], lookup))
in
(Core.Bexp e, z)
end
val (d, _) = expandDec (d, fn _ => NONE)
in
d
end
end
----------------------------------------------------------------------
So what does all this accomplish? It makes it clear that the mlb and
sml files are "just" abbreviations for constructs in some language.
Maybe that's all Henry wanted. The extended language is a superset of
what I sent in my earlier mail. So I'm still happy with the
conciseness. But I'm not sure if it helps us implement anything, or
leads to a clearer semantics than what I gave earlier.
Maybe part of the problem is that I'm pattern matching of the erasure
semantics approach of the definition, when what we really want the
elaborator to produce is a translation to a typed IL. The expansion
above looks more complex than what I gave earlier because it actually
gives the translated decs.
Perhaps the right way to explain things is to combine the elaboration
rules I gave in the earlier mail with the expansion above to describe
how to produce an SML program from an mlb. There are two ways I could
do this:
1. Expanded Bdec ----> Core Bdec ----> SML Program
2. Bdec from Earlier Mail ----> SML Program
(1) would use the expansion above, plus modified elaboration rules
from above
(2) would use modified elaboration rules from my earlier mail, and
would combine the expansion with elaboration
Henry, I assume you prefer (1), but I would like to understand what it
really buys us. It seems worse to me because it requires an
additional language.
I am also curious if you think the actual <bdec> language from the
earlier email should be changed, and how, or if you are happy leaving
it the same but using (1) for the explanation.
Can you explain how you might achieve your goal of making the scoping
language less tied to file structure, while still retaining the
benefits that I mentioned earlier, like allowing simple files lists to
be mlb files and keeping mlb files concise?
-------------------------------------------------------
This SF.Net email sponsored by: Parasoft
Error proof Web apps, automate testing & more.
Download & eval WebKing and get a free book.
www.parasoft.com/bulletproofapps1
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel