Higher Logics

I've written about the limitations of C#'s equational constraints before . Truth is, I now believe that any such limits can be circumvented by a relatively simple translation. The result is less "object-oriented", as it requires a set of cooperating objects instead of being encapsulated in a single object. Let's take a simple, unsafe list flattening operation described in Generalized Algebraic Data Types and Object-Oriented Programming (GADTOOP) . This can be expressed in OCaml as: let List = struct type 'a t = Nil | Cons of 'a * 'a t let append l a = Cons(a, l) let flatten la = Cons(a, l) -> append a (flatten l) | Nil -> Nil end The argument to flatten, la, is a list of lists of type 'a. However, there is no way to express this in C# without unrestricted equational constraints as I described earlier. Here is the translation to C# from GADTOOP: public abstract class List<T> {... public abstract List<T> Append(Lis...

In previous posts, I had commented on certain non-sensical limitations in the C# type system, particularly with regard to equational constraints on generic type parameters ; these unfortunate limitations significantly reduce the expressiveness of well-typed solutions. Microsoft Research had actually already tackled the problem in their 2006 paper Variance and Generalized Constraints for C# Generics . Taking inspiration from Scala, they generalize class and method parameter constraints with arbitrary subtyping relations, and they further add use-constraints on generic methods. This increased expressiveness should address the problems I alluded to in my previous posts; if only the changes were integrated into the .NET VM and C#... :-) [Edit: figures that LTU already covered this paper ]

The benefits of advanced programmings languages are sometimes difficult to grasp for everyday programmers. The features of such languages and how they relate to industrial software development are sometimes hard to understand, especially since the arguments are couched in terms such as "referential transparency", "totality", "side-effect-free", "monads", "non-determinism", "strong static typing", "algebraic data types", "higher-order functions", "laziness/call-by-need", and so on. Many of these features are attributed to "pure" languages, but purity is also a nebulous concept. I will explain the importance of a number of these features and how they impact the everyday programmer's life. The Benefits of Referential Transparency Referential transparency (RT) is a simple principle with profound consequences. Essentially, RT dictates that functions may access only the parameters they...

Taking a break from my programming language blogging, I thought I'd describe a recent adventure with my new iPhone: reading PDFs. The iPhone can read PDFs, but insists on doing so only when reading the PDF from the network in some way, ie. via the mail client or Safari. Being the programming language enthusiast I am, I have plenty of papers stored locally on my machine which I'd like to read on the go, and network access is less than desirable for obvious reasons. Unfortunately, Apple disabled the obvious answer to local browsing: using the "file://" URI scheme. Very stupid of them IMO. Fortunately, I'm an "unscrupulous" person, because I jailbroke my iPhone so I could install third-party apps. So if network access is required to view PDFs in Safari, then I'll just have to access local files over the network! The way that's been done for over 20 years is available on the iPhone: a web server. Both Apache and LightTPD are available in Installer.a...

In previous posts [ 1 , 2 ], I argued that the visitor pattern was a verbose, object-oriented equivalent of a pattern matching function. The verbosity stems from the need to add the dispatching code to each data class in the hierarchy, and because the encapsulation inherent to objects is awkward when dealing with pure data. A single addition to an OOP language could completely do away with the need for the dispatching code and make OO pattern matching simple and concise: first-class messages (FCM). By this I mean, messages sent to an object are themselves 'objects' that can be passed around as parameters. To recap, functional languages reify the structure of data (algebraic data types), and they abstract operations (functions). OOP languages reify operations (interfaces), but they abstract the structure of data (encapsulation). They are duals of one another. All the Exp data classes created in [ 1 , 2 ] shouldn't be classes at all, they should be messages that are sent to...

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; ...