# At the feet of the Great Monad, or, How the functional programming craze plays out

"Today, object-oriented programming (OOP) rules the IT industry absolutely. It is impossible to dislodge. While functional programming (FP) has seen a resurgence of late, it is typically used as an adjunct to OOP." – Louis Cyphre, 'Why are functional programming languages used so rarely in practice?' The leader of the …

1. #### Peyton-Jones's Book of Martyrs

Nearer than you think. Simon P-J's wife Dorothy is a priest at my local Anglican church.

Obvious icon choice.

2. #### Holier than thou

Philip Wadler notes in Propositions as Types, that lambda calculus as introduced by Alonzo Church at Princeton could be used to communicate with aliens to show intelligence. While sending a C program

might not work as successfully as in Independence Day.

3. #### Been there, done that

Back in the mid-70s, at the U of St Andrews, one of our lecturers was Dave Turner, who created the functioning programming language SASL, and later moved to Kent at Canterbury where he developed Miranda, an ancestor of Haskell.

His colleagues thought it was a great joke to allocate him to give us the Fortran course... and scheduled the lectures for 0900 in the morning.

For some reason, my Fortran was never very good...

1. #### Re: Been there, done that

His colleagues thought it was a great joke to allocate him to give us the Fortran course... and scheduled the lectures for 0900 in the morning.

Ah, the joys of being a young lecturer. Lectures at 9:00 Monday and 5:00pm Friday, while the Profs & Readers get just before lunch in the midweek.

For some reason, my Fortran was never very good...

Was anybody's? There was a joke back in the 70s & 80s that as all the particle physicists shared code, a significant number of the particles discovered were probably Fortran bugs.

1. #### Re: Been there, done that

I always preferred coders who had been brought up writing assembler - high level languages just make it easier to ignore the bugs in the code.

2. #### Re: Been there, done that

I remember FORTAN as being painful because of the decidedly non-agile development cycle. It was at school in the 70's, where coding took place on paper worksheets, transformed into cards using a manual hand punch, and then the card decks sent via mail to the local technical college (remember them). Where it would be compiled and the almost inevitable error message sent back to you. A week long process for one iteration. But eventually I did get a graphical plot, on the classic green stripy paper, that looked a bit like a pair of boobs - as any 14 year old would want.

1. #### Re: Been there, done that

"... transformed into cards using a manual hand punch, and then the card decks sent ..."

You forgot to mention that the card decks would be dropped or otherwise shuffled by the recipients, both before and after being processed.

1. #### Re: Been there, done that

"You forgot to mention that the card decks would be dropped or otherwise shuffled by the recipients, both before and after being processed."

Which is why you always put a stripe across the top of the deck with a big black marker.

1. #### Re: Been there, done that

Which is why you always put a stripe across the top of the deck with a big black marker.

No, a DIAGONAL stripe so to spot the out of order cards.

Tsk. Kids. These days.

2. #### Re: Been there, done that

No, that is why you punch sequence numbers in columns 73-80 of the cards. The sequence numbers should increment by 10, to allow insertions between lines without re-sequencing.

If you look hard enough in the back of the computer room, there is an old electromechanical sorter, with 10 output bins, and you know how to program it (by wiring a punchboard) to perform a radix sort, most significant column first.

And if you are an honor student, you can write a simple program for the computer to punch the numbers for you. If you are a total genius, you can program the 029 keypunch to do it.

3. #### Re: Been there, done that

"There was a joke back in the 70s & 80s that as all the particle physicists shared code, a significant number of the particles discovered were probably Fortran bugs."

They still do and they probably are - and they're still insisting on having Fortran 77 support.

1. #### Re: Been there, done that

IMO if it can't be done in Fortran 77, it's not worth doing.

(BTW I'm another UKC alumnus)

1. #### Re: Been there, done that

"if it can't be done in Fortran 77, it's not worth doing" - Almost a direct quote from "Real Programmers Don't Use Pascal" - http://web.mit.edu/humor/Computers/real.programmers

2. #### Re: Been there, done that

I remember hearing about SASL at that time, although in our department we were using Forth.

3. #### Re: Been there, done that

I remember Dave at Kent - he was still teaching Fortran occasionally) - actually mine was quite good. I really remember the SBNOBOL4 courses - run for arts students - mainly English who wanted to do analysis on texts - very popular with CS students for some reason (nothing whatsoever to do with the large number of women who attended of course)

