myLOGO

One of the programming languages that I love is LOGO. Yes, it is a programming language, although it is limited for drawing. I started using it when I was about 7 years old. Using LOGO formed my perception of computers in general and of programming specifically.

One of the first project I did when I started learning C# by myself (when I was doing my B.Sc) was a tool for running LOGO commands and displaying the results - "myLOGO". It also supported definition of custom procedures (using "ED <proc-name> ... END"). You can download the project here (RAR file). Here is a screenshot:

myLOGO, implemented using C# and WinForms

Then, few years later I started focusing on Java. After a while I started developing plugins for Eclipse. This introduced me with SWT (Standard Widget Toolkit). As a result of my need for understanding SWT better, as a standalone, I decided to implement myLOGO again, only this time in Java & SWT. Doing so I also added support in loops (i.e. the REPEAT command). You can download the project here (ZIP file). Here is a screenshot:

myLOGO, implemented using Java & SWT

The code is hosted in GitHub: https://github.com/yinonavraham/myLOGO

It includes a parser, an AST (Abstract Syntax Tree), design-time and run-time models, UI, etc. I implemented it in a way it can be embedded as a library in other projects. I will elaborate in a future post on another project in which I did exactly that - an Eclipse plugin for developing LOGO scripts.

Griddlers Solver

You know these griddlers puzzles? Every day there is a new 2D 20x20 puzzle in the newspaper we were getting at work. So I decided to implement a solver for those problems.
Before I start talking, you can take a look at the Griddler Solver page. I have prepared some examples.

I chose client-side JavaScript as the runtime environment. Why? just because it's easy to use for coding the solver and it also integrates smoothly with a well known UI - HTML... Oh, and because I wanted to practice my JavaScript skills...
My first attempt with implementing the solver was using kind of DFS (Depth-First-Search). The algorithm was (roughly):

1. Calculate possible solutions for each column
2. Iterate recursively over the columns:
1. Get the current column
2. Iterate recursively over the possible solutions of the column:
1. Get the current possible solution
2. If this is the last column:
1. If the problem is solved (the rows constraints are matched) - stop

This worked great for small problems (about 5x5), but for bigger problems the performance was horrible.
The next step I tried was to add some heuristics. For example, I added some heuristics for pruning branches which are not feasible. Some of the rules I used:

• If the sum of colored cells in a row of the solution is higher than the some of colored cells in the constraint - this branch is not feasible
• If the length of the current block is higher than its expected length - this branch is not feasible

With those rules the performance improved tremendously, but still not enough for the average problem (20x20). 

Then I decided to change direction and instead of implementing based on a generic algorithm (i.e. DFS), I decided to implement an algorithm which is based on the way a human will solve it. So, how do you solve these puzzles? I usually use an iterative solution:

