On Turing Completeness of LESS

Introduction

Continuing with my earlier post "LESS is More" about how different it is to write a simple Fibonacci program in LESS, I wanted to really understand the main differences of LESS from more general purpose programming languages like Java, C++ etc. Also, whether this language is as powerful as these other general purpose languages, or in other words, is it Turing complete? There are some key differences which become apparent after some use of this language. For example,

1. One cannot define methods which return a value, instead, variables defined by methods become available to calling method. These variables can then be used by callee to return values to caller.
2. A variable in a given scope can hold only one value. This is similar to some functional languages where all variables are immutable. This also applies to variables which become available from callee. Since, user defined methods also return value via variables, a side effect of this limitation is that one cannot call a user defined function more than once with different arguments. If you did that, then there would be no way to access value of returned variable from second call. This is because as value from second call will not be able to override it.

Apart from above language supports recursion, which makes it possible to write infinite loops. Ability to write infinite loops is one of the differentiators of turing complete languages. As explained by Douglas Hofstadter that a language without ability to express non terminating loops is definitely not Turing complete as programs written in such a language are always halting and therefore do not suffer from halting problem, which is one of the characteristic of turing complete languages.

But can we still say that language with given limitations turing complete? In order to prove this we would have to emulate either turing machine or any other equivalent model of computation using this language. One such model is Rule 110. Rule 110 is a cellular automaton, it has been proven that it is turing complete, so if we can implement Rule 110 in LESS we can be sure that LESS is also at least as powerful as a turing machine.

But what does it mean to simulate Rule 110 cellular automata(RCA from here on)? Simulating Rule 110 means that we would have to define a function is LESS which when given an initial configuration of RCA and a number, representing number of generations or steps, will give final state of RCA after given number of generations of RCA.

Input Encoding and data structure

Before we begin, we need to decide encoding for the state of RCA. For RCA we just need some way to store a sequence of zeros and ones. We can use string to store zeros and once but it seems that there is no way to access individual characters of string in LESS. Other option seems to be lists but it seems there is no way to modify or even append elements to a given list. For example, if we try to append an element to a given list, it actually creates a new list such that first element is the element we appended but the second element points to entire list and length of this new list comes out to be two, no matter how large the original list was. So, it seems there is no way to manipulate/access a sequence of zero and ones. But all hope is not lost and it seems we can create a new data structure using these native lists. This new data structure is based on the idea that when we create a native list of two variables, each of which can be a list, it creates a new list of length two such that each element points to two variables. We can use this to create LISP like lists, in which list consists of pair objects, each object has two elements (first and second), first element points to the element in the list, and second element points to remaining list. There is also a null element, the second element of last pair points to this null element.

Some conventions

For our purpose we can chose "-1" as the null element since we have to store only zeros and ones in the list. Since this list is not a native data structure we would have to write certain methods for working with this list. Before we start writing code for these methods there is a minute detail, a convention, that we are going to follow in this post. As there is no way to return values from functions in LESS and value has to be returned as a variable, we can follow a naming convention for these variables that are used to return values. So, in this post we are going to follow this convention that a function named "foo" will return its result in a variable named "foo_res", similarly, a function named "foo_bar" will return its result in "foo_bar_res" variable.

With these conventions lets write our first method. This method converts native space separated list of zeros and ones to our LISP like lists.

.define_list(@nlist){
  .-(@i:length(@nlist),@acc:-1) when (@i > 0){
    .-((@i - 1),extract(@nlist, @i) @acc);
  }
  .-(0,@acc){
    @define_list_res: @acc;
  }
  .-;
}

This method takes @nlist variable as an argument which is a native LESS list. It then defines a recursive routine "-". This routine is used to iterate over @nlist. There are two definitions of "-" method. First one takes first argument @i which is position in @nlist that is to be processed by this call, second argument @acc is an accumulator, it is used to build our list. This definition also has a guard condition such that it will be executed only when @i is greater than zero. This definition recursively calls "-". It passes a decremented value of @i and in the second argument we use "extract" built-in function to take value of @nlist at @i position and combine it with @acc. This expression creates a new pair, such that first element is the value read from @nlist and second element points to whatever is in the @acc. The second definition of "-" is executed only when first argument is "0", this happens when we have already traversed all of the list. At this point @acc contains our list, we simply create variable "define_list_res" and set its value equal to @acc. This variable here is being used to return the value. Finally we call the "-" with no arguments. By default value of its first argument will be set to length of @nlist and value @acc will be set to -1. To see this method in action, add following lines to the script and then run it using LESS

.print_result {
  .define_list(0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0);
  result_length:length(@define_list_res);
  result:@define_list_res;
}

This should print our created list. Our list is a nested data structure but LESS prints it as flat list. This can be confirmed as length of the list is printed as 2. This is because structure of our list is composed of multiple lists, each of length two. Something like [0, [0 , [0 ,[0 , [1 , [1 , -1] ] ] ] ] ]

Output

.print_result {
  result_length: 2;
  result: 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 -1;
}

Utility Functions

Now lets define few more functions for working with these lists.

1. list_len function to calculate length of the list.
2. tail_list to find tail of the list after skipping given number of elements
3. reverse_list function to reverse the input list

