January 2003

Comparing Partial Evaluation with Lazy Evaluation and Currying

Introduction

This document defines the differences between these three concepts in both the semantic and implementation realms.

Definitions

Currying

A second order function (C) that takes a function (f) of 2 parameters, together with a value, and returns a function (g) with 1 parameter.

C(f, x=x₀) = g, where g(y) = f(x₀, y)

Of course, the restricting the domain function to be of 2 parameters is contrived for simplicity. Any isomorphic mapping to this problem domain is also considered currying.

Lazy Evaluation

Lazy Evaluation is a composite of both Normal Order Evaluation (delaying evaluation until the results, if ever, are needed) and Sharing (caching precomputed results). Normal Order Evaluation involves keeping/making a data structure to represent the required evaluation instead of doing the calculation itself. Most times this datastructure is a continuation called a "thunk". Sharing is not of concern to us in this document.

Partial Evaluation

The act of defining a faster program, named the residual program, given an original program and a set of constraints on parameters.

Semantic Difference

Currying is a special form of Partial Evaluation: Currying can only remove whole parameters, and can not handle the case where only part of a single parameter is provided. The following example is a perfectly valid PE:

PE(f, x Integer) = g where g(x, y) = f(x, y) only if x Integer

PE can also be used to Curry, but will also do the work of optimization:

PE(f, x=x₀) = C(f, x=x₀) = g where g(y) = f(x₀, y)

The semantics of Lazy Evaluation can not be compared to the semantics of Partial Evaluation because the two are completely different with such obviously different purposes. There is the possibility that an investigation into the semantics of recursion and it's applicability to PE may reveal a relationship.

Implementation Difference

PE may use LE as an evaluation scheme, but since this is a hard problem, the opportunities are few. It is best to have recursive semantics suited for LE.

The naive implementation of Currying is actually a form of LE albeit without Sharing. The following example explicitly curries f() to make g(). Note the use of a global x0 has to be assigned before g() can be used.

static int x0 = x;public int g(int y){ return f(x0, y); }//g

A function that would create this curry in this way would in fact be making a continuation; a data structure representing the actions that should be taken if called. This is just like when LE makes a data structure to delay expensive operations (like compiling an optimized form of g).

Summary

In summary: