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

666

u/kqr Jun 09 '12

That is a very broad question, but as this subject is somewhat of a favourite of mine, I'll do my best to elaborate on it. There are a few ways to categorise programming languages, and I will try to convey the most useful ones I know of.

This is of course a simplified version, but I hope it'll suffice. If you disagree, please tell us all why instead of simply downvoting. (Simplifications tend to collect downvotes.)

This grew quite a lot longer than I expected, but as I've written it anyway I'll post it here. If you have any question or don't understand something, please, please, please ask it. I'd love to answer. I hope the glow I get in my eyes when I speak or write about this is evident enough.

TURING COMPLETENESS

One thing you need to know before you discuss programming languages is the concept of Turing completeness. If a language is Turing complete, it means that programs written in the language can perform the same things as a program written in any other Turing complete language.

It might surprise you that most probably, all programming languages you've ever heard of are Turing complete. That means that most probably, a program written in any language you've heard of can accomplish the same things as a program written in any other language you've heard of.

This, in a sense, means that you will never come across a situation where you can't write a particular program because of the language you're using. It might be complicated to write that program in your language, but it will never be impossible.

Now, on to how programming languages can differ.

495

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

STATIC VS. DYNAMIC LANGUAGES

Your physical computer runs on a language which pretty much just consists of numbers. Loads and loads of numbers. When you program in Java, you do not type numbers. The things you type when you program needs to somehow be converted to these numbers that the computer can churn. The language that your computer speaks, that just consists of lots and lots of numbers, that language is called machine code. Machine codes are different between different computers.

Static languages

Examples:

  • Assembly

  • C

  • C++

  • Fortran

  • Pascal

  • Objective-C

  • Haskell

  • Go

(List 1)

One simple way would be to just take all the code that the programmer has written, and translate it to numbers that mean the same thing. This step is usually called compilation. Then you can execute the program, which now is essentially just a long list of numbers. These numbers are the machine code for your particular computer. Languages which do this compilation are called static.

When you have this translation separately, you can perform a lot of analysis on the code before turning it into a runnable program. Static languages generally prefer to signal errors and add code and definitions during compilation, rather than when running the programs. (That is by the way the real technical version of what a static language is: a language that is trying to signal errors and define stuff in the code before the program is even run.)

Dynamic languages

Examples:

  • Python

  • Scheme

  • Ruby

  • Perl

  • PHP

  • JavaScript

  • Common Lisp

(List 2)

Another solution could be to have some kind of interpreter running on the computer, which reads your code directly and does the corresponding right thing on your physical machine. Now, you never translate to numbers in between, the interpreter does the right thing based directly on what code you typed. You never get a separate file for the compiled program, but you just feed your code directly to the interpreter. Languages which do this are called dynamic.

When feeding the code to an interpreter, you usually don't do much analysis on the code before running it. If there is an error in the code, it will usually not be signalled until you're trying to execute the line of code that contains the error. In dynamic languages, you can sometimes even extend the code or add definitions and such things when the program is running. (So this is the real technical version of what a dynamic language is: a language that post-pones signalling of errors until you actually try to execute the bad parts of the code, and a languge where you can alter and add definitions of functions and things while the program is running.)

Common Lisp is an interesting outlier here, because it is a dynamic language in that it postpones signalling of errors and it has an advanced macro system which allows you to change code run-time, but it is fairly common to compile it to machine code.

Languages compiled to bytecode

Examples:

  • Java

  • C#

  • Erlang

  • Scala

  • F#

  • Clojure

  • Flash ActionScript

(List 3)

There is, however, a third way. You could do a combination of the two. You could compile the code into machine code which is not meant for your machine, but for a "virtual" machine running on your machine. (Yo dawg...) This is called compiling into bytecode. Java does this, for example. When you compile Java code, it does not turn into machine code for your physical machine. It turns into bytecode for the Java Virtual Machine. Then the virtual machine acts as an interpreter for the bytecode. There is no proper name for languages of this class, you usually just say that they "compile to bytecode."

Generally, static languages have sorter execution times than languages compiled to byte code. Dynamic languages are the slowest of all. There are exceptions. Java, for one, is unexpectedly bloody quick, due to several features which have been fine tuned and amazingly optimised over time. Java beats many static languages as far as raw speed is concerned. That is by the way one of the few things with Java that impress me.

Edit: I rephrased a little of the static/dynamic sections to highlight the real difference. Thanks to /u/blablahblah for pointing the difference out.

413

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

COMPARING TYPE SYSTEMS

As far as your computer is concerned, everything is just numbers. Everything can be converted to numbers, and reasoned about as numbers. Text is numbers, images are numbers, music is numbers, films are numbers. Everything is just numbers man.

Now, think about the following snippet of code (in no particular language):

a = 6
b = 1.414
return a + b

(Snippet 1)

What should be returned? If we pretend our computer can only store integers (which is as close to the truth as you'll get), how does it store b? And how does it know that it should convert both a and b to the same format before doing the addition?

This is where type systems come in. In Java, the previous code would look something like this:

int a = 6;
double b = 1.414;
return a + b;

(Snippet 2)

Now, we have included extra information. Now, Java will know that a is an integer and b is a floating point number. Java knows how to deal with the addition now, and to avoid losing precision, it will first convert a to a floating-point number and then perform the addition.

This is essentially what a type system does at its core. It provides the computer with a way of doing the right thing for the right kind of value. There are a few different approaches to type systems though. Let's first look at what kind of problems can occur.

Pretend you have the following snippet (in no particular language):

age = 43
name = "Vincent"
return age - name

(Snippet 3)

Now this doesn't make sense. At all. As a human, we quickly see that you never subtract a name from an age. It doesn't mean anything at all. This is wrong. This is an error.

The type system can catch this. If the type system knows that age is a number and name is a string, the type system can say, "Hey, you're trying to subtract a string from a number. You can't do that, fool!"

How do different kinds of type systems deal with this?

Static type systems

Examples:

  • C

  • Java

  • Haskell

  • C#

  • C++

  • Scala

  • F#

  • Objective-C

  • Go

(List 4)

As you remember, static languages were all about translating your code into machine code, or compiling your code. As a part of this compilation, you might want to look into conflicts among the types. In a language with a static type system, the compiler will say, "Hey! Stop! I can't do this!" if it encounters the code in Snippet 3. It will refuse to compile the program until you fix the error.

When you program in languages with static type systems, the compiler will refuse to compile your code until you have fixed possible type errors. Depending on how you view this, it might be either a benefit (you can't compile programs which are wrong somewhere) or a drawback (you can't compile programs which you as a human know are right, even though they look wrong to the computer.)

Dynamic type systems

Examples:

  • Python

  • Ruby

  • Common Lisp

  • Scheme

  • Clojure

  • JavaScript

  • PHP

  • Erlang

  • Prolog

(List 5)

As you might be able to guess, a dynamic type system is the counterpart to a static type system. When the type system is dynamic, it essentially means that type errors will not be caught by any kind of compiler. If you were to run Snippet 3 in a language with a dynamic type system, it will happily chug along until it hits the offending line.

As with a static type system, if this is good or not depends on how you view it. Some people like being able to run a program which contains some dubious code because they know the code is really correct, or because they know they won't execute that bit of code anyway. Other people prefer that the compiler tells them immediately where the code looks suspicious.

Strong vs. weak type systems

It is easy to think that a "weak" type system is bad, and that a "strong" type system is good. This is absolutely not the case. The strength of a type system simply indicates how minor errors it will trip up on. Technically, the following is wrong, from a type system perspective:

5 + 9.3

(Snippet 4)

It is "wrong" because you're trying to apply the addition operator to values of two different types. It is a very minor "error" so only a very, very strong type system will refuse to compile/crash at that line. A slightly weaker type system will do what is probably "the Right Thing" in that situation and produce the floating point value 14.3.

However, even a weaker type system might trip up on something like what you say in Snippet 3. There are however really, really weak type systems that would allow that thing to go through as well.

Examples of languages with very weak type systems:

Examples of languages with pretty strong or very strong type systems:

  • All the others.

JavaScript is notorious for its weak type system. If you haven't seen it yet, I recommond you watch The Wat Talk which makes fun of the weak typing of JavaScript. I'm not saying weak typing is bad, mind you. To each their own.

(More to come.)

386

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

IMPERATIVE VS. DECLARATIVE PROGRAMMING

You can divide programming languages (or methodologies, really) into two very broad categories. When you write code, you can do it either imperatively or declaratively. In many languages, you can do either, but all languages I have used have leaned to one style, and trying to do the other in those languages is not always the best idea.

Imperative programming

Examples:

  • Java

  • C

  • C++

  • Assembly

  • Pascal

  • Objective-C

  • Go

  • Python

  • Ruby

  • Perl

  • PHP

  • C#

(List 6)

You will recognise imperative programming form your Java experience. When programming imperatively, you pretty much write down a series of steps the computer must take to give you the result you're looking for. Programs tend to be of the form

do this
then do this
then do this
if not this
    do this
else
    do this instead
then do this
and then this

(Snippet 5)

For imperative programming to be useful, you need variables with values which can change over time. This might seem like a strange remark to you, coming from Java, but it's not as obvious as you might think.

Imperative programming relies on having some kind of representation of the state of the program, and then being able to modify that state. This is usually accomplished with changing the value of variables. This has been the dominant style to write programs since the conception of computers, pretty much. This is the way machine code works too, so yeah, it has a pretty deep tradition in computing.

To give you a very rudimentary example (this is of course ridiculous, but I'm very bad at examples so bear with me), this would be a very imperative way to calculate a mathematical expression:

x = 3
division = f(x)
division /= df_dx(x)
x -= division

(Snippet 6)

You might or might not recognise that this is a very basic implementation of parts of the Newton–Raphson method. It contains two variables which it changes during the course of the program to achieve a result. It changes the variables through a "do this; then do this; and then this" pattern of instructions. Don't worry too much about what the lines do if you're not familiar with Newton–Raphson. It's just an example.

Declarative programming

Examples:

  • Common Lisp

  • Haskell

  • Scheme

  • Erlang

  • Scala

  • F#

  • Clojure

  • Prolog

(List 7)

Whereas imperative programming was about stating a series of steps to take, when programminging declaratively, you try to describe the values you're looking for as accurately as possible. Instead of saying "do this; then do this; and then this", you strive for something like:

doing A is the same thing as doing F(X)
doing F(A) is the same thing as doing G(A, H(3, A))
doing G(A, B) is the same thing as doing A + B
and doing H(A, B) is the same thing as doing G(A, B) + B

When programming declaratively, you try to compose descriptions of problems instead of listing the steps required to solve the problems. When programming this way, you don't need variables which can change with time. All the variables in your program can have the values they started with. For ever. Having variables which don't change comes with a lot of benefits if you're trying to write programs which can run several instances of itself simultaneously; you don't have to worry about instances trashing each others variables, because you can't change variables anyway.

The mathematical expression would declaratively look something more like:

x = 3
new_x = x - f(x) / df_dy(x);

Instead of supplying each individual step, I compose all the steps onto a single line of code, saying, "Calculating new_x is the same thing as calculating this expression." The expression will then be further divided into pieces by the compiler/interpreter, and I don't have to worry about doing that manually.

As you might realise now, mathematics are usually partly programmed declaratively, even in traditionally imperative languages.

Summary on imperative vs. declarative programming

The summary usually given is the following:

Imperative programming is about describing how to do something. Declarative programming is about describing what something is.

The two types of programming have different benefits and drawbacks, of course.

(There's more.)

353

u/kqr Jun 09 '12 edited Jun 11 '12

PROGRAMMING PARADIGMS

Paradigm is a word you'll hear every now and then. It essentially refers to a mindset you have when writing code and solving problems. There are really 7982349 different paradigms out there, so I was thinking I could maybe summarise the ones I feel are the most important ones to know. You will see this topic relates a lot to the previous one, and that is because imperative and declarative programming are really paradigms, but with several sub-paradigms under it. I made them a separate topic because I think they're very important.

Sequential programming

Examples:

  • Assembly

  • BASIC

(List 8)

This is the paradigm that is absolutely closest to the physical machine. Sequential programming languages are languages where the program is just a huge, huge list of instructions to perform, one after the other. If you want a loop, you have to specify that pretty much as "Start over from instruction number 37." If you do not explicitly jump to another instruction, the computer/interpreter will just continue on and execute the next instruction in the list.

Structured (or procedural) programming

Examples:

  • C

  • C++

  • Pascal

  • Go

(List 9)

This is a step up from sequential programming. Structured, or procedural, programming implies that you have access to some control structures. You don't have to jump to a particular instruction, because you can use an if–else block. You can even loop using something like while. And you can define and call functions/methods/procedures (whatever you want to call them.)

Functional programming

Examples:

  • Common Lisp

  • Haskell

  • Scheme

  • JavaScript

  • Erlang

  • Scala

  • F#

  • Clojure

(List 10)

Now this you mentioned in your submission. Functional programming is not related to sequential or procedural programming. Functional programming is essentially the embodiment of declarative programming. You define functions in terms of other functions, and then in the end, the thing you want to do is preferably just functions applied to functions applied to functions.

Functional programming tends to allow you to do very funky stuff with functions, which makes life easier for some types of problems.

Logic programming

Examples:

  • Prolog

(List 11)

This must be one of the stranger paradigms. In logic programming, what you essentially do is state a the rules that your solution must comply to, and then the interpreter finds a solution for you. By itself. It can be really powerful when mastered and used correctly.

Object Oriented Programming

Examples:

  • C++

  • Objective-C

  • Python

  • Ruby

  • PHP

  • JavaScript

  • Scala

  • Common Lisp (thanks to /u/sepok)

(List 12)

You're probably pretty aware of this paradigm already. The essentials of it is that it's trying to solve some of the problems with procedural programming by encapsulating stuff inside independent sections called "objects." Then there are some fancy features which allow you to do some pretty neat stuff with objects to save lots of sweat.

Parallell programming

Examples:

  • Haskell

  • Erlang

  • Scala

  • Clojure

(List 13)

When making programs which should run on many processors and many computers at the same time, you run into a whole class of new problems, many of which are really difficult to solve. This is where the front of programming language research is right now. If you want to become invaluable as a programmer in a few years, learn this shit properly.

Parallell programming are all the ways you can reason about programming for multiple CPU's/machines without data corruption and other nasty problems.

(I'll try to wrap this up now.)

356

u/kqr Jun 09 '12

ABSTRACTION

When you take something hairy and complicated and wrap it in a nice package, you have just abstracted away the scary thing into something manageable.

Think about how complicated a car really is. You've got the engine, the exhaust system, the ignition, the fuel tank, the cooling, the oil, the differential, and a lot of things I can't even pronounce. Still, driving a car isn't scary. Why is that? It's because all those hairy details are abstracted away, and all the driver sees is a wheel, some pedals and a stick, pretty much.

Abstractions are all around when you're programming.

With no level of abstraction, you're writing machine code. You enter numbers manually, the very same numbers your computer speaks. If you abstract away those numbers, you could perhaps use letters instead of numbers. You get assembly.

If you abstract away the hairiness of assembly further, you might get a low-level language such as C. C is pretty comfortable to work with, but you're still exposed to some of your computers internals. You can abstract away more of those, and you arrive at something similar to Java.

If you provide abstractions over Java, you get something like C#. Provide abstractions on C#, you get Python. Provide abstractions on Python, you get Haskell.

When someone talks about a "high-level" or "low-level" language, don't listen. Put your hands on your head and hum loudly. Those are two very confusing terms. What they essentially mean is "a high level of abstraction" or "a low level of abstraction." But what is a high level of abstraction, really? Is Java at a high level of abstraction? Is Python at a high level of abstraction? As it turns out: it depends.

I would say that Python is at a higher level than Java, and by that I mean that to make Java more like Python, you will have to add layers of abstraction. On the other hand, I would say that C is at a lower level of abstraction than Java, and by that I mean that to make Java more like C, you will have to remove layers of abstraction.

To go back to the car analogy, I would say a car with automatic transmission is at a higher level of abstraction than a car with a manual gearbox. With an automatic gearbox, you're essentially letting the computer do some of the work you previously did. The computer might not do it as good as you, but to some people that tradeoff is worth it, because it means a lot to them that they don't have to shift manually.

This means that there is no such universal thing like "a high level language is better than a low level language" or "a low level language is better than a high level language." In higher level languages, development times tend to be really quick, because the programmer doesn't have to do as much manually. On the other hand, in lower level languages, execution times tend to be quicker, but the program itself also takes much longer to develop.

What you prefer is completely up to you. (Or your project leader.)

345

u/kqr Jun 09 '12

WHERE TO GO NEXT?

I know this might have been an seemingly endless rant without answering any of your questions, but if you have anything specific to ask about now, please do. I can answer almost anything relating to what I've written, and if I can't, then I'm sure someone else on here can.

I have experience with most paradigms and types of programming. I have a fairly good understanding of the computer internals and what happens at a very low level as well as how to compose stuff at a higher level. I have toyed with all the paradigms I have mentioned, and most of the languages I've mentioned.

Personally, I have trouble standing programming in Java, because I feel it is on a much lower level of abstraction than I want. I rarely want performance, so that usually isn't a matter to me and I prefer to stay at as high a level of abstraction as possible, which to me means declarative/functional programming.

Haskell amazes me with it's level of abstraction. It's unbelievable how composable stuff in that language is.

(And no. I have not proof-read all this yet. I usually do on reddit but this is helluva lot of text.)

123

u/D_day Jun 09 '12

This should be added to the FAQ.

23

u/zzyzzyxx Jun 10 '12

I plan on doing just that.

→ More replies (2)

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?

→ More replies (0)
→ More replies (11)

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.

→ More replies (4)
→ More replies (1)

6

u/beardless_captain Jun 10 '12

Thank you man! Really, thank you. I got in the thread expecting a few lines answering the question and pointing out some examples and I face this and I'm simply overwhelmed.

I don't know any background of yours or anything but people like you, who has the same kind of interest -- and I can tell, passion --, even though I'm just a beginner, inspires me to go and learn even more stuff. A big cheer to you.

5

u/Plithe8 Jun 10 '12

You just wrote over 8 pages of text.

→ More replies (13)

5

u/commonslip Jun 10 '12

Eh, in practice, Common Lisp is not that declarative. I wish it was.

→ More replies (1)

11

u/LALocal305 Jun 10 '12

The Wat Talk

Thank you so much for linking to this! It is hilarious.

10

u/VancitySwag Jun 09 '12

TL; Read it anyways

thanks for the explanation

→ More replies (12)

10

u/blablahblah Jun 10 '12

I've always seen this referred to as compiled vs. interpreted. However, this is related to the behavior of the specific implementation of the language and not the language itself. You could write a C interpreter if you wanted to.

Static vs. dynamic languages refer to whether the language has features to let you modify the program during run time. Common Lisp is a dynamic language even though it is compiled. You could do the same things in any Turing-complete language but it's much harder in static languages

7

u/kqr Jun 10 '12

I had a lot of doubts myself when writing that section. The difference between the set of compiled languages and the set of static langueages is so small. I'll think about ways to reword it. Thanks for bringing it to my attention.

15

u/SwimmingPastaDevil Jun 10 '12

These are incredibly detailed answer. Thanks for taking the time to type alll that.

I made a pdf from your answers mainly to read at a leisurely pace. Here is a link, if anyone is interested.

Link

5

u/ultragnomecunt Jun 10 '12

Should be put in the sidebar/FAQ!

7

u/[deleted] Jun 10 '12

Too Long!!

But after reading the first quarter, I could not stop. I read all the posts word for word and this is not the last time I read through these words.

Thank you for taking your time and explaining everything in such a simple easy to understand manner.

I wish Reddit allowed me to give more than 1 karma per post.

5

u/allthatjizz Jun 10 '12

Holy cow... I like how you broke this into several posts so I can upvote each of them.

→ More replies (16)