4 ms·

I am happy that functions/subroutines were invented and in common use by programmers in the 1970’s, otherwise we would have had arguments that function calls wi

I am happy that functions/subroutines were invented and in common use by programmers in the 1970’s, otherwise we would have had arguments that function calls with their stack based semantics are confusing, and explicitly writing out what you want your code to do instead of hiding it behind a function call increases code clarity. There would have been a group of people who criticized Go’s lack of functions, but other people would have pointed out that functions are not strictly necessary and besides they will be added in version N+1 once we are sure about the best way to do functions.

foldr 7y ago
Subroutines themselves weren't the innovation. Everyone was already calling out to subroutines in their assembly code. The innovation was structured programming.
- fpoling 7y ago
  Stack-based subroutine calls associated with structured programming came quite after people started to use subroutines in the assembly or higher level programming. Fortran, for example, gained those in eighties. Prior that everything was statically allocated and recursive calls were not supported.
  - zozbot234 7y ago
    I'm not sure that "stack-based subroutine calls" are associated with structured programming. An activation stack is required to ensure reentrancy e.g. if a subroutine might be called from an ISR or a cooperatively-executing task, in addition to suppprting recursion.
    - srean 7y ago
      Could you give us an example of a pre-structured programming, high level language that supported the things that you talk about. PDPs had instruction support for cooperatively executing tasks but the return address was stored in a register, and was therefore limited to a depth of one. From what I know stack based subroutines really became common around Dijsktra's famous paper which really ought to have been called 'Use the Stack, Stupid" rather than GOTO considered harmful. I am more than willing to be corrected with citations to the contrary.
- wwright 7y ago
  And at the time, a lot of programmers did whine and moan about structured programming. The famous joke should be “there are two hard problems with computer programmers: whining, moaning, and off by one errors.”
bryanlarsen 7y ago
If you learned the difference between reentrant functions and non-reentrant subroutines the way I did you would never equate them again. Back in the early 80's when I was 14 or so I wanted to replace a slow bubble sort in a BASIC program of mine with something faster. I had a book that had a quicksort implementation in Pascal and I thought it would be straight-forward to translate it into BASIC. Of course the naive translation didn't work. Luckily the chapter before the quicksort in the book was all about recursion so I did figure out what was wrong. I also had enough experience with assembly language to be familiar with the concept of passing parameters on a stack. I just hadn't really internalized why someone would do that. In the end, I had to use an array to create a parameter stack to work around the lack of reentrant functions, but I did get it working, and it was a lot faster than the old bubble sort.
- ethelward 7y ago
  I don't understand what it has to do with reentrancy?
  - anewvillager 7y ago
    A (non-tail) recursive function actually needs a reentrant mechanism to implement the semantics of calling itself; this mechanism is a stack. Without recursive functions, we have a bounded call depth and thus don't actually need a growable stack; a fixed-size array suffices. We take for granted that function calls are always implemented with a stack, because that's how processors work today, but it could have been done differently. We could imagine an alternative timeline with much restricted functions and no implicit call stack. And indeed, tail recursive functions are usually implemented with tail call elimination, in which the caller reuses the stack frame of the callee; function call becomes a simple goto, which transforms recursion into loop iteration. If we didn't have an implicit stack we could still have tail recursive functions (and a bounded number of non-tail calls), and manage other recursion cases with explicit stacks. See for example pratt parsing https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra... which uses the implicit call stack, and contrast with Dijkstra's shunting yard algorithm https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.... which is the same thing but with an explicit stack. If we didn't have a call stack, we could always program in Dijkstra's style and be none the wiser.
JadeNB 7y ago
MJD speculated on much the same thing: https://blog.plover.com/prog/design-patterns.html https://blog.plover.com/prog/design-patterns.html .

foldr 7y ago

Subroutines themselves weren't the innovation. Everyone was already calling out to subroutines in their assembly code. The innovation was structured programming.

fpoling 7y ago
Stack-based subroutine calls associated with structured programming came quite after people started to use subroutines in the assembly or higher level programming. Fortran, for example, gained those in eighties. Prior that everything was statically allocated and recursive calls were not supported.
- zozbot234 7y ago
  I'm not sure that "stack-based subroutine calls" are associated with structured programming. An activation stack is required to ensure reentrancy e.g. if a subroutine might be called from an ISR or a cooperatively-executing task, in addition to suppprting recursion.
  - srean 7y ago
    Could you give us an example of a pre-structured programming, high level language that supported the things that you talk about. PDPs had instruction support for cooperatively executing tasks but the return address was stored in a register, and was therefore limited to a depth of one. From what I know stack based subroutines really became common around Dijsktra's famous paper which really ought to have been called 'Use the Stack, Stupid" rather than GOTO considered harmful. I am more than willing to be corrected with citations to the contrary.
wwright 7y ago
And at the time, a lot of programmers did whine and moan about structured programming. The famous joke should be “there are two hard problems with computer programmers: whining, moaning, and off by one errors.”

bryanlarsen 7y ago

If you learned the difference between reentrant functions and non-reentrant subroutines the way I did you would never equate them again. Back in the early 80's when I was 14 or so I wanted to replace a slow bubble sort in a BASIC program of mine with something faster. I had a book that had a quicksort implementation in Pascal and I thought it would be straight-forward to translate it into BASIC. Of course the naive translation didn't work. Luckily the chapter before the quicksort in the book was all about recursion so I did figure out what was wrong. I also had enough experience with assembly language to be familiar with the concept of passing parameters on a stack. I just hadn't really internalized why someone would do that. In the end, I had to use an array to create a parameter stack to work around the lack of reentrant functions, but I did get it working, and it was a lot faster than the old bubble sort.

ethelward 7y ago
I don't understand what it has to do with reentrancy?
- anewvillager 7y ago
  A (non-tail) recursive function actually needs a reentrant mechanism to implement the semantics of calling itself; this mechanism is a stack. Without recursive functions, we have a bounded call depth and thus don't actually need a growable stack; a fixed-size array suffices. We take for granted that function calls are always implemented with a stack, because that's how processors work today, but it could have been done differently. We could imagine an alternative timeline with much restricted functions and no implicit call stack. And indeed, tail recursive functions are usually implemented with tail call elimination, in which the caller reuses the stack frame of the callee; function call becomes a simple goto, which transforms recursion into loop iteration. If we didn't have an implicit stack we could still have tail recursive functions (and a bounded number of non-tail calls), and manage other recursion cases with explicit stacks. See for example pratt parsing https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra... which uses the implicit call stack, and contrast with Dijkstra's shunting yard algorithm https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.... which is the same thing but with an explicit stack. If we didn't have a call stack, we could always program in Dijkstra's style and be none the wiser.

JadeNB 7y ago

MJD speculated on much the same thing: https://blog.plover.com/prog/design-patterns.html https://blog.plover.com/prog/design-patterns.html .