.tail_list(@my_list,@num_skips) when (@num_skips = 0){
   @tail_list_res:@my_list;
}
.tail_list(@my_list,@num_skips) when (@num_skips > 0){
   .tail_list(extract(@my_list,2),@num_skips - 1);
}
.list_len(@my_list){
  .list_len_loop(@my_list,@len_acc:0) when (@my_list = -1){
    @list_len_res:@len_acc;
  }
  .list_len_loop(@my_list,@len_acc:0) when (length(@my_list) > 1) {
     .list_len_loop(extract(@my_list,2),@len_acc + 1);
  }
  .list_len_loop(@my_list);
}
.reverse_list(@rev_list:-1,@acc1:-1) when (@rev_list = -1){
   @reverse_list_res:@acc1;
}
.reverse_list(@rev_list:-1,@acc1:-1) when (length(@rev_list) > 1) {
   .reverse_list(extract(@rev_list,2),extract(@rev_list,1) @acc1);
}

I will not go into detail to explain these methods. All these methods use recursion to iterate of input list. tail_list function probably deserves some explanation in that, it skips @num_skips number of elements in the list and returns the remaining list. In previous section when we used native "length" method to find length of our list, it returned 2. Now we can use this new method to find actual length. Replace .print_result block with following and again run using LESS compiler

.print_result {
  .define_list(0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0);
  .list_len(@define_list_res);
  result_length:@list_len_res;
  result:@define_list_res;
}

It should now print following output

.print_result {
  result_length: 26;
  result: 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 -1;
}

Now that we have basic set of functions done, we can start writing actual program. For Rule 110 we first need to write a function which given state of then cell and its neighbouring cells, outputs final value of the cell after one generation. Such a function can be return as follows.

.rule_110(0,0,0){
  @rule_110_res:0;
}
.rule_110(0,0,1){
  @rule_110_res:1;
}
.rule_110(0,1,0){
  @rule_110_res:1;
}
.rule_110(0,1,1){
  @rule_110_res:1;
}
.rule_110(1,0,0){
  @rule_110_res:0;
}
.rule_110(1,0,1){
  @rule_110_res:1;
}
.rule_110(1,1,0){
  @rule_110_res:1;
}
.rule_110(1,1,1){
  @rule_110_res:0;
}

This is a simple function, a call to .rule_110(1,1,0) will return 1 as value of @rule_110_res variable and call to .rule_110(1,0,0) will return 0.

Calculating one generation of cellular automaton

Now lets write the function which given state of the machine, outputs state after next generation. Our cellular automaton consists of a sequence of cells. Each cell can be in either of the two states, zero or one. Therefore, state of the machine is represented as a sequence of zeros and ones.

.apply_rule110(@machine_state) {
  .list_len(@machine_state);
  @machine_state_len:@list_len_res;
  .apply_rule110_loop(@pos:1,@acc:-1) when (@pos = 1) {
      .rule_110(0,extract(@machine_state,1),extract(extract(@machine_state,2),1));
      .apply_rule110_loop(@pos + 1,@rule_110_res @acc);
  }
  .apply_rule110_loop(@pos:1,@acc:-1) when (@pos = @machine_state_len){
     .tail_list(@machine_state,@machine_state_len - 2);
     .rule_110(extract(@tail_list_res,1),extract(extract(@tail_list_res,2),1),0);
     @apply_rule110_loop_res:@rule_110_res @acc;
  }
  .apply_rule110_loop(@pos:1, @acc:-1) when (@pos > 1) and (@pos < @machine_state_len){
     .tail_list(@machine_state,@pos - 2);
     .rule_110(extract(@tail_list_res,1),extract(extract(@tail_list_res,2),1),extract(extract(extract(@tail_list_res,2),2),1));
     .apply_rule110_loop(@pos + 1,@rule_110_res @acc);
  }
  .apply_rule110_loop;
  .reverse_list(@apply_rule110_loop_res);
  @apply_rule110_res:@reverse_list_res;
}

In short this function takes as input the current state of the machine. It iterates of each element of that list, it creates triplets of element containing previous element, current element, and next element. It passes these triplets to rule_110 function to calculate next state of the current cell. These states are combined in @acc to form next state of the machine or next generation. It handles two edge cases, first when @pos, which points to current position in @machine_state being processed, is equal to 1 and second, when it is equal to length of the @machine_state. These two cases represent the two ends of the list representing @machine_state. When @pos is 1 it considers left neighbour as 0 and when @pos is @machine_state_len it considers right neighbour as 0. The final list created this way happens to be actually the reverse of the next generation. This happens because we process elements from 1 to end of the machine state but append result in our list from backward to front. This is because of a limitation of our list data structure, in which, only way to traverse it is to from front to backward and only way to create it is from backward to front. Nevertheless, we remedy this by using reverse_list function in the end, to reverse the resulting list.

Completing the Simulation

Now lets write final method which computes final state of machine after given number of generations.

.ca_machine(@init_state,@cycle:0) when (@cycle = 0){
   @ca_machine_res:@init_state;
}
.ca_machine(@init_state,@cycle:0) when (@cycle > 0){
   .apply_rule110(@init_state);
   .ca_machine(@apply_rule110_res,@cycle - 1);
}

This method simply calls apply_rule110 method @cycle times, passing result of previous calls to it as its argument. Writing this function is critical to this proof. As simulation of only finite number of steps does not constitute as proof. Since, with this method we can simulate arbitrary number of generations. Memory and time are the only limitations. You can test this method by adding following

.test {
 .define_list(0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0);
 .ca_machine(@list_res,29);
 val_res:@ca_machine_res;
}

This should print following, which is the final state of automaton after 29 generations

.test {
  val_res: 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 -1;
}

Conclusion

With above it seems that LESS is indeed a turing complete language. There are only some limitations which make it hard to do such simulation and probably other general purpose tasks. For example, if there were library routine to append elements to native list, we would not have to roll out our own list. Similarly, a mechanism to define methods similar to built-in ones, which can return values would also make it easier to use this language for more general purpose uses.

WYO: Write your own diff tool

