5 ms·
Ask HN: How does the return statement of a function work?
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.
- blindriver 4y agoYou 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.
- ggm 4y agoHeap 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.
- eesmith 4y agoTo 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_cases.c.h#L34 https://github.com/python/cpython/blob/main/Python/generated... (which has is derived from https://github.com/python/cpython/blob/main/Python/bytecodes.c#L149 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_cases.c.h#L442 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.
- version_five 4y agoYou 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.
- wruza 4y agoWe 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.
- cpach 4y ago“(…) 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.
- wruza 4y agoNo, 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.
- cpach 4y agoI think 'dang made some changes a while ago that makes Ask HN posts stay longer on the Ask page.
- hayst4ck 4y agoI believe this class: https://www.cs.cmu.edu/~213/ https://www.cs.cmu.edu/~213/ With this textbook: https://csapp.cs.cmu.edu/ 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?"
- hayst4ck 4y agohttps://www.nand2tetris.org/ https://www.nand2tetris.org/ Might also interest you.
- noob_eng 4y agoThanks for the suggestion. Btw, which compiler class are you talking about?
- hayst4ck 4y agoI 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.seas.upenn.edu/~cis3410/current/schedule.html https://www.cs.princeton.edu/courses/archive/spring20/cos320/ https://www.cs.princeton.edu/courses/archive/spring20/cos320... https://online.stanford.edu/courses/soe-ycscs1-compilers https://online.stanford.edu/courses/soe-ycscs1-compilers I think the dragon book is well respected: https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq... This one might be good too: https://www.elsevier.com/books/engineering-a-compiler/cooper/978-0-12-815412-0 https://www.elsevier.com/books/engineering-a-compiler/cooper... Reddit comparison: https://www.reddit.com/r/Compilers/comments/pjn25h/how_does_engineering_a_compiler_by_keith_cooper/ https://www.reddit.com/r/Compilers/comments/pjn25h/how_does_...
- skrishnamurthi 4y agoYou 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/ 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.
- noob_eng 4y ago> 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!
- duped 4y ago> 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.
- aristofun 4y agoIn 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.
- _448 4y agoTo 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.
- psyklic 4y agoIn 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.)
- noob_eng 4y agoFantastic explanation. My doubt was half cleared by skrishnamurthi. You cleared it entirely. Thanks.