The compilers tag has no wiki summary.
2
votes
1answer
128 views
Monotonicity in data flow analysis
I am studying program analysis and synthesis, I was reading a presentation
about some data flow analysis.
I can't seem to understand why $$\bigcap_{s'\in\text{pred (s)}}\text{Out}(s')$$
and ...
6
votes
1answer
214 views
Literature on alias analysis
I am writing my master's thesis in CS and I am working with alias analysis. The thing that I am interested in is intraprocedural, flow sensitive must- and may-alias analysis for Java-like languages.
...
5
votes
3answers
130 views
Preserving termination when rewriting recursive programs
Powerful program transformations like partial evaluation, deforestation and supercompilation are based on applying three kinds of transformations:
Rewrite using axioms, e.g. a+b = b+a.
...
5
votes
2answers
416 views
Certified compiler and optimizations in Coq/Agda
I am interested in verified compilers formalized in Martin-Löf type theory, i.e. Coq/Agda. At the moment I’ve written a small toy example. Therewith I can prove that my optimizations are correct. For ...
5
votes
2answers
120 views
Why do we need PAP (partial aplication) objects in heap?
In the paper “Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages” by Simon Marlow and Simon Peyton Jones it is told that a PAP heap object may be created in the push/enter model ...
9
votes
1answer
210 views
What are possible implementations of Haskell's type classes and what are their (dis)advantages?
As far as I know, a Haskell function with type classes constraints is internally compiled to a function with additional arguments that receive dictionaries with the necessary implementations of each ...
4
votes
2answers
353 views
machine learning for code and compiler optimization?
I am looking into ML for generating more efficient code (i.e. compile time and run time heuristics). I have a phd (compilers, hpc), but very little ML experience.
I would appreciate any references ...
-4
votes
1answer
572 views
Proof that DFA that accepts string has NFA that accepts reversal of string
I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...
18
votes
5answers
580 views
Compiler correctness proofs
I am looking for tutorial material that covers compiler correctness proofs, preferably using denotational methods, at the level of a beginning grad student.
Alternatively, do you know of some ...
1
vote
1answer
151 views
How is the iteration space of a nested for-loop containing two sequential nested loops represented?
In a general for loop of the form:
for (i = 0, i <= n, i++) {
for (j = i, j <= n, j++)
...
for (k = i, k <= n, k++)
...
}
What ...
2
votes
1answer
189 views
Can any language be modeled as LR(k)
If L(G1) is the language that is produced by grammar G1 and G1 is not LR(k) parsable (specifically speaking for k = 1). Does there exist a grammar Gx that is L(Gx) = L(G1) where Gx is LR(1) parsable ? ...
5
votes
1answer
491 views
The Stalin compiler brutally optimizes, but how?
This question was first asked on Stackoverflow, but the question was closed and suggested that it should be moved to cstheory. Since compiler questions are quite rare here, I was not entirely sure. If ...
1
vote
0answers
90 views
Optimal inlining algorithm
I seek an algorithm to optimise the process of inlinling. Is there such an algorithm, or set of such algorithms? Is there an efficient functional algorithm?
To be specific assume we have an Algol ...
7
votes
2answers
199 views
Where can I find an elementary small-step structural operational semantics for closures?
Lexical closures are an implementation technique in languages with first-class functions.
I'm interested in a simple operational description of function closures. Does anyone know of such a ...
0
votes
1answer
134 views
Describing a grammar and associated parser
In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization ...
1
vote
2answers
418 views
Equivalence of two basic blocks
My questions:
What are other names for this and similar problems and their fields? ("equivalence of varieties in universal algebra", "equivalence of algebraic structures", "rewriting systems for ...
5
votes
2answers
745 views
Brackets expression incremental parsing algorithm
I am looking for efficient and easy in implementation algorithm for incremental parsing of expressions with brackets.
Consider the example with expression like "((1)())(2)". Parse tree for that ...
10
votes
1answer
231 views
Has anyone used Pottier and Gauthier's polymorphic defunctionalization in a modular compiler?
Defunctionalization is a program transformation that converts higher-order programs into first-order programs. The idea is that given a program, there are only finitely many lambda-abstractions, so ...
0
votes
0answers
225 views
Compiler Construction: Similarities between the token, leaf and variant classes [closed]
I am currently writing my own programming langauge using the standard multipass compiler model. I haven't studied cs at uni (yet!) so if I have got anything very wrong then please do say.
A friend of ...
14
votes
4answers
908 views
What's new in compiler optimization techniques over last few years?
I'm interested in optimization of data flow and control flow graphs and in particular more computationally complex.
But it will also be interesting to know about the latest inventions in the field of ...
9
votes
2answers
996 views
What are current open problems in compiler theory?
Compiler theory seems to be a pretty vetted subject. What are some open problems or current research happening in the field?
