Programming paradigms that change how you think about coding

http://brikis98.blogspot.com/2014/04/six-programming-paradigms-that-will.html

by niels • 12 years ago

523 199 12 years ago

brikis98.blogspot.com

simias4• 12 years ago

In the "concurrent by default" section I would add the hardware description languages like VHDL and Verilog.

Learning Verilog was an eye opening experience for me. It reminded me of the time I switched from unstructured BASIC to C when I was a kid. At first it seems complex and weird then suddenly it clicks and it all starts making sense.

adwn6• 12 years ago

... and then suddenly you realize what a horrible, horrible language it is. I'm not exaggerating, it isn't even well-suited for the domain it is mainly used for (i.e., designing digital hardware circuits). For example:

1) Synthesis/simulation mismatch: Your design might work in simulation but not in hardware, and vice versa. Often, this is due to X-value (representing unknown/invalid values) problems.

2) Signed datatypes: If you mix signed and unsigned values in an expression, the result is unsigned. So, if a is unsigned and has the value 4, b is signed and has the value -3, then

  (a * b) < 5

will return 0 (false), while

  ($signed(a) * b) < 5

will correctly return 1 (true). That's because signed datatypes are just an afterthought and weren't officially introduced until 2001, more than 15 years after the language's inception.

3) If an undeclared net is used in an module instantiation, the compiler silently creates a 1 bit net with that name. No error message, no warning. You can turn off that stupid behavior with a compiler directive, but you have to turn it back on at the end of your file, because otherwise its effects are active in all files compiled afterwards, and many third-party sources don't work correctly with this setting.

VHDL is also a bad language, but for very different reasons. And yet, alternative HDLs have a hard time getting traction, for various reasons and non-reasons.

Igglyboo• 12 years ago

I wholeheartedly agree.

I'm a CSE Major and I took a hardware design class last fall, we programmed and Xilinx FPGA using VHDL.

It was a huge change from everything I had learned before, I had no idea what a latch was and why it was bad to imply them. The thing that bothered me the most was the simulation/synthesis disconnect, the only efficient way to debug a program is by using the simulator because debugging it on the board takes a very long time when changing code. But even after you've debugged it in the simulation it might not even synthesize, which is an even harder "bug" to debug.

swah2• 12 years ago

I really enjoyed writing VHDL. I don't remember having problems with unknown values: we used only '0' and '1' for anything that's supposed to be synthesized.

(For testbenches, everything goes..)

     Value set is ('U','X','0','1','Z','W','L','H','-')
     TYPE std_logic IS ( 'U',  -- Uninitialized
                         'X',  -- Forcing unknown
                         '0',  -- Forcing 0
                         '1',  -- Forsing 1
                         'Z',  -- High    impedance
                         'W',  -- Weak    unknown
                         'L',  -- Weak    0
                         'H',  -- Weak    1
                         '-'); -- Don't care

     SIGNAL stdLogicName : STD_LOGIC:='0';
     stdLogicName <= 'Z';

simias4• 12 years ago

Oh I agree, while writing verilog I was amazed people used it to develop something as critical as ASICs. The language is way too forgiving. And it's not like you can release a patch once the thing is on the silicium unless you're working with FPGAs. It was still very interesting to see how hardware was designed and definitely an enlightening experience as far as I'm concerned.

I found verilog very similar to C in a way, if you're not familiar with all the quirks of the language it's very easy to write code that looks completely benign and straightforward and yet ends up blowing up in your face because of an implicit cast or undefined behaviour...

On the other hand there's not much of a "hacker scene" for driving up the innovation for HDLs, unfortunately. And I don't expect the big companies making ASICs and FPGAs to come up with a radical new solution any time soon.

So basically, if one of you HNers want to try their hand at writing a new programming language, consider designing a modern Verilog instead of yet an other Javascript transpiler :)

marcosdumay2• 12 years ago

Well, #1 is a problem of the tools, not the language.

noobiemcfoob4• 12 years ago

The problems you mentioned are all easily bypassed by design guidelines.

1) (At least at the X's point) Don't build designs that rely on X behavior or could result in X behavior. Where I work, X's are completely unacceptable and a sign that something is broken. In general, if writing Verilog to model hardware, don't write non-synthesizeable constructs.

2) Signed datatypes don't make any sense when designing hardware. Verilog treats everything as bit vectors. While 2's complement can implement signed behavior, hardware doesn't know or care about signed types. Again, if modeling hardware, write code that models hardware.

3) This is annoying, but another issue that is stepped around with design practices and not a major problem.

Overall, when talking about Verilog, you have to keep in mind its a language built to model hardware. Most features of modern languages don't make much sense in that context.

ShellfishMeme• 12 years ago

It also kind of reminded me of Pi calculus (http://en.wikipedia.org/wiki/Pi_calculus). It's pretty fun to play around with and try to understand and replicate those examples on the page.

bru• 12 years ago

Some notes:

- parallel and concurrent are 2 different things

- the 'symbolic languages' definition seems off. Wikipedia puts it right:

symbolic programming is computer programming in which the program can manipulate formulas and program components as data

So it's not "using graphs & such to program"

vkjv• 12 years ago

If you want concurrent by default, try an HDL. :)

noobiemcfoob4• 12 years ago

I had the same thought. I find it odd he didn't mention them.

seanmcdirmid6• 12 years ago

