Ask HN: How does the return statement of a function work? | Hacker News Reader

Ask HN: How does the return statement of a function work?

8 pointsnoob_eng20 comments

Suppose for a function written in Python:

def func(param):

    a = [1, 2, 3, 4]
    n = len(a)

    for i in range(n):

        a[i] = a[i] + param

    return a

We know that by lexical scoping rules the variable 'a' (which here is a list) is available only to the function body. Once the function call has completed execution, it no longer exists in memory. Then, how can we return the variable 'a'? How does return hold on to a local variable of the function and pass it on to whatever called the function?

I know this is not an anomaly. I just don't know how or why it works. Maybe, I am missing some very important concept. I want to learn. Please explain of point me to resources where I can get rid of my confusions of similar sort.

View on HN

I believe this class: https://www.cs.cmu.edu/~213/

With this textbook: https://csapp.cs.cmu.edu/

Is the gold standard of education for the question you are asking.

There is probably a class on compilers if you thirst for even more depth.

I suppose it's important to mention that your selection of python matters a lot because the language itself is very meaningful to the behavior you want to understand.

Can you explain what malloc is and why it is needed in C? Do you know what %rip is? If you understand those concepts, then the question you are asking is very different than the question you are asking if you don't.

If you understand those concepts you are asking: "How does python work?"

If you do not understand those concepts you are asking: "How does memory management work?"

https://www.nand2tetris.org/

Might also interest you.

Thanks for the suggestion. Btw, which compiler class are you talking about?

I don't think any particular college has set the standard for compiler education.

Maybe one of these: https://www.seas.upenn.edu/~cis3410/current/schedule.html https://www.cs.princeton.edu/courses/archive/spring20/cos320... https://online.stanford.edu/courses/soe-ycscs1-compilers

I think the dragon book is well respected: https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...

This one might be good too: https://www.elsevier.com/books/engineering-a-compiler/cooper...

Reddit comparison: https://www.reddit.com/r/Compilers/comments/pjn25h/how_does_...

In Python, variable names do not directly contain their values. Instead, in your memory (on "the heap") there are "boxes". You can visualize them like cardboard boxes that contain values. In Python, these boxes are called "objects".

Variable names merely point to these boxes. They can be bound to boxes (`a = 9999` -- here, evaluating 9999 creates a box) and unbound from boxes (`del a`). The boxes exist independently of the variable names -- at least until they are no longer bound to, at which point they may be "thrown out" (deallocated) by the garbage collector.

>> Interestingly, in CPython you can see the "address" of the box `a` is bound to by evaluating `id(a)`.

With this in mind, let's try the given example. In the first assignment `a = [1, 2, 3, 4]`, the right-hand side (RHS) is evaluated first. This creates a "box" in memory that contains the list (see Note). So, visualize that the RHS evaluates to this newly created "box" in memory. Then the name `a` is bound to it (alternatively, "points"/"refers" to it).

When we `return a`, first `a` is evaluated. It is evaluated to be the "box" in memory. Just for comparison, suppose we instead `return 9999`. Similarly here, 9999 evaluates to a newly-created "box" (which contains the int value 9999).

So now let's call the function `result = func(5)`. First, the RHS is evaluated to be the "box" referred to in the return statement. Finally, the variable `result` is bound to that box. This is actually how all assignments work -- the RHS is evaluated to a box, and the variable name is bound to the box!

>> So if we evaluate `b = a`, then both variable names end up pointing to the box referred to by `a`. You can verify this easily: `id(a) == id(b)`.

(Note) Technically, a list is represented by one box. However, each element also requires at least one additional box. (In coding-speak we say a list is a "collection" of objects.)

Fantastic explanation. My doubt was half cleared by skrishnamurthi. You cleared it entirely. Thanks.

You are not at all alone in having this confusion. In fact, you are farther along than many learners in having gotten this far and being able to articulate your confusion so clearly.

The problem is with the statement `return a`. It should be read not as it's written, but rather as `return the value of a`. Once you realize that, much of your confusion will be resolved.

Over the past several years, my research group has studied and documented these kinds of programming misconceptions. We have abstracted them into a set of key issues we find people getting confused about in the basics of programming semantics that cut across languages like Python, JavaScript, OCaml, Racket, etc. — what I call "SMoL", the Standard Model of Languages.

My PhD student Kuang-Chen Lu has created an excellent SMoL Tutor that is a self-guided tool for learning these concepts clearly and addressing misconceptions. Please go to https://www.plai.org/ and pick either of the version 3.2.2 books, and in there go to page number 14/PDF page 15, "Teach Yourself SMoL". It provides links to all the tutors in order. Based on past student experience, you will need about 20 minutes per module. That's why they are broken down into several modules; so each one is relatively quick and you don't have to spend hours at one sitting.

