Standard ML# of Kansai : A new extension of Standard ML I would like to announce a new extension of Standard ML, tentatively called Standard ML# of Kansai. (Kansai is a region in western Japan, which is, I guess, smaller than New Jersey.) SML# extends SML with polymorphic field selection and polymorphic non-destructive field update operation. Furthermore, polymorphic field accesses are always complied into efficient index operations. (For a formal description of SML#, see my paper "A Compilation Method for ML-style Polymorphic Record Calculi", POPL 1992 (its dvi file can be found in this directory.) A compiler is implemented by modifying Standard ML of New Jersey version 0.75 compiler. I hope that the extensions embodied in SML# (or something like them) be integrated in the standard of future Standard ML. Atsushi Ohori Oki Electric, Kansai Laboratory, Crystal Tower, 1-2-27 Shiromi, Chuo-ku, Osaka 540 JAPAN Email : ohori@kansai.oki.co.jp The following are some description of SML#. -------------------------------------------------------------------- FEATURES (1) Polymorphic Field Selection. SML expressions of the form #lab or more generally fn {lab1=pat1,---,labn=patn,...} => exp are given a polymorphic type and compiled to a polymorphic function. (Note: "---" is meta level ellipsis and "..." is ML syntax for "flexible record pattern".) Here are simple examples: - fun polyXval {x,...} = x; val polyXval = fn : 'b#{x:'a,...} -> 'a - val colorPoint1 = {x=100,y=200,z=10,color="Green"}; val colorPoint1 = {color="Green",x=100,y=200,z=10} : {color:string,x:int,y:int,z:int} - polyXval colorPoint1; val it = 100 : int - polyXval {x="123", y = "456"}; val it = "123" : string The notation "'b#{x:'a,...}" is a type variable "'b" with the record kind "{x:'a,...}" denoting any record type that contains a field "x:'a". As SML does for monomorphic selection, SML# compiles polymorphic field selection to efficient index operation. (See Feature (3) below.) (2) Non-Destructive Field Update. SML# includes the following expression constructor (which is called "modify" in my paper.) (The notation is a generalization of the notation suggested by Dave MacQueen in his post to sml mailing list.) #> exp => {lab1=exp1,---,labn=expn} This creates a new record from exp by modifying the value of each labi to expi, keeping all the others unchanged. Here is an example. - fun moveXby1 p = #> p => {x = #x p + 1}; val moveXby1 = fn : 'a#{x:int,...} -> 'a#{x:int,...} - moveXby1 colorPoint1; val it = {color="Green",x=101,y=200,z=10} : {color:string,x:int,y:int,z:int} - colorPoint1; val it = {color="Green",x=100,y=200,z=10} : {color:string,x:int,y:int,z:int} (3) Efficiency. SML# compiles polymorphic field selection into efficient index operation, as SML of NJ does for for monomorphic field selection. For monomorphic record field access, SML# (should) produces the same code as SML of NJ does. A polymorphic field access requires a small number of additional function applications to pass the appropriate index value (an integer constant). For simple cases, SML# compiles a polymorphic field access as efficient as the corresponding monomorphic one. Here is a very simple comparison: (a) In SML of NJ version 75 Source code: fun don n f x = if n = 1 then f x else (f x;don (n - 1) f x); System.Control.Profile.profiling := true; fun Xval ({x,...}:{x:int,y:int,z:int,color:string}) = x; System.Control.Profile.profileOn(); don 1000000 Xval {x=100, y=200, z=10, color = "Green"}; System.Control.Profile.profileOff(); System.Control.Profile.report std_out; The result: Standard ML of New Jersey, Version 75, November 11, 1991 Arrays have changed; see Release Notes val it = () : unit - use "test2.sml"; ........ %time cumsecs #call ms/call name 96.78 20.50 1000000 .0051 Xval 2.73 21.08 0 (toplevel) .47 21.18 0 (gc) .00 21.18 0 (unprofiled) (b) In SML# of Kansai Source code: fun don n f x = if n = 1 then f x else (f x;don (n - 1) f x); System.Control.Profile.profiling := true; fun polyXval {x,...} = x; System.Control.Profile.profileOn(); don 1000000 polyXval {x=100, y=200, z=10, color = "Green"}; System.Control.Profile.profileOff(); System.Control.Profile.report std_out; The result: % sml# Standard ML# of Kansai, Version 0-75, December 24, 1992 Based on Standard ML of New Jersey, Version 75. val it = () : unit - use "test.sml"; ........ %time cumsecs #call ms/call name 96.55 20.74 1000000 .0051 polyXval.anon 3.07 21.40 0 (toplevel) .27 21.46 0 (gc) .09 21.48 0 (unprofiled) .00 21.48 1 .0000 polyXval (See also (3) in SOME WEAKNESSES OF THE CURRENT VERSION below.) SYNTAX OF SML#. It is the same as Standard ML except: (1) Flexible record patters (and the derived form of #label) are now first-class patterns, and can therefore used without type constraints, as explained above. (2) The expression constructor of the form #> exp => {lab1=exp1,---,labn=expn} is added. (The sequence #> is now a reserved word and cannot be used as an identifier.) (3) A type variable can be constrained with a record kind by the syntax: 'a # {label_1:type_1,---,label_n:type_n,....} The trailing "..." is optional. HOW TO BUILD THE SYSTEM For sun4 under sunos, use the binary file sml#sun4.Z, which is an executable interactive system of SML#. For other machines, compile the system just the same way as SML of NJ using src.sml#.tar, which is a tar file of src directory. When compilation is done, build the desired system by using makeml# file (in src directory) instead of the standard makeml. SOME WEAKNESSES OF THE CURRENT VERSION (1). Some Observable Difference from Standard ML. Since SML# insert extra function abstraction for program that has a type containing a kinded type variable of the form 'a#{...}, the evaluation of such a program is delayed until it is used. Because of this, a program that causes side effect and returns a polymorphic function on record may behave differently form in Standard ML. Here is a simple example. val f = (print 1;fn {x,...} => x); The "1" is printed not the time f is defined but when(ever) f is used. (2). Module Signature Matching Module signature matching is not yet refined to deal with kinded type variables. (It is, however, sound. In the current implementation, signature match fails when an actual type of some val declaration of a module contains a kinded type variables. ) (3). Optimization. The current implementation does not produce an optimal code in term of the number of index abstractions and index applications. In particular, those programs that involves bindings of structured values containing polymorphic field access, and deeply nested let abstraction of kinded type variables are tend to be less efficient than they should be. As an example of the latter, in the follwoing program, fun f {x,...} = x; fun g x = f x; g {x=1,y=2}; the last application requires two additional function applications to pass the index value (1 in this case) to g and then to f. In the future release, I intend to optimize the compiler so that the number of the additional function application is always 1, using a technique of partial evaluation. ACKNOWLEDGMENTS I am very grateful to Peter Buneman and Department of Computer and Information Science, University of Pennsylvania for allowing me to place this software in its ftp directory. DISCLAIMER I shall in no event be liable for any special, indirect or consequential damages or any damages whatsoever resulting from loss of use, data or profits, whether in an action of contract, negligence or other tortious action, arising out of or in connection with the use or performance of this software.