/tech/ - Technology★

>>932067 (OP)

Absolutely impure.

>>932073

Recursion is just fragile iteration that often relies on assumptions about what a compiler will do. Don't do it.

>>932078

Every feature relies on assumptions about what the compiler will do. If your compiler does not support proper recursion that's retarded.

A fold is just the equivalent of summation notation. In other words it's an absurdly common idiom. If you're too dumb to understand it, then you're too dumb to understand a lot of things, and should stick to "coding" instead of telling others what to do.

HNNGGG PILE UP THOSE FUCKING STACK FRAMES AND OVERFLOW MY FUCKING BUFFER BABY! FUCK YEAH

>>932067 (OP)

Epic thread, but I think you got lost on your way to http://4chan.org/g/

>>932104

A left fold is tail call optimized.

>>932107

Doesn't change the fact that you're being an obscurantist fuck for job security. Don't worry, Pajeetsoft will figure out a way to generate and deobfuscate your 1337 h4xx0r tricks.

>>932111

>map inc [1 2 3 4]

oh shit thats so complicated!

>>932111

for-loop iteration is far more abstracted from the idea of summation than a fold is.

You're just a baby duck.

A loop can be added to the language on top of recursion. It's all the same for the machine, but the semantic intent is more clear for the programmer. Here is what Racket does:

(for ([i (in-range 10)])
  (display i))

This is just a macro which could be expanded into

(let loop ([i 0])
  (display i)
  (unless (= i 10)
    (loop (+1 i)))

The former is much easier for a human to read and reason about, but the latter makes use of what the language already offers instead of having to add yet another feature to the implementation. A language should offer both recursion and loops, but only implement on of them.

>>932158

Why the hell are you doing recursion directly instead of a fold

>>932158

This is a totally unfair comparison. All the work is being done by the "in-range" part not the for loop part. This is substantially more complicated than the second example. Allow similar constructs in the second one and it would be much simpler.

>>932158

(([()])())

(([])()(()(()))

In common lisp:

;; augmentative recursion
(defun acc (n)
  (cond ((= n 1) (list n))
	(T (cons n (acc (1- n))))))

;; regular tail recursion using optional keyword
(defun acc2 (n &optional list)
  (cond ((zerop n) list)
	(T (acc2 (1- n) (cons n list)))))

;; tail recursion using labels
(defun acc3 (n)
  (labels ((acc3h (n list)
		  (cond ((zerop n) list)
			(T (acc3h (1- n) (cons n list))))))
    (acc3h n nil)))

;; you can too use a helper function
(defun acc4 (n)
  (acc4h n nil))
(defun acc4h (n list)
  (cond ((zerop n) list)
	(T (acc4h (1- n) (cons n list)))))

Funny thing is that common lisp don't support recursion; even though SBCL support tail recursion by replacing it with a GOTO.

That's why people really dissaprove using recursion in common lisp. The loop function is anyway so god damn powerful, you'll never find any equivalent.

That's like format, that allows crazy twerks.

God I love lisp.

>>932107

Not in all languages, not with all compilers. Tail-call recursion is not defined in ANSI C, therefore not all C compilers will support it.

>>932067 (OP)

Recursion is literally just for loser math nerds who want to look smart.

There's literally no reason to use recursion today.

>>932188

But anon, what if every step of a problem reveals a subproblem that looks exactly the same as the original problem?

>>932192

Use a stack-loop combination :^)

>>932184

;;(()(((=)())(((())))));;((&)((())((()()))));;(()(((()((())(()())))))()));;(()())(()((())((()()))))

>>932163

You are right, I was just trying to point out the basic idea that a loop can be just syntactic sugar for recursion. This is a better example:

;; Using a do-loop
(do ([i 0 (add1 i)])
    ((= i 10) i)
  (display i))

;; Using recursion
(let loop ([i 0])
  (cond
    ((= i 10) i)
    (else (display i)
          (loop (add1 i)))))

The variable i serves as both a counter and an accumulator, but you could also have two separate variables.

>>932184

> loop

> function

>>932257

>> loop

>> function

Nigger, both of your loops are functions.

>>932097

>Every feature relies on assumptions about what the compiler will do.

Untrue. Assuming a compiler will take code that you designed to exhaust the stack & crash and do a tail-return optimization to turn it into code that doesn't crash is dangerous and shitty programming. Many languages don't require the compiler to do that optimization.

>>932278

>Untrue

Which part of what you said exactly makes that untrue

>>932257

You're right, I went fast here. That's a macro. I actually thought it was a special function.

>>932306

Sure if you think all lambda calculus and brainfuck are the same thing

>>932276

see >>932303

>>932278

>>932187

Anybody who is explicitly opting for recursion and takes pains to write it in a TCO style (often involves an extra variable) is already aware of what their compiler is capable of; they wouldn't be doing it otherwise.

>>932283

Are you retarded? There's a big difference between doing something the language guarantees will work and doing something only specific compilers guarantee will work.

>>932349

It's bad form. It's like designing your code to only work with GNU extensions that will only work on GCC. Don't tie code to a specific compiler.

>>932359

It isn't a 'specific compiler'. It's 'any compiler for this language will do'.

Anyway, with ATS you can have all the recursion you want and still use any C compiler. And you avoid a little bit of overhead vs. using a HOF.

>>932184

You can add recursive forms to CL though. Read Let Over Lambda.

>>932303

To be fair, macros are "special functions" of sorts. There is special forms (built right into the language), functions (only regular ones) and macros (get expanded into s-expressions which themselves are written in terms of special forms, functions and macros).

>>932359

If the language standard requires TCO then it's not bad form. If a compile does not provide TCO then it's simply a bug in the compiler and the compiler is not standard-compliant.

For instance, Common Lisp does not require TCO, so it is advisable to use loop instead of recursion (the compiler may provide TCO and it could implement loops as recursion, but that is not guaranteed by the standard). On the other hand, Scheme does require TCO, so there is nothing wrong with using recursion.

>>932368

>the compiler may provide TCO

All the major implementations, both commercial and noncommercial, support TCO.

>>932359

Most people iterate recursively in languages where the standard guarantees TCO rather than a single compiler.

I would agree that needless recursion probably isn't a good idea for portable C, but it's a good thing I'm not a computer nigger who has to worry about that.

>>932367

I'll, thanks.

>>932078

...assumptions that are spelled out by every reasonable language specification.

>>932187

IIRC it is defined in newer revisions of ISO C though, which is what every reasonable compiler targets these days.

>>932278

>Many languages don't require the compiler to do that optimization.

Fuck them with GRIDS-laced barbed wire then. Use a properly defined language.

>>932391

>Use a properly defined language.

How about just not writing shitty code?

Tail call optimization is not required by Common Lisp. If you depend on tail call optimization your lisp code is not portable.

It's not required by C.

It's not required by C++, not even for templates (did you know there's a recursion limit?).

It's not required by Rust although they've been arguing about that for 4 years ( https://github.com/rust-lang/rfcs/issues/271 ).

It's required by Javascript but as only one browser supports it (lol safari) it's defacto not required.

It's not required by Java.

Stop writing tail recursive functions! It's a shitty, fragile way to write a function, will often be compiled in the worst way possible, and there's no way to cleanly handle running out of stack.

>>932420

>How about just not writing shitty code?

Who says its "shitty" if it's targeting a properly specified language with TCO? I suggest you stick to javascript, don't worry yourself with these concerns.

>>932473

>Who says its "shitty" if it's targeting a properly specified language with TCO?

I'm eagerly awaiting the language you have in mind that has guaranteed TCO in the spec and in practice. I just showed you this isn't the case for C, C++, Java, Rust, Lisp, or Javascript. What useless meme language will you recommend I use, I am on the edge of my seat!

>>932500

Scheme, Erlang, ML, ATS.

Literally every single language where people write recursive functions *instead* of using iterative constructs. Scheme is trash and ATS is weak to the criticism, but Erlang and OCaml are completely serious languages and you should consider using them.

>recursing

like, just iterate. you're not even being clever at this point

>>932391

>IIRC it is defined in newer revisions of ISO C though

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf

Pages 99 and 100, no mention of tail call optimization.

if it makes my stuff faster you need shut the fuck up

>>932556

Recursion never makes anything faster. At most, it's optimized to be turned into iteration.

>>932557

It makes reading faster.

More importantly, it can guarantee referential transparency. If you have a proven-to-work function that's ironed out into a for-loop by the compiler, it's a win/win.

>>932557

How do you recursively iterate something like a JSON object with iteration only?

I thought this essentially depended upon recursion? I can't see how else this would be achievable.

>>932578

>I can't see how else this would be achievable.

If you absolutely cannot use recursion, with a stack, of course, although I wouldn't recommend it. How do you think recursion works?

>>932585

Sounds like iteration is really just bad recursion

>>932587

You can implement either with either, "bad" or "good" doesn't make sense here.

>>932594

You can implement c / scheme / haskell / java in brainfuck. that does not make brainfuck good. things are not equal.

>>932374

That may be, but the standard does not promise it. I know that it's true for any implementation worth a shit, but still. It's in the realm of "undefined behaviour".

>>932860

Sounds like a shit standard to me anon.

>>932306

Just because a function is recursive doesn't mean it's tail-recursive.

>>932957

You can make recursive functions that aren't tail recursive iterative by using a stack.

>>932078

>recursion is a subset of iteration

iteration is a special case of recursion (primitive recursive).

<muh elegant recursion

Inefficient. Use dynamic programming.

<muh tail calls

A weak and limited excuse. Just use dynamic programming.

>>932192

>what if every step of a problem reveals a subproblem that looks exactly the same as the original problem?

Start at the bottom and work your way up; i.e. use dynamic programming.

>>933524

Recursion is a pretty big tool in doing dynamic programming.

>>932578

Look at a JSON parser. They don't use recursion, they use a token stack (on the heap). Recursion isn't used much in real world code because it doesn't work. Thread stacks are usually around 1-2MiB which is quite small and as a library you have to work with the stack size you've been given, and assume that the caller might already have used a lot of it. And that 1-2MiB goes fast when you're storing a lot of bloat like return pointers, base pointers, saved registers, local variables, etc. per recursion rather than just the information you needed.

Acknowledging recursion is stupid isn't a new thing in CS. Yacc used a token stack in the 1970s.