7
votes
Accepted
Difference between syntax and semantic error in programming languages
In the strictest sense, there is no real difference between syntax errors and semantics errors, at least as far as language theory is concerned: the only salient difference is the complexity of the ...
- 13.7k
7
votes
Accepted
Does Standard ML validate (CBV) eta equivalence?
@xuq01's guess is (extremely surprisingly!) wrong. The CBV eta rule described in the question is sound in Standard ML: the value v is contextually equivalent to <...
- 32.4k
6
votes
Has anyone used Pottier and Gauthier's polymorphic defunctionalization in a modular compiler?
One approach is described by
Georgios Fourtounis and Nikolaos S. Papaspyrou. 2013. Supporting Separate Compilation in a Defunctionalizing Compiler. SLATE 2013.
As @gasche mentions:
A different ...
- 2,049
6
votes
Commutative operation benefits
One example where commutativity helps is in computing the determinant. Nisan showed that any non-commutative algebraic formula that computes the $n \times n$ determinant must have size $2^{\Omega(n)}$....
- 743
3
votes
Generating grammar from a string
You might be interested in Sequitur (given a single string, it compresses it by finding a grammar that generates just that one string) or in grammar induction (given a set of strings, it finds a ...
- 11.7k
3
votes
Locally nameless representation implementation
Locally nameless discipline is important when one has to normalize expressions with free variables. This happens in dependent type theories, where equality of types is tangled up with equality of ...
- 28.3k
2
votes
Accepted
Why can a Predictive Parser contain E' -> TE' | ε
... is not valid since we have "left recursion" (a variable that calls itself).
That's not what a left recursion is. That's simply recursion.
Direct left recursion is when a rule $A \to A\alpha$ ...
- 720
2
votes
Does Standard ML validate (CBV) eta equivalence?
SML compilers do perform eta-reduction (at least SML/NJ does), but I expect most functional programming language compilers do, even those for which the eta-law does not always hold.
E.g. the pointer ...
- 390
2
votes
Difference between syntax and semantic error in programming languages
It is hard to say. The boundary between "syntactic errors" and "static semantic errors" can be really blurred.
One appropriate example would be Curry-style (extrinsic typing) and Church-style (...
- 1,175
2
votes
Optimal evaluation of polynomials / rational functions
In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic ...
1
vote
Accepted
Can we say that Church encoding is a form of Gödelization?
It's possible to do a Gödel numbering that assigns every term in System F to a unique natural number?
The answer is yes, pick your favorite way of coding terms in F, simply because they are ...
- 21.5k
Only top scored, non community-wiki answers of a minimum length are eligible