Compiler Construction and JavaCC

Scanning and Parsing are two important phases of compilation process.While it is possible to code a scanner and a parser all by hand, it becomes tedios, specially when the grammar of the language gets more complex. There are Lexer and Parser generators so that we can generate them from a specified grammer.

JavaCC is one such compiler generator. Here are key points about JavaCC.

• It can generate both scanner and parser.
• TopDown parsing: generate the parse tree in a top-down manner.
• It generates Recursive Descent parsers. The parser will execute a set of recursive methods to process the input (not based on parse tables)
• Predictive (non-backtracking). It looks ahead a number of symbols to decide which grammar rule to use.
• Supports LL(K) grammars. That means there must not be left recursion, and the grammar should be left refactored.
• Detects left-recursion, possible ambiguities and warns during compiler generation.
  
• Can use different look-ahead values in different local sections
• Can use syntactic look-ahead. Hence can be considered as a LL(*) parser generator.
• Gammar can be provided in EBNF notation. Removing left recursion is easy and the grammar is more readable.
• Provides debugging support: tokenizing / parsing / looking ahead.
• Supports panic-mode error recovery.
• Supports Unicode.
• Lots of good documentation / resources to follow.
• Good tooling support, including an Eclipse plugin, IntelliJ IDEA plugin and a Maven plugin.

Having unicode support means you can build your compiler using any (natural) language you prefer! You'll only have to change the (programming) language keywords for the new (natural) language. You can also change the (context-free) grammar a bit if you want to make your (programming) language closer to the new (natural) language.

Here is my attempt to create a compiler in my own language, සිංහල (Sinhala). This uses a simplified version of c grammer.
https://github.com/amilamanoj/CMinus/

Recording Music from a Musical Instrument

You can record high quality audio by direct cable connection between your computer and musical instrument (such as musical keyboard, electric guitar).

You need a two way audio cable. (with 3.5mm TRS connectors). Just connect it to audio out of the instrument and line-in/mic of the computer.
Most of the instruments have a 6.35mm socket for audio output. In that case you also need a 6.35mm male to 3.5mm female jack stereo audio adapter. You can get these from a local electronics store or a site like amazon, ebay.

Moving on to software, you don't need expensive professional sound editing software. Audacity is a free and open source cross-platform audio recorder/editor and perfectly fits our purpose.
 
Next comes the tricky part. During recording, you hear what you play through the computer. If there's a delay between what you play and what you hear, it's very difficult to play. Let's look at solutions for this.

Windows

When it comes to Windows, drivers pass sound through the system kernel, resulting considerable amount of latency.
This won't be a big issue on sound cards that support ASIO. ASIO is a sound card driver  protocol that minimizes the latency by bypassing operating system layers and connecting directly to the soundcard. However, not many soundcards support ASIO (specially integrated audio chipsets).

ASIO4ALL may help you in this case. It is an independent universal emulated ASIO driver and brings ASIO support to virtually all consumer-grade soundcards and integrated audio chipsets.
The problem here is that, you need a recording program that supports ASIO. Though Audacity can support ASIO, they don't distribute it with ASIO support since it's proprietary and has an incompatible license. You maybe able to find an unofficial version with ASIO support to download, or if you are a software geek, you can compile Audacity yourself with ASIO support.

Linux

Most modern distributions (Ubuntu, Fedora, Mint, OpenSUSE)  use PluseAudio with ALSA. Usually it results in lower latencies. If you are lucky, you may be able to record without any tweaking.
Within audacity, just goto Edit -> Preferences -> Recording and select Software Playthorugh.

If you experience some delay, you can route the input at PulseAudio level by engaging loopback module. Goto terminal and execute:
pactl unload-module module-loopback
In my experience, this can also have some latency, and if your computer (laptop) has a built in microphone, you might get a loud noise.

What worked best for me is using the pacat command. What we do here is capturing the raw audio steam from the specific device we want and playing it back from the output device on the fly, specifying minimum latency. You can quickly get this working by following these instructions. Make sure you have selected "pulse" as both playback and recording device in Audacity Preferences -> Devices, otherwise you won't be able to record while pacat is active.

