7 ms·

I find it surprising that a single-pass compiler is easier to implement than a traditional lexer->parser->AST->emitter. (I'm not a compiler expert, though.) I

I find it surprising that a single-pass compiler is easier to implement than a traditional lexer->parser->AST->emitter. (I'm not a compiler expert, though.) I'd have expected that generating an AST would be at least as simple, if not simpler. Plus by generating an AST, doing some simple optimization is a lot easier: one can pattern-match parts of the AST and replace them with more efficient equivalents. Maybe I'm overthinking this, though. I tend to like extensible program designs, even when they don't necessarily make sense for the scale of the program… Still a really cool article and an impressive project, though. I especially like the StringPool technique; I'll have to keep it in mind if I ever write a compiler!

arjvik 1y ago
Not sure if fewer LoC necessarily implies easier!
kragen 1y ago
I think this might depend on the language you're writing in. Historically, at least, it's pretty verbose to define a data type in Python compared to languages that are more designed for writing compilers. Consider these definitions from my prototype Bicicleta interpreter, which is written in ML, specifically OCaml: type methods = NoDefs (* name, body, is_positional ... *) | Definition of string * bicexpr * bool * methods and bicexpr = Name of string | Call of bicexpr * string | Literal of string option * methods | Derivation of bicexpr * string option * methods | StringConstant of string | Integer of int | Float of float | NativeMethod of (lookup -> bicobj) Those ten lines of code would be ten classes in Python with an average of 1.6 attributes each. Using dataclasses or attrs, that would be 36 lines of code, and then (if you're doing it the OO way) every function that I defined on one of these OCaml types becomes a method implemented in each class implementing a particular protocol, with a copy of its argument signature in every class. (If you used namedtuple instead, it's no less code, but you write it on less lines.) So, for example, this function on bicexprs let rec freevars = function Name n -> stringset [n] | Integer _ | StringConstant _ | Float _ -> stringset ["prog"] | NativeMethod _ -> stringset [] | Literal (Some selfname, methods) -> StringSet.diff (freevars_methods methods) (stringset [selfname]) | Literal (None, methods) -> freevars_methods methods | Derivation(object_, self, methods) -> StringSet.union (freevars object_) (freevars (Literal(self, methods))) | Call(object_, _) -> freevars object_ becomes six to eight method definitions in the different classes. (You can cut it down to six if you define an abstract base class for the constant classes.) And Literal.freevars needs an if-then-else. So that's another 20 lines of code. Python does support pattern-matching now, so functions like this might not be any more verbose than the ML version if you program them the same way instead of in the OO fashion. I haven't tried using Python pattern-matching, so I don't really know. In general, though, Python is more verbose than ML-family languages for this kind of thing by a factor of about 2–4, and that's before you count the test code you need in Python to get the kind of confidence in correctness that ML's type-checking gives you with no extra code. To my knowledge, Mypy doesn't do the kinds of pattern-matching-exhaustiveness checks that ML compilers do. I've sometimes "cheated" by trying to write code like this in Python using regular tuples rather than named tuples. You can definitely make it work, but it's a real pain to debug. Quoting Andy Chu from https://andychu.net/projects/ https://andychu.net/projects/: > Python is not the right language for [implementing] languages. I will use OCaml for subsequent projects like this. Python does have GC and dynamic dispatch, though, and those count for a lot.
- kragen 1y ago
  Eli Bendersky's blogpost on the Expression Problem: https://news.ycombinator.com/item?id=45155877 https://news.ycombinator.com/item?id=45155877
  - sevensor 1y ago
    I thought this was a good read, and it’s clearly a problem in an OO language, but I struggled to see how it’s an actual problem in a functional language. Maybe I need to go read that paper he referenced by the Racket guys.
    - naasking 1y ago
      The example in the article was very clear I thought: try to extend an interpreter with a new primitive (function call in the article) without changing the original interpreter's source code. I'm an FP language, you can't extend the core AST without changing the source code for eval.
    - kragen 1y ago
      In my example above, to add a new variant type to bicexpr, you need to edit roughly every function that pattern-matches on bicexprs, which is a good fraction of the Bicicleta interpreter codebase.
      - sevensor 1y ago
        Ah, I see. I’ve written that code where you have to add one case to a whole bunch of pattern matches. It’s not terrible; I rather like that everything that does the same thing is in the same place. But I have wondered if there was a better way. Clearly I need to go read the article again.
        kragen 1y ago
        Yeah, I share your assessment that it's not unmanageable. But it does add friction. I suspect that there are only two real solutions: - program source code that isn't a linear document but instead can be viewed in multiple different ways: by operation or by operand type, for example. Then you would use the view that best suits the modification you were doing at the time. Smalltalk, for example, does support browsing either all the implementors of a method selector or all the methods of a class. (But in both cases you normally only see one method at a time.) - Alternating levels of hierarchy. Maybe if you have 63 operations on 63 types, you could arrange it so that you can add a 64th operation or a 64th type by editing only 8 places instead of 63.
markus_zhang 1y ago
I think it depends on the language. I heard Turbo Pascal was pretty fast because 1) Pascal’s language features, 2) no optimization in TP 1.0 at least.
- MarsIronPI 1y ago
  Fast to run or fast to compile?
  - markus_zhang 1y ago
    Fast to compile. It was very fast comparing to the others then. Since computers were slow (8086/80286) compiling speed actually mattered. https://www.pcengines.ch/tp3.htm https://www.pcengines.ch/tp3.htm
    - MarsIronPI 1y ago
      As an ex-Gentoo user I can confirm that compiling speed still matters on certain machines.
      - markus_zhang 1y ago
        I have never worked as a system programmer so I never had the need to compile something big. I guess it could be an issue with very large software like Oracle Database, the Linux kernel and other similar stuffs.
        rini17 1y ago
        The kernel is quite okay. On the other hand, qtwebengine..
  - renox 1y ago
    Well given that often the alternative was BASIC which was interpreted, it also felt fast to run..
