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.3k
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 <...
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,019
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)}$....
4 votes
Accepted

Computing the DAG of a program given source code or AST

I assume you're looking for ways to compute the Control Flow Graph of a given program. This graph depends (obviously) on the actual operational semantics of the language you are interested in, and so ...
  • 13.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$ ...
  • 690
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 ...
  • 382
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,125
2 votes
Accepted

Name a set of program variables

This new version of the answer tries to take into account the changes in the question, and the information exchanged in the comments. This answer assumes that $S$ should be the set of variables that ...
  • 1,512
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.3k

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