4. #### As a scientist, I only program functions...

... then I only call them using OO syntax. That'll teach them.

5. #### Oh well

I was expecting an amusing but insightful look at functional programming, not a weak, unfunny sub (x10) Pratchett style satire.

1. #### Re: Oh well

Worth it for "Thomas and the Unsatisfactory Weld In His Left-Hand Side Valve Gear."

1. #### Re: Oh well

"Worth it for "Thomas and the Unsatisfactory Weld In His Left-Hand Side Valve Gear.""

I guess that just proves how subjective humour is. To me that might just as well be a line from the phone book.

1. #### Re: Oh well

Best TtTE&F reference ever. Subjectively.

2. #### Re: Oh well

> Thomas and the Unsatisfactory Weld In His Left-Hand Side Valve Gear

As a steam engine, it would be slide valve gear. I think side valve is more your internal combustion engine.

/mines the one with the trim heraldic dragon in the firebox.

6. #### Missed one

"But is that not just syntactic sugar for <insert inane construct here>?"

A favourite of the Scala herd, that one.

7. So how exactly does one sort an array without a) mutating state, or b) running out of RAM?

1. You define the global ordering to be used is just the one that would give the input array. This way a do-nothing implementation is sufficient. Importantly, no side effects!

2. simple, create a new copy of the input array with every step of your sort algorithm. You did not ask for it to be fast, did you?

3. I was wondering more how you do I/O without side effects. Isn't output always a side effect?

1. I was wondering more how you do I/O without side effects. Isn't output always a side effect?

That's why I/O is a monad. As well as everything else inconvenient.

4. #### Sort in a functional language

I just use "array.sorted", but I'm sure that there are much more complicated ways to achieve the same thing. ;-)

A functional version of quicksort is only about 7 lines long, and the implementation is very close to the abstract algorithm, making use of recursion.

1. #### Re: Sort in a functional language

"A functional version of quicksort is only about 7 lines long, and the implementation is very close to the abstract algorithm, making use of recursion."

You know you can do recursion in almost all procedural and OO languages?

1. #### Re: Sort in a functional language

> You know you can do recursion in almost all procedural and OO languages?

Inefficiently, yes, and with the danger of blowing the stack, yes.

1. #### Re: Sort in a functional language

"Inefficiently, yes, and with the danger of blowing the stack, yes."

You seem to be under the impression that functional languages have some magic fairy dust they sprinkle on their recursion. Newsflash - it all gets converted to assembler under the hood so the recursion either works in the same way as procedural languages by pushing the stack and a call, or its simulated by iterative loops and heap allocation. The latter can also be done in procedural and OO languages which oddly enough is what most functional language compilers & interpreters are written in.

1. #### Re: Sort in a functional language

"You seem to be under the impression that functional languages have some magic fairy dust they sprinkle on their recursion."

Yes, they do. The magic fairy dust is called bloody necessity. You have to have fast recursion in a functional language or it all goes pair shaped. In an object orientated language, you often don't.

Case in point: the JVM does not implement generalized (nor any) tail recursion. A problem for both Scala and Clojure which are compiled to JVM byte code. Solution: both use a hack in their respective compilers to provide at least a specialised tail recursion that addresses the issue in most cases.

Java could do it, but doesn't. Clojure and Scala do do it, because they have to.

1. #### Re: Sort in a functional language

"Yes, they do. The magic fairy dust is called bloody necessity. You have to have fast recursion in a functional language or it all goes pair shaped"

Congratulations on not understanding the point I was making. I guess you think functional languages use a special functional based CPU rather than the normal one? Never mind.

1. #### Re: Sort in a functional language

"Congratulations on not understanding the point I was making. I guess you think functional languages use a special functional based CPU rather than the normal one? Never mind."

The magic fairy dust is this: If you structure your function so that the recusive call is the last act of your function, then erlang will reuse the same stack memory, allowing you to write a recusive function to iterate over a very long list without running out of stack space.

