3 ms·

Yes, but I generate the arguments from converting the AST into the internal byte code, so arguments are just a LOAD_NAME, etc. There seems to be a problem when

by _RPM 10y ago

Yes, but I generate the arguments from converting the AST into the internal byte code, so arguments are just a LOAD_NAME, etc. There seems to be a problem when the arguments are coming from the currently executing function's stack (instead of the AST) As I restore the context from current executing function execute data to the previous execute data, and pop the stack once, and push it into the old context's stack as the return value. Also, just to be clear, I understand how recursion works as a user of a programming language, though implementing it is different than using it.

ericbb 10y ago
I definitely struggled to find a satisfying approach to recursion in my own current language project. What I'm doing right now is passing the closure value of the callee as a hidden first argument to every call. Nonrecursive functions just ignore that argument but recursive functions can always call themselves via that hidden argument. It doesn't allow you to support syntactic mutual recursion but it's easy to do and can be implemented without data modification at any level.
- chrisseaton 10y ago
  Do you not have any kind of registry of functions in your language where you can look up a function from a name and then call it? Then you don't need to pass in the current function to itself as it can look itself up in the registry, like any other function could (again, no special cases needed). There shouldn't be any need for recursive calls to be a special kind of call. They caller shouldn't need to know that it is calling itself (again, lack of special casing). This is how recursion works in languages like Java, Python, Ruby, C.
  - _RPM 10y ago
    My language has first class functions, as names are tied to values, and a value can be a function. With the opcode CALL_FUNCTION (in my VM), it does a searching of the hash table for the value.
  - ericbb 10y ago
    That's an excellent question! :) In my language, there is no special global scope for variables; every program is basically one giant (extended and sugared) lambda calculus expression. I do use lambda-lifting so that in the C code I generate, there is a C function in the global C namespace that is called to execute an object-language function but object-language functions also have closure environments so any kind of self-reference needs to include both the global C function and the closure environment for that particular closure. Note that my language does support modularity (breaking programs into multiple files, basically). However, the mechanism for referring to "packages" (stuff in other files) uses a separate name system. I agree that languages that bind all functions in a global scope can easily use that global scope to resolve recursive references. It's also easier when your language supports variable assignment and destructive updates of data structures. But my language doesn't support those things either. :) Addendum: By the way, you mentioned Java, Python, and Ruby, which are all object-oriented. Of course, the recursion among methods in those languages arises in a way that's very similar to passing a callee as a hidden argument. In OO languages, the hidden argument is "self" or "this"!
    - chrisseaton 10y ago
      > Of course, the recursion among methods in those languages arises in a way that's very similar to passing a callee as a hidden argument. In OO languages, the hidden argument is "self" or "this"! Self or this allows you to refer to the same object. You don't need to refer to the same object to wind up calling the same method. You could have two different objects that just have the same method. Maybe they share a class, or a mixin, or whatever. So I'm not sure self is relevant here.
      - ericbb 10y ago
        Yes, I think I see your point. If I may put it in my own words, I think you are talking about "dynamic recursive activation" throughout this thread. I don't mean to disagree with the point you are making! It's a valid point. However, I would like to emphasize that some languages have syntactic properties that complicate things a bit and I feel that a comment about how things "should" be really ought to be qualified by something like, "in a mainstream Java-like language". Consider the simply-typed lambda calculus, or Martin-Löf type theory. These languages don't allow general recursion but it's not because they are always poorly implemented!
ww520 10y ago
Recursion call should be exactly the same as an ordinate function call. The following is an example of asm code gen for function definition and recursive function call. Code gen to VM code should be similar. Hope it help. Assume the following AST. FN_DEF: { NAME: foo, PARAMS: [int4 param1, int4 param2] } LOCAL_VARS: [int4 var1, int4 var2, int4 var3] ... ASSIGN: { var1, CONST: 0x1 } ASSIGN: { var2, ADD:{ 0x2, param1 } } ... var3 = FN_CALL: { foo, ARGS: [var1, var2] } ... RETURN: { var3 } The generated code would be (all numbers are 10-based instead of hex for simplicity): fn_foo: push ebp ; save the caller's old frame pointer mov ebp, esp ; the new frame pointer to current stack ptr sub esp, 20 ; make new space in stack for params and locals ; EBP points to the base of the current frame ; the frame has 20 bytes in the stack ; var1 at [ebp-4] ; var2 at [ebp-8] ; var3 at [ebp-12] ; param1 at [ebp-16] ; param2 at [ebp-20] ... mov [ebp-4], 1 ; assign 0x1 to var1 mov [ebp-8], 2 ; assign 0x2 to var2 add [ebp-8], [ebp-16] ; add param1 to var2 ... push [ebp-4] ; push var1 for the function call push [ebp-8] ; push var2 for the function call call fn_foo ; call function foo at address fn_foo ; the current EIP is saved in stack ; the return value will be in EAX mov [ebp-12], eax ; save function return value to var3 ... mov eax, [ebp-12] ; set function return value from var3 mov esp, ebp ; pop frame pop ebp ; restore old EBP to previous frame ret ; return to the caller by popping the ; caller's address from stack into EIP. ; Execution will continue at the restored EIP address.

by _RPM 10y ago

ericbb 10y ago

I definitely struggled to find a satisfying approach to recursion in my own current language project. What I'm doing right now is passing the closure value of the callee as a hidden first argument to every call. Nonrecursive functions just ignore that argument but recursive functions can always call themselves via that hidden argument. It doesn't allow you to support syntactic mutual recursion but it's easy to do and can be implemented without data modification at any level.

chrisseaton 10y ago
Do you not have any kind of registry of functions in your language where you can look up a function from a name and then call it? Then you don't need to pass in the current function to itself as it can look itself up in the registry, like any other function could (again, no special cases needed). There shouldn't be any need for recursive calls to be a special kind of call. They caller shouldn't need to know that it is calling itself (again, lack of special casing). This is how recursion works in languages like Java, Python, Ruby, C.
- _RPM 10y ago
  My language has first class functions, as names are tied to values, and a value can be a function. With the opcode CALL_FUNCTION (in my VM), it does a searching of the hash table for the value.
- ericbb 10y ago
  That's an excellent question! :) In my language, there is no special global scope for variables; every program is basically one giant (extended and sugared) lambda calculus expression. I do use lambda-lifting so that in the C code I generate, there is a C function in the global C namespace that is called to execute an object-language function but object-language functions also have closure environments so any kind of self-reference needs to include both the global C function and the closure environment for that particular closure. Note that my language does support modularity (breaking programs into multiple files, basically). However, the mechanism for referring to "packages" (stuff in other files) uses a separate name system. I agree that languages that bind all functions in a global scope can easily use that global scope to resolve recursive references. It's also easier when your language supports variable assignment and destructive updates of data structures. But my language doesn't support those things either. :) Addendum: By the way, you mentioned Java, Python, and Ruby, which are all object-oriented. Of course, the recursion among methods in those languages arises in a way that's very similar to passing a callee as a hidden argument. In OO languages, the hidden argument is "self" or "this"!
  - chrisseaton 10y ago
    > Of course, the recursion among methods in those languages arises in a way that's very similar to passing a callee as a hidden argument. In OO languages, the hidden argument is "self" or "this"! Self or this allows you to refer to the same object. You don't need to refer to the same object to wind up calling the same method. You could have two different objects that just have the same method. Maybe they share a class, or a mixin, or whatever. So I'm not sure self is relevant here.
    - ericbb 10y ago
      Yes, I think I see your point. If I may put it in my own words, I think you are talking about "dynamic recursive activation" throughout this thread. I don't mean to disagree with the point you are making! It's a valid point. However, I would like to emphasize that some languages have syntactic properties that complicate things a bit and I feel that a comment about how things "should" be really ought to be qualified by something like, "in a mainstream Java-like language". Consider the simply-typed lambda calculus, or Martin-Löf type theory. These languages don't allow general recursion but it's not because they are always poorly implemented!

ww520 10y ago

Recursion call should be exactly the same as an ordinate function call. The following is an example of asm code gen for function definition and recursive function call. Code gen to VM code should be similar. Hope it help. Assume the following AST. FN_DEF: { NAME: foo, PARAMS: [int4 param1, int4 param2] } LOCAL_VARS: [int4 var1, int4 var2, int4 var3] ... ASSIGN: { var1, CONST: 0x1 } ASSIGN: { var2, ADD:{ 0x2, param1 } } ... var3 = FN_CALL: { foo, ARGS: [var1, var2] } ... RETURN: { var3 } The generated code would be (all numbers are 10-based instead of hex for simplicity): fn_foo: push ebp ; save the caller's old frame pointer mov ebp, esp ; the new frame pointer to current stack ptr sub esp, 20 ; make new space in stack for params and locals ; EBP points to the base of the current frame ; the frame has 20 bytes in the stack ; var1 at [ebp-4] ; var2 at [ebp-8] ; var3 at [ebp-12] ; param1 at [ebp-16] ; param2 at [ebp-20] ... mov [ebp-4], 1 ; assign 0x1 to var1 mov [ebp-8], 2 ; assign 0x2 to var2 add [ebp-8], [ebp-16] ; add param1 to var2 ... push [ebp-4] ; push var1 for the function call push [ebp-8] ; push var2 for the function call call fn_foo ; call function foo at address fn_foo ; the current EIP is saved in stack ; the return value will be in EAX mov [ebp-12], eax ; save function return value to var3 ... mov eax, [ebp-12] ; set function return value from var3 mov esp, ebp ; pop frame pop ebp ; restore old EBP to previous frame ret ; return to the caller by popping the ; caller's address from stack into EIP. ; Execution will continue at the restored EIP address.