Friday, December 28, 2007

A quick look at SNOBOL

This entry is just a brief glimpse at the SNOBOL programming language. From its Wikipedia entry:


SNOBOL (String Oriented Symbolic Language) is a computer programming language developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky.


SNOBOL is a language for string manipulations. Also from its Wikipedia entry:


... SNOBOL was widely used in the 1970s and 1980s as a text manipulation language ... its popularity has faded as newer languages such as Awk and Perl have made string manipulation by means of regular expressions popular ...



This language caught my attention while listening to the OOPSLA podcast episode on the excellent 50-in-50 talk by Guy Steele and Richard Gabriel.

Given that this a programming language exploration blog, learning more about this language provide an excellent opportunity to know more about the first languages for text manipulation.

The best place to learn about the language is http://www.snobol4.org/ a lot of SNOBOL resources can be found there. One of the best resources is a link to the THE SNOBOL4 PROGRAMMING LANGUAGE (Green Book).

All the examples presented in this post were created using the Macro SNOBOL4 in C implementation.

A "Hello world" program in SNOBOL looks like this:


OUTPUT = 'Hello World'
END


As shown here, the assignment to the special OUTPUT variable outputs the value to the standard output.

The inverse is also true for the INPUT variable. For example the following program asks the name of the user.


OUTPUT = "Your name? "
NAME = INPUT
OUTPUT = "Hello " NAME
END


Flow of control is given by jumps to labels given the successful execution of a statement. For example:


ASK
OUTPUT = "Your name? "
NAME = INPUT :F(DONE)
OUTPUT = "Hello " NAME :(ASK)
DONE
OUTPUT = "Finished"
END


This example asks for a name until the input is closed, that is end of file or Ctrl+D (in Linux). The ASK,DONE and END elements are labels; all of them (except for END) are user specified names. The :F(DONE) modifier means jump to DONE if failed and the :(ASK) modifier means jump to ASK.

The most interesting thing about the language is the string pattern matching capabilities. Here's an small(and very incomplete) example that extracts the parts of a simplified URL string:


LETTER = "abcdefghijklmnopqrstuvwxyz"
LETTERORDOT = "." LETTER
LETTERORSLASH = "/" LETTER

LINE = INPUT
LINE SPAN(LETTER) . PROTO "://" SPAN(LETTERORDOT) . HOST "/" SPAN(LETTERORSLASH) . RES

OUTPUT = PROTO
OUTPUT = HOST
OUTPUT = RES
END



In line 6, the contents of the LINE variable is matched against a pattern. The pattern contains the following elements:


  1. The SPAN(LETTER) . PROTO "://" section says identify a sequence of letters followed by "://" and assign them to the variable called PROTO

  2. The SPAN(LETTERORDOT) . HOST "/" secotion says take a sequence of letters and dots followed by "/" and assign then to the variable called HOST

  3. Finally the last section takes the remaining letters and slash characters and assign them to the RES variable




To show a litte program that uses all the elements presented here, I wanted to create a small example that takes as input the authentication /var/log/auth.log and shows all the uses of sudo and the program that was executed. The desired lines look like this:


Dec 28 08:21:42 glorfindel sudo: lfallas : TTY=pts/3 ; PWD=/home/lfallas ; USER=root ; COMMAND=/bin/bash


This file also contains entries other than sudo usages, so we have to ignore them.

Heres the program:


&ANCHOR = 0
UCASE = "ABCDEFGHIJLKMNOPQRSTUVWXYZ"
LCASE = "abcdefghijlkmnopqrstuvwxyz"
DIGIT = "0123456789"
APATH = SPAN(DIGIT)
USERNAMECHAR = DIGIT LCASE UCASE
USERNAMEPAT = SPAN(USERNAMECHAR)

READLINE LINE = INPUT :F(DONE)
LINE " sudo: " USERNAMEPAT . USER :F(READLINE)
LINE "COMMAND=" ARB . COMMAND RPOS(0)

OUTPUT = USER ":" COMMAND :(READLINE)

DONE

END


Here the &ANCHOR assignment tells SNOBOL that pattern matching is performed at any position of the specified string. The ARB element says any character before the next pattern succeeds and the RPOS(0) element is used to identify the end of line.



For future entries I'm going to show more interesting SNOBOL features.

Thursday, December 20, 2007

Combining iterators in Java

In this post I'm going to show a little experiment for combining iterators in Java.

A couple of week a ago I read an excellent blog entry by Debasish Ghosh called
Infinite Streams using Java Closures. In it an implementation of the Infinite Stream concept is presented with the help of Java closures.

For this post I wanted to show something related to this but using the Iterable/Iterator interfaces instead of a custom stream object. What interest me the most is the operations applied to stream objects such as map or filter but on iterators. These and other operations are defined for the IEnumerable/IEnumerator interfaces in C# with the extension methods defined in System.Linq.Enumerable.

Also, given the amount of discussion lately around Java closures I wanted to create this code using the Java closures prototype of the BGGA closures proposal to learn about it.

What I want to have is the following operations on iterators:


import java.util.*;

public class IteratorUtils {
public static <X,V> Iterable<V> map({X=>V} f,Iterable<X> i) {
return new EachElementIterable<X,V>(i,f);
}
public static <X> Iterable<X> take(int count,Iterable<X> i) {
return new TakeIterable<X>(i,count);
}
public static <X> Iterable<X> filter({X=>boolean} pred,Iterable<X> i) {
return new FilterIterable<X>(i,pred);
}
public static <X> Iterable<X> flatten(Iterable<Iterable<X>> multiIterator) {
return new FlattenIterable<X>(multiIterator);
}
}


The map operation takes a function and a iterator and generate another iterator with the function applied to each element. The take operation generates an iterator for a number of elements on another iterator. The filter operation takes a predicate and a iterator and returns another iterator with only the elements that applied to the predicate. The flatten operation takes an iterator of iterators and returns a flattened sequence of values.

