Showing posts with label scala. Show all posts
Showing posts with label scala. Show all posts

Friday, November 11, 2011

Scala, regex, and null

One of the perks of using scala is that I hardly ever see a NullPointerException unless I'm working with java libraries. The primary reason is because most scala libraries tend to use Option rather than null. However, while using a regex with pattern matching I was surprised by a NullPointerException when trying to look at the result of an optional capture group. Consider the following example:

scala> val Pattern = "(a)(b)?".r
Pattern: scala.util.matching.Regex = (a)(b)?

scala> "a" match { case Pattern(a, b) => printf("[%s][%s]%n", a, b) }
[a][null]

scala> "ab" match { case Pattern(a, b) => printf("[%s][%s]%n", a, b) }
[a][b]

I just assumed that b would be of type Option[String]. There is probably a good reason for this travesty, my guess would be something about making it work with the type system, but after using scala for a while it just seems wrong to be getting a null value.

Monday, August 15, 2011

Scaladoc wiki syntax

I was having some trouble getting the scaladoc wiki syntax to work properly so I finally spent some time and read through the code to learn the quirks. Since I prefer examples to lengthy explanations, I'm posting the reference example I used for testing along with a screen shot showing the actual rendering. So here is the example markup:
/**
 * Example of using scaladoc wiki syntax. I use this example to make sure
 * [[https://wiki.scala-lang.org/display/SW/Syntax scaladoc syntax page]]
 * examples actually work. In particular, I could not get the wiki syntax lists
 * to work based on the documentation.
 *
 * This is another paragraph (note the empty line above) containing '''bold''',
 * ''italic'', `monospace`, __underline__, ^superscript^, and ,,subscript,,
 * words. This sentence uses the inline elements specified in the section
 * "Inline elements" on the syntax page that are sometimes different from the
 * example for _italic_, *bold*, +underline+, {{monspace}}, ^superscript^, and
 * ~subscript~. Why are there multiple ways of specifying the same format?
 * Apparently there aren't, the ones from the inline elements section do not
 * work.
 *
 * == Inline elements ==
 * This section contains a correct listing of inline elements. It is also a
 * handy example of an unordered list as well as escaping.
 *
 *  - '''Italic''': `''text''` becomes ''text''.
 *  - '''Bold''': `'''text'''` becomes '''text'''.
 *  - '''Underline''': `__text__` becomes __text__.
 *  - '''Monospace''': use backticks, I couldn't figure out how to escape
 *    other than sticking something in an inline monospace section, `text`.
 *  - '''Superscript''': `^text^` becomes ^text^.
 *  - '''Subscript''': `,,text,,` becomes ,,text,,.
 *  - '''Entity links''': `[[scala.collection.Seq]]` becomes
 *    [[scala.collection.Seq]]. As far as I know there is know way to link to
 *    external scaladoc so this is useless except for linking to other classes
 *    in the same build.
 *  - '''External links''': `[[http://scala-lang.org Scala web site]]` becomes
 *    [[http://scala-lang.org Scala web site]].
 *
 * == Block elements ==
 * Paragraphs should be obvious by now, just include a blank line. So lets move
 * to code blocks with a simple fibonacci example:
 *
 * {{{
 * def fib(n: Int) = if (n < 2) n else fib(n - 1) + fib(n - 2)
 * }}}
 *
 * Headings are pretty straightforward, lets show some examples:
 * =h1=
 * Note that the default style for h1 makes it some white color with a drop
 * shadow that is difficult to see in the main body of the documentation.
 * ==h2==
 * ===h3===
 * ====h4====
 * =====h5=====
 * ======h6======
 *
 * == Lists ==
 * There is an example unordered list for the inline elements. This example will
 * be more gratuitous and try the various list types that are supported. I must
 * be an idiot because I couldn't figure out how to make unordered lists work
 * without looking at the scaladoc source code. Now it seems rather obvious
 * from the instructions. The problem I had was the "`$` is the left margin"
 * bit. I kept trying to include a `$` in the code to now avail. The other
 * problems is that the first whitespace after the `*` is ignored. However,
 * I still contend that with a simple example it would have been obvious right
 * away, so here are some list examples that have been tested and actually
 * generate a list:
 *
 *  1. item one
 *  1. item two
 *    - sublist
 *    - next item
 *  1. now for broken sub-numbered list, the leading item must be one of
 *     `-`, `1.`, `I.`, `i.`, `A.`, or `a.`. And it must be followed by a space.
 *    1. one
 *    2. two
 *    3. three
 *  1. list types
 *    I. one
 *      i. one
 *      i. two
 *    I. two
 *      A. one
 *      A. two
 *    I. three
 *      a. one
 *      a. two
 *
 * I didn't see it mentioned on the document but you can also add a horizontal
 * rule with 4 dashes. See hr below:
 *
 * ----
 *
 * Ok now a brief look at supported javadoc tags. `@code` gets mapped to
 * inline monospace, e.g., {@code testing}. `@docRoot` and `@inheritDoc` are
 * mapped to empty strings. `@link`, `@linkplain`, and `@value` are also mapped
 * to inline monospace, e.g., {@link link}, {@linkplain linkplain},
 * {@value value}. Note it seems linkplain is confused with link. `@literal`
 * just dumps the value in without modification, e.g., {@literal some value
 * '''in a literal''' that __will__ get wiki formatting}.
 *
 * @author subnormal numbers
 * @see scala.collection.Seq
 */