Other languages dont tend to do this, as the programmer will have written a loop instead.

5. #### @James 47

> So how exactly does one sort an array without a) mutating state, or b) running out of RAM?

Recursion + Tail call optimisation.

1. #### Re: @James 47

I never understood the value of sorting arrays, except as a way to demonstrate a technique. I would always build an index with the desired new sort order. OK, I admit that this comes from a time when batch processing (without BAT files) was a thing. Yeah, and sometimes I'd be looking at a potentially confusing element such as myarray (index1 (index2 (counter))). Sigh. I suppose that's why they invented debmesses.

6. You work out a way to "copy" a list efficiently, so that you can make a new one for every step without it going really slow. It's easy to do this with a singly linked list; you can share identical list tails between all other lists that have the same tail. It's relatively easy to program, although quite hard to visualize, which is a recurrent theme for functional programming.

The other way is to google the answer. Although we are, apparently going through a functional craze at the moment, people have been thinking about this stuff for years. All the simple and obvious questions were answered 20 years ago, so you usually find the answer if you really want it.

1. "All the simple and obvious questions were answered 20 years ago"

I wrote my first optimised bi-directional xor bubble sort more than 40 years ago!

8. #### ah yes those were the days

When you could manage to fit an OS and a useful piece of multi-user code on a machine with 512k or ram and 32Mb of hard drive... of course not nearly as exciting as using 8mb of ram just to get started :)

1. #### Re: ah yes those were the days

RSX11M - running in 32kb with a pair of 10Mb drives (one was scratch) and supporting multiple users in real time while collecting real time data (TV line rates) ... yea, been there, but moths ate the T-Shirt.

1. #### Re: ah yes those were the days

I remember being on a creaky old SunOS machine that supported dozens of users simultaneously...load averages in the triple digits were commonplace. That's when I learned to type blind and trust that eventually the remote echo would catch up.

2. #### Re: ah yes those were the days

Them were the days all right.

Running RSX-11D on a very early PDP-11/40 with 56Kb of RAM and three 2.4Mb RK05's

We developed a flight simulator to test aircraft avionics. We could run the Real Time simulation while others could compile Fortran. All on a 200KHz machine.

Not sure if things really have got better

1. #### Re: ah yes those were the days

I learned programming on the HP2000F Time Sharing System, 4K RAM, 5MB HD, 32 simultaneous users.

9. #### A digression: Sir Topham Hatt?

... so I dutifully followed the link, and encountered a vastly expanded backstory compared to when I was there last, far far away a long time ago possibly around 1977. Newer illustrations as well.

I recognise those eyes. And those porcine cheeks.

From the thumbnail sketch of the Hatt family tree provided, I expect we shall also find a connection to the Hutt family tree, with Jabba being on a cadet branch (line).

The directors of national rail companies related to some of the most notorious organized criminals in the Galaxy. Who'd have thought it?

But it's no Kingdom of the Nouns.

11. #### Highly amusing to the cognosenti but utterly baffling to the rest of us.

Which sounds like a pretty good metaphor for functional programming.

If I understood what it actually is.

1. #### Re: Highly amusing to the cognosenti but utterly baffling to the rest of us.

The closest I've got to functional programming is SQL and that has often made me fear for my sanity.

Perhaps functional programmers have travelled through a black hole and out the other side into hell and end up as some unnatural human-functional code merged construct, like in the Disney film of the same name*. They don't make them like that any more.

* The Black Hole, not that whole sentence.

2. #### Re: Highly amusing to the cognosenti but utterly baffling to the rest of us.

I think that Functional Programming means different things to different people. I don't go in for the really abstract stuff.

As someone who has 20+ years of successfully writing professional C in embedded systems, then my view of functional programming is that it is generally a better way to more quickly write programs that are easier to understand and have far fewer problems.

If I try and sum it up in a nutshell, then it feels to me that imperative programming is generally about telling the computer *how* to manipulate some data, but functional programming is more about telling the computer *what* manipulation you want it to perform on the data.

You might think that this makes functional programs really slow, but its speed is comparable to imperative programs, e.g. A reasonable Scala program is generally within 3 times the speed of highly optimised C. And, by highly optimised, I mean that most professional C programmers would not choose to write the code that way, and other programmers needing to maintain it wouldn't be thanking them for it either.

