|
Post by tkorrovi on Oct 29, 2006 16:21:16 GMT -5
You are now registered as the ADS-AC project developer, with all permissions, and project's wiki user. Your wiki username is abramdemski, and password is abramdemski -- *please log in immediately and change your password*.
WOW!!! Now we don't talk about all the theories, because now we celebrate, you becoming a developer of the ADS-AC project!!!
|
|
|
Post by tkorrovi on Oct 31, 2006 22:26:36 GMT -5
Your code reflects correctly the main principles of how to create and delete nodes, but it's still not the ADS mechanism, that's a bit more subtle. First, creating new nodes with set-difference, doesn't add the back links to new nodes to the old nodes, when new nodes point to them -- the links in ADS are bidirectional. Second, going through the old nodes that way each time, will create new nodes twice for every pass, and will create the same new nodes every next pass. Because of that consideration, in ADS-AC the new nodes would be created as a new generation, and then the nodes would be created only between these new nodes and old nodes. Also there of course are many special situations, like node will be deleted when the last link of it would be deleted, what happens if an i/o node would be deleted etc etc. So look at the ADS-AC code, how the things are done there, it just doesn't make sense to reinvent it all, even learning a bit C is easier than that. Also, Lisp uses singly linked list, but ADS uses doubly linked lists. Therefore I think that implementing ADS with Lisp lists would be terribly slow, as in singly linked list for finding the previous, the only way is to go through the list from the beginning. ADS uses arrays, but there is in general no difference between arrays and pointers in C, and therefore the array size can be changed by freeing and reallocating it (there is a special and fast garbage collection implemented in ADS-AC). Of course, arrays can be used in Lisp as well, though I don't know it so well to say whether it is possible to free arrays in Lisp. But then all the effectiveness of the Lisp lists would be lost at least.
Well, I looked at Lisp, I agree it's a good language, as it has a very clear syntax, with much less rules than in C. And kind of clever thing as well, when it can compile from just an interpreter language, without any variable declarations, this also makes programs shorter. Otherwise it's equal to C. I have really nothing against, if you want to write the code in Lisp, would not be worse than in C, though I think much more work for writing an equivalent code instead of using the existing C code. I think you also have some Linux installed, so you can debug things in Linux as well (I also have Debian Etch in parallel with Windows).
One more thing -- this thread is now the longest in this forum :-)
|
|
|
Post by tkorrovi on Oct 31, 2006 22:47:25 GMT -5
Also, I don't know whether the arrays in Lisp are really random-access arrays, or implemented by linked lists, like in Java, where it may seem like some arrays are the same as in C, but really it goes through the whole array from the beginning every time, to find a single element of it. If it is so, then it is horribly slow. But of course I don't know Lisp to say so well what other possibilities there may be, but whatever there is, it must be very fast.
|
|
|
Post by tkorrovi on Nov 1, 2006 16:53:03 GMT -5
I benchmarked Lisp for arrays, which are common in ADS-AC. I did it in my Debian Etch linux. First this tcc script: #!/usr/bin/tcc -run #include <stdio.h> #include <time.h> #define SIZE 10000
int main () { unsigned long array , t = clock (), p = 10000, i, j;
for (i = 0; i < p; i++) for (j = 0; j < SIZE; j++) array [j] = p; printf ("\nExecution time %.0f ms\n\n", ((double) clock () - t) / CLOCKS_PER_SEC * 1000); return 0; }
The result was 660 ms. Then the equivalent code in CLISP, the only stand-alone lisp there is in Debian distribution. (defun arraybench () (setq size 10000) (setq p 10000) (setq etime (get-internal-run-time)) (setq array (make-array size)) (setq i 0) (loop (setq j 0) (loop (setf (aref array j) p) (setq j (+ j 1)) (when (= j size) (return nil)) ) (setq i (+ i 1)) (when (= i p) (return nil))
) (format t "~%Execution time ~,0F ms~%~%" (* (/ (- (get-internal-run-time) etime) INTERNAL-TIME-UNITS-PER-SECOND) 1000) ) )
This was compiled into bytecode, and then executed with CLISP. The result was 27094 ms, slow like hell, 41 times slower than C code. CLISP compiles only to bytecode, which is really not fast at all. If you have some Lisp compile which compiles to machine code, then you may test it with that. It is also not completely without a reason, that C needs variable declarations, these enable a faster code, without any type checks within code, and second they enable to define different data types, which are absolutely necessary for things for which C is often used, like reading from memory, or from different interfaces, I see no way how this can be done with Lisp, with its arbitrary variables.
|
|
|
Post by tkorrovi on Nov 2, 2006 12:42:29 GMT -5
For c, there are some functions for working with linked lists in glib, I never tried them though, and there was no glib when I started to write ADS-AC. Glib is something which comes with gtk, at least when you install it in windows. Also there are regular expressions for c, I even made a shorter version of the public domain ones, recursion is also possible, but not the best programming method. Nothing is really missing in c, just that these are not a part of the syntax, and therefore a bit more difficult to use. But that c is the fastest programming language, is no advocacy, it really is so. And at that, c also has the fastest compilers, like tcc, it compiles so that you don't even notice, and then runs the code in machine code, you just write a text file, and then run that text file, so the same as script, but runs in machine code. This is better for some scripts, than any interpretator language, like perl or php, as it compiles only once, and then a long time runs the machine code, so that the interpreter doesn't have to work all the time, and will not take the processor time, as it is the case in most of the web servers, where the php interprets the same script again and again, whenever you look at another web page. No but I still don't think that you have to write in c, I just say what is good in c, which you perhaps don't know, sorry if I said something which you already know though. If you'll find it necessary to write in lisp, it's ok that you write in lisp, just anything is ok which really helps to move the ac research further. And I'm thankful for the code in lisp you wrote, in spite that it's not yet the full ads mechanism, it may help (others) to understand some general principles how such things work. But just, when you write something necessary, put them somewhere in the project's wiki, so that everyone can see who looks at the project. And something bigger, like substantial change or something enough for, say, a linux package, you can write in cvs, and make a file release, you can do all that as developer of the project. Yes and, also some minor thing, if you'll want to write some code in this forum, put it between [ pre ] and [ / pre ], not [ code ], this is the eigth button from left when you write a message, this will insert the indentation correctly, but watch the smileys, something like a comma immediately after semicolon, it woult replace such with smiley, it's better to simply write a space between in such places, if the code allows that. There is also something like verbatim, but they don't want to allow it, as this disables all replacements, and therefore also enables to write all kind of unwanted code, which they usually delete by replacements.
|
|
|
Post by tkorrovi on Nov 2, 2006 16:47:23 GMT -5
About project development there is this guide autotoolset.sourceforge.net/tutorial.html from the GNU autotoolset project. Everything is right, except that emacs is not so widely used, mostly they use vim as a text editor and ide, and I use vim, both in Windows and Linux. You see there that the autoconf and automake are really simple for programs with only one source file, only copy and paste from there. The most recommended programming language is C, but the recommended interpretator language is Guile, not CLISP. Guile implements Scheme, a version of Lisp. And Guile can use GTK for GUI, the same as C, it can use the whole posix, and all other C libraries directly, as you see, CLISP has its own functions instead of posix ones. So Guile indeed seems better than CLISP, as it can better interact with C, and use more standard libraries.
|
|
|
Post by tkorrovi on Nov 2, 2006 22:14:55 GMT -5
Now I found something in debian, which can compile common lisp, it's called gcl, and it seems to be better than clisp. I compiled the benchmark code with gcl into an object file, loaded that object file, and run the function. I got
6680 ms
This is the fastest which lisp can run, because this is a machine code. And this is ten times slower than the equivalent c code. (Profiling information was not included in the object file, which could make the code slower.)
|
|
|
Post by tkorrovi on Nov 7, 2006 0:12:07 GMT -5
I'm sorry but I see Lisp as a scripting language. The scripting languages are enticing, because they enable to do so many things with quite little knowledge. It is so only because these languages were never intended to be full programming languages. But I of course don't deny the beauty, and the value in teaching programming. I read the scheme tutorial, I didn't exactly need to read it, as I knew most of the things, but it was so nice to read, when someone so carefully wants to explain you the things. Unfortunately no one can write so shortly everything one needs to know about C, I tried, but the terms form more like a system, so there is no way to start from somewhere, and explain the rest through that. And we never achieve such beauty, as it is explaining a scripting language, In fact, if one wants to explain, say, scheme in every detail, it would not be so beautiful either, though it has quite short standard, some 50 pages, much shorter than that of Lisp. Just that, for a universal programming language, all these details would be necessary to know, but for scripting language, one can do without knowing them. And they are the main thing to know, for C, and also for Lisp all these beautiful things are only a small part in any complete description. Yes I mostly used to know C, but then also I like simplicity, C programmers mostly don't like C++, though they mostly can code in C++. Just C is the simplest really universal programming language, which is still possible to completely learn by a human, which cannot be said about things like C++. This is just to say here what I think, I think it's important to say that sometimes. But then, if you would like, say, do something completely in Lisp, and you know exactly how to do that, and that it would really be some way useful, and should not be rewritten in C very soon, then go ahead, I like also the beauty, and I like the simplicity. Just I myself kind of used to satisfy with everything C, as for writing many different things, there is no escape from that anyway. But then, how nice it would be if one only had to know Lisp, and can work only with that all life, unfortunately probably only the university lecturers can afford that. And then, I'm also likely a bit more like a philosopher, I can say a lot about how the things should be, but then I always used to do a bit less than necessary. Sure you can be the same if you like.
|
|
|
Post by Abram on Nov 11, 2006 13:46:21 GMT -5
Hey, sorry I haven't been on in a while. I'm now working on coding a logic engine based on networks instead of logical statements. Except for the fact that it's in Lisp and programmed by me (I don't know much about writing fast code), it should be a good deal faster than the current standard in logic engines. The reason is that normal logic engines, even if they claim to be based on the n=idea of networks (and some do), still store their data as a big bin of seperate logical statements. I'm actually interconnecting it, so that when the engine reasons about one particular set of interconnected things it can retrieve each datum directly instead of going and getting it from the big bin. This datastructure should be perfectly compatible with Rete, but it probably won't need Rete to be fast (based on the fact that LEAPS is fast without Rete for the same reasons).
Anyway, I do need to learn to write fast code-- I can't very well demonstrate that my method is fast if my code isn't. I'm planning on comparing it's speed to other logic engines written in Lisp, though-- that will make it a bit more "fair".
I didn't know that about Java arrays... that's horrible!
Java is the language that my university is using now, so it's what I'll be getting an education in. It's a wierd compromize between Lisp and C, I guess.
Paul Graham says that Lisp code can be about as fast as C, if you know how. Mainly he seems to say "use structures and compiled code".
|
|
|
Post by Abram on Nov 11, 2006 14:50:44 GMT -5
It's possible that I actually get funding from the university for my fast logic project. (I need to think of a good name for it... logic-net, logic-graph, concept-net, and concept-graph are all already taken by the people who are using network-type ideas without a real network datastructure...) But I don't think I'll be trying to make my ADS in Lisp fully functional for a while, because I want to do this logic engine. Plus, like you said, there's no huge reason to put ADS in Lisp. But I'm sure I'll mess with it again eventually.
|
|
|
Post by tkorrovi on Nov 11, 2006 17:24:25 GMT -5
Yes there are infinite number of ways to write benchmarks, and it's certainly possible to find code which is only two times slower in Lisp, than in C. I though know no benchmarks where C isn't faster than Lisp. I don't know what structures Graham exactly meant, I may confuse terms in Lisp and C, in C structure is a sequentially allocated set of members, something which can be declared with defstruct in Lisp, and there can be arrays of structures in C, well, writing a few very simple functions, we can create linked lists of structures as well. Nothing really which can be done in Lisp, and cannot be done in C, except perhaps generating new code, but this is not a very good method at all, and also compiled Lisp cannot do that either. But the benchmark which I wrote was about a simple going through the array, because it's necessary quite often. But looking at different benchmark, it seems to me like Lisp compiler somehow first translates loop to tail recursion, and then to C code (then to machine code, this C code though is not very simple, more something like interpretator and code put together). And it seems that the most time consuming for Lisp are the function calls, which is logical when it always has to do different stack-cleaning and such operations, to enable frequent recursions and such. So likely the Lisp code would become faster, when there is more to do in the loop.
Well, I don't say that there's no reason to put ADS in Lisp, just that it would be too much effort only in order to use Lisp. It can be much more easily and much more smoothly changed to anything whatsoever, as everything can be done in C. As a C programmer, Lisp seems to me very similar to C, only written with a syntax which looks like somewhat different, though does the same things, I don't see a big difference. But then, if there is no other easy way to create it, and it can really do something at the speed it would have, then there certainly is a reason to put ADS in Lisp. And then, things like Java and such, are created only in order to offer another method which arguably helps to solve the biggest problem, the time it takes to write programs, and make them reliable, for people who mostly didn't write programs themselves. But all these methods are essentially based only on one thing, to force programmers to write programs certain way. Good programmers mostly write programs the right way also without these methods, and as fast as using these methods, the biggest problem is likely that there are not so many of these. And a cost of such methods is always either making the language unnecessarily complicated, like C++, or then too restricted, like Java. C, and also Lisp, are languages which give programmer a freedom, enable everything, are as simple as possible, and it depends on programmer how well they can write a program. I think good programming language must be like that.
Do you have any Linux installed?
|
|
|
Post by tkorrovi on Nov 12, 2006 12:57:40 GMT -5
I wrote my first program when I was in high school, on PDP 11 in Fortran 77, it was about finding symmetric and redundant variables in system complexity analysis, and it worked faster than a program doing the same on Cray 1, I got paid for that too. The first programming language which I learned was Fortran, and I didn't like it, as it is too restricted, it had no possibility to allocate data, and no way to change the size of the arrays. But for some tasks Fortran is extremely fast, faster than C, so that in science it sometimes makes sense. Think you did read that which I recently wrote here under software, about programming tools, I think that we should talk about general things in programming in that board, otherwise just when we talk in a single thread about everything, it may be for others somewhat hard to follow.
|
|
|
Post by Abram on Nov 16, 2006 10:09:31 GMT -5
No, I don't have Linux installed. I'm on a Mac (which means that I can't download your program for Windows).
|
|
|
Post by tkorrovi on Nov 16, 2006 12:10:14 GMT -5
Yeah that's bad really. Os x incorporates bsd unix, but this doesn't mean so much, as linux is not exactly bsd, and all programs don't compile anyway. Also, everything I said about free software etc, was about windows, as a lot is ported there, but many quite difficult to install or don't install correctly. Don't know about mac, as I have never seen it. Yes and of course that it is in windows api, if it was, say, tcl/tk bindings, then maybe it did compile even on mac (hope there is gcc on mac), but then there are still some minor differences even between windows and linux. Don't know, linux is a kind of "standard" os, which works on every processor, and in science they mostly use linux. Thought that maybe port the program only to linux, as everyone who has a deal with programming usually has linux, or is it so? If you think this makes sense, it would be much easier to maintain it on only one platform... Yes there is debian for powerpc, but if you had only linux there, then not sure whether all these games would work. Then it is of course possible to install linux in parallel with os x, with double boot, but as I said, you most likely have to buy a second hard disk for that...Yes and if you even need linux, though I think it's good even for programming in general, linux is some kind of classics, some kind of standard, the programs there are kind of right ones, at least considered so by better programmers and scientists... And well, not so big problem to port it to, say, tcl/tk, yet I have not seen a reason to do that, as I don't know whether it's even necessary, as I don't know whether anyone would even run it...
|
|
|
Post by tkorrovi on Nov 17, 2006 5:27:59 GMT -5
But windows api is, btw, a very good thing, very fast and high quality, includes everything from the most low level to every kind of widgets, which are also all overlapping, which they are not in gtk. Gtk also includes gdk, which is some equivalent of xlib, but this doesn't work well separately, like refreshing when moving windows. Tk is much lower quality than gtk, though of course for these programs for research purposes, there is not necessary a very high quality gui. Only in linux, it's also possible to write everything only in xlib, this is simple but of course low quality, without any antialiased fonts. This would be the most natural, without any additional libraries, only X, though kind of primitive. It's strange that tcl/tk is still often the best alternative, there is still no similar separate gui library as easy to use and with a good enough quality. And this is why they made lisp gui "ltk" also with tcl/tk, though to think how strange it is, to run all the time the interpreter of another language, tcl, which they depreciated in favor of the lisp dialects, and to use bindings of that interpreter language for the lisp gui, but this is exactly how it is still implemented.
|
|