# Tag Info

21

To the best of my knowledge, the term staged computation was first used by Bill Scherlis in this paper. Prior to that, the term "partial evaluation" was used for much the same concept, but the idea of staged computation is subtly different. Both the ideas are related to Kleene's S-m-n theorem. If you have a function $\phi(m,n)$ of two arguments, but you ...

9

Although the other answers are technically correct, I don't think they give a correct understanding of why computer scientists are interested in staged functions. By creating staged functions, you define programs that generate programs. One of the big goals of modern practical language theory is to maximise potential reuse. We want to make it possible to ...

5

Update Based on your comment, I'm not concerned so much about switch statement being inefficient as I am by the fact that the switch statement exists at all. , I think that I understand the question better now. And the answer is that you want currying to be applied on the first execution. As a quick explanation of currying, consider a mathematical ...

5

The PEPM (Partial Evaluation and Program Manipulation) Symposium Series is still running. That'd be a good place to start to see what the current hot topics are and who is still working on Partial Evaluation.

5

The answer is given in the technical perspective piece for the article in question [1]. The problem under consideration is the area of tension between general and specific code: Programs can be written to be either general-purpose or special-purpose. General-purpose code has the advantage of being usable in a variety of situations, whereas special-purpose ...

4

Yes and no. Yes, you could structure a compiler this way, but most of the benefits you are hoping for would not materialize. There may be some benefits, such as a powerful compile-time meta-language. There are also costs like a complete loss of the ability to make meaningful guarantees about code that isn't completely self-contained (e.g. takes in objects ...

4

The 1998 Partial Evaluation. Practice and Theory series of lecture notes is slightly newer and fits your desired terminology. Like said however, the notions of program specialization and partial evaluation are often taken as synonymous (e.g. they are so on p.1 of Jones et al.), so ignore the literature using/preferring the later term at your own peril. ...

2

I have not been looking at partial evaluation for a very long time. There is much stuff in code optimization techniques for compilers that can fit that framework when properly presented. Thing often become relevant when you start looking at them the right way. But people in optimizing compilers may not try to emphasize the partial evaluation view when ...

2

The meta-problem $\mathcal P$ is: Given a problem $P\in \mathcal P$, find a (Turing) machine that solves $P$, optimized for some resource constraints $C(P)$. It's undecidable* whether a given Turing machine even solves $P$, let alone whether it's optimal according to some criterion. Since your problem isn't computable even without resource bounds, ...

2

The problem with this is that there is no way to distinguish between (1, 2) and 1 . 2: both have to produce (1, 2). This means that for a left-associative ., 1 . 2 . 3 and (1, 2) . 3 have to produce the same result. (And switching to right-associative . does not help: it has the same issue with 1 . (2, 3).) Some ways I could think of bypassing this: The . ...

2

It is reasonably common nowadays that code is recompiled on occasion. For example, a JVM compiler will initially assume that some function call is not virtual (but can be proved wrong). It will then for a virtual function call generate code like "if (function implementation is what I thought it would be) then (call that implementation) else (recompile this ...

2

Unroll the loop. Instead of while true: switch on var: 1 => branch1 2 => branch2 default => branch3 replace that with an unrolled version: while true: switch on var: 1 => branch1 2 => goto loop2 default => branch3 return loop2: while true: branch2 Or, if you prefer: while true: switch on var: 1 =&...

1

It sounds to me that you're interested in complexity of preprocessing. I'll state your question in a different way. We have a problem $P$ consisting of pairs $(x,y)$ that satisfy some condition. We'd like an algorithm which (1) takes $x$, (2) can perform a lot of computation (preprocessing), (3) finally it's given $y$ and needs to output quickly whether \$(x,...

1

No. So far the only ones I've found are pretty obscure/old, both variations of C: `C E-Code

1

Caveat: I have not followed the field closely. In the early 1990s partial evaluation was fashionable as a research subject, but activity died down around the turn of the millennium. I think that's because nobody could make partial evaluation efficient. Later some key ideas resurfaced from a different community and in warped form, this time leading to ...

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