r/learnprogramming • • Jun 09 '12

Types of programming

So i have been teaching myself Java programming for the last two months,and I understand that it's an Object-Oriented Programming language. But from my time of stalking these forums I've read a lot about functional programming,and other types that I don't really understand. I get that I shouldn't expect to know much outside Java after only 2 months,but I'm just interested in how other languages differ from Java.

I've also read about Haskel,Scala and other seemingly unusual languages,and so my question is:

TLDR - "What are the differences between the programming types?"

215 Upvotes

96 comments sorted by

View all comments

Show parent comments

65

u/sw1sh Jun 09 '12

This answered all my questions about the types of programming,and just opened up a whole new world of stuff for me to look up about programming!

They all sound so freaking interesting,i just want to know them all!Prolog in particular sounds like it could be a weird experience. I still dont fully understand how the likes of these other paradigms would work,but I imagine that's why people spend so much time learning them. You have seriously made me want to discover different styles of programming when I have learned Java much better. Haskell in particular has made me interested as it seems like it would have the widest variety of things to learn about. And particularly because I was planning on learning a higher level language next,but didnt realise Haskell was so high level.

What in particular makes Haskell so high level? And when you say parallel programming,do you mean telling a piece of code to run different parts at the same time on different CPUs(for example) and then combining the results at the end? Have you programmed in CUDA and is that an example of a parallel programming language?(I ask because a friend of mine did his final year project on using CUDA to work on huge matrices because he could harness the multiple cores of a GPU to solve them much quicker)

102

u/kqr Jun 10 '12

This answered all my questions about the types of programming,and just opened up a whole new world of stuff for me to look up about programming!

Great! It's a very exciting world with lots of things going on independently, and if you manage to view it all in an unbiased fashion, you can learn a lot.


Prolog in particular sounds like it could be a weird experience.

Yes, It's really, really weird and very difficult. I have a friend who, too, have toyed a little with Prolog, and he likes to say the experience is like "programming... only backwards."

It's not uncommon for me, when playing around with Prolog, to write some rules for the solution that feels natural to me, and then just blindly test my program to see what I've accomplished, and then it works. And I have no idea how it does.


You have seriously made me want to discover different styles of programming when I have learned Java much better.

Learning Java well first is a very wise decision and I'm glad you made it. I was thinking about including a paragraph where I tell you to be careful with jumping between languages without learning the one you're doing properly first, but it seems you have realised that by yourself.


Haskell in particular has made me interested as it seems like it would have the widest variety of things to learn about.

Haskell is the playground for most of the programming language research today, so it's really interesting in that sense, yes. And people who use Haskell likes to use fancy words as well (what is a functor? What is a formal category? What is a monad? What does it mean for a program to have partiality?) so you'll pick up lots of those in time as well.


What in particular makes Haskell so high level?

That is unfortunately not something I can easily explain. It's just that you get a particular set of functions and data types and whatnot built into the language, but then you can implement your own, and your implementations extend the language. When you have implemented your own extensions to the language, using them feels just like they were in the language from the beginning.

The particular example I have is much too complicated to be easy to get (I spent a good two hours trying to understand, probably), but the thing is that what you do might be really complex and difficult and require lots of code, but once you've done a proper implementation, using it is a breeze.

In that particular example, the author had a function called accumSum which is meant to read in an infinite list of numbers and output an infinite list of numbers which are the sum of the numbers read so far. As an example, if accumSum would be applied to the infinite list of all the positive odd numbers:

1, 3, 5, 7, 9, 11, 13, 15, ...

It would output the infinite list of the accumulated sums, like so:

1, 4, 9, 16, 25, 36, …

At each step, all the previous elements are summed and outputted. I keep saying that the lists are infinite because they really are. In Haskell, they can be.

Anyway, the function for doing this accumulated sum is, to start with, not very complicated, but kind of long:

accumSum = Coroutine $ step 0 where
    step s i = (s+i, Coroutine $ step (s+i))

(No, I don't expect you to understand a thing. Just look at the length of it, and realise that it's a very specific function for just this purpose.)

Then the author goes on to realise that accumSum actually follows a more general scan pattern, so he defines a scan function.

scan f i = Coroutine $ step i where
    step a b = let a' = f a b in (a', scan f a')

The scan function is very general, very academic in its nature and very, very difficult to understand. Specific examples are always easier than more general principles.

Anyway, using this general scan function, the author can implement accumSum in terms of it. accumSum simply becomes a call to the scan function with some specific parameters. The new accumSum is a lot more declarative than the previous one:

accumSum = scan (+) 0

And the amazing thing is that these functions and data types and whatnot are user defined and all, but it really seems like they're part of the language.

The thing that tells me a language is very high level is when you can extend the language with your own operators, functions, data types and whatnot, and in a blind test, a random programmer should think your stuff is part of the language.


And when you say parallel programming,do you mean telling a piece of code to run different parts at the same time on different CPUs(for example) and then combining the results at the end.

Precisely.


Have you programmed in CUDA and is that an example of a parallel programming language?(I ask because a friend of mine did his final year project on using CUDA to work on huge matrices because he could harness the multiple cores of a GPU to solve them much quicker)

I have thought about doing some CUDA, and I even started downloading the toolkits and all, but something got in the way. Yes, programming for CUDA would be a prime example of parallell programming.

16

u/sw1sh Jun 10 '12

It seems like you would have to get very low-level then if you need to tell different processors to do separate things at the same time,but I suppose that these rules for telling them what to do could just be abstracted away the same way as any language is.

And yeah,I figure that if I can learn one language solidly before I start messing around with others,I'll have a much easier time getting to grips with it all. If I try to learn two together I feel like I wouldn't get as much out of either and end up have a very basic knowledge of both,rather than an in-depth and applicable knowledge of one. I've heard Haskell has a very steep learning curve,how true would you say that is?

21

u/kqr Jun 10 '12

It seems like you would have to get very low-level then if you need to tell different processors to do separate things at the same time,but I suppose that these rules for telling them what to do could just be abstracted away the same way as any language is.

Yes, precisely. Consider a very simple problem: sorting a list. You could divide the list into two halves and sort them independently, and then merge the results into a sorted list. The two halves can, in turn, be divided into halves and sorted independently, only to be merged later on. This is incidentally called a merge sort algorithm.

A sufficiently smart language can sort the two halves independently using two processors, without you having to delegate work manually.


If I try to learn two together I feel like I wouldn't get as much out of either and end up have a very basic knowledge of both,rather than an in-depth and applicable knowledge of one.

Yup. You've pretty much described me!


I've heard Haskell has a very steep learning curve,how true would you say that is?

