Compilers for Free

https://codon.com/compilers-for-free

by grawprog • 7 years ago

165 48 7 years ago

codon.com

iamNumber4• 7 years 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• 7 years ago

Thank you.

sephoric• 7 years 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• 7 years 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

4thaccount5• 7 years 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• 7 years 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.

quickthrower2• 7 years ago

Free as in monad, not as in beer or as in speech

tom_mellior• 7 years ago

Free as in "once you have written an interpreter, you do not need to write a compiler anymore, it will just appear".

thedaemon• 7 years 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• 7 years 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

sifoobar2• 7 years 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

gizmo686• 7 years 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• 7 years 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

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

gmueckl• 7 years ago

All modern x86 CPUs do this to some extent. The details changed over the decades, but the basic principle these days is that the CPUs decode the x86 instruction set into a secret, internal only, more orthogonal sequence of instructions. My understanding is that these sequences can be quite long for the more involved CISC operations. And according to the manuals written by Agner Fox, some instructions even have special cases based on their operands to do something equivalent, but much faster. One particular example that I remember is xor ax,ax which is often used to set ax to zero and is a one byte instruction. Modern CPUs don't compute the xor in the ALU, but just rename ax to a register that is set to 0.

mamcx• 7 years ago

My understanding is that you need for pull this off (apart of transpiring) you need that the host have a solid meta-programming facilities.

I'm on rust now and can't see how pull the same idea, apart of emit rust code then compile it with rust.

andyonthewings• 7 years ago

The Haxe compiler is also an interpreter of the Haxe programming language, and it is properly treated as one of the many back-end targets of the compiler.

Moreover, the interpreter is also used as the macro runtime, that means Haxe macros can run arbitrary "real" Haxe code during compilation, e.g. checking the current git branch name or current time and inject the result as a static read-only string in the code.

grawprog• 7 years ago

DMD also comes with a built in D interpreter, RDMD, allowing you to use D as a scripting language with a compiled binary. This can be embedded or called from your D program allowing your program to have a scripting layer written in the same language as the compiled binary. As far as I know, executing a .d file with RDMD is nearly as fast as running a compiled binary.

Joky• 7 years ago

To me the difference is that an interpreter read the code and execute every operation immediately as it encounter them, while I expect a compiler to process a large portion of the code and potentially perform more transformation on it before executing it. In some way I see an interpreter as potentially invoking a compiler on a single operation one-at-a-time and executing the result of the compilation before moving to the next operation.

RHSeeger2• 7 years ago

The lines are grey, to some extent. Many interpreted languages (such as Tcl) compile to bycode, then interpret that. The compilation happens not at the operation level, but at the block (or maybe file) level.

abeppu• 7 years 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• 7 years 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-...

nirvdrum2• 7 years 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

[2] -- https://github.com/oracle/graal/tree/master/compiler

[3] -- https://github.com/oracle/graal/blob/master/truffle/docs/Lan...

marktangotango• 7 years ago

Isn’t “new” a bit of stretch? That project must be close to 10 years old by now!

dtech• 7 years ago

Why is it that [...] when we want to produce a new compiler, we don't write an interpreter and pass it through a high quality, general partial evaluator?

As far as I know, it has been tried numerous times and has been an area of active research in the past, but results turned out unsuccessful. Mainly because error reporting and performance, both compile-time and run-time, is hard to achieve.

It's a little bit like pure functional programming. Super elegant in principle, hard to get right and usable in practice.

chrisseaton2• 7 years ago

As far as I know, it has been tried numerous times and has been an area of active research in the past, but results turned out unsuccessful.

TruffleRuby is a Ruby implementation that works exactly by writing an interpreting and passing it through a general partial evaluator. It's successful enough to pass almost all the Ruby spec and to run real Ruby applications including their C extensions.

https://github.com/oracle/truffleruby

vanderZwan• 7 years ago

Mainly because error reporting and performance, both compile-time and run-time, is hard to achieve.

Do you have more information on the error reporting bit? Is it due to losing important metadata during compilation? If so, couldn't a different, more metadata-rich representation than the basic AST most of us are familiar with help here?

agumonkey• 7 years ago

wild guess, maybe it's like yacc vs hand made recursive descent parsers.. the former doesn't allow enough control so people prefer doing the effort so they can change bits here and there

dmux• 7 years 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• 7 years 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

Compilers for Free

Related Stories