A diff tool generates an output given two input files. This output can be thought of as a script which when applied to first input returns the second input. Diff tool is nothing but a straight forward implementation for finding edit distance at its core. In addition to finding minimum edit distance we also find actions which when applied first input would lead to second input. These actions constitute diff tools output. Lets first define some classes which denote these actions

trait EditAction
case class Delete(line:Int) extends EditAction
case class Insert(line:Int) extends EditAction
case class Copy(line1:Int,line2:Int) extends EditAction

Above we declare three forms of edit actions which can be performed on first input to arrive at second input. Delete action contains line number of the line which is deleted from first input. Insert action contains line number from second input which is inserted into first. Copy action contains two line numbers. First is the line number from first input which is copied and second is line number in second input where it is copied.

Although, there would be many ways to do this but we would like a sequence of these action with minimum cost. Now, we assume that cost of Delete and Insert is more that Copy action since in case of Copy line in first and second input is same and we did not make a change. And since while finding minimum cost only relative cost matters we can assign cost 1 to Delete and Insert Actions and cost of 0 to Copy action. Below is cost function for these edit actions

def cost(action:EditAction) = {
    case _:Delete => 1
    case _:Insert => 1
    case _:Copy => 0
}

Now, lets code up the actual diff method which takes line numbers in first and second input at which starts calculating the diff. The actual diff of two file can be found by invoking this function at position 0,0. This method also assumes that lines from first input are available in lines1 and lines from second input are available in lines2 variables.

def diff(pos1:Int,pos2:Int):List[EditAction]={
   // all lines processed, return empty list
   if(pos1>=lines1.length && pos2>=lines2.length)  
       List[EditAction]()
   // all input 1 lines processed, insert lines from input 2
   else if(pos1 >= lines1.length)
       Insert(pos2)::diff(pos1,pos2+1)
   // all input 2 lines processed, delete lines from input 1
   else if(pos2 >= lines2.length)
       Delete(pos1)::diff(pos1+1,pos2)
   else if(lines1(pos1) == lines2(pos2))
   // both lines from input1,input2 are same, we can copy from 
      // input 1 to input 2 
       Copy(pos1,pos2)::diff(pos1+1,pos2+1)
   else {
       val diff1 = Insert(pos2)::diff(pos1,pos2+1)
       val diff2 = Delete(pos1)::diff(pos1+1,pos2)
       val diff1Cost = (diff1 map cost).sum
       val diff2Cost = (diff2 map cost).sum
       if(diff1Cost < diff2Cost) diff1
       else diff2       
   }
}

Above is a naive implementation of our diff algorithm where in first if we just return empty list of EditAction since pos1 and pos2 are both equal to or greater than number of lines in files, which means that we have already processed all lines. In second if we see that we have already processed all lines in first file so we have no option but to insert lines from second file. Third if handles the case when we have processed all lines in second file, in this case we have no option but to delete remaining lines from first input. Next we handle case when current line in input 1 and input 2 is same, in this case it would be best to simply copy this line from file one to file two.

Next we handle more complex case by calculating cost of both performing Insert and Delete and then comparing the diff cost and returning the diff with minimum cost. Now lets also add code to read input files and call diff method.

object DiffTool extends App {
  val lines1 = io.Source.fromFile(args(0)).getLines.toArray
  val lines2 = io.Source.fromFile(args(1)).getLines.toArray

  trait EditAction
  case class Delete(line:Int) extends EditAction
  case class Insert(line:Int) extends EditAction
  case class Copy(line1:Int,line2:Int) extends EditAction

  def cost(action:EditAction)= action match {
     case _:Delete => 1
     case _:Insert => 1
     case _:Copy => 0
  }

 def diff(pos1:Int,pos2:Int):List[EditAction]={
   if(pos1>=lines1.length && pos2>=lines2.length)
       List[EditAction]()
   else if(pos1 >= lines1.length)
       Insert(pos2)::diff(pos1,pos2+1)
   else if(pos2 >= lines2.length)
       Delete(pos1)::diff(pos1+1,pos2)
   else if(lines1(pos1) == lines2(pos2))
       Copy(pos1,pos2)::diff(pos1+1,pos2+1)
   else {
       val diff1 = Insert(pos2)::diff(pos1,pos2+1)
       val diff2 = Delete(pos1)::diff(pos1+1,pos2)
       val diff1Cost = (diff1 map cost).sum
       val diff2Cost = (diff2 map cost).sum
       if(diff1Cost < diff2Cost) diff1
       else diff2
   }
 }



  println(diff(0,0))
}

When running above program two files, the program literally prints a list of actions to be performed to convert input one into input two. Now this list of actions can be easily translated to either text patch format or html diff or html split view diff. Now, let us add a method to convert these actions to html.

def toHtml(diffActions:List[EditAction]) = {
 <html>
  <body>
   <table border="0" cellspacing="0" >
    {(diffActions map {
       case Delete(line)=>{<tr style="background-color:pink;"><td>{line+", -"}</td><td>{lines1(line)}</td></tr>}
       case Insert(line)=>{<tr style="background-color:lightgreen;"><td>{"- ,"+line}</td><td>{lines2(line)}</td></tr>}
       case Copy(line1,line2)=>{<tr><td>{line1+","+line2}</td><td>{lines1(line1)}</td></tr>}
    })}
   </table></body></html>
}

println(toHtml(diff(0,0)))

Although, this is conceptually complete implementation for generating HTML diff of two files, this implementation is usable only for creating diffs of small files. For large files this implementation is likely to fail with Stack Overflow Exception, since the definition is recursive. One way to fix this is to have an implementation which is tail recursive, such implementations are converted to iteration by Scala compiler. Following is such an implementation of diff routine. We also define a type alias DiffScript for List[EditAction] type