1. Find the large blocks and find overlaps - color them.
2. Check for other constraints which are now easier to match, according to the new colored cells.
3. If there is no single solution - find the minimal possible solutions, select one and try to move forward. If this fails, go back and select a different possible solution. (This step usually does not happen - you usually just need to look harder in steps #1 & #2).

What I have decided to implement was some variation of it. I decided to calculate all the possible solutions for all rows and columns and then do cross-checks for each cell and calculate its probability to be colored. In each step some possible solutions can be discarded since they do not match the decisions that were made during that step.

So the algorithm is basically:

1. Initialize:
1. Calculate all possible solutions for each row & column
2. Initialize the grid so that each cell has an undefined value
2. Solve - while the solution changes:
1. Update probabilities:
   For each cell, calculate the probability for it to be colored by cross checking the possible solutions for both row and column - count the number of solutions where the cell is colored and not colored.
2. Remove false solutions:
   For each cell, if the cell's value is known (i.e. 100% colored or empty) - remove all possible solution (columns and rows) where the cell's value is different from its expected value.

You can see above that I don't yet handle the case when there are multiple possible solutions which none of them can be removed - i.e. need to choose one of them and try to move forward. This is because I did not have such a case yet in any of the puzzles I tried. It's not that difficult to create such example, nor implement it, I just didn't... (for example: 2x2 puzzle with rows - [ [1], [1] ] , and columns - [ [1], [1] ]. Try it...).

In my implementation I implemented the solver as an Iterator which enabled me to add animation to the UI. Since in each step the grid has probabilities for each cell (for whether it is colored), it can make quite nice animations.

You can find the code in my GitHub project yinonavraham/GriddlerSolverJS.

"My" proof for Euler's identity

Few years back, I was sitting in the classroom during my M.E. getting bored. Then I remembered of one of the most beautiful equations - Euler's identity:
\[e^{i\pi}+1=0\]
So I decided to prove it using Taylor series.
Yes, you can ask why? The answer is - because I was bored and because I can...

So, first a reminder - Taylor series definition:
\[
\sum_{n=0}^{\infty}\frac{f^{(n)}(a)\cdot(x-a)^n}{n!}
\]
Now, Taylor series for some basic functions (\(a=0\)):
\(

\begin{align*}
e^x &= e^0+\frac{e^0x}{1!}+\frac{e^0x^2}{2!}+\frac{e^0x^3}{3!}+\dots \\
&= 1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots
\end{align*}
\)

\(
\begin{align*}sin(x) &= 0+\frac{cos(0)x}{1!}+\frac{-sin(0)x^2}{2!}+\frac{-cos(0)x^3}{3!}+\dots \\
&= \frac{x}{1!}-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\dots
\end{align*}
\)

\(
\begin{align*}cos(x) &= 1+\frac{-sin(0)x}{1!}+\frac{-cos(0)x^2}{2!}+\frac{sin(0)x^3}{3!}+\dots \\
&= 1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\dots
\end{align*}
\)

Let's start. If we assign \(x=ix\) in \(e^x\) we get:
\(
\begin{align*}
e^{ix} &= 1 + ix + \frac{(ix)^2}{2!} + \frac{(ix)^3}{3!} + \frac{(ix)^4}{4!} + \dots \\
&= 1 + ix - \frac{x^2}{2!} - \frac{ix^3}{3!} + \frac{x^4}{4!} + \frac{ix^5}{5!} - \frac{x^6}{6!} - \frac{ix^7}{7!} + \dots \\
\end{align*}
\)

If we reorder what we got, we get:
\(
\begin{align*}
e^{ix} &= \underbrace{1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \frac{x^6}{6!} + \dots}_\text{cos(x)} + i \cdot (\underbrace{x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \dots}_\text{sin(x)}) \\
&= cos(x) +i \cdot sin(x) \end{align*}
\)

Let's assign \( x = \pi \):
\(
\begin{align*}
e^{i\pi} &= cos(\pi) +i \cdot sin(\pi) \\
&= -1 + i \cdot 0 \\ &= -1 \end{align*}
\)

So, finally we got what we wished for:
\(
e^{i\pi} + 1 = 0
\)


OK, now - for all of you saying "of course - the identity is just a special case for Euler's formula: \(e^{ix}=cos(x) +i \cdot sin(x)\)" - I know and I "proved" it (well, it's not a real proof and it's not really mine to claim...). Oh, and I also wanted to write some \(\LaTeX\)...
So that was me goofing around out of boredom..


The \(\LaTeX\) in this post is powered by MathJax

Using Java generics for proxy implementation

Overview

Java's generics is very powerful and easy to use. Its common use is straight forward, for example in the Collections API. In this post I would like to show another use, not so common, of generics. The purpose is to implement a proxy for remote class, e.g. when using RMI (Remote Method Invocation), JMX (Java Management Extensions), etc. This is handy since you usually have similar basic functionality in your proxy - connect, disconnect, etc.

Design

The participants in the design - remote classes in green, local classes in blue (the interface is deployed remotely and locally)

As you can see in the class diagram above, there are 4 participants:

• MyInterface -
  This is the interface of the remote class. This interface must be deployed both remotely and locally.
• MyRemoteClass -
  This is the implementation of the remote class. It is deployed remotely and is the target for our proxy (in the client-side)
• AbstractProxy -
  This is an abstract implementation of a proxy. It has some basic common proxy functionality such as connect, disconnect, etc. and it holds the actual proxy object encapsulated inside. This class is deployed locally (in the client-side).
• MyProxy -
  This is the specific proxy for MyRemoteClass. It implements MyInterface and extends AbstractProxy setting the generic type to be MyInterface.

Implementation

Here is partial and simplified implementation of the classes in the design above.

MyInterface

public interface MyInterface {

    void doSomething();

}

MyRemoteClass

public class MyRemoteClass implements MyInterface {

    @Override
    public void doSomething() {
        // Do something...
    }

}

AbstractProxy

public abstract class AbstractProxy<T> {
 
    private T proxy;
 
    protected T getProxy() {
        return proxy;
    }
 
    public void connect() {
        // Connect to the remote class - set the encapsulated proxy object 
    }
 
    public void disconnect() {
        // Disconnect from the remote class - reset the encapsulated proxy object 
    }
 
    public boolean isConnected() {
        // Check whether the proxy is connected
        return true;
    }

}

MyProxy

public class MyProxy extends AbstractProxy<MyInterface> implements MyInterface {

    @Override
    public void doSomething() {
        // Delegate the call to the proxy
        getProxy().doSomething();
    }

}

Use Case Example

Here is a more realistic example of how I used this pattern (with some simplification and modification) for implementing an abstract proxy for JMX agents.

Background

(If you are not interested in the "why", you can skip to the Implementation part)

A few years ago, as part of a distributed system I was working on (school project...), I wanted to implement agents that will be deployed on the servers and listen for requests. This agents needed to answer 2 main requirements:

1. Remote method invocation -
   The ability to connect from one machine to another and trigger actions on the remote server.
2. Monitor the agents on the remote server -
   The ability to connect from a PC to the agent on the remote server and interact with it for monitoring, configuration, perform "manual" actions, etc.

In the beginning I chose Java RMI for the task. It's quite easy to use (in development), and once you run the server you're OK. But then, if you want to monitor it from a remote PC you need to develop a dedicated client UI for that. Therefore I looked for another technology that will give me similar capabilities (of Remote Method Invocation) using an API, but will also answer my other requirement with an existing UI (command line or graphical).
The answer I found was JMX (Java Management Extensions). Although this is not exactly the purpose of JMX, it was close enough and it answers my requirements. The UI for monitoring is JConsole (part of the SDK). It enables you to connect to a Java process (local or remote) and monitor its threads, memory, loaded classes, registered MBeans and more. In the MBeans section you can view & update the attributes each MBean exposes and invoke its methods. This is a simple generic UI which was quite enough for the requirements.

After implementing the MBeans I needed to implement the clients which will enable me to programmatically connect to the remote agents. When I started I noticed there is some basic code that I repeats itself in all clients, just with small differences. These are good candidates for refactoring.

Implementation

public abstract class AbstractJmxClient<MBeanInterface> {
    private MBeanInterface proxy = null;
    private JMXConnector conn = null;
    private MBeanServerConnection mbsc = null;

    // JMX properties which are used to connect to the registered MBean 
    private String jmxHost = null;
    private String jmxDomain = null;
    private String jmxKeyName = null;
    private String jmxKeyValue = null;
    private int    jmxPort = -1;

    // Constructor getting all the JMX properties...
    // Getters for all the JMX properties...

    protected MBeanInterface getProxy() {
        return _proxy;
    }

    /**
     * Connect to the remote JMX agent
     */
    @SuppressWarnings("unchecked")
    public void connect() throws Exception
    {
        String urlSuffix = null;
        try {
            urlSuffix = this.jmxHost + ":" + this.jmxPort + "/jmxrmi";
            ObjectName oName = new ObjectName(this.jmxDomain, this.jmxKeyName, this.jmxKeyValue);
            JMXServiceURL url = new JMXServiceURL("service:jmx:rmi:///jndi/rmi://" + urlSuffix);
            if (this.conn == null) {
                this.conn = JMXConnectorFactory.connect(url, null);
            }
            if (this.mbsc == null) {
                this.mbsc = this.conn.getMBeanServerConnection();
            }
            Type type = getClass().getGenericSuperclass();
            Class<MBeanInterface> mbiClass = null;
            if (type instanceof ParameterizedType) {
                ParameterizedType paramType = (ParameterizedType) type;
                mbiClass = (Class<MBeanInterface>) paramType.getActualTypeArguments()[0];
            }
            this.proxy = JMX.newMBeanProxy(this.mbsc, oName, mbiClass);
        } catch (RuntimeException e) {
            String errMsg = String.format(
                "Could not connect to the JMX agent: [%s:%s=%s] at %s due to the following error: %s",
                this.jmxDomain, this.jmxKeyName, this.jmxKeyValue, urlSuffix, e.getMessage());
            throw new Exception(errMsg, e);
        }
    }

    /**
     * Disconnect from the remote JMX agent
     */
    public void disconnect() {
        this.proxy = null;
        this.mbsc = null;
        if (this.conn != null) {
            try {
                this.conn.close();
            } catch (IOException e) {
                // Write to the trace
            }
            this.conn = null;
        }
    }

    /**
     * Check whether the client is connected to the remote JMX agent
     * 
     * @return true if the client is connected
     */
    public boolean isConnected() {
        if (this.proxy == null || this.conn == null) {
            return false;
        }
        try {
            this.conn.getConnectionId();
            return true;
        } catch (IOException e) {
            return false;
        }
    }

}