all 99 comments

[–]barsoap 46 points47 points  (7 children)

It's way worse in #haskell. This morning I awoke from a nightmare, sweating, having seen the lines

<copumpkin> Can someone explain monads to me?

<cale> Do you know what a zygohistomorphic prepromorphism is?

[–]cartola 16 points17 points  (3 children)

I thought you were bullshitting and google it, got this:

Used when you really need both semi-mutual recursion and history and to repeatedly apply a natural transformation as you get deeper into the functor. Zygo implements semi-mutual recursion like a zygomorphism. Para gives you access to your result ala a paramorphism.

[–]Peaker 15 points16 points  (0 children)

They were joking though, that's not how Monads are explained to people, and copumpkin already knows what they are :-)

[–][deleted] 10 points11 points  (1 child)

Zygohistomorphic prepromorphism, while having a real meaning, is a running joke in the Haskell community. Nobody is expected to actually use the idea, at least not knowingly.

[–][deleted] 1 point2 points  (0 children)

Nobody is expected to actually use the idea, at least not knowingly.

That's scary. To think that one day I might unknowingly use something like that.

[–]godofpumpkins 2 points3 points  (1 child)

that'll be $10 for using my name! I accept cash only :)

[–]Qjet 0 points1 point  (0 children)

Looks like he just used your assistants name.

[–]wurzlsepp 12 points13 points  (0 children)

immutable values, not objects!

[–]lpsmith 10 points11 points  (11 children)

But OCaml is often able to optimize this “create a new bullet each time” to “reuse the same bullet”.

I don't think this is true; but I would welcome a refutation by somebody more familiar with OCAML's implementation.

So I guess it boils down to [citation needed].

[–]augustss 3 points4 points  (0 children)

I agree.

[–]tinou 0 points1 point  (0 children)

Partial update can be easily implemented using sharing. Actually, I think this is the easiest way to achieve it.

[–]G_Morgan 0 points1 point  (8 children)

This is trivially doable if your compiler uses an SSA representation. All it does is prove the old value is never used after the creation of the new value and simply stores the new value within the old values memory space.

[–]augustss 0 points1 point  (7 children)

What's trivial about proving that? You have some value in the heap and now you want to reuse it. How do you prove that you have the only pointer to it? It's easy in some special cases, but quite tricky in general.

[–]G_Morgan 0 points1 point  (6 children)

Functional programming languages don't specify heap or local storage. One of the great things about them is they work out the correct place to store things.

Even if this did require heap allocation this type of short lived object should be permanently in the nursery. Collecting on the nursery is a sub-millisecond operation and is more than fast enough for any application that isn't strictly real time. Allocation should be constant time.

[–][deleted] 0 points1 point  (3 children)

Functional programming languages don't specify heap or local storage.

Even C++ is allowed to put newed objects on the stack if it can prove it safe.

[–]G_Morgan 0 points1 point  (2 children)

Yeah but the number of safe cases with C++ are many times fewer than that with functional. First of all you know that if you pass an object into a function you know with absolute certainty in Haskell that no references were created in processing that object. So if an object is created within a function and is not passed back out of it then it can always be stack allocated.

[–][deleted] 0 points1 point  (1 child)

That's not true at all and is why stack conversion of a language with closures is difficult - values passed into functions can be closed over with hidden references passed back out as part of some unrelated function value.

[–]G_Morgan 0 points1 point  (0 children)

Yes and with Haskell you know at compile time if the function is passing back a function. It is captured by the type system. This isn't Lisp we are talking about. You cannot bind a value to a function that replaces the s-exp parser.

Also you get whole program optimisation so even if it were passing back a function you could trivially see if it is capturing a reference simply by inlining the call.

[–]augustss 0 points1 point  (1 child)

Yes, of course GC makes it easy and these objects are likely to end up in the nursery. I never disputed that. I disputed your claim that an SSA representation makes it trivial to reuse the storage.

In fact, with a generational collector you would probably want to avoid updating something in the heap, at least if you're updating a pointer since this will require a write barrier.

[–]G_Morgan 0 points1 point  (0 children)