We welcome feedback on the Tutor after people have done it.

> It should be read not as it's written, but rather as `return the value of a`

So values that are returned need not be primitive values like basic ints, floats, strings, etc? They can be complicated structure values also?

Got it, then!

> So values that are returned need not be primitive values like basic ints, floats, strings, etc? They can be complicated structure values also?

It depends on the language and the rules about what structures can hold.

For example, say your function doesn't return a value, but returns another function, and that function refers to variables in the first (this is called a "closure" or "lambda", the variable is "captured" or "closed over" by the returned function).

In some languages this is OK and normal to do, in others there's no guarantee that the original variable exists anymore and the behavior is "undefined", and in others it is forbidden.

The way that it is implemented also depends on the language.

This also depends on a language. If we talk about python, every structure (dict, array, object) and value (string, number) is an object, and variables can only reference these objects (internally by hw address into the “heap”, which is not visible in python). So when you return a python array, only its reference is returned. And that reference, among others possibly, prevents an actual object from being destroyed. Similar in js, perl, ruby, vb, other safe languages which never expose references (pointers).

But in e.g. C, structs and arrays can also be allocated right on stack, which may be, and often is, preferable performance-wise. So their variables are their values, without referencing, aka “automatic storage”. Like in, 700 byte-sized struct right in stack memory. You can return such struct in C, it will be copied or “moved” as described elsewhere itt. But you cannot return an automatic array, because it decays to a pointer to stack memory that gets reclaimed right after return, and accessing through such pointer is a programming error. To deal with this limitation you either return a pointer to a heap—allocated array, or accept an array as an argument instead, offloading the storage class responsibility to the caller. Same thing people do with structs really, except for very small ones, to avoid copying and related issues.

To simplify the understanding I will limit to mentioning just the "stack memory". When a function is called, memory on the stack is reserved for the function that is called. In addition to other elements on the stack, the stack contains the memory for the function parameters and local variables of that function(I am avoiding the mention of heap memory here for simplicity). So, the local variable `a` in your example is on the stack. When the function returns to the caller, the stack memory associated with that function is "freed"(freed is in quotes because the stack elements are not freed but "popped/removed" as in a stack data structure). So how does the value of `a` that was on the stack which is removed when the function returns passed to the calling function? Well, the value of `a` is just copied into the variable from the calling function that is assigned the function value that returns `a`. That is why, if you return a very large object from a function, it becomes a performance issue. But with some latest compilers this is resolved by performing return value optimisation, i.e instead of copying, the value is "moved". There are various techniques to achieve this and is a much broader topic.

You should read up on "Pass by Value" and "Pass by Reference" and stack vs heap. In Python everything is created on the heap which means it exists until it is garbage collected. When you return the list, you're actually passing back the memory address which is why it is accessible.

In a language like C which is Copy-by-value, if you are returning a struct, it will make a copy of the struct and pass that back to the calling code. It's actually a bit more complicated than that when you deal with pointers or structs that have pointer members, but it's all still essentially copy by value.

> Once the function call has completed execution, it no longer exists in memory.

This is the part that is wrong. If it's created on the heap it still exists. If it's created on the stack like a local variable in C, then it won't be after the function returns. In Go, it will figure out if the variable should be created on the stack or the heap.

Heap values which persist across function calls (and thus are not bound in a stack frame closure). They have to come with extra state of some kind to do reference counting, or you can't reclaim the space. This is the kind of reasons GC languages have runtime costs. The malloc/alloc/calloc functions in C can be adorned with similar costly state and associated functions for debug and runtime tracing, and GC. The costs are implied across creation, assignment, and function call passing to do this. If you never explicitly "free" then you may not realise behind the scenes some languages do this work for you. Sometimes it can be managed away by compiling where scopes can be predetermined. Not applicable in Python.

We know that by lexical scoping rules the variable 'a' (which here is a list) is available only to the function body. Once the function call has completed execution, it no longer exists in memory

The variable no longer exists, but the value does. It depends on a language/runtime, but it’s safe to think about it in terms of “roots” which are non-collectible. A stack (up to the tip) or a special register is one of the roots. Globals table/object is also a root.

When you pin a value (not a variable) into a root, e.g. by putting it on stack (as `return x` does) or by setting it into a global, you prevent it from being destroyed.

Also, this question better fits stackoverflow and likely already answered there, in much more detail than HN could do.

“(…) this question better fits stackoverflow and likely already answered there, in much more detail than HN could do.”