object Example {
   /**
    * Adds two integers.
    * @param v1  actual parameter
    * @param v2  actual second parameter
    * @param v3  garbage, but no warning :(
    * @return  sum of two integers
    * @throws java.io.Exception also garbage, but no warning
    * @since 1.5
    * @todo do something useful
    * @deprecated
    * @note a profound note
    * @example add(2, 2)
    */
   def add(v1: Int, v2: Int): Int = v1 + v2
}
The generated output with 2.9.0.final looks like:

Monday, February 21, 2011

zfcat

While messing with java, I have frequently wanted an easy way to cat a file inside of a zip archive such as a jar, war, ear, and whatever other names they have cooked up for a zip file with a manifest. As one example, when trying to setup maven to generate an OSGi bundle, I want to generate the jar file and then look at the generated manifest to see if it is correct. There is probably an existing command line tool that provides this functionality, but I couldn't find one with the little bit of searching I tried and it is trivial to write such a tool. So I wrote a quick "zip file cat" tool called zfcat in Scala:
#!/bin/sh
exec scala $0 $@
!#

import java.io._
import java.util.zip._

object zfcat {
    def copy(in: InputStream, out: OutputStream): Unit = {
        val buffer = new Array[Byte](4096)
        var length = in.read(buffer)
        while (length != -1) {
            out.write(buffer, 0, length)
            length = in.read(buffer)
        }
    }

    def main(args: Array[String]): Unit = {
        if (args.length < 2) {
            System.err.printf("Usage: zfcat <archive> [file ...]%n")
            exit(1)
        }

        val zfile = new ZipFile(new File(args(0)))
        args.tail.foreach(file => {
            val entry = zfile.getEntry(file)
            if (entry != null) {
                val in = zfile.getInputStream(entry)
                copy(in, System.out)
                in.close
            } else {
                System.err.printf("Warning: zfcat: %s: no such file%n", file)
            }
        })
    }
}

zfcat.main(args)
This tool worked ok, but it just felt really slow compared to other command line tools. Java in general, and languages that run off of the JVM such as Scala, seems to be a terrible choice for writing command line tools. The problem is that the JVM is designed for long running tasks. For command line tools where most of the time it will be a very short lived job, programs based on the JVM are just too slow. So I wrote a new version of zfcat in Go:
package main

import (
    "archive/zip"
    "fmt"
    "io"
    "os"
)

func die(err os.Error) {
    if err != nil {
        fmt.Fprintf(os.Stderr, "Error: %s\n", err)
        os.Exit(1)
    }
}

func copy(r io.Reader, w io.Writer) os.Error {
    const BUFFER_SIZE = 4096
    var buffer [BUFFER_SIZE]byte
    for {
        switch nr, er := r.Read(buffer[:]); true {
            case nr <  0: return er
            case nr == 0: return nil
            case nr >  0: if nw, ew := w.Write(buffer[0:nr]); nw != nr {
                return ew
            }
        }
    }
    return nil
}

