3
$\begingroup$

I am contemplating the project of writing a compiler. I am wondering if, aside from the availability of easy google results, it is easier to write a compiler for a more explicit/verbose language such as ada, compared to a very compact language such as APL, for example.

I should add that i am especially interested in whole-program optimization.

Edit: my question boils down to "do highly abstracted symbols/keywords (as in APL, where a single operator represents a function) make it easier to write a compiler, or is a language with a more traditional syntax (where a function includes a variety of operators) easier?"

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Can you define what you mean by "compact"? Do you just mean that keywords are shorter, for instance? Why do you think it would be easier? $\endgroup$
    – D.W. ♦
    Commented Jul 30, 2017 at 23:27
  • 1
    $\begingroup$ While this is probably an accidental aspect of your question, if APL is like J, which I suspect it is, parsing it requires information that is only available at run-time. This makes compilation of J (and presumably APL) non-obvious. $\endgroup$
    – Derek Elkins left SE
    Commented Jul 31, 2017 at 2:08
  • $\begingroup$ Define "easy". Lexer, parser, analyzer/checker, optimizer and code generator might be made "easy" by very different, and sometimes contradictory features of the language. $\endgroup$
    – Raphael
    Commented Jul 31, 2017 at 5:07
  • $\begingroup$ I believe you are concerning too much with the precise syntax of your language. Usually, parsing is the most straightforward part of a compiler. It does not matter much how your program constructs are represented, but what they are. Knowing whether you have e.g. loops, recursion, closures, objects, dynamic allocation, etc. is much more important than the syntactic details, for instance, especially if you want to perform program analysis. $\endgroup$
    – chi
    Commented Jul 31, 2017 at 12:50

2 Answers 2

Reset to default
7
$\begingroup$

In almost every case, the more compact languages like APL will be harder write a compiler for:

  • On the front end (parser), in the worst case, you have a ton bunch of special cases for your symbols in your parser, and in the best case, you treat them as generic symbols, in which case you're in the exact same parsing position as a language that has
  • In the back-end, with type checking, optimizers, etc., you either treat your symbols as standard library functions, in which case you're in the exact same place as a more verbose language, or you treat them as parts of the language, in which case you will have a bunch of special cases in your type checker, code generation, etc.

In general, compilers are easiest for smaller languages. This is why most languages feature syntactic sugar, where some features are translated into a subset of your original language at compile time (for example, eliminating for-loops by turning them into while-loops). Many languages also keep code-generation and optimization simpler by compiling their language into a smaller intermediate language after parsing or type checking, then optimizing and compiling that language into machine code.

I should add that i am especially interested in whole-program optimization.

Syntax will not influence this in the slightest. Parsing is generally the least interesting part of writing a compiler, since there's many solutions for parsing, and once you have things into an Abstract Syntax Tree, what concrete syntax you used is entirely irrelevant. That is, two languages that parse to isomorphic ASTs will be exactly the same for difficulty to optimize.

The only case where having a more compact language could help optimization is if you have a bunch of special cases of known optimizations (e.g. fusion rules) for your operators, but you could just as easily write special cases for standard library functions of a more verbose language.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @DerekElkins Yep I was confused, got it in my head somehow that "verbose = more things defined by the language", but of course it's the opposite. Should be fixed now. $\endgroup$
    – Joey Eremondi
    Commented Jul 31, 2017 at 2:09
  • $\begingroup$ "once you have things into an Abstract Syntax Tree, what syntax you used is entirely irrelevant" -- is that strictly true? Yes, whether you use if ... fi or if { ... } has gone away, but other features of the language (e.g. paradigm, or if there are else branches, if there are named parameters, ...) are retained through parsing. Depends on what you call "syntax", I guess. $\endgroup$
    – Raphael
    Commented Jul 31, 2017 at 5:05
  • 1
    $\begingroup$ @Raphael Very true, I've clarified the answer $\endgroup$
    – Joey Eremondi
    Commented Jul 31, 2017 at 6:12
0
$\begingroup$

Writing compiler for simple language like Lisp or APL, is simpler. First, you have to deal with less amount of syntax rules. Second, you have to develop code generators for less types of AST nodes. APL is particularly easy - it have only a few rules, and most of the code generation is just sequential function calls since it has no operation priorities.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.