After you have recorded, you can easily get the mp3 by using Audacity's Export command.

Here is a recording I made. This is a part of the song "Never Forget" in Halo3. Played with Yamaha PSR-E323. Recorded with Audacity in Linux with the last technique above.
Never Forget (cover) by Amila Manoj

AS2 Protocol

AS2 is a protocol that describes how to exchange structured business data securely using the HTTP transfer protocol.

Structured business data exchanged using AS2 protocol can be,

• Electronic Data Interchange (EDI) in either the
• UN Electronic Data Interchange for Administration, Commerce, and Transport (UN/EDIFACT) format or
• The American National Standards Committee (ANSI) X12 format
• XML or any other structured data formats.

Major application of AS2 is to exchange data in EDI formats.

Security is achieved using digital certificates and encryption. Exchanged messages can be signed using to provide security requirements such as authenticity and preventing non-repudiation. They can be also encrypted to provide confidentiality and integrity. Those are optional requirement according to AS2 specification. An AS2 message can have its content in plain text and without a digital signature.

S/MIME is a format and protocol for adding cryptographic signature and/or encryption services to Internet MIME messages. In AS2, files are encoded as attachments in an S/MIME message. This is what we call an AS2 message. Those messages are sent using the HTTP or HTTPS, usually as POST.

Content Types and AS2

 

There can be several content types for AS2 messages.

• When there is no encryption, no signature
• application/EDIxxxx or application/xml
• When there is no encryption, but signature is present
• multipart/signed – message contains two MIME parts
• application/EDIxxxx or application/xml
• application/pkcs7-signature
• When there is Encryption, but no signature is present
• application/pkcs7-mime
• application/EDIxxxx or application/xml (in the decrypted message)
• When there is both encryption and signature
• application/pkcs7-mime
• multipart/signed(encrypted) – decrypted message contains 2 parts
• application/EDIxxxx or /xml)
• application/pkcs7-signature)

Usually AS2 clients are called "Trading partners". When sending a message, they can request an acknowledgement message called MDN (Message Disposition Notification).

There are several options of requesting a MDN. They are Synchronous MDN, Asynchronous MDN and No MDN.

If there are problems receiving or interpreting the original AS2 message, a "failed" MDN may be sent back. Both "failed" MDN and not receiving MDN (when it is requested) are considered as failures according to specs.

Mendelson (GPL) and OpenAS2 (BSD) are open source implementations of AS2 for java, These can be used to send and receive AS2 messages. Specifically, Mendelson has a user-friendly GUI.

Ruby Notes

I recently started learning Ruby as a part of "Software Engineering for Software as a Service" online course offered by  University of California, Berkeley.

Since I am mostly experienced with java, I found some differences to be interesting.

• Ruby is object oriented, similar to Java. 
• But everything is an object. Even primitive types such as integers are objects. 
• Almost everything is a method call on some object. Even most operators are instance methods. You can do method calls on anything. 
• 6.methods will return a list of methods that it will respond to.
• 1+2 means we pass the objects operator + and the number 2 to the send method of object 1. 1.send(:+, 2)
• Dynamically typed
• Even though objects have types, variable don't have types. 
• Also, there are no declarations either
• That means, you just can use a variable without declaring first, and use it to store any type of object.
• Identifier Conventions
• Class names should UpperCamelCase similar to Java
• But methods and variable names should use snake_case unlike java's camelCase
• Ruby is pass-by-reference, since everything is an object. (whereas Java is pass-by-value.)
• Metaprogramming
• this basically means you can do some of the programming during the runtime, such as method definitions. 
• Say there's an instance variable name. Instead of writing it's getter and setter, you can specify to create them during runtime using metaprogramming by: attr_accessor :name
• Iterators
• Iterations play a big role in Ruby. 
• In Java, we usually run a loop with an index and do something with the object for the index in each iteration.
• In Ruby, iterating with an index is discouraged. Rather, we let objects manage their own traversal.
• my_array.each do |elt| { } end
• Duck Typing
• An object's current set of methods and properties determines the valid semantics, rather than its inheritance from a particular class or implementation of a specific interface.
• For example, you can call sort on arrays with different type of objects, strings, hashes, if they respond to the method somehow, without considering their types.
• Mix-ins
• This is used to achieve duck typing.
• In Ruby, there are things called Modules, A module is a collection of class & instance
  methods that are not actually a class. Therefore you cannot instantiate it
