Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I want to fix programming

jonbho.net

Post reply on HN
Print view View original

41–50 of 163 posts

Re: I want to fix programming

#41

Post by AUmrysh »

Tuna-Fish wrote: post #32
skizm wrote: post #26

Earlier quoted context omitted.

So I am relatively naive when it comes to declarative programming in general and have not yet read this paper (I will after commenting here), but that said... Don't you have to (at the very least) tell the compiler how to do things? To reuse the example from the article: when you tell your friend to get you a beer, at some point your friend has learned HOW to get you a beer. Similarly the compiler will need to know H…

Declarative languages are defined by the fact that in them, you don't tell the compiler how to do things. You just describe the result you want, and it's the compilers job to get there. Yes, this makes the compiler rather hard to write. SQL is probably the primary example. Prolog is also well-known.

For anyone who may not know, Prolog does this in a pretty interesting way. You have some declarations that make up your program, Prolog takes these and then uses them to conduct a logical proof (like in discrete math). You negate the premise (proof by contradiction), and then try to show that this will cause a contradiction (line 5 says Bob is Human, but line 42 says Bob is not Human). If you can find such a contradiction, your premise was true.

It does this by using backtracking, which is really interesting in itself if you're not familiar with it.

Re: I want to fix programming

#42

Post by dullcrisp »

barrkel wrote: post #34

So long as the problem you are trying to solve is constrained by the ease with which you can express the problem, this will help. But it will not help when the constraints are elsewhere: memory, network, CPU, heterogeneous interoperability; all still relevant in these times of mobile and distributed computing. When you are operating to these other constraints, you need control - or rather, consistency and predictabil…

He doesn't have to specify whether or not the sort is stable -- the compiler should only have to satisfy the constraints he imposes. So if he doesn't specify that it must be a stable sort, the sort might be unstable, just as with many sort routines that don't specify whether they're stable.

Re: I want to fix programming

#43

Post by jng »

Ygor wrote: post #18

For those who haven't read it yet, this paper has a lot to say about the cause of programming complexity, Out of The Tarpit: http://web.mac.com/ben_moseley/frp/paper-v1_01.pdf They say that the only essential complexity is the one inherent to the problem the program is trying to solve. Everything else is just here because we haven't yet found the methodology or invented the tools to battle it. They also describe an i…

Great paper. I'm familiar with it, and I think it's one of the initiatives out there pointing in the right direction. Same as Prolog and SQL. But we still have to work a long way in that direction for it to pay off nicely in our day to day!

Re: I want to fix programming

#44

Post by jng »

AUmrysh wrote: post #35

I'm curious about how a compiler can infer the algorithm for sorting. I've played with machine learning algorithms like neural networks and genetic algorithms which might be able to do some of this, but what other things are out there?

I will cover my approach to that in later posts in the series :)

Re: I want to fix programming

#45

Post by dustingetz »

Jon, you're looking for haskell. But there's a catch -- programming in haskell is HARD, and expert haskellers are the best of the best, thus EXPENSIVE.

many customers don't want correct programs, they want cheap programs. Some people in finance care about correctness, maybe you should check them out.

Re: I want to fix programming

#46

Post by barrkel »

dullcrisp wrote: post #42
barrkel wrote: post #34

So long as the problem you are trying to solve is constrained by the ease with which you can express the problem, this will help. But it will not help when the constraints are elsewhere: memory, network, CPU, heterogeneous interoperability; all still relevant in these times of mobile and distributed computing. When you are operating to these other constraints, you need control - or rather, consistency and predictabil…

He doesn't have to specify whether or not the sort is stable -- the compiler should only have to satisfy the constraints he imposes. So if he doesn't specify that it must be a stable sort, the sort might be unstable, just as with many sort routines that don't specify whether they're stable.

This is what I mean by hidden / unstated assumptions. So on one version / implementation of the compiler, a program may produce correct output, where on another, it produces incorrect output, because of a hidden assumption about the stability of the produced sort. The problem may not be found in testing due to this; and what will debugging the program look like?

