Functional Programming (was Pitfalls of lacking a MMU)

Discussions on more advanced topics such as monolithic vs micro-kernels, transactional memory models, and paging vs segmentation should go here. Use this forum to expand and improve the wiki!
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by Brendan »

Hi,
brain wrote:Brendan, what about forks and extensions of languages, for example the many dialects of basic? Each solves a specific set of problems right but isn't strictly a new language, whereas there are very few 'dialects' of c if you include objective c, c# etc as dialects...
As a summary, and in the hope of not dragging this discussion further off topic, I created Brendan's Law Of Language Adoption.


Cheers,

Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
CrypticalCode0
Member
Member
Posts: 81
Joined: Wed Nov 09, 2011 2:21 am
Location: Behind a keyboard located in The Netherlands

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by CrypticalCode0 »

Define what makes a proper programming language people.

I am inclined to agree with Brendan on this BTW.
User avatar
bubach
Member
Member
Posts: 1223
Joined: Sat Oct 23, 2004 11:00 pm
Location: Sweden
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by bubach »

For future forum search and just general fun here's the continued talk/VirtualFistFight in another thread:
http://forum.osdev.org/viewtopic.php?f=11&t=24896
"Simplicity is the ultimate sophistication."
http://bos.asmhackers.net/ - GitHub
davidv1992
Member
Member
Posts: 223
Joined: Thu Jul 05, 2007 8:58 am

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by davidv1992 »

Brendan wrote:Hi,
davidv1992 wrote:Brendan, you're last post just gives the idea that you're completely oblivious to the gains of fundamental research (most of what you write can be transposed one to one to every other field of fundamental research out there) combined with a complete lack of respect.
That would depend if the reader understands important key concepts or not.
Unfortunately it was unclear to me your post was meant satirically. I have had the unpleasant experience of meeting people who happen to genuinely have the view expressed in your post about purely theoretical research, and (luckily mistakenly) believed you fit into that same category.
Brendan wrote: Let's be honest here - programming (the task) is harder than it should be, and programming (the career) is worse.

Why is programming (the task) is harder than it should be?

The task is hard because natural solutions are often not the best solutions due to restrictions. Consider your LCS example. If you had a group of 100 children (all without any programming experiences at all) and asked each child how they would solve the problem, you'll find that almost all of them would start by searching the string for the first character of the substring, and each time they found the first character of the substring they'd count to see how many characters at that starting position match. This is the natural solution. In C, it might look like this:

Code: Select all

