[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