Skip to main content
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 ...
cody's user avatar
  • 13.9k
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 <...
Neel Krishnaswami's user avatar
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)}$....
Robert Andrews's user avatar
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 ...
Blaisorblade's user avatar
  • 2,069
5 votes
Accepted

Is there a high level (functional) language compiling to Mixed Integer Linear Programming problems?

Here are the systems/languages I know of for representing these kinds of problems at a higher level of abstraction: The Z3 solver has higher-level constructs for words (fixed-length bit-strings), ...
D.W.'s user avatar
  • 12.2k
4 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 ...
Andrej Bauer's user avatar
  • 29.2k
4 votes
Accepted

Is beta normalization used for program optimization?

Short answer: $\beta$-reduction is done like crazy in any modern optimizing compiler. As you can easily check e.g. for GHC. The caveat is that $\lambda$s usually serve no useful purpose in the ...
cody's user avatar
  • 13.9k
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 ...
D.W.'s user avatar
  • 12.2k
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$ ...
orlp's user avatar
  • 885
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 ...
Stefan's user avatar
  • 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 (...
xrq's user avatar
  • 1,185
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 ...
Remco Bloemen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible