Skip to main content

Questions tagged [compilers]

Compilers are implementations of programming languages which convert source code into another format, such as a binary executable, bytecode, or another programming language. Use this tag for questions about the design or implementation of compilers. This contrasts with interpreters, which execute source code directly.

Filter by
Sorted by
Tagged with
4 votes
2 answers
213 views

What are the cons of inlining then optimizing and then reverse inlining?

In many programming languages, not all functions may be inlined. However, assuming that a language is designed in such a way that all functions may be inlined, what the disadvantages of inlining all ...
ggZQX6YPvD's user avatar
24 votes
7 answers
12k views

Why do compilers typically convert code into abstract syntax/parse trees before the final product?

When I started researching parsing and compiling I started with simple mathematical expression parsers. Many of the existing implementations I found have an intermediate step of converting a string ...
CPlus's user avatar
  • 8,261
7 votes
1 answer
243 views

Theoretical Book on Compilers [closed]

I am looking for books that mostly discuss the theory of compilers (e.g. full-abstraction), and less how to actually build them. Basically, "compilers for mathematicians". Are there any such ...
IllogicalUser's user avatar
3 votes
1 answer
195 views

How to save C struct pointers in interpreted language? [closed]

I am making an interpreter based on the lox from the book Crafting Interpretes. I have modified the language implementation heavily but the core still remains the same. Currently I am adding standard ...
Timsib Adnap's user avatar
5 votes
1 answer
297 views

How does link-time function inlining work?

I am familiar with traditional linking concepts (static and dynamic linking, relocation, PIE) and with traditional compiler optimizations (such as static expression evaluation, loop unrolling and ...
Borisav Živanović's user avatar
18 votes
8 answers
356 views

What's the relation between a language being managed and its compiler being reversible?

As a starting developer, I worked with Pascal and Delphi. Later on, I came in contact with C++ and Visual Basic. All those are native languages, which means that their compiled binaries were ...
Dominique's user avatar
  • 315
1 vote
0 answers
107 views

How to serialize IR with cross references?

When I type check, I generate IR and serialize them to avoid retypechecking of libraries, which is usually unchanged after the first compilation. However, I store these variable references using ...
ice1000's user avatar
  • 2,424
9 votes
0 answers
227 views

How can a compiler optimise persistent data structures to use mutable data structures "under the hood"?

Consider for a motivating example a copy-on-write array, which implements a persistent (i.e. immutable) array data type. As an optimisation at runtime, a reference counter can be used to avoid the ...
kaya3's user avatar
  • 19.1k
1 vote
0 answers
181 views

Global value numbering implementation

I wrote a global value numbering algorithm according to this paper and I would like to verify if certain behaviour of the algorithm is correct. My implementation as is performs the following code ...
chrysante's user avatar
  • 768
0 votes
1 answer
361 views

How would you implement a language in which the function-name could be separated from function arguments two different ways?

Suppose that there was a programming language in which there were two different syntaxes for function calls. An example of this is shown below: ...
Samuel Muldoon's user avatar
1 vote
1 answer
133 views

Expressing runtime constraints with trait-bounds

I've recently listened to Corecursive episode with John A De Goes and there's one thing that really got me thinking: the idea of type class laws pertaining to performance guarantees. The example ...
gstukelj's user avatar
  • 143
30 votes
11 answers
19k views

Why do so many programming languages not have a "built-in" way to do simple math functions?

Note 1: My question is not about the factorial function. It's about "simple math functions" that high-school level pocket calculators can do, but most programming languages cannot do without ...
Nike Dattani's user avatar
6 votes
2 answers
175 views

How to determine the meaning of a polymorphic operator?

Some operators have multiple meanings. For example: - represents the prefix negative, or it can represent the infix ...
Aster's user avatar
  • 3,198
1 vote
1 answer
213 views

How might we convert type declarations into constructor calls? [closed]

Suppose that we have two languages, A and B. In language A, there are a lot of data-type declarations. In language B there are no data-type declarations to the left of the assignment operator, but ...
Samuel Muldoon's user avatar
6 votes
1 answer
586 views

What, if any, runtime cost is incurred by using 64-bit ints on 32-bit platforms in LLVM?

I'm writing a language frontend for LLVM, and I noticed that the IR docs say that integers of (almost)any width can be used without limit. I presume this to mean that LLVM or its backends convert ...
Ginger's user avatar
  • 2,619
2 votes
1 answer
331 views

Are enum members literals or constants in an IR?

While implementing enums in Tyr, I just realized that enum constants are the only form of literal-like entity that is not represented like a literal in the intermediate representation. The enum ...
feldentm's user avatar
  • 1,779
6 votes
2 answers
206 views

How to ensure coherent choices of representatives in an e-graph?

E-graphs are a neat intermediate representation for program transformations and optimisations, which group program terms into equivalence classes (e-classes). An optimising compiler can then select ...
kaya3's user avatar
  • 19.1k
11 votes
4 answers
1k views

Data structures for scopes and variable shadowing

Let's say I have some code in my target language like: ...
Rob N's user avatar
  • 1,083
9 votes
1 answer
1k views

What are the tradeoffs between using sea of nodes, CFG of basic blocks, and egraphs for compiler optimizations?

I've heard of "sea of nodes" intermediate representations mostly in the context of just-in-time compilation (JVM, V8, Graal) whereas intermediate representations such as LLVM IR are used in ...
Troy Sargent's user avatar
16 votes
5 answers
2k views

What are some techniques for faster, fine-grained incremental compilation and static analysis?

An incremental compiler is one which only needs to recompile the parts of a program which changed since the last output, as opposed to a batch compiler which must re-compile everything. Incremental ...
tarzh's user avatar
  • 3,859
38 votes
6 answers
5k views

How to ensure that an optimising compiler will terminate?

An optimising compiler typically applies some set of rewrites to some intermediate representation of the program, replacing terms with other terms which are supposed to be equivalent but more ...
kaya3's user avatar
  • 19.1k
10 votes
1 answer
731 views

Can type-checking algorithms be practically generated from formal descriptions of type systems?

It's well-known that a formal grammar (a formal description of a language's syntax) can be used to programmatically generate a parser (an algorithm which analyses that syntax); tools which do this are ...
kaya3's user avatar
  • 19.1k