Tail Recursive Diff implementation

 // type alias
 type DiffScript = List[EditAction]
 // an empty diff script
 val emptyDiffScript = List[EditAction]()
 // an empty list of diff scripts
 val empty = List(emptyDiffScript)

 // return diff script with minimum cost
 def minDiff(a:DiffScript,b:DiffScript)={
   val aCost = (a map cost).sum
   val bCost = (b map cost).sum
   if(aCost < bCost) a
   else b
 }
 def diff():DiffScript={
   val emptyList = Seq.fill(lines2.length+1)(emptyDiffScript).toList
   diff(0,0,emptyList)
 }
 /**
  * @param pos1 current line being processed in file1
  * @param pos2 current line being processed in file2
  * @param last last calculated DiffScripts
  * @param curr list of DiffScripts being created
  * @return final optimal DiffScript 
  */
 @tailrec
 def diff(pos1:Int,pos2:Int,last:List[DiffScript],curr:List[DiffScript]=empty):DiffScript={
   if(pos1 >= lines1.length)
       last.reverse.head.reverse
   else if(pos2 < lines2.length){
       val newCurrent = if(lines1(pos1) == lines2(pos2)){
         Copy(pos1,pos2)::last.head
       }else {
         val diff1 = Insert(pos2)::current.head
         val diff2 = Delete(pos1)::last.tail.head
         minDiff(diff1,diff2)
       }
       diff(pos1,pos2+1,last.tail,newCurrent::curr)
   } else
       diff(pos1+1,0,curr.reverse)
 }

Above diff method is tail recursive implementation of iterative lcs implementation. Instead of calculating diff(a,b) in terms of diff(a-1,b),diff(a,b-1) and diff(a-1,b-1), it sequentially calculates diff(a,0),diff(a,1)....diff(a,lines2.length) and stores it in last variable. It then uses this list to calculate diff(a+1,0),diff(a+1,1)...diff(a+1,lines2.length). Proceeding this way it calculates diff(lines1.length,lines2.length) which is the final result.

Setting Up Scala-js with maven

Much of the documentation around setting up Scala-js (sjs from now on) is focused on SBT but if you are already using maven for your project, integrating sjs with it can become a little difficult. Sjs allows one to compile Scala code to Javascript, that is, if you create a Scala class (a.b.C) and then compile it using Sjs to javascript then that class will be available as a variable in window object and can be accessed as window.a.b.C and can be instantiated as new window.a.b.C() in javascript. So, you can write some code directly in javascript and call some code which you originally wrote in Scala (then converted to JS using sjs). Also, there are many Scala Stubs available for DOM API, JQuery etc. which allow you to interact with DOM from within Scala code. These libraries are available as jars as usual.

Now compilation from Scala code to javascript proceeds in mainly two steps. In first step your code is converted to .sjsir and also .class files. So, for each .class file a .sjsir file is generated. These files contain a sort of intermediate or object code which is later converted to js file. Also, other sjs libraries like library for DOM API, Jquery or standard scalajs library come with both .class and .sjsir files in the jar file. Once .sjsir files for your project have been generated, scalajsld tool is used to generate final javascript file by specifying location of generated .class and .sjsir files and also jar files for dependent libraries. scalajsld then combines all these .sjsir files and generates a single .js file which can be used in an HTML file.

Lets take example of following Hello world ScalaJS app from scala-js website. This app simply uses ScalaJS standard library and DOM API to interact with HTML DOM.

package tutorial.webapp

import scala.scalajs.js.JSApp
import org.scalajs.dom
import dom.document

object TutorialApp extends JSApp {
  def appendPar(targetNode: dom.Node, text: String): Unit = {
     val parNode = document.createElement("p")
     val textNode = document.createTextNode(text)
     parNode.appendChild(textNode)
     targetNode.appendChild(parNode)
  }
  def main(): Unit = {
     appendPar(document.body, "Hello World")
  }
}

Lets create a directory for this project "scalajs-tutorial" and copy above code to a file named "TutorialApp.scala" in "scalajs-tutorial/src/main/scala/tutorial/webapp" folder. Also, create a pom.xml file in "scalajs-tutorial/" folder with following contents

 <?xml version="1.0"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0                       http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>org.scalajs</groupId>
<artifactId>scala-js-tutorial-fastopt</artifactId>
<version>1.0.0-SNAPSHOT</version>
<properties>
    <scala.version>2.11.0</scala.version>
    <scalajs.version>0.6.5</scalajs.version>
</properties>
<dependencies>
    <dependency>
        <groupId>org.scala-js</groupId>
        <artifactId>scalajs-dom_sjs0.6_2.11</artifactId>
        <version>0.8.0</version>
    </dependency>
    <dependency>
        <groupId>org.scala-js</groupId>
        <artifactId>scalajs-library_2.11</artifactId>
        <version>${scalajs.version}</version>
    </dependency>
</dependencies>
<build>
    <plugins>
        <plugin>
            <groupId>org.scala-tools</groupId>
            <artifactId>maven-scala-plugin</artifactId>
            <executions>
                <execution>
                    <goals>
                        <goal>compile</goal>
                        <goal>testCompile</goal>
                    </goals>
                </execution>
            </executions>
            <configuration>
                <scalaVersion>${scala.version}</scalaVersion>
                <jvmArgs>
                    <jvmArg>-Xms64m</jvmArg>
                    <jvmArg>-Xmx1024m</jvmArg>
                </jvmArgs>
            </configuration>
        </plugin>
    </plugins>
</build>
</project>

