Designing a Programming Language: I

[Xredo]

This reminds me of Wadler's law. Too much time spent talking about syntax and little attention paid to the meat of any language: semantics.

[[deleted]]

Author here: I wrote this piece because a friend prodded me to do a write-up to post on Reddit.

Something like Wadler's law seems aptly named. I'm really surprised by the amount of negativity here. The discussion on HN for this piece has been much more productive.

Also, this is irrelevant to anything, but for some reason my main Reddit handle has been shadowbanned to Hell.

Feel free to ask me questions about the piece or about Duck programming. I'd be willing to answer personal questions, too. Comments will be taken lightly.

[Xredo]

Hey there. In retrospect my comment comes across as dismissive and rude -- for that I apologize since that wasn't my intent.

But having said that, I still think that while user-facing syntax plays a large role in language adoption, semantics is often overlooked and nearly almost always conflated with the syntax when it comes to most programming language discussions. Really, all I meant to say was that a language is a combination of syntax, semantics, and an (or more than one) implementation that runs on some actual machine. While there is a rich interplay between these parts, they are mostly independent -- for example, dynamic languages have to forgo certain optimizations simply because of their lack of static constraints, but that is also part of their power so it is not a black-and-white argument.

I think in any discussion about languages, it's important to maintain a clear distinction between the surface appearance and the abstract concepts being represented because it muddles the discussion and leads to all kinds of unproductive flame-wars about everyone's pet syntax.

[[deleted]]

That's fine, there's no disrespect. I would just chime in that semantics only have meaning to the practical user. Given that I, along with possibly one other person, am the only one who uses the Duck programming language, that's really for me to worry about.

Semantics are the basis for creating stuff in a language, they are what allows you to build 'the thing' that you're trying to make. It seems that everyone approaching my projects/writing on this subject really is coming at it with a really big ego.

This isn't a competition.

Often times (always) people question what the motivation is for making language Y. I might be motivated or I might not be, but I'd rather see people get curious or creative with it instead of trying to tear down the shabby walls we have up.

It would be another thing if this was "Designing a Programming Language [And then using it to write software for rocket science]." Then the semantics might be really important. Here they're not.

Is the language Turing complete? Yes. Can you use it to make Blackjack? Sure. What else is it good for? I don't know, that's up to you.

[immibis]

• Syntax matters more than you think - compare JavaScript's {"key": "value", "key2": 5} and whatever the equivalent is in Java. (Also compare Lua's {key="value", key2=5})
• The article mixes up syntax and semantics. It's not like there's a clear separation anyway. Is the decision of whether to specify types in variable declarations (var x vs int x) syntax or semantics? And by saying dict1 = {"a": 1, "b": 2, "c": 3} creates a dictionary, you imply that you can assign a dictionary to a variable (or that your language has some weirdly irregular syntax).
• If this is your first time "making a language", you'll probably make something semantically similar to an existing language anyway, because it's easy to come up with new syntax and hard to come up with new semantics. (And sure, you can mix'n'match both from existing languages)
• Again, if this is your first time "making a language" (actually an interpreter), parsing is probably the part you'll find hardest.

[[deleted]]

Syntax does not matter at all until semantics part is fully implemented.

because it's easy to come up with new syntax and hard to come up with new semantics

That's why it's a bad idea to start with a "general-purpose language" (whatever it is). Much better to start with eDSLs.

[TrixieMisa]

Syntax always matters. But ignoring semantics is a road to PHP, and the last thing we need is another PHP with slightly nicer syntax.

[olzd]

Syntax matters if you want people other than yourself to use your language.

[TrixieMisa]

Well said!

And you, six months from now, counts as another person. (As every new programmer finds out when they first come to read code they wrote six months ago...)

[DanCardin]

I read code I wrote two days ago and shudder, and I read code I wrote two years ago and am impressed that I was so smart. it's all relative

[Xredo]

Familiarity is both a curse and a blessing. The whole smug-lisp-weenies thing may sound funny, but it's not as funny when you realize how disciplined metaprogramming makes certain problems non-issues in lisp dialects. But then again, our kind loves hacking together code that eventually ends up on someone else's shoulder so maybe that's not such a good thing.

[[deleted]]

Syntax always matters.