marssaxman 1y ago
A single-pass compiler is easier to implement in part because you're not going to do any of that optimization. You're writing a single-pass compiler either because you're banging out a quick sketch of an idea, and you don't care about production use, or because you've time-traveled back to the '70s or the '80s, where processors were so painfully slow and memory so eye-wateringly expensive that you might not even be able to read the entire source file into RAM at once, much less convert it all into some intermediate representation before starting to write out the machine code.
- dlcarrier 1y ago
  I used to write software on my HP calculator, when I was bored in classes, before smartphones existed. It used a tokenized language called RPL, and the editor would read and parse just enough tokens to fill up the screen. I miss how fast it was, compared to modern computers. VS Code is much laggier in comparison.
  - fuzztester 1y ago
    Which model of HP calculator? And what kinds of programs could you write with it?
    - dlcarrier 1y ago
      I had a 48S then a 49g+. I played around with a few games and a Magic Eye style (https://en.wikipedia.org/wiki/Random_dot_stereogram https://en.wikipedia.org/wiki/Random_dot_stereogram) 3D image generator, as well as programs to do actual math in my math classes. The math teachers teachers at my high school had a policy that, on exams, students could run any program they wrote, so I wrote programs to do the math and "show my work". Solving equations on paper was half of the grade, and getting the correct answer was the other half, but my handwriting is really bad, so I'd always get the wrong answer if I did it by hand. HP's calculators are pretty capable, with built-in commands for image processing, so RPL programs could rival the capabilities of assembly language programs on TI-8x calculators.
comonoid 1y ago
C was designed to be compiled with a single-pass compiler.
- Joker_vD 1y ago
  It wasn't; the original C compiler had two passes, and built expression trees in the first pass which the second pass would turn into assembly (and the original as on UNIX also had two passes).
- whobre 1y ago
  C was not designed at all. It evolved from B, by adding types to it.
  - fuzztester 1y ago
    Yes. And B evolved from BCPL: https://en.m.wikipedia.org/wiki/BCPL https://en.m.wikipedia.org/wiki/BCPL I had read the book about BCPL by Martin Richards, creator of the language. it was quite interesting. IIRC, after describing the language, he gave some examples of small system software routines or utilities, written in it. https://en.m.wikipedia.org/wiki/Martin_Richards_(computer_scientist) https://en.m.wikipedia.org/wiki/Martin_Richards_(computer_sc...

arjvik 1y ago

Not sure if fewer LoC necessarily implies easier!

kragen 1y ago

I think this might depend on the language you're writing in. Historically, at least, it's pretty verbose to define a data type in Python compared to languages that are more designed for writing compilers. Consider these definitions from my prototype Bicicleta interpreter, which is written in ML, specifically OCaml: type methods = NoDefs (* name, body, is_positional ... *) | Definition of string * bicexpr * bool * methods and bicexpr = Name of string | Call of bicexpr * string | Literal of string option * methods | Derivation of bicexpr * string option * methods | StringConstant of string | Integer of int | Float of float | NativeMethod of (lookup -> bicobj) Those ten lines of code would be ten classes in Python with an average of 1.6 attributes each. Using dataclasses or attrs, that would be 36 lines of code, and then (if you're doing it the OO way) every function that I defined on one of these OCaml types becomes a method implemented in each class implementing a particular protocol, with a copy of its argument signature in every class. (If you used namedtuple instead, it's no less code, but you write it on less lines.) So, for example, this function on bicexprs let rec freevars = function Name n -> stringset [n] | Integer _ | StringConstant _ | Float _ -> stringset ["prog"] | NativeMethod _ -> stringset [] | Literal (Some selfname, methods) -> StringSet.diff (freevars_methods methods) (stringset [selfname]) | Literal (None, methods) -> freevars_methods methods | Derivation(object_, self, methods) -> StringSet.union (freevars object_) (freevars (Literal(self, methods))) | Call(object_, _) -> freevars object_ becomes six to eight method definitions in the different classes. (You can cut it down to six if you define an abstract base class for the constant classes.) And Literal.freevars needs an if-then-else. So that's another 20 lines of code. Python does support pattern-matching now, so functions like this might not be any more verbose than the ML version if you program them the same way instead of in the OO fashion. I haven't tried using Python pattern-matching, so I don't really know. In general, though, Python is more verbose than ML-family languages for this kind of thing by a factor of about 2–4, and that's before you count the test code you need in Python to get the kind of confidence in correctness that ML's type-checking gives you with no extra code. To my knowledge, Mypy doesn't do the kinds of pattern-matching-exhaustiveness checks that ML compilers do. I've sometimes "cheated" by trying to write code like this in Python using regular tuples rather than named tuples. You can definitely make it work, but it's a real pain to debug. Quoting Andy Chu from https://andychu.net/projects/ https://andychu.net/projects/: > Python is not the right language for [implementing] languages. I will use OCaml for subsequent projects like this. Python does have GC and dynamic dispatch, though, and those count for a lot.

kragen 1y ago
Eli Bendersky's blogpost on the Expression Problem: https://news.ycombinator.com/item?id=45155877 https://news.ycombinator.com/item?id=45155877
- sevensor 1y ago
  I thought this was a good read, and it’s clearly a problem in an OO language, but I struggled to see how it’s an actual problem in a functional language. Maybe I need to go read that paper he referenced by the Racket guys.
  - naasking 1y ago
    The example in the article was very clear I thought: try to extend an interpreter with a new primitive (function call in the article) without changing the original interpreter's source code. I'm an FP language, you can't extend the core AST without changing the source code for eval.
  - kragen 1y ago
    In my example above, to add a new variant type to bicexpr, you need to edit roughly every function that pattern-matches on bicexprs, which is a good fraction of the Bicicleta interpreter codebase.
    - sevensor 1y ago
      Ah, I see. I’ve written that code where you have to add one case to a whole bunch of pattern matches. It’s not terrible; I rather like that everything that does the same thing is in the same place. But I have wondered if there was a better way. Clearly I need to go read the article again.
      - kragen 1y ago
        Yeah, I share your assessment that it's not unmanageable. But it does add friction. I suspect that there are only two real solutions: - program source code that isn't a linear document but instead can be viewed in multiple different ways: by operation or by operand type, for example. Then you would use the view that best suits the modification you were doing at the time. Smalltalk, for example, does support browsing either all the implementors of a method selector or all the methods of a class. (But in both cases you normally only see one method at a time.) - Alternating levels of hierarchy. Maybe if you have 63 operations on 63 types, you could arrange it so that you can add a 64th operation or a 64th type by editing only 8 places instead of 63.

markus_zhang 1y ago

I think it depends on the language. I heard Turbo Pascal was pretty fast because 1) Pascal’s language features, 2) no optimization in TP 1.0 at least.

