ITT: Write correct algorithms with comically bad in as few lines of code as possible.
for (int i = 0 ; i < MAXN ; i++) {
for (int j = 0 ; j < MAXN ; j++) {
if ( a[i] > a[j] ) {
swap(a[i], a[j]);
}
}
}
function comicallyBad(int) {
/*'REM This has comically bad*/
return;
}
>>55421302
>ITT: Write correct algorithms with comically bad in as few lines of code as possible.
AKA every recursive program ever
>>55421579
This desu senpai
>>55421302template<typename ForwardIterator>
void permutation_sort(ForwardIterator begin, ForwardIterator end)
{
while (std::next_permutation(begin, end))
{
// -- this block intentionally left empty by the drunken programmer --
}
}
>>55421579
Lel.
Although while all recursive programs might be comically bad with minimal LOC, I would not say all comically bad minimal LOC algorithms are recursive.
>>55421604
What a discusting language.
>>55421302
Just look at any existing python code
>>55421615
How has the choice of algorithm got anything to do with the chosen language?
>>55421579
This is what code monkeys actually believe.
>>55421302while not isInOrder(deck):
shuffle(deck)
>>55421655
Recursion has no place in production code.
>>55421676
y tho. it's the best shit ever
>>55421655
Recursive code gave me cancer
>>55421688
i honestly dont understand, why dont you like it? it makes life so much easier
>>55421687
ex:
>http://www.infoworld.com/article/3055885/microsoft-windows/its-time-for-microsoft-to-fix-the-windows-7-update-slowdowns.html
>Their supersedence function is un-optimized, now that we have more supersedence than in the past (see KB3035583 & KB2952664, no SP2) this poorly optimized function is causing havoc.
>Called recursively, 20+ layers deep:
>They called this function about 3,270,000 times during the 2 hour check for updates. Microsoft says "Only call this once, it won't change between boots", Microsoft calls it 3.27 MILLION times. Windows update is slow.
>>55421366
It's been awhile since I've programmed anything but isn't this effectively useless?
>>55421699
Computing the 40th Fibonacci number takes 331,160,281 recursive function calls.
>>55421715
Yes it is.
>ITT: Write correct algorithms with comically bad in as few lines of code as possible.
it is correct sorting algorithm, it is comically bad and is only 4 lines of code (You can skip the brackets)
>>55421676
That's true if the coders aren't very good, or the software they are working with is big/messy or they don't have enough time to thoroughly optimize. This is admitidally most of the time, but to unilaterally call recursive programming bad is absurd. Most 'pretty' algorithms are recursive.
>>55421676
There are problems which you can not solve without recirsion
>>55421728
memoization?
>>55421765
>CS majors actually believe this
>>55421765
any recursive statements can be written as loops, any loops can be written as recursive statements but why would you do that because you're overloading memory
>>55421747
True... but then the algorithm actually being implemented by the computer isn't a recursive algorithm.
>>55421728
Hey buddy, you should try to write a simple Merge-Sort/tower of hanoi script with just iteration, then think about how you could have wrote it with recursion without any difference in runtime.
>>55421801
This was meant to be a response to this >>55421768 not the one quoted.
>>55421801
That's as silly as saying a rock falling in a vacuum implement the algorithm speed = 9.8 meters per second per second, technically true, but it misses the point of computation.
>>55421784
Sure, write an Ackermann function without recursion
>>55421823
Oh. Never mind about this >>55421801 then
>>55421849
No it no at all. If you store prior values then it is no longer a true recursive algorithm.
>>55421883
>>55421858
>>55421849
>>55421823
>>55421801
I am so confused.
>>55421854
Could you imagine actually having to do that?
How fucking boring would that be
>>55421302f a 1 = a
f a n
| n % 2 == 0 = f (2 * a) (n / 2)
| otherwise = a + f a (f a (n - 1) + a - 1)
Guess what this does.
>>55421898
>Not having an argument
Better shitpost
>>55421972
It wasn't supposed to be an argument. I'm just saying it would be really fucking boring, there is no further point
>>55422004
It may be boring and pointless but it shows that there are algorithms that can't be solved without recursion
>>55422035
Ok, i'm not the person you were arguing with and I don't disagree.
>>55421798
is the year 1977? any computer/mobile device comes with >2GB of ram. I don't give a fuck if my stack's gonna be 1M big instead of 400K.
Tail recursion optimizations are also a thing and make recursive code as memory efficient as iterative, if you do it right
Doing things with recursive functions is pretty good for analysis, as you can tend to make the code match the structure of an inductive proof of its required properties...
That said, highly recursive code isn't fast.
>>55421929
multiplies
>>55421798
>you're overloading memory
Maybe if you don't know how to use recursion
>>55422035
any recursive algorithm can be written as an iterative algorithm making use of a stack...
cfr
https://www.reddit.com/r/compsci/comments/29lgtz/can_the_ackermann_function_be_rewritten_so_that/
>>55421798
>any recursive statements can be written as loops
Please write a loop that can traverse a tree to any arbitrary depth.
inb4 sleepsort
>>55421895
>recursion
>>55422121
>iterative algorithm making use of a stack
But how is that different from recursion? You're basically doing part of the compiler's job manually.
(define o+
(lambda (n m)
(if (zero? m) n
(o+ (add1 n) (sub1 m)))))
(define o-
(lambda (n m)
(if (zero? m) n
(o- (sub1 n) (sub1 m)))))
(define o*
(lambda (n m)
(if (zero? m) 0
(o+ n (o* n (sub1 m))))))
(define o>
(lambda (n m)
(cond ([zero? n] #f)
([zero? m] #t)
(else (o> (sub1 n) (sub1 m))))))
(define o<
(lambda (n m)
(cond ([zero? m] #f)
([zero? n] #t)
(else (o< (sub1 n) (sub1 m))))))
(define o=
(lambda (n m)
(nor (o> n m) (o< n m))))
some simple math functions built using primitives add1, sub1, and zero?. This sort of thing is fun to think about even if it is impractical.
>>55422399
(positive integer only)
>>55421854
Doing so requires more math than cs majors can handle :^)
>>55422436
>smiley with carat nose
kys
Applied Math major here, I guess you haven't learned anything about recursion.
>https://www.youtube.com/watch?v=Mv9NEXX1VHc
>https://www.youtube.com/watch?v=i7sm9dzFtEI
>>55422436
>mfw half my classmates don't know what the Ackermann function is
>graduating in a few months
>>55421302
With comically bad what?
>>55422492
most likely asymptotic time complexity, possibly also asymptotic space complexity
>>55422508
Hey OP here. It was meant to be time-complexity
>>55422079
Ideally, but the odd number case fucks it up. Came upon it while messing with discrete logarithms.
>>55422135q = new queue()
q.push(root)
while not q.empty():
node = q.pop()
do_thing(node)
for c in node.children():
q.push(c)
>>55421664
Laffd
>>55421728def fib(n, a=0, b=1):
if n == 0:
return a
else:
return fib(n - 1, b, a + b)
>>55422374
It stores that stack in heap, not in program's stack(which is only 8MB by default).
>>55421664
Not guaranteed to finish.
>>55422070
>>55423549
The average time will be n!
>>55423570
This is not really being calculated recursively though — the Haskell compiler is smart and is using memoization.
>>55423549
It will almost surely finish in finite time... and yes, I mean "almost surely" in the technical sense. Also, depending on who you perform the shuffling it may even be guaranteed depending on the RNG used for the shuffling.
is_negative(number):
return (str(number)[0])=='-'
>>55421812
tower of hanoi is actually incredibly easy to do iterative
>>55421579
>>55421676
>>55421801
>>55421784
>>55421898
You all are retarded. I'd like to remind you that iteration (as in while (cond), and successfully in for (int i=0;i<n;i++) which is syntactical sugar to a while call) is simply a concise way to write a loop, which in assembly is expressed via goto jump. It is OK for some operations, since it may result more expressive (loop through a collection/list/array/other shit), but not for some others. It should have place only in imperative programming (C, C++, Java, other pajeet langs), since the entire paradigm is based on telling the compiler HOW to do shit, not WHAT.
Recursion, OTOH, is another kind of abstraction over conditional goto jumps, and is harder to implement - but surely is more powerful, since it allows to express more concepts. Should be used in declarative languages (SQL, every functional language ever, logical programming), since it tells the compiler WHAT to do, not HOW.
The point is - everything depends on the compiler/interpreter your language is using. And if it's biased towards one paradigm instead of another - use that one. You'll be fighting a language while trying to write iterative loops in lisp or recursion in C.
>>55421302public int getnumber(){
Return getnumber();}
>>55424298
In this comment:
>call everyone retarded.
>make some irrelevant point about for loops.
>state some obvious shit that isn't relevant to the discussion about recursion.
>call people pajeets.
>shill imperative languages for muh functional paradigm
>Repeat irrelevant point.
>finish with another obvious point but at least relevant point
Also learn to fucking paragraph.
>>55421579
Neo-/g/ everyone
>>55421712
This is like saying that cars are bad because a trained monkey at microsoft once took a bicycle and crashed it into a car.
>>55424423
Can we please stop with the shitty analogies. I agree with the sentiment but was that really the best analogy you could come up with?
>>55421854
I did so in assembly for my programming intro class..
>>55423027
fucking REKT
>>55424443
managed to find the code#include "asm_regnames.h"
.data
prompt: .asciiz "Input n, m:\n"
.text
.globl entry
entry:
addiu sp, sp, -4
sw ra, 0(sp)
la a0,prompt
jal writestring
jal readdec // n = readdec()
move t0, v0
jal readdec // m = readdec()
move a0, t0
move a1, v0
jal ackermann
move a0, v0
jal writedec
lw ra, 0(sp)
addiu sp, sp, 4
jr ra
ackermann:
beqz a0, n0 // if (n==0) { goto n0 }
beqz a1, m0 // if (m==0) { goto m0 )
addiu sp, sp, -8 // int tmp, ra
sw a0, 4(sp) // tmp = n
sw ra, 0(sp) // ra = $ra
addiu a1, a1, -1 // v0 = ackermann(n, m-1)
jal ackermann
lw a0, 4(sp) // return ackermann(tmp-1, v0)
addiu a0, a0, -1
move a1, v0
lw ra, 0(sp)
addiu sp, sp, 8
b ackermann
n0: addiu v0, a1, 1 // return m+1
jr ra
m0: addiu a0, a0, -1 // return ackermann(n-1, 1)
li a1, 1
b ackermann
>>55424441
I was trying to use a nonsensical analogy for a nonsensical statement. Given by your reaction, I assume I have succeeded in picking a nonsensical analogy but failed in conveying my intent.
>>55424458
2016 and firefox/4chan/whatever still can't handle tab characters, sad.#include "asm_regnames.h"
.data
prompt: .asciiz "Input n, m:\n"
.text
.globl entry
entry:
addiu sp, sp, -4
sw ra, 0(sp)
la a0,prompt
jal writestring
jal readdec // n = readdec()
move t0, v0
jal readdec // m = readdec()
move a0, t0
move a1, v0
jal ackermann
move a0, v0
jal writedec
lw ra, 0(sp)
addiu sp, sp, 4
jr ra
ackermann:
beqz a0, n0 // if (n==0) { goto n0 }
beqz a1, m0 // if (m==0) { goto m0 )
addiu sp, sp, -8 // int tmp, ra
sw a0, 4(sp) // tmp = n
sw ra, 0(sp) // ra = $ra
addiu a1, a1, -1 // v0 = ackermann(n, m-1)
jal ackermann
lw a0, 4(sp) // return ackermann(tmp-1, v0)
addiu a0, a0, -1
move a1, v0
lw ra, 0(sp)
addiu sp, sp, 8
b ackermann
n0: addiu v0, a1, 1 // return m+1
jr ra
m0: addiu a0, a0, -1 // return ackermann(n-1, 1)
li a1, 1
b ackermann
>>55424469
Okay, thank fuck haha!! I was like 'what in the fuck... this guy must be smoking some heavy doobies'.
>>55424485
But that's recursive.
>>55425522
He just wanted to show off that he knows mips32
>>55425522
please point out where in that code a recursive function call happens
>>55425565addiu sp, sp, -8 // int tmp, ra
sw a0, 4(sp) // tmp = n
sw ra, 0(sp) // ra = $ra
addiu a1, a1, -1 // v0 = ackermann(n, m-1)
jal ackermann
Right here, you grow the stack and you call ackermann again without having freed the stack.
>>55424485
hmu when you can do a real architecture like ARM64, kid
>>55425581
Even in the comments it's stating it's recursive
>>55421366
this is disgusting
I love it.
>>55425581
>using a stack automatically makes it recursion
Oh, you're one of those people who will twist the definitions of words far enough to win any semantic argument. But your argument is still invalid, and I'll tell you why:
There is no recursion in assembly since there is no concept of a function in assembly.
>>55425619
>you're one of those people who will twist the definitions of words
You're literally the one doing that.
>>55425619
The comment shows the assembly was conceptualized as functions.
By your logic, recursion doesn't exists at all in an executable program since it's all machine code without "the concept of a function"
>>55425604
>the comments to a piece of code define the piece of code
The comment is meant to help understand what the code does. In this case, the comments are written in a recursive manner because the recursive explanation is the easiest to understand.
Note how the actual code deviates from the comments. For example, it overwrites the registers and jumps directly into the target function instead of using a jal whereas the comments (if translated naively) would call a subfunction and then jr the result of this.
>>55425619
Oh my
>>55425619
nice b8
>>55425647
>By your logic, recursion doesn't exists at all in an executable program since it's all machine code without "the concept of a function"
Yes, this is a fully correct statement. Assembly has no concept of recursion, neither do many other machine languages.
Recursion is only a thing that exists in high-level languages which are sophisticated enough to have a concept of self-reference. But just because there exists SOME high-level language in which a recursive code is translated by SOME compiler into assembly X does not somehow magically make the assembly ‘X’ recursive itself.
Case in point: An imperative code could have resulted in the exact same assembly. In fact, assembly is pretty much *the* proof of why imperative and recursive are equivalent; since both imperative and recursive code have to be translated by the compiler into a sequence of labels and jumps - the only form of control flow that exists in assembly.
You could semantically decompile the assembly presented into an imperative program that only uses only labels, goto, a handful of variables and a single data structure that permits LIFO access. (i.e. some stack)
>>55425619
>>55424298
You do know that the simpler and more predictable a function call is, the more optimizations can be made by the compiler, right?
If the code is formulated in an obscure and unpredictable way for muh code aesthetics, the compiler cannot take advantage of instruction level parallelism.
It is much more than a GOTO m8.
>>55425694
>recursion doesn't exist
Nice, I guess that's what you'll tell your boss next time a car navigation program you wrote kills someone.
>sophisticated enough to have a concept of self-reference
But Assembly does have that.
See how the ackermann *FUNCTION* references itself though its label?
See how it uses the JAL instruction AND SAVES A REFERENCE TO ITSELF?
>>55425694
Can we have a CS degree meme thread going?
>>55425694
A worked example:
Both this imperative programf(int x, y) {
while (y != 0) {
x *= x;
y -= 1;
}
return x;
}
and this recursive programf x 0 = x
f x y = f (x*x) (y-1)
might be translated by their respective compilers into this assembly fragment:loop:
test B
jz end
imul A, A
dec B
j loop
end:
ret
So is this piece of assembly imperative or recursive?
>>55421302for (int i=0; i<=n; i++) {
int fizz, buzz;
for (fizz=i; fizz > 3; fizz-=3);
for (buzz=I; buzz > 5; buzz-=5);
if (fizz == 0 && buzz == 0) print("FizzBuzz");
else if (fizz == 0) print("Fizz");
else if (buzz == 0) print("Buzz");
else print(i);
}
>>55425775
imperative.
>>55425775
Bad example, loop should have been named f for clarity.
>>55425758
>Nice, I guess that's what you'll tell your boss next time a car navigation program you wrote kills someone.
If your program runs out of memory, you are fucked whether it was recursive or imperative.
>See how the ackermann *FUNCTION* references itself though its label?
Ackermann isn't a function, it's a label. I'm beginning to think you don't understand assembly in the slightest.
>>55425796
>Arbitrary answer
Okay, now justify it in a non-ambiguous way that doesn't contradict other examples.
>>55425805
Do you think programming came before the idea if recursion?
>>55425805
>If your program runs out of memory, you are fucked whether it was recursive or imperative.
It's your fault you wrote an unoptimizable recursive function in a limited-stack space embedded machine when you could have used a simple loop.
It's a label that conceptualize a function.
In >>55425775, would you say f is a label or a function? To me it's both. f is just a name in a symbol table. You'll say it's a function because you're using the langage semantics and not the implementation's semantics.
>>55425820
>Okay, now justify it in a non-ambiguous way that doesn't contradict other examples.
The assembly block doesn't save a reference to its caller on a stack.
>>55425874
>The assembly block doesn't save a reference to its caller on a stack.
Multiple times*.
>>55425843
No. Recursion as a concept predates programming, for example any sentence involving “this sentence” is recursive.
Recursion has also been studied formally in mathematics, since things like recursive proofs or recursive definitions can lead to big headaches and paradoxes - while simultaneously being useful (if not required) for completeness, e.g. in the form of induction axioms.
>>55425896
At least you aren't a complete fool
>>55425785
Woah that is some sorts of algebra there
>>55425874
>It's your fault you wrote an unoptimizable recursive function in a limited-stack space embedded machine when you could have used a simple loop.
If the recursive function was unoptimizable and features an unbounded stack, then the loop version would have needed to access an unbounded region of memory.
So I'm not exactly sure why you bring up this meaningless example as if it's somehow going to change a fundamental fact of computer science.
>It's a label that conceptualize a function.
The function is a higher-order concept that you are imposing on the assembly. Assembly is itself just a long stream of instructions, some of them with labels attached. There is no concept of a function in assembly except by convention.
In >>55425775, the f: is a label, and this label is (by convention) intended to be functionally equivalent to any number of conceptual functions with identical denotational semantics. The idea of a “function” in an assembly is a tool used for programmers, like design patterns in some higher-level languages. It's not a part of assembly itself.
Your argument is like trying to say “this atom is a car” because a car happens to contain this atom. Do you see where I'm coming from?
Assembly as an abstraction doesn't understand the concept of a function. It only arises from a convention. In fact, nothing in assembly requires you to follow convention when it comes to uses of the stack, for example. The stack being used for recursive calls is also just a convention. The way it's used (i.e. the calling conventions) are *also* just conventions. It's in the fucking name.
None of these “conventions” are legitimated in the language itself.
>>55425918
It may behoove you to understand that you are talking to somebody with decades of experience who probably knows a thing or two more about programming language theory and compiler design than the average /g/ shitposter.
>>55425989
>Your argument is like trying to say “this atom is a car” because a car happens to contain this atom. Do you see where I'm coming from?
No, your argument is like saying "Recursion doesn't exists because the ink you use to write your expressions has no understanding of mathematical concepts"
>>55426009
And somehow you don't know what recursion is
>>55425989
And if I try to reuse *your* analogy, my argument would be like saying "this group of atoms makes up a car", and you say "no, we can't say for sure until we see the "higher-order" blueprints that led to the creation of said object", or "no, a car is a high level concept of engineering, that is just a lump of atoms".
>>55425594
nothing personnel, kid, but ARM is for babies. x86 ftw, although im considering looking into MIPS, looks really promising.
>>55426170
>not SPARC/IBM mainframe assembly
one day you'll be as great as me kiddo
look into QEMU, it supports lots of architectures, I am coding on qemu-system-aarch64 (arm64) now. qemu-system-mips64el has better than native performance
>>55426018
That's a bad analogy because when you're reading a mathematical paper written in ink, you're operating on the abstraction level of the mathematical paper, not the ink.
But in >>55425989 I'm studying assembly on the abstraction level of assembly - not the higher-level language it was generated from.
>>55426042
On the contrary - somehow *you* don't understand the concept of turing equivalence even when demonstrated with a worked example. Maybe I need to construct a more general proof?
Any recursive function of this form:f x
| t x = j x
| otherwise = g x (f (h x))
...can be rewritten to the following imperative code:f(x) {
z = new List();
while (!t(x)) {
z.push(x);
x = h(x);
}
x = j(x);
while (!z.empty() {
x = g(z.pop(), x);
}
return x;
}
You can apply pretty much the same construction to every recursive algorithm in existence - the implicit stack is replaced by an explicit stack. (for example a malloced list).
A stack overflow in a recursive language is just another type of an out-of-memory exception.
>>55426209
>this guy
you just went full autism, bro.
at least i slam pussy every night.
>falling for the assembly meme
>2000 + Math.pow(4, 2);
>>55426209
>a more general proof
Or maybe a real proof Mr. decades of experience
>>55422399
me likey.
data ℕ : Set where
zero : ℕ
suc : (n : ℕ) → ℕ
_+_ : ℕ → ℕ → ℕ
zero + n = n
suc m + n = suc (m + n)
>>55426209
When you read assembly code, you have to operate on what the code is trying to convey, assembly isn't random garbage, a valid program is logically structured, for example functions (translated from higher level langages to assemble) all have when necessary a prologue to set up a stack frame and clean up at the end. You could see instructions as the words in this post, english as the target langage and functions as sentences. Words carry a part of meaning themselves, same as instructions, they serve a purpose. You can even take it down at a lower level and look at words, they're made of letters that convey little meaning, but still enough to be able to.
Disagreeing with the fact recursion (and functions) exist in assembly would be the same as denying a message can convey meaning.
>>55426308
Well, the real proof are already given by church and turing. See the church-turing thesis, and more importantly their work on proving that general recursive functions, lambda calculs and turing machines are all equivalent.
I was just trying to demonstrate the result to the /g/ audience in a more understandable manner.
>>55422399
>>55426350
Now do it in the type system! \o/
https://github.com/haasn/units/blob/master/src/Units/Internal/Types.hs
>>55426209
What? No one is arguing that recursive functions can't be rewritten. Your defending the asinine statement that "recursion does not exist in assembly because functions don't exist".
>>55426285
Different anon here
pussy won't win your argument
>>55426285
>at least I slam pussy
Babbies first girlfriend
>>55426352
>When you read assembly code, you have to operate on what the code is trying to convey, assembly isn't random garbage, a valid program is logically structured, for example functions (translated from higher level langages to assemble) all have when necessary a prologue to set up a stack frame and clean up at the end.
Okay then, please tell me where are the functions, stack frames and prologues in this snippet of real-world assembly. (Taken from my music player, for lack of a more imaginative example)==================== Asm code ====================
.text
.align 8
.long SYGJ_srt-(Vimus.Render.addLine_go_info)+32
.long 0
.quad 12884901911
.quad 0
.quad 158913789967
.globl Vimus.Render.addLine_go_info
.type Vimus.Render.addLine_go_info, @object
Vimus.Render.addLine_go_info:
_cZ6E:
leaq -32(%rbp),%rax
cmpq %r15,%rax
jb _cZ6F
_cZ6G:
movq $block_cYZ4_info,-24(%rbp)
movq %rdi,%rbx
movq %r14,-16(%rbp)
movq %rsi,-8(%rbp)
addq $-24,%rbp
testb $7,%bl
jne _cYZ4
_cYZ5:
jmp *(%rbx)
.text
.align 8
.long SYGJ_srt-(block_cYZ4_info)+32
.long 0
.quad 2
.quad 158913789984
block_cYZ4_info:
_cYZ4:
movq %rbx,%rax
andl $7,%eax
cmpq $2,%rax
jae _cZ6C
_cZ6D:
movl $a_rYxF_closure+2,%ebx
addq $24,%rbp
jmp *(%rbp)
.text
.align 8
.long SYGJ_srt-(block_cYZa_info)+32
.long 0
.quad 3
.quad 158913789984
block_cYZa_info:
_cYZa:
movq 16(%rbp),%rax
movq 24(%rbp),%rcx
movq 8(%rbp),%rdx
movq %rbx,%rsi
andl $7,%esi
cmpq $2,%rsi
jae _cZ6V
_cZ6W:
addq $128,%r12
cmpq 856(%r13),%r12
ja _cZ6O
>>55426209
>it's a haskellfag all along
Decades of experiences in academics, aka being a bit above NEET, I guess?
>>55426416
>functions
Vimus.Render.addLine_go_info
>stack frames and prologuesmovq $block_cYZ4_info,-24(%rbp)
movq %rdi,%rbx
movq %r14,-16(%rbp)
movq %rsi,-8(%rbp)
addq $-24,%rbp
And epiloguemovq 16(%rbp),%rax
movq 24(%rbp),%rcx
movq 8(%rbp),%rdx
movq %rbx,%rsi
>>55426285
>being proud of acquiring a woman
>2016
that's sad
>>55425619
>>55426285
>java
FUCKING PAJEET NORMIE! GO BACK TO YOUR SHITTING STREAT!
JUST KILL YOURSELF! IF YOU DONT' PROGRAM IN ASSEMBLY THEN YOU AREN'T A REAL PROGRAMMER!
GO BACK TO COLLEGE, YOU FAGGOT KID!
>>55426416
To perhaps my illustrate point in a manner that randomly quoting assembly will probably lose:
The assembly produced is a snippet of assembly produced by GHC, the Glasgow Haskell Compiler. If you're familiar with C and reading gcc assembly, this is probably entirely alien and nonsensical to you - and that's because it is.
GHC shits all over the C family's assembly conventions and pretty much does its own thing. (More specifically, it implements a spineless, tagless G-machine that uses the stack to push and pop continuations)
Not every compiled language is C, and not every compiler is gcc. Just because gcc happens to like inserting its stack frames and has its own particular mannerisms and calling conventions when implementing recursive functions does not mean that other compilers need to follow suit.
You are trying to argue that assembly snippets are meant to be interpreted in a particular way just because ONE language exists which is compiled in that way.
But your argument breaks down when, for example, looking at the output of GHC-produced assembly for Haskell programs.
>>55426448
But those do not correspond to C functions at all. What's being pushed and popped in these examples are continuations and closures. The “stack frame” is wholly alien to the GNU debugger, for example.
Also,
>Vimus.Render.addLine_go_info
This is not a function either. It's a symbol pointing to the info table, which is entirely different from something you could just “call” in a typical C fashion.
https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects#InfoTables
>>55421854
All recursive code is compiled to assembly, which is iterative.
I'll write a recursive Ackermann function and then let my compiler tackle your challenge.
>>55426519
So what you're saying basically is:
The concept of what a function looks like to GCC is completely different to GHC's concept?
No shit.
>>55423650
Wrong. GHC does not automatically memoize anything. The function is just fast enough to not cause problems.
>>55426580
Yes, exactly. I'm glad we can finally agree on something, maybe we're getting somewhere.
Now that we've established that GCC's idea of a function and GHC's idea of a function are totally different, and we know that both compile to assembly, then surely it isn't such a big leap of faith to claim that what a “function” looks like in assembly can be wildly different based on what compiler you used to compile it?
If what a “function” in assembly looks like wholly depends on the compiler, then that alone already indicates that the idea of a “function” in assembly is something that only depends on the compiler's semantics, and not the assembly itself.
Arguing that assembly itself has functions is a direct contradiction of this. It's simply meaningless unless you take “assembly” to mean “X compiler's generated assembly”, which I don't remember doing.
>>55426592
GHC *will* automatically rewrite closures, though, which is effectively the same as memoization for CAFs and other constant forms (such as the list in this example - but note that since it's running in GHCi it will just get bytecode evaluated at runtime either way)
>>55426519
>Uses Haskell
>Can't understand concepts like instructions representing functions
>Can't make logical arguments
Wew
>>55426623
>If what a “function” in assembly looks like wholly depends on the compiler, then that alone already indicates that the idea of a “function” in assembly is something that only depends on the compiler's semantics, and not the assembly itself.
L'alphabet ne permet pas de composer des phrases car le concept de "phrase" dépend de la sémantique du langage utilisé.
What you're saying:
"Assembly doesn't represent functions"
What I'm saying:
"You can't NOT represent functions without using assembly"
>>55426685
>L'alphabet ne permet pas de composer des phrases car le concept de "phrase" dépend de la sémantique du langage utilisé.
You're confusing the concept of “using” something and the concept of “being” something.
An atom can be used to build a car.
^- we both agree with this
An atom is a car.
^- we both agree that this is false
Assembly pattern X can be used to implement a function.
^- we both agree with this
Then why do you struggle so much with rejecting “Assembly pattern X *is* a function”?
Essentially, you're arguing that the alphabet is english because it can be used to write english - which is the same argument as arguing that a piece of assembly is recursive because it can be used to implement a recursive function.
>>55426749
I didn't use "use" in my sentence, but "compose" which is "being a part of".
>you're arguing that the alphabet is english because it can be used to write english
You said that because GCC and GHC had different ideas of what a function is, then it means that assembly can't compose a function.
Which is the same as saying that, as english and french have different concepts of sentence structure, when their alphabet (which's the same) can't be used to construct sentences.
>>55426792
>You said that because GCC and GHC had different ideas of what a function is, then it means that assembly can't compose a function.
[citation needed]
All I'm arguing is that assembly itself doesn't have a concept of function. You can compile a function into assembly, and you can treat a block of assembly as a function under convention, but that doesn't inherently *make* it a function itself.
>>55426749
>Then why do you struggle so much with rejecting “Assembly pattern X *is* a function”?
Wait, so we're agreeing that any slice of assembly code is indeed a function?
>>55426898
>Wait, so we're agreeing that any slice of assembly code is indeed a function?
This sentence makes no sense to me. Can you try rephrasing it?
What do you mean by “slice”? And what do you mean by “any”? Are you trying to suggest that every possible snippet of assembly is a function? If so, that's clearly nonsensical.
>>55426898
>>55426978
function is just a reference for an address in the .text region you retards its a meme and functions = labels in assembly
>>55426896
>[citation needed]
in >>55426623
>If what a “function” in assembly looks like wholly depends on the compiler, then that alone already indicates that the idea of a “function” in assembly is something that only depends on the compiler's semantics, and not the assembly itself
>and you can treat a block of assembly as a function under convention
A single instruction is enough to be a function.
So if an instruction IS a function, the assembly DOES understand the concept of a function at a certain level, that is different than what compilers do about a function.
Compilers use assembly "functions" to represent "higher-level" functions.
Compilers themselves are just functions, translators that translate the meaning of a piece of code in another piece of code in another langage that conveys the *same meaning*.
If your high level function is recursive, then it will be translated to an assembly code that will have THE SAME MEANING, and thus, conceptually, will be recursive, without even looking at the actual generated code, because the source code is what the representation is based upon.
Like saying my fibonnacci function isn't recursive because it's tail recursive and an optimization may remove the recursion.
>>55426978
>If so, that's clearly nonsensical
How so?
>>55427007
>functions = labels in assembly
So we agree, no need to call me a retard.
>>55427017
I am a third guy, I didn't mean to hurt your feelings bae *kisses*
>>55425619
>subroutines aren't functions
get a load of this guy
>>55421895
Recursion is basically having a function that calls itself with slightly different arguments until it gets the desired output.
A recursive algorithm is an algorithm that uses recursion and doesn't rely on external state.
It's kinda tricky initially, it it is actually a really cool way of doing things since it acts like a loop where you don't need to manage anything outside of it.
That said, the reason this doesn't make the stack explode is that languages that are good for this kind of thing have something called "tail call optimization", which makes each recursive call not act like another function call, but rather like a loop that begins at the function's beginning.
>>55428606
>Recursion is basically having a function that calls itself with slightly different arguments until it gets the desired output.
Small correction: A recursive *function* is what you described.
Recursion in general is a broader concept. For example, you could have a recursive data structure, a recursive argument, a recursive sentence or a recursive construction.
>>55428606
Recursion works especially well when you combine it with declarative programming and nonstrict semantics, which is what languages like Haskell do.
You can also eliminate the need to have a recursive call stack even in non-tail calls by using a transformation to closures.
>>55429353
>a transformation to closures.
s/closures/continuations/
>>55421579
Head recursion yes
Tail recursion is the shit
>>55423594
Only if you ignore the shuffle operation, else it'll be O(n * n!)
>>55429582
O(n * n!) is O(n!)
Same reason O(n + 3) is O(n)
>>55431173
>O(n * n!) is O(n!)
Let f(n) = n * n!. f is trivially O(n * n!).
Assuming O(n*n!) = O(n!), then f must also be O(n!), so there must exist some M and N such that M*n! ≥ n*n! for all n ≥ N.
Let n = max(M,N)+1. This is trivially ≥N, therefore M*n! ≥ n*n! would have to hold, which is true iff M ≥ n. But since n ≥ M+1, this is a logical contradiction.
Therefore, O(n*n!) and O(n!) are not the same thing. QED.
