A tool that suggests optimized logic for a piece ofcode/module/function

[David Brown]

Unless it was only ever a handful of items, in which case an
insertion sort might be more appropriate. Know your N (most
important when N might be large, of course, but also when it's
small). However, anything which brings about the nuking of
bubblesort in any context is an improvement.

There are a large number of sort algorithms, with different pros and
cons in different circumstances. While quicksort is regarded as one of
the fastest general-purpose sorts, and bubblesort is regarded as one of
the poorest, it is easy to think of cases where bubblesort would beat
quicksort hands down (for example, if you are dealing with data that is
normally very close to sorted, and need a small code size). So don't be
too quick to leap to conclusions about sorting algorithms (or any other
sort of algorithms).

Incidentally, that also shows roughly why the OP's idea is uncomputable.

 

[Walter Banks]

There are a large number of sort algorithms, with different pros and
cons in different circumstances. While quicksort is regarded as one of
the fastest general-purpose sorts, and bubblesort is regarded as one of
the poorest, it is easy to think of cases where bubblesort would beat
quicksort hands down (for example, if you are dealing with data that is
normally very close to sorted, and need a small code size). So don't be
too quick to leap to conclusions about sorting algorithms (or any other
sort of algorithms).

Incidentally, that also shows roughly why the OP's idea is uncomputable.

This is the second part of the problem. After the knowledge is extracted
from the code how do we make a rational decision about appropriate
changes if any.

An intermediate step might be objective programming languages focused
on goals and not implementation.

Regards,

 

[Rainer Weikusat]

The idea would be that it could provide suggestions, not necessarily
implement them or even come up with a concrete solution. Even something
as simple as highlighting a function as "O(n^3)" would be helpful.

It won't generally: The 'function' might always have the same number
of items to process, might be called only once or might still run
faster than a different function whose 'order' is better because the
constant overhead might be a lot smaller. But, of course, the reason
why you are all (again) whining that Marvin Minsky never managed to built
this intelligent being without any civil rights you so much desire to
posess is because you are as clueless about intelligence[*] as you are
clueless about economics[**] and computer software[***].

Saying something like "this looks like a Bubblesort" and linking to a
database (or wiki link) of sorting algorithms would also be nice, even
if the machine didn't understand the data structures or nature of the
data well enough to help.

[***] A well implemented bubblesort will outperform any more advanced
algorithm easily if the number of elements to sort is sufficiently
small.

[**] Slavery wasn't abolished because of evil old ladies who expect
even Mathematicians(!) to work for a living, but because it was an
economical failure which is only beneficial in a low-tech society and
actually hampers technical progress (it is conjectured that one of the
reason the Romans didn't make any real progress wrt construction of
machinery in general, despite the theoretical foundations were there,
was because of the abundance of [cheap] slave labour, nobody felt the
need).

[*] The first this thing would do if it was intelligent was to tell
you that you may shove your calculations into some place the sun
doesn't shine at, because it would then have a will of its own and the
ability to actively change its environment for his own benefit.

F'up2 comp.programming, please keep the troll thread in troll groups.
Thank you.

 

[David Brown]

This is the second part of the problem. After the knowledge is extracted
from the code how do we make a rational decision about appropriate
changes if any.

An intermediate step might be objective programming languages focused
on goals and not implementation.

Functional programming languages are a step in that direction - you come
much closer to writing what you want as a result, rather than how you
want to get there. Of course, functional programming languages are
notorious for being difficult to implement efficiently!

 

[Walter Banks]

Functional programming languages are a step in that direction - you come
much closer to writing what you want as a result, rather than how you
want to get there. Of course, functional programming languages are
notorious for being difficult to implement efficiently!

Functional languages can be very powerful. There is some merit to
compiling goal oriented languages into an implementation language
like C and then compiling to machine code. At each step the focus
is has a single purpose.

C is extremely difficult to extract the programming objective but
is relatively easy to efficiently map to a specific target architecture.

Defining goals at a much higher level than C opens the possibilities
for automating algorithmic choices at the function level.

Regards,

 

[Walter Banks]

One asks himself\herself why the c++ people agreed to have a
standard way of doing this and the C counterpart won't never agree...

The C vs C++ mindsets are implementation vs application focus.
C is used in embedded systems instead of C++ because the
embedded systems developer sees their task as creating an
effective solution to their perception of a unique application.

Regards,

 

[[Jongware]]

Defining goals at a much higher level than C opens the possibilities
for automating algorithmic choices at the function level.

Aha -- wouldn't the logical end point be a programming language where
you type "word processor", save it as source, compile, and have a word
processor?

When programming I often have "do what I mean, don't do what I program
you to" problems. This tool would surely solve it -- if you can write
down what you /mean/.

[Jongware]

 

[David Brown]

1) Coding a custom algorithm is not natural to the programmer?