Heres the iterator for the map operation:


import java.util.*;
public class EachElementIterable<T,J> implements Iterable<J>{
private Iterable<T> iterable;
private {T=>J} function;
public EachElementIterable(Iterable<T> iterable,{T=>J} function) {
this.iterable = iterable;
this.function = function;
}
public Iterator<J> iterator() {
return new EachElementIterator<T,J>(iterable.iterator(),function);
}

static class EachElementIterator<T,J> implements Iterator<J>{
private Iterator<T> iterator;
private {T=>J} function;
public EachElementIterator(Iterator<T> iterator,{T=>J} function) {
this.function = function;
this.iterator = iterator;
}
public J next() {
return function.invoke(iterator.next());
}
public boolean hasNext() {
return iterator.hasNext();
}
public void remove() {
}
}
}


The implementation is not as elegant as the one presented in the Infinite Stream entry, but it can be used with anything implementing Iterable.

Heres the iterator for the take operation:


import java.util.*;

public class TakeIterable<T> implements Iterable<T> {
private int count;
private Iterable<T> iterable;
public TakeIterable(Iterable<T> iterable,int count) {
this.count = count;
this.iterable = iterable;
}
public Iterator<T> iterator() {
return new TakeIterator<T>(iterable.iterator(),count);
}

static class TakeIterator<T> implements Iterator<T> {
private Iterator<T> iterator;
private int count;
private int current;
public TakeIterator(Iterator<T> iterator,int count) {
this.count = count;
this.iterator = iterator;
this.current = 0;
}
public T next() {
if (current++ < count) {
return iterator.next();
} else{
return null;
}
}
public boolean hasNext() {
return iterator.hasNext() && current < count;
}
public void remove() {
}
}

}


Here's the implementation of the filter iterator:


import java.util.*;

public class FilterIterable<T> implements Iterable<T> {
private Iterable<T> iterable;
private {T=>boolean} predicate;
public FilterIterable(Iterable<T> iterable,{T=>boolean} predicate) {
this.iterable = iterable;
this.predicate = predicate;
}
public Iterator<T> iterator() {
return new FilterIterator<T>(iterable.iterator(),predicate);
}

static class FilterIterator<T> implements Iterator<T> {
private Iterator<T> iterator;
private {T=>boolean} predicate;
private T currentValue;
boolean finished = false;
boolean nextConsumed = true;

public FilterIterator(Iterator<T> iterator,{T=>boolean} predicate) {
this.predicate = predicate;
this.iterator = iterator;
}

public boolean moveToNextValid() {
boolean found = false;
while(!found && iterator.hasNext()) {
T currentValue = iterator.next();
if(predicate.invoke(currentValue)) {
found = true;
this.currentValue = currentValue;
nextConsumed = false;
}
}
if(!found) {
finished = true;
}
return found;
}

public T next() {
if (!nextConsumed) {
nextConsumed = true;
return currentValue;
} else {
if (!finished) {
if(moveToNextValid()) {
nextConsumed = true;
return currentValue;
}
}
}
return null;
}
public boolean hasNext() {
return !finished &&
(!nextConsumed || moveToNextValid());
}
public void remove() {
}
}
}


And finally, here's the flatten iterator:


public class FlattenIterable<T> implements Iterable<T> {
private Iterable<Iterable<T>> iterable;
public FlattenIterable(Iterable<Iterable<T>> iterable) {
this.iterable = iterable;
}
public Iterator<T> iterator() {
return new FlattenIterator<T>(iterable.iterator());
}
static class FlattenIterator<T> implements Iterator<T> {
private Iterator<Iterable<T>> iterator;
private Iterator<T> currentIterator;
public FlattenIterator(Iterator<Iterable<T>> iterator) {
this.iterator = iterator;
currentIterator = null;
}
public boolean hasNext() {
boolean hasNext = true;
if (currentIterator == null) {
if (iterator.hasNext()) {
currentIterator = iterator.next().iterator();
} else {
return false;
}
}

while(!currentIterator.hasNext() &&
iterator.hasNext()) {
currentIterator = iterator.next().iterator();
}

return currentIterator.hasNext();
}

public T next() {
return currentIterator.next();
}

public void remove() {
}
}
}


We can combine these wrapper iterators to create operators on iterators of any kind for example:


ArrayList<String> anArray = new ArrayList<String>();
anArray.add("foo");
anArray.add("goo");
anArray.add("zoo");
...

for(String s : map({String s => "<li>"+s+"</li>"},
filter({String s => !s.startsWith("g")},
anArray))) {
System.out.println(s);
}


This example prints the "foo" and "zoo" between <li> and </li> tags. Also here I'm using Java static import to avoid writing IteratorUtils in every operation call.

Returning to the infinite stream operations, for me the most interesting thing about these wrapper iterators is that an iterator with a large amout of elements could be manipulated without consuming all of its elements in each step. For example take the following iterator:


public class NumericSequence implements Iterable<Integer>,Iterator<Integer>{
private int value = 0;
public NumericSequence() {
}
public NumericSequence(int start) {
value = start;
}
public Iterator<Integer> iterator() {
return this;
}
public Integer next() {
return value++;
}
public boolean hasNext() {
return true;
}
public void remove() {
}
}


We can manipulate this iterator using the operations and wrappers defined above:


for(int i : take(5,
filter(
{Integer x => x % 2 != 0 },
map( {Integer x=>x*x},
new NumericSequence())))) {
System.out.println(i);
}


This program prints only 1,9,25,49 and 81.

For the final example I wanted to create a little snippet that prints a list of friendly pairs of numbers. A Friendly Pair is a pair of numbers that share the common characteristic of having the same value as a result of the sum of all of its divisors divided by itself. Another nice definition of a Friendly number is presented here.

First we define some utilities:


public class IntegerIteratorUtils {
public static int sum(Iterable<Integer> integerIterable) {
int result = 0;
for(Integer i : integerIterable) {
result += i.intValue();
}
return result;
}
public static Iterable<Integer> divisors(int number) {
return
IteratorUtils.filter(
{Integer x => x != 0 && number % x == 0 },
IteratorUtils.take(number+1,new NumericSequence()));
}

public static int divisorFunction(int number) {
return sum(divisors(number));
}
}



Having these functions we can now calculate the pairs:


int max = 1000;
for(Pair<Integer,Integer> p :
filter( {Pair<Integer,Integer> p =>
divisorFunction(p.first)/(double)p.first ==
divisorFunction(p.second)/(double)p.second },
flatten(
map(
{Integer x =>
map({Integer ix => new Pair<Integer,Integer>(x,ix)},
take(max,new NumericSequence(x+1)))},
take(max,
new NumericSequence(1)))))) {

System.out.println("("+p.first.toString()+", "+p.second.toString()+")");
}


This program prints:


(6, 28)
(6, 496)
(12, 234)
(28, 496)
(30, 140)
(40, 224)
(66, 308)
(78, 364)
(80, 200)
(84, 270)
....


Code for this example was created with the closures prototype from 2007-11-30. Source can be found here.

Tuesday, December 11, 2007

Creating fractal images with C# 3.0 features and Parallel Extensions

In this post I'm going to show a small example of using the Parallel Extensions Library to improve a program that renders a escape time fractal image.

A couple of months ago I wrote about a small program that creates an image with the escape time algorithm using C# 3.0 features . For this post I'm going to change the implementation to use the Parallel Extensions Library.

Along the the library documentation and MSDN articles, the blog entries from the Parallel Extensions Team blog provided a nice introduction and guidance . The original post was inspired by Luke Hoban's blog entry A Ray Tracer in C#3.0 .

The escape time algorithm is very simple and also considered a embarrassingly parallelproblem. For previous posts I did a similar experiment of using Fortress parallel for loops to render the Mandelbrot Set fractal.

The code for the original program was the following:


void CreateFractal(double minX, double minY,double maxX, double maxY,int imageWidth, int imageHeight)
{
Func<double, double> xF = MathUtils.InterpFunc(0, minX, imageWidth, maxX);
Func<double, double> yF = MathUtils.InterpFunc(0, minY, imageHeight, maxY);

foreach (var p in from yi in Enumerable.Range(0, imageHeight)
from xi in Enumerable.Range(0, imageWidth)
select new
{
x = xi,
y = yi,
xD = xF(xi),
yD = yF(yi)
})
{

Complex p0 = new Complex(p.xD, p.yD);
Func<Complex, Complex> function = functionConstructor(p0);

int i = ApplyFunction(function, p0)
.TakeWhile(
(x, j) => j < maxIteration && x.NormSquared() < 4.0)
.Count();

HandlePixel(p.x, p.y, i);
}

}



We can change this code in several ways to take advantage of the library. Here I'm going to present two of them.

Write one big LINQ expression

The code for the generation of pixel data is coded in a single LINQ expression.

Func<double, double> xF = MathUtils.InterpFunc(0, minX, imageWidth, maxX);
Func<double, double> yF = MathUtils.InterpFunc(0, minY, imageHeight, maxY);

foreach (var p in from yi in Enumerable.Range(0, imageHeight).AsParallel()
from xi in Enumerable.Range(0, imageWidth)
let mappedX = xF(xi)
let mappedY = yF(yi)
let p0 = new Complex(xF(xi), yF(yi))
let function = functionConstructor(p0)
select new
{
x = xi,
y = yi,
xD = mappedX,
yD = mappedY,
i = ApplyFunction(function, p0)
.TakeWhile(
(x, j) => j < maxIteration && x.NormSquared() < 4.0)
.Count()
})
{
HandlePixel(p.x, p.y, p.i);
}


Elements from the body of the foreach loop were moved to the LINQ expression by using the let keyword.

The AsParallel extension method called does the magic of distributing the work for calculating the lines of the image. A nice discussion on were to put this call can be found in Parallelizing a query with multiple “from” clauses and Chunk partitioning vs range partitioning in PLINQ.

Although this problem is much more simpler than Ray tracing, this alternative tries to follow the same approach as: Taking LINQ to Objects to Extremes: A fully LINQified RayTracer.



Add a Parallel.For loop

The other alternative is to replace one of the from elements with a Parallel.For loop.


Func<double, double> xF = MathUtils.InterpFunc(0, minX, imageWidth, maxX);
Func<double, double> yF = MathUtils.InterpFunc(0, minY, imageHeight, maxY);

Parallel.For(0, imageHeight , delegate(int yi)
{
foreach (var p in from xi in Enumerable.Range(0, imageWidth)
let mappedX = xF(xi)
let mappedY = yF(yi)
let p0 = new Complex(xF(xi), yF(yi))
let function = functionConstructor(p0)
select new
{
x = xi,
y = yi,
xD = mappedX,
yD = mappedY,
i = ApplyFunction(function, p0)
.TakeWhile(
(x, j) => j < maxIteration && x.NormSquared() < 4.0)
.Count()
})
{
lock (this)
{
HandlePixel(p.x, p.y, p.i);
}
}
});



A lock needed to be added because HandlePixel calls Bitmap.SetPixel which needs to be protected.

Results

I tested this code by generating a 2000 by 2000 image of a small section of the Mandelbrot fractal located between (-1.1752491998171,0.223337905807042) and (-1.17342021033379,0.225166895290352) with a escape time of 512. A reduced image of this location looks like this:

Calculated Fractal Image

By using the library the program took about 40% less of the time of original version on my dual core machine. The performance for the two approaches presented above was very similar.

The nicest thing about this experiment is that the code required just a couple of modifications in order to take advantage of the other CPU.

Another approach for rendering this fractal using Parallel extensions is from Jon Skeet's Coding Blog : LINQ to Silliness: Generating a Mandelbrot with parallel potential and A cautionary parallel tale: ordering isn't simple.

Code for this post can be found here.

