Grammars for Programming Languages (2018)

https://medium.com/@mikhail.barash.mikbar/grammars-for-programming-languages-fae3a72a22c6

by bo0tzz • 7 years ago

88 44 7 years ago

snidane2• 7 years ago

Controversial opinion but I believe that eventually these grammars and complex parsers will be found to have been a huge mistake for computer science. A mistake made for the sole reason of making programming languages resemble natural languages, even though they are not meant to be read fluently.

Everyone who experienced the magic of lisp understands how beneficial it is to have the textual representation as close to the parsed abstract syntax tree. One can create new languages fit for the purpose of a given class of problems and thus reducing size of codebase 10 to 100 fold (or even million times in case of modern multi million LOC software projects).

The biggest mistake lisp ever made was the unintuitive parenthesized prefix notation. Which can be thrown away by having all operations strictly infix.

Ie. instead of doing combinations of the following:

  lisp: (plus 1 2)
  methods: 1.plus(2)
  algol,C: plus(1, 2)
  haskell: plus 1 2

One can use the simplest form ever and achieve even simpler lisp:

  1 + 2

but use it consistently for every function call or operator within the language. (even for functions of multiple arguments).

APL came close, but for some reason decided to ignore the important Phoenician discoveries of 1. reading from left to right 2. use of phonetic alphabet instead of hyeroglyphs.

platform• 7 years ago

One can create new languages fit for the purpose of a given class of problems and thus reducing size of codebase 10 to 100 fold

interesting, thank you for sharing.

Could I transpose your thought into:

Solutions (or large scale programs), should not be written in a general purpose language.

Instead, there should be core domain language (solution DSL) developed (using a general purpose language) and then the solution should be developed using the solution DSL.

AnimalMuppet2• 7 years ago

Here's another unpopular opinion: Not much of the value of a DSL is in the syntax.

That is, I'm trying to write a program to do X. In, say, C++, I create data structures and functions as building blocks to write the higher-level functionality of the program. That's my "DSL" - just classes (structures and functions).

In Lisp, I can go further. In creating a DSL, I can not only create function (and, through functions, data structures), but I can also create syntax. This may let me write less code, and may make the code I write clearer.

My assertion is that, while that's nice, most of the DSL is actually the functions and data structures. The syntax is sugar - say, maybe 10% of the benefit, but not more.

ColanR• 7 years ago

J fixed the second problem you have with APL, and many people think that was a mistake. What do you think the better version of lisp/apl/whatever would actually be? I get the idea of a simple 1 + 2, but that doesn't express all the power of what makes lisp lisp.

AnimalMuppet2• 7 years ago

One can create new languages fit for the purpose of a given class of problems and thus reducing size of codebase 10 to 100 fold (or even million times in case of modern multi million LOC software projects).

I find that a bit hard to believe. Here's a 100 million line codebase; I seriously doubt that you can express it in 100 lines in any language. Lisp may be good, but it isn't that good.

chubot5• 7 years ago

Yeah to be honest one of the things that made me skeptical of the code compression / productivity claim is looking at the implementations of Chez Scheme and Racket (after also looking at 20+ compilers / interpreters, and working on a language for a few years).

I'm pointing to them as very long-lived and valuable codebases written in Lisp dialects. Chez Scheme is a 35 year old codebase and Racket is also decades old.

So I'm not saying there's anything wrong with them, but I am saying that it doesn't appear that they're 10x easier to understand or modify than LLVM or CPython (Chez being a compiler and Racket being an interpreter as far as I remember). Or that you can get a 10x better result.

Basically for the claim to be true, why can't you write something like Racket in Racket 10x faster? Like 3 years instead of 30 years. And why doesn't it do way better things than CPython or Ruby? Those claims might be "slightly" true depending on who you are, but they're not devastatingly true. There's been more than enough time to evaluate the claims empirically.

In other words they would have already proven themselves in the market if that were the case. You would have extraordinarily productive teams using these languages -- along the lines of what PG hypothesized 15+ years ago.

http://www.paulgraham.com/avg.html

In fact the thing I found was interesting is that at the core of Racket is a big pile of C code, just like CPython. A year or 2 ago I watched a talk about them self-hosting more, and moving to Chez scheme's backend, but I don't recall the details now.

https://github.com/cisco/ChezScheme

https://en.wikipedia.org/wiki/Chez_Scheme

https://github.com/racket/racket/tree/master/racket/src/rack...

(FWIW I also looked at and hacked on femtolisp around the same time, since I was impressed by how Julia uses it.)

correction: it looks like Racket has a JIT too, written in C. Still same point applies: it's not magic and looks a lot like similar codebases in C. Chez is more self hosted AFAIR but it's also hundreds of thousands of lines of code.

c3534l• 7 years ago

I suppose at a certain point you violate the source coding theorem. As a back of the envelope calculation, take the compiled binary and tarball it. That's the smallest you should consider even possible assuming that compressed binaries are readable to, say, an alien species with extraordinarily different minds. Suffice to say, getting rid of a million lines is one heck of a one-liner.

nmadden• 7 years ago

Well this is trivially true: here's my domain specific language "main". It has a single keyword "main" that when executed runs the main method of the 100 million line codebase (which is the language runtime).

agumonkey2• 7 years ago

I know few but the best effort/research on the subject I know of is VPRI OS written in Ometa (it has a page on wikipedia).

I think they made the whole thing in 100kLoC using dedicated DSLs (compared to Windows which is in the 100M ballpark). I think Alan Kay wanted at 10kLoC system.. who knows maybe one day. :)

specialist• 7 years ago

I'm a bit more open to the possibility. I'd like @snidane to share examples, real or imagined.

