27 ms·

The naked truth about writing a programming language (2014)

250 points by pcr910303 7y ago

billconan 7y ago
I want to implement a toy programming language, but I have questions regarding the following in that article: > Context free grammars. What this really means is the code should be parseable without having to look things up in a symbol table. C++ is famously not a context free grammar. A context free grammar, besides making things a lot simpler, means that IDEs can do syntax highlighting without integrating in most of a compiler front end, i.e. third party tools become much more likely to exist. Many complex languages, like c++, rust are not context free. We therefore need semantic analysis. What programming language features will be compromised if I stick to context free? Will the end result be as expressive as c++/rust? Any programming language that is massively adopted is context free? BTW, the toy language I want to build will be something similar to javascript.
- steveklabnik 7y ago
  Rust is almost context free; there’s one relatively rarely used bit that requires context. And usually it’s only one or two bytes of it.
  - h-cobordism 7y ago
    You're referring to raw string literals, right?
    - steveklabnik 7y ago
      Yes. You need to include more #s than you have in the string, and it’s rare to have a ton of them, let alone a raw string literal in the first place.
      - wtetzner 7y ago
        Does that make the grammar context-sensitive, or just the lexer?
        steveklabnik 7y ago
        This is not an area of my expertise, so I can't say.
  - deleted 7y ago
    [deleted]
- desc 7y ago
  https://stackoverflow.com/questions/898489/what-programming-languages-are-context-free https://stackoverflow.com/questions/898489/what-programming-... Most languages have context-free syntax, which is what the article refers too. There really is no reason to sacrifice that. Even modern PHP recognises the value of having a parse tree independent of an entire compiler. Context-free semantics is an entirely different matter, and I'm not even sure what it'd mean...
  - chubot 7y ago
    The two top answers are in conflict. The second answer with 43 points is closer to right: There are hardly any real-world programming languages that are context-free in any meaning of the word. The first answer with 41 points is totally wrong: The set of programs that are syntactically correct is context-free for almost all languages ----- A better source is this whole series by Trevor Jim, which has nice ways of relating theory to practice. He lists a bunch of reasons why you could consider nearly all programming languages not context-free. http://trevorjim.com/parsing-not-solved/ http://trevorjim.com/parsing-not-solved/ -- hundreds of parser generators support context-free grammars, but there are almost no context-free languages in practice. http://trevorjim.com/python-is-not-context-free/ http://trevorjim.com/python-is-not-context-free/ -- A main point here is that you have to consider the lexer and parser separately. Grammars don't address this distinction, which arises in essentially all programming languages. Also there is some lexical feedback, similar in spirit to C's lexer hack. http://trevorjim.com/haskell-is-not-context-free/ http://trevorjim.com/haskell-is-not-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-language-is-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-languag... http://trevorjim.com/c-and-cplusplus-are-not-context-free/ http://trevorjim.com/c-and-cplusplus-are-not-context-free/ -- the way LALR(1) conflicts are resolved in practice can make a language not context-free (copying from a recent comment)
    - WalterBright 7y ago
      The implementation of D has a lexer that is independent of the parser, and a parser that is independent of the rest of the implementation. I have resisted enhancement proposals that would put holes in those walls.
- tom_mellior 7y ago
  This point in the article is pretty weird (the rest is good). I don't think IDEs do a lot of parsing to do syntax highlighting, isn't it all just regex matching to identify the types of tokens? I'd be interested in real-world examples of IDEs doing something more complex to achieve syntax highlighting. And conversely, examples of imperfect syntax highlighting of C++ due to the undecidability of its input language. I mean, yes, an actual parser for C++ must be able to execute template computations, and that's a pain, but why would that be relevant to syntax highlighting? It isn't. Now, there are valid reasons for running a proper language frontend from the IDE: Error reporting of all kinds, not just syntax but also type errors and whatever else the compiler likes to complain about. But there the IDE should not try to replicate the parser. Parsing only a context-free surface language will not catch type errors, exactly because enforcing a static type system requires one to "look things up in a symbol table". So the actual compiler should provide an IDE-friendly mode where it runs its frontend and reports errors back, and the IDE should not try to roll its own version of this. In other words, the IDE is not relevant either way. > Any programming language that is massively adopted is context free? Statically typed languages require semantic analysis and symbol table lookups, so they are out. And yet we have context-free grammars for all widely adopted statically typed programming languages. And we also have additional semantic checks for all of them. The notion of a "context free programming language" being one that has context free syntax and no semantic checks at all is not a useful notion. Don't worry about it while designing your language.
  - alpaca128 7y ago
    > I don't think IDEs do a lot of parsing to do syntax highlighting, isn't it all just regex matching to identify the types of tokens? IntelliJ highlights variables etc. differently if they're unused and can highlight different identifiers in different colors. Not sure about other current IDEs. That said I never felt like I needed such features, normal syntax highlighting does the job pretty well for me.
    - dehrmann 7y ago
      IntelliJ has context-aware autocomplete. Type this.field.get and it will show methods and fields starting with get for whatever type field is. There's a lot of context needed to make that happen.
- tomp 7y ago
  The purpose of context-free, or rather unambiguous grammars in general, isn't for the benefit of compilers, but for the benefit of humans. A computer can parse almost everything, even regexes (with backtracking etc.), it's the humans that trip over fancy grammars.
- kyllo 7y ago
  Context-free has nothing to do with symbol tables, it just means that in the grammar, the left-hand side of a production rule can only have a single non-terminal symbol, which can always be replaced by the expression on the right-hand side, without ambiguity. Language features are an orthogonal issue--you can implement any language feature with a CFG, but you just can't reuse the same keyword or operator to have different meanings in different grammatical contexts. A classic example is that in C++ it is impossible to know whether << is brackets around template arguments, or the left bit shift operator, or the stream output operator, without arbitrary lookahead--you need to parse the rest of the statement in order to decide which one it is in the current statement's context. Generally language designers don't choose to implement a context-sensitive grammar on purpose because they desire some feature that requires it; they strive for a context-free grammar, but end up with a handful of special cases that require context-sensitive parsing because of either convenience or legacy reasons. Popular programming languages nearly all use custom parsers written in other (or the same) Turing-complete programming languages, so it's not "harder" to parse the context-sensitive rules, it only poses a problem if you want to use a parser generator to implement parsing for a CSG.
  - johannes1234321 7y ago
    > A classic example is that in C++ it is impossible to know whether << is brackets around template arguments, or the left bit shift operator, or the stream output operator, without arbitrary lookahead--you need to parse the rest of the statement in order to decide which one it is in the current statement's context. The classic example, I guess, is the most vexing parse: https://en.m.wikipedia.org/wiki/Most_vexing_parse https://en.m.wikipedia.org/wiki/Most_vexing_parse """ The line TimeKeeper time_keeper(Timer()); is seemingly ambiguous, since it could be interpreted either as a variable definition [...] a function declaration [...] """ These things you can only resolve by having the symbol tables around and checking. The parser alone can't tell. A language could avoid this i.e. by requiring specific keywords or having more distinct syntax. Humans (programmers) however often can deal with ambiguity, we have it in humannlanaguage as well and context on most cases helps and I argue those aren't practical problems. (While that's only opinion)
- a1369209993 7y ago
  Note that "context free grammars", in the technical sense, is completely the wrong thing. Eg, enforcing consistent indentation is not context free: foo() { return; } ↓↓↓↓↓↓↓↓↓↓↓ aaaa{ bbbbreturn; cccc} ↓↓↓↓↓↓↓↓↓↓↓ aaaabbbbcccc This is equivalent to aⁿbⁿcⁿ, which is pretty much the canonical example of a non-context-free language. What you acually want is not context-free grammar, but, as TFA says: > the code should be parseable without having to look things up in a symbol table
  - qznc 7y ago
    There is a trick for indentation: Use a context-sensitive lexer in front of a context-free parser. The lexer serves indent and dedent tokens to the parser. With this trick, you can parse Python with a context-free grammar.
  - bmn__ 7y ago
    There are plenty, the majority even, of programming languages that do not enforce consistent indentation. You make a false generalisation when you claim that CFG are completely the wrong thing.
  - tom_mellior 7y ago
    > This is equivalent to aⁿbⁿcⁿ Is it? You only indent with spaces, so a = b = c = ' ', and the problem you claim disappears.
    - gbear605 7y ago
      I'm not sure that's a solution. The problem is verifying that the three 'n's are equal, not that 'a', 'b', and 'c' are equal. Solving this cannot be done in a context free grammar [0]. [0]: https://cs.stackexchange.com/questions/33153/is-an-bn-cn-context-free https://cs.stackexchange.com/questions/33153/is-an-bn-cn-con...
      - tom_mellior 7y ago
        Yeah, you're right. I got confused by the original phrasing.