Tuesday, December 4, 2007

Improving code using more Scala features

A couple of days ago Eric Willigers gave me some nice feedback on how to improve the code of the quick fix created for the previous post.

Before modifying the document we are required to lock it and then release it. I did it like this:


...
doc.atomicLock
doc.replace(ifRange.getStart,ifRange.getLength,resultingStatement,null)
doc.atomicUnlock
...


However this is not safe since the replace method could throw a BadLocationException. One of the things we could do is to add a try/catch/finally block. However Eric pointed me to a much nicer way to do , by using two techniques called:



The Loan pattern is a way to ensure resource disposal when the control leaves some scope. For this propose closures are used.

The Pimp my library pattern, based on a Martin Odersky’s article, provides a way to extend existing class libraries with new operations without recompiling. New operations are added by defining a wrapper for specific classes. In this case we need to apply the Loan pattern to the BaseDocument class


class RichDocument(doc : BaseDocument) {
def withLock[T](f : BaseDocument => T ) = {
try {
doc.atomicLock()

f(doc)

} catch {
case ble : BadLocationException =>
Exceptions.printStackTrace(ble)
} finally {
doc.atomicUnlock()
}
}
}


This class defines our wrapper, the f is an anonymous function with code that will modify the document. Now we can add this functionality to the BaseDocument class by using the following declaration:


object DocumentImplicits {
implicit def toRichDocument(doc : BaseDocument) = new RichDocument(doc)
}



Putting using these definitions in the fix code leaves the code like this:


...
doc.withLock(_.replace(ifRange.getStart,
ifRange.getLength,
resultingStatement,
null))
...


The "_.replace ..." syntax is interesting way of specifying an anonymous function with one argument. For more information on this see Placeholder Syntax for Anonymous Functions in section 6.23 of the Scala Language Specification.


Another thing that could be done using this pattern is to eliminate direct uses of the AstUtilities class. By doing this we can add the following definitions:


object AstNodeImplicits {
implicit def toRichAstNode(node : Node) = new RichAstNode(node)
}

class RichAstNode(node : Node) {
def getRange() = AstUtilities.getRange(node)
}


Before using this implicits we need to import them:


import org.langexplr.nbhints.utils.DocumentImplicits.toRichDocument
import org.langexplr.nbhints.utils.AstNodeImplicits.toRichAstNode


The final code for the fix method is the following:


def implement() = {
val doc = info.getDocument.asInstanceOf[BaseDocument]
val conditionRange = condition.getRange()
val conditionText = getConditionText(doc,conditionRange)
val statementRange = statement.getRange()
val statementText = doc.getText(statementRange.getStart,
statementRange.getLength)
val ifRange = ifNode.getRange()

val resultingStatement = statementText + getModifierText + conditionText

doc.withLock(_.replace(ifRange.getStart,
ifRange.getLength,
resultingStatement,
null))
}


Code for this example can be found here (Now updated to the released Netbeans 6.0 ) .

Saturday, November 24, 2007

Creating Netbeans Ruby Hints with Scala, Part 2

In this part I'm going to show a quick fix for the Netbeans Ruby hint presented in part 1.

The quick fix class

The definition of the quick fix for the hint presented in part 1 is the following:


class IfToStatementModifierFix(
info : CompilationInfo,
condition : Node,
statement : Node,
ifNode : Node,
kind : StatementModifierFix) extends Fix {

def isSafe = true
def isInteractive = false

...

}


As shown in this fragment the class that represents the fix requires a reference to each tree element involved in the problem. In this case the important parts are the complete if statement, the condition and the then statement.

Also a kind argument(specific for this quick fix) is used to determine if a if or a unless statement modifier needs to be created. The definition for StatementModifierFix, looks like this:

abstract class StatementModifierFix
case class IfStatementModifierFix extends StatementModifierFix
case class UnlessStatementModifierFix extends StatementModifierFix


The quick fix implementation

The IfToStatementModifierFix class needs to implement the implement method in order to do its work, here's the code:


def implement() = {
val doc = info.getDocument.asInstanceOf[BaseDocument]
val conditionRange = AstUtilities.getRange(condition)
val conditionText = getConditionText(doc,conditionRange)
val statementRange = AstUtilities.getRange(statement)
val statementText = doc.getText(statementRange.getStart,statementRange.getLength)
val ifRange = AstUtilities.getRange(ifNode)

val resultingStatement = statementText + getModifierText + conditionText
doc.atomicLock
doc.replace(ifRange.getStart,ifRange.getLength,resultingStatement,null)
doc.atomicUnlock
}


In order to generate the unless statement we need to change the operator from != to ==.
The getConditionText method does this job:


def getConditionText(doc : BaseDocument,range: OffsetRange) = {
val text = doc.getText(range.getStart,range.getLength)
kind match {
case IfStatementModifierFix() => text
case UnlessStatementModifierFix() => text.replace("!=","==")
}
}


The last thing we need to do is to connect the hint with this quick fix. In order to do this we need to modify the run method of the IfToStatementModifierHint class presented in part 1. We need to add a fix for each identified case.

The case when a method is used as a condition:


...
case ifStat@IfStatement(methodCall : CallNode,
NewlineNode(thenStat),
null) => {

val range = AstUtilities.getRange(node)

val fixes = new java.util.ArrayList
fixes.add(
new IfToStatementModifierFix(info,methodCall,thenStat,ifStat,IfStatementModifierFix))

val desc =
new Description(this,
recomendationText,
info.getFileObject,range,
fixes,
600)
result.add(desc)
}
...


The case when the condition is a not-equal comparison with nil:


case ifStat@IfStatement(condition@NotNode(eqExp@EqualComparison(x,_ : NilNode)),
NewlineNode(thenStat),
null) => {


val range = AstUtilities.getRange(node)

val fixes = new java.util.ArrayList
fixes.add(
new IfToStatementModifierFix(info,condition,thenStat,ifStat,IfStatementModifierFix))
fixes.add(
new IfToStatementModifierFix(info,eqExp,thenStat,ifStat,UnlessStatementModifierFix))

val desc =
new Description(this,
recomendationText,
info.getFileObject,range,
fixes,
600)
result.add(desc)
}