If this is the kind of issue that can come up in a really simple task, what kind of issues will emerge as things scale up?

Re: I want to fix programming

#47

Post by apsp »

Not to discourage you from trying anything but it looks like you've ignored the complexity issues with this (I won't pick at the fact that you described an O(n^2) algorithm for sorting).

I understand that you don't want to specify the steps to achieving the goal but the steps directly impacts running time.

In your particular example, a compiler could produce a program with the correct output but runs extremely slowly even for small arrays (by simply trying all permutations until it finds one satisfying your constraints, or even worse, randomizes the entries until the constants are satisfied ("bogo sort")).

Furthermore, there are undecidable problem for which the output is easy to specify but no program could exist. For example, deciding if an input piece of code will loop indefinitely.

In your article, you've mixed needless overhead (the dummy/local swapped variable comes to mind) and the steps needed to specify an algorithm.

If you only want to remove the overhead (and thus, some source of mistakes you've pointed out), you could aim for a language where the algorithms are easier to specify.

In the bubble sort case, the code would look something like.

  def bubble_sort( array ):
  	while there is an i such that array[i]
(You can almost do this in Python already which seems to be where the syntax is inspired from. I can elaborate if interested.)

Ultimately, I have to agree with other comments saying this will be more useful for checking than specifying a program.

[EDIT: fixed code formatting]

Re: I want to fix programming

#48

Post by barrkel »

jng wrote: post #38
barrkel wrote: post #34

So long as the problem you are trying to solve is constrained by the ease with which you can express the problem, this will help. But it will not help when the constraints are elsewhere: memory, network, CPU, heterogeneous interoperability; all still relevant in these times of mobile and distributed computing. When you are operating to these other constraints, you need control - or rather, consistency and predictabil…

You are right, and I think you've found one of the weak spots. But I do think that can be treated, and the advantages of the programming-ease will be a good trade-off in many cases with the lost control for efficiency. It's like the switch from assembly to C, or from manual memory management to automatic memory management. You lose something. You gain something else. The new approach is not valid for everything, but…

I wish you the best of luck in any case. I look forward to reading more about how you expect the transformation logic would work.

Re: I want to fix programming

#49

Post by jng »

dustingetz wrote: post #45

Jon, you're looking for haskell. But there's a catch -- programming in haskell is HARD, and expert haskellers are the best of the best, thus EXPENSIVE. many customers don't want correct programs, they want cheap programs. Some people in finance care about correctness, maybe you should check them out.

Dusting, thanks for the suggestion, but I'm not looking for Haskell. It's not what I'm looking for. What I want is declarative, not functional. There is an inherent limitation in the functional approach, I hope to cover why that is in a further article in the series.

I am not after correctness per-se. I am actually more after "cheapness" at least in programmer time. But I do think a lot of the programmer time is spent in things that a solution-describing approach removes, and correctness gets a ride.

Hopefully I am in a right path in that direction!

Re: I want to fix programming

#50

Post by ezyang »

Here is another way of defining something is sorted, taken straight from a real language:

  Inductive StronglySorted : list A -> Prop :=
    | SSorted_nil : StronglySorted []
    | SSorted_cons a l : StronglySorted l -> Forall (R a) l -> StronglySorted (a :: l).
What this says is that an empty list is sorted (SSorted_nil), and that given some sorted list l, if a is less than all of the elements in l (well, we generalize to some relation R), then a prepended to the whole list is sorted. (SSorted_cons)

But it turns out, there is another way we can say this property, if our relation is transitive: all we need to say is that the element is less than or equal to the first element of the list.

And for any non-trivial specification, there are literally dozens of ways of specifying it, all of which happen to be identical. Which one do you pick? Which one is easier to use? Hard to say, in general.

Source: http://coq.inria.fr/stdlib/Coq.Sorting.Sorted.html

Post reply on HN