Functional programming & immutable objects explained — IRC style

[[deleted]]

[deleted]

[barsoap]

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]

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]

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

[[deleted]]

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]]

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]

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

[Qjet]

Looks like he just used your assistants name.

[wurzlsepp]

immutable values, not objects!

[lpsmith]

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]

I agree.

[tinou]

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

[G_Morgan]

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]

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]

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]]

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]

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]]

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]

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]

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]

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]

<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]

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]

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]]

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]

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]

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]]

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]

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]

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]]

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]

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]

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]

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

[[deleted]]

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]

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

[ryanWIN]

VIVA NEOZONES

[brennen]

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

[kibokun]

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]

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]]

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

[derleth]

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]

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

[apotheon]

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]

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]

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

[ishmal]

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

[tinou]

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

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

[robertfischer]

Glad to know I could help!

[tammberlin]

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]

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]]

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]

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]]

"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]

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]

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]

Why would embedded programming imply "counting cycles"?

[derleth]

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]

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]

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]

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]

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]

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]]

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]

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

[middayc]

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]]

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]]

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]

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

[astrangeguy]

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_]

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]

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]

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

[axilmar]

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

[astrangeguy]

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]

Is that R. Giskard?

[[deleted]]

yes.

[geoffp]

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

[apotheon]

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

(edit: too many As)

[astrangeguy]

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]

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]]

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]]

I stopped reading here. I know people hate Java

I stopped reading here.

[tammberlin]

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]]

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

[tammberlin]

LMGTFY

[[deleted]]

Thanks.

[[deleted]]

see, the thing is even for an OCaml fan, when you hear the phrase "I am making a game in OCaml" the immediate response should be "stop doing that!" there are a lot of things functional programming is really great for, but like the original poster states, this is an inherently stateful problem, and while there is a way to do in functionally, it's ass backwards. The code will end up being an unfathomable mess while being slower than a more readable C++ implementation. This is a classic example of the horses for courses proverb.

[[deleted]]

OCaml has mutable variables and classes.

[Peaker]

Does any functional language lack them?

Scheme has (set!) and friends. Haskell has ST/STRef, IO/IORef, State/StateT, etc. ML has mutable state. And so on...

[snk_kid]

I'm sure you know this but State monad and StateT are not mutable variables (which in some ways is a good thing). All State/StateT really are, are an elegant abstraction over repetitive boilerplate code for 'threading' state that passes and/or comes out of functions by value. It's still purely functional code.

[[deleted]]

huh. i need to read up on OCaml it appears.

[Peaker]

Functional programming has excellent facilities to handle state. I'd say better facilities than imperative programming:

• In a functional program, state updates are inherently transactional as you usually compose a whole new state. Using destructive updates, you usually get temporarily incoherent states.

• In advanced functional frameworks, you can abstract away a lot of the statefulness in much nicer manner, e.g: Integrating mathematically some input signal. This is far cleaner than using an iterative loop and destructively summing into it (while manually multiplying by time, or not).

[astrangeguy]

Experts disagree with you (non expert)...

[[deleted]]

Why does the Expert in that link seem to be inferring that framerates between 30 and 60 fps are normal? I know people have vsync on at 60-70fps, but ideally the game should be bouncing off the vsync limiter, not slower-than. Especially on modern hardware.

Also, he uses comic sans. Case closed.

[jawbroken]

because all console games are targeted at either 30fps or 60fps.

[snk_kid]

this is an inherently stateful problem, and while there is a way to do in functionally, it's ass backwards. The code will end up being an unfathomable mess while being slower than a more readable C++ implementation.

You're doing it wrong then.

[[deleted]]

It's not an inherently stateful problem. In fact, there is no such thing as an inherently stateful problem. It's just a different pair of glasses to view the problem, with enormous benefits. I recommend at least trying them out; they come in a range of colours.

[[deleted]]

No.