Note that for this case we also offer the quick fix for unless.

Example 1

Activating the hint on this code:



Now displays the following quick fix:



And changes the code as:



Example 2

Also for code like this:



The following options are presented:



By selecting option 2 the code is changed as:



Code for this experiment can be found here.

Monday, November 12, 2007

Creating Netbeans Ruby Hints with Scala, Part 1

In this post I'm going to show a little experiment of creating a Netbeans Ruby Hint using the Scala language. This is the first of a two-part series of posts on this topic.

Netbeans Ruby Hints and Quick Fixes is a very nice feature that will be part of Netbeans 6.0 Ruby integration. This feature can be used to identify potential problems or to promote best practices in Ruby programs. I first learned about it by reading Tor Norbye's blog.

I really like the idea of mixing languages to accomplish something. This is the main reason I chose Scala to do this experiment. Also I wanted to try to apply some ideas from previous posts. For a future experiment it will be very nice to write this code using JRuby.

For this post I'm using Netbeans 6.0 Beta 2. As described below the APIs for writing hints are still not officially public because they're still under development. Again, as with previous posts, this is only an experiment to see how different programming languages could be used solve special tasks.

Motivation

Several weeks ago I wrote a post on Ruby's yield statement, there I showed a function that calculates the Fibonacci sequence using a while statement in a pretty traditional way. Then someone posted a comment with a much compact version of it by using some nice Ruby features. That got me thinking how Netbeans Ruby Hints could also be used to help Ruby beginners(like me) to find out about alternative ways to do something.

The Hint

One of the things I like about Ruby is statement modifiers. That's one of the first things you notice while reading the Why's (Poignant) Guide to Ruby.

I think statement modifiers makes the code look nice if used carefully.

So the hint that will be implement it's going to identify opportunities to apply the if or unless statement modifiers. For example:


table = Hash.new
...
if table.empty? then
puts "No items"
end
...


Could also be written as:


table = Hash.new
...
puts "No items" if table.empty?
...


Creating the Netbeans module

The biggest challenge I had was to create a Netbeans module using only Scala. The main issue is not having all the nice GUI facilities available to create to module.

Luckily there's a series of articles in Geertjan's Weblog called NetBeans Modules for Dummies Part 1,2,3,4. These articles provided a lot of information on how to create an NBM file using Ant tasks .

I also had to create a some Netbeans modules using Java to dissect the resulting NBM file and to provide some of the missing arguments. The resulting Ant file is can be found here.

Another challenge that I had was that some of the classes that I needed to access were only available to friend packages, this mainly because I was trying to access APIs that are still changing. Luckly, Tor Norbye from the Netbeans Ruby development list, provided a solution for this issue which could be found here. Again this is a consequence of using API's that are still not public.

The last issue that I had was to add the Scala Runtime Jar file as part of the package. The How do module dependencies/classloading work? Netbeans Faq entry was very helpful to solve this.

The code

By reading the code of existing hints, I learned that, the way to define hints (which is still under development) is very nice and very simple. Also there's useful documentation in the Writing New Ruby Hints entry from the Netbeans wiki.

Here's the code:

class IfToStatementModifierHint extends AstRule {

def appliesTo(info : CompilationInfo) = true

def getKinds() : Set = {
val nodeKinds = new HashSet()
nodeKinds.add(NodeTypes.IFNODE)
nodeKinds
}

def run(info :CompilationInfo,
node : Node,
path : AstPath ,
caretOffset : int,
result : java.util.List) : unit = {

node match {
case IfStatement(callNode : CallNode,
NewlineNode(thenStat),
null) => {

val range = AstUtilities.getRange(node)

val desc =
new Description(this,
recomendationText,
info.getFileObject,range,
Collections.emptyList,
600)
result.add(desc)
}
case IfStatement(NotNode(EqualComparison(x,_ : NilNode)),
NewlineNode(thenStat),
null) => {


val range = AstUtilities.getRange(node)

val desc =
new Description(this,
recomendationText,
info.getFileObject,range,
Collections.emptyList,
600)
result.add(desc)
}
case _ =>
{
}
}
}

def getId() = "TestHint1"

def getDisplayName() = "If statement as statement modifier"

def getDescription() = "Identifies certain ..."

def getDefaultEnabled() = true

def getDefaultSeverity() = HintSeverity.WARNING

def getCustomizer(node: Preferences) : JComponent = null

def showInTasklist() = true

def recomendationText = "Consider changing..."

}


The most interesting methods of this class are getHints and run.

The getHints method defines the kinds of AST nodes this method applies to. The run method identifies which kinds of if statement apply to this hint. To do this a couple of extractor objects defined in previous posts are used. Two special cases are identified:

  • One if statement with a method call as condition, one statement in the then section and no statements in the else section.

  • One if statement with an equal comparison to nil as condition, one statement in the then section and no statements in the else section.


This Hint is shown as a WARNING because it's the how severity that seems to apply. Although it will be very nice to have a RECOMMENDATION severity which seems to be more appropriate for this hint.

I really like this way of defining hints because you have to write exactly the code related to your problem.

Here's and example in action:




Code for this experiment can be found here.

For the next post I'll try to implement a quick fix for this hint.

Saturday, November 10, 2007

Exploring JRuby Syntax Trees With Scala, Part 2

In this post I'm going to show a couple of examples of using Scala to extract elements of Ruby programs.

Because of its functional influence Scala provides nice features to manipulate tree structures. As I mentioned in previous posts, I think one of the most interesting features provided by Scala is pattern matching. Among other pattern matching constructs, Scala provides one that I particularly like : Extractors.

