Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
It's Time to Rethink Programming Languages from the Ground Up

By tscola in Op-Ed
Thu May 03, 2001 at 08:46:11 PM EST
Tags: Software (all tags)
Software

The lineage of virtually all programming languages in common use today can be directly traced back to a handful of languages that were invented in the late 1950s and 1960s. These languages were invented to solve batch programming problems on monolithic uniprocessor systems. They were never meant for today's programming problems, and greatly hamper our ability to solve them.

As noted by John Backus 24 years ago, programming languages are too closely tied to the von Neumann architecture, and we are way overdue for a change.


PLEASE NOTE: I am not a language designer, and I am not a compiler writer. These opinions are based solely on my experiences -- and my frustrations -- with the current choice of programming languages.

I don't plan on making this essay a history of programming languages, but to briefly -- and simplistically -- summarize things, high-level computer languages were invented in the late 1950s. What followed was an explosion of different computer languages, most of which died away. One computer language, Algol, became very influential in the design of languages that proceeded it. One Algol successor was particularly influential: Simula, which introduced object-oriented programming. Note that object-oriented programming took about 15-20 years to be adopted by programmers for mainstream use.

In the 1970s, several other important programming language concepts were developed, most notably exceptions, paramaterized types and concurrency. These concepts were adopted by the Ada language in 1980. But Ada was never really successful outside of the military, and the concepts it expounded are only being adopted by programmers now.

Since then, there haven't been any significant new features in programming languages. Two of the most widely adopted languages today, C++ and Java, are fairly recent, but they contain mixes of features found in older languages, and don't have any significant innovations.

What these languages have in common is that they are all closely tied to the von Neumann architecture. Variables refer to words of memory. The flow of control is linear, structured using if and while statements (or syntactic variations of them), and have synchronous subroutine calls.

However, in the last 40 years, computer hardware has become significantly more complicated. Data is no longer held in fixed memory locations, but instead can exist in various levels of cache, or in registers. Computer hardware can execute instructions in a different order than specified by the programmer. However, all of this is hidden from the programmer, and the same simple computer model is still presented.

The type of programming problems has also changed in the last 40 years. Instead of simple batch programming jobs with very few inputs and outputs, today's applications are GUI based and highly interactive. The computer system often has multiple CPUs, and the program should be efficiently spread across them. The program itself might be distributed, and run across many computers which may be anywhere on the globe.

The one key idea here is that a computer program has to deal with events from many different input sources, all of which can occur asynchronously. The program often spends less time performing computations, and more time switching data between its various input and output sources. The channels often have high latencies, and the program usually spends much of its time waiting for events to happen.

Using today's computer languages, there are basically two ways of handing this type of problem. One is to have a main loop in your program -- an event loop -- that listens to all of the program's input sources and then dispatches the data using subroutine calls, i.e. callbacks. The problem is that dealing with stateful data using callbacks is extremely difficult. The other way is to use threads, where each thread listens to its own input source, and deals with its own state. The problem here is that threads are a very low-level concept. Transfering data between threads is difficult. It is very easy to write code which is not "thread-safe", and the compiler will provide the programmer with little guidance writing safe code.

The underlying problem with both of these solutions is with the programming language. While the languages let the programmer write code where the flow of execution is structured, they provide little help for structuring the flow of data. Callbacks and threads are bad because they obscure the flow of data through the program.

This is a problem that has long been recognized by computer scientists, yet ignored by programmers. In 1977, John Backus gave his Turing Award lecture, "Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs." [1] In this lecture he proposed FP, a functional programming language. The key features of his language was that it had no variables, and no side-effects. The good part about this design is that it solves our dataflow problem -- the dataflow is now highly structured. However, it still exhibits the same problems if state management that we had with callbacks.

Another good approach, which would solve our state management problem would be coroutines. Coroutines were described by Knuth in The Art of Computer Programming.[2] They were implemented in Simula, yet sadly, not in the languages that evolved from it. However, coroutines are starting to gain in popularity, mostly through the efforts of the Stackless Python effort.

Another problem with both function calls and coroutines as a dataflow mechanism is that they are synchronous. A program must explicitly transfer control to a (sub/co)routine, and control must be explicitly returned. This can lead to tremendous inefficiencies when writing distributed code.

A popular model for distributed programming is the remote procedure call, whether implemented as Sun-RPC, RMI, CORBA or SOAP. This purports to make distributed programming simple by letting the programmer use a mechanism that is readily available in her programming language of choice -- the subroutine call. However, trying to simulate a synchronous subroutine call over an asynchronous message passing channel is extremely inefficient. A program must block while it waits for a result. Of course, you can thread your program to get around this, but at that point the alleged benefit of the RPC model -- its simplicity -- starts to become illusionary. The problem is that you are trying to bend the distributed programming problem to fit the limitations of the programming language, rather than the other way around.

My ideal programming language would have the following features:

  • The flow of data would be explicit and structured.
  • The program can easily handle multiple inputs and outputs.
  • The program can handle input and output asynchronously.
  • Input and output can be pipelined at all stages to deal with latencies.
  • Programs should be easily scalable across many CPUs and across networks.

The limitations of current programming languages is only going to become worse as computer architectures evolve. At a recent conference, Ivan Sutherland described the architecture of his asynchronous CPU [3]:

FleetZero replaces synchronous arithmetic operations with data-movement operations among asynchronous processor blocks called ships. In place of synchronous chips' instructions are binary codes that specify the routes data items need to take among the processor blocks to accomplish the same tasks that synchronous chips perform via sequential operations. Software compilers would manage on-chip communications, routing data among the asynchronous blocks.

This CPU would implement in hardware all of the features I described above. It would be a shame if we didn't have a programming language to take advantage of it.

[1] John Backus: Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. CACM 21(8): 613-641(1978) (Can anyone find a link to this article?)

[2] Donald E. Knuth: The Art of Computer Programming. Third Edition, Addison-Wesley, 1997 <http://www-cs-faculty.stanford.edu/~knuth/taocp.html>

[3] "Scrap system clock, Sun exec tells Async". EE Times, 03/19/01. <http://www.eetimes.com/story/OEG20010316S0046>

Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Related Links
o The Art of Computer Programming
o described
o &lt;http:/ /www-cs-faculty.stanford.edu/~knuth/taocp.html&gt;
o &lt;http:/ /www.eetimes.com/story/OEG20010316S0046&gt;
o Also by tscola