int lcs(char *a, char *b) {
    int pos;
    int length;
    int bestPos = 0;
    int bestLength = 0;
    char first;

    first = b[0];
    for(pos = 0; a[pos] != 0; pos++) {
        if(a[pos] == first) {
            length = 1;
            while( (a[pos + length] != 0) && (a[pos + length] == b[length]) ) {
                length++;
            }
            if(length > bestLength) {
                bestPos = pos;
                bestLength = length;
            }
        }
    }
    return bestPos;
Of course this is the natural way of doing it with only one thread. The natural way of doing it with multiple threads is relatively simple (it's "embarrassingly parallel") - determine how many CPUs/children you've got and get each of them to scan part of the main string, then determine which result is the best result at the end.

Restrictions that prevent the natural solution from being the best solution include performance and language features. For performance, in this case the natural solution is likely to perform well (nice predictable pattern of accesses for the prefetcher to deal with, good cache locality even for the multi-threaded version, etc). However, if the language you're using doesn't have arrays, or doesn't let you use variables to remember what the "best length so far" is, then you're screwed.

When you can't use the natural solution, you have to use an unnatural solution. This makes programming awkward and means that how a piece of code works isn't how people expect the code to work.
I agree with you that in a perfect world the natural solution (or definition) is the best one to write, and that languages have to strive to make that as easily expressable as possible. However, the current state of affairs is that it is in a lot of cases impossible if one want's any type of performance. The argument I tried to make in my previous post is that because of the limitations it imposes, for certain classes of problems functional programming languages allow the programmer to jot down the natural solution (or sometimes even the mathematical definition) and get away with it without performance problems, whereas in languages with mutable state, due to the CURRENT state of affairs in analyzing code for optimizations like memoization they cannot be done.

What also needs to be noticed is that what might be a natural solution to one person is not neccesarily a natural solution to another person. You seem to be orriented to a mostly procedural style. I myself like to think in terms of reducing a problem to simpler cases. Some problems also lend themselfs more to one aproach than the other.
Brendan wrote: For language design, restrictions that prevent the natural solution from being used must be avoided, and any language that forces programmers to use unnatural solutions is a failure. For compiler design, the goal is to find ways to optimise the natural solution into the fastest solution, in an attempt to remove restrictions that prevent the natural solution from being the best solution.

For language design, functional languages are a complete failure because they don't allow the programmer to express the natural solution in many cases. For compiler design, research into functional languages is important, because it can lead to better ways of converting the natural solution into the fastest solution. It's important not to confuse these things - normal programmers should never need to care about functional languages unless they're designing code optimisers.
Here I do not agree. Again, different problems have different requirements, but there are (big) classes of problems which still can be "naturaly" formulated in functional programming languages. Furthermore, for these problems, the fact that the language is functional might enable the compiler to actually deduce a fast way of computing the requested answer, where it might not be able to do so in languages that support mutable state.
Brendan wrote: Why is programming (the career) harder than it should be?

Let's start with some quotes!
brain wrote:Lol someone's got an axe to grind against some academics :-)
davidv1992 wrote:That said brendan, your posts in this thread do not give the impression that you have spend any decent ammount of time with languages other than C/C++. Whilst this is your choice, it might be refreshing to try and use some other languages, i would suggest something like haskell or lisp, and something like scheme or erlang. These are languages structured in radically different ways to C/C++ type languages, and working with them might teach new methods of approaching problems. If you've tried them and you felt they didn't work for you that's fine, but at the moment you give the impression that you haven't used them at all.
Guess who's right?

Up until a few years ago I'd learnt several dialects of BASIC (Commodore 64 BASIC, QuickBASIC, VisualBASIC), several assembly languages (6502, 80x86) and C. I learnt some more obscure languages (e.g. "ladder diagrams" used by electricians to program industrial controllers, some BASH scripting, etc). I also picked up small pieces of other languages along the way (a little Pascal and a little C++, etc).

However, more recently I've been doing a "Bacheler of IT" course. In the last 18 months or so I've been taught (which isn't quite the same as "I've learnt") Alice, PHP, Phython, Perl, Java, Javascript and SQL.

I just want to write software, but over the last 18 months I haven't really been able to. Instead I've been faced with churn - learning languages for the sake of learning languages (although to be fair it's not just languages, it's the libraries and frameworks too). I've been getting more and more frustrated because I can't find enough time.

What have I learnt? Mostly what I've learnt is that the single biggest problem for programmers today is the proliferation of different languages (and the libraries, tools, code documentation systems, etc. that go with them). It's futile and unproductive and has a massive cost on the I.T. industry as a whole - retraining, retooling, rewriting and the "Tower of Babel" effect. As a test, go to stackoverflow and see how many of the questions you can answer (for any experienced programmer, I can almost guarantee that it will be less than 25% of them).

What we need is to limit the number of languages to one per field (e.g. one for low level programming, one for high level programming and scripting, one for databases, etc). What we need is some sort of conference for academics and language researchers (to get them all in the same place at the same time) and a special educational tool (a baseball bat with nails/spikes) that can be applied to these people until they get the message.


Cheers,

Brendan
I agree that there are too many frameworks for programming, and that there may be too many languages. I do, however, not agree on the stated cause for this problem. Most of the programming languages you have worked with, are not the result of language research, with the exception of python. Most are either the result of a professor thinking he needs a new language to be able to properly teach a programming concept, or individual programmers making something that they percieve solves a problem. This is where the core of the problem is. Different people have different expectations of what a programming language should do for them. This might be shaped by their education, but also comes from their personal preferences. Your proposed solution would require not just putting language researchers into that room, but almost every IT manager in the world, as it are these people who in their infinite wisdom decide that their company needs a new framework because the ones currently existing are not up to the spefic requirements their company has.

Also, I do still believe that the languages you have worked with are not a broad enough basis to make statements about all programming languages. Almost all of them, with the exception of SQL and ladder diagrams, are based on the procedural paradigm used by C/C++, meaning that one has a serial programming flow, and specifies not what needs to happen, but step by step how it needs to be done. Again, working with a language like lisp or haskel, and working with something like erlang or smalltalk might change the perspective one has on programming.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by Brendan »

Hi,
berkus wrote:That is the key and the essence. Everybody thinks differently and so many different languages exist.
For a lot of things, people think the same way unless they're specifically trained not to. Even when they are trained to think in certain ways they often (for a brief moment) start from the natural solution.

For example, imagine you've got an array or list of "person" structures and you need to find the a structure where "name = Fred Smith". For most people, their first thought will be a linear search (a likely natural solution). For trained programmers this initial thought will be quickly superseded by "Can I/should I use a hash or tree or parallelism or something to speed it up". This second thought is something they've learned purely for the purpose of optimisation; or to put it another way, the only reason they think differently is that they've been trained to make up for the limitations of code optimisers.

This is why I said "a group of 100 children (all without any programming experiences at all)". If you want the natural solution, you want people who haven't been trained to think differently.

Also note that I'm talking of a group of people for a reason. For a specific problem, if 99 children have the same solution but one child has a different solution, then it's easy to see which solution is more natural. If there's multiple solutions and none seem dominant, then maybe in some cases there's more than one natural solution. I don't know (I just don't have enough spare children to test).


Cheers,

Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
User avatar
Solar
Member
Member
Posts: 7615
Joined: Thu Nov 16, 2006 12:01 pm
Location: Germany
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by Solar »

berkus wrote:You deliberately excluded that one child who dared think like no other did.
But language is for communication. Sure you can teach that one child a different language so that it could express its thought patterns better, but no-one would be able to communicate with the poor fellow...

I know, the metaphor starts falling apart if you push it too far, but I think there's a grain of salt in it if you look at where this thread was coming from...
Every good solution is obvious once you've found it.
User avatar
JamesM
Member
Member
Posts: 2935
Joined: Tue Jul 10, 2007 5:27 am
Location: York, United Kingdom
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by JamesM »

Guys, fun as this is, can't we stop now and agree that all of our penises are equal size and cease waving them in each others' faces?
User avatar
AndrewAPrice
Member
Member
Posts: 2299
Joined: Mon Jun 05, 2006 11:00 pm
Location: USA (and Australia)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by AndrewAPrice »

I would assume that most computer science graduates would at least touch one functional programming language. For example I learnt about Scheme. Its a very minimal beautiful language (define, lambda, if are the only inbuilt constructs) that's very flexible (let, cons are library definitions). Still, I don't think I would ever find a job programming in Scheme or any other functional language. At my job now I help give input towards the creation of new tools and if I was like "let's use Schema/Haskell" they would respond with "wtf you crazy fool?" and I wouldn't blame them :lol:

In my day job I use C, SQL, C#, and Java.

I understand functional languages have their merits, and there may be times where I could benefit from functional languages but they are small in the overall projects. So unless you could mix languages (e.g. 90% Java and 10% Haskel) without dealing complex interop calling and type conversion I don't think it'll achieve mainstream adoption.
My OS is Perception.
User avatar
bubach
Member
Member
Posts: 1223
Joined: Sat Oct 23, 2004 11:00 pm
Location: Sweden
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by bubach »

JamesM wrote:Guys, fun as this is, can't we stop now and agree that all of our penises are equal size and cease waving them in each others' faces?
Actually, they did. In February.

EDIT:
My bad. It was MessiahAndrw that dug this up. Not JamesM. Retarded Sunday indeed (see next post).
Last edited by bubach on Sun Apr 22, 2012 4:31 pm, edited 1 time in total.
"Simplicity is the ultimate sophistication."
http://bos.asmhackers.net/ - GitHub
User avatar
gravaera
Member
Member
Posts: 737
Joined: Tue Jun 02, 2009 4:35 pm
Location: Supporting the cause: Use \tabs to indent code. NOT \x20 spaces.

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by gravaera »

/facepalm

I think it's something about Sundays that makes people just go full retard, no holds or bars. Given that I just lost about 40% of my brain mass debating on facebook with two women, I do believe Sundays have the power of lycanthropy for the retarded. No offense to anyone in particular \o/
17:56 < sortie> Paging is called paging because you need to draw it on pages in your notebook to succeed at it.
User avatar
Jezze
Member
Member
Posts: 395
Joined: Thu Jul 26, 2007 1:53 am
Libera.chat IRC: jfu
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by Jezze »

Why debate something you can't possibly win.
Fudge - Simplicity, clarity and speed.
http://github.com/Jezze/fudge/
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by Brendan »

Hi,

Please use more commas:
gravaera wrote:Given that I just lost about 40% of my brain; mass debating on facebook with two women, I do believe Sundays have the power of lycanthropy for the retarded.
:roll:

Cheers,

Brendan
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
User avatar
gravaera
Member
Member
Posts: 737
Joined: Tue Jun 02, 2009 4:35 pm
Location: Supporting the cause: Use \tabs to indent code. NOT \x20 spaces.

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by gravaera »

I C wut u did thar...

I am not amused :|
17:56 < sortie> Paging is called paging because you need to draw it on pages in your notebook to succeed at it.
Qeroq
Member
Member
Posts: 52
Joined: Wed Aug 25, 2010 6:35 am
Location: Bonn, Germany

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by Qeroq »

Despite all the flame war I'd really like to thank Rusky for providing these papers on dependent types. I came up with a pretty similar concept (although I called them conditional types) while experimenting with formal code verification a couple of months ago and how I could apply it for kernel programming. Maybe those papers contain some additional insight to the subject and can help me to solve the few problems I was struggling to get my head around back then.

Anyway, keep calm, folks. I think we're all intelligent people around here and all have our well founded opinions on things. I think that theoretical research, including but not limited to, (pure) functional languages, formal code verification etc., can dramatically enhance our understanding of programming, compiler and language architecture, optimization etc. and may indeed sip through in one's everyday workflow, even when not directly confronted with the cutting edge technology at hand (such as several weeks of Haskell has provided me a pretty useful mindset, even when working with C/Java). On the other hand I can understand rather refusing positions to some extent as well, because existing tool sets might be enough for getting things done quite well. Just remember to keep an open mind, stick to the facts and read the papers if you consider them interesting, or let it be otherwise.
https://github.com/qero/Hydrogen (Loader for AMD64 kernels running on top of GRUB2)
User avatar
elderK
Member
Member
Posts: 190
Joined: Mon Dec 11, 2006 10:54 am
Location: Dunedin, New Zealand
Contact:

Re: Functional Programming (was Pitfalls of lacking a MMU)

Post by elderK »

There's a lot of interesting talk here if you're careful to avoid being burned.

And as for theory/research not being conducted on useful, practical things...

Remember that everything we take for granted now was once considered academic wank. For example: compilers, linkers, regular expressions, optimizers, scheduling algorithms, IPC/synchronization, memory management algorithms...

Alan Turing and Alonzo Church were both outstandingly intelligent men and both contributed a massive amount to Computer Science. They worked together several times, also. They weren't enemies but fellow researchers, colleagues in pushing towards greater understanding.

The Turing machine and the Lambda Calculus are both just ways of expressing computation, both bring insights.

In any case, it's good to see the ol' regulars are still alive and kicking: Combuster, Bubach, Brendan, JamesM, Colonel Kernel, MessiahAndrew (I remember when you first starting posting here :)).

And it's great to see newcomers, too. ChildOfTechno, Rusky and the like.

Keep it coming, all of you. It's all interesting. :)
Post Reply