ParaSail (programming language)
- 11 min read
- 2 chapters
Related on Lably
Through Object-oriented programming, Object (computer science) and Syntax
ParaSail uses a pointer-free programming model, where objects can grow and shrink, and value semantics are used for assignment. It has no global garbage collected heap. Instead, region-based memory management is used throughout. Types can be recursive, so long as the recursive components are declared optional. There are no global variables, no parameter aliasing, and all subexpressions of an expression can be evaluated in parallel. Assertions, preconditions, postconditions, class invariants, etc., are part of the standard syntax, using a Hoare-like notation. Any possible race conditions are detected at compile time.
Initial design of ParaSail began in September 2009, by S. Tucker Taft.
Both an interpreter using the ParaSail virtual machine, and an LLVM-based ParaSail compiler are available. Work stealing is used for scheduling ParaSail's light-weight threads. The latest version can be downloaded from the ParaSail website.
Description
The syntax of ParaSail is similar to Modula, but with a class-and-interface-based object-oriented programming model more similar to Java or C#.
More recently, the parallel constructs of ParaSail have been adapted to other syntaxes, to produce Java-like, Python-like, and Ada-like parallel languages, dubbed, respectively, Javallel, Parython, and Sparkel (named after the Ada subset SPARK on which it is based). Compilers and interpreters for these languages are included with the ParaSail implementation.
Sign in to keep reading
One more chapter is free with a Lably account.
Examples
The following is a Hello world program in ParaSail:
<span id="mwRA"></span><span class="kr" id="mwRQ">func</span> <span class="n" id="mwRg">Hello_World</span><span class="p" id="mwRw">(</span><span class="kr" id="mwSA">var</span> <span class="n" id="mwSQ">IO</span><span class="p" id="mwSg">)</span> <span class="kr" id="mwSw">is</span> <span class="n" id="mwTA">IO</span><span class="p" id="mwTQ">.</span><span class="n" id="mwTg">Println</span><span class="p" id="mwTw">(</span><span class="s" id="mwUA">"Hello, World"</span><span class="p" id="mwUQ">);</span> <span class="kr" id="mwUg">end</span> <span class="kr" id="mwUw">func</span> <span class="n" id="mwVA">Hello_World</span><span class="p" id="mwVQ">;</span>
The following is an interface to a basic map module:
<span id="mwWQ"></span><span class="kr" id="mwWg">interface</span> <span class="n" id="mwWw">BMap</span><span class="p" id="mwXA"><</span><span class="n" id="mwXQ">Key_Type</span> <span class="kr" id="mwXg">is</span> <span class="n" id="mwXw">Ordered</span><span class="p" id="mwYA"><>;</span> <span class="n" id="mwYQ">Element_Type</span> <span class="kr" id="mwYg">is</span> <span class="n" id="mwYw">Assignable</span><span class="p" id="mwZA"><</span><span class="o" id="mwZQ">>></span> <span class="kr" id="mwZg">is</span> <span class="kr" id="mwZw">op</span> <span class="s" id="mwaA">"[]"</span><span class="p" id="mwaQ">()</span> <span class="o" id="mwag">-</span><span class="p" id="mwaw">></span> <span class="n" id="mwbA">BMap</span><span class="p" id="mwbQ">;</span> <span class="c1" id="mwbg">// Create an empty map</span> <span class="kr" id="mwbw">func</span> <span class="n" id="mwcA">Insert</span><span class="p" id="mwcQ">(</span><span class="kr" id="mwcg">var</span> <span class="n" id="mwcw">BMap</span><span class="p" id="mwdA">;</span> <span class="n" id="mwdQ">Key</span> <span class="p" id="mwdg">:</span> <span class="n" id="mwdw">Key_Type</span><span class="p" id="mweA">;</span> <span class="n" id="mweQ">Value</span> <span class="p" id="mweg">:</span> <span class="n" id="mwew">Element_Type</span><span class="p" id="mwfA">);</span> <span class="kr" id="mwfQ">func</span> <span class="n" id="mwfg">Find</span><span class="p" id="mwfw">(</span><span class="n" id="mwgA">BMap</span><span class="p" id="mwgQ">;</span> <span class="n" id="mwgg">Key</span> <span class="p" id="mwgw">:</span> <span class="n" id="mwhA">Key_Type</span><span class="p" id="mwhQ">)</span> <span class="o" id="mwhg">-</span><span class="p" id="mwhw">></span> <span class="kr" id="mwiA">optional</span> <span class="n" id="mwiQ">Element_Type</span><span class="p" id="mwig">;</span> <span class="kr" id="mwiw">func</span> <span class="n" id="mwjA">Delete</span><span class="p" id="mwjQ">(</span><span class="kr" id="mwjg">var</span> <span class="n" id="mwjw">BMap</span><span class="p" id="mwkA">;</span> <span class="n" id="mwkQ">Key</span> <span class="p" id="mwkg">:</span> <span class="n" id="mwkw">Key_Type</span><span class="p" id="mwlA">);</span> <span class="kr" id="mwlQ">func</span> <span class="n" id="mwlg">Count</span><span class="p" id="mwlw">(</span><span class="n" id="mwmA">BMap</span><span class="p" id="mwmQ">)</span> <span class="o" id="mwmg">-</span><span class="p" id="mwmw">></span> <span class="n" id="mwnA">Univ_Integer</span><span class="p" id="mwnQ">;</span> <span class="kr" id="mwng">end</span> <span class="kr" id="mwnw">interface</span> <span class="n" id="mwoA">BMap</span><span class="p" id="mwoQ">;</span>
Here is a possible implementation of this map module, using a binary tree:
<span id="mwpQ"></span><span class="kr" id="mwpg">class</span> <span class="n" id="mwpw">BMap</span> <span class="kr" id="mwqA">is</span> <span class="kr" id="mwqQ">interface</span> <span class="n" id="mwqg">Binary_Node</span><span class="p" id="mwqw"><></span> <span class="kr" id="mwrA">is</span> <span class="c1" id="mwrQ">// A simple "concrete" binary node module</span> <span class="kr" id="mwrg">var</span> <span class="n" id="mwrw">Left</span> <span class="p" id="mwsA">:</span> <span class="kr" id="mwsQ">optional</span> <span class="n" id="mwsg">Binary_Node</span><span class="p" id="mwsw">;</span> <span class="kr" id="mwtA">var</span> <span class="n" id="mwtQ">Right</span> <span class="p" id="mwtg">:</span> <span class="kr" id="mwtw">optional</span> <span class="n" id="mwuA">Binary_Node</span><span class="p" id="mwuQ">;</span> <span class="kr" id="mwug">const</span> <span class="n" id="mwuw">Key</span> <span class="p" id="mwvA">:</span> <span class="n" id="mwvQ">Key_Type</span><span class="p" id="mwvg">;</span> <span class="kr" id="mwvw">var</span> <span class="n" id="mwwA">Value</span> <span class="p" id="mwwQ">:</span> <span class="kr" id="mwwg">optional</span> <span class="n" id="mwww">Element_Type</span><span class="p" id="mwxA">;</span> <span class="c1" id="mwxQ">// null means deleted</span> <span class="kr" id="mwxg">end</span> <span class="kr" id="mwxw">interface</span> <span class="n" id="mwyA">Binary_Node</span><span class="p" id="mwyQ">;</span> <span class="kr" id="mwyg">var</span> <span class="n" id="mwyw">Tree</span> <span class="p" id="mwzA">:</span> <span class="kr" id="mwzQ">optional</span> <span class="n" id="mwzg">Binary_Node</span><span class="p" id="mwzw">;</span> <span class="kr" id="mw0A">var</span> <span class="n" id="mw0Q">Count</span> <span class="o" id="mw0g">:=</span> <span class="mi" id="mw0w">0</span><span class="p" id="mw1A">;</span> <span class="kr" id="mw1Q">exports</span> <span class="kr" id="mw1g">op</span> <span class="s" id="mw1w">"[]"</span><span class="p" id="mw2A">()</span> <span class="o" id="mw2Q">-</span><span class="p" id="mw2g">></span> <span class="n" id="mw2w">BMap</span> <span class="kr" id="mw3A">is</span> <span class="c1" id="mw3Q">// Create an empty map</span> <span class="kr" id="mw3g">return</span> <span class="p" id="mw3w">(</span><span class="n" id="mw4A">Tree</span> <span class="o" id="mw4Q">=></span> <span class="kr" id="mw4g">null</span><span class="p" id="mw4w">,</span> <span class="n" id="mw5A">Count</span> <span class="o" id="mw5Q">=></span> <span class="mi" id="mw5g">0</span><span class="p" id="mw5w">);</span> <span class="kr" id="mw6A">end</span> <span class="kr" id="mw6Q">op</span> <span class="s" id="mw6g">"[]"</span><span class="p" id="mw6w">;</span> <span class="kr" id="mw7A">func</span> <span class="n" id="mw7Q">Insert</span><span class="p" id="mw7g">(</span><span class="kr" id="mw7w">var</span> <span class="n" id="mw8A">BMap</span><span class="p" id="mw8Q">;</span> <span class="n" id="mw8g">Key</span> <span class="p" id="mw8w">:</span> <span class="n" id="mw9A">Key_Type</span><span class="p" id="mw9Q">;</span> <span class="n" id="mw9g">Value</span> <span class="p" id="mw9w">:</span> <span class="n" id="mw-A">Element_Type</span><span class="p" id="mw-Q">)</span> <span class="kr" id="mw-g">is</span> <span class="c1" id="mw-w">// Search for Key, overwrite if found, insert new node if not</span> <span class="kr" id="mw_A">for</span> <span class="n" id="mw_Q">M</span> <span class="o" id="mw_g">=></span> <span class="n" id="mw_w">BMap</span><span class="p" id="mwAQA">.</span><span class="n" id="mwAQE">Tree</span> <span class="kr" id="mwAQI">loop</span> <span class="kr" id="mwAQM">if</span> <span class="n" id="mwAQQ">M</span> <span class="ow" id="mwAQU">is null</span> <span class="kr" id="mwAQY">then</span> <span class="c1" id="mwAQc">// Not already in the map; add it</span> <span class="n" id="mwAQg">M</span> <span class="o" id="mwAQk">:=</span> <span class="p" id="mwAQo">(</span><span class="n" id="mwAQs">Key</span> <span class="o" id="mwAQw">=></span> <span class="n" id="mwAQ0">Key</span><span class="p" id="mwAQ4">,</span> <span class="n" id="mwAQ8">Value</span> <span class="o" id="mwARA">=></span> <span class="n" id="mwARE">Value</span><span class="p" id="mwARI">,</span> <span class="n" id="mwARM">Left</span> <span class="o" id="mwARQ">=></span> <span class="kr" id="mwARU">null</span><span class="p" id="mwARY">,</span> <span class="n" id="mwARc">Right</span> <span class="o" id="mwARg">=></span> <span class="kr" id="mwARk">null</span><span class="p" id="mwARo">);</span> <span class="n" id="mwARs">BMap</span><span class="p" id="mwARw">.</span><span class="n" id="mwAR0">Count</span> <span class="o" id="mwAR4">+=</span> <span class="mi" id="mwAR8">1</span><span class="p" id="mwASA">;</span> <span class="kr" id="mwASE">else</span> <span class="kr" id="mwASI">case</span> <span class="n" id="mwASM">Key</span> <span class="o" id="mwASQ">=?</span> <span class="n" id="mwASU">M</span><span class="p" id="mwASY">.</span><span class="n" id="mwASc">Key</span> <span class="kr" id="mwASg">of</span> <span class="p" id="mwASk">[</span><span class="l" id="mwASo">#less</span><span class="p" id="mwASs">]</span> <span class="o" id="mwASw">=></span> <span class="kr" id="mwAS0">continue</span> <span class="kr" id="mwAS4">loop</span> <span class="kr" id="mwAS8">with</span> <span class="n" id="mwATA">M</span><span class="p" id="mwATE">.</span><span class="n" id="mwATI">Left</span><span class="p" id="mwATM">;</span> <span class="p" id="mwATQ">[</span><span class="l" id="mwATU">#greater</span><span class="p" id="mwATY">]</span> <span class="o" id="mwATc">=></span> <span class="kr" id="mwATg">continue</span> <span class="kr" id="mwATk">loop</span> <span class="kr" id="mwATo">with</span> <span class="n" id="mwATs">M</span><span class="p" id="mwATw">.</span><span class="n" id="mwAT0">Right</span><span class="p" id="mwAT4">;</span> <span class="p" id="mwAT8">[</span><span class="l" id="mwAUA">#equal</span><span class="p" id="mwAUE">]</span> <span class="o" id="mwAUI">=></span> <span class="c1" id="mwAUM">// Key is already in the map;</span> <span class="c1" id="mwAUQ">// bump count if Value was null;</span> <span class="kr" id="mwAUU">if</span> <span class="n" id="mwAUY">M</span><span class="p" id="mwAUc">.</span><span class="n" id="mwAUg">Value</span> <span class="ow" id="mwAUk">is null</span> <span class="kr" id="mwAUo">then</span> <span class="n" id="mwAUs">BMap</span><span class="p" id="mwAUw">.</span><span class="n" id="mwAU0">Count</span> <span class="o" id="mwAU4">+=</span> <span class="mi" id="mwAU8">1</span><span class="p" id="mwAVA">;</span> <span class="kr" id="mwAVE">end</span> <span class="kr" id="mwAVI">if</span><span class="p" id="mwAVM">;</span> <span class="c1" id="mwAVQ">// in any case overwrite the Value field</span> <span class="n" id="mwAVU">M</span><span class="p" id="mwAVY">.</span><span class="n" id="mwAVc">Value</span> <span class="o" id="mwAVg">:=</span> <span class="n" id="mwAVk">Value</span><span class="p" id="mwAVo">;</span> <span class="kr" id="mwAVs">return</span><span class="p" id="mwAVw">;</span> <span class="kr" id="mwAV0">end</span> <span class="kr" id="mwAV4">case</span><span class="p" id="mwAV8">;</span> <span class="kr" id="mwAWA">end</span> <span class="kr" id="mwAWE">if</span><span class="p" id="mwAWI">;</span> <span class="kr" id="mwAWM">end</span> <span class="kr" id="mwAWQ">loop</span><span class="p" id="mwAWU">;</span> <span class="kr" id="mwAWY">end</span> <span class="kr" id="mwAWc">func</span> <span class="n" id="mwAWg">Insert</span><span class="p" id="mwAWk">;</span> <span class="kr" id="mwAWo">func</span> <span class="n" id="mwAWs">Find</span><span class="p" id="mwAWw">(</span><span class="n" id="mwAW0">BMap</span><span class="p" id="mwAW4">;</span> <span class="n" id="mwAW8">Key</span> <span class="p" id="mwAXA">:</span> <span class="n" id="mwAXE">Key_Type</span><span class="p" id="mwAXI">)</span> <span class="o" id="mwAXM">-</span><span class="p" id="mwAXQ">></span> <span class="kr" id="mwAXU">optional</span> <span class="n" id="mwAXY">Element_Type</span> <span class="kr" id="mwAXc">is</span> <span class="c1" id="mwAXg">// Search for Key, return associated Value if present, or null otherwise</span> <span class="kr" id="mwAXk">for</span> <span class="n" id="mwAXo">M</span> <span class="o" id="mwAXs">=></span> <span class="n" id="mwAXw">BMap</span><span class="p" id="mwAX0">.</span><span class="n" id="mwAX4">Tree</span> <span class="kr" id="mwAX8">while</span> <span class="n" id="mwAYA">M</span> <span class="ow" id="mwAYE">not null</span> <span class="kr" id="mwAYI">loop</span> <span class="kr" id="mwAYM">case</span> <span class="n" id="mwAYQ">Key</span> <span class="o" id="mwAYU">=?</span> <span class="n" id="mwAYY">M</span><span class="p" id="mwAYc">.</span><span class="n" id="mwAYg">Key</span> <span class="kr" id="mwAYk">of</span> <span class="p" id="mwAYo">[</span><span class="l" id="mwAYs">#less</span><span class="p" id="mwAYw">]</span> <span class="o" id="mwAY0">=></span> <span class="kr" id="mwAY4">continue</span> <span class="kr" id="mwAY8">loop</span> <span class="kr" id="mwAZA">with</span> <span class="n" id="mwAZE">M</span><span class="p" id="mwAZI">.</span><span class="n" id="mwAZM">Left</span><span class="p" id="mwAZQ">;</span> <span class="p" id="mwAZU">[</span><span class="l" id="mwAZY">#greater</span><span class="p" id="mwAZc">]</span> <span class="o" id="mwAZg">=></span> <span class="kr" id="mwAZk">continue</span> <span class="kr" id="mwAZo">loop</span> <span class="kr" id="mwAZs">with</span> <span class="n" id="mwAZw">M</span><span class="p" id="mwAZ0">.</span><span class="n" id="mwAZ4">Right</span><span class="p" id="mwAZ8">;</span> <span class="p" id="mwAaA">[</span><span class="l" id="mwAaE">#equal</span><span class="p" id="mwAaI">]</span> <span class="o" id="mwAaM">=></span> <span class="c1" id="mwAaQ">// Found it; return the value</span> <span class="kr" id="mwAaU">return</span> <span class="n" id="mwAaY">M</span><span class="p" id="mwAac">.</span><span class="n" id="mwAag">Value</span><span class="p" id="mwAak">;</span> <span class="kr" id="mwAao">end</span> <span class="kr" id="mwAas">case</span><span class="p" id="mwAaw">;</span> <span class="kr" id="mwAa0">end</span> <span class="kr" id="mwAa4">loop</span><span class="p" id="mwAa8">;</span> <span class="c1" id="mwAbA">// Not found in BMap</span> <span class="kr" id="mwAbE">return</span> <span class="kr" id="mwAbI">null</span><span class="p" id="mwAbM">;</span> <span class="kr" id="mwAbQ">end</span> <span class="kr" id="mwAbU">func</span> <span class="n" id="mwAbY">Find</span><span class="p" id="mwAbc">;</span> <span class="kr" id="mwAbg">func</span> <span class="n" id="mwAbk">Delete</span><span class="p" id="mwAbo">(</span><span class="kr" id="mwAbs">var</span> <span class="n" id="mwAbw">BMap</span><span class="p" id="mwAb0">;</span> <span class="n" id="mwAb4">Key</span> <span class="p" id="mwAb8">:</span> <span class="n" id="mwAcA">Key_Type</span><span class="p" id="mwAcE">)</span> <span class="kr" id="mwAcI">is</span> <span class="c1" id="mwAcM">// Search for Key; delete associated node if found</span> <span class="kr" id="mwAcQ">for</span> <span class="n" id="mwAcU">M</span> <span class="o" id="mwAcY">=></span> <span class="n" id="mwAcc">BMap</span><span class="p" id="mwAcg">.</span><span class="n" id="mwAck">Tree</span> <span class="kr" id="mwAco">while</span> <span class="n" id="mwAcs">M</span> <span class="ow" id="mwAcw">not null</span> <span class="kr" id="mwAc0">loop</span> <span class="kr" id="mwAc4">case</span> <span class="n" id="mwAc8">Key</span> <span class="o" id="mwAdA">=?</span> <span class="n" id="mwAdE">M</span><span class="p" id="mwAdI">.</span><span class="n" id="mwAdM">Key</span> <span class="kr" id="mwAdQ">of</span> <span class="p" id="mwAdU">[</span><span class="l" id="mwAdY">#less</span><span class="p" id="mwAdc">]</span> <span class="o" id="mwAdg">=></span> <span class="kr" id="mwAdk">continue</span> <span class="kr" id="mwAdo">loop</span> <span class="kr" id="mwAds">with</span> <span class="n" id="mwAdw">M</span><span class="p" id="mwAd0">.</span><span class="n" id="mwAd4">Left</span><span class="p" id="mwAd8">;</span> <span class="p" id="mwAeA">[</span><span class="l" id="mwAeE">#greater</span><span class="p" id="mwAeI">]</span> <span class="o" id="mwAeM">=></span> <span class="kr" id="mwAeQ">continue</span> <span class="kr" id="mwAeU">loop</span> <span class="kr" id="mwAeY">with</span> <span class="n" id="mwAec">M</span><span class="p" id="mwAeg">.</span><span class="n" id="mwAek">Right</span><span class="p" id="mwAeo">;</span> <span class="p" id="mwAes">[</span><span class="l" id="mwAew">#equal</span><span class="p" id="mwAe0">]</span> <span class="o" id="mwAe4">=></span> <span class="c1" id="mwAe8">// Found it; if at most one subtree is non-null, overwrite</span> <span class="c1" id="mwAfA">// it; otherwise, set its value field to null</span> <span class="c1" id="mwAfE">// (to avoid a more complex re-balancing).</span> <span class="kr" id="mwAfI">if</span> <span class="n" id="mwAfM">M</span><span class="p" id="mwAfQ">.</span><span class="n" id="mwAfU">Left</span> <span class="ow" id="mwAfY">is null</span> <span class="kr" id="mwAfc">then</span> <span class="c1" id="mwAfg">// Move right subtree into M</span> <span class="n" id="mwAfk">M</span> <span class="o" id="mwAfo"><==</span> <span class="n" id="mwAfs">M</span><span class="p" id="mwAfw">.</span><span class="n" id="mwAf0">Right</span><span class="p" id="mwAf4">;</span> <span class="kr" id="mwAf8">elsif</span> <span class="n" id="mwAgA">M</span><span class="p" id="mwAgE">.</span><span class="n" id="mwAgI">Right</span> <span class="ow" id="mwAgM">is null</span> <span class="kr" id="mwAgQ">then</span> <span class="c1" id="mwAgU">// Move left subtree into M</span> <span class="n" id="mwAgY">M</span> <span class="o" id="mwAgc"><==</span> <span class="n" id="mwAgg">M</span><span class="p" id="mwAgk">.</span><span class="n" id="mwAgo">Left</span><span class="p" id="mwAgs">;</span> <span class="kr" id="mwAgw">else</span> <span class="c1" id="mwAg0">// Cannot immediately reclaim node;</span> <span class="c1" id="mwAg4">// set value field to null instead.</span> <span class="n" id="mwAg8">M</span><span class="p" id="mwAhA">.</span><span class="n" id="mwAhE">Value</span> <span class="o" id="mwAhI">:=</span> <span class="kr" id="mwAhM">null</span><span class="p" id="mwAhQ">;</span> <span class="kr" id="mwAhU">end</span> <span class="kr" id="mwAhY">if</span><span class="p" id="mwAhc">;</span> <span class="c1" id="mwAhg">// Decrement count</span> <span class="n" id="mwAhk">BMap</span><span class="p" id="mwAho">.</span><span class="n" id="mwAhs">Count</span> <span class="o" id="mwAhw">-=</span> <span class="mi" id="mwAh0">1</span><span class="p" id="mwAh4">;</span> <span class="kr" id="mwAh8">end</span> <span class="kr" id="mwAiA">case</span><span class="p" id="mwAiE">;</span> <span class="kr" id="mwAiI">end</span> <span class="kr" id="mwAiM">loop</span><span class="p" id="mwAiQ">;</span> <span class="c1" id="mwAiU">// Not found in the map</span> <span class="kr" id="mwAiY">end</span> <span class="kr" id="mwAic">func</span> <span class="n" id="mwAig">Delete</span><span class="p" id="mwAik">;</span> <span class="kr" id="mwAio">func</span> <span class="n" id="mwAis">Count</span><span class="p" id="mwAiw">(</span><span class="n" id="mwAi0">BMap</span><span class="p" id="mwAi4">)</span> <span class="o" id="mwAi8">-</span><span class="p" id="mwAjA">></span> <span class="n" id="mwAjE">Univ_Integer</span> <span class="kr" id="mwAjI">is</span> <span class="c1" id="mwAjM">// Return count of number of items in map</span> <span class="kr" id="mwAjQ">return</span> <span class="n" id="mwAjU">BMap</span><span class="p" id="mwAjY">.</span><span class="n" id="mwAjc">Count</span><span class="p" id="mwAjg">;</span> <span class="kr" id="mwAjk">end</span> <span class="kr" id="mwAjo">func</span> <span class="n" id="mwAjs">Count</span><span class="p" id="mwAjw">;</span> <span class="kr" id="mwAj0">end</span> <span class="kr" id="mwAj4">class</span> <span class="n" id="mwAj8">BMap</span><span class="p" id="mwAkA">;</span>
Here is a simple test program for the BMap module:
<span id="mwAkQ"></span><span class="kr" id="mwAkU">import</span> <span class="n" id="mwAkY">PSL</span><span class="p" id="mwAkc">::</span><span class="n" id="mwAkg">Core</span><span class="p" id="mwAkk">::</span><span class="n" id="mwAko">Random</span><span class="p" id="mwAks">;</span> <span class="kr" id="mwAkw">import</span> <span class="n" id="mwAk0">BMap</span><span class="p" id="mwAk4">;</span> <span class="kr" id="mwAk8">func</span> <span class="n" id="mwAlA">Test_BMap</span><span class="p" id="mwAlE">(</span><span class="n" id="mwAlI">Num</span> <span class="p" id="mwAlM">:</span> <span class="n" id="mwAlQ">Univ_Integer</span><span class="p" id="mwAlU">;</span> <span class="n" id="mwAlY">Seed</span> <span class="p" id="mwAlc">:</span> <span class="n" id="mwAlg">Univ_Integer</span><span class="p" id="mwAlk">)</span> <span class="kr" id="mwAlo">is</span> <span class="c1" id="mwAls">// Test the Binary-Tree-based Map</span> <span class="kr" id="mwAlw">var</span> <span class="n" id="mwAl0">Ran</span> <span class="p" id="mwAl4">:</span> <span class="n" id="mwAl8">Random</span> <span class="o" id="mwAmA">:=</span> <span class="n" id="mwAmE">Start</span><span class="p" id="mwAmI">(</span><span class="n" id="mwAmM">Seed</span><span class="p" id="mwAmQ">);</span> <span class="c1" id="mwAmU">// Start a random-number sequence</span> <span class="c1" id="mwAmY">// Declare a map from integers to strings</span> <span class="kr" id="mwAmc">var</span> <span class="n" id="mwAmg">M</span> <span class="p" id="mwAmk">:</span> <span class="n" id="mwAmo">BMap</span><span class="p" id="mwAms"><</span><span class="n" id="mwAmw">Key_Type</span> <span class="o" id="mwAm0">=></span> <span class="n" id="mwAm4">Univ_Integer</span><span class="p" id="mwAm8">,</span> <span class="n" id="mwAnA">Element_Type</span> <span class="o" id="mwAnE">=></span> <span class="n" id="mwAnI">Univ_String</span><span class="p" id="mwAnM">>;</span> <span class="n" id="mwAnQ">M</span> <span class="o" id="mwAnU">:=</span> <span class="p" id="mwAnY">[];</span> <span class="c1" id="mwAnc">// Initialize the map to the empty map</span> <span class="kr" id="mwAng">for</span> <span class="n" id="mwAnk">I</span> <span class="kr" id="mwAno">in</span> <span class="mi" id="mwAns">1</span><span class="o" id="mwAnw">..</span><span class="n" id="mwAn0">Num</span><span class="o" id="mwAn4">*</span><span class="mi" id="mwAn8">2</span> <span class="kr" id="mwAoA">forward</span> <span class="kr" id="mwAoE">loop</span> <span class="c1" id="mwAoI">// Add elements to the map</span> <span class="kr" id="mwAoM">const</span> <span class="n" id="mwAoQ">Key</span> <span class="o" id="mwAoU">:=</span> <span class="n" id="mwAoY">Next</span><span class="p" id="mwAoc">(</span><span class="n" id="mwAog">Ran</span><span class="p" id="mwAok">)</span> <span class="ow" id="mwAoo">mod</span> <span class="n" id="mwAos">Num</span> <span class="o" id="mwAow">+</span> <span class="mi" id="mwAo0">1</span><span class="p" id="mwAo4">;</span> <span class="kr" id="mwAo8">const</span> <span class="n" id="mwApA">Val</span> <span class="o" id="mwApE">:=</span> <span class="s" id="mwApI">"Val"</span> <span class="o" id="mwApM">|</span> <span class="n" id="mwApQ">To_String</span><span class="p" id="mwApU">(</span><span class="n" id="mwApY">I</span><span class="p" id="mwApc">);</span> <span class="n" id="mwApg">Println</span><span class="p" id="mwApk">(</span><span class="s" id="mwApo">"About to insert "</span> <span class="o" id="mwAps">|</span> <span class="n" id="mwApw">Key</span> <span class="o" id="mwAp0">|</span> <span class="s" id="mwAp4">" => "</span> <span class="o" id="mwAp8">|</span> <span class="n" id="mwAqA">Val</span><span class="p" id="mwAqE">);</span> <span class="n" id="mwAqI">Insert</span><span class="p" id="mwAqM">(</span><span class="n" id="mwAqQ">M</span><span class="p" id="mwAqU">,</span> <span class="n" id="mwAqY">Key</span><span class="p" id="mwAqc">,</span> <span class="n" id="mwAqg">Val</span><span class="p" id="mwAqk">);</span> <span class="kr" id="mwAqo">end</span> <span class="kr" id="mwAqs">loop</span><span class="p" id="mwAqw">;</span> <span class="n" id="mwAq0">Println</span><span class="p" id="mwAq4">(</span><span class="s" id="mwAq8">"Count = "</span> <span class="o" id="mwArA">|</span> <span class="n" id="mwArE">Count</span><span class="p" id="mwArI">(</span><span class="n" id="mwArM">M</span><span class="p" id="mwArQ">));</span> <span class="kr" id="mwArU">for</span> <span class="n" id="mwArY">I</span> <span class="kr" id="mwArc">in</span> <span class="mi" id="mwArg">1</span><span class="o" id="mwArk">..</span><span class="n" id="mwAro">Num</span> <span class="kr" id="mwArs">loop</span> <span class="c1" id="mwArw">// Search for elements in the map</span> <span class="kr" id="mwAr0">const</span> <span class="n" id="mwAr4">Key</span> <span class="o" id="mwAr8">:=</span> <span class="n" id="mwAsA">Next</span><span class="p" id="mwAsE">(</span><span class="n" id="mwAsI">Ran</span><span class="p" id="mwAsM">)</span> <span class="ow" id="mwAsQ">mod</span> <span class="n" id="mwAsU">Num</span> <span class="o" id="mwAsY">+</span> <span class="mi" id="mwAsc">1</span><span class="p" id="mwAsg">;</span> <span class="n" id="mwAsk">Println</span><span class="p" id="mwAso">(</span><span class="s" id="mwAss">"Looking for "</span> <span class="o" id="mwAsw">|</span> <span class="n" id="mwAs0">Key</span> <span class="o" id="mwAs4">|</span> <span class="s" id="mwAs8">", found "</span> <span class="o" id="mwAtA">|</span> <span class="n" id="mwAtE">Find</span><span class="p" id="mwAtI">(</span><span class="n" id="mwAtM">M</span><span class="p" id="mwAtQ">,</span> <span class="n" id="mwAtU">Key</span><span class="p" id="mwAtY">));</span> <span class="kr" id="mwAtc">end</span> <span class="kr" id="mwAtg">loop</span><span class="p" id="mwAtk">;</span> <span class="kr" id="mwAto">for</span> <span class="n" id="mwAts">I</span> <span class="kr" id="mwAtw">in</span> <span class="mi" id="mwAt0">1</span><span class="o" id="mwAt4">..</span><span class="n" id="mwAt8">Num</span><span class="o" id="mwAuA">/</span><span class="mi" id="mwAuE">3</span> <span class="kr" id="mwAuI">loop</span> <span class="c1" id="mwAuM">// Delete some elements from the map</span> <span class="kr" id="mwAuQ">const</span> <span class="n" id="mwAuU">Key</span> <span class="o" id="mwAuY">:=</span> <span class="n" id="mwAuc">Next</span><span class="p" id="mwAug">(</span><span class="n" id="mwAuk">Ran</span><span class="p" id="mwAuo">)</span> <span class="ow" id="mwAus">mod</span> <span class="n" id="mwAuw">Num</span> <span class="o" id="mwAu0">+</span> <span class="mi" id="mwAu4">1</span><span class="p" id="mwAu8">;</span> <span class="n" id="mwAvA">Println</span><span class="p" id="mwAvE">(</span><span class="s" id="mwAvI">"About to delete "</span> <span class="o" id="mwAvM">|</span> <span class="n" id="mwAvQ">Key</span><span class="p" id="mwAvU">);</span> <span class="n" id="mwAvY">Delete</span><span class="p" id="mwAvc">(</span><span class="n" id="mwAvg">M</span><span class="p" id="mwAvk">,</span> <span class="n" id="mwAvo">Key</span><span class="p" id="mwAvs">);</span> <span class="kr" id="mwAvw">end</span> <span class="kr" id="mwAv0">loop</span><span class="p" id="mwAv4">;</span> <span class="n" id="mwAv8">Println</span><span class="p" id="mwAwA">(</span><span class="s" id="mwAwE">"Count = "</span> <span class="o" id="mwAwI">|</span> <span class="n" id="mwAwM">Count</span><span class="p" id="mwAwQ">(</span><span class="n" id="mwAwU">M</span><span class="p" id="mwAwY">));</span> <span class="kr" id="mwAwc">for</span> <span class="n" id="mwAwg">I</span> <span class="kr" id="mwAwk">in</span> <span class="mi" id="mwAwo">1</span><span class="o" id="mwAws">..</span><span class="n" id="mwAww">Num</span> <span class="kr" id="mwAw0">forward</span> <span class="kr" id="mwAw4">loop</span> <span class="c1" id="mwAw8">// Search again for elements in the map</span> <span class="n" id="mwAxA">Println</span><span class="p" id="mwAxE">(</span><span class="s" id="mwAxI">"Looking for "</span> <span class="o" id="mwAxM">|</span> <span class="n" id="mwAxQ">I</span> <span class="o" id="mwAxU">|</span> <span class="s" id="mwAxY">", found "</span> <span class="o" id="mwAxc">|</span> <span class="n" id="mwAxg">Find</span><span class="p" id="mwAxk">(</span><span class="n" id="mwAxo">M</span><span class="p" id="mwAxs">,</span> <span class="n" id="mwAxw">I</span><span class="p" id="mwAx0">));</span> <span class="kr" id="mwAx4">end</span> <span class="kr" id="mwAx8">loop</span><span class="p" id="mwAyA">;</span> <span class="kr" id="mwAyE">end</span> <span class="kr" id="mwAyI">func</span> <span class="n" id="mwAyM">Test_BMap</span><span class="p" id="mwAyQ">;</span>

