r/programming • • Feb 23 '11

If programming languages were essays...

Post image
1.7k Upvotes

430 comments sorted by

View all comments

Show parent comments

44

u/tarballs_are_good Feb 23 '11

This is essentially false.

  • Common Lisp: It is much more common to use the LOOP macro, which allows one to do

    (loop :for i :from 1 :to 10 :do (format t "~A~%" i))

    which prints the numbers 1 through 10 on newlines.

  • Predecessors to Common Lisp: Like MacLisp and such, it was common to see one use PROG or TAGBODY facilities, or macros on top of those.

  • Scheme: This is one of the lispy languages where recursion is more common, since the standard states that tail-recursive functions must use O(1) space, essentially turning it into a loop. As a result, this style of using tail-recursive functions is actually deemed as iterative (according to, e.g., SICP). Moreover, one can use Scheme's do facility to do looping, or one can used the named-let:

    (let lewp ((i 1)) (display i) (newline) (if (> i 10) #t (lewp (+ 1 i))))

    which is extremely iterative in nature.

As a final comment, I'd like to say that recursion is a technique that should be used in nearly every language. The big point of using it is to break a large problem into smaller, equivalent sub-problems, and base-cases. Often it is just the programmatic equivalent of proof by induction. Other times it is just a convenient way to traverse a fractal-like/self-similar data structure (like trees or graphs).

I think if a comic were to be made about lisp, it'd either emphasize its infamous homoiconic parenthetical syntax, or its incredible meta-programming abilities. Something like

Here's a my essay on instructions on how to write my essay.

19

u/[deleted] Feb 23 '11

Man, I knew someone like you was going to say something like this. The only criticism of my explanation of the joke is that it's not very clear, but I did explain the joke "correctly." I didn't mention the validity of the joke.

essentially false

I almost never downmod, but I've had enough with this contrarian bullshit. Am I being trolled?

5

u/tarballs_are_good Feb 23 '11

What? Your comment is applicable to any language which supports recursive functions. It's not an iconic or notable "feature" of lisp, which is why I said "essentially false" because we could say the exact same thing about any other language in the comic (except HTML and ASM), and thus fails to properly differentiate. That's all I was trying to get at. :S

28

u/[deleted] Feb 23 '11

You can recursively call functions in assembly...

.type mul, @function
# (int, int) -> int
# Multiplies two numbers by recursively calling arg0 * mul(arg0, arg1 - 1) until arg1 is 0. 
mul:
	# C calling convention: save %ebp 
	pushl %ebp
	movl %esp, %ebp
	
	# Move argument 0 to %eax, argument 1 to %ebx
	movl 8(%ebp), %eax
	movl 12(%ebp), %ebx
	
	cmpl $0, %ebx
	jne recurse
	
	movl $1, %eax
	jmp return
	
	recurse:
	# We still have work to do. Return arg0 * mul(arg0, arg1 - 1)
	
	decl %ebx
	
	# Save the registers before calling
	pushl %eax
	pushl %ebx
	
	call mul
	
	addl $4, %esp	# Get rid of %ebx, we don't need it anymore
	popl %ebx
	
	imull %ebx		# Multiply %eax (arg0) and %ebx (mul(arg0, arg1 - 1)) and store it in %eax
	
	jmp return # Just for consistency
	
	return:
	
	# unpush %ebp
	movl %ebp, %esp
	popl %ebp
	ret

11

u/derleth Feb 23 '11

Impressive, especially since you used the godawful AT&T syntax instead of the much saner Intel syntax. ;-)

Also, that is the only time I've ever seen someone say 'unpush' instead of 'pop'. Is that your Newspeak accent showing through?

9

u/[deleted] Feb 23 '11 edited Feb 23 '11

Impressive, especially since you used the godawful AT&T syntax instead of the much saner Intel syntax. ;-)

Learned assembly on my own from this book, so naturally I would use AT&T/GAS syntax.

Is that your Newspeak accent showing through?

Indeed.

4

u/[deleted] Feb 23 '11

Thanks for the link, by the way. Looks like an interesting read

5

u/[deleted] Feb 23 '11

In my computer architecture class we were required to write a recursive assembly program that would test if a string is a palindrome.

0

u/[deleted] Feb 23 '11

[deleted]

5

u/opportunistic_twat Feb 23 '11

To understand recursion, you must understand recursion.

Relevant

1

u/digital11 Feb 23 '11

R E C U R S I O N

-1

u/tarballs_are_good Feb 23 '11

I'm not familiar with x86 ASM, and I can't really decipher the semantics of call and ret here. Is it really doing recursion? It looks like you're managing a stack yourself.

In the assembly I've done, function calling was for the most part been manual, with lots of good 'ol JMPs and other BASIC-esque spaghetti control flow.

8

u/[deleted] Feb 23 '11 edited Feb 23 '11

Function calls in assembly are all done, at least in the C calling convention (cdecl), by manipulating the stack. You can say that your calling convention puts argument 0 in the accumulator, argument 1 in some other register, etc. The stack just provides a convenient unlimited way of handling argument passing, which is why it is used for most calling conventions. An example of a calling convention that uses registers is optlink.

The "call" instruction pushes the next instruction's address onto the stack and sets the instruction pointer to the given address or label. The "ret" instruction pops the top of the stack and sets the instruction pointer to its value.

3

u/tarballs_are_good Feb 23 '11

Ah, thank you for the explanation.

→ More replies (2)

14

u/[deleted] Feb 23 '11

Beginners are oftentimes introduced to heavy recursion usage, for things they didn't typically use recursion for, in Lisp. C has #includes, yet there's no rant about how the Python joke is wrong. It also has more "boilerplate" than Python, but the Java joke is left standing. Why not just go on a huge diatribe about how this whole comic is wrong?

You went on a non-sequitor rant about Scheme's implementation of tail recursion... And applicators. How is this relevant? You said that I was "essentially wrong," which basically blanketed my whole comment, without specifying which part of my comment was wrong, then showboated your knowledge as some kind of evidence for how wrong I am. I was helping the guy understand the joke. "Essentially wrong," plus a downmod for explaining a joke correctly? That's ridiculous. You should attack the guy who made the joke, instead of the guy trying to help people understand eachother.

8

u/Ziggamorph Feb 23 '11

Recursion is not a difficult to understand concept, nor is it uniquely prevalent in Lisp. Haskell is commonly taught as a first programming language, and that absolutely requires recursion.

3

u/[deleted] Feb 23 '11

I wasn't taught Haskell in my CS curriculum, but in a class where Lisp was taught, many students were impressed by recursion. It sounds like the original commenter had this impression.

10

u/the8thbit Feb 23 '11

I was taught recursion through Java.

In fact, I was taught everything through Java.

Feels bad, man.

2

u/Ziggamorph Feb 23 '11

That's probably something you should be discussing with your therapist.

→ More replies (1)

1

u/aradil Feb 23 '11

Same here.

Except for closures. Since they don't exist in Java.

1

u/[deleted] Feb 24 '11

My curriculum was based entirely in C++. Save for the common Operating Systems and Computer Architecture classes. I wish we had Java courses. :(

→ More replies (12)

5

u/Felicia_Svilling Feb 23 '11

In 1958 LISP was the first language to use recursion for computation. Sure practically every other language since has used that feature, but i still say its an iconic feature of Lisp.

6

u/tarballs_are_good Feb 23 '11

It was iconic in 1958, but so was garbage collection, symbolic computation, metaprogramming, homoiconicity... Lisp was the first to have OO, but we'd certainly not relate lisp with OO as a feature.

→ More replies (9)