The Matching Object With Patterns paper by Burak Emir , Martin Odersky , and John Williams, describes several techniques for exploring complex object data structures. One of this techniques is the Visitor design pattern which is one of the most used techniques that is used to navigate a syntax tree structure. I think the pattern matching approach can be combined with the visitors to solve different tasks.

In this post I'm interested in showing pattern matching using Scala extractors on the JRuby AST. The JRuby AST seems to provide nice visitor mechanism which will be explored in future posts.

Scala extractor objects allow existing Scala or Java Platform classes to participate in pattern matching just as case classes. Extractor objects can be used to expose only interesting elements for a certain problem and also makes the definition of the class independent of the way it is used in a match construct. A nice description of this feature for Scala is provided in the Matching Object With Patterns paper. A similar feature is implemented in F# as active patterns.This concept was originated by work on Views by Philip Walder .

I'm going to show a couple of examples of using this feature with the JRuby AST.

Example 1:

Say that you want to identify the key value that is given to Hash assignment: (here highlighted in red)


x["a"] = 1


We need to define extractors for related objects. In order to do this I'm going to use the tool from the previous post to see which classes we need to represent.



By reading this code we noticed that we need at least extractors for

  • BlockNode

  • NewlineNode

  • AttrAssignNode

  • LocalVarNode

  • ArrayNode

  • StrNode

  • FixnumNode



Basic extractors for the child nodes of these elements could be defined as follows:


object NewlineNode {
def unapply(astNode : Node) =
if (astNode.isInstanceOf[NewlineNode]) {
Some(astNode.asInstanceOf[NewlineNode].getNextNode)
} else {
None
}
}

object LocalVarNode {
def unapply(astNode : Node) = {
if (astNode.isInstanceOf[LocalVarNode]) {
Some (astNode.asInstanceOf[LocalVarNode].getName)
} else {
None
}
}
}

object StrNode {
def unapply(astNode : Node) = {
if (astNode.isInstanceOf[StrNode]) {
Some (astNode.asInstanceOf[StrNode].getValue)
} else {
None
}
}
}

object BlockNode {
def unapply(astNode : Node) = {
if (astNode.isInstanceOf[BlockNode]) {
Some (List.fromIterator(
new JavaIteratorWrapper[Node](
astNode.asInstanceOf[BlockNode].childNodes.iterator())))
} else {
None
}
}
}

object FixnumNode {
def unapply(astNode : Node) = {
if (astNode.isInstanceOf[FixnumNode]) {
Some (astNode.asInstanceOf[FixnumNode].getValue)
} else {
None
}
}
}


object AttrAssignNode {
def unapply(astNode : Node) = {
if (astNode.isInstanceOf[AttrAssignNode]) {
val attAsgn = astNode.asInstanceOf[AttrAssignNode]
Some (attAsgn.getReceiverNode,attAsgn.getArgsNode)
} else {
None
}
}
}

object ArrayNode {
def unapply(astNode : Node) =
if (astNode.isInstanceOf[ArrayNode]) {
val theArrayNode = astNode.asInstanceOf[ArrayNode]
Some(List.fromIterator(new JavaIteratorWrapper[Node](theArrayNode.childNodes.iterator)))
} else {
None
}
}


By defining these extractors we can combine them with existing Scala pattern matching constructs to create the required pattern:


val rubyCode2 = "x = Hash.new\n"+"x[\"a\"] = 1"
val rootNode2 = r.parse(rubyCode2,"dummy.rb",r.getCurrentContext.getCurrentScope,0).asInstanceOf[RootNode]

rootNode2.getBodyNode match {
case BlockNode(
List(_,
NewlineNode(
AttrAssignNode(
LocalVarNode("x"),
ArrayNode(
List(key,
FixnumNode(1))))))) =>
System.out.println("Matches for: "+ key.toString())
case _ => System.out.println("No Match!")
}


Example 2:

For the next example say that we want to extract the identifier which is compared to some number in the condition of an if statement. For example:


if the_variable == 1 then
...
else
...
end


The tree representation of a code similar to this looks like:



The following extractors will be used to identify this pattern:


object IfStatement {
def unapply(astNode : Node) =
if (astNode.isInstanceOf[IfNode]) {
val theIfNode = astNode.asInstanceOf[IfNode]
Some (theIfNode.getCondition,theIfNode.getThenBody,theIfNode.getElseBody)
} else {
None
}
}


object EqualComparison {
def unapply(astNode : Node) =
if (astNode.isInstanceOf[CallNode]) {
val theCallNode = astNode.asInstanceOf[CallNode]
if (theCallNode.getName.equals("==") &&
theCallNode.getArgsNode.isInstanceOf[ArrayNode] &&
theCallNode.getArgsNode.asInstanceOf[ArrayNode].size == 1) {
Some (theCallNode.getReceiverNode,
theCallNode.getArgsNode.asInstanceOf[ArrayNode].get(0))
} else {
None
}
} else {
None
}
}


Note that in this case I'm using a shortcut, instead of defining an extractor for CallNode and using it with ArrayNode a single extractor is used to identify the binary equal comparison.

By using this extractors we can define the pattern as follows:


val rubyCode3 = "if the_variable == 30 then\n puts 2\nelse\n puts 3\nend"
val rootNode3 = r.parse(rubyCode3,"dummy.rb",r.getCurrentContext.getCurrentScope,0).asInstanceOf[RootNode]
val nodeToMatch = rootNode3.getBodyNode.asInstanceOf[NewlineNode].getNextNode
nodeToMatch match {
case IfStatement(EqualComparison(leftSide,_ : FixnumNode),
_,
_) =>
System.out.println("Matches for: "+ leftSide.toString())
case _ => System.out.println("No Match!")
}



For future post I'm going to be using these extractors to create more examples in other contexts.

Wednesday, November 7, 2007

Exploring JRuby Syntax Trees With Scala, Part 1

In this post I'm going to show how to use Scala to have access to JRuby syntax trees.

Abstract syntax trees(AST) provide a representation of the source code that can be manipulated by another program. These trees are used by compilers and IDEs to do their work.