Display: Sort:
It's Time to Rethink Programming Languages from the Ground Up | 94 comments (90 topical, 4 editorial, 0 hidden)
Thoughts (4.40 / 5) (#1)
by ucblockhead on Thu May 03, 2001 at 02:35:04 PM EST

I liked this article, and voted +1, FP. I also agree with the gist of it. We desperately need to design a new language from scratch, rather than building yet another evolutionary language. However...

Transfering data between threads is difficult.
This is not really true, after all, the whole point of threads is that they share address space. "Transfering" data between threads is fairly easy when compared to transfering it between processes.

That said, coordinating multiple threads is a very hard task, and having a language designed from the ground up would be a very useful thing.

Data is no longer held in fixed memory locations, but instead can exist in various levels of cache, or in registers.
While this is true, strictly speaking, it doesn't really mean much as nothing has really changed from a programmer's perspective. To the programmer, it still seems as if the memory locations are fixed. And this is a very, very good thing, because making the programmer worry about caches and paging and such is a needless complication.

But those are nitpicks. Otherwise, I agree completely.

(I've actually used FP, by the way, back in my college days in my Programming Languages class. Interesting concept, though I don't remember if it had anything to deal with multiple processes.)


-----------------------
This is k5. We're all tools - duxup

Concurrency in FP (3.00 / 1) (#2)
by hading on Thu May 03, 2001 at 02:45:19 PM EST

I'm not that familiar with the details, but concurrency is supported in some FP languages (e.g. SML/NJ with Concurrent ML, Concurrent Clean, etc.). Perhaps the poster boy for concurrent FP programming, though, is Erlang, which is primarily designed to handle telecommunications problems. A short quote from the Erlang FAQ:

1.3. What sort of applications is Erlang particularly suitable for?

Distributed, reliable, soft real-time concurrent systems.

...

Concurrency and message passing are a fundamental to the language. Applications written in Erlang are often composed of hundreds or thousands of lightweight processes.Context switching between Erlang processes is typically one or two orders of magnitude cheaper than switching between threads in a C program.

Writing applications which are made of parts which execute on different machines (i.e. distributed applications) is easy. Erlang's distribution mechanisms are transparent: programs need not be aware that they are distributed.



[ Parent ]
The language.. (3.00 / 1) (#4)
by ucblockhead on Thu May 03, 2001 at 02:49:33 PM EST

I was talking about the language "FP", not FP languages in general....

That's good info, though.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]

oops (3.00 / 1) (#9)
by hading on Thu May 03, 2001 at 03:08:35 PM EST

Sorry, my fault for not noticing that FP was used in the article to name a specific language. Hopefully someone will find the information useful anyway. :-)



[ Parent ]
FP has little to do with multiple processes (4.00 / 2) (#5)
by Carnage4Life on Thu May 03, 2001 at 02:51:37 PM EST

I've actually used FP, by the way, back in my college days in my Programming Languages class. Interesting concept, though I don't remember if it had anything to deal with multiple processes.)

From the comp.lang.functional FAQ
Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands. The expressions in these language are formed by using functions to combine basic values. A functional language is a language that supports and encourages programming in a functional style.
The core idea behind FP is moving away from representing ideas in the computer-centric manner that most of us are currently used to. Programs are usually simply long lists of expressions to evaluate or simply put "lots of recursive function calls" as can be evidenced in Lisp, Scheme and the like.

[ Parent ]
I know, but... (3.00 / 1) (#13)
by ucblockhead on Thu May 03, 2001 at 03:32:55 PM EST

Yeah, I know, but I was talking about the (confusingly named) language called "fp", not functional programming in general. (Since the story talked about concurrancy a lot.)
-----------------------
This is k5. We're all tools - duxup
[ Parent ]
Danger Will Robinson (5.00 / 4) (#24)
by SlydeRule on Thu May 03, 2001 at 09:33:37 PM EST

Transfering data between threads is difficult.
This is not really true, after all, the whole point of threads is that they share address space. "Transfering" data between threads is fairly easy when compared to transfering it between processes.
Data is no longer held in fixed memory locations, but instead can exist in various levels of cache, or in registers.
While this is true, strictly speaking, it doesn't really mean much as nothing has really changed from a programmer's perspective.
Reread those two points, then put them together.

Programmers who believe that transferring data between threads is easy and that caching is irrelevant to the programmer are making a huge mistake. A growing number of magazine articles are trying to sound the alarm, but the coders keep trudging onward, under the delusion that they understand what they're doing.

Here's the most obvious glitch. If you have a multi-processor system, and the processors both have cache, you cannot simply store something in memory in one thread and expect it to immediately be seen in another thread. The other thread may be running in another processor and may be using a cached copy of the data.

This is only the most obvious facet, though. There are so many aspects of this problem. Consider, for example, the effects of lazy-write caches, optimizing compilers which hold variables in registers and defer or eliminate the actual store into memory, optimizing compilers which reorder instructions, and pipelined CPUs which execute instructions speculatively.

It's a bloomin' nightmare, and one which requires careful consideration when trying to communicate data between threads.

[ Parent ]

Nice article, it shows what most people don't know (5.00 / 2) (#29)
by Carnage4Life on Thu May 03, 2001 at 11:43:21 PM EST

Programmers who believe that transferring data between threads is easy and that caching is irrelevant to the programmer are making a huge mistake. A growing number of magazine articles are trying to sound the alarm, but the coders keep trudging onward, under the delusion that they understand what they're doing.

Transfering data between threads is easy if people follow the rules. The number one rule of multithreaded programming is
All accesses to shared variables must be protected by locks.
The DCL idiom mentioned in that article was fundamentally flawed because it broke the above rule which typically leads to non-deterministic behavior regardless of whatever language you are using. This could have been solved by using synchronized methods unfortunately they chose to synchronize within the method body (which is typically more inefficient) given the current JVM standard.

[ Parent ]
"Easy, just follow the rules!" (none / 0) (#56)
by Steeltoe on Fri May 04, 2001 at 04:46:22 PM EST

Yeah, that's what they'd like us to believe. It's easy to come up with easy examples that works every time. Try sharing an arbitrary graph in which you can switch, add and remove references between the nodes without resorting to the bullet-proof solution of locking the whole thing. Try avoiding deadlocks, race conditions and inefficient avoidance-techniques of these. I don't think it's very easy, since you HAVE to taylor the solution to the problem to get any efficiency. Try tracking down thread-bugs that others have made. I usually recommend to avoid using threads if you can.

- Steeltoe

[ Parent ]
Graph lock granularity (none / 0) (#64)
by bored on Fri May 04, 2001 at 06:02:17 PM EST

"Try sharing an arbitrary graph in which you can switch, add and remove references between the nodes without resorting to the bullet-proof solution of locking the whole thing"

Easy... :> Per node lock. You lock all referencing nodes, make the update then unlock the locked nodes. Of course that might be a little fine grained for your application. I'm sure there is a nice compromise with the way you store data into the graph, that gives you something a little more ideal. Data structure locking is one of the fun parts of designing a modern piece of software.



[ Parent ]

Hehe (4.00 / 1) (#80)
by Steeltoe on Sat May 05, 2001 at 08:58:12 AM EST

Yeah, very "easy". :-)

I've defined my own solution to the problems I had with this, similar to yours. I won't go into details here though, because that depends on the project.

What I forgot to mention was that the methods working on the graph would have to traverse the graph to find out which nodes to lock. Also, it's not always possible to know excactly the number of nodes to lock before you've started computing with them. And if you lock them in a non-blocking sequence, deadlocks may/will occur (unless you only lock them in one and only one path-direction of the graph). If you lock, unlock, and then try to lock including more nodes, the state may have changed so that the conditions you previously had for doing so is now false. Trying to figure out all this makes your head hurt after a while ;-)

I'm not sure if anyone has done any mathematical analysis on this, but I suspect one general solution to any arbitrary problem of this kind is close to impossible to find. You need to find constraints for your code and data (which I only wish I had a programming language to express in).

It IS fun to do it when you know what you're doing. But I would hate to have to try to understand how a newbie worker did it, and one month later realize his design is all wrong. As Homer Simpson says it: Doh!

- Steeltoe

[ Parent ]
Yup. (4.00 / 1) (#91)
by bored on Mon May 07, 2001 at 01:20:21 PM EST

Yup, like I said there may be more optimum methods for locking than per node. The deadlock situation can be real in a multiple writer situation. In which case you need some kind of deadlock avoidance. There are solutions to that as well. Not all are that easy, or optimum. Code which backs its locks out when it discovers a node it needs is already locked is a simple solution to deadlock avoidance. Methods for writer arbitration can be fun. Making all your graph links two way avoids the need to traverse the graph to find all referencing nodes. The result is that basic solutions are easy. Getting an optimum one isn't always that easy. I'm sure you know this though.... :> You seem to have a good grasp of your problem. I was simply pointing out that expressing the basic idea was easy even in code, making it optimal, or even proving that it is optimal may be harder. Adding extra steps can complicate the system if you weren't paying attention in the original design. Hence the 'fun' part of designing your data structures.



[ Parent ]
taking into account (3.00 / 1) (#36)
by Pink Daisy on Fri May 04, 2001 at 01:13:41 AM EST

The supporting system is supposed to take memory coherence into account. The hardware is supposed to make sure that memory writes are broadcast and snooped, the compiler that registers are committed where necessary. It's worth keeping up, because experience shows that people have a lot of difficulty with different with different programming models. If you don't believe me, try writing stuff in low level VHDL instead of C... parallelizable, yes, but easy, not in the least.

[ Parent ]
Semantics... (3.00 / 1) (#54)
by ucblockhead on Fri May 04, 2001 at 03:28:06 PM EST

To nitpick: sharing data between threads is trivial. That's the whole point of threads. The tricky part is coordinating access to the data.

But even that isn't that hard. Mutexes are a very old concept.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]

No it isn't (none / 0) (#60)
by SlydeRule on Fri May 04, 2001 at 05:36:51 PM EST

To nitpick: sharing data between threads is trivial. That's the whole point of threads.
That's not a nitpick; that's missing the entire point.

Sharing data between threads is not trivial unless the data is read-only.

The compiler, processors, and caches are conspiring against you. They are reordering and removing your loads and stores because memory references are slow.

Unless both a and b are declared volatile, the statement "a = b" does not mean "pull the current data from memory location a and put it into memory location b". It means "make the variable a (whether in register, cache, or whatever) equal in value to what should be the value of b, whether in register, cache, or whatever, based on the assumption that nobody else has messed with b.

Furthermore, a sequence of statements is not necessarily executed in the order that they appear in the source code. The compiler can reorder them to improve performance as long as the end result as observed in this thread is the same. Statements can be moved far from their original sequence, and even deleted. Pipelined CPUs can reorder instructions, too.

Locking is necessary but not sufficient.

Properly used, locks can prevent simultaneous and conflicting memory access. Properly used, locks can make the apparently bizarre sequence of memory operations as viewed from a different thread irrelevant.

Locks cannot assure that the data that your thread is accessing is fresh. Neither can they guarantee that your results have been stored all the way into the shared main memory where other threads can see them.

The methods for assuring that vary. The basic technique is the volatile attribute on shared data. This is okay for an occasional shared int. It doesn't help with dynamically allocated data, though.

In Java, it's specified that the synchronized keyword controls both mutual-exclusion locking and memory barriers. Java also provides the volatile keyword, which enforces load and store sequence as well as providing memory barriers, but does not necessarily provide mutual-exclusion locking.

Here's another article which gets into more gory detail.

[ Parent ]

It is not that hard... (3.00 / 1) (#65)
by ucblockhead on Fri May 04, 2001 at 06:58:29 PM EST

Seriously. I do it every day. I have been since ~1989 when I first started working on OS/2 1.0. It isn't that hard if you follow a few simple rules and know what you are doing.

And it can be done pretty easily with mutexes, and with the proper use of wrapper classes, can be done pretty damn transparently, too.

I'm doing it right now, in fact. In what I'm working on now, I've got a fairly complex data structure (an STL map, actually) that is shared by two threads.

Language support would certainly be nice of course, but it isn't the sort of impossible problem you make it out to be if you have a common sense design and follow the rules.

(The optimization code rearrangement thing is not the issue you make it out to be because the optimizer is not going to move a statement around a mutex call. Optimizers know what side-effects are.)

You also seem confused about the "cache" and main memory. The processor cache is transparent to code. If two threads hit the same location, they're going to go through the cache and get the same data. The only time this is going to be an issue is if you've got threads on different processors, but to my knowledge, no major OS supports this. Just different processes on each processor.

Yes, data can be in the processor cache, and yes, pipelined CPUs can reorder instructions. But what you seem unclear on is that such systems are designed in such a way that it is utterly transparent to the software. Instructions are only reordered when the reordering has no effect at the cpu level.
-----------------------
This is k5. We're all tools - duxup
[ Parent ]

There are still gotchas (none / 0) (#66)
by statusbar on Fri May 04, 2001 at 07:12:09 PM EST

Yes, optimizers know what side-effects are.
But they don't know about out of order data writes flushing of the cache that is possible on some processors. This isn't a problem in a single processor machines, but IS a problem in SMP machines.

the code for a simple example:
   a=123;
   get_mutex()
   b=456;
   release_mutex();

will have this problem. The other processor may see b set to 456 BEFORE a is set to 123.

On the power pc cpu, you have to use the special instruction:

eieio : Enforce In-Order Execution of I/O
(funny name!)

It is a performance hit to use this. C/C++ both have NO concept of threads or multi-processors. Because of this, the compiler can not know when it should or does not need to use this instruction. So I would hope that all get_mutex() and release_mutex() functions would use it all the time just to be safe. If the language knew about threads and shared objects, then it would be able to do the right thing always.


--jeff

[ Parent ]
Multithreaded vs. Multiprocess (4.00 / 1) (#70)
by ucblockhead on Fri May 04, 2001 at 07:36:10 PM EST

Neither Windows nor Linux will put two user-space threads in the same process on different processors, so your point is moot in the real world.

(And given that the CEO of my company has a dual processor box, you can be damn sure I know our code works on it.)


-----------------------
This is k5. We're all tools - duxup
[ Parent ]

Not true! (none / 0) (#71)
by statusbar on Fri May 04, 2001 at 07:48:54 PM EST

That is ABSOLUTELY not true! At first I thought it might, I JUST wrote a test program under linux on my dual-g4 powerpc. Creates X threads which spin, incrementing a var on each loop.

With X set to 1, I see one CPU go to 100 % usage.
With X set >=2, I see both CPU's go to 100 %.

Try it yourself.

Of course, the linux kernel does use the eieio instruction on a task/thread swap, so your code is safe, and the point IS moot.

--jeff

[ Parent ]
Check the docs (none / 0) (#74)
by ucblockhead on Fri May 04, 2001 at 08:02:50 PM EST

According to the SMP HowTo:

  1. Does Linux support multi-threading? If I start two or more processes, will they be distributed among the available CPUs?

    Yes. Processes and kernel-threads are distributed among processors. User-space threads are not.

So I'm not sure what you are doing, but it isn't what you think you are doing.

Anyway, the point is always going to be moot because if the CPU cache were not transparent to the applications programmer, threading would be near impossible. Because of this, the OS is always going to have to make it invisible.


-----------------------
This is k5. We're all tools - duxup
[ Parent ]

User space threads (4.50 / 2) (#77)
by statusbar on Fri May 04, 2001 at 08:19:05 PM EST

Are not what people use.

glibc contains the pthreads library.

The pthreads library uses kernel threads to implement posix style threads. Specifically, pthreads uses the linux 'clone()' call to create a thread.

User space threads are not used on linux anymore. To use user space threads, you need to use a special library which is not standard on any linux distribution.

How about YOU read the docs on them? Threads in glibc ARE kernel level threads. Previously, pthreads was a separate library, called LinuxThreads. Then LinuxThreads got merged into glibc.

From http://pauillac.inria.fr/~xleroy/linuxthreads/ :

"Unlike other implementations of Posix threads for Linux, LinuxThreads provides kernel-level threads: threads are created with the new
clone() system call and all scheduling is done in the kernel."

"LinuxThreads is now closely integrated in the glibc GNU C library. The initial author of LinuxThreads (Xavier Leroy) is no longer active on
LinuxThreads; maintenance and further developments are mostly handled by Kaz Kylheku and the glibc team, in particular Ulrich Drepper"


--jeff

[ Parent ]
You/your CEO are just lucky (none / 0) (#92)
by VZ on Mon May 07, 2001 at 09:55:35 PM EST

This is completely wrong. Windows NT can happily schedule different threads to run on different processes - and usually does. And, of course, Linux, Solaris and just about anything else do it as well.

[ Parent ]
Multi-processor multi-threading (5.00 / 1) (#72)
by SlydeRule on Fri May 04, 2001 at 07:51:13 PM EST

The only time this is going to be an issue is if you've got threads on different processors, but to my knowledge, no major OS supports this.
Solaris does.

And Sun sells a lot of multi-CPU Solaris boxes.

[ Parent ]

Feature list (4.14 / 7) (#3)
by ksandstr on Thu May 03, 2001 at 02:48:30 PM EST

Writing feature lists is fun. Implementing the language that has all the features in the list usually is not, especially if the feature list was designed by a committee (though I'm not saying the one in the article was).

Even less fun is writing stuff in the newly implemented language. According to your feature list for the Language of the Future, you would have to arrange your code so that it'll be scalable (you'll be dividing your program into very small units which practically kills unix-style quick experimentation) and asynchronous (callbacks, in any traditional programming language -- horrible implicitness in some others) since all this will be a "feature" of the language. Java is a perfect example of this -- in order to have SMP scalability, the standard library forces you to handle socket I/O using a thread-per-connection model (and no matter how threadpooled your connection manager is you still cannot have more clients than you have threads, which becomes a problem if connections can remain idle for a long time). Still worse, this misfeature can't really be turned off without becoming non-100% pure.

In my opinion, a programming language/paradigm/library cannot replace a good, solid design. Never will, either, unless somebody comes up with a way to eliminate the need to specify explicitly what you really want the compiler to emit (which is also the point where you'll have created a machine that can read your mind, eliminating the need for programming altogether).


--
Somebody has to set Imperial America up the bomb.

Re: Feature List (3.00 / 2) (#10)
by tscola on Thu May 03, 2001 at 03:11:37 PM EST

you'll be dividing your program into very small units which practically kills unix-style quick experimentation) and asynchronous
Hmmm... Diving a program up into small units and then connecting them with asynchronous pipelines? That's not the Unix way at all! :-)
In my opinion, a programming language/paradigm/library cannot replace a good, solid design.
No, but the wrong language/paradigm/library can kill a good design.

[ Parent ]
Small units? (3.00 / 2) (#45)
by NoseyNick on Fri May 04, 2001 at 08:05:33 AM EST

"you'll be dividing your program into very small units which practically kills unix-style quick experimentation"

find / -type f | xargs type | grep -i 'image' | cut -d: -f1 | xargs xv

I spot at least 5 small units in the above quick experiment, and some of them create multiple small units themselves. They could all be run on different CPUs already. If they were run on different MACHINES I wouldn't mind much as long as the filesystem was the same.

What on earth's your problem with small units and unix experimentation? That's exactly what unix is all about - plugging together small units to get the job done!



[ Parent ]

Prograph (3.66 / 3) (#7)
by kallisti on Thu May 03, 2001 at 02:54:16 PM EST

Prograph is probably the most successful dataflow-oriented language. It is also visual, object oriented, proprietary, and expensive. It requires a very different way of thinking about programming, so this may be a step towards what you are thinking of.

"I say, don't you watch the movies, man? That's been tried. The Spaniards tried it, they curled their mustache to the plain of time. And there was no relief..." - Robert Ashley, Perfect Lives.

Well, (4.44 / 9) (#11)
by trhurler on Thu May 03, 2001 at 03:20:33 PM EST

As it happens, the conclusion may be right even though the rest is crap. We're still using von Neumann machines, for all intents and purposes.

Caches are irrelevant; they are SUPPOSED to be transparent, and if they weren't, they wouldn't work very well.

Yes, our systems have a harder time moving data than processing it, but this is a hardware difficulty; it has nothing to do with the language you program in.

That said, if you can find a way to run multiple processors on one task more naturally than we presently do, you'll get famous. Have fun.

--
'God dammit, your posts make me hard.' --LilDebbie

Re: Well (4.00 / 2) (#16)
by tscola on Thu May 03, 2001 at 05:41:35 PM EST

We're still using von Neumann machines, for all intents and purposes.
Are you writing a program that communicates with another computer across a netowrk? Then you're not using a von Neumann architecture any more.
Yes, our systems have a harder time moving data than processing it, but this is a hardware difficulty; it has nothing to do with the language you program in.
Ah, yes, but the other computer architecture (as in: The Network Is The Computer TM) has a much easier time moving data than processing it. It's a shame we don't have a language to take advantage of it.

[ Parent ]
Not quite transparent (4.00 / 3) (#22)
by KWillets on Thu May 03, 2001 at 08:55:47 PM EST

Caches are irrelevant; they are SUPPOSED to be transparent, and if they weren't, they wouldn't work very well.
Caches work on only one assumption, that data that is accessed once will be accessed again soon. That assumption falls apart when you do, eg, a single-pass scan of a large memory block. The cache ends up full of junk. I should also add that cache takes up tons of transistors and power, with only 32-64 bits of it active in any one cycle.

It wouldn't hurt to have a "nocache" modifier on memory instructions (and C, etc. pointer declarations) to avoid the cache-filling phenomenon.

Also, it should be noted that Transmeta, etc. use the cache as a "Gated Store Buffer" which holds memory writes until a suitable commit point has been reached, or an exception causes them to be abandoned. That's non-trivial functionality, which also happens to be very useful for speculative execution.

[ Parent ]

Caches (3.33 / 3) (#28)
by statusbar on Thu May 03, 2001 at 11:42:19 PM EST

Yes, and the G4 has special cache control instructions which are quite nifty and can provide a HUGE speed increase in programs when used correctly - like 50 to 100%. You can tell the cache controller things like "Soon I am going to need x blocks of data from over there, each block is y bytes long and each block is separated by z bytes. oh, and I'll only be needing this data temporarily, so don't throw out anything important from the cache". And then the cache controller will go out and pre-fetch the data while you are busy munching on the previous data.

Right now, no language has a concept of this. You can inject these instructions manually, but they have to be hand tuned. The language should be expressive enough for the compiler to know when these instructions will be useful and figure out how to tune them by itself! The C, C++ and Java languages are ALL incapable of expressing this. Even with the complexity of C++ and templates!

We are still mostly living in the dark ages of computer languages.


--jeff

[ Parent ]
You shouldn't have to (3.66 / 3) (#42)
by jynx on Fri May 04, 2001 at 04:57:11 AM EST

Surely, this is exactly the kind of detail you shoudn't have to express in a language. The compiler should work it out for you.

--

[ Parent ]

yes! (3.00 / 2) (#49)
by statusbar on Fri May 04, 2001 at 12:28:16 PM EST

Sorry if I wasn't clear... In C and C++ there is NO way for the compiler to FIGURE OUT that the cache control instructions may be useful. In a better language, the compiler would be able to decide on its own where to put the cache control instructions for best results.

--jeff

[ Parent ]
That's not necessarily a good thing. (4.50 / 4) (#46)
by trhurler on Fri May 04, 2001 at 10:51:59 AM EST

First of all, as another poster noted, the compiler should figure that out for you; if it has to be in the language, then it will never get used right, because most programmers won't understand it and the ones who do won't understand the way optimization and runtime insertions modify their code well enough to do the right thing.

Secondly, that's one of the most questionable decisions I've ever seen in cache design. Maybe you can write a little sample code that it speeds up a lot, but I bet the usual case is that after you add in the cost of those instructions, you have to be doing some pretty heavy access to sizable chunks of memory before it is a win to use them. Remember, the cost is not merely in the instructions themselves; this sort of thing slows the cache down overall.

--
'God dammit, your posts make me hard.' --LilDebbie

[ Parent ]
Cache control (3.00 / 1) (#48)
by statusbar on Fri May 04, 2001 at 12:25:48 PM EST

My point was that C and C++ languages do not provide enough information to the compiler in order for any C or C++ compiler to automatically figure out when these cache control instructions would be needed. Not that the language needs a 'Cache Control' syntax.

In actual fact it isn't a questionable cache design! It works very very well in the real world. Programs like photoshop use it very effectively to speed up some image processes up to 50%.

Go to www.altivec.org for more info


[ Parent ]
Have you ever studied dataflow analysis? (4.50 / 2) (#50)
by trhurler on Fri May 04, 2001 at 12:34:00 PM EST

You certainly can figure out where to put cache control instructions. Not perfectly, but better than most programmers will manage, especially if you have other optimization going on. Not only that, but there are optimizations that can make caches more effective even without any special control over them. The fact that most C compilers suck does not limit what could be done.

Anyway, if you don't know much about it, buy the 2nd version of the dragon book and look up dataflow analysis. This is already a very dated book, but you'll find that there is a lot that you can do with C and similar languages, given cache control instructions. For instance, variables used in innermost loops - these should stay in the damned cache, no matter what, while you're in that loop - unless you run out of space. Globals accessed all over the code, same story. On the other hand, it is trivial to say that if a variable is dead before the first loop or goto target, you should ignore it. It can get a lot more complex than this, but I'm only now learning some of that stuff, and more to the point, it takes up whole books, so I obviously can't write it all down here:)

Anyway, yes, I'm sure Photoshop can benefit. Photoshop also goes through huge amounts of data quickly - it is NOT a typical program.

--
'God dammit, your posts make me hard.' --LilDebbie

[ Parent ]
Scanning data. (4.00 / 1) (#53)
by ucblockhead on Fri May 04, 2001 at 03:24:50 PM EST

Even when scanning data, a lot of important stuff is going to be usefully cached. For example:

for(long i=0;i<1000000L;i++){<BR>   Foo = AllTheFoos[i];
  BarIt(Foo);
}

Yeah, you are going to put some stuff in the cache which never gets hit again. But you are also going to have some that should be in the cache, like 'i', and the code that makes up the loop, and the code in BarIt(). That ends up being quite a bit.

And as you say, it isn't that hard for the compiler to figure out what's going on here and potentionally not bother to cache the data in 'Foo'.

(Though a good compiler will make 'i' a register variable, but anyway...)
-----------------------
This is k5. We're all tools - duxup
[ Parent ]

Caching and pipelining (4.00 / 1) (#55)
by statusbar on Fri May 04, 2001 at 04:26:13 PM EST

Yes, in that case the compiler can figure out how to do the cache instructions. Although there is still one thing missing - There is no way to tell the compiler that this is transient data. This is important.

The only way for the compiler to know if it is transient data is for the compiler to know if other functions are going to be usually re-using that data later. With C/C++ the compiler can't know - You have to manually profile the whole thing and measure, and tune the cache control instructions. A functional language WOULD be able to know - and it could generate a new loop automatically customized for the parameters that are used.

The cache control instructions used also depend on what BarIt() does, how long it does it for, and what other data it uses.

Another thing that C can't do is merge similiar loops to reduce pipeline conflicts.

For instance if you had two loops like your example one after another, it should be able to automatically merge the contents of the loop into a single loop - possibly interleaving the two calls to BarIt() into one function BarIt2(). BarIt2() would contain interleaved instructions that would allievate pipeline stalls. The C/C++ standard does not allow this kind of optimization.

For an example take a look at http://www.jdkoftinoff.com/eqtest.tar.gz

It is a program I wrote to test parametric equalizer algorithms on audio data sets that are larger than the cache size. It has two seperate functions for both altivec and non-altivec processors, and the altivec versions can be with or without manual cache control instructions. The two other versions do either groups of 1,2,4 or 8 audio channels per loop iteration.

Even though the basic algorithm to do a biquad filter is the same, right now you have rewrite it for each case. And it is not because the C/C++ compilers are not good enough (although the keyword 'restrict' would help a little). It is because the language of C/C++ is too low level to allow the compiler to really understand what it is you are trying to do.


--jeff

[ Parent ]
Actually, (none / 0) (#58)
by trhurler on Fri May 04, 2001 at 05:29:28 PM EST

A C/C++ compiler can in fact verify liveness of variables. Granted, it has to be a bit conservative, but you still gain an awful lot - more than you would if you had a programmer sticking inline asm into the source to try to control the cache, for damned sure. This is one area where well written code is much easier to optimize, btw. The problems with C/C++ usually stem from bad implementation decisions on the part of the guy writing the code to be optimized. It is trivial to optimize a program that rarely if ever uses globals and so on. Sure, you may never verify that a given global is dead, but if 99.9% of data is not global, you can still do a damned fine job; inside a single function liveness is certainly computable.

--
'God dammit, your posts make me hard.' --LilDebbie

[ Parent ]
Liveness of variables (none / 0) (#63)
by statusbar on Fri May 04, 2001 at 05:55:48 PM EST

Yes I agree that most problems stem from crappy compiler implementations. And the new 'restrict' keyword can be used to help the compiler.

But there are cases where the compiler can't know the liveness of variables. For instance, when your data is NOT in a variable and is accessed via a pointer.

My data in my specific situation has been placed into RAM via DMA. When the DMA happens I have to be sure that the old data is NOT in the cache otherwise I get a cache-snoop penalty on every DMA write to dram.

When I run my processing algorithm on the data I have to put in the inline asm to tell the cache controller to pre-read that data as transient data.

In C/C++ I can not specify that data is transient - it is not truly 'volatile' either. If I could specify that a buffer is transient to the compiler, then the compiler would be able to do the right thing.

I guess C/C++ would need a 'transient' keyword or something like that. Then with proper data flow analysis the compiler could do the right thing.

It may sound like my situation is highly specialized, but in fact it isn't. Every web server that reads a file from disk into memory buffers and streams it out via a socket would benefit from this.

Hence the need for the new 'sendfile()' function call in Linux and its equivalent in Win32. They are explicitely hand written to manage the (filesystem) cache efficiently so that the transient data isn't manually copied between internal buffers.

The same concept is needed for hardware caches.

--jeff



--jeff

[ Parent ]
Data Flow (none / 0) (#57)
by statusbar on Fri May 04, 2001 at 05:13:52 PM EST

Thanks for the info.

Yes, there are some things that C/C++ compilers should be able to do. However, large data sets may be accessed via global pointers by various functions, even though the data should be marked transient - or not. Of course it is very complex. But a better language would be able to give an easier data flow analysis job to the compiler.

For instance if you have a complex function called in various ways, within different looping constructs and contexts, the compiler should be free to create new equivalent functions automatically, each optimized for that situation.

--jeff

[ Parent ]
Cache prefetch and stuff.. (5.00 / 1) (#62)
by bored on Fri May 04, 2001 at 05:53:27 PM EST

Most processors have 'streaming' instructions as well as prefetch hints. The x86 has stuff like this for years. The MMX,SSE and SSE2 instruction sets have extended it each generation quite a bit. There is both prefetch this block and please access this data without letting it go into the cache. If you don't let streaming data into the cache you get application performance improvement due to not dirtying the cache.

I point this out as a side issue because it is really just a crutch for lack of Si on processors. The P4 has new fencing instructions too. It also has a cache that can detect streaming accesses and prefetch them. The massive application data transfer benchmarks have been partially attributed to rambus but the truth is the P4 does a much better job at automatically prefetching accesses than any other processor on the market. Eventually data prefetch and streaming logic will get good enough that the compiler won't have to provide static analysis of the data stream. The end result will be much better runtimes than can ever be achieved with just static analysis.



[ Parent ]
Code vs. Data (3.00 / 1) (#52)
by ucblockhead on Fri May 04, 2001 at 03:16:44 PM EST

Caches are most important for code, not data, and code often is executed repeatedly.


-----------------------
This is k5. We're all tools - duxup
[ Parent ]

Transmeta 'gated store buffer' and exceptions (4.00 / 1) (#61)
by bored on Fri May 04, 2001 at 05:37:42 PM EST

What I understand is Transmeta does this because its hard to have precise exceptions when your runtime optimizer is reordering the code. What they do then is mark a start point where everything is in order, then they start executing a piece of code. If the code completes successfully then they flush the results and rest the mark. If the code takes an exception then they roll it back to the last check point and execute everything in order till they hit the exception at which point they throw it in the manner expected by the X86 application or OS that is running.



[ Parent ]
MLP: GUIs for FPLs (3.80 / 5) (#12)
by Puchitao on Thu May 03, 2001 at 03:25:35 PM EST

You might already be aware of this, but there's some interesting work being done on GUIs in functional languages. Fudgets (functional widgets) and FranTk are two GUI libraries for Haskell (a descendent of FP) that work within the Monadic I/O framework, so as to allow GUIs -- written in a concise declarative style -- that don't break the nice properties (like referential transparency) of a pure functional language. (I've never used either, so anyone who has please speak up about whether they succeed or not.)

Clean, a close relative of Haskell, has a pretty mature graphical I/O library based on its preferred model, uniqueness types. An effort is underway to port it to Haskell.

If you're not familiar with any of these efforts, they might be worth checking out. Although undernearth, their machinery is fairly conventional, the representation of these GUI programs within a functional structure allows one to reason about their behavior much more easily than one could in a purely imperative environment.

We are happy *people energy* from the *outside*! -- Orz
My ideal programming language has one command (4.77 / 9) (#14)
by marlowe on Thu May 03, 2001 at 03:39:49 PM EST

dowhatiwant();

...and it always works.

But seriously, folks. It's nice to point out that we need to rethink our programming language pradigms, but it's an observation that borders on the trivially obvious. And even your list of desired features is more a wish list than a game plan.

Over on the old Infoworld forums, there was this guy who said OOP is crap, and he kept pushing this notion called Table Oriented Programming. But his main focus was saying that OOP is crap. After many months, we shamed him into doing a first-pass specificication for this vague idea for a language we had. It was interesting, but we had doubts it could be implemented, by anyone, let alone him. I never did hear if he started implementing it.

My point is: the proof is in the pudding. It's easy to criticise the status quo, and suggest vaguely that we can do better, because you're comparing reality to a fantasy, and the fantasy will always come out looking better. But if you want to sway skeptics such as myself, you're going to have to actually design and implement something. It needn't be perfect, just usable. It can be rough, so long as it demonstrates a new concept, and we can all play with it and see for ourselves that such a thing is possible.

Let these three words be your mantra: PROOF OF CONCEPT.

-- The Americans are the Jews of the 21st century. Only we won't go as quietly to the gas chambers. --
with apologies to Jack Handey... (3.75 / 4) (#20)
by Puchitao on Thu May 03, 2001 at 07:59:58 PM EST

It's easy to sit there are wish for more features. And that's what I like about it. It's easy. Just sitting there, rocking back and forth, wanting those features.

Perhaps we can do *snappy fun* with you everytime! -- Orz
[ Parent ]
Ideas come first (4.33 / 3) (#26)
by BigNachos on Thu May 03, 2001 at 10:28:43 PM EST

But, long before you have a proof of concept, you have a single idea. Then, perhaps, that idea mutates, other ideas form around it, and you get a vague collection of ideas. After that, you mention it to a friend, who adds his own ideas or points out some faults in yours. Then, you repeat this process, gather up more ideas, throw some others out, post to a public forum and discuss, talk to some college professors, etc. etc. A few years later, if things pan out, you may have a coherent plan and you can form a proof of concept. If not, you can start over with a new idea.

Who are you to interupt this process? What's wrong with throwing around ideas? You aren't going to get a proof of concept without ideas.

[ Parent ]

OOP isn't crap: OOP people are crap (2.00 / 2) (#86)
by exa on Sun May 06, 2001 at 03:03:52 PM EST

Because many managers and lamer-corporate-programmers think OO is a silver bullet and UML can describe everything.

I'd really like to smash the faces of one or two "researchers" in Software Engineering doing all the "object oriented design" and "component technology" bullsh**.

__
exa a.k.a Eray Ozkural
There is no perfect circle.

[ Parent ]
Asynchronous CPUs (3.00 / 1) (#15)
by Morn on Thu May 03, 2001 at 05:08:33 PM EST

Are here now (though they're not exactly as described). In fact, they were launched today.

Take a look at Metagence Technologies.

Asynchrony (3.00 / 1) (#19)
by Simon Kinahan on Thu May 03, 2001 at 07:00:09 PM EST

There's been an asynchronous variant on the ARM for several years, called Amulet. A friend of mine redesigned a commonly used microcontroller in an asynchronous style. In general, async logic is only beneficial if you need very low power consumption (and I mean *very* low), as the design overhead is large (though admittedly this is partly through lack of tools), and the speed benefit is small or negative.

Simon

If you disagree, post, don't moderate
[ Parent ]
also for mixed analog circuits (3.00 / 1) (#35)
by Pink Daisy on Fri May 04, 2001 at 01:04:10 AM EST

Clocked circuits have a big RF spike around the clock frequency. Very bad for things like mobile phones.

[ Parent ]
The language isn't really the barrier (3.00 / 3) (#17)
by gblues on Thu May 03, 2001 at 05:51:38 PM EST

You want to know why we don't use functional (e.g. algebraic) programming languages? Because most microprocessors don't work that way. Even if you design a language that avoids Von Neumann concepts, the compiler/interpreter still has to convert it into a Von Neumann program so the CPU can understand it. This, like OOP, simply becomes an abstraction layer between the programmer and the hardware, resulting in slower and less efficient code.

Nathan


... although in retrospect, having sex to the news was probably doomed to fail from the get-go. --squinky
Definitely not true (4.00 / 1) (#23)
by KWillets on Thu May 03, 2001 at 09:06:42 PM EST

If you look at VLIW architectures you find patterns of speculative execution which are very tree-like and amenable to functional languages. The different pipelines are used to explore different branches of a tree, for example both branches of an if statement, while the condition is being evaluated in a third pipeline. I doubt if we'll all be writing ML soon, but things like low-level OS code should be written to take full advantage of VLIW. It's like C 20 years ago; the first use was to write unix, because C was closer to the (then Von Neuman) architecture than other 3GL's. Nowadays C is no closer to the hardware than COBOL was then.

[ Parent ]
VLIW Needs new languages (4.00 / 1) (#27)
by statusbar on Thu May 03, 2001 at 11:30:06 PM EST

I've been doing lots of coding on a VLIW based DSP. If you do things right, this cheap 150 Mhz chip can pull off almost a gigaflop. It is the Texas Instrument C6701 DSP, but i'm sure the same problems will be found when programming the IA64.

But it is hell to program in C and C++. Put plainly, C style languages are horrible for this architecture. C style languages do not allow for the expression of functions in a way that is nice for the compiler or chip.

What I have wanted for a long time is a pure functional language that could compile directly to the chip architecture. If I can specify my algorithm in a pure functional way, then the compiler should be free to re-order the evaluations in whatever order is needed to be most efficient on the DSP/CPU architecture. The same source code then could be compiled optimally for pentium, various DSP's, and G4 Altivec. Right now, even the simplest parts have to be recoded in C by hand to be optimal on different architectures.

Unfortunately, when I brought up this idea to comp.lang.functional, it ended up in a flameware between the lazy evaluation folks and the non-lazy evaluation folks, and my question was never answered.

I don't know if any existing functional language would suit the situation, though.

But I expect designing a new language would actually be easier than writing the assembly-optimizer for the Von Neumann style languages. The available optimizer is hugely buggy and can take 380 megs of ram to figure out how to schedule a loop that takes 100 clock cycles to execute.

--jeff


[ Parent ]
My google train-of-thought (3.00 / 1) (#32)
by KWillets on Fri May 04, 2001 at 12:44:18 AM EST

Here's a search I did a few months ago for "VLIW Tree Language". MLTree looks like a good candidate, and I read through a lot of the IBM stuff.

I don't actually do much low-level stuff, so YMMV. (I'm interested in the tie-ins to other complex systems, like databases, which also do cache management, and commit/rollback.)

[ Parent ]

Wow! (3.00 / 2) (#39)
by statusbar on Fri May 04, 2001 at 02:02:46 AM EST

Cool! I like that very much! Thank you!

--jeff

[ Parent ]
efficiency (4.00 / 1) (#31)
by Puchitao on Fri May 04, 2001 at 12:12:46 AM EST

CPU efficiency really isn't as important as it used to be as a metric to evaluate programming languages. Unless you're primarily interested in game programming, there's usually not much need to drop into assembly. Assembly's (of course) the best for speed, but it's terribly inefficient in terms of manpower. (And, for a large project, it's quite difficult for a human programmer to do such tasks as register-coloring, liveness analysis, and all the other tricks that HLL compilers do mechanically.) Take some of the most popular languages today. VB, Java, Perl, Python... none of these have speed going for them. Why, then, are these popular? A couple reasons, among many:
  1. Higher programmer efficiency.
  2. Good and plentiful library support, both standard and third-party.
  3. Readable and maintainable code.
  4. Good compiler/interpreter support, preferrably on several platforms.
  5. Support for reliability and correctness verification
  6. Industry hype ;)
(The even numbered reasons are, btw, much bigger barriers to FPL-acceptance than execution speed, which is getting better and better as time goes by.) The languages that help teams develop large, maintainable, and reliable systems are what the industry's looking for these days, often regardless of whether maximum CPU efficiency is achieved. We're no longer living in the age of Mel, here.

Perhaps we can do *snappy fun* with you everytime! -- Orz
[ Parent ]
Maybe once (4.00 / 2) (#41)
by jynx on Fri May 04, 2001 at 04:50:25 AM EST

You want to know why we don't use functional (e.g. algebraic) [because we need] an abstraction layer between the programmer and the hardware, resulting in slower and less efficient code.

But this isn't really true anymore. Remember that we have years of experience of optimising C, but relatively little experience optimising functional languages. Over the last few years it has been found increasingly that functional programming languages, due to there lack of side effects can be optimised much more aggresively than procedural languages. The performance gap between the two is now relatively small.

I have seen studies in which programs written is Haskell have been shown to outperform the equivelent programs in C or FORTRAN.

The reason we don't use functional languages is because programmers don't like functional languages, because much of there procedural knowledge needs to be unlearnt, and their experience is of little value.

--

[ Parent ]

efficiency vs effectiveness (4.60 / 5) (#18)
by Speare on Thu May 03, 2001 at 06:50:23 PM EST

Someone below wrote this, and I am putting my meta-response back in the main thread:

    This [...] simply becomes an abstraction layer between the programmer and the hardware, resulting in slower and less efficient code.
There's a difference between efficiency and effectiveness. To illustrate the difference, think of a room full of desks. When all of the floorspace has been taken up by desks, the space is being used to maximum efficiency... but nobody can get to their desk to work. To be effective, you may have to back off a little on the efficiency.

The programming language world is no different: Perl ain't possibly as efficient as assembler, but it may be a more effective tool for certain problems.

LISP is fairly solid for knowledge representation, Prolog for knowledge interpretation, APL for matrix transformations, Perl for string transformations, C for driving system calls, and so on.

The problem is being effective in the problem space, not the efficiency in the machine. People are slow thinkers; allowing them to express their solutions quickly and easily makes them more effective. Optimizers can churn on the efficiency question once the problem and solution are well-known.

Automation just makes the remaining problems harder on average. Just remember that. Automate the easy stuff away and what's left? Effectiveness becomes key.



[ e d @ e x p l o r a t i . c o m ]
My thoughts... (4.00 / 3) (#25)
by BigNachos on Thu May 03, 2001 at 09:56:38 PM EST

I think the biggest problem with current popularprogramming languages is that they aren't designed around the way humans think-- they're designed around computer architecture. Languages have basically evolved from assembly to C to C++/Java, but have kept their low level machine roots.

If you remember back when you first started to learn how to program, it was awfully awkward and at times frustrating. At first, it's quite difficult to express what we want a program to do. Programming requires us to learn a new way of thinking.

Us seasoned programmers forget about this as we've grown accustomed to thinking like a computer when writing code. But, have you ever stopped to think about how easy a program would be to write if we didn't have to translate our thoughts into programming code? Think about the specs of a simple program, such as a text editor. You can probably describe such a program in a few sentences. How many lines of code would it take? Probably a lot more than a few. No wonder programmers always underestimate a project's time to completion.

I'd like to see a programming language built around the way *we think*, not the way computers work. Granted, object-oriented programming is a step in this direction, but it's an awfully small one.

I have no idea how to design such a language, and what it would look like. But, it's interesting stuff to throw around in your head.

I'm dying to learn some alternative languages like LISP, and see how they compare to the popular languages...

my thoughts (3.00 / 1) (#30)
by timmyd on Thu May 03, 2001 at 11:48:42 PM EST

I have no idea how to design such a language, and what it would look like. But, it's interesting stuff to throw around in your head.

well that doesn't help anyone. if you want to have a language that work how human think, why don't you try to figure out how humans think? i bet it is pretty complex. maybe that's why there aren't many chess computers that do something besides attacking a position with brute force.

i think imitating a human would probably be too complex and too hard to write a compiler for. the more you abstract a language the harder it is going to be to translate it back down to machine code.

[ Parent ]
Ok, let's get started (4.00 / 1) (#33)
by BigNachos on Fri May 04, 2001 at 12:55:11 AM EST

Say, for example, you wanted to write a function in a typical programming language that tested if a string was numeric, ie. was equivalent to a valid number.

This is an extremely simple concept to an educated human, right? In our minds, we can identify a number very quickly. How do we implement it in code?

Well, initially, we'd define a number as a bunch of digits such as 1734065832. So, we'd enumerate through each character in the string and see if it was in the set of characters 0-9. If every character was in the set, we'd have the function return true. That's pretty easy, right?

But, then we realize a number could be preceded by a + or -. So we add a line of code that reads the first char in the string to take into account the possibility of a + or - as well as 0-9.

Ok, that's fine. Then we realize a string could be numeric if it has a '.', but only one of them. So now we have to add a decimal counter that's initialized to 0. Then, when testing the chars in the string, if we find a decimal, check the counter. If it's 1, we return false. Otherwise, we add +1 to the counter.

Damn, thinking like a machine sucks. In our mind, the concept of "there can be only one decimal point" is incredibly simple and fundamental, but the programming code is somewhat more involved.

So how would a programming language that imitated human thought implement this scenario?

I would say the biggest different between machine code and human thought is in the way we handle concepts. A machine knows 0s and 1s, and that's it. We abstract these in modern programming languages to an extent, but fundamentally computer data is quite simple.

Humans, on the other hand, are great at abstract thought. In our mind, a number isn't a string of digits with a decimal point somewhere in the middle (which is how it would be treated in C). It's just a number. We learned numbers in much the same fashion as the way I implemented my numeric function. However, to the computer, it can't do anything more with the concept of number we just taught it. It can only test if the string is numeric and return true or false. But, humans can take the concept of a number and use it to add 2 numbers togethers, use them in calculus, etc.

So, a human-based programming language would be based on extensible concepts, rather than 0s and 1s, ints and strings, "objects"... (how's that for a vague beginning?)

At this stage, I wouldn't worry about the implementation of such a language on a computer. That would only bog you down. Instead, come up with a well-defined programming environment that does exactly what you want it to do. If it's defined precisely enough, it will be possible to implement on a computer. After all, computers are by definition absolutely precise, right?

[ Parent ]

I think I'm on to something... (4.00 / 1) (#37)
by BigNachos on Fri May 04, 2001 at 01:25:10 AM EST

The more I think about it, the more I like this idea of programmable "concepts".

For example, take the concept of a digit. A digit is a special subset of characters (another concept). A series of characters form the concept of a string, or word, or whatever. A string of digits gives us the concept of an integer.

Another concept would be the concept of "in", or containing at least one occurance of a concept. Then there's the concept of "there can be only one" (heh), obviously a subset of "count", which is in turn related to integers.

Then you can combine the concept of "there can be only one" with the character "." and "in" "integer", and you form the concept of a real number. Introduce the concept of addition, or combining the sum of 2 real numbers. With addition, you could define multiple additions, or the concept of multiplication... division... trig... calculus...

What a cool system. Just like human intelligence, it would just keep growing as more and more concepts were learned and combined to form new concepts.

Imagine the possibilities...

Now we need a mechanism that defines how to combine concepts and store them, and we're well on our way to a new programming language...

Did someone say this was too hard to do?

[ Parent ]

Math Proofs (3.00 / 1) (#38)
by statusbar on Fri May 04, 2001 at 01:40:17 AM EST

I like that.

Would the Metamath proof explorer be a good starting point along that vein?

http://metamath.planetmirror.com/mmexplorer/mmset.html

[ Parent ]
Hmmm (none / 0) (#78)
by BigNachos on Fri May 04, 2001 at 08:48:54 PM EST

That does look pretty interesting. I'm not sure if it's a good place to start, considering my original idea was to design a programming language that closely resembled the human thought process to facilitate easier programming.

Maybe some of the metamath ideas could be applied...

[ Parent ]

Component based OO (none / 0) (#59)
by bored on Fri May 04, 2001 at 05:31:52 PM EST

This is exactly OO programming. The problem is 90% of 'OO programmers' don't understand OO techniques they only understand syntax. The only difference between a good OO language and what you are describing is that the OO language is constrained in the syntax you can extend. How you extend it is up to the developer. The basis for 'Good OO' development is Black box inheritance not white box. The idea with black box inheritance is that each object has a self contained purpose. You combine these self contained things to form another self contained object that has new functionality. For instance you take a few button type objects, write some code to combine them with a number object and tie the whole thing up into a visual calculator object. Now every time your application needs to show the user a calculator you instantiate a calculator and when it returns you read the result from it. Of course this is an example and you probably wouldn't write your own calculator because there is a system wide calculator component.

[ Parent ]
I was wondering if someone was going to say that (none / 0) (#68)
by BigNachos on Fri May 04, 2001 at 07:31:03 PM EST

It's not exactly OOP. As I said in my original post, OOP is only a small step in this direction.

OOP can only be applied to my "conceptual programming" theory in its data model, and only to a limited extent. You can derive classes from other classes, creating special cases of the parent object. But, in OOP, the only concept is the object. You can't do something like combine the concept of red to the concept of a box to create a new concept of a red box.

You could create a class box that had a color property. But this requires extra work, and isn't very flexible. If you wanted to create a red ball, you'd have to re-implement the color property--you couldn't just apply the concept like humans readily do in our mind.

Furthermore, it's pretty cumbersome to code a flexible object-based system with classes that are useable for many different applications. You have to spend an awful lot of time in the design process. It's much more work than what's possible if we do it in our heads.

An object-based system would only be a subset of my concept system, and it would be much more flexible and easy to implement.

...in theory, anyway...

[ Parent ]

Bzzt. (none / 0) (#88)
by Jacques Chester on Sun May 06, 2001 at 10:28:48 PM EST

The depressing about being smart - like yourself and I - is that whenever we think of a Great New Idea, we tend to find that some other smart person has beaten us to it. You've just provided an example in your "conceptual programming" posts:
You can't do something like combine the concept of red to the concept of a box to create a new concept of a red box.
But alas, you can. I do so in Java every day. I am writing a little robot-fight-robot type game. In this game I have a hierarchy of physical objects, derived from RobotObject. Some of these can explode, some of these cannot explode. It would be tedious to copy-and-paste code into each exploding object, wouldn't it? It would defeat the purpose of OO programming to do so.

But I don't need "conceptual programming" here, because OO deals with this problem just fine. Instead I write an "interface class", called CanExplode. Thus my class header for a FuelTank reads:

class FuelTank extends RobotObject implements CanExplode

In your case, you want to combine "Boxes" and "Redness". Hence we create a hierarchy of classes under Box: We get entries like ToolBox, ClothesChest, DecorativeBox and so forth. Then we define an interface, IsRed. So when you want your toolboxes to be red:

class ToolBox extends Box implements IsRed

Although really you should relegate colour to a variable. Good planning beats New Programming Paradigm ninety nine times out of ninety eight, in my experience ... the other one time is right after you read the Latest SE Book - which you later realise is a rehash of what you already know.

And really, it's that simple. Read "Thinking in Java" to find out what else you've been beaten to.

--
Well now. We seem to be temporarily out of sigs here at the sig factory. We apologise for any inconvenience this may cause.
[ Parent ]

True, but... (none / 0) (#89)
by BigNachos on Sun May 06, 2001 at 11:32:45 PM EST

Object orientented programming still doesn't feel right to me. I've been using it for a few years now, and it can be really nice in theory, but in practice it's pretty clumsy.

It's really hard to design an elegant object-oriented program. It takes a lot of time, trial and error, and patience. A big reason it hasn't been well embraced by the hacker community is that it's much more satisfying to start hacking something immediately than to spend a few weeks constructing hierarchies and interfaces. It's not as easy to translate our thoughts and ideas into OO code. In the end, however, the structure of the code will probably be easier for us to understand.

Personally, I enjoy the challenge of building an OO program. But, I still find it to be quite inefficient. I'd rather remove the trade-offs-- I want to be able to hack away at something right away, and in the end have a nice, logically structured program. It should be as easy to program as it is to write prose. I want to be able to freely implement my ideas into my code, without building classes and worrying about interfaces or any other burdens. I don't want to have to think for the computer. I want the computer to think just like me.

While it's probably possible to implement all of the ideas I mentioned in OO code, it just isn't as easy or flexible as it should be.

It bothers me to think about all the extra time an effort that goes into writing a program, when I can describe the functionality of the program with minimal effort in my mind. There has to be an easier way to do this stuff...

[ Parent ]

hacking and OO (none / 0) (#90)
by bored on Mon May 07, 2001 at 01:03:54 PM EST

There isn't any reason you can't just slam together code using OO either. You just have to be willing to rewrite/massage massive parts of your code when you see an object beginning to form. A lot of my development work is like this, I start with an idea of what is required and start to code it. Then when I get a firmer understanding of the requirements I start to massage the existing code into cute little modules and classes. The end result usually is relatively easy to read.

With a little practice and a solid understand of 'proper' OO development I think that coding like this forces seat of the pants code to have clean interfaces. When all you do is write procedural code then there isn't any incentive to clean up the data structures and control the scope of existing code. The end result is crap loads of functions that intermix in non obvious ways. MFC and to a lesser extent Java both piss me off with their inheritance is the method for getting functionality model. Its just plain annoying, and screws up peoples perceptions of 'proper' OO development. Hence the move to change to verbiage so that you program in a 'component' model rather than an OO one.

When I'm seat of the pants programming I find that the only time I use white box inheritance is when I have an existing class that does something, say communicates with the serial port, and I want to plug in the ability for the rest of the program to communicate using TCP. In this case I create a new abstract base class for communication and inherit both the old serial classes and the new TCP class from it. Then I run a global search and replace to replace absolute references to the serial class with the communications class. The end result is a program that now can have new communications nodes plugged in. In this respect OO is a lot like my thought processes. I think It should be able to use TCP as the method for getting its data rather than the serial port and that is the way the resulting code reads.



[ Parent ]
libraries (none / 0) (#67)
by timmyd on Fri May 04, 2001 at 07:15:10 PM EST

most high level languages now-a-days have functions where you read from something and it help you determine whether it is a string or number. take scheme for instance:

guile> (define determine
(lambda ()
(let ((var (read)))
(if (or (string? var) (symbol? var))
(display "it is a string."))
(if (number? var)
(display "it is a number."))
(newline))))

guile> (determine)
3
it is a number.
guile> (determine)
hi
it is a string.
guile> (determine)
2+4.23i
it is a number.
guile> (determine)
3e7
it is a number.


[ Parent ]
So? (none / 0) (#69)
by BigNachos on Fri May 04, 2001 at 07:34:18 PM EST

Of course they do. I only used that as an example because it was easy to explain.

[ Parent ]
then? (none / 0) (#73)
by timmyd on Fri May 04, 2001 at 07:55:24 PM EST

what is your point? you can add and redefine functions as you go along... so what are you trying to do?

[ Parent ]
I'm trying to... (1.00 / 2) (#75)
by BigNachos on Fri May 04, 2001 at 08:07:28 PM EST

Approach programming from a completely different perspective, which you seem incapable of.

[ Parent ]
well then (none / 0) (#76)
by timmyd on Fri May 04, 2001 at 08:14:41 PM EST

just like the world didn't start out with humans, programming didn't start out with reading the programmers mind. look like your going to have to build something massive with very simple blocks for now.

[ Parent ]
Yup (none / 0) (#79)
by BigNachos on Fri May 04, 2001 at 08:59:59 PM EST

That's what I've been trying to do. Instead of building up from bits to assembly to structured programming languages, I'm started from the other end: Humant thought patterns eventually cumulating into machine-readable code.

Feel free to contribute. :)

[ Parent ]

We *don't* know how humans think (none / 0) (#82)
by exa on Sat May 05, 2001 at 09:02:50 PM EST

if we did then we'd have solved AI long ago...
__
exa a.k.a Eray Ozkural
There is no perfect circle.

[ Parent ]
Not true (none / 0) (#83)
by BigNachos on Sun May 06, 2001 at 12:51:05 AM EST

We don't know how to explicitly define how humans think. We don't know a mathematical formula which expresses our thought process.

However, that doesn't mean we can't express how we think. There are professions that do just that--psychologists, psychiatrists, philosophers...

There is no reason we can't try to mimic the human thought process empirically.

Did Einstein say, we don't know how anything about special relativity because we, as humans, haven't traveled at near light speed, and therefore it's not worthwhile to try to express empirically? Or, did he ignore what seemed to be impossible until it finally was possible?

Maybe it would be worthwhile for you to try to figure out how to do what we haven't already done instead of merely pointing out we haven't done it yet.

[ Parent ]

cog. sci. is not that developed (none / 0) (#85)
by exa on Sun May 06, 2001 at 02:59:24 PM EST

As a person who has studied AI, linguistics and philosophy of mind for quite some time, I can't be that optimistic about the state of the art.

Functional and logic PLs which are widely used in AI research are the best examples of what has really been applied. AI people thought of that long before you did.

There is a long way to go in AI research before we can have something that can replace class based languages.

Currently, our best bet is to develop better KR and planning languages. Which sounds like more logic programming to me. And, I don't you think there will be much benefit from neural networks and genetic programming fluff if that's what's on your mind.

__
exa a.k.a Eray Ozkural
There is no perfect circle.

[ Parent ]
Stuck in a Rut (4.00 / 5) (#40)
by jynx on Fri May 04, 2001 at 04:35:50 AM EST

I think that programming language change is going to be very hard. Programmers seem very resistant to significant change with regard to languages. Lots of programmers learn programming during there teens. They find a style they are comfortable with and stick to it.

Ever tried to convince a hardcore C programmer the advantages of OO? Ever tried to convince a Java programmer the advantages of functional programming? It's not easy.

I can see why. Learning a programming language is easy. If you know C, you can probably learn Pascal in a week. If you know C++, it probably won't take you long to learn Java.

But as soon as you start crossing paradigms it becomes much harder. The best evidence I have for this is from my own degree course.

There are quite a few people who start the course with little or no programming experience. There are others who have done programming before. Those of have coding experience have usually know a procedural or object oriented language (C, C++, Java).

In the first year of the course, students are taught procedural (C) and functional programming (Haskell) side by side. Strangely, the people who have previous procedural programming experience find it much harder to learn functional programming than those with no programming experience.

Why? Programming is not just about knowing a language. It's about being able to decompose a problem into something programmable. Procedural programmers decompose programs procedurally. When they have to program functionally, they may know the syntax of the language, but they still think procedurally, and find themselves trying to shoehorn procedural ideas into functional syntax.

This is so frustrating it almost hurts. (I know, because I've done it.) It takes a lot of unlearning to go from procedural to functional programming. So much so that most people don't bother. By the end of the 1st year, most students on my course who had procedural experience have decided that they hate functional programming and vow never to touch it again. (I happen to like FP, but I seem to be quite unusual.)

Bear in mind that the vast majority of these people start the course aged 18-25, and therefore probably have at most 5 years of programming experience. Now, imagine how much worse this will be with someone whose been programming for 10 or 20 years. Is it any wonder it's taken OOP so long to catch on? And OOP is relatively small paradigm shift.

In conclusion, any major change in the way people program is going to be very hard. The longer we stick with current methods the harder this change is going to be. And if the benefits of the change aren't immediately obvious, it could be impossible.

--

Are functional languages a paradigm shift? (3.00 / 2) (#43)
by Mental Blank on Fri May 04, 2001 at 05:38:52 AM EST

Firstly, I must admit that I'm no expert with functional programming languages (though I have played with SML and Lisp). But nothing I've learned about them has convinced me that they're a fundamentally different "rethink" of programming. Essentially, I don't see the difference between writing

(func1 (func2 (func3 some_data)))

in a functional language, and writing

result = func3(some_data);
result = func2(result);
result = func1(result);

in an imperative language (ignoring type conversion issues, etc...). It seems to me that functional programming is just a way of converting a standard imperative language into something that's mathematically tractable - the end result is still that operations get performed sequentially in a certain order.

Of course, this results in having to put yourself in a bit of a straitjacket, at least with pure functional languages - I'm amazed at the hoops I've seen people jump through to express things recursively and without side-effects.

Declarative languages and those with built-in parallelism, on the other hand, I would say are a completely different way of thinking about programming, and it should be interesting to see what happens in those areas in the future. Something else which would be great would be a popular language with superior support for message-passing and callbacks ("Smalltalk", I hear you shout...).

Bad example (4.00 / 1) (#44)
by jynx on Fri May 04, 2001 at 07:49:57 AM EST

the end result is still that operations get performed sequentially in a certain order.

Mmm, yes this is true. But the compiler is free to choose whatever order suits it best.

In the example you gave there was only one possible ordering, so it was a pretty bad example.

Besides which, this is only one small aspect of FP. There are many other advantages.

I don't know SML, but LISP is not a good example of FP. I program Haskell which is a very neat, modern FP langauage.

I'm amazed at the hoops I've seen people jump through to express things recursively and without side-effects.

I'm not sure what you mean with regard to recusion. I/O is hard to express without side-effects, but that's because I/O, by definition, has side effects.

The problems have been mostly solved with monadic I/O. I/O is still not as easy as procedural languages (it never will be), but it's really not that bad once you get your head around how and why FP does it the way it does. And it's more than made up for by other features of FP.

Advantages of FP:

  • Generally neater code. Code density much higher. (More functionality per line of code.)
  • Closer correspondance between elegant code and efficient code. (In procedural languages, the fastest solutions are often not the most readable, and vice versa)
  • Lazy evaluation.
  • Easier to build advanced type systems, e.g. parametrised types, multiple inheritance etc.
  • Higher order functions make it very easy to build reusable algorithms. (Better than the reusable data structures in OOP.)
  • Far easier to prove correctness. (Doesn't apply to many of us, but still...)
  • Build efficient specialised code from general code.

Declarative languages and those with built-in parallelism, on the other hand, I would say are a completely different way of thinking about programming,

Functional languages are declarative. (Although not all declarative languages are functional.) In built parallelism is pretty easy in functional languages.

If I had looked at FP independantly, I would have discarded it after a couple of weeks. But it was forced upon me for a whole year. (I think it took me about 9months before I admitted it could be usefull.)

FP is subtle, and hard to learn. But once you get good at it, you can code a lot of things more neatly and more quickly.

But at the end of the day "the right tools for the right job". With the current state of FP, if you are coding heavily I/O driven programs, FP is probably not the way. But if your job involved prototyping algorithms, FP will probably get the job done much quicker. I guess this is why FP is more popular in academia - our programs don't need to look nice or interact with the user, they just need to work, and explain themselves easily.

--

[ Parent ]

Err.... occam? :) (3.00 / 3) (#47)
by leibnitz27 on Fri May 04, 2001 at 12:21:18 PM EST

  • The flow of data would be explicit and structured.
    Occam
  • The program can easily handle multiple inputs and outputs.
    Occam
  • The program can handle input and output asynchronously.
    Occam
  • Input and output can be pipelined at all stages to deal with latencies.
    Occam
  • Programs should be easily scalable across many CPUs and across networks.
    Occam

That's not to say I'd suggest you use it.... but that's what it's there for. See Charles Hoare's book Communicating Sequential Processes



Time complexicty and functional programming (4.00 / 4) (#51)
by keyeto on Fri May 04, 2001 at 01:00:03 PM EST

I was once an advocate of functional programming, for many of the reasons already cited in this discussion. But one day I was exposed to a programming problem, with real practical applications, that showed up a very serious weaknesses in functional programming.

The problem is inverting a permutation. Consider, for example, the permutation ( 4, 2, 0, 1, 3 ). Using zero based indices, this can be interpreted as a the following mapping:

  • 0 to 4
  • 1 to 2
  • 2 to 0
  • 3 to 1
  • 4 to 3
Now invert that to get a similar structure that performs the following inverse mapping:
  • 4 to 0
  • 2 to 1
  • 0 to 2
  • 1 to 3
  • 3 to 4
The result, then, is ( 2, 3, 1, 4, 0 ).

To get to the point, this can be written trivially in an imperative language to a time complexity of O(n). The vast majority of implementations in pure functional programming have the time complexity O(n2). Even worse, it is impossible to get better than O(n log n) in a pure functional language, and that takes such a mindbendingly complex implementation, it's simply unrealistic to expect it to come from anywhere but the high end of academia.

So, while there are quite a few benefits to the functional approach, you've got to realise that good results are more readily available from programmers of imperative languages.


--
"This is the Space Age, and we are Here To Go"
William S. Burroughs
Quicksort in LISP: linked lists suck!! (4.00 / 1) (#81)
by exa on Sat May 05, 2001 at 09:02:30 PM EST

One day we were asked to write quicksort in lisp, and i wrote one that had O(nlogn) (avg.) time complexity. But I'd had to spend a lot of effort to get it right. I went to the assistant and told him "Well, most people wrote it this way, right?" and scratched something to him, and then I told him "You see this takes at least O(n^2) time because.." I guess you know why, anyway I couldn't quite convince him to give me a bonus, but hey world isn't perfect. :)

Most symbolic languages do very wrongly by using stupid linked list structures generously. You can implement efficient data structures with funtional languages, too. Ah, yes, i know linked list also qualifies as the *only* data structure 90% of all programmers know :/



__
exa a.k.a Eray Ozkural
There is no perfect circle.

[ Parent ]
data structures in FP (none / 0) (#84)
by hading on Sun May 06, 2001 at 11:26:36 AM EST

You probably know this, but for anyone else who is interested, Purely Functional Data Structures by Chris Okasaki is a nice book for data structures in a purely functional style.



[ Parent ]
agreed completely (none / 0) (#87)
by Puchitao on Sun May 06, 2001 at 04:06:04 PM EST

Even if you're not interested in FP, Okasaki's book is a good reference. I've found some of his insights useful even while working on imperative/OO programs.

On a side note, I believe you can do that permutation thing in O(n) time in Clean; simply use a unique unboxed array -- the kind that looks something like {#} -- and tail recurse over it. (The unboxed array type is pretty commonly used in Clean, afaict; it's even the way they represent strings.) You can even use destructive updating without jumping through monadic hoops, because of the uniqueness typing. (IIRC, unboxed arrays are always unique, but even if they aren't you can make them that way.) Unfortunately, I don't really know Clean well enough to show it; it's syntax is just different enough from Haskell's that I become disoriented. ;) So don't take my word for it.

Perhaps we can do *snappy fun* with you everytime! -- Orz
[ Parent ]
Not quite so "pure" though (none / 0) (#93)
by keyeto on Tue May 08, 2001 at 05:07:16 AM EST

Yes, the trick to getting it in O(n) time is being able to index into the input list in constant time. You can still construct the output list using the ordinary cons operator, by tail recursing down the input list in the manner you suggest. With tail call elimination it becomes just as space efficient as the imperative implementation too.

I was being specific about pure functional languages, and there's something about lists being implemented internally using arrays that doesn't seem quite "pure" enough to me. Trivial nitpick. Your point stands.


--
"This is the Space Age, and we are Here To Go"
William S. Burroughs
[ Parent ]
arrays are pretty pure (none / 0) (#94)
by exa on Sat May 12, 2001 at 07:06:34 PM EST

as pure as it can get.

after all an array is only a function from an index space (or range) set to another set.

I usually think like:
A: R -> C

where A is array, R is the range set, and C is a component type.

So, there you go :) The real trick is having this neatly in a functional pl and making it as fast as FORTRAN.

__
exa a.k.a Eray Ozkural
There is no perfect circle.

[ Parent ]
It's Time to Rethink Programming Languages from the Ground Up | 94 comments (90 topical, 4 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!