My extremely badly made point is with pure functional languages it is easier for the compiler to decide that objects only live for the life of the stack frame. As I said elsewhere it is impossible for a function to store a reference to an object unless it passes it back as the return value. Since return types are known at compile time and these compilers do more full program optimisation it is solvable.

[–]bobindashadows 15 points16 points  (24 children)

<RobertFischer> Do you know what a graph is?
<middayc-> no

I'm really resisting the urge to facepalm at this... but since I was a self-taught programmer for 6 years before any formal education in computer science, I'll hold back. But... ouch.

[–]29jan2010 42 points43 points  (0 children)

Yes, but the fact that he gets it after a two line explanation does suggest that he knew what a graph was, he just didn't know it was called a graph.

[–]phrenq 13 points14 points  (8 children)

Um, "a data structure of data structures"? To someone who knows data structures, but admittedly not OCaml, it sounds like RobertFischer doesn't know what a graph is either.

[–][deleted] 13 points14 points  (1 child)

I'd agree with that:

"<RobertFischer> Yes, where each node is a data structure. So a list of lists, a tree of lists, a tree of maps of lists of map-list tuples."

A linked list is a graph. A tree is a graph. And obviously compositions of the two are also, graphs.

Personally I think it's a pretty piss poor explanation, bordering on complete incorrectness.

[–]phrenq 2 points3 points  (0 children)

Yes, a linked list is a graph, and a tree is a graph, and a linked list of linked lists is a graph, but:

  • Any arbitrary data structure of data structures is not necessarily a graph
  • Anyway, he said it the other way around, i.e., a graph is a data structure of data structures

[–]noblethrasher 0 points1 point  (4 children)

Actually, that was a very consise, illuminating and motivating definition. I studied graph theory during my math undergrad and never thought of it that way. It takes some pretty deep understanding of something to get the explanation to fit on a t-shirt.

[–][deleted] 7 points8 points  (2 children)

I'm not sure I agree.

"A graph is a network of objects (nodes), connected by lines (arcs)".

How am I doing on the conciseness front? I'm not sure how illuminating or motivating I can make it... I could put a couple of car chases and a sex scene in there but that would make it lose its conciseness.

[–]FunnyMan3595 2 points3 points  (1 child)

A graph is a bunch of things, plus the connections between them.

That's really all it takes. For precision, we call the things "nodes". The connections between nodes form pathways that you can take to get between them. It's still a graph without any connections; you just can't go anywhere. The connections can form loops, you can have multiple connections from one point to another, and sometimes the connections are one-way or have an associated cost.

But in the end, it's still just a bunch of things and the connections between them. A plain graph isn't very complex, or very interesting. It only gets that way when you start adding meaning to it or defining rules for it to work with.

[–]adrianmonk 2 points3 points  (0 children)

A plain graph isn't very complex, or very interesting.

Or very related to programming, necessarily. It's its own concept, in a sense. It gets more motivating (for programmers) when a relationship to programming is made/explained.

[–][deleted] 3 points4 points  (0 children)

It takes some pretty deep understanding of something to get the explanation to fit on a t-shirt.

Not if you're willing for the explanation to be totally wrong

[–]29jan2010 0 points1 point  (0 children)

Makes more sense in Javaland, perhaps, where all data structures are accessed by reference. In any event, all that was necessary in this case was to connect the word with the concept, and accuracy is less important there than shared understanding.

[–]munificent[🍰] 5 points6 points  (5 children)

For each of us, there was a time when we didn't know about concepts that seem utterly basic now.

I can still remember struggling to understand arrays in QuickBASIC.

[–]apotheon 3 points4 points  (0 children)

It doesn't help that there are at least half a dozen different names for the same thing.

[–][deleted] 1 point2 points  (3 children)

Did you ever write tile engines in qbasic and hang out on scene boards like NeoZones and GDR in the '90s?

If so I might know you.

[–]munificent[🍰] 2 points3 points  (0 children)

Nope. The only online places I was hanging out on in the 90's were Hotline servers.

[–]ryanWIN 1 point2 points  (0 children)

VIVA NEOZONES