The JRuby distribution includes a parser and a nice tree representation for Ruby source code. This AST is used by the JRuby implementation to do its work, and also recently I noticed that the Netbeans Ruby support uses this representation for some tasks.

Calling JRuby Parser is pretty straightforward, just do the following:


package org.langexplr.jrubyasttests;
import org.jruby._
import org.jruby.ast._


object ScalaTestApp {
def main(args : Array[String]) : Unit = {
val rubyCode = "puts \"Hello\""

val r = Ruby.getDefaultInstance
val rootNode = r.parse(rubyCode,"dummy.rb",r.getCurrentContext.getCurrentScope,0).asInstanceOf[RootNode]
...
}
}


The rootNode variable contains the root of the syntax tree for the code stored in rubyCode.

In order to explore the syntax tree I wrote a small program that shows a Swing JTreecomponent with the result of parsing a snippet. Creating this program was easy because Node, the base class of all the elements in JRuby AST, provides a childNodes method. The model for the AST is the following:


package org.langexpr.jrubyasttest;

import javax.swing.tree.TreeModel
import javax.swing.event.TreeModelListener
import javax.swing.tree.TreePath
import org.jruby._
import org.jruby.ast._

class JRubyTreeModel() extends TreeModel {
var rootNode : Node = null;
def this(rubyCode : String) = {
this()
val r = Ruby.getDefaultInstance
this.rootNode = r.parse(rubyCode,"dummy.rb",r.getCurrentContext.getCurrentScope,0)
}

def getRoot : Object = rootNode

def isLeaf(node: Object ) =
node.asInstanceOf[Node].childNodes.size == 0

def getChildCount( parent : Object) : int =
parent.asInstanceOf[Node].childNodes.size

def getChild(parent : Object , index : int) : Object = {
parent.asInstanceOf[Node].childNodes.get(index)
}
def getIndexOfChild( parent : Object, child : Object) : int = {
parent.asInstanceOf[Node].childNodes.indexOf(child)
}
def valueForPathChanged( path : TreePath, newValue : Object) : unit ={

}
def addTreeModelListener( l : TreeModelListener) : unit = {

}
def removeTreeModelListener( l : TreeModelListener) : unit = {

}
}


With this model now we can create the main program:


package org.langexpr.jrubyasttest;


import javax.swing._
import java.awt.event._
import java.awt.BorderLayout
import java.awt.Dimension

object JRubyAstTest {
val treeVisualizer = new JTree
val input = new JTextArea


def createFrame = {
val theFrame = new JFrame("JRuby AST test")
theFrame.setSize(new Dimension(640,450))
val content = theFrame.getContentPane
content.setLayout(new BorderLayout)
content.add(treeVisualizer,BorderLayout.CENTER)


val bottomPanel = new JPanel
bottomPanel.setLayout(new BorderLayout)
content.add(bottomPanel,BorderLayout.SOUTH)

bottomPanel.add(new JScrollPane(input),BorderLayout.CENTER)
input.setText("x=1\ny = 2\n")

treeVisualizer.setModel(new JRubyTreeModel(input.getText))

val button = new JButton("Parse!")
button.addActionListener( new ActionListener() {
def actionPerformed(ae : ActionEvent) =
{
treeVisualizer.setModel(new JRubyTreeModel(input.getText))
}
})

bottomPanel.add(button,BorderLayout.SOUTH)

theFrame
}
def main(args : Array[String]) : Unit = {
val f = createFrame
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setVisible(true)
}
}


Now we can visually explore the AST using this little program.

The following code:

def foo(x)
return x*x
end


Is visualized like this:



Examples in this post could also be implemented easily using JRuby but in the second part I'm going to a couple of Scala features that I specially like to manipulate this data structure.

Tuesday, October 23, 2007

Discriminated unions in Mercury

While reading the Mercury tutorial I learned how to define discriminated unions or algebraic datatypes.

Discriminated unions provide a way to define new structured data types.

For example here's a couple of type definitions that represent very simple arithmetic expressions:


:- type expression ---> const(int)
; var(string)
; binaryOperation(expression,operator,expression).
:- type operator ---> add ; subtract.


These definitions specify arithmetic expression parts such as constants(const), variables(var), binary operations(binaryOperation), etc.

Given these definitions we can instantiate them by calling the constructors:


main(!IO) :-
X = binaryOperation(var("x"),add,const(10)),


Also we can use Mercury's unification to easily manipulate them, for example the following function writes the content of the expression to the output:


:- func operator_to_string(operator) = string.
operator_to_string(add) = "+".
operator_to_string(subtract) = "-".

:- pred write_expression(expression::in,io::di,io::uo) is det.

write_expression(const(C),!IO) :-
io.write_int(C,!IO).
write_expression(var(S),!IO) :-
io.write_string(S,!IO).
write_expression(binaryOperation(Operand1,Operator,Operand2) ,!IO) :-
write_expression(Operand1,!IO),
io.write_string(operator_to_string(Operator),!IO),
write_expression(Operand2,!IO).


Calling this predicate like this:


main(!IO) :-
X = binaryOperation(var("x"),add,const(10)),
write_expression(X,!IO).

Generates:

x+10

Sunday, October 21, 2007

Drawing the Apollonian Gasket with Common Lisp and Vecto

In this post I'm going to show a simple, yet incomplete, program to draw the Apollonian Gasket using Common Lisp and Vecto.

The Wikipedia entry for the Apollonian Gasket defines it as:


In mathematics, an Apollonian gasket or Apollonian net is a fractal generated from three circles, any two of which are tangent to one another. It is named after Greek mathematician Apollonius of Perga.


Basically the Apollonian gasket is generated by finding the 4th circle that is tangent to a given tree tangent circles and repeating the process recursively.

According to Wikipedia in order to find the position and the radius of the 4th circle we use the Descartes theorem which implies that we can apply the following formula:



Given that kn is the curvature of the circle n. The curvature can be calculated as 1/radius of the circle.

According to the Wikipedia article this formula could also be used to determine the position of the 4th circle. By multiplying each curvature value kn with a complex number that represents the position of the circle we can obtain a complex number with the position of the remaining circle.

For example given the following circles:



We can calculate the position of the 4th circle (shown in red) by using the following function:


(defun solve-equation (k1 k2 k3)
(let ((equation
(lambda (op)
(+ k1 k2 k3
(funcall op
(* 2 (sqrt (+ (* k1 k2)
(* k2 k3)
(* k1 k3) ))))))))
(values (funcall equation #'+)
(funcall equation #'-))))


This function is used to solve the equation shown above. We use values to return multiple values implied by the solution of the equation . For this post I'm only using the first solution (that's why the program is incomplete!!!).

To find the radius we can say:


* (* 50 (solve-equation 1/50 1/50 1/50))

6.4641013


To find to position we use the complex numbers provided by Common Lisp and the same function defined above:


* (defvar radius (* 50 (solve-equation 1/50 1/50 1/50)))

RADIUS
* (* radius (solve-equation (* 1/50 #c(50 50)) (* 1/50 #c(150 50)) (* 1/50 #c(100 136.6))))

#C(83.56915 65.90832)




In order to draw the picture of the Apollonian gasket we use the Vecto library which provides an easy way for drawing the picture.


(defun draw-forth-circle (pos1 r1 pos2 r2 pos3 r3)
(set-rgb-stroke 1 0 0)
(let* ((curv1 (/ 1 r1))
(curv2 (/ 1 r2))
(curv3 (/ 1 r3))
(kz1 (* curv1 pos1))
(kz2 (* curv2 pos2))
(kz3 (* curv3 pos3))
(r4 (/ 1 (solve-equation curv1 curv2 curv3)))
(pos4 (* r4 (solve-equation kz1 kz2 kz3))))
(progn
(centered-circle-path
(realpart pos4)
(imagpart pos4)
r4)
(stroke)
(list pos4 r4))))


(defun draw-apollonian-gasket (c1 r1 c2 r2 c3 r3 steps)
(if (> steps 0)
(let ((lc41 (draw-forth-circle c1 r1 c2 r2 c3 r3)))
(draw-apollonian-gasket c1 r1 c2 r2 (car lc41) (cadr lc41) (- steps 1))
(draw-apollonian-gasket c2 r2 c3 r3 (car lc41) (cadr lc41) (- steps 1))
(draw-apollonian-gasket c3 r3 c1 r1 (car lc41) (cadr lc41) (- steps 1)))))

(defun tria (file)
(with-canvas (:width 300 :height 300)
(set-rgb-stroke 1 1 1)
(set-line-width 1)
(translate 50 150)

(let* ((pos1 #c(50 50))
(r1 50)
(pos2 #c(150 50))
(r2 50)
(pos3 (complex
100
(- 50 (sqrt (- (* 100 100) (* 50 50))))))
(r3 50))

(centered-circle-path (realpart pos1) (imagpart pos1) r1)
(centered-circle-path (realpart pos2) (imagpart pos2) r2)
(centered-circle-path (realpart pos3) (imagpart pos3) r3)
(stroke)
(draw-apollonian-gasket
pos1 r1
pos2 r2
pos3 r3 5))
(save-png file)))



Running this program generates the following picture:



By applying scale and translate command we can obtain a better picture:



This program only draws one portion of the complete Apollonian Gasket, in order draw the complete picture, the other solutions of the equation shown above must be used. In future posts I'm going to try to complete the program.

Friday, October 12, 2007

The Mercury Programming Language

Mercury is a programming language that combines concepts from the logic and functional programming paradigms. In this post I'm going to show a couple of features of this language.

The hello world program looks like this:


:- module hello.


:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.

:- implementation.

main(!IO) :-
io.write_string("Hello world from Mercury!\n",!IO).



Where module hello is a module declaration, interface declares elements exported by this module and implementation contains the code for this module.

A couple of days ago I started reading the Ralph Becket's Mercury tutorial which is a very nice tutorial for learning the language. Also there's useful documentation available in the website including a Prolog to Mercury Transition Guide .

The language allows the creation of functions, for example here's the mandatory factorial function:


:- func factorial(int) = int.
factorial(N) = (if N = 0 then 1 else N*factorial(N-1)).


But also the language allows the creation of predicates that result in multiple solutions as in Prolog. For example see the following predicate that generates the numbers from 0 to N:


:- pred numbers(int::in, int::out) is nondet.

numbers(0,0).
numbers(N,R) :-
N > 0,
(
numbers(N-1,R);
R = N
).


The pred section declares the numbers predicate. It says that the first argument is of type int and is for input and the second argument is also type int and is for output. Finally the is nondet says that this predicate may result in zero or more solutions.

The first rule says that when asking for numbers from 0, return 0. The second rule says that if asking for a number greater than 0 then return all the numbers from 0 to N-1 and then return N.

Using this predicate we can implement the following example from a previous post:

We need to write a program to find a 4-digit number such that ABCD*4 = DCBA where A,B,C,D are the digits of that number.

(Complete problem is described here)

A Mercury predicate that solves this problem looks like this:


:- pred solve_problem(list(int)::out) is nondet.

solve_problem(R) :-
numbers(9,A),
numbers(9,B),
numbers(9,C),
numbers(9,D),
A > 0,
(1000*A + 100*B + 10*C + D)*4 = (1000*D + 100*C + 10*B + A),
R = [A,B,C,D].


As with Prolog the backtracking mechanism will find the values of A,B,C and D that satisfy the constraints.

In order to use the result of this predicate the solutions predicate is used. This predicate returns a list with all the results from the specified predicate.


main(!IO) :-
solutions(solve_problem,R),
io.write(R,!IO),
io.write_string("\n",!IO).


This program writes:


[[2, 1, 7, 8]]


In future post I'll try to explore more features of this interesting language.