MENTAL
 Main Menu
 Language
 Techniques
 Partial Evaluation

Partial Evaluation
 PARTIAL EVALUATION

"Calculus and algorithm are the two main ideas of Western science" (David Berlinski).

"The parts are derived from the whole and not the whole from the parts" (Arthur M. Young).


The Concept of Partial Evaluation

Introduction

Partial evaluation is a computer technique that consists in the transformation of an expression (basically, source code) by means of a specialization. To do this, the original expression is assigned values to part of its parameters and then evaluated, producing a new expression, a specialized expression.

This simple but powerful idea is taken from the area of mathematical functions: a curry function is one in which only one argument is applied at a time, yielding successively more and more particularized functions with one less parameter.

Partial evaluation is a generic mechanism that has been the object of special attention and study, since it provides a unifying paradigm, a new perspective, in mathematics, computer science and logic, having received different names: restriction, projection, specialization and currying. But it has been in programming the area where it has undergone the most development, having also provided a very valuable aid in understanding the properties of programming languages themselves.


Motivation

The main motivation for partial evaluation is to increase the speed of execution, since particularized programs are more efficient than generic programs. There are, in this sense, two extreme tendencies:
  1. Write many small efficient programs. The disadvantage is that it takes a lot of programming and maintenance effort.

  2. Write a single highly parameterized program, capable of solving a wide range of problems. The disadvantage is inefficiency, mainly due to parameter processing.
The best between the two positions is to write a highly parameterized program and perform partial evaluations to obtain more efficient, understandable and manageable versions.


Partial evaluation process

The partial evaluation can be manual or automatic. The manual specialization has the disadvantage that it is necessary to make an effort to adapt the code, with the consequent possible appearance of errors. The most interesting is the automatic partial evaluation, because of its predictable behavior and as a generic mechanism:

The starting point is a parameterized X expression (source code segment). The automatic partial evaluation process consists of two phases:
  1. Specialization phase.
    The expression X is particularized by assigning values to some parameters E (which are called "static") and evaluated, obtaining a new expression < i>XXEX (called "specialized" or "residual" expression).

    Automatic specialization involves the development of a partial evaluator EP (or specializer): a program (rather, a metaprogram) with two arguments: the source code X and the set E corresponding to the static parameters. Its evaluation produces the specialized expression XE:

      EP(X, E) = XE

    The expression XE, in general, is shorter than the original (X), although sometimes, by deployment of loops or recursive calls, it could be longer.

  2. Evaluation phase. Values are assigned to the remaining D parameters (which are called "dynamic") and XE is evaluated with those dynamic parameters, i.e., XE(D), producing the result R:

      XE(D) = R

    The result obtained, R, is identical to that which would be obtained by evaluating X with all parameter values, i.e., X(E, D) = R.

    The expression XE(D) is more efficient than X(E, D), having precomputed the parts of X that depend only on E.

Partial evaluation types

The partial evaluation process can be of 3 types:
  1. Online. The evaluation phase takes place immediately after the specialization phase, i.e. after the specialized expression XE is obtained.

    Its main advantage is that it makes immediate use of computational resources, but it has the disadvantage that code generation may not be adequate, even infinite.

  2. Offline. Specialization is carried out in several stages. Initially, a preprocessing of the original expression (X) is performed based on information about which parameters are static, not on their values, and no decision process is performed by the specializer. In a second stage, starting from the concrete values of the static parameters, the specialization process (obtaining XE) takes place.

    Its main advantage is that it allows self-application (application to one's own partial evaluator EP) and the generation of program generators. In addition, the specialization algorithm is simpler.

  3. There is also the strategy called "mixline", in which the two previous methods are mixed.

Partial Evaluation in MENTAL

In MENTAL, partial evaluation is a mechanism that is available directly in the language. There is no need to develop any specializing program. The resources available to perform partial assessments are: A specialized expression may itself be specialized (higher-order partial evaluation). In this case, partial evaluation can be considered a type of phased or staged evaluation process.

Combined with the rest of the primitives, a highly flexible and expressive environment is available, including the possibility of evaluation in all three modes (online, offline and mixline).


Examples of simple particularization
  1. 123/(3=a) // ev. 1a2

  2. aaa/(a=123) // ev. (123 123 123)

  3. (a*x + b*y + c)/(a=1 b=2) // ev. (x + 2*y + c)

  4. (data = (123 "pepe" 6.5))
    data/("pepe" = "juan") // ev. (123 "juan" 6.5)
    data/("pepe" = θ) // ev. (data = (123 6.5))

  5. ( z = ⟨( f(x/b> y) = (x+y x*y) )⟩ )
    z/(+° = −°) // ev. ⟨( f(x y) = (x−y x*y) )⟩

Examples of currification
  1. We have the two-argument function

    ⟨( f(x y) = (x+y x*y) )⟩

    A curry version of f would be, for example, to specialize the parameter y with 7:

    ⟨( g(x) = f(x 7) )⟩ // ev. ⟨( g(x) = (x+7 x*7) )⟩

    Therefore,

    g(2) // ev. (9 14)
    g(a) // ev. (a+7 a*7)

  2. We have the union function (of sequences or sets).

    ⟨( union(x y) = (x↓ y↓) )⟩

    If we know one of the parameters, e.g. y=(1 2 3), we can specialize the generic expression:

    ⟨( union1(x) = union(x (1 2 3)) )⟩

    This expression evaluates to:
    ⟨( union1(x) = (x↓ 1 2 3) )⟩

    Application examples:

    union1(a b c) // ev. (a b c 1 2 3)
    union1(a b) // ev. (a b 1 2 3)
    union1(a) // ev. (a 1 2 3)

Examples of code specialization

(c =: (x=5 ← a>b →' x=4)°

ce = c/(a=3 b=4) // ev. x=4 (specialized code)

ce // ev. x=4 (specialized code evaluation)


Example of higher order specialization (specialization of specialization)

The scalar product of two numerical sequences x=(x1 ... xn) and y=(y1 ... yn) is defined as the sum of the products corresponding to each of the components of both sequences:

⟨( pe(x y) = +⊢([(x \⌊i... x#⌋ * y\⌊1…y#⌋]) )⟩

If we know that the size of the vectors is 3, then we can perform the first specialization:

⟨( (pe3((x1 x2 x3) (y1 y2 y3 )) = pe((x1 x2 x3) (y1 y2 y3) )⟩

The result is:

⟨( (pe3((x1 x2 x3) (y1 y2 y3)) = (x1*y1 + x2*y2 + x3*y3)) )⟩

If we now know one of the vectors, e.g., y=(10 20 30), then we have a second specialization:

⟨( pe3a(x1 x2 x3) = (pe3((x1 x2 x3) (10 20 20 30))) )⟩

The result is:

⟨( pe3a(x1 x2 x3) = (10*x1 + 20*x20 + 30*x3) )⟩

Application examples:

pe3a(1 2 3) // ev. (1*10 + 2*20 + 3*30) ev. 140
pe3a(1 1 1 1) // ev. (10 + 20 + 30) ev. 60


Addendum

Milestones in the history of partial evaluation


Applications of partial evaluation
Advanced applications
Bibliography