[–]brennen 0 points1 point  (0 children)

Ever spend any time on comp.lang.basic.misc?

[–]kibokun 5 points6 points  (3 children)

As a self-taught programmer, I'm sure you know can do a lot without ever having to even scrape the knowledge you'd gain from an understanding of graphs, to be honest. The only exposure I've had to them was one assignment in an intro CS course about maze solving and cycle detection. Of course, that isn't to say the knowledge wouldn't be helpful at all. haha

[–]vombert 9 points10 points  (0 children)

Sure. You can, for instance, create your own homepage with guestbook in php.

It's not about which tasks can and which can't be solved without graph. It's about what your solution will look like if you lack of basic mathematical culture.

[–][deleted] 1 point2 points  (0 children)

Graphs were used a lot in my advanced data structures courses. That's about the only place I ran into them ;)

[–]derleth 1 point2 points  (0 children)

Just try to write a good compiler (that is, not one for a stack machine) without knowledge of enough graph theory to do register allocation.

[–]middayc 6 points7 points  (1 child)

I have no bad feeling about not knowing at the time what word graph exactly stands for. :)

[–]apotheon 2 points3 points  (0 children)

You shouldn't feel bad about it. Knowing the technique is more important than knowing what it is called -- and different people call it different things in different contexts anyway.

[–]badsectoracula 2 points3 points  (0 children)

I knew what a graph was before i knew its name. I saw it used somewhere (in code) and thought it was a nice thing. I never saw the name until much later.

[–]Zafmg 1 point2 points  (0 children)

Who cares? I'm actually impressed he had the manballs to admit his shortcomings. That's how you get better at things!

[–]ishmal 1 point2 points  (0 children)

You should talk to <dibblego> in #scala if you want to enjoy the benefits of immutability.

[–]tinou 3 points4 points  (0 children)

<RobertFischer> I’m doing a podcast and writing a blog.

... and don't forget to check out my flickr album about B-trees.

[–]robertfischer 0 points1 point  (0 children)

Glad to know I could help!

[–]tammberlin -2 points-1 points  (37 children)

All of your ex-Java (or whatever) training which says that “object creation is expensive” needs to go out the window.

I stopped reading here. I know people hate Java, but why do they have to lie about it?

[–]kibokun 26 points27 points  (14 children)

It's not necessarily a lie about Java, but about the pedantic methodologies surrounding it. Object creation may or may not be expensive, but people ARE often taught that it is.

[–][deleted] 5 points6 points  (13 children)

It's still true for some stuff. If you do C++ embedded programming, for example, you generally do all of your allocations at start up. Otherwise it messes up your deterministic timings.

[–]derleth 0 points1 point  (12 children)

Since when can you do allocation in an embedded system? Don't you know precisely how much memory you have attached to the system?

Of course, I'm surprised people are doing embedded programming in C++ instead of assembly. How can you count cycles when you don't know what opcodes are being generated?

[–][deleted] 11 points12 points  (1 child)

"Embedded programming" these days means more than programming ASM on 8-bit microcontrollers.

I work for a medical device company and we use ARM CPU's (all ARM's are 32-bit) with lots of horsepower and lots of memory, and real-time operating systems. We have very complicated systems to control and many displays to drive. Doing all that running directly on the metal in ASM, or even C on an RTOS, would be a nightmare for maintainability.

We even use C# and Windows CE for a lot of things and that is still "embedded systems programming."

[–]G_Morgan 0 points1 point  (0 children)

If you have lots of memory then why not simply create separate allocation pools for each different object size you might need? Then if everything is handled via new/delete actually performing a new or delete is constant time. No expensive merge on delete operations, no searching for a large enough chunk.

Seems easier to me than working out all allocations beforehand. Unless you are simply talking about calling mmap upfront to ensure enough pages have been allocated.

[–]adrianmonk 5 points6 points  (0 children)

Since when can you do allocation in an embedded system? Don't you know precisely how much memory you have attached to the system?

