Skip to content

6 Features of the Next Best Programming Language

As I’m about to start my PhD studies here in a couple days, I thought it might be interesting to put down my thoughts about what would make a very strong contender for “best” programming language by listing the features this language would have. In a few years time, I can (hopefully) return to this list and see how my opinions have changed.

General-purpose

To start off, I should mention this PL has to be general-purpose because otherwise how could it be “best”? The original title of this post was “Building a Perfect Programming Language” but really languages will always favor expressing some concepts over others. There isn’t one that’s perfect for everything. That said, this language should be able to fill the most needs, and do so with minimal effort.

Bare metal

Some may disagree with me and say that I spent too much time looking at the language shootout. Really, though, this comes down to being truly general-purpose. If you can’t be compiled to the bare metal, you can’t be used in things like embedded devices, operating systems, device drivers, high performance computing, scientific computing (large-scale)… really any performance-bound application. It’s not an accident that both web browsers and web servers still use languages like C/C++.

Zero compile time during development (aka Show me the REPL)

This may seem to contradict the previous point, but languages like Python, PHP, and Ruby have really shown us, it’s important for a sizable sector of programmers to be able to tests out different ideas quickly to shape their mental models of how the app should work. This requirement also stems from the original general-purpose requirement above. If the language doesn’t work for the sector of programmers that need a very tight feedback loop, then it’s not general-purpose.

How can this be accomplished with also being bare metal? Languages like Haskell and Common Lisp use what’s called a REPL or read-eval-print loop. This gives the programmer a way to plug into the brains of the language and try out ideas at what resembles a bash prompt.

Applications must be verifiable

There are two main circles of thought in program verifiability: full coverage unit testing and automatic verification.

Unit testing, pushed heavily by agile programming figures like Bob Martin and groups like the Ruby on Rails. There are a few flavors on this theme, but the end goal is the same: an informal executable spec that can demonstrate that for some cases your application performs correctly.

On the other side of program verifiability is automatic verification, the most popular of these is static typing. Strong type systems, like those found in Haskell, Scala, or OCaml (and to a lesser extent C++ and Java) are built to make requirements of your program expressible as types. Using types in this way makes up a formal, but incomplete, proof of the correctness of your application.

So, between unit tests and automatic verification with static types, which should we choose for our “best” language? I’ll give you the cheeky answer: “How much do you like debugging?” If you’re like me, you hate it, so the more the compiler can catch the better. Others will want the compiler to be more relaxed, especially when prototyping.

What we want is a dial on the compiler, some setting that tells it how much to enforce formal methods on the user to prove that the application works correctly. For “launch the missiles” type applications, the programmer can crank it to the max and require total application verification. For the web application you’re building for your bowling league’s website, perhaps a lower setting would be sufficient.

Implicit parallelism with visual profiling

I’m going to give you a million dollars and put you at a casino table. The bet: “Will computers be more parallel or less parallel in the future”? You’ve got to bet it all in one direction, which do you pick?

If you bet on “less parallel”, you can focus your efforts on meeting the needs of your users with the type of hardware we have now (4 cores or less), using the languages we already have available (namely C/C++), with minimal effort. Good to go.

Let’s say computers, starting tomorrow, had a 1000 cores. Now, plan how you’re going to get the edge on your competitors who will also be scrambling to use this newly found 1000 cores of awesomeness. Who is going to get the edge, and how? You might say “but my application doesn’t need 1000 cores, it runs fine on 1.” That’s fine, but imagine the number of new features your competitors can add leveraging all that new power.

Explicit parallelism, the kind where you’re literally spawning threads, locking locks, and passing messages, has two serious disadvantage: you need to know where and how to make your application parallel. Implicit parallelism, the kind where loops are performed in parallel for you, has its own serious disadvantage: you don’t know where the compiler will make something parallel.

Enter “implicit parallelism with visual profiling” – along with the compiler’s ability to make code parallel, the programmer needs a way to view the code as it runs to make sure the performance is there. A visual profiler gives you the ability to do this kind of probing to find the bottlenecks in your application.

So why did I pick implicit over explicit here? Let’s say that the “sky is falling” alpha geeks are wrong, and that we aren’t entering a massively parallel age. Tomorrow, Intel comes out with a new single-core that runs 10x faster than the current processors. Why should you have to maintain explicitly parallel code when the processors aren’t using it? That’s just extra work and (in all honesty) probably something of a maintenance nightmare. If it’s implicit, you at least have the option of going parallel again in the future without being pressed to maintain it in the interim.

Readable

I highly recommend Barbara Liskov’s OOPSLA talk (a reprise of her Turing award lecture). No, it’s not stuffy, it’s awesome, watch it.