Above is a basic pom file for compiling a standard scala project, it uses maven scala plugin for compiling scala source. It also mentions dependency on scalajs-library and scalajs-dom libary, since our source in TutorialApp makes use of these two libraries. Running mvn clean install on this pom.xml will generate .class files from Scala source and also create a jar file containing those class file under target directory.

In order to generate sjsir files we need to add a scala compiler plugin to this pom file. This plugin is a scala compiler plugin and not a maven plugin. To configure this plugin modify scala maven pluging configuration so that it looks as below.

<plugin>
    <groupId>org.scala-tools</groupId>
    <artifactId>maven-scala-plugin</artifactId>
    <executions>
        <execution>
            <goals>
                <goal>compile</goal>
                <goal>testCompile</goal>
            </goals>
        </execution>
    </executions>
    <configuration>
        <scalaVersion>${scala.version}</scalaVersion>
        <jvmArgs>
            <jvmArg>-Xms64m</jvmArg>
            <jvmArg>-Xmx1024m</jvmArg>
        </jvmArgs>
        <compilerPlugins>
            <compilerPlugin>
                <groupId>org.scala-js</groupId>
                <artifactId>scalajs-compiler_2.11.0</artifactId>
                <version>0.6.4</version>
            </compilerPlugin>
        </compilerPlugins>
    </configuration>
</plugin>

Here we added compilerPlugins tag to configuration section of scala maven plugin and also specified GAV of scalajs compiler plugin. Now if you run mvn clean install, it should generate .sjsir files along with .class files under target/classes directory.

Our next step is to generate final js file. Unfortunately, there is no maven plugin to do this yet, instead there is a command line utility provided by scala-js, which we can invoke from maven to generate the final js file. To obtain the command line utility download standalone distribution of scalajs from scalajs website [0]. Untar/unzip the distribution and add bin directory inside the expanded archive to your PATH enviornment variable. Make sure to give execute permissions to all files in this directory. Now, to invoke this from maven, lets add following maven exec plugin to plugins tag in pom.xml

<plugin>
    <groupId>org.codehaus.mojo</groupId>
    <artifactId>exec-maven-plugin</artifactId>
    <executions>
        <execution>
            <id>final-js</id>
            <phase>package</phase>
            <goals>
                <goal>exec</goal>
            </goals>
        </execution>
    </executions>
    <configuration>
        <executable>scalajsld</executable>
        <commandlineArgs>-d target --output target/${project.artifactId}.js target/classes ${jartoLink.paths}</commandlineArgs>
    </configuration>
</plugin>

This exec plugin will run "scalajsld" command with target as destination directory (-d option) and name of the generated final js file is specified using --output argument, in this example it is project artifact id .js. Finally we specify location of all .sjsir files. target/classes contains .sjsir files for our project. We then specify paths to all library jar file files using variable "jartoLink.paths". This variable contains paths to all jar files in in local file system (.m2 repository) specified in dependencies sections. This variable is set using maven dependency plugin. Add following plugin in pom xml plugins section to make this work.

<plugin>
    <groupId>org.apache.maven.plugins</groupId>
    <artifactId>maven-dependency-plugin</artifactId>
    <version>2.10</version>
    <executions>
        <execution>
            <id>build-classpath</id>
            <phase>generate-sources</phase>
            <goals>
                <goal>build-classpath</goal>
            </goals>
            <configuration>
                <outputProperty>jartoLink.paths</outputProperty>
            </configuration>
        </execution>
    </executions>
</plugin>

Now, if you run mvn clean install, it should generate scala-js-tutorial-fastopt.js file in target directory. You can now include this in an HTML page as follows.

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8">
    <title>The Scala.js Tutorial</title>
  </head>
  <body>
    <!-- Include Scala.js compiled code -->
    <script type="text/javascript" src="./target/scala-js-tutorial-fastopt.js"></script>
    <!-- Run tutorial.webapp.TutorialApp -->
    <script type="text/javascript">
      tutorial.webapp.TutorialApp().main();
    </script>
  </body>
</html>

Place above HTML file in "scalajs-tutorial" directory. If you open this file in browser you should be see "Hello World".
Scala js is a great tool as it allows one to use advanced features of scala for writing javascript code. As more and more scala js libraries become available to use with scala js, it will make writing and most importantly maintaining Javascript code. Scala JS automatically gives you static typing, packages, pattern matching, Options, flatMap etc. It also allows you to write common code for both server and client only once.
[0] http://www.scala-js.org/doc/internals/downloads.html

Functors in Java

Java is not a functional language. Java does not support functions as values which can be passed around as parameters to other functions. Although, a similar sort of functionality can be implemented using Function Objects. Many people confuse function objects and Functors which are actually quite different things. In this article we focus on Functors but to be able to demonstrate we need to first be able to define function objects which can be passed around as values.

Java 8 adds support for lambda expressions which are a nothing but some sugar for Anonymous classes from earlier versions Java and functions returned from lambda expression are objects which implement a usual interface with only one method. Here we will be using these lambda expressions but similar functionality can be obtained by using Anonymous class syntax by providing inline implementation of these interfaces. Java 8 also introduce default methods for interface which again we will be using in this article, but similar functionality can be obtained by using Abstract class instead, in earlier versions of Java.

As a first step lets define some simple interfaces for function objects, we will be adding more features to these interfaces as we go along.

/**
 * Function Object interface for defining a function
 * which takes a input parameter of type A
 * and returns a value of type B
 */
public interface Function1<A,B> {
   B apply(A a);
}

/**
 * Function object interface for defining a function
 * which takes input parameters of type A and B
 * return s value of type B
 */
public interface Function2<A,B,C> {
   C apply(A a,B b);
}