10 votes
4 answers
2k views

How to ensure correct transformations with `break`, `continue` and other context-dependent statements?

I have a compiler backend which targets high-level languages, by building an abstract syntax tree for the output and then using this to generate code ─ that is, this tree is really an intermediate ...
kaya3's user avatar
  • 19.1k
10 votes
3 answers
1k views

Can you, should you, go straight from AST to SSA?

I'm beginning to read Appel's book Modern Compiler Implementation in C. The book is about 25 years old, so maybe it's not so "modern" anymore, I don't know. I'm skimming the book and it ...
Rob N's user avatar
  • 1,083
5 votes
0 answers
215 views

Why has there been little recent work on GPU compiler phase optimization?

While GPU compiler phase optimization has been shown to improve performance significantly (e.g. https://link.springer.com/chapter/10.1007/978-3-319-75178-8_35), there has been very little follow-up ...
Amrit Baveja's user avatar
16 votes
7 answers
3k views

What languages give you access to the AST to modify during compilation?

Are there any languages which allow you to get access to the AST during compile time, to use some part of the AST to generate code, or to possibly rewrite the code/AST to optimize it in a heuristic ...
Lance's user avatar
  • 705
4 votes
1 answer
167 views

Why link the entire static library rather than only the needed functions?

This is more about compiler implementation than language design but when statically linking a library (e.g. in Swift) the entire library is linked even if only a handful of the functions are actually ...
CPlus's user avatar
  • 8,261
8 votes
1 answer
341 views

What are the key steps to compiling a custom programming language that is similar to Rust (typechecking, type inference, and borrow checking)?

I have been working on a custom programming language for a bit, and keep coming back to the fact that I am not easily visualizing in my mind how the compiler will work past the step of creating the ...
Lance's user avatar
  • 705
5 votes
1 answer
166 views

What parts of the code can be easily shared between the LSP and the Compiler?

I was originally thinking to design the compilier upfront as a compiler and LSP server as well, but the answers there dissuaded me from making them share all code. But, I would still like them to ...
Starship - On Strike's user avatar
13 votes
2 answers
1k views

Why is it so difficult to implement the first Futamura projection?

The Futamura projections are a series of three transformations that can be performed on interpreters, compilers, and compiler-compilers respectively. These transformations rely on a specializer which ...
Corbin's user avatar
  • 851
22 votes
2 answers
5k views

Why is it so hard to evaluate functions with constant arguments at compile-time?

I noticed C23 has constexpr but only for variables, not for functions. While C++ does, this would allow a function to be defined in such a way that if the function ...
user1345541's user avatar
11 votes
5 answers
993 views

What are the pros and cons of a compiler with a single-pass parser?

Assume you are tasked with writing a compiler for a language that can be parsed in a single pass, like C, but does not necessarily have to be. What are the pros and cons for doing this? Would you do ...
Gavin D. Howard's user avatar
13 votes
3 answers
2k views

What are the pros and cons of single-pass compilers?

Okay, we all know the standard compiler architecture: a batch program with multiple passes for parsing, optimizing, and generating code. Suppose you wanted to go all Turbo Pascal and implement a ...
Gavin D. Howard's user avatar
17 votes
7 answers
3k views

What are the pitfalls of using an existing IR/compiler infrastructure like LLVM?

Using something like LLVM when designing a compiler has a lot of advantages, since tons of work can be saved by using an existing optimizer and code generation for a variety of platforms. Even large, ...
Rydwolf Programs's user avatar
3 votes
2 answers
688 views

What are the pros/cons of a tree-based interpreter vs a bytecode-VM-based interpreter?

Based on this closed question. Basically, why would one choose a pure interpreter for a language implementation as opposed to a virtual machine/bytecode approach like Java or Python (even if at ...
kouta-kun's user avatar
  • 1,359
8 votes
3 answers
384 views

When is ABI stability “worth it”?

ABI stands for application binary interface, and it represents how different precompiled components of a program interact. This can be a program calling out to an OS function or part of the language ...
Bbrk24's user avatar
  • 8,937
7 votes
4 answers
274 views

How can we backpatch differently-sized jump instructions?

Consider a compiler whose target language is some virtual machine bytecode. The jump instructions have to encode the size of their jumps. For example, in JVM bytecode the ...
hugomg's user avatar
  • 1,345
6 votes
2 answers
249 views

How can a compiler's parse errors be tested?

There are fairly straightforward ways to test a compiler's behaviour on valid programs: most obviously, build a suite of programs to run through the compiler, and know what should happen when they run....
Michael Homer's user avatar
  • 12.9k
6 votes
1 answer
163 views

How do I make LLVM actually inline anything?

I've been working on a draft of a Trilangle compiler using LLVM. Out of curiosity, I took the generated IR (given the Trilangle program ?!oi@) and plugged it into ...
Bbrk24's user avatar
  • 8,937
3 votes
1 answer
225 views

How can an abstract-syntax tree be converted into linear three-address code?

I have an abstract-syntax tree (AST) for a language, and I'd like to use some sort of three-address code (TAC) to represent the program in a linear way, before converting it to assembly. How do I do ...
springogeek's user avatar
11 votes
2 answers
481 views

What are some caveats to be careful about when implementing the `?:` (ternary conditional) operator?

Thus far, I see two things that can go wrong when implementing the ?: (ternary conditional) operator: PHP famously incorrectly implemented the ...
FlatAssembler's user avatar
4 votes
2 answers
180 views

How does a compiler know that an identifier in an expression refers to a memory location, or the value stored at that location?

There are situations during compilation when some identifier represents a particular value ("contained" in a variable, etc), but sometimes it references the variable's memory location ...
springogeek's user avatar
4 votes
0 answers
75 views

How could I use the TypeScript Compiler API to compile TypeScript to ActionScript 3 bytecode? [closed]

TypeScript is a superset of ECMAScript and its compiler supports targetting ECMAScript 3; it even supports yield and await based ...
Hydroper's user avatar
  • 1,007
13 votes
1 answer
252 views

How to implement a REPL for a compiled language?

Implementing a REPL is relatively straightforward for an interpreted language; the interpreter maintains the program state as normal, and evaluates each separate statement as normal, just using the ...
kaya3's user avatar
  • 19.1k
2 votes
1 answer
86 views

When you write regex engines how do you know if question marks `?` mean zero or one of if they refer to non-capturing groups?

When you write regulair expression (regex) engines, how do you tell .... if ? means zero or one ...or if... ...
Samuel Muldoon's user avatar
12 votes
1 answer
228 views

How do I implement coroutines on WebAssembly?

I am building a compiler targeting WebAssembly for a language that makes heavy use of first-class coroutines. WASM doesn't have native coroutine support (yet), so I have to emulate it. Given the ...
Michael Homer's user avatar
  • 12.9k
19 votes
6 answers
1k views

Can regex be compiled into efficient machine code?

Most languages that have regex have a regex parsing library that interprets the regex at runtime and matches them to strings. I am a fan of eliminating as much runtime overhead as possible, and as ...
CPlus's user avatar
  • 8,261
24 votes
3 answers
742 views

How to transpile goto to a language that lacks it?

I'm writing a transpile for a C-like language to Javascript, which lacks a goto statement. Unfortunately the existing library code contains a lot of ...
mousetail's user avatar
  • 8,229
5 votes
1 answer
96 views

How would I allow a variety of different syntaxes for passing arguments into MathJax or LaTeX commands? [closed]

What is LaTeX If you already know what LaTeX is, then skip down the the section labeled "sloppy syntax". There is a type-setting language known as LaTeX. LaTeX even has its very own Stack ...
Samuel Muldoon's user avatar
5 votes
1 answer
253 views

What is defunctionalisation useful for?

Defunctionalisation refers to program transformations which replace first-class functions and closures with conventional data structures (e.g. structs and enums), so that higher-order functions become ...
kaya3's user avatar
  • 19.1k