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