Function1 and Function2 are interfaces for functions with 1 and 2 input parameters respectively. Similarly, We could also define a Function0,Function3, Function4 etc. interfaces for functions which do not take any input parameter and take 3 and 4 or more parameters. Now lets create some functions and invoke them.

public class TestMain {
   public static void main(String args[]){
       /**
        * square function returns an Integer
        * and return square of it
        */
       Function1<Integer,Integer> square = (Integer a)->{ return a*a; };
       Integer squareValue = square.apply(3);
       System.out.println(squareValue);  // prints 9

       /*
        * Defines a function which takes two integers
        * a and b and returns product of both
        */
       Function2<Integer,Integer,Integer> mult = (Integer a,Integer b)-> { return a*b; };
       Integer productValue = mult.apply(3,4);
       System.out.println(productValue); // prints 12
   }
}

We defined some simple functions which take Integers as input and return Integer as output. Since, in our interfaces we define separate type parameters for each parameter and return type we can function which take and return different types. Let's write a function which takes Age as Integer in years and Height as Double in cm, and returns String with Age and Height separated by "-"

   Function2<Integer,Double,String> ageHeight = (Integer age,Double height)->{ return age+"-"+height; };
   // Now we can print age height
   System.out.println(ageHeight.apply(19,168.2)); // prints 19-168.2

Many functional languages also provide ability to apply a function partially, that is, provide only first few parameters instead of all parameters. When this is done function returns another function which takes remaining parameters, this is called currying and is a very useful feature. Again, it is simple to add this currying to our Function Objects. Lets add this capability to our Function interfaces.

/**
 * Function Object interface for defining a function
 * which takes a input parameter of type A
 * and returns a value of type B
 */
public interface Function1<A,B> {
   B apply(A a);
   default Function1<A,B> apply(){
       return (A a)->{ return apply(a); };
   }
}

/**
 * Function object interface for defining a function
 * which takes input parameters of type A and B
 * return s value of type B
 */
public interface Function2<A,B,C> {
   C apply(A a,B b);
   default Function1<B,C> apply(A a){
       return (B b)->{ return apply(a,b); };
   } 
   default Function2<A,B,C> apply(){
     return (A a,B b)->{return apply(a,b);};
   }
}

Lets see currying in action

  // mult.apply(3) returns a function which when invoked with 
  // a parameter x returns x multiplied by three 
  Function1<Integer,Integer> mult3 = mult.apply(3);
  // A function to calculate a^n
  Function2<Integer,Integer,Integer> pow = (Integer n, Integer a)-> { return (int) Math.pow(a,n); };
  // now we can define other functions like square, cube like so
  Function1<Integer,Integer> square1 = pow.apply(2);
  Function1<Integer,Integer> cube = pow.apply(3);

Functor

Now lets say we have a List of Integers and we want to calculate square of all the Integers in the List. One obvious way is to iterate over each element of the list and pass the value of each item to our square function. And lets say we also want to have all the resulting integers also as a List, so we need to create a new List of Integers and resulting integers to this new list. This is a very common pattern that appears again and again in functional programming. That is, we have a function from input type A to return type B, and a List of type A and we want List of type B created by application of function on each element. This is applicable to all container types like Sets, Lists, Tree,Vector etc, in fact, it applies to types other than container types, only requirement is that Type in question must have at least one type variable, we will see example of a type other than container type later in this blog. For example, List<T> is a List with type variable T. Formally, a Functor is any type, F, with at least one type parameter, A, and which implements a function fmap which accepts function (A to B) and instance of Type F[A] and returns another instance of type F[B]. This is also called lifting of function (A to B) to (F[A] to F[B]) , that is , it operates on higher type now. Lets see how we can implement Functor in Java. In order to demonstrate this we will first create an Interface called Functor and then create a new List by extending java.util.ArrayList and we will also implement Functor interface by defining required fmap method.

interface Functor<L extends Functor<?,?>,A> {
  <B>  L fmap(Function1<A,B> f);
}
static class FList<A> extends ArrayList<A> implements Functor<FList<?>,A> {
  public <R> FList<R> fmap(Function1<A,R> f){
       FList<R> list = new FList<R>();
       for(A a:this){
           list.add(f.apply(a));
       }
       return list;
  }
}


public class TestMain {
   public static void main(String args[]){
       /**
        * square function returns an Integer
        * and return square of it
        */
       Function1<Integer,Integer> square = (Integer a)->{ return a*a; };
       Integer squareValue = square.apply(3);
       System.out.println(suqareValue);  // prints 9

       /*
        * Defines a function which takes two integers
        * a and b and returns product of both
        */
       Function2<Integer,Integer,Integer> mult = (Integer a,Integer b)-> { return a*b; };
       Integer productValue = mult.apply(3,4);
       System.out.println(productValue); // println 12
       FList<Integer> nums = new FList<Integer>();
       nums.add(1);nums.add(2);nums.add(3);nums.add(4);nums.add(5);
       System.out.println(nums); // prints [1,2,3,4,5];
       System.out.println(nums.fmap(square)); //prints [1,4,9,16,100];
       System.out.println(nums.fmap(square).fmap(mult.apply(4))); // println [4,16,36,64,100]
   }
}

Here we first calculated square of all numbers in the list of integers. We also chained fmap to first multiply all numbers by square and the fmap resulting list with partially applied mult function with only first parameter specified as 4, this further multiplies numbers in list by 4. This chaining of functions, that is, of applying one function after another is common. And there exist another more elegant way of doing this, which is called function composition. In function composition instead of applying one function first and then applying second function on the result, we create a new function by composing these two functions. This new function when applied to list has the same effect.
We can achieve function composition if we also make our Function Object Functors too, that is, have Function Object also implement fmap method. This is an example where our type is not a container type but still can be Functor. As explained previously that only requirement of a potential Functor type is that it must have at least one type parameter.

// new Function1 defintion with fmap implementation
interface Function1<A,B> extends Functor<Function1<?,?>,B> {
   B apply(A input);
  default <C> Function1<A,C> fmap(Function1<B,C> f){
       return  (A a) -> { return f.apply(apply(a)); };
  }
  default Function1<A,B> apply(){
    return (A a)->{return apply(a);};
  }
}
public class TestMain {
   public static void main(String args[]){
       /**
        * square function returns an Integer
        * and return square of it
        */
       Function1<Integer,Integer> square = (Integer a)->{ return a*a; };
       /*
        * Defines a function which takes two integers
        * a and b and returns product of both
        */
       Function2<Integer,Integer,Integer> mult = (Integer a,Integer b)-> { return a*b; };

       FList<Integer> nums = new FList<Integer>();
       nums.add(1);nums.add(2);nums.add(3);nums.add(4);nums.add(5);
       System.out.println(nums); // prints [1,2,3,4,5];
       
      Function1<Integer,Integer> square_and_mult4 = square.fmap(mult.apply(4));
      System.out.println(nums.fmap(square_and_mult4)); //prints [4,16,36,64,100];
   }
}

This makes our Function Objects Functors too. fmap on Function Object is same as function composition and using that we created a new function square_and_mult4, this function when mapped of elements of list produces same result as applying square and mult individually.
Although, we could implement such a functionality as available in more functional languages such as Haskell but there are some weaknesses in type system of java. For example, when implementing Functor interface we had to again specify implementing type (FList), also there is no way to enforce constraint in the interface that only types which have at least one type parameter should be able to implement this interface. Also, we could declare functions using lambda system but we still had to provide all the types in the LHS, whereas, languages like Haskell can auto deduce this type information. These are some areas where languages like Haskell, scala have real advantage over java.

LESS is More

When a programer looks at a new language which is slightly different than general programming languages, first question that comes to his mind is if the language is turing complete. Similar thing happened to me when I looked at LESS. LESS is a CSS preprocessor and from a cursory look it looks like a macro sort of language which copy pastes definitions from one place to another. Actually, it is little more than that as it also tries to be a CSS like declarative language. That is, instead of defining variable you define properties and order defining those properties does not matter. Nevertheless, I have still not well understood the model of computation followed by this language, but it seems that even implementing a counter in this language is not very straightforward. I do not have anything to say to creators of LESS as it is not intended to be a general purpose language. Language does allow mathematical expression, variable definition, conditions (guards), methods. With these tools at hand I thought it would be easy to implement loops using recursion and calculate factorial and fibonacci sequence. My first attempt at creating a program that will find the factorial of a given number failed as it seems language does not allow updating a variable in a given scope once it is defined. At this point I knew that probably language does not well support writing such routines. I googled a lot to see if someone else has done something like this, but did not find anything. I was now looking for a language feature which could be exploited to carry out calculations and also preserve state. After trying many things I found that if you keep all the state in the form of parameters of a function (mixin), it is possible to get the effect of modifying a variable (state updation).  Below are some programs I wrote for calculating factorial and fibonacci numbers.

  
.fact_impl(@n,@res) when (@n > 1){
   .fact_impl(@n - 1, @res * (@n - 1));
}

.fact_impl(1,@res){
  @fact_res:@res;
}
.fact(@k){
  .fact_impl(@k,@k);
}

.fib_impl(@n,@first,@second) when (@n > 0){
  .fib_impl(@n - 1,@second,@first+@second);
}
.fib_impl(0,@first,@second){
  @fib_res:@first;
}
.fib(@k){
  .fib_impl(@k,0,1);
}

result{
  .fact(6);
  .fib(8);
  factorial_of_6:@fact_res;
  fibonacci_8:@fib_res;
}

LISP in Javascript

The main concept in LISP is that data is program and program is data. A wonderful way in which authors of SICP present the later is by creating data structure just by using functions. Lists in LISP and methods to operate on them can be created using just functions. We can do the same in Javascript as well, i.e. create List data-structure by just using functions and without objects or arrays. In fact we can create any data structure in this way. But an interesting question is where is data stored? (Its not too difficult to answer this question). Following is the JavaScript code which implements basic cons, car and cdr routines in Javascript.

  
function cons(x,y){
    var p=function(n){
        if(n==0)return x;
        if(n==1)return y;
        throw new Error("Index out of bound"+n);
    }
    p.toString=function(){
        return "("+x+","+y+")";
    }
    return p;
}
function car(z){
    return z(0);
}
function cdr(z){
    return z(1);
}

Now let us create some functions based on this list

  
/**
 * Syntactic sugar for constructing a list
 */
function list(){
   var args = [].slice.call(arguments);
   if(args.length == 0)
       return null;
   var first = args.shift();
   return cons(first,list.apply(this,args));
}
/**
 *  calculates length of the list
 */
function len(l){
    if(!l) return 0;
    return 1 + len(cdr(l))
}
/**
 * Calculate the factorials upto n
 * returns a list of factorials upto n
 */ 
function fact1(n,acc,a){
   if(n>1) return cons(acc,fact(n-1,acc*a,a+1));
   return acc;
}
function fact(n){
  return fact1(n,1,1);
}

These lists are created purely out of functions, we did not use any array or object type. This list can be extended to more complex data structures such as tree or graph.
Now let us create a little more complicated data structure, a binary search tree.

/**
 * Method to create a node in tree
 */
function create_node(val,left,right){
  return cons(val,cons(left,right));
}
/**
 * method to get left subtree
 */
function left(tree){
  return car(cdr(tree));
}
/**
 * method to get right subtree
 */
function right(tree){
  return cdr(cdr(tree));
}
/**
 * method to add a new number in binary search tree
 */
function add(num,tree){
    if(!tree){
      return create_node(num,null,null);
    }
    var val=car(tree);
    var l = left(tree);
    var r = right(tree);
    if(num > val) return create_node(val,l,add(num,r));
    if(num < val) return create_node(val,add(num,l),r);
    return tree;
}
/*
 * method to check if a number 
 * exists in the tree
 */
function num_exists(num,tree){
  if(tree){
     var l = left(tree);
     var r = right(tree);
     var val = car(tree);
     if(num == val){
       return true;
     }
     return num_exists(num,l) || num_exists(num,r);
  }
  return false;
}

/**
 * method to do in order traversal of tree
 * and output list of sorted nodes
 * @param tree current node to traverse in the tree
 * @parent list of root val and in order traversed 
 * list of right sibling subtree
 */
function traverse(tree,parent){
  if(!parent){
    parent = null;
  }
  if(tree){
     var l = left(tree);
     var r = right(tree);
     var val = car(tree);
     var traversedRight = traverse(r,parent);
     var trr = cons(val,traversedRight);
     return traverse(l,trr);
  }
  return parent;
}

/* sample run */
var tree = add(3);
tree=add(4,tree);
tree=add(9,tree);
tree=add(5,tree);
tree=add(1,tree);
tree=add(2,tree);
console.log(num_exists(5,tree)); // outputs: true
console.log(""+traverse(tree)); // outputs: (1,(2,(4,(5,(9,null)))))

As we can how complex data structures can be created without using any object or array

Quality

Recently I finished reading Zen and Art of Motorcycle Maintenance by Robert M. Pirsig. In this book Pirsig introduces a concept of Quality which is so weird that it cannot be defined. I found concept of Quality so intriguing that I went ahead and read his another book "Lila" in which he explains Quality in more detail and introduces some new concepts.

He describes Quality as something that cannot be defined because whenever you try to define it, it loses its essence and what we end up defining is something inferior to the Quality itself. He argues that we all know what Quality is but we cannot define it. For example we often talk about things having high quality and things having low Quality but when asked why, the answer usually varies from person to person and also from time to time.

My original intention here was to put down the concept of Quality in as much detail as I understand and in as simple terms as possible. But while writing this I quickly realized that it's very difficult if not impossible to nail down the concept of Quality. Trying to talk about Quality in its full genrality is like shaking a bee hive. Therefore, I will not attempt this. Instead, I will first present a simplified model of our universe and define what quality is in that universe.

This Model Universe ( or 'MUniverse' for short) consists of an arbitrary number of entities. These entities represent anything and everything of our real universe. An entity could represents something as small as a grain of salt or an atom, or something as big as mountain. It could represent something as simple as an atom or something as complex as a human being. In MUniverse these entities constantly interact with each other by exchanging messages.

Now these entities have an internal state which gets modified as they send and receive messages. Change in state of these entities can be small or large or there maybe no change at all. One other property of these entities is that usually these entities would not like their state to be changed, and when a message arrives they may either ignore the message completely or modify it so that change in their state is very small. So there is some discrepancy in the message that arrived and the message which actually took effect.

   Analogy to our real universe
   -------------------+----------------------------------------
       MUniverse      |      Real Universe
   -------------------+----------------------------------------------------
       Entities       |     everything from atom(or subatomic particles 
                      |     to human beings, thus group of entites is also 
                      |     entity
       Interactions   |     events, anything from motion, collision
                      |     or even thought.
   ------------------------------------------------------------------------

In this model of universe "Quality" is the message that originally arrived. And since it is we humans who have created the concepts of subject and objects, this distinction between subject and object arises only after message has been perceived either after modification or without any modification.

Prisig in his book further clarifies it by introducing two new concepts that of Static Quality and Dynamic Quality. Dynamic Quality is what we have been referring to as "Quality" so far. Static quality is the state in which entities have become stuck and are resisting any further change.

Now as in the Model I made it clear that a group entities can also form another entity which can have its own state and a state where this group as whole is stuck. This gives rise to a hierarchy of Static Qualities. Pirsig Identifies four levels of Static Qualities. Intellectual Quality, Social Quality, Biological Quality, Inorganic Quality.

Now according to Pirsig we normally perceive only Static Quality or in other words we are trying to ignore the original message (Dynamic Quality). This works well for some time as long as the descrepancy between Dynamic and Static Quality is not too much. When the difference between Dynamic Quality and Static Quality of entity is too great a change occurs which create a new Static Quality. This manifests itself as revolution in society when current Static Quality of society is replaced by new Dynamic Quality that someone or some group of people perceived which forms yet another Static Quality ( or state) which would last as long as it can model Dynamic Quality or the actual messages being sent quite well.

Pirsig also explains that when we solve a problem, one first tries everything one knows to find the solution. At some point it may also seem impossible to solve problem and we find ourselves stuck. It happens because we always were try not to percieve original message and are stuck within our state (Static Quality). After trying everything we know, we reach a state of mind where we have no idea good or bad in our mind. This is the state according to Pirsig that zen budhists try to achieve through meditation. In this state mind becomes empty and ready to accept original messages which are required to solve the problem at hand. In this state the problem and the solver become one. That is, there is no distinction between them just as there is no distinction between the entities of the Model universe they are just exchanging messages to each other. Ability to come into this state of oneness is what distinguishes as expert problem solver from a novice.

With this I hope I have been able to record the concept of quality that Pirsig wanted to communicate.