Two points really got drilled home to me watching the talk: 1) Why aren’t there more women in computing, esp. programming languages? We could use them. 2) Programs always, always, always should be readable.

How do we make our “best” language readable? Probably the best way is to try to avoid being unreadable. Features like a giant number of operators, unnecessary concision, operator overloading, and syntactic extensions are all two-edged swords. Yes, for some minority readability actually goes up, but the time investment required to get to that stage is prohibitive for programmers at large.

Conclusion

There we have it, six features for the next best programming language, and there no doubt could be others. The functional programming camps, high performance camps, scripting language camps, and just about everyone else likely have their own two cents for what should be in the list. When it comes down to it, really only one things matters for this next best programming language: it gets the job done.

Posted in Thoughts.

2 comments

By jonathan – January 8, 2010

Dive into Google’s Go Programming Language

Google’s Go programming language hit the blogo-/tweeto-spheres with a splash yesterday.

Let’s take a look at some of the features that set it apart from other languages:

Pedigree

I was cautiously optimistic first diving into Go after seeing some of the authors. Ken Thompson and Rob Pike both have impressive resumes, and their work in languages like C and Newsqueak helped shape some of my thoughts as I was first starting to do serious research in programming languages.

I say cautiously optimistic because the pedigree also had quite a C/Unix bent to them, which isn’t exactly known for its strong UX.

Let’s Get Started

In Rob’s excellent, albeit rapid-fire, intro video he starts us out with “hello, world”. 

package main

import fmt "fmt" // Package implementing formatted I/O.

func main() {
  fmt.Printf("Hello, world; or Καλημέρα κόσμε; or こんにちは 世界\n");
}

A couple of things jump out:

  • It’s unicode. Hey, no surprise, since Rob worked on UTF-8.
  • It’s scared of letters. No surprised, since it comes from Unix, the land of /tmp and /usr.
  • Capitalization matters. Here the caps on ‘Printf’ tell us that it’s a public function/method.

Variables and Declarations

Let’s look a bit further. The next stand-out we come to is variable declaration. To declare variable in Go, we switch the position of type and varname:

var s string = "";

Where in something like Java/C# we would have done:

string s = "";

The reason for this switch comes from years of experience with C’s pointer syntax. Take this example:

char* s, t;  //s is a pointer, t is not

To eliminate this, the type goes last at the list of variables. One might well ask, “couldn’t they have changed the semantics of the declaration, since they are creating a new programming language?” Yes, one might well ask that.

Variable declaration can be considerably shortened using a witness (this trick is also used in ooc):

s := "";

Here the ‘:=’ means “declare and set the variable to the type and value given”.

Inheritance and Interfaces

There is no inheritance in Go. Verily, there was much rejoicing.

In its place, it uses a riff on the concept of Java interfaces (but used in a way similar to Haskell’s type classes). The big takeaway with Go’s implementation is that it allows inference of interface compliance. Meaning, if you create new interfaces, you don’t have explicitly say “implements” on your existing types. If they meet the requirements they are said to implement the interface.

Goroutines/Channels

Knowing Rob Pike’s previous work in Newsqueak, I already knew I was going to see a comeback of this feature. Let’s look at an example from the website:

var sem = make(chan int, MaxOutstanding)

func handle(r *Request) {
    sem <- 1;    // Wait for active queue to drain.
    process(r);  // May take a long time.
    <-sem;       // Done; enable next request to run.
}

func Serve(queue chan *Request) {
    for {
        req := <-queue;
        go handle(req);  // Don't wait for handle to finish.
    }
}

The keyword "go" in front of a function call turns it into an asynchronous call. In order to communicate once its been invoked, we use the notion of a channel (where those strange "<-" operators show up). Each channel is typed, and represents a synchronized stream. When a receiver reads from this channel, they will block until data has arrived. The sender will also block until a receiver has successfully received the value (you can create buffered channels, but by default all channels are synchronous).

Methods Separate From Types

We use this in ChaiScript as well, so it was cool to see another language pick up the torch. The gist is that the struct and the methods that work on it are separated. This allows you to create new methods on existing classes without having to dig through the code of the class. Taking a look at an example:

func (file *File) Read(buf []byte) (n int, err os.Error)

The first part after the 'func' is the receiver for the method. In most languages this would just be an implied 'this' pointer, but for some reason Go requires it to be explicit. The type of the receiver tells the compiler what class you are extending, and the rest is a normal Go function prototype. Again, recall that capital letters mean something, and here this method is public.

Consts are Arbitrary Precision

A const number in Go has the precision you give it, and will not truncate until it's assigned to a variable with lower precision. This is a nice touch, the compiler should be able to find the best representation for the number, as opposed to forcing the programmer to find one.

Stuck in the 80's

For all that Go has, ummm, going for it, it does have a few strikes against it:

Global Variables

The short of it: Go has them. Why?

The long of it:

Yes, I can understand, coming from the C background you are used to doing cute tricks that you and other coders who grew up in the 80s know how to do. It's not the 80s anymore. Am I allowed to say it's ironic that it also supports unit tests out of the box? There I said it.

Goto

I wish I were kidding. Come on guys.

No Exceptions

Pretty much every language on the planet now has them. Does Go? No. Perhaps this came from Google's own aversion to exceptions. Like them or hate them, something is better than nothing, and Go's current invariants story is pretty weak.

Sigils

Perl has them, but these days most languages don't. Go has them:

  • Pointer: *
  • Slice: []
  • Address: &

Whether they make it easier for the code to read and use is open to debate.

Pointers

Go doesn't have pointer arithmetic, but it does have a pointer type. Unlike C#'s notion that value types and reference types are implicitly separate, Go follows the C style of making them explicit (see sigils above). Is this more precise? Yes. Is it more complicated? You decide.

No Generics

It might have taken a bright functional programmer to help push generics into popular languages, but the switch has been thrown. Go, as of yet, lacks them. Rob Pike, in his video, comments that some of Go's other features fill some of the gaps left by not having them, but it remains to be seen how much they will be missed.

Conclusion

Will Go stand the test of time and shine amongst other languages? Who knows. They've thrown together some interesting, thought-provoking ideas that no doubt will spawn debates and spin-off projects in the days to come.

Posted in Rant.

1 comment

By jonathan – November 11, 2009

Cults of Done, Evolution, and Fun

With the recent abrupt disappearance of one of the Ruby’s most exotic (and famous) writers, _why the lucky stiff, speculation began about what caused the disappearance and why he chose to pull the plug on so many of his websites. I’d rather not add to the speculation as to why he might have left, knowing less than most people who worked with him or knew him. Instead, I’d rather talk about the process of creating and experimenting with ideas, and why there is little value in judging their worth beyond asking the question “am I enjoying working on this?”.

As people in Getting Things Done and Cult of Done will tell you, once something reaches some kind of “done” state, it’s, well, done. There isn’t a “think about whether or not you wasted your time, that other people do better work or have better ideas, or should I release this to the public and bare their ridicule?” stage.

Any desire to measure the awesome-ness of the project by ourselves really short circuits a much larger process that is going on, which we’re only a small part of. The act of releasing projects to the world, so that others get ideas from them and release their own projects is itself a sort of on-going evolution. Ideas mutate, they’re cloned and modified, the ones that suck less survive and get used by other people.

Absolutely none of the project’s survivability comes from our judgment of how cool or original it is. Simon Peyton Jones, in his talk on how to write a good research paper, says that if he had to wait for a great idea before writing a paper, he would never write one. That thought is true of most creative perfectionists. The fallacy is to think that the beautiful mind that came up with the idea is also strong enough to guess how useful the idea might ultimately be. While the idea was something you could hold in your head, predicting usefulness takes being able to get into everyone else’s head. If you can read other people’s minds and see into the future, please email me, I want to talk. But then, you already know that.

Not being a mind reader myself, I’ve picked up a new habit. Whenever I start a new idea, I ask myself if working on it is fun. If it’s fun, I keep going, and a bit later I ask if it’s fun again. If, for some reason, it stops being fun, unless I’m almost finished, I drop the idea. “How would you ever finish anything,” you might ask, “since you’re bound to hit speed bumps that are less fun cross”.

There are really only two types of speed bumps:

  • Those that only diminish the fun a little while you work over, or around, them.
  • Those that suck all the fun out of the project once you hit them

You ask the question “is this still fun?” so you know which of the two you’ve hit.

Imagine going to a foreign country. The longer you stay there, the better you’ll know where things are, how to speak the language, and the customs of the people. But if you’re not having fun, you won’t feel like embracing the culture and language, in fact, you’ll probably just get up and go somewhere else.

The same is true of projects. While you’re enjoying working on something, and spending time doing it, there’s a kind of on-going evolution in your brain. Steadily you’re getting re-wired to be better at what you’re working on. The fun you’re having is the fuel for that progress.

When we feel like we’re running out of fuel, it’s likely because we’re no longer having fun.

Posted in Thoughts.

No comments

By jonathan – August 22, 2009

What’s So Important About Embeddable Scripting?

…and why do we care?

Over the last few weeks, when I’ve tried to explain ChaiScript to someone, I’ve inevitably wanted to say “isn’t it obvious?”, knowing full well that, in fact, it’s not. With any luck this article will make it at last more obvious why embeddable scripting is a natural side effect of wanting flexible applications.

Design what?

Ideas always start smaller than they end up. The joy of creating your first ‘hello world’ version of your new idea inevitably gives way to the balancing act of creating a larger application.

The main problem scaling simple examples like ‘hello world’ to larger applications is that in scaling the application we lose much of the readable simplicity we started with. Where we once had one or two lines, we soon have pages of GUI component initialization. Then, we learn initializing components isn’t good enough, we must organize our code to be more modular, because we need places to put changes as they come in.

The “Two Groups”

When we look back at the example we find a clue as to why complexity scales so rapidly. If the project never had to change, it would never need new code. Obvious, right? Admittedly a fairly useless observation given that projects change all the time. Therein lies the key, and if you’ll allow me, a route to a possible solution.

Let’s imagine sorting a project’s requirements into two groups: in one group we put the requirements which are fundamental to our system that change only occasionally, and in the other we put requirements that change fairly regularly. Attempting to handle both types of requirements in a static, and fairly rigid, manner puts the brakes on the train and code cleanliness comes crashing to a halt, giving the kind of infrastructure explosion we talked about earlier.

The rise of dynamic (read: less rigid) languages and their focus on test-driven development aims to conquer this explosion with rapid development techniques, and that community has gone a long way in being successful in this regard. Where they’ve fallen short is that it becomes harder to prove your system is correct without a plethora of unit tests, tests that duplicate the type checking, structural verification, and semantic warnings that are standard in most static systems.

When, as an engineer, I see two camps with strengths and weaknesses, I’m tempted to ask the question “can we have both?” Indeed, in some sense, we can.

Embedding for fun and profit

Let’s take our earlier example and again sort our imaginary requirements into fundamentals and changing requirements. Additionally, let’s describe the changing requirements with a set of primitives that rarely change, and add these primitives to our set of fundamental requirements. Once we’re done, these two groups become the two areas of our application. The static system (in our case C++) will handle the fundamental requirements. The dynamic system (in our case ChaiScript) will handle the changing requirements.

The two systems work together, allowing us to field change requests in not one, but two possible ways. The fundamental parts get the benefit of static analysis and compilation. The traditional drawback of long compile times is mitigated by only forcing a compile when a fundamental changes. The dynamic system handles the more dynamic side of the project, allowing the user to express these changing rules in a simple way without recompiling.

What is it for?

Doing some brainstorming, it’s not difficult to come up with an incomplete list of traditionally dynamic areas in applications:

  • Configuration: let the script handle the settings
  • Business logic: let the script hold the rules based on the fundamental principles of the domain. This could mean anything from what a particular sale price is, to what steps must be taken to confirm a user’s identity
  • Remote procedure calls: let the script be the remote user’s view of the system. We see this in web services, for example
  • Testing and verification: let the scripts be your runtime verifier. You can add new verifications to a live system

No doubt there are many more, some general and some specific to particular applications. The important thing is that we have a new tool, and, as is often the case, you don’t realize it was missing until you have it.

Posted in Thoughts.

Tagged with .

No comments

By jonathan – July 15, 2009

ChaiScript 1.0 Released!

What started as the next part of the “Creating a Programming Language” series has grown into a full-fledged project with the help of my cousin, Jason. He had begun experimenting with what could be exposed to scripting languages from C++ in a type-safe way, and after he mentioned what he was working on, an idea began to grow. Soon, code took the place of ideas, and two months later, we see the fruit of his initial idea.

So, what have we got?

Early on, we decided a few things about ChaiScript: it had to be type-safe (yet dynamic), it had to easily embed into C++ apps, and it had to be useful. To see how we ended up, let’s look at some examples:

Type-safe, yet dynamic

The one big reason for type-safety is that we wanted to make sure the user could bring over objects from C++ land and return them safely, which meant we couldn’t allow any type-foolery of the kind you see in weak-binding dynamic languages like this example from Python:

i = 3
i = "bob"
print(i)

What type is ‘i’?

In ChaiScript, once the variable gets a value, that variable promises to only be set to values of that type from then on. This has an added advantages of generally making source code easier to read. But don’t let that fool you, ChaiScript is still very much a dynamic language. Take this example:

var arr = [1, "bob", 4.4]
print(arr[1])

Arrays can have mixed types, and it’s perfectly fine. When the print() function is called, we look for a print that can accept the type it’s given. Which brings us to the next point: what else does type-safety give us?

Dynamic method dispatch

ChaiScript, and the underlying C++ dispatch system, allow for very powerful ways of calling functions. Let’s start with the most simple: the overloaded function call. Let’s say you’ve registered “print_me(int)” and “print_me(string)” in your C++ code and want to be able to see them from your ChaiScript code. This is handled automatically, without any extra work on the part of the programmer.

Function overloading by itself is a bit tame, everyone already does that. ChaiScript goes a step further, and takes a page from Clojure, allowing the programmer to add their own dispatch functions. Let’s take a simple example:

def print_num(x) : x == 0 || x > 1 {
  print(x.to_string() + " units")
}
 
def print_num(x) : x == 1 {
  print(x.to_string() + " unit")
}

Now, when we call print_num(x), the print statement that is called is based on the value of x, not just its type.

C++ Embeddable

ChaiScript has the advantage of being made specifically for C++, and one benefit of this is that it’s header-only (in the same vein as you often see using Boost). The immediate advantage to this is that it’s trivial to add another path to your include paths, add an include line, and be ready to do scripting without working with libraries, intermediary setup languages or preprocessors.

Useful

The idea of being “useful” is hard to pin down, as what’s useful to one person might be less useful to another. What we aimed for in ChaiScript is a good balance of functional techniques with techniques you’d be used to in scripting languages. The system has support for a handful of STL types, its own iteration based on ranges, a number of composible functions borrowed from Haskell’s prelude, and a seamless merging of functions registered on the C++ side with those created in the script side.

Will the end result be useful to other programmers? Time will tell. It’s a safe bet, though, that Jason and I will be using it in our projects to come.

Posted in News, Projects.

Tagged with .

No comments

By jonathan – July 13, 2009

Some Cool Ideas from PLDI ‘09

CEAL: A C-Based Language for Self-Adjusting Computation [paper]

I’d never heard of self-adjusting computation before seeing this talk, so the talk blew me away twice over. The general idea is this: say you have a long-running computation, one that takes upward of 30 mins to run to completion, so you only run it when you have to. Then, say you only made a small change to the input. You’d like to be able to only re-run affected parts of that computation by tracking the AST branches affected by that change. A very cool idea, and especially cool in the field of live-coding, where programs are adjusted on the fly as they run.

Yet another tick in the “we need more purity in our programming languages”[1] column as doing something like this is no doubt encumbered by the presence of any side-effects.

Verifiable Composition of Deterministic Grammars [paper]

A couple really interesting ideas in this paper and the research leading up to it.

The first observation is that scanning (lexing) could be made context-aware and be driven by the parser. The dragon book hints at this possibility in talking about breaking parsing down into FIRST(x)/FOLLOW(x) transitions. The next logical step that August took was to say “why not minimize the scanner’s lookahead table to only acceptable parsing tokens?”

The big win comes when context-aware scanning is merged with a parser capable of extending and merging external grammars into a single coherent grammar (the kind of thing you’re likely to see when handling multiple DSLs at the same time). Because tokens in different contexts will naturally be of different types (eg. your null might be a reserved word but my null might be a variable name), we capture this by only looking ahead for tokens appropriate to the current grammar. This allows us to prevent premature creation of tokens. The familiar scenario given in the talk was parsing “>>”. In the C sense it’s a right shift. In the C++ sense it’s not only the right shift operator, but the embedded template marker as in “std::vector<std::vector<int>>”. The C++ specification doesn’t actually allow this because it’s ambiguous, so the two > must be separated with a space, but with context-aware scanning it isn’t necessary to enforce this limitation.

This is definitely an idea I want to play around with in my own projects.

Implementation of the Memory-Safe Full ANSI-C Compiler [paper]

The title says it all. I haven’t had time to sit and read through the paper or the thesis, but the ideas in the talk were pretty wild. That he was able to maintain most of the performance of bare-metal C, give the programmer full C idioms (including casts, pointer manipulations, and expanding structures), and still ensure memory safety seemed pretty serious[2] .

Automatic Generation of Library Bindings Using Static Analysis [paper]

I have to admit, when I was first sitting through this talk I caught myself thinking: “what’s the big deal?” But, in my defense, this was the last day of the conference, so my head was thoroughly nuked by then. This is a big deal, though. The notion that you could tease out programmer intentions inside of limited languages like C looking at common coding idioms and proceed to use those to generate library bindings is such a useful idea. The time saved for any project doing FFI like SWIG or languages like Haskell should reap considerable benefits.

And more…

Many other talks are worth mentioning, and I’m sure as the conference settles in I’ll remember other good examples. Despite the total mind nuke-age of sitting through almost every session (I only missed about 20-30 mins of the entire conference), I’m definitely glad I went.

  1. During the conference there were a lot of ticks in that column for security, parallelism, traceability, and static analysis. [↩]
  2. Other talks attacked the safety problem from different directions, so no doubt this is a very tread area. [↩]

Posted in News, Research.

1 comment

By jonathan – June 20, 2009

Diamond Inheritance

Oops, in the last article I didn’t quite explain diamond inheritance clearly (or all that correctly). My cousin was kind enough to set me straight.

Reposting the emails:

Me:

Okay, you’re right, I kinda mucked up that example, do you have a better one?

I mean, say you had this:

class Grandfather {
 int beardLength;
};
 
class Dad : Grandfather {
 public: Dad() { beardLength = 10; }
};
 
class Mom : Grandfather {
 public: Mom() { beardLength = 12; }
};
 
class Me : Dad, Mom {
};

I don’t see the issue here. You’re calling the Dad constructor first,
before the Mom one, so the beardLength should be 12… unless I
totally didn’t catch the twist in your message.

Jason:

ok, so in your example:

Me me;
 
me.beardLength; // error ambiguous
 
int i = me.Dad::beardLength; // i = 10
int j = me.Mom::beardLength; // i = 12
 
// Grandfather is actually constructed twice and exists twice in the object
// If however, you did this:
 
class Dad : virtual Grandfather;
class Mom : virtual Grandfather;
 
//Now all instances of Grandfather are merged, so:
 
int i = me.Dad::beardLength; // i = 12
int j = me.Mom::beardLength; // i = 12
 
// Because Mom was initialized second, like you said

The idea I was trying to get at in the last post was mostly correct, but not quite. The diamond inheritance occurs when the state inherited comes from the same source, so edits now mutate the same merged state regardless of where the methods originated, hence the ‘diamond’. In the example in my previous article no state is actually merged, the two variables stayed separate.

Posted in Research.

No comments

By jonathan – May 19, 2009

Brainstorming Traits

Read an interview with Martin Odersky about the goals of Scala. In it he says:

Another thing, which people sometimes criticize, is that Scala has both traits and classes. A cleaner design could make do with just traits. There have been some clean designs that only have traits and give up the notion of classes.

One would think I would have done my homework and studied traits thoroughly by now. Hmm, due diligence v. coder laziness. I think we know which one often wins. Yet, after my rant against classes and my general unhappiness with Minnow’s feature system, it was time to do some reading.

First, what are traits and how do they differ from classes and interfaces?

From the paper, we know that traits have a few properties:

  • They have no state (object/class attributes)
  • They have method implementations
  • They have method requirements that must be met when all traits for a class are mixed together
  • They have a flattened interface, just like classes. For example, when you call x.doSomething(), you don’t know which trait .doSomething() came from (though you do when you are composing the traits together).

No State

To avoid the worst issue of diamond inheritance, traits do not allow state. Why is that? Quoting the paper:

Whereas method conflicts can be resolved relatively easily (e.g., by overriding), conflicting state is more problematic. Even if the declarations are consistent, it is not clear whether conflicting state should be inherited once or multiply

That’s almost English, but if it sounds garbled, here’s another way to think about it:

Let’s say we have two classes:

class Height {
  double value;
 
  double getHeight() { return value; }
}
 
class Width {
  double value;
 
  double getWidth() { return value; }
}
 
class Area extends Height, Width {
}

Whose value do we use? Here we’d like to not mix them in, but you can imagine cases where you might want to mix in one or the other. If we did end up picking one attribute over the others, let’s say Height’s value, what do we do with Width’s methods that reference the Width version of value? This is not only messy, it’s also dangerous – any user of this class would have to worry about their attributes or any subtle side effect of ordering.

To help prevent this spaghetti, traits limit two things: 1) they can’t have state and 2) they can’t reference others’ state directly.

Method Implementations

The difference between traits and, say, Java interfaces, is that traits give an implementation for the method instead of just its prototype. Why is this difference important? Let’s jump to the next point to see why.

Method Requirements

If you’ve spent much time with templates in C++, C#, or Java, you might already be familiar with the concept of method requirements. Imagine that you can write a method and leave bits of it marked “fill me in later”. For instance, let’s redo our Area idea from earlier:

int getArea() {
  return (this.getHeight() * this.getWidth());
}

When you make that definition, you may not have the .getHeight() and .getWidth() methods. Later the compiler will try to find methods that match during trait composition where the traits that make the class are merged together. If matching definitions are found, the compiler happily continues and points the method calls at the matching methods it found.

This is what allows traits to have default method implementation: they can still refer to “fuzzy” implementation details that are resolved later.

Flattened Interfaces

Probably one of my biggest annoyances with Minnow’s features is that the end result isn’t flat. You’re used to flat interfaces from class-based inheritance – you can call x.doMethod() regardless of what class .doMethod() comes from. In Minnow’s features, the interface is not flat, requiring you do something like: x.Thing.doMethod(). This requires more typing, which is nearly always a bad thing.

Traits let you mix together different features, and the end result is just as flat as a class-based approach, even if there’s a lot of mixing going on.

Minnow’s future?