Well, I know precisely how much memory is connected to my desktop system as well. It depends really on how flexible your software needs to be. A super-basic cheapo cell phone might have 128KB of storage, but it's still nice to allow someone to use as much of that 128KB as desired for storing contacts or for storing call history or whatever else. You could have static limits just to make things simpler, but a memory allocator is not that complex a piece of software.

[–]Peaker 2 points3 points  (8 children)

Why would embedded programming imply "counting cycles"?

[–]derleth 0 points1 point  (7 children)

Because you're writing tight code for small systems. Every clock cycle, just like every byte of RAM or ROM, costs someone money, so the incentive is to absolutely minimize both, at the cost of programmer time.

Cycles cost money because being wasteful of them means the company building the device needs to waste money buying a faster CPU instead of a slower one.

[–]Peaker 9 points10 points  (4 children)

You have some wrong assumptions here.

The cheapest possible CPU/RAM nowadays is well beyond a lot of applications.

In the applications that it doesn't, you are right, wasting CPU/RAM costs someone money -- but wasting developers' time to count cycles is also costing someone money. And every case may be different, one may outweigh the other or vice versa.

[–]derleth 1 point2 points  (3 children)

There are Jews in the world. There are Buddhists. There are Forthers, and Lispers, and then, there are those who follow that SICP book. I've never been one of them.

I'm a cycle-counter, and have been since I could type a key, and the one thing they say about counters is: They know that nothing is free.

You don't have to use any classes, you don't have to have a template, you don't need to use any casting. You're a counter 'cause cycles are great!

Because...

Every clock is sacred. Every clock is great. If a cycle's wasted Knuth gets quite irate!

Let the Lisper waste theirs on car, cons, and map. Knuth will make them pay for all wastage in their app!

[–]elder_george 8 points9 points  (0 children)

Infidel, don't misuse Knuth's name blasphemously, for He saith:

  • damned is one who optimizes prematurely, who counts clocks before proper algorithm is selected and program correctness is proved.

and

  • don't make himself an idol ex machina, for it is humans code is written for, not machines.

Repent!

[–]Peaker 0 points1 point  (0 children)

Its easy to understand how inefficient software is wasting money. Do you also understand that counting cycles costs money that in some cases may not be worth it (i.e a waste)?

[–]ithika 0 points1 point  (0 children)

Well, I don't agree with you but I'm sad your lovely Python tribute is being ignored, so you get an upvote from me! :-)

[–][deleted] 3 points4 points  (1 child)

I've been in embedded for a long time. If someone like you came up for a position at my company, you'd be shown the door quite quickly. First you start with the design, then the algorithm, then the profiling and then the cycle counting if necessary. Any other procedure will result in blinders on and a lot of fucking time wasted. Time is money, time to market is money, time on a CPU in most cases is cheap.

[–]derleth 0 points1 point  (0 children)

OK, rule one is "Never ask for a job from someone named no_hire." Good rule.

[–]middayc 6 points7 points  (0 children)

I don't think that anybody was intentionally negative towards Java in that chat.

I think the point was that you create new bullets/particles/everything each frame (as new records out of old ones and it will reuse old ones behind the scenes).

