The Rewards of Creating a Programming Language | Hacker News Reader

The Rewards of Creating a Programming Language

mikedrivendevelopment.blogspot.com

I was hired (a long time ago) to write a language for a Very Large Telco Equipment Supplier in Canada in order to support their automated regression testing effort for their digital telephone switches.

It was called, ingeniously enough, "T" (no, not that "T"). As far as I (and cursory Google searches) know, it was never released to the adoring public.

I used lex and yacc (half jokingly referred to as 'ick' and 'yuck') and K&R C for the compiler and VM.

The particular type of testing we were targeting involved writing test cases that would read/write over serial lines to a telephone switch's console program. Therefore, the language needed to have good serial/terminal I/O, and it needed to have amazing string/pattern matching.

I wrote two features that I am still particularly fond of:

- regexps were a built in type. Strings were written like 'hi there' and regexps were written like `hi ..ere` - supported standard unix regexps

- associative arrays. Lots of languages have these now, like python's dict

The cool thing about it was how we tried to allow strings and regexps have a polymorphic relationship at the language level. The statements:

  x == 'some string' or x == `some [^t]ring`

would be valid for strings in x, though the regexp had other operators that didn't make much sense with strings. It got really interesting when we combined the regexps with the associative array:

  dict['hello'] = 4
  dict['help'] = 2

  dict[`he.*`] == [2, 4]   # true

I wonder how one would go about efficiently implementing such an associative array.

I suppose a trie + glue logic (regexp -> NFA -> DFA) could work, for classic (read: actually regular expressions) regexps at least.

I have wondered the same thing, but wasn't extremely concerned about getting it super-fast at the time. We had an existing, older language that was much loathed and quite slow, and we just had to beat it. And awk.

Just curious, did you specify order ?

dict[`he.*`] == [4,2] could also hold. Or maybe [...] was a set literal and not ordered list.

Interesting ideas, perlish in spirit, somehow less cryptic.

Was it published ? was there other ideas you could talk about ?

My code above isn't the exact syntax. I doubt I implemented array equality. I was just demonstrating that an array would be returned when indexing the dict with a regexp.

I know nothing was published or released. I actually left BNR/NT less than a year after the language went into production (going to say July, 1990) - I don't really know how long it remained there. Perl was popular, and Tcl was definitely a 'thing' in the lab at the time - the writing was on the wall for home-grown languages.

If you’re thinking of writing a language in earnest, you will create something much more valuable if you start from a novel semantics, and only then come up with a syntax to express those semantics, than if you were to start from syntax.

The world does not need yet another reskin of Java, but it could use new programming paradigms and new ways of solving problems.

As a learning exercise, implementing a language is worthwhile simply to gain the understanding that languages are not magic. To boot, you’ll pick up loads of useful techniques in the realms of parsing, data flow analysis, error reporting, and optimisation.

Agree. I'm (trying!) to do one, and now I only focused in the AST and trying to build the features. Is a waste of effort to rewrite parser/lexers/etc if the core is in constant change:

https://www.reddit.com/r/coding/comments/2ocw2r/how_to_creat...

If you're looking to build something that people will actually use, you're better off not doing anything novel at all, but rather combining novel ideas that have shown promise in research languages into a package that people might actually want to use for everyday programming.

There's a rule of thumb among language designers that your language should either focus on proving out one big language feature, or it should introduce zero new language features but combine new language features from a number of other languages. So for example:

Erlang introduced lightweight CSP-based concurrency. Go popularized it.