I haven’t decided whether or not this is a good direction for Minnow. There are two big places for it: replacing feature-based objects and giving actors some amount of polymorphism. It does have some pretty sizable benefits:

  • They naturally compose and stay loosely-coupled. By being able to “fill in” the methods of a trait, traits can be layered such that the outside acts as the uniform interface for the internals. This gives us the polymorphism we know and love.
  • They’re small. This was one of the Minnow feature’s strong points: they were little ideas that you melded together to form more complex models. Being small meant they were likely much more reusable and easier to reason about.

And some disadvantages:

  • They’re not as widely understood as classes.
  • They’re fairly new. The original traits paper is from 2002[1], and only one major language, Scala, uses them.
  • They aren’t a silver bullet. You still have to handle method name conflicts via aliasing or overrides.

Where we’ll end up is anyone’s guess, but it’s a good bet I’ll be mulling over the details for the next few days.

  1. Though the idea of mixins had been around for longer [↩]

Posted in Research.

Tagged with , .

No comments

By jonathan – May 12, 2009

Creating a Programming Language – Part 5: Sifula in Practice

The expression prompt

Now that we’ve got the interpreter up and running, it’s time play with it and see what the language is like in practice. As an experiment, this allows us to really dig into the design choices we made and learn what was good (and not so good) about them.

Starting with the basics:

Expression> 1 + 2 + 3
6
Expression> x = 1 + 2 + 3
Expression> x + 4
10
Expression> add x y = x+y
Expression> add 10 20
30

Hey, it works! Next, what if we play around with the fact that the functions are re-evaluated each time they’re called?

Expression> a = b + 10
Expression> a
Eval error: Can not find identifier: b
Expression> b = 12
Expression> a
22
Expression> b = 6
Expression> a
16

Intriguing. The ‘b’ it sees is whatever the most recent value is in the global variable namespace. As we change what the definition of the variables are, the functions value also changes. This technically would mean that the function is closed over the environment where the variables live – making these functions actually closures instead of pure functions. We didn’t exactly intend for this to happen, it just fell out of our design.

The next question you might ask might be: “does this have drawbacks?”

Drawbacks

I found two issues that I would consider drawbacks of our design, though you may find more as you play with it.

The first is that it’s all to easy to accidentally define a variable/function in terms of itself. For instance:

Expression> z = z+1

That seems all well and good, but we know from earlier that the definition doesn’t do much beside set up the expression for us. Once we ask for z’s value, “something bad” will probably happen. Sure enough, it does:

Expression> z
Segmentation fault

Without some way of preventing the infinite recursion, the call will keep going until we run out of stack space[1].

The other drawback I found led to some unnecessary confusion. Take this example:

Expression> add x y = x+y
Expression> add 10 x
20

Wait a second… how did that work? What’s the value of ‘x’ in the second expression?

I discovered this oddity when trying to iron out a couple bugs in the eval function. At first this looks like a bug, but on closer inspection what’s actually going on is this:

  1. “add x y” is defined
  2. “add 10 x” is executed
  3. first, the ‘x’ from “add x y” is bound to 10
  4. this newly visible ‘x’ is visible to evaluator, so it next sets ‘y’ to the value of this newly defined ‘x’

This kind of squirrel-ly subtle behavior is something I would chalk up as a user interface bug, though it’s not a bug in the implementation sense. Instead, it’s this kind of subtlety that will bite you one day when the planets align just right.

Going forward

There’s a lot to add to the language if you want. New operators, sanity checks, if statements… you name it. Now that we’re over the hump of actually having a working demo, we can poke and prod it to our hearts’ content.

The Sifula Project

  1. Overview of the first project
  2. Lexing Sifula
  3. Parsing Sifula
  4. Evaluating Sifula
  5. Sifula in Practice
  1. We can prevent this by creating a function that checks for this scenario, explicitly walking the expression tree when you define a new variable/function. The programmer may want recursion, though, so disallowing it may be bad as well [↩]

Posted in Research.

Tagged with .

No comments

By jonathan – May 7, 2009

Creating a Programming Language – Part 4: Evaluating Sifula

Before we begin: if you’d like to follow along looking at the complete source code, the source to all the “Creating a Programming Language” toy languages (as they are made) will live in their own space on GitHub.

In the previous article we built a tree of tokens that represented our line of code. In this article we’ll take the final step and evaluate this tree.

The evaluator

Our evaluator for the token tree will be fairly straightforward, but as you’ll see in this article and the next, it’s also where a good bit of the subtlety enters the language, depending on how and when we choose to evaluate the trees.

For our approach, we’ll focus on two statements types in Sifula – expressions and definitions – and how they relate to each other.

Expressions

