Higher Logics

There's a long-running debate on the power of functional languages over object-oriented languages. In truth, now that C# has full generics, aka parametric polymorphism, it's almost equivalent in typing power to most typical statically typed functional languages. In fact, in terms of typing power, generic objects are universal and existential types, and can be used for all the fancy static typing trickery that those entail (see my previous reference to the GADTs in C# to see what I mean). As a prior post explained, C#'s type system still lacks some of the flexible constraint refinement available in more powerful functional type systems, but in general C# is powerful enough to encode most interesting functional abstractions. And I started a new project to demonstrate this: FP# . It provides a number of widely used functional abstractions, like the option type, a lazy type, lists, lazy lists, etc. and map, filter, and fold over all the collection types, including the sta...

I just read a blog post recommending that developers broaden their language horizons, with a particular emphasis on Ruby. The author attempts to explain why expressiveness is an important metric for a language: What is this obssesion[sic] with "expressiveness"? Go write poertry [sic] if you want to be expressvive.[sic] Remember that ultimately our jobs are (usually) to solve some kind of business problem. We're aiming for a finish line, a goal. The programmer's job is translate the language of the business person to the language of the computer. The whole point of compilers, interpreters, layers of abstraction and what-not are to shorten the semantic distance between our intent and the way the computer thinks of things. To be honest, this is not very convincing; the moment you mention "semantics", is the moment many developers will close your blog and go do something "productive". The argument for expressiveness is ultimately quite simple: the mor...

GEXL is a general expression library providing core primitives for building and processing expression trees. I had abandoned it awhile ago because I quickly ran into a serious, well-known issue: The Expression Problem . Basically, the expression problem boils down to the fact that typical programming solutions are extensible in only a single direction: either the data types or the operations defined on them, but not both, can be extended without modifying existing code. It takes some sophisticated type machinery to safely solve the expression problem, and various languages, including OCaml , Haskell , Beta/gBeta , and Scala , have acceptable solutions. Languages supporting multimethods support less type safe extension , so I exclude them here (although Nice might do it properly). So GEXL, which aims to provide both data and their operations as data and visitors respectively, runs smack into the expression problem. Fortunately, Mads Torgersen's paper, The Expression Problem Revisi...

I work with .NET everyday, and it's a decent virtual machine from the developer's perspective, and a slight overall improvement over Java in a number of respects. But for a language implementor, .NET continues a tradition of mistakes that began with Java, which inhibit it from achieving its much touted goal as the Common Language Runtime (CLR). These issues are divided into two categories: blatant mistakes, and nice to haves. The former requires no cutting edge features or research to implement, and the CLR should have had them from the get-go. The latter might have required some research to get right (like they did with generics), but which are ultimately required for a truly secure and flexible virtual machine. Blatant Mistakes Insufficiently powerful primitives for execution and control flow. The most glaring of these omissions are first class function pointers and verifiable indirect calls. On .NET a function pointer is reified as an IntPtr, which is an opaque struct repre...

My previous definition of IVisitor hard-coded the return value as a type of Val, but one can generalize a visitor to any kind pattern-matching function by adding a generic type parameter to the interface: //the pattern matching visitor public interface IVisitor<T> { //return type is now parameterized T App(Exp e0, Exp e1); } This of course requires a modification to the class variants as well: //the type representing an expression application public sealed class App : Exp { Exp e0; Exp e1; public App(Exp e0, Exp e1) { this.e0 = e0; this.e1 = e1; } //add a generic constraint to the Visit method, so the client can //specify the return type public override T Visit<T>(IVisitor<T> v) { return v.App(e0, e1); } } So instead of IVisitor being hard-coded as an evaluator, I can now write an IVisitor that performs transformations on the expression tree (such as rewriting optimizations), or a visitor that implements some arbitrary predica...

To kick off my first post, I thought I'd cover a post on another blog that I found interesting . Basically, the gist of the post is that object oriented visitor pattern does not lend itself to the problem of walking trees, and general symbolic manipulation, despite that being its claim to fame. In general, algebraic data types and pattern matching are much simpler, and more concise. I agree, however I think that post goes a bit too far in saying that visitors simply can't do this elegantly, because in fact there's a straightforward translation of a pattern matching function into a visitor, as long as you keep your objects "functional", ie. treat them as variants. For instance, let's say we are constructing an evaluator: //the Expression type public abstract class Exp { public abstract Val Visit(IVisitor v); } //the type of Values public abstract class Val : Exp { } //the type representing an application public sealed class App : Exp { Exp e0; Exp e1; ...