8 ms·

Compilers for Free

165 points by grawprog 8y ago

iamNumber4 8y ago
Nothing to see here, peaked my interest since “who would pay for a compiler??” In the modern age of open source. Post has a missleading title, and is just rambles about ruby and compilers.
- SllX 8y ago
  Thank you.
- sephoric 8y ago
  More specifically > "Programs that manipulate other programs are powerful, interesting and fun. I’ll use Ruby to take you on a tour of how interpreters and compilers work, introduce the ideas behind a technique called partial evaluation, and explain a surprising computer science result which allows compilers to be generated automatically."
- nixpulvis 8y ago
  I believe the title is a reference to "Theorems for free", a somewhat well known paper. https://ecee.colorado.edu/ecen5533/fall11/reading/free.pdf https://ecee.colorado.edu/ecen5533/fall11/reading/free.pdf
- deleted 8y ago
  [deleted]
- 4thaccount 8y ago
  It depends on what you want. If I wrote aerospace code I'd probably buy adacore's ada and spark compilers and tools. Since I mostly do scripting work, I usually stick to Python, Bash, & Powershell though. Some commercial compilers are very affordable with extremely sane licenses. One that has interested me lately is called 8th and is $250 for a professional license which lasts forever and can create encrypted binary executables on Linux, Mac, Windows, raspberry pi, iPhone, android, or embedded all with a cross-compiler, builtin graphics, sound, database support, full REPL, good support...etc. There is also a free version that just has some features missing (not a dumb temporary trial) and a $50 hobby license with many of the features. The Enterprise license would be expensive for me, but fairly cheap for most companies and includes priority support and the source code, so that is neat. I'm all for open-source, but if we're honest, some commercial tools are great and don't abuse users. It is not an only option situation. I will say closed source can really stink too. I once had to use a product that all of the vendor's customers had to use, but it wasn't officially supported (although it was critical for infrastructure) and I was running into a bug they couldn't figure out or didn't care to look into. The terminal would tell me the problem was in line x of the encrypted script, but wouldn't let me know what line x did so I could get the app working.
  - vram11 8y ago
    >One that has interested me lately is called 8th Link, please? Did not find a page about the makers of 8th, though I googled and saw some other related pages I'm reading.
    - reitzensteinm 8y ago
      It's probably this one: https://8th-dev.com/ https://8th-dev.com/
      - 4thaccount 8y ago
        Yea it's this one. The main developer wrote an open source Forth called Reva-Forth awhile back. I think he does a lot of paid development a across various fields from phone app development to embedded work, and machine learning stuff. When he was trying to do phone apps he realized (like most of us) that it is a pain to need to know Java for Android (+ API) and Objective C or Swift for iOS and then there is WinForms or Gtk or WxWidjets for desktop development, so you have to learn a lot of different technologies if you want to write software to run on all major platforms and 8th helps solve most of that problem. 8th is also a Forth, but he has added some features like using JSON as a generic data structure (not generally done in Forth), bundled the C++ JUCE GUI framework and associated licenses, added ODBC/SQLITE/MYSQL support, sound, cross-compilation to many platforms...etc. Most of my coding needs fall into either general scripting (Python, Powershell, Bash, Perl...etc) or numerical work (Python + Numpy or Julia). 8th seems to be pretty speedy, but Forths in general usually aren't lightning fast due to their stack usage and emphasis and you need really fast code for numeric work. He has made it a priority to work on performance though and continuously adds scientific features like adjacency graphs, so he is on the right track and I'll keep my eyes on it. For general scripting work and utility apps it should work pretty nicely for my needs and distributing a tiny .exe to users with a GUI is nice. I'm not sure how good the file I/O & filesystem support is though (need to look at the doc), because I use those common features a lot. I also need to check if he wrote functions (called words in Forth speech) for web scraping as there is a project I'd like to do where 8th would be ideal. If you've never seen Forth before, try to keep an open mind with the syntax as it can look alien at first. There are a lot of 8th examples on Rosetta Code and although they are short, it might look like gobblygook if you're not used to thinking about the stack where parameters are popped off and used in functions which then return data to the stack so functions can be chained (kind of like Unix pipes). Leo Brodie's books on Forth (classics and free online) are called "Learning Forth" and "Thinking Forth" and are recommended on HN sometimes.
- quickthrower2 8y ago
  Free as in monad, not as in beer or as in speech
  - tom_mellior 8y ago
    Free as in "once you have written an interpreter, you do not need to write a compiler anymore, it will just appear".
    - klibertp 8y ago
      ...if you have a sufficiently smart partial evaluator, that is... ;)
- thedaemon 8y ago
  As usual, the only relevant post is downvoted to submission. Can you all stop downvoting honest and helpful comments? This is one of the most hostile communities on the internet today. The post title is 100% misleading, it is not a large list of Compilers that are free. Which is what I expected. It's all about Ruby... Why was Ruby not in the title? OP should fix the title.
fjfaase 8y ago
I have implemented the method of parsing an expression into objects with an evaluation method in the scripting language that I build into an editor for performing complex manipulations of images. See http://www.iwriteiam.nl/MySample.html http://www.iwriteiam.nl/MySample.html
sifoobar 8y ago
The more I learn about interpreters and compilers, the more everything looks the same. Snigl [0] is designed as a VM interpreter. But it has a separate compile stage where code may be evaluated using the same interpreter and the results reused at runtime. And it traces code before running it, evaluating as much as possible statically. Finally, it supports emitting C code for an interpreter preloaded with the current, traced program. Which is where compile time evaluation really shines, as the results are embedded in the executable. [0] https://gitlab.com/sifoo/snigl https://gitlab.com/sifoo/snigl
- gizmo686 8y ago
  I have written far more compilers/interpreters in my career than I probably should have, and I reached the same conclusion. For most of them, I probably couldn't even tell you weather or not what I had involved a compiler. At this point, my working distinction is that a compiler produces a serialized representation. If you feed the AST directly into the runtime, then you just have an interperater. I don't see any practical benifit to this distinction, but it seems to match up with what people consider a "compiler". As an asside, I had a simmilar insight when I built a computer from logic gates [0]. Essentially, the control unit had an EEPROM of microcode, and the logic to execute an actual instruction was to use the upper 4 bits of the instruction as an index into a lookup table, then write the result to the microcode program counter. Eg: switch(OP & 0xf0): case 1: jmp &add case 2: jmp &sub ... Which looks a lot like an interperator. It wouldn't suprise me if modern CPUs actually added an additional step, where they first translate (compile?) the input stream into some internal instruction set, and then have microcode that acts as an interperator for that. [0] Also EEPROM, and various composite circuits.
  - nickpsecurity 8y ago
    "It wouldn't suprise me if modern CPUs actually added an additional step, where they first translate (compile?) the input stream into some internal instruction set, and then have microcode that acts as an interperator for that." Among Java processors, there was quite a mix of methods ranging from CISC to RISC to in-hardware to interpret-to-regular-CPU's: https://www.electronicdesign.com/embedded/java-processors https://www.electronicdesign.com/embedded/java-processors IBM's System/38 also did something with portable microcode that got converted to internal microcode: https://homes.cs.washington.edu/~levy/capabook/index.html https://homes.cs.washington.edu/~levy/capabook/index.html
abeppu 8y ago
Why is it that 35 years after the Futamura projections were first described, when we want to produce a new compiler, we don't write an interpreter and pass it through a high quality, general partial evaluator? Whenever the Futamura projections are described, it's always at a conceptual level, in general terms. Reading a blog post like this one, I'm always left to wonder (a) why does this not end with a link to a github implementation of a general partial evaluator and (b) why is it the case that none of the compilers I use were produced with these techniques? There must be some set of tradeoffs preventing this approach from living up to the "compilers for free" promise, but I haven't found anyone with a real explanation. Either there must be hard challenges which make implementing a general partial evaluator very difficult, or the results that we'd get from using such a partial evaluator are poorer than what we get through other means right? Perhaps the greatest success in this direction is PyPy. At some level the RPython toolchain is general enough that people have used it to produce JITted versions of ruby, php and a few other languages. But these are a handful of alternative implementations to existing languages, where the predominant implementation doesn't use this toolset. And PyPy's own docs note that the JIT compiler needs some amount of hinting from the interpreter; you can't just throw any interpreter (written in RPython) at it.
- lifthrasiir 8y ago
  > Why is it that 35 years after the Futamura projections were first described, when we want to produce a new compiler, we don't write an interpreter and pass it through a high quality, general partial evaluator? I think the rationale for abandoning partial evaluation for PyPy [1] explains most complications with it. Or put in different words, PE-based compilers don't have all necessary knobs that real compilers need. [1] https://morepypy.blogspot.com/2018/09/the-first-15-years-of-pypy.html#why-did-we-abandon-partial-evaluation https://morepypy.blogspot.com/2018/09/the-first-15-years-of-...
