November 11th, 2007
I just read Hans-Eric Gronlund’s post on the pending extinction of programmers. The sky is falling in Software Development Land, it would seem: we’re all to be replaced by the very programs we’re writing. My natural reaction to his post is outright rejection. To my mind, there are too many fringe cases to account for, too many semantic nuances in spoken and written language to possibly pretend - even for a moment - that we’re just an academic paper or two away from being able to produce truly useful software from a high level specification. I wager that we’ll never see such a silver bullet come to fruition any time in the foreseeable future.
The Devil in the Details
Software development is not easy. You can trivialize it away all you want, and pretend that somehow the computer is going to know what you mean when you say “generate a report based on the data in the products table”. The devil is, and always will be, in the details. Simply put, you cannot abstract away details. Combine this with the fact that programming languages are constantly being born, evolved and killed. Ideas in languages decades old are being reimplemented in modern languages with a twist. We’re in an endless spiral of self-destruction: the software we write to day will be out of date - technologically speaking - by tomorrow because language X is no longer popular, or framework Y is now unsupported, or platform Z has crap support for multiple cores and so our software simply cannot scale. Our tools are constantly improving, but as developers we’re forever reinventing the software wheel - and that’s a problem caused by the overzealous nature of the software market.
The VM Wars
For example, the arrival of feasible byte-code-driven virtual machines is a wonderful thing: so what if language X is out of date? We can start using language W on Monday because it compiles down to the same bytecode. Platform Z has crap support for multiple cores? Hey, that’s cool: the VM we target also runs on another platform with better support for multi-core hardware. Sure, we’re still stuck with a shit framework, but hey: gift, horse, mouth. Virtual machines, while not fixing The Semantic Problem discussed by Gronlund, are a big step forward on other fronts.
How could the industry possibly screw such a theoretically wonderful idea up? Enter Sun and Microsoft with the JVM and .NET, respectively. Two entirely incompatible virtual machines with separate bytecode instructions and standard libraries. Brilliant. So now we all have to make a choice and hope that it’s the right one or we’re back to inventing wheels when the JVM is no longer supported by Sun, or .NET is superseded by an instruction set only feasibly implemented on specific hardware configurations. Even if both continue to exist forever and a day, the choice is still largely mutually exclusive: if you pick Java, your options for reuse are limited to Java solutions. If you pick .NET, you’re in the same boat in a different creek with the familiar uneasiness one feels in the absence of paddles in such a situation.
I wouldn’t for a second advocate blind homogeneity, but the two virtual machines are so god damn similar at a semantic level, they might as well be the same platform. It’s for entirely avoidable reasons like this VM divide that we’re doomed to the software development dark ages - and all that without even mentioning the words “software patent”. My prediction is that there will never be a magical breakthrough while we’re throwing away everything we produce every few years. We’ll be too busy fixing yesterday’s problem with today’s technology to ever think about a better way to approach the process as a whole. Even if we improve the process, we’re still doomed to the details, because - again - you can’t abstract away details.
No “Super Compiler”
Clearly, I’m a sceptic of the super compiler that Gronlund predicts (even when looking far, far into the future as he does), but I do see highly configurable software systems filling specific niches: systems like Drupal and Joomla are already filling this niche on the web development front. For bog-standard content-managed web sites, you can hand Drupal off to a half-trained monkey, slap a pretty theme on it, and you really can’t go wrong. However, even with such systems you are limited to the constraints of the systems themselves: the moment you want your site to do something unsupported out-of-the-box, the moment you want a certain feature to behave slightly differently, you’re back in the land of programmers. Further, what happens should PHP (the technology on which Drupal is built) disappear? Is Drupal then to be simply rebuilt in another language on another platform? Even if this is unlikely to happen in the real world: on a hypothetical level, why the hell should we need to do this?
Commercialization, Legislation and a Dull Sense of Deja VuÂ
To make matters worse, software development is outrageously commercialized. Even if we assume that a massive breakthrough in the software development tool set will eventually surface, you can bet it will be so riddled with patents that nobody will be able to legally use it anyway. It’s sad, but it’s the brutal truth. I don’t mean to be overly gloomy with this post: I love software development, and the possibilities for our profession are simply endless. It’s because I love my job that I look to the future with such pessimism: it’s unrealistic to think that - with the industry’s current approach to software development - we are going to see anything more than incremental improvement.
The more you try something new to the software development scene, the more it feels like we’re all doing a slightly different dance to the same bad song. I guess all we can do for now is keep on trying new things and hope somebody, somewhere stumbles upon Brooks’ silver bullet in the process …
Categories: Compilers, Languages, Software Development |
4 Comments
November 3rd, 2007
Writing a compiler is no simple undertaking. I’ve spent a few years on and off (mostly with the Python source code) trying to understand compiler internals on a practical level, and I’m only really only just beginning to learn enough to be able to manage some of the basics. So, in this article I present a detailed discussion of a simple compiler implementation that targets the Java Virtual Machine. I’ve been wanting to write a tutorial like this for a few months, because it’s exactly the sort of thing I wish I could have read a two or three years ago. So this is my little gift to all the other aspiring compiler nerds out there struggling (like me!) with the learning curve of compiler construction 
Prerequisites
You’ll probably need at least a fundamental understanding of Scala and/or Java to be able to follow the code samples in this article, but I promise to try and keep the code as simple as possible. I’d also recommend that you have at least a high-level understanding of how compilers tend to be structured internally i.e. if you don’t know what a “scanner” or a “parser” is, you’re going to get lost very quickly.
Obviously, you’ll want Scala installed if you plan to run the code. You’ll also want some sort of *nix toolchain available if you plan on using the simple build scripts I’ve provided. It’s not that hard to compile it by hand if you’re stuck on Windows or something like that.
Scala, the language
I haven’t covered Scala a whole lot on this blog. To be honest, I only started using Scala about two weeks ago. I’m already falling in love with it - you can think of it as a more expressive Java that straddles the fence the computing industry seems to have erected between functional and object-oriented languages. Yes, yes, there’s classes in Ocaml, the other functional/OO language you’ll hear me ranting about on this blog - but even in Ocaml, OOP is generally shunned in favour of a functional approach. Scala, on the other hand, is a beautiful blend of the two. I won’t go into the details of some of the more elegant aspects of Scala, but here’s just a few little things about Scala that I find especially nice:
- Scala is statically typed, but the excessive verbosity of Java is a thing of the past thanks to Scala’s type inferencing
- Scala has closures and anonymous methods
- Scala has what I can only describe as anonymous types: Neil Bartlett called this statically-checked duck typing
- Scala types can be aliased
- Scala code can use any Java class
- If some care is taken, Java code can easily use Scala classes.
Scala, the standard library
Scala comes with its own standard library (on top of the standard Java library) containing a slew of useful components. The Scala standard library comes with its own unit testing toolkit called SUnit, a database abstraction layer (think Scalafied JDBC), syntactic sugar wrappers around well-known Java collection classes, concurrent programming utilities and - the bit we’re interested in - a bunch of stuff useful to compiler construction.
For more information about the Scala standard library, please check out the Scala API documentation.
Our programming language
The source language will effectively be a glorified calculator with variables. The result of the final expression evaluated is to be printed to the screen. For example, something like this:
v = 5;
t = 10;
v + 6 * t;
Would output “65″.
High-level overview of a compiler
Irrespective of what language you write it in, the structure of a compiler tends to look something like this:
- Lexical analysis or Scanning - scan the source document to produce a stream of interesting tokens
- Syntax analysis or Parsing - transform the token stream produced by the previous phase into an abstract representation of the program structure
- Semantic analysis or Type Checking - analyse the in-memory representation of the compiled program to ensure it “makes sense”
- Code generation - generate the executable code from the type-checked representation of the program
The compiler presented by this tutorial won’t have an explicit “step 3″ - the language is simple enough that it should be impossible to write a syntactically correct, semantically invalid program.
Our abstract syntax tree
Our parser will be transforming the token sequence generated by the scanner in phase 1 to produce what’s called an Abstract Syntax Tree - a representation of the program as a structured tree. There’s plenty of literature available on ASTs out in the wild, so I’ll gloss over the details and provide you with the relevant Scala code for declaring the nodes in our tree:
abstract class Expr
case class Add(l: Expr, r: Expr) extends Expr
case class Sub(l: Expr, r: Expr) extends Expr
case class Mul(l: Expr, r: Expr) extends Expr
case class Div(l: Expr, r: Expr) extends Expr
case class Num(value: int) extends Expr
case class Store(id: String, r: Expr) extends Expr
case class Load(id: String) extends Expr
case class Program(body: List[Expr]) extends Expr
So for a simple example, imagine we have a simple program in our language that looks something like this:
3 + 5; 4 * 6 - 2;
We could manually express this as an AST using the above classes as follows:
Program(
List(
Add(Num(3), Num(5)),
Sub(
Mul(Num(4), Num(6)),
Num(2)
)
)
)
Of course, building ASTs like this isn’t quite what we’re after. In practice, we break AST construction down into a set of simple rules using Scala’s parser combinators. But more on that later.
Finally, you will want to note that the concrete elements of the AST are implemented as Scala case classes. Case classes will allow us to use Scala’s pattern matching features to inspect the AST in the code generation phase. This makes it really, really easy conceptually to see how the code should be generated.
The standard lexer
Scala comes with a standard lexical analysis class (StdLexical) which is capable of producing tokens for a simple Scala-like language. More than enough for our particular needs here. StdLexical knows how to parse numeric values, so all we need to do is tell the scanner which delimiters are important (i.e. a few simple arithmetic operators):
type Tokens = StdLexical
val lexical = new StdLexical
lexical.delimiters ++= Set("(", ")", "+", "-", "*", "/", ";")
That’s all the Scala code we need to write to configure our lexical analyser! Assuming your language doesn’t do anything too weird, StdLexical will likely be able to take care of the rest of the scanning process for you.
Pseudo-EBNF using parser combinators
EBNF is the notation de rigeur for describing programming language syntax in the compiler construction world. In theory, once you have written an EBNF description of your programming language syntax, writing a parser for it should be reasonably simple: you simply transcribe the EBNF into your language of choice and away you go. Unfortunately it’s not always that simple in practice, so people resort to using tools like yacc or bison to generate their parsers using EBNF-esque pattern-matching. The downside to these tools is that most have a fairly big learning curve.
Along comes parser combinators. Using combinators, it suddenly becomes possible to use EBNF-like rules in the compiler implementation language - a sort of DSL for parsers, if you like. Combinators appear to be especially popular in functional languages like Haskell (via Parsec) - although I’m still not sure what’s intrinsically special about functional languages that would make them more appropriate for combinators. If anybody could clear that up for more it would be much appreciated. In any case, Scala provides a parser combinator library as part of its standard API. Here’s the Scala code describing our simple little language, which also acts as the parser for our language:
def program = ((expr ~ ";")+) ^^ ((e: List[Expr]) => Program(e))def expr = assign | simpleExpr
def assign = ident ~ "=" ~ expr ^^ flatten2(Store)
def simpleExpr = term * (
"+" ^^ ((x: Expr, y: Expr) => Add(x, y))
| "-" ^^ ((x: Expr, y: Expr) => Sub(x, y))
)
def term = factor * (
"*" ^^ ((x: Expr, y: Expr) => Mul(x, y))
| "/" ^^ ((x: Expr, y: Expr) => Div(x, y))
)
def factor: Parser[Expr] = ("(" ~ expr ~ ")"
| ident ^^ ((s: String) => Load(s))
| numericLit ^^ ((s: String) => Num(s.toInt)))
Please note that, although I haven’t been explicit about return types for all of these methods they all return a Parser[Expr] - that is, a parser for an element of our AST. In fact, pretty much every method call you see here (including the operators!) is returning a Parser of some sort. If it’s not obvious, parser combinators - despite the scary name - have a very simple task: that of chaining simple parsers together to form a slightly more complex parser. These slightly more complex parsers can then be combined together as well, to form a slightly more complex parser again. Eventually you wind up with a tree of parsers that match one-to-one with the rules you provide in your combinator “grammar”.
It’s also interesting to note here that precedence is actually being enforced using the nested parsing rules: a factor will be parsed before any other rules because the factor rule is nested deeper in the parsing hierarchy than any of the others.
Now it probably goes without saying, but there’s a lot going on under the hood here. I’ll spend the next few sections trying to explain just exactly what all this actually means, but before we start it’s important that you understand …
Scala operators are just method calls
Many of the operators you see in the above source code listing are actually method calls on the objects preceding them. For example:
def assign = ident ~ "=" ~ expr ^^ flatten2(Store)
Could actually be rewritten thus:
def assign = ident.~(keyword("=").~(expr.^^(flatten2(Store))))
Obviously the first example is much more readable, but knowing this will make understanding what’s going on in the above code examples just that little bit easier.
Another bit of Scala magic: the parser combinators know to implicitly convert String arguments into a UnitParser using the keyword method. keyword accepts a string argument - the token it “expects” - and then discards the result.
As a side note, methods with more traditional names can be used as operators too:
import java.util.ArrayList
val list = new ArrayList
list add "Test" // the same as list.add("Test")
Finally, Scala operators - being methods - can be trivially overridden:
class Monkey {
var numBananas = 0
def +=(numBananas: int): unit = this.numBananas += numBananas
}
val m = new Monkey
Console.println(m.numBananas)
m += 5
Console.println(m.numBananas)
The “sequence”, “one-or-more” and “apply” combinators
Let’s take a look at the first rule in our program.
def program = ((expr ~ ";")+) ^^ ((e: List[Expr]) => Program(e))
The parser for this rule is expressed by this fragment:
def program = ((expr ~ ";")+)
Which, in plain old English, means: “a program consists of one or more sequences of expr and a semi-colon.”. Those of you familiar with regular expressions will probably have already guessed that the + combinator means “one or more”. The ~ combinator has a slightly more subtle meaning: it’s used to combine parsers together in a sequence. That is, within the context of this rule, once we have finished parsing an expr we would expect to find a literal semi-colon. If we do not, it’s a syntax error.
The final operator we’re covering here is the ^^ operator, which takes the result of the previous parser, applies a function to it, and returns the result (which should be an element of our AST) . Let’s take a look at the whole rule again:
def program = ((expr ~ ";")+) ^^ ((e: List[Expr]) => Program(e))
So the result of the one-or-more combinator is a list of expressions (List[Expr]). If parsing of the one-or-many rule succeeds, the ^^ takes the result (the said list of expressions) and passes it to the function passed as the operand on the right. In this case, we’re wrapping the list of expressions in a Program AST element.
So that should really be all you need to know about the ~, + and ^^ combinators. Please note that the annoying excess of brackets I use here is more for clarity than anything else - you could rewrite this as:
def program = (expr ~ ";" +) ^^ ((e: List[Expr]) => Program(e))
The “alternative” combinator
Take the next rule in our parser:
def expr = assign | simpleExpr
A relatively simple rule compared to the previous one. The only thing of note here, really, is the | operator, which creates a parser that can parse either of its operands: in this case, an assign or a simpleExpr. You can specify as many alternatives as you want. e.g.
def expr = assign | simpleExpr | ifExpr | functionDef | classDef | lambda
The way it works is by simply attempting to parse the leftmost rule. If that fails, it tries the next rule along. If that fails, it tries the next one along again and so on and so forth, until there are no more alternatives (in which case we have a syntax error) or one of the rules are successfully parsed. The net effect is similar to a logical “or”.
Something else of note is that we’re not using the apply combinator here. We simply don’t need to in this case, since both assign and simpleExpr both return a Parser[Expr], so there’s no need to convert the result of the parse into an AST element.
Simplifying your code with flatten[2-5]
The next rule - the “variable assignment” rule - appears to be pretty straightforward:
def assign = ident ~ "=" ~ expr ^^ flatten2(Store)
You’ve seen ~ and ^^ before - we’re just parsing a sequence and applying a function. But what’s flatten2?
The Scala parser combinator library includes a utility class called ImplicitConversions. This includes a couple of functions useful for writing cleaner combinators, including flatten2. Calling flatten2 here returns a function that takes the two arguments resulting from the sequence (the ident String and the expr Expr) and passes them to our AST Store constructor. Rewriting this using typical anonymous methods isn’t quite so clean:
def assign = ident ~ "=" ~ expr ^^ ((id: String, e: Expr) => Store(id, e))
It’s still readable, but still obviously much cleaner in the first example. Feel free to use either approach.
If you need to use flatten with more than two arguments, the library also provides flatten3, flatten4 and flatten5.
(Note: It should also be possible to have the flatten* calls happening implicitly, but I haven’t quite worked out how yet)
The “zero-or-more with separator” combinator
The next combinator we’re going to cover is similar to the one-or-more combinator, with a slight twist. First, let’s take a look at the next parsing rule:
def simpleExpr = term * (
"+" ^^ ((x: Expr, y: Expr) => Add(x, y))
| "-" ^^ ((x: Expr, y: Expr) => Sub(x, y))
)
Let’s get rid of the application combinators and look at the core rule to simplify things:
term * ("+" | "-")
That should be much easier to read. Now, you might initially think that this rule can be described as “a simpleExpr is zero or more terms followed by a plus or minus”. However, that’s not the case. In actual fact, it means: “a simpleExpr is zero or more terms interleaved by a plus or minus”. In order to parse the former, it would need to be expressed as something like:
(term*) ~ ("+" | "-")
But you probably don’t want that, and I digress
Let’s take another look at the original rule:
def simpleExpr = term * (
"+" ^^ ((x: Expr, y: Expr) => Add(x, y))
| "-" ^^ ((x: Expr, y: Expr) => Sub(x, y))
)
If there is a single term, it will be returned as the result for simpleExpr. If there are multiple terms, separated by “+” or “-” literals, they will be folded into a single Expr by recursively parsing the terms into Add or Sub AST nodes depending on which separator is encountered at each step. For example, given this source code:
5 + 3 - 2;
First, the parser will see a term, which evaluates a Num:
Num(5)
Next, the parser will see the literal “+”, and wraps the Num we just parsed in an Add with the next evaluated term (another Num):
Add(Num(5), Num(3))
Finally, the parser will see the literal “-” before wrapping the previous Add in a Sub with the next evaluated term (again, another Num):
Sub(Add(Num(5), Num(3)), Num(2))
I hope this clears up a potentially hairy construct. It’s really pretty simple once you get used to it, just keep at it.
More of the same
The next rule is exactly the same as the previous rule, except it expects factors (instead of terms) interleaved by either “*” or “/” (instead of “+” and “-”), and returns Mul and Div AST nodes (instead of Add and Sub nodes).
def term = factor * (
"*" ^^ ((x: Expr, y: Expr) => Mul(x, y))
| "/" ^^ ((x: Expr, y: Expr) => Div(x, y))
)
No further explanation should be necessary, but feel free to query it in the comments if you have any problems.
Parsing numbers and variable identifiers
Earlier I discussed the fact that parser combinators (and, indeed, parsers in general) simply take rules for simple parsers and combine them together to make more complex parsers. The factor rule is the simplest of all the parsers in terms of complexity, although the syntax expressing it is a little daunting:
def factor: Parser[Expr] = ("(" ~ expr ~ ")"
| ident ^^ ((s: String) => Load(s))
| numericLit ^^ ((s: String) => Num(s.toInt)))
The first thing to note is that I’ve explicitly stated the return type: because our parser is recursive, we must explicitly tell the compiler what our return type is going to be in the most fundamental element of our compiler. Now let’s break that rule down into more manageable chunks for discussion:
"(" ~ expr ~ ")"
This parser forces expressions in brackets to be parsed before anything else. As soon as a factor starting with a bracket is found, parsing starts near the top level again at the expr rule. Once the inner expr has been parsed, we expect a closing bracket. Easy.
ident ^^ ((s: String) => Load(s))
The ident method is provided by the Scala parser combinator library, which can handle typical variable names. If you need to handle any weird and wonderful characters, you may need to write your own.
Anyway, this simple rule parses a variable identifier (expressed as a String) and wraps it in an AST Load node. The only time that identifiers are not wrapped in an AST Load is when we’re doing assignment (see assign), where we use a Store node instead. The difference between Load and Store is semantically important to the code generator. I’ll discuss that more in the next part of this tutorial.
numericLit ^^ ((s: String) => Num(s.toInt))
As above, numericLit is provided by the Scala parser combinator library. It can parse simple numeric values (including floating point numbers, I believe). It returns a string expression of the number, which we then convert to an int and pass to the Num constructor. All numeric literals in our program will be wrapped in Num AST nodes.
Looking at the original factor rule again:
def factor: Parser[Expr] = ("(" ~ expr ~ ")"
| ident ^^ ((s: String) => Load(s))
| numericLit ^^ ((s: String) => Num(s.toInt)))
It doesn’t look so daunting any more. In simple terms, a factor is any expression wrapped in brackets, a variable name, or a number.
Code generation
Just to get something on-screen, let’s generate some simple bytecode:
def generateCode(e: Expr): String = e match {
case Num(v) => "push " + v + "n"
case Ident(id) => pushString(id) + "derefn"
case Mul(l, r) => generateCode(r) + generateCode(l) + "muln"
case Div(l, r) => generateCode(r) + generateCode(l) + "divn"
case Add(l, r) => generateCode(r) + generateCode(l) + "addn"
case Sub(l, r) => generateCode(r) + generateCode(l) + "subn"
case Assign(id, e) => generateCode(e) + pushString(id) + "bindn"
case Program(body) => body map(generateCode(_)) mkString ""
}
def pushString(s: String): String = "push '" + s + "'n"
The code generation method accepts an AST node (an Expr) and uses pattern matching to determine what code should be generated. This pseudo-bytecode is for a stack-based virtual machine, similar to the JVM. I’m not going to go into the details of how it works, because it’s quite self explanatory: effectively we walk the AST generated in the parse phase and generate simple pseudo-bytecode instructions depending on the type of the AST node. Arguments to operations like add, sub, mul & div are passed in reverse order. When the node we’re processing contains child nodes, we generate code for them through simple recursion.
Hooking the lexer up to the parser and starting compilation
Finally, to kick of the compilation process we use the following code:
program(new lexical.Scanner(Console.readLine())) match {
case Success(e, _) => Console.println(generateCode(e))
case Failure(msg, _) => Console.println("[FAILURE] " + msg)
case Error(msg, _) => Console.println("[ERROR] " + msg)
}
Here we simply instantiate a new lexical.Scanner instance (recall that lexical is an instance of StdLexical from the Scala standard library). Our call to program here actually returns the Parser[Expr] combinator constructed from our set of parsing rules, which then has its apply method called with the scanner as its one and only argument. It is the apply() call which starts the actual parsing of the input. This is possible thanks to functor-like syntatic sugar made possible by Scala conventions.
Once the Parser object has finished the parsing process, a ParseResult case class is returned. We use pattern matching to determine the outcome of the parsing process: ParseResult can be an instance of any one of Success, Failure or Error. Success obviously means that parsing completed successfully. The other two obviously indicate parsing failures and other problems in the combinators. Assuming parsing completes successfully, the root node of the AST (a Program instance in our parser) is provided as part of the Success case class. We then simply generate code for the AST and print it to the screen.
Click here to download the source code for part 1. Just for kicks, I’ve included a simple Python “virtual machine” in the download below which takes the pseudo-bytecode generated by this compiler and “executes” it in case you want to test it out. You can run the compile/execute toolchain using the following command:
script/build; script/run "v = 1; n = 2; v + n * 5;"
Thanks
This massive post was in no small part inspired by this document, written by Adriaan Moors. I strongly recommend you give it a read for a more formal introduction to Scala’s parser combinators by somebody who’s probably been doing it a lot longer than I have.
Part 2
Thanks for taking the time to read this tutorial. If you enjoyed it, drop me a line with some suggestions and/or improvements. I’m always open to input. In part 2 I’ll be discussing code generation with BCEL and providing the source code to the final, JVM-targetted compiler discussed in both tutorials. See you next time!
UPDATE: No part 2 yet, but part 1.5 is here!
Categories: Compiler Construction with Scala and BCEL, Compilers, Scala, Software Development |
6 Comments
October 3rd, 2007
Welcome to part two in my series of Ocaml tutorials! There was an overwhelming response to the first tutorial in the series and I have taken plenty of suggestions on board for this and future tutorials. In this instalment I’ll be introducing the list data type and the very useful List.iter function from the Ocaml standard library.
An Introduction to List Initialization and List.iter
Here’s the source code we’re going to be breaking down:
let main () =
let seq = ["a"; "b"; "c"] in
List.iter print_endline seq ;;
let _ = main ()
Looks scary, doesn’t it? It’s actually quite simple, but we’ll get to the source code in a moment. First, let’s see the program’s output. Save this file as tmhoo02.ml and run it like so:
$ ocaml tmhoo02.ml
You should see the following:
a
b
c
Now, let’s take a look at the interesting bits of the source code:
let seq = ["a"; "b"; "c"] in
As you (hopefully!) learned in part 1, the let syntax binds the variable seq to some expression. The in keyword indicates that this binding is a named local expression whose value to be discarded when the function exits (think “local variable”). But what exactly does that expression mean?
["a"; "b"; "c"]
This is the most direct way to initialize a list in Ocaml. Each element in a list is separated by a semi-colon. This particular list has three elements: the strings “a”, “b” and “c”. As our list comprises of string elements, we can say that this is a string list. Note that unlike some dynamically typed languages (e.g. Python and Ruby), every Ocaml list element must be of the same type: you have a list of string elements or a list of integer elements, but you simply can’t mix the two. Honestly, it won’t compile.
List.iter print_endline seq ;;
Here we’re calling the iter function of the List module - a module which is bundled as part of the Ocaml standard library. This function takes two parameters: the first is another function that accepts a single parameter, the second is a list.
As you might suspect, List.iter iterates over the list, passing each element in the list to the function one by one. To word it another way, inside List.iter we’re calling print_endline for each element in our list to the equivalent of: print_endline “a”, print_endline “b”, print_endline “c”. This explains the output of our example program.
Finally:
let _ = main ()
main is evaluated here and its return value (the <em>unit</em> value) is ignored by the underscore wildcard. You’ll notice in part 1 I omitted everything up to the equals operator but, at the behest of others who know better, I’ve included it here in part two. I’m not going to say anything more about it, other than the fact that the underscore wildcard is a simple but powerful construct you’ll likely become very familiar with at a later date. If you’d prefer to use the syntax from part 1, that should work too (but don’t come crawling to me when other Ocaml programmers come down on you like a ton of bricks ;)).
Advanced Discussion of the Type System
As a sneak preview into Ocaml’s type system, I can tell you that List.iter isn’t restricted to string lists. In fact, it can work with lists containing elements of any type. However, because each element of the list is passed to the function given to List.iter as the first parameter, that function must accept a parameter the same type as a single element in the list. Since print_endline accepts a string, we must use a string list. Or: since we’re passing in a string list as the second parameter to List.iter, the function passed as the first parameter must itself accept a string as its sole parameter.
Confused? Read that last paragraph again carefully. If you still don’t understand it, don’t worry too much: we’ll cover Ocaml’s type system more in the next few tutorials.
Until Next Time …
So that wraps up tutorial number two. I’ve already got parts three and four in the pipeline and I can tell you they introduce a fair bit of new material. Take your time trying to understand what was covered in this tutorial and post a comment or two if you have any suggestions, questions or improvements.
Categories: Functional Programming, Ocaml, Software Development, TMHOO |
No Comments
September 11th, 2007
Okay, sorry to get all touchy-feely on what’s mostly a technical blog - but here we go.
I’ve just read an article by Jonathan Rauch which was both reassuring and, at the same time, a little offensive. As an introvert myself, I could very much relate to what Jonathan was saying and I think a lot of what he had to say was spot on. However, his assertion that introverts (<em>innies</em>)are somehow more intelligent, reflective and all-round more intellectually and emotionally sound than their extroverted counterparts is a great big pile of blathering crap. I was embarrassed to hear him say as such and apparently truly believe it. So in response to his sweeping generalizations, here are a few of my own:
We’re NOT implicitly more intelligent, we’re just private
Innies think a whole lot. And we keep it all to our quiet little selves. Every single living day, thoughts occur to people - irrespective of whether they’re introverted or extroverted. These thoughts may range from, “What colour shirt will I wear to work today?” all the way through to doozies like, “Why are we here?”. Extroverts are not talking puppets, and most definitely have ideas and thoughts as deep as any introverts. The simple difference is that an extrovert is likely to mention such thoughts in passing as part of a larger conversation. Meanwhile, an introvert may take private joy in contemplating the colour of his/her shirt or the meaning of life all to him/herself.
Extroverts are not necessarily idiots. They’d probably tell you so, too.
We’re not always level-headed
Sometimes people get angry and annoyed. Sometimes they overreact, or get embarrassed, or hurt, or cry. You’ll find this true for all types of personality - wallflower, social butterfly and in-between. Emotionally volatile introverts may give the impression of level-headedness by virtue of the fact they don’t necessarily interact if they’re not “on” in a social sense.
Maybe we’re slightly more independent than the average extrovert (in a very loose sense)
I know as many needy introverts as I do needy extroverts. I’ve seen the extroverted go introverted when in emotional pain, and the introverted tell anybody who’ll listen about their dog dying. I guess the introverted may come off as a little aloof and detached, but it’s not because we care about you any less.
Perhaps one thing that may be true about introverts and extroverts, though, is the innie’s comfort within themselves: to be perfectly happy in silence and solitude.
Does that make us more independent? Too deep for me to think about at this time of night
We’re not more refined (or at least I’m not)
Often my awful Aussie drawl creeps out (I got that from my mother - imagine an Australian version of Fran Drescher). I sometimes struggle to use “proper” English when speaking. I rarely shave (I try, I really do!). On weekends, showers become an optional chore. My shoebox apartment is a fucking mess. No, it’s not because I’m a programmer - I know plenty of refined programmers! - it’s because I’m a bit of a slob. So are lots of people, introverted and extroverted alike. Extroverts are not slobs, wankers or rednecks by default.
More sensitive? Pah!
Rubbish. What about drama queens?
One might argue that introverts are more sensitive because we think about our feelings so god damn hard. The fact is everybody has feelings and we all experience them to varying degrees. How we express these feelings is another matter entirely. To designate introverts as somehow being more susceptible to human emotions shows both ignorance and a little narcissism.
Off-the-cuff tips for understanding an introvert
- Just because we don’t come to dinner doesn’t mean we hate you, nor is it necessarily because we’re lazy. Sometimes we just feel like we need a day to ourselves because we spent yesterday with Bert and last night with Betty. It may surprise you, but this takes a certain amount of effort from us when we’d really like to just sit down and relax for a few hours.
- Chances are your introvert loves to party, but being guilt tripped into going to a party when they’d prefer to be doing something else damages the introverted soul.
- If an introvert says he’ll come to your shindig and then pulls out at the last minute, it’s likely that such a decision wasn’t made lightly. Either something important is keeping him away, or he feels like his presence would be detrimental to the party.
- We love to talk - really, we do - it’s just not always so easy for us to know what to say. (Disclaimer: Other innies may feel differently!)
- Sometimes we just like time to be with ourselves and our own thoughts. Nothing personal.
Please don’t get the wrong impression of us innies from Jonathan’s article. He almost hit the nail on the head, but instead just wound up stomping mercilessly on the toes of pretty much every extrovert who might happen upon his somewhat harsh article.
Categories: Life |
No Comments