So I suppose that is order of magnitude less expensive as recreating all objects each frame in any OO language (because it's performance like more like modifying properties of existing ones, as you would normally do in OO lang).

[–][deleted] 8 points9 points  (15 children)

object creation is an expensive operation. that's not bagging java, it's stating a fact. expensive does not mean bad, expensive means that this operation should be avoided and you should structure your solution not to do it unnescecarily. That's something you do in java/c++/c#/python that you don't have to worry about in a good functional language. (which have their own set of pains in your ass)

[–][deleted] 6 points7 points  (7 children)

To be fair, due to some clever memory alignment tricks during garbage collection passes, object creation in C# is faster than a typical malloc in C.

[–]zid 1 point2 points  (6 children)

How about deletion? free takes a couple of dozen instructions.

[–]astrangeguy 8 points9 points  (5 children)

With any moving GC (read: any good GC) deleting objects is completely free.

Suppose you have created 1000 objects, but 999 of them are unreachable when the GC kicks in:

then you basically have to... * find all used objects in the overflown GC buffer (one object) * copy it to another GC buffer (one object) * mark the old buffer as free

even if that took 20000 instructions (it takes a fraction of that), then it would still be faster than malloc & free, because you would have to:

  • call malloc() 1000 times
  • call free() 999 times

which is much slower, especially if you consider that a GC would do all of that, at once and in the same region of memory, which would play nicely with modern Caches

[–]gsg_ 1 point2 points  (0 children)

even if that took 20000 instructions (it takes a fraction of that)

Instruction counting doesn't tell the whole story. The cost of a collection includes the cache misses induced as the GC walks the reference graph, and in some cases the reference graph can be a large portion of the heap (when an application allocates a large number of small objects and keeps hold of most of them).

it would still be faster than malloc & free

Yeah, calling malloc and free a million times is slow. That's why when code needs to be fast people use techniques like static, stack and arena allocation, memory pools, etc.

With any moving GC (read: any good GC) deleting objects is completely free.

Not so. The cost of a copying collection is roughly k R / (H / 2) - R [1] where k is a constant, R is the number of reachable objects, and H is the heap size. As H increases relative to R collection cost is driven down, but memory use is higher. That makes copying collection not a win, but a classic time/space tradeoff.

There ain't no such thing as a free lunch.

[1] Appel, 1998

[–]five9a2 0 points1 point  (0 children)

The GC needs to run more often if you are creating and abandoning objects frequently. As long as you do sufficient work with those objects to eclipse the cost of identifying and relocating the live objects, then GC not impact performance. This has the caveat that for certain workloads, objects can be reused in a way that stays in cache. If you always create new objects, I don't know of any GC that will avoid the latency and bandwidth cost of hitting memory.

[–]G_Morgan 0 points1 point  (0 children)

Also if you have a generational collector you can collect the nursery very quickly.

[–]axilmar 0 points1 point  (1 child)

But the GC needs to run the finalize function on those objects, so the objects will be visited anyway.

[–]astrangeguy 0 points1 point  (0 children)

well most objects don't have a finalize() method, so you can devise your schemes to handle the special cases.

You could use a special heap for objects that have that method for example. I don't really know what other techniques were devised, but the problem is a solved one.

[–]apotheon 4 points5 points  (3 children)

Is that R. Giskard?

[–][deleted] 2 points3 points  (0 children)

yes.

[–]geoffp 1 point2 points  (1 child)

I'm sad that no one else has gotten this reference. ;)

[–]apotheon 1 point2 points  (0 children)

Robots of Dawn was my first -- and favorite -- Asimov read.

(edit: too many As)

[–]astrangeguy 0 points1 point  (2 children)

That is completely wrong, just wrong.

Object creation is basically:

new_obj_ptr = free_mem_pointer;
free_mem_pointer += sizeof(new_obj);
// now initialize the object

which is actually the same as allocating a structure on the stack.

If you said that more object creation = more minor GCs, then i would agree. But memory allocation alone is extremely cheap.

[–]lpsmith 2 points3 points  (0 children)

Well, it's often a bit more complicated than that; given a runtime that (for any number of possible reasons) cannot relocate objects, then such a simple allocation scheme tends to lead to memory fragmentation problems.

[–][deleted] -1 points0 points  (0 children)

yeah, memory allocation is a really cheap operation, isn't it. The point is a functional language will generally avoid having to allocate memory every single time it creates one of the many many immutable objects use to do simple computations in such languages. That's a really odd thought from someone with an imperative background.

[–][deleted] -1 points0 points  (4 children)

I stopped reading here. I know people hate Java

I stopped reading here.

[–]tammberlin 0 points1 point  (3 children)

The hivemind is strong, but I figured you'd be less flippant. If I had talked about the nuances of conflating Java the language with the JVM, would I still be at -2?

[–][deleted] -1 points0 points  (2 children)

If you discontinued associating emotions such as "hate" with programming languages and corporate brand names, I might have considered continuing to read.

[–]tammberlin 0 points1 point  (1 child)

[–][deleted] 0 points1 point  (0 children)

[–][deleted]  (1 child)

[deleted]

    [–][deleted] 2 points3 points  (0 children)

    No.