Mathematica is a good example of a symbolic language (can't get more symbolic than term rewriting), but he calls that....knowledge oriented or some other nonsense.

Orangeair• 12 years ago

Mathematica[0] and The Wolfram Language[1] are two different things. The Wolfram Language is a sort of extension of their Wolfram Alpha service, which Wolfram itself describes as "Knowledge Based." Mathematica is still just Mathematica.

[0]http://www.wolfram.com/mathematica/

[1]https://www.wolfram.com/language/

coldtea• 12 years ago

parallel and concurrent are 2 different things

That should be an implementation detail as far as the programmer is concerned. And languages should strive for parallelism anyway, not merely concurrency.

tel6• 12 years ago

The idea that parallel code is executed through a concurrency mechanism should be hidden, but it doesn't mean that the distinction between the two should be.

http://existentialtype.wordpress.com/2011/03/17/parallelism-... http://existentialtype.wordpress.com/2014/04/09/parallelism-...

ExpiredLink2• 12 years ago

@see http://www.reddit.com/r/programming/comments/22nhb2/six_prog...

for some valid critique.

tokipin• 12 years ago

Take this[1] for example. That's a regular Mathematica notebook. You can insert images (like drag & drop them from your desktop) directly into notebooks. It's actually very convenient for image processing. The same thing holds true for things like the graphical output of plotting functions, which retain their underlying vector data.

The symbolic paradigm isn't necessary for this, but it makes it easier. Implementation-wise these things requires less "special case-ing" than you would think because the symbolic paradigm in essence encourages your representations to be naked. Thus images, plots, etc are not "black box" items. They're structured data represented in the same language, but which the frontend happens to display in visual forms.

(Code itself is also data, except that if a symbol in the data has an associated transformation rule, that transformation rule is applied. This mechanism is how you make data do 'variables' and 'functions'. These variables and functions work more or less the same as they would in a common programming language, but the underlying mechanism is nothing but data transformations.)

[1] http://reference.wolfram.com/mathematica/ref/EdgeDetect.html

brikis98• 12 years ago

Thanks for the feedback. I updated the post with notes that mention these corrections.

Blahah• 12 years ago

The concurrent by default paradigm looks like it could be really useful for some cases. Does anyone know of any more well-used languages that support it?

maaaats• 12 years ago

It's a "well-used language" in academic contexts, but probably not exactly an answer to your question ;) Anyways, in OZ[1] you can just add thread <x> end around code x, and it's concurrent. It will wait for all bindings to be resolved before continuing.

It's a pretty cool language with a lot of paradigms one can easily try out.

[1] http://en.wikipedia.org/wiki/Oz_%28programming_language%29#D...

simias4• 12 years ago

As I mentioned in my other comment Verilog and VHDL are "concurrent by default" since that's how hardware works anyway.

If you want to experiment with them you don't need an FPGA, you can just start with a simulator such as Icarus Verilog[1] and a waveform viewer like gtkwave[2] and get a feel of the language. There are a bunch of tutorials on the net.

[1] http://iverilog.icarus.com/ [2] http://gtkwave.sourceforge.net/

GotAnyMegadeth• 12 years ago

Verilog is Turing complete and can do standard IO, so you probably don't even need a simulator/wave viewer.

krupan• 12 years ago

http://www.edaplayground.com/ is a great way to play with hardware description languages too. You don't need to install anything.

Serow225• 12 years ago

Is Labview concurrent by default?

mjcohen• 12 years ago

Yes. I enjoyed watching LV code execute graphically.

jberryman• 12 years ago

Haskell's Par monad gives you a nice eDSL that lets you lay out your data dependencies and have things evaluated in parallel

http://hackage.haskell.org/package/monad-par-0.3.4.6/docs/Co...

z3phyr• 12 years ago

Since 'functional' is not mentioned, I will assume that it is mainstream now!

nly2• 12 years ago

Or maybe it just won't 'change the way you think about coding'

lomnakkus• 12 years ago

I think that depends a lot on what you mean by "functional". If "functional" means "everything is immutable" then I can guarantee that you'll learn a lot by programming that way. If you mean "first-class functions" then I cannot -- although you still might. You could probably program in Scheme (say) as if it were C with side effects all over the place, but that wouldn't teach you anything except a different syntax. OTOH, coding something non-trivial in Haskell would teach you a lot -- even if you don't end up using/liking it.

(Aside: I was somewhat disappointed by the blogger calling out the "Wolfram Language" as something special or to be admired. It's a ridiculous ad-hoc hodgepodge of a language. I stress the word language.)

ChrisGaudreau• 12 years ago

If you don't know FP and you learn FP, then it will almost certainly change the way you think about coding.

Dewie5• 12 years ago

One could say that it goes under declarative

marcosdumay2• 12 years ago

And concurrent.

bnegreve2• 12 years ago

According to Wikipedia, functional programming is an example of declarative programming [1], which is mentioned in the article.

This is not immediately obvious to me, here's why (from the same wikipedia article [1]):

While functional languages typically do appear to specify "how", a compiler for a purely functional programming language is free to extensively rewrite the operational behavior of a function, so long as the same result is returned for the same inputs. This can be used to, for example, make a function compute its result in parallel, or to perform substantial optimizations (such as deforestation) that a compiler may not be able to safely apply to a language with side effects.

[1] http://en.wikipedia.org/wiki/Declarative_programming

cjfont• 12 years ago

Seems pretty obvious to me, since the above description could also apply to your typical declarative languages such as SQL, where you also rely on the database to do optimizations based on a description of the result you're looking for, rather than procedures for calculating it.

tel6• 12 years ago

I'm pretty happy hoping that it's because we're beginning to realize that "functional" is not a terrifically descriptive term.

Xophmeister2• 12 years ago

The second paragraph:

This is not your grandma's "functional programming will change the world!" blog post

Presumably because a lot of people write blog posts about how FP will change your approach. That's true but, while I wouldn't say FP is mainstream, it's well-known in circles such as ours; whereas the topics he mentions are much less run-of-the-mill. It makes for a more interesting and original read.

I notice he didn't include array-based languages, like APL and J. They were flavour of the week here a couple of weeks ago, but you still don't get much written about them and they would fit nicely in this article.

copx• 12 years ago

I think your perception of what is "well-known" strongly depends on your age. For example neither concatenative nor declarative programming are exotic to me and I think many other older programmers.

Forth (concatenative) used to be pretty big, back then software was simpler and you did not need a Qt wrapper, XML parser etc. Forth was very practical for the things it was originally used for. Like that embedded control software for a telescope where the "user interface" consisted of a few buttons, as in physical buttons, no screen, no mouse, no harddisk, no network connection to worry about. In that environment Forth made a lot of sense, on a modern computer, as a tool to write a modern GUI application it makes no sense at all if you ask me.

And "declarative".. Prolog is old, back then it was usually called "logic-based programming", though.

Really, Forth and Prolog, every older guy who cares about programming knows those fellas.

And Prolog did not change the way I think about programming at all. I considered it breathtakingly clean and elegant (compared to C and Pascal).. for the few things it was good at (e.g. expert systems).. but utterly unsuitable as a general-purpose language / paradigm. I felt the same way about Standard ML (it was the dominant FP language before Haskell became big). "Wow, writing a simple input/output transformer (e.g. academic compiler) or doing some basic math is so clean and elegant with this! Everything else.. not so much."

In contrast, Forth actually changed my thinking. According to Charles Moore, Forth's creator, proper software development with Forth meant finding just the right set of words, the right vocabulary, for the problem domain. Once that was accomplished writing down the program logic became trivial. Note that in Forth functions are called "words", are usually very short, and indeed word-like. So you end up with code like "ARM 90 DEGREES ROTATE".

As I said my approach to programming was changed by the exposure to Forth. I aim to discover/define an efficient "vocabulary" for the problem domain in every language. That is not the same as designing a "domain-specific language" by the way. DSLs usually go much further, making up a syntax of their own. I do not like DSLs at all. Mostly because of the associated learning curve forced upon you by every new DSL and by the usually poor tool support.

EDIT: Removed needlessly trollish part

snorkel• 12 years ago

10 Ways Buzzfeed-style Headlines Will Forever Be Annoying

cshimmin• 12 years ago

Honestly, my facebook feed has trained me to simply never click on any article that begins with a number.

jameshart• 12 years ago

This is a substantial piece of writing with information many here would find interesting; putting it behind a buzzfeed list style headline does it a disservice. One step short of calling it "Six weird programming paradigms that will blow your mind".

nly2• 12 years ago

I thought it was a tiny but deliberate master-stroke of tongue-in-cheek irony. Or maybe the author was really after that buzzfeed crowd ;) I any case, I bet I wasn't the only one who thought "well, HN is going downhill fast" first, and came out glad my prejudices were tested.

weland• 12 years ago

It also includes quite some information that isn't exactly right.

notduncansmith• 12 years ago

My first thought was "How this 36-year-old mom learned to code with one neat trick!"

andrelaszlo• 12 years ago

Changing paradigms has to change the way you think about things, by definition. By the scientific definition of "paradigm", at least, but I think it's no less true for programming paradigms.

chriswarbo3• 12 years ago

I think the idea is that we usually don't change paradigms. However, by broadening our perspective we can gain insights into our existing code. An example of a paradigm that won't change the way you think about code is a cyclic tag system. You might find it interesting to know about, but I doubt that knowledge would change the way you write code.

As a concrete example, learning pure functional programming gives me another perspective on the OO code I write; ie. that methods are functions where the first argument is the implicit "this" and the body of the function contains a top-level pattern-match on the class tag. This perspective has helped me avoid over-complicating my code at times.

glifchits• 12 years ago

Just because Buzzfeed uses list style headlines and has vacuous content does not mean that list style headlines are an indicator of vacuous content. If you read this and you liked it, does the title really matter?

zwieback2• 12 years ago

Exactly. Plus, while the content might be vacuous it's often quite entertaining and the editorial style is genius, in my opinion. I think writers can probably learn 41 things from Buzzfeed.

cowls• 12 years ago

I read it, and how I think about coding remains the same as before I read it.

mcherm• 12 years ago

I don't think the idea was that reading the article would change how you thought about coding. I believe the point was that trying out these unusual programming paradigms would change how you thought. For the cases on his list that I have tried (declarative programming and Forth/Joy) I have found that to be true.

I would add object oriented programming (eg: smalltalk), macro programming (eg: lisp) and functional programming (eg: Haskell) to the list of things that change your thinking, but since most of the article's prospective audience has already heard of those I was happy that he stuck with paradigms that are LESS well known.

lolo_• 12 years ago

I think an underrated non-standard approach to programming is graphical programming. Though this approach doesn't seem to received significant uptake amongst professional programmers, there is an application called max [0] that is popular amongst musicians and artists and quite surprisingly powerful and effective.

There's an interesting article [1] on how Jonny Greenwood of Radiohead uses it extensively, in there you can see some examples of how it works - modules wired together visually.

I think there is a lot of potential for a really nice mix between text-based programming and graphical programming to work for general programming too.

[0] http://cycling74.com/products/max/ [1]:http://thekingofgear.com/post/25443456600/max-msp

prawks• 12 years ago

The digital media department at my alma mater used Max/MSP to teach programming to art students with a lot of success. It's really fascinating to watch the programs as they run, and it makes for a great way to visualize abstraction and separation of concerns in a concrete way.

adambard• 12 years ago

My degree included a "Computer Music" option, which were a few classes that were half music students and half computer science ones. We used Max/MSP quite a bit.

For anyone that wants to play around with a very similar language, PureData is an open-source application that is a relative of Max/MSP (they share a creator, and are quite similar). Not wanting to come in to do the homework or purchase the software myself, I used it quite a bit.

http://puredata.info/

humanrebar2• 12 years ago

I've used graphical programming in the past. It sounds amazing in abstract, but ends up being a mess when it is implemented. It basically requires a "sufficiently smart editor", which, even if implemented perfectly, would not leave a lot of room for a third-party ecosystem to be built around the language.

There are many solved problems in text-based programming that would need to be resolved in order for a graphical programming language to be as useful.

How would one post a "snippet" to StackOverflow? How would diffs work? Consequently, how would source code management work?

tarblog• 12 years ago

The solution that comes to mind is that the graphical elements are backed by text for these purposes. Then, the graphical interface amounts to an editor for this meta-language.

mmaldacker• 12 years ago

Graphical programming is also popular for animation/cgi/special FX, e.g. XPresso in Cinema4D.

JupiterMoon2• 12 years ago

Isn't "Dependent types" just re-inventing how Fortran handles non allocatable array and character variables i.e. those who's length is declared at compile time using a parameter?

octo_t• 12 years ago

That's just one use of dependent types (and the easiest one for an audience to understand).

JupiterMoon2• 12 years ago

But it is the only one described in the article.

patrickmay• 12 years ago

Common Lisp also supports specialized type declarations like this. (In Common Lisp type declarations are optional.)

nbouscal2• 12 years ago

Common Lisp does not have dependent types. The example given is unfortunate because it often leads people to think they already have (and understand) dependent types, when that isn't the case.

nbouscal2• 12 years ago

The article unfortunately does quite a poor job of explaining what dependent types are and why they're valuable. They're a lot more complicated than just "storing the length of a vector in its type". Dependent types allow you to create types where one type in a signature 'depends' on the value of another type in the same signature. This is very powerful, but unfortunately easily understandable examples are still somewhat hard to come by.

tel6• 12 years ago

It's a bit more than that. Let's assume Vector is a typed list type of know length

    [1,2,3] : Vector 3 Int

we can write `append` which combines Vectors

    append : (Vector n a, Vector m a) -> Vector (n + m) a

which works as you expect because the expression in the type (n+m) is written in the value language.

Here's another (slightly pathological) dependent type. Normally `if` statements require that the then and the else branches result in the same type, but in a DT language you can write

    if' : (cond : Bool) -> a -> b -> (if cond then a else b)

In other words, `if'` takes the type where you first provide it a boolean, we'll call it `cond`, and then two differently type continuation parameters. The type of the result is an expression: "if cond is true then this is the type of the first continuation, otherwise this is the type of the second continuation".

Both of these examples would be proud to call themselves trivial. The DT rabbit hole goes very deep.

mcguire2• 12 years ago

Short answer: No.

Longer answer: Sort of. An array has an element type and length associated with it (and it ATS at least, the type-level length isn't kept at run-time) and that length is set when the array is created, and modified if elements are added or removed. However, functions can require parameter types or provide return values of "array T n | n > 0 && n < m" --- the array cannot be empty and has to be smaller than some limit.

There's a good deal more to dependent types, but they are much more flexible than simply attaching the length of the array to its type.

mjb• 12 years ago

Other languages to add to this list would be Dijkstra's Guarded Command Language, and Promela. Promela is especially interesting because of the (nondeterministic) execution semantics, which provide an extremely interesting way to model parallelism. In a similar vein, TLA+ is worth a look.

Both Promela (Spin) and TLA+ have active communities and have found fairly wide use in industry. They are generally used for model checking, model extraction by guided abstraction, and development by refinement, but can be used in a much more adhoc way to just experiment with parallel ideas.

SeanLuke2• 12 years ago

If you've used SQL, you've done a form of declarative programming

This is so wrong I don't know where to begin.

dllthomas11• 12 years ago

Per Wikipeda, "Common declarative languages include those of database query languages (e.g., SQL, XQuery), regular expressions, logic programming, functional programming, and configuration management systems."

http://en.wikipedia.org/wiki/Declarative_programming

"Wikipedia is mistaken" is totally a defensible position, but it should be defended, so please find a place to begin.

SeanLuke2• 12 years ago

Wikipedia is mistaken.

To me, in a declarative programming language you tell the computer what you want without exactly telling it how to achieve it. It's the compiler's job to figure that out. That classic example of a declarative programming language is Prolog.

In databases there are two traditional approaches to extracting queries: the relational algebra and the relational calculus. One of these (the relational calculus) is very clearly declarative: you essentially are saying "give me all students whose ID numbers are less than 1000 and who took a class from someone who is no longer a member of the faculty." The interpreter figures how what relational operations should be performed to do this.

The other option is the relational algebra, which to me is very obviously not declarative: you are telling the system exactly what to do, and giving it an implicit ordering (though just like in any procedural language it can change the ordering if it thinks it's a good idea). Thus in the relational algebra you'd say "get the table of students. Reduce it to those whose ID numbers are less than 1000. Join it with those students who took a class. Take the list of faculty. Reduce it to those who are longer teaching. Join that with the previously generated students relation. Project out just the student names."

The primary language for the declarative relational calculus is Datalog.

The primary language for the (non-declarative) relational algebra is SQL. Though SQL has a few extra gizmos added to compensate for the fact that it's less expressive than the relational calculus.

archena• 12 years ago

Why do you think SQL doesn't qualify? it's certainly not the only example of declarative programming, and maybe not the most interesting, but it is one which most developers have come across.

hibikir• 12 years ago

In theory, SQL is a declarative programming language, in practice, past the simplest of examples, there are dozens, if not hundreds of ways to ask the same question, and each one of them performs differently. The moment one starts to do things like add anonymous views, the declarative facade tends to disappear.

Let's also remember that many companies stuck with big RDBMs systems have entire teams of people whose job includes turning declarative statements into extremely procedural ones.

So in practice, writing a SQL statement has little to do with making a query readable, but with abusing knowledge of internals to make it work fast. So declarative, not so much.

milliams• 12 years ago

QML [1] is an interesting example of declarative programming. It allows constraints and relationships to be defined and the runtime will do the rest. Perhaps it's not as powerful as other languages but in its domain it does very well.

[1] https://en.wikipedia.org/wiki/Qt_Modeling_Language

general_failure• 12 years ago

QML is simply brilliant for developing UIs.

sirsar• 12 years ago

LabVIEW is concurrent by default; control flow is done by linking the outputs of one function to the inputs of another. This makes writing concurrent loops ridiculously easy: just put two loops next to each other.

I rarely use it because organization is such a pain, but its "data-flow" paradigm does simplify a lot of logic.

sesm• 12 years ago

Another example would be Bloom language. Here is a great talk explaining motivation for using "disorderly" languages in distributed systems: http://vimeo.com/53904989

bane• 12 years ago

Yeah there's a pretty large class of data processing tasks that are made pretty trivial by LabVIEW-likes visual dataflow languages. One I've seen for XML work that was pretty good was called "SDE"

http://www.futurepointsystems.com/?page=products

cdtwoaway• 12 years ago

Happy to see another LV user here.

Organization gets much, much easier once you get the big architecture concepts - produce/consumer patterns, messenger-queues, event structures, actor framework. Yes, it can be painful, but the newer functionalities (clean-up, riddiculously easy sub-vi creation,..) subtly improve it.

Btw: If you are using LabVIEW and have never used Quickdrop, try it. It is the most underutilized and amazing feature.

untothebreach2• 12 years ago

I was a little disappointed that Factor[1] didn't get a mention in the 'Concatenative' section. Its stack effect checker takes care of a lot of the problems he mentions, IMO.

1: factorcode.org

protomyth2• 12 years ago

Postscript is another excellent example of the type.

evincarofautumn• 12 years ago

“Stack checking” is definitely the ticket to maintainable stack programs. I have been working on a statically typed concatenative language called Kitten[1] off and on for a while, and while the error messages leave something to be desired, they can at least help you understand how data is flowing through a program, and of course rule out some bugs.

[1] http://github.com/evincarofautumn/kitten

untothebreach2• 12 years ago

very cool, I will definitely take a look at this

kitd• 12 years ago

Pointed out elsewhere, but ANI appears to be dead according to its own tutorial[1]. However Funnel[2] by Martin Odersky/EPFL does a similar job, with a more explicit nod to Petri nets which are usually used as the basis for concurrent systems.

[1] https://code.google.com/p/anic/wiki/Tutorial [2] http://lampwww.epfl.ch/funnel/

danielweber• 12 years ago

I'm in the midst of something else and can't pull out my C++11 book now, but doesn't C++ have custom types that would let you declare something like "this must be a positive integer"?

I might be confusing this with custom literals.

AnimalMuppet• 12 years ago

Well, there's unsigned integers. This means that it can't be less than 0. But if you have a 32 bit unsigned integer, and you decrement 0, you get 0xFFFFFFFF. That may or may not be what you want or expect.

You also could create a class that wrapped an integer, that would have a range, and would maintain that range as a class invariant. It could either clip or throw an exception when an attempt was made to go out of the range. But that's just regular class stuff, so I don't think it's what you had in mind...

jarrett5• 12 years ago

A thought on dependent types:

Can a dependent type system catch all type errors at compile time? For example, suppose I write the following (in pseudo-code):

  // Variable x is an integer greater than or equal to 0 and less than 256.
  int x (>=0, <256) 

  x = 128 // This is valid.
  x = x * 3 // This violates the type.

I can imagine how a compiler could catch that kind of error. But that's trivial. What happens in programs like this:

  int x (>= 0, <=10)
  x = parseInt(getKeyboardInput)

Now the compiler can't know for sure whether the type has been violated, because the value of getKeyboardInput could be anything. To take a page from Haskell, you could do something like this (which is still pseudocode, not valid Haskell):

  // x is a value that is either 1) an int from 0 to 10, or 2) nothing at all.
  maybe (int (>= 0, <=10) x
  
  // applyConstraint recognizes that parseInt may return a value violating x's contraints.
  // Thus it transforms the return type of parseInt from int to maybe (int (>= 0, <=10)
  x = applyConstraint(parseInt(getKeyboardInput))

Or perhaps applyConstraint wouldn't have to be called explicitly, but would be implicitly added by the compiler as needed. I'm not sure which is better stylistically.

Either way, applyConstraint would be required any time a computation could return an invalid value. That would get tricky, because the compiler would have to track the constraints on every variable, even where those constraints aren't declared. For example:

  int w (>= 0, <= 10)
  int x (>= 0, <= 2)
  int y
  int z (>= 0, <= 20)

  y = w * x
  z = y

Here, the compiler would have to infer from the assignment "y = w * x" that y is always between 0 and 20.

Do any languages currently take the idea this far (or farther)?

nuncanada• 12 years ago

Yes, Depently Typed languages can. They are full blown theorem provers...

JadeNB5• 12 years ago

Gödel guarantees that full-blown theorem provers, even with human guidance, cannot prove all true statements about sufficiently rich systems. 'Sufficiently rich' here just means 'includes Peano arithmetic', and you can find tons of tutorials for doing just that (Church encoding) in even the simplest type systems.

(This bit of pure-mathematics wonkery ignores the substance of jarrett's question, though; one doesn't need the full Gödelian power to observe that a priori theorems that must be verified at compile time can never account for data that are provided only after compilation.)

tel6• 12 years ago

Your idea about `maybe (int (>= 0, <= 10))` is exactly correct, but there's an important point to emphasize around it:

In a DT language when you express such a type the compiler will demand that you write a type like maybe which can fail at runtime and demand that you handle that failure.

To the compiler, `int` and `int (>= 0, <256)` are different types which require an explicit conversion (though the particular choice of conversion may be implicitly defined, viz. Idris' Coerce typeclass). In order to do multiplication like you suggested you would have to provide enough information to the compiler (either at compile time via constants or via a possibly failing mechanism which generates proof requirements at runtime) that your multiplication will not violate the constraints of the type.

To you final point about tracking constraints, even those defined implicitly, I think the answer is no-ish. Most frequently, DT languages have such a richness of types that there's no way to infer them—you're forced to write out all of the top-level types. But the idea of passing around constraints like you're suggesting here is not impossible.

You might imagine a pair type like (in no particular notation)

    (x, x => [Constraint])

where the first is a number and the second indicates a type-level function taking that particular number to a set of proofs that certain constraints are satisfied. We could indicate all of this at the type level and demand the compiler ensure that constraints are not violated (i.e. we end up coercing between constrained types like this and some coercions, those that coerce to supersets of the current constraints, are valid only) and we could also define a loose kind of (+), (*), (-) etc on this pair type such that the result passes along the proper constraints.

vilhelm_s3• 12 years ago

Agreed in general, but it is possible to enable this style of constraint propagation by being restrictive about what kind of contraints you can write. In particular, the "LIQUID" family of languanges that have been developed at UCSD allows properties which are conjunctions of LInear IneQUlites, and can infer them automatically. The programmer would annotate one declaration of a variable with a constraint like (0 <= x < 10), and the system tries to infer suitable constraints for all other variables (calling out to an SMT solver, and using invariant inference techniques from the program analysis community).

Their latest research language is "Liquid Haskell", I think it could deal with jarrett's example out of the box (with the caveat that yes, you still need to write the test explicitly). They used to have an online demo where you could just type programs into a web form, but that doesn't seem to work right now...

JoshTriplett• 12 years ago

The compiler doesn't necessarily have to have that level of inference; it can simply require the code to prove the constraints. For instance, parseInt will return an unconstrained int, so you'll get a type error trying to assign that to a range-constrained int. For your first and last examples, the multiplication operator on range-constrained ints can easily propagate the range constraints. In your last example, `z = w * x` would work, but assigning through the unconstrained int y may simply cause the last assignment z=y to produce a type error, forcing the code to re-establish the constraint explicitly.

dllthomas11• 12 years ago

"Can a dependent type system catch all type errors at compile time?"

Provably not, if you want a type checker guaranteed to finish.

jarrett5• 12 years ago

Could you give a brief overview of why? Does this come down to the halting problem?

JadeNB5• 12 years ago

Without really addressing your question, notice that the power of dependently typed languages is not in the intelligence of the compiler, but in the expressivity of the type system. That is, the question becomes not "can the compiler catch this error on its own?", but rather "can the compiler verify my proof that I have not made this error?" A language with a very powerful type system can still have a very dumb compiler (although it will generate extremely slow code).

EDIT: It occurs to me that this is well summarised by the apparently facetious remark "Ask not what your compiler can do for you; ask what you can do for your compiler."

quandrum• 12 years ago

Yes

  int x (>= 0, <=10)
  x = parseInt(getKeyboardInput)

Dependent Type systems don't have to know what is possible keyboard input. They have to know what type the getKeyboardType function returns (and the parseInt), and if it's possible for that type to be out of the range of your constraint.

If that's so, it throws an error. At that point you simply have to compose your types and functions so they match the constraint, and you know you are safe.

jarrett5• 12 years ago

if it's possible for that type to be out of the range of your constraint....If that's so, it throws an error.

If I'm understanding you correctly, that would seem to take a lot of the power out of dependent type systems. Almost all values will eventually depend on input from the outside world, so it seems you'd rarely have a chance to use your dependent type system.

Haskell (which doesn't have dependent types baked in) has a good approach to possibly-invalid data via the Maybe type. E.g. Maybe Int means "either an integer, or nothing." So it forces you to explicitly handle the possible error cases.[1]

To spell it out in Haskell terms: In the example of getting an integer from the keyboard, x is a Maybe Int. If the input is invalid, the value is set to Nothing, which is a unique constant. If it's valid, the value is of type Just Int.

At that point you simply have to compose your types and functions so they match the constraint, and you know you are safe.

But how do you get from untrusted, potentially invalid data into the world of trusted, guaranteed-valid data? How do you bridge the gap? I was suggesting some combination of an applyConstraint function and a Maybe type to achieve that. Are there other ways?

[1] Actually, it will let you bypass the usual compile-time protections with the fromJust function. But if you want compile-time safety, either refrain from using fromJust, or use it only where you're absolutely sure the value won't be Nothing.

randyrand• 12 years ago

| int x (>= 0, <=10) | x = parseInt(getKeyboardInput)

Will be a compile time error because getKeyBoard input returns integers that are between 0-256(?) not 0-10 like 'x' wants.

jarrett5• 12 years ago

Exactly. That's why I proposed a Haskell-ish Maybe construct to represent the uncertainty of the input's validity. The code snippet:

  int x (>= 0, <=10) | x = parseInt(getKeyboardInput)

...was meant as an example of what won't work.

arh68• 12 years ago

Can a dependent type system catch all type errors at compile time?

I'm probably not clever enough, but someone could probably prove that'd be equivalent to solving the halting problem. It seems impossible.

because the value of getKeyboardInput could be anything

That makes my brain hurt. I think implicitly narrowing the type is stylistically better. Maybe just adding a dependent type declaration:

    x = (parseInt(getKey) :: Int(>=0, <=10))

Then you type-annotate everything you can, marking every non-annotated expression as wild:

    w = ... :: Int(>=0, <=10)
    x = ... :: Int(>=0, <=2)
    z :: Int(>=0, <=20)
    y = w * x                 -- :: Wild
    z = y                     -- compiler should Scream!

Asking the compiler to infer arbitrary type declarations seems hard. I think y probably shouldn't be inferred as :: Int(0<=..<=20) unless there is a rule somewhere that Int(a<=..<=b) * Int(c<=..<=d) = .. :: Int(f<=..<=g).

The work still needs to be done (no magic bullet here), but we should be able to use the computer to generate well-defined type combinations.

mnarayan01• 12 years ago

I'm probably not clever enough, but someone could probably prove that'd be equivalent to solving the halting problem. It seems impossible.

Guessing you're plenty clever...just didn't think about it enough :)

Simply transform a program into one which halts on a type error rather than whatever else it might be doing. Done.

leoc• 12 years ago

I'm probably not clever enough, but someone could probably prove that'd be equivalent to solving the halting problem. It seems impossible.

IIRC dependently-typed languages dodge this bullet by not being completely Turing-complete (as 'twere).

rybosome4• 12 years ago

As others have noted, it's less about the compiler running code and making determinations as it is using extremely robust, information-rich types. For instance, the Vector type in Idris has two type parameters (not sure that's the correct term to use in this case): the first is the type of the element contained by the vector, and the second is the length of the vector. Operations that increase the size of the vector are guaranteed to return a non-empty vector. They might look something like this:

    (::) : a -> Vector a n -> Vector a (S n)

This says that an element cons a vector of any size results in a vector that is guaranteed to be non-empty. This means that you could safely write a function to retrieve the head of a list by restricting the type to lists that are guaranteed to be non-empty.

    head : Vector a (S n) -> a

Something like the following pseudo-code in a REPL(I don't actually know a thing about Idris):

    let nums : Vector Int n = []
    head nums

...would fail to compile, since the second type param to nums is simply `n` rather than `(S n)`, as required by our `head` function. All of the things you would expect from Haskell like the power of ADTs and pattern-matching apply here, so you get even more compile time type-soundness.

chriswarbo3• 12 years ago

For instance, the Vector type in Idris has two type parameters (not sure that's the correct term to use in this case): the first is the type of the element contained by the vector, and the second is the length of the vector.

In case anyone's wondering, only the first of these (the element type) is a type parameter, since it has a constant value in all sub-expressions (ie. the cons cells all contain elements of the same type).

The second is a 'type index', which is a more general term (type parameters are a special case of type indices), since its value changes in the sub-expressions (the cons cells have different lengths).

The difference is that we don't need to pattern-match parameters on every recursive call, since they're guaranteed to be constant (although we can if we like).

I didn't know this until I asked http://cs.stackexchange.com/questions/20100/what-are-the-dif...

RogerL• 12 years ago

In Ada you have subtype, so you would write

subtype my_type is Integer range 0..10; my_type x = 9; my_type y = 10; my_type a = x + y;

So, obviously there is enough information to deduce at compile time that the sum operation yields an incorrect value. In practice, as many of the replies point out, you can determine no such thing (my_type x = user_input()).

In that case Ada will throw a runtime exception. All this checking is expensive, so it ends up being much like C/C++, where you have debug and release builds, where the release builds do not do the checking.

prezjordan• 12 years ago

I wish APL/J/K were on here, but I guess that doesn't really change the way I think about coding... it just blows my mind.

protomyth2• 12 years ago

I've been thinking a lot about agent-oriented programming. I had a General Magic device back in the day and later thought the concept of a Telescript like language as applied more for code organization than code mobility might be interesting. I guess APIs won, but I still think there is something there.

abecedarius• 12 years ago

http://erights.org/ was not technically like Telescript, but aimed at a similar-enough vision you might find it interesting. http://erights.org/elib/capability/ode/index.html for that vision. The section on mobile almost-code at http://erights.org/elib/distrib/pipeline.html should help to relate it to Telescript.

hexagonc• 12 years ago

My first and only encounter with "Concatenative Languages" was programming the HP48GX[1] graphing calculator in highschool. Thinking back to it, I'm amazed by what you could do with it. It was very powerful even by today's standards. Whereas other kids had Gameboys, I had an "HP". I even got in trouble playing tetris on it during my German language class. My calculus teacher never knew that you could do symbolic integrals and derivatives with it (using a free computer algebra library). Sadly, the only program of note that I wrote for it was an implementation of the The Game of Life[2].

[1] http://en.wikipedia.org/wiki/HP-48_series [2] http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

sergiosgc• 12 years ago

Where is Aspect Oriented Programming and all the other offspring of the Inversion of Control pattern (Dependency Injection, Dependency Inversion, ...)?

Is this line of evolution in languages considered dead?

ExpiredLink2• 12 years ago

Yes, thank heavens, yes!

platz3• 12 years ago

These are more tactical (i.e. low-level) techniques that big strategies that encapsulate entire languages.

mcguire2• 12 years ago

What, you don't like computed non-local come-from's?

NathanOsullivan• 12 years ago

Came here to say the same thing. Learning about Inversion of Control utterly changed how I program on a day-to-day basis.

It may not be a language feature, but the things in the article seem rather academic by comparison.

saosebastiao2• 12 years ago

I'm a huge fan of the declarative programming paradigm, but outside of Regexp and SQL and a handful of other DSLs, it's dead. Its death should be a case study in Open Source strategy: It died because it became boring before it became useful. SQL and Regexp have stuck around because they did something useful immediately.

I think that any future that the Declarative paradigm has within general purpose languages is the kind applied by compilers. For example, x = (a + b) - a can be reduced to x = a or even eliminated altogether with subsequent in-scope references to x being replaced with a. Another example is dead code elimination. These forms of declarative let you use an imperative or functional language immediately but gently introduce you to declarative benefits without having to deal with all the mind bending that is necessary to optimize pure declarative code.

segmondy2• 12 years ago

You are very mistaken. Prolog is still very much alive. You can find us on ##prolog in freenode. You can build a web application with prolog. When the 2048 madness was going on, I implemented in prolog in about 200 lines in 2 hours and I had about 3 weeks of prolog under my belt at that time. It's a very powerful concept. I didn't have to figure out the how to implement it, I just broke 2048 down into rules, declared it, and bam, I had a game.

singold• 12 years ago

How/where do you recommend to learn prolog? The concept looks really interesting and useful, at least for me.

saosebastiao2• 12 years ago

I never said it wasnt useful, I said that it was dead...much in the same sense as COBOL. I use datalog and constraint programming extensively, but I'm a black sheep.

jroesch• 12 years ago

Prolog is an interesting exercise and occasionally useful as a tool, but most implementations leave a lot to be desired as a general purpose programming language. An example of this is SWIPL's 3 string types and their crazy behavior. You are also stuck in a first order language that is essentially pure, and have no abstractions for common patterns except meta programming which makes code even more difficult to reason about.

That being said I love having logical variables and I would love having them in other situations.

josephschmoe3• 12 years ago

Dependent types are a wonderful idea so long as I can do a couple things with them: 1. Copy paste them without complications. i.e. "non-null" requires no code that relies on specific variables unless there's a logical conflict (which variable?) 2. If it's a known failure, give me a warning. If it's an unknown failure, let me choose how to deal with it, again in a neutral fashion that I could simply say @Notnull<skip> and it would just skip the code if the variable is null.

keenerd• 12 years ago

Declarative programming is a great one, almost a magical experience.

"It feels like I am sitting at the controls of a quantum computer. I've got all my qubits (terms) all wired together in some complicated expression and when power is applied every qubit will instantly collapse out of superposition and crystallize into a perfect answer."

(From something I've been working on, http://kmkeen.com/sat/ )

josephschmoe3• 12 years ago

Would be pretty cool to have concurrency by default and then a lock declaration I could do on a particular function to fix any concurrency issues. Would need a new style of debugger/code view though specifically for this purpose.

josephschmoe3• 12 years ago

Code Search is a better way to do Declarative Programming for non-optimized solutions. I've been obsessing over this topic for the last few months. Right now there's limited versions in a few places: Python's howdoi and Visual Studio's Code Search.

A true Code Search would work like this: 1. Type in your search term in your code in a comment line. i.e. "Bubble sort StampArray by name" 2. Google/Bing/StackOverflow searches for your string. Replaces your terms with generics. Searches for "Bubble sort [an array of objects] by [string variable]" 3. Takes code results and shows them to you. Replaces all instances of [string variable] with getName() and all instances of [Object[]] with StampArray. 4. You pick your favorite. 5. Your IDE adds the code to a "code search module" which you can edit. 6. Your edits get added to the search database.

The best part? You could even put your Declarative Programming engine -inside- of the Search just by populating initial search results. What about better code coming to exist in the future, you say? Well, you don't necessarily have to keep the same result forever. If it's been deprecated, you can re-do the search.

AlexanderDhoore2• 12 years ago

The aurora language seems very interesting. Too bad there is already another language called Aurora...

I makes me think of Elm [1] and (functional) reactive programming. Reactive programming is fantastic. It's kind of like how a spreadsheet program works. If a variable changes, all variables who depend on it change as well. Given "a = b + c", if c increments by 1, so does a.

It has many advantages over event based systems, like Javascript. Reactive programs don't need callbacks. The changing values propagate the "event" through the system.

I'd love to hear what you guys think about this direction of programming. It seems very natural to me.

Edit: I also see reactive programming as the golden way of having changing state in functional languages. Functional languages have no problem with data or state. They have a problem with change of state. The reactive paradigm solves that problem. All change is implicit and code can be exactly as functional as before.

[1] http://elm-lang.org/

[2] http://en.wikipedia.org/wiki/Reactive_programming

ibdknox• 12 years ago

we're actually in the process of changing the name :)

EDIT: re FRP, you might find this Lambda The Ultimate post insightful: http://lambda-the-ultimate.org/node/4900

FRP has issues with openness and isn't real great at dealing with collections. It also forces you to express things kind of unnaturally (e.g. instead of "click this and increment x", you say "the counter is the count of all click events"). There are other methods of managing time, like Glitch[1] and Bloom[2] that seem more promising :)

[1] http://lambda-the-ultimate.org/node/4910 [2]: http://boom.cs.berkeley.edu/

AlexanderDhoore2• 12 years ago

Well, I'm not a fan of the "use folds over time" concept either. FRP is too complex, but there's some great ideas there.

Would you say Aurora and these other languages are "reactive"? Or do you have a better term for it?

BTW: I'm reading "Toward a better programming" right now :)

rybosome4• 12 years ago

"It also forces you to express things kind of unnaturally (e.g. instead of 'click this and increment x', you say 'the counter is the count of all click events')"

I suppose it's personal preference, but I actually think that the latter of the two statements is much more understandable. This is why I like functional programming in general; a single value can be expressed as a declarative transformation of other pieces of data, making it clear how the value is derived. Using the imperative model, it's up to variable names and documentation to make it clear what 'x' is. It's like looking at one of those pictures that contains multiple shapes simultaneously; suddenly you see the one you haven't been seeing, and then you wonder how you didn't see it all along.

joshlegs• 12 years ago

.... did .... did you crosspost this from reddit ???

http://www.reddit.com/r/programming/comments/22nhb2/six_prog...

aufreak3• 12 years ago

Would be good to add Mozart/Oz.

Dealing with process coordination using the resolution of logical variables gave me a refreshing new perspective. The finite domain constraint system design in Oz is an awesome example of this in action.

An interesting tidbit - the Mozart/Oz team invented "pickling" before it caught on with Python.

kazagistar• 12 years ago

If a programming paradigm does not change how you think about coding, it isn't a programming paradigm. Good article though.

Programming paradigms that change how you think about coding

Related Stories