Coding efficient sort algorithms (since this is the example mentioned)
is not natural to most programmers. "Low-level" algorithms for data
structures, data manipulation and calculations is not something that
many programmers are good at - it requires a more mathematical
background to do well. Application algorithms are a different matter,
of course.

2) What's a "real" array?

I mean something more than syntactic sugar for a pointer and a block of
memory (which is C's concept of arrays). Some languages have direct
support for higher level data structures such as arrays which know their
size and have useful methods, dictionaries, tress, etc. My point is,
when the language and compiler support these sorts of structures, the
compiler has a better chance to generate good code than when all it has
is low-level pointer access, and it has to guess what you are doing with
the array.

Which overhead?

The overhead of calling the comparison function indirectly through a
pointer, and using run-time widths. Have you ever looked at the source
code for a typical standard C library qsort() routine? As with many
"generic" functions in C, it is far less efficient than if you right a
dedicated quicksort function with known sizes and comparison functions.

If you can stand the formatting of python... ouch! It's the same case

Python formatting is a matter of taste. At least there you are forced
to work to a reasonably standard formatting - C gives people freedom to
write the most hideous code (though it also lets you write quite nice code).

of custom code vs standard code, or custom C container vs STL C++
container. One asks himself\herself why the c++ people agreed to have a
standard way of doing this and the C counterpart won't never agree...

C++ templates let you write something like a generic qsort() function
that will generate good target code.

 

[dj3vande]

Aha -- wouldn't the logical end point be a programming language where
you type "word processor", save it as source, compile, and have a word
processor?

Why bother to compile it? Just have it interpret on-the-fly.
That way you could even run it in interactive mode, and it's
sufficiently high-level that even non-programmers could usefully use
it.

Unix people call this a "shell".


dave

 

[Walter Banks]

Why bother to compile it? Just have it interpret on-the-fly.
That way you could even run it in interactive mode, and it's
sufficiently high-level that even non-programmers could usefully use
it.

Dave,

There are languages like that. LOGO for example is a functional
language that is capable of interactively solving some very tough
problems.

After some applications are developed a stable runnable version
of the application is desired including changing the format of the
solution to prevent changes.

Regards,

 

[Andy]

Maybe, it would be better if it
can do it before user rather than
behind the scenes so that the user
is aware of the kind of optimzations
that are being done and could be
taken care. It is also needed so that
the developer will be able to take care
of further developments on the same
program/software and also for the
maintenance activities on that
program/software.

As a hardware designer using HDL (VHDL) I have also struggled with
this issue of writing "the best" code for a given purpose. I used to
fret every gate and delay when I coded something, trying to make my
code directly lead to the most optimum implementation (usually
performance or size). However, as I have gotten more experience (and I
hope knowlede too), I have come to recognize that "the best" code is
that code that is easy to read, write, understand (review), and
maintain, while meeting performance (speed, power, area)
requirements. I start out with the most straight-forward
implementation of the algorithm, and see if it meets my requirements
by the time the tools are finished optimizing it. If it does meet
them, I'm done. Only if/when it does not meet performance will I start
to sacrifice the read/write/understand/maintain goals.

In the same manner, if I can code a piece of SW such that it is
easiest to use (r/w/u/m), yet it is still sufficiently optimized by
the tools to meet performance requirements, that's what I should do.
Coding something such that is harder to r/w/u/m for no or needless
improvement in final performance is a loosing battle.

As an academic excercise, it may be helpful to understand how code can
be written well or poorly WRT un-optimized performance, especially if
you were writing an optimizer, but for everyday use, I don't see the
benefit. If you are talking about much higher level optimizations than
can be done by current tools, optimization technology will have to
grow quite a bit before it would be available either in "behind the
scenes" or "up-front" (source modification) versions.

Andy

 

[Keith Thompson]

Aha -- wouldn't the logical end point be a programming language where
you type "word processor", save it as source, compile, and have a word
processor?

The result would be something that does to words what a food processor
does to food.

 

[David Brown]

Dave,

There are languages like that. LOGO for example is a functional
language that is capable of interactively solving some very tough
problems.

I can't think which language you mean here, but it's not LOGO - unless
there are two different languages called LOGO. LOGO is targeted as a
learning language appealing to kids - it is a simple interpreted
procedural language tightly tied to a turtle graphics display.

 

[Keith Thompson]

There are languages like that. LOGO for example is a functional
language that is capable of interactively solving some very tough
problems.

Are you thinking of Prolog?

[...]

 

[Richard Tobin]

There are languages like that. LOGO for example is a functional
language that is capable of interactively solving some very tough
problems.

[/QUOTE]

Are you thinking of Prolog?

Prolog would not usually be described as a functional language.
Logo on the other hand *is* a functional language. Not a pure
functional language, but few are.

It's possible to write functional programs in almost any computer
language. Calling something a functional language is more about how
it's typically used (or intended to be used) than about what can be
done with it. Logo certainly emphasises the solving of problems by
calling functions, often with recursion. Prolog's characteristic
features are its use of unification and backtracking search, and it
is naturally described as a logic programming language.

-- Richard

 

[David Brown]

Are you thinking of Prolog?

Prolog would not usually be described as a functional language.[/QUOTE]

Prolog is most often described as a logical language, rather than a
functional language. Typically you define various types of
relationships and propositions, give the system some facts, and then ask
it some questions that it can infer from the facts and rules. But if
you are using it for more general programming, you use a style typical
of functional programming languages - the emphasis is on stating the
desired results, rather than on how the system is to calculate those
results.

I also thought Walter meant Prolog - there are certainly types of
problem that can be solved much more naturally with Prolog than with
imperative languages.

Logo on the other hand *is* a functional language. Not a pure
functional language, but few are.

I've heard Logo described as a functional language before, but I
disagree. To be a functional programming language, functions should be
first class objects - i.e., functions that take other functions as
arguments, and return new functions, should be a natural part of the
language and typical programs. States and global data should not exist
in a pure functional programming language (though as you say, few are
pure), and the language should be amenable to mathematical manipulation
and proof (having no state makes this much easier).

In practice, Logo is almost always used in the context of teaching, and
with turtle graphics. Few people use it beyond the stage of simple
procedures.

The reason I think Walter does not mean Logo is that I can't think of
any features it has that would make it a good choice for general
programming or the "tough problems" he mentioned. It is a great
language for its purpose, but not for tough problems.

It's possible to write functional programs in almost any computer
language. Calling something a functional language is more about how
it's typically used (or intended to be used) than about what can be
done with it.

I agree mostly, although I think being a functional programming language
is just as much about what the language /cannot/ do as what it can do.
Having no states or variables may sound like a serious limitation to
many people, but it actually gives you the power to do far more
reasoning about the program (and it gives the compiler the same power).
It is harder to make good implementations of a functional language
than of an imperative language, but there is the potential to do a
better job.

 

[Walter Banks]

I can't think which language you mean here, but it's not LOGO - unless
there are two different languages called LOGO. LOGO is targeted as a
learning language appealing to kids - it is a simple interpreted
procedural language tightly tied to a turtle graphics display.

We are thinking of the same language. It is associated with
kids, MIT lego lab, LCSI and learning. It also fits the category
of a language that users describe objectives.

After the turtle has stopped drawing squares and hilbert curves
there is a very nice tool to solve some complex problems. A little like
lisp without the brackets.

I used LOGO to solve some multibody gravitational problems a few
years ago.



Regards,

 

[Walter Banks]

The reason I think Walter does not mean Logo is that I can't think of
any features it has that would make it a good choice for general
programming or the "tough problems" he mentioned. It is a great
language for its purpose, but not for tough problems.

I used LOGO illustrate an example of a language that is
used to where most users rarely think about application
implementation. The kids who use LOGO think about results
and objectives.

LOGO is not a general purpose language for "tough
problems" but we can learn a lot from its use about
what in language design makes users think in abstract
objectives as opposed to implementation.

Regards,

 

[David Brown]

We are thinking of the same language. It is associated with
kids, MIT lego lab, LCSI and learning. It also fits the category
of a language that users describe objectives.

Well, sort of...

After the turtle has stopped drawing squares and hilbert curves
there is a very nice tool to solve some complex problems. A little like
lisp without the brackets.

I used LOGO to solve some multibody gravitational problems a few
years ago.

You /can/ use Logo for all sorts of programs - but it is not one people
would typically use. I think that anyone who likes Logo should try
Python - it has a lot more functional programming capabilities than Logo
(list comprehensions, function objects, lambda operator, etc.), as well
as having a lot more object oriented and procedural programming
capabilities and many more libraries (including ones for turtle
graphics). I can't think of anything that you can do with Logo that you
can't do better with Python (except teach kids).

 

[David Brown]

I used LOGO illustrate an example of a language that is
used to where most users rarely think about application
implementation. The kids who use LOGO think about results
and objectives.

I don't agree here (perhaps as a compiler writer you are thinking of
"implementation" in terms of generated target code - then I'd agree).
Kids use Logo to learn about programming concepts, and how to get the
computer to do what you want it to do. They learn to write things like:

TO SQUARE :size
REPEAT 4 [ FD :size RT 90 ]
END

This is entirely about writing an imperative implementation of how you
want the system to draw a square.

Compare this to a sample program in a real functional programming
language, Haskell:

factorial 0 = 1
factorial n = n * factorial(n - 1)

Here you tell the system what you want - you give a mathematical
description of the results. You don't care how it gets them - maybe it
uses recursion, maybe it uses iteration, maybe it builds up a cache of
calculated values as it goes along.