LispCast

> Every operator in C can be thought of as a lambda expression of finite arity. Indeed, the output of a C compiler's parser is an abstract syntax tree -- expressed usually as a list of lists, just like Lisp code. Well-factored C code is largely identical in semantics to similarly factored Lisp code.

The problem with the semantics of C is that anything is allowed. If you write good, clean C, I am sure you can perform a lot of these operations. But C allows you to read from and write to any memory location in the program at any point. Some correct programs take advantage of that. Some programs are incorrect because of that. But how can the compiler tell the difference?

> But, I shy away from all these automatic systems, because there is no one-to-one correspondence with what I write, and what the computer executes. I've been burned by this more times than I can remember.

Have you been burned by tail-call elimination?

> No, I prefer instead to write simple code, with a simple compiler, producing simple binaries.

This is what I am suggesting. Write the simplest, abstract representation of a function. The compiler will produce a simple binary. The simplest abstract representation very often is a recursive definition. The simplest binary is usually iterative.

> I don't care how long they run, at least at first.

I don't care, either. But when it's time to optimize, I don't want to complicate my code any more than I have to. Just like I want to say (memoize 'fib), I want to be able to say (iteratize 'fib). But I don't want to have to drastically change my code when it can be left the way it is and simply advised how to make it faster.

> Finally, what you're describing cannot solve the largest problem of all -- the recognition that you're writing a simple linked list implementation when you meant a B-tree. But, then again, what kind of B-tree? Would a skip-list be sufficient? You want real 2-3-4 trees, or are you happy with an AVL-tree implementation?

It's true. No computer will be able to recognize that your algorithm is inefficient for the problem.

But the point of a high-level language is to allow you to quickly change from one implementation to another. Painlessly. That means with as few changes as possible.

For instance, many high-level languages support polymorphism. This allows you to trade out a Vector for a Linked List if you choose with minimal change in the code. If it makes it difficult to change, you'll be less likely to do it. And I think the same should be true of recursive/iterative functions.

> I vote no to automatic anything.

Perhaps you would want to control when it happens? Certainly it could be built as a compiler advice system.

> The computer is stupid, able to recognize, and optimize based on, only the most basic of arithmetic truths. There are a number of them, for sure; but, what you're calling for above makes no economic sense. Why write one implementation of something, when you write rules on how to replace said something with something else. You might as well just delete and re-write the relevant code into "something else" from the start. You'll save time, money, energy, frustration, nerves, and electricity.

The whole reason for this is that there is the difference between what I think is simple to read, write, and maintain (ie, simple recursive functions) and what the machine thinks is easy to run (ie, iterative functions). Why implement one version and write rules to translate it? Because the first version is usually simpler. The rules can be used repeatedly. So I wind up with code that's smaller. Do Not Repeat Yourself.

When I write C, the simpler functions are usually faster. There's a much more direct correlation between what I write and what the compiler writes. In C, fewer lines of code, in general, really does seem faster. Basically, I would say that fewer lines of code means you're doing less unnecessary computation.

The same happens with Forth. Though I've never written in Forth, my understanding is that the low-level control you have over what happens tends to push you toward simple implementations.

The reason to have automated optimization is very simple: when you are exploring your problem space, like you said, you don't care how fast it runs. But as you understand your performance bottlenecks and you need to make it faster, how much of the code do you want to have to rewrite? How willing are you to trade simple code for longer, more optimized code?

In assembly, after the first version you understand the problem a bit better. Then you throw it away and start over. This is actually recommended by some of the giants of programming. But in higher-level languages, people tend to do more refactoring instead of starting over. Write code then make it cleaner. Encapsulate complexity. Leverage the language. Abstract code into higher-level constructs.

So the code tends toward high-level, more abstract notions. In contrast, many optimizations require low-level control. So your simple, abstract representations will have to be broken.

When you optimize for low-level control, you set down a path that is hard to recover from without rewriting a lot of code. High-level languages let you encapsulate the change (through polymorphism, functional abstraction, etc) so that you don't have to rewrite everything. Of course you give up low-level control. You trade it for the ability to not have to think about it.

For instance, I would like to see a collections interface where you give it constraints and it gives you an implementation of the optimal collection. You can say "I need O(1) random read access" and it might give you a Vector. But if you say "I need O(1) push" it would give you a linked list. Abstraction abstraction abstraction.

>> How willing are you to trade simple code for longer, more optimized code?

>Extremely, if warranted. When rewriting code to use greater performance optimizations, the original code should remain available, as a drop-in replacement for the optimized code. E.g., you might have files like:

>foo-knowngood.c
>foo-optimized.c

Pardon me if I am naively misunderstanding you, but are you suggesting that we should maintain two separate code-bases? That seems tedious, but I'm not a professional software engineer, so maybe this is standard practice for you guys.