- nirvdrum 8y ago
  If you're interested in looking into some active research in the area of partial evaluation, you should look at Truffle [1] and Graal [2] from my team at Oracle Labs. Graal is a new JIT compiler for HotSpot written in Java, with an API to interact with the compiler from Java. Truffle is a toolkit for implementing programming languages as self-optimizing AST interpreters. Truffle uses the Graal hooks to perform partial evaluation of Truffle-based interpreters to generate highly optimized native code. The partial evaluator doesn't know anything about the language being compiled, save for a few annotations that Truffle provides to control inline caches and such. We're using this approach to create new optimizing runtimes for Ruby (TruffleRuby), JavaScript (Graal.js), R (FastR), Python (GraalPython), and even LLVM bitcode (Sulong). There are languages being implemented outside of Oracle Labs as well [3]. So, it's being stressed by a wide range of language semantics. As for performance... I work mostly on TruffleRuby. There we're seeing considerable performance advantages against other Ruby implementations across a wide array of benchmarks and workloads. We really do get the JIT for free by virtue of being a Truffle-based language implementation. It's quite liberating as the compiler technology is free to evolve separately from our Ruby implementation, in contrast to the tight coupling you'd have with a language-specific JIT. [1] -- https://github.com/oracle/graal/tree/master/truffle https://github.com/oracle/graal/tree/master/truffle [2] -- https://github.com/oracle/graal/tree/master/compiler https://github.com/oracle/graal/tree/master/compiler [3] -- https://github.com/oracle/graal/blob/master/truffle/docs/Languages.md https://github.com/oracle/graal/blob/master/truffle/docs/Lan...
honestoHeminway 8y ago
it even rhymes with gcc
dmux 8y ago
The description immediately reminded me of a book called "Understanding Computation." Scrolling down I see the video is by Tom Stuart, the author of that book. I'd really recommend it (the book) for anyone interested in learning about "big step" (operational) and "small step" (structural) semantics.
Dangeranger 8y ago
Tom Stuart, the author of the post, also has written an interesting article called "Programming with Nothing" in which he demonstrates how to use first-class functions in Ruby to explain the Lambda Calculus.[0] [0] https://codon.com/programming-with-nothing https://codon.com/programming-with-nothing

165 points by grawprog 8y ago

Nothing to see here, peaked my interest since “who would pay for a compiler??” In the modern age of open source. Post has a missleading title, and is just rambles about ruby and compilers.