func main() {
    if len(os.Args) < 3 {
        fmt.Fprintf(os.Stderr, "Usage: %s <archive> [file ...]\n", os.Args[0])
        os.Exit(1)
    }

    reader, err := zip.OpenReader(os.Args[1])
    die(err)

    var zfiles = make(map[string] *zip.File)
    for i := range reader.File {
        file := reader.File[i]
        zfiles[file.FileHeader.Name] = file
    }

    files := os.Args[2:]
    for i := range files {
        file := zfiles[files[i]]
        if file != nil {
            r, err := file.Open()
            die(err)
            die(copy(r, os.Stdout))
            die(r.Close())
        } else {
            fmt.Fprintf(os.Stderr, "Warning: %s: %s: no such file\n",
                os.Args[0], files[i])
        }
    }
}
The Go version is fast for short lived jobs and seems to work great. I compared the times for three versions 1) running Scala as a script, 2) Scala pre-compiled, and 3) compiled Go version. The times to cat a small manifest file:
$ time ./zfcat.scala test.jar META-INF/MANIFEST.MF
Manifest-Version: 1.0
Created-By: 1.6.0_22 (Apple Inc.)


real    0m1.588s
user    0m1.076s
sys     0m0.083s
$ time scala zfcat test.jar META-INF/MANIFEST.MF
Manifest-Version: 1.0
Created-By: 1.6.0_22 (Apple Inc.)


real    0m0.635s
user    0m0.822s
sys     0m0.070s
$ time ./zfcat test.jar META-INF/MANIFEST.MF
Manifest-Version: 1.0
Created-By: 1.6.0_22 (Apple Inc.)


real    0m0.028s
user    0m0.003s
sys     0m0.018s
Pre-compiling more than doubles the speed of the Scala version, but it still takes over half a second. The Go version takes less than 30ms. I'm not sure I like the use of the error return values in Go and having to explicitly check them all the time. The decision to limit the use of exceptions as a control structure was deliberate, but I haven't bothered to read through the arguments for their proposal and it is a minor annoyance right now. I was also a little disappointed that I couldn't run valgrind, apparently the 6g compiler generates an executable that valgrind doesn't understand. Valgrind might work with executables generated by gccgo, but I didn't try it.
$ valgrind ./zfcat test.jar META-INF/MANIFEST.MF
bad executable (__PAGEZERO is not 4 GB)
valgrind: ./zfcat: cannot execute binary file

Sunday, November 28, 2010

Automatic Generation of Color Palettes

A problem I've had several times is how to automatically generate colors for use in graphs. The user will be able to select some set of items that should be included and I need to select colors for each item. The requirements are:
  • The color for an item should be easy to distinguish from other items. Of course, it would also be nice if the colors looked decent, but from a functional perspective, the requirement is to be able to distinguish the items in the graph.
  • I need to be able to generate an arbitrary number of colors and avoid a fixed color palette with a predefined number. For practical purposes the number will be limited by the ability to distinguish different colors, but it would be nice for the mechanism to scale gracefully as the number of items increases.
  • The color of the background, for my purposes white, cannot be used.
When I examined a few tools, I found that most worked by having a fixed set of colors. My first attempt was to perform a naive increment of RGB pixel values. A trivial increment works well for shades of gray. This produces a palette like:

Hex24816
000000                                                                
0E0E0E                                                                   
1C1C1C                                                                    
2A2A2A                                                                    
383838                                                                    
464646                                                                    
545454                                                                    
626262                                                                    
707070                                                                    
7E7E7E                                                                    
8C8C8C                                                                    
9A9A9A                                                                    
A8A8A8                                                                    
B6B6B6                                                                    
C4C4C4                                                                    
D2D2D2                                                                    

The problem is that grayscale can be difficult to distinguish with more than a few colors. That is why tools like gnuplot use line patterns and shapes. However, most of my use cases are for graphs shown on a color monitor so there is no need to limit to grayscale. What happens if we try a naive increment with color? My first attempt was to treat the color as a three byte integer and simply divide the desired number of colors to get the increment value. Looking at the palette below you can see the results are poor:

Hex24816
000000                                                                    
0FFFF0                                                                    
1FFFE0                                                                    
2FFFD0                                                                    
3FFFC0                                                                    
4FFFB0                                                                    
5FFFA0                                                                    
6FFF90                                                                    
7FFF80                                                                    
8FFF70                                                                    
9FFF60                                                                    
AFFF50                                                                    
BFFF40                                                                    
CFFF30                                                                    
DFFF20                                                                    
EFFF10                                                                    

After looking around for a bit I found that the HSV representation is fairly well suited for this problem. HSV stands for hue, saturation, and value. The color space is represented as a cylinder:

For more background the paper Color Spaces for Computer Graphics gives a good overview and discusses how the various color spaces were designed with respect to human perception of color. To generate a palette the saturation and value settings can be fixed. The 360o for the hue can be divided by the desired number of colors and then we just increment the angle for each color. This technique gives a nice palette, but for more than around 8 colors it will be difficult for a person to distinguish some shades.

Hex24816
FF0000                                                                    
FF5F00                                                                    
FFBF00                                                                    
DFFF00                                                                    
7FFF00                                                                    
1FFF00                                                                    
00FF3F                                                                    
00FF9F                                                                    
00FFFF                                                                    
009FFF                                                                    
003FFF                                                                    
1F00FF                                                                    
7F00FF                                                                    
DF00FF                                                                    
FF00BF                                                                    
FF005F                                                                    

The Scala code I used for generating the palettes is shown below.
object Colors {

    import java.awt.Color

    def grayscale(num: Int): Seq[Color] = {
        // Truncate the full range of values to make sure we can distinguish
        // from the color white, i.e., (256, 256, 256).
        val range = 256 - 32

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta == 0) {
            throw new IllegalArgumentException(
                "grayscale can support at most " + range + " colors")
        }

        // Generate the sequence of colors
        (0 until num).map(n => {
            val value = n * delta
            new Color(value, value, value)
        })
    }

    def naiveIncrement(num: Int): Seq[Color] = {
        // Truncate the full range of values to make sure we can distinguish
        // from the color white, i.e., (256, 256, 256).
        val range = 0xFFFFFF - 0xFF

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta == 0) {
            throw new IllegalArgumentException(
                "naive increment can support at most " + range + " colors")
        }

        // Generate the sequence of colors
        (0 until num).map(n => {
            val value = n * delta
            new Color((value >> 16) & 0xFF, (value >> 8) & 0xFF, value & 0xFF)
        })
    }

    def hsv(num: Int): Seq[Color] = {
        // Range is 360 degrees for the hue
        val range = 360.0

        // Determine how much to increment for each color.
        val delta = range / num
        if (delta < 1.0) {
            throw new IllegalArgumentException(
                "hsv can support at most " + range + " colors")
        }
        // Generate the sequence of colors
        (0 until num).map(n => {
            val hue = n * delta
            val h = hue / 60.0
            val x = ((1 - Math.abs(h % 2 - 1)) * 255).toInt
            val c = h match {
                case h if 0.0 <= h && h < 1.0 => (255, x, 0)
                case h if 1.0 <= h && h < 2.0 => (x, 255, 0)
                case h if 2.0 <= h && h < 3.0 => (0, 255, x)
                case h if 3.0 <= h && h < 4.0 => (0, x, 255)
                case h if 4.0 <= h && h < 5.0 => (x, 0, 255)
                case h if 5.0 <= h && h < 6.0 => (255, 0, x)
                case _ => (0, 0, 0)
            }
            new Color(c._1, c._2, c._3)
        })
    }

    def main(args: Array[String]): Unit = {
        if (args.length < 2) {
            println("Usage: scala Colors <palette> <num>")
            exit(1)
        }

        // Supported palettes
        val palettes = Map(
            "grayscale" -> grayscale _,
            "naive"     -> naiveIncrement _,
            "hsv"       -> hsv _
        )

        // Generate colors and print
        palettes(args(0))(args(1).toInt).foreach(c => {
            println(c.getRGB.toHexString.toUpperCase.substring(2))
        })
    }
}