tag:blogger.com,1999:blog-82732012398053229322024-02-19T02:00:41.371-06:00Exploring Beautiful LanguagesProgramming language exploration blogLuis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comBlogger142125tag:blogger.com,1999:blog-8273201239805322932.post-38747589549871780592023-06-10T13:16:00.000-06:002023-06-10T13:16:16.652-06:00A quick look at functors in OCaml<p>A couple of weeks ago I was working on a small program that required generating code in different ways depending on a user option. I was trying to make as few changes as possible. Because of the way the program was created and the language it was written in (not <em>OCaml</em>), it required changing several places in the code.</p>
<h3 id="ocaml-functors">OCaml functors</h3>
<p>I remembered reading a little bit about the concept of a <a href="https://ocaml.org/docs/functors">functor</a> in OCaml. Functors are a powerful mechanism that allow you to create modules parameterized by modules. In the case of the task I was working on, I can use it to write the code generation section using module parameterized by a module that provides the final implementation of the code generation.</p>
<h3 id="the-example-code-generation-via-method-calls-or-operators">The example: Code generation via method calls or operators</h3>
<p>I’m going to use a simple example of using a <em>functor</em>. Say that we have a representation for a <em>very</em> simple language:</p>
<div class="sourceCode" id="cb1"><pre class="sourceCode ocaml"><code class="sourceCode ocaml"><a class="sourceLine" id="cb1-1" title="1"><span class="co">(* ast.ml *)</span></a>
<a class="sourceLine" id="cb1-2" title="2"><span class="kw">type</span> expr =</a>
<a class="sourceLine" id="cb1-3" title="3"> | Plus <span class="kw">of</span> expr * expr</a>
<a class="sourceLine" id="cb1-4" title="4"> | Minus <span class="kw">of</span> expr * expr</a>
<a class="sourceLine" id="cb1-5" title="5"> | Div <span class="kw">of</span> expr * expr</a>
<a class="sourceLine" id="cb1-6" title="6"> | Times <span class="kw">of</span> expr * expr</a>
<a class="sourceLine" id="cb1-7" title="7"> | Call <span class="kw">of</span> expr * (expr <span class="dt">list</span>)</a>
<a class="sourceLine" id="cb1-8" title="8"> | Var <span class="kw">of</span> <span class="dt">string</span></a>
<a class="sourceLine" id="cb1-9" title="9"> | Dot <span class="kw">of</span> expr * <span class="dt">string</span></a></code></pre></div>
<p>I want to have the posibility of generating arithmetic expressions in this language in two ways:</p>
<ol type="1">
<li>Generating method calls of arithmetic operations for a Java-like language</li>
<li>Generate common operators</li>
</ol>
<p>One example of option #1 is:</p>
<pre><code>var1.multiply(10).plus(var2)</code></pre>
<p>For option #2 is:</p>
<pre><code>var1 * 10 + var2</code></pre>
<p>The code that generates the expressions must not be aware of the strategy that we are using to generate the code. To do this in OCaml we define a signature for the module used to generate the code:</p>
<div class="sourceCode" id="cb4"><pre class="sourceCode ocaml"><code class="sourceCode ocaml"><a class="sourceLine" id="cb4-1" title="1"><span class="kw">module</span> <span class="kw">type</span> GeneratorFuncs = <span class="kw">sig</span></a>
<a class="sourceLine" id="cb4-2" title="2"> <span class="kw">val</span> (+) : Ast.expr -> Ast.expr -> Ast.expr</a>
<a class="sourceLine" id="cb4-3" title="3"> <span class="kw">val</span> (-) : Ast.expr -> Ast.expr -> Ast.expr</a>
<a class="sourceLine" id="cb4-4" title="4"> <span class="kw">val</span> (/) : Ast.expr -> Ast.expr -> Ast.expr</a>
<a class="sourceLine" id="cb4-5" title="5"> <span class="kw">val</span> ( * ) : Ast.expr -> Ast.expr -> Ast.expr</a>
<a class="sourceLine" id="cb4-6" title="6"><span class="kw">end</span></a></code></pre></div>
<p>We use operators to make it easy to write the code generation. The module that makes the code generator is written as a functor with a parameter that is the module which implements the <code>GeneratorFuncs</code> signature.</p>
<p>The following code shows the “generator” which generates random arithmetic expressions using the provided module for emitting the code:</p>
<div class="sourceCode" id="cb5"><pre class="sourceCode ocaml"><code class="sourceCode ocaml"><a class="sourceLine" id="cb5-1" title="1"><span class="kw">module</span> Make_generator(Current_funcs : GeneratorFuncs) = <span class="kw">struct</span></a>
<a class="sourceLine" id="cb5-2" title="2"> <span class="kw">let</span> gen_single() = </a>
<a class="sourceLine" id="cb5-3" title="3"> <span class="kw">if</span> <span class="dt">Random</span>.<span class="dt">int</span> <span class="dv">10</span> > <span class="dv">5</span> <span class="kw">then</span></a>
<a class="sourceLine" id="cb5-4" title="4"> Ast.Var <span class="st">"x"</span></a>
<a class="sourceLine" id="cb5-5" title="5"> <span class="kw">else</span> </a>
<a class="sourceLine" id="cb5-6" title="6"> Ast.Lit (<span class="dv">1</span> + <span class="dt">Random</span>.<span class="dt">int</span> <span class="dv">5</span>)</a>
<a class="sourceLine" id="cb5-7" title="7"></a>
<a class="sourceLine" id="cb5-8" title="8"></a>
<a class="sourceLine" id="cb5-9" title="9"> <span class="kw">let</span> <span class="kw">rec</span> generate_sample (depth: <span class="dt">int</span>) = </a>
<a class="sourceLine" id="cb5-10" title="10"> <span class="kw">let</span> new_depth = depth - <span class="dv">1</span> <span class="kw">in</span></a>
<a class="sourceLine" id="cb5-11" title="11"> Current_funcs.(</a>
<a class="sourceLine" id="cb5-12" title="12"> <span class="kw">match</span> depth, <span class="dt">Random</span>.<span class="dt">int</span> <span class="dv">10</span> <span class="kw">with</span></a>
<a class="sourceLine" id="cb5-13" title="13"> | <span class="dv">0</span>, _ -> gen_single()</a>
<a class="sourceLine" id="cb5-14" title="14"> | _, r <span class="kw">when</span> r >= <span class="dv">0</span> && r <= <span class="dv">3</span> -> </a>
<a class="sourceLine" id="cb5-15" title="15"> ((generate_sample new_depth) + (generate_sample new_depth))</a>
<a class="sourceLine" id="cb5-16" title="16"> | _, r <span class="kw">when</span> r >= <span class="dv">4</span> && r <= <span class="dv">6</span> -> </a>
<a class="sourceLine" id="cb5-17" title="17"> ((generate_sample new_depth) - (generate_sample new_depth))</a>
<a class="sourceLine" id="cb5-18" title="18"> | _, r <span class="kw">when</span> r >= <span class="dv">7</span> && r <= <span class="dv">10</span> -> </a>
<a class="sourceLine" id="cb5-19" title="19"> ((generate_sample new_depth) / (generate_sample new_depth))</a>
<a class="sourceLine" id="cb5-20" title="20"> | _, _ -> Ast.Var <span class="st">"x"</span>)</a>
<a class="sourceLine" id="cb5-21" title="21"><span class="kw">end</span></a></code></pre></div>
<p>We can write our emitter for generating code using method calls like this:</p>
<div class="sourceCode" id="cb6"><pre class="sourceCode ocaml"><code class="sourceCode ocaml"><a class="sourceLine" id="cb6-1" title="1"><span class="co">(* mgenerator.ml *)</span></a>
<a class="sourceLine" id="cb6-2" title="2"><span class="kw">module</span> MGenerator = <span class="kw">struct</span></a>
<a class="sourceLine" id="cb6-3" title="3"> <span class="kw">let</span> simple_call (obj: Ast.expr) mmethod arg =</a>
<a class="sourceLine" id="cb6-4" title="4"> Ast.Call(</a>
<a class="sourceLine" id="cb6-5" title="5"> Ast.Dot(</a>
<a class="sourceLine" id="cb6-6" title="6"> obj, </a>
<a class="sourceLine" id="cb6-7" title="7"> mmethod), [arg])</a>
<a class="sourceLine" id="cb6-8" title="8"> <span class="kw">let</span> (+) (a: Ast.expr) (b: Ast.expr) = simple_call a <span class="st">"plus"</span> b</a>
<a class="sourceLine" id="cb6-9" title="9"> <span class="kw">let</span> ( * ) a b = simple_call a <span class="st">"times"</span> b</a>
<a class="sourceLine" id="cb6-10" title="10"> <span class="kw">let</span> (-) a b = simple_call a <span class="st">"minus"</span> b</a>
<a class="sourceLine" id="cb6-11" title="11"> <span class="kw">let</span> (/) a b = simple_call a <span class="st">"div"</span> b</a>
<a class="sourceLine" id="cb6-12" title="12"><span class="kw">end</span></a>
<a class="sourceLine" id="cb6-13" title="13"></a>
<a class="sourceLine" id="cb6-14" title="14"><span class="kw">module</span> MGen = Generator.Make_generator(MGenerator)</a></code></pre></div>
<p>An alternative module that generates arithmetic expression using operators:</p>
<div class="sourceCode" id="cb7"><pre class="sourceCode ocaml"><code class="sourceCode ocaml"><a class="sourceLine" id="cb7-1" title="1"><span class="kw">module</span> OGenerator = <span class="kw">struct</span></a>
<a class="sourceLine" id="cb7-2" title="2"> <span class="kw">let</span> (+) (a: Ast.expr) (b: Ast.expr) = Ast.Plus(a, b)</a>
<a class="sourceLine" id="cb7-3" title="3"> <span class="kw">let</span> ( * ) a b = Ast.Times(a, b)</a>
<a class="sourceLine" id="cb7-4" title="4"> <span class="kw">let</span> (-) a b = Ast.Minus(a, b)</a>
<a class="sourceLine" id="cb7-5" title="5"> <span class="kw">let</span> (/) a b = Ast.Div(a, b)</a>
<a class="sourceLine" id="cb7-6" title="6"><span class="kw">end</span></a>
<a class="sourceLine" id="cb7-7" title="7"></a>
<a class="sourceLine" id="cb7-8" title="8"><span class="kw">module</span> OGen = Generator.Make_generator(OGenerator)</a></code></pre></div>
<p>We can use this modules to generate sample code snippets:</p>
<div class="sourceCode" id="cb8"><pre class="sourceCode ocaml"><code class="sourceCode ocaml"><a class="sourceLine" id="cb8-1" title="1"><span class="kw">let</span> main = </a>
<a class="sourceLine" id="cb8-2" title="2"> <span class="kw">let</span> _ = <span class="dt">Random</span>.self_init() <span class="kw">in</span></a>
<a class="sourceLine" id="cb8-3" title="3"> <span class="kw">in</span> <span class="kw">let</span> generat = Mgenerator.MGen.generate_sample <span class="dv">3</span> </a>
<a class="sourceLine" id="cb8-4" title="4"> <span class="kw">in</span> <span class="kw">let</span> generat2 = Ogenerator.OGen.generate_sample <span class="dv">3</span> </a>
<a class="sourceLine" id="cb8-5" title="5"> <span class="kw">in</span> </a>
<a class="sourceLine" id="cb8-6" title="6"> <span class="dt">print_endline</span> (Ast.pprint_string generat);</a>
<a class="sourceLine" id="cb8-7" title="7"> <span class="dt">print_endline</span> (Ast.pprint_string generat2)</a></code></pre></div>
<p>Output:</p>
<pre><code>x.plus(2).plus(5.div(4)).div(x.plus(x).plus(5.div(1)))
x + 4 / x - 2 + 4 + x + 5 + x</code></pre>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-4066719961398184792023-06-04T18:03:00.002-06:002023-06-04T18:03:47.323-06:00Haskell 'newtype' and the record syntax<p>While reading some Haskell code snippets I found something that seemed confusing. The snippet involved <code>newtype</code> and record syntax. A simplified example is the following:</p>
<pre><code>newtype PersonName = PersonName { theName :: String }
...
let p1 = PersonName $ getName obj
in print $ theName</code></pre>
<p>I was not able to find a place where the <code>PersonName</code> was created by specifying the value of <code>theName</code> explicitly for example (<code>Person { theName = "xyz" }</code>) . The reason is that record syntax allows an alternative way of specifying the field values. For example:</p>
<pre><code>let p1 = PersonName "Luis" -- valid!
...
let p2 = PersonName { theName = "Luis" } -- valid!</code></pre>
<p>Another thing that I found interesting is the <code>newtype</code> restrictions. For example it only allows you to specify one field in our record:</p>
<pre><code>newtype PersonName' = PersonName' { firstName :: String, lastName ::String }</code></pre>
<p>Compiling this is going to generate the following error:</p>
<pre><code>newtypeexp.hs:6:23: error:
• The constructor of a newtype must have exactly one field
but ‘PersonName'’ has two
• In the definition of data constructor ‘PersonName'’
In the newtype declaration for ‘PersonName'’
|
6 | newtype PersonName' = PersonName' { firstName :: String, lastName ::String }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^</code></pre>
<p>This seems to be related to the fact that <code>newtype</code> is used as a compile-type concept only. More info here https://wiki.haskell.org/Newtype#The_short_version .</p>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-8267283597846865172023-04-07T22:02:00.000-06:002023-04-07T22:02:42.395-06:00Some considerations for using closures in Rust/WASM<p>Here are a couple of things I learned while trying to pass a Rust closure to a JavaScript function. Some of these notes are a result of my lack of experience with Rust and Rust/WASM.</p>
<h2 id="passing-a-closure-that-is-going-to-outlive-the-current-function-call">Passing a closure that is going to outlive the current function call</h2>
<p>Passing a Rust function that exists in the stack to JavaScript is easy for example, here is a call to <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map">Array.map</a>:</p>
<pre><code>#[wasm_bindgen]
pub fn square_elements(a : &js_sys::Array) -> js_sys::Array {
a.map(&mut |value:JsValue, idx: u32, arr: js_sys::Array| {
let value = value.as_f64().unwrap();
JsValue::from_f64(value * value)
})
}</code></pre>
<p>In this case the function used as argument to <code>map</code> exists only for the time of the invocation of the <code>square_elements</code> function. You need to do something extra when passing a closure is going to outlive the current call. This section of the Rust WASM documentation: <a href="https://rustwasm.github.io/wasm-bindgen/reference/passing-rust-closures-to-js.html#heap-allocated-closures" class="uri">https://rustwasm.github.io/wasm-bindgen/reference/passing-rust-closures-to-js.html#heap-allocated-closures</a> has details on how to call a JavaScript function that receives a closure that “survives” the current method or function call. A typical example is calling <a href="https://rustwasm.github.io/docs/wasm-bindgen/examples/request-animation-frame.html">requestAnimationFrame</a> .</p>
<p>It has a very important note that I overlooked at first:</p>
<blockquote>
<p>Once a Closure is dropped, it will deallocate its internal memory and invalidate the corresponding JavaScript function so that any further attempts to invoke it raise an exception…<a href="https://rustwasm.github.io/wasm-bindgen/reference/passing-rust-closures-to-js.html#heap-allocated-closures" class="uri">https://rustwasm.github.io/wasm-bindgen/reference/passing-rust-closures-to-js.html#heap-allocated-closures</a></p>
</blockquote>
<p>One thing that I want to do in Rust with WASM is to write a “requestAnimationFrame loop” which allows me to write code that performs a repetitive task without blocking the UI thread of the browser. Here is an example of how this looks in JavaScript</p>
<pre><code>// JavaScript
let i = 0;
let action = () => {
if (i < 3) {
console.log(`Calling with ${i}`);
// do something interesting...
requestAnimationFrame(action);
}
i++;
};
requestAnimationFrame(action);</code></pre>
<p>I found a nice example on how to do this loop in Rust here: <a href="https://rustwasm.github.io/docs/wasm-bindgen/examples/request-animation-frame.html" class="uri">https://rustwasm.github.io/docs/wasm-bindgen/examples/request-animation-frame.html</a> . The example has a lot of documentation that explains its functionality in the comments. The code looks a little bit intimidating for a Rust newbie (like me). Here is a small reduced code with the most important parts of the example:</p>
<pre><code>let f = Rc::new(RefCell::new(None));
let g = f.clone();
let mut i = 0;
*g.borrow_mut() = Some(Closure::wrap(Box::new(move || {
if i > 300 {
...
let _ = f.borrow_mut().take();
return;
}
i += 1;
...
request_animation_frame(f.borrow().as_ref().unwrap());
}))
...
request_animation_frame(g.borrow().as_ref().unwrap());</code></pre>
<p>As described in the source of the example, this code uses <a href="https://doc.rust-lang.org/std/rc/struct.Rc.html">Rc</a> and <a href="https://doc.rust-lang.org/std/cell/struct.RefCell.html">RefCell</a> to keep the <a href="https://rustwasm.github.io/wasm-bindgen/api/wasm_bindgen/closure/struct.Closure.html">Closure</a> instance <em>alive</em> while the sequence of <a href="https://developer.mozilla.org/en-US/docs/Web/API/window/requestAnimationFrame">requestAnimationFrame</a> calls do its work. In this case when the <code>i</code> counter reaches <code>300</code> the closure will return and finish the loop.</p>
<p>Each part in this code is very important. I did some mistakes that I’m going to detail in the next sections.</p>
<h2 id="the-closure-is-dropped-before-requestanimationframe-does-its-job">The closure is dropped before ‘requestAnimationFrame’ does its job</h2>
<p>The goal of the two <code>Rc/RefCell</code> references to the same closure is to keep the <code>Closure</code> alive before finishing the call to the current function. This is an example of the error that is raised when you fail to do that:</p>
<pre><code>// this example is incomplete
pub fn greet() {
let f = Rc::new(RefCell::new(None));
let g = f.clone();
let mut i = 0;
*g.borrow_mut() = Some(Closure::new(move || {
log("At the end of the closure");
}));
log(&format!("Before quitting 'greet' {}", Rc::strong_count(&g)));
request_animation_frame(g.borrow().as_ref().unwrap());
} </code></pre>
<p>Notice that here we don’t pass <code>f</code> into the closure. Hence at the end of the function both <code>g</code> and <code>f</code> are going to be dropped along with the <code>Closure</code> instance. Running this code shows the following errors in the browser console:</p>
<pre><code>...
Before quitting 'greet' 2 wasm_loop_bg.js:259:13
Uncaught Error: closure invoked recursively or after being dropped
...</code></pre>
<p>To fix this issue in the incomplete example I just need to move the <code>f</code> instance to the closure so it will be captured:</p>
<pre><code>// this example is incomplete
pub fn greet() {
let f = Rc::new(RefCell::new(None));
let g = f.clone();
let mut i = 0;
*g.borrow_mut() = Some(Closure::new(move || {
let _ = f; /// Now 'f' is moved inside!
log("At the end of the closure");
}));
log(&format!("Before quitting 'greet' {}", Rc::strong_count(&g)));
request_animation_frame(g.borrow().as_ref().unwrap());
} </code></pre>
<h2 id="resources-not-being-released">Resources not being released</h2>
<p>After writing the complete loop, I also found that I was not doing the complete cleanup for the closure.</p>
<p>Here is an example that shows the problematic code:</p>
<pre><code>#[derive(Debug)]
struct MyStruct {
x: i32
}
impl Drop for MyStruct {
fn drop(&mut self) {
write_debug(format!("Calling `drop` on MyStruct: {}", self.x).as_str());
}
}
#[wasm_bindgen]
pub fn greet() {
let f = Rc::new(RefCell::new(None));
let g = f.clone();
let captured = MyStruct { x: 100 };
let mut i = 0;
*g.borrow_mut() = Some(Closure::new(move || {
log(format!("Counter: {} captured value: {:?}", i, &captured).as_str());
if i != 2 {
request_animation_frame(f.borrow().as_ref().unwrap());
}
} else {
log("Finished"); return;
}
i += 1;
}));
request_animation_frame(g.borrow().as_ref().unwrap());
log("Before finishing 'greet'");
}</code></pre>
<p>In this example I created a dummy <code>struct</code> called <code>MyStruct</code> . This structure implements the <a href="https://doc.rust-lang.org/std/ops/trait.Drop.html">Drop</a> trait to display a message in the console when the structured is being dropped. An instance of this structure is being captured by the closure passed to the <code>requestAnimationFrame</code> call.</p>
<p>When running this code we see the following messages in the console:</p>
<pre><code>Before finishing 'greet' wasm_loop_bg.js:267:13
Counter: 0 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Counter: 1 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Counter: 2 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Finished</code></pre>
<p>Notice that we don’t see the message logged in the <code>drop</code> method of <code>MyStruct</code>. The reason for this is that I forgot to release the value inside the <code>Rc/RefCell</code> wrapper.</p>
<p>Here is the corrected code:</p>
<pre><code>...
#[wasm_bindgen]
pub fn greet() {
let f = Rc::new(RefCell::new(None));
let g = f.clone();
let captured = MyStruct { x: 100 };
let mut i = 0;
*g.borrow_mut() = Some(Closure::new(move || {
log(format!("Counter: {} captured value: {:?}", i, &captured).as_str());
if i != 2 {
request_animation_frame(f.borrow().as_ref().unwrap());
} else {
log("Finished");
let _ = f.take();
return;
}
i += 1;
}));
request_animation_frame(g.borrow().as_ref().unwrap());
log("Before finishing 'greet'");
}</code></pre>
<p>And now here is the output of the code:</p>
<pre><code>Before finishing 'greet' wasm_loop_bg.js:267:13
Counter: 0 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Counter: 1 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Counter: 2 captured value: MyStruct { x: 100 } wasm_loop_bg.js:267:13
Finished wasm_loop_bg.js:267:13
Calling `drop` on MyStruct: 100</code></pre>
<p>As with the original example the <a href="https://doc.rust-lang.org/std/cell/struct.RefCell.html#method.take">take</a> method is used to move the <code>Closure</code> out of the <code>Rc/RefCell</code> reference. The value will be dropped at the end of the call.</p>
<h2 id="not-following-the-requirement-of-using-fnmut-for-the-closure">Not following the requirement of using FnMut for the closure</h2>
<p>This is another case of not following the rules and not taking the time to read the error message. I did a small change to the code as follows:</p>
<p>…</p>
<pre><code>fn my_dummy_function_requiring_move(ms: MyStruct) {
log(format!("-- {:?}", &ms).as_str());
}
...
#[wasm_bindgen]
pub fn greet() {
let f = Rc::new(RefCell::new(None));
let g = f.clone();
let captured = MyStruct { x: 100 };
let mut i = 0;
*g.borrow_mut() = Some(Closure::new(move || {
my_dummy_function_requiring_move(captured);
log(format!("Counter: {} captured value: {:?}", i, &captured).as_str());
if i != 2 {
request_animation_frame(f.borrow().as_ref().unwrap());
} else {
log("Finished");
let _ = f.take();
return;
}
i += 1;
}));
request_animation_frame(g.borrow().as_ref().unwrap());
log("Before finishing 'greet'");
}</code></pre>
<p>When introducing this code the compiles shows the following error:</p>
<pre><code>error[E0525]: expected a closure that implements the `FnMut` trait, but this closure only implements `FnOnce`
--> src\lib.rs:74:41
|
74 | *g.borrow_mut() = Some(Closure::new(move || {
| ------------ -^^^^^^
| | |
| ____________________________|____________this closure implements `FnOnce`, not `FnMut`
| | |
| | required by a bound introduced by this call
75 | |
76 | | my_dummy_function_requiring_move(captured);
| | -------- closure is `FnOnce` because it moves the variable `captured` out of its environment
77 | | log(format!("Counter: {} captured value: {:?}", i, &captured).as_str());
... |
85 | | i += 1;
86 | | }));
| |_____- the requirement to implement `FnMut` derives from here
|
= note: required for `[closure@src\lib.rs:74:41: 74:48]` to implement `IntoWasmClosure<dyn FnMut()>`
note: required by a bound in `wasm_bindgen::prelude::Closure::<T>::new`
--> C:\Users\ldfallasu2\.cargo\registry\src\github.com-1ecc6299db9ec823\wasm-bindgen-0.2.84\src\closure.rs:271:12
|
271 | F: IntoWasmClosure<T> + 'static,
| ^^^^^^^^^^^^^^^^^^ required by this bound in `wasm_bindgen::prelude::Closure::<T>::new`
</code></pre>
<p>It is really impressive to see how to compiler shows the location of the error and the related areas. As the error message says, the problem here is that we are moving a value <em>out</em> of the closure. This fact prevents the compiler from assuming that our closure implements the <a href="https://doc.rust-lang.org/std/ops/trait.FnMut.html">FnMut trait</a> (More information here <a href="https://doc.rust-lang.org/stable/book/ch13-01-closures.html#moving-captured-values-out-of-closures-and-the-fn-traits" class="uri">https://doc.rust-lang.org/stable/book/ch13-01-closures.html#moving-captured-values-out-of-closures-and-the-fn-traits</a> ).</p>
<p>The solution in this case is simple, since the move was not really required I created an alternative version of the function that do not require a “move”:</p>
<pre><code>fn my_dummy_function_requiring_ref(ms: &MyStruct) {
write_debug(format!("-- {:?}", ms).as_str());
}</code></pre>
<p>The call is changed to <code>my_dummy_function_requiring_ref(&s);</code> which removes the compilation error.</p>
<p>The examples created in this post use the following utility functions and declarations:</p>
<pre><code>fn window() -> web_sys::Window {
web_sys::window().expect("not global 'window'")
}
fn request_animation_frame(f: &Closure<dyn FnMut()>) {
window()
.request_animation_frame(f.as_ref().unchecked_ref())
.expect("Call to request animation frame ");
}
#[wasm_bindgen]
extern {
#[wasm_bindgen(js_namespace = console)]
fn log(s: &str);
}</code></pre>
<h2 id="conclusions">Conclusions</h2>
<p>I think there are two main conclusions for this post:</p>
<ol type="1">
<li>Read the documentation carefully!</li>
<li>Take time to read the compiler errors. The Rust compiler team put a lot of effort explain the error and help you locate the origin of the problem.</li>
</ol>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-16035736141468932312022-11-02T20:20:00.000-06:002022-11-02T20:20:00.569-06:00Implementing WHILE in a toy BASIC interpreter<p>
While working on a toy BASIC implementation, I ran into an unexpected challenge implementing the <code>WHILE</code> instruction.
</p>
<p>
The implementation of this instruction seems simple. Here is an example :
</p>
<pre class="example">
10 X = 1
20 WHILE X <> 10
30 PRINT X
40 X = X + 1
50 WEND
</pre>
<p>
This program is going to print the numbers from 1 to 9. The <code>WHILE</code> statement is really a combination of <code>WHILE</code> and <code>WEND</code>. The <code>WEND</code> statement indicates the end of the 'block'.
</p>
<p>
The first challenge is to create a relation between these statements. This relation is going to be used by the interpreter to identify where to 'jump' when evaluating <code>WHILE</code> and <code>WEND</code>. One interesting challenge is that BASIC (GWBASIC) supports `nested` <code>WHILE</code> blocks:
</p>
<pre class="example">
10 X = 10
20 Y = 10
30 WHILE X <> 0
40 PRINT "X = ", X
50 Y = 10
60 WHILE Y <> 0
70 PRINT "y =", Y
80 Y = Y - 1
90 WEND
100 X = X - 1
110 WEND
</pre>
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjSK1iJ1T2scDM80xVySriDanDBWS8o5qRJA_PxafvZoK6nx_M9TD2nUjwEOtU2Q-d-OXzeG6pqK1gTzYy4Y8J1VpBEqaR2CI9_U7NI6rE6RAvSZhqWZmUQ6YST0aCH1jaAosbGQZeKH21UJBFtuToWBuBD50hPJqEQBlta-ugG9oC_Q20O5YMmrJMg0A/s1019/nestedwhilebasic.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" height="320" data-original-height="1019" data-original-width="382" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjSK1iJ1T2scDM80xVySriDanDBWS8o5qRJA_PxafvZoK6nx_M9TD2nUjwEOtU2Q-d-OXzeG6pqK1gTzYy4Y8J1VpBEqaR2CI9_U7NI6rE6RAvSZhqWZmUQ6YST0aCH1jaAosbGQZeKH21UJBFtuToWBuBD50hPJqEQBlta-ugG9oC_Q20O5YMmrJMg0A/s320/nestedwhilebasic.png"/></a></div>
<p>
Since the source of the original <b>GW-BASIC</b> implementation is published in GitHub, we can take a look at it here: <a href="https://github.com/microsoft/GW-BASIC">https://github.com/microsoft/GW-BASIC</a>. There is code in <code>GWMAIN.ASM</code> used to search for the correspoing <code>WEND</code> of a <code>WHILE</code> (a code block called <code>WNDSCN</code>). This also seems to be used to locate the <code>FOR=/=NEXT</code> pair of instructions. It seems that the interpreter tries to find the matching instruction by scanning the instructions that follow the <code>WHILE</code>. A counter is used to keep track of nested WHILE/WEND blocks:
</p>
<pre class="example">
..
PUBLIC WNDSCN
WNDSCN: MOV CL,LOW OFFSET ERRWH ;SCAN FOR MATCHING WEND THIS IS ERROR IF FAIL
.
.
.
FORINC: INC CH ;INCREMENT THE COUNT WHENEVER "FOR" IS SEEN
.
.
.
JZ SHORT NXTLOK ;FOR/NEXT SEARCHING
CMP AL,LOW OFFSET $WHILE ;ANOTHER WHILE/WEND NEST?
JZ SHORT FORINC
CMP AL,LOW OFFSET $WEND
JNZ SHORT FNLOP
DEC CH
.
.
.
</pre>
<h3 id="org26e1b22"><span class="section-number-3">1.2</span> Strategy</h3>
<p>
One way to start implementing this feature in the interpreter was to add a table (<code>pair_instruction_table</code>) to the interpreter context. This table is going to keep the relation between instructions. In particular it will be used to relate a <code>WHILE</code> and <code>WEND</code> pair. In the near future it will keep the relation between <code>FOR</code> and <code>NEXT</code>.
</p>
<p>
The evaluation context will now look like this:
</p>
<pre class="example">
pub struct EvaluationContext<'a> {
pub variables: HashMap<String, ExpressionEvalResult>,
pub array_variables: HashMap<String, GwArray>,
pub jump_table: HashMap<i16, i16>,
pub underlying_program: Option<&'a mut GwProgram>,
pub pair_instruction_table: HashMap<i16, i16>,
}
</pre>
<p>
With this information we can create a search function that emulates the same behavior as <code>WNDSCN</code> . Something like this:
</p>
<pre class="example">
fn find_wend(line: i16, real_lines: &Vec<&Box<dyn GwInstruction>>) -> i16{
let mut curr_line = line + 1;
let mut while_end_balance = 0;
loop {
if curr_line >= real_lines.len() as i16 {
break;
} else if let Some(ref instr) = real_lines.get(curr_line as usize) {
if instr.is_while() {
while_end_balance += 1;
}
if instr.is_wend() {
if while_end_balance == 0 {
return curr_line as i16;
} else {
while_end_balance -= 1;
}
}
}
curr_line += 1;
}
return -1;
}
</pre>
<p>
Notice that we solve the problem of nested <code>WHILE/WEND</code> blocks by keeping a counter <code>while_end_balance</code>.
</p>
<p>
With this utility we can create the implementation of the <code>WHILE</code> statement with the following code:
</p>
<pre class="example">
impl GwInstruction for GwWhile {
fn eval (&self, line: i16, context : &mut EvaluationContext) -> InstructionResult {
let mut wend_line : i16 = 0;
// Find the cached corresponding line for this WHILE statement
if let Some(corresponding_wend) = context.pair_instruction_table.get(&line) {
wend_line = *corresponding_wend;
} else if let Some(ref real_lines) = context.real_lines {
// Try to look for the WEND statement in the program lines
let index_of_wend = find_wend(line, real_lines);
if index_of_wend == -1 {
return InstructionResult::EvaluateToError(String::from("WHILE WITHOUT WEND"));
} else {
context.pair_instruction_table.insert(line, index_of_wend);
context.pair_instruction_table.insert(index_of_wend, line);
}
wend_line = index_of_wend;
}
// Evaluate the condition and move the following line
let condition_evaluation = self.condition.eval(context);
match condition_evaluation {
ExpressionEvalResult::IntegerResult(result) if result == 0 => {
InstructionResult::EvaluateLine(wend_line + 1)
}
ExpressionEvalResult::IntegerResult(_) => {
InstructionResult::EvaluateNext
}
_ => {
InstructionResult::EvaluateToError(String::from("Type mismatch"))
}
}
}
</pre>
<h3 id="org6f62292"><span class="section-number-3">1.3</span> Additional problems</h3>
<p>
While working in this implementation I found an additional problem. In BASIC you can have several statements in one line separated by colons (:) . For example you can have a complete <code>WHILE</code> block in just one line:
</p>
<pre class="example">
10 X = 1 : WHILE X < 10 : PRINT X : X = X + 1 :WEND
</pre>
<p>
Or you can have a <code>WHILE</code> in one line and the <code>WEND</code> inside another line:
</p>
<pre class="example">
10 x = 1
20 WHILE x <> 5
30 print x
40 x = x + 1 : print "a" : WEND
50 print "END"
</pre>
<p>
To support his scenario the program is "flattened" before executing it. For example, the previous snippet becomes is converted to:
</p>
<pre class="example">
0 x = 1
1 WHILE x <> 5
2 print x
3 x = x + 1
4 print "a"
5 WEND
6 print "END"
</pre>
<p>
This way it is easy to implement a jump between instructions that didn't exist in as explicit lines in the original program. This transformation is performed before running the program:
</p>
<pre class="example">
...
let real_lines = &mut context.real_lines.as_mut().expect("instr vector");
for e in self.lines.iter() {
real_lines.push(&e.instruction);
if let Some(ref rest) = e.rest_instructions {
for nested in rest {
real_lines.push(&nested);
}
}
}
...
</pre>
<p>
Something that needs to be improved is the way to identify existing <code>WHILE</code> and <code>WEND</code> instructions. Sadly, right now this is implemented using a pair of methods <code>is_while</code> and <code>is_wend</code>. These methods are defined in the <code>GwInstruction</code> trait and overriden on <code>GwWhile</code> and <code>GwWend</code>. This is ugly since these methods are very specific to this problem. It doesn't seem right to have them in <code>GwInstruction</code>.
</p>
<p>
One alternative to solve this problem is to redesign the code representation to include a way to retrieve the original instruction from a <code>GwInstruction</code>. This is one of the things that will be implemented next.
</p>
<p>
Code for the interpreter is here: <a href="https://github.com/ldfallas/rgwbasic">https://github.com/ldfallas/rgwbasic</a> .
</p>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-31528137001662211722022-04-16T08:44:00.000-06:002022-04-16T08:44:53.764-06:00Executing code from a buffer with Rust on Windows<p>Creating and executing code at runtime is an intriguing topic. It is one of the pieces that makes it possible to write JIT compilers for things like Java or C#.</p>
<p>Creating a byte array with executable instructions and “casting” that array to a function pointer is not enough . For security reasons, modern operating systems require you to specify which region of memory of your program is executable. On Windows the <a href="https://docs.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualalloc">VirtualAlloc</a> and <a href="https://docs.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualprotect">VirtualProtect</a> functions are used to do this.</p>
<p>There is a nice StackOverflow answer: <a href="https://stackoverflow.com/questions/40936534/how-to-alloc-a-executable-memory-buffer">https://stackoverflow.com/questions/40936534/how-to-alloc-a-executable-memory-buffer</a> by user <a href="https://stackoverflow.com/users/3313064/christian-hackl">Christian Hackl</a> on how to use these API functions. In this post I’m going to try to replicate the C++ example from the SO post in Rust .</p>
<p>The first is to be able to call VirtualAlloc and VirtualProtect from Rust. There are several ways to call “C” style functions in Rust. However to call these Win32 API functions I am going to use <a href="https://docs.microsoft.com/en-us/windows/dev-environment/rust/rust-for-windows">Rust for Windows</a>. This package provides an easy way to call into Win32 API .</p>
<p>First we start by adding the the <a href="https://crates.io/crates/windows">windows crate</a> to our dependencies. And we also specify that we need a couple of features:</p>
<pre><code>//Cargo.toml
...
[dependencies.windows]
version="0.35.0"
features = [
"alloc",
"Win32_Foundation",
"Win32_System_Memory",
]</code></pre>
<p>Here, the most important feature is “Win32_System_Memory” which allows us to call VirtualAlloc and VirtualProtect. You can see that in the "Required features" section of the documentation entry here <a href="https://microsoft.github.io/windows-docs-rs/doc/windows/Win32/System/Memory/fn.VirtualAlloc.html">https://microsoft.github.io/windows-docs-rs/doc/windows/Win32/System/Memory/fn.VirtualAlloc.html</a></p>
<p>Now that we have this functions we can rewrite the example from the StackOverflow question:</p>
<pre><code>use windows::{
core::*,
Win32::Foundation::*,
Win32::System::Memory::*,
};
fn main() -> Result<()> {
unsafe {
let buffer = VirtualAlloc(
std::ptr::null(),
4096,
MEM_COMMIT | MEM_RESERVE,
PAGE_READWRITE,
);
let buff_arr = std::mem::transmute::<*mut ::core::ffi::c_void, &mut [u8; 6]>(buffer);
buff_arr[0] = 0xb8; // MOV opcode
buff_arr[1] = 0x05; // '5' value
buff_arr[2] = 0x00;
buff_arr[3] = 0x00;
buff_arr[4] = 0x00;
buff_arr[5] = 0xc3; // RET
let mut dummy: [PAGE_PROTECTION_FLAGS; 1] = [PAGE_PROTECTION_FLAGS::default()];
let vpResult = VirtualProtect(buffer, 6, PAGE_EXECUTE_READ, dummy.as_mut_ptr());
if !vpResult.as_bool() {
GetLastError().to_hresult().ok()?;
}
let new_function = std::mem::transmute::<*mut ::core::ffi::c_void, fn() -> i32>(buffer);
let result = new_function();
println!("The result is {}", result);
VirtualFree(buffer, 0, MEM_RELEASE);
}
Ok(())
}</code></pre>
<p>After compiling and running this example we can see:</p>
<p><code>The result is 5</code></p>
<p>I was very happy the first time I saw that running!. Here the <code>buff_array</code> buffer has real x86 instructions equivalent to something like:</p>
<pre><code>mov eax, 0x5
ret</code></pre>
<p>Encoding this instructions is a very complex process. The documentation contains dense tables explaining the format for example for <a href="https://www.felixcloutier.com/x86/mov">MOV</a> or <a href="https://www.felixcloutier.com/x86/ret">RET</a>.</p>
<p>Also it is clear that we need unsafe Rust here since we are dealing with low level code.</p>
<p>The process of encoding the instructions is very complex. We can take a shortcut using the <a href="https://github.com/icedland/iced">iced-x86 crate</a>. This really cool library has a complete x86 assembler and dissembler. It was very easy (with my limited Rust knowledge) to adapt it to this little example.</p>
<p>For we include it in the Cargo.toml file:</p>
<pre><code>[dependencies.iced-x86]
version = "1.17.0"
features = ["code_asm"]</code></pre>
<p>Now we can create the code using the nice API that iced-x86 provides. Here I’m adding a call to a function defined in the same program.</p>
<pre><code>fn print_hello() -> u32 {
println!("Hello!!!");
1
}
fn encode_small_program() -> ::core::result::Result<Vec<u8>, asm::IcedError> {
let mut assembler = asm::CodeAssembler::new(64)?;
unsafe {
let print_hello_addr = std::mem::transmute::<fn() -> u32, u64>(print_hello);
assembler.sub(asm::rsp, 0x28)?;
assembler.mov(asm::rax, print_hello_addr)?;
assembler.call(asm::rax)?;
assembler.mov(asm::eax, 0x7)?;
assembler.add(asm::rsp, 0x28)?;
assembler.ret()?;
}
let instr = assembler.take_instructions();
let block = InstructionBlock::new(&instr, 0);
let res = BlockEncoder::encode(64, block, BlockEncoderOptions::NONE)?;
Ok(res.code_buffer)
}
</code></pre>
<p>We can modify the make program to use this new function:</p>
<pre><code> let encoded_program = encode_small_program().unwrap();
let p = encoded_program.as_ptr();
unsafe {
let buffer = VirtualAlloc(
std::ptr::null(),
4096,
MEM_COMMIT | MEM_RESERVE,
PAGE_READWRITE,
);
let buff_arr = std::mem::transmute::<*mut ::core::ffi::c_void, *mut u8>(buffer);
std::ptr::copy_nonoverlapping(p, buff_arr, encoded_program.len());
let mut dummy: [PAGE_PROTECTION_FLAGS; 1] = [PAGE_PROTECTION_FLAGS::default()];
let vpResult = VirtualProtect(buffer, 6, PAGE_EXECUTE_READ, dummy.as_mut_ptr());
if !vpResult.as_bool() {
GetLastError().to_hresult().ok()?;
}
let new_function = std::mem::transmute::<*mut ::core::ffi::c_void, fn() -> i32>(buffer);
let result = new_function();
println!("The result is {}", result);
VirtualFree(buffer, 0, MEM_RELEASE);
}</code></pre>
<p>Running this program now shows:</p>
<pre><code>Hello!!!
The result is 7</code></pre>
<p>This experiment bring intriguing possibilities for future posts!.</p>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-3277324976535594682022-04-15T07:54:00.001-06:002022-04-16T07:14:32.068-06:00Exploring a Webpack stats file with Prolog<p>A couple of days ago I was reading about the <a href="https://webpack.js.org/api/stats/">Webpack statistics file</a> created using the following command line options:</p>
<pre><code>npx webpack --profile --json</code></pre>
<p>This file contains a lot of information collected by Webpack about the project being processed. The information in this file is used by nice visualization tools like <a href="https://www.npmjs.com/package/webpack-bundle-analyzer">Webpack Bundle Analyzer</a>.</p>
<p>The dependency graph is included in this file. That is, all the dependencies between modules of the project. Being able to perform queries on this data could be useful to get insights into the code. </p>
<p>There are many tools to process JSON, but I wanted to try to use <a href="https://www.swi-prolog.org/">SWI-Prolog</a> to see if I can get information from this file.</p>
<p>The information I am looking for is the module dependency information. By taking a look at the <a href="https://webpack.js.org/api/stats/#module-objects">Module Object</a> we can get this information using the <code>reasons</code> property. </p>
<p>We can start by parsing the <code>stats.json</code> file using SWI-Prolog <a href="https://www.swi-prolog.org/pldoc/man?section=jsonsupport">builtin library for reading JSON</a>:</p>
<pre><code>
:- use_module(library(http/json)).
read_json_file(FileName, Terms) :-
open(FileName, read, Stream),
json_read(Stream, Terms),
close(Stream).
</code></pre>
<p>For convenience, I'm adding the loaded file to the Prolog database using <a href="https://www.swi-prolog.org/pldoc/doc_for?object=assert/1">assert/1</a>:</p>
<pre style="overflow: scroll;"><code>
?- read_json_file('c:\\smallexample\\stats.json',F), assert(testfile(F)).
F = json([hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json(...), ... = ...|...]).
</code></pre>
<p>Now that we can load the stats file we can start by performing simple queries. For example we can start by looking at top-level properties:</p>
<pre style="overflow: scroll;"><code>
?- testfile(json(Contents)), member(Name=_,Contents).
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = hash ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = version ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = time ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = builtAt ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
Name = publicPath ;
Contents = [hash='71029f66a2fb5a3de779', version='5.70.0', time=3694, builtAt=1649775116882, publicPath=auto, outputPath='C:\\smallexample\\public', assetsByChunkName=json([...]), assets=[...], ... = ...|...],
...
</code></pre>
<p>Here notice, that I'm using <a href="https://www.swi-prolog.org/pldoc/doc_for?object=member/2">member/2</a> to get the name of the properties in the main file.</p>
<p>By the way, as a side note, yesterday I learned that you can exclude variables from Prolog results using the following (<a href="https://stackoverflow.com/questions/43183904/prolog-ignore-unwanted-variables-in-the-output">Stack overflow question here</a>) goal:</p>
<pre><code>
set_prolog_flag(toplevel_print_anon, false).
</code></pre>
<p>With this nice tip, we can exclude variables that start with underscore from the results:</p>
<pre><code>
?- testfile(json(_Contents)), member(Name=_, _Contents).
Name = hash ;
Name = version ;
Name = time ;
Name = builtAt ;
Name = publicPath ;
Name = outputPath ;
Name = assetsByChunkName ;
Name = assets ;
Name = chunks ;
Name = modules ;
Name = entrypoints ;
Name = namedChunkGroups ;
Name = errors ;
Name = errorsCount ;
Name = warnings ;
Name = warningsCount ;
Name = children.
</code></pre>
<p>Now I can access the <code>modules</code> section to extract the <code>reasons</code> property. This property has information on modules that depend on the current module. For example say that we have a small TypeScript program that have the following structure:</p><p> </p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKyFvwgDZJRhPkkmNwPSlYCKYnRc3bFDsmJ6TTfefVqlIBx7AuTZ_hKkiwIjDosNCIM_xhIMcrWVT2a62Evei8RKjilXQR5qcMwS8qzumdkUvAiinzgW7smkYjkAhaeO_iSiFPfcoHii3pala4Tsq8KAQUWS1Ryd7z25DUaUUakqv3zyQlRVKu9LKMvQ/s605/sampletsprj.jpg" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="180" data-original-width="605" height="144" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKyFvwgDZJRhPkkmNwPSlYCKYnRc3bFDsmJ6TTfefVqlIBx7AuTZ_hKkiwIjDosNCIM_xhIMcrWVT2a62Evei8RKjilXQR5qcMwS8qzumdkUvAiinzgW7smkYjkAhaeO_iSiFPfcoHii3pala4Tsq8KAQUWS1Ryd7z25DUaUUakqv3zyQlRVKu9LKMvQ/w486-h144/sampletsprj.jpg" width="486" /></a></div><br /> <br /><p></p>
<p> We can start the exploration of this project by looking at the contents of the <code>modules</code> objects.</p>
<pre><code>
?- testfile(json(_Contents)),
| member( ('modules'=_Modules), _Contents),
| member( json(_ModulePropsList), _Modules),
| member( ('name'=ModuleName), _ModulePropsList).
ModuleName = './src/index.ts' ;
ModuleName = './src/parser.ts' ;
ModuleName = './src/FuncApply.ts' ;
ModuleName = './src/NumLiteral.ts' ;
ModuleName = './src/SymbolObj.ts' ;
ModuleName = './src/BaseObject.ts' ;
ModuleName = 'webpack/runtime/define property getters' ;
ModuleName = 'webpack/runtime/hasOwnProperty shorthand' ;
ModuleName = 'webpack/runtime/make namespace object' ;
</code></pre>
<p>We can create a new goal with the code above which we can use later:</p>
<pre><code>
module_name(json(ContentsList), Name) :-
member(('modules'=Modules), ContentsList),
member(json(ModulePropertiesList), Modules),
member('name'=Name, ModulePropertiesList).
module_properties_by_name(json(ContentsList), Name, ModulePropertiesList) :-
member(('modules'=Modules), ContentsList),
member(json(ModulePropertiesList), Modules),
member('name'=Name, ModulePropertiesList).
</code></pre>
<p> Now that we located the modules, we can get the contents of the <code>reasons</code> property. </p>
<pre><code>
?- testfile(_Json),
| module_properties_by_name(_Json, './src/BaseObject.ts', _Props),
| member((reasons=_Reasons), _Props),
| member(json([_|[RefModName|_]]), _Reasons).
RefModName = (module='./src/FuncApply.ts') ;
RefModName = (module='./src/FuncApply.ts') ;
RefModName = (module='./src/NumLiteral.ts') ;
RefModName = (module='./src/NumLiteral.ts') ;
RefModName = (module='./src/SymbolObj.ts') ;
RefModName = (module='./src/SymbolObj.ts') ;
false.
</code></pre>
<p>(Repeated results seem to indicate different "reasons")</p>
<p>With this data we can generate <a href="https://graphviz.org/">Graphviz</a> representation (for example the one used in the graph above).
<pre><code>
name_modules([], [], _).
name_modules([ModName|Rest], [ModNamePair|RestResult], Counter) :-
number_string(Counter, CounterStr),
string_concat('M', CounterStr, ModuleId),
ModNamePair = ModName - ModuleId,
NewCounter is Counter + 1,
name_modules(Rest, RestResult, NewCounter).
module_dependencies_by_reason(File, (Name-Referencer)) :-
module_name(File, Name),
module_properties_by_name(File, Name,Props),
member((reasons=R), Props),
member(json([_|[(module=Referencer)|_]]),R).
generate_node_descriptions([],Result, Result).
generate_node_descriptions([(Name-Id)|Rest],TmpResult, OutStr) :-
format(atom(Tmp3), '~a[label="~a"];\n', [Id, Name]),
string_concat(TmpResult, Tmp3, OutStrTmp),
generate_node_descriptions(Rest, OutStrTmp, OutStr).
generate_node_relations([], _, Result, Result).
generate_node_relations([(Target-Src)|Rest], NodeIds, TmpResult, Result) :-
get_assoc(Src, NodeIds , SrcCode),
get_assoc(Target, NodeIds , TargetCode),
format(atom(RelationStr), '~a -> ~a;\n', [SrcCode, TargetCode]),
string_concat(TmpResult, RelationStr, NewTmpResult),
generate_node_relations(Rest, NodeIds, NewTmpResult, Result), !.
generate_node_relations([_|Rest], NodeIds, TmpResult, Result) :-
generate_node_relations(Rest, NodeIds, TmpResult, Result),!.
dot_file_from_reasons(File, DotFileStr) :-
findall(Name, module_name(File, Name), NameList),
name_modules(NameList, CodedList, 0),
list_to_assoc(CodedList, AssocNameModList),!,
setof(Pairs, module_dependencies_by_reason(File, Pairs), PairList),
generate_node_descriptions(CodedList, 'digraph G {\n', DotFileStrTmp1),
generate_node_relations(PairList, AssocNameModList, DotFileStrTmp1, DotFileStrTmp2),
string_concat(DotFileStrTmp2, '}', DotFileStr).
</code></pre>
<p>I am impressed by the power of Prolog. I have always admired the way it <a href="https://langexplr.blogspot.com/2019/03/a-quick-note-about-programming-in-prolog.html">works differently dependending on how you use it</a>. For example the way <a href="https://www.swi-prolog.org/pldoc/man?predicate=member/2">member/2</a> was used above to extract internal elements from terms. One would assume that this predicate is only used to test list membership. However by the power of Prolog unification and backtracking we can used to explore the contents of a list.</p>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-22883436229514975632021-12-26T16:03:00.000-06:002021-12-26T16:03:15.724-06:00A small programming exercise in APL #2: Combinations<p>In this post I'm going to continue my <a href="https://en.wikipedia.org/wiki/APL_(programming_language)">APL</a> exploration by working in a possible solution for the problem of generating all the <a href="https://en.wikipedia.org/wiki/Combination">combinations</a> of 'n' elements of an array.</p>
<p>Generating the 'n' combinations of an array means generating a sequence of all possible 'n' unique elements from the original array . For example, given the array <code>12, 34, 35, 65</code> all possible '2' combinations of this array are:
</p><ul>
<li>12, 34</li>
<li>12, 35</li>
<li>12, 65</li>
<li>34, 35</li>
<li>34, 65</li>
<li>35, 65</li>
</ul>
<p>Notice that order is not important. That is "12, 34" is considered to be the same as "34, 12". Generating all 'n' permutations of the elements of an array may be an interesting problem for a future post. </p>
<p>One of my goals was to be as idiomatic as possible (with my limited APL knowledge!). Because of this, I will try avoid using <a href="https://aplwiki.com/wiki/Branch">explicit loops or conditionals</a> and instead use array operators.</p>
<h3>Strategy</h3>
<p>The general strategy for solving this problem was to calculate all possible boolean arrays having 'n' bits and use <a href="https://aplwiki.com/wiki/Replicate">Compress</a> to extract the elements.</p>
<p>For example, in the array <code>12, 34, 35, 65</code> all possible boolean vectors having two bits <emph>on</emph> are:</p>
<ul>
<li>1 1 0 0</li>
<li>1 0 1 0</li>
<li>1 0 0 1</li>
<li>0 1 1 0</li>
<li>0 1 0 1</li>
<li>0 0 1 1</li>
</ul>
Using these vectors in APL we get the elements we need:
<pre><code>
a
12 34 35 65
1 1 0 0 / a
12 34
1 0 1 0 / a
12 35
1 0 0 1 / a
12 65
0 1 1 0 / a
34 35
0 1 0 1 / a
34 65
0 0 1 1 / a
35 65
</code></pre>
<p>This strategy is not efficient in space or time but it allowed me to explore a solution without using imperative constructs or recursion.</p>
<h3>Generating the boolean arrays</h3>
<p>To generate the boolean arrays we start by generating all integer values required to encode n-bit values:</p>
<pre><code>
a ← 12 34 35 65
⍳ ( ¯1 + 2 * ⍴ a)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
</code></pre>
<p>When converting these numbers to binary we get all possible boolean vectors for 4-bit values. This is same as the same as the length of our sample array. We can see these arrays if we use <a href="https://aplwiki.com/wiki/Encode">Encode</a> and <a href="https://aplwiki.com/wiki/Each">Each</a>:</p>
<pre><code>
{ ((⍴ a) ⍴ 2) ⊤ ⍵ } ¨ ⍳ ( ¯1 + 2 * ⍴ a)
0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0\
1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1
</code></pre>
<p>I can reshape this array to get a better representation: </p>
<pre><code>
15 1 ⍴ { ((⍴ a) ⍴ 2) ⊤ ⍵ } ¨ ⍳ ( ¯1 + 2 * ⍴ a)
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
</code></pre>
<p>Now we are only interested in boolean arrays with 'n' number of '1' bits. For <code>n = 2</code> we can get only those elements using the <a href="https://aplwiki.com/wiki/Replicate">Compress</a> operator: </p>
<pre><code>
seq ← ⍳ ( ¯1 + 2 * ⍴ a)
n ← 2
({ n = +/ ((⍴ a) ⍴ 2) ⊤ ⍵} ¨ seq) / seq
3 5 6 9 10 12
</code></pre>
<p>Again we can visualize these values using <a href="https://aplwiki.com/wiki/Reshape">reshape</a> and encode:</p>
<pre><code>
6 1 ⍴ { ((⍴ a) ⍴ 2) ⊤ ⍵ } ¨ ({ n = +/ ((⍴ a) ⍴ 2) ⊤ ⍵} ¨ seq) / seq
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
</code></pre>
<h3>Selecting desired elements</h3>
<p>Now that we have our boolean arrays we can pick all the values using <a href="https://aplwiki.com/wiki/Replicate">Compress</a>: </p>
<pre><code>
{(((⍴ a) ⍴ 2) ⊤ ⍵)/a} ¨ ({ n = +/ ((⍴ a) ⍴ 2) ⊤ ⍵} ¨ seq) / seq
35 65 34 65 34 35 12 65 12 35 12 34
</code></pre>
<p>And again we can reshape this array to see it better:</p>
<pre><code>
6 1 ⍴ {(((⍴ a) ⍴ 2) ⊤ ⍵)/a} ¨ ({ n = +/ ((⍴ a) ⍴ 2) ⊤ ⍵} ¨ seq) / seq
35 65
34 65
34 35
12 65
12 35
12 34
</code></pre>
<p> Finally we can pack these expressions in a function: </p>
<pre><code>
∇r←a ncombinations1 n;seq
seq ← ⍳ ( ¯1 + 2 * ⍴ a)
r ← {(((⍴ a) ⍴ 2) ⊤ ⍵)/a} ¨ (({ n = +/ ((⍴ a) ⍴ 2) ⊤ ⍵} ¨ seq) / seq\
)
∇
</code></pre>
<p>We can use it like this:</p>
<pre><code>
1 2 3 4 5 ncombinations1 3
3 4 5 2 4 5 2 3 5 2 3 4 1 4 5 1 3 5 1 3 4 1 2 5 1 2 4 1 2 3
</code></pre>
<p>APL has a build-in <a href="https://aplwiki.com/wiki/Binomial">Binomal</a> operator which allows us to calculate the number of combinations. For example: </p>
<pre><code>
a ← 1 2 3 4 5
(3 ! ⍴ a) = ⍴ a ncombinations3 3
1
</code></pre>
<h3>Final words</h3>
<p>It was very interesting (and difficult) to try to write a solution of this problem using only array operations. Reading the definion of the <code>ncombinations1</code> I noticed that there are many expressions nested in parenthesis (maybe related to my limited APL knowledge). I know that APL developers value terseness, so I tried to reduce the size of the expressions. Here is a new version: </p>
<pre><code>
∇r←a ncombinations3 n;seq
s ← ⍳ ( ¯1 + 2 * ⍴ a)
b ← 2⍴⍨⍴a
r ← {a/⍨b⊤⍵}¨s/⍨{n=+/b⊤⍵}¨s
∇
</code></pre>
<p>I was able to remove a couple of parenthesis by taking advantage of the <a href="https://aplwiki.com/wiki/Commute">Commute</a> operator.</p>
<p><a href="https://www.gnu.org/software/apl/">GNU APL</a> was used to create the examples in this post.</p>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-2094194832894997082021-07-26T17:55:00.000-06:002021-07-26T17:55:54.830-06:00A small programming exercise in APL #1This post shows a possible solution written in APL for the following programming problem:
<blockquote>
Given an array, determine if a value <code>'number'</code> is found in every consecutive segment of <code>'size'</code> elements.
</blockquote>
<p>For example, given this array:</p>
<pre><code>
1,2,1,3,4,1
</code></pre>
<p>This predicate is true for <code>number = 1</code> and <code>size = 2</code>. Because '1' is found in (1,2), (1,3) and (4,1).</p>
<h2>A possible APL solution</h2>
This is a possible solution to this problem (using my limited APL knowledge).
<pre><code>
∇ z←array arraysegments args
number ← args[1]
size ← args[2]
z ← ∧/ ({number∊⍵} ⍤1) (((⍴ array) ÷ size) , size) ⍴ array
∇
</code></pre>
<p>This function is called <code>arraysegments</code> and is a dyadic function. It receives the array to validate as the left argument and on the right argument a two-value array with the value ('number') to find inside the array segment and the length of the segments.</p>
<p>An example of using this function</p>
<pre><code>
1 2 1 3 4 1 arraysegments 1 2
1
1 2 1 3 4 1 arraysegments 2 2
0
1 2 1 3 4 1 arraysegments 1 3
1
300 200 300 300 400 500 arraysegments 300 3
1
300 200 300 300 400 500 arraysegments 400 3
0
</code></pre>
<p>To see how this function works I'm going to start by defining some sample data:</p>
<pre><code>
array ← 1 2 1 3 4 1
number ← 1
size ← 3
</code></pre>
<p>1. First, start by <a href='https://aplwiki.com/wiki/Reshape'>reshaping</a> the input array into a matrix with each row being </p>
<pre><code>
(((⍴ array) ÷ size) , size)
2 3
(((⍴ array) ÷ size) , size) ⍴ array
1 2 1
3 4 1
</code></pre>
<p>2. Now that we have the 'groups' as the rows of the new matrix, we apply the membership operation to each element of the matrix. To do this, we use the <a href='https://aplwiki.com/wiki/Rank'>rank operator</a> in conjunction with an inline function to test the membership:</p>
<pre><code>
({number∊⍵} ⍤1) (((⍴ array) ÷ size) , size) ⍴ array
1 1
</code></pre>
<p>As a final step we apply the <a href='https://aplwiki.com/wiki/Reduce'>reduce operator '/'</a> with the <a href='https://aplwiki.com/wiki/And'>And operator</a> to see if the input number exists in every group:</p>
<pre><code>
∧/ ({number∊⍵} ⍤1) (((⍴ array) ÷ size) , size) ⍴ array
1
</code></pre>
<p>There are some problem with this solution. For example if the array cannot be splitted in groups of the specified size you get a runtime error.</p>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-28486946449979646872021-06-13T17:26:00.000-06:002021-06-13T17:26:30.692-06:00Reading APL #1: Roman numerals to decimal<p>As part of a new recurring series I’m going to take a small <a href="https://en.wikipedia.org/wiki/APL_(programming_language)">APL</a> function or program and try to break it down in to its parts. I hope this is going to help me get a better understanding of the language.</p>
<h2 id="reading-apl">Reading APL</h2>
<p>This article: <a href="https://computerhistory.org/blog/the-apl-programming-language-source-code/">The APL Programming Language Source Code</a> has a nice introduction to the language and its history. One sentence in this article is key to understand how to read APL code:</p>
<blockquote>
<p><i>Order of evaluation: Expressions in APL are evaluated right-to-left, and there is no hierarchy of function precedence</i></p>
</blockquote>
<p>Two additional concepts are useful to understand when trying to read code:</p>
<ol type="1">
<li>A <a href="https://aplwiki.com/wiki/Monadic_function">monadic function</a> : an operation applied to the right expression</li>
<li>A <a href="https://aplwiki.com/wiki/Dyadic_function">dyadic function</a> : a function applied to two arguments ( left and right )</li>
</ol>
<p>One example of these elements is the following:</p>
<pre><code> 2 2 ⍴⍳⍴ 8 8 8 8
1 2
3 4</code></pre>
<p>Here is an example of evaluating this expression from right to left.</p>
<pre><code> myarray←8 8 8 8
myarray
8 8 8 8
length_of_my_array← ⍴ myarray
length_of_my_array
4
new_array← ⍳ length_of_my_array
new_array
1 2 3 4
2 2 ⍴ new_array
1 2
3 4</code></pre>
<p>Note that here we use <code>⍴</code> both as a monadic function (<a href="https://aplwiki.com/wiki/Shape">Shape</a>) and as a dyadic function (<a href="https://aplwiki.com/wiki/Reshape">Reshape</a>).</p>
<h2 id="the-example">The example</h2>
<p>For this post I’m going to use a small function I found in the <a href="https://github.com/blakemcbride/APLUtils">APL Utils repository by Blake McBride</a> . This function takes a string representing a roman number and converts it back to an integer:</p>
<pre><code>∇z←Romanu a
z←+/(¯1+2×z≥1↓z,0)×z←(1 5 10 50 100 500 1000)['IVXLCDM'⍳a]
∇</code></pre>
<p>An example of executing this function:</p>
<pre><code> Romanu 'XVII'
17
Romanu 'IX'
9</code></pre>
<h2 id="reading-this-function">Reading the code</h2>
<p>Let’s start by reading the function definition:</p>
<pre><code>∇z←Romanu a
...
∇</code></pre>
<p>This code represents the definition of the <code>Romanu</code> function with an <code>a</code> argument.</p>
<p>Now, the interesting part is reading the body of the function which performs the actual calculations.</p>
<pre><code>z←+/(¯1+2×z≥1↓z,0)×z←(1 5 10 50 100 500 1000)['IVXLCDM'⍳a]</code></pre>
<p>As described in the previous section we need to read this code from right to left. To do this we need to ‘parse’ it and extract the largest complete expression from the right:</p>
<pre><code>(1 5 10 50 100 500 1000)['IVXLCDM'⍳a]</code></pre>
<p>This expression is a particular example of an <strong><em>bracked indexing</em></strong> expression(https://aplwiki.com/wiki/Bracket_indexing). A simpler example of this is:</p>
<pre><code> (10 20 30)[1]
10
(10 20 30)[2]
20
(10 20 30)[3]
30
(10 20 30)[3 1 1 2]
30 10 10 20
a←10 20 30
a[3 1 1 2]
30 10 10 20</code></pre>
<p>As shown above this expression is used to select elements of an array into a new array.</p>
<p>In the <code>Romanu</code> function this expression is used to assign a value to eacho of the roman numeral 'digits':</p>
<pre><code>'IVXLCDM'⍳a</code></pre>
<p>Here the dyadic form of <code>⍳</code> or ‘Index of’(https://aplwiki.com/wiki/Index_Of) . This expression returns the indices of the left side array of the elements on the right. Here are some examples of this expression in action:</p>
<pre><code> (10 20 30) ⍳ (20 20 10 20 30 10)
2 2 1 2 3 1</code></pre>
<p>When using this expression with the roman digits string we get the equivalent positions:</p>
<pre><code> 'IVXLCDM' ⍳ 'XVII'
3 2 1 1</code></pre>
<p>As shown above we get the positions in the roman digits string. Returning to our original expression we use the selection expression to get the value of each roman digit in decimal form:</p>
<pre><code> (1 5 10 50 100 500 1000)['IVXLCDM' ⍳ 'XVII']
10 5 1 1</code></pre>
<p>As you can see here we almost have the result for the conversion of <code>XVII</code>. We just have to sum these numbers up to get 17.</p>
<p>Going back to the example and continuing reading for right to left we find and assignment to the <code>z</code> variable.</p>
<pre><code>z←(1 5 10 50 100 500 1000)['IVXLCDM'⍳a]</code></pre>
<p>The rest of the expression is going to take care of subtracting the value required for converting numbers like: ‘IX’.</p>
<p>Reading the expression from right to left we find:</p>
<pre><code>(¯1+2×z≥1↓z,0)×z←(1 5 10 50 100 500 1000)['IVXLCDM'⍳a]</code></pre>
<p>This expression is a multiplication (<code>×</code>). For arrays it applies to operation element wise :</p>
<pre><code> 2 3 × 4 5
8 15</code></pre>
<p>The interesting part here is the expression being used for the left operand of the multiplication:</p>
<pre><code>(¯1+2×z≥1↓z,0)</code></pre>
<p>Again we are going to analyze this expression from right to left.</p>
<pre><code>z,0</code></pre>
<p>This expression returns the an array with a zero at the end:</p>
<pre><code> (10 20 30),0
10 20 30 0
z←(1 5 10 50 100 500 1000)['IVXLCDM' ⍳ 'IX']
z,0
1 10 0</code></pre>
<p>Then the following operation <em>drops</em> the first element of the array:</p>
<pre><code> 1↓z,0
10 0</code></pre>
<p>The <em>drop</em> expression returns an array without the first ‘n’ elements:</p>
<pre><code> 3 ↓ 20 30 40 30 20 10
30 20 10</code></pre>
<p>The following section is very interesting . We use the greater equal expression <code>≥</code> to determine which elements of the array are greater or equal than the second array:</p>
<pre><code> 10 20 30 ≥ 5 21 30
1 0 1</code></pre>
<p>Applying this to our example for ‘IX’:</p>
<pre><code> z←(1 5 10 50 100 500 1000)['IVXLCDM' ⍳ 'IX']
z≥1↓z,0
0 1</code></pre>
<p>This is interesting: we get an array that indicates which entries are lower than its successor. In the case of IX we are getting <code>0 1</code> saying that the first digit needs to be subtracted from the second. The final part performs this operation.</p>
<pre><code> z←(1 5 10 50 100 500 1000)['IVXLCDM' ⍳ 'IX']
z≥1↓z,0
0 1
¯1+2×z≥1↓z,0
¯1 1
(¯1+2×z≥1↓z,0)×z
¯1 10</code></pre>
<p>Now we can finally sum all the numbers on the resulting array and get the decimal number. This is performed with the reduce operation <code>/</code> (https://aplwiki.com/wiki/Reduce) with the <code>+</code> operator.</p>
<pre><code> +/ 10 20 30
60
10 + 20 + 30
60</code></pre>
<p>Applying this operation to our partial expression returns the expected value:</p>
<pre><code> (¯1+2×z≥1↓z,0)×z
¯1 10
+/(¯1+2×z≥1↓z,0)×z
9</code></pre>
<p>We can see this process in action by executing all the parts with an interesting number like <code>MMCXXIX</code> (2129).</p>
<pre><code> z←(1 5 10 50 100 500 1000)['IVXLCDM'⍳a]
z
1000 1000 100 10 10 1 10
z,0
1000 1000 100 10 10 1 10 0
1↓z,0
1000 100 10 10 1 10 0
z≥1↓z,0
1 1 1 1 1 0 1
¯1+2×z≥1↓z,0
1 1 1 1 1 ¯1 1
+/(¯1+2×z≥1↓z,0)×z
2129</code></pre>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-36224187415245787662021-06-05T16:11:00.000-06:002021-06-05T16:11:53.187-06:00A small experiment with fragment shaders<p>
I wanted to work on an experiment that allowed me to learn a little bit about <b>modern</b> graphics programming with OpenGL (with shaders that is). A nice choice is the 'hello world; of graphics programming: rendering the Mandelbrot set.
</p>
<p>
In this post I'm going to record my experiences from zero to a basic rendering of the Mandelbrot set. Here is how the final product looks like:
</p>
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhSrFs2fBA7FdWBQv4KxKRWx8MWLSbgjaV50dIu2Q1UYJZGC2d6AuZmjEGqYeQH_z2A3ef0LxLlT0wMuKLmEKDtth2u-5CetKivNK_4nyePB8nwnyyPTGPXoR11IjNQR_IylMS_1wVMAo1W/s799/simplemandel.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="320" data-original-height="616" data-original-width="799" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhSrFs2fBA7FdWBQv4KxKRWx8MWLSbgjaV50dIu2Q1UYJZGC2d6AuZmjEGqYeQH_z2A3ef0LxLlT0wMuKLmEKDtth2u-5CetKivNK_4nyePB8nwnyyPTGPXoR11IjNQR_IylMS_1wVMAo1W/s320/simplemandel.png"/></a></div>
<h3 id="org486f89d"><span class="section-number-3">1.1</span> The experiment</h3>
<p>
To get the "native" feel I decided to create the example as a C++ Windows program (but using mostly C). There are many options to do this, but the following combination worked for me:
</p>
<ul class="org-ul">
<li>A C++ Compiler : Visual Studio build tools</li>
<li>An IDE: VSCode C++ integration (<a href="https://code.visualstudio.com/docs/cpp/config-msvc">https://code.visualstudio.com/docs/cpp/config-msvc</a>)</li>
<li>OpenGL libraries and loader: Windows SDK (<a href="https://developer.microsoft.com/en-us/windows/downloads/windows-10-sdk/">https://developer.microsoft.com/en-us/windows/downloads/windows-10-sdk/</a>) + GLAD (<a href="https://glad.dav1d.de/">https://glad.dav1d.de/</a>)</li>
<li>A build system (although the experiment is quite small): CMake</li>
<li>A simple GUI library: GFLW (<a href="https://www.glfw.org/">https://www.glfw.org/</a>)</li>
</ul>
<p>
I'm quite impressed with the VSCode C++ support .
</p>
<h3 id="orgdff4e56"><span class="section-number-3">1.2</span> The program</h3>
<p>
The structure of the program it's very simple since it is a hello world program. We start with some initialization boilerplate (quite short since GLFW abstracts away many windowing system details):
</p>
<pre class="example">
GLFWwindow *window;
glfwSetErrorCallback(error_callback);
if (!glfwInit())
{
return -1;
}
window = glfwCreateWindow(
800,
600,
"Shader example",
NULL,
NULL);
if (!window)
{
glfwTerminate();
return -1;
}
glfwMakeContextCurrent(window);
gladLoadGL();
</pre>
<p>
This code creates a 800x600 window ready to use with OpenGL. To access OpenGL I'm using a loaded called GLAD.
</p>
<h3 id="org3557352"><span class="section-number-3">1.3</span> Strategy for rendering the Mandelbrot set</h3>
<p>
In this experiment I am going to use the <a href="https://en.wikipedia.org/wiki/Plotting_algorithms_for_the_Mandelbrot_set#Unoptimized_na%C3%AFve_escape_time_algorithm">"escape time algorithm"</a> to render the image of the Mandelbrot set. This algorithm is very simple and easy to implement using fragment shaders.
</p>
<p>
Before we start implementing this algorithm we are going to define geometry to and apply a fragment shader to it. Since we are going to render a 2D image, the easiest way to do this is to create two triangles that fill the viewport. Since OpenGL uses normalized coordinates we can define this triangles using values between -1.0 and 1.0 using the following code:
</p>
<pre class="example">
GLfloat vertices[] = {
-1.0f, 1.0f,
1.0f, 1.0f,
1.0f, -1.0f,
1.0f, -1.0f,
-1.0f, -1.0f,
-1.0f, 1.0f};
GLuint vertex_buffer;
glGenBuffers(1, &vertex_buffer);
glBindBuffer(GL_ARRAY_BUFFER, vertex_buffer);
glBufferData(
GL_ARRAY_BUFFER,
sizeof(vertices),
vertices,
GL_STATIC_DRAW);
</pre>
<p>
This code is going to define two triangles that are highlighted here:
</p>
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhau7i2S9xCtvkX3SxLg5gngNGxUFGjjI03o0_PNWvYhlUq7ldYilqXcYciGD95eOWdvSlnJNMzaYbZm2sBl2mBAjWPfy1C-LVoWU8aZOY-kTIuEsAekCBxh1y5TUlNP93Km2wFIYBrnDRQ/s804/mandeltrangles.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="320" data-original-height="650" data-original-width="804" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhau7i2S9xCtvkX3SxLg5gngNGxUFGjjI03o0_PNWvYhlUq7ldYilqXcYciGD95eOWdvSlnJNMzaYbZm2sBl2mBAjWPfy1C-LVoWU8aZOY-kTIuEsAekCBxh1y5TUlNP93Km2wFIYBrnDRQ/s320/mandeltrangles.png"/></a></div>
<p>
This code is also making these coordinates as the active ones (glBindBuffer).
</p>
<p>
Now we need both a vertex shader to apply transformations to the vertex data and a fragment shader to provide color to our pixels.
</p>
<p>
Our vertex shader is really simple since we are not performing transformations to the triangles:
</p>
<pre class="example">
#version 110
attribute vec2 pos;
void main() {
gl_Position = vec4(pos, 0.0, 1.0);
}
</pre>
<p>
In this vertex shader we can manipulate the vertices of the triangles that we are going to draw. The X and Y values of the vertices are passed using the <b>pos</b> attribute. This is not automatic, we need to specify the data that is passed to the vertex shader in the C++ program for the <b>pos</b> attribute. This is accomplished by using the following code:
</p>
<pre class="example">
GLuint vpos_location;
vpos_location = glGetAttribLocation(program, "pos");
glEnableVertexAttribArray(vpos_location);
glVertexAttribPointer(
vpos_location,
2,
GL_FLOAT,
GL_FALSE,
sizeof(float) * 2, 0);
</pre>
<p>
One of the most interesting aspects of this snippet is the [glVertexAttribPointer](<a href="https://www.khronos.org/registry/OpenGL-Refpages/gl4/html/glVertexAttribPointer.xhtml">https://www.khronos.org/registry/OpenGL-Refpages/gl4/html/glVertexAttribPointer.xhtml</a>). This function specifies the way the values are going to be extracted from the array data. Here we specify:
</p>
<ol class="org-ol">
<li><b>vpos_location</b> the attribute that we are configuring</li>
<li><b>2</b> the number of components (remember that <b>pos</b> is <b>vec2</b>)</li>
<li><b>GL_FLOAT</b> the data type of the data element</li>
<li><b>GL_FALSE</b> the data is not normalized. This seems to be important for integer data (here we use floating point data, more info here: <a href="https://gamedev.stackexchange.com/questions/10859/glvertexattribpointer-normalization">https://gamedev.stackexchange.com/questions/10859/glvertexattribpointer-normalization</a>).</li>
<li><b>sizeof(float) * 2</b> The offset between consecutive elements. This is useful when the array has different kinds of data elements. For example vertices and normals mixed in the same array. This parameter must be used to skip undesired data elements. In our case 0 is also a valid value since we only have vertex data.</li>
</ol>
<p>
The boilerplate code to compile this shader is the following:
</p>
<pre class="example">
GLint shader_compiled;
GLuint vertex_shader;
vertex_shader = glCreateShader(GL_VERTEX_SHADER);
glShaderSource(vertex_shader, 1, &vertex_shader_src, NULL);
glCompileShader(vertex_shader);
glGetShaderiv(vertex_shader, GL_COMPILE_STATUS, &shader_compiled);
if (shader_compiled != GL_TRUE)
{
std::cout << "Vertex shader not compiled";
GLchar message[1023];
GLsizei log_size;
glad_glGetShaderInfoLog(vertex_shader, 1024, &log_size, message);
std::cout << message;
}
</pre>
<p>
When you are starting with shaders, the call to <a href="https://www.khronos.org/registry/OpenGL-Refpages/es2.0/xhtml/glGetShaderiv.xml">glGetShaderiv</a> is useful . This code returns error information that occurred when compiling the shader.
</p>
<p>
There is an important part of the process that is always confusing to me. Many things in the OpenGL API change a global state aspect of the functionality. For example the <a href="https://www.khronos.org/registry/OpenGL-Refpages/gl4/html/glBindBuffer.xhtml">glBindBuffer</a> function used above is going to determine the set of vertices used by the <a href="https://www.khronos.org/registry/OpenGL-Refpages/gl4/html/glDrawArrays.xhtml">glDrawArrays</a> function.
</p>
<p>
Here's the code of the fragment shader:
</p>
<pre class="example">
#version 110
uniform vec4 boundaries;
void main() {
float x0, y0,x ,y;
x0 = gl_FragCoord.x*((boundaries.z - boundaries.x)/800.0) + boundaries.x ;
y0 = gl_FragCoord.y*((boundaries.w - boundaries.y)/600.0) + boundaries.y ;
int maxIteration, iteration;
maxIteration = 256;
iteration = 0;
while((x*x + y*y <= 4.0) && (iteration < maxIteration)) {
float tmp;
tmp = x*x - y*y + x0;
y = 2.0*x*y + y0;
x = tmp;
iteration = iteration + 1;
}
gl_FragColor = vec4(vec3(0.0, float(iteration)/256.0, 0.0 ),1.0);
}
</pre>
<p>
This code contains a simple implementation of the escape time algorithm described in Wikipedia here: <a href="https://en.wikipedia.org/wiki/Plotting_algorithms_for_the_Mandelbrot_set#Unoptimized_na%C3%AFve_escape_time_algorithm">https://en.wikipedia.org/wiki/Plotting_algorithms_for_the_Mandelbrot_set#Unoptimized_naïve_escape_time_algorithm</a> .
</p>
<p>For simplicity this shader chooses only between shades of green for the colors.</p>
<h3 id="org9bafbe4"><span class="section-number-3">1.4</span> Zooming in</h3>
<p>
As part of this experiment I wanted to have the possibility to zoom a particular area of the Mandelbrot set. To add support for this we need to pass the top-left and bottom right coordinates of the area when want to render. This is accomplished by declaring a <a href="https://www.khronos.org/opengl/wiki/Uniform_(GLSL)">uniform</a> to pass this value from the C++ program.
</p>
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjU3-pVbz9lzscSJGLEpRQ3gRXD2xRw6T70-XhmHdxQnS1bhqHO8tmqYzVlXYVk7R9YokLaA8T_u7zUV7TL35v3cqBKj55YmlSq7X3BXvlNDGWhu_QSgRr6TOIr8aMtgtadRAWdI82p8We4/s798/mandelzoomshader.PNG" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="320" data-original-height="628" data-original-width="798" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjU3-pVbz9lzscSJGLEpRQ3gRXD2xRw6T70-XhmHdxQnS1bhqHO8tmqYzVlXYVk7R9YokLaA8T_u7zUV7TL35v3cqBKj55YmlSq7X3BXvlNDGWhu_QSgRr6TOIr8aMtgtadRAWdI82p8We4/s320/mandelzoomshader.PNG"/></a></div>
<p>
Here is the code that uses this parameter in the fragment shader:
</p>
<pre class="example">
uniform vec4 boundaries;
...
x0 = gl_FragCoord.x*((boundaries.z - boundaries.x)/800.0) + boundaries.x ;
y0 = gl_FragCoord.y*((boundaries.w - boundaries.y)/600.0) + boundaries.y ;
</pre>
<p>
And here is the code that specify the value of the <b>boundaries</b> uniform in the C++ program:
</p>
<pre class="example">
int coordinatesUniformLocation = glGetUniformLocation(program, "boundaries");
glUniform4f(coordinatesUniformLocation, boundaries.x1, boundaries.y1, boundaries.x2, boundaries.y2);
</pre>
<p>
We can manipulate the values of the <b>boundaries</b> array using a mouse click handler like this:
</p>
<pre class="example">
glfwSetMouseButtonCallback(window, mouseCallback);
...
void mouseCallback(GLFWwindow* window, int button, int action, int mods) {
if (action == GLFW_PRESS) {
double xpos, ypos;
glfwGetCursorPos(window, &xpos, &ypos);
ypos = 600 - ypos;
double xclick, yclick;
xclick = xpos*((boundaries.x2 - boundaries.x1)/800.0) + boundaries.x1;
yclick = ypos*((boundaries.y2 - boundaries.y1)/600.0) + boundaries.y1;
double currentWidth = (boundaries.x2 - boundaries.x1) - (boundaries.x2 - boundaries.x1)/10;
double currentHeight = (boundaries.y2 - boundaries.y1) - (boundaries.y2 - boundaries.y1)/10;
boundaries.x1 = (float)( xclick - currentWidth/2);
boundaries.x2 = (float)( xclick + currentWidth/2);
boundaries.y1 = (float)( yclick - currentHeight/2);
boundaries.y2 = (float)( yclick + currentHeight/2);
}
}
</pre>
<p>
Finally we define the code draw loop like this:
</p>
<pre class="example">
while (!glfwWindowShouldClose(window))
{
int width, height;
glfwGetFramebufferSize(window, &width, &height);
glViewport(0, 0, width, height);
glClear(GL_COLOR_BUFFER_BIT);
glUseProgram(program);
int coordinatesUniformLocation = glGetUniformLocation(program, "boundaries");
glUniform4f(coordinatesUniformLocation, boundaries.x1, boundaries.y1, boundaries.x2, boundaries.y2);
glDrawArrays(GL_TRIANGLES, 0, 6);
glfwSwapBuffers(window);
glfwPollEvents();
}
</pre>
<h3 id="org5d7f254"><span class="section-number-3">1.5</span> Conclusion</h3>
<p>
This was a fun experiment!. I got a small glimpse on how to work with OpenGL. Future posts are going to explore even further and maybe use other programming languages to explore OpenGL.
</p>
<p>
Code for this experiment can be found here: <a href="https://github.com/ldfallas/openglmandelbrot">https://github.com/ldfallas/openglmandelbrot</a> .
</p>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-78093151823455761952020-02-23T16:56:00.002-06:002020-02-23T16:56:47.310-06:00First programming language: GW-BASIC<p>Like many developers my age, the first programming language I ever used was BASIC. Specifically, GW-BASIC in a nice Epson "Abacus" XT machine with a green-on-black monitor back in primary school.</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVtl12NaBIvD6I_nT-IOiHfdichnReHu6QaTd6MZnDCG4kXrDFSIa60Y1BnIUW8BXxx7rqX5IUfZ6kHvyd4PbOWT1mk36_hdXnt_IyNikrOQWhBs-nymYZJ3ZAETlevZpXfR2tAM3J0Coh/s1600/abacusbasicmanual.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVtl12NaBIvD6I_nT-IOiHfdichnReHu6QaTd6MZnDCG4kXrDFSIa60Y1BnIUW8BXxx7rqX5IUfZ6kHvyd4PbOWT1mk36_hdXnt_IyNikrOQWhBs-nymYZJ3ZAETlevZpXfR2tAM3J0Coh/s320/abacusbasicmanual.jpg" width="224" height="320" data-original-width="300" data-original-height="429" /></a></div>
<p>For me, the experience of writing my first program was magical. Having feedback from the computer with just few key strokes was an essential part of it.</p>
<pre><code>10 PRINT "hola"
RUN
hola</code></pre>
<p>Writing a small/toy implementation of GW-BASIC may be a good exercise and a homage to this programming language. In the following posts I'm going to write about the ongoing experience of doing this.</p>
<p>As with other posts in this blog I'm going to try to write this program using a language I'm learning. For this task I'll be using Rust. <a href="https://www.rust-lang.org/">Rust</a> is a very interesting language with many concepts to learn. For me the only way of learning a new programming language is trying to use it to implement something.</p>
<p>The repo for work in this small project it's located here: <a href="https://github.com/ldfallas/rgwbasic">https://github.com/ldfallas/rgwbasic</a> .</p>
<p>The current implementation still lacks of most of the features to make it a useful (or usable) implementation. But at least you can write:</p>
<pre><code>$ cargo run
...
Finished dev [unoptimized + debuginfo] target(s) in 0.05s
Running `target/debug/rgwbasic`
Ok
10 print "hello"
Ok
20 goto 10
Ok
run
"HELLO"
"HELLO"
"HELLO"
"HELLO"
"HELLO"
...</code></pre>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-622163088567210432019-03-10T17:54:00.000-06:002019-03-10T17:54:18.821-06:00A quick note about programming in Prolog<p>Prolog predicates work in different ways depending on how you use them. A simple example is the <code>append</code> predicate. One may say that <code>append</code> is used to get the result of appending two lists. For example:</p>
<pre><code>?- append([1,2,3], [4,5,6], NewList).
NewList = [1, 2, 3, 4, 5, 6].</code></pre>
<p>But we can also use <code>append</code> to get the prefix of a list given a suffix.</p>
<pre><code>?- append(Prefix, [5,6], [1,2,3,4,5,6]).
Prefix = [1, 2, 3, 4] ;</code></pre>
<p>Or we can get all the possible combinations of lists that can concatenated produce a specified list:</p>
<pre><code>?- append(First, Second, [1,2,3,4,5,6]).
First = [],
Second = [1, 2, 3, 4, 5, 6] ;
First = [1],
Second = [2, 3, 4, 5, 6] ;
First = [1, 2],
Second = [3, 4, 5, 6] ;
First = [1, 2, 3],
Second = [4, 5, 6] ;
First = [1, 2, 3, 4],
Second = [5, 6] ;
First = [1, 2, 3, 4, 5],
Second = [6] ;
First = [1, 2, 3, 4, 5, 6],
Second = [] ;</code></pre>
<p>This is a powerful concept that is accomplished by Prolog's execution mecanism which involves unification, resolution and backtracking. This mechanism tries to find a way to bind <em>free</em> variables so the goal makes sense.</p>
<p>Recently, I found an example of this behavior while writing some quick experiments with a JavaScript parser I'm working on (which deserves a separate post).</p>
<p>It all started while trying to define a predicate to translate from a JavaScript <code>switch</code> statement to an equivalent sequence of <code>if</code>/<code>else</code> statements. An example of this conversion it's take the following statement:</p>
<pre><code>switch(myVar) {
case 1:
print('one');
break;
case 2:
print('two');
break;
}</code></pre>
<p>And convert it to something like:</p>
<pre><code>if (myVar == 1) {
print('one');
} else if (myVar == 2) {
print('two');
}</code></pre>
<p>A simple version of a predicate that performs this conversion is the following:</p>
<pre><code>switch_if(js_switch(js_identifier(Variable, _),
Cases,
_),
IfStat) :-
switch_if_cases(Variable, Cases, IfStat).
switch_if_cases(Variable,
[js_case(Value, Body, _)|Rest],
js_if(Comparison,
js_block(NoBreakBody, _),
RestIf,
_)) :-
value_comparison(Comparison, Variable, Value),
body_with_no_break(Body, NoBreakBody),
switch_if_cases(Variable, Rest, RestIf).
switch_if_cases(Variable,
[js_default( Body, _)],
js_block(NoBreakBody, _)) :-
body_with_no_break(Body, NoBreakBody).
value_comparison(js_binary_operation(
equals_op,
js_identifier(Variable, _),
Value,
_),
Variable, Value).
body_with_no_break([js_break(_)], []).
body_with_no_break([Stat|Rest1], [Stat|Rest2]) :-
body_with_no_break(Rest1, Rest2)</code></pre>
<p>Here's an example of using the <code>switch_if</code> predicate to convert a small code snippet. The input contains a <code>switch</code> statement. The result is unified in the <code>IfString</code> variable.</p>
<pre><code>?- parse_js_stat_string("switch(w) {
case 1:
print('first');
break;
case 2:
print('second');
break;
default:
print('Nothing');
break;
}", SwitchAst), switch_if(SwitchAst, IfAst), print_js_ast_to_string(IfAst, IfString), writef(IfString).
if (w == 1) {
print('first', );
} else if (w == 2) {
print('second', );
} else {
print('Nothing', );
}
SwitchAst = js_switch(...),
IfString = "if (w == 1) {\n print('first', );\n} else if (w == 2) {\n print('second', );\n} else {\n print('Nothing', );\n}"
</code></pre>
<p>The <code>parse_js_stat_string</code> predicate parses a string containing a statement. On success this predicate generates a simple AST representation of the input element as a Prolog term. For example:</p>
<pre><code>?- parse_js_stat_string("switch(w) {
case 1:
print('first');
break;
case 2:
print('second');
break;
default:
print('Nothing');
break;
}", SwitchAst).
SwitchAst = js_switch(js_identifier([119], lex_info(1, [])), [js_case(js_literal(number, [49], lex_info(2, [ws(19, false)])), [js_expr_stat(js_call(js_identifier([112, 114|...], lex_info(3, [ws(..., ...)])), js_arguments([js_literal(string, [...|...], lex_info(..., ...))], lex_info(3, [], 3, [])), null)), js_break(lex_info(4, [ws(43, true)]))], lex_info(2, [ws(11, true)])), js_case(js_literal(number, [50], lex_info(5, [ws(63, false)])), [js_expr_stat(js_call(js_identifier([112|...], lex_info(6, [...])), js_arguments([js_literal(..., ..., ...)], lex_info(6, [], 6, [])), null)), js_break(lex_info(7, [ws(..., ...)]))], lex_info(5, [ws(55, true)])), js_default([js_expr_stat(js_call(js_identifier([...|...], lex_info(..., ...)), js_arguments([...], lex_info(..., ..., ..., ...)), null)), js_break(lex_info(10, [...]))], lex_info(8, [ws(100, true)]))], lex_info(1, []))
</code></pre>
<h2 id="going-the-other-way">Going the other way</h2>
<p>An awesome surprise it's that the <code>switch_if</code> predicate can be used in "the order direction" without any modification. That is, we can specify an <code>if</code> AST and get a <code>switch</code> version of it. Of course this can only be done if the conversion makes sense. For example:</p>
<pre><code>?- parse_js_stat_string("
if (x == 10) {
print('10 val');
} else if (x == 20) {
print('20 val');
} else {
print('None');
}", IfAst), switch_if(SwitchAst, IfAst), print_js_ast_to_string(SwitchAst, SwitchString), writef(SwitchString).
switch(x) {
case 10:
print('10 val', );
break;
case 20:
print('20 val', );
break;
default:
print('None', );
break;
}
IfAst = js_if(js_binary_operation(equals_op,...),
SwitchAst = js_switch(...),
SwitchString = "switch(x) {\n case 10:\n print('10 val', );\n break;\n case 20:\n print('20 val', );\n break;\n default:\n print('None', );\n break;\n}\n"
</code></pre>
<h2 id="several-alternatives-for-converting-between-switch-and-if">Several alternatives for converting between <code>switch</code> and <code>if</code></h2>
<p>One of the most intriguing characteristics of Prolog is the posibility of giving different valid results for a given goal.</p>
<p>For example we can give another posibility to the <code>value_comparison</code> predicate:</p>
<pre><code>value_comparison(js_binary_operation(
equals_op,
js_identifier(Variable, _),
Value,
_),
Variable, Value).
value_comparison(js_binary_operation(
equals_op,
Value,
js_identifier(Variable, _),
_),
Variable, Value).</code></pre>
<p>By doing this what we are saying is that either <code>x == 1</code> and <code>1 == x</code> are valid possibilities for the condition of the <code>if</code> statement replacing a <code>case</code> section.</p>
<p>If we do this we can get more alternatives:</p>
<pre><code>?- quick_switch_if_test("switch(w) {
case 1:
print('first');
break;
case 2:
print('second');
break;
default:
print('Nothing');
break;
}").
if (w == 1) {
print('first', );
} else if (w == 2) {
print('second', );
} else {
print('Nothing', );
}
true ;
if (w == 1) {
print('first', );
} else if (2 == w) {
print('second', );
} else {
print('Nothing', );
}
true ;
if (1 == w) {
print('first', );
} else if (w == 2) {
print('second', );
} else {
print('Nothing', );
}
true ;
if (1 == w) {
print('first', );
} else if (2 == w) {
print('second', );
} else {
print('Nothing', );
}
true ;
false.
</code></pre>
<p>Code for this post can be found <a href="https://github.com/ldfallas/pljsexperiments">here</a>.</p>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-32033020027410570312018-12-29T09:18:00.001-06:002018-12-29T09:18:20.854-06:00Using Racklog for parsing<div id="content">
<div id="outline-container-sec-1" class="outline-2">
<div class="outline-text-2" id="text-1">
<p>
This post shows a small experiment of creating parsing predicates using the <a href="http://docs.racket-lang.org/racklog/">Racket's Racklog</a> package . This package enables the use of logic programming features inside <a href="https://racket-lang.org/">Racket</a>.
</p>
<p>
Logic programming languages, like Prolog, use the <a href="https://en.wikipedia.org/wiki/Definite_clause_grammar">Definite clause grammars</a> syntax for this purpose. In this post this technique is not directly used, the goal is to express the grammar in the same way the DCG syntax is expanded. A nice experiment for a future post is to create macros for hiding state change variables.
</p>
<p>
As always the goal is to experiment with a concept without worrying too much about performance!
</p>
</div>
<div id="outline-container-sec-1-1" class="outline-3">
<h3 id="sec-1-1"><span class="section-number-3">1.1</span> How it looks</h3>
<div class="outline-text-3" id="text-1-1">
<p>
Here's an example of a predicate for parsing an <code>if</code> statement for a fictional language.
</p>
<pre class="example">
(define %if-stat
(%rel (ctxt new-ctxt)
[(ctxt new-ctxt)
(%let (ifkw-ctxt lpar-ctxt rpar-ctxt
cond-ctxt then-ctxt
stats-ctxt else-ctxt end-ctxt)
(%and
((%literal-id "if") ctxt ifkw-ctxt)
(%lpar ifkw-ctxt lpar-ctxt)
(%expression lpar-ctxt cond-ctxt)
(%rpar cond-ctxt rpar-ctxt)
((%literal-id "then") rpar-ctxt then-ctxt)
(%stat then-ctxt stats-ctxt)
((%opt %else-block) stats-ctxt else-ctxt)
(%is new-ctxt (with-result
`(-if ,(parse-context-result cond-ctxt)
,(parse-context-result stats-ctxt)
,(parse-context-result else-ctxt))
else-ctxt))))]))
</pre>
<p>
Running this predicate from the <code>REPL</code> using a string with sample code produces the following output:
</p>
<pre class="example">
racklogexperiments.rkt> (parse-context-result
(cdar
(%which (result-ctxt)
(%if-stat (string-context "if (c) then
foo(c);
else
moo(d);")
result-ctxt))))
'(-if
(-id "c")
(-call-stat (-call "foo" ((-id "c"))))
(-else (-call-stat (-call "moo" ((-id "d"))))))
racklogexperiments.rkt>
</pre>
</div>
</div>
<div id="outline-container-sec-1-2" class="outline-3">
<h3 id="sec-1-2"><span class="section-number-3">1.2</span> Creating parsing predicates</h3>
<div class="outline-text-3" id="text-1-2">
<p>
An important piece that we need to define our parsers it's the "parsing context". This element is represented as as simple structure which keeps track of :
</p>
<ol class="org-ol">
<li>The result or <code>output</code> of the last parser.
</li>
<li>The text used as input for the parser.
</li>
<li>The current position inside the string as a zero-based index.
</li>
</ol>
<pre class="example">
(struct
parse-context
(result text position))
(define (string-context str)
(parse-context '() str 0))
(define (with-result value ctxt)
(struct-copy parse-context ctxt [result value]))
</pre>
<p>
The way we define parsers using <code>Racklog</code> predicates is that we transform an input parsing context to new context. The new context is going to have a the result of the last parsing operation and it will move the position as many characters as consumed by the last parsing operation.
</p>
<p>
We use a couple of parsers as the foundation for all must all other parsers. The first one, <code>%a-char</code> has the next available character as the result.
</p>
<pre class="example">
(define %a-char
(%rel (a-char ctxt new-ctxt)
[(a-char ctxt new-ctxt)
(%is #t (has-more-chars? ctxt))
(%is new-ctxt (get-char-from-context ctxt))
(%is a-char (parse-context-result new-ctxt))
]))
</pre>
<p>
The code for the utility functions used in these parsers is the following:
</p>
<pre class="example">
(define (get-char-from-context ctxt)
(struct-copy
parse-context
ctxt
[result (string-ref (parse-context-text ctxt) (parse-context-position ctxt))]
[position (+ 1 (parse-context-position ctxt))]))
(define (has-more-chars? ctx)
(<
(parse-context-position ctx)
(string-length (parse-context-text ctx))))
</pre>
<p>
The <code>get-char-from-context</code> function creates a new context with the current character as result and advances the context to the next position. We use Racklog unification and <code>%and</code> to chain together the parsing contexts. The following interaction illustrates this:
</p>
<pre class="example">
racklogexperiments.rkt> (define result (%which (c1 result-ctxt)
(%and (%a-char #\a (string-context "abc") c1)
(%a-char #\b c1 result-ctxt))))
racklogexperiments.rkt> result
'((c1 . #<parse-context>) (result-ctxt . #<parse-context>))
racklogexperiments.rkt> (assoc 'result-ctxt result)
'(result-ctxt . #<parse-context>)
racklogexperiments.rkt> (parse-context-result (cdr (assoc 'result-ctxt result)))
#\b
racklogexperiments.rkt> (parse-context-position (cdr (assoc 'result-ctxt result)))
2
racklogexperiments.rkt>
</pre>
<p>
Here we create a very simple parser that recognizes the sequence: "ab" . As presented above, the position of the resulting parsing context is <code>2</code> which is the zero based position inside the string after 'b'.
</p>
</div>
</div>
<div id="outline-container-sec-1-3" class="outline-3">
<h3 id="sec-1-3"><span class="section-number-3">1.3</span> Sequences</h3>
<div class="outline-text-3" id="text-1-3">
<p>
A very useful parser is one that let's you apply another parser zero or more times. The parser that archives this is the following:
</p>
<pre class="example">
(define %p-simple-sequence
(λ (pred)
(%rel (ctxt new-ctxt)
[(ctxt new-ctxt)
(%let (tmp-ctxt tmp-result)
(%or
(%and
(pred ctxt tmp-ctxt)
(%is tmp-result (with-result
(cons (parse-context-result tmp-ctxt)
(parse-context-result ctxt))
tmp-ctxt))
((%p-simple-sequence pred) tmp-result new-ctxt))
(%is new-ctxt ctxt)))])))
(define %p-sequence
(λ (pred)
(%rel ( ctxt new-ctxt)
[(ctxt new-ctxt)
(%let (tmp-ctxt)
(%and
(%is tmp-ctxt (with-result '() ctxt))
((%p-simple-sequence pred)
tmp-ctxt new-ctxt)
))]
)))
</pre>
<p>
We can apply this parser as follows:
</p>
<pre class="example">
racklogexperiments.rkt> (parse-context-result
(cdar (%which (result-ctxt)
((%p-sequence
(%rel (c r) [(c r) (%a-char #\a c r)]))
(string-context "aaaa") result-ctxt))) )
'(#\a #\a #\a #\a)
racklogexperiments.rkt>
</pre>
</div>
</div>
<div id="outline-container-sec-1-4" class="outline-3">
<h3 id="sec-1-4"><span class="section-number-3">1.4</span> Optionals</h3>
<div class="outline-text-3" id="text-1-4">
<p>
Another useful element we need is a way to parse optional elements. We used this in our <code>if</code> example above for the <code>else</code> section.
</p>
<p>
To implement this we use <code>%or</code> to try to parse the optional parser first or succeed with an empty result. Using this technique will enable multiple solutions (see an example of this below).
</p>
<pre class="example">
(define %opt
(λ (parser)
(%rel (ctxt new-ctxt)
[(ctxt new-ctxt)
(%let (tmp-ctxt)
(%and
(%or (parser ctxt new-ctxt)
(%is new-ctxt (with-result '() ctxt)))))])))
</pre>
</div>
</div>
<div id="outline-container-sec-1-5" class="outline-3">
<h3 id="sec-1-5"><span class="section-number-3">1.5</span> Multiple possible ASTs</h3>
<div class="outline-text-3" id="text-1-5">
<p>
One interesting possibility of using a <code>Racklog</code> (or Prolog's DCGs) is that you can get many possible interpretations of the grammar. Although it may not be of practical use it looks rather interesting.
</p>
<p>
An example of these shows up when parsing an <code>if</code> statement with a <i><a href="https://en.wikipedia.org/wiki/Dangling_else">https://en.wikipedia.org/wiki/Dangling_else</a></i> .
</p>
<pre class="example">
(define sample-code
"if (x) then if (y) then foo(); else goo();")
</pre>
<p>
Here there are two possible valid interpretations of this <code>if</code> statement. The default one:
</p>
<pre class="example">
racklogexperiments.rkt> (parse-context-result
(cdar
(%which (result-ctxt)
(%if-stat (string-context sample-code)
result-ctxt))))
'(-if
(-id "x")
(-if
(-id "y")
(-call-stat (-call "foo" ()))
(-else (-call-stat (-call "goo" ()))))
())
racklogexperiments.rkt>
</pre>
<p>
Here's an alternative visualization of this tree:
</p>
<div class="figure">
<p><i><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUfwMzUiZRF2LGvkbxRQeVnr63itIW6EhE61_XSmp41Q4cB6nT3rNTX5fK7NrmvV_2wJyMVfzDzWJAB8szl70PsjhjWXcCX_LN6QLVC_5rxYEfOImBKQ5ho6QOonPBHuav34PR0wEVR8GS/s1600/rckdanglingif1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiUfwMzUiZRF2LGvkbxRQeVnr63itIW6EhE61_XSmp41Q4cB6nT3rNTX5fK7NrmvV_2wJyMVfzDzWJAB8szl70PsjhjWXcCX_LN6QLVC_5rxYEfOImBKQ5ho6QOonPBHuav34PR0wEVR8GS/s320/rckdanglingif1.jpg" width="241" height="320" data-original-width="334" data-original-height="443" /></a></div></i>
</p>
</div>
<p>
We can now ask <code>Racklog</code> for another solution using the <code>%more</code> function. See the result here:
</p>
<pre class="example">
racklogexperiments.rkt> (parse-context-result (cdar (%more)))
'(-if
(-id "x")
(-if (-id "y") (-call-stat (-call "foo" ())) ())
(-else (-call-stat (-call "goo" ()))))
racklogexperiments.rkt>
</pre>
<p>
Here's the other alternative visualization:
</p>
<div class="figure">
<p><i><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLliwahsWItDiw11FaEdDEe_SV3hGmjY-rivXqyHM01AnWp4eklSDSUCkrtfEK1AySx02i3z7zkC1idNwdJyuaUeL7n7Gd1az8tjRKMyp3Yf20tjffob4979J8WsoCjnUKOQVGbjxrsweU/s1600/rckdanglingif2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLliwahsWItDiw11FaEdDEe_SV3hGmjY-rivXqyHM01AnWp4eklSDSUCkrtfEK1AySx02i3z7zkC1idNwdJyuaUeL7n7Gd1az8tjRKMyp3Yf20tjffob4979J8WsoCjnUKOQVGbjxrsweU/s320/rckdanglingif2.jpg" width="320" height="315" data-original-width="353" data-original-height="347" /></a></div></i>
</p>
</div>
</div>
</div>
<div id="outline-container-sec-1-6" class="outline-3">
<h3 id="sec-1-6"><span class="section-number-3">1.6</span> Code</h3>
<div class="outline-text-3" id="text-1-6">
<p>
The code for this post can be found <a href="https://github.com/ldfallas/racketexperiments">here</a>.
</p>
</div>
</div>
</div>
</div>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-87951668486159616362017-05-11T20:53:00.001-06:002017-05-11T20:53:41.835-06:00A small Tetris-like clone using J and ncurses. Part 2<p>This is part two of our Tetris-like clone in J series. In this part we're going to see how the <code>ncurses</code> interface was created.</p>
<h3 id="creating-the-ncurses-ui">Creating the ncurses UI</h3>
<p>To create the user interface we used the <code>ncurses</code> UI using the <code>api/ncurses</code> package. Sadly all interactions with this API makes the code look like straightforward imperative code.</p>
<p>Since we represented the game field using a matrix, we need a way to visualize this matrix. The next snippet shows how we used the <code>wattr_on</code> and <code>mvwprintw</code> functions to print each cell of the game field with the given color.</p>
<pre class="j"><code>drawGame=: 3 : 0
matrix =. >{.}.y
win =. >{.y
cols =. }. $ matrix
rows =. {. $ matrix
for_row. i.rows do.
for_col. i.cols do.
value =. (<row, col) { matrix
wattr_on_ncurses_ win;(COLOR_PAIR_ncurses_ (value+1));0
mvwprintw_1_ncurses_ win; row; (2*col); ((' '))
end.
end.
)</code></pre>
<p>The game loop handles user interactions and game rules . Here's how it looks:</p>
<pre class="j"><code>NB. Game loop
while. 1 do.
c =. wgetch_ncurses_ vin
if. c = KEY_UP_ncurses_ do.
game =: put_in_matrix (current*_1);k;j;game
current =. rotate current
needs_refresh =. 1
elseif. c = KEY_RIGHT_ncurses_ do.
game_tmp =. put_in_matrix (current*_1);k;j;game
if. can_put_in_matrix current;k;(j + 1);game_tmp do.
game =: game_tmp
j =. j + 1
needs_refresh =. 1
end.
elseif. c = KEY_LEFT_ncurses_ do.
game_tmp =. put_in_matrix (current*_1);k;j;game
if. can_put_in_matrix (current);k;(j - 1);game_tmp do.
game =: game_tmp
j =. j - 1
needs_refresh =. 1
end.
elseif. 1 do.
if. ((seconds_from_start'') - timestamp) < 0.1 do.
continue.
else.
timestamp =. seconds_from_start''
end.
if. automove = 0 do.
game =: put_in_matrix (current*_1);k;j;game
if. can_put_in_matrix (current);(k+1);j;game do.
k =. k + 1
else.
game =: put_in_matrix (current);k;j;game
k =. 0
j =. 0
if. can_put_in_matrix current;k;j;game do.
current =. (?@$ tetriminos) {:: tetriminos
else.
mvwprintw_1_ncurses_ vin; 0; 0; ' Game over '
nodelay_ncurses_ vin ;'0'
wgetch_ncurses_ vin
exit''
end.
end.
automove =. 2
needs_refresh =. 1
else.
automove =. automove - 1
end.
end.
unget_wch_ncurses_ c
if. needs_refresh do.
game =: put_in_matrix (current);k;j;game
game =: remove_full_rows game
drawGame vin; game
wrefresh_ncurses_ vin
needs_refresh =. 0
end.
end.</code></pre>
<p>The rest of the code is pure <code>ncurses</code> initialization which is not that interesting. Code for this post can be found here: : <a href="https://github.com/ldfallas/jcurtris" class="uri">https://github.com/ldfallas/jcurtris</a> .</p>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-50710476397577613612017-04-30T11:02:00.001-06:002017-04-30T11:02:06.478-06:00A small Tetris-like clone using J and ncurses. Part 1
<p>For me, the <a href="http://jsoftware.com">J programming language</a> it's a very intriguing. It is full of ideas and concepts that I'm not familiar with. Getting to know a programming language it's not only about learning the syntax. It is learning the techniques that people use to take advantage of it what gives you more insight . This is particularly true for J.</p>
<p>For me the best way to learn more about a programming language is to try to solve a small problem with it. In this post I'm going to describe an attempt to write a small and incomplete Tetris-like clone using J and the ncurses library. Here's a preview of how it looks:</p>
<div class="figure">
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiI7WgdjprPOmn0zn7IZ_3PQqPFGUR3V8ZK5-xoWZ17Fqf4LkFCTtY_86jEVLeAXcJJ3enJmWSw-DOWMqI6lxhUm0cIL6p9drOJKPwe7KaXLmERtinwlM7XOscvVukLeN70yGDuabY1Q2M-/s1600/jcursestetris.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiI7WgdjprPOmn0zn7IZ_3PQqPFGUR3V8ZK5-xoWZ17Fqf4LkFCTtY_86jEVLeAXcJJ3enJmWSw-DOWMqI6lxhUm0cIL6p9drOJKPwe7KaXLmERtinwlM7XOscvVukLeN70yGDuabY1Q2M-/s1600/jcursestetris.gif" /></a></div>
</div>
<h3 id="tetriminos">Tetriminos</h3>
<p>According to the Wikipedia page for Tetris, the pieces are named Tetriminos <a href="https://en.wikipedia.org/wiki/Tetris#Gameplay" class="uri">https://en.wikipedia.org/wiki/Tetris#Gameplay</a>. Each piece is composed of blocks. In J we can represent this pieces as matrices.</p>
<p>To create this matrices we use the <a href="http://www.jsoftware.com/help/dictionary/d210.htm"><em>Shape</em> verb</a> ($) For example:</p>
<ul>
<li>The "L" tetrimino:</li>
</ul>
<pre class="j"><code> ] l_tetrimino =. 2 3 $ 1 1 1 1 0 0
1 1 1
1 0 0</code></pre>
<ul>
<li>The "O" tetrimino:</li>
</ul>
<pre class="j"><code> ] b_tetrimino =. 2 2 $ 4 4 4 4
4 4
4 4</code></pre>
<ul>
<li>The "S" tetrimino:</li>
</ul>
<pre class="j"><code> ] s_tetrimino =. 2 3 $ 0 5 5 5 5 0
0 5 5
5 5 0</code></pre>
<h3 id="tetrimino-rotation">Tetrimino rotation</h3>
<p>In Tetris pressing the 'up' arrow is going to rotate the current piece. We can use matrix <a href="http://www.jsoftware.com/help/dictionary/d232.htm"><em>Transpose</em></a> (|:) and <a href="http://www.jsoftware.com/help/dictionary/d231.htm"><em>Reverse</em></a> (|.) verbs and compose them together using the <a href="http://www.jsoftware.com/help/dictionary/d620.htm"><em>Atop</em> conjunction</a> (@). Here's the definition:</p>
<pre class="j"><code>rotate =: |.@|:</code></pre>
<p>Here we can see how this verb works:</p>
<pre class="j"><code> l_tetrimino
1 1 1
1 0 0
rotate l_tetrimino
1 0
1 0
1 1
rotate rotate l_tetrimino
0 0 1
1 1 1
rotate rotate rotate l_tetrimino
1 1
0 1
0 1
rotate rotate rotate rotate l_tetrimino
1 1 1
1 0 0
</code></pre>
<p>We can apply this transformation to the other tetriminos for example:</p>
<pre class="j"><code> ] s_tetrimino =. 2 3 $ 0 5 5 5 5 0
0 5 5
5 5 0
rotate s_tetrimino
5 0
5 5
0 5
rotate rotate s_tetrimino
0 5 5
5 5 0
</code></pre>
<p>We use different numbers for each tetrimino so we can use different colors to paint them.</p>
<h3 id="tetrimino-placement">Tetrimino placement</h3>
<p>A natural way to model the game is to use a matrix representing the playing field. We use a 10 columns by 20 rows matrix for this effect. We use the <a href="http://www.jsoftware.com/help/dictionary/d210.htm"><em>Shape</em> verb</a> ($) to do this:</p>
<pre class="j"><code> ] game =: 20 10 $ 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0</code></pre>
<p>A fundamental piece of functionality that we need is a way to put a tetrimino inside this matrix. This proved to be tricky (maybe because of lack of J knowledge). We're going to incrementally create this verb.</p>
<p>Reading the J documentation, it seems that we can use the <a href="http://www.jsoftware.com/help/dictionary/d530n.htm"><em>Amend</em> (m } _ _ _) verb</a> to change just a set of cells of the game matrix. Here's an example on how to use this verb</p>
<pre class="j"><code> ] sample =. 5 5 $ 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 2 3 4 (1 1;2 1;1 2;2 2) } sample
0 0 0 0 0
0 1 3 0 0
0 2 4 0 0
0 0 0 0 0
0 0 0 0 0</code></pre>
<p>What we are saying here is that we can to change the following cells in <code>sample</code>:</p>
<ul>
<li>row 1 column 1 with value 1</li>
<li>row 2 column 1 with value 2</li>
<li>row 1 column 2 with value 3</li>
<li>row 2 column 2 with value 4</li>
</ul>
<p>Now to take advantage of this verb we need to calculate the target coordinates to change the value of a tetrimino. First we start by generating coordinates for each of the cells of the tetrimino.</p>
<p>We're going to use the following predifined values:</p>
<pre class="j"><code> ] l_tetrimino =. 2 3 $ 1 1 1 1 0 0
1 1 1
1 0 0
sample
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0</code></pre>
<p>We start by determining how many rows and columns. We use the <a href="http://www.jsoftware.com/help/dictionary/d210.htm"><em>Shape of</em> verb</a> ($) to do this:</p>
<pre class="j"><code> $ l_tetrimino
2 3</code></pre>
<p>Now we want to generate (0, 0);(0, 1);...(1, 2);(2, 2). With the result of <em>Shape of</em> we generate a sequence of numbers for each of the axis. To do this we use the <a href="http://www.jsoftware.com/help/dictionary/didot.htm"><em>Integers</em> (i.) verb</a>with the number of rows and the number of columns. For example:</p>
<pre class="j"><code> NB. Get the number of rows:
(0&{@$) l_tetrimino
2
NB. Get the number of columns:
(1&{@$) l_tetrimino
3
NB. Get an integer sequence from zero to number of rows or columns
i.(1&{@$) l_tetrimino
0 1 2
i.(0&{@$) l_tetrimino
0 1</code></pre>
<p>Now this is very cool, we can use the <a href="http://www.jsoftware.com/help/dictionary/d420.htm"><em>Table</em> verb (/)</a>to pair this two arrays. From the documentation:</p>
<blockquote>
<p>In general, each cell of x is applied to the entire of y . Thus x u/ y is equivalent to x u"(lu,_) y where lu is the left rank of u .</p>
</blockquote>
<p>This is very important!. To taken advantage of this we need to use the <em>Append verb</em> (,) <help/dictionary/d320.htm> but changing the rack to operate on each of the elements from the right argument. See this example:</p>
<pre class="j"><code> 0 (,"0) 0 1 2
0 0
0 1
0 2</code></pre>
<p>Now we can take advantage of this and write:</p>
<pre class="j"><code> ( (i.@(0&{@$)) (<@,"0)/ (i.@(1&{@$))) l_tetrimino
+---+---+---+
|0 0|0 1|0 2|
+---+---+---+
|1 0|1 1|1 2|
+---+---+---+</code></pre>
<p>Now this is almost what we need. We can use the <a href="http://www.jsoftware.com/help/dictionary/d320.htm"><em>Ravel</em> veb</a> (,) to flatten this box:</p>
<pre class="j"><code>
, ( (i.@(0&{@$)) (<@,"0)/ (i.@(1&{@$))) l_tetrimino
+---+---+---+---+---+---+
|0 0|0 1|0 2|1 0|1 1|1 2|
+---+---+---+---+---+---+</code></pre>
<p>With this positions we can use the <a href="http://www.jsoftware.com/help/dictionary/d530n.htm"><em>Amend</em> verb</a> to change our game matrix:</p>
<pre class="j"><code> (,l_tetrimino) positions } sample
1 1 1 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0</code></pre>
<p>We need something else since this technique only allows us to put the tetrimino at the top of the matrix. In order to do this we need to sum the target position to the coordinates that we generated. We can use the powerful <a href="http://www.jsoftware.com/help/dictionary/d631.htm"><em>Under</em> verb</a> (&.) which allows us to apply an operation to each of the cells of a box.</p>
<pre class="j"><code> (3 2)&+ &.> positions
+---+---+---+---+---+---+
|3 2|3 3|3 4|4 2|4 3|4 4|
+---+---+---+---+---+---+</code></pre>
<p>We construct this operation by:</p>
<ol style="list-style-type: decimal">
<li>using <a href="http://www.jsoftware.com/help/dictionary/d630n.htm"><em>Bond</em> conjuction</a> (&) to tie together the position (3 2) with the plus operation (+) . That is <code>(3 2)&+</code> .</li>
<li>we apply this operation to each of the elements of the box and then assemble the box again. That is <code>&.></code></li>
</ol>
<p>Now we can put the tetrimino in row 3, column 2.</p>
<pre class="j"><code> target_position =. 3 2
target_position =. 2 1
(,l_tetrimino) (target_position&+&.>positions) } sample
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0</code></pre>
<p>We cannot just pust the tetrimino in the target position. It may also "blend" with existing values. For example say the following game field and the following tetrminio:</p>
<pre class="j"><code> ] game
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 1 0
0 0 0 1 1
positions =., ( (i.@(0&{@$)) (<@,"0)/ (i.@(1&{@$))) tetrimino
(,tetrimino) ((1 2)&+&.> positions) } game
0 0 0 0 0
0 0 1 1 0
0 0 1 0 0
0 0 1 0 0
0 0 0 1 1
</code></pre>
<p>Because of this we need to mix the tetrimino with the current values of the target region. We do this by extracting the values of the target position:</p>
<pre class="j"><code> ($tetrimino) $ ((1 2)&+&.> positions) { game
0 0
0 1
0 1</code></pre>
<p>We can combine this array with the tetrimino and we get the desired target value:</p>
<pre class="j"><code> ] target_tetrimino =. +&tetrimino ($tetrimino) $ ((1 2)&+&.> positions) { game
1 1
1 1
1 1
(,target_tetrimino) ((1 2)&+&.> positions) } game
0 0 0 0 0
0 0 1 1 0
0 0 1 1 0
0 0 1 1 0
0 0 0 1 1</code></pre>
<p>The final verb definition looks like this:</p>
<pre class="j"><code>put_in_matrix =: 3 : 0
NB. unpack argumets
tetrimino =. > 0 { y
i =. > 1 { y
j =. > 2 { y
game =. > 3 { y
NB. calculate target positions
positions =. , ((i.@(0&{)@$)(<@,"0)/(i.@(1&{)@$)) tetrimino
NB. combine tetrimino with target section
tetrimino =. +&tetrimino ($tetrimino) $ ((+&(i,j))&.> positions) { game
NB. change matrix
(,tetrimino) ((+&(i,j))&.> positions)} game
)</code></pre>
<h3 id="checking-if-space-is-available">Checking if space is available</h3>
<p>The other piece of functionality that we need is a way to verify if we can put the tetrimino in a target position. We need to verify two conditions: 1. We can put the tetrimino inside the game field. 2. There's space available in the target position.</p>
<p>To check the boundaries we use common comparison operators:</p>
<pre class="j"><code> NB. Verify field boundaries
is_inside =. (xpos >: 0) *. (ypos >: 0) *. ( (xpos+tetrimino_width - 1) < game_width) *. ((ypos+tetrimino_height - 1) < game_height)</code></pre>
<p>The second criteria it's more intersesting. To illustrate how we did the detection we're going to start with a predifined game field:</p>
<pre class="j"><code> game
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
] tetrimino =. 2 3 $ 2 0 0 2 2 2
2 0 0
2 2 2</code></pre>
<p>The first step is to reset the values of the tetrimino to be either zero or one:</p>
<pre class="j"><code> ] tetrimino =. 0&< tetrimino
1 0 0
1 1 1</code></pre>
<p>Now we extract the elements of the target position (in this example column 1, row 3)</p>
<pre class="j"><code> ypos =. 3
xpos =. 1
positions =. , ((i.@(0&{)@$)(<@,"0)/(i.@(1&{)@$)) tetrimino
($tetrimino) $ ((+&(ypos,xpos))&.> positions){ game
0 0 1
0 0 0</code></pre>
<pre class="j"><code> xpos =. 1
ypos =. 2
positions =. , ((i.@(0&{)@$)(<@,"0)/(i.@(1&{)@$)) tetrimino
($tetrimino) $ ((+&(ypos,xpos))&.> positions){ game
0 0 0
0 0 1</code></pre>
<p>Now we can multiply the tetrimino by the target value:</p>
<pre class="j"><code> target_segment =. ($tetrimino) $ ((+&(ypos,xpos))&.> positions){ game
] hits =. +/ , *&tetrimino target_segment
1</code></pre>
<p>Now the variable <code>hits</code> contains the number of elements with a target cell value. The final predicate looks like this:</p>
<pre class="j"><code>can_put_in_matrix =: 3 : 0
NB. Unpack the arguments
tetrimino =. 0&< > 0 { y
tetrimino_width =. 1 { $ tetrimino
tetrimino_height =. 0 { $ tetrimino
ypos =. > 1 { y
xpos =. > 2 { y
game =. > 3 { y
game_width =. 1 { $ game
game_height =. 0 { $ game
NB. Verify field boundaries
is_inside =. (xpos >: 0) *. (ypos >: 0) *. ( (xpos+tetrimino_width - 1) < game_width) *. ((ypos+tetrimino_height - 1) < game_height)
NB. Check if we hit an occupied cell
hits =. 0
if. is_inside do.
positions =. , ((i.@(0&{)@$)(<@,"0)/(i.@(1&{)@$)) tetrimino
hits =. +/ , *&tetrimino ($tetrimino) $ ((+&(ypos,xpos))&.> positions){ game
end.
is_inside *. (hits = 0)
)</code></pre>
<h3 id="end-words">End words</h3>
<p>As it was said in the beginning, J it's very interesting. For me there are many things to learn (you can tell that by looking at all those parenthesis in some expressions). Also there are many strategies in array languages that one needs to understand in other to write idiomatic code.</p>
<p>The ncurses interface will be discussed in part 2. For future posts it will be interesting to talk about concepts like the <code>obverse</code> (<a href="http://www.jsoftware.com/help/jforc/u_1_uv_uv_and_u_v.htm#_Toc191734413" class="uri">http://www.jsoftware.com/help/jforc/u_1_uv_uv_and_u_v.htm#_Toc191734413</a>) and <code>state machines</code> (<a href="http://www.jsoftware.com/help/jforc/loopless_code_vii_sequential.htm#_Toc191734470" class="uri">http://www.jsoftware.com/help/jforc/loopless_code_vii_sequential.htm#_Toc191734470</a>) .</p>
<p>Code for this post can be found here: <a href="https://github.com/ldfallas/jcurtris" class="uri">https://github.com/ldfallas/jcurtris</a></p>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-44490733358414400762017-04-10T20:51:00.002-06:002017-04-10T20:51:49.504-06:00A simple language with indentation based blocks. Part 4: Improving error messages<p>Going back to our first post, we defined the type of a parser function as :</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">ReaderState -> (('a * ReaderState) <span class="dt">option</span> )</code></pre></div>
<p>Which means that a parser is a function from a reader state to an <a href="https://msdn.microsoft.com/visualfsharpdocs/conceptual/core.option%5b%27t%5d-union-%5bfsharp%5d"><code>Option<'a></code></a> of a value and a new reader state.</p>
<p>Using <code>Option<'a></code> is handy for writing code that may result on a value or a failure indicator. In our case it's possible that the parser fails to recognize its input. The most common example it's a program with syntax errors. For example the following program is incorrect:</p>
<div class="sourceCode"><pre class="sourceCode python"><code class="sourceCode python"><span class="cf">if</span> cond1:
<span class="cf">if</span> x y z:
<span class="bu">print</span>(x)</code></pre></div>
<p>A parser failure may also be something we expected. This is the case when need to use failure to choose a parser from a list of possible parsers. For example the expression parser:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> pStatements := [pReturn; ifParser; pCallStatement; pAssignStatement; whileParser]
<span class="kw">let</span> pStatement =
<span class="kw">fun</span> state -> (List<span class="kw">.</span>reduce disjParser !pStatements) state
</code></pre></div>
<p>Using the bultin <code>Option<'a></code> type comes handy, but it has the problem that it doesn't provide information about the parsing failure. When a parser cannot recognize some input string, the only response we get is <code>None</code>. That's why we introduced the <code>ParsingResult<'a></code> type to replace the <code>Option<'a></code> type. Here's the definition:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">type</span> ReaderState = { Data: <span class="dt">string</span>;
Position: <span class="dt">int</span>;
Line: <span class="dt">int</span>;
Indentation: <span class="dt">int</span> list }
<span class="kw">type</span> ParserFailure =
| Fatal <span class="kw">of</span> <span class="dt">string</span> * <span class="dt">int</span>
| Fail
<span class="kw">type</span> ParsingResult<'a> =
| Success <span class="kw">of</span> ('a * ReaderState)
| Failure <span class="kw">of</span> ParserFailure</code></pre></div>
<p>We still have two possible states: <code>Success</code> and <code>Failure</code>. However now we have a space to add more information about a syntax error . In this case <code>Fatal</code> has a couple of slots to specify an error message and a line number.</p>
<h3 id="failure-information">Failure information</h3>
<p>The <code>Failure</code> has a parameter of type <code>ParserFailure</code>. This type is defined as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">type</span> ParserFailure =
| Fatal <span class="kw">of</span> <span class="dt">string</span> * <span class="dt">int</span>
| Fail</code></pre></div>
<p>We use this two alternatives to represent the scenarios described at the beginning of this post:</p>
<ul>
<li><code>Fatal</code> : a syntax error in the input string</li>
<li><code>Fail</code> : a failure to completely recognize something</li>
</ul>
<p>We use <code>Fatal</code> for scenarios such as the following program which has a syntax error in the <code>while</code> condition ( <code>x y</code> ):</p>
<div class="sourceCode"><pre class="sourceCode python"><code class="sourceCode python"><span class="cf">while</span> x y:
<span class="bu">print</span>(<span class="dv">1</span>)</code></pre></div>
<p>This is the definition of the <code>whileParser</code>:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> whileParser =
whileKeyword >>
pExpression >>= (<span class="kw">fun</span> condition ->
colon >>
pBlock >>= (<span class="kw">fun</span> block ->
preturn (PWhile(condition, block))))</code></pre></div>
<p>We can say that any failure after the <code>while</code> keyword is a fatal failure. However a failure detecting the <code>while</code> keyword is a simple failure . In order to represent this situation we're going to introduce the <code>+>></code> which is going to sequence two parsers and produce a fatal failure in case that the first parser fails. The definition of this operation looks like this:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> <span class="kw">inline</span> (+>>) (parser1 : (ReaderState -> ParsingResult<'a>))
(parser2 : (ReaderState -> ParsingResult<'b>)) =
<span class="kw">fun</span> input -> <span class="kw">match</span> (parser1 input) <span class="kw">with</span>
| Success (_, restState) -> parser2 restState
| Failure(f & Fatal(_, _)) -> Failure(f)
| Failure(_) -> Failure(Fatal(<span class="st">"Parsing error "</span>, input.Line))
<span class="kw">let</span> <span class="kw">inline</span> (+>>=) (parser1 : (ReaderState -> ParsingResult<'a>))
(parser2N : ('a -> (ReaderState -> ParsingResult<'b>))) =
<span class="kw">fun</span> input -> <span class="kw">match</span> (parser1 input) <span class="kw">with</span>
| Success (matchedTxt, restState) -> (parser2N matchedTxt) restState
| Failure(f & Fatal(_)) -> Failure(f)
| Failure(_) -> Failure(Fatal(<span class="st">"Parse problem "</span>, input.Line)) </code></pre></div>
<p>Now with this operator we can modify the definition of <code>whileParser</code> to be as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> whileParser =
whileKeyword >>
pExpression +>>= (<span class="kw">fun</span> condition ->
colon +>>
pBlock +>>= (<span class="kw">fun</span> block ->
preturn (PWhile(condition, block))))</code></pre></div>
<h3 id="example">Example</h3>
<p>Now we can see the result of parsing a file:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"if x:</span>
<span class="st">- </span>
<span class="st">- while x y:</span>
<span class="st">- print(1)</span>
<span class="st">- "</span> pStatement;;
<span class="kw">val</span> it : ParsingResult<PStat> = Failure (Fatal (<span class="st">"Parsing error "</span>,<span class="dv">3</span>))</code></pre></div>
<h3 id="expected-failure">Expected failure</h3>
<p>Now we also we parser failures for choosing from a set of possible parsers. We do that in the <code>disjParser</code> which chooses between two parsers. The old definition of the <code>disjParser</code> looks like this:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">let</span> disjParser (parser1 : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> )))
(parser2 : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> ))) =
<span class="kw">fun</span> input -> <span class="kw">match</span> (parser1 input) <span class="kw">with</span>
| result & Some _ -> result
| _ -> parser2 input</code></pre></div>
<p>Notice that this definition uses the <code>Option<'a></code> cases (<code>Some</code> and <code>None</code>) to determine if it succeeds or if it needs to give a chance to <code>parser2</code>. With our new <code>ParserResult<'a></code> type we need to make a distinction between fatal and a "controlled" failure. We can now change the definition of this parser to be:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">let</span> disjParser (parser1 : (ReaderState -> ParsingResult<'a>))
(parser2 : (ReaderState -> ParsingResult<'a>)) =
<span class="kw">fun</span> input -> <span class="kw">match</span> (parser1 input) <span class="kw">with</span>
| success & Success(_) -> success
| Failure(fatal & Fatal(_, _)) -> Failure(fatal)
| _ -> parser2 input</code></pre></div>
<h3 id="next-steps">Next steps</h3>
<p>In the next post we're going to deal with code comments.</p>
<p>This is part #4 of an ongoing series of posts on building a parser for a small language. The first post can be found here: <a href="http://langexplr.blogspot.com/2017/01/a-simple-language-with-indentation.html" class="uri">http://langexplr.blogspot.com/2017/01/a-simple-language-with-indentation.html</a> and a GitHub repository with the code can be found there: <a href="https://github.com/ldfallas/fsharpparsing" class="uri">https://github.com/ldfallas/fsharpparsing</a>.</p>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-50975506552006026052017-03-25T10:25:00.000-06:002017-03-25T10:26:49.466-06:00A simple language with indentation based blocks. Part 3: Blocks<p>In this post we're going to add support for statements containing blocks which is the main goal of these series of posts.</p>
<h2 id="identifying-blocks-by-using-indentation">Identifying blocks by using indentation</h2>
<p>The technique we're going to use to identify blocks is based the following description from the (excellent) Python documentation:</p>
<blockquote>
<p><i>Before the first line of the file is read, a single zero is pushed on the stack; this will never be popped off again. The numbers pushed on the stack will always be strictly increasing from bottom to top. At the beginning of each logical line, the line's indentation level is compared to the top of the stack. If it is equal, nothing happens. If it is larger, it is pushed on the stack, and one INDENT token is generated. If it is smaller, it must be one of the numbers occurring on the stack; all numbers on the stack that are larger are popped off, and for each number popped off a DEDENT token is generated. At the end of the file, a DEDENT token is generated for each number remaining on the stack that is larger than zero.</i></p>
</blockquote>
<p>This section was taken from: <a href="https://docs.python.org/3/reference/lexical_analysis.html#indentation" class="uri">https://docs.python.org/3/reference/lexical_analysis.html#indentation</a></p>
<p>The IDENT and DEDENT tokens act as begin/end block indicators. They have the same function as '{' and '}' in C-based languages. The following Python grammar fragment shows how this tokens are used.</p>
<pre class="bnf"><code>...
suite: simple_stmt | NEWLINE IDENT stmt+ DEDENT
...
if_stmt: 'if' test ':' suite ...
...</code></pre>
<p>Since our little parser uses parsing combinators without a tokenizer, we need to adjust this strategy a little bit. We're going to jump right ahead to show how we define the parser for the <code>if</code> statement.</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> pBlock =
newlines >>
indent >>
pStatement >>= (<span class="kw">fun</span> firstStat ->
(zeroOrMore
(newlines >>
indented >>
pStatement) []) >>= (<span class="kw">fun</span> restStats ->
dedent >> preturn (firstStat::restStats)))
<span class="kw">let</span> ifParser =
ifKeyword >>
pExpression >>= (<span class="kw">fun</span> expr ->
colon >>
pBlock >>= (<span class="kw">fun</span> block ->
(optionalP pElse []) >>= (<span class="kw">fun</span> optElseBlockStats ->
preturn (PIf(expr,
block,
(<span class="kw">match</span> optElseBlockStats <span class="kw">with</span>
| [] -> None
| elements -> Some elements))))))</code></pre></div>
<p>Here's an example of the generated AST for a simple <code>if</code> statement:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"if x:</span>
<span class="st">- print(x)</span>
<span class="st">- return x*x</span>
<span class="st">- "</span> ifParser;;
<span class="kw">val</span> it : (PStat * ReaderState) <span class="dt">option</span> =
Some
(PIf
(PSymbol <span class="st">"x"</span>,
[PCallStat (PCall (<span class="st">"print"</span>,[PSymbol <span class="st">"x"</span>]));
PReturn (PBinaryOperation (Times,PSymbol <span class="st">"x"</span>,PSymbol <span class="st">"x"</span>))],<span class="kw">null</span>),
{Data = <span class="st">"if x:</span>
<span class="st"> print(x)</span>
<span class="st"> return x*x</span>
<span class="st">"</span>;
Position = <span class="dv">45</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<p>The key element here is the definition of the <code>pBlock</code> parser. In the definition of this parser we try to emulate the same strategy as the Python grammar definition:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> pBlock =
newlines >>
indent >>
pStatement >>= (<span class="kw">fun</span> firstStat ->
(zeroOrMore
(newlines >>
indented >>
pStatement) []) >>= (<span class="kw">fun</span> restStats ->
dedent >> preturn (firstStat::restStats)))</code></pre></div>
<p>We define <code>indent</code>, <code>dedent</code> and <code>indented</code> as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> indentation =
pGetIndentation >>=(<span class="kw">fun</span> indentation ->
(readZeroOrMoreChars (<span class="kw">fun</span> c -> c = <span class="ch">' '</span>))
>>=
(<span class="kw">fun</span> spaces ->
<span class="kw">match</span> (spaces.Length,
indentation) <span class="kw">with</span>
| (lessThan, top::_) <span class="kw">when</span> lessThan > top ->
(pSetIndentation lessThan) >> (preturn <span class="st">"INDENT"</span>)
| (lessThan, top::_) <span class="kw">when</span> lessThan = top ->
preturn <span class="st">"INDENTED"</span>
| (identifiedIndentation, top::rest) ->
(pSetFullIndentation rest) >> (preturn <span class="st">"DEDENT"</span>)
| _ -> pfail))
<span class="kw">let</span> indent = indentation >>= (<span class="kw">fun</span> result -> <span class="kw">if</span> result = <span class="st">"INDENT"</span> <span class="kw">then</span> preturn result <span class="kw">else</span> pfail)
<span class="kw">let</span> dedent = indentation >>= (<span class="kw">fun</span> result -> <span class="kw">if</span> result = <span class="st">"DEDENT"</span> <span class="kw">then</span> preturn result <span class="kw">else</span> pfail)
<span class="kw">let</span> indented = indentation >>= (<span class="kw">fun</span> result -> <span class="kw">if</span> result = <span class="st">"INDENTED"</span> <span class="kw">then</span> preturn result <span class="kw">else</span> pfail)</code></pre></div>
<p>We define each of these indentation elements as:</p>
<ul>
<li>INDENTED verifies that the expected indentation level is present. It consumes this indentation. For example, if expecting 3 space indentation, it will consume and verify that there are three spaces from the current position.</li>
<li>INDENT Verifies that there's a new indentation level can be found from the current position. It changes the 'Indentation' value in the current reader state.</li>
<li>DEDENT decreases the expected indentation level from the reader.</li>
</ul>
<p>We can test these combinators to see how they affect the state of the parser.</p>
<p>We start with the following fragment:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> <span class="kw">let</span> code = <span class="st">"if x:</span>
<span class="st"> if y:</span>
<span class="st"> return 1</span>
<span class="st"> else:</span>
<span class="st"> return 2</span>
<span class="st">"</span></code></pre></div>
<p>We can test parts of our complex parsers by specifying just pieces of others. For example let's get to the <code>then</code> part of the parser.</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse code (ifKeyword >> pExpression >> colon >> newlines >> indent);;
<span class="kw">val</span> it : (<span class="dt">string</span> * ReaderState) <span class="dt">option</span> =
Some
(<span class="st">"INDENT"</span>, {Data = <span class="st">"if x:</span>
<span class="st"> if y:</span>
<span class="st"> return 1</span>
<span class="st"> else:</span>
<span class="st"> return 2</span>
<span class="st">"</span>;
Position = <span class="dv">8</span>;
Indentation = [<span class="dv">2</span>; <span class="dv">0</span>];})</code></pre></div>
<p>As you can see, after executing these parsers we get to position 8. For example:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> code.Substring(<span class="dv">8</span>);;
<span class="kw">val</span> it : <span class="dt">string</span> = <span class="st">"if y:</span>
<span class="st"> return 1</span>
<span class="st"> else:</span>
<span class="st"> return 2</span>
<span class="st">"</span></code></pre></div>
<p>Also the indentation stack now has <code>2</code> and <code>0</code>. If we execute these series of parsers again to get to the <code>then</code> section of the first nested <code>if</code> we get:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse code (ifKeyword >> pExpression >> colon >> newlines >> indent >>
- ifKeyword >> pExpression >> colon >> newlines >> indent);;
<span class="kw">val</span> it : (<span class="dt">string</span> * ReaderState) <span class="dt">option</span> =
Some
(<span class="st">"INDENT"</span>, {Data = <span class="st">"if x:</span>
<span class="st"> if y:</span>
<span class="st"> return 1</span>
<span class="st"> else:</span>
<span class="st"> return 2</span>
<span class="st">"</span>;
Position = <span class="dv">19</span>;
Indentation = [<span class="dv">5</span>; <span class="dv">2</span>; <span class="dv">0</span>];})</code></pre></div>
<p>Now we have three indentation levels on our stack and we got to position <code>19</code>.</p>
<h2 id="blocks">Blocks</h2>
<p>Just as the Python grammar reuses <code>suite</code> production, we can reuse the <code>pBlock</code> parser to define other kinds of statements. For example we can define the <code>while</code> statement as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> whileParser =
whileKeyword >>
pExpression >>= (<span class="kw">fun</span> condition ->
colon >>
pBlock >>= (<span class="kw">fun</span> block ->
preturn (PWhile(condition, block))))</code></pre></div>
<p>Now we can define more interesting statements such as:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">val</span> code : <span class="dt">string</span> = <span class="st">"if x > 0:</span>
<span class="st"> while x < 10:</span>
<span class="st"> print(x)</span>
<span class="st"> x := x + 1</span>
<span class="st">"</span>
> parse code pStatement;;
<span class="kw">val</span> it : (PStat * ReaderState) <span class="dt">option</span> =
Some
(PIf
(PBinaryOperation (Gt,PSymbol <span class="st">"x"</span>,PNumber <span class="st">"0"</span>),
[PWhile
(PBinaryOperation (Lt,PSymbol <span class="st">"x"</span>,PNumber <span class="st">"10"</span>),
[PCallStat (PCall (<span class="st">"print"</span>,[PSymbol <span class="st">"x"</span>]));
PAssignStat
(PSymbol <span class="st">"x"</span>,PBinaryOperation (Plus,PSymbol <span class="st">"x"</span>,PNumber <span class="st">"1"</span>))])],
<span class="kw">null</span>),
{Data = <span class="st">"if x > 0:</span>
<span class="st"> while x < 10:</span>
<span class="st"> print(x)</span>
<span class="st"> x := x + 1</span>
<span class="st">"</span>;
Position = <span class="dv">53</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<h2 id="next-steps">Next steps</h2>
<p>Now that we can define blocks we can focus in other parts of our little language parser. One thing we can definetly improve is error messages. For example, let's try to parse the following fragment:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"notanif x y z"</span> ifParser;;
<span class="kw">val</span> it : (PStat * ReaderState) <span class="dt">option</span> = None</code></pre></div>
<p>Here's where the <code>Option<'a></code> type is not that useful since it doesn't allow you to specify a failure value such as a error message or location.</p>
<p>Another thing that we need to implement is comments. Our parser combinators work directly with the text. Because of this it will be interesting to see to introduce comments support without changing all our parsers.</p>
<p>This is part #3 of an ongoing series of posts on building a parser for a small language. The first post can be found here: <a href="http://langexplr.blogspot.com/2017/01/a-simple-language-with-indentation.html" class="uri">http://langexplr.blogspot.com/2017/01/a-simple-language-with-indentation.html</a>.</p>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-30027006047403694112017-02-26T19:41:00.001-06:002017-02-26T19:41:44.634-06:00A simple language with indentation based blocks. Part 2: Expressions
<p>The focus of the second part will be expression parsing. The desired grammar for the expression small language experiment is the following (here in pseudo BNF):</p>
<div class="sourceCode"><pre class="sourceCode python"><code class="sourceCode python">NESTED_EXPRESSION <span class="op">=</span> <span class="st">'('</span> EXPRESSION <span class="st">')'</span>
PRIMARY_EXPRESSION <span class="op">=</span> SYMBOL <span class="op">|</span> NUMBER <span class="op">|</span> STRING <span class="op">|</span> NESTED
UNARY_EXPRESSION <span class="op">=</span> NOT_EXPRESSION <span class="op">|</span> CALL_EXPRESSION <span class="op">|</span> ARRAY_ACCESS_EXPRESSION <span class="op">|</span>
PRIMARY_EXPRESSION
MULTIPLICATIVE_EXPRESSION <span class="op">=</span> UNARY_EXPRESSION ( (<span class="st">'*'</span> <span class="op">|</span> <span class="st">'/'</span>) UNARY_EXPRESSION)<span class="op">*</span>
ADDITIVE_EXPRESSION <span class="op">=</span> MULTIPLICATIVE_EXPRESSION ( (<span class="st">'*'</span> <span class="op">|</span> <span class="st">'/'</span>) MULTIPLICATIVE_EXPRESSION)<span class="op">*</span>
RELATIONAL_EXPRESSION <span class="op">=</span> ADDITIVE_EXPRESSION ( (<span class="st">'<'</span> <span class="op">|</span> <span class="st">'>'</span>) ADDITIVE_EXPRESSION)<span class="op">*</span>
EQUALITY_EXPRESSION <span class="op">=</span> RELATIONAL_EXPRESSION ( (<span class="st">'='</span> <span class="op">|</span> <span class="st">'<>'</span>) RELATIONAL_EXPRESSION)<span class="op">*</span>
LOGICAL_OR_EXPRESSION <span class="op">=</span> EQUALITY_EXPRESSION (<span class="st">'||'</span> EQUALITY_EXPRESSION)<span class="op">*</span>
LOGICAL_AND_EXPRESSION <span class="op">=</span> LOGICAL_OR_EXPRESSION (<span class="st">'&&'</span> LOGICAL_OR_EXPRESSION)<span class="op">*</span>
EXPRESSION <span class="op">=</span> LOGICAL_AND_EXPRESSION</code></pre></div>
<p>In this post we're going to build some key techniques for creating the code for parsing a subset of this grammar. Not every element of expression grammar will be presented since it gets repetitive at some point.</p>
<p>For this small experiment we're going to use the following F# types as the AST of the program:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">type</span> Operator =
| Plus
| Minus
| Times
| Div
| And
| Or
| Equal
| NotEqual
| Assign
| Lt
| Gt
<span class="kw">type</span> PExpr =
| PSymbol <span class="kw">of</span> <span class="dt">string</span>
| PString <span class="kw">of</span> <span class="dt">string</span>
| PNumber <span class="kw">of</span> <span class="dt">string</span>
| PBoolean <span class="kw">of</span> <span class="dt">bool</span>
| PNot <span class="kw">of</span> PExpr
| PCall <span class="kw">of</span> <span class="dt">string</span> * (PExpr list)
| PNested <span class="kw">of</span> PExpr
| PArrayAccess <span class="kw">of</span> PExpr * PExpr
| PBinaryOperation <span class="kw">of</span> Operator * PExpr * PExpr</code></pre></div>
<h3 id="simple-atomic-expressions">Simple atomic expressions</h3>
<p>We're going to start with the atomic expressions:</p>
<ul>
<li>Symbols or variables (ex. <code>x</code>,<code>y</code>,<code>z</code>)</li>
<li>Number literals (ex <code>1</code>, <code>1.2</code>)</li>
<li>String literals (ex. <code>"Hello"</code>)</li>
</ul>
<p>We already got these parsers from the previous post:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> pSymbol =
concatParsers2
(readWithConditionOnChar (<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsLetter(c, <span class="dv">0</span>)))
(<span class="kw">fun</span> initialChar ->
concatParsers2
(readZeroOrMoreChars (<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsLetter(c) || System<span class="kw">.</span>Char<span class="kw">.</span>IsDigit(c)))
(<span class="kw">fun</span> suffixString -> (preturn (PSymbol (initialChar + suffixString))))
)
<span class="kw">let</span> pNumber =
( (optionalP (readSpecificChar <span class="ch">'-'</span>) <span class="st">""</span>) >>= (<span class="kw">fun</span> neg ->
digitP >>= (<span class="kw">fun</span> firstChar ->
(readZeroOrMoreChars (<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsDigit(c))) >>= (<span class="kw">fun</span> chars ->
(optionalP decimalPartP <span class="st">""</span>) >>= (<span class="kw">fun</span> dec ->
preturn (PNumber (neg + firstChar + chars + dec)))))))
<span class="kw">let</span> pString =
whitespace >>
readSpecificChar <span class="ch">'"'</span> >>
readZeroOrMoreStringChars (<span class="kw">fun</span> previous current ->
(previous = <span class="ch">'\\'</span> && current = <span class="ch">'"'</span>) || current <> <span class="ch">'"'</span>)
>>= (<span class="kw">fun</span> stringContents ->
readSpecificChar <span class="ch">'"'</span> >> (preturn (PString stringContents)))</code></pre></div>
<p>We can call these expressions "primary expressions", which are used in conjunction with operators to create more complex elements. We need a parser that recognizes any one these elements. We can use the <code>disjParser</code> from the previous post :</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> <span class="kw">let</span> primaryExpression = (disjParser (disjParser pSymbol pNumber) pString);;
<span class="kw">val</span> primaryExpression : (ReaderState -> (PExpr * ReaderState) <span class="dt">option</span>)
> parse <span class="st">"10"</span> myPrimaryExpression;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PNumber <span class="st">"10"</span>, {Data = <span class="st">"10"</span>;
Position = <span class="dv">2</span>;
Indentation = [<span class="dv">0</span>];})
> parse <span class="st">"x"</span> myPrimaryExpression;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PSymbol <span class="st">"x"</span>, {Data = <span class="st">"x"</span>;
Position = <span class="dv">1</span>;
Indentation = [<span class="dv">0</span>];})
> parse <span class="st">"</span><span class="ch">\"</span><span class="st">hello</span><span class="ch">\"</span><span class="st">"</span> myPrimaryExpression;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PString <span class="st">"hello"</span>, {Data = <span class="st">""</span>hello<span class="st">""</span>;
Position = <span class="dv">7</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<p>We can use <code>List.reduce</code> function to improve this code since we could have several parsers as the primary expression.</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> <span class="kw">let</span> myPrimaryExpression = List<span class="kw">.</span>reduce disjParser [pSymbol; pNumber; pString] ;;
<span class="kw">val</span> myPrimaryExpression : (ReaderState -> (PExpr * ReaderState) <span class="dt">option</span>)
> parse <span class="st">"10"</span> myPrimaryExpression
- ;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PNumber <span class="st">"10"</span>, {Data = <span class="st">"10"</span>;
Position = <span class="dv">2</span>;
Indentation = [<span class="dv">0</span>];})
> parse <span class="st">"x1"</span> myPrimaryExpression
- ;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PSymbol <span class="st">"x1"</span>, {Data = <span class="st">"x1"</span>;
Position = <span class="dv">2</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<h3 id="binary-operations">Binary operations</h3>
<p>Binary expressions are composed of two expressions and an operator which connects them. For example: <code>a + b</code> . For these operations we can define the following utility parser creation function:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> buildExpressions (leftExpr:PExpr) (rightExprs:(Operator * PExpr) list) =
(List<span class="kw">.</span>fold (<span class="kw">fun</span> left (op,right) -> PBinaryOperation(op, left, right)) leftExpr rightExprs)
<span class="kw">let</span> pBinaryExpression operators lowerLevelElementParser =
lowerLevelElementParser
>>= (<span class="kw">fun</span> leftTerm ->
(zeroOrMore
(operators
>>= (<span class="kw">fun</span> op ->
lowerLevelElementParser >>= (<span class="kw">fun</span> expr -> preturn (op, expr))))
[])
>>= (<span class="kw">fun</span> acc -> preturn (buildExpressions leftTerm acc) ))</code></pre></div>
<p>This function allows us to build parsers for binary expressions . The same expressed in pseudo BNF may look like this:</p>
<div class="sourceCode"><pre class="sourceCode python"><code class="sourceCode python"> pBinaryExpression <span class="op">=</span> lowerLevelElementParser ( operators lowerLevelElementParser )<span class="op">*</span></code></pre></div>
<p>Which means that we'll like to recognize an element with <code>lowerLevelElementParser</code> and zero or more pairs of an element recognized by <code>operators</code> followed by another <code>lowerLevelElementParser</code>. What looks strange at first is the use of <code>zero or more</code> which implies that this parser can recognize just one element with <code>lowerLevelElementParser</code>. This will be useful in the following section when we try to implement operator precedence.</p>
<p>As an example we can define a parser for <code>plus</code> as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> <span class="kw">let</span> identifyOperator operatorChar operatorResult =
- concatParsers
- whitespaceNoNl
- ((readSpecificChar operatorChar) >> (preturn operatorResult))
- ;;
<span class="kw">val</span> identifyOperator :
operatorChar:<span class="dt">char</span> ->
operatorResult:'a -> (ReaderState -> ('a * ReaderState) <span class="dt">option</span>)
> <span class="kw">let</span> plusOperator = identifyOperator <span class="ch">'+'</span> Plus;;
<span class="kw">val</span> plusOperator : (ReaderState -> (Operator * ReaderState) <span class="dt">option</span>)
> <span class="kw">let</span> myPlus = pBinaryExpression plusOperator myPrimaryExpression;;
<span class="kw">val</span> myPlus : (ReaderState -> (PExpr * ReaderState) <span class="dt">option</span>)
> parse <span class="st">"1+2"</span> myPlus;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PBinaryOperation (Plus,PNumber <span class="st">"1"</span>,PNumber <span class="st">"2"</span>), {Data = <span class="st">"1+2"</span>;
Position = <span class="dv">3</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<h3 id="arithmetic-operations">Arithmetic operations</h3>
<p>Now we're going to add support for basic arithmetic operations: <code>+</code>, <code>-</code>, <code>/</code>, <code>*</code>. By using the <code>pBinaryExpression</code> utility function defined in the previous section we can preserve operator precedence. To do this we define the operations as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">let</span> pMultiplicativeExpression = pBinaryExpression (disjParser pDivOperator pTimesOperator) myPrimaryExpression
<span class="kw">let</span> pAdditiveExpression = pBinaryExpression (disjParser plusOperator minusOperator) pMultiplicativeExpression</code></pre></div>
<p>What we say here is that an <code>additive expression</code> is composed of addition or subtraction <code>(disjParser plusOperator minusOperator)</code> of <code>multiplicative expressions</code>. Also we said that a <code>multiplicative expression</code> is composed of multiplication or division <code>(disjParser pDivOperator pTimesOperator)</code> of primary expressions.</p>
<p>An example of using these operators looks like this:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"1 * 2 + 3"</span> pAdditiveExpression;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some
(PBinaryOperation
(Plus,PBinaryOperation (Times,PNumber <span class="st">"1"</span>,PNumber <span class="st">"2"</span>),PNumber <span class="st">"3"</span>),
{Data = <span class="st">"1 * 2 + 3"</span>;
Position = <span class="dv">9</span>;
Indentation = [<span class="dv">0</span>];})
> parse <span class="st">"1 + 2 * 3"</span> pAdditiveExpression;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some
(PBinaryOperation
(Plus,PNumber <span class="st">"1"</span>,PBinaryOperation (Times,PNumber <span class="st">"2"</span>,PNumber <span class="st">"3"</span>)),
{Data = <span class="st">"1 + 2 * 3"</span>;
Position = <span class="dv">9</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<h3 id="recursion">Recursion</h3>
<p>One thing that was tricky to implement at first was recursion. At some point in the grammar we need to refer back to the top parser . For example a parentheses expression can have any other expression and its recognized as a primary expression. For example:</p>
<div class="sourceCode"><pre class="sourceCode python"><code class="sourceCode python"><span class="dv">1</span> <span class="op">*</span> (<span class="dv">2</span> <span class="op">+</span> <span class="dv">3</span>)</code></pre></div>
<p>Needs to be parsed as:</p>
<div class="sourceCode"><pre class="sourceCode python"><code class="sourceCode python"> <span class="op">*</span>
<span class="op">/</span> <span class="op">\</span>
<span class="op">/</span> <span class="op">\</span>
<span class="dv">1</span> (<span class="dv">2+3</span>)
<span class="op">|</span>
<span class="op">+</span>
<span class="op">/</span> <span class="op">\</span>
<span class="dv">2</span> <span class="dv">3</span></code></pre></div>
<p>What we need to do is to define a top level <code>pExpression</code> parser used for recognizing all our expressions . This parser will be used to define the parenthesis or nested expression. At this point our grammar written using pseudo BNF looks like this:</p>
<div class="sourceCode"><pre class="sourceCode python"><code class="sourceCode python">pPrimaryExpression <span class="op">=</span> pNumber <span class="op">|</span> pSymbol <span class="op">|</span> pString
pAdditiveExpression <span class="op">=</span> pPrimaryExpression ( (plusOperator <span class="op">|</span> minusOperator) pPrimaryExpression )<span class="op">*</span>
pMultiplicativeExpression <span class="op">=</span> pAdditiveExpression ( (divOperator <span class="op">|</span> timesOperator) pPrimaryExpression )<span class="op">*</span>
pTopExpression <span class="op">=</span> pMultiplicativeExpression</code></pre></div>
<p>In F# this using our set of combinators it looks like:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">let</span> myPrimaryExpression = List<span class="kw">.</span>reduce disjParser [pSymbol; pNumber; pString]
<span class="kw">let</span> pMultiplicativeExpression = pBinaryExpression (disjParser pDivOperator pTimesOperator) myPrimaryExpression
<span class="kw">let</span> pAdditiveExpression = pBinaryExpression (disjParser plusOperator minusOperator) pMultiplicativeExpression
<span class="kw">let</span> pTopExpression = pAdditiveExpression</code></pre></div>
<p>We can use <code>pTopExpression</code> to parse any expression:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"3+10*x-1/32"</span> pTopExpression;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some
(PBinaryOperation
(Minus,
PBinaryOperation
(Plus,PNumber <span class="st">"3"</span>,PBinaryOperation (Times,PNumber <span class="st">"10"</span>,PSymbol <span class="st">"x"</span>)),
PBinaryOperation (Div,PNumber <span class="st">"1"</span>,PNumber <span class="st">"32"</span>)),
{Data = <span class="st">"3+10*x-1/32"</span>;
Position = <span class="dv">11</span>;
Indentation = [<span class="dv">0</span>];})
> parse <span class="st">"x"</span> pTopExpression;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PSymbol <span class="st">"x"</span>, {Data = <span class="st">"x"</span>;
Position = <span class="dv">1</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<p>But now we want to use <code>pTopExpression</code> to define one of our primary expressions:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">//<span class="co">WARNING THE FOLLOWING CODE WILL NOT COMPILE</span>
<span class="kw">let</span> readLPar =
concatParsers whitespace (readSpecificChar <span class="ch">'('</span>)
<span class="kw">let</span> readRPar = readSpecificChar <span class="ch">')'</span>
<span class="kw">let</span> pNested = readLPar >>
pTopExpression >>= (<span class="kw">fun</span> expr ->
readRPar >> (preturn (PNested expr)))
<span class="kw">let</span> myPrimaryExpression = List<span class="kw">.</span>reduce disjParser [pSymbol; pNumber; pString; pNested]
<span class="kw">let</span> pMultiplicativeExpression = pBinaryExpression (disjParser pDivOperator pTimesOperator) myPrimaryExpression
<span class="kw">let</span> pAdditiveExpression = pBinaryExpression (disjParser plusOperator minusOperator) pMultiplicativeExpression
<span class="kw">let</span> pTopExpression = pAdditiveExpression</code></pre></div>
<p>When we try to compile this code we get the following error:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> pTopExpression >>= (<span class="kw">fun</span> expr ->
--------------^^^^^^^^^^^^^^
/dir/stdin(<span class="dv">6</span>,<span class="dv">15</span>): error FS0039: The value <span class="kw">or</span> constructor 'pTopExpression' is <span class="kw">not</span> defined</code></pre></div>
<p>Which is totally correct, <code>pTopExpression</code> is defined after <code>pNested</code>. It has to because pTopExpression is defined using <code>pAdditiveExpression</code> has a dependency on pPrimaryExpression. Until now we only used function composition to create our parsers.</p>
<p>What we want to do is to define:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> number symbol <span class="dt">string</span> nested
^ ^ ^ ^ |
| | | | |
| | | | |
+------+------+-----+ |
| |
| |
primary |
| |
| |
additive |
| |
| |
multiplicative |
| |
| |
top <-----------+</code></pre></div>
<p>To solve this problem we're going to take advantage of reference variables in F#. And do the following trick:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">let</span> pTopExpressions = <span class="kw">ref</span> []
<span class="kw">let</span> pTopExpression =
<span class="kw">fun</span> state -> (List<span class="kw">.</span>reduce disjParser !pTopExpressions) state
<span class="kw">let</span> pNested = readLPar >>
pTopExpression >>= (<span class="kw">fun</span> expr ->
readRPar >> (preturn (PNested expr)))
<span class="kw">let</span> myPrimaryExpression = List<span class="kw">.</span>reduce disjParser [pSymbol; pNumber; pString; pNested]
<span class="kw">let</span> pMultiplicativeExpression = pBinaryExpression (disjParser pDivOperator pTimesOperator) myPrimaryExpression
<span class="kw">let</span> pAdditiveExpression = pBinaryExpression (disjParser plusOperator minusOperator) pMultiplicativeExpression
pTopExpressions := [pAdditiveExpression]</code></pre></div>
<p>Using a reference (<code>ref</code>) allows us to create the recursive parser that we need . Here's an example of using it:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"1*(2+3)"</span> pTopExpression;;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some
(PBinaryOperation
(Times,PNumber <span class="st">"1"</span>,
PNested (PBinaryOperation (Plus,PNumber <span class="st">"2"</span>,PNumber <span class="st">"3"</span>))),
{Data = <span class="st">"1*(2+3)"</span>;
Position = <span class="dv">7</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<h3 id="next-steps">Next steps</h3>
<p>Using the same techniques presented so far we can finish our basic grammar. This is part #2 of an ongoing series of posts on building a parser for a small language. The first post can be found here: <a href="http://langexplr.blogspot.com/2017/01/a-simple-language-with-indentation.html" class="uri">http://langexplr.blogspot.com/2017/01/a-simple-language-with-indentation.html</a>.</p>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-54942615851645768702017-01-29T09:36:00.001-06:002017-01-29T09:36:12.728-06:00A simple language with indentation based blocks. Part 1: Parsing combinators<p>In this post, I'm going to start with the implementation of the parser using the F# programming language. There are several tools for creating parsers for example <strong>FParsec</strong> <a href="http://www.quanttec.com/fparsec/" class="uri">http://www.quanttec.com/fparsec/</a> or <strong>FsYacc/FsLex</strong> <a href="https://en.wikibooks.org/wiki/F_Sharp_Programming/Lexing_and_,arsing" class="uri">https://en.wikibooks.org/wiki/F_Sharp_Programming/Lexing_and_,arsing</a>. However for this experiment I wanted to create a small set of simple parser combinators, just to learn more about them.</p>
<p>The contents of this post is loosely based on the definition of the <strong>Parser Monad</strong> . There are many great articles on the net about them. One of this papers is the incredibly nice <em>Monadic Parsing in Haskell</em> <a href="http://www.cs.nott.ac.uk/~pszgmh/pearl.pdf" class="uri">http://www.cs.nott.ac.uk/~pszgmh/pearl.pdf</a> .</p>
<p>Let's start by defining the type of the state of our parser:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">type</span> ReaderState = { Data : <span class="dt">string</span>;
Position: <span class="dt">int</span>;
Indentation: <span class="dt">int</span> list}</code></pre></div>
<p>This state contains the following:</p>
<ul>
<li>Data : the input string containing the program to parse</li>
<li>Position : the current position of the parser inside the Data string</li>
<li>Indentation : an indentation stack (more on that in future posts)</li>
</ul>
<p>And now we're going to define the type of a "parser" :</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">ReaderState -> (('a * ReaderState) <span class="dt">option</span> )</code></pre></div>
<p>This means that a "parser" is a function that takes the reader state and returns a tuple of some parsed value (<code>'a</code>) and the new parsing state. Notice that parsers could fail, so the result it's wrapped in an <code>option</code> type <a href="https://docs.microsoft.com/en-us/dotnet/articles/fsharp/language-reference/options" class="uri">https://docs.microsoft.com/en-us/dotnet/articles/fsharp/language-reference/options</a>.</p>
<p>A very simple example of a parser is the following:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> readChar(state : ReaderState) : (<span class="dt">string</span> * ReaderState) <span class="dt">option</span> =
<span class="kw">if</span> state.Data<span class="kw">.</span>Length > state.Position <span class="kw">then</span>
Some (state.Data<span class="kw">.</span>[state.Position].ToString(),
{ state <span class="kw">with</span> Position = state.Position + <span class="dv">1</span> } )
<span class="kw">else</span>
None</code></pre></div>
<p>We can test this parser using the following function:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> parse (input : <span class="dt">string</span>) (parser : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> ))) =
parser { Data = input ; Position = <span class="dv">0</span>; Indentation = [<span class="dv">0</span>] }</code></pre></div>
<p>For example:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"hello"</span> readChar;;
<span class="kw">val</span> it : (<span class="dt">string</span> * ReaderState) <span class="dt">option</span> = Some (<span class="st">"h"</span>, {Data = <span class="st">"hello"</span>;
Position = <span class="dv">1</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<p>Here we can see that the result is a successful optional <code>Some</code> with a string with the single recognized char . Also part of the result is the new reader state .</p>
<p>We can also specify operations for several characters for example:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> readZeroOrMoreChars (pred:<span class="dt">char</span> -> <span class="dt">bool</span>) (state : ReaderState) : (<span class="dt">string</span> * ReaderState) <span class="dt">option</span> =
<span class="kw">let</span>
secondPosition = readingChar state.Position pred state.Data
<span class="kw">in</span>
Some ( state.Data<span class="kw">.</span>Substring(state.Position,
secondPosition - state.Position),
{ state <span class="kw">with</span> Position = secondPosition })</code></pre></div>
<p>We can use this function as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"1231abc"</span> (readZeroOrMoreChars System<span class="kw">.</span>Char<span class="kw">.</span>IsDigit);;
<span class="kw">val</span> it : (<span class="dt">string</span> * ReaderState) <span class="dt">option</span> = Some (<span class="st">"1231"</span>, {Data = <span class="st">"1231abc"</span>;
Position = <span class="dv">4</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<p>Using this function we can define a parser for whitespace:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> whitespace = readZeroOrMoreChars System<span class="kw">.</span>Char<span class="kw">.</span>IsWhiteSpace</code></pre></div>
<h2 id="connecting-parsers">Connecting parsers</h2>
<p>The parsers I've been showing so far look very simple, and they are!. The goal is to have small parsers and combine them to create more interesting ones. The next operation is called <code>concatParsers2</code> and it's goal is create a new parser that will execute two parsers in sequence. That is, apply the first one and with the resulting state, execute the second one.</p>
<p>For example, the following parser for recognizing symbols use the <code>readWithConditionOnChar</code> parser with the <code>readZeroOrMoreChars</code> in order to create a <code>PSymbol</code> with the recognized element:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> symbol =
concatParsers2
(readWithConditionOnChar (<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsLetter(c, <span class="dv">0</span>)))
(<span class="kw">fun</span> initialChar ->
concatParsers2
(readZeroOrMoreChars (<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsLetter(c) || System<span class="kw">.</span>Char<span class="kw">.</span>IsDigit(c)))
(<span class="kw">fun</span> suffixString -> (preturn (PSymbol (initialChar + suffixString))))
)</code></pre></div>
<p>In our little language a symbol is represented by :</p>
<ul>
<li>a letter</li>
<li>zero or more letters or numbers</li>
</ul>
<p>We can use the <code>readWithConditionOnChar</code> and <code>readZeroOrMoreChars</code> to archive these goals, for example:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"hello"</span> (readWithConditionOnChar (<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsLetter(c, <span class="dv">0</span>)))- ;;
<span class="kw">val</span> it : (<span class="dt">string</span> * ReaderState) <span class="dt">option</span> = Some (<span class="st">"h"</span>, {Data = <span class="st">"hello"</span>;
Position = <span class="dv">1</span>;
Indentation = [<span class="dv">0</span>];})
> parse <span class="st">"hi1and2and3"</span> (readZeroOrMoreChars (<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsLetter(c) || - System<span class="kw">.</span>Char<span class="kw">.</span>IsDigit(c)));;
<span class="kw">val</span> it : (<span class="dt">string</span> * ReaderState) <span class="dt">option</span> =
Some (<span class="st">"hi1and2and3"</span>, {Data = <span class="st">"hi1and2and3"</span>;
Position = <span class="dv">11</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<p>Notice that we cannot use just <code>readZeroOrMoreChars</code> since it will recognize symbols starting with numbers (like '13hello').</p>
<p>We can create a small parser for recognizing a letter (<code>readWithConditionOnChar</code>) and we can use <code>readZeroOrMoreChars</code> to read the rest. We could combine these two blocks to get another parser. The key for composing our parsers is the <code>concatParsers2</code> function. This function has the following signature:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> concatParsers2;;
<span class="kw">val</span> it :
((ReaderState -> ('a * ReaderState) <span class="dt">option</span>) ->
('a -> ReaderState -> ('b * ReaderState) <span class="dt">option</span>) -> ReaderState ->
('b * ReaderState) <span class="dt">option</span>) = <<span class="kw">fun</span>:clo@<span class="dv">21-1</span>>
</code></pre></div>
<p>This signature means that <code>concatParsers2</code> receives a parser that produces a value of type <code>'a</code>. The second argument is a function that receives a value of type <code>'a</code> (the result of the first parser) and returns a parser of another type <code>'b</code>. The result of <code>concatParsers2</code> is itself another parser that produces a value of type <code>'b</code>.</p>
<p>The implementation looks like this:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> concatParsers2 (parser1 : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> )))
(parser2N : ('a -> (ReaderState -> (('b * ReaderState) <span class="dt">option</span> )))) =
<span class="kw">fun</span> input -> <span class="kw">match</span> (parser1 input) <span class="kw">with</span>
| Some (matchedTxt, restState) -> (parser2N matchedTxt) restState
| _ -> None</code></pre></div>
<p>This small function lets us create parsers using small blocks. But before we do that, we need to create another useful operation.</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">let</span> preturn aValue (state : ReaderState ) = Some (aValue, state)</code></pre></div>
<p>This operation is very simple, but really important!. It lets us prepare a result. By taking a look at the signature, we can see that it matches our <code>parser</code> signature. We can now used it in conjunction with <code>concatParsers2</code> to produce results:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"AXXXC"</span>
- (concatParsers2 recognizeABC
- (<span class="kw">fun</span> firstChar ->
- (concatParsers2
- recognizeXs
- (<span class="kw">fun</span> xs ->
- (concatParsers2
- recognizeABC
- (<span class="kw">fun</span> lastChar ->
- preturn (firstChar, xs, lastChar)- ))))));;
<span class="kw">val</span> it : ((<span class="dt">string</span> * <span class="dt">string</span> * <span class="dt">string</span>) * ReaderState) <span class="dt">option</span> =
Some ((<span class="st">"A"</span>, <span class="st">"XXX"</span>, <span class="st">"C"</span>), {Data = <span class="st">"AXXXC"</span>;
Position = <span class="dv">5</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<p>Given that we define <code>recognizeABC</code> and <code>recognizeXs</code> as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> <span class="kw">let</span> recognizeABC = readWithConditionOnChar (<span class="kw">fun</span> c -> c = <span class="st">"A"</span> || c = <span class="st">"B"</span> || c= <span class="st">"C"</span>);;
<span class="kw">val</span> recognizeABC : (ReaderState -> (<span class="dt">string</span> * ReaderState) <span class="dt">option</span>)
> <span class="kw">let</span> recognizeXs = readZeroOrMoreChars (<span class="kw">fun</span> c -> c = <span class="ch">'X'</span> ) ;;
<span class="kw">val</span> recognizeXs : (ReaderState -> (<span class="dt">string</span> * ReaderState) <span class="dt">option</span>)</code></pre></div>
<p>Using the <code>concatParsers2</code> function seems a little verbose. We can borrow inspiration from the Haskell's Monad type class <a href="https://hackage.haskell.org/package/base-4.9.1.0/docs/Control-Monad.html#t:Monad" class="uri">https://hackage.haskell.org/package/base-4.9.1.0/docs/Control-Monad.html#t:Monad</a> by defining versions of the <code>>>=</code> operator as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> <span class="kw">inline</span> (>>=) (parser1 : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> )))
(parser2N : ('a -> (ReaderState -> (('b * ReaderState) <span class="dt">option</span> )))) = concatParsers2 parser1 parser2N</code></pre></div>
<p>Now using this operator we can write:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">parse <span class="st">"AXXXC"</span> ( recognizeABC >>= (<span class="kw">fun</span> firstChar ->
recognizeXs >>= (<span class="kw">fun</span> xs ->
recognizeABC >>= (<span class="kw">fun</span> lastChar ->
preturn (firstChar, xs, lastChar)))))</code></pre></div>
<h2 id="ignoring-output-from-previous-parsers">Ignoring output from previous parsers</h2>
<p>Another useful operation allows us to connect two parsers but</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> concatParsers (parser1 : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> )))
(parser2 : (ReaderState -> (('b * ReaderState) <span class="dt">option</span> ))) =
<span class="kw">fun</span> input -> <span class="kw">match</span> (parser1 input) <span class="kw">with</span>
| Some (_, restState) -> parser2 restState
| _ -> None</code></pre></div>
<p>Notice that it's similar to the <code>concatParsers2</code> but it ignores the result of <code>parser1</code>. This is useful for discarting whitespace:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"><span class="kw">let</span> whitespaceNoNl =
readZeroOrMoreChars
(<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsWhiteSpace(c) && c <> <span class="ch">'\n'</span>)
<span class="kw">let</span> colon =
concatParsers whitespaceNoNl (readSpecificChar <span class="ch">':'</span>)
</code></pre></div>
<p>As with the <code>concatParsers2</code> we can use another well known operator for this operation:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> <span class="kw">inline</span> (>>) (parser1 : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> )))
(parser2 : (ReaderState -> (('b * ReaderState) <span class="dt">option</span> ))) = concatParsers parser1 parser2</code></pre></div>
<h2 id="useful-parsing-operations">Useful parsing operations</h2>
<p>We need to create more operations that help us create complex parsers. For example, we can create a small operation for optional elements:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> optionalP (parser : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> ))) (defaultValue:'a) =
<span class="kw">fun</span> input -> <span class="kw">match</span> (parser input) <span class="kw">with</span>
| result & Some _ -> result
| _ -> (Some (defaultValue, input))</code></pre></div>
<p>We can use this new operator to parse numbers as follows:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> number =
( (optionalP (readSpecificChar <span class="ch">'-'</span>) <span class="st">""</span>) >>= (<span class="kw">fun</span> neg ->
digitP >>= (<span class="kw">fun</span> firstChar ->
(readZeroOrMoreChars (<span class="kw">fun</span> c -> System<span class="kw">.</span>Char<span class="kw">.</span>IsDigit(c))) >>= (<span class="kw">fun</span> chars ->
(optionalP decimalPartP <span class="st">""</span>) >>= (<span class="kw">fun</span> dec ->
preturn (PNumber (neg + firstChar + chars + dec))))</code></pre></div>
<h2 id="choosing-from-two-options">Choosing from two options</h2>
<p>The following operation helps us to try to use one parser and fallback to another if it didn't work:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> disjParser (parser1 : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> )))
(parser2 : (ReaderState -> (('a * ReaderState) <span class="dt">option</span> ))) =
<span class="kw">fun</span> input -> <span class="kw">match</span> (parser1 input) <span class="kw">with</span>
| result & Some _ -> result
| _ -> parser2 input</code></pre></div>
<p>A simple scenario using this parser looks like this:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"39"</span> (disjParser symbol number);;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PNumber <span class="st">"39"</span>, {Data = <span class="st">"39"</span>;
Position = <span class="dv">2</span>;
Indentation = [<span class="dv">0</span>];})
> parse <span class="st">"hello"</span> (disjParser symbol number);;
<span class="kw">val</span> it : (PExpr * ReaderState) <span class="dt">option</span> =
Some (PSymbol <span class="st">"hello"</span>, {Data = <span class="st">"hello"</span>;
Position = <span class="dv">5</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<h2 id="repetitions">Repetitions</h2>
<p>Identifying sequences of elements identified by a parser is very useful. We can define the following operations</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp"> <span class="kw">let</span> <span class="kw">rec</span> oneOrMore parser accumulated =
parser >>=
(<span class="kw">fun</span> lastResult ->
<span class="kw">let</span> result = lastResult::accumulated
<span class="kw">in</span> disjParser (oneOrMore parser result) (preturn (List<span class="kw">.</span>rev result)))
<span class="kw">let</span> zeroOrMore parser accumulated =
disjParser (oneOrMore parser accumulated) (preturn accumulated)</code></pre></div>
<p>A simple example of using this operation looks like this:</p>
<div class="sourceCode"><pre class="sourceCode fsharp"><code class="sourceCode fsharp">> parse <span class="st">"1 2 3 4"</span> (zeroOrMore (whitespace >> number) []);;
<span class="kw">val</span> it : (PExpr list * ReaderState) <span class="dt">option</span> =
Some
([PNumber <span class="st">"1"</span>; PNumber <span class="st">"2"</span>; PNumber <span class="st">"3"</span>; PNumber <span class="st">"4"</span>],
{Data = <span class="st">"1 2 3 4"</span>;
Position = <span class="dv">10</span>;
Indentation = [<span class="dv">0</span>];})</code></pre></div>
<p>The next post will show how to create more interesting things with the pieces we have so far.</p>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-44162599543022948622017-01-29T09:29:00.001-06:002017-04-10T20:53:13.989-06:00A simple language with indentation based blocks (part 0)<p>One of the first things I noticed when reading about Python, is the use of indentation for defining code blocks. For example:</p>
<div class="sourceCode"><pre class="sourceCode python"><code class="sourceCode python"><span class="kw">def</span> foo(x):
<span class="cf">while</span> x <span class="op"><</span> <span class="dv">20</span>:
<span class="cf">if</span> x <span class="op">></span> <span class="dv">10</span>:
<span class="bu">print</span> <span class="st">"argument is greater than 10"</span>
<span class="bu">print</span> <span class="st">"value: "</span> <span class="op">+</span> x
<span class="cf">else</span>:
<span class="bu">print</span> <span class="st">"the argument is less than or equal to 10"</span>
<span class="bu">print</span> <span class="st">"its value is : "</span> <span class="op">+</span> x</code></pre></div>
<p>If you're only familiar to C-based language this seems a bit strange. Not using characters like '{}' or words like BEGIN/END seems fragile at first. For example one could expect something like:</p>
<div class="sourceCode"><pre class="sourceCode java"><code class="sourceCode java">def <span class="fu">foo</span>(x) {
<span class="kw">while</span> x < <span class="dv">20</span> {
<span class="kw">if</span> x > <span class="dv">10</span> {
print <span class="st">"argument is greater than 10"</span>
print <span class="st">"value: "</span> + x
} <span class="kw">else</span> {
print <span class="st">"the argument is less than or equal to 10"</span>
print <span class="st">"its value is : "</span> + x
}
}</code></pre></div>
<p>I've always wondered how do you create a parser for this kind of a language. In the following series of posts I'm going to record my experiences writing a parser for a simple little language. This language will use a style similar to Python. I'm going to write the code using F# .</p>
<h2 id="posts">Posts</h2>
<ol style="list-style-type: decimal">
<li><a href="http://langexplr.blogspot.com/2017/01/a-simple-language-with-indentation_29.html">Parsing combinators</a></li>
<li><a href="http://langexplr.blogspot.com/2017/02/a-simple-language-with-indentation.html">Expressions</a></li>
<li><a href="http://langexplr.blogspot.com/2017/03/a-simple-language-with-indentation.html">Blocks</a></li>
<li><a href="http://langexplr.blogspot.com/2017/04/a-simple-language-with-indentation.html">Error messages</a></li>
</ol>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-30211116018216187812016-08-13T10:37:00.000-06:002016-08-13T10:37:40.301-06:00Solving a small primary school problem with Prolog<p>A couple of days ago my small son came home with math homework from school. The problem: add parenthesis to the following arithmetic expression so it makes sense.</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="dv">14</span> <span class="fu">*</span> <span class="dv">3</span> <span class="fu">-</span> <span class="dv">8</span> <span class="fu">/</span> <span class="dv">2</span> <span class="kw">=</span> <span class="dv">17</span></code></pre>
<p>When I saw that, I thought it was a nice little programming exercise. Also Prolog seems like an appropriate language to write the a solution for this problem.</p>
<p>To solve this problem we need at least to:</p>
<ol style="list-style-type: decimal">
<li>Choose a representation for the input formula and the results</li>
<li>A way to generate all possible combinations of arithmetic expressions</li>
<li>Something to evaluate the arithmetic expression so we can get the result</li>
<li>Let Prolog find the answer we need!</li>
</ol>
<p>First, we need to generate all possible expressions from given the problem .</p>
<h2 id="input-representation">Input representation</h2>
<p>We're going to represent the input formula as a list of the parts of the expression.</p>
<p>For example, given the following expression:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="dv">14</span> <span class="fu">*</span> <span class="dv">3</span> <span class="fu">-</span> <span class="dv">8</span> <span class="fu">/</span> <span class="dv">2</span> </code></pre>
<p>The input representation for this formula is the following:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">[ <span class="dv">14</span>, '*', <span class="dv">3</span>, '-', <span class="dv">8</span>, '/', <span class="dv">2</span> ]</code></pre>
<p>To represent the output formula I'm going to use a term with the form <code>op(operator, left, right)</code>.</p>
<p>For example, to represent the following possible groupings:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">(<span class="dv">9</span><span class="fu">*</span>(<span class="dv">6</span><span class="fu">+</span>(<span class="dv">6</span><span class="fu">/</span>(<span class="dv">6-9</span>))))</code></pre>
<p>It will be represented as:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">9</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">+</span><span class="kw">,</span> <span class="dv">6</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="dv">6</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">-</span><span class="kw">,</span> <span class="dv">6</span><span class="kw">,</span> <span class="dv">9</span>))))</code></pre>
<h2 id="generating-expression-groupings">Generating expression groupings</h2>
<p>Given the representation of the problem we can write a predicate to generate all possible groupings of these operations.</p>
<p>After some unsuccessful attempts I came with the following predicate:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">arith_op([<span class="dt">X</span>]<span class="kw">,</span> <span class="dt">X</span>) <span class="kw">:-</span> <span class="dt">number</span>(<span class="dt">X</span>)<span class="kw">,!.</span>
arith_op(<span class="dt">Arr</span><span class="kw">,</span> <span class="fu">op</span>(<span class="dt">Op</span><span class="kw">,</span> <span class="dt">X</span><span class="kw">,</span> <span class="dt">Y</span>)) <span class="kw">:-</span>
append(<span class="dt">First</span><span class="kw">,</span> [<span class="dt">Op</span> <span class="fu">|</span> <span class="dt">Second</span>]<span class="kw">,</span> <span class="dt">Arr</span>)<span class="kw">,</span>
arith_op(<span class="dt">First</span><span class="kw">,</span> <span class="dt">X</span>)<span class="kw">,</span>
arith_op(<span class="dt">Second</span><span class="kw">,</span> <span class="dt">Y</span>)<span class="kw">.</span></code></pre>
<p>What I really like about Prolog is that with relative few words we can find a solution for problems like this.</p>
<p>Now I can take advantage from Prolog's backtracking mechanism and find all possible solutions for the following input.</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="fu">?-</span> arith_op([ <span class="dv">1</span>, '*', <span class="dv">2</span>, '+', <span class="dv">3</span>, '/', <span class="dv">4</span>] <span class="kw">,</span><span class="dt">X</span>)<span class="kw">.</span>
<span class="dt">X</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">1</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">+</span><span class="kw">,</span> <span class="dv">2</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="dv">3</span><span class="kw">,</span> <span class="dv">4</span>))) <span class="kw">;</span>
<span class="dt">X</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">1</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">+</span><span class="kw">,</span> <span class="dv">2</span><span class="kw">,</span> <span class="dv">3</span>)<span class="kw">,</span> <span class="dv">4</span>)) <span class="kw">;</span>
<span class="dt">X</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">+</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">1</span><span class="kw">,</span> <span class="dv">2</span>)<span class="kw">,</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="dv">3</span><span class="kw">,</span> <span class="dv">4</span>)) <span class="kw">;</span>
<span class="dt">X</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">1</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">+</span><span class="kw">,</span> <span class="dv">2</span><span class="kw">,</span> <span class="dv">3</span>))<span class="kw">,</span> <span class="dv">4</span>) <span class="kw">;</span>
<span class="dt">X</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">+</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">1</span><span class="kw">,</span> <span class="dv">2</span>)<span class="kw">,</span> <span class="dv">3</span>)<span class="kw">,</span> <span class="dv">4</span>) <span class="kw">;</span>
<span class="kw">false.</span></code></pre>
<h2 id="evaluating-the-arithmetic-expressions">Evaluating the arithmetic expressions</h2>
<p>Having a way to evaluate the expression is useful so we can verify the result of the operation. A simple way to implement it looks like this:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">eval(<span class="fu">op</span>(<span class="dt">Op</span><span class="kw">,</span><span class="dt">X</span><span class="kw">,</span><span class="dt">Y</span>)<span class="kw">,</span><span class="dt">Result</span>) <span class="kw">:-</span>
eval(<span class="dt">X</span><span class="kw">,</span><span class="dt">R1</span>)<span class="kw">,</span>eval(<span class="dt">Y</span><span class="kw">,</span><span class="dt">R2</span>)<span class="kw">,</span>
( (<span class="dt">Op</span> <span class="kw">=</span> '+'<span class="kw">,</span> <span class="dt">Result</span> <span class="dt">is</span> (<span class="dt">R1</span> <span class="dt">+</span> <span class="dt">R2</span>))
<span class="kw">;</span> (<span class="dt">Op</span> <span class="kw">=</span> '-'<span class="kw">,</span> <span class="dt">Result</span> <span class="dt">is</span> (<span class="dt">R1</span> <span class="dt">-</span> <span class="dt">R2</span>))
<span class="kw">;</span> (<span class="dt">Op</span> <span class="kw">=</span> '*'<span class="kw">,</span> <span class="dt">Result</span> <span class="dt">is</span> (<span class="dt">R1</span> <span class="dt">*</span> <span class="dt">R2</span>))
<span class="kw">;</span> (<span class="dt">Op</span> <span class="kw">=</span> '/'<span class="kw">,</span> <span class="dt">Result</span> <span class="dt">is</span> (<span class="dt">R1</span> <span class="fl">/</span> <span class="dt">R2</span>)))<span class="kw">,</span> <span class="kw">!.</span>
eval(<span class="dt">X</span><span class="kw">,</span> <span class="dt">X</span>)<span class="kw">.</span></code></pre>
<p>With this predicate we can get the result of an operation. For example:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="fu">?-</span> eval(<span class="fu">op</span>('+'<span class="kw">,</span> <span class="fu">op</span>('*'<span class="kw">,</span> <span class="dv">34</span><span class="kw">,</span> <span class="dv">23</span>)<span class="kw">,</span> <span class="dv">34</span>)<span class="kw">,</span> <span class="dt">R</span>)<span class="kw">.</span>
<span class="dt">R</span> <span class="kw">=</span> <span class="dv">816</span><span class="kw">.</span></code></pre>
<h2 id="solving-the-problem">Solving the problem</h2>
<p>With these two predicates we can solve the problem like this:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="fu">?-</span> arith_op([ <span class="dv">14</span>, '*', <span class="dv">3</span>,'-', <span class="dv">8</span>, '/', <span class="dv">2</span> ] <span class="kw">,</span><span class="dt">Operation</span>)<span class="kw">,</span> eval(<span class="dt">Operation</span><span class="kw">,</span> <span class="dv">17</span>)<span class="kw">.</span>
<span class="dt">Operation</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">-</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">14</span><span class="kw">,</span> <span class="dv">3</span>)<span class="kw">,</span> <span class="dv">8</span>)<span class="kw">,</span> <span class="dv">2</span>) <span class="kw">;</span>
<span class="kw">false.</span></code></pre>
<p>Now it is useful to present the results using infix notation with parenthesis. To do this we can write the following predicate:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">forprint(<span class="fu">op</span>(<span class="dt">Op</span><span class="kw">,</span><span class="dt">X</span><span class="kw">,</span><span class="dt">Y</span>)) <span class="kw">:-</span>
writef(<span class="ot">"("</span>)<span class="kw">,</span>
forprint(<span class="dt">X</span>)<span class="kw">,</span>
writef(<span class="dt">Op</span>)<span class="kw">,</span>
forprint(<span class="dt">Y</span>)<span class="kw">,</span>
writef(<span class="ot">")"</span>)<span class="kw">,!.</span>
forprint(<span class="dt">X</span>) <span class="kw">:-</span>
<span class="fu">write</span>(<span class="dt">X</span>)<span class="kw">,!.</span></code></pre>
<p>Now we can write:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">arith_op([ <span class="dv">14</span>, '*', <span class="dv">3</span>,'-', <span class="dv">8</span>, '/', <span class="dv">2</span> ] <span class="kw">,</span><span class="dt">Operation</span>)<span class="kw">,</span> eval(<span class="dt">Operation</span><span class="kw">,</span> <span class="dv">17</span>)<span class="kw">,</span> forprint(<span class="dt">Operation</span>)<span class="kw">.</span>
(((<span class="dv">14</span><span class="fu">*</span><span class="dv">3</span>)<span class="fu">-</span><span class="dv">8</span>)<span class="fu">/</span><span class="dv">2</span>)
<span class="dt">Operation</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">-</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">14</span><span class="kw">,</span> <span class="dv">3</span>)<span class="kw">,</span> <span class="dv">8</span>)<span class="kw">,</span> <span class="dv">2</span>) <span class="kw">;</span>
<span class="kw">false.</span></code></pre>
<p>I can also use this predicate to generate samples of results for other groupings. For example:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="fu">?-</span> arith_op([ <span class="dv">14</span>, '*', <span class="dv">3</span>,'-', <span class="dv">8</span>, '/', <span class="dv">2</span> ] <span class="kw">,</span><span class="dt">Operation</span>)<span class="kw">,</span> eval(<span class="dt">Operation</span><span class="kw">,</span> <span class="dt">Result</span>)<span class="kw">,</span> <span class="dt">Result</span> <span class="dt">></span> <span class="dv">0</span><span class="kw">,</span> forprint(<span class="dt">Operation</span>)<span class="kw">.</span>
((<span class="dv">14</span><span class="fu">*</span><span class="dv">3</span>)<span class="fu">-</span>(<span class="dv">8</span><span class="fu">/</span><span class="dv">2</span>))
<span class="dt">Operation</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">-</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">14</span><span class="kw">,</span> <span class="dv">3</span>)<span class="kw">,</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="dv">8</span><span class="kw">,</span> <span class="dv">2</span>))<span class="kw">,</span>
<span class="dt">Result</span> <span class="kw">=</span> <span class="dv">38</span> <span class="kw">;</span>
(((<span class="dv">14</span><span class="fu">*</span><span class="dv">3</span>)<span class="fu">-</span><span class="dv">8</span>)<span class="fu">/</span><span class="dv">2</span>)
<span class="dt">Operation</span> <span class="kw">=</span> <span class="fu">op</span>(<span class="fu">/</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">-</span><span class="kw">,</span> <span class="fu">op</span>(<span class="fu">*</span><span class="kw">,</span> <span class="dv">14</span><span class="kw">,</span> <span class="dv">3</span>)<span class="kw">,</span> <span class="dv">8</span>)<span class="kw">,</span> <span class="dv">2</span>)<span class="kw">,</span>
<span class="dt">Result</span> <span class="kw">=</span> <span class="dv">17</span> <span class="kw">;</span>
<span class="kw">false.</span></code></pre>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-10244035639434404242016-05-21T21:45:00.000-06:002016-05-21T21:45:00.952-06:00Some things I learned while creating a small program in Mercury<p>Some time ago I started creating a program using the <a href="https://www.mercurylang.org/">Mercury programming language</a> to create images using the <a href="https://en.wikipedia.org/wiki/Mandelbrot_set#Escape_time_algorithm">Escape Time algorithm</a>. The goal was to learn about the language by solving a small problem.</p>
<p>The current result of this experiment can be found here <a href="https://github.com/ldfallas/graphicswithmercury/">https://github.com/ldfallas/graphicswithmercury/</a>. Here's a list of things I learned.</p>
<h2 id="terms-for-configuration-files">Terms for configuration files</h2>
<p>For this program I wanted to have a configuration file to specify :</p>
<ul>
<li>The resolution of the final image</li>
<li>The coordinates used to render the fractal</li>
<li>The formula to use with the escape time algorithm</li>
<li>The palette to be used to render the final image</li>
</ul>
<p>To create this configuration file I could use XML or create a special file format and parse it using Mercury's DCG. However I chose to use a different alternative, which is to use the <code>term</code> syntax. </p>
<p>Here's an example of the configuration file:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"> fractal_config(
image_resolution(<span class="dv">320</span><span class="kw">,</span><span class="dv">200</span>)<span class="kw">,</span>
top_left(<span class="fu">-</span><span class="fl">2.0</span><span class="kw">,</span> <span class="fl">1.5</span>)<span class="kw">,</span>
bottom_right(<span class="fl">1.0</span> <span class="kw">,</span> <span class="fu">-</span><span class="fl">1.5</span>)<span class="kw">,</span>
formula(z<span class="fu">*</span>z <span class="fu">+</span> z <span class="fu">+</span> c)<span class="kw">,</span>
palette(
single(<span class="dv">10</span><span class="kw">,</span><span class="dv">20</span><span class="kw">,</span><span class="dv">30</span>)<span class="kw">,</span>
range(from(<span class="dv">10</span><span class="kw">,</span> <span class="dv">30</span><span class="kw">,</span> <span class="dv">40</span>)<span class="kw">,</span> to(<span class="dv">30</span><span class="kw">,</span> <span class="dv">50</span><span class="kw">,</span> <span class="dv">76</span>)<span class="kw">,</span><span class="dv">127</span>)<span class="kw">,</span>
range(from(<span class="dv">200</span><span class="kw">,</span> <span class="dv">100</span><span class="kw">,</span> <span class="dv">50</span>)<span class="kw">,</span>to(<span class="dv">150</span><span class="kw">,</span> <span class="dv">0</span><span class="kw">,</span> <span class="dv">0</span>)<span class="kw">,</span><span class="dv">100</span>)<span class="kw">,</span>
range(from(<span class="dv">200</span><span class="kw">,</span> <span class="dv">100</span><span class="kw">,</span> <span class="dv">50</span>)<span class="kw">,</span>to(<span class="dv">150</span><span class="kw">,</span> <span class="dv">10</span><span class="kw">,</span> <span class="dv">10</span>)<span class="kw">,</span><span class="dv">27</span>)<span class="kw">,</span>
single(<span class="dv">0</span><span class="kw">,</span><span class="dv">0</span><span class="kw">,</span><span class="dv">0</span>)
)
)<span class="kw">.</span> </code></pre>
<p>Here I'm saying that:</p>
<ul>
<li>The image will have a 320px by 200px resolution</li>
<li>The <code>real</code> coordinates of this image are between -2.0 and 1.0 in the X axis and 1.5 and 1.5 in the Y axis</li>
<li>The formula used in the escape time algorithm will be <code>z*z + z + c</code></li>
<li>The palette will be constructed with the given ranges of colors</li>
</ul>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicJeHWQEge3r_kvkd9yFJUu42vyvrq2TzVJ4dg11U5JKVAetOh-UhM8297G7Pa1iKyxM-VJNzVnhsaGPyt08GhUNWVNQKpAa-VMVq3SjI3jI7Ad0iI3JuB98PUSvms3wEqcZCby-o7j-MA/s1600/filefrt1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEicJeHWQEge3r_kvkd9yFJUu42vyvrq2TzVJ4dg11U5JKVAetOh-UhM8297G7Pa1iKyxM-VJNzVnhsaGPyt08GhUNWVNQKpAa-VMVq3SjI3jI7Ad0iI3JuB98PUSvms3wEqcZCby-o7j-MA/s1600/filefrt1.jpg" /></a></div>
<p>In order to read these term I used the <a href="https://www.mercurylang.org/information/doc-release/mercury_library/term.html#term">term</a> and <a href="https://www.mercurylang.org/information/doc-release/mercury_library/parser.html#parser">parser</a> modules which provides an easy interface for reading terms.</p>
<p>Here's a code snippet showing how the file is being loaded.</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred read_fractal_configuration_from_file(
string::in<span class="kw">,</span>
maybe_error(fractal_configuration)::out<span class="kw">,</span>
io::di<span class="kw">,</span> io::uo) <span class="dt">is</span> det<span class="kw">.</span>
read_fractal_configuration_from_file(<span class="dt">FileName</span><span class="kw">,</span> <span class="dt">Configurati</span> onResult<span class="kw">,</span> <span class="kw">!</span><span class="dt">IO</span>) <span class="kw">:-</span>
parser<span class="kw">.</span>read_term_filename( <span class="dt">FileName</span><span class="kw">,</span> <span class="dt">ReadTermResult</span><span class="kw">,</span> <span class="kw">!</span><span class="dt">IO</span>)<span class="kw">,</span>
((<span class="dt">ReadTermResult</span> <span class="kw">=</span> term(<span class="dt">_</span><span class="kw">,</span> <span class="dt">Term</span>)<span class="kw">,</span>
term_to_fractal_configuration(<span class="dt">Term</span><span class="kw">,</span> <span class="dt">ConfigurationResult</span>))
<span class="kw">;</span> (<span class="dt">ReadTermResult</span> <span class="kw">=</span> error(<span class="dt">ErrMessage</span><span class="kw">,</span> <span class="dt">_</span>)<span class="kw">,</span>
<span class="dt">ConfigurationResult</span> <span class="kw">=</span> error(<span class="dt">ErrMessage</span>))
<span class="kw">;</span> (<span class="dt">ReadTermResult</span> <span class="kw">=</span> eof<span class="kw">,</span>
<span class="dt">ConfigurationResult</span> <span class="kw">=</span> error(<span class="ot">"</span><span class="er">Empty</span><span class="al"> </span><span class="er">file</span><span class="ot">"</span>))
)<span class="kw">.</span></code></pre>
<p>The <code>parser.read_term_filename</code> reads these terms to a <code>term</code> data structure. The <code>term_to_fractal_configuration</code> predicate creates a configuration structure from these terms. An error is returned if the file doesn't have the expected structure. This is archived using the <code>maybe_error</code> data type.</p>
<p>Here's an example of how the first part of the configuration is loaded:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred term_to_fractal_configuration(
term(string)::in<span class="kw">,</span>
maybe_error(fractal_configuration)::out) <span class="dt">is</span> det<span class="kw">.</span>
term_to_fractal_configuration(<span class="dt">Term</span><span class="kw">,</span> <span class="dt">Result</span>) <span class="kw">:-</span>
(if <span class="dt">Term</span> <span class="kw">=</span> <span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">fractal_config</span><span class="ot">"</span>)<span class="kw">,</span><span class="dt">Args</span><span class="kw">,</span><span class="dt">_</span>) then
term_to_fractal_config_resolution(<span class="dt">Args</span><span class="kw">,</span> <span class="dt">Result</span>)
else
error_message_with_location(<span class="ot">"</span><span class="er">Expecting</span><span class="al"> </span><span class="ot">'</span><span class="er">fractal_config</span><span class="ot">'"</span><span class="kw">,</span><span class="dt">Term</span><span class="kw">,</span> <span class="dt">Message</span>)<span class="kw">,</span>
<span class="dt">Result</span> <span class="kw">=</span> error(<span class="dt">Message</span>)
)<span class="kw">.</span></code></pre>
<p>One interesting feature of the <code>term</code> library is that it stores line number information. This makes it easy to report errors that occurred in a specific line of the input file:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred error_message_with_location(
string::in<span class="kw">,</span>
term(string)::in<span class="kw">,</span>
string::out) <span class="dt">is</span> det<span class="kw">.</span>
error_message_with_location(<span class="dt">Msg</span><span class="kw">,</span> <span class="fu">functor</span>(<span class="dt">_</span><span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> context(<span class="dt">_</span><span class="kw">,</span> <span class="dt">Line</span>))<span class="kw">,</span> <span class="dt">ResultMsg</span>) <span class="kw">:-</span>
string<span class="kw">.</span>append(<span class="ot">",</span><span class="al"> </span><span class="er">at</span><span class="al"> </span><span class="er">line</span><span class="ot">:"</span><span class="kw">,</span>string<span class="al">.</span>int_to_string(<span class="dt">Line</span>)<span class="kw">,</span><span class="dt">TmpString</span>)<span class="kw">,</span>
string<span class="kw">.</span>append(<span class="dt">Msg</span><span class="kw">,</span> <span class="dt">TmpString</span><span class="kw">,</span> <span class="dt">ResultMsg</span>)<span class="kw">.</span>
error_message_with_location(<span class="dt">Msg</span><span class="kw">,</span> variable(<span class="dt">_</span><span class="kw">,</span> context(<span class="dt">_</span><span class="kw">,</span><span class="dt">Line</span>))<span class="kw">,</span> <span class="dt">ResultMsg</span>) <span class="kw">:-</span>
string<span class="kw">.</span>append(<span class="ot">",</span><span class="al"> </span><span class="er">at</span><span class="al"> </span><span class="er">line</span><span class="ot">:"</span><span class="kw">,</span>string<span class="al">.</span>int_to_string(<span class="dt">Line</span>)<span class="kw">,</span><span class="dt">TmpString</span>)<span class="kw">,</span>
string<span class="kw">.</span>append(<span class="dt">Msg</span><span class="kw">,</span> <span class="dt">TmpString</span><span class="kw">,</span> <span class="dt">ResultMsg</span>)<span class="kw">.</span></code></pre>
<p>Now the main predicate for reading the documentation from terms is the following:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred term_to_fractal_config_resolution(
list(term(string))::in<span class="kw">,</span>
maybe_error(fractal_configuration)::out)<span class="kw">.</span>
term_to_fractal_config_resolution(<span class="dt">Terms</span><span class="kw">,</span> <span class="dt">Result</span>) <span class="kw">:-</span>
(if <span class="dt">Terms</span> <span class="kw">=</span> [<span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">image_resolution</span><span class="ot">"</span>)<span class="kw">,</span>
[ <span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">Width</span>)<span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">Height</span>)<span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">_</span>) ]<span class="kw">,</span>
<span class="dt">_</span>)<span class="fu">|</span><span class="dt">Rest1</span>] then
(if <span class="dt">Rest1</span> <span class="kw">=</span> [<span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">top_left</span><span class="ot">"</span>)<span class="kw">,</span>
[ <span class="fu">functor</span>(<span class="dt">float</span>(<span class="dt">LeftX</span>)<span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">float</span>(<span class="dt">TopY</span>)<span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">_</span>) ]<span class="kw">,</span>
<span class="dt">_</span>)<span class="fu">|</span><span class="dt">Rest2</span>] then
(if <span class="dt">Rest2</span> <span class="kw">=</span> [<span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">bottom_right</span><span class="ot">"</span>)<span class="kw">,</span>
[ <span class="fu">functor</span>(<span class="dt">float</span>(<span class="dt">RightX</span>)<span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">float</span>(<span class="dt">BottomY</span>)<span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">_</span>) ]<span class="kw">,</span>
<span class="dt">_</span>)<span class="fu">|</span><span class="dt">Rest3</span>] then
(if <span class="dt">Rest3</span> <span class="kw">=</span> [<span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">formula</span><span class="ot">"</span>)<span class="kw">,</span> [<span class="dt">Term</span>]<span class="kw">,</span> <span class="dt">_</span>)<span class="fu">|</span><span class="dt">Rest4</span>]<span class="kw">,</span> term_to_expression(<span class="dt">Term</span><span class="kw">,</span> ok(<span class="dt">Expr</span>)) then
(if <span class="dt">Rest4</span> <span class="kw">=</span> [<span class="dt">PaletteConfig</span>]<span class="kw">,</span> term_to_palette_config(<span class="dt">PaletteConfig</span><span class="kw">,</span> ok(<span class="dt">Palette</span>)) then
<span class="dt">Result</span> <span class="kw">=</span> ok(config( <span class="kw">{</span> <span class="dt">Width</span><span class="kw">,</span> <span class="dt">Height</span> <span class="kw">},</span>
<span class="kw">{</span> <span class="dt">LeftX</span><span class="kw">,</span> <span class="dt">TopY</span> <span class="kw">},</span>
<span class="kw">{</span> <span class="dt">RightX</span><span class="kw">,</span> <span class="dt">BottomY</span> <span class="kw">},</span>
<span class="dt">Expr</span><span class="kw">,</span>
<span class="dt">Palette</span>
))
else
<span class="dt">Result</span> <span class="kw">=</span> error(<span class="ot">"</span><span class="er">Error</span><span class="al"> </span><span class="er">reading</span><span class="al"> </span><span class="er">palette</span><span class="ot">"</span>)
)
else
<span class="dt">Result</span> <span class="kw">=</span> error(<span class="ot">"</span><span class="er">Error</span><span class="al"> </span><span class="er">reading</span><span class="al"> </span><span class="er">formula</span><span class="ot">"</span>))
else
<span class="dt">Result</span> <span class="kw">=</span> error(<span class="ot">"</span><span class="er">Error</span><span class="al"> </span><span class="er">expecting</span><span class="ot">:</span><span class="al"> </span><span class="er">bottom_right</span><span class="ot">(</span><span class="er">float</span><span class="ot">,</span><span class="er">float</span><span class="ot">)"</span>)
)
else
<span class="dt">Result</span> <span class="kw">=</span> error(<span class="ot">"</span><span class="er">Error</span><span class="al"> </span><span class="er">expecting</span><span class="ot">:</span><span class="al"> </span><span class="er">top_left</span><span class="ot">(</span><span class="er">float</span><span class="ot">,</span><span class="er">float</span><span class="ot">)"</span>)
)
else
<span class="dt">Result</span> <span class="kw">=</span> error(<span class="ot">"</span><span class="er">Error</span><span class="al"> </span><span class="er">expecting</span><span class="ot">:</span><span class="al"> </span><span class="er">image_resolution</span><span class="ot">(</span><span class="er">int</span><span class="ot">,</span><span class="er">int</span><span class="ot">)"</span>)
)<span class="kw">.</span></code></pre>
<p>One improvement opportunity here is to separate this predicate into several parts to avoid this nesting structure.</p>
<p>As shown above our final goal is to create a result of the following type:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> type fractal_configuration --->
config( <span class="kw">{</span> int<span class="kw">,</span> int <span class="kw">},</span> <span class="co">% image resolution</span>
<span class="kw">{</span> <span class="dt">float</span><span class="kw">,</span> <span class="dt">float</span> <span class="kw">},</span> <span class="co">% top left cartesian coordinates</span>
<span class="kw">{</span> <span class="dt">float</span><span class="kw">,</span> <span class="dt">float</span> <span class="kw">},</span> <span class="co">% bottom right cartesian coordinates</span>
expression<span class="kw">,</span> <span class="co">% formula</span>
array(<span class="kw">{</span> int<span class="kw">,</span> int<span class="kw">,</span> int <span class="kw">}</span>))<span class="kw">.</span> <span class="co">% palette</span></code></pre>
<p>This structure provides the necessary information to render the fractal. One special datatype here is <code>expression</code> which is used to store the formula used with the escape time algorithm.</p>
<p>This data type looks like this:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">
<span class="kw">:-</span> type operator ---> times <span class="kw">;</span> plus <span class="kw">;</span> minus <span class="kw">;</span> division<span class="kw">.</span>
<span class="kw">:-</span> type expression --->
literal_num(<span class="dt">float</span>)
<span class="kw">;</span> <span class="dt">var</span>(string)
<span class="kw">;</span> imaginary
<span class="kw">;</span> bin_operation(expression<span class="kw">,</span> operator<span class="kw">,</span> expression)<span class="kw">.</span></code></pre>
<p>Since the <code>term</code> library parser can parse arithmetic expressions, I can write simple code that translates terms to these abstract datatype.</p>
<p>Here's the definition of the predicate that does the translation:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred term_to_expression(term(string)::in<span class="kw">,</span> maybe_error(expression)::out) <span class="dt">is</span> det<span class="kw">.</span>
term_to_expression(<span class="fu">functor</span>(<span class="dt">atom</span>(<span class="dt">AtomStr</span>)<span class="kw">,</span><span class="dt">Ops</span><span class="kw">,</span><span class="dt">_</span>)<span class="kw">,</span> <span class="dt">Expr</span>) <span class="kw">:-</span>
(if (<span class="dt">Ops</span> <span class="kw">=</span> [<span class="dt">Op1</span>,<span class="dt">Op2</span>]<span class="kw">,</span>
op_to_string(<span class="dt">Operator</span><span class="kw">,</span><span class="dt">AtomStr</span>)<span class="kw">,</span>
term_to_expression(<span class="dt">Op1</span><span class="kw">,</span> ok(<span class="dt">Op1Expr</span>))<span class="kw">,</span>
term_to_expression(<span class="dt">Op2</span><span class="kw">,</span> ok(<span class="dt">Op2Expr</span>))) then
<span class="dt">Expr</span> <span class="kw">=</span> ok(bin_operation(<span class="dt">Op1Expr</span><span class="kw">,</span> <span class="dt">Operator</span><span class="kw">,</span> <span class="dt">Op2Expr</span>))
else
(if <span class="dt">Ops</span> <span class="kw">=</span> [] then
(if <span class="dt">AtomStr</span> <span class="kw">=</span> <span class="ot">"</span><span class="er">i</span><span class="ot">"</span> then
<span class="dt">Expr</span> <span class="kw">=</span> ok(imaginary)
else
<span class="dt">Expr</span> <span class="kw">=</span> ok(<span class="dt">var</span>(<span class="dt">AtomStr</span>)))
else
<span class="dt">Expr</span> <span class="kw">=</span> error(<span class="ot">"</span><span class="er">Error</span><span class="ot">"</span>))
)<span class="kw">.</span>
term_to_expression(<span class="fu">functor</span>(<span class="dt">float</span>(<span class="dt">X</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)<span class="kw">,</span> <span class="dt">Expr</span>) <span class="kw">:-</span>
<span class="dt">Expr</span> <span class="kw">=</span> ok(literal_num(<span class="dt">X</span>))<span class="kw">.</span>
term_to_expression(<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">X</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)<span class="kw">,</span> <span class="dt">Expr</span>) <span class="kw">:-</span>
<span class="dt">Expr</span> <span class="kw">=</span> ok(literal_num(<span class="dt">float</span>(<span class="dt">X</span>)))<span class="kw">.</span>
term_to_expression(<span class="fu">functor</span>(big_integer(<span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)<span class="kw">,</span> error(<span class="ot">"</span><span class="er">Error</span><span class="ot">"</span>))<span class="kw">.</span>
term_to_expression(<span class="fu">functor</span>(string(<span class="dt">_</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)<span class="kw">,</span> error(<span class="ot">"</span><span class="er">Error</span><span class="ot">"</span>))<span class="kw">.</span>
term_to_expression(<span class="fu">functor</span>(implementation_defined(<span class="dt">_</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)<span class="kw">,</span> error(<span class="ot">"</span><span class="er">Error</span><span class="ot">"</span>))<span class="kw">.</span>
term_to_expression(variable(<span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)<span class="kw">,</span> error(<span class="ot">"</span><span class="er">Error</span><span class="ot">"</span>))<span class="kw">.</span></code></pre>
<h2 id="reading-the-palette">Reading the palette</h2>
<p>The palette used by the escape time algorithm is just an array of colors. The configuration file allows two kinds of elements for specifying the colors :</p>
<ul>
<li><code>single(RED, GREEN, BLUE)</code> a single color for the current entry</li>
<li><code>range(from(RED1, GREEN1, BLUE1), to(RED1, GREEN2, BLUE2), COUNT)</code> to create a range of colors of <code>COUNT</code> steps between the two colors.</li>
</ul>
<p>The following code reads the palette configuration:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred terms_to_palette(
list(term(string))::in<span class="kw">,</span>
list(<span class="kw">{</span>int<span class="kw">,</span> int<span class="kw">,</span> int<span class="kw">}</span>)::in<span class="kw">,</span>
maybe_error(array(<span class="kw">{</span>int<span class="kw">,</span>int<span class="kw">,</span>int<span class="kw">}</span>))::out) <span class="dt">is</span> det<span class="kw">.</span>
terms_to_palette([]<span class="kw">,</span><span class="dt">TmpResult</span><span class="kw">,</span> ok(<span class="dt">ResultArray</span>)) <span class="kw">:-</span>
list<span class="kw">.</span>reverse(<span class="dt">TmpResult</span><span class="kw">,</span> <span class="dt">ReversedList</span>)<span class="kw">,</span>
array<span class="kw">.</span>from_list(<span class="dt">ReversedList</span><span class="kw">,</span> <span class="dt">ResultArray</span>)<span class="kw">.</span>
terms_to_palette([<span class="dt">Term</span><span class="fu">|</span><span class="dt">Rest</span>]<span class="kw">,</span><span class="dt">TmpResult</span><span class="kw">,</span><span class="dt">Result</span>) <span class="kw">:-</span>
(if <span class="dt">Term</span> <span class="kw">=</span> <span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">single</span><span class="ot">"</span>)<span class="kw">,</span>
[<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">R</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">G</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">B</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)]<span class="kw">,</span>
<span class="dt">_</span>) then
terms_to_palette(<span class="dt">Rest</span><span class="kw">,</span> [{<span class="dt">R</span><span class="kw">,</span><span class="dt">G</span><span class="kw">,</span><span class="dt">B</span><span class="kw">}</span><span class="fu">|</span><span class="dt">TmpResult</span>]<span class="kw">,</span> <span class="dt">Result</span>)
else
(if <span class="dt">Term</span> <span class="kw">=</span> <span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">range</span><span class="ot">"</span>)<span class="kw">,</span>[
<span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">from</span><span class="ot">"</span>)<span class="kw">,</span>
[<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">R1</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">G1</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">B1</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)]<span class="kw">,</span><span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">atom</span>(<span class="ot">"</span><span class="er">to</span><span class="ot">"</span>)<span class="kw">,</span>
[<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">R2</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">G2</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">B2</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)]<span class="kw">,</span><span class="dt">_</span>),
<span class="fu">functor</span>(<span class="dt">integer</span>(<span class="dt">Count</span>)<span class="kw">,</span><span class="dt">_</span><span class="kw">,</span><span class="dt">_</span>)
]<span class="kw">,</span> <span class="dt">_</span>) then
int_interpolate_funcs(<span class="dt">R1</span><span class="kw">,</span> <span class="dt">R2</span><span class="kw">,</span> <span class="dv">1</span><span class="kw">,</span> <span class="dt">Count</span><span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">R2RFunc</span>)<span class="kw">,</span>
int_interpolate_funcs(<span class="dt">G1</span><span class="kw">,</span> <span class="dt">G2</span><span class="kw">,</span> <span class="dv">1</span><span class="kw">,</span> <span class="dt">Count</span><span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">G2GFunc</span>)<span class="kw">,</span>
int_interpolate_funcs(<span class="dt">B1</span><span class="kw">,</span> <span class="dt">B2</span><span class="kw">,</span> <span class="dv">1</span><span class="kw">,</span> <span class="dt">Count</span><span class="kw">,</span> <span class="dt">_</span><span class="kw">,</span> <span class="dt">B2BFunc</span>)<span class="kw">,</span>
gen_colors_for_range(<span class="dv">1</span><span class="kw">,</span> <span class="dt">Count</span><span class="kw">,</span> <span class="dt">R2RFunc</span><span class="kw">,</span> <span class="dt">G2GFunc</span><span class="kw">,</span> <span class="dt">B2BFunc</span><span class="kw">,</span> []<span class="kw">,</span> <span class="dt">RangeList</span>)<span class="kw">,</span>
list<span class="al">.</span>append(<span class="dt">TmpResult</span><span class="kw">,</span> <span class="dt">RangeList</span><span class="kw">,</span> <span class="dt">NewTmpResult</span>)<span class="kw">,</span>
terms_to_palette(<span class="dt">Rest</span><span class="kw">,</span> <span class="dt">NewTmpResult</span><span class="kw">,</span> <span class="dt">Result</span>)
else
<span class="dt">Result</span> <span class="kw">=</span> error(<span class="ot">"</span><span class="er">Problem</span><span class="al"> </span><span class="er">reading</span><span class="al"> </span><span class="er">palette</span><span class="al"> </span><span class="er">configuration</span><span class="ot">"</span>))
)<span class="kw">.</span></code></pre>
<p>Given the following configuration:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">...
palette(
range(from(<span class="dv">20</span><span class="kw">,</span><span class="dv">244</span><span class="kw">,</span><span class="dv">100</span>)<span class="kw">,</span> to(<span class="dv">200</span><span class="kw">,</span><span class="dv">0</span><span class="kw">,</span><span class="dv">56</span>)<span class="kw">,</span> <span class="dv">15</span>)<span class="kw">,</span>
single(<span class="dv">0</span><span class="kw">,</span><span class="dv">0</span><span class="kw">,</span><span class="dv">0</span>)
...</code></pre>
<p>We can generate the following palette:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="dv">1</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">20</span><span class="kw">,</span> <span class="dv">244</span><span class="kw">,</span> <span class="dv">100</span><span class="kw">}</span>
<span class="dv">2</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">32</span><span class="kw">,</span> <span class="dv">226</span><span class="kw">,</span> <span class="dv">96</span><span class="kw">}</span>
<span class="dv">3</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">45</span><span class="kw">,</span> <span class="dv">209</span><span class="kw">,</span> <span class="dv">93</span><span class="kw">}</span>
<span class="dv">4</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">58</span><span class="kw">,</span> <span class="dv">191</span><span class="kw">,</span> <span class="dv">90</span><span class="kw">}</span>
<span class="dv">5</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">71</span><span class="kw">,</span> <span class="dv">174</span><span class="kw">,</span> <span class="dv">87</span><span class="kw">}</span>
<span class="dv">6</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">84</span><span class="kw">,</span> <span class="dv">156</span><span class="kw">,</span> <span class="dv">84</span><span class="kw">}</span>
<span class="dv">7</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">97</span><span class="kw">,</span> <span class="dv">139</span><span class="kw">,</span> <span class="dv">81</span><span class="kw">}</span>
<span class="dv">8</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">110</span><span class="kw">,</span> <span class="dv">122</span><span class="kw">,</span> <span class="dv">78</span><span class="kw">}</span>
<span class="dv">9</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">122</span><span class="kw">,</span> <span class="dv">104</span><span class="kw">,</span> <span class="dv">74</span><span class="kw">}</span>
<span class="dv">10</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">135</span><span class="kw">,</span> <span class="dv">87</span><span class="kw">,</span> <span class="dv">71</span><span class="kw">}</span>
<span class="dv">11</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">148</span><span class="kw">,</span> <span class="dv">69</span><span class="kw">,</span> <span class="dv">68</span><span class="kw">}</span>
<span class="dv">12</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">161</span><span class="kw">,</span> <span class="dv">52</span><span class="kw">,</span> <span class="dv">65</span><span class="kw">}</span>
<span class="dv">13</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">174</span><span class="kw">,</span> <span class="dv">34</span><span class="kw">,</span> <span class="dv">62</span><span class="kw">}</span>
<span class="dv">14</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">187</span><span class="kw">,</span> <span class="dv">17</span><span class="kw">,</span> <span class="dv">59</span><span class="kw">}</span>
<span class="dv">15</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">200</span><span class="kw">,</span> <span class="dv">0</span><span class="kw">,</span> <span class="dv">56</span><span class="kw">}</span>
<span class="dv">16</span><span class="kw">.</span> <span class="kw">{</span><span class="dv">0</span><span class="kw">,</span> <span class="dv">0</span><span class="kw">,</span> <span class="dv">0</span><span class="kw">}</span></code></pre>
Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-39055067347130236262016-04-10T19:44:00.001-06:002016-04-11T12:39:03.766-06:00Determinism categories in Mercury
<p>When you define a predicate in <a href="https://mercurylang.org/">Mercury</a>, you have to specify if it can fail or succeed more than once. This is called a determinism category.</p>
<p>The category is specified as part of a predicate (or function) declaration. For example:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred get_partitions(
list(int)::in<span class="kw">,</span>
list(list(int))::out) <span class="dt">is</span> multi<span class="kw">.</span></code></pre>
<p>The <code>is multi</code> section says that this predicate belongs to the <code>multi</code> category.</p>
<p>The following tables describe the main determinism categories.</p>
<p>Maximum number of solutions:</p>
<table style="border-collapse: collapse;border-style: solid" >
<thead>
<tr style="border-style: solid" class="header">
<th style="border-style: solid;width: 60px" align="left">Mode</th>
<th style="border-style: solid;width: 30px" align="center">1</th>
<th style="border-style: solid;width: 30px" align="center">> 1</th>
</tr>
</thead>
<tbody>
<tr style="border-style: solid" class="odd">
<td style="border-style: solid" align="left">det</td>
<td style="border-style: solid" align="center">x</td>
<td style="border-style: solid" align="left"></td>
</tr>
<tr style="border-style: solid" class="even">
<td style="border-style: solid" align="left">multi</td>
<td style="border-style: solid" align="left"></td>
<td style="border-style: solid" align="center">x</td>
</tr>
<tr style="border-style: solid" class="odd">
<td style="border-style: solid" align="left">semidet</td>
<td style="border-style: solid" align="center">x</td>
<td style="border-style: solid" align="left"></td>
</tr>
<tr style="border-style: solid" class="even">
<td style="border-style: solid" align="left">nondet</td>
<td style="border-style: solid" align="left"></td>
<td style="border-style: solid" align="center">x</td>
</tr>
</tbody>
</table>
<p>Failure:</p>
<table style="border-style: solid">
<thead>
<tr class="header">
<th align="left">Mode</th>
<th align="left">Can fail?</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td align="left">det</td>
<td align="center">no</td>
</tr>
<tr class="even">
<td align="left">multi</td>
<td align="center">no</td>
</tr>
<tr class="odd">
<td align="left">semidet</td>
<td align="center">yes</td>
</tr>
<tr class="even">
<td align="left">nondet</td>
<td align="center">yes</td>
</tr>
</tbody>
</table>
<p>(Based on information from <a href="https://mercurylang.org/information/doc-latest/mercury_ref/Determinism-categories.html#Determinism-categories">https://mercurylang.org/information/doc-latest/mercury_ref/Determinism-categories.html#Determinism-categories</a> ).</p>
<p>Other categories exist : <code>erroneous</code> , <code>failure</code>, <code>cc_mult</code> and <code>cc_nondet</code>. These are not discussed in this post, see the link above for more info.</p>
<p>Now a some of each category:</p>
<h2 id="det">det</h2>
<p>These predicates in must always succeed . For example:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred list_length(list(int)::in<span class="kw">,</span> int::out) <span class="dt">is</span> det<span class="kw">.</span>
list_length([<span class="dt">_</span><span class="fu">|</span><span class="dt">R</span>]<span class="kw">,</span> <span class="dt">Length</span>) <span class="kw">:-</span>
list_length(<span class="dt">R</span><span class="kw">,</span><span class="dt">SubListLength</span>)<span class="kw">,</span>
<span class="dt">Length</span> <span class="kw">=</span> <span class="dt">SubListLength</span> <span class="fu">+</span> <span class="dv">1</span><span class="kw">.</span>
list_length([]<span class="kw">,</span> <span class="dv">0</span>)<span class="kw">.</span></code></pre>
<p>In this case this predicate is going to calculate the size of a list. It should not fail.</p>
<h2 id="semidet">semidet</h2>
<p>These predicates can either succeed or fail. For example the following code shows the definition of a <code>first_even_number</code> predicate.</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred first_even_number(list(int)::in<span class="kw">,</span> int::out)
<span class="dt">is</span> semidet<span class="kw">.</span>
first_even_number([<span class="dt">X</span><span class="fu">|</span><span class="dt">R</span>]<span class="kw">,</span> <span class="dt">N</span>) <span class="kw">:-</span>
(if (<span class="dt">X</span> <span class="fu">mod</span> <span class="dv">2</span>) <span class="kw">=</span> <span class="dv">0</span> then
<span class="dt">N</span> <span class="kw">=</span> <span class="dt">X</span>
else
first_even_number(<span class="dt">R</span><span class="kw">,</span><span class="dt">N</span>))<span class="kw">.</span></code></pre>
<p>Notice that this predicate can fail for a couple of reasons:</p>
<ul>
<li>The input list may be empty</li>
<li>The input list may not contain an even number</li>
</ul>
<p>I think it's pretty nice that you these situations will be handled without explicitly writing code for it.</p>
<p>A use of this predicate looks like this:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">...
(if first_even_number([<span class="dv">3</span>,<span class="dv">41</span>,<span class="dv">5</span>,<span class="dv">32</span>,<span class="dv">342</span>]<span class="kw">,</span> <span class="dt">EvenNumber</span>) then
io<span class="al">.</span>write_string(<span class="ot">"</span><span class="er">First</span><span class="al"> </span><span class="er">even</span><span class="al"> </span><span class="er">number</span><span class="ot">:</span><span class="al"> </span><span class="ot">"</span><span class="kw">,</span> <span class="kw">!</span><span class="dt">IO</span>)<span class="kw">,</span>
io<span class="al">.</span><span class="fu">write</span>(<span class="dt">EvenNumber</span><span class="kw">,</span> <span class="kw">!</span><span class="dt">IO</span>)
else
io<span class="al">.</span><span class="fu">write</span>(<span class="ot">"</span><span class="er">Not</span><span class="al"> </span><span class="er">even</span><span class="al"> </span><span class="er">number</span><span class="al"> </span><span class="er">found</span><span class="ot">"</span><span class="kw">,</span> <span class="kw">!</span><span class="dt">IO</span>)
)<span class="kw">.</span></code></pre>
<p>Another think that's pretty nice about Mercury is that, the compiler is going to detect inconsistent determinism annotations. For example, if I change the declaration of the predicate to:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred first_even_number(list(int)::in<span class="kw">,</span> int::out)
<span class="dt">is</span> det<span class="kw">.</span></code></pre>
<p>The compiler is going to fail with the following error:</p>
<pre class="sourceCode bash"><code class="sourceCode bash"><span class="kw">testsolutions.m</span>:093: In <span class="kw">`first_even_number</span><span class="st">'(in, out):</span>
<span class="st">testsolutions.m:093: error: determinism declaration not satisfied.</span>
<span class="st">testsolutions.m:093: Declared `det'</span>, inferred <span class="kw">`</span>semidet<span class="st">'.</span></code></pre>
<h2 id="multi">multi</h2>
<p>The <code>multi</code> category is used for predicates that succeed in multiple ways. At least one solution exists.</p>
<p>For example the following predicate is used to get a pair of lists that, when concatenated together, result in the input list (ex. [1,2,3] result in { [1],[2,3] }) .</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred partitions(list(int)::in<span class="kw">,</span>
<span class="kw">{</span>list(int)<span class="kw">,</span> list(int)<span class="kw">}</span>::out) <span class="dt">is</span> multi<span class="kw">.</span>
partitions(<span class="dt">InputList</span><span class="kw">,</span><span class="dt">Output</span>) <span class="kw">:-</span>
(
<span class="dt">Output</span> <span class="kw">=</span> <span class="kw">{</span>[] <span class="kw">,</span> <span class="dt">InputList</span><span class="kw">}</span>
<span class="kw">;</span>
<span class="dt">InputList</span> <span class="kw">=</span> [<span class="dt">A</span><span class="fu">|</span><span class="dt">TMP</span>]<span class="kw">,</span>
partitions(<span class="dt">TMP</span><span class="kw">,{</span><span class="dt">R</span><span class="kw">,</span><span class="dt">B</span><span class="kw">}</span>)<span class="kw">,</span>
<span class="dt">Output</span> <span class="kw">=</span> <span class="kw">{</span> [<span class="dt">A</span><span class="fu">|</span><span class="dt">R</span>]<span class="kw">,</span> <span class="dt">B</span> <span class="kw">}</span>
)<span class="kw">.</span></code></pre>
<p>This predicate is <code>multi</code> because we can get several different pairs of lists that from an input list. For example:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">main(<span class="kw">!</span><span class="dt">IO</span>) <span class="kw">:-</span>
solutions(partitions([<span class="dv">513</span>,<span class="dv">242</span>,<span class="dv">355</span>,<span class="dv">4</span>])<span class="kw">,</span><span class="dt">Pairs1</span>)<span class="kw">,</span>
io<span class="kw">.</span><span class="fu">write</span>(<span class="dt">Pairs1</span><span class="kw">,!</span><span class="dt">IO</span>)<span class="kw">,</span>
io<span class="kw">.</span><span class="fu">nl</span>(<span class="kw">!</span><span class="dt">IO</span>)<span class="kw">.</span></code></pre>
<p>Running this program result in the following output:</p>
<pre class="sourceCode bash"><code class="sourceCode bash">[{[], [<span class="kw">513</span>, 242, 355, 4]}, {[<span class="kw">513</span>], [242, 355, 4]}, {[<span class="kw">513</span>, 242], [355, 4]}, {[<span class="kw">513</span>, 242, 355], [4]}, {[<span class="kw">513</span>, 242, 355, 4], []}]</code></pre>
<p>In the case we use the <code>solutions/2</code> Mercury predicate to get a list from the generated solutions.</p>
<p>It's important to note that <code>multi</code> predicates must not fail.</p>
<h2 id="nondet">nondet</h2>
<p>Finally the <code>nondet</code> category is used for predicates that result on 0 or many solutions.</p>
<p>For example the following predicate result on an even number that is part of the input list.</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog"><span class="kw">:-</span> pred even_member(list(int)::in<span class="kw">,</span> int::out) <span class="dt">is</span> nondet<span class="kw">.</span>
even_member([<span class="dt">X</span><span class="fu">|</span><span class="dt">_</span>]<span class="kw">,</span> <span class="dt">X</span>) <span class="kw">:-</span>
(<span class="dt">X</span> <span class="fu">mod</span> <span class="dv">2</span>) <span class="kw">=</span> <span class="dv">0</span><span class="kw">.</span>
even_member([<span class="dt">_</span><span class="fu">|</span><span class="dt">Rest</span>]<span class="kw">,</span> <span class="dt">X</span>) <span class="kw">:-</span>
even_member(<span class="dt">Rest</span><span class="kw">,</span><span class="dt">X</span>)<span class="kw">.</span></code></pre>
<p>This predicate is <code>nondet</code> because :</p>
<ul>
<li>The list may be empty</li>
<li>It may not contain an even number</li>
</ul>
<p>Here's an example of how to use it:</p>
<pre class="sourceCode prolog"><code class="sourceCode prolog">main(<span class="kw">!</span><span class="dt">IO</span>) <span class="kw">:-</span>
solutions(even_member([<span class="dv">513</span>,<span class="dv">242</span>,<span class="dv">18</span>,<span class="dv">355</span>,<span class="dv">12</span>,<span class="dv">4</span>])<span class="kw">,</span><span class="dt">Pairs1</span>)<span class="kw">,</span>
io<span class="kw">.</span><span class="fu">write</span>(<span class="dt">Pairs1</span><span class="kw">,!</span><span class="dt">IO</span>)<span class="kw">.</span></code></pre>
<p>Running this program result in the following output:</p>
<pre class="sourceCode bash"><code class="sourceCode bash">[<span class="kw">4</span>, 12, 18, 242]</code></pre>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-78529842986433177882016-02-28T20:36:00.000-06:002016-02-28T20:36:24.830-06:00A couple of quick notes on Mercury #1<p>I'm trying to learn about <a href="https://mercurylang.org/">Mercury programming language</a>. Here's a quick list of things I learned recently about it.</p>
<h3>Getting a Windows version of the Mercury compiler</h3>
<p>I was able to get a version of the Mercury compiler by downloading a "Release of the day" version from here: <a href="http://dl.mercurylang.org/index.html">http://dl.mercurylang.org/index.html</a>.</p>
<p>I just followed the instructions from INSTALL file. The only requirement is to have a Cygwin version installed.</p>
<h3>Operations are associated with a data type</h3>
<p>For example the predicate for performing an operation N times is defined in the <code>int</code> module (<code>int.fold_up, int_fold_down</code>).</p>
<h3>Predicates can be partially applied</h3>
<p>Mercury supports a mechanism similar to <i>currying</i> in other languages.</p>
<p>For example, in the following invocation to <code>int.fold_up</code> we're not specifying values or variables for the last three arguments(these are resolved by the application inside <code>int.fold_up</code>):</p>
<pre><code>
:- pred write_pixel_data(
io.binary_output_stream::in,
array(int)::in,
int::in, % width
int::in, % height
int::in, % padding
int::in, % idx
io::di, io::uo) is det.
.
.
.
int.fold_up(write_pixel_data(Stream,
ImgData,
Width * 3,
Height,
(RowWidth - (Width * 3))),0,(RowWidth*Height) - 1,!IO)
</code></pre>
<h3>Bitwise operators look nice!</h3>
<p>For example bitwise "and" look like:</p>
<pre><code> io.write_byte(Stream, (IntValue >> 8) /\ 0xFF,!IO), </code></pre>
<p> Code for this post can be found <a href="https://github.com/ldfallas/graphicswithmercury/">here</a></p>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.comtag:blogger.com,1999:blog-8273201239805322932.post-7681993794678836702015-10-18T20:49:00.000-06:002015-10-18T20:49:06.624-06:00Using traits to reuse code in Pharo<p>While working on a small Tetris-like clone in <a href="http://pharo.org/">Pharo</a>, I found an opportunity to reuse some code.</p>
<p>It's common for Tetris implementations to show a small preview of the tetrimino that comes next. Here's how it looks:</p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0RsKe4lnGHCE2dbyRud3stKnKkXfrDAP5I3a7vNiI0XRpugexVhr3F_zCaQiTqrqIxSELIQTV18LGVbLypMHPB4OY9ovJ10jvfBh1pAQ_Q8CFMnJ81FO2fitmMyJsnDc2y9hfaJKgbksm/s1600/previewtetrimino.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj0RsKe4lnGHCE2dbyRud3stKnKkXfrDAP5I3a7vNiI0XRpugexVhr3F_zCaQiTqrqIxSELIQTV18LGVbLypMHPB4OY9ovJ10jvfBh1pAQ_Q8CFMnJ81FO2fitmMyJsnDc2y9hfaJKgbksm/s1600/previewtetrimino.jpg" /></a></div>
<p>I wanted to create a separate Morphic component to show this preview. But I didn't want to duplicate the code required to paint the tetriminos. Sharing this code will allow me to have just one place to change the way tetriminos look. Also I didn't want to create a base class on top of both the game and the preview Morphs.</p>
<p>While reading about Pharo and Squeak I found that it supports <a href="https://en.wikipedia.org/wiki/Trait_(computer_programming)">Traits</a>. The <a href="http://pharo.gemtalksystems.com/book/LanguageAndLibraries/Traits/">Pharo collaborActive book</a> provides a nice explanation of how to use traits. Here's a quick definition from this document:</p>
<blockquote>... traits are just groups of methods that can be reused in different classes. </blockquote>
<p>This is exactly what I needed for reusing the tetrimino matrix drawing code. The following code shows the code defined in the game matrix Morph component.</p>
<pre class="smalltalk"><code>drawOn: canvas
"Draws the current game state"
|rows columns currentValue rectangle currentColor cellWidth cellHeight|
rows := gameState size x.
columns := gameState size y.
super drawOn: canvas.
cellWidth := ((self width) / columns) asFloat truncated.
cellHeight := ((self height) / rows) asFloat truncated.
1 to: rows do: [ :row |
1 to: columns do: [ :column|
currentValue := gameState at: row at: column .
currentValue ~= 0 ifTrue: [
currentColor := (colors at: currentValue).
rectangle := Rectangle left: (self bounds left)
canvas frameAndFillRectangle: rectangle
fillColor: currentColor
borderWidth: 1
borderColor: (Color white).
]
]
].</code></pre>
<p>Moving this code to a trait implies that I have to pass all instance state variables as an argument of the draw method.</p>
<p>The definition of the trait looks like this:</p>
<pre class="smalltalk"><code>Trait named: #TTetriminoDrawing
uses: {}
category: 'TryTrix'</code></pre>
<p>And the definition of the method inside this trait looks like this:</p>
<pre class="smalltalk"><code>drawGameStateOn: canvas
width: areaWidth height: areaHeight
columns: columns rows: rows
morphBounds: morphBounds
matrix: contentMatrix
colors: colorPalette
"Draw the contents of the specified matrix on the given canvas"
|cellWidth cellHeight currentValue currentColor rectangle|
cellWidth := (areaWidth / columns) asFloat truncated.
cellHeight := (areaHeight / rows) asFloat truncated.
1 to: rows do: [ :row |
1 to: columns do: [ :column|
currentValue := contentMatrix at: row at: column .
currentValue ~= 0 ifTrue: [
currentColor := (colorPalette at: currentValue).
rectangle := Rectangle left: (morphBounds left) + ((column - 1)*cellWidth)
right: (morphBounds left) + ((column - 1)*cellWidth) + cellWidth
top: (morphBounds top) + ((row - 1)*cellHeight )
bottom: (morphBounds top) + ((row - 1)*cellHeight ) + cellHeight.
canvas frameAndFillRectangle: rectangle
fillColor: currentColor
borderWidth: 1
borderColor: (Color white).
]
]
].</code></pre>
<p>Now I can use this trait inside each morph definition:</p>
<pre class="smalltalk"><code>Morph subclass: #TryTrixMorph
uses: TTetriminoDrawing
instanceVariableNames: 'gameState colors eventHandlers'
classVariableNames: ''
category: 'TryTrix'
Morph subclass: #TetriminoPreview
uses: TTetriminoDrawing
instanceVariableNames: 'matrix'
classVariableNames: ''
category: 'TryTrix'</code></pre>
<p>This code can be found in <a href="https://github.com/ldfallas/TryTrix">here</a>.</p>Luis Diego Fallashttp://www.blogger.com/profile/01461500891939895224noreply@blogger.com