MarsIronPI 1y ago
Fast to run or fast to compile?
- markus_zhang 1y ago
  Fast to compile. It was very fast comparing to the others then. Since computers were slow (8086/80286) compiling speed actually mattered. https://www.pcengines.ch/tp3.htm https://www.pcengines.ch/tp3.htm
  - MarsIronPI 1y ago
    As an ex-Gentoo user I can confirm that compiling speed still matters on certain machines.
    - markus_zhang 1y ago
      I have never worked as a system programmer so I never had the need to compile something big. I guess it could be an issue with very large software like Oracle Database, the Linux kernel and other similar stuffs.
      - rini17 1y ago
        The kernel is quite okay. On the other hand, qtwebengine..
- renox 1y ago
  Well given that often the alternative was BASIC which was interpreted, it also felt fast to run..

marssaxman 1y ago

A single-pass compiler is easier to implement in part because you're not going to do any of that optimization. You're writing a single-pass compiler either because you're banging out a quick sketch of an idea, and you don't care about production use, or because you've time-traveled back to the '70s or the '80s, where processors were so painfully slow and memory so eye-wateringly expensive that you might not even be able to read the entire source file into RAM at once, much less convert it all into some intermediate representation before starting to write out the machine code.

dlcarrier 1y ago
I used to write software on my HP calculator, when I was bored in classes, before smartphones existed. It used a tokenized language called RPL, and the editor would read and parse just enough tokens to fill up the screen. I miss how fast it was, compared to modern computers. VS Code is much laggier in comparison.
- fuzztester 1y ago
  Which model of HP calculator? And what kinds of programs could you write with it?
  - dlcarrier 1y ago
    I had a 48S then a 49g+. I played around with a few games and a Magic Eye style (https://en.wikipedia.org/wiki/Random_dot_stereogram https://en.wikipedia.org/wiki/Random_dot_stereogram) 3D image generator, as well as programs to do actual math in my math classes. The math teachers teachers at my high school had a policy that, on exams, students could run any program they wrote, so I wrote programs to do the math and "show my work". Solving equations on paper was half of the grade, and getting the correct answer was the other half, but my handwriting is really bad, so I'd always get the wrong answer if I did it by hand. HP's calculators are pretty capable, with built-in commands for image processing, so RPL programs could rival the capabilities of assembly language programs on TI-8x calculators.

comonoid 1y ago

C was designed to be compiled with a single-pass compiler.

Joker_vD 1y ago
It wasn't; the original C compiler had two passes, and built expression trees in the first pass which the second pass would turn into assembly (and the original as on UNIX also had two passes).
whobre 1y ago
C was not designed at all. It evolved from B, by adding types to it.
- fuzztester 1y ago
  Yes. And B evolved from BCPL: https://en.m.wikipedia.org/wiki/BCPL https://en.m.wikipedia.org/wiki/BCPL I had read the book about BCPL by Martin Richards, creator of the language. it was quite interesting. IIRC, after describing the language, he gave some examples of small system software routines or utilities, written in it. https://en.m.wikipedia.org/wiki/Martin_Richards_(computer_scientist) https://en.m.wikipedia.org/wiki/Martin_Richards_(computer_sc...