Further, it is also my belief that it makes me a better C programmer because I start to think about things in different ways, and I try to write my code differently, so that it doesn't just work today, but so that it will work reliably (even when extended) in 20 years time.

Finally, I see that the best techniques of functional programming are making their way into main stream languages like Java, and the new crop of languages like Swift, Rust, etc are adopting even more functional principals, just because it makes programmers lives easier.

Perhaps google for "Programming in Scala" by Martin Odersky, Lex Spoon, and Bill Venners. The first edition is freely available online, and gives some access into functional programming from one of the people who is very much at the forefront of modern program language design ...

1. #### Re: Highly amusing to the cognosenti but utterly baffling to the rest of us.

You're one of the few commentards to "get it," Robot W. Functional programming is not some obscure passtime for nerds, but a powerful way of thinking about programming and the management of complexity in the systems we create. From experience, a solid foundational knowledge of FP makes programmers more effective in any language.

The article was still mildly funny though, if only for the excellent TtTE reference.

12. #### Sometimes you need to be humble.

And a humble way of programming is to use an ASR33 teletype as your I/O device while you

code everything all up.

All in all a humbling experience.

Of course, the alternative before that was a keypunch and cards with a turn around time of over an hour, but I digress.

13. That's strange. I remember FORTRAN being great fun, waiting a week to see the result, and getting back a bit of paper with 1000 lines of printout all on one line. Being told that massive overprinting can damage the printhead, and maybe I should not do that.

1. Ahh the carriage return - a great innovation.

1. #### Carriage return and ....

Re: BebopWeBop

Ahh the line feed

- the other great innovation.

2. I remember the particle physicist (it might even have been Jim Virdee in his PhD student days) running an overnight job on our DecSystem10 that produced a whole box of line printer paper for its output.

He looked at the first page, realised it had all gone wrong, and scrapped the output.

Still, it helped the Christmas Party fund along niceley.

14. #### But...but...

I'd like to posit the claim that having to wait a non-trivial amount of time to get code results may actually make for better code, not worse. Because you don't want to explain to your boss why you took 48 hours to produce a core dump, so you take the time to code it right the first time. As opposed to the hack/build/hack/build loop that we are in today.

Discuss.

1. This post has been deleted by its author

2. #### Re: But...but...

Well, I agree.

It's basically "measure twice, cut once". Inconvenient obstacles make you think things through a little further. Useful not only when writing progams.

(FORTRAN 77 with punchcards, a 40 minute bus ride to the uni datacentre, waiting anything between a couple of hours to a week until they had time to feed your stack into the card reader. Yes, diagonal stripe in big felt tip pen on the side of the stack. Columns 78-80 had to contain your initials. Still, after the first trip to the datacentre to collect your printout and stack which inevitably meant collecting something that had not worked as intended, you thought harder and longer before you punched that card.)

15. #### No Erlang/OTP?!

Methinks telephony will still be here.

16. From https://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/

> While working for Church, Stephen was trying to show that the lambda calculus could compute anything “computable”. Unfortunately, Church and Kleene could not see how to compute even the following function:

> $x \rightarrow x+1.$

> Yes, even the lowly successor function was not obviously computable in their calculus. The story goes that one day Stephen was getting his hair cut, when he realized how to encode the successor function into the lambda calculus. It is claimed, he jumped out of the barber chair, with half a haircut, and ran to tell Church. Not quite Archimedes running naked through the streets of Syracuse, shouting “Eureka,” but close. I think the story, true or not, says more about the nature of the lambda calculus as a basis of computing than anything else, but that is my take.

17. #### Or if you want a more balanced view...

https://pragprog.com/book/ppanth/functional-programming-a-pragpub-anthology - contains a range of views from people using these tools to build real systems.

18. #### Pleased to see Verity has graduated from "Bootnotes" to "Software"

Verity's oeuvre on El Reg has been listed under "Bootnotes". Until now. Today she graduates to "Software". Congrats Verity, well deserved!

## POST COMMENT House rules

Not a member of The Register? Create a new account here.