<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">
<title>ArrayLiteral - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">
<link rel="Start" href="Home">
</head>
<body lang="en" dir="ltr">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
<tr>
<td style = "
border: 0px;
color: darkblue;
font-size: 150%;
text-align: left;">
<a class = mltona href="Home">MLton MLTONWIKIVERSION</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
ArrayLiteral
<td style = "
border: 0px;
text-align: right;">
<table cellspacing = 0 style = "border: 0px">
<tr style = "vertical-align: middle;">
</table>
<tr style = "background-color: white;">
<td colspan = 3
style = "
border: 0px;
font-size:70%;
text-align: right;">
<a href = "Home">Home</a>
<a href = "TitleIndex">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
<a href="StandardML">Standard ML</a> does not have a syntax for array literals or vector literals. The only way to write down an array is like
<pre class=code>
Array.fromList [w, x, y, z]
</PRE>
<p>
</p>
<p>
No SML compiler produces efficient code for the above expression. The generated code allocates a list and then converts it to an array. To alleviate this, one could write down the same array using <tt>Array.tabulate</tt>, or even using <tt>Array.array</tt> and <tt>Array.update</tt>, but that is syntactically unwieldy.
</p>
<p>
Fortunately, using <a href="Fold">Fold</a>, it is possible to define constants <tt>A</tt>, and <tt>`</tt> so that one can write down an array like:
</p>
<pre class=code>
A `w `x `y `z $
</PRE>
<p>
</p>
<p>
This is as syntactically concise as the <tt>fromList</tt> expression. Furthermore, MLton, at least, will generate the efficient code as if one had written down a use of <tt>Array.array</tt> followed by four uses of <tt>Array.update</tt>.
</p>
<p>
Along with <tt>A</tt> and <tt>`</tt>, one can define a constant <tt>V</tt> that makes it possible to define vector literals with the same syntax, e.g.,
</p>
<pre class=code>
V `w `x `y `z $
</PRE>
<p>
</p>
<p>
Note that the same element indicator, <tt>`</tt>, serves for both array and vector literals. Of course, the <tt>$</tt> is the end-of-arguments marker always used with <a href="Fold">Fold</a>. The only difference between an array literal and vector literal is the <tt>A</tt> or <tt>V</tt> at the beginning.
</p>
<p>
Here is the implementation of <tt>A</tt>, <tt>V</tt>, and <tt>`</tt>. We place them in a structure and use signature abstraction to hide the type of the accumulator. See <a href="Fold">Fold</a> for more on this technique.
</p>
<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> Literal:>
<B><FONT COLOR="#0000FF">sig</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> 'a z
</FONT></B><B><FONT COLOR="#A020F0">val</FONT></B> A: ('a z, 'a z, 'a array, 'd) Fold.t
<B><FONT COLOR="#A020F0">val</FONT></B> V: ('a z, 'a z, 'a vector, 'd) Fold.t
<B><FONT COLOR="#A020F0">val</FONT></B> ` : ('a, 'a z, 'a z, 'b, 'c, 'd) Fold.step1
<B><FONT COLOR="#0000FF">end</FONT></B> =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> 'a z </FONT></B>=<B><FONT COLOR="#228B22"> int * 'a option * ('a array -> unit)
</FONT></B><B><FONT COLOR="#A020F0">val</FONT></B> A =
<B><FONT COLOR="#A020F0">fn</FONT></B> z =>
Fold.fold
((<B><FONT COLOR="#5F9EA0">0</FONT></B>, NONE, ignore),
<B><FONT COLOR="#A020F0">fn</FONT></B> (n, opt, fill) =>
<B><FONT COLOR="#A020F0">case</FONT></B> opt <B><FONT COLOR="#A020F0">of</FONT></B>
NONE =>
Array.tabulate (<B><FONT COLOR="#5F9EA0">0</FONT></B>, <B><FONT COLOR="#A020F0">fn</FONT></B> _ => <B><FONT COLOR="#A020F0">raise</FONT></B> Fail <B><FONT COLOR="#BC8F8F">"array0"</FONT></B>)
| SOME x =>
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> a = Array.array (n, x)
<B><FONT COLOR="#A020F0">val</FONT></B> () = fill a
<B><FONT COLOR="#A020F0">in</FONT></B>
a
<B><FONT COLOR="#A020F0">end</FONT></B>)
z
<B><FONT COLOR="#A020F0">val</FONT></B> V = <B><FONT COLOR="#A020F0">fn</FONT></B> z => Fold.post (A, Array.vector) z
<B><FONT COLOR="#A020F0">val</FONT></B> ` =
<B><FONT COLOR="#A020F0">fn</FONT></B> z =>
Fold.step1
(<B><FONT COLOR="#A020F0">fn</FONT></B> (x, (i, opt, fill)) =>
(i + <B><FONT COLOR="#5F9EA0">1</FONT></B>,
SOME x,
<B><FONT COLOR="#A020F0">fn</FONT></B> a => (Array.update (a, i, x); fill a)))
z
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
</p>
<p>
The idea of the code is for the fold to accumulate a count of the number of elements, a sample element, and a function that fills in all the elements. When the fold is complete, the finishing function allocates the array, applies the fill function, and returns the array. The only difference between <tt>A</tt> and <tt>V</tt> is at the very end; <tt>A</tt> just returns the array, while <tt>V</tt> converts it to a vector using post-composition, which is further described on the <a href="Fold">Fold</a> page.
</p>
</div>
<p>
<hr>
Last edited on 2007-08-15 22:05:16 by <span title="fenrir.uchicago.edu"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
