Live data from Hacker News

Subroutine calls in the ancient world, before computers had stacks or heaps

devblogs.microsoft.com

211–220 of 241 posts

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#211

Earlier quoted context omitted.

using recursion involves functions as basic block of logic, that represent sub-parts of a domain That's what functions do. often creates finite set of self dependent functions This doesn't have anything to do with recursion. all you do is call and pass other functions, that will call each others You this doesn't have anything to do with recursion. If you consider `map` or `fold` these create opaque functional process…

> This doesn't have anything to do with recursion. recursion is compressing the domain so small it eats itself, crafting a small set of function is mirroring this, kinda like grammars > You this doesn't have anything to do with recursion. > I think you mean, they iterate for you. They don't use recursion. afaik map and fold were defined recursively ... foldl f z (x:xs) = foldl f (f z x) xs albeit accumulative recursi…

recursion is compressing the domain so small it eats itself, crafting a small set of function is mirroring this, kinda like grammars

I don't think this means anything. At best it's a completely abstract claim with nothing backing it up. It isn't "compressing a domain" to do iteration differently.

afaik map and fold were defined recursively

Fundamentally they are useful because the do the iteration for you. Internally it doesn't matter if the iteration is done in a roundabout way with recursion, they aren't about recursion and don't really have anything to do with them, just because some language decides to do iteration with recursion.

that was what i was pointing at, iterators are not encapsulated enough

You keep saying iterators, I keep saying iteration, but the only difference here is that the recursive version hides the accumulation in the arguments on the function. There isn't any more encapsulation, just a variable moved into the function argument. The brevity is from haskell's type deduction, not recursion.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#212
post #209

Earlier quoted context omitted.

How can you differentiate between them? One is a concept that means that something is defined in terms of itself, which why I linked you the definition. The other is a data structure where the first item in is the last item out. One is an abstract concept that isn't limited to computer, the other is an ordering. Why do you think these two completely different things have anything to do with each other? You just keep…

> One is a concept that means that something is defined in terms of itself, which why I linked you the definition. The other is a data structure where the first item in is the last item out. One is an abstract concept that isn't limited to computer, the other is an ordering. Well first of all, both are abstract concepts. In particular, in computer science stacks are considered to be an abstract data type with a push…

Well first of all, both are abstract concepts.

No they aren't. A stack is a specific type of data structure. Recursion isn't even specific to computers.

in computer science stacks are considered to be an abstract data type

I think you meant data structure and they aren't both concepts.

Of course, another way to refer to this kind of a structurally induced data type is to call it recursive.

You are making a linked list. A node in a traditional linked list has data and a pointer to the next node. This is what you are making here. Just because you over complicate a stack by using a linked list, it doesn't mean a 'stack' and 'recursion' are the same thing.

Fundamentally this is functional programming silver bullet syndrome. These things really have nothing to do with recursion, haskell is just putting a square peg in a round hole by using recursion for iteration and linked lists.

It's all fun and games until you get past trivial examples. Then pretending complex iteration and data structures are best done with recursion aren't so fun anymore and you want to control what is actually happening.

One example is this rust quicksort being 40x faster than haskell

https://github.com/LightAndLight/how-fast-does-it-quicksort

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#213
post #149

Earlier quoted context omitted.

emacs still does this IIUC. The beating heart of the emacs edit model is a "gap buffer" at the cursor. There's a neat compare-and-contrast someone did awhile back on the gap buffer approach vs. the other approach often taken for code IDEs ("ropes"). The tl;dr is that gap buffers are actually really performant for a lot of cases except for having to edit at a lot of randomly-chosen cursor points far apart from each ot…

> except for having to edit at a lot of randomly-chosen cursor points far apart from each other (but how often is that your use case?) I use Sublime, and pretty often I do a "Find All" for some term; then Multiselect (Cmd+L); then select from cursor (Shift+RightArrow); and then type something. Which is essentially "editing at a lot of randomly [or at least arbitrarily]-chosen cursor points." That, and IIRC Sublime ac…

I do the same thing in sublime. Doing it still feels like I have super powers even after years of doing it.

I’m sure there’s some magic key combo in emacs and/or vim to do it, too.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#214
> And if you were really fancy, you wrote a custom allocator that operated on that fixed-size buffer so people could “allocate” and “free” memory from the buffer.

That's still what current day allocators are.

Think of RAM as just a byte array in your favorite systems programming language. It's size is that fixed-size buffer (or, when RAM size is unknown due to hardware modularity, its size is the maximum possible and you pinky-promise not to look beyond the end).

The kernel sees all of the RAM as a fixed-size buffer, and an allocator manages what's free etc. These days, userspace processes see virtual addresses and you can think of them as all getting 2*64 bytes as their "fixed-size buffer". brk and mmap are really more hints to the kernel as to what part of the buffer you won't be needing.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#215
post #164

Earlier quoted context omitted.

wait what? you're right! 386 came 1985, 45 years later is 2030 now I feel old

Why the 386? You could do preemptive multitasking on a 286 or even an 8088.

without MMU you have to trust your tasks, but yes technically all you need is timed interrupts. so if you go the no mmu route, you could even list 6502 and z80, as in "I rarely do multithreading, but if I do I do it without MMU" ;-)

or at least have an MPU, which is what some microcontrollers have to protect multitasking.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#216

Earlier quoted context omitted.

> This doesn't have anything to do with recursion. recursion is compressing the domain so small it eats itself, crafting a small set of function is mirroring this, kinda like grammars > You this doesn't have anything to do with recursion. > I think you mean, they iterate for you. They don't use recursion. afaik map and fold were defined recursively ... foldl f z (x:xs) = foldl f (f z x) xs albeit accumulative recursi…

recursion is compressing the domain so small it eats itself, crafting a small set of function is mirroring this, kinda like grammars I don't think this means anything. At best it's a completely abstract claim with nothing backing it up. It isn't "compressing a domain" to do iteration differently. afaik map and fold were defined recursively Fundamentally they are useful because the do the iteration for you. Internally…

Grammars are not iteration concepts.

Map doesn't do iteration.

It's not about Haskell.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#217

Earlier quoted context omitted.

recursion is compressing the domain so small it eats itself, crafting a small set of function is mirroring this, kinda like grammars I don't think this means anything. At best it's a completely abstract claim with nothing backing it up. It isn't "compressing a domain" to do iteration differently. afaik map and fold were defined recursively Fundamentally they are useful because the do the iteration for you. Internally…

Grammars are not iteration concepts. Map doesn't do iteration. It's not about Haskell.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

https://www.geeksforgeeks.org/python-map-function/

The whole point of map is that it does the iteration for you and you pass it a function. Iteration is literally the reason it exists.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#218

I really liked the Art of Computer Programming with regards to this subject. While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures. The book also builds up to garbage collection and how to implements Lisp-lists. The kind of encyclopedic knowledge you'd expect from Knuth. ------- One of my favorites is how to have two Arrays dynamically ta…

>but at that point you might as well use Malloc and Realloc. IIRC, the first edition of the classic K&R C book, The C Programming Language, had an example of creating a memory allocator and using it.

It's not difficult to write a memory allocator, but there are some assumptions there which don't always hold true. For instance SmartCards (e.g. SIMs) use a language alleged to be Java, but without a garbage collector and with only one data type. Applications never terminate, so while you can allocate heap memory, you cannot free it and memory exhaustion is one way to brick the device. Since it is "Java" you don't have the low level control of C. Standard practice is to allocate some global variables once, and use them throughout the life of the device. Since another way to brick the device is by exhausting write cycles on the EEPROM on which these variables are stored, you are also allowed to allocate an array in the small amount of RAM. Ah, you might think - I can use that for an allocator! Nope. The array space is only allocated until the end of an event handler, and after that it holds undefined content.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#219
I don't feel like this is quite the right way to look at it. Computers don't have stacks and heaps, software has stacks and heaps. Of course, in recent times there are built-in CPU instructions that do memory management and whatnot, but that's not the point. Give a programmer a Turing-complete machine and enough time to play with it and, while elegance and efficiency will vary with the underlying architecture, they (on that machine) will have stacks, heaps, and any other computable thing they wanted.

I first learned to program on a calculator in a kneecapped version of BASIC which didn't support recursion, function calls, user defined variables (you got 'A' to 'Z' and that was all) or dynamic memory management (other than resizing 'matrices' and 'lists' iirc). I wanted to write Minesweeper on it and to do so I independently invented what I later found out were well know as depth first search and breadth first search, using just some loops and a list as a stack. (I was a kid and we didn't really have the internet yet. :P )

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#220

Earlier quoted context omitted.

Grammars are not iteration concepts. Map doesn't do iteration. It's not about Haskell.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... https://www.geeksforgeeks.org/python-map-function/ The whole point of map is that it does the iteration for you and you pass it a function. Iteration is literally the reason it exists.

map predates javascript and python by decades
Post reply on HN