Questions tagged [compilers]
The compilers tag has no usage guidance.
44 questions
2
votes
1
answer
141
views
Is beta normalization used for program optimization?
Beta normalization reduces a lambda term to its beta normal form, if it exists. The beta normal form is a computationally equivalent term with no "redundant" computation, in a sense; for ...
- 105
4
votes
1
answer
182
views
Is there a high level (functional) language compiling to Mixed Integer Linear Programming problems?
Many different kinds of optimization problems can be expressed as Mixed Integer Linear Programming (MILP). The translation is usually very direct, and one has to encode invariants as constraints in a ...
- 648
-1
votes
1
answer
91
views
Generating grammar from a string
Given a string generated with a valid grammar, how can I find list of all the valid grammar for that particular string?
Problem statement - I'm trying to build a code base scanner, and I'd like to ...
- 99
-1
votes
1
answer
262
views
Locally nameless representation implementation
ORIGINAL: I am programming a functional compiler and found out about locally nameless representation (using de brujin indeces for bound variables and names for free variables). I just don't understand ...
- 9
2
votes
0
answers
128
views
Does GHC use graph reduction?
I have read somewhere that GHC does not use graph reduction for compiling/evaluating expressions. Is this right? If yes, what does it use as an alternative?
- 131
0
votes
0
answers
27
views
Quantifying the cost of procedures
Is there any research on quantifying the cost of a procedure, with regard to compiler optimization?
I.e. assigning some kind of cost in terms of CPU time or memory to a procedure, either so the ...
- 111
5
votes
1
answer
138
views
Commutative operation benefits
With an associative operation I can rewrite a computation tree
+
/ \
+ 4
/ \
+ 3
/ \
+ 2
/ \
0 1
to be more efficient ...
- 71
4
votes
0
answers
146
views
Origin of simulation relations for compiler correctness
Leroy uses simulation relations as a means of showing compiler correctness; the basic idea is that a simulation relation is an asymmetric binary relation between states in two different small step ...
- 41
1
vote
1
answer
69
views
Why can a Predictive Parser contain E' -> TE' | ε
I am studying the basics of predictive parsing and I think I have missed a concept that I would like to understand instead of just accepting and memorizing. I am watching this video and I am confused ...
- 41
1
vote
0
answers
81
views
Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?
I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that
$G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$.
$G$ has no left recursion; that is, we can't ...
- 81
5
votes
2
answers
238
views
Does Standard ML validate (CBV) eta equivalence?
$\eta$ equality of functions is fundamental in their Category-theoretic semantics but in practice even "functional" languages include "impure" features that violate it.
Note that this is not an issue ...
- 1,730
7
votes
4
answers
7k
views
Difference between syntax and semantic error in programming languages
When compilers generate errors for a specific programming language, there's distinction between syntax & semantic errors. E.g. ) + f 3 has ill-formed syntax, ...
- 181
1
vote
1
answer
267
views
Optimal evaluation of polynomials / rational functions
A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the ...
- 429
-3
votes
1
answer
552
views
Can we say that Church encoding is a form of Gödelization?
We see here the following statement about Godelization:
Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the ...
- 2,581
0
votes
1
answer
2k
views
Computing the DAG of a program given source code or AST
I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG).
...
1
vote
1
answer
175
views
Name a set of program variables
I am interested in the set of the variables that satisfy the following properties. I would like to find a proper name for them.
We assume that a program $\phi$ has a set of variables $v_0, \ldots, ...
- 73
2
votes
2
answers
235
views
Would it be possible for a compiler to convert a recursive sum into the average formula?
def sum1(n):
if n==0: return 0
else: return n + sum1(n-1)
def sum2(n):
return n*(n+1)/2
A compiler can not convert ...
- 3,217
-4
votes
1
answer
293
views
Fermat's last theorem and the LLVM compiler [closed]
The following blog:
http://blog.regehr.org/archives/140
discusses how the LLVM compiler seems to prove that Fermat's last theorem is false by showing that the compiler optimizes the $while(1)$ "...
- 29
10
votes
1
answer
232
views
Program Minimization
Circuit Minimization is the problem to minimize the size of a given circuit. Is there anything similar for general programs?
In particular my question is -
Do there exist algorithms to minimize the ...
- 1,311
4
votes
1
answer
162
views
Is it possible to create an algorithm-aware optimizer?
I've recently implemented a physics system where each object has to interact with eachother. It consisted of, pretty much, the following algorithm:
...
- 3,217
3
votes
1
answer
342
views
Compiler Optimization: How do you automatically fuse conditionals into the loop index?
Let's say that you have some loop
for(i=0;i<n;i++){
if(i > 3 && i < 8){ p(i); }
}
How would I go about automatically fusing that into
...
- 141
2
votes
1
answer
1k
views
How can an inherited attribute be simulated using a synthesized attribute?
Is it possible to simulate an inherited attribute using a synthesized attribute? For example, can the inherited attribute SYMTAB used in normal code generation modules be simulated using a synthesized ...
- 175
9
votes
3
answers
498
views
Can one automate algorithmic analysis?
Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a ...
- 341
13
votes
2
answers
2k
views
Is compiler for dependent type much harder than an intepreter?
I have been learning something about implementing dependent types, like this tutorial, but most of them is implementing interpreters. My question is, it seems that implementing a compiler for ...
- 347
2
votes
1
answer
369
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 $$\...
- 161
10
votes
1
answer
359
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.
...
- 211
6
votes
3
answers
281
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.
Unfolding/...
- 390
10
votes
2
answers
1k
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 ...
- 443
5
votes
2
answers
314
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 ...
- 557
10
votes
1
answer
486
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 ...
- 2,611
8
votes
1
answer
3k
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 ...
- 81
-5
votes
1
answer
3k
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 ...
- 7
20
votes
5
answers
1k
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 ...
- 4,806
1
vote
1
answer
215
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 ...
- 127
2
votes
2
answers
405
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 ? ...
- 121
14
votes
1
answer
2k
views
The Stalin compiler brutally optimizes, but how?
J.M. Siskind's research statement states:
Stalin is an optimizing compiler for Scheme that performs whole-program static analysis and uses the results of that analysis to generate extremely efficient ...
- 390
1
vote
0
answers
156
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 ...
- 111
8
votes
2
answers
300
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 ...
- 2,717
0
votes
1
answer
191
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 ...
- 103
2
votes
2
answers
918
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
2
answers
1k
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 ...
- 151
15
votes
2
answers
471
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 ...
- 32.9k
15
votes
4
answers
1k
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 ...
- 253
13
votes
2
answers
3k
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?