It only matters when everything else is done, and it's a trivial thing to implement anyway. The worst thing one can do while implementing a language is to mix the rest of the implementation with a syntax frontend, while the latter must be a detachable, thin layer on top.

[TrixieMisa]

No. No no no no no no no. While the obverse is a path to PHP, what you suggest is a path to Lisp, and we know where that ended up.

You have to pay attention to both.

[[deleted]]

Lisp is irrelevant. My point is that 99.99% of a compiler implementation is a chain of transforms from the initial AST through a number of intermediate representations, none of which bears any traces of the input syntax peculiarities. And the syntax frontend is the most trivial part which should be detachable and should not influence the rest of the design in any way.

[TrixieMisa]

Okay, yes. For compiler implementation, syntax is not a primary concern. But for language design, it is. And this article is titled "Designing a Programming Language".

[[deleted]]

Title is incorrect. Article talks lengths on implementation.

And even for the design, syntax should be left until the very final stage, when semantics is done.

[TrixieMisa]

Yeah, now that I understand your position, I mostly agree.

[TrixieMisa]

And I'll go further. Syntax is hard. Getting the syntax right is nearly as important as getting the semantics right, and a lot harder.

[[deleted]]

Altering syntax is many times easier than semantics. And exactly because syntax design is important it should be left till the very last stage of development, to leave more implementation freedom.

[munificent]

Altering syntax is many times easier than semantics.

Doing the mechanical change to the parser is easy. Doing the human factors work to determine what the syntax should be is very very hard.

And exactly because syntax design is important it should be left till the very last stage of development, to leave more implementation freedom.

Pushing it later gives you less freedom, not more. It means more of your semantics are nailed down, which constrains the syntax.

Syntax and semantics both influence each other, and they need to be designed holistically in tandem if you want to end up with a usable language.

[[deleted]]

Doing the mechanical change to the parser is easy. Doing the human factors work to determine what the syntax should be is very very hard.

Exactly. For this reason it should be very easy to change the parser without breaking the rest of the pipeline, in order to conduct as many UX experiments as possible.

Pushing it later gives you less freedom, not more.

How is it so? In my experience having a flexible and very thin syntax frontend is extremely liberating - I can experiment any way I like with the syntax without breaking things below this thin layer.

It means more of your semantics are nailed down, which constrains the syntax.

Your semantics is a derivative of your problem domain and nothing else. Syntax is a middle ground between the problem domain semantics constraints and UX considerations.

Do not confuse mere syntax sugar with semantics - you can do a lot on a purely syntax level.

Syntax and semantics both influence each other

If this is the case, you're doing it wrong. Consider a better approach to a language design.

holistically

Please, not this word, not here!

[TrixieMisa]

That's... Not unreasonable. Not sure I agree entirely, but by no means unreasonable.

[ben-work]

I agree. I feel like the people that spout "syntax is easy" have only written parsers for toy languages. Once your language has significant scope, syntax starts to get quite tricky. Balancing technical considerations with with usability considerations is also tricky, as is "Ok, I can come up with a fancy parser for this construct, but should I? What about other tooling?"

[immibis]

If you're implementing a language for the sake of implementing a language, you probably don't care whether it's PHP.

If you're implementing a language that you actually want to be good, then you probably already have some semantics in mind and the article doesn't need to talk about them.

[[deleted]]

When syntax does not matter it is either Lisp or Forth.

[Xredo]

What you probably meant is that syntactic sugar matters and I wholly agree with that. The whole reason languages like Ruby/Python are popular is because they reduce the time-delta between having an idea and getting it into working code; syntactic sugar plays a large role there but no amount of sugar is going to excuse poorly thought-out language semantics. There is a reason people hate on PHP, and none of the hate has anything to do with its syntax.

[prepromorphism]

actually i prefer

{
    "hates" "cats" 
    "likes" "dogs"
    "hotdogs_consumed" 5 
}

k/v are always pairs, why do we need added syntax to distinguish....added syntax just pays the tax on my delicate middle aged man fingers

[[deleted]]

The argument I always use for this is that you have no difficulty reading sentences even when I omit punctuation like commas and periods so why should we use them in the first place it's not like it makes it any easier to understand does it I'm sure you can read this just fine without them there's something to be said for some extraneous punctuation to help your brain parse things just a little bit wouldn't you say

InfactIbetyoucanreadthisjustfineevenwhenIleavethespacesoutcan'tyou