To understand the basics of evaluation, let’s start with an example. The expression “3 + 4″ comes to the evaluator as a small tree with a ‘+’ that branches into ‘3′ on the left hand side and ‘4′ on the right hand side. It follows that one way of handling the evaluation of this small tree is to create an evaluator that handles the plus operation. To do so it takes the following steps:

  • Evaluate the left hand side. Confirm that the result you get back is a number.
  • Repeat the above for the right hand side.
  • Finally, add the results together and return a new result that represents the sum.

This works for all our basic mathematical operators (’-', ‘*’, etc).

Let’s take a moment to see this in practice:

Result eval_add(NodePtr exp, std::map<std::string, NodePtr> &symbols) {
    Result answer;
    answer.value = 0;
    answer.type = ResultType::NUMBER;
 
    for (unsigned int i = 0; i < exp->children.size(); ++i) {
        Result child = eval(exp->children[i], symbols);
        if (child.type != ResultType::NUMBER) {
            throw EvalError("Expression could not be solved: " + 
                exp->children[i]->text);
        }
 
        answer.value += child.value;
    }
 
    return answer;
}

Definitions

We’ve only talked about numbers, but the language also allows us to define and use variables and functions. For example, the statement “x = 3+4″ defines the ‘x’ symbol as the expression “3+4″. To tie the symbol to the expression, we’ll use a hashtable/map:

std::map<std::string, NodePtr> symbols;

In effect, the symbol on the left hand side of the equals sign becomes the lookup key in our hashtable. The expression on the right hand side is then its value. When an evaluator later comes across this symbol, it’s queried from the table and the resulting expression (here called NodePtr) is evaluated in its place[1].

Functions

In keeping with our mantra of simplicity, functions behave very similarly to symbols. They live in the same symbol table and are also stored as the same expressions, with a few tweaks:

  • We create a new node type called NodeType::FUNCTION, which bundles the function parameters and the expression together.
  • When evaluated, we discover the name of the function and find its definition. The first node of the definition is the NodeType::FUNCTION node, which allows us to bind the expressions passed in the function call to the parameters of the function definition. This lets us re-use our symbol table for parameters as well.
  • After the function runs, we roll back the symbol table to the previous state and continue evaluating.

Let’s look at how we define symbols and functions in code:

Result eval_equate(NodePtr exp, std::map<std::string, NodePtr> &symbols) {
    Result answer;
    answer.value = 0;
    answer.type = ResultType::STATUS;
 
    if (exp->children[0]->text == " ") {
        std::vector<NodePtr> args;
        NodePtr node = exp->children[0];
        while (node->text == " ") {
            args.push_back(node->children[1]);
            node = node->children[0];
        }
 
        NodePtr func(new Node());
        func->type = NodeType::FUNCTION;
        while (args.size() > 0) {
            NodePtr arg = args.back();
            args.pop_back();
            func->children.push_back(arg);
        }
 
        func->children.push_back(exp->children[1]);
 
        symbols[node->text] = func;
    }
    else {
        symbols[exp->children[0]->text] = exp->children[1];
    }
 
    return answer;
}

You’ll notice that most of this function is taken up by the code to parse a function definition. The arguments are pulled off and stored, the new Node is created, and the definition is completed. Variable definitions look meager by comparison, as they only need the one line hashtable entry.

The main evaluator

Now that we know how different aspects of evaluation work, let’s take a look at what drives evaluation:

Result eval(NodePtr exp, std::map<std::string, NodePtr> &symbols) {
    switch (exp->type) {
        case (NodeType::OPERATOR): {
            if (exp->text == "+") {
                return eval_add(exp, symbols);
            }
            else if (exp->text == "=") {
                return eval_equate(exp, symbols);
            }
            else if (exp->text == " ") {
                return eval_funcall(exp, symbols);
            }
        }
        break;
        case (NodeType::NUMBER) : {
            return eval_number(exp, symbols);
        }
        break;
        case (NodeType::IDENTIFIER) : {
            return eval_identifier(exp, symbols);
        }
        break;
        default :
            throw EvalError("Unknown type for: " + exp->text);
        break;
    }
    return Result();  //this is never called
}

This bit of code acts as the backbone to our evaluator, calling out to the other evaluation functions depending on the type of the node it’s looking at. In turn, other evaluators can call back to this backbone. For example, in the “3 + 4″ expression, the ‘+’ evaluator uses this main evaluator to evaluate its two children.

How does it feel?

With that we’ve actually finished our toy language and should be able to stand it up and play with it. In the next article, we’ll drill into what we’ve made and draw some conclusions.

The Sifula Project

  1. Overview of the first project
  2. Lexing Sifula
  3. Parsing Sifula
  4. Evaluating Sifula
  5. Sifula in Practice
  1. This way we re-use the token tree as the definition of our symbols, instead of coming up with a whole new representation [↩]

Posted in Research.

Tagged with .

No comments

By jonathan – May 7, 2009