Lambda the Ultimate

Lip service was given to functional programming, genetic algorithms, and neural-nets. However these were not taught.

Obviously there are many other (and more important) factors, but my experience of my current Univercitys syllabus is that "good old-fashioned programming" is here to stay.

But when you say "Nonalgorithmic" you are obviously thinking of a more expansive notion of algorithm. But I'm not sure what that means. A genetic algorithm is certainly an algorithm. You might not be writing an algorithm when you query the program for an answer, but *someone* wrote algorithm that comes up with the answer. Same with the declarative example, or constraints. *Someone* wrote an algorithm.

Then you ask -- is the person who uses that program a programmer? Or just a user? Is Prolog programming? Is writing SQL programming? Is using Acess programming? What's the line?

And what qualifies as algorithmic? Is implementing an HTTP client algorithmic? (Maybe a little, but not a lot) Using someone else's client? Is using a browser?

Programming isn't about algorithms, it's about abstractions. Using an HTTP client can be programming if you use it abstractly, with unknown inputs or unknown outputs. And so using a browser isn't programming, it's entirely concrete.

Most programming isn't algorithmic, but it's still programming. We spend out time packing and unpacking data structures, passing information around to systems or libraries we don't ourselves author. When we say "if" or "while" or "for", does that suddenly turn it into an algorithm? I dunno... maybe. Can a program be mostly non-algorithmic, with a little bit of algorithm thrown in? Or does it ruin you immediately? What if you use a shell script to start up your genetic algorithm? ;)

I'm thinking of the standard definition of "algorithm" as a recipe for getting a result in finite time. "Algorithmic" programming is then programming by telling the computer explicitly what to do to get a result.

But if you understand the process that the underlying language uses to evaluate (or solve) programs (or problem specifications), then isn't it quite valid to think of all programming as algorithmic programming according to your definition?

For example, it is hardly possible to write anything non-trivial in Prolog (or pretty much any logic language) without having a very detailed understanding of how the program will be evaluated. [You can extend this to pretty much any language. Different kinds of languages just have different kinds of evaluation rules.]

Or are you perhaps advocating that programs shouldn't be designed as algorithms (that terminate), but as some sort of abstract problem specifications and that the process by which the problem will be solved should not be published so that there will not be any guarantees that such problem specifications indeed produce efficient algorithms?

Sorry, I didn't mean to sound insulting. The above just combines both the premises and the consequence, as I basically assume it would be, into a single question. I find it quite unrealistic, at least today, to assume that a language specification would not impose some evaluation process on programs, but would only specify the kinds of programs that will lead to an [efficient] algorithm.

i could probably write a bunch of clauses to define some relationships, but inferring something from them *efficiently* is beyond my ability in prolog. so i can only use prolog in a nonalgorithmic manner.

Thank you for bringing this up. It is critically important, and from what I can see, not very well understood.

You don't have to jump off into AI to find examples of "nonalgorithmic programming". How about these?

• Excel
• Yacc
• SQL
• XUL (user interface language)
• Mathematic?
• Modeling languages (e.g. UML and OGM MDA)

But you do need a better name for the concept. I have felt for some time that functional languages are in a sense very "procedural", since they define steps of computation expressed via functions applied to arguments. The fact that they avoid the use of state does not mean that they avoid step-by-step logic.

Perhaps the problems is the very word "programming": a "program" is a "step-by-step list of activities".

I think the key idea is describing the properties of a desired solution without specifying explicit instructions on how to implement the solution. This could apply to anything, from algorithms to the creation of a web page. It is saying "what" not "how".

Some classic examples, especially from the algorithmic area, suggest that this is not possible in general. For example, it is easy to specify the behavior of the "sort" algorithm. However, I am not going to expect a computer to come up with quicksort given this specification.

I think that the technique of "what-oriented programming", or "executable specifications", or "real-world programming" is going to be increasingly important (it is already important, see list above). But it requires working in a specialized domains (spreadsheets, databases, etc) rather than thinking always about general-purpose programming languages.

I am still not sure what's wrong with the name 'declarative programming'.

I think that there are some compelling cases, but, in the end, it seems to me that the programmer must be aware of the intimate details of the evaluation process. I think that this is not just an ideal, because one of the last thing I want, is to sit in a plane, whose software is programmed by people who don't really understand the principles upon which the programming language they used is based upon.

I think that this gets more and more true as the computational completeness of the declative language increases. One can be relatively unaware of the process by which regular expression matching is done and still write correct regular expressions that yield efficient matchers.

With context free grammars, it is already difficult to create correct grammar specifications that yield correct and efficient parsers, when the complexity of the specified languages increase, without having a detailed knowledge of both the theory of context free languages and the exact parsing technique used.

When the language becomes Turing-complete, many declarative languages make it very easy to create non-terminating programs, that don't appear to be non-terminating, unless you have a detailed understanding of the evaluation process imposed by the language. When the "algorithmic complexity", by which I mean some measure of the complexity of the best known solution algorithm, of the problem increases, it becomes difficult to create programs that would not be too inefficient to be useful. To reach the complexity of the best known solution algorithm, you typically need to effectively program in a non-declarative style.

Of course, I'm not arguing that declarative programming would be useless. I'm just arguing that declarative programming falls rather short of the ideals attached to concepts such as "automatic programming" in the early days. I think that it is very likely that there will never be "breakthrough" in the use of general purpose declarative programming. I think that it is very likely that the use of declarative programming exhibits steady piecemeal growth as declarative techniques are develoved for rather specific problem areas.

What I was thinking about goes beyond declarative programming as it is usually understood. It's more like, what is the relationship between a user/programmer and the machine? (*)

Does the programmer have (in principle) to explain all the steps? Or can the programmer treat the machine more like another programmer (who can often get by with much less)?

This does not mean that we are implementing general AI (see, e.g., William Cook's examples, which go in this direction without being intelligent). It just means that the system is "filling in the blanks" as regarding the steps. In some limited domains, we already know how to do this (up to a point). We are also learning how to "finesse" things by leaning on brute force (Moore's Law) and large knowledge bases (table lookup with simple inferencing). I think that there is a clear trend towards this style of programming.

(*) In my view, the distinction between "user" and "programmer" will get fuzzier in the future. Users will be doing more programming, and power users will become indistinguishable from programmers. This will be possible because programming itself will become much easier, because it will be nonalgorithmic.

At one level, fopen() can be viewed as extremely declarative, because I don't have to talk about disk platters, file system format, interrupt handlers, etc. At another level, it can be viewed as a pesky implementation detail because I'd much rather say "make this data structure persistent" and ignore how that gets done.

So I wonder to whether "nonalgorithmic programming" is a difference in kind, versus a difference in degree.

Or, to take another tack, I wonder whether lazy evaluation qualifies as a step towards nonalgorithmic programming, because any given function can be evaluated in several different orders, depending on how it's used by the client.

Perhaps many more errors are caught by "declarative" or "non-algorithmic" systems, but my experience has been that (a) I still make lots of mistakes and (b) the correlation between the error message I receive (or the incorrect result) and the site and nature of the error is often a lot more remote than it is with imperative programming. Maybe it is just me.

Still, I have always found that a good debugging technique is to work backwards from the observed result, asking "what could have happened to produce this effect?" Doing that requires a pretty good understanding of the steps that the computation went through. So often I end up "working out" the declarative->imperative transformation myself, which is exactly what the declarative system was trying to save me from.

The distinction between implicit and explicit state is important. The reason we want a new term is that this distinction is not the one we want to focus on. The issue is whether we describe the steps, or describe the outcome we want and let the system find the right steps. I don't think "declarative" captures this distinction.

The issue of understanding the execution model is also important. A "non-algorithmic programming language" must have a well-defined semantics. But the user does not have to fully understand the execution model. How many users of Excel understand how it works? Or SQL? One of the laws of "worse is better" states that a language must have a transparent execution and performance model, and one that does not require mathematical sophistication to understand. This is probably a requirement of the success of general-purpose languages.

The issue is that the more you look at them, the more the general-purpose problems start looking like members of a family of related specialized problems. Specific tools may be better for these tasks than general-purpose tools. There will always be a large role for general-purpose tools, but think a gradual shift away from them is inevitable.

That is a very good example. Suppose I have expressed the grammar in yacc. Sure, I can look at the grammar states. If I have a good theoretical understanding of LALR(1) parsing, I may be able to figure out what is going on. But the tool doesn't help me very much, as is evidenced by the number of questions which pop up on any random parsing discussion group. On the other hand, LL(k) systems which implement recursive descent parsers are pretty easy to debug, albeit arguably less powerful.

SQL plans might help me improve the efficiency of an expression, but it is not clear to me that they help me debug a faulty expression. Maybe. I don't have a lot of SQL experience.

Here is another domain where tools are lacking: debug a complex C++ template. In fact, don't even think about debugging the template; just think about interpreting the C++ error message when the template is misapplied in a program. I haven't yet had the courage to venture into XSLT but I have the feeling that the same sort of swamp awaits me there.

I am sure that there is a solution. There are good, commercial parsing packages which actually help you visualise how a grammar applies to an input, for example. Some functional languages will show you type inference rules in a way that actually gives you a clue as to what is going on. Some OO languages do the same with overloading/polymorphism rules: colour-coding in the Dylan IDE is very helpful, for example.

In a way, this is related to the problem with generating useful error messages in an LR(k) grammar system. That is difficult to do, because at the moment the error is detected by the engine, you have to analyse the state of the parser to figure out the context of the incorrect input.

Anyway, I think that the challenge remains. It is nice to come up with declarative/non-algorithmic/whatever systems which make some problems very elegant to solve. But in the real world, people like me make mistakes -- and there seems to be more emphasis on "elegant programming models" than helping errant programmers/users.

Buddha

I think the problem with this "things are getting better and better" point of view is that, as we all know here, many problems of interest have no general solutions with nice computational properties.

The upshot of this for programming (as is already the case in my experience) is that a programmer is someone who thinks carefully about a particular problem in a particular situation and finds a manageable computational solution for it.

Barring P=NP or the invention of HAL 9000, I don't see that this is in danger of being otherwise.

Regarding debugging: this is part of the general issue, "what to do when things go wrong?" Examples are asking the system the wrong question, wrong behavior of the system due to software or hardware errors, complexity problems (needing too many resources to solve the problem as stated).

When your car (or other appliance) works well, then you don't need to be an automobile technician. When there is a simple problem, you can often fix it yourself, so you don't need to be a technician either. But harder problems need a professional!

I think that for software, this simple analogy will break down. Software exists in a formal world that obeys formal laws (forget the embodiment for a moment; I will get back to that). This formal world is much simpler than the real world. This means that, in principle, a software solution to the debugging problem can exist (assuming a big dose of Moore's Law to oil the works; remember that we are speculating on possible futures!).

I don't know how this solution will work. But I can imagine that the system will have invariants at all levels of abstraction, and that brute force path exploration can track down the problem and replace the faulty module (or wrap it in something) with a "more correct" module obtained by a brute force question (the system asks itself: "please give me a module that obeys the following specification"). All this can be done automatically. In some sense, the system rewrites itself!

Regarding the embodiment: given a little bit of redundancy, I think that the probability that the debugging will actually need intervention by a professional programmer can be made very low. A simple "board swap" can be done by a naive user, when the system asks for it after autodiagnosing itself.

All this is just informed speculation of course.

the system asks itself: "please give me a module that obeys the following specification"

The reason that I think this might eventually be able to work is that the system as a whole is much bigger than the faulty module. The idea is that a very large system with a lot of processing power can focus its attention on a very small part of itself and improve that part.

but we'll still need programmers to ask the correct questions to the almighty computer

This is an interesting point: the profession of "programmer" will then no longer be people who can write programs, but rather people who can ask the right questions!

If you do Test-Driven Development, this is already true...