Curly Programming Language

I'm a seasoned coder who doesn't know anything about compiler design. So, I'm building Curly in order to learn the ropes. It will be a slow moving, but daily process. “It does not matter how slow you go so long as you do not stop.” - Confucius

[curlylang]

Generating an Atomaton

Thanks for the input!  I went with nil.  It is more concise and less to type.

I also finished the NFA code.  Currently it only builds the NFA structure; it can't execute anything.  So, I was playing around with it and I thought I'd implement part of a scanner by hand, just for a test.  Here are nodes for scanning string literal, integer, and identifier.

It dumps out its data in GraphVis format, which produces a cute little picture like this.  Next up is to have it generate an NFA from regex. 

[curlylang]

To Null or Nil?

I'd like some input if you have the time.

I was working on the NFA today, and since simple Curly doesn't have lists or maps, I was implementing the transition collections as a linked list.

Then I realized, I don't have a "null" or "nil" literal.

So, I'm trying to decide which keyword makes more sense.  I've used null for years in C and Java, but I've read that nil makes more sense linguistically (null means none, while nil means nothing).

What do you guys think or prefer?

[curlylang]

Eating Curly Dog Food

Tonight I was hoping to hack out my first NFA, but instead I worked on the bootstrap compiler more.  Working in the language makes the compiler bugs crawl out of the woodwork. 

I had to fix being able to use a struct element as an array and vice versa.  I had also forgotten the trailing apostrophe on character literals.  That doesn't sound like a lot to fix, but tracking down the errors was kind of tough when all Coco/R gives you is "Expected '.' on line 28" to work with as an error message.

It is rather fun though, molding my own language.  It has also made me think about how to implement smarter error messages in my own compiler.

[curlylang]

Today I started digging into how lexers work. Lexers are the first step of turning source code into executable. Their job is to take a stream of letters, symbols and whitespace and convert it into chunks of text which represent the various parts of the language. These chunks are called tokens. At…

[xjtian]

I’ve always been interested in the theory and practice behind compilers, so it’s just my luck that I find someone working on their own compiler AND PL at an early stage in the game… real fun to read about in general.

I did a small project with a regex engine based on automata recently, and the tough part was that I had to parse the regexes with a recursive descent parser before I could feed them into the Thompson algorithm. It’s almost circumlocutory in that you have to parse the tool that you’re going to use to help you parse/lex stuff.

I enjoyed this article about parsing regexes with a recursive-descent parser: http://matt.might.net/articles/parsing-regex-with-recursive-descent/. It drives you in even more of a circle because it uses a CFG to define regexes ;).

I also remember non-minimized DFA’s of regexes actually being much slower than the corresponding NFA because the NFA has O(n) states but the corresponding non-minimized DFA can have O(2^n) states. To me, it seemed like it wasn’t worth the effort in converting the NFA from the Thompson algorithm to the DFA, but there must be a reason for it that I’m missing.

[curlylang]

Great comments, and thanks a bunch for the link with the regex CFG.  That’s pretty meta!

As for NFA vs. DFA, from what I’ve been reading, NFA do have less states, but require more iteration over them, or more memory usage, depending upon implementation, in order to find the correct route through the graph.

[curlylang]

Lexers, Finite Automata, and Regex

Today I started digging into how lexers work.  Lexers are the first step of turning source code into executable.  Their job is to take a stream of letters, symbols and whitespace and convert it into chunks of text which represent the various parts of the language.  These chunks are called tokens.  At this point the lexer's job is done and the parser works on the new stream of tokens.

From what I've found, lexers almost always use small machines called Finite Automata to accomplish the task.  There are two kinds of automata used in lexers: non-deterministic and deterministic.

I read on another site that "NFA are easy to construct, difficult to implement.  DFA are easy to implement, harder to construct."  Fortunately, you can convert NFA to DFA and get the best of both worlds.

However, automata are represented as a graph; just a bunch of nodes (or vertices), connected together with a web of simplified machine instructions called transition functions.

So, how can I change my rules for lexing source code into a graph the automaton can use?

Regex!

This next site I found talks about the "Thompson NFA" and has some great images showing how you can construct an NFA from regex patterns.  It only describes converting simple regex to NFA not a true lexer which produces a stream of tokens.

Close enough.

Immediately, I thought of a way to break each token to be scanned into it's own regex and then add a special code to the regex parser in order to call that from another regex.

The algorithm was coming together.  The resulting grammar file would look a bit like the Coco/R grammar, and as I did a bit more googling, I discovered that this was called a recursive descent parser.

Excellent!

So, next up is to try and make a basic NFA graph, then try and convert it to a DFA with a working machine.  After I get my head around that I'll work on a regex parser to generate the NFA graph from a regex grammar.

[curlylang]

Curly Jars of Goodness

Tonight I finally have all the pieces together!  I added things like compiling to a single file, calling the java compiler on that file, and calling the jar program to create a single Java executable.

It all works so beautifully.  I am very proud of myself.

So, now I can write a (simplified) Curly program, and run

java -jar curlyc.jar HelloWorld.curly

and it will generate a HelloWorld.jar file! I then follow that with a quick

java -jar HelloWorld.jar

to have Java run the program for me.

Curly is alive!  All is well.

Good night tumblr.

[curlylang]

From Curly to Java

Wow!  I'm serious surprised and impressed at how easy it is to make a grammar for a simple language.  I have the grammar for this basic version of Curly done and it's generating Java source!

It was mostly easy peasy, but I hit a couple of bumps along the way.

I started out getting the tokens set up.  However, getting the string and char literals right was a bit tricky.  When scanning a string literal, you need to allow any character that is not a quote (end of string), but also not a backslash (in order to catch those crazy C escape characters).