I'm barely qualified to discuss such things, so please humor me:

Alphabets, syntax, grammars, semantics, vocabulary, mental models, transformers, etc... There's a dance, right? Working at the right level of abstraction. Changing something here and figuring out the impact over there.

Switching from roman to arabic numerals. Small tweaks to combo of digits, representation, operations yielded a huge leap.

I once replaced an huge stack for designing print production plans (ScenicSoft's Preps, had 80% of the prepress imposition market at one time) with a simple form. My central insight was identifying and modeling the physical system as a series of transformation steps (how the paper was fed, folded, cut).

Optimist me hopes there's many more of these clever hacks to be discovered.

analbumcover• 7 years ago

1. reading from left to right

This seems a strange quibble when it is an arbitrary convention that doesn't really matter in the slightest. It's just the natural extension of the usual mathematical function composition f(g(x)) to include dyadic functions and thus do away with function/operator precedence. It doesn't make things any easier or harder if you were to prefer generalizing ((x)g)f instead so that the language could be read left to right, it's just a different convention.

2. use of phonetic alphabet instead of hyeroglyphs.

The purpose of the symbols in APL is that they are meant to be a "tool for thought" [0]. But I'm a mathematician so I was already trained to this way of thinking. Using more verbose languages becomes an exercise in tedium, they make programming feel like trying to chop down a tree with a herring. The "hieroglyphs" are a large part of what make APL feel like wielding a lightsaber by comparison.

[0] http://www.eecg.toronto.edu/~jzhu/csc326/readings/iverson.pd...

jcranmer• 7 years ago

the important Phoenician discoveries of 1. reading from left to right 2. use of phonetic alphabet instead of hyeroglyphs.

The Phoenician alphabet was written right-to-left or boustrophedon (alternating left-to-right and right-to-left, usually mirroring glyphs when writing them backwards). The Greeks appear to have started with boustrophedon writing and then settled with left-to-right writing. The other Semitic scripts that borrowed from Phoenician (e.g., Hebrew and Arabic) copied Phoenician's right-to-left writing direction.

While we're being pedantic here, the Phoenicians also didn't invent an alphabet. They used an abjad, not recording any vowels. The Greeks were the first to create a true alphabet, adapting 'aleph (representing the glottal stop, which Greek did not have) into alpha (representing the open front unrounded vowel 'a'), he into epsilon, and 'ayin into omicron. Phoenician semivowels waw and yodh furnished upsilon and iota, respectively.

A final point is that the principle of using glyphs to represent phonetic values does not originate even with Phoenician. The rebus principle was already present in both cuneiform and hieroglyphics, and Middle Egyptian already developed a full inventory of consonant glyphs, although these were not used exclusively.

agumonkey2• 7 years ago

I use to dislike linguistics, but you made me change my mind. Any book suggestion on early language development ?

rustybolt• 7 years ago

Infix notation is closer to natural language, but it's only easier to read for simple expressions. You really have to know the precedence and associativity of each and every operator that is used to make sense of an expression.

lmm3• 7 years ago

Interesting idea.

How would you write functions of multiple arguments as infix? Scala can get close to

    myListOfInts foldLeft 0 +

which is... honestly not much more readable.

How do you resolve ambiguity when functions take optional arguments / are overloaded? Or would you not allow that?

snidane2• 7 years ago

Make the right side of the function call a list or a dict.

  myListOfInts foldLeft (0, +)

or if you make : to be right associative cons function

  myListOfInts foldLeft 0 : +

or using dict

  myListOfInts foldLeft (zero: 0, op: +)

carapace4• 7 years ago

See also Definite Clause Grammars (DCG):

https://en.wikipedia.org/wiki/Definite_clause_grammar

https://www.metalevel.at/prolog/dcg

Joker_vD• 7 years ago

I manually wrote more recursive-descent parsers that I am comfortable to admit (hey, they're fun to write), and most of the "beyond the context-free!" approaches described in this article seem to me to fall into two categories:

1. There is this one common pattern in recursive-descent parsers that allow you to write a more concise recognizing code — let's make it directly expressible! Ordering rules, "not an ending quote/not an end of a comment", "ident that's not a keyword" fall into this category.

2. Semantic actions work really well in practice, but it's gauche. Let's instead encode some restricted, non-Turing-complete, but still useful PL directly in grammar, that'll improve things somehow! Detecting "undeclared identifier used" and "identifier redeclaration" falls into this category: this "quite knotty" Boolean grammar has a dict-like structure threaded through it, isn't it amazing? And this grammar-with-context has built-in support for scoped environments, you don't need your symbol tables anymore (unless you have user-defined types, presumably)!

Of course you can parse the input according using any of these more expressive grammars in the same time and space as you can with a boring old CFG grammar with rule priorities and semantic actions: because that's essentially what they're, just expressed differently. And is there much gained by expressing it differently? It's the same story as with DSLs, really, you keep making them more and more complex and feature-full up until the point you arrive at a full-fledged programming language with awkward semantics and realize that you probably should have stayed with limited DSL that could invoke arbitrary actions written in a proper general-purpose programming languages.

So, yes, "Devising an adequate and convenient formalism on top of grammars with contexts is a challenging task", and it's the task that must be solved before any of those approaches would be more useful than what we have today.

drallison• 7 years ago

There is a tension between the language (grammar) used to describe a language and the algorithm that is used to parse the language. In practice, a Pratt Parser (https://en.wikipedia.org/wiki/Pratt_parser) is often a good choice since it has the simplicity of a recursive descent parser but avoids the recursive plunge for objects like expressions.

Grammars for Programming Languages (2018)

Related Stories