4 ms·

>Use compiler-friendly languages, by which he is really taking about languages that are good for implementing compilers, like Lisp and ML why?

rwmj 4y ago
You can easily match over structures, reaching into ASTs to any depth, which makes writing certain optimizations easier. As a very contrived example: match expr with | Mul (Const x, Const y) -> Const (x*y) | Mul (x, Const 2) -> (* optimize as a left shift *) | ...
- bicarbonato 4y ago
  It might not be a great language to create compilers, but python also has a pretty good structured pattern matching as of version 3.10: class BinOp: def __init__(self, left, right, operator): self.left = left self.right = right self.operator = operator sum_of_ints = BinOp(left=1, right=1, operator='+') match sum_of_ints: case BinOp(left=int(left), right=int(right), operator='+'): print(f'Summing int {left} + {right}') case BinOp(left=str(left), right=str(right), operator='+'): print(f'Concateneting strings {left} + {right}') case _: print('Don\'t know how to sum this')
  - sealeck 4y ago
    One shortcoming (though it's nice that Python has this) of this is that this isn't checked for exhaustiveness by the compiler (because there isn't a Python one) which makes it easy to forget cases and introduce bugs. Not sure if there are any runtime checks for this?
  - danuker 4y ago
    And look at the difference in verbosity. Lisp is to Python as Python is to Java.
Fellshard 4y ago
I expect the former because sexprs give you AST structure for free, and the latter because pattern-matched dispatch on AST nodes is ubiquitous.
- bigdict 4y ago
  Yeah, compare to C where you’d start by making a struct to implement a tree node.
kragen 4y ago
In addition to the pattern-matching rwmj pointed out, for ML I'd add strong static typing (because compilers are bug-prone!) with sum types, statically checked pattern matching, implementations that generate efficient code (because compilers are often slow), automatic memory management (usually GC), and duck typing in the form of higher-order functions. Lisp shares the last two of these. Both ML and Lisp make it pretty easy to write out complex domain-specific data structures (like ASTs) as part of your code, but I haven't found that as valuable as you might expect when writing toy compilers. Pattern-matching, though, that's super important. Compilers are full of case analysis of sum types, and not just in the sort of optimization transformations rwmj mentions, though in a sufficiently advanced compiler most of the code will probably be in the optimizer. (For these purposes Python is basically a slow Lisp.)
shadytrees 4y ago
Big question. Some glittering generalities: 1. These languages, having been used many times over to write compilers, have been battle-tested. 2. These languages do a good job of making immutable data structures easy to reach for and use, with escape hatches for more performant, mutable structures if need be; it's easier to reason about correctness when things are immutable by default. Correctness matters a lot for compilers. 3. Compilers are, in some sense, a bag of functions that iterate or map over trees. Pattern-matching is a way to reify trees: the branches of the trees become branches of your match expression. These languages support pattern-matching in a pervasive, first-class sort of way, as they prefer recursion and pattern matching over other kinds of control flow. 4. ML-likes have an advanced type system, while still being relatively ergonomic to write code in, as the type system admits some form of Hindley-Milner type inference. Good for correctness; but not strictly necessary for a compiler, maybe. 5. Lisp-likes don't generally have a type system (although some do!). But Lisps have extreme dynamism in the form of macros. Being able to tersely write code that expands out to exactly what you need can carry the day too. Whereas imperative languages sort of strike a compromise: their type systems are neither all that great (although C++, C#, and Java have all improved on type inferencing in the last decade) nor do they have anything as powerful as Lisp macros. 6. People and culture. Compiler people are generally made forged in academia, where it's generally taught in some Lisp or ML derivative. Type theory papers are usually written in some Haskell-like. Implementing a GHC extension is a path to a degree for grad student.

rwmj 4y ago

You can easily match over structures, reaching into ASTs to any depth, which makes writing certain optimizations easier. As a very contrived example: match expr with | Mul (Const x, Const y) -> Const (x*y) | Mul (x, Const 2) -> (* optimize as a left shift *) | ...

bicarbonato 4y ago
It might not be a great language to create compilers, but python also has a pretty good structured pattern matching as of version 3.10: class BinOp: def __init__(self, left, right, operator): self.left = left self.right = right self.operator = operator sum_of_ints = BinOp(left=1, right=1, operator='+') match sum_of_ints: case BinOp(left=int(left), right=int(right), operator='+'): print(f'Summing int {left} + {right}') case BinOp(left=str(left), right=str(right), operator='+'): print(f'Concateneting strings {left} + {right}') case _: print('Don\'t know how to sum this')
- sealeck 4y ago
  One shortcoming (though it's nice that Python has this) of this is that this isn't checked for exhaustiveness by the compiler (because there isn't a Python one) which makes it easy to forget cases and introduce bugs. Not sure if there are any runtime checks for this?
- danuker 4y ago
  And look at the difference in verbosity. Lisp is to Python as Python is to Java.

Fellshard 4y ago

I expect the former because sexprs give you AST structure for free, and the latter because pattern-matched dispatch on AST nodes is ubiquitous.

bigdict 4y ago
Yeah, compare to C where you’d start by making a struct to implement a tree node.

kragen 4y ago

In addition to the pattern-matching rwmj pointed out, for ML I'd add strong static typing (because compilers are bug-prone!) with sum types, statically checked pattern matching, implementations that generate efficient code (because compilers are often slow), automatic memory management (usually GC), and duck typing in the form of higher-order functions. Lisp shares the last two of these. Both ML and Lisp make it pretty easy to write out complex domain-specific data structures (like ASTs) as part of your code, but I haven't found that as valuable as you might expect when writing toy compilers. Pattern-matching, though, that's super important. Compilers are full of case analysis of sum types, and not just in the sort of optimization transformations rwmj mentions, though in a sufficiently advanced compiler most of the code will probably be in the optimizer. (For these purposes Python is basically a slow Lisp.)

shadytrees 4y ago

Big question. Some glittering generalities: 1. These languages, having been used many times over to write compilers, have been battle-tested. 2. These languages do a good job of making immutable data structures easy to reach for and use, with escape hatches for more performant, mutable structures if need be; it's easier to reason about correctness when things are immutable by default. Correctness matters a lot for compilers. 3. Compilers are, in some sense, a bag of functions that iterate or map over trees. Pattern-matching is a way to reify trees: the branches of the trees become branches of your match expression. These languages support pattern-matching in a pervasive, first-class sort of way, as they prefer recursion and pattern matching over other kinds of control flow. 4. ML-likes have an advanced type system, while still being relatively ergonomic to write code in, as the type system admits some form of Hindley-Milner type inference. Good for correctness; but not strictly necessary for a compiler, maybe. 5. Lisp-likes don't generally have a type system (although some do!). But Lisps have extreme dynamism in the form of macros. Being able to tersely write code that expands out to exactly what you need can carry the day too. Whereas imperative languages sort of strike a compromise: their type systems are neither all that great (although C++, C#, and Java have all improved on type inferencing in the last decade) nor do they have anything as powerful as Lisp macros. 6. People and culture. Compiler people are generally made forged in academia, where it's generally taught in some Lisp or ML derivative. Type theory papers are usually written in some Haskell-like. Implementing a GHC extension is a path to a degree for grad student.