• But by including modules in your class you can resuse (mix) their methods
• class A < B ; include MyModule ; end . A.foo first search A, MyModule and finally B.

Here are some of the resources for getting started with Ruby:

1. Ruby in Twenty Minutes
2. Try Ruby

Ruby Installer is a nice packaging that makes it easy to install Ruby on Windows

Using Apache Thrift with Maven

When you use Thrift for your project, you have to manually generate the sources, put them inside your source folder and build.

This plugin does the work for you when you execute the maven build.

However, this plugin is not yet available on maven central repositories, therefore you have to add developer's repo. to your project pom.

 
    <pluginRepositories>
        <pluginRepository>
            <id>dtrotts</id>
            <name>Repository for maven thrift plugin</name>
            <url>http://maven.davidtrott.com/repository</url>
            <layout>default</layout>
        </pluginRepository>
    </pluginRepositories>
 

Then, as described in the plugin's project page, you have to:

1. Use Java 1.5 or newer due to the usage of Generics

You can specify it in the configuration of maven compiler plugin:

 
    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <configuration>
                    <source>1.6</source>
                    <target>1.6</target>
                </configuration>
            </plugin>
            ...
 

2. Have Thrift executable is in your PATH or set the parameter of the plugin to the correct location.

 
            <plugin>
                <groupId>org.apache.thrift.tools</groupId>
                <artifactId>maven-thrift-plugin</artifactId>
                <version>0.1.10</version>
                <configuration>
                    <thriftExecutable>/usr/local/bin/thrift
                </configuration>
                ...
 

3. Include the dependency for libthrift

 
        <dependency>
            <groupId>org.apache.thrift</groupId>
            <artifactId>libthrift</artifactId>
            <version>0.8.0</version>
        </dependency>
 

Then place your *.thrift files to the directory: src/main/thrift.

Now you can execute mvn clean install as usual.

Volunteer Computing: An Introduction

As the technology advances and research areas widen, demand for computational power increases day by day. Such computational demands can be mainly observed in several categories. Physical simulations from molecular level to universe level, analysis of large data from optical telescopes, gene sequencers, gravitational wave detectors, particle colliders and biology-inspired algorithms are some of those categories.
These tasks require high-performance computing (HPC). So one solution is to use supercomputers. But typically, the rate of job completion is more important than the turnaround time of individual jobs since overall result is what’s useful. The term to refer to that idea is high-throughput computing.

To achieve high-throughput computing, distributed computing is a better approach since individual job can be processed in parallel in large quantities.
Available distributed computing options are:
○ Cluster computing - dedicated computers in a simple location.
○ Desktop grid computing - PCs within an organization as a computing resource.
○ Grid computing - sharing computing resources by separate organizations.
○ Cloud computing - a company selling access to computing power
○ Volunteer computing

Volunteer computing (also sometimes referred to as global computing) uses computational power volunteered by the general public to perform distributed scientific computing. Volunteers may include individuals as well as organizations such as universities.
This approach allow ordinary Internet users to volunteer their computer resources on idle time by forming parallel computing networks easily, quickly and inexpensively without needing expert help.

Typically when it comes to volunteer computing, the volunteers who contribute with their resources are considered to be anonymous, although some volunteer computing frameworks may collect information like a nickname and email address of the volunteers for the usage of credit system, etc.

Each of the distributed computing paradigms have different resources pools. For example, number of computers owned by a particular university when it comes to grid computing, and the number of servers owned by a company in cases of cloud computing. The number of total possible personal computers is the resource pool in the case of volunteer computing.

To understand the importance of volunteer computing, we have to consider its resource pool.
The number of privately-owned PCs around the globe is currently estimated as 1 billion and is expected to grow to 2 billion by 2015. Also, the resource pool is self-financing, self-updating and self-maintaining. Users buy and maintain their own computers. Therefore various costs associated with other types of grid computing do not apply to volunteer computing. Another important point is that consumer market adopts the latest technology quickly. A supercomputer or a computing grid cannot be replaced or upgradedeasily as newer technologies emerge. But the typical PC user can. For example, the fastest processors today are GPUs developed with computer games in mind. Due to these factors, we can state that volunteer computing has a huge potential for world computational needs.