Haskell introduced typeclasses. Go and Rust popularize them (as interfaces and traits, respectively, the latter also influenced by C++ STL's concepts).

Cyclone introduced linear types. Rust popularizes them.

Smalltalk introduced object-orientation. (More precisely, Simula did and Smalltalk took it to its logical conclusion.) Java, C++, and Objective-C popularized it.

Self introduced prototype-based programming. Javascript popularized it.

CLOS (Common Lisp) introduced the meta-object protocol. Python and Ruby popularized it, particularly in their Django and Rails web frameworks respectively.

Usually popularizing a language involves a good deal of work that's not sexy, notably building up a large standard library, developer tools, a package manager, and a whole ecosystem around the language.

> There's a rule of thumb among language designers that your language should either focus on proving out one big language feature, or it should introduce zero new language features but combine new language features from a number of other languages.

This rule doesn't exist among language designers, at least the ones I hang out with. You'll find a mix of innovation and invention in most programming languages.

erlang's concurrency is actors, which is different from go's CSP. And I nearly spat out my tea when you said that Go popularized something Haskell did; and I haven't even had any tea today.

But didn't Go effectively popularize typeclasses through interfaces?

no?

Can you explain how? Obviously at least two people either disagree or aren't privy to the knowledge you hold!

I suspect a reasonable person might expect you to explain how you came to the conclusion that a language with a smaller or comparative user base / popularity to Haskell "popularised" type classes.

Huh, I interpreted it differently, as in questioning whether Go's interfaces have much in common with Haskell's typeclasses. But now I'm intrigued — does Haskell really have a larger or comparative popularity as Go? That would surprise me, but I don't have any data, do you?

It's remarkably difficult to find anything approaching hard numbers :-) However, I am going off:

* http://redmonk.com/sogrady/2015/01/14/language-rankings-1-15... (Haskell slightly ahead in their numeric ranking) * http://www.tiobe.com/index.php/content/paperinfo/tpci/index.... (Golang slightly ahead in their ranking) * Slightly more published books on Haskell that I can find (although obviously it's been around a lot longer)

I have no doubt that Go will eventually surpass Haskell in terms of popularity, and may even have a slight edge, but suggesting that Go popularized typeclasses smacks of fanboyism, and reminds me - in no small measure - of: https://www.youtube.com/watch?v=bzkRVzciAZg

> suggesting that Go popularized typeclasses smacks of fanboyism

I'm not exactly a fan of Go nor am I a fanboy, quite the opposite these days. I don't have to like go to mention that the way interfaces are used kind of accomplish the same thing as typeclasses.

I also feel that (sadly) Go is more popular than Haskell. Partially because of the number of Haskell programmers I've encountered in real life is much lower than the number of Go programmers I've encountered.

Why do you think they're similar? Is it actually specific enough that it couldn't apply to Pythonic duck typing, or Java interfaces?

There's a bit of writing on StackOverflow about it:

http://stackoverflow.com/questions/2982012/haskells-typeclas...

The main similarity is that 'methods' are defined 'outside' the data type they belong to. But there are a huge number of differences: Haskell's typeclasses are used for many things that don't look like methods at all, while Go's behave more like a classic OOP interface you'd find in Java.

So, perhaps superficially similar-looking, but they work quite differently in practice.

Duck typing (which is what Go supports) has absolutely nothing to do with type classes.

It's always worth pointing out that CSP is a language, rather than a concept. Perhaps "CSP-inspired" would be a better choice?

CSP is based on the theory of process calculi: http://en.wikipedia.org/wiki/Actor_model_and_process_calculi

>Haskell introduced typeclasses. Go and Rust popularize them (as interfaces and traits, respectively, the latter also influenced by C++ STL's concepts).

This is a really ironic thing to say considering Go doesn't have generics, rust doesn't have higher kinds, they don't support any sort of implicit (or global) way of using them as constraints.... are you sure you know what type classes are?

This may be true about Go, but Rust's traits were very similar to Haskell type classes and now are equivalent in power to Haskell's type classes with several extensions turned on (even though they lack HKTs).

As a side note although clunky HKTs are encodable in Rust and I plan on implementing them natively once we have landed a stable version of 1.0.

How do you enforce them as constraints on a method?

    pub trait SomeTrait { ... }

    pub fn some_function<T: SomeTrait>(arg: T) { ... }

> If you're looking to build something that people will actually use

Why bother? I mean, at some point some bigger "name-brand" language is going to take your feature and subsume it anyway. Why compete for mindshare?

If you really have an idea for some new language semantics, then skip the whole syntax phase: express your language as a DSL in another language you already know, use that DSL to write programs and libraries, and see if it helps you compared to not using the DSL. The great thing about this is that you can still rely on all the features and libraries of the parent language while you're doing this! Your DSL only gives you the option of using the new, extra semantics you wanted to test, where and when it adds a benefit.

Now, of course, this might not work if your idea is for a reduction in or purification of semantics—if, merely by having the option of "calling through" to the parent language, the value of your language semantics is destroyed. But if it's just an idea for a feature? Building an interpreter and defining a grammar and create a whole new ecosystem around it is putting the cart before the horse.

Saying that Go "popularized" type classes is ludicrous, especially from a language whose type system is weaker than Java's.

> Erlang introduced lightweight CSP-based concurrency. Go popularized it.

Erlang introduced fault tollerant concurrent programming. With isolated heaps (thus fault isolation) and a framework for supervision and distribution. Nobody has popularized that except Erlang so far.

Besides even if you want to talk about CSP, what Erlang has is "Actor" based programming. And even that fell out organically out of concurrency and fault tollerance rather than through academic channels or academic literature survey. Creators at the time didn't even hear about "actors" only years later someone associated the two together.

How come Go has popularized Type Classes?

They are nothing more than Objective-C protocols that served as inspiration to Java interfaces.

Indeed. Recently I was inspired to learn K, a language in the APL family. There aren't many implementations available, so I wrote my own. Doing this forced me to come to terms with a whole range of features I might have otherwise shied away from using.

Hi! Is your implementation available for use?

I'm curious - how did you test it for compatibility with the main K implementation?

Sure, here's the repository: https://github.com/JohnEarnest/ok

I don't have a rigorous approach for testing compatibility at present; My starting point was the K2 manual, and I've tried to get as many examples from that working as possible. I have been learning the language as I go, so often I don't realize functionality is missing until I stumble across an existing K program that doesn't work properly.

I'm targeting K5, which is unreleased, so there's a great deal of speculation. I think I have a decent subset of the functionality working now, but most of the time when I write new programs using it I still shake out bugs and unhandled edge cases.

Awesome. I started building a toy C interpreter to the k5 spec (http://kparc.com/k.txt) based on the k4 data structures (http://kx.com/q/c/c/k.h) and documentation (http://code.kx.com/wiki/Cookbook/InterfacingWithC). That k2 manual is a good find.

Cool! Nice to know that I'm not the only person trying to implement K5 from scraps and speculation.

It is certainly a fun puzzle; hopefully kOS is released soon to application developers.

Since you are playing in JS, you might also have a look at c.js (http://kx.com/q/c/c.js), which is the tool KX uses to translate between JS objects and k objects through web socket IPC with a k process (http://code.kx.com/wiki/Cookbook/Websocket). Might be useful to see how Arthur envisioned the k data structure in JS. Also, it would be kind of interesting to have a k5 process running in the browser talking with a k4 process running locally in the 32bit trial...

I wrote a language once where functions were not allowed to return values. All you could do was pass a continuation that could handle the results of that function. Totally impractical language, but it was fun and did force me to think out of the box.

The author says he turned to Coursera, but doesn't mention the course(s) he took, but I'm going to guess it's the the 'Compilers' class from Stanford[0]. I've heard good things about the course and the lecturer (Alex Aiken) so I really wanted to take the course while it was being offered but was too busy last year. I hope they offer it again this year.

https://www.coursera.org/course/compilers

I've listened to the lectures and they're awesome! he is a very good lecturer.

A self-paced version of that course is (still) available now:

https://class.stanford.edu/courses/Engineering/Compilers/Fal...

I did this class. It is quite challenging (and rewarding). If you plan to do it make sure to allocate a significant amount of time per week. My recommendation would be to do the Java version of the assignments over the C++ version, even if you know C++. The codebase provided is pretty crufty.

This is excellent: I recently worked through this class (at my own pace: you can register for past offerings). I made things a little harder than necessary by eschewing the provided framework code and writing everything myself, in go.

I found SPIM super-annoying, but managed to resist the temptation to build a better MIPS emulator. :-)

Highly recommend: writing a (very simple) compiler is no longer a black-art-seeming thing to me.

Oh, http://github.com/zellyn/gocool: I recommend you steal my tests (bash, sorry!) but avoid cheating too much on the actual meat of the exercises :-)

Thank you for this; cloning it now

I was able to only participate in a small amount of it, and came away with significant value in increased understanding.

Yeah, that course is awesome. I also took it in order to properly learn about compilers for my language design/compiler side project. I wrote about the experience here:

https://dirkjan.ochtman.nl/writing/2012/07/21/compilers-on-c...

Afterwards, I thoroughly overhauled my nascent compiler. It currently lives here:

https://github.com/djc/runa/

(It's a Python-like systems language, with a compiler written in Python targeting LLVM IR.)

Another interesting thing to try (and maybe complementary as well) is building an interpreter or compiler for a language you like, trying to match the spec and feature set as closely as possible, and (hopefully) gaining more insight into the tradeoffs the language designers made when deciding why things are the way they are.

Yes, I've written tools for existing languages, and found just getting the parser right to be a challenge, be it with Emacs highlighting, flex/bison, what have you. Real languages aren't as tidy as the textbook examples.

When I do PL these days, I always start with the editor; e.g. see:

http://research.microsoft.com/en-us/people/smcdirm/managedti...

Co-designing your editor with your language allows for a better experience.

You are right in that all of this is basically undocumented in textbooks. Even their presentation on on parsing is mostly unhelpful (if you want an error tolerant incremental parser for your editor, recursive descent works very well).

That is really cool. This focus on time is what draws me into the whole clojure/datomic world. We're ill equipped to handle it. Tools help.

Does time itself reveal itself as the horizon of being?

We can manage time one way or the other. Clojure does it with a focus on immutability, I'm doing it with a focus on mutability :)

One thing that is cool is how time is related to observation, the same thing that happens in quantum entanglement. If you don't observe the state of an object, time doesn't really exist.

I did that with Ruby[1]. I learned things nobody should ever have to learn. But I also came away with a much greater appreciation for the basic model it uses, most of the biggest warts are at the surface (flip-flops, bizarre rules around how arguments get passed to blocks when the block takes one argument, etc). The way metaclasses work is, imo, one of the most elegant object models I've seen for the amount of power it gives you. It only took a couple hundred lines of code to implement reasonably correctly [2]. And along the way, I wrote another language for expressing some of the higher level VM-stuff (object model, exception propagation, etc).

I definitely recommend targeting languages that already have robust test suites. It makes things a lot easier. I was going to do a JS implementation a while ago, and there is a pretty solid suite for that from the ECMA[3], but it's kind of hard to extract. One of the things that made ruby so fun was that the test suite that existed at the time was rubyspec, which is actually written in ruby. Just getting to the point where I could run the specs was a huge moment where the implementation reached a measure of usability.

[1] https://github.com/stormbrew/channel9 -- it's a perennial project for me, it can run an old version of mspec+rubyspec as a ruby 1.8.6 implementation. Note that I skipped the parsing, leaving that to an existing parser written in ruby, because parsing ruby is a bigger project than a ruby-compatible VM.

[2] https://github.com/stormbrew/channel9/tree/master/environmen... -- see class.c9s and object.c9s for the vm specific script the fundamental implementation of language features is written in.

[3] http://test262.ecmascript.org/

I wrote this a while back on creating your own language: http://digitalmars.com/articles/b89.html

As an aside, I'll note that working on stuff that I needed has fared quite a bit better than working on stuff that I was told others need.

Someone once told me something similar, "always be customer number one".

If you are a developer and you have never written a language, you owe it to yourself to do this at least once.

Writing a language (lexical, syntactic, semantic phase and then code generation) will teach you an incredible amount of things in much less time it would take you to read about these things.

What your language looks like is completely irrelevant, this is strictly about learning from the journey.

And once you've done that, make sure to mention it in your resume: I, for one, will instantly give you brownie points if you mention in your resume that you wrote a language.

I view writing a language as either a creative epiphany or evidence of psychosis, so when I see someone with a language on their CV I'm always careful to explore why they wrote it. Surprisingly often they think it's going to Solve All The Problems rather than allowing them to explore one of the deepest and most important parts of the programming art.

I've written little languages (mostly for generating code in other languages, which proved to be an interesting way to explore certain design patterns) but always shied away from going all in on a bigger language. Maybe when I retire...

I've been working on a programming language in my spare time, also. I call it OWL. Its not quite ready, but here's a link anyways: https://github.com/bsurmanski/wlc

OWL aims to be a low level object-oriented language without a garbage collector (albeit with reference counting).

The best 'example' program using OWL right now is a game I made for the 48 hour game jam, Global Game Jam 2015: https://github.com/bsurmanski/ggj2015

I agree with the poster that making a programming language from scratch is a great way to explore programming. On top of that, its a great experience seeing able to implement all of those features you wish were in your favorite language (or find out why they aren't).

> Notice how not a single variable in this code has a name. They all only have types.

Pretty cool, never even thought about this being possible.

It’s not a novel idea, but Wake does it quite well. Most variable names aren’t that useful—they’re just one of many possible syntactic ways to plumb values around.

I've been playing around with an idea to replace variable names with brands. So say you have an argument to a procedure:

    brand position <- Point

Position is a point, but is not a distinct type. You can document it centrally and not for each time it is used as an argument to a procedure or as a variable. E.g.

    def Set(position): ...

You have define brands before you can define your procedure, but multiple procedures can share brands they use to declare their arguments.

So position is like a typedef that you can use without a name, because it is self-naming.

Obvious problem:

   def Drawline(position, position): ...

Oops! We now need a position0 brand and a position1 brand, both of which are aliases for Point.

They aren't just type aliases, they actually have unique slots in the symbol table when used so...you define more brands :)

   brand position <- Point
   brand start-position <- position
   brand end-position <- position

   def DrawLine(start-position, end-position): 
       ... = start-position + ...
       ... = end-position - ...

But that is kind of annoying, brand composition as adjectives would probably work better:

   brand position <- Point
   brand start
   brand end
   def DrawLine(start&position, end&position):
       ... = start&position + ...
       ... = end&position - ...

Very natural language, and start/end can be used to qualify all variables that are starty or endy. The biggest problem with the approach is that you have to think ahead of time about what your variables mean, and they might become fairly verbose (so "start position" rather than "startp"). Also, when you get into the implementation, it is kind of tiring to think about what every local variable should mean, so maybe this only really works for procedural parameters and maybe to help define fields.

I've been thinking about this for awhile, but haven't put it into a prototype yet.

The canonical example is how it's done in Forth: Ask for a number and it's already on the stack. Ask for three numbers and you push onto the stack three times. Upside: Terse code. Downside: Stack juggling can be a big maintenance burden.

FWIW I've realized that in languages that are variable centric, an anonymous naming convention is often preferable to a human name because it centers one's concerns around the algorithm. After studying the options for a while I now flip between descriptive word style and "single letter and number." So I have a lot of "x0, x1, i0, s0, a0" in my function arguments. Where it's a record type, I'm deciding between abbreviation and descriptive - which ultimately depends on how often and densely I expect the data structure to be accessed(short names imply it gets used in a dense, idiomatic style).

Yep. I am working on a statically typed stack-based language, as I quite like the Forth style. Stack manipulation sucks, so I mainly use locals for auxiliary parameters, to get them out of the way of the main data structure or values that a definition is manipulating implicitly. For example:

    define do_the_thing (Foo bool -> Bar):
      -> should_log;

      if (should_log):
        dup log_foo

      foo_to_bar

      if (should_log):
        dup log_bar

That's how I find functions in Haskell! [1] Most of the time searching the type will give you the function you need.

[1] https://www.haskell.org/hoogle/?hoogle=%28a+-%3E+b%29+-%3E+%...

It kind of fits how we'd talk in natural language about many common fragments of code.

I mean, if I write a small function doSomething(inputDataString) then when talking about what the function does, I'd just refer to "the string" or "that string" as there really can be no more meaningful name to refer to that. If there are multiple such parameters, only then names start making sense.

Similarly for iteration constructs like java 'for (Foobar foobar : foobars)' - when you're talking about what is done with that single instance of foobar, you just refer to it as 'a foobar' or 'every foobar', and a specific name is often meaningless if you don't need to distinguish it from others.

I've recently discovered PEG.js [0] and prototyped a small DSL in the browser [1]. Amazing stuff! I've dealt with ANTLR [2] before, but PEG.js feels so much nicer although it may not be as powerful!

[0] http://pegjs.org/

[1] http://pegjs.org/online

[2] http://www.antlr.org/

Related side-project : http://peg.arcanis.fr

Like the demo version, but doesn't lock your browser with infinite recursion, and supports Ctrl+S! PegJS is a really great/fun tool.

PEG.js is definitely fun to prototype ideas in the browser.

My new love is Parsec [1] + doctest [2]. You start building simple little parsers, and build on top of them, plus inline testing makes it easy to write the parsers correctly. Also Haskell's algebraic datatypes and pattern matching make it nice to build and work with the AST. <3

[1] https://wiki.haskell.org/Parsec [2] https://hackage.haskell.org/package/doctest

I always wonder about the final conversion to assembly. Do you really need to learn all the instructions, the linking, the binary formats and all that stuff ?

My favorite way is to output C, which is conveniently human-readable for debugging. Many people also like the LLVM back end.

I new about that possibility but how efficient is it compared to other techniques ?

Nim is competing effectively by using this tactic. It's efficient.

It is the approach taken by Eiffel. Byte code interpreter for the IDE and compilation to native code via C for distribution.

Also how the first C++ compiler used to generate code.

When your top-down parser gets caught in an infinite loop, you'll need to convert the left recursion to right recursion. See here: https://en.wikipedia.org/wiki/Left_recursion#Removing_left_r...

Writing a compiler is a significant amount of work and should be pre-researched to avoid issues like the above.

I was reading something similar here about creating your own language using LLVM (and also using the Ruby bindings for LLVM as opposed to C++) ... http://macournoyer.com/blog/2008/12/09/orange/

I'm curious how people feel about syntax. I tend to think everything should be written in sexp (I like [s]ml syntax too though). Much like this http://cs.brown.edu/courses/cs173/2012/book/Everything__We_W...

Maybe I'm missing something, how many people felt that syntax made an idea pop differently and was part of the understanding ? To me it's often the opposite, it conflates too many things in a few symbols and then you waste time discussing corner cases.

Inaccurately, programming language = syntax + semantics.

Do not waste your time on syntax, if you are going to create a new language, rather than a parser.

I'm not saying that syntax is not important. But I feel semantics deserves much more attention.

I think syntax may actually be more important for adoption than semantics. But for just learning semantics is king.

Yes! I agree entirely, which is why I've been diving deep into creating (and playing with) new languages lately. Turns out a lot of problems that I have to solve at work can be fit into a parsing problem too, so it's not just all theoretical, but the big part of learning how to build languages is appreciating how the ones I use every day work; I can extend them, understand bugs, and push them to their limits. I couldn't do that prior: I always thought it was just black magic that greying neckbeard wizards did off in some ivory tower!

"that types are often a great name for variables, which both the programmer and compiler can use to easily and effectively understand most common code."

This hit me, what if variable names CONTAIN types? int__i = 1

And of course, it can be made optional. I will much prefer to do optional typing in the var name itself rather than the ugly syntax that guido has proposed with python.

It's called Hungarian Notation, famously used by Microsoft.

http://en.wikipedia.org/wiki/Hungarian_notation

the best happy-accident ... Months and months later, I realized that ... thanks to this simple idea, I could ...

That sentence is in every act of creation - something new just spawns something else that was not possible before the original act.

It's marvellous to see and indicates he is on the trail of something good - all the best.

I scrolled through the article and found some attributes of a language that is probably created by the author. But where are the rewards? I'm confused.

I wonder how much fun one could have with OMeta http://tinlizzie.org/ometa/ ?

I had fun doing Hecl. It didn't bring me fame and riches, but it did get used by a few companies, and it got me some interesting gigs.

currently stockpiling semantics ideas until I have enough good ones to justify the effort...

Reply on news.ycombinator.com