1
$\begingroup$

If I have n lines in a programming language like Python (globally or inside a function):

..
..
# from here
..
..
..
..
# to here
..
..

or

def example():
    ...
    ...
    # from here
    ...
    ...
    ...
    ...
    # to here
    ...
    ...

can I always transform it to a function if the for form s1, s2, s3 … = function(s1, s2, s3 ...), where:

  1. s1, s2, and s3 etc are the local/global variables created/updated after the n lines gets executed.
  2. function is almost the same code as the n lines above except it collects them and returns them?

As an example, in the below function:

def example():
    ...
    ...
    # from here
    ...
    ...
    a = 'c'
    b = 'd'
    ...
    ...
    # to here
    ...
    ...

I know I can do this:

def example():
    ...
    ...
    a, b = transform('a', 'b')
    ...
    ...

But my question is if I can extend this idea to any arbitrary n lines of code; effectively abstracting them as an input-output block?

According to me, the only thing that happens after any n lines is executed, is a state change (as far as the program is concerned) -- which can always be represented as a function with an input and output.

Am I missing something? Can someone please clarify?

$\endgroup$
  • 1
    $\begingroup$ Is there any differences between the function you wanted and a function which executes the same lines in example() and then returns all defined variables as a tuple? $\endgroup$ – nekketsuuu Sep 3 at 16:53
  • $\begingroup$ @nekketsuuu, Python supports passing and returning multiple values; so any approach is OK. My question is, can this be achieved theoretically -- are they completely equivalent -- where you can decide the choice based on readability? If that does not answer your question, I can elaborate with a better example. $\endgroup$ – Nishant Sep 3 at 16:58
4
$\begingroup$

The short answer is yes. The longer answer is no.

The short answer is yes: that's a fundamental computation operation and it's pretty much the definition of a function. The equivalence between

def f(x):
    do something with x
f(foo)

and

do something with foo

is in fact the definition of a function, or more precisely of function application. This is so fundamental that it's the basis of the lambda calculus. In the lambda calculus, there are just three syntactic constructs:

  • variables ($x$, $y$, …);
  • applying a function to an argument ($F X$ where $F$ is a function and $X$ is the argument);
  • lambda abstraction $\lambda x. M$ where $x$ is the parameter name and $M$ is the function body.

The lambda calculus gets its name from that $\lambda$ notation, and it's where Python got lambda. In the lambda calculus, there is a single computation rule, called beta conversion (beta reduction when done from left to right, beta expansion from right to left): $$ (\lambda x. M) N \equiv M[x \leftarrow N] $$ where $M[x \leftarrow N]$ means to replace $x$ by $N$ in $M$. (Details omitted because it would take a book chapter or two.) That single rule is enough to express all possible computations, in the sense that the lambda calculus is Turing-complete.

Beta conversion can be done in any language that has something that can reasonably called a function. But you need to take care of the details, and there are some language features that require additional effort or make it impossible in certain cases. Pretty much any language that isn't purely functional has restrictions on when beta expansion is correct.

In any language, the lines that you move to the new function must form a syntactic block. For example, if you have lines that are part of a multi-line construct like

while condition():
    instruction1()
    instruction2()

then you can move the loop out as a whole, but you can't move out while condition(): instruction1() and keep instruction2() in place.

One superficial but easily understood feature where beta conversion changes the behavior is introspection features. For example, if the language exposes a way to identify the current function or the function call stack trace, such as traceback.extract_stack() in Python, beta conversion changes that trace. If you put a call to traceback.extract_stack in a new auxiliary function, it's going to return something different. To make a beta-expansion that preserves the behavior, you'd need to modify calls to traceback.extract_stack to remove the new function from the trace. Note that this includes calls that may be deeply nested (if a function called inside the moved code calls a function that calls a function that … that calls traceback.extract_stack), so doing a fully behavior-preserving beta expansion turns into a global program transformation.

Another introspection feature of Python that breaks beta conversion is that it exposes local variables through locals(): locals()['x'] evaluates to the same value as x. If the code that you move calls locals(), you also need to pass the variables accessed through locals() as arguments to the new function and return their new values. So it isn't a purely syntactic transformation anymore.

A more interesting interaction is with flow control features. If the instructions that you put in the new function have self-contained flow, meaning that they're executed by starting at the top and either finishing at the bottom or raising an exception, then beta expansion or beta conversion doesn't change anything. It's ok if the code has loops and function calls inside it. But if the block of code that you move contains a non-local exit, i.e. an instruction that makes the execution jump outside that block of code such as return or break, you can't just move it. Likewise if the block contains a jump target (in imperative languages that have goto). It's possible to get around this with a local transformation: make the auxiliary function take one more argument which indicates the entry point (if there's a way to jump into the middle of the code), and one more return value which indicates where to exit to (if there's a way to jump out to a place other than the end of the code block). For example:

def outer_function(x):
    if x == 1: return 2       #
    else: x = x - 1           #
    return x

If you want to extract the two lines marked with # on the right into a function, you need to remember whether to return the 2 or continue on to return x.

def new_auxiliary_function(x):
    if x == 1: return "RETURN", 2
    else: x = x - 1
    return "FALLTHROUGH", x
def new_outer_function(x):
    tmp = new_auxiliary_function(x)          #
    if tmp[0] == "RETURN": return tmp[1]     #
    x = tmp[1]                               #
    return x

Your transformation also changes exactly when variables are modified. This can become an issue due to aliasing. Aliasing is not normally an issue in Python since there's no way for a variable to designate another variable, as opposed to designating the same object as another variable. I wouldn't swear that it's never an issue, but I can't think of a way to do it. So instead I'll give an example in C, where aliasing is common due to pointers.

int x = 3;
int *p = &x;
*p = 2;                    //
printf("%d\n", x);         //

This code prints 2, since the pointer p points to x and the line *p = 2 therefore sets x to 2. Now let's create an auxiliary function for the part marked with //. Since C can't create compound values on the fly, we need to define a structure type for the return values, but that's just a cosmetic change compared with Python.

typedef struct {
    int x;
    int *p;
} values;
values new_function(int x, int *p) {
    *p = 2;
    printf("%d\n", x);
}
…

int x = 3;
int *p = &x;
values tmp = new_function(x, p);
x = tmp.x;
p = tmp.p;

The line *p = 2 in new_function sets the outer variable x to 2, since that's where p points to. It does not change the variable x that is inside new_function. Therefore this program prints 3.

When a compiler performs a beta reduction, it's called inlining. This is a common optimization, which typically makes the program run faster at the expense of larger code size. Compilers much more rarely do beta expansions. It's a worthwhile optimization when the same block of code (or more generally similar-enough blocks) appears more than once and code size is more important than execution speed, but it's difficult to detect worthwhile cases. Both transformations have limitations as to exactly when they're correct.

$\endgroup$
  • $\begingroup$ A very-very detailed and interesting read. Thanks for relating it to the fundamental ideass of Turing Completion and Lambda Calculus; I had a vague feeling that this question is somewhat connected to these topics. $\endgroup$ – Nishant Sep 4 at 12:08
2
$\begingroup$

Maybe one issue is how to handle the early return.

Example:

# A function which returns a sum of 0, 1, ..., n.
def sum(n):
    # from here
    if n < 0:
        return 0
    answer = 0
    # to here
    for i in range(n+1):
        answer += i
    return answer

We want to transform the above three lines into one line:

answer = some_function(n)

But we can't directly return from sum() function just by calling some_function().

$\endgroup$
  • $\begingroup$ Upvoted. That is a good point to think about! return is something tricky; I didn't think about that. $\endgroup$ – Nishant Sep 4 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.