By now we have an answer that explains CPython’s assembly, so I think we’re on par. Considering the amount of articles on HN related to business, culture, history, etc, IMHO it can’t hurt with some programming questions every now and then.

No, I think it’s perfectly fine to ask. I was talking from a viewpoint of chances to get an answer. Some threads here just sink too quickly, while SO specializes in being Q&A-purposed, at least in my experience there.

I think 'dang made some changes a while ago that makes Ask HN posts stay longer on the Ask page.

You may be interested to contrast how it works in python with C. If you have something like

  int * bar() {
    int d[2] = {1,2};
    return d;}

When you compile with gcc you get

  foo.c: In function ‘bar’:
  foo.c:4:8: warning: function returns address of local  variable [-Wreturn-local-addr]

This is the behavior it seems like you were expecting, where the array is stored on the stack and so a pointer is invalid once the function ends.

In short it’s called a call stack - returned value (not the variable) is what is left of the function for the “outer” function.

And because finished function is removed from stack - all its variables are gone with it.

To expand on blindriver's response, the standard C-based implementation of Python ("CPython") uses a stack-based assembly language for what's called the "Python virtual machine".

In the PVM, objects on the stack are owned by the stack. The implementation carefully ensures that the reference count of those stack-owned objects is correct. That's how the return object is not freed when the local context finishes - the stack owns it.

You can look at the CPython assembly language with the "dis" module:

    def func(a, b):
        return a + b

  >>> from t import  *
  >>> dis.dis(func)
    2           0 LOAD_FAST                0 (a)
                2 LOAD_FAST                1 (b)
                4 BINARY_ADD
                6 RETURN_VALUE

The "LOAD_FAST" tells the PVM to get the value of the "a" local variable and put it on the stack. More specifically, we can look at the implementation of "LOAD_FAST" at https://github.com/python/cpython/blob/main/Python/generated... (which has is derived from https://github.com/python/cpython/blob/main/Python/bytecodes... )

        TARGET(LOAD_FAST_CHECK) {
            PyObject *value;
            #line 150 "Python/bytecodes.c"
            value = GETLOCAL(oparg);
            if (value == NULL) goto unbound_local_error;
            Py_INCREF(value);
            #line 41 "Python/generated_cases.c.h"
            STACK_GROW(1);
            stack_pointer[-1] = value;
            DISPATCH();
        }

This gets the local value from "a". If it doesn't exist, raise an UnboundLocalError. If it does exist, increase the reference count, increase the stack size by one, and put the new value on end of the stack. The DISPATCH() means to go to the next instruction.

The BINARY_ADD implementation has a number of specializations. If a and b are both integers, we can see the implementation at https://github.com/python/cpython/blob/main/Python/generated... :

        TARGET(BINARY_OP_ADD_INT) {
            PyObject *right = stack_pointer[-1];
            PyObject *left = stack_pointer[-2];
            PyObject *sum;
            #line 323 "Python/bytecodes.c"
            assert(cframe.use_tracing == 0);
            DEOPT_IF(!PyLong_CheckExact(left), BINARY_OP);
            DEOPT_IF(Py_TYPE(right) != Py_TYPE(left), BINARY_OP);
            STAT_INC(BINARY_OP, hit);
            sum = _PyLong_Add((PyLongObject *)left, (PyLongObject *)right);
            _Py_DECREF_SPECIALIZED(right, (destructor)PyObject_Free);
            _Py_DECREF_SPECIALIZED(left, (destructor)PyObject_Free);
            if (sum == NULL) goto pop_2_error;
            #line 456 "Python/generated_cases.c.h"
            STACK_SHRINK(1);
            stack_pointer[-1] = sum;
            next_instr += 1;
            DISPATCH();
        }

This takes the last two elements on the stack (at positions -1 and -2), does some checks that these really are integers, computes the sum, does a call to the internal macro _Py_DECREF_SPECIALIZED (at the top of the file), which decrements the reference count and frees the object if the refcount is 0.

        _Py_DECREF_STAT_INC(); \
        PyObject *op = _PyObject_CAST(arg); \
        if (--op->ob_refcnt == 0) { \
            destructor d = (destructor)(dealloc); \
            d(op); \
        }

It can do this because it knows the object is an integer, so it knows the correct deallocator for it.

The _PyLong_Add returns the sum as an object with a refcount of at least 1, so there's no need for an increment in the PVM implementation.

Since the last two objects have been deallocated, it removes those two from the stack, but it will place the new sum in the stack, giving an overall stack size shrink by one.

The sum is placed in the end of the stack, and execution goes on to the next instruction.

Reply on news.ycombinator.com