- froh 7y ago
  Notwithstanding the other comments on context free vs sensitive, the 2014 article predates the language server protocol, which neatly moves the support for programming languages from the IDE to a stand alone tool tied to the language: https://microsoft.github.io/language-server-protocol/ https://microsoft.github.io/language-server-protocol/ https://en.m.wikipedia.org/wiki/Language_Server_Protocol https://en.m.wikipedia.org/wiki/Language_Server_Protocol So that IDE support point has become much weaker, if not moot.
xiphias2 7y ago
,,grammar should be redundant. You’ve all heard people say that statement terminating ; are not necessary because the compiler can figure it out. '' I'll stay with my non-redundant Julia language, thank you very much. It gave me a lot of joy to programming, and I don't remember having big problems with error messages. Even if I have, syntactic errors are trivial to find. The hard parts of efficient programming are memory management (garbage collection), controlling vectorizing instructions, balance between ease of GPU programming and efficiency, parallelization, not semicolons at the end of a line. All programming languages have to decide on how low level control they give to the computer resources, and how they abstract them, to make high level programming possible without sacrificing too much efficiency.
- adimitrov 7y ago
  Whilst you're not wrong about what you value about a programming "language", I'd say there is an important distinction to be drawn between two things people tend to conflate: the language and the runtime. Perhaps a counterexample is in order to explain it: Java the language and Java the runtime (VM, stl) are two different things entirely. Kotlin, for example makes a lot of different choices in language design (e.g. semicolons) while reusing the same runtime (GC, threads, etc.) Of course, you can often not tease these two concerns apart easily and neatly, but there is merit in giving thought to the ergonomics of the pure language side of things. At the end of the day, a programming language doesn't need an implementation to be useful (e.g. as a teaching tool) as it's an abstract, formal concept.
didibus 7y ago
After learning s-expression based syntax, I am just baffled why we even bother with anything else. When you play around with different Lisps, the syntax is always the same, the language differences becomes the semantics only. Other languages put too much emphasis on the syntax in my opinion. And while I understand the "popularity" appeal. I've almost never seen someone learning the s-expression syntax and afterwards not liking it. Basically I think it be worth it to push people to learn the s-expression syntax just so we can stop wasting our time with syntax afterwards. Also if I recall, without user macros, I think s-expression syntax is context free no?
- daenz 7y ago
  It's simple, but it's fundamentally reductionist. You can ease the cognitive load by making certain programming structures first-class citizens in the language.
  - amelius 7y ago
    Yes but now you have to worry about parentheses and at what nesting level certain constructs should live.
    - pfdietz 7y ago
      An adequate editor with autoindent and paren matching solves those problems completely.
  - F-0X 7y ago
    > You can ease the cognitive load by making certain programming structures first-class citizens in the language. Which, in every s-expression based language I'm aware of, can be achieved using macros.
    - chrisseaton 7y ago
      Isn't that the point - s-expressions aren't good enough so people work around them by writing more conventional languages and parsers (the reader macros) to avoid having to write in them.
chubot 7y ago
On regexes, he is generalizing from a small number of examples. Some lexers are straightforward to write by hand, but others are better done with a code generator. edit: I should really say that you should consider using regular languages to lex your programming languages, not (Perl-style) regexes. Those are different things: https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ I used re2c for Oil and it saves around 5K-10K lines of "groveling through backslashes and braces one a time" (e.g. what other shells do) http://www.oilshell.org/blog/2019/12/22.html#appendix-a-oils-lexer-uses-two-stages-of-code-generation http://www.oilshell.org/blog/2019/12/22.html#appendix-a-oils... And the parser is faster than bash overall: http://www.oilshell.org/blog/2020/01/parser-benchmarks.html http://www.oilshell.org/blog/2020/01/parser-benchmarks.html
WalterBright 7y ago
Author here. AMA!
- Rochus 7y ago
  The article is from 2014. Is it still current? What would you change in 2020?
  - WalterBright 7y ago
    I'd write the same thing today. 6 years more experience just confirms it.
    - Rochus 7y ago
      Good to know, thanks.
- nafey 7y ago
  Are you familiar with Jai language being developed by Jonathan Blow? What is your opinion on its design?
  - WalterBright 7y ago
    My opinion is that Jonathan Blow is an amazing developer and he should be joining us on D! It's been a while since I reviewed the language, and I'd have to re-review it to say anything sane here. But one thing stuck out at me. In D, the support for Compile Time Function Execution (CTFE) is very extensive, and opens the door to a lot of incredible metaprogramming abilities. Jai has this too, but has extended it to allow system calls. While his demos of programs being run in the compiler is impressive, D doesn't support CTFE system calls for a good reason: It'll become a vector for malware. People download source code from the intertoobs all the time, and just compile it. Heaven help us if that means your system is now compromised. I'm not going to open that door and make people afraid to compile D code. It's not worth it.
    - 7y ago
pbiggar 7y ago
This advice is quite good for certain types of programming language, if you look at the world the same was as he does. We're implementing Dark from a completely different worldview, and from that vantage point, a lot of these aren't exactly wrong, but different. > Syntax matters The approach we took with Dark is that there isn't a syntax, per se, in that there isn't a parser. There's certainly a textual view of Dark and so it's important that the code looks good (it currently looks only OK, in my opinion). But as a result, we have other options for minimizing keystrokes (autocomplete built-in), parsing (again, no parse), and minimizing keywords (you're allowed have a variant with the same name as a keyword, which isn't allowed in languages with parsers (well, lexers, but same idea). > context free grammars No parser, no need to have a grammar. His point about IDEs is great - we only support our own IDE (a controversial decision to be sure!) > Redundancy This is an esoteric parsing problem, that only applies if you have a parser. No parser means no syntax errors. We are left with editor errors (how does the editor have good UX) and run-time errors. > Implementation He's right about how hard error messages are, so I feel good about our "not parsing" approach. > Compiler speed Our compilation is instant. The way it's instant is: - very small compilation units: you're editing a single function at a time, and so nothing else needs to be parsed. - no parser: The editor directly updates the AST, so you don't have to read the whole file (there isn't a "file" concept). Even in JS, that means an update takes a few milliseconds at the most. - extremely incremental compilation: making a change in the editor only changes the exact AST construct that's changing. > Lowering This is really about compilation. One thing you can do, which is what we do, is have an interpreter. Now, interpreters are slow, but we simply have a different goal with the language, which is to run HTTP requests quickly. We do run into problems with the limit of the interpreter, but we plan to add a compiler later to deal with this. Really what I'm suggesting here is that compiled languages look at having interpreters in addition to compilers. > i/o performance > memory allocation I think he's approaching this with an implicit goal of "it must be as fast as possible", which isn't necessarily a goal for all languages. > You’ve done it, you’ve got a great prototype of the new language. Now what? Next comes the hardest part. This is where most new languages fail. You’ll be doing what every nascent rock band does — play shopping malls, high school dances, dive bars, etc., slowly building up an audience. For languages, this means preparing presentations, articles, tutorials, and books on the language. Then, going to programmer meetings, conferences, companies, anywhere they’ll have you, and show it off. You’ll get used to public speaking, and even find you enjoy it (I enjoy it a lot). Well this is certainly correct!
matheusmoreira 7y ago
Is it true that optimization follows the 80/20 rule? What are some common performance issues that new languages and their implementations face? Are there common optimization techniques that can be applied in order to make the new language competitive with existing ones? For example, I know that it's generally better to compile programs into a linear code structure such as bytecode instead of interpreting a tree structure directly.
- barrkel 7y ago
  Linear encoding is better than interpreting a tree because accessing adjacent elements in arrays is faster than chasing pointers. Poor performance depends on what your language does. What's poor performance for SQL will be different than for JS. Features which don't have efficient implementations will be slow. If the language encourages use of inefficient features, then it will generally be slower. The easiest optimization technique is to leverage an existing back end; for example, target LLVM or JVM or .NET.
  - matheusmoreira 7y ago
    > Linear encoding is better than interpreting a tree because accessing adjacent elements in arrays is faster than chasing pointers. Yes. From this we can derive some general optimization principles: reduce indirection, increase data locality. Are there any others? > Poor performance depends on what your language does. What's poor performance for SQL will be different than for JS. Let's consider modern dynamic languages like Javascript and Python. What performance problems did these languages face? Which optimizations had the biggest impact on code execution performance? Which optimizations were the easiest to understand and implement? For example, I know Javascript virtual machines will automatically create hidden classes for objects. This allows the data to be accessed by constant offsets rather than lookups.
    - barrkel 7y ago
      You're sticking your toe in a very big lake, and this isn't the right forum to meaningfully talk about it. (I don't mean this in any way negatively, but your two posts have a distinct whiff of Help Vampire - https://meta.stackexchange.com/questions/19665/the-help-vampire-problem https://meta.stackexchange.com/questions/19665/the-help-vamp... - just a tiny chunk of information, and a naive question where you'd need years to properly survey the knowledge. It's a big topic and you need to be goal directed to get anywhere IMO.)
somewhereoutth 7y ago
I am currently developing a language, though more as a research project than anything practical. Apologies for jumping on this post, but it is a good opportunity to organize and set out my thoughts (and possibly someone might find it interesting): Essentially the language is a pure functional language that takes the untyped lambda calculus and adds decoration terms as first class citizens in the calculus. These terms can be used to wrap selected combinators (eg church numerals). The normal beta reduction rules are extended to handle these decorations in a useful way. The decorations allow predicates to be formed that are total over the term space (eg isChurchNumeral?), which means that function call identifiers can be dynamically dispatched based on their arguments (using a certain amount of term assembly from the surface syntax). Adhoc polymorphism can thus be encoded in a transparent fashion. This has been sufficient to build a numerical tower up to and including the Complex numbers, such that the usual operations add, mul, sub, div are defined within and between Natural, Integer, Rational and Complex numbers. It can also manipulate strings as if they were lists, whilst retaining their 'stringyness'. All without needing number or string specific features internal to the runtime (save parsing and formatting on the way in and out). REPL examples: > (sum [1 -3 2.5 3/2 1+2i]) > 3+2i > (reverse "hello") > "olleh" Something resembling Haskell's typeclasses naturally arises, with the usual definitions of Functor, Monad, and Applicative. It is, needless to say, astonishingly slow.
- tpush 7y ago
  From your description it sounds like these decorators are an alternative to type annotations? Mind showing how these decorators look and work? I'm also building a language, and always interested in seeing novel features like these :).
  - somewhereoutth 7y ago
    Possibly an alternative - but operating at the term level as predicates - if you consider 'type' to be a total function dividing your term space into 'of the type' and 'not of the type'. Church numerals: 0 = (^Nat (\f \x x)) 1 = (^Nat (\f \x (f x))) The ^Nat is the decoration, and can be recovered with a special predicate function ?Nat. So: (?Nat (^Nat (\f \x x))) =>Beta (^Bool (\x \y x)) *i.e. true* For this to work the inner part must be reduced first. It does seem to be consistent with Normal order reduction - the Y combinator etc work as expected.
mrlonglong 7y ago
Zortech C was fabulous, wrote a disk editor in it many moons ago. Kudos!
- WalterBright 7y ago
  Thanks for the kind words! Zortech was indeed a great compiler for its time.
  - a9h74j 7y ago
    Years ago IIRC you put out a request for original Zortech C++ disks and packaging, if anyone had some. I was sorry that I had just disposed of mine six months earlier. .. That was my one-and-only C++ in the early 90's, and I am still programming in D. Sorry I couldn't help!
    - WalterBright 7y ago
      No problem. By the kind work of many people, I managed to accrete a fairly complete collection.
      - mrlonglong 7y ago
        I still have Zortech C 1.06 on my old P166. I should boot it up to see if it still lives !
jakear 7y ago
Off topic: Annoying that this is totally unreadable even at 300% zoom on an iPhone 11 Pro. I feel like a set of people refuse to learn proper HTML/CSS as some sort of statement, not realizing their laziness renders their work unavailable to the visually disabled. HN behaves similarly poorly.
- nerdponx 7y ago
  The irony is that if this site were actually simple (i.e. just text without a sidebar) it would be as responsive as you needed it to be. In the worst case scenario, you could fix it with client-side CSS. The problem here is that the site is complicated beyond what HTML is meant to do: it has a sidebar. It's no longer just a document; it's a document and a navigation menu. Effectively it's a small software application, and once you're in the business of writing software applications you ought to be in the business of accessibility and UX design.
- saagarjha 7y ago
  What's wrong with Hacker News?
  - jakear 7y ago
    it doesn't respect iOS font size, and you can't alter the zoom to make the text actually bigger. It zooms the entire page rather than just the text, so the text doesn't re-flow. It's pretty much equivalent to just pinching to zoom, when it should be adjusting the font size.
    - catalogia 7y ago
      Why can firefox on the desktop resize the font on HN and reflow the content, but iOS cannot?
      - jakear 7y ago
        Beats me. But usually the onus is on the application developer to make their content accessible on all platforms. Especially one as common as iOS Safari
Animats 7y ago
That's a good set of questions for 2014. Questions that have become important more recently include: - Imperative? Functional? Some mixture of both? Mixtures of the two tend to have syntax problems. - Concurrency primitives. The cool kids want "async" now. Mostly to handle a huge number of slow web clients from one server process. Alternatively, there are "green threads", which Go calls "goroutines". All this stuff implies some level of CPU dispatching in compiled code. - Concurrency locking. Really hard problem. There's the Javascript run to completion approach, which reappears in other languages as "async". Ownership based locking, as in Rust, is promising, but may lock too much. And what about atomic operations and lockless operations? Source of hard to find bugs. Get this right. - Ownership. Rust got serious about this, with the borrow checker. C++ now tries to do "move semantics", with modest success, but has trouble checking at compile time for ownership errors. Any new language that isn't garbage collected has to address this. Historically, language design ignored this problem, but that's in the past. - Metaprogramming. Templates. Generics. Capable of creating an awful mess of unreadable code and confusing error messages. From LISP macros forward, a source of problems. Needs really good design, and there aren't many good examples to follow. - Integration with other languages. Protocol buffers? SQL? HTML? Should the language know about those? - GPUs. Biggest compute engines we have. How do we program them?
- zzo38computer 7y ago
  I would say possibly to use a different programming language for GPU than CPU. I like the idea of Checkout (see [0]) for GPU programming, although unfortunately it is not implemented and the preprocessor is not yet invented. (The trigonometric functions are also missing. They should probably have at least sine, cosine, and arctangent, since these functions seem like useful to me when doing graphics.) [0] http://esolangs.org/wiki/Checkout http://esolangs.org/wiki/Checkout
  - neutronicus 7y ago
    I think using trig and especially inverse trig is almost always an antipattern in graphics code. Careful use of dot and cross product will almost always be both more performant and more robust.
zzo38computer 7y ago
In some programming languages, e.g. TeX, Forth, PostScript, etc you cannot really syntax highlight the program without executing it. However, syntax highlighting is a feature that I can do without, and I don't think those programming languages are bad. In some programming languages, such as C and Free Hero Mesh, you can read the sequence of tokens despite there are macros, which you need not parse to find where the tokens are (although I think older versions of the C preprocessor did not work like this). They mention tools. I do think valgrind is sometimes helpful; I do use that. However, Git is not the only version control system; some people prefer others, such as Mercurial, Fossil, etc. I use Fossil. They also mention error messages. I like the first one; print one error message and quit. However, in some cases, it might be possible to easily just ignore that error and continue after displaying the error message (and then finally fail at the end). It might also be possible to skip a lot of stuff, and then continue, e.g. if there is an unknown variable or function then you might display an error message and then skip the entire statement that mentions it. They mention a runtime library. This should be reduced as much as possible, I think, and if you can make it so that it has functions which will only be included in the compiled program when they are used, that can be a good idea, since you can include some functions that many people don't need and don't waste space and time with them. Something they did not mention but I think it is very good to have and useful is metaprogramming and 'pataprogramming. But I also think that different programming languages can be good for different purposes, and that some are domain specific, and some are easier to write than others. This can be done using existing syntax or new syntax, and I have done both, and so have some others. Another thing that I can recommend to have is a discussion system with NNTP; even Digital Mars themself have a NNTP-based discussion system. Perhaps better will be to have the same messages with NNTP, web forum, and mailing lists; again, this is what Digital Mars does. However, I do think that minimizing keystrokes is helpful. Minimizing runtime dependencies and runtime memory usage is also helpful.
- ken 7y ago
  > In some programming languages, e.g. TeX, Forth, PostScript, etc you cannot really syntax highlight the program without executing it. Technically true. In practice, however, I've run into way more issues with syntax highlighters in overly-complex fixed languages than I have with simpler-but-programmable languages.
DonaldFisk 7y ago
You might be doing this as a learning exercise, in which case it doesn't need to be particularly innovative, and writing another Lisp or Forth implementation is fine. In fact, I'd recommend beginning along those lines, followed by developing several different new languages, probably domain-specific ones. Your first attempts probably won't be worth keeping. (I haven't kept the object oriented Prolog I wrote about 25 years ago, but I do regularly use a small Prolog I recently wrote in Lisp.) The languages at the roots of all programming languages are Fortran, Lisp, Cobol, Algol60, APL, Snobol, Forth, Prolog, OPS5, SASL, Smalltalk, Prograph. (If I've missed any out, or any of the above have important predecessors, please let me know.) A new language is unlikely to be radically different from any of those languages or their descendants - of those I listed, the most recent is from the mid 1980s. Within the descendants, which is your favourite? Can you make big improvements to it? If so, make them. Otherwise, can you improve another language so that it becomes your favourite? One heuristic I've found useful: the right design choices at the start might be unknown, but when I need make them, they're obvious to me, and often a particular choice leads to other equally obvious choices. If the choice isn't obvious, I've probably done something wrong. My own preference is for pure rather than hybrid languages with simple regular syntaxes (i.e. one idea expressed well), and very strong static typing. My favourite language is Common Lisp or rather a subset of it. I have trouble thinking of ways to make it significantly better. But I also like the idea of dataflow (a few decades ago I knew some of those working on experimental dataflow hardware), and graphical programming seems to be the right approach to dataflow. Prograph was the closest existing language to what I wanted. It's isn't pure dataflow, it's dynamically typed, it's object oriented (so, unless it's Smalltalk it's hybrid), and entering programs in it involves too many mouse gestures and keystrokes. So I'm implementing a new language which corrects those deficiencies. It's been particularly difficult because I have to write an IDE as well as the language, and there aren't any textbooks I can rely on for help. I'll have succeeded if I use the new language more often than I do Lisp, and if along the way I get a few more papers (two so far) and some academic interest, so much the better. I don't expect a wide user base. If that was important to me, it would have C syntax and I'd try to get corporate backing. Your criterion for success might differ from mine.
- lioeters 7y ago
tom-thistime 7y ago
"Wanna know the secret of making [X] fast? [...] Use a profiler." Still really valuable advice. We know it, but do we do it?
pfdietz 7y ago
A reason for simple parsing is to make the toolchain for the language easier. And in particular, you don't want a preprocessor. Try to parse your program into an AST? You can't in C/C++ in general -- you can only parse it for a particular set of preprocessor defines, which will leave out large chunks that were deleted during preprocessing.
nostrademons 7y ago
I used to be big into programming language design, but eventually decided that there just wasn't enough headroom to do something innovative enough to warrant the switching costs. The world doesn't need yet another syntax on top of basic C-style or Lisp-style semantic constructs. Lately I've been wondering if I should reconsider, though, and have had a bunch of ideas that blur the lines of what should be considered in-scope for a programming language. Things like: 1. Universal constructs for serial & parallel execution, but with user-defined semantics for where the code should execute. So for example, at low-scale you'd execute in a loop on the CPU. At mid-scale it'd run on the GPU. At high-scale you could transparently distribute across thousands of GPU boxes. 2. Profiling and execution statistics built into the language. Write your code, run it on representative data, and instantly get statistics on how many times each function is called, what the average size of data structures is, how much memory is used, etc. Profilers do this, but often not at a granularity that's particularly useful (ever tried to find out how many Strings are created within a particular dynamic call-tree?), and most new languages overlook implementing a profiler, leaving it to third-party vendors. This is a shame, because a standardized programmatic API to a profiler could be a very effective compiler tool, leading to... 3. A way of defining transformations between data representations, benchmarking the cost of those transformations, and then having the compiler automatically decide whether it's worth bulk-converting data based on typical profiler results. The motivating example for this is the AoS-SoA transformation, but they also feature in common system design questions like "Do you unpack all of the fields of this wire protocol, or lazily construct an object only when necessary?" or "Should you zip your data before sending it in an RPC?" or "Do you do this work at indexing or serving time?" 4. The ability to dump intermediate data from any function call site to disk, and then restart program execution from there without re-running the whole program. Handy when iterating on a complex algorithm. 5. Drill-down data visualizations for large collections. If you've ever tried to find the logic bug in a 500,000 element array using a standard IDE debugger, you'll know about this pain point. 6. Built-in support for machine-learning. In particular, many ML applications need extensive preprocessing, and you need to preprocess the data in exactly the same way for training and serving. Wouldn't it be neat if you could write your traditional algorithms, dump out your signals at the particular call-site of the classifier, and then have the development environment automatically send it to Mechanical Turk or Craigslist for labeling? Then have the system return the labeled data in a format easily suited for your ML framework of choice, do your data analysis & training, and import the finished model back into the call site of the language. 7. GPU-native, with language constructs that lead to efficient GPU code. This is becoming increasingly important not just for execution speed, but for developer velocity, because devs in data-intensive areas can waste a significant amount of time waiting for their program to run.
tanin 7y ago
What a great article. It's something I need to read, as I have been working on my own programming language for a while now. This creating-programming-language-thing is so difficult and so much effort. (I'm stuck at designing how string works right now) +1 on writing parser by hand. I've done it once with java (https://github.com/tanin47/javaparser.rs https://github.com/tanin47/javaparser.rs), and I switched my own programming language from a parser generator to a hand-written one. Once you know how to write a parser by hand, it's a much better approach (e.g. easier to test, modularizable). My programming language is a bit strange in a way that I drop the performance requirement. Performance distorts other aspects. I focus on making the language featureful and beautiful instead. I hope I'll achieve this dream of making a usable programming language one day.
ChicagoDave 7y ago
I just started down this road. I’ve mucked with scanning text into object trees but want learn how to make my own language. The difference is this would be a very small domain-specific language that controls an in-memory graph data store targeting interactive stories. There are great existing tools for this sort of thing, but I have theories/ideas I want to explore. I’m glad there are healthy discussions on compilers.
valera_rozuvan 7y ago
One should consider creating a VM first - it simplifies life a bit, and makes the language more portable in the future. The implementation task is split in two - compiler and VM. First, compiler targets the VM. Second, the VM targets the CPU. This way porting to different architectures is just a matter of adding to the VM to interface with the new arch. A compiler and VM definitely are 2 separate projects with their own set of issues. Also we should consider the possibility of going the eDSL (embedded domain-specific language) route. Working at a very high level, re-using existing constructs of the host language. If one is interested, looking into SICP [1] will show an example of such a project. Using Scheme to build an interpreter. This can easily be done in several days. Best to try to reduce doing work that has been done many times before. ---------- [1] https://mitpress.mit.edu/sites/default/files/sicp/index.html https://mitpress.mit.edu/sites/default/files/sicp/index.html
deleted 7y ago
[deleted]
bogomipz 7y ago
>"Context free grammars. What this really means is the code should be parseable without having to look things up in a symbol table. C++ is famously not a context free grammar." Could someone elaborate on why C++ is not a "not a context free grammar"? Also how does C++ deal with this fact?
- colejohnson66 7y ago
  Here’s a good Medium post on why C++ is undecidable: https://medium.com/@mujjingun_23509/full-proof-that-c-grammar-is-undecidable-34e22dd8b664 https://medium.com/@mujjingun_23509/full-proof-that-c-gramma...
  - bogomipz 6y ago
    This is a great read! It summed things up quite nicely with some good graphics as well. Cheers.
teleforce 7y ago
As you are probably aware that the author of the article is the designer of the D programming language. For background reading of the design of D programming language, this is a very interesting and insightful paper on the history and the origins of D programming language up to 2018 [1]. [1] http://erdani.com/hopl2020-draft.pdf http://erdani.com/hopl2020-draft.pdf

250 points by pcr910303 7y ago

I want to implement a toy programming language, but I have questions regarding the following in that article: > Context free grammars. What this really means is the code should be parseable without having to look things up in a symbol table. C++ is famously not a context free grammar. A context free grammar, besides making things a lot simpler, means that IDEs can do syntax highlighting without integrating in most of a compiler front end, i.e. third party tools become much more likely to exist. Many complex languages, like c++, rust are not context free. We therefore need semantic analysis. What programming language features will be compromised if I stick to context free? Will the end result be as expressive as c++/rust? Any programming language that is massively adopted is context free? BTW, the toy language I want to build will be something similar to javascript.

steveklabnik 7y ago
Rust is almost context free; there’s one relatively rarely used bit that requires context. And usually it’s only one or two bytes of it.
- h-cobordism 7y ago
  You're referring to raw string literals, right?
  - steveklabnik 7y ago
    Yes. You need to include more #s than you have in the string, and it’s rare to have a ton of them, let alone a raw string literal in the first place.
    - wtetzner 7y ago
      Does that make the grammar context-sensitive, or just the lexer?
      - steveklabnik 7y ago
        This is not an area of my expertise, so I can't say.
- deleted 7y ago
  [deleted]
desc 7y ago
https://stackoverflow.com/questions/898489/what-programming-languages-are-context-free https://stackoverflow.com/questions/898489/what-programming-... Most languages have context-free syntax, which is what the article refers too. There really is no reason to sacrifice that. Even modern PHP recognises the value of having a parse tree independent of an entire compiler. Context-free semantics is an entirely different matter, and I'm not even sure what it'd mean...
- chubot 7y ago
  The two top answers are in conflict. The second answer with 43 points is closer to right: There are hardly any real-world programming languages that are context-free in any meaning of the word. The first answer with 41 points is totally wrong: The set of programs that are syntactically correct is context-free for almost all languages ----- A better source is this whole series by Trevor Jim, which has nice ways of relating theory to practice. He lists a bunch of reasons why you could consider nearly all programming languages not context-free. http://trevorjim.com/parsing-not-solved/ http://trevorjim.com/parsing-not-solved/ -- hundreds of parser generators support context-free grammars, but there are almost no context-free languages in practice. http://trevorjim.com/python-is-not-context-free/ http://trevorjim.com/python-is-not-context-free/ -- A main point here is that you have to consider the lexer and parser separately. Grammars don't address this distinction, which arises in essentially all programming languages. Also there is some lexical feedback, similar in spirit to C's lexer hack. http://trevorjim.com/haskell-is-not-context-free/ http://trevorjim.com/haskell-is-not-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-language-is-context-free/ http://trevorjim.com/how-to-prove-that-a-programming-languag... http://trevorjim.com/c-and-cplusplus-are-not-context-free/ http://trevorjim.com/c-and-cplusplus-are-not-context-free/ -- the way LALR(1) conflicts are resolved in practice can make a language not context-free (copying from a recent comment)
  - WalterBright 7y ago
    The implementation of D has a lexer that is independent of the parser, and a parser that is independent of the rest of the implementation. I have resisted enhancement proposals that would put holes in those walls.
tom_mellior 7y ago
This point in the article is pretty weird (the rest is good). I don't think IDEs do a lot of parsing to do syntax highlighting, isn't it all just regex matching to identify the types of tokens? I'd be interested in real-world examples of IDEs doing something more complex to achieve syntax highlighting. And conversely, examples of imperfect syntax highlighting of C++ due to the undecidability of its input language. I mean, yes, an actual parser for C++ must be able to execute template computations, and that's a pain, but why would that be relevant to syntax highlighting? It isn't. Now, there are valid reasons for running a proper language frontend from the IDE: Error reporting of all kinds, not just syntax but also type errors and whatever else the compiler likes to complain about. But there the IDE should not try to replicate the parser. Parsing only a context-free surface language will not catch type errors, exactly because enforcing a static type system requires one to "look things up in a symbol table". So the actual compiler should provide an IDE-friendly mode where it runs its frontend and reports errors back, and the IDE should not try to roll its own version of this. In other words, the IDE is not relevant either way. > Any programming language that is massively adopted is context free? Statically typed languages require semantic analysis and symbol table lookups, so they are out. And yet we have context-free grammars for all widely adopted statically typed programming languages. And we also have additional semantic checks for all of them. The notion of a "context free programming language" being one that has context free syntax and no semantic checks at all is not a useful notion. Don't worry about it while designing your language.
- alpaca128 7y ago
  > I don't think IDEs do a lot of parsing to do syntax highlighting, isn't it all just regex matching to identify the types of tokens? IntelliJ highlights variables etc. differently if they're unused and can highlight different identifiers in different colors. Not sure about other current IDEs. That said I never felt like I needed such features, normal syntax highlighting does the job pretty well for me.
  - dehrmann 7y ago
    IntelliJ has context-aware autocomplete. Type this.field.get and it will show methods and fields starting with get for whatever type field is. There's a lot of context needed to make that happen.
tomp 7y ago
The purpose of context-free, or rather unambiguous grammars in general, isn't for the benefit of compilers, but for the benefit of humans. A computer can parse almost everything, even regexes (with backtracking etc.), it's the humans that trip over fancy grammars.
kyllo 7y ago
Context-free has nothing to do with symbol tables, it just means that in the grammar, the left-hand side of a production rule can only have a single non-terminal symbol, which can always be replaced by the expression on the right-hand side, without ambiguity. Language features are an orthogonal issue--you can implement any language feature with a CFG, but you just can't reuse the same keyword or operator to have different meanings in different grammatical contexts. A classic example is that in C++ it is impossible to know whether << is brackets around template arguments, or the left bit shift operator, or the stream output operator, without arbitrary lookahead--you need to parse the rest of the statement in order to decide which one it is in the current statement's context. Generally language designers don't choose to implement a context-sensitive grammar on purpose because they desire some feature that requires it; they strive for a context-free grammar, but end up with a handful of special cases that require context-sensitive parsing because of either convenience or legacy reasons. Popular programming languages nearly all use custom parsers written in other (or the same) Turing-complete programming languages, so it's not "harder" to parse the context-sensitive rules, it only poses a problem if you want to use a parser generator to implement parsing for a CSG.
- johannes1234321 7y ago
  > A classic example is that in C++ it is impossible to know whether << is brackets around template arguments, or the left bit shift operator, or the stream output operator, without arbitrary lookahead--you need to parse the rest of the statement in order to decide which one it is in the current statement's context. The classic example, I guess, is the most vexing parse: https://en.m.wikipedia.org/wiki/Most_vexing_parse https://en.m.wikipedia.org/wiki/Most_vexing_parse """ The line TimeKeeper time_keeper(Timer()); is seemingly ambiguous, since it could be interpreted either as a variable definition [...] a function declaration [...] """ These things you can only resolve by having the symbol tables around and checking. The parser alone can't tell. A language could avoid this i.e. by requiring specific keywords or having more distinct syntax. Humans (programmers) however often can deal with ambiguity, we have it in humannlanaguage as well and context on most cases helps and I argue those aren't practical problems. (While that's only opinion)
a1369209993 7y ago
Note that "context free grammars", in the technical sense, is completely the wrong thing. Eg, enforcing consistent indentation is not context free: foo() { return; } ↓↓↓↓↓↓↓↓↓↓↓ aaaa{ bbbbreturn; cccc} ↓↓↓↓↓↓↓↓↓↓↓ aaaabbbbcccc This is equivalent to aⁿbⁿcⁿ, which is pretty much the canonical example of a non-context-free language. What you acually want is not context-free grammar, but, as TFA says: > the code should be parseable without having to look things up in a symbol table
- qznc 7y ago
  There is a trick for indentation: Use a context-sensitive lexer in front of a context-free parser. The lexer serves indent and dedent tokens to the parser. With this trick, you can parse Python with a context-free grammar.
- bmn__ 7y ago
  There are plenty, the majority even, of programming languages that do not enforce consistent indentation. You make a false generalisation when you claim that CFG are completely the wrong thing.
- tom_mellior 7y ago
  > This is equivalent to aⁿbⁿcⁿ Is it? You only indent with spaces, so a = b = c = ' ', and the problem you claim disappears.
  - gbear605 7y ago
    I'm not sure that's a solution. The problem is verifying that the three 'n's are equal, not that 'a', 'b', and 'c' are equal. Solving this cannot be done in a context free grammar [0]. [0]: https://cs.stackexchange.com/questions/33153/is-an-bn-cn-context-free https://cs.stackexchange.com/questions/33153/is-an-bn-cn-con...
    - tom_mellior 7y ago
      Yeah, you're right. I got confused by the original phrasing.
froh 7y ago
Notwithstanding the other comments on context free vs sensitive, the 2014 article predates the language server protocol, which neatly moves the support for programming languages from the IDE to a stand alone tool tied to the language: https://microsoft.github.io/language-server-protocol/ https://microsoft.github.io/language-server-protocol/ https://en.m.wikipedia.org/wiki/Language_Server_Protocol https://en.m.wikipedia.org/wiki/Language_Server_Protocol So that IDE support point has become much weaker, if not moot.

xiphias2 7y ago

,,grammar should be redundant. You’ve all heard people say that statement terminating ; are not necessary because the compiler can figure it out. '' I'll stay with my non-redundant Julia language, thank you very much. It gave me a lot of joy to programming, and I don't remember having big problems with error messages. Even if I have, syntactic errors are trivial to find. The hard parts of efficient programming are memory management (garbage collection), controlling vectorizing instructions, balance between ease of GPU programming and efficiency, parallelization, not semicolons at the end of a line. All programming languages have to decide on how low level control they give to the computer resources, and how they abstract them, to make high level programming possible without sacrificing too much efficiency.

adimitrov 7y ago
Whilst you're not wrong about what you value about a programming "language", I'd say there is an important distinction to be drawn between two things people tend to conflate: the language and the runtime. Perhaps a counterexample is in order to explain it: Java the language and Java the runtime (VM, stl) are two different things entirely. Kotlin, for example makes a lot of different choices in language design (e.g. semicolons) while reusing the same runtime (GC, threads, etc.) Of course, you can often not tease these two concerns apart easily and neatly, but there is merit in giving thought to the ergonomics of the pure language side of things. At the end of the day, a programming language doesn't need an implementation to be useful (e.g. as a teaching tool) as it's an abstract, formal concept.

didibus 7y ago

After learning s-expression based syntax, I am just baffled why we even bother with anything else. When you play around with different Lisps, the syntax is always the same, the language differences becomes the semantics only. Other languages put too much emphasis on the syntax in my opinion. And while I understand the "popularity" appeal. I've almost never seen someone learning the s-expression syntax and afterwards not liking it. Basically I think it be worth it to push people to learn the s-expression syntax just so we can stop wasting our time with syntax afterwards. Also if I recall, without user macros, I think s-expression syntax is context free no?

daenz 7y ago
It's simple, but it's fundamentally reductionist. You can ease the cognitive load by making certain programming structures first-class citizens in the language.
- amelius 7y ago
  Yes but now you have to worry about parentheses and at what nesting level certain constructs should live.
  - pfdietz 7y ago
    An adequate editor with autoindent and paren matching solves those problems completely.
- F-0X 7y ago
  > You can ease the cognitive load by making certain programming structures first-class citizens in the language. Which, in every s-expression based language I'm aware of, can be achieved using macros.
  - chrisseaton 7y ago
    Isn't that the point - s-expressions aren't good enough so people work around them by writing more conventional languages and parsers (the reader macros) to avoid having to write in them.

chubot 7y ago

On regexes, he is generalizing from a small number of examples. Some lexers are straightforward to write by hand, but others are better done with a code generator. edit: I should really say that you should consider using regular languages to lex your programming languages, not (Perl-style) regexes. Those are different things: https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ I used re2c for Oil and it saves around 5K-10K lines of "groveling through backslashes and braces one a time" (e.g. what other shells do) http://www.oilshell.org/blog/2019/12/22.html#appendix-a-oils-lexer-uses-two-stages-of-code-generation http://www.oilshell.org/blog/2019/12/22.html#appendix-a-oils... And the parser is faster than bash overall: http://www.oilshell.org/blog/2020/01/parser-benchmarks.html http://www.oilshell.org/blog/2020/01/parser-benchmarks.html

WalterBright 7y ago

Author here. AMA!

Rochus 7y ago
The article is from 2014. Is it still current? What would you change in 2020?
- WalterBright 7y ago
  I'd write the same thing today. 6 years more experience just confirms it.
  - Rochus 7y ago
    Good to know, thanks.
nafey 7y ago
Are you familiar with Jai language being developed by Jonathan Blow? What is your opinion on its design?
- WalterBright 7y ago
  My opinion is that Jonathan Blow is an amazing developer and he should be joining us on D! It's been a while since I reviewed the language, and I'd have to re-review it to say anything sane here. But one thing stuck out at me. In D, the support for Compile Time Function Execution (CTFE) is very extensive, and opens the door to a lot of incredible metaprogramming abilities. Jai has this too, but has extended it to allow system calls. While his demos of programs being run in the compiler is impressive, D doesn't support CTFE system calls for a good reason: It'll become a vector for malware. People download source code from the intertoobs all the time, and just compile it. Heaven help us if that means your system is now compromised. I'm not going to open that door and make people afraid to compile D code. It's not worth it.
  - 7y ago

pbiggar 7y ago

This advice is quite good for certain types of programming language, if you look at the world the same was as he does. We're implementing Dark from a completely different worldview, and from that vantage point, a lot of these aren't exactly wrong, but different. > Syntax matters The approach we took with Dark is that there isn't a syntax, per se, in that there isn't a parser. There's certainly a textual view of Dark and so it's important that the code looks good (it currently looks only OK, in my opinion). But as a result, we have other options for minimizing keystrokes (autocomplete built-in), parsing (again, no parse), and minimizing keywords (you're allowed have a variant with the same name as a keyword, which isn't allowed in languages with parsers (well, lexers, but same idea). > context free grammars No parser, no need to have a grammar. His point about IDEs is great - we only support our own IDE (a controversial decision to be sure!) > Redundancy This is an esoteric parsing problem, that only applies if you have a parser. No parser means no syntax errors. We are left with editor errors (how does the editor have good UX) and run-time errors. > Implementation He's right about how hard error messages are, so I feel good about our "not parsing" approach. > Compiler speed Our compilation is instant. The way it's instant is: - very small compilation units: you're editing a single function at a time, and so nothing else needs to be parsed. - no parser: The editor directly updates the AST, so you don't have to read the whole file (there isn't a "file" concept). Even in JS, that means an update takes a few milliseconds at the most. - extremely incremental compilation: making a change in the editor only changes the exact AST construct that's changing. > Lowering This is really about compilation. One thing you can do, which is what we do, is have an interpreter. Now, interpreters are slow, but we simply have a different goal with the language, which is to run HTTP requests quickly. We do run into problems with the limit of the interpreter, but we plan to add a compiler later to deal with this. Really what I'm suggesting here is that compiled languages look at having interpreters in addition to compilers. > i/o performance > memory allocation I think he's approaching this with an implicit goal of "it must be as fast as possible", which isn't necessarily a goal for all languages. > You’ve done it, you’ve got a great prototype of the new language. Now what? Next comes the hardest part. This is where most new languages fail. You’ll be doing what every nascent rock band does — play shopping malls, high school dances, dive bars, etc., slowly building up an audience. For languages, this means preparing presentations, articles, tutorials, and books on the language. Then, going to programmer meetings, conferences, companies, anywhere they’ll have you, and show it off. You’ll get used to public speaking, and even find you enjoy it (I enjoy it a lot). Well this is certainly correct!

matheusmoreira 7y ago

Is it true that optimization follows the 80/20 rule? What are some common performance issues that new languages and their implementations face? Are there common optimization techniques that can be applied in order to make the new language competitive with existing ones? For example, I know that it's generally better to compile programs into a linear code structure such as bytecode instead of interpreting a tree structure directly.

barrkel 7y ago
Linear encoding is better than interpreting a tree because accessing adjacent elements in arrays is faster than chasing pointers. Poor performance depends on what your language does. What's poor performance for SQL will be different than for JS. Features which don't have efficient implementations will be slow. If the language encourages use of inefficient features, then it will generally be slower. The easiest optimization technique is to leverage an existing back end; for example, target LLVM or JVM or .NET.
- matheusmoreira 7y ago
  > Linear encoding is better than interpreting a tree because accessing adjacent elements in arrays is faster than chasing pointers. Yes. From this we can derive some general optimization principles: reduce indirection, increase data locality. Are there any others? > Poor performance depends on what your language does. What's poor performance for SQL will be different than for JS. Let's consider modern dynamic languages like Javascript and Python. What performance problems did these languages face? Which optimizations had the biggest impact on code execution performance? Which optimizations were the easiest to understand and implement? For example, I know Javascript virtual machines will automatically create hidden classes for objects. This allows the data to be accessed by constant offsets rather than lookups.
  - barrkel 7y ago
    You're sticking your toe in a very big lake, and this isn't the right forum to meaningfully talk about it. (I don't mean this in any way negatively, but your two posts have a distinct whiff of Help Vampire - https://meta.stackexchange.com/questions/19665/the-help-vampire-problem https://meta.stackexchange.com/questions/19665/the-help-vamp... - just a tiny chunk of information, and a naive question where you'd need years to properly survey the knowledge. It's a big topic and you need to be goal directed to get anywhere IMO.)

somewhereoutth 7y ago

I am currently developing a language, though more as a research project than anything practical. Apologies for jumping on this post, but it is a good opportunity to organize and set out my thoughts (and possibly someone might find it interesting): Essentially the language is a pure functional language that takes the untyped lambda calculus and adds decoration terms as first class citizens in the calculus. These terms can be used to wrap selected combinators (eg church numerals). The normal beta reduction rules are extended to handle these decorations in a useful way. The decorations allow predicates to be formed that are total over the term space (eg isChurchNumeral?), which means that function call identifiers can be dynamically dispatched based on their arguments (using a certain amount of term assembly from the surface syntax). Adhoc polymorphism can thus be encoded in a transparent fashion. This has been sufficient to build a numerical tower up to and including the Complex numbers, such that the usual operations add, mul, sub, div are defined within and between Natural, Integer, Rational and Complex numbers. It can also manipulate strings as if they were lists, whilst retaining their 'stringyness'. All without needing number or string specific features internal to the runtime (save parsing and formatting on the way in and out). REPL examples: > (sum [1 -3 2.5 3/2 1+2i]) > 3+2i > (reverse "hello") > "olleh" Something resembling Haskell's typeclasses naturally arises, with the usual definitions of Functor, Monad, and Applicative. It is, needless to say, astonishingly slow.

tpush 7y ago
From your description it sounds like these decorators are an alternative to type annotations? Mind showing how these decorators look and work? I'm also building a language, and always interested in seeing novel features like these :).
- somewhereoutth 7y ago
  Possibly an alternative - but operating at the term level as predicates - if you consider 'type' to be a total function dividing your term space into 'of the type' and 'not of the type'. Church numerals: 0 = (^Nat (\f \x x)) 1 = (^Nat (\f \x (f x))) The ^Nat is the decoration, and can be recovered with a special predicate function ?Nat. So: (?Nat (^Nat (\f \x x))) =>Beta (^Bool (\x \y x)) *i.e. true* For this to work the inner part must be reduced first. It does seem to be consistent with Normal order reduction - the Y combinator etc work as expected.

mrlonglong 7y ago

Zortech C was fabulous, wrote a disk editor in it many moons ago. Kudos!

WalterBright 7y ago
Thanks for the kind words! Zortech was indeed a great compiler for its time.
- a9h74j 7y ago
  Years ago IIRC you put out a request for original Zortech C++ disks and packaging, if anyone had some. I was sorry that I had just disposed of mine six months earlier. .. That was my one-and-only C++ in the early 90's, and I am still programming in D. Sorry I couldn't help!
  - WalterBright 7y ago
    No problem. By the kind work of many people, I managed to accrete a fairly complete collection.
    - mrlonglong 7y ago
      I still have Zortech C 1.06 on my old P166. I should boot it up to see if it still lives !

jakear 7y ago

Off topic: Annoying that this is totally unreadable even at 300% zoom on an iPhone 11 Pro. I feel like a set of people refuse to learn proper HTML/CSS as some sort of statement, not realizing their laziness renders their work unavailable to the visually disabled. HN behaves similarly poorly.

nerdponx 7y ago
The irony is that if this site were actually simple (i.e. just text without a sidebar) it would be as responsive as you needed it to be. In the worst case scenario, you could fix it with client-side CSS. The problem here is that the site is complicated beyond what HTML is meant to do: it has a sidebar. It's no longer just a document; it's a document and a navigation menu. Effectively it's a small software application, and once you're in the business of writing software applications you ought to be in the business of accessibility and UX design.
saagarjha 7y ago
What's wrong with Hacker News?
- jakear 7y ago
  it doesn't respect iOS font size, and you can't alter the zoom to make the text actually bigger. It zooms the entire page rather than just the text, so the text doesn't re-flow. It's pretty much equivalent to just pinching to zoom, when it should be adjusting the font size.
  - catalogia 7y ago
    Why can firefox on the desktop resize the font on HN and reflow the content, but iOS cannot?
    - jakear 7y ago
      Beats me. But usually the onus is on the application developer to make their content accessible on all platforms. Especially one as common as iOS Safari

Animats 7y ago

That's a good set of questions for 2014. Questions that have become important more recently include: - Imperative? Functional? Some mixture of both? Mixtures of the two tend to have syntax problems. - Concurrency primitives. The cool kids want "async" now. Mostly to handle a huge number of slow web clients from one server process. Alternatively, there are "green threads", which Go calls "goroutines". All this stuff implies some level of CPU dispatching in compiled code. - Concurrency locking. Really hard problem. There's the Javascript run to completion approach, which reappears in other languages as "async". Ownership based locking, as in Rust, is promising, but may lock too much. And what about atomic operations and lockless operations? Source of hard to find bugs. Get this right. - Ownership. Rust got serious about this, with the borrow checker. C++ now tries to do "move semantics", with modest success, but has trouble checking at compile time for ownership errors. Any new language that isn't garbage collected has to address this. Historically, language design ignored this problem, but that's in the past. - Metaprogramming. Templates. Generics. Capable of creating an awful mess of unreadable code and confusing error messages. From LISP macros forward, a source of problems. Needs really good design, and there aren't many good examples to follow. - Integration with other languages. Protocol buffers? SQL? HTML? Should the language know about those? - GPUs. Biggest compute engines we have. How do we program them?

zzo38computer 7y ago
I would say possibly to use a different programming language for GPU than CPU. I like the idea of Checkout (see [0]) for GPU programming, although unfortunately it is not implemented and the preprocessor is not yet invented. (The trigonometric functions are also missing. They should probably have at least sine, cosine, and arctangent, since these functions seem like useful to me when doing graphics.) [0] http://esolangs.org/wiki/Checkout http://esolangs.org/wiki/Checkout
- neutronicus 7y ago
  I think using trig and especially inverse trig is almost always an antipattern in graphics code. Careful use of dot and cross product will almost always be both more performant and more robust.

zzo38computer 7y ago

In some programming languages, e.g. TeX, Forth, PostScript, etc you cannot really syntax highlight the program without executing it. However, syntax highlighting is a feature that I can do without, and I don't think those programming languages are bad. In some programming languages, such as C and Free Hero Mesh, you can read the sequence of tokens despite there are macros, which you need not parse to find where the tokens are (although I think older versions of the C preprocessor did not work like this). They mention tools. I do think valgrind is sometimes helpful; I do use that. However, Git is not the only version control system; some people prefer others, such as Mercurial, Fossil, etc. I use Fossil. They also mention error messages. I like the first one; print one error message and quit. However, in some cases, it might be possible to easily just ignore that error and continue after displaying the error message (and then finally fail at the end). It might also be possible to skip a lot of stuff, and then continue, e.g. if there is an unknown variable or function then you might display an error message and then skip the entire statement that mentions it. They mention a runtime library. This should be reduced as much as possible, I think, and if you can make it so that it has functions which will only be included in the compiled program when they are used, that can be a good idea, since you can include some functions that many people don't need and don't waste space and time with them. Something they did not mention but I think it is very good to have and useful is metaprogramming and 'pataprogramming. But I also think that different programming languages can be good for different purposes, and that some are domain specific, and some are easier to write than others. This can be done using existing syntax or new syntax, and I have done both, and so have some others. Another thing that I can recommend to have is a discussion system with NNTP; even Digital Mars themself have a NNTP-based discussion system. Perhaps better will be to have the same messages with NNTP, web forum, and mailing lists; again, this is what Digital Mars does. However, I do think that minimizing keystrokes is helpful. Minimizing runtime dependencies and runtime memory usage is also helpful.

ken 7y ago
> In some programming languages, e.g. TeX, Forth, PostScript, etc you cannot really syntax highlight the program without executing it. Technically true. In practice, however, I've run into way more issues with syntax highlighters in overly-complex fixed languages than I have with simpler-but-programmable languages.

DonaldFisk 7y ago

You might be doing this as a learning exercise, in which case it doesn't need to be particularly innovative, and writing another Lisp or Forth implementation is fine. In fact, I'd recommend beginning along those lines, followed by developing several different new languages, probably domain-specific ones. Your first attempts probably won't be worth keeping. (I haven't kept the object oriented Prolog I wrote about 25 years ago, but I do regularly use a small Prolog I recently wrote in Lisp.) The languages at the roots of all programming languages are Fortran, Lisp, Cobol, Algol60, APL, Snobol, Forth, Prolog, OPS5, SASL, Smalltalk, Prograph. (If I've missed any out, or any of the above have important predecessors, please let me know.) A new language is unlikely to be radically different from any of those languages or their descendants - of those I listed, the most recent is from the mid 1980s. Within the descendants, which is your favourite? Can you make big improvements to it? If so, make them. Otherwise, can you improve another language so that it becomes your favourite? One heuristic I've found useful: the right design choices at the start might be unknown, but when I need make them, they're obvious to me, and often a particular choice leads to other equally obvious choices. If the choice isn't obvious, I've probably done something wrong. My own preference is for pure rather than hybrid languages with simple regular syntaxes (i.e. one idea expressed well), and very strong static typing. My favourite language is Common Lisp or rather a subset of it. I have trouble thinking of ways to make it significantly better. But I also like the idea of dataflow (a few decades ago I knew some of those working on experimental dataflow hardware), and graphical programming seems to be the right approach to dataflow. Prograph was the closest existing language to what I wanted. It's isn't pure dataflow, it's dynamically typed, it's object oriented (so, unless it's Smalltalk it's hybrid), and entering programs in it involves too many mouse gestures and keystrokes. So I'm implementing a new language which corrects those deficiencies. It's been particularly difficult because I have to write an IDE as well as the language, and there aren't any textbooks I can rely on for help. I'll have succeeded if I use the new language more often than I do Lisp, and if along the way I get a few more papers (two so far) and some academic interest, so much the better. I don't expect a wide user base. If that was important to me, it would have C syntax and I'd try to get corporate backing. Your criterion for success might differ from mine.

lioeters 7y ago

tom-thistime 7y ago

"Wanna know the secret of making [X] fast? [...] Use a profiler." Still really valuable advice. We know it, but do we do it?

pfdietz 7y ago

A reason for simple parsing is to make the toolchain for the language easier. And in particular, you don't want a preprocessor. Try to parse your program into an AST? You can't in C/C++ in general -- you can only parse it for a particular set of preprocessor defines, which will leave out large chunks that were deleted during preprocessing.

nostrademons 7y ago

I used to be big into programming language design, but eventually decided that there just wasn't enough headroom to do something innovative enough to warrant the switching costs. The world doesn't need yet another syntax on top of basic C-style or Lisp-style semantic constructs. Lately I've been wondering if I should reconsider, though, and have had a bunch of ideas that blur the lines of what should be considered in-scope for a programming language. Things like: 1. Universal constructs for serial & parallel execution, but with user-defined semantics for where the code should execute. So for example, at low-scale you'd execute in a loop on the CPU. At mid-scale it'd run on the GPU. At high-scale you could transparently distribute across thousands of GPU boxes. 2. Profiling and execution statistics built into the language. Write your code, run it on representative data, and instantly get statistics on how many times each function is called, what the average size of data structures is, how much memory is used, etc. Profilers do this, but often not at a granularity that's particularly useful (ever tried to find out how many Strings are created within a particular dynamic call-tree?), and most new languages overlook implementing a profiler, leaving it to third-party vendors. This is a shame, because a standardized programmatic API to a profiler could be a very effective compiler tool, leading to... 3. A way of defining transformations between data representations, benchmarking the cost of those transformations, and then having the compiler automatically decide whether it's worth bulk-converting data based on typical profiler results. The motivating example for this is the AoS-SoA transformation, but they also feature in common system design questions like "Do you unpack all of the fields of this wire protocol, or lazily construct an object only when necessary?" or "Should you zip your data before sending it in an RPC?" or "Do you do this work at indexing or serving time?" 4. The ability to dump intermediate data from any function call site to disk, and then restart program execution from there without re-running the whole program. Handy when iterating on a complex algorithm. 5. Drill-down data visualizations for large collections. If you've ever tried to find the logic bug in a 500,000 element array using a standard IDE debugger, you'll know about this pain point. 6. Built-in support for machine-learning. In particular, many ML applications need extensive preprocessing, and you need to preprocess the data in exactly the same way for training and serving. Wouldn't it be neat if you could write your traditional algorithms, dump out your signals at the particular call-site of the classifier, and then have the development environment automatically send it to Mechanical Turk or Craigslist for labeling? Then have the system return the labeled data in a format easily suited for your ML framework of choice, do your data analysis & training, and import the finished model back into the call site of the language. 7. GPU-native, with language constructs that lead to efficient GPU code. This is becoming increasingly important not just for execution speed, but for developer velocity, because devs in data-intensive areas can waste a significant amount of time waiting for their program to run.

tanin 7y ago

What a great article. It's something I need to read, as I have been working on my own programming language for a while now. This creating-programming-language-thing is so difficult and so much effort. (I'm stuck at designing how string works right now) +1 on writing parser by hand. I've done it once with java (https://github.com/tanin47/javaparser.rs https://github.com/tanin47/javaparser.rs), and I switched my own programming language from a parser generator to a hand-written one. Once you know how to write a parser by hand, it's a much better approach (e.g. easier to test, modularizable). My programming language is a bit strange in a way that I drop the performance requirement. Performance distorts other aspects. I focus on making the language featureful and beautiful instead. I hope I'll achieve this dream of making a usable programming language one day.

ChicagoDave 7y ago

I just started down this road. I’ve mucked with scanning text into object trees but want learn how to make my own language. The difference is this would be a very small domain-specific language that controls an in-memory graph data store targeting interactive stories. There are great existing tools for this sort of thing, but I have theories/ideas I want to explore. I’m glad there are healthy discussions on compilers.

valera_rozuvan 7y ago

One should consider creating a VM first - it simplifies life a bit, and makes the language more portable in the future. The implementation task is split in two - compiler and VM. First, compiler targets the VM. Second, the VM targets the CPU. This way porting to different architectures is just a matter of adding to the VM to interface with the new arch. A compiler and VM definitely are 2 separate projects with their own set of issues. Also we should consider the possibility of going the eDSL (embedded domain-specific language) route. Working at a very high level, re-using existing constructs of the host language. If one is interested, looking into SICP [1] will show an example of such a project. Using Scheme to build an interpreter. This can easily be done in several days. Best to try to reduce doing work that has been done many times before. ---------- [1] https://mitpress.mit.edu/sites/default/files/sicp/index.html https://mitpress.mit.edu/sites/default/files/sicp/index.html

deleted 7y ago

[deleted]

bogomipz 7y ago

>"Context free grammars. What this really means is the code should be parseable without having to look things up in a symbol table. C++ is famously not a context free grammar." Could someone elaborate on why C++ is not a "not a context free grammar"? Also how does C++ deal with this fact?

colejohnson66 7y ago
Here’s a good Medium post on why C++ is undecidable: https://medium.com/@mujjingun_23509/full-proof-that-c-grammar-is-undecidable-34e22dd8b664 https://medium.com/@mujjingun_23509/full-proof-that-c-gramma...
- bogomipz 6y ago
  This is a great read! It summed things up quite nicely with some good graphics as well. Cheers.

teleforce 7y ago

As you are probably aware that the author of the article is the designer of the D programming language. For background reading of the design of D programming language, this is a very interesting and insightful paper on the history and the origins of D programming language up to 2018 [1]. [1] http://erdani.com/hopl2020-draft.pdf http://erdani.com/hopl2020-draft.pdf