Coco/R uses what is called an LL(1) parser.  That means it can't tell what is coming up next in your code.  It can only read the token it is currently looking at.  Because of this, I had to rearrange some of my grammar expressions in order to make it work.  

In Curly, the start of a function call, a struct element access, or an array element access, all start with a "Symbol".  Coco/R doesn't like having multiple pathways with the same grammar element like that.

xyz(); xyz.a = 0; xyz[a] = 0;

When the compiler is looking at "xyz" in each one of those statements, it gives an error because it can't look ahead and tell what kind of statement it is going to be. To remedy that you need to group the statements together into a combined grammar entry (like InvokeStructArray) with the common symbol first, then an option for either an open paren, a dot, or an open bracket.

It is kind of a pain having to group things like that and I can imagine it gets worse as the language gets more complex.  LL(1) seems like a very primitive way of doing things.  Maybe there's something better.  I'll look around.

[curlylang]

C is for Curly

I've worked out a simplified version of Curly that I can use for bootstrapping the first version of the compiler.

It works like plain C, with just functions, structs, and a few basic types: char, string, and int.

It looks kind of like this:

native func println(str:string); struct Message { hello:string; bye:string; } func main(args:string[]) { msg:struct Message; msg.hello = "Hello World"; msg.bye = "Goodbye World"; i:int; i = 0; while i < 10 { if i < 5 { println(msg.hello); } else { println(msg.bye); } i = i + 1; } }

The native functions are just an easy way to access things like saving files and printing to console.

You might notice some of the influences of ActionScript and GoLang.  I like the lack of parenthesis on the while and if statements.

Currently there is not an increment operator "++", but that will be added at a later date.  Also, there is no for statement.  I'll just use whiles for the time being.

[curlylang]

Hello Coco/R

So I fought with ANTLR.  Well, more like drowned in the documentation.

Then I found Coco/R.  This is just what I need.  It is really easy to set up for Java, just a single jar file with no dependencies.

I found the grammar language to be very straightforward and it allows you to inject java code into the grammar tree, which is perfect for basic source-to-source translation.

So, I've set up a project and I'll be spending the next couple of days making a simplified and probably ugly version of Curly from which I can create the next version of it.

[curlylang]

Bootstrapping by Source to Source Translation

I was thinking last night about how to bootstrap Curly.

Of the options given here, only two really apply to new languages:

Implement a starting version of an interpreter or compiler in another language.

Write the compiler in Curly then hand-compile it in a non-optimized way to get something that just works; then use that to make an optimized version.

I was hoping to avoid writing the compiler in two languages, so that leaves hand-compiling, which honestly sounds like a lot of crazy work.

But then, I started to think about ANTLR more and I looked a bit into how the grammars work.  I believe I can create a grammar for a baby version of Curly that has only the absolutely necessary language elements for me to write the compiler.

I can then use ANTLR's output to generate the same program in Java.  I essentially would be only implementing a small portion of option 1 above, and I'll let ANTLR and the Java compiler do the rest.

So I guess I need to get enough of a working knowledge of ANTLR to generate the data I need.

Maybe I'll google around first and see what other options I have for a parser generator.

[curlylang]

Back to the roots.

I don't really like it when someone says something like, "You need to do it this way because it's been proven and tested as the best way."  It's not that I'm a rebel and want to buck the system, or that I naively think that I can figure out a better way.  It's just that I love to learn the theory behind things.

So, today I started browsing around looking where to start with making a compiler.  Most answers I found talked simply about lexers and parsers and then promptly said that you don't want to waste your time on those and that you should just download ANTLR3.

ANLTR3 seems like a great piece of software indeed.  Something that you need to download and install and spend a good time learning.  You can give it a grammar file which describes your language of choice and it will actually generate a parser for you.  I looked through the docs and found it a bit daunting. I'm sure I could grok it with time, but at the end I still wouldn't really know how lexers and parsers work.

So, I googled some more, and I stumbled onto a really neat article which included the code for a very early version of the C compiler.   I was surprised at how succinct it was.  I also discovered the concept of a self-hosting compiler, which embodies one of my goals for Curly. And I also discovered the chicken-and-egg problem of having a compiler which compiles itself and how to bootstrap.

I'm going to think more about bootstrapping and what is the best way to approach that for Curly.

[curlylang]

Why am I creating a programming language?

I have been programming now for almost 30 years in many languages and with many APIs.  One thing I have realized is that I really like curly-bracket (or braces) based languages.  There are a lot out there: C++, Java, Javascript, PHP, ActionScript, haXe.  Some are great, some lacking, some verbose and some loosey-goosey.

So why add another one?  Simple.  I WANT CONTROL, DAMMIT!!1

Yeah, I'm a control freak.  And, here are some of the things I would really like to have in my own programming language:

I want to be able to run it on multiple platforms without having to install a huge compiler or run-time components that require root privileges.

I want to be able to have a smart language that can infer types but that also keeps types strict.

I want to be able to target other languages like PHP or Javascript with an easy to extend source transformation module (without having to learn oCaml... yeah... I'm looking at you haXe) In fact...

I want the whole thing compiler and all written in Curly.

I want a package manager that can keep it's data in a non-administrative area and has the option of statically including a package directly into your code base for distribution or legacy reasons.

I want an IDE for it that can auto-complete, refactor code and present compiler errors while editing.

I want to type less while coding, but still have good assistance from the compiler.  (Duck-typing?  WTF, python? And you Java, with your abstract public static final transient volatile crap)

I want a native interface that's easy to work with for all target languages.

And of course, I want it curly.

There is another key reason for me making Curly.  I want to understand and experience the act of making a computer programming language.

So, here we go...