The learning material has a very steep learning curve. There's nothing inherently difficult about the language itself (except that it's a lot different from imperative languages), but almost all learning material assumes ten years of programming and requires you to think a lot, not much unlike a maths textbook. (I'm exaggregating a little, but I do think the state of the available learning material is pretty sad.)

With that being said, there are excellent texts available. Learn You a Haskell for Greater Good is a free online book which is praised for being simple and very funny to read.

The thing that usually trips people up about Haskell early on is the fact that it's a pure functional programming language. The pure bit means that functions can have no side effects. No function is allowed to change the world in any way at all. Then how do you draw something on the screen, write to a file or even print something to the console?

There's a brilliantly smart system in place to allow for some functions to actually change the world, and while I can't speak for how difficult it is for everyone else, what I've gathered is that people very often go about trying to learn that system the wrong way. People often try to learn all the theory and mathematics behind it instead of just using it over and over to learn how to use it. This is partly due to the complicated learning material available, which encourages learning the theory and mathematics because that happened to work for the author of the material.

2

u/JimboMonkey1234 Jun 10 '12

If you're curious about CUDA, I just did a project on it myself and can tell you it's not very low-level at all. It's essentially C++ with some special parallel sections that usually work on arrays. It's something like:

// disclaimer: not valid syntax!
__parallel__ func(int array[])
{
    int id = myThreadId();
    array[id] = id*id;
}

All you need to make sure is that you have enough "threads" (that's a process that can run on a CPU) running and that code will fill up the array with a sequence of perfect squares (and really quickly too!).

2

u/[deleted] Jun 10 '12

The thing that tells me a language is very high level is when you can extend the language with your own operators, functions, data types and whatnot, and in a blind test, a random programmer should think your stuff is part of the language.

How is this any different from C++ though? You can do all those things in C++. The only why a random programmer knows whether these new types and operators are part of the language or not is because the compiler is intelligent enough to highlight them differently.

I only have experience with C++ so that's why I ask this question :)

1

u/kqr Jun 10 '12 edited Jun 10 '12

I believe you have to use the new keyword for custom types which are not structs. I might be wrong though. I'm also pretty sure you have to manually delete values of custom types when you're done with them. This separates library- and custom data types from the primitive types which are "in" the language, so to speak.

You are also very limited when it comes to inventing syntax. C++0x improves on this, and because I have no idea how many goodies C++0x adds, I can't speak too much about it, but I still believe a custom loop construct will look a little different from the default while loop.

1

u/[deleted] Jun 10 '12

I believe you have to use the new keyword for custom types which are not structs. I might be wrong though.

New is used to initiate pointers, it doesn't matter whether these pointers point to native or custom classes. Usually, it doesn't make much sense to use new on a native class because native objects are always 4 bytes or less. But it does certainly happen in some cases.

I'm also pretty sure you have to manually delete values of custom types when you're done with them.
Again, only with pointers.

You don't have to use pointers necessarily, you can move the entire class if you want. When doing that you don't use new or delete.

You are also very limited when it comes to inventing syntax. C++0x improves on this, and because I have no idea how many goodies C++0x adds, I can't speak too much about it, but I still believe a custom loop construct will look a little different from the default while loop.

I'm not sure what you are talking about here. As far as I know, C++0x adds new syntax to the language that makes it easier/more readable to do things that were otherwise hard to write/hard to read.
There is no distinction between a default while loop or a custom loop construct in c++. All loops are native to the language, there is no such thing as your own loop in c++. Unless you wrap that in a custom class with overload/add operators, but that I can't imagine a situation in which that would be useful in any way.

1

u/kqr Jun 10 '12 edited Jun 10 '12

New is used to initiate pointers, it doesn't matter whether these pointers point to native or custom classes. Usually, it doesn't make much sense to use new on a native class because native objects are always 4 bytes or less. But it does certainly happen in some cases.

I didn't think there was such a thing as a native class. I guess I'm influenced by Java, which makes a difference between "primitive types" and other types.

You don't have to use pointers necessarily, you can move the entire class if you want. When doing that you don't use new or delete.

Can you make an array or a vector of entire instances, and not pointers to instances?

there is no such thing as your own loop in c++.

This is precisely what I'm talking about. I might want to be able to say something like

repeat (500) {
    printf("hello!\n");    // prints hello! 500 times
}

or

foreach (list) {    // where foreach works for *any* sequential type, including those you have defined
    printf("%i\n", element);
}

If I can't define such a loop on my own, the language gets pulled down a notch or two in my low-to-high level continuum.

I can't imagine a situation in which that would be useful in any way.

Have you read about the blub paradox? (Always a dangerous thing to bring up, but I think it's interesting.)

1

u/[deleted] Jun 10 '12

Can you make an array or a vector of entire instances, and not pointers to instances?
Yep.

This is precisely what I'm talking about. I might want to be able to say something like repeat (500) { printf("hello!\n"); // prints hello! 500 times } or foreach (list) { // where foreach works for any list types, including those you have defined printf("%i\n", element); } If I can't define such a loop on my own, the language gets pulled down a notch or two in my low-to-high level continuum.

Ah, now I understand what you meant. The two types loops you used as example are both definitely possible, although the syntax is different a bit more code is needed. They are both possible and both those types of loops are used a lot.

Have you read about the blub paradox? (Always a dangerous thing to bring up, but I think it's interesting.)

Well, good point!

1

u/kqr Jun 10 '12

The two types loops you used as example are both definitely possible, although the syntax is different a bit more code is needed.

Yes. C++ is turing complete, I know. However, the interesting thing is if you can make your own loops look like they were in the language all along. That's what matters to me in this case. That's what I was talking about.

2

u/terari Jun 10 '12

It's not uncommon for me, when playing around with Prolog, to write some rules for the solution that feels natural to me, and then just blindly test my program to see what I've accomplished, and then it works. And I have no idea how it does.

I tried to explain the basics of Prolog here (but I am not Prolog expert either)

1

u/itsjareds Jun 11 '12

I think at this point I've realized why I'm going into a computer science major next year. Reading all your posts, including this one, put a smile on my face and I'm laughing with excitement and eagerness just learning about all of this. Thanks for the write-up.

0

u/[deleted] Jun 14 '12

[deleted]

2

u/kqr Jun 15 '12

Take a square and divide it up this way. If it isn't clear already, just tell me and I'll explain further.

6

u/terari Jun 10 '12

Prolog in particular sounds like it could be a weird experience.

To understand prolog, you need to look up "resolution method" at logic.

At a logic, you can deduce statements from other statements by using inference rules (such as modus ponens: if I have the statements "if A then B" and "A", I can derive "B"). The resolution method replaces all inferences rules for a single rule, and enable you to rewrite a demonstration or refutation of a theorem proof as a finite search (basically, you rewrite your theorem as "if the premises are true and the conclusion is false, then you have a contradiction", and search for the contradiction).

In Prolog, all formulas are horn clauses and the resolution method is called SLD resolution. The objective of the resolution method is to combine the formulas in a way that you end up with a contradiction (an empty horn clause). To combine formulas one use the resolution rule, that consists in elimination of complementary literals and unification. The article on resolution method has an example that illustrate this rule. The example says:

  1. Suppose the premise "For all x, if P(x) then Q(x)"

  2. and "P(a)" for a given a

  3. The conclusion is Q(a) is true

Point 1, rewritten as a horn clause, is "P(x) is false, or Q(x) is true" for x being any term.

P(a) and Q(a), with a being a constant term, are already horn clauses.

At the resolution method, one would from supposing the conclusion is false, try to reach a conclusion. That is, you work with the following horn clauses:

  1. P(x) is false, or Q(x) is true

  2. P(a) is true

  3. Q(a) is false

The goal is to reach a contradiction from 1., 2. and 3.

Rewriting this using the set notation for clauses one have

  1. { ¬P(x), Q(x) }

  2. { P(a) }

  3. { ¬Q(a) }

Where ¬x means "x is false". The goal is to reach the empty clause { }, that is a contradiction.

The resolution rule says that from the clauses { d, k.. } and { ¬d, g.. } one can conclude { k.., g.. } where k.. and g.. are a set of literals and d, ¬d are literals. A literal is a formula P(..) or ¬P(...) where P is a predicate.

Then one needs to find two clauses where a d appear in one, and ¬d appear in another.

{ ¬P(x), Q(x) } and { P(a) }, are such clauses, if you unify P(x) and P(a) by substituting x for a. (here P(x) means P(x) for "any x", while P(a) is for a specific a only)

By unifying P(x) and P(a), the 1. becomes { ¬P(a), Q(a) } and from it and { P(a) } one can conclude { Q(a) } by eliminating the complementary literals P(a) and ¬P(a).

You then have

  1. { ¬P(x), Q(x) }

  2. { P(a) }

  3. { Q(a) }

  4. { ¬Q(a) }

From 3. and 4. you can eliminate Q(a) and ¬Q(a) and conclude the empty clause { }.

With this you prove that you can conclude Q(a) from the premises "for all x, if P(x) then Q(x)" and P(a). That's how Prolog works.

This might be alien talk, but what I meant is, if you know first-order logic and the resolution method Prolog is totally logical.

2

u/sw1sh Jun 10 '12

Really have no idea what you just said...but it sounds seriously interesting. I'll have a look again later and explore the links you left to fully understand it all,but thanks for putting the time in to explain it. It just seems so counter-intuitive to normal thinking.

I just finished a degree applied math,so my brain is always thinking if x is true then y as standard logic. I imagine it will just take a bit of rethinking the logic to understand how it is used.

2

u/kqr Jun 10 '12 edited Jun 10 '12

You set a few basic facts. For example, you can say that

female(jenny).

This is a fact in Prolog that simply states "jenny is female." You could also state a relation:

child(jenny, sarah).

This relation says that "jenny is a child of sarah." Then you can say something like:

daughter(X, Y) :- child(X, Y), female(X).

This is Prolog for "To prove that X is a daughter of Y, you first need to prove that X is a child of Y, and then that X is female." You could also do:

grandchild(X, Y) :- child(X, Z), child(Z, Y).

This means that "To prove that X is a grandchild of Y, you will first need to prove that there is a child Z of X, so that Y is a child of Z." Then we can ask the interpreter:

?- daughter(jenny, sarah).

which is the question, "Is jenny a daughter of sarah?" The interpreter will respond:

yes

You could also perhaps ask:

?- grandchild(jenny, sarah).

to which the interpreter responds:

no

That's Prolog programming in a nutshell. The methods the interpreter uses to prove things are contained in the resolution engine, and there are essentially three methods, I think. I'm not very good with the details of it.


Edit: Oh, and I missed the most important part. When asking the interpreter questions, you can leave wildcards instead of actual values. You could, for example, ask:

?- daughter(jenny, X).

Prolog responds with:

X = sarah ?

(If jenny has more than one daughter, the interpreter can list them all.) Of course, you can turn this around, giving:

?- daughter(X, sarah).

X = jenny ?

What are we really asking here? We're asking, "sarah is the daughter of whom?" Which is essentially the same thing as asking "Who is sarahs mother?"

1

u/terari Jun 10 '12

Okay =)

But hey, this is standard logic. Prolog works with first-order classical logic, as vanilla as predicate logic can be.

It seems that math courses don't study mathematical logic. (at least, on my university, only computer science students study logic... I don't understand this, but this is how it is)

1

u/terari Jun 10 '12 edited Jun 10 '12

Did you ever see a natural deduction derivation tree? Some leaves of this tree (the "open leaves") are called premises, and the root is called a conclusion. Each node of this tree corresponds to the application of an inference rule, and the tree itself is, by definition, a testimony that from the premises you can derive the conclusion.

If you rewrite your formulas in conjunctive normal form (or, in the case of first-order logic, clausal normal form), then all inference rules can be substituted by the application of a single rule (the resolution rule). This does not really change your logic, it is just a change on notation.

1

u/sumguysr Jul 09 '12

And when you say parallel programming,do you mean telling a piece of code to run different parts at the same time on different CPUs(for example) and then combining the results at the end

Yes, but almost any language can do this, provided its compiler or interpreter supports these hardware features, but some languages have features that figure some things out for the programmer to avoid common problems, or even make all common problems impossible. One very common problem in parallel programming is dead locks, when you have two processes, one asks for information from the other to proceed, then the other asks the first one for information to proceed, then neither can continue and the program has probably crashed or failed. Programming languages which have awareness of parallel processing languages built in can sometimes realize when that sort of thing will happen ahead of time and warn the programmer or prevent it.