Berkeley Open Infrastructure for Network Computing (BOINC) is the predominant volunteer computing framework in use.

Some of the other volunteer computing frameworks are:
○ Bayanihan Computing Group
○ JADIF - Java Distributed (volunteer / grid) computing Framework
○ Javelin Global Computing Project
○ XremWeb Platform
○ Entropia

Here is a list of most active volunteer computing projects as of January 2012.
○ SETI@home: Search for extra-terrestrial life by analyzing radio frequencies emanating from space
○ Einstein@home: Search for pulsars using radio signals and gravitational wave data
○ World Community Grid: Humanitarian research on disease, natural disasters, and hunger
○ Climateprediction.net: Analyse ways to improve climate prediction model
○ Folding@home: Computational molecular biology
○ LHC@home: Improve the design of the Large Hadron Collider and its detectors
○ Milkyway@home: Create a highly accurate three-dimensional model of the Milky Way galaxy using data collected from the Sloan Digital Sky Survey
○ Spinhenge@home: Study nano-magnetic molecules for research into localized tumor chemotherapy and micro-memory
○ PrimeGrid: Generate a list of sequential prime numbers, search for particular types of primes
○ Malariacontrol.net: Simulate the transmission dynamics and health effects of malaria

(This post includes citations from several sources and aims to summarize volunteer computing)

First Steps of Apache Thrift with Java in Linux

Apache Thrift is a software framework for scalable cross-language services development. It was originally developed by Facebook before it was donated to Apache Software Foundation.  

Download the stable release

Unpack the tar.gz archive to a directory you prefer
(say home /home/amila/apacheThrift)

tar -xvzf thrift-0.8.0.tar.gz

You need JDK and Apache Ant at least to run Thrift's Java tutorial.
(You can refer to my previous posts to find how to install JDK on ubuntu.)

Use apt-get to install Ant

sudo apt-get install ant
 

We first need to install Thrift compiler and language variables before we start developing we Thrift.

There are several required packages to install Thrift that are not installed on a linux distribution by default.
To install those

sudo apt-get install libboost-dev libboost-test-dev libboost-program-options-dev libevent-dev automake libtool flex bison pkg-config g++ libssl-dev 
 

Goto top level directory of unpacked thrift distribution
(eg: /home/amila/apacheThrift/thrift-0.8.0)

./configure
 

During this process, thrift will scan and list the different language found.
It should say:

Building Java Library ........ : yes
Using javac .................. : javac
Using java ................... : java
Using ant .................... : /usr/bin/ant

..along with other languages found on your computer.

However, to configure Thrift for all those languages, you may need to install additional packages

Now you can make Thrift:

make
 

You might get some error if all required libraries for the languages configured in above step are not present.

In that case, you can deselect the packages you don't need when configuring
For example, say you don't need the support for Ruby. When configuring, you can use:

./configure --without-ruby
 

(I had to deselect erlang libraries to get it working on ubuntu 11.04)

After make is completed successfully, install Thrift by,

sudo make install
 

To check if the installation is successfully completed:

thift
 

You should get an output like:

Usage: thrift [options] file
Options:
  -version    Print the compiler version
  -o dir      Set the output directory for gen-* packages
               (default: current directory)
  -out dir    Set the ouput location for generated files
.........
.........
 

Tutorial are located at ./tutorials directory.

There you will find two files tutorials.thrift and shared.thrift

.thrift files describe the interfaces (IDL) in terms of the classes, methods they include.

thrift -r -gen java tutorial.thrift
 

This will create a directory named "gen-java" inside your current directory which will include generated Java classes according to specified thrift file.

Now goto the directory "java" inside the current directory (tutorial) and execute ant.
The ant script will compile both generated source files and the source file inside java directory and build a jar file.

Finally, run the tutorial by:

thrift/tutorial/java$ ./JavaServer
thrift/tutorial/java$ ./JavaClient
 

You may also find this page useful.