SllX 8y ago
Thank you.
sephoric 8y ago
More specifically > "Programs that manipulate other programs are powerful, interesting and fun. I’ll use Ruby to take you on a tour of how interpreters and compilers work, introduce the ideas behind a technique called partial evaluation, and explain a surprising computer science result which allows compilers to be generated automatically."
nixpulvis 8y ago
I believe the title is a reference to "Theorems for free", a somewhat well known paper. https://ecee.colorado.edu/ecen5533/fall11/reading/free.pdf https://ecee.colorado.edu/ecen5533/fall11/reading/free.pdf
deleted 8y ago
[deleted]
4thaccount 8y ago
It depends on what you want. If I wrote aerospace code I'd probably buy adacore's ada and spark compilers and tools. Since I mostly do scripting work, I usually stick to Python, Bash, & Powershell though. Some commercial compilers are very affordable with extremely sane licenses. One that has interested me lately is called 8th and is $250 for a professional license which lasts forever and can create encrypted binary executables on Linux, Mac, Windows, raspberry pi, iPhone, android, or embedded all with a cross-compiler, builtin graphics, sound, database support, full REPL, good support...etc. There is also a free version that just has some features missing (not a dumb temporary trial) and a $50 hobby license with many of the features. The Enterprise license would be expensive for me, but fairly cheap for most companies and includes priority support and the source code, so that is neat. I'm all for open-source, but if we're honest, some commercial tools are great and don't abuse users. It is not an only option situation. I will say closed source can really stink too. I once had to use a product that all of the vendor's customers had to use, but it wasn't officially supported (although it was critical for infrastructure) and I was running into a bug they couldn't figure out or didn't care to look into. The terminal would tell me the problem was in line x of the encrypted script, but wouldn't let me know what line x did so I could get the app working.
- vram11 8y ago
  >One that has interested me lately is called 8th Link, please? Did not find a page about the makers of 8th, though I googled and saw some other related pages I'm reading.
  - reitzensteinm 8y ago
    It's probably this one: https://8th-dev.com/ https://8th-dev.com/
    - 4thaccount 8y ago
      Yea it's this one. The main developer wrote an open source Forth called Reva-Forth awhile back. I think he does a lot of paid development a across various fields from phone app development to embedded work, and machine learning stuff. When he was trying to do phone apps he realized (like most of us) that it is a pain to need to know Java for Android (+ API) and Objective C or Swift for iOS and then there is WinForms or Gtk or WxWidjets for desktop development, so you have to learn a lot of different technologies if you want to write software to run on all major platforms and 8th helps solve most of that problem. 8th is also a Forth, but he has added some features like using JSON as a generic data structure (not generally done in Forth), bundled the C++ JUCE GUI framework and associated licenses, added ODBC/SQLITE/MYSQL support, sound, cross-compilation to many platforms...etc. Most of my coding needs fall into either general scripting (Python, Powershell, Bash, Perl...etc) or numerical work (Python + Numpy or Julia). 8th seems to be pretty speedy, but Forths in general usually aren't lightning fast due to their stack usage and emphasis and you need really fast code for numeric work. He has made it a priority to work on performance though and continuously adds scientific features like adjacency graphs, so he is on the right track and I'll keep my eyes on it. For general scripting work and utility apps it should work pretty nicely for my needs and distributing a tiny .exe to users with a GUI is nice. I'm not sure how good the file I/O & filesystem support is though (need to look at the doc), because I use those common features a lot. I also need to check if he wrote functions (called words in Forth speech) for web scraping as there is a project I'd like to do where 8th would be ideal. If you've never seen Forth before, try to keep an open mind with the syntax as it can look alien at first. There are a lot of 8th examples on Rosetta Code and although they are short, it might look like gobblygook if you're not used to thinking about the stack where parameters are popped off and used in functions which then return data to the stack so functions can be chained (kind of like Unix pipes). Leo Brodie's books on Forth (classics and free online) are called "Learning Forth" and "Thinking Forth" and are recommended on HN sometimes.
quickthrower2 8y ago
Free as in monad, not as in beer or as in speech
- tom_mellior 8y ago
  Free as in "once you have written an interpreter, you do not need to write a compiler anymore, it will just appear".
  - klibertp 8y ago
    ...if you have a sufficiently smart partial evaluator, that is... ;)
thedaemon 8y ago
As usual, the only relevant post is downvoted to submission. Can you all stop downvoting honest and helpful comments? This is one of the most hostile communities on the internet today. The post title is 100% misleading, it is not a large list of Compilers that are free. Which is what I expected. It's all about Ruby... Why was Ruby not in the title? OP should fix the title.

fjfaase 8y ago

I have implemented the method of parsing an expression into objects with an evaluation method in the scripting language that I build into an editor for performing complex manipulations of images. See http://www.iwriteiam.nl/MySample.html http://www.iwriteiam.nl/MySample.html

sifoobar 8y ago

The more I learn about interpreters and compilers, the more everything looks the same. Snigl [0] is designed as a VM interpreter. But it has a separate compile stage where code may be evaluated using the same interpreter and the results reused at runtime. And it traces code before running it, evaluating as much as possible statically. Finally, it supports emitting C code for an interpreter preloaded with the current, traced program. Which is where compile time evaluation really shines, as the results are embedded in the executable. [0] https://gitlab.com/sifoo/snigl https://gitlab.com/sifoo/snigl

gizmo686 8y ago
I have written far more compilers/interpreters in my career than I probably should have, and I reached the same conclusion. For most of them, I probably couldn't even tell you weather or not what I had involved a compiler. At this point, my working distinction is that a compiler produces a serialized representation. If you feed the AST directly into the runtime, then you just have an interperater. I don't see any practical benifit to this distinction, but it seems to match up with what people consider a "compiler". As an asside, I had a simmilar insight when I built a computer from logic gates [0]. Essentially, the control unit had an EEPROM of microcode, and the logic to execute an actual instruction was to use the upper 4 bits of the instruction as an index into a lookup table, then write the result to the microcode program counter. Eg: switch(OP & 0xf0): case 1: jmp &add case 2: jmp &sub ... Which looks a lot like an interperator. It wouldn't suprise me if modern CPUs actually added an additional step, where they first translate (compile?) the input stream into some internal instruction set, and then have microcode that acts as an interperator for that. [0] Also EEPROM, and various composite circuits.
- nickpsecurity 8y ago
  "It wouldn't suprise me if modern CPUs actually added an additional step, where they first translate (compile?) the input stream into some internal instruction set, and then have microcode that acts as an interperator for that." Among Java processors, there was quite a mix of methods ranging from CISC to RISC to in-hardware to interpret-to-regular-CPU's: https://www.electronicdesign.com/embedded/java-processors https://www.electronicdesign.com/embedded/java-processors IBM's System/38 also did something with portable microcode that got converted to internal microcode: https://homes.cs.washington.edu/~levy/capabook/index.html https://homes.cs.washington.edu/~levy/capabook/index.html

abeppu 8y ago

Why is it that 35 years after the Futamura projections were first described, when we want to produce a new compiler, we don't write an interpreter and pass it through a high quality, general partial evaluator? Whenever the Futamura projections are described, it's always at a conceptual level, in general terms. Reading a blog post like this one, I'm always left to wonder (a) why does this not end with a link to a github implementation of a general partial evaluator and (b) why is it the case that none of the compilers I use were produced with these techniques? There must be some set of tradeoffs preventing this approach from living up to the "compilers for free" promise, but I haven't found anyone with a real explanation. Either there must be hard challenges which make implementing a general partial evaluator very difficult, or the results that we'd get from using such a partial evaluator are poorer than what we get through other means right? Perhaps the greatest success in this direction is PyPy. At some level the RPython toolchain is general enough that people have used it to produce JITted versions of ruby, php and a few other languages. But these are a handful of alternative implementations to existing languages, where the predominant implementation doesn't use this toolset. And PyPy's own docs note that the JIT compiler needs some amount of hinting from the interpreter; you can't just throw any interpreter (written in RPython) at it.

lifthrasiir 8y ago
> Why is it that 35 years after the Futamura projections were first described, when we want to produce a new compiler, we don't write an interpreter and pass it through a high quality, general partial evaluator? I think the rationale for abandoning partial evaluation for PyPy [1] explains most complications with it. Or put in different words, PE-based compilers don't have all necessary knobs that real compilers need. [1] https://morepypy.blogspot.com/2018/09/the-first-15-years-of-pypy.html#why-did-we-abandon-partial-evaluation https://morepypy.blogspot.com/2018/09/the-first-15-years-of-...
nirvdrum 8y ago
If you're interested in looking into some active research in the area of partial evaluation, you should look at Truffle [1] and Graal [2] from my team at Oracle Labs. Graal is a new JIT compiler for HotSpot written in Java, with an API to interact with the compiler from Java. Truffle is a toolkit for implementing programming languages as self-optimizing AST interpreters. Truffle uses the Graal hooks to perform partial evaluation of Truffle-based interpreters to generate highly optimized native code. The partial evaluator doesn't know anything about the language being compiled, save for a few annotations that Truffle provides to control inline caches and such. We're using this approach to create new optimizing runtimes for Ruby (TruffleRuby), JavaScript (Graal.js), R (FastR), Python (GraalPython), and even LLVM bitcode (Sulong). There are languages being implemented outside of Oracle Labs as well [3]. So, it's being stressed by a wide range of language semantics. As for performance... I work mostly on TruffleRuby. There we're seeing considerable performance advantages against other Ruby implementations across a wide array of benchmarks and workloads. We really do get the JIT for free by virtue of being a Truffle-based language implementation. It's quite liberating as the compiler technology is free to evolve separately from our Ruby implementation, in contrast to the tight coupling you'd have with a language-specific JIT. [1] -- https://github.com/oracle/graal/tree/master/truffle https://github.com/oracle/graal/tree/master/truffle [2] -- https://github.com/oracle/graal/tree/master/compiler https://github.com/oracle/graal/tree/master/compiler [3] -- https://github.com/oracle/graal/blob/master/truffle/docs/Languages.md https://github.com/oracle/graal/blob/master/truffle/docs/Lan...

honestoHeminway 8y ago

it even rhymes with gcc

dmux 8y ago

The description immediately reminded me of a book called "Understanding Computation." Scrolling down I see the video is by Tom Stuart, the author of that book. I'd really recommend it (the book) for anyone interested in learning about "big step" (operational) and "small step" (structural) semantics.

Dangeranger 8y ago

Tom Stuart, the author of the post, also has written an interesting article called "Programming with Nothing" in which he demonstrates how to use first-class functions in Ruby to explain the Lambda Calculus.[0] [0] https://codon.com/programming-with-nothing https://codon.com/programming-with-nothing