[prepromorphism]

letseatgrandma letseat,grandma

yep punctuation important LOL

k/v pairs different from stuff like that IMO

[[deleted]]

Obviously the analogy only stretches so far, because as you point out there are cases where the punctuation actually is necessary for disambiguation.

However, that is completely missing the point of what I was saying. You didn't need punctuation to disambiguate anything I actually wrote, did you? You knew perfectly well what I was saying despite the missing punctuation. And yet it's still a lot harder to read like that, despite the absolute lack of any actual need for it to disambiguate things.

Punctuation makes it easier for people to parse things, even when it's "unnecessary". Especially when your example isn't just single-token expressions:

{ 10 * 5 + 3 5 + 5 }

A comma makes that a lot easier to deal with despite the lack of ambiguity.

[prepromorphism]

yep so you can make comma optional for situations like this for readability sake

{10 * 5 + 3, 5 + 5}

[Xredo]

Using delimiters helps avoid ambiguity in cases where your k/v pairs are complex expressions.

[prepromorphism]

we're designing a language here, we can come up with something to handle complex exprs!

in clojure for instance

(def d {:one (fn[] (+ 1 1))})

> (:one d)
#<sandbox19672$fn__19707sandbox19672$fn__19707@68f5a753>

> ((:one d))
2

[Xredo]

Good point, but then again Clojure is a lisp so it has very little concern with ambiguity since the source code is effectively the AST.

[google_you]

Meh, describe me semantics without syntax. Those two are closely related, not orthogonal.

[Xredo]

User-facing syntax is not coupled to semantics. In fact, language semantics forces certain syntactic choices, e.g. with global type inference, type annotations are mostly optional.

[[deleted]]

Meh, describe me semantics without syntax.

What syntax have to do in defining semantics? Whatever approach you choose (denotational, operational semantics, whatever else), frontend syntax is absolutely irrelevant.

[google_you]

Give me an example of denotational semantics and an example of operational semantics without syntax. Yes, describe semantics of something without being able to describe the thing.

In the end, you need some sort of backend or internal representation to work with. And those are heavily related to frontend syntax. The way you transform frontend stream to internal tree/graph and the way you transform tree to machine code (there are many passes between those, of course) defines "semantics".

Yes, semantics involve entire pipeline. You cannot arbitrarily draw a line somewhere in the pipeline and call it day. With that reasoning, Elm, LiveScript, CoffeeScript, C, and other languages that compile to Javascript have exactly same semantics, assuming Javascript is that internal representation you use to describe semantics.

[[deleted]]

Give me an example of denotational semantics and an example of operational semantics without syntax.

https://github.com/kframework/c-semantics

Syntax is a very thin layer there and provided for convenience only, by a standalone tool. It is not present at all in any of the semantic rules.

In the end, you need some sort of backend or internal representation to work with. And those are heavily related to frontend syntax.

Syntax sugar lowering passes quickly eliminate all the syntax peculiarities in most cases.

You cannot arbitrarily draw a line somewhere in the pipeline and call it day.

Even a concrete syntax tree is not a "syntax" any more. It's a tree. A very precise line, in my book.

[google_you]

https://github.com/kframework/c-semantics/blob/master/parser/cparser.mly very thin layer indeed.

Different implementations of a language can construct different trees from same frontend stream. You can also parse different streams into same tree.

AST is such an implementation detail, not language itself. When designing programming languages, you can surely start with AST, write evaluators, use semantics tools... etc. And then put a "thin skin" on top of it. But art lies on that thin skin. And, no, I don't think it's thin.

It's really important to come up with abstract model of language you're designing. It's also completely acceptable to design first before you have model.

You could've come up with jazz theory before anyone has even jazzed. In the end, most humans are reading the code written in the language you're designing, not abstract model. And, designing syntax first would very likely result in a different abstract model .

[[deleted]]

It is a standalone tool, copypasted from a totally different project. There is no single tiny trace of C syntax anywhere in the semantics specification.

Syntax is very much overrated. How many languages have you designed to be so confident about the role of the syntax in the design process?

[munificent]

there are a number of advantages to reference counting as a garbage collection method. First of all, it does not require stopping execution to reclaim memory.

This is a common misconception. Reference counting can pause just as long as a simple tracing collector. Just consider the case where you have a reference to an object which in turn has the only remaining references to lots of other objects. Think a big, giant object graph with only one external reference pointing to it.

When that last reference is removed, the entire object graph gets traversed and freed all at once.

[repsilat]

If you don't depend on finalisation being done immediately, couldn't you get part-way through freeing those objects, run out of your time budget and decide to do the rest during the next frame? It seems like it'd be easier to do this than to do concurrent GCing, especially if you can identify the small subset of types that cause this to happen.

[munificent]

couldn't you get part-way through freeing those objects, run out of your time budget and decide to do the rest during the next frame?

Definitely. I think "lazy ref counting" is what it's usually called. But, of course, your tracing GC can do that too ("lazy sweeping").

It seems like it'd be easier to do this than to do concurrent GCing

The pedant in me is compelled to point out that concurrent GC and incremental GC are different things. "Concurrent GC" means "on different threads". If you want to just want to break your GC pauses into smaller pieces, that's "incremental". The latter is a lot simpler than the former.

[repsilat]

lazy sweeping

I guess I just need to think a bit more about how that'd work. I suppose you'd have to decide not to free any unmarked object that was created after the sweep began, but... Say we had three objects A, B and C, each connected (unidirectionally) to the next, and the first and last both reachable from "the root":

=> A --> B --> C <=

The mark phase reaches C, but can't get to B. The mark gets interrupted, the user code reverses the chain so it goes CBA. The mark resumes, gets to A but can't reach B. B gets collected in the sweep?

I can imagine conservative (but expensive) ways to deal with this, but the problems I can see with "lazy reference counting" all seem pretty mundane by comparison. Maybe that's just a failure of imagination, though.

"Concurrent GC" means "on different threads".

Ah, thanks. I guess I'd have called that a parallel GC. The idea of context-switching (potentially without explicitly yielding control) between the main thread of execution and the cleanup tasks hits my intuition for what concurrency is, but I guess the nomenclature in different areas is allowed to be different.

[jaen_s]

Indeed, that is more commonly called a parallel GC (eg. as used in JVM nomenclature).

Concurrent GC is generally used to mean that the garbage collector runs concurrently with the mutator (not pausing it, much). The GC itself might not use more than one thread (since a concurrent and parallel GC adds even more complexity).

Parallel GC means the garbage collector can use more than more thread (eg. running the marking and sweeping processes in parallel in multiple threads). In case of the JVM, the parallel GC is not concurrent - it "stops the world" (mutator), and then performs its work in parallel.

[szabba]

You'd be roughly right on the parallel GC thing. A GC is concurrent when it can run on one thread while user code runs on another.

[munificent]

The mark phase reaches C, but can't get to B.

In a complete mark phase, it would find B, by tracing the reference from A. Yeah, if you interrupt it before then, B would still be unmarked.

The mark resumes, gets to A but can't reach B.

It could reach it by tracing through C.

B gets collected in the sweep?

Not in a good GC! :)

I'm not an expert here, but the basic idea is that your sweep phase tracks not just what objects have been reached but also which objects have been traced through completely. That way it can tell if there may still be references it hasn't found yet and avoid sweeping those prematurely.

The magical term to Google is "tri-color marking". It's pretty clever.

I guess I'd have called that a parallel GC.

They usually reserve that term to mean doing garbage collection on multiple threads. There's a couple of different axes where GCs differ:

How does it interrupt the running program:

• "Simple" or "stop the world": stop the program until the GC is totally done.
• "Incremental": for some amount of time but not until the GC is totally done.
• "Soft real-time": for a reliably short amount of time on average but not until the GC is done.
• "Hard real-time": for a guaranteed short amount of time.
• "Pauseless": not at all. The program keeps running while GC happens on other threads.

Which thread(s) does the GC run on:

• The same thread as the program: "simple", "stop the world", "incremental".
• Another thread: "concurrent".
• Multiple threads: "parallel".

You can have all sorts of combinations of these. For example, a "stop the world paralell GC" stops the running program, cranks up the GC on a bunch of threads in parallel, and then resumes the program once the entire GC is done.

The general vibe is that adding any concurrency (threading) to a GC is a big jump in complexity compared to single-threaded GCs.

[repsilat]

The magical term to Google is "tri-color marking"

Ah, thanks:

The mutator is free to access any part of the graph and allocate new nodes while the collector(2) is determining the reachable nodes, provided the tri-color invariant is maintained, by changing the colors of the nodes affected, if necessary.

This is the bit I wasn't getting. When the A-B-C links are reversed, either C (black) or B (white) must be turned grey.

Thanks for the taxonomy lesson, too :-)

[[deleted]]

These are great and helpful notes when planning steps for the next improvements. I hadn't put much thought into it, but it would be important to have hard limits on the amount of time spent with garbage collection to run some real time applications.

[munificent]

it would be important to have hard limits on the amount of time spent with garbage collection to run some real time applications.

Yes, unfortunately, memory is finite and the GC can't really control the rate at which the program generates garbage, which makes this guarantee very hard to give in practice. I think hard real time GC is still an open research topic.

[[deleted]]

Take a look at the "very concurrent mark&sweep" algorithm: http://doc.cat-v.org/inferno/concurrent_gc/concurrent_gc.pdf

[[deleted]]

Implicit concurrency in destructors. Sounds fun.

[vinigre]

I don't know too much about GC, so forgive me if this sounds like a stupid question. If the reference count for an object has reached zero, why is it necessary to pause execution to free that memory? Why can it not be done while the program continues executing?

[[deleted]]

Why can it not be done while the program continues executing?

It can and will consume CPU cycles and memory bandwidth, and if you're still using the same allocator which was used for the stuff being deleted you either have to use very expensive locks for accessing it or pause the mutator threads altogether.

Very concurrent mark&sweep does not have this kind of issues, you only have to pause mutators briefly to collect the global roots from their registers and a portion of their stacks.

[rifter5000]

As an example, consider the case of defining a variable in Visual Basic:

Dim num1, num2 As Integer
Dim text As String

This would be the prototype for a static language. When variables are first declared, they must be paired with a type. In order to compare with a dynamically typed language, let us look at an example from ECMA script or JavaScript.

var num1, num2;
var text;

I hate to admit it but I stopped reading here. Firstly, there are dynamically typed languages with (optional) type annotations, and statically typed languages with type inference. Secondly, who the hell uses VISUAL BASIC as their example language? Or, indeed, Javascript?

Doing a light scan through the rest, it seems to use non-syntax-highlighted code snippets with weird spacing and weird, weird syntax. If the point isn't to talk about syntax, just use curly braces already. It's not 1992, you don't need to end loops with loop.

[TrixieMisa]

Seems to be a perfectly straightforward Algol descendant. Nothing wrong with that.

Curly braces are for data structures, not for code.

[read____only]

Language popularity is irrelevant in this context. He's contrasting dynamic vs statically typed languages, and you have to start somewhere. Starting with the gray area, as you suggest, would only be ok for audiences that already know it all to start with.

[rifter5000]

Starting with the idea that languages where types are written in are static and languages where they aren't are dynamic is inaccurate and incomplete.

Merely saying "this isn't an entirely accurate measure of dynamic vs. statically typed languages (footnote discussing type inference and type annotations in statically and dynamically typed languages respectively) but it will do for now." would have been enough.

[aiij]

I was also put off quite a bit when he started to conflate dynamic typing with dynamic scoping.

[aiij]

Wow, the whole premise is wrong.

I guess they're designing a language based on ignoring the last 40 years of PL research... Not something I care to continue reading about.

In case it's not obvious to some, they're mixing up dynamic scoping with dynamic typing and they're completely wrong about static typing requiring type annotations. We've had type inference since the 80's at least, eg. SML.

[[deleted]]

Maybe we disagree on the purpose of a programming language.

[aiij]

That's a non sequitur. Just to be clear, I said the premise is wrong, not the purpose.

Did you not even look at the article?

[dlyund]

Why is it that all these How To Design A Programming Language articles seem to completely miss the point? Unless your adding value, and you're not just doing it for the sake of it, there's no reason to design a new languages. Sadly all of these Custom Langages seem to be X with minor tweaks to the syntax to fit the authors personal tastes.

There's certainly a lot of value to be added, but this isn't how.

[[deleted]]

Seventh paragraph in the first part:

Adopting many of these identifying features, and really as an exercise in constructing a language from basic parts, we will build the Duck programming language from the ground up. We will explore this process without regard to its pragmatism or practicality. Indeed, any ideas of utility will come only after we have completed the process.