Sunday, March 15, 2009

F# for Cheapskates

Since I've been hearing good things about the F# language from various people, I wanted to give it a try, but I wasn't interested in spending $250 on Microsoft Visual Studio. It turns out, however, that you can run F# for free in several ways.

F# with Visual Studio Shell

On Windows, you can run F# with a complete IDE by using Visual Studio Shell (not to be confused with Visual Studio or Visual Studio Express). Visual Studio Shell is an IDE without any included languages, and is available for free.


(Instructions updated August 2009 for latest versions.)

  • Download Visual Studio 2008 Shell SP1 (integrated mode).
  • Run the download. Note: this download does not install Visual Studio Shell; it unpacks a "redistributable package" for Visual Studio Shell that contains the installer. Don't ask why. Make sure you note where it puts this, probably C:\VS 2008 Shell Redist\Integrated Mode.
  • Run the Visual Studio Shell installer vside.enu.exe that was unpacked above. Important: you must not have F# installed at this point; if you already have it installed, uninstall it first.
  • Make sure Microsoft Visual Studio 2008 shows up in your Start menu.
  • Download and install F# 2009 CTP (msi).

Running F# inside Visual Studio Shell

Start Visual Studio Shell. Start F# should appear under View -> Other Windows -> F# Interactive; Control-Alt-F should also work. Type into the F# Interactive window:
printfn "Hello world!";;
Hello world!
val it : unit = ()
Note that in the interactive window, you must enter ;; to have your input processed.

F# in Visual Studio

To see the F# tutorial, click "Create Project ..." in the "Recent Projects" window, then double-click "F# Tutorial".

To create a new program, click "Create Project ..." in the "Recent Projects" window, then double-click "F# Application". Type code into the "Program.fs" window, for example:

printfn "Hello world!"

open System
Console.ReadKey(true) |> ignore
To run the program, hit F5. The purpose of the last two lines is to keep the console window open until you hit a key; otherwise, the window will only flash up briefly. Note that the double-semicolons aren't required.

F# in Visual Studio

You can also highlight text in the program window and press Alt-Enter to have it executed in the F# Interactive window. Visual Studio includes a debugger with breakpoints and all. Select Debug -> Start Debugging to run under the debugger.

F# from the Windows command line

You can also skip Visual Studio and run F# from the command line. To do that, just download F# as above. Then run the F# interpreter fsi.exe either from a cmd window or from the Start menu:
C:\Program Files\FSharp-\bin\fsi.exe
> printfn "Hello world!";;
Hello world!
val it : unit = ()

F# with Mono

Another option is running F# with Mono. This provides a way to run F# on Linux or OS X. To do this, download and unzip F# 2008 CTP (zip). Download and install Mono 2.X. The Readme file in the F# distribution provides all the details on running F# with Mono, so look there.

(I wasn't too successful with Mono; it's no longer supported on RedHat, and compiling from sources ran into libgdiplus incompatibility. I could only run fsi.exe with the --no-gui flag.)

F# under mono

F# vs Arc

Since this is nominally an Arc blog, I should compare F# and Arc. The F# language has some nice features such as type inference, currying, and pattern matching. On the other hand, it lacks powerful Lisp-style macros, and is not as terse as Arc. The F# implementation is much, much more polished than Arc. It has extensive documention, an IDE, real error messages, reasonable performance, huge libraries, a compiler, and so forth. Overall, I find programming in F# more enjoyable than in Arc, and find it easier to get something done in F# after using it for a few hours than in Arc after several months.

Next steps

Once you have F# running, you can take a look at Microsoft's F# in 20 Minutes tutorial to learn more. I'm currently going through the book Expert F#.

One of the interesting things about F# is you can easily write graphical Windows applications. A couple quick hints: to use the Windows Forms dlls, go to "Project -> Add Reference" and click "System.Windows.Forms", and then "ok". To suppress the console window, go to "Project -> ConsoleApplication2 Properties..." and select "Output type: Windows Application".

I found (and I realize this is an obvious lesson) that I learned much more from actually writing simple F# programs than from reading blog posts about it. So if you're still reading, stop now, install F#, and write some code!

Tuesday, March 3, 2009

Why Unicode is important

A couple months ago I went to a French cafe at the Denver airport. Outside the restaurant was a large rotating menu, clearly costly to manufacture. Some of the beverages on the menu puzzled me: "Caf  Latte", "Caf  Americano", and "Caf  Mocha".
faulty menu
When I saw "Proven al Salad", I realized that they had suffered an unfortunate accented character mishap; the menu was supposed to offer "Café Latte", "Café Americano", "Café Mocha", and "Provençal Salad". Unfortunately, the accented characters disappeared somewhere in the sign printing process. The font, likely Marker Felt Thin, has accented characters, so they should have been able to get it right.

I {entity} unicode So... can any deep insight be extracted from this, or is it just a somewhat entertaining picture? My first conclusion is that notwithstanding the Arc Unicode debacle, support for non-ASCII characters is important even if you're a sign shop in Denver. My second conclusion (based on personal experience) is that everything conspires to destroy non-ASCII characters, and it's non-trivial to get them right. My third conclusion - which will make sense if you've seen UTF-8 get misinterpreted as latin-1 - is the restaurant should be grateful that they didn't end up with "Café Latte".

Sunday, March 1, 2009

The Y Combinator in Arc and Java

I was recently reading The Little Schemer, a very intersting book about how to think in Scheme. The book uses a unique question-response style to present simple concepts such as cons and recursion, as well as complex concepts such as using lambda functions to build arithmetic out of fundamental axioms, and deriving the Y Combinator.

As you're probably aware, the Y Combinator is a fixed-point combinator, which lets you build recursion out of an anonymous, non-recursive function. The tricky part of building recursion without naming is that if you can't name a function, how can the function call itself? The Y Combinator is a way to do this.

In Arc, it's easy to write a recursive factorial function:

(def fact (n)
  (if (is n 0) 1
      (* n (fact (- n 1)))))
Note that def assigns the name fact to this function, allowing it to recursively call itself. But without def, how can the function call itself?

Fixed point as an infinite stack of function calls

Let's make a function fact-gen that if passed the factorial function as input, returns the factorial function. (Note that fn is Arc's equivalent of lambda.)
(def fact-gen (fact-in)
 (fn (n)
  (if (is n 0) 1
      (* n (fact-in (- n 1))))))
This may seem rather useless, returning the factorial function only if you already have it. Since we don't have a factorial function to pass in, we'll pass in nil (technically bottom). This at least gets us started:
arc> ((fact-gen nil) 0)
arc> ((fact-gen nil) 1)
Error: "Function call on inappropriate object nil (0)"
We can compute factorial of 0, but factorial of 1 hits nil and dies. But we can take our lame factorial function, pass it in to fact-gen and get a slightly better factorial function that can compute factorials up to 1:
arc> ((fact-gen (fact-gen nil)) 1)
We can repeat this to get an even more useful factorial function:
arc> ((fact-gen (fact-gen (fact-gen (fact-gen (fact-gen nil))))) 4)
If we could have an infinite stack of fact-gen calls, then we would actually have the factorial function. But we can't do that. Or can we?

The fixed point of a function f is a value x for which f(x) = x. We can apply the same idea to our infinite stack of fact-gen. Since applying fact-gen to the infinite stack one more time makes no difference, (fact-gen infinite-stack) = infinite-stack, so the infinite stack is a fixed point of fact-gen. Thus, the fixed-point of fact-gen is the factorial function.

If taking the fixed point of an algorithmic function seems dubious to you, a full explanation is available in Chapter 5 of the 1300 page tome Design Concepts in Programming Languages; trust me, it's all rigorously defined.

The fixed-point combinator

So how do you find the fixed point without an infinite stack of functions? That's where the fixed-point combinator (also known as the Y combinator) comes in. The fixed-point combinator Y takes a function and returns the fixed point of the function. That is, applying the function once more makes no difference:
y f = f (y f)
You may wonder how the Y combinator computes an infinite stack of functions. The intution is it computes a finite stack that is just big enough for the argument.

The fixed-point combinator in Haskell

In Haskell, you can use the above definition of the Y combinator directly:
y(f) = f (y f)
fact f n = if (n == 0) then 1 else n * f (n-1)
y(fact) 10
This is a bit of a "cheat", since the definition of the y combinator takes advantage of Haskell's pre-existing recursion, rather than providing recursion from scratch. Note that this only works because of lazy evalation; otherwise the definition of y is an infinite loop. (Haskell includes the Y combinator under the name fix.)

The Y combinator in Arc

The Little Schemer derives the Y combinator in Scheme. The Arc version is very similar:
(def Y (r)
  ((fn (f) (f f))
   (fn (f)
     (r (fn (x) ((f f) x))))))
If the Y combinator is applied to the earlier fact-gen, it yields a recursive factorial function. Like magic:
arc>((Y fact-gen) 10)

You may protest that this doesn't really implement anonymous recursion since both Y and fact-gen are explicitly named with def, so you could really just call fact-gen directly. That naming is just for clarity; the whole thing can be done as one big anonymous function application:

arc> (((fn (r)
  ((fn (f) (f f))
   (fn (f)
     (r (fn (x) ((f f) x))))))

(fn (fact)
 (fn (n)
  (if (is n 0) 1
      (* n (fact (- n 1)))))))

Now you can see the recursive factorial can be computed entirely with anonymous functions, not a def in sight. The first blob is the Y combinator; it is applied to the second blob, the factorial generator, and the resulting function (factorial) is applied to 10, yielding the answer.

Y Combinator in Java

The Y combinator in a Lisp-like language is not too tricky. But I got to wondering if it would be possible to implement it in Java. I'd done crazy continuation stuff in Java, so why not the Y combinator?

Several objections come to mind. Java doesn't have first-class functions. Java doesn't have closures. Everything in Java is an object. Java is statically typed. Is the idea of a Y combinator in Java crazy? Would it require total Greenspunning?

To implement the Y combinator in Java, I did several things. Since Java doesn't have first-class functions, I wrapped each function in an anonymous inner class with a single method apply(), which executes the function. That is, I used a function object or functor. Since "objects are a poor man's closures" (Norman Adams), I used this object creation in place of each closure. In order to define types, I restricted my Java Y combinator to integer functions on integers. Each type defines an interface, and each object implements the appropriate interface.

Using these techniques, I was able to fairly directly implement the Y combinator in Java. The first part defines a bunch of types: IntFunc is a simple function from integers to integers. IntFuncToIntFunc is the type of the factorial generator, taking an integer function and returning another integer function. FuncToIntFunc is the somewhat incomprehensible type of the Y combinator subexpressions that apply f to f yielding an integer function. Finally, the Y combinator itself is an IntFuncToIntFuncToIntFunc, taking an IntFuncToIntFunc (fact-gen) as argument and returning an IntFunc (the factorial function itself).

class YFact {
  // Integer function returning an integer
  // int -> int
  interface IntFunc { int apply(int n); }

  // Function on int function returning an int function
  // (int -> int) -> (int -> int)
  interface IntFuncToIntFunc { IntFunc apply(IntFunc f); };

  // Higher-order function returning an int function
  // F: F -> (int -> int)
  interface FuncToIntFunc { IntFunc apply(FuncToIntFunc x); }

  // Function from IntFuntToIntFunc to IntFunc
  // ((int -> int) -> (int -> int)) -> (int -> int)
  interface IntFuncToIntFuncToIntFunc { IntFunc apply(IntFuncToIntFunc r);};
Next comes the meat. We define the Y combinator, apply it to the factorial input function, and apply the result to the input argument. The result is the factorial.
  public static void main(String args[]) {
      // Y combinator
      (new IntFuncToIntFuncToIntFunc() { public IntFunc apply(final IntFuncToIntFunc r) {
      return (new FuncToIntFunc() {public IntFunc apply(final FuncToIntFunc f) {
          return f.apply(f); }})
          new FuncToIntFunc() { public IntFunc apply(final FuncToIntFunc f) {
         return r.apply(
                new IntFunc() { public int apply(int x) {
    return f.apply(f).apply(x); }});}});}}

        // Recursive function generator
        new IntFuncToIntFunc() { public IntFunc apply(final IntFunc f) {
          return new IntFunc() { public int apply(int n) {
     if (n == 0) return 1; else return n * f.apply(n-1); }};}} 

      // Argument
The result is the factorial of the input argument: (source code)
$ javac
$ java YFact 10
Surprisingly, this code really works, implementing the Y combinator. Note that there are no variables (apart from arguments), and no names are assigned to any of the anonymous functions. Yet, we have recursion.

The Java version is considerably more verbose than the Arc version, since each function becomes an object creation wrapping an anonymous function declaration, with a liberal sprinkling of type declarations, public and final. Even so, there is a direct mapping between the Arc code and the Java code. There's no Greenspunning in there, no Lisp simulation layer. Ironically, the Java code starts to look like Lisp code, except with a bunch of }}} instead of ))).

To convince you that the Java recursion works even in a more complex case, we can implement Fibonacci numbers by simply replacing the input function: (source code)

        // Recursive Fibonacci input function
        new IntFuncToIntFunc() { public IntFunc apply(final IntFunc f) {
          return new IntFunc() { public int apply(int n) {
            if (n == 0) return 0;
            else if (n == 1) return 1;
            else return f.apply(n-1) + f.apply(n-2); }};}}
The code recursively generates Fibonacci numbers:
$ java YFib 30

Is this the "real" Y Combinator?

The typical form of the Y combinator is:
λf.(λx.f (x x)) (λx.f (x x))
and you may wonder why the Y combinator in Arc and Java is slightly different. Because Java (and Scheme, Arc, etc.) are call-by-value languages and not call-by-name languages, they require the applicative-order Y combinator. This combinator has the form:
λr.(λf.(f f)) λf.(r λx.((f f) x))
The call-by-name Y combinator will go into an infinite loop in a call-by-value language. I found this out the hard way, when I implemented the "wrong" Y combinator in Java and quickly got a stack overflow.

For details on applicative-order, eta-reduction, why different combinators are required, and a derivation of the Y combinator, see Sketchy Lisp.

Java vs. Lambda Calculus

In the Java code, new takes the place of λ and apply explicitly shows application, which is implicit in lambda calculus. To make the connection between the Java code and the lambda expression clearer, I have highlighted the key parts of the Java Y combinator:
      // Y combinator
      (new IntFuncToIntFuncToIntFunc() { public IntFunc apply(final IntFuncToIntFunc r) {
      return (new FuncToIntFunc() {public IntFunc apply(final FuncToIntFunc f) {
          return f.apply(f;) }})
          new FuncToIntFunc() { public IntFunc apply(final FuncToIntFunc f) {
         return r.apply(
                new IntFunc() { public int apply(int x) {
    return f.apply(f).apply(x); }});}});}}
Note the exact correspondence of the highlighted parts with the lambda calculus expression:
λr.(λf.(f f)) λf.(r λx.((f f) x))


It is possible to implement the Y combinator in Java, showing that Java has more power than many people realize. On the other hand, the Java code is ugly and bulky; a Lisp-like language is a much more natural fit. For more fun, try going through SICP in Java.


I received some great feedback with interesting links. Apparently a number of people enjoy implementing the Y combinator in a variety of languages: