ordered associative arrays
Hugh Aguilar
Lisp"). Can anybody tell me if CL (or PLT Scheme) has an associative
arrays implementation? I want an implementation that supports doing an
ordered traversal, and which also supports filtering of regions. I
want to be able to copy everything within a region into another
association, or everything outside of a region into another
association, and also be able to merge two associations together.
The reason why I ask, is that I wrote such an associative arrays
implementation (using LLRB trees) in ANS-Forth. I want to have the
same capability in Lisp that I have in Forth. I can port my code from
Forth to Lisp (after I get better at Lisp), but I would be interested
in knowing if somebody else has already done something similar.
This is my Forth code:
http://www.forth.org/novice.html
Regards --- Hugh
RG
<dcf45d56-c3cc-4930...@j2g2000yqf.googlegroups.com>,
Hugh Aguilar <hughag...@yahoo.com> wrote:
Hugh Aguilar
Let me further clarify. The associative arrays should be able to work
with *any* data-type in the key, including objects of the programmer's
own design. The programmer would have to write a function to compare
the keys for his specific data-type, and provide a vector to this
function at the time that he defines his associative array.
The region-filtering feature is primarily useful for situations in
which the key is a floating point number. The application I have in
mind is numerical.
Note that using a hash-table with an integer key, and then sorting by
another field (such as a float or whatever) isn't going to work. The
reason is that the boundaries of the region may not have
representative nodes in the associative array. For example, in my
Forth code, I may specify a region bounded by 1.0 and 2.0 --- and what
I actually get includes nodes from 1.1 to 1.9. A hash-table won't work
because searching for a 1.0 or 2.0 node will come up NIL, because
there is no such node. With hash-tables or arrays, a complete
traversal of the entire associative array would be necessary, which is
inefficient. With my Forth code, I can find the *nearest* node with a
simple search, with the same efficiency as finding an exact match for
a node. For example, I search for 1.0 and find 1.1, which is the
closest node that is >= to what I searched for. Or I search for 2.0
and find 1.9, which is the closest node that is <= to what I searched
for.
P.S. This question isn't Lisp related, but have any of you guys worked
with Lua at all? Any opinion?
Thanks for your assistance --- Hugh
Pascal J. Bourguignon
And also:
http://www.informatimago.com/develop/lisp/com/informatimago/common-lisp/llrbtree.lisp
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
w_a_x_man
MatzLisp (Ruby):
aa = {:a,22, :b,9, :c,33, :d,8, :e,7}
==>{:d=>8, :b=>9, :e=>7, :c=>33, :a=>22}
# traversal
aa.each{|x| puts x.join " "}
d 8
b 9
e 7
c 33
a 22
# filtering
aa.reject{|key,val| val < 9}
==>{:b=>9, :c=>33, :a=>22}
aa.reject{|key,val| val > 9}
==>{:d=>8, :b=>9, :e=>7}
# merging
aa.merge( {:f,0, :g,99} )
==>{:d=>8, :b=>9, :f=>0, :c=>33, :e=>7, :g=>99, :a=>22}
w_a_x_man
> Let me further clarify. The associative arrays should be able to work
> with *any* data-type in the key, including objects of the programmer's
> own design. The programmer would have to write a function to compare
> the keys for his specific data-type, and provide a vector to this
> function at the time that he defines his associative array.
MatzLisp (Ruby):
dot_type = Struct.new( :x, :y, :color )
==>#<Class:0x28ff7a8>
dot = dot_type.new( 0.78, 3.33, "red" )
==>#<struct #<Class:0x28ff7a8> x=0.78, y=3.33, color="red">
hash = {dot,"hello", (2..9),"world", [2,3,5,8],"bye"}
==>{#<struct #<Class:0x28ff7a8> x=0.78, y=3.33, color="red"> =>
"hello",
2..9=>"world", [2, 3, 5, 8]=>"bye"}
hash.keys
==>[#<struct #<Class:0x28ff7a8> x=0.78, y=3.33, color="red">,
2..9, [2, 3, 5, 8]]
Frank Buss
> P.S. This question isn't Lisp related, but have any of you guys worked
> with Lua at all? Any opinion?
Yes, I'm the main author of Lua Player:
http://www.frank-buss.de/luaplayer/
It is a nice small scripting-like language. In combination with easy to
write C extensions, it is very good for fast prototyping, even for
applications which requires high performance, because the parts which needs
to be fast are implemented in C and the logic, memory handling etc. is
implemented in Lua and by the Lua runtime system and GC.
Of course, Lisp doesn't need this split between two languages, it can be
fast all the time, but I think it is not as easy as Lua for beginners.
--
Frank Buss, http://www.frank-buss.de
piano and more: http://www.youtube.com/user/frankbuss
Hugh Aguilar
> Hugh Aguilar wrote:
> > P.S. This question isn't Lisp related, but have any of you guys worked
> > with Lua at all? Any opinion?
>
> Yes, I'm the main author of Lua Player:
>
> http://www.frank-buss.de/luaplayer/
>
> It is a nice small scripting-like language. In combination with easy to
> write C extensions, it is very good for fast prototyping, even for
> applications which requires high performance, because the parts which needs
> to be fast are implemented in C and the logic, memory handling etc. is
> implemented in Lua and by the Lua runtime system and GC.
>
> Of course, Lisp doesn't need this split between two languages, it can be
> fast all the time, but I think it is not as easy as Lua for beginners.
The application I have in mind will need to provide the user with a
domain-specific embedded-scripting language (DSL). If I write the
application in Lisp, the DSL will presumably be a subset of Lisp
(although I could possibly make it Forth). Another possibility would
be to write the application in C, and use Lua as the DSL. Yet another
possibility would be to write in C, and use FICL as the DSL. Some of
the code might require some speed, but I have heard that CL is as fast
as C these days (true?), so either should be fine.
The user will likely be somebody with minimal programming experience,
so I want a pretty simple DSL. Lua has been used in World-of-Warcraft,
and those teenage gamesters often have never programmed in any
language before, so Lua seems to be a good first-language for folks.
On the other hand, both Forth and Lisp offer more power and
flexibility --- experienced users may appreciate this.
Lua has a reputation for being easy to extend with C, and you seem to
agree. Do you think that it is feasible for me to replace the hash-
tables with LLRB trees, or would this involve too much tearing apart
of the Lua innards? I haven't examined Lua's C source-code yet, as I'm
still just learning to program in Lua itself.
In regard to your application, have you had any trouble with novices
complaining that Lua is too difficult for them?
On the other hand, have you had any trouble with experienced users
complaining that Lua is too wimpy for them?
Lisp has a long history of use as a DSL (Brief, Emacs and AutoCAD).
Forth has some history as a DSL, but mostly for use by electronics
technicians who use it for testing circuit boards or for low-level
operating-system initialization --- not so much for consumer
applications. I like Forth (it is the only language that I am
particularly good at), so I would prefer it, but I am worried that the
users might be intimidated by it and not make any effort to learn at
all. Because of this, I'm mostly only considering Lisp or Lua.
P.S. Thanks to everybody who has provided links for Lisp LLRB trees.
Some of that I could have found on my own. The reason why I posted the
question here, is that I only used LLRB trees in my novice Forth
package because they were simple to implement. Any kind of balanced
tree algorithm would be fine for my application, and some of the
algorithms might even be more efficient --- I don't really know very
much about the various balanced-tree algorithms and how they compare
to each other --- that is why I'm asking you Lispers, who presumably
do know something about algorithms.
Hugh Aguilar
> MatzLisp (Ruby):
I had never heard of Ruby being called "MatzLisp" before. I hadn't
known that Ruby was derived from Lisp --- I had assumed that it was
yet-another SmallTalk derivative.
I don't really know anything about Ruby except that *everything* is an
object, and it is slow.
For my DSL I also considered Python, with the speed-critical innards
being written in C. Python seems to be oriented toward being a front-
end for a C program, but I have never heard of this being done in
Ruby. Isn't it true that Ruby was mostly designed for use as a stand-
alone scripting language?
I doubt that either Python or Ruby generate fast-enough code to be
used on their own, without the innards being written in C. Also, Ruby
and Python seem too big for my use --- Lua has the advantage of being
small enough that users can learn it quickly. Lua, Scheme and Forth
are the only languages I know of that the designers spent more effort
on removing features than adding features --- their goal was to make a
language as simple as possible, while still being usable. This was
also Niklaus Wirth's goal with Oberon, but that one came out *too*
simple by most accounts.
Mark Wooding
> I had never heard of Ruby being called "MatzLisp" before. I hadn't
> known that Ruby was derived from Lisp --- I had assumed that it was
> yet-another SmallTalk derivative.
I usually describe Ruby -- slightly unfairly -- as the shameful
love-child of Perl and Smalltalk. But there is a bit of Lisp heritage
there: Ruby's symbol syntax looks like CL keywords, and Ruby has
Scheme's first-class continuations.
-- [mdw]
Pascal J. Bourguignon
> On Nov 1, 2:06�pm, w_a_x_man <w_a_x_...@yahoo.com> wrote:
>> MatzLisp (Ruby):
>
> I had never heard of Ruby being called "MatzLisp" before. I hadn't
> known that Ruby was derived from Lisp --- I had assumed that it was
> yet-another SmallTalk derivative.
Ruby is a Matzacred lisp.
> I don't really know anything about Ruby except that *everything* is an
> object, and it is slow.
You can also write code like this in ruby:
http://groups.google.com/group/comp.lang.ruby/msg/56fce4adeaa79f68
Scott L. Burson
> Hello, I'm very new to CL (working my way through "Practical Common
> Lisp"). Can anybody tell me if CL (or PLT Scheme) has an associative
> arrays implementation? I want an implementation that supports doing an
> ordered traversal, and which also supports filtering of regions. I
> want to be able to copy everything within a region into another
> association, or everything outside of a region into another
> association, and also be able to merge two associations together.
FSet has ways to do all those things:
http://common-lisp.net/project/fset/
-- Scott
Scott L. Burson
>
> http://tinyurl.com/3yb8by2
The sarcasm here is uncalled-for. I'm glad Hugh asked us and gave me a
chance to plug FSet, which I don't think he would have found on his own
-- certainly not with that query.
-- Scott
Scott L. Burson
>
> FSet has ways to do all those things:
>
> http://common-lisp.net/project/fset/
I should have added: you can perhaps most easily download and install
FSet by using Quicklisp:
http://www.quicklisp.org/beta/
-- Scott
Hugh Aguilar
> I'm glad Hugh asked us and gave me a
> chance to plug FSet, which I don't think he would have found on his own
> -- certainly not with that query.
Thanks for telling me about FSet. Your FSet package seems to be
inspired by the same kind of thinking that inspired my Forth novice
package --- you are providing basic data-structures and trying to be
robust, rather than application-specific.
I noticed that you said in your documentation: "[Fset is] not the
place to start for newcomers to the language."
I'm currently working my way through "Practical Common Lisp." Can you
recommend a path for getting from here to there?
My plan right now is to learn the basics of Lisp from this book, and
then port my slide-rule program from Forth to Lisp. That program is
recursive at its crux, which seems to make it the kind of program that
would usually get written in Lisp.
I tried to learn Factor, but got bogged down and quit. The problem was
that I didn't understand dynamic-OOP (I have only used static-OOP,
including C++). Factor's documentation is a reference, and it assumes
that the reader already knows the concepts, which I didn't. I decided
to learn Lisp, which Factor is largely derived from, because there are
beau-coup books and documents teaching CLOS concepts. After I grasp
the ideas, I may give Factor another try. I may just stick with CL
though; Factor doesn't support compile-time code, which CL does, so CL
is actually closer to Forth than Factor is, despite the fact that CL
doesn't have a Forth-like parameter stack (which Factor does).
In addition to arrays and lists, my novice package now has associative
arrays too. My slide-rule program used lists for holding all of the
marks in each scale. If I were rewriting that program today, I would
use associative arrays for the marks, with float values as keys. It
would be more efficient because I wouldn't have to sequentially search
for particular nodes or regions the way that I do with the lists. On
the other hand though, lists are useful for the gcode or PostScript
programs that I am generating --- I just append each line of code to
the list as I generate it. The same is true of the shapes, which are
intermediate data that the gcode and Postscript gets generated from.
I think that both Forth and Lisp are good languages for implementing
custom compilers, which is essentially what my slide-rule program is.
Writing a program like this in C would *not* be a good idea! It would
likely be twice as large as the Forth program, and take four times as
long to write.
Frank Buss
> Lua has a reputation for being easy to extend with C, and you seem to
> agree. Do you think that it is feasible for me to replace the hash-
> tables with LLRB trees, or would this involve too much tearing apart
> of the Lua innards? I haven't examined Lua's C source-code yet, as I'm
> still just learning to program in Lua itself.
I don't know much of the details of the Lua runtime system, but why do you
want to change the hashtables with LLRB trees? What is the advantage? If
there are not many collisions, hashtables are fine and maybe even faster
for insert operations.
> In regard to your application, have you had any trouble with novices
> complaining that Lua is too difficult for them?
I have written a tutorial for novices for Lua Player:
http://wiki.ps2dev.org/psp:lua_player:tutorial
and there was a forum, if someone needed more help. In my experience Lua
was easier for non-programmers than other languages. Maybe one of the
reason WoW chooses it, too.
> On the other hand, have you had any trouble with experienced users
> complaining that Lua is too wimpy for them?
No, they didn't use it at all, if it was to wimpy for them :-) But there
were some power users, who like the idea of fast scripting in Lua and
enhanced it with their own C functions for the things which are not
possible in Lua.
Scott L. Burson
>
> I noticed that you said in your documentation: "[Fset is] not the
> place to start for newcomers to the language."
> I'm currently working my way through "Practical Common Lisp." Can you
> recommend a path for getting from here to there?
I think that once you get through Practical Common Lisp, FSet will not
be too much of a stretch, given your other experience. Just be sure you
understand the difference between functions and macros.
-- Scott
Rob Warnock
+---------------
| Hugh Aguilar wrote:
| > Lua has a reputation for being easy to extend with C, and you seem to
| > agree. Do you think that it is feasible for me to replace the hash-
| > tables with LLRB trees, or would this involve too much tearing apart
| > of the Lua innards? I haven't examined Lua's C source-code yet, as I'm
| > still just learning to program in Lua itself.
|
| I don't know much of the details of the Lua runtime system, but why do you
| want to change the hashtables with LLRB trees? What is the advantage? If
| there are not many collisions, hashtables are fine and maybe even faster
| for insert operations.
More importantly, Lua tables are *NOT* merely "hashtables": for
positive integer keys they are *also* "arrays" which provide O(1)
performance for keys that are "dense enough" between 1 and N [where
"dense" and "N" are dynamically discovered as the array is populated].
See <news:jf2dnZcKDNhFVsHR...@speakeasy.net> for more
details and references to the relevant Lua docs.
I'm not saying that it's totally infeasible to replace the hashtable
*part* of Lua tables with LLRB trees, just that you *MUST* preserve
the O(1) performance of the array part.
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Hugh Aguilar
> Frank Buss <f...@frank-buss.de> wrote:
> +---------------| Hugh Aguilar wrote:
>
> | > Lua has a reputation for being easy to extend with C, and you seem to
> | > agree. Do you think that it is feasible for me to replace the hash-
> | > tables with LLRB trees, or would this involve too much tearing apart
> | > of the Lua innards? I haven't examined Lua's C source-code yet, as I'm
> | > still just learning to program in Lua itself.
> |
> | I don't know much of the details of the Lua runtime system, but why do you
> | want to change the hashtables with LLRB trees? What is the advantage? If
> | there are not many collisions, hashtables are fine and maybe even faster
> | for insert operations.
> +---------------
The advantage is that I can do an ordered traversal when the key is a
non-integer value (specifically, when the key is a floating point
value). This could be accomplished in Lua-as-is by using a positive
integer as the key and then sorting the table by the floating-point
datum within the payload of the records. This would be inefficient
because, if I insert a new node, I have to resort the entire table
again. With the LLRB trees, the key can be the float, and the table
will *always* be sorted.
Another advantage, is that I can find regions, and filter out
everything in the region or everything outside of the region. This
could be accomplished in Lua-as-is by sorting the table and then doing
a binary search of the table to find the left-bracket and right-
bracket nodes for the region. The binary search for the left-bracket
would have to find the lowest node that is >= to the target, and the
search for the right-bracket would have to find the highest node that
is <= to the target. This is because, in many cases, there won't be a
node that is *exactly* on the specified boundary.
All in all, using Lua-as-is to work with ordered data would be
inefficient. You are right that the hash-tables may be faster for
insertions, but the inefficiency arises from the need to sort the
table after every insertion. Also, my program would be much
simplified
to have the floating-point value be the key, rather than have an
integer key that doesn't have any particular meaning, and have the
floating-point value buried in the payload. Because I'm expecting non-
programmers to be writing scripts in Lua, I want the table to be as
conceptually simple as possible, which means that the floating point
value will be the key.
> More importantly, Lua tables are *NOT* merely "hashtables": for
> positive integer keys they are *also* "arrays" which provide O(1)
> performance for keys that are "dense enough" between 1 and N [where
> "dense" and "N" are dynamically discovered as the array is populated].
> See <news:jf2dnZcKDNhFVsHR...@speakeasy.net> for more
> details and references to the relevant Lua docs.
>
> I'm not saying that it's totally infeasible to replace the hashtable
> *part* of Lua tables with LLRB trees, just that you *MUST* preserve
> the O(1) performance of the array part.
I know that Lua tables segregate the positive integer keys into an
array, and everything else into a hash-table. I'm only intending to
replace the hash-table part with an LLRB tree. We will still have
IPAIRS for the array part. The big difference is that PAIRS will
provide the nodes in an ordered manner, rather than just saying that
the order is undefined. Also, we will get the region-filtering that
isn't currently available.
Hugh Aguilar
Thanks for your encouragement. After I finish "Practical Common Lisp,"
I will tackle the project of porting the slide-rule program to CL, and
will also upgrade it to use an associative array for the marks rather
than a list, although I will continue to use lists for everything
else.
I've pretty much decided to go with Lua for the new project that I was
discussing, but I also want to learn CL for general interest. I know
the difference between functions and macros --- that is really what
attracted me to Lisp. In Forth we have IMMEDIATE words, and in Lisp
you have macros, and afaik these are the only languages that have
anything like this. C does do string-replacement with #DEFINE, but
that is not at all the same thing as having code that executes at
compile-time.
namekuseijin
>
> - Show quoted text -
care to enlighten us about how much fun it is to be a user of other
people's code rather than write code by yourself?
namekuseijin
> Of course, Lisp doesn't need this split between two languages, it can be
> fast all the time, but I think it is not as easy as Lua for beginners.
http://shootout.alioth.debian.org/u32/benchmark.php?test=all&lang=luajit&lang2=sbcl
That's LuaJIT beating SBCL hard, both in CPU time, memory usage and
code size. It's the scripting language of the Gods... python and ruby
are no match, even Scala has a hard time against it...
who could imagine highly optimized table datastructure could beat the
hell out of cons cells, lists, vectors and the like, huh?
it also allows for sweet-jesus easy FFI by calling GNU gmp here and
there with such grace you hardly notice it's FFI...
Lua's original developer was a Scheme teacher back then, BTW.
Nathan
> On Nov 1, 6:36 pm, Frank Buss <f...@frank-buss.de> wrote:
>
> > Of course, Lisp doesn't need this split between two languages, it can be
> > fast all the time, but I think it is not as easy as Lua for beginners.
>
>
> That's LuaJIT beating SBCL hard, both in CPU time, memory usage and
> code size. It's the scripting language of the Gods... python and ruby
> are no match, even Scala has a hard time against it...
>
> who could imagine highly optimized table datastructure could beat the
> hell out of cons cells, lists, vectors and the like, huh?
>
> it also allows for sweet-jesus easy FFI by calling GNU gmp here and
> there with such grace you hardly notice it's FFI...
>
> Lua's original developer was a Scheme teacher back then, BTW.
Okay, this is likely to tork a lot of people off, that's not my goal.
I only want to accurately reflect what I've seen and heard. From my
own personal benchmarking, from emails with some of the implementors,
from stat's I've read: there is no such thing as a mature
implementation of Common Lisp. We learn Lisp because it is an amazing
language, not because it has an amazing implementation.
If you want your Lisp programs to perform, look into Clojure, it's a
Lisp dialect that runs in the JVM; fully bi-directional Java
compatible. I haven't benchmarked Common Lisp vs Clojure myself, but
I've read a few pieces by other people who said they did it. According
to their statistics at least, Clojure will run about 1/10 the speed of
Java which means it beats existing implementations of Common Lisp by a
factor of 100-1000 times.
Clojure is something a lot of Lisp people like to call a toy. From
what I've see, it doesn't have nearly the feature set of Common Lisp,
the development tools are also not up to the same level which is why I
personally don't use it. If I were trying to write production level
Lisp code however, rather than just being here to learn an amazing
language, I would absolutely go with Clojure.
Nothing about Clojure is that amazing, except that it's standing on
the shoulders of a giant (and computer scientists rarely stand on each
others shoulders). The libraries you're going to get from Java are
much more extensive than you'll find with Common Lisp. Java has also
had a lot of very smart people working on optimizing it's VM.
I read Guy Steele saying "...we were after the C++ programmers. We
managed to drag a lot of them about halfway to Lisp" while talking
about the Java programming language. Ever since then I've been
thinking that a project like Clojure might actually be the original
intent of the Java development team.
Anyway, don't give up on Lisp just because of a slow implementation.
It's true that it's something every developer likes to know they've
got good, but there's enough right with Common Lisp to put up with
almost anything.
Pascal Costanza
> On Nov 3, 3:13 pm, namekuseijin<namekusei...@gmail.com> wrote:
>> On Nov 1, 6:36 pm, Frank Buss<f...@frank-buss.de> wrote:
>>
>>> Of course, Lisp doesn't need this split between two languages, it can be
>>> fast all the time, but I think it is not as easy as Lua for beginners.
>>
>> http://shootout.alioth.debian.org/u32/benchmark.php?test=all〈=lua...
>>
>> That's LuaJIT beating SBCL hard, both in CPU time, memory usage and
>> code size. It's the scripting language of the Gods... python and ruby
>> are no match, even Scala has a hard time against it...
>>
>> who could imagine highly optimized table datastructure could beat the
>> hell out of cons cells, lists, vectors and the like, huh?
>>
>> it also allows for sweet-jesus easy FFI by calling GNU gmp here and
>> there with such grace you hardly notice it's FFI...
>>
>> Lua's original developer was a Scheme teacher back then, BTW.
>
> Okay, this is likely to tork a lot of people off, that's not my goal.
> I only want to accurately reflect what I've seen and heard. From my
> own personal benchmarking, from emails with some of the implementors,
> from stat's I've read: there is no such thing as a mature
> implementation of Common Lisp. We learn Lisp because it is an amazing
> language, not because it has an amazing implementation.
There are a lot of industrial applications of Common Lisp, in the real
world, here and now. This wouldn't be possible if Common Lisp weren't a
mature language.
> If you want your Lisp programs to perform, look into Clojure, it's a
> Lisp dialect that runs in the JVM; fully bi-directional Java
> compatible. I haven't benchmarked Common Lisp vs Clojure myself, but
> I've read a few pieces by other people who said they did it. According
> to their statistics at least, Clojure will run about 1/10 the speed of
> Java which means it beats existing implementations of Common Lisp by a
> factor of 100-1000 times.
I would like to see a more serious comparison, taking different features
of each language into account. While in general, I wouldn't be surprised
if Clojure did better performance-wise, there are certain aspects in the
Clojure design where I find it hard to believe that it has a good chance
at beating Common Lisp. Say, plain functions in Clojure are probably
more efficient than in Common Lisp, but Clojure's method dispatch
mechanism is too general compared to that of CLOS, which in turn was
carefully designed to be both expressive _and_ efficient.
I don't want to make any predictions here, but you can't make them either.
> Clojure is something a lot of Lisp people like to call a toy. From
> what I've see, it doesn't have nearly the feature set of Common Lisp,
> the development tools are also not up to the same level which is why I
> personally don't use it. If I were trying to write production level
> Lisp code however, rather than just being here to learn an amazing
> language, I would absolutely go with Clojure.
This depends a lot on context. See above.
Just as an example, here is an example of a product recently shipped,
implemented in LispWorks: http://www.youtube.com/watch?v=Ti2q8eK0l58
> Nothing about Clojure is that amazing, except that it's standing on
> the shoulders of a giant (and computer scientists rarely stand on each
> others shoulders). The libraries you're going to get from Java are
> much more extensive than you'll find with Common Lisp. Java has also
> had a lot of very smart people working on optimizing it's VM.
Java libraries have to center around the very limiting single
inheritance, single dispatch object-centric model, which usually makes
them too complicated.
> I read Guy Steele saying "...we were after the C++ programmers. We
> managed to drag a lot of them about halfway to Lisp" while talking
> about the Java programming language. Ever since then I've been
> thinking that a project like Clojure might actually be the original
> intent of the Java development team.
After 15 years, still waiting for the other half. Not holding my
breath... :-P
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Tim Bradshaw
> If you want your Lisp programs to perform, look into Clojure, it's a
> Lisp dialect that runs in the JVM; fully bi-directional Java
> compatible. I haven't benchmarked Common Lisp vs Clojure myself, but
> I've read a few pieces by other people who said they did it. According
> to their statistics at least, Clojure will run about 1/10 the speed of
> Java which means it beats existing implementations of Common Lisp by a
> factor of 100-1000 times.
This is so confused as to be tragic. For a start it makes the classic
class/instance confusion that people like to do: you can't compare the
performance of languages, only implementations of those languages. An
in fact you can't even do that, you can compare the performance of
implementations running specific programs. Java is a language, so does
not have performance charactistics. An implementation of Java running
a specific program does.
Then you claim a factor of 1,000 to 10,000 performance difference
(presumably for the same algorithm on good implementations of both
languages), which is just mad.
I thought this kind of silliness had died out, actually.
Nicolas Neuss
> compatible. I haven't benchmarked Common Lisp vs Clojure myself, but
> I've read a few pieces by other people who said they did it.
Maybe you should. You will be surprised.
> According to their statistics at least, Clojure will run about 1/10
> the speed of Java which means it beats existing implementations of
> Common Lisp by a factor of 100-1000 times.
And can probably be beaten by other "existing" implementations of Common
Lisp by a factor of 100-1000.
> Clojure is something a lot of Lisp people like to call a toy.
I'm quite sure you won't find anyone here in this list calling it a toy.
Nicolas
Tamas K Papp
> only want to accurately reflect what I've seen and heard. From my own
> personal benchmarking, from emails with some of the implementors, from
> stat's I've read: there is no such thing as a mature implementation of
> Common Lisp. We learn Lisp because it is an amazing language, not
> because it has an amazing implementation.
Please speak only for yourself. Personally, I find SBCL amazing.
> If you want your Lisp programs to perform, look into Clojure, it's a
> Lisp dialect that runs in the JVM; fully bi-directional Java compatible.
> I haven't benchmarked Common Lisp vs Clojure myself, but I've read a few
> pieces by other people who said they did it. According to their
> statistics at least, Clojure will run about 1/10 the speed of Java which
> means it beats existing implementations of Common Lisp by a factor of
> 100-1000 times.
So you found that the program runs 1000-10000 slower when implemented
in CL, compared to Java? I find this very hard to believe.
Can share the information necessary to replicate this benchmark ---
including source code, the exact implementation(s) you used, etc?
> Clojure is something a lot of Lisp people like to call a toy. From what
I can't say that this is a prevalent attitude. What made you form
this impression?
> Anyway, don't give up on Lisp just because of a slow implementation.
I was not about to give up on Lisp. Also, I find you premise is
false: CL has quite a few implementations that compile very efficient
code.
I think that you have made some extraordinary claims about CL, now it
is time to supply some extraordinary evidence. I am looking forward
to seeing your benchmarks.
Best,
Tamas
namekuseijin
> Then you claim a factor of 1,000 to 10,000 performance difference
> (presumably for the same algorithm on good implementations of both
> languages), which is just mad.
mad it is indeed:
http://shootout.alioth.debian.org/u32/benchmark.php?test=all&lang=sbcl&lang2=clojure
but this is on single core... which is not Clojure's strength...
Pascal J. Bourguignon
> If you want your Lisp programs to perform, look into Clojure, it's a
> Lisp dialect that runs in the JVM; fully bi-directional Java
> compatible. I haven't benchmarked Common Lisp vs Clojure myself, but
> I've read a few pieces by other people who said they did it. According
> to their statistics at least, Clojure will run about 1/10 the speed of
> Java which means it beats existing implementations of Common Lisp by a
> factor of 100-1000 times.
I don't believe that. I think it's a trick to have all CLispers try
Clojure and perhaps switch to it.
Next week, another lisp-like language will be invented, and they will
also try to disperse the lisp community efforts.
This is a 'babel' plot to destroy lisp.
Paul Donnelly
> Okay, this is likely to tork a lot of people off, that's not my goal.
> I only want to accurately reflect what I've seen and heard. From my
> own personal benchmarking, from emails with some of the implementors,
> from stat's I've read: there is no such thing as a mature
> implementation of Common Lisp. We learn Lisp because it is an amazing
> language, not because it has an amazing implementation.
What is your definition of "mature"? It seems different from the one I
am using.
Thomas A. Russ
> Okay, this is likely to tork a lot of people off, that's not my goal.
> I only want to accurately reflect what I've seen and heard. From my
> own personal benchmarking, from emails with some of the implementors,
> from stat's I've read: there is no such thing as a mature
> implementation of Common Lisp. We learn Lisp because it is an amazing
> language, not because it has an amazing implementation.
Um, this is patently not true.
There are several mature implementations of Common Lisp. Among them I
would note
Allegro Common Lisp (ACL) from Franz
Lucid Common Lisp
Steel Bank Common Lisp (SBCL)
CMU Common Lisp
These are mature in the sense of having been around for quite a while,
implementing the entire Common Lisp specification, and having high
quality implementations and good compilers.
> If you want your Lisp programs to perform, look into Clojure, it's a
> Lisp dialect that runs in the JVM; fully bi-directional Java
> compatible. I haven't benchmarked Common Lisp vs Clojure myself, but
> I've read a few pieces by other people who said they did it. According
> to their statistics at least, Clojure will run about 1/10 the speed of
> Java which means it beats existing implementations of Common Lisp by a
> factor of 100-1000 times.
Obviously you have not done much work with one of the quality Common
Lisp implementations if you think that is the speed you should expect.
We run a large system, PowerLoom [1], which we translate into native
Lisp, Java and C++ code. When we run our standard test suite on these
different base implementations we generally observe the following
performance characteristics:
The Java and Lisp versions perform about the same.
The C++ version is faster by a factor of 1.5 to 2x.
This is actually one of the few examples of what is essentially a single
code base translated into multiple languages. I think that gives a much
better feel for the effects of the language than random rumors.
[1] http://www.isi.edu/isd/LOOM/PowerLoom
--
Thomas A. Russ, USC/Information Sciences Institute
Hugh Aguilar
> [Lua is] the scripting language of the Gods... python and ruby
> are no match, even Scala has a hard time against it...
Lua is the scripting language of the gods??? I thought the gods did
their programming in DNA. We may not be qualified to criticize their
programming skills, considering that we *are* the programs. :-)
By some accounts, the internet was invented so people could argue
about which is the "best" programming language, and this continues to
be its primary use today. ;-) What I'm trying to say, is that it was
not my intention in this thread to start yet-another Language Wars
skirmish. These kinds of debates are like comparing apples and
oranges. Python and Ruby are *very* different from Lua in their size
and their intended use, so it doesn't really mean much to say that Lua
can beat them. For the application that I have in mind right now, I do
think that Lua is likely the best choice because it is *very* light-
weight. A lot of people like Ruby and Python for writing light-weight
programs, and PLT Scheme is also in this league. CL seems to be more
oriented toward heavy-weight programs though. A lot of this is just a
matter of taste though. There are people writing huge heavy-weight
programs in Scheme (Donald Knuth and his iTex), and there are also
people using CL for scripting.
My goal with Lisp or Scheme or whatever, is to learn how to do
"scripting" on desktop computers. When I worked as a Forth programmer
previously, I wrote software for micro-controllers, which is a lot
different than scripting on desktop computers. I have written software
for desktop computers in Forth, but I am increasingly unconvinced of
Forth appropriateness to the desktop environment (although I still
think that Forth is and always will be the best language for micro-
controllers). Given my background as a Forther, I think that PLT
Scheme would be a pretty good language for me, because it is lighter-
weight than CL. On the other hand though, there are more books
available for CL than Scheme, so I am learning CL first to make my
educational process easier (I prefer paper-and-ink books to online
documents).
On the subject of speed, in Forth I have always dropped down into
assembly-language as necessary. I'm generally more interested in how
easy this is for the various implementations, than in any table of
benchmarks comparing the various implementations in regard to
"typical" code (whatever that is). I asked about this once before and
was told that PLT Scheme and several of the CL implementations have
assemblers. Does anybody have an opinion on which systems lend
themselves to assembly-language programming?
Isaac Gouy
> On Nov 4, 10:54 am, Tim Bradshaw <t...@tfeb.org> wrote:
>
> > Then you claim a factor of 1,000 to 10,000 performance difference
> > (presumably for the same algorithm on good implementations of both
> > languages), which is just mad.
>
> mad it is indeed:
>
>
> but this is on single core... which is not Clojure's strength...
So look at quad-core ;-)
http://shootout.alioth.debian.org/u32q/benchmark.php?test=all&lang=sbcl&lang2=clojure
http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=sbcl&lang2=clojure
namekuseijin
> On Nov 4, 9:04 am, namekuseijin <namekusei...@gmail.com> wrote:
>
> > On Nov 4, 10:54 am, Tim Bradshaw <t...@tfeb.org> wrote:
>
> > > Then you claim a factor of 1,000 to 10,000 performance difference
> > > (presumably for the same algorithm on good implementations of both
> > > languages), which is just mad.
>
> > mad it is indeed:
>
> >http://shootout.alioth.debian.org/u32/benchmark.php?test=all〈=sbc...
>
> > but this is on single core... which is not Clojure's strength...
>
> So look at quad-core ;-)
>
>
> http://shootout.alioth.debian.org/u64q/benchmark.php?test=all〈=sb...
hey, aren't you from C++ world alone?
anyway, yeah, pretty dismal results. Still I find more impressive is
that you get quite a few concurrency in Clojure for granted, without
even looking (or writing) for it:
http://shootout.alioth.debian.org/u64q/program.php?test=spectralnorm&lang=clojure&id=3
this shares computation on 4 cores for a load of about 30% for each
one, yet I see no explicit concurrency mechanisms like in the low-
level CL one:
http://shootout.alioth.debian.org/u64q/program.php?test=spectralnorm&lang=sbcl&id=3
I wonder what would result if someone more experienced in Clojure
would program a more concurrently-geared version with operators like
doseq...
Tim Bradshaw
> There are several mature implementations of Common Lisp. Among them I
> would note
> Allegro Common Lisp (ACL) from Franz
> Lucid Common Lisp
> Steel Bank Common Lisp (SBCL)
> CMU Common Lisp
I suspect Lucid (now Liquid) is mostly legacy now. However LispWorks
(from the same vendor) should definitely be on this list, as should
Clozure Common Lisp, CLISP, and I am sure others I have missed.
There are probably ~10 good mature, maintained, implementations I
should think including at least a couple with excellent commercial
support.
I guess the point I'm trying to make is that the implementation
position is currently better than it has ever been: you have to be on a
fairly left-field platform to not have at least a couple of really good
implementations.
Isaac Gouy
> On Nov 4, 7:46 pm, Isaac Gouy <igo...@yahoo.com> wrote:
> > > but this is on single core... which is not Clojure's strength...
>
> > So look at quad-core ;-)
>
> >http://shootout.alioth.debian.org/u32q/benchmark.php?test=all〈=sb...
>
> >http://shootout.alioth.debian.org/u64q/benchmark.php?test=all〈=sb...
>
> hey, aren't you from C++ world alone?
I have nothing to do with C++
> anyway, yeah, pretty dismal results. Still I find more impressive is
> that you get quite a few concurrency in Clojure for granted, without
> even looking (or writing) for it:
>
> http://shootout.alioth.debian.org/u64q/program.php?test=spectralnorm&...
>
> this shares computation on 4 cores for a load of about 30% for each
Add the percentages
5,500: 20% + 20% + 43% + 17% = 100%
that's just the OS bouncing the process among the cores.
(I don't recall if JVM GC can use multi core even when the program
itself does not?)
> one, yet I see no explicit concurrency mechanisms like in the low-
> level CL one:
>
> http://shootout.alioth.debian.org/u64q/program.php?test=spectralnorm&...
namekuseijin
> On 2010-11-04 16:38:15 +0000, Thomas A. Russ said:
>
> > There are several mature implementations of Common Lisp. Among them I
> > would note
> > Allegro Common Lisp (ACL) from Franz
> > Lucid Common Lisp
> > Steel Bank Common Lisp (SBCL)
> > CMU Common Lisp
>
> I suspect Lucid (now Liquid) is mostly legacy now. However LispWorks
> (from the same vendor) should definitely be on this list, as should
> Clozure Common Lisp, CLISP, and I am sure others I have missed.
>
> There are probably ~10 good mature, maintained, implementations I
> should think including at least a couple with excellent commercial
> support.
good. It gives me a warm feeling inside to know that mature CL
implementations are being beaten hard by a still quite experimental
Lua JIT compiler... :p
Thomas A. Russ
> On 2010-11-04 16:38:15 +0000, Thomas A. Russ said:
>
> > There are several mature implementations of Common Lisp. Among them I
> > would note
> > Allegro Common Lisp (ACL) from Franz
> > Lucid Common Lisp
> > Steel Bank Common Lisp (SBCL)
> > CMU Common Lisp
>
> I suspect Lucid (now Liquid) is mostly legacy now. However LispWorks
> (from the same vendor) should definitely be on this list,
You're right. I had the nagging feeling that I had gotten the name
wrong, but was too lazy to check.... I meant LispWorks.
Pascal Costanza
It's not the first time in history that CL implementations get beaten by
implementations of other languages in terms of performance. There must
be something to Common Lisp that makes it worthwhile to use it in spite
of this.
namekuseijin
> > good. It gives me a warm feeling inside to know that mature CL
> > implementations are being beaten hard by a still quite experimental
> > Lua JIT compiler... :p
>
> It's not the first time in history that CL implementations get beaten by
> implementations of other languages in terms of performance. There must
> be something to Common Lisp that makes it worthwhile to use it in spite
> of this.
perseverance?
in any case, it's the first time it's beaten by a dynamically typed
scripting language.
I have a love/hate relationship with the Lisp family of languages. I
like the basic ideas, its kernel of operators, I love the homoiconic
nature, I dig hierarchical paren-editing with proper tools, but it's
hard to cope up with the idea that lesser tools often provide better
performance out of ugly means. I mean, often Lisp compiled code is
beaten by tools not actually compiling anything, just translating as
much as they can into as close to C real loops as they can.
Pascal Costanza
> On Nov 5, 6:04 pm, Pascal Costanza<p...@p-cos.net> wrote:
>>> good. It gives me a warm feeling inside to know that mature CL
>>> implementations are being beaten hard by a still quite experimental
>>> Lua JIT compiler... :p
>>
>> It's not the first time in history that CL implementations get beaten by
>> implementations of other languages in terms of performance. There must
>> be something to Common Lisp that makes it worthwhile to use it in spite
>> of this.
>
> perseverance?
>
> in any case, it's the first time it's beaten by a dynamically typed
> scripting language.
I wouldn't know. Smalltalk, for example, is known to have very efficient
implementations, and I wouldn't be surprised if at some stage in history
it was better than Lisp. Or maybe not. So what?
> I have a love/hate relationship with the Lisp family of languages. I
> like the basic ideas, its kernel of operators, I love the homoiconic
> nature, I dig hierarchical paren-editing with proper tools, but it's
> hard to cope up with the idea that lesser tools often provide better
> performance out of ugly means. I mean, often Lisp compiled code is
> beaten by tools not actually compiling anything, just translating as
> much as they can into as close to C real loops as they can.
To quote Richard Gabriel: "Performance is an issue, but it is not the
only issue."
Tamas K Papp
> On Nov 5, 6:04 pm, Pascal Costanza <p...@p-cos.net> wrote:
>> > good. It gives me a warm feeling inside to know that mature CL
>> > implementations are being beaten hard by a still quite experimental
>> > Lua JIT compiler... :p
>>
>> It's not the first time in history that CL implementations get beaten
>> by implementations of other languages in terms of performance. There
>> must be something to Common Lisp that makes it worthwhile to use it in
>> spite of this.
>
> perseverance?
>
> in any case, it's the first time it's beaten by a dynamically typed
> scripting language.
I think that you are reading too much into a few simple benchmarks.
The graph that you linked to shows that sometimes SBCL is faster than
LUA, sometimes the other way round. Consider this simple statistical
model:
log CPU time_{i,j} ~ N(alpha_j+beta_i, sigma^2_j)
for benchmark i and language (& implementation) j. Even if you care a
lot about speed, presumably you would not be interested in the log CPU
time measurements, but the comparison of alpha's. Since they are
stochastic, you would care about alpha_SBCL-alpha_LUAJIT or something
like that.
Given the small amount of data, you would have a huge posterior
uncertainty about these variables. You could overcome some of that
using a multilevel model for all the benchmarks, but even then, you
could only conclude that a language has "beaten" the other with
reasonable posterior probability when the disparity is very large.
> I have a love/hate relationship with the Lisp family of languages. I
> like the basic ideas, its kernel of operators, I love the homoiconic
> nature, I dig hierarchical paren-editing with proper tools, but it's
> hard to cope up with the idea that lesser tools often provide better
> performance out of ugly means. I mean, often Lisp compiled code is
> beaten by tools not actually compiling anything, just translating as
> much as they can into as close to C real loops as they can.
I don't see the problem --- you can always profile you code and
rewrite that 5% that is using up 80% of the CPU time; in
micro-optimized CL, or C, or Fortran, whatever. So you get the
elegance and power of Lisp, and speed is always available on demand.
For example, Liam Healy's GSLL uses GSL (written in C), while my LLA
library uses LAPACK/ATLAS (written in Fortran). I wrote the bindings,
then from then on I could just ignore this part and concentrate on
programming the tricky parts in CL. So I don't share your concerns,
for me this is a non-issue.
Best,
Tamas
Hugh Aguilar
> On 06/11/2010 01:38, namekuseijin wrote:
>
> > On Nov 5, 6:04 pm, Pascal Costanza<p...@p-cos.net> wrote:
> >>> good. It gives me a warm feeling inside to know that mature CL
> >>> implementations are being beaten hard by a still quite experimental
> >>> Lua JIT compiler... :p
>
> >> It's not the first time in history that CL implementations get beaten by
> >> implementations of other languages in terms of performance. There must
> >> be something to Common Lisp that makes it worthwhile to use it in spite
> >> of this.
>
> > perseverance?
Code speed isn't a big issue for me. A modern computer can run a Lisp
program in a few seconds, compared to the same program written in 8088
assembly-language and taking a few hours back in the 1980s. Besides
that, if speed really is an issue, I wouldn't be using *any* dynamic-
OOP language for the job, so comparing the speed of dynamic-OOP
languages seems pointless to me. That is like comparing the speed of
pickup trucks, and ignoring the fact that their purpose is hauling
cargo.
According to the book, "Practical Common Lisp" (page 1, paragraph 1),
people use CL because: "you'll get more done, faster."
That is why I'm learning Lisp. I looked at Python, which makes the
same claim, but I decided that CL was a better choice because it is a
lot more powerful (it has macros, which I'm familiar with from Forth).
Also, I didn't like Python's philosophy that there is only one way to
do any job. That may be comforting for a novice (in the same way that
Christianity is comforting to children and child-like adults), but I
doubt that you'll find many Lispers claiming that there is only one
way to do any job and that due to divine inspiration they alone know
what that one true way is. That kind of thinking leads to an "End
Times" type of conclusion --- but I don't think any of us want the
world to come to an end, or computer science either. Lispers seem to
be a smarter crowd than you'll find in other language communities, but
they also are smart enough to know that they don't know everything ---
at least, that is what I'm hoping for (there may be exceptions).
As for Lua, I like it and intend to use it as an embedded scripting
language in C programs. Lua is completely different from CL though.
You can't embed CL inside of a C program because CL is too big. On the
other hand though, CL can be used for much larger programs than you
would really want to attempt in C/Lua. Those tables are pretty cool,
but they are somewhat of a Procrustean Bed, in the sense that they
aren't the best choice for every kind of data. As an analogy, C/Lua is
like an economy-hatchback that you use for carrying light loads, and
Lisp is like a full-size pickup truck that you use for carrying heavy
loads.
Tim Bradshaw
> good. It gives me a warm feeling inside to know that mature CL
> implementations are being beaten hard by a still quite experimental
> Lua JIT compiler... :p
I very much doubt these benchamrks mean anything at all.
Tamas K Papp
> You can't embed CL inside of a C program because CL is too big. On the
AFAIK you can embed ECL in C/C++ programs. Their webpage has examples.
Best,
Tamas
Pascal J. Bourguignon
> You can't embed CL inside of a C program because CL is too big.
What a brainfart!
On my system, there are 65 libraries in /usr/lib that are bigger than
libecl! boost-regexp is bigger than libecl! (This is just a fucking
regexp library and it's bigger than a whole language including a
compiler, an interpreter, and a standard library). Or libxml2, which is
just a fucking serializer and deserializer for sexps!
If CL is too big to include in a C program, then you should just stop
writing C program, because libc which is the standard library for C
programs, is twice the size of a CL implementation!
-rwxr-xr-x 1 root root 1960912 Oct 22 11:15 /usr/lib/libecl.so.9.12.3*
-rw-r--r-- 1 root root 1994280 Sep 25 21:15 /usr/lib/libdb-4.5.a
-rw-r--r-- 2 root root 2051448 Sep 25 12:58 /usr/lib/libboost_regex-1_41.a
-rw-r--r-- 2 root root 2051448 Sep 25 12:58 /usr/lib/libboost_regex-mt-1_41.a
-rwxr-xr-x 1 root root 2065040 Sep 25 23:27 /usr/lib/libgsl.so.0.15.0*
-rwxr-xr-x 1 root root 2074480 Sep 26 00:23 /usr/lib/libosp.so.5.0.0*
-rw-r--r-- 2 root root 2115172 Sep 25 12:58 /usr/lib/libboost_unit_test_framework-1_41.a
-rw-r--r-- 2 root root 2115172 Sep 25 12:58 /usr/lib/libboost_unit_test_framework-mt-1_41.a
-rw-r--r-- 1 root root 2116278 Oct 24 05:28 /usr/lib/libxml2.a
-rw-r--r-- 1 root root 2146394 Sep 25 21:05 /usr/lib/librecode.a
-rw-r--r-- 1 root root 2183898 Sep 25 21:15 /usr/lib/libdb_cxx-4.5.a
-rw-r--r-- 2 root root 2187126 Sep 25 12:58 /usr/lib/libboost_math_tr1l-1_41.a
-rw-r--r-- 2 root root 2187126 Sep 25 12:58 /usr/lib/libboost_math_tr1l-mt-1_41.a
-rw-r--r-- 1 root root 2190672 Sep 25 12:58 /usr/lib/libboost_math_tr1-1_41.a
-rw-r--r-- 1 root root 2190672 Sep 25 12:58 /usr/lib/libboost_math_tr1-mt-1_41.a
-rwxr-xr-x 1 root root 2198464 Oct 22 03:23 /usr/lib/libpoppler.so.7.0.0*
-rw-r--r-- 1 root root 2200582 Sep 25 21:15 /usr/lib/libdb_java-4.5.a
-rw-r--r-- 2 root root 2229584 Sep 25 12:58 /usr/lib/libboost_math_tr1f-1_41.a
-rw-r--r-- 2 root root 2229584 Sep 25 12:58 /usr/lib/libboost_math_tr1f-mt-1_41.a
-rw-r--r-- 1 root root 2292584 Sep 25 05:12 /usr/lib/libdb-4.7.a
-rwxr-xr-x 1 root root 2390936 Nov 1 14:10 /usr/lib/libMagickCore.so.3.0.0*
-rw-r--r-- 1 root root 2408634 Sep 25 05:11 /usr/lib/libdb-4.8.a
-rw-r--r-- 1 root root 2490538 Sep 25 05:12 /usr/lib/libdb_cxx-4.7.a
-rw-r--r-- 1 root root 2520144 Sep 25 05:12 /usr/lib/libdb_java-4.7.a
-rwxr-xr-x 1 root root 2558432 Sep 26 00:24 /usr/lib/libostyle.so.0.0.1*
-rwxr-xr-x 1 root root 2567840 Oct 20 02:12 /usr/lib/libmzscheme3m-4.2.2.so*
-rwxr-xr-x 1 root root 2569096 Oct 24 06:33 /usr/lib/libosg.so.2.8.3*
-rw-r--r-- 1 root root 2622160 Sep 25 05:11 /usr/lib/libdb_cxx-4.8.a
-rw-r--r-- 1 root root 2651792 Sep 25 05:11 /usr/lib/libdb_java-4.8.a
-rw-r--r-- 1 root root 2721322 Oct 23 09:59 /usr/lib/libdns.a
-rwxr-xr-x 1 root root 2729024 Sep 25 22:29 /usr/lib/libkdecore.so.5.4.0*
-rw-r--r-- 1 root root 2786418 Sep 25 05:11 /usr/lib/libdb_stl-4.8.a
-rw-r--r-- 1 root root 2819722 Sep 25 17:40 /usr/lib/libclucene.a
-rw-r--r-- 1 root root 2828816 Oct 22 11:26 /usr/lib/libpdf.a
-rwxr-xr-x 1 root root 2878784 Oct 11 06:00 /usr/lib/libXm.so.4.0.3*
-rw-r--r-- 1 root root 2882180 Oct 22 08:59 /usr/lib/libpython2.6.a
-rwxr-xr-x 1 root root 2918016 Sep 25 22:29 /usr/lib/libkio.so.5.4.0*
-rwxr-xr-x 1 root root 2942944 Sep 25 03:35 /usr/lib/libvorbisenc.so.2.0.7*
-rw-r--r-- 1 root root 2959148 Oct 22 11:26 /usr/lib/libpdf_java.a
-rwxr-xr-x 1 root root 3027216 Sep 25 22:29 /usr/lib/libplasma.so.3.0.0*
-rw-r--r-- 1 root root 3040934 Sep 25 21:24 /usr/lib/libgtk.a
-rw-r--r-- 1 root root 3053534 Oct 22 09:01 /usr/lib/libpython3.1.a
-rwxr-xr-x 1 root root 3104176 Oct 22 09:59 /usr/lib/libpari.so.2.3.4*
-rw-r--r-- 1 root root 3223716 Oct 8 09:35 /usr/lib/libcrypto.a
-rw-r--r-- 1 root root 3265690 Sep 25 12:58 /usr/lib/libboost_wave-1_41.a
-rw-r--r-- 1 root root 3265690 Sep 25 12:58 /usr/lib/libboost_wave-mt-1_41.a
-rwxr-xr-x 1 root root 3311752 Sep 25 23:28 /usr/lib/libqalculate.so.5.0.0*
-rw-r--r-- 1 root root 3978808 Sep 25 23:27 /usr/lib/libgsl.a
-rwxr-xr-x 1 root root 4259976 Oct 24 06:25 /usr/lib/libgtk-x11-2.0.so.0.2000.1*
-rw-r--r-- 1 root root 4405634 Nov 1 14:05 /usr/lib/libc.a
-rwxr-xr-x 1 root root 4446328 Sep 25 22:29 /usr/lib/libkdeui.so.5.4.0*
-rw-r--r-- 1 root root 4533916 Oct 11 06:00 /usr/lib/libXm.a
-rwxr-xr-x 1 root root 4666216 Sep 25 21:55 /usr/lib/libgtkmm-2.4.so.1.1.0*
-rwxr-xr-x 1 root root 4820608 Oct 24 08:39 /usr/lib/libsmbclient.so.0*
-rwxr-xr-x 1 root root 5009016 Oct 24 08:39 /usr/lib/libnetapi.so.0*
-rw-r--r-- 1 root root 5338078 Sep 25 23:28 /usr/lib/libqalculate.a
-rwxr-xr-x 1 root root 6758936 Oct 24 05:58 /usr/lib/libavcodec.so.52.72.2*
-rw-r--r-- 1 root root 7071428 Oct 22 09:48 /usr/lib/libcln.a
-rwxr-xr-x 1 root root 7536312 Sep 25 22:29 /usr/lib/libkhtml.so.5.4.0*
-rwxr-xr-x 1 root root 7970544 Oct 23 07:33 /usr/lib/libgs.so.8.71*
-rwxr-xr-x 1 root root 8142598 Oct 27 19:38 /usr/lib/libcuda.so.256.44*
-rw-r--r-- 1 root root 8587306 Oct 24 05:58 /usr/lib/libavcodec.a
-rwxr-xr-x 1 root root 11296848 Oct 22 05:24 /usr/lib/libCg.so*
-rwxr-xr-x 1 root root 14930560 Sep 25 17:41 /usr/lib/libicudata.so.44.1*
-rwxr-xr-x 1 root root 15886888 Oct 27 19:38 /usr/lib/libnvidia-compiler.so.256.44*
-rwxr-xr-x 1 root root 18637080 Sep 25 22:19 /usr/lib/libwebkit-1.0.so.2.17.5*
-rwxr-xr-x 1 root root 24999088 Oct 27 19:38 /usr/lib/libnvidia-glcore.so.256.44*
namekuseijin
> Hugh Aguilar <hughaguila...@yahoo.com> writes:
> > You can't embed CL inside of a C program because CL is too big.
>
> What a brainfart!
>
> On my system, there are 65 libraries in /usr/lib that are bigger than
> libecl! boost-regexp is bigger than libecl! (This is just a fucking
> regexp library and it's bigger than a whole language including a
> compiler, an interpreter, and a standard library). Or libxml2, which is
> just a fucking serializer and deserializer for sexps!
>
> If CL is too big to include in a C program, then you should just stop
> writing C program, because libc which is the standard library for C
> programs, is twice the size of a CL implementation!
>
> -rwxr-xr-x 1 root root 1960912 Oct 22 11:15 /usr/lib/libecl.so.9.12.3*
PWNED
libecl is smaller than libpython too. But I suspect that's because
libecl is just some interpreter for CL code, not a lib of CL code.
There must be some /usr/share/ecl or something for CL libs code,
right?
besides, regex is not part of CL... it is part of python, though...
Mark Wooding
> On my system, there are 65 libraries in /usr/lib that are bigger than
> libecl! boost-regexp is bigger than libecl! (This is just a fucking
> regexp library and it's bigger than a whole language including a
> compiler, an interpreter, and a standard library).
Be fair. ECL's compiler is separately loaded from
/usr/lib/ecl-VERSION/cmp.fas. (It's still rather worrying, though.)
-- [mdw]
André Thieme
> On 04/11/2010 12:52, Nathan wrote:
>> If you want your Lisp programs to perform, look into Clojure, it's a
>> Lisp dialect that runs in the JVM; fully bi-directional Java
>> compatible. I haven't benchmarked Common Lisp vs Clojure myself, but
>> I've read a few pieces by other people who said they did it. According
>> to their statistics at least, Clojure will run about 1/10 the speed of
>> Java which means it beats existing implementations of Common Lisp by a
>> factor of 100-1000 times.
>
> I would like to see a more serious comparison, taking different features
> of each language into account. While in general, I wouldn't be surprised
> if Clojure did better performance-wise, there are certain aspects in the
> Clojure design where I find it hard to believe that it has a good chance
> at beating Common Lisp. Say, plain functions in Clojure are probably
> more efficient than in Common Lisp, but Clojure's method dispatch
> mechanism is too general compared to that of CLOS, which in turn was
> carefully designed to be both expressive _and_ efficient.
The number 100 to 1000 is totally bogus. On many problem sets an
equivalent Clojure implementation, running on the JVM with the right
parameters set, may outperform a CL version, though not by orders of
magnitude. Plus there are still challenges that (for example) SBCL will
perform better.
About the function calls:
Yes, they are pretty efficient in Clojure. And you are right that the
method dispatch for multimethods is less efficient and some CLs are
probably better at this.
I microbenchmarked fns vs. multimethods, and got roughly a factor of 10.
Though since Clojure 1.2 there are now Protocols that are a special case
of MM: they dispatch on the type of the first argument.
This is the most typical case and a reason why single-dispatch languages
are able to get anything done, as one often wants to call a method for
a specific kind of object.
And calls of Protocol methods vs. ordinary fns is about factor of 2.
> Java libraries have to center around the very limiting single
> inheritance, single dispatch object-centric model, which usually makes
> them too complicated.
In my experience single dispatch works well for most cases.
For example, let’s assume how many ANSI CL functions could be
implemented with single dispatch. It is not like 3%, but more like,
say, 90%.
Pascal Costanza
CLOS is specified in such a way that it doesn't matter whether single
dispatch occurs more often than multiple dispatch or not. I think this
is better, because you don't have to worry about this anymore, and you
don't need to change between different concepts for performance reasons.
Juanjo
Be fair too. ECL has TWO compilers. A bytecodes compiler that is in
libecl.so and a separate Lisp-to-C compiler that is in cmp.fas :-)
Mark Wooding
> Be fair too. ECL has TWO compilers. A bytecodes compiler that is in
> libecl.so and a separate Lisp-to-C compiler that is in cmp.fas :-)
It's a fair cop. You're indeed right.
-- [mdw]
Pascal J. Bourguignon
Only 972 macros and functions, in addition to the compilier (granted,
targetting C, not x86), interpreter and debugger.
> There must be some /usr/share/ecl or something for CL libs code,
> right?
Not really.
[pjb@kuiper :0.0 lispm.dyndns.org]$ ls -lh /usr/lib/ecl-9.12.3/
total 4.2M
drwxr-xr-x 3 root root 4.0K Oct 22 11:15 ./
drwxr-xr-x 148 root root 120K Nov 7 11:18 ../
-rw-r--r-- 1 root root 753 Oct 22 11:15 BUILD-STAMP
-rwxr-xr-x 1 root root 156K Oct 22 11:15 asdf.fas*
-rw-r--r-- 1 root root 64 Oct 22 11:15 bytecmp.asd
-rwxr-xr-x 1 root root 19K Oct 22 11:15 bytecmp.fas*
-rw-r--r-- 1 root root 56 Oct 22 11:15 clx.asd
-rwxr-xr-x 1 root root 1.7M Oct 22 11:15 clx.fas*
-rw-r--r-- 1 root root 56 Oct 22 11:15 cmp.asd
-rwxr-xr-x 1 root root 653K Oct 22 11:15 cmp.fas*
-rw-r--r-- 1 root root 68 Oct 22 11:15 defsystem.asd
-rwxr-xr-x 1 root root 172K Oct 22 11:15 defsystem.fas*
-rw-r--r-- 1 root root 80K Oct 22 11:15 dpp
-rw-r--r-- 1 root root 701K Oct 22 11:15 ecl_min
drwxr-xr-x 2 root root 4.0K Oct 22 11:15 encodings/
-rw-r--r-- 1 root root 185K Oct 22 11:15 help.doc
-rw-r--r-- 1 root root 64 Oct 22 11:15 profile.asd
-rwxr-xr-x 1 root root 39K Oct 22 11:15 profile.fas*
-rw-r--r-- 1 root root 54 Oct 22 11:15 rt.asd
-rwxr-xr-x 1 root root 31K Oct 22 11:15 rt.fas*
-rw-r--r-- 1 root root 78 Oct 22 11:15 sb-bsd-sockets.asd
-rwxr-xr-x 1 root root 5.8K Oct 22 11:15 sb-bsd-sockets.fas*
-rw-r--r-- 1 root root 72 Oct 22 11:15 serve-event.asd
-rwxr-xr-x 1 root root 19K Oct 22 11:15 serve-event.fas*
-rw-r--r-- 1 root root 64 Oct 22 11:15 sockets.asd
-rwxr-xr-x 1 root root 87K Oct 22 11:15 sockets.fas*
-rw-r--r-- 1 root root 71K Oct 22 11:15 sysfun.lsp
-rw-r--r-- 1 root root 100K Oct 22 11:15 ucd.dat
ecl_min is a duplicate of libecl, it doesn't use it:
[pjb@kuiper :0.0 lispm.dyndns.org]$ ldd /usr/lib/ecl-9.12.3/ecl_min
linux-vdso.so.1 => (0x00007ffffd74b000)
libgmp.so.3 => /usr/lib/libgmp.so.3 (0x00007f86a15f6000)
libgc.so.1 => /usr/lib/libgc.so.1 (0x00007f86a139e000)
libpthread.so.0 => /lib/libpthread.so.0 (0x00007f86a1182000)
libdl.so.2 => /lib/libdl.so.2 (0x00007f86a0f7e000)
libm.so.6 => /lib/libm.so.6 (0x00007f86a0cfd000)
libc.so.6 => /lib/libc.so.6 (0x00007f86a09a1000)
/lib64/ld-linux-x86-64.so.2 (0x00007f86a184e000)
libgcc_s.so.1 => /lib/libgcc_s.so.1 (0x00007f86a078a000)
Most of the size in /usr/lib/ecl is the unicode character encoding
descriptions, and clx and other add-on systems.
> besides, regex is not part of CL... it is part of python, though...
What is part of a language, what is not part? That's why discussing
sizes is ridiculous. clisp provides the REGEXP package which is a FFI
to regex(3), and you can write a reader macro to integrate regular
expressions written as /a(b|c)*d/ in CL.
Pascal J. Bourguignon
Robert Maas, http://tinyurl.com/uh3t
> Can anybody tell me if CL (or PLT Scheme) has an associative
> arrays implementation?
CL has three different associative-array implementations built in:
- Assoc lists
- Property lists
- Hashtables
> I want an implementation that supports doing an ordered traversal
The first two of those listed above have a well-defined traversal order.
> and which also supports filtering of regions. I want to be able
> to copy everything within a region into another association, or
> everything outside of a region into another association,
Since we're talking about a linear object, by "region" do you
really mean segment (from some starting element to some ending
element, where each element is a key-value pair)?
> and also be able to merge two associations together.
By "merge" do you mean "append" or "collate" or merge per some
order-relation that each linear object satisfied before the merge?
So-far it sounds like you want an assoc list. You can use the SORT
function to rearrange it per some order-relation, and after two
assoc lists have been sorted you can use the MERGE function to
merge them per that same order-relation.
> The reason why I ask, is that I wrote such an associative arrays
> implementation (using LLRB trees) in ANS-Forth. I want to have the
> same capability in Lisp that I have in Forth. I can port my code from
> Forth to Lisp (after I get better at Lisp), but I would be interested
> in knowing if somebody else has already done something similar.
Google search shows LLRB is a type of self-balacing binary search
tree. Such have extra properties that you didn't list above,
specifically that you can insert/delete/merge/split in log(n) time
while sharing all structure (between original and modified tree)
except the log(n) path from root to the point of change. You didn't
say whether you *need* that feature, in which case assoc lists
wouldn't satisfy your needs, or not, in which case assoc lists
would be good enough. If you typically have less than a thousand
items in each associative array, the speed difference is probably
too small to care about.
By the way, a few years ago I implemented my own SBBST, which
balances on the basis of total number of nodes rather than maximum
depth of each sub-tree, and allows you to find the nth element in
log(n) time which some of the other SBBSTs don't allow.
Robert Maas, http://tinyurl.com/uh3t
> And also:
> http://www.informatimago.com/develop/lisp/com/informatimago/common-lisp/llrbtree.lisp
> ;;;;AUTHORS
> ;;;; <PJB> Pascal J. Bourguignon <p...@informatimago.com>
That's weird! All these years I thought Pascal J. Bourguignon was
just one person. How many people are you? Sind Sie und bist du
zwei? Did you ever get in a disagreement with yourself about how to
do some part of the program, and have a knock-down drag-out fight
with yourself? Which of you-all won the fight?
Pascal J. Bourguignon
writes:
It's even worse, in some asd files (generated automatically), we see
that the authors are Pascal J. Bourguignon and Pascal Bourguignon.
I'm just an optimist and dream eventually to sprout into a
multi-nationnal corporation with thousands of lisp programmers helping
me.
Hugh Aguilar
wrote:
> Hugh Aguilar <hughaguila...@yahoo.com> writes:
> > You can't embed CL inside of a C program because CL is too big.
>
> What a brainfart!
>
> On my system, there are 65 libraries in /usr/lib that are bigger than
> libecl! boost-regexp is bigger than libecl! (This is just a fucking
> regexp library and it's bigger than a whole language including a
> compiler, an interpreter, and a standard library). Or libxml2, which is
> just a fucking serializer and deserializer for sexps!
>
> If CL is too big to include in a C program, then you should just stop
> writing C program, because libc which is the standard library for C
> programs, is twice the size of a CL implementation!
Considering that I'm an admitted newbie to CL, I think you could have
disagreed with me without all of the vulgarity.
A big part of why I'm getting away from comp.lang.forth is because of
the vulgarity over there. I have been told that my code is "crap" and
it "sucks" --- that my use of binary trees rather than hash tables is
"stupid" and "incompetent" --- that I am "diseased" --- etc.. If I
complain that this kind of language is inappropriate for a programming
forum, Elizabeth Rather accuses me of being "homophobic and
intolerant:"
http://groups.google.com/group/comp.lang.forth/browse_thread/thread/c37b473ec4da66f1
I'm expecting you Lispers to be a more classy crowd than the Forthers.
Don't they have etiquette classes at MIT? :-)
Tim Bradshaw
> I'm expecting you Lispers to be a more classy crowd than the Forthers.
We're a pretty nasty lot, on the whole.
> Don't they have etiquette classes at MIT? :-)
have you *met* anyone from MIT? They say some of them have had
successful relationships, but I doubt it, myself.
namekuseijin
>
> I'm expecting you Lispers to be a more classy crowd than the Forthers.
> Don't they have etiquette classes at MIT? :-)
people grow nastier as they get older. go to alt.astronomy and marvel
at a bunch of old men throwing shit at each other all day long and
talking about anything but astronomy...
namekuseijin
BTW, I suspect something like that will happen to Lisp as it implodes
into a brown dwarf... :p
Hugh Aguilar
http://tinyurl.com/uh3t) wrote:
> > From: Hugh Aguilar <hughaguila...@yahoo.com>
> > Can anybody tell me if CL (or PLT Scheme) has an associative
> > arrays implementation?
>
> CL has three different associative-array implementations built in:
> - Assoc lists
> - Property lists
> - Hashtables
To a large extent, I'm interested in learning CL because it offers
flexibility. Unlike Python in which there is *one* way to do anything,
CL offers plenty of choices.
Also, unlike in Forth, I won't have to write everything myself from
scratch --- I can do something useful, like write an application,
rather than getting bogged down in implementing things like LLRB trees
before I can even start on the application.
> > I want an implementation that supports doing an ordered traversal
>
> The first two of those listed above have a well-defined traversal order.
>
> > and which also supports filtering of regions. I want to be able
> > to copy everything within a region into another association, or
> > everything outside of a region into another association,
>
> Since we're talking about a linear object, by "region" do you
> really mean segment (from some starting element to some ending
> element, where each element is a key-value pair)?
Yes. When I say "region" that is what you're describing as a
"segment."
The code (association.4th) is actually pretty short and simple. If you
know any Forth at all, you could figure it out quickly. Even if you
don't know any Forth, the comments alongside of each function pretty
much tell the tale.
> > and also be able to merge two associations together.
>
> By "merge" do you mean "append" or "collate" or merge per some
> order-relation that each linear object satisfied before the merge?
>
> So-far it sounds like you want an assoc list. You can use the SORT
> function to rearrange it per some order-relation, and after two
> assoc lists have been sorted you can use the MERGE function to
> merge them per that same order-relation.
No, I don't want to sort by some order-relation (meaning to sort by
some data in the payload) --- I want the association to be *always*
sorted by the key. When two associations are merged together, they
necessarily result in a new association that is also sorted by the
key.
In my application, the key will be a floating point number. The
association will be just like an array, except that the indices don't
have to be integers.
> > The reason why I ask, is that I wrote such an associative arrays
> > implementation (using LLRB trees) in ANS-Forth. I want to have the
> > same capability in Lisp that I have in Forth. I can port my code from
> > Forth to Lisp (after I get better at Lisp), but I would be interested
> > in knowing if somebody else has already done something similar.
>
> Google search shows LLRB is a type of self-balacing binary search
> tree. Such have extra properties that you didn't list above,
> specifically that you can insert/delete/merge/split in log(n) time
> while sharing all structure (between original and modified tree)
> except the log(n) path from root to the point of change. You didn't
> say whether you *need* that feature, in which case assoc lists
> wouldn't satisfy your needs, or not, in which case assoc lists
> would be good enough. If you typically have less than a thousand
> items in each associative array, the speed difference is probably
> too small to care about.
In my slide-rule program, I was working with data sets containing over
15,000 items. In the application that I'm aiming for (a more general-
purpose CAM program), I would be generating gcode programs of a
comparable size.
I don't want to have to run a SORT function on the data structure
*every* time that I insert a new item --- I want it to maintain itself
sorted at all times.
> By the way, a few years ago I implemented my own SBBST, which
> balances on the basis of total number of nodes rather than maximum
> depth of each sub-tree, and allows you to find the nth element in
> log(n) time which some of the other SBBSTs don't allow.
I would be interested in seeing your code. I find binary trees to be
pretty fascinating. I get criticized for this a lot because
*everybody* knows that hash tables are better, but I just *like*
binary trees --- sue me!
You might be interested in my symtab package, which uses an algorithm
I invented myself. Once again, even if you don't know Forth, I
commented the heck out of it so you can hopefully still understand
what I'm doing. :-)
Hugh Aguilar
You mean a "white dwarf" --- brown dwarfs are like overgrown versions
of Jupiter that were too small to have ever become stars at all, so
they live uneventful lives in which they neither explode nor implode.
http://en.wikipedia.org/wiki/White_dwarf
http://en.wikipedia.org/wiki/Brown_dwarf
I'm only telling you this because I'm a grumpy old man who gets a
thrill out of shining a spotlight on other people's mistakes. :p
You're right though, that this problem is most pronounced in
comp.lang.forth because pretty much everybody is unemployed, and have
little or no chance of finding employment as a Forth programmer (I
work as a cab-driver myself). On that subject, I don't see a whole lot
of advertisements for Lisp programming jobs either. Lisp may be way
cool, but it has never become very popular "in the trenches" the way
that C++ or Java have, despite the myriad problems in C++ and Java
that the Lispers solved decades ago.
Java was originally designed for use on other people's computers. A
programmer might write a Java program, but it would then run in a
browser on some guy's computer, and that guy doesn't particularly
trust the programmer --- he wants a lot of security to prevent
malicious Java programmers from installing viruses on his computer, or
searching his hard-disk for passwords and/or credit-card numbers, and
so forth. For reasons obscure (to me), Java flopped as a browser
language, and we now use JavaScript instead. Instead of dying out
though, Java found a new home in the universities. Previously, Pascal
had been the language of education, but it didn't offer any security.
Students could crash the school's computer either through malicious
"hacking" or just because they tend to write buggy programs. Also,
students could write programs that searched through the hard-disk
looking for other students' completed homework assignments or
(jackpot!) the professor's upcoming exam. By switching from Pascal to
Java, the school was able to prevent all of this skullduggery. The
result is that a lot of people graduate from college and the only
language they know is Java, so they expect to find a job programming
in Java --- so Java becomes the mainstream language in the work world,
despite the fact that Java's security has little or no use in the work
world, because your software is running on your own computer anyway.
If the Lispers had thought of the making Lisp secure, and had sold the
idea of security to the universities, then Lisp would be the
mainstream language rather than Java. The schools care a lot more
about security from malicious students, then they care about teaching
those students high-falutin concepts such as meta-programming. Clojure
may yet pull Lisp's bacon out of the fire though, as Clojure has most
of the coolness of CL, and also has all of the security of Java ---
the best of both worlds.
Pascal J. Bourguignon
> On Nov 7, 3:14 am, p...@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> Hugh Aguilar <hughaguila...@yahoo.com> writes:
>> > You can't embed CL inside of a C program because CL is too big.
>>
>> What a brainfart!
>>
>> On my system, there are 65 libraries in /usr/lib that are bigger than
>> libecl! boost-regexp is bigger than libecl! (This is just a fucking
>> regexp library and it's bigger than a whole language including a
>> compiler, an interpreter, and a standard library). Or libxml2, which is
>> just a fucking serializer and deserializer for sexps!
>>
>> If CL is too big to include in a C program, then you should just stop
>> writing C program, because libc which is the standard library for C
>> programs, is twice the size of a CL implementation!
>
> Considering that I'm an admitted newbie to CL, I think you could have
> disagreed with me without all of the vulgarity.
If you're a newbie, then learn more before issuing categorical sentences
such as the above quoted. You'll avoid a lot of problems.
> A big part of why I'm getting away from comp.lang.forth is because of
> the vulgarity over there. I have been told that my code is "crap" and
> it "sucks" --- that my use of binary trees rather than hash tables is
> "stupid" and "incompetent" --- that I am "diseased" --- etc.. If I
> complain that this kind of language is inappropriate for a programming
> forum, Elizabeth Rather accuses me of being "homophobic and
> intolerant:"
> http://groups.google.com/group/comp.lang.forth/browse_thread/thread/c37b473ec4da66f1
>
> I'm expecting you Lispers to be a more classy crowd than the Forthers.
> Don't they have etiquette classes at MIT? :-)
Unfortunately not everybody has the chance (or ability) to pass thru the
MIT.
Scott L. Burson
>
> people grow nastier as they get older. go to alt.astronomy and marvel
> at a bunch of old men throwing shit at each other all day long and
> talking about anything but astronomy...
For some reason this reminds me of my high school Latin teacher, who
liked to tell of his professors at Oxford who would get drunk and
proceed to insult one another, not just in Latin, but in perfect
dactylic hexameter too.
-- Scott
Thomas A. Russ
> On 2010-11-08 20:31:00 +0000, Hugh Aguilar said:
>
> > I'm expecting you Lispers to be a more classy crowd than the Forthers.
>
> We're a pretty nasty lot, on the whole.
>
> > Don't they have etiquette classes at MIT? :-)
Not in general, although that might be a good idea for IAP.
> have you *met* anyone from MIT? They say some of them have had
> successful relationships, but I doubt it, myself.
I beg your pardon.
;-) ;-)
--
Thomas A. Russ, USC/Information Sciences Institute
TheFlyingDutchman
> though, Java found a new home in the universities. Previously, Pascal
> had been the language of education, but it didn't offer any security.
> Students could crash the school's computer either through malicious
> "hacking" or just because they tend to write buggy programs. Also,
> students could write programs that searched through the hard-disk
> looking for other students' completed homework assignments or
> (jackpot!) the professor's upcoming exam. By switching from Pascal to
> Java, the school was able to prevent all of this skullduggery.
I don't believe Java prevents you from searching through files on a
hard drive.
Mark Wooding
> I don't believe Java prevents you from searching through files on a
> hard drive.
If you fiddle with the security (sandboxing) interfaces enough I'm sure
it can prevent this sort of thing. More-or-less prevent, anyway: the
Java class library is stuffed with ambient authority and the security
stuff works by grobbling through the call stack to see who's asking to
do what, so I wouldn't be surprised if you there was some bit of code
somewhere you could confuse into doing what you wanted.
-- [mdw]
TheFlyingDutchman
Even if there was a way to "fiddle" with the Java compiler or class
library to prevent access to some directories, the System
Administrator can do it quite easily with the OS, which will prevent
access by Pascal programs as well as Java programs. I don't believe
that hard drive directory access was a factor in Java replacing Pascal
in college curriculums.
Mark Wooding
> Even if there was a way to "fiddle" with the Java compiler or class
> library to prevent access to some directories, the System
> Administrator can do it quite easily with the OS, which will prevent
> access by Pascal programs as well as Java programs.
I think we're at cross purposes. I (and I think whoever started this
subthread) was thinking about a teacher or an automated submission
system running a student-provided program. The system can use the Java
VM's sandboxy stuff to (try to) prevent the program from doing Bad
Things.
> I don't believe that hard drive directory access was a factor in Java
> replacing Pascal in college curriculums.
No, I don't buy that either. I think that the original claim also got
cause and effect the wrong way around with respect to uptake of Java in
academia and industry. Pascal is extremely long in the tooth and
generally awful (see Kernighan's famous rant, for example); Scheme
(distressingly) doesn't seem to have taken off as something to teach
fresh shiny new undergraduates very much outside MIT; and Java was being
used in industry so I suspect a number of universities latched onto it
in a misguided attempt to be seen to be `relevant'.
My own university education tried to teach me Pascal, C++, Miranda
(which I undervalued at the time) and Prolog.
-- [mdw]
Robert Maas, http://tinyurl.com/uh3t
> To a large extent, I'm interested in learning CL because it
> offers flexibility. Unlike Python in which there is *one* way to
> do anything, CL offers plenty of choices.
Then perhaps you'd be interested in my initiatives:
- Hierarchial&mixin intentional types and their specific implementations.
- No-syntax software development via a menu+keyword-driven IDE.
> Also, unlike in Forth, I won't have to write everything myself
> from scratch --- I can do something useful, like write an
> application, rather than getting bogged down in implementing
> things like LLRB trees before I can even start on the application.
You might also like PHP for similar reasons. Associative arrays are
a built-in part of the language. Using them, it's almost trivial to
implement a wide variety of intentional datatypes.
> Yes. When I say "region" that is what you're describing as a
> "segment."
Thanks for clarifying by confirming my guess.
> The code (association.4th) is actually pretty short and simple.
> If you know any Forth at all, you could figure it out quickly.
I don't believe that. All I know about forth is:
- Each word in sequence performs an immediate action on the stack,
except some words start special modes such as defining new words
or terminating such a definition.
- swap and dup.
- Literal numeric constants self-push on the stack.
- Arithmetic operators combine the top two items on the stack and
push the result in their place.
I know there are about a hundred words defined in Pocket Forth, the
only version of Forth available to me here, but I don't remember
any of them specifically, except as listed above. I don't even know
how to define a function.
I wish I knew somebody who could tell me how to use MacPPP from Forth.
> No, I don't want to sort by some order-relation (meaning to sort
> by some data in the payload) --- I want the association to be
> *always* sorted by the key.
So you want the order-relation (i.e. the sorting predicate) to be
implicit in the datatype, like what Java terms the "natural" order?
There are actually two ways to do it:
- Have a generic container, but the keys are in a class that has
the order relation. All the keys in any given container must be
in the same class, or the container can't auto-sort.
- Have an order-relation specific to each class of container, thus
the same exact keys in two different classes of container would
auto-sort differently.
> When two associations are merged together, they necessarily
> result in a new association that is also sorted by the key.
Only if the order-relations for the two classes (of keys, or of
containers) are the same, i.e. the keys are of the same class (with
its natural ordering), or the containers are of the same class
(ditto). If you try to merge two generic containers that happen to
contain keys from different classes, or if you try to merge two
order-specific containers from different-ordered classes, it isn't
going to work.
> In my application, the key will be a floating point number.
Why? Floating-point numbers are supposed to be mere approximations,
shots-in-dark, not exact values that have well-defined order. If
you compute exactly the same mathematical value using two different
values, roundoff error could resut in different floats, thus the
same mathematical value would be less than itsef. Contrarywise,
with fixed-precision floats, there are only a finite number of
different floats, hence with an infinite number of possible
mathematical values at least two different values will float the
same.
> The association will be just like an array, except that the
> indices don't have to be integers.
"White man speak with forked tongue."
What you said there is meaningless.
"Just like an array" implies:
- Whenever you insert a new element, or delete an old element, all
entries after that point must be *moved* forward or backward to
make room for the new element or fill the gap from the old
element respectively.
- Indexes of an array are a contiguous segment of number space.
Whenever you insert/delete you must change the keys of each of
the elements that were moved to get out of the way of the new
element or fill the void from the old element.
From what else you write, I'm quite sure you do *not* want that behaviour.
If you said "just like a sparse array", that would make more sense.
Sparse arrays are typically implemented as self-balancing search
trees, either binary (with the usual need to modify a log(n) path
each time an element is inserted or deleted), or ternary+ (with the
need to skip void spots when traversing, and when you over-fill a
node you just need to split into two not-full nodes under a third
node, never a log(n) re-organization needed).
> In my slide-rule program, I was working with data sets containing
> over 15,000 items.
If you have that many items in a single sorted-container, and you
want insert/delete/merge/copySegment to be efficient, then you need
some kind of self-balancing search-tree, rather than any of the
container types built into Common Lisp.
> I don't want to have to run a SORT function on the data structure
> *every* time that I insert a new item --- I want it to maintain
> itself sorted at all times.
Hence: Self-balancing search tree.
> > By the way, a few years ago I implemented my own SBBST, which
> > balances on the basis of total number of nodes rather than maximum
> > depth of each sub-tree, and allows you to find the nth element in
> > log(n) time which some of the other SBBSTs don't allow.
> I would be interested in seeing your code.
I haven't been paid for my work. I don't have the money to file a
patent on it. The only way I would show the code to anyone is if
he/she meets me in person and signs a non-disclosure agreement. But
if you think of what I already said, that it's a self-balancing
binary-search-tree, based on balancing the number of nodes in each
sub-tree rather than the depth of each sub-tree, there are only a
few additional design decisions needed before the code will be
obvious to any competant software designer. The interesting case is
when one sub-tree is completely empty, under what condition do you
rebalance and otherwise leave as-is slightly unbalanced.
> I find binary trees to be pretty fascinating. I get criticized
> for this a lot because *everybody* knows that hash tables are
> better, but I just *like* binary trees --- sue me!
Hash tables aren't better at all!!!!! Hash tables are *different*.
They do *not* in any way guarantee fast per-insert time. If they
are mis-designed, they might not even guarantee fast amortized
insertion time. And in particular they don't in any way provide a
built-in order relation that can be maintained efficiently, nor a
way to extract segments efficiently.
This question just occurred to me: How long does it take to merge
two self-balancing binary-search-trees (assuming they use the same
order relation)? Is it o(N) where N is the total number of
elements? Or is it o(N * log(N))?
> You might be interested in my symtab package, which uses an
> algorithm I invented myself.
Just curious: Does it rebalance when the sub-tree node-counts are
too lopsided, or when the sub-tree longest-paths are too lopsided?
Hugh Aguilar
http://tinyurl.com/uh3t) wrote:
> > From: Hugh Aguilar <hughaguila...@yahoo.com>
> > To a large extent, I'm interested in learning CL because it
> > offers flexibility. Unlike Python in which there is *one* way to
> > do anything, CL offers plenty of choices.
>
> Then perhaps you'd be interested in my initiatives:
> - Hierarchial&mixin intentional types and their specific implementations.
> - No-syntax software development via a menu+keyword-driven IDE.
If you provide some links to papers on these, I would read them.
The phrase "no-syntax software development" reminds me of Chuck
Moore's latest effort: ColorForth. Control structures are denoted by
colors rather than by words (WHILE, IF, etc.). I haven't tried it. A
lot of Chuck Moore's latter work is too far out and funky for me. :-)
> > Also, unlike in Forth, I won't have to write everything myself
> > from scratch --- I can do something useful, like write an
> > application, rather than getting bogged down in implementing
> > things like LLRB trees before I can even start on the application.
>
> You might also like PHP for similar reasons. Associative arrays are
> a built-in part of the language. Using them, it's almost trivial to
> implement a wide variety of intentional datatypes.
Well, I used AWK a long time ago and liked it, and AWK has associative
arrays.
There is somewhat of a balance between fat and thin that has to be
achieved. Some languages, such as Forth are too thin, as they don't
provide *any* built-in structures. On the other hand, PHP has a
reputation for being too fat, in the sense that there it provides
everything but the kitchen-sink, but instead of increasing flexibility
it all becomes a Procrustean Bed for the user, and it is also time-
consuming to learn --- I don't know if this reputation is fair or not
though, as I've never tried PHP.
It takes a lot of time and effort to learn a language (especially for
me, as I'm not a quick study), so right now I'm aiming for CL and
ignoring PHP, Ruby, Python, and the myriad other valid choices
available.
> > Yes. When I say "region" that is what you're describing as a
> > "segment."
>
> Thanks for clarifying by confirming my guess.
I almost never do any research, but generally just figure everything
out myself. The result is that I typically don't use the standard
terminology --- that is at least *one* of the reasons why I often
sound like I don't know what I'm talking about.
> > No, I don't want to sort by some order-relation (meaning to sort
> > by some data in the payload) --- I want the association to be
> > *always* sorted by the key.
>
> So you want the order-relation (i.e. the sorting predicate) to be
> implicit in the datatype, like what Java terms the "natural" order?
>
> There are actually two ways to do it:
> - Have a generic container, but the keys are in a class that has
> the order relation. All the keys in any given container must be
> in the same class, or the container can't auto-sort.
> - Have an order-relation specific to each class of container, thus
> the same exact keys in two different classes of container would
> auto-sort differently.
>
> > When two associations are merged together, they necessarily
> > result in a new association that is also sorted by the key.
>
> Only if the order-relations for the two classes (of keys, or of
> containers) are the same, i.e. the keys are of the same class (with
> its natural ordering), or the containers are of the same class
> (ditto). If you try to merge two generic containers that happen to
> contain keys from different classes, or if you try to merge two
> order-specific containers from different-ordered classes, it isn't
> going to work.
Well, in my associations I require that *every* node have the same
data-type for its key (although the payload can differ from one node
to another). I also require the programmer to write a comparer
function for this data type and provide the xt (execution token) for
that comparer function at the time that the association is defined. If
the key is an ascii string, then COMPARE can be used. I also provide
FLOAT-COMPARE that can be used when the key is a float.
Dynamic-OOP languages such as Lua can allow the key to be any data-
type whatsoever, and they figure out how to compare the various data-
types at run-time. Forth isn't a dynamic-OOP language though, so the
programmer has to provide the comparer function at compile-time, and
the keys all have to be of that data-type.
> > In my application, the key will be a floating point number.
>
> Why? Floating-point numbers are supposed to be mere approximations,
> shots-in-dark, not exact values that have well-defined order. If
> you compute exactly the same mathematical value using two different
> values, roundoff error could resut in different floats, thus the
> same mathematical value would be less than itsef. Contrarywise,
> with fixed-precision floats, there are only a finite number of
> different floats, hence with an infinite number of possible
> mathematical values at least two different values will float the
> same.
Well, in Forth we have F~ that does an approximate equality test for
floats. This can be used to smooth out tiny round-off differences such
as you are describing.
Also, in my novice package I have a RATIO data-type that stores
numbers as an integer numerator and denominator. This doesn't work
very well because ANS-Forth fails to provide a double-precision
integer division, and so I have to have a single-precision denominator
and double-precision numerator, which doesn't provide as much
precision as needed to compete with floating-point. Still though, it
does work well for repeating decimals such as 1/3 (and repeating
binaries such as 1/5).
> > In my slide-rule program, I was working with data sets containing
> > over 15,000 items.
>
> If you have that many items in a single sorted-container, and you
> want insert/delete/merge/copySegment to be efficient, then you need
> some kind of self-balancing search-tree, rather than any of the
> container types built into Common Lisp.
Well, that is why I wrote association.4th! In the program I used
linked-lists only because I didn't have association.4th written at
that time. If I were to rewrite the program in Forth today, I would
use the LLRB trees for the MARK data rather than the linked lists, and
likely get a nice boost in speed.
When I port the program into CL I will use a self-balancing search-
tree as part of the upgrade.
> > > By the way, a few years ago I implemented my own SBBST, which
> > > balances on the basis of total number of nodes rather than maximum
> > > depth of each sub-tree, and allows you to find the nth element in
> > > log(n) time which some of the other SBBSTs don't allow.
> > I would be interested in seeing your code.
>
> I haven't been paid for my work. I don't have the money to file a
> patent on it. The only way I would show the code to anyone is if
> he/she meets me in person and signs a non-disclosure agreement. But
> if you think of what I already said, that it's a self-balancing
> binary-search-tree, based on balancing the number of nodes in each
> sub-tree rather than the depth of each sub-tree, there are only a
> few additional design decisions needed before the code will be
> obvious to any competant software designer. The interesting case is
> when one sub-tree is completely empty, under what condition do you
> rebalance and otherwise leave as-is slightly unbalanced.
I don't think there is any money to be made from writing low-level
code such as associative arrays --- you might as well just put the
code in the public domain and bask in the glory.
My entire novice package is BSD-license. I haven't basked in any glory
yet though --- the only result has been that trolls call me "dumbass"
now --- it makes me long for the peace and quiet of obscurity that I
enjoyed before I wrote my novice package.
> > I find binary trees to be pretty fascinating. I get criticized
> > for this a lot because *everybody* knows that hash tables are
> > better, but I just *like* binary trees --- sue me!
>
> Hash tables aren't better at all!!!!! Hash tables are *different*.
> They do *not* in any way guarantee fast per-insert time. If they
> are mis-designed, they might not even guarantee fast amortized
> insertion time. And in particular they don't in any way provide a
> built-in order relation that can be maintained efficiently, nor a
> way to extract segments efficiently.
Congratulations! This is the first intelligent commentary on binary-
trees versus hash-tables that I've seen this year (which is pretty
disturbing, considering that this is November!).
This is what Bernd Paysan said: "Wow, what amount of effort you put in
that. John, it's not worth the time. Hugh will dismiss it, because
analysis contains the word "anal", and he's not responsive to critics,
anyways. Other people like me have already done that analysis (tree
vs. hash) 20 years ago, and the result hasn't changed - a proper
implemented hash wins hands down. "
Apparently, everything to be known about associative arrays was known
20 years ago! We might as well shut down the patent office, as there
isn't anything remaining to be invented! LOL
> This question just occurred to me: How long does it take to merge
> two self-balancing binary-search-trees (assuming they use the same
> order relation)? Is it o(N) where N is the total number of
> elements? Or is it o(N * log(N))?
It is N*lg(N).
> > You might be interested in my symtab package, which uses an
> > algorithm I invented myself.
>
> Just curious: Does it rebalance when the sub-tree node-counts are
> too lopsided, or when the sub-tree longest-paths are too lopsided?
It doesn't balance the tree at all. Each node has a .COUNT field that
keeps track of how many times the node is accessed. The more-
frequently accessed nodes are moved above the less-frequently accessed
nodes.
I also have some enhancements over this basic idea. For one thing, I
provide the option of inserting nodes at the root rather than at the
leaves, which is theoretically incorrect because the new nodes have
a .COUNT of 1 and belong at the leaves. They sink down to their
appropriate place fairly quickly though. The idea is that newly
defined functions are often used immediately, and possibly are not
used again at all, so they enjoy fast access for a little while. I
also now balance "stringers" that are at the leaves and which have
low .COUNT values, which helps a lot in keeping the tree at least
somewhat balanced (there are a lot of low-.COUNT nodes at the leaves).
I also have an OPTIMIZE function that restructures the entire tree.
My claim to have invented this algorithm is somewhat dubious, as the
basic idea is pretty obvious. All in all though, it is pretty nice,
and I have never seen anything like this in any algorithm book. It is
a lot different from the Splay Tree that assumes recently accessed
nodes will be used again soon, which I don't assume.
Robert Maas, http://tinyurl.com/uh3t
> > > offers flexibility. Unlike Python in which there is *one* way to
> > > do anything, CL offers plenty of choices.
> > Then perhaps you'd be interested in my initiatives:
> > - Hierarchial&mixin intentional types and their specific implementations.
> > - No-syntax software development via a menu+keyword-driven IDE.
> From: Hugh Aguilar <hughaguila...@yahoo.com>
> If you provide some links to papers on these, I would read them.
I don't have a printer, so I can't put any of this on paper.
I've posted several newsgroup articles that introduce various
aspects of my initiatives, which can be found via search engine,
but nobody has expressed any interest in working with me to develop
the ideas, so I have them in my queue for just doing on my own
without any help from anyone and without writing them up more
coherently prior to implementation. My current plan is to include
the IDE as part of http://TinyURL.Com/NewEco, whereby the first
partial implementation will be used to bootstrap the rest of the
implementation. But until I get lots of users of NewEco, I can't
proceed.
I tried to use the Google Groups search engine just now to find
some of those articles I posted with the phrase "no-syntax
programming", but it's completely broken, finds several places
where people copied my text but doesn't find even one of the
original articles I posted. Here are some excerpts from the copied
text:
From the thread "Cons cell archaic!?":
| I've recenty proposed a no-syntax programming environment where you
| browse a library of functions available and select from a menu what
| you want and never need to even *see* the actual name of the
| function you're calling from your new "code".
| A computer language isn't necessary to define algorithms in a computer.
| See flowcharting that has been around since the early 1960's, and
| think of implementing it using a GUI. Or see Dijkstra's D-charts
| which could likewise be drawn in a GUI. Or see my proposal for a
| no-syntax programming system, using intentional datatypes of
| previously generated data objects to direct menus of available
| operations upon those objects, whereby the D-chart gets drawn
| automatically any time you want to see it as a visual aid.
From the thread "The future programming language (does it already exist ? ;))":
| Why do you insist on the need for a *language* in the first place?
| All you need to make a computer program (an organized bunch of
| computer software) is some tool for making computer programs.
| You do *not* need a programming language!!!
| Have you seen my proposal for a no-syntax (i.e. no language)
| way to build software?
| groups.google.com/group/alt.sys.pdp10/msg/0ee4054bf9ddcb6f
| groups.google.com/group/comp.lang.lisp/msg/55fbe9bd7fa29a8d
| Would you volunteer to help me flesh out my idea and maybe actually
| get something working?
From the thread "Whats your favorite language and why?":
| Why do you feel the need to learn a *language*? Why not learn how
| to design algorithms independent of any *language*? Have you seen
| my proposal for a no-syntax software-development system? Perhaps
| you would like to work with me to create such a system?
| If you really really *must* learn a *language* rather than just
| learn how to design algorithms in a no-syntax manner, then I
| suggest you learn Common Lisp.
Using a different search string "syntax-free" I found:
http://groups.google.com/group/comp.lang.lisp/msg/4d5ead2ea71ffa6a
| How about a syntax-free development and archival system, which
| automatically lists which known programming languages support any
| given module and offers a menu for converting the syntax-free
| software to whichever of the known programming languages the user
| wishes to express it in (port it to)? I've proposed this idea
| several times recently, but nobody else has expressed any serious
| interest.
| > I don't see that happening in my lifetime (and I expect to live
| > another 30-40 years).
| If you like my syntax-free idea, would volunteer to offer me
| emotional support for my idea and also brainstorm with me to work
| out the details of the design and also perform beta tests on any
| code I write to implement the idea per our agreed-upon design?
So if you become the first person to show serious interest in the
basic idea of:
- Building software by unit testing from input forward to output,
using menus to build starting data (either data per se, or
filenames for existing datasets), then using menus to select an
operation to perform on some data you already have.
- Categorizing each item of test data per a hierarchy of
intentional datatypes, and (the IDE) using that information to
decide which methods to include at the top of the menu to show
user.
then we can discuss the topic further, and in the course of our
discussion my answers to your specific questions can serve as a
guide towards writing a formal proposal.
Meanwhile, two generations (of my thoughts/plans) earlier I started
a database ("cookbook") of how to do the same task in multiple
languages (sometimes just calling a single function or method, but
in other languages requiring several lines of user code), organized
according to a hierarchy implemetational datatypes. (This was
before I realized that intentional datatypes were more important
for such classification.) Here's what I had before I switched
gears:
http://www.rawbw.com/~rem/HelloPlus/hellos.html
-> http://www.rawbw.com/~rem/HelloPlus/hellos.html#step4
-> http://www.rawbw.com/~rem/HelloPlus/CookBook/CookTop.html
Then when I realized that such a "cookbook" really should be
organized per intentional rather than implementational datatypes, I
decided to re-organize the "cookbook" in that way, but before I
could find time for that I realized that no-syntax IDE is even
better. Instead of having a Web page where you must *read*
descriptions of how to do things in various languages, and where
you must manually browse the datatypes hierarchy to find the
functions that deal with your data, and where you must **choose**
one of the various languages and stick with it in order to have the
different parts of your program able to compile/build together,
better to have the IDE automatically find the appropriate section
of the "cookbook" for your data-at-hand, and better that you have
the IDE do your data-processing directly rather than tell you how
to program it in some "language", and then when you have a
completed function or library or fullfledged application the IDE
can tell you which of the known programming languages support all
the tasks you have invoked from your function(s)/application, and
you choose one and it *writes* your function/library/application
for you.
> The phrase "no-syntax software development" reminds me of Chuck
> Moore's latest effort: ColorForth. Control structures are denoted
> by colors rather than by words (WHILE, IF, etc.).
How does the user build individual "lines of code" to perform
single data/stack transformations/calculations? Does the user have
to key in (or copy+paste) actual FORTH "words"? Or is all the FORTH
language invisible to the user, where the user *describes* what
he/she wants to happen and the IDE suggests various more precise
descriptions that are directly available from the FORTH
word-library?
> There is somewhat of a balance between fat and thin that has to
> be achieved.
There's a quote floating around, something like the choice between
a system so simple it always works or so complex you can't tell
that it's not really working so you give it a pass anyway. I
believe it's possible to provide rich abilities while maintaining
simplicity by defining a few *very* generally-useful primitives.
PHP seems to do that, with these datatypes:
- Strings
- A few types of numbers
- Associative arrays
- Streams/continuations
-- Functions
-- Some OO libraries
That's about it!!
SQL queries are implemented as strings.
SQL result sets are implemented as streams that deliver associative arrays.
XML DOM parser is implemented as an OO library.
> Some languages, such as Forth are too thin, as they don't provide
> *any* built-in structures.
Forth doesn't even provide a user-friendly way to nest expressions.
Compare these:
C: (a + b) / (a - b)
Lisp: (/ (+ a b) (- a b))
Forth: a b + a b - /
(And if you use DUP and SWAP to avoid needing to repeat the names
'a' and 'b', Forth gets even uglier!!)
> On the other hand, PHP has a reputation for being too fat, in the
> sense that there it provides everything but the kitchen-sink, but
> instead of increasing flexibility it all becomes a Procrustean
> Bed for the user, and it is also time- consuming to learn
I disagree. I taught myself everything I need to write PHP
applications, mostly by doing Google search for [PHP tutorial] once
at the start to get a general idea, then doing more specific Google
searches such as [PHP tutorial string length] to look for functions
I need at any moment. Once I got used to the trick of alternating
between PHP syntax and verbatim HTML pass-through, coding PHP Web
applications became almost a breeze. Now maybe because I don't know
*all* that PHP provides, I sometimes write my own version of
something that already exists, "re-inventing the wheel", but if it
takes me a half hour to fully implement an algorithm myself, but
would take more than a half hour to *find* it already done and
figure out how to adapt what's already done to my specific use, why
not do it myself?
> I don't know if this reputation is fair or not though, as I've
> never tried PHP.
Not even a PHP WebServer "hello world" test? Try these in succession:
http://www.rawbw.com/~rem/HelloPlus/hellos.html#php0
http://www.rawbw.com/~rem/HelloPlus/hellos.html#php1
http://www.rawbw.com/~rem/HelloPlus/hellos.html#php2
http://www.rawbw.com/~rem/HelloPlus/hellos.html#php3
> It takes a lot of time and effort to learn a language (especially
> for me, as I'm not a quick study),
How do you like my CGI Hello World tutorial, that starts with the
absolutely most primitive demo for Web server then builds up in 3
successive "baby steps" to reach full form-contents decoding (which
is done automatically by PHP, but which takes some programming with
the other languages)?
> so right now I'm aiming for CL
Have you built and installed your first CGI/CL application so that
I can run it from here to see how it works?
> and ignoring PHP, Ruby, Python, and the myriad other valid
> choices available.
I accept your choice to work with one new language at a time, and
Common Lisp is a reasonable choice if you want to write useful
applications for STDIO or WebServer.
> > > Yes. When I say "region" that is what you're describing as a
> > > "segment."
> > Thanks for clarifying by confirming my guess.
> I almost never do any research, but generally just figure everything
> out myself. The result is that I typically don't use the standard
> terminology --- that is at least *one* of the reasons why I often
> sound like I don't know what I'm talking about.
By "research", which you say you don't usually do, do you mean
"library research", i.e. trying to find what is already done by
others and documented in public records, rather than "original
research", i.e. trying to invent something new yourself? I.e. you
prefer to do original research rather than library research?
In college I majored in mathematics, and learned that "research"
means "original research", i.e. problem solving, compared to high
school where English classes had me going to the public library to
do "research" which really meant finding sources of already-done
information. Funny how math and English folks define "research"
totally differently.
> Well, in my associations I require that *every* node have the
> same data-type for its key
Every node in *all* applications of your software, or every node in
any particular application but different key-data-type in different
applications? This makes a difference in how robust your utility
must be.
> I also require the programmer to write a comparer function for
> this data type
I take this to mean that the *application* programmer, the person
who uses your utility, must decide which datatype and comparator
will be used in each such application, but the same programer can
create different applications that use different datatypes and
different comparators, providing that person doesn't mix up his
applications.
> and provide the xt (execution token) for that comparer function
> at the time that the association is defined.
What is "execution token"? Is it a FORTH word that when later
invoked will take the top two items from the stack and compares
them and replaces them with TRUE/FALSE or LESS/EQUAL/GREATER
result? If so, which is it, two-way (less or not less), or
three-way (less or equal or greater)?
> If the key is an ascii string, then COMPARE can be used. I also
> provide FLOAT-COMPARE that can be used when the key is a float.
I've never used either word in my limited Pocket Forth experience.
In fact I don't think I've ever even used strings as datatypes.
I've used only two different lengths of integers, one of which
occupies one stack location and other of which occupies two
consecutive stack locations treated together in SWAP2 and
arithmetic operations. I think strings in Pocket Forth are
implemented as one character per stack location with some
end-of-string marker also on the stack, but I'm not sure. I seem to
recall a FORTH word that reads a line of input from the interaction
window, putting all the characters consecutively on the stack with
a marker at the deep end, but again I'm not sure.
> ... in Forth we have F~ that does an approximate equality test for
> floats. This can be used to smooth out tiny round-off differences such
> as you are describing.
That's horrible to use in a self-balancing search tree, because
equality per that predicate isn't transitive, that is A can equal
B, and B can equal C, but A not equal to C. That totally breaks the
concept of self-balancing search tree where equal keys are
clustered into a single node and anything not equal to all those
keys are either before it or after it. If a node already has two
keys approximately equal, and you try to add a third key that is
equal to one of the old equal keys but not equal to the other equal
key in the same node, does it add to the same node or create a new
node? Or if you can keep only one instance of equal keys per node,
is it random which of the first two keys is in the node when the
third key arrives, thus random whether the third key is considered
equal or not equal to the key of the existing node?
> Also, in my novice package I have a RATIO data-type that stores
> numbers as an integer numerator and denominator. This doesn't work
> very well because ANS-Forth fails to provide a double-precision
> integer division, and so I have to have a single-precision
> denominator and double-precision numerator, which doesn't provide
> as much precision as needed to compete with floating-point.
Can't you implement unlimited-size integers, and ratios of them?
> I don't think there is any money to be made from writing
> low-level code such as associative arrays --- you might as well
> just put the code in the public domain and bask in the glory.
I've been living in poverty for years because I've been unable to
find anyone to pay me for my work. Must I now *give*away* all my
unpaid work so that I will *never* have a chance to get paid for
any of my years of work?
> > > I find binary trees to be pretty fascinating. I get criticized
> > > for this a lot because *everybody* knows that hash tables are
> > > better, but I just *like* binary trees --- sue me!
> > Hash tables aren't better at all!!!!! Hash tables are *different*.
> > They do *not* in any way guarantee fast per-insert time. If they
> > are mis-designed, they might not even guarantee fast amortized
> > insertion time. And in particular they don't in any way provide a
> > built-in order relation that can be maintained efficiently, nor a
> > way to extract segments efficiently.
> Congratulations! This is the first intelligent commentary on binary-
> trees versus hash-tables that I've seen this year (which is pretty
> disturbing, considering that this is November!).
I accept your compliment.
> > > You might be interested in my symtab package, which uses an
> > > algorithm I invented myself.
> > Just curious: Does it rebalance when the sub-tree node-counts are
> > too lopsided, or when the sub-tree longest-paths are too lopsided?
> It doesn't balance the tree at all. Each node has a .COUNT field that
> keeps track of how many times the node is accessed. The more-
> frequently accessed nodes are moved above the less-frequently accessed
> nodes.
Is the count an unbounded integer, or does the count have an upper
bound after which point it stops increasing, or do all the counts
get decayed from time to time to protect against any one exceeding
the maximum possible value? If counts are periodically decayed,
then behaviour is somewhat like demand paging, where the most
recent working set has more influence on speed than data used
earlier.
> My claim to have invented this algorithm is somewhat dubious,
I've heard of a different algorithm where *every* time a node is
used it is miagrated just one step higher in the tree (unless it is
already at the root), thus miagrating recently-used nodes towards
the top, and avoiding the need for any total-access count. An
extreme version of this algorithm checks the top old node when
inserting new node:
- If old node has two sub-trees, new node is inserted above it,
with one branch null.
- If old node has only one sub-tree, new node replaces the null
branch or swaps with old top node depending on order relation.
An alternate version inserts new nodes between the adjacent old
nodes, at whatever level of tree, adding or removing null sub-tree
similar to the extreme version but *there* instead of at the very
top. With either version, when new access to old node occurs, a
local pivot moves that node higher unless it is already at the top.
Since most self-balancing or self-optimizing search trees (binary
or not) have roughly log(n) behaviour per access, the minor
differences between styles of balancing (per path length or
sub-tree count) or up-miagration (per recent or total usage) might
not really be worth fussing over. Pick any random algorithm you
like, make sure it really works in all cases, then put your main
effort elsewhere.
> It is a lot different from the Splay Tree that assumes recently
> accessed nodes will be used again soon, which I don't assume.
Lots of software applications have context shifts, where you work
on one set of data for a while, then work on another set of data
for a while, etc. Demand paging works good for this, and
recent-access search trees likewise. At worst, if you are accessing
*all* the data totally randomly, recent-access search trees won't
be any worse than log(n) on average, so you lose nothing. But if
you *are* switching contexts, recent-access search trees should
give you a modest speed-up. But like I said just earlier, the
differences between various balancing/optimizing algorithms might
be trivial compared to the important choice to use a tree in the
first place.
Hugh Aguilar
http://tinyurl.com/uh3t) wrote:
> > From: Hugh Aguilar <hughaguila...@yahoo.com>
> > If you provide some links to papers on these, I would read them.
>
> I don't have a printer, so I can't put any of this on paper.
Actually, I meant "paper" in the sense of "document" --- I was hoping
that you might have a website where you describe your work.
> Then when I realized that such a "cookbook" really should be
> organized per intentional rather than implementational datatypes, I
> decided to re-organize the "cookbook" in that way, but before I
> could find time for that I realized that no-syntax IDE is even
> better.
There have been a lot of efforts to write software-generating software
that can be used by non-programmers, but none of this has come to
fruition --- good-old programming is still required, and likely always
will be. Because of this, I can't say that I'm very much interested in
the idea. I would read any document that you've written, but I can't
promise that I will be inspired to get involved.
The only success story that I know of, is the software that is used
for programming PLCs (Programmable Logic Controllers). The user can
point-and-click and can generate the "ladder diagrams" that represent
a purely logical "program." This is widely used for motion-control
programs that do a lot of flipping of relay-switches to make some
factory-machine do whatever it does, and it works pretty well --- or
so I've heard --- I don't have any experience in this myself.
> > The phrase "no-syntax software development" reminds me of Chuck
> > Moore's latest effort: ColorForth. Control structures are denoted
> > by colors rather than by words (WHILE, IF, etc.).
>
> How does the user build individual "lines of code" to perform
> single data/stack transformations/calculations?
I have never used ColorForth, so I ought not to speculate on how it
works. I think the programmer just types in the code blocks, but is
only saved from typing in the control-flow code, but I don't really
know. You will just have to get a copy and experiment with it. Chuck
Moore and friends are as enthusiastic about ColorForth as you are
about your ideas, so I'm sure you will find plenty of people who can
answer your questions. :-)
> Forth doesn't even provide a user-friendly way to nest expressions.
> Compare these:
> C: (a + b) / (a - b)
> Lisp: (/ (+ a b) (- a b))
> Forth: a b + a b - /
> (And if you use DUP and SWAP to avoid needing to repeat the names
> 'a' and 'b', Forth gets even uglier!!)
You really should learn more about Forth before you call it ugly.
Forth can be much cleaner than C! Look in my novice package (in the
toy.4th file) for some code that calculates parallel resistance. This
is a very novice-level introduction to the parameter stack, and it is
also an excellent example of how Forth can make C look ugly and
cumbersome by comparison.
> > so right now I'm aiming for CL
>
> Have you built and installed your first CGI/CL application so that
> I can run it from here to see how it works?
Actually, I have no intention of using CL for web applications (I just
want to use CL for scripting). I am not much interested in web stuff,
but if I ever did get interested, I would most likely use a web-
specific language such as PHP. I looked into Turbo Gears (based on
Python), and that looked pretty cool too. I don't know enough about
the subject to know if Python is better than PHP, or Ruby on Rails is
best (as many claim), or whatever.
I'm really turned off by the internet right now, because it seems to
promote the worst in humanity --- the internet has become the Kingdom
of Trolls. :-( Somebody would have to convince me that the internet
has some kind of positive influence on humanity, before I would want
to start writing web software. Until that time I would consider the
internet to be similar to a nest of vipers --- the best solution is a
can of fuel-oil and a match!
> > Well, in my associations I require that *every* node have the
> > same data-type for its key
>
> Every node in *all* applications of your software, or every node in
> any particular application but different key-data-type in different
> applications? This makes a difference in how robust your utility
> must be.
The programmer can have as many different associations in his
application as he wants. In each association however, every node must
have the same data-type for its key. You can't merge associations
together if they have different data-types for their key.
> > and provide the xt (execution token) for that comparer function
> > at the time that the association is defined.
>
> What is "execution token"?
It is what you Lispers call a lambda function. Essentially, it is a
pointer to a function that can be passed around as data --- the
function can ultimately be executed with EXECUTE. The xt may be of a
named function, or it may be of an unnamed function --- EXECUTE works
either way.
Look in my novice package and see how functions such as EACH (in list.
4th) take an xt and execute that function for every node in a list.
That is a pretty typical use of xt values. It is a kind of factoring.
> > ... in Forth we have F~ that does an approximate equality test for
> > floats. This can be used to smooth out tiny round-off differences such
> > as you are describing.
>
> That's horrible to use in a self-balancing search tree, because
> equality per that predicate isn't transitive, that is A can equal
> B, and B can equal C, but A not equal to C. That totally breaks the
> concept of self-balancing search tree where equal keys are
> clustered into a single node and anything not equal to all those
> keys are either before it or after it.
You are right --- I hadn't considered that problem at all.
So what is the solution?
> > Also, in my novice package I have a RATIO data-type that stores
> > numbers as an integer numerator and denominator. This doesn't work
> > very well because ANS-Forth fails to provide a double-precision
> > integer division, and so I have to have a single-precision
> > denominator and double-precision numerator, which doesn't provide
> > as much precision as needed to compete with floating-point.
>
> Can't you implement unlimited-size integers, and ratios of them?
I don't know of any Forth implementation of unlimited-size integers.
Forth is very efficiency-focused --- it is primarily used in micro-
controllers. Unlimited-size integers aren't the kind of thing that
would normally be implemented in Forth --- that is Python-type of
software!
> > > > You might be interested in my symtab package, which uses an
> > > > algorithm I invented myself.
> > > Just curious: Does it rebalance when the sub-tree node-counts are
> > > too lopsided, or when the sub-tree longest-paths are too lopsided?
> > It doesn't balance the tree at all. Each node has a .COUNT field that
> > keeps track of how many times the node is accessed. The more-
> > frequently accessed nodes are moved above the less-frequently accessed
> > nodes.
>
> Is the count an unbounded integer, or does the count have an upper
> bound after which point it stops increasing, or do all the counts
> get decayed from time to time to protect against any one exceeding
> the maximum possible value? If counts are periodically decayed,
> then behaviour is somewhat like demand paging, where the most
> recent working set has more influence on speed than data used
> earlier.
They decay (get halved) when any of them get close to the upper bound
of integers. As a practical matter, this doesn't matter when you have
a 32-bit field, because it happens so rarely. Even with a 16-bit field
it is not going to be a big deal --- this is a symbol table after all!
> I've heard of a different algorithm where *every* time a node is
> used it is miagrated just one step higher in the tree (unless it is
> already at the root), thus miagrating recently-used nodes towards
> the top, and avoiding the need for any total-access count.
That is the Splay Tree that I mentioned.
> > It is a lot different from the Splay Tree that assumes recently
> > accessed nodes will be used again soon, which I don't assume.
>
> Lots of software applications have context shifts, where you work
> on one set of data for a while, then work on another set of data
> for a while, etc. Demand paging works good for this, and
> recent-access search trees likewise. At worst, if you are accessing
> *all* the data totally randomly, recent-access search trees won't
> be any worse than log(n) on average, so you lose nothing. But if
> you *are* switching contexts, recent-access search trees should
> give you a modest speed-up. But like I said just earlier, the
> differences between various balancing/optimizing algorithms might
> be trivial compared to the important choice to use a tree in the
> first place.
Well, that pretty much sums up the criticism of symtab that I already
suffered through on comp.lang.forth!
The way I see it, the words' likelihood of appearing is pretty long
term. The only exception is that a word is more likely to be used
immediately after it is defined, than later on (when it may not be
used at all anymore). I don't really expect much difference in
"contexts" except at a fairly high-level (some programs use a lot of
floating-point functions, some use a lot of string functions, etc.).
I won't really know if my symtab is better than whatever algorithm
until I have implemented both in a compiler and tried each of them out
on a test suite of "typical" source files. Until this is done, and
there is some actual data available, I'm not going to worry about all
of this speculation as to what is better than what else. Most of the
criticism comes from trolls who have never implemented any code of
their own, and just get a kick out of telling me that my code "sucks."
ron
> The way I see it, the words' likelihood of appearing is pretty long
> term. The only exception is that a word is more likely to be used
> immediately after it is defined
This is why you will never be a professional programmer, Hugh. By
your own admission you "never research". By your demonstrated actions
here, you never test alternative hypotheses or test your own. You
program by "assertion".
You have been told countless times, and it has been *demonstrated*,
that there are better structures for symbol tables than the one you
came up with. Yet you continue to "assert" the superiority of your
solution, without one single *fact* to back it up. Do you understand
why that is a problem?
> and just get a kick out of telling me that my code "sucks."
Nobody "gets a kick" out of telling you anything, Hugh. Before you
can progress as a programmer, you need to show some level of maturity
and accept criticism (even if unfortunately stated at times). If one
person calls you a donkey, you can ignore it. But if it becomes a
commonplace, perhaps you should invest in a bridle?
Tell me something: would you be happy going to a medical doctor who
"never did research", and just asserted that "this treatment is the
best"? Why or why not?
Robert Maas, http://tinyurl.com/uh3t
> From: Hugh Aguilar <hughaguila...@yahoo.com>
> > > and provide the xt (execution token) for that comparer function
> > > at the time that the association is defined.
> > What is "execution token"?
> It is what you Lispers call a lambda function. Essentially, it is
> a pointer to a function that can be passed around as data --- the
> function can ultimately be executed with EXECUTE.
Is EXECUTE like APPLY, whereby it applies the lambda of
so-many-args to a list of arguments, matching the lambda paramters
to the actual arguments? For example, a compare function would take
two parameters, which would be matched with two items in two
corresponding containers being merged? If so, EXECUTE seems to be a
misleading word. APPLY would be a better word for this action.
> Look in my novice package and see how functions such as EACH (in
> list. 4th) take an xt and execute that function for every node in
> a list.
It sounds more like you are APPLYing the function to each node in a
list. I think this is a case where you re-invented the wheel (John
McCarthy invented APPLY circa 1959) but never heard the standard
jargon for the concept so you invented your own term and IMO your
term is not as appropriate as the standard term. I invent my own
jargon under similar circumstances (not knowing what other people
are already calling the concept), or in more original circumstances
(when I'm the very first person with a new concept, such as
interval-refinement mapping between probability spaces). Sometimes
I already know the standard term, but don't like it, because it's
misleading, so I invent my own jargon more precise and accurate
than the standard jargon. For example what most people call
"balanced [binary] search trees" is more accurately called
"self-balancing [binary] search trees".
> > > ... in Forth we have F~ that does an approximate equality test for
> > > floats. This can be used to smooth out tiny round-off differences such
> > > as you are describing.
> > That's horrible to use in a self-balancing search tree, because
> > equality per that predicate isn't transitive, that is A can equal
> > B, and B can equal C, but A not equal to C. That totally breaks the
> > concept of self-balancing search tree where equal keys are
> > clustered into a single node and anything not equal to all those
> > keys are either before it or after it.
> You are right --- I hadn't considered that problem at all.
> So what is the solution?
Don't convert exact mathematical values to floating-point
approximations in the first place. Start with totally-ordered exact
values, where for any two values a,b exactly one of these sentences
is true:
a<b
a=b
a>b
The *keep* that total ordering whenever you simplify the data to be
more efficient to compare.
Or if you never have exact values to begin with, only
approximations based on inexact real-world data sampling, then
don't try to make a totally-ordered set, instead make an explicit
partial ordering. For example, if each real-world data value has an
exact lower bound and upper bound, you could have a two-level
self-balancing search tree, where the top level sorts into bins per
lower bound, and then inside each bin another level sorts according
to upper bound, and so a search for items satisfying a query would
have require a two-level nested traversal. Or with the same
lower+upper bound you could have a sort of "radix" classification,
where values with wide margin were directly located in a cell near
the root while values more accurate would be located within a
deeper cell that had more digits of precision fixed by its location
in the hierarchy. This nexted-radix tree would be efficient for
finding all values whose error-interval overlaps with a given exact
value or which overlaps with a given error-interval, because you'd
only have to look in one or two top-level cells and follow only one
or two branches down each level until you hit the level where the
query interval was wider then the radix intervals.
> I don't know of any Forth implementation of unlimited-size integers.
"This looks like a job for Superman."
(This looks like a good project for any Forth expert, as you claim to be.)
> Forth is very efficiency-focused --- it is primarily used in
> micro- controllers. Unlimited-size integers aren't the kind of
> thing that would normally be implemented in Forth --- that is
> Python-type of software!
I disagree. Forth is very small to install on a computer of any
size, as a way to bootstrap to higher-level languages. One idea
floating around in comp.lang.lisp in recent years is to implement
Lisp within Forth. Specifically I figured out a strategy for
implementing a reference-count storage-reclamation system that
almost never hung waiting for storage to be reclaimed, by doing
lazy-evaluation on reclaiming sub-trees whose reference-count had
dropped to zero. Each storage-allocation step you do, it'd check if
any storage-reclamation is in progress, and spend a tiny bit of
time doing the next step of such before getting back to your
service request. Thus instead of your program running at maximum
speed until it ran out of memory, then hanging for a long time
while a GC happened, it'd run slightly slower whenever
storage-reclamation was in progress, because it's effectively
timesyaring the user process with the storage-reclamation process,
and *never* need to STOP THE WORLD for a GC. Such a version of Lisp
could then run real-time time-critical micro-controller
applications. All you'd need is a CPU that is about 3 times as fast
as needed to do the application without any storage reclamation,
and then timesharing half its time on application and half on
storage reclamation would still be fast enough to meet critical
time deadlines.
Unfortuately I never found anybody expert at Forth who might be
interested in such a project ... until now! You!! Yes, you!!
> They decay (get halved) when any of them get close to the upper
> bound of integers. As a practical matter, this doesn't matter
> when you have a 32-bit field, because it happens so rarely. Even
> with a 16-bit field it is not going to be a big deal --- this is
> a symbol table after all!
Good, that you thought of that already and did the "right thing".
By the way, in my adaptive data-compression algorithms, with
left-context to choose which histogram to work from, I use
histogram counts only up to 255, and scale all histogram entries by
some factor such as 3/4 whenever the largest entry reaches the
maximum. (And for efficiency, historgram is kept sorted in
descending order by count of usage.) Whenever any count would drop
to zero, that node is absorbed in the "escape" ("none of the
above") node. Thus new nodes are constantly added each time the
"escape" node is exercised, and a batch of low-frequency nodes are
expunged each time the histogram is down-scaled. Also, if it runs
out of memory, it runs a GLOBAL down-scale, which instead of
scaling down individual histograms, scales down the left-context
tree, merging low-frequency left-contexts into their parent tree.
> > I've heard of a different algorithm where *every* time a node is
> > used it is miagrated just one step higher in the tree (unless it is
> > already at the root), thus miagrating recently-used nodes towards
> > the top, and avoiding the need for any total-access count.
> That is the Splay Tree that I mentioned.
Aha, this is a case where you knew the standard jargon but I didn't.
Google search -> http://en.wikipedia.org/wiki/Splay_tree
"The splay tree was invented by Daniel Dominic Sleator and Robert
Endre Tarjan in 1985."
Is this the same Dan Sleator whom I met in 1969 at Santa Clara
University, when he showed me the XOR-square hack for making pretty
patterns on dotmatrix printers?
> I won't really know if my symtab is better than whatever
> algorithm until I have implemented both in a compiler and tried
> each of them out on a test suite of "typical" source files. Until
> this is done, and there is some actual data available, I'm not
> going to worry about all of this speculation as to what is better
> than what else.
Wise choice. Just use *something* that is efficient (log(n) for
search/insert/delete/excerptSegment, n*log(n) for merge) and get on
with the rest of your application, and worry about tiny speed
improvements if and when you have various alternate plug-in
self-balancing-search-tree implemetations you can compare for
speed.
I reached the end of my reply here, so let me go back to say more
about my idea for implementing a reference-count storage-management
system within Forth:
The main problem is to make sure I don't accidently increment or
decrement a reference count the wrong number of times. My proposed
solution is to have primitives for DUPrefCOUNT and DROPrefCOUNT
which do the usual DUP or DROP operation in Forth but *also* do the
appropiate adjustment on the reference count of the object pointed
at by the duplicated or deleted pointer. Once you have that
implemented, and all your Lisp service routines do *all* their
duplicating and discarding local copies of variable through those
two primitives, it's possible to write higher level code without
accidently goofing the reference count.
Whenever DROPrefCOUNT gets a node with reference count exactly 1,
thus it reduces it to zero, it immediately sends that pointer to
the first stage of storage reclamation, with interrupts disabled
during this critical section of code, does enough work there to
free up some key global used for the interface, then turns
interrupts back on before returning to the caller.
DUPrefCOUNT has several options:
- Never allow count to exceed some fixed size. If it'll exceeds it,
signal an exception, so that a higher level of program can
decide what to do.
- Never allow count to exceed some fixed size. If it'll exceeds it,
make a semi-deep copy of the structure, as deep as necessary to
avoid any sub-node count exceeding the limit, which is fine for
functional programming but not so good for object identity.
- Use different kinds of reference-count cells, one for nodes
expected to have only small reference count, another format for
nodes that have many direct references hence need a larger
max-ref-count. When a small-ref-count node exceeds its limit,
copy the payload to a new location and use the old storage to
install a large-ref-count node pointing to the payload. Thus
small-count nodes have refcnt and payload contiguous while
large-count nodes have reference count in original location and
payload somewhere else.
Back to splay trees from my previous part of reply:
| Advantages include:
| * Simple implementation--simpler than other self-balancing binary
| search trees, such as red-black trees or AVL trees.
Hey, somebody adopted my new jargon here "self-balancing ..."!!
It's nice to know somebody out there realized my new jargon was
more accurate than the old standard jargon. (Or I'm not the only
person who has independently invented the same new jargon.)
Robert Maas, http://tinyurl.com/uh3t
> > > If you provide some links to papers on these, I would read them.
> > I don't have a printer, so I can't put any of this on paper.
> Actually, I meant "paper" in the sense of "document" --- I was
> hoping that you might have a website where you describe your work.
I've written up a lot of my proposals, sometimes by newsgroup
articles, sometimes by Web pages, and so-far not one person has
shown that he/she read what I wrote carefully enough to understand
the concept and offer feedback that would help me to fix my writing
and ecourage me to do further work on the proposal and/or
implementation. I have to spend my energy writing up just the most
crucial of my new ideas, such as http://TinyURL.Com/NewEco, and
don't have enough remaining energy to write up stuff of lesser
urgency that not one person has ever expressed interest in (asking
for an already-written "paper" doesn't count as expressing
interest). This creates a "chicken and egg" problem for such
not-so-urgent proposals.
As for my proposal of no-context software-development IDE that is
based on menus to navigate a hierarchy of pre-existing intentional
types and pre-defined methods that operate on various
implementations of those intentional types: You have expressed just
the minimal level of interest so-far, not enough to break the
"chicken and egg" block. I think the best way to proceed is for me
to post quick summaries of the proposal (already done), then you
ask pointed questions about speficic aspects (pending), then I
answer any of those questions, and back and forth Q&A until the
combination of your interest and my piecemeal information
constitutes enough informal "brainstorming" and firming of my
proposal to warrent my collecting the Q&A into either a Web page or
a FAQ database
At the moment, I've just (a few days ago) finished implementing my
method for covertly bootstrapping public-key parameters across a
non-secure link from my covert-PK-creation process (CMUCL) to
various remote PHP/MySQL sites that I'm building, and now I'm
trying to decide how to build upon these now-PK-enabled servers in
the context of NewEco, and also I urgently need to devise a way to
automatically miagrate appx. 180 megabytes of images (JPEG&BMP)
from my shell account out to various free hosting sites, to free up
shell disk space to allow further work processing images for
cell-phone. So the only work I can afford to do on anything else is
just to respond to newsgroup articles, including aswering questions
about my proposals.
> > Then when I realized that such a "cookbook" really should be
> > organized per intentional rather than implementational datatypes, I
> > decided to re-organize the "cookbook" in that way, but before I
> > could find time for that I realized that no-syntax IDE is even
> > better.
> There have been a lot of efforts to write software-generating
> software that can be used by non-programmers, but none of this
> has come to fruition --- good-old programming is still required,
> and likely always will be.
I actually disagree with this, and have solid evidence to support my
disagreement:
(1) In the 1940's, somebody might have made the same claim about
(literally) hardwiring computer programs by plugging physical wires
into boards that are then mounted onto computers to connect
circuits together in a particular way to solve a particular
problem. Somebody might have claimed that such hardwiring of
programs would always be required, because if somebody wrote a
program to automatically build a "virtual" program into memory by
loading from some external medium such as hollerith cards, by the
time somebody had completed running the load-into-memory process,
memory would already be full, so there'd be no room to actually run
the program, which would be moot because by that point one of the
vacuum tubes would need to be replaced and the whole process would
need to re-start. Better plug wires into a board so that no memory
is consumed for the program itself and as soon as all vacuum tubes
are working the program can be plugged in and started to run
immediately before another vacuum tube burns out. But then
transistors were invented, and ferrite-core memory was invented,
allowing computers to have longer mean-time-before-failure and over
a thousand BCD-digits or binary-words of memory.
(2) In the early 1950's, somebody might have made the same claim
about coding programs directly in machine language by manually
composing binary codes and punching them into paper tape or
Hollerith cards. Two thousand BCD-digits or one thousand 16-bit
words of memory simply wasn't enough memory to fit an assembler for
machine language and still have room left to actually run the
program. So assembly language will always be an aid to manually
coding binary programs, not anything that can be reasonably
automated. But then computers with 10k decimal digits of memory
were built (IBM 1402,1620), and computers with rotating-drum memory
(IBM 704), were built, allowing room for an assembler, and card
punches were developed for punching the binaries out, to load back
in later, so that the assembler could be loaded into memory, and
run, then the object program could be loaded back in to replace it,
allowing the full 20k BCD-digits or 5k 16-bit-binary words to be
occupied by the object program plus memory.
(3) In the late 1950's, somebody might have made the same claim
about coding programs in assembly language, that concepts of "high
level" language were impractical. But ferrite-core memory got
cheaper, so that there was room for compilers, and Lisp and Fortran
and COBOL were invented and squeezed into this decent-sized memory,
turning such "high-level" languages into something practical.
(4) In the early-mid 1960's, somebody might have made the same
claim about coding algorithms directly in Lisp 1.5 (MIT) or 1.6
(Stanford) or in FORTRAN or COBOL. But Lisp has gotten successively
better (MacLisp, BBN-Lisp, UCI-Lisp, Standard-Lisp, Portable-SL,
LispMachine, and now Common Lisp), while Fortran has been replaced
by Algol then Pascal then C, and C has been extended to C++ then
merged with features from Lisp (most notably a standard data
representation that supports reliable automatic garbage collection)
to yield Perl and Java and PHP. And memory is now measured in
gigabytes instead of tens of kilobytes, so just about everyone can
afford to write high-level code where the programmer doesn't have
to worry about storage reclamation or low-level implemetations.
(5) Now in the 2010's, *you* are making the same claim about coding
algorithms directly in "high-level" string-of-text syntaxes. But I
see Google as just about everybody's favorite way to find
information, not just about "popular" topics, but also highly
technical need-to-know topics such as how to perform specific types
of data processing (such as finding the length of a string, or
matching a regex to sub-strings, or opening a TCP/IP socket) in a
specific programming language (Common Lisp, PHP, Java, etc.). I see
the union of these two techniques: Instead of doing a Google search
to find a tutorial or manual that tells how to do some D/P task
within a specific language, or browsing a "cookbook" of collected
how-to information such as
http://www.rawbw.com/~rem/HelloPlus/CookBook/CookTop.html
and then reading the text and copying the example and trying to
adapt it to your specific needs, you would use an IDE to
automatically do a search for what you need and automatically apply
it to your needs, without you ever having to eyeball whatever the
IDE is really doing "under the hood". The difference is analagous
to today's housekeepers who read a cookbook and manually follow a
recipe, to Captain Picard asking the food replicator for some
specific food item to be made.
Note: At present it's an open question whether my initiative will
work reasonably or be another good-sounding idea that didn't really
work. I consider my initiative to be worth pursuing, if I can find
anybody else interested.
> Because of this, I can't say that I'm very much interested in the
> idea. I would read any document that you've written, but I can't
> promise that I will be inspired to get involved.
Not even to ask follow-up questions to what I already summarized?
> The only success story that I know of, is the software that is
> used for programming PLCs (Programmable Logic Controllers). The
> user can point-and-click and can generate the "ladder diagrams"
> that represent a purely logical "program." ...
Is there any Web version of this interface/utility?
> > Have you built and installed your first CGI/CL application so that
> > I can run it from here to see how it works?
> Actually, I have no intention of using CL for web applications (I
> just want to use CL for scripting). I am not much interested in
> web stuff,
So basically you have no way to provide a pubilc demo of anything
you've accomplished, and have no intention of any such?
> but if I ever did get interested, I would most likely use a web-
> specific language such as PHP.
Somebody here (c.l.l) announced something called LSP (Lisp Server Pages)
which just like PHP:
- is resident in the HTTP server so that it doesn't need to start
up a new process each time it runs a script;
- supports alterating between script mode and verbatim-printthru mode
If that were freely available, I'd use it instead of PHP. But at
the present I do what you would do, use PHP. For tasks that can't
be done efficiently in PHP, such as resampling images, or
big-integer modular powers, I spawn a sub-process of Lisp or C-appl
from PHP just to do that single task. In the case of Lisp, that one
task takes an extra half second to re-start Lisp (plus a few
milliseconds for the actual task in Lisp), compared to taking
several seconds with bcmath or several minutes if coded directly in
PHP. LSP would be so much better if it were available to me.
> I don't know enough about the subject to know if Python is better
> than PHP,
I don't know of any HTTP server that has Python integrated into it
to avoid the overhead of re-starting a new process for each
script-run. Do you know of any? Any that are on free hosting
servers?
> or Ruby on Rails is best (as many claim),
Same questions about that.
> I'm really turned off by the internet right now, because it seems
> to promote the worst in humanity --- the internet has become the
> Kingdom of Trolls.
See http://TinyURL.Com/TruFut for a proposed solution to the
mis-inforation going around. See http://TinyURL.Com/RevTre for a
proposed solution to filtering a large supply of information
towards a given target (person's interest, or specific topic) per
both relevancy (on topic) and quality (truthiness and clarity of
statement). In particular, some comination of RevTre & TruFut could
filter the content of a newsgroup to eliminate spam and trolling
from what the end-viewer sees.
> Somebody would have to convince me that the internet has some
> kind of positive influence on humanity, before I would want to
> start writing web software.
Take a look at http://TinyURL.Com/NewEco and tell me if it could
potentially provide employment for nearly everyone, thereby ending
poverty, and thus ending the desperation that drives people to
crime and terrorism and drives nations to warfare.
(cutting my reply here; more later)
Hugh Aguilar
> > software that can be used by non-programmers, but none of this
> > has come to fruition --- good-old programming is still required,
> > and likely always will be.
>
> I actually disagree with this, and have solid evidence to support my
> disagreement:
Certainly there have been advances in programming --- not too many
people are using Hollerith cards these days! The important point
however, is that all of these advances allowed programmers to program
more easily than they had done previously --- but they were still
programmers.
The reason why I'm turned off by point-and-click "programming" is that
the primary motivation here is to allow non-programmers to program,
without ever requiring them to learn anything. There are a lot of MBA
managers who realize that they don't know *anything* about
programming, but who also wish that they didn't have to pay those
pesky programmers' salaries, so they ask: "Why isn't there some
software available that generates computer programs, and all I will
have to do is describe what I want the program to do, and the program
will be handed to me on a silver platter?" They basically want
Aladdin's Jinni to build their palace for them --- this is magic, not
technology.
I'm not saying that you won't be able to make an improvement in
software development --- improvements have been made before, and will
continue to be made --- I'm just saying that if you try to please the
MBA types, you will never succeed, because you're not a Jinni.
> Note: At present it's an open question whether my initiative will
> work reasonably or be another good-sounding idea that didn't really
> work. I consider my initiative to be worth pursuing, if I can find
> anybody else interested.
I don't have any money, so I couldn't invest in it even if I did think
that it would work. Also, I'm still just working my way through
"Practical Common Lisp," so I'm not prepared to help with the code
either.
> > The only success story that I know of, is the software that is
> > used for programming PLCs (Programmable Logic Controllers). The
> > user can point-and-click and can generate the "ladder diagrams"
> > that represent a purely logical "program." ...
>
> Is there any Web version of this interface/utility?
Most PLC software is proprietary, and specific to a PLC board. Also,
I've never used a PLC, so I don't really know much about the subject.
When I worked at Testra, there was some interest there in developing a
PLC front-end for their motion-control board, but nothing ever came of
this. I did learn a little about what PLCs are though. They do offer
quick development compared to using a programming language such as
Forth or C, but they also have limitations --- they will never replace
Forth and C, and they weren't designed to do so.
In programming micro-controllers, there is such a thing as a "timed
loop." The idea is that you have a loop with a delay function on the
end of it, which causes the loop to take *exactly* the same amount of
time for each iteration (for example, 1/60th of a second, or one
"jiffy"). The programmer writes functions that go into the loop, and
he has to make sure that none of these are so time-consuming as to
overflow the alloted time. Often, there will be count-down counters
that cause a particular function to execute once every so many
iterations through the loop. By syncing all of these functions'
counters properly, the programmer can make the machine push and pull
pistons or whatever, without the machine parts hitting each other.
There was a book out by Mototola a long time ago, (I think it was
called: "Programming the MC6805") that described timed-loops for
novices.
PLCs can do what timed loops can do, but you program them using
graphical diagrams (so-called "ladder diagrams") rather than assembly-
language. There are obviously some limitations here as to what you can
accomplish, but within those limitations, PLCs work pretty well.
> > > Have you built and installed your first CGI/CL application so that
> > > I can run it from here to see how it works?
> > Actually, I have no intention of using CL for web applications (I
> > just want to use CL for scripting). I am not much interested in
> > web stuff,
>
> So basically you have no way to provide a pubilc demo of anything
> you've accomplished, and have no intention of any such?
I'm just barely learning Lisp --- I have sample code in Forth only.
I may be more helpful in the future when I know more Lisp --- until
then, good luck with your work. :-)
Hugh Aguilar
I didn't invent or name EXECUTE --- Chuck Moore did --- that word has
been with us since the very first Forth implementations of the 1970s.
EXECUTE is a lot simpler than what you are supposing. It doesn't
examine the argument list to determine if the function is matches or
not. There is actually no way in Forth to examine an argument list,
because there is no explicit argument list --- there is just data on
the parameter stack which may or may not be used by the function.
EXECUTE just does an indirect CALL through the xt address. EXECUTE
typically compiles into a handful of machine-language instructions ---
super-simple!
Forth is a *very* low-level language compared to Lisp. To a large
extent, Forth is just a kind of macro-assembler --- all of the Forth
words expand into a handful of machine-language instructions. I
consider Forth to be the best micro-controller language invented, and
I expect this to continue to be true forever. On the other hand, I am
learning Lisp so that I can become a better desktop-computer
programmer --- I no longer believe that Forth is appropriate for that
environment, and I think that Lisp may be best choice, although there
are actually quite a lot of valid choices in that environment that
have their adherents --- it is largely a matter of taste. I'm mostly
choosing Lisp because it has macros, which I am familiar with from
Forth, whereas languages such as Ruby and Python don't.
The problem is that A=B and B=C, but A<>C. With F~, we are just
measuring the distance between the numbers, so A and C can be too far
apart to be considered equal, although they are both close enough to
the in-between value B to be considered equal to it.
This is easily solved by rounding off each number to a lower-
precision, and then doing an *exact* comparison for equality. If we
determine that the last few digits of the floats are mush, then we
just round-off to a level of precision that we consider to be
meaningful (for the data involved) --- get rid of the mush!
> > I don't know of any Forth implementation of unlimited-size integers.
>
> "This looks like a job for Superman."
> (This looks like a good project for any Forth expert, as you claim to be.)
Maybe, but that sounds like an effort to turn Forth into yet another
desktop-computer language. I would really prefer to just use Lisp for
desktop programming and Forth for micro-controller programming --- let
each focus on the arena which they were designed for --- Forth will be
ruined by making it a "Jack of all trades and a master of none."
> > Forth is very efficiency-focused --- it is primarily used in
> > micro- controllers. Unlimited-size integers aren't the kind of
> > thing that would normally be implemented in Forth --- that is
> > Python-type of software!
>
> I disagree. Forth is very small to install on a computer of any
> size, as a way to bootstrap to higher-level languages. One idea
> floating around in comp.lang.lisp in recent years is to implement
> Lisp within Forth.
I don't get it. Forth can be implemented on a small computer (a micro-
controller), but this doesn't imply that Lisp can be implemented on
such a small computer --- or that it would be a good idea to do so.
I don't know enough about Lisp yet to follow your reference-count
idea. From the little that I know about Lisp however, I do agree that
it might be easier to implement Lisp in Forth rather than in C (as was
done in Xlisp that later became AutoLisp). This would only be
interesting if it were done on a Forth-engine (a processor that is
designed to run Forth, such as the MiniForth that I wrote the
development system for). It might be easier to build a Forth-engine
than a Lisp-engine, although I don't know enough about processor
design to comment on this. If so, it might be possible to get Lisp to
run in the micro-controller environment using a Forth-engine as a base
underneath it. Why anybody would want to do this, I don't know --- we
already have Forth for use on micro-controllers, so why try to
introduce Lisp, which is basically a desktop-computer language?
My boss at Testra (which developed the MiniForth processor) told me
that some Lispers once talked to him about developing a Lisp
processor, but nothing ever came of it. You may want to talk to Testra
about this possibility --- they have already done some research on the
idea. They might be able to provide you with a customized version of
the MiniForth that provides support for Lisp (maybe a few new machine-
language instructions on top of the core instruction-set). I no longer
work for Testra though, so that kind of thing is not my concern
anymore.
Robert Maas, http://tinyurl.com/uh3t
> > > software that can be used by non-programmers, but none of this
> > > has come to fruition --- good-old programming is still required,
> > > and likely always will be.
> > I actually disagree with this, and have solid evidence to support my
> > disagreement:
> > ...
> From: Hugh Aguilar <hughaguila...@yahoo.com>
> Certainly there have been advances in programming --- not too many
> people are using Hollerith cards these days! The important point
> however, is that all of these advances allowed programmers to program
> more easily than they had done previously --- but they were still
> programmers.
Right now most of my software writing is by copy+paste+edit. Most
of my software is data-flow, whereby I get some data, then call a
function to process it to get some new data, then call another
function to process that data to get yet newer data, etc., until
finally I have the desired end-result data. Putting those two
concepts together, what I do is copy+paste the source of data, the
copy+paste the name of the function to call, and trim up the form
whereby the function is applied to the data, then copy+paste
another function-name, and trim up that new form, etc. Each time I
need the name of a function, most of the time, I need to find some
code I already wrote that uses that function, and then I can
copy+paste that function name. Sometimes I copy+paste a whole form
or set of nested forms or sequence of SETQ forms and then
copy+paste to replace pieces within it. If I'm calling a function I
never called before, I use Google to search for the appropriate
function (mostly in PHP) or open my CLtL1 to find it and manually
re-key it that one time. My proposed menu-driven system would
simply replace the search (on Google or CLtL1 or old code) by
menus, replace the copy+paste by a simple click, and eliminate the
need to clean up the form to have properly nested parentheses. How
would that not be "programming", if what I do now IS "programming"?
> The reason why I'm turned off by point-and-click "programming" is
> that the primary motivation here is to allow non-programmers to
> program, without ever requiring them to learn anything.
Wrong. They would still need to think out the dataflow so that they
choose the correct first function, then the correct second
function, etc. etc., with a goal in mind, and they recognize when
they have achieved the desired final data in that chain or DAG
(directed acylcic graph). If they can't visualize the goal, and the
conceptual path towards the goal, they have no idea which functions
to choose, and would random-walk to generate all sorts of "random"
data without getting any closer to any goal they might have had in
mind (or might have been assigned by their supervisor/boss).
The one major thing they *won't* need to do is *memorize* hundreds
of names of functions, or spend endless time tediously searching
Google or CLtL or K&R etc. trying to find the appropriate function
to apply to the data. In other words, all they need to do is
imagine a description of the next data-processing step in their
mind, effectively writing "pseudo-code" in their head, then feed
enough keywords (not necessarily spelled correctly) to the search
engine to prime the menu system with what is most likely what they
had in mind, to make selection near the top of the menu
easy-as-pie.
They will *still* need to learn how to design algorithms to process
data, and use my system to practice that design process, in order
to develop software by my proposed IDE.
> There are a lot of MBA managers who realize that they don't know
> *anything* about programming, but who also wish that they didn't
> have to pay those pesky programmers' salaries, so they ask: "Why
> isn't there some software available that generates computer
> programs, and all I will have to do is describe what I want the
> program to do, and the program will be handed to me on a silver
> platter?"
If what they want has already been programmed, all the way from
start (given data for input) to end (finally processed data
presented in a legible format), then indeed that's how it will
work. But if what they want hasn't been exactly done before,
they'll need to learn how to break the task into pieces, or hire
others to break it into pieces. In some cases there will be three
pieces: A middle piece that does the major task, a pre-processing
step that simply converts the given data into the format needed by
the middle piece, and a final step that merely reformats the final
data in the way the MBA manager wants. In that case, all he'd need
to hire anyone to do are the first and last steps, so he'll save a
lot of money compared to the old way of paying pesky programmers.
> They basically want Aladdin's Jinni to build their palace for
> them --- this is magic, not technology.
If you ever watched "I Dream of Jeannie", you'd realize the
obvious, that it's harder to explain to her what you want, and
convince her that you *really* want that, than to figure out how to
do it yourself or hire an ordinary mortal to do the work by
ordinary means. Hopefully the MBA manager will learn how to make
best use of my IDE, either with the help of others or by himself,
and realize the dream of a Genie wouldn't have been so great.
> I'm not saying that you won't be able to make an improvement in
> software development --- improvements have been made before, and
> will continue to be made --- I'm just saying that if you try to
> please the MBA types, you will never succeed, because you're not
> a Jinni.
I disagree. The MBA has already learned how to use a cell-phone,
and surely can also learn how to use my IDE together with
everything it's coupled with in http://TinyURL.Com/NewEco,
including low-cost contract labor to do all those little tasks
needed to fit an existing application into specific needs of the
day.
> > Note: At present it's an open question whether my initiative will
> > work reasonably or be another good-sounding idea that didn't really
> > work. I consider my initiative to be worth pursuing, if I can find
> > anybody else interested.
> I don't have any money, so I couldn't invest in it even if I did
> think that it would work.
In this regard, I have no use for your money. I need your critique
of my overall design for NewEco and the IDE component and the
contract-work component and brainstorming how to fit the components
together. I also need user-feedback for what's already implemented
in NewEco and the multi-language "cookbook" that will be converted
to intentional data-types. As I develop more of NewEco, and as I
start to implement the IDE (if and when somebody shows enough
interest to spur me to spend time building it), I need your
user-feedback on that. And as I use the first draft of the IDE to
bootstrap the rest of the IDE, I need you to design some of the
algorithms and also brainstorm with me to design the user
interface.
> Also, I'm still just working my way through "Practical Common
> Lisp," so I'm not prepared to help with the code either.
You won't need to write any "code" directly. Can you plan out
algorithms? If not, do you want to learn how?
> > > > Have you built and installed your first CGI/CL application so that
> > > > I can run it from here to see how it works?
> > > Actually, I have no intention of using CL for web applications (I
> > > just want to use CL for scripting). I am not much interested in
> > > web stuff,
> > So basically you have no way to provide a pubilc demo of anything
> > you've accomplished, and have no intention of any such?
> I'm just barely learning Lisp --- I have sample code in Forth only.
Do you have access to any machine that is Web-accessible (including
CGI) and *also* has a Forth environment available on that machine?
AFAIK there's no version of Forth on the FreeBSD system where I
have my account, where I write my Lisp and PHP applications, so
unless somebody finds such a program for me, I can't write a
CGI/Forth hello-world demo.
> man forth
No manual entry for forth
> man Forth
No manual entry for Forth
> man FORTH
No manual entry for FORTH
Maybe you could write one for me and install it on your server and
show it to me so that I can add it to my collection? Or if you know
where to find an already-installed Forth on FreeBSD, you could tell
me where to find it here, and then you could coach me towards
writing my own CGI/Forth demo.
For "hello world", the hard part isn't writing the code, you just
copy the code from my demo. The hard part is figuring out how to
make an application accessible via CGI. You could do that already
without needing to learn any Lisp first. Then as you learn more and
more Lisp, for each interesting demo you get working you could
adapt it to CGI to "show it around".
Before posting this, I did a Google search for Pocket Forth
FreeBSD, found http://www.forth.org/compilers.html with link to
http://www.rainbarrel.com/ which has Diaperglu 1.5 (formerly called
Dllforth). I dowloaded the tgz version, got:
2692 -rw------- 1 rem user 2707474 Nov 22 22:37 diaperglu13oct2009v1.5.tgz
Then I gunzipped it, got:
16013 -rw------- 1 rem user 16302080 Nov 22 22:37 diaperglu13oct2009v1.5.tar
That left only 3.3 MB unused space in my account, so there's no way
I could possibly untar it, so I deleted it all. If anyone knows of
a *much* smaller Forth for FreeBSD, I could try again to see if it
fits. By comparison, Pocket Forth that I have on my Macintosh is
just over half of a megabyte. Why is Forth for FreeBSD about 30
times as large??
The Google search also turned up:
http://www.savvyfrog.com/Computers/Programming/Languages/Forth/Implementations/
* Pocket Forth Free, small implementation for Macintosh, by Chris
Heilman. With floating point math, apple events, and full toolbox
availability, quick implementation of powerful yet small
applications is easy and fast.
which sounds like what I have on my Mac, but when I click on the link:
Link that you currently have selected
Linkname: Pocket Forth
URL: http://chemlab.pc.maricopa.edu/pocket.html
it just hangs trying to connect to the host.
The Google search also turned up:
http://www.dmoz.org/Computers/Programming/Languages/Forth/Implementations/
with link to:
http://www.mactech.com/articles/mactech/Vol.05/05.04/PocketForth/
which is a pretty nice review of Pocket Forth, including innerds of
how it works.
The Google search also turned up two different pages with links to:
http://home.iae.nl/users/mhx/eforth.html
I downloaded eforthl.zip:
52 -rw------- 1 rem user 52111 Nov 22 23:22 eforthl.zip
Unzipped it, total now 2.2 megabytes, leaving 17 MB free, so next I
need to compile it:
gcc eforth.c; mv a.out eforth
That's won't work, because all the files are upper-case:
3 -rw------- 1 rem user 1636 Feb 10 1996 BUBBLE-S.E4
1 -rw------- 1 rem user 235 Feb 10 1996 EF.TXT
9 -rw------- 1 rem user 7702 Apr 11 1998 EFORTH.C
1027 -rw------- 1 rem user 934974 Feb 10 1996 EFORTH.IMG
63 -rw------- 1 rem user 63103 Oct 19 1996 EFORTHL.ASM
3 -rw------- 1 rem user 1586 Oct 19 1996 EXE2OUT.FRT
1 -rw------- 1 rem user 173 Feb 10 1996 FIB.E4
6 -rw------- 1 rem user 5514 Oct 19 1996 IO.C
1 -rw------- 1 rem user 343 Apr 29 1997 MAKEEL.BAT
2 -rw------- 1 rem user 1291 Feb 10 1996 MATRIX-M.E4
6 -rw------- 1 rem user 5178 Oct 19 1996 NEW.TXT
8 -rw------- 1 rem user 7100 Feb 10 1996 OPT.E4
1 -rw------- 1 rem user 318 Apr 29 1997 PACK.BAT
3 -rw------- 1 rem user 2288 Apr 29 1997 READ.ME
5 -rw------- 1 rem user 3666 Oct 19 1996 RELOCATE.FRT
1 -rw------- 1 rem user 471 Feb 10 1996 SIEV.E4
5 -rw------- 1 rem user 3593 Feb 10 1996 TTY.C
1 -rw------- 1 rem user 484 Feb 10 1996 TTY.H
52 -rw------- 1 rem user 52111 Nov 22 23:22 eforthl.zip
1027 -rw------- 1 rem user 934974 Apr 10 1998 eforthlinux8050000.img
So let's try this:
gcc EFORTH.C
EFORTH.C:10:17: error: tty.c: No such file or directory
EFORTH.C:254:2: warning: no newline at end of file
EFORTH.C:17: error: aggregate 'tty std_in' has incomplete type and cannot be defined
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:73: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:102: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C:130: warning: deprecated conversion from string constant to 'char*'
EFORTH.C: In function 'int identify()':
EFORTH.C:167: error: 'read' was not declared in this scope
EFORTH.C:169: error: 'strcmp' was not declared in this scope
EFORTH.C:170: error: 'keyq' was not declared in this scope
EFORTH.C: In function 'int qkey()':
EFORTH.C:175: error: 'nodevice' was not declared in this scope
EFORTH.C:176: error: 'keyq' was not declared in this scope
EFORTH.C:177: error: 'read' was not declared in this scope
EFORTH.C: At global scope:
EFORTH.C:183: error: redefinition of 'int row'
EFORTH.C:140: error: 'int row' previously declared here
EFORTH.C:183: error: redefinition of 'int col'
EFORTH.C:140: error: 'int col' previously declared here
EFORTH.C: In function 'void goaway(int)':
EFORTH.C:203: error: 'tty_restore' was not declared in this scope
EFORTH.C: In function 'int qkb()':
EFORTH.C:212: error: 'nodevice' was not declared in this scope
EFORTH.C: At global scope:
EFORTH.C:239: error: invalid conversion from 'void (*)(int)' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)(int)' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)(int, char*)' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'int (*)(int, char*)' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)()' to 'int (*)()'
EFORTH.C:239: error: invalid conversion from 'void (*)(int, int)' to 'int (*)()'
EFORTH.C: In function 'int main(int, char**)':
EFORTH.C:249: error: 'tty_init' was not declared in this scope
EFORTH.C:249: error: 'tty_keymode' was not declared in this scope
EFORTH.C:249: error: 'tty_noecho' was not declared in this scope
EFORTH.C:250: error: 'nodevice' was not declared in this scope
EFORTH.C:250: error: 'strcmp' was not declared in this scope
EFORTH.C:253: error: too many arguments to function
mv TTY.C tty.c
gcc EFORTH.C
In file included from EFORTH.C:10:
tty.c:7:17: error: tty.h: No such file or directory
..
mv TTY.H tty.h
gcc EFORTH.C
EFORTH.C:254:2: warning: no newline at end of file
In file included from EFORTH.C:10:
tty.c:10: error: conflicting declaration 'char* sys_errlist []'
/usr/include/stdio.h:347: error: 'sys_errlist' has a previous declaration as 'const char* const sys_errlist []'
I give up at this point.
mv a.out eforth
Nevermind.
Robert Maas, http://tinyurl.com/uh3t
> I didn't invent or name EXECUTE --- Chuck Moore did --- that word
> has been with us since the very first Forth implementations of the
> 1970s.
You need to distinguish between the low-level implementation of
Forth and the high-level conceptual task being done, and you need
to be to translate (in your mind) between the two. Here are some
examples:
In Forth you put 3 and 5 on the stack, then execute +, which prints 8.
In Lisp you enter (+ 3 5) into read, pass the result to eval,
pass the result to print, which prints 8.
Conceptually you apply + to two parameters 3 and 5.
In Forth you put 42 on the stack, then execute 1+, which prints 43.
In Lisp you enter (1+ 42) into read, pass the result to eval,
pass the result to print, which prints 43.
Conceptually you apply 1+ to the parameter 42.
Conceptually you have a list (3 5 7) and want to apply 1+ to each
element of that list, collecting the results into a new list..
In Lisp you have a linked-list containing [3|>]-->[5|>]-->[7|>]-->NIL
and a function 1+. You type (mapcar #'1+ '(3 5 7)) to read, pass
the result to eval, pass the result to print, which prints (4 6 8).
The way Lisp does it is to work its way down the linked list
applying CAR to the cell to get the element, and applyig CDR to
the cell to get the next cell. For each element it applyes 1+ to
that element. Somehow it builds the list of return values.
In Forth you have the same linked list with pointer on the stack,
and a word 1+ on the stack, and now you execute MAPCAR, which
swaps top items on stack, duplicates top item (the list),
executes CAR to get element, swaps some more to get 1+ and that
element at top of stack, executes APPLY, somehow saves the
result in a new list being built, swaps some more to get the
list at the top of the stack, executes CDR to get the pointer to
the next cell, etc. etc. Finally MAPCAR flushes all the extra
copies of stuff from the stack, leaving only the pointer to the
newly-built list at the top of the stack.
Do you understand that the conceptual description at the top of
this example is a *lot* more terse and understandable than the
horrible mess that is how Forth MAPCAR would do it internally?
> EXECUTE is a lot simpler than what you are supposing. It doesn't
> examine the argument list to determine if the function is matches or
> not. There is actually no way in Forth to examine an argument list,
> because there is no explicit argument list --- there is just data on
> the parameter stack which may or may not be used by the function.
But conceptually, each of the ordinary words in Forth applies some
data-processing function to some top items on the stack, replacing
them with the return value from that function. (I'm excluding
special words that start/end function definitions etc.)
And MAPCAR, conceptually, applies the same function to each of the
elements in a linked list, building a new linked-list. In Forth, it
does that using the top two elements of the stack, the function
word (or "execute" pointer) and the pointer to the linked list,
replacing those two stack items by the pointer to the list of
results.
> EXECUTE just does an indirect CALL through the xt address. EXECUTE
> typically compiles into a handful of machine-language
> instructions --- super-simple!
At a conceptual level, that doesn't matter. All that matters is
that in most cases it applies some function to top items on stack
and puts result back on the stack in their place.
> I am learning Lisp so that I can become a better desktop-computer
> programmer --- I no longer believe that Forth is appropriate for
> that environment,
At the application-programmer level, I agree. But Forth would be a
nifty way to implement a high-level language on a medium-small
desktop computer, such as my Macintosh Performa 600 with only 8MB
RAM, or a medium-large portable device with a similar amount of
RAM.
> and I think that Lisp may be best choice, although there are
> actually quite a lot of valid choices in that environment that
> have their adherents --- it is largely a matter of taste.
IMO Lisp is clearly the best choice for stdio applications, but PHP
might be best for the user-facing part of Web applications, more
difficult and troublesome to program complex algorithms than Lisp,
but more efficient for toplevel scripts CPU-wise because it's
integrated directly in a lot of Apache HTTP servers, and easier to
intermix HTML and script sections. (If LSP = Lisp Server Pages
becomes more generally available in the future, that might beat out
PHP.)
> I'm mostly choosing Lisp because it has macros,
I've programmed in Lisp since 1973, and I hardly ever feel a need
to write a new macro, although I appreciate the macros already
provided with Common Lisp, such as LOOP and WITH-OPEN-FILE and
WITH-OUTPUT-TO-STRING. But someday I might find a need to write a
new macro, so I appreciate that I'd be allowed to do so.
Closures are IMO more useful for me to use, hence a reason to use
Lisp instead of PHP for some tasks. I also rather like
ext:run-program which is in CMUCL. The interactive debug pagkage
with in-context REPloop is *essential*, in Lisp but missing from
all other languages I've used.
> The problem is that A=3DB and B=3DC, but A<>C. With F~, we are just
> measuring the distance between the numbers, so A and C can be too far
> apart to be considered equal, although they are both close enough to
> the in-between value B to be considered equal to it.
Yes, you do understand the problem I explained.
> This is easily solved by rounding off each number to a lower-
> precision, and then doing an *exact* comparison for equality.
No, that doesn't solve the problem at all, and in some cases makes
it worse. All it does is mask the problem so it's harder to realize
you have already screwed yourself, like being blindfolded when
walking the plank or going to the gallows.
As I said, a single mathematical value can be computed different
ways, resuilt in different roundoff effects, resulting in the final
value appearing as different floating point values. If you simply
round further, to lower precision, effectively putting the original
values into more coarse buckets, causing the same mathematical
value to *sometimes* arrive in the same bucket by two different
methods of calculation, other times the two values will bridge the
boundary between adjacent buckets, causing the apparent difference
between the value and itself to be aggravated. Furthermore, two
mathematical values that are *different* will often fall into the
same bucket, so they seem (mistakenly) to be equal, even when the
original full-precision floating-point values were different.
IMO the best way to achieve "fail soft" behaviour, where at least
you aren't blindfolded and confused, where you at least know when
you are getting screwed by roundoff error, is to use interval
arithmetic. If two values come out overlapping, then they *might*
be equal, you have no way to know except by increasing precision
and trying again, or doing some *real*math* to prove them
different. If two values come out non-overlapping, then you can be
*sure* which is smaller and which is larger. So at least some of
the time you get a *sure* result, and the rest of the time you
surely know that you don't know whether the numbers are equal or
not.
IEEE floating point arithmetic is *supposed* to provide various
roundoff modes (ceiling, floor, round-towards-zero,
round-away-from-zero, etc.), and the latest Intel CPUs are supposed
to implement all that, and Common Lisp is *supposed* to provide
hooks to make that all usable from user-level Lisp code, so if you
are fortunate enough to have such a Lisp then you can implement
interval arithmetic where both upper and lower bound are IEEE
floating point values. With some other version of Lisp that doesn't
give proper access to those roundoff modes, you'd need to use some
other representation such as rationals to implement interval
arithmetic.
(When I looked at this issue a few years ago, the documentation
warned that Intel's IEEE roundoff modes were settable only as a
global flag, whereby *every* floating-point operation whatsoever
was affected equally by the current roundoff mode, making it nigh
impossible for an application programmer to control the mode
properly for writing an interval-arithmetic library. I don't know
whether this has changed since then.)
> > > I don't know of any Forth implementation of unlimited-size integers.
> > "This looks like a job for Superman."
> > (This looks like a good project for any Forth expert, as you claim to be.)
> Maybe, but that sounds like an effort to turn Forth into yet
> another desktop-computer language.
But one with a *very* small footprint that ran very fast.
> I would really prefer to just use Lisp for desktop programming
> and Forth for micro-controller programming --- let each focus on
> the arena which they were designed for --- Forth will be ruined
> by making it a "Jack of all trades and a master of none."
Here on my Mac, the only free version of Lisp I've found that even
halfway works is PowerLisp 2.01, which takes about five minutes
just to start up, and takes several minutes to reach the toplevel
when an ERROR happens, and takes about ten minutes to do a garbage
collect, and is missing some really basic stuff in Common Lisp, and
is very slow doing big-integer arithmetic, and I don't even know if
it's possible to hack the Mac toolbox traps from it, wheras I know
that Pocket Forth has a way to directly call both register and
stack traps simply by specifying the opcode with a special word. In
particular I'd like to write a utility that operates MacPPP from
it. Do you happen to know how to do that from Forth?
> > > Forth is very efficiency-focused --- it is primarily used in
> > > micro- controllers. Unlimited-size integers aren't the kind of
> > > thing that would normally be implemented in Forth --- that is
> > > Python-type of software!
> > I disagree. Forth is very small to install on a computer of any
> > size, as a way to bootstrap to higher-level languages. One idea
> > floating around in comp.lang.lisp in recent years is to implement
> > Lisp within Forth.
> I don't get it. Forth can be implemented on a small computer (a
> micro- controller), but this doesn't imply that Lisp can be
> implemented on such a small computer
Not tiny (I had a 6502 computer with only 4k bytes of RAM and no
disk, too small), more like semi-small (8 MB RAM for example).
Since Pocket Forth is only half a megabytes, there's plenty of room
to write list-processing primitives on top of it, with my system
for reference-count storage management.
> I don't know enough about Lisp yet to follow your reference-count
> idea.
What I said about my reference-count idea had nothing to do with
Lisp specifically. All you needed to know about is allocating cells
of memory and using them to build linked-lists and trees. The basic
idea of a reference-count system is that each cell has a counter
that tells how many direct references there are to it. When you
make a copy of the pointer to a given cell, that cell's count gets
incremented, and when you destroy one of the copies of the pointer
to that same cell, its count gets decremented, and if it's reached
zero then you can expunge that cell and decrement the count on each
cell it points to. So long as you don't create a pointer loop then
discard all pointers to that loop from outside that loop, you don't
have "memory leak". You should be able to understand what I wrote
just there. The rest of what I wrote earlier was simply a claim
that I have a system for duplicating and discarding pointers in a
well-defined way which can then be used to build higher-level
algorithms that always maintain the correct reference count on each
cell, plus some variant ideas how to implement it.
> From the little that I know about Lisp however, I do agree that
> it might be easier to implement Lisp in Forth rather than in C
Yes. That's the main point, plus my idea to use reference count
instead of traditional garbage collection algorithms. An advantage
of Forth compred to C is that the higher-level (Lisp innerds) code
can be written and tested interactively in Forth instead of the
annoying edit-compile-relink cycle needed in C. Also, for me
personally, my Mac doesn't have any decent C compiler, but I
believe that Pocket Forth is a decent Forth environment.
> (as was done in Xlisp that later became AutoLisp).
I tried XLisp 2.1g here on my Mac, and basically it didn't work
decently at all.
> This would only be interesting if it were done on a Forth-engine
> (a processor that is designed to run Forth, such as the MiniForth
> that I wrote the development system for). It might be easier to
> build a Forth-engine than a Lisp-engine, although I don't know
> enough about processor design to comment on this.
I have no money to buy anything like that, nor space to put it if
you give me free beta-test version to play with, so I'll pass on
further discussion of that otherwise fine idea. If you can make a
Forth engine powerful enough to run PPP over dialup, and if you can
then program it to host Web pages, with CGI/Forth, then you could
show me a demo of your stuff over the Web.
> If so, it might be possible to get Lisp to run in the
> micro-controller environment using a Forth-engine as a base
> underneath it. Why anybody would want to do this, I don't know
You don't need to go all the way to Lisp REP. You could go halfway,
with Forth words that invoke list-processing primitives with
automatic storage management. This would be a huge win compared to
needing to explicitly allocate memory and later explicitly recycle
it when you are done using it.
> we already have Forth for use on micro-controllers, so why try to
> introduce Lisp, which is basically a desktop-computer language?
Because lots of algorithms require allocating memory for data
structures that are built dynamically, and it's a royal pain to
need to explicitly "free" storage with done with it, and it's a
total pain not to be able to allocate memory at all during the run
of a program and thus not be able to write 99% of the applications
I would like to write.
All you really need to worry about implementing carefully are my
proposed DUPrefCOUNT and DROPrefCOUNT primitives, and then on top
of that write CONS CAR and CDR. Then write all your ordinary Forth
application code, with calls to CONS/CAR/CDR whereever you need
dynamic storage for data structures.
> My boss at Testra (which developed the MiniForth processor) told
> me that some Lispers once talked to him about developing a Lisp
> processor, but nothing ever came of it.
Google: "Lisp Machine"
Circa 1989 Symbolics Inc. made them.
Albert van der Horst
Robert Maas, http://tinyurl.com/uh3t <seeWeb...@rem.intarweb.org> wrote:
<SNIP>
>Maybe you could write one for me and install it on your server and
>show it to me so that I can add it to my collection? Or if you know
>where to find an already-installed Forth on FreeBSD, you could tell
>me where to find it here, and then you could coach me towards
>writing my own CGI/Forth demo.
Already installed ... Are you happy with one binary in the path
and a library sources in the current directory?
"Installation" is sooo "unsimple".
>
>For "hello world", the hard part isn't writing the code, you just
>copy the code from my demo. The hard part is figuring out how to
>make an application accessible via CGI. You could do that already
>without needing to learn any Lisp first. Then as you learn more and
>more Lisp, for each interesting demo you get working you could
>adapt it to CGI to "show it around".
>
>That left only 3.3 MB unused space in my account, so there's no way
>I could possibly untar it, so I deleted it all. If anyone knows of
>a *much* smaller Forth for FreeBSD, I could try again to see if it
>fits. By comparison, Pocket Forth that I have on my Macintosh is
>just over half of a megabyte. Why is Forth for FreeBSD about 30
>times as large??
There are simple Forth on unices.
lina for linux is only 28 kbyte. It is a statically linked binary that
reportedly runs on FreeBSD 386 unaltered. With a library of
300 kbyte source you are good to go.
You can build it on linux:
nasm lina.asm -felf -o lina.o
ld -N lina.o -o lina
OR
as lina.s
ld -N a.out -o lina
This is hello world:
cat >hello.frt
: hello ." hello world " ;
^D
lina -c hello.frt
Groetjes Albert
P.S.
Didn't you try apropos Forth ?
If I ask my debian package manager on Ubuntu about Forth I
get loads of things.
--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
Hugh Aguilar
> In Lisp you enter (+ 3 5) into read, pass the result to eval,
> pass the result to print, which prints 8.
> Conceptually you apply + to two parameters 3 and 5.
Actually, + just adds the top two datums on the parameter stack --- to
print the top datum you use a dot. The + and . correspond to Lisp's +
and PRINT pretty much exactly (except that Forth uses a stack and Lisp
uses a list).
> Conceptually you have a list (3 5 7) and want to apply 1+ to each
> element of that list, collecting the results into a new list..
In my list.4th package, I have a word called EACH that applies a
function (called a "toucher") to each element of list. I also have
some macros EACH[ ... ]EACH that allow the touching code to be put
inline, rather than made into a function. This code can generate a new
list, or it can modify the existing list in place. It can also remove
nodes from the list.
I also have FIND-NODE and FIND-PRIOR that apply a toucher function
that returns a flag, and the traversal of the loop stops when the flag
is true, and the found node (or the prior node for FIND-PRIOR) is
returned.
See my slide-rule program for an example of an application that uses
lists quite a lot. My list.4th package is supposed to be Forth's
answer to Factor's sequences --- that is one thing that I did like
about Factor.
> At the application-programmer level, I agree. But Forth would be a
> nifty way to implement a high-level language on a medium-small
> desktop computer, such as my Macintosh Performa 600 with only 8MB
> RAM, or a medium-large portable device with a similar amount of
> RAM.
I'm still dubious that the result would be more efficient or simpler
than a traditional approach. I really have to learn more about Lisp
before I comment further though. I'm still trying to figure out how to
implement Forth efficiently, so Lisp-in-Forth is definitely beyond me
at this time.
> > I'm mostly choosing Lisp because it has macros,
>
> I've programmed in Lisp since 1973, and I hardly ever feel a need
> to write a new macro, although I appreciate the macros already
> provided with Common Lisp, such as LOOP and WITH-OPEN-FILE and
> WITH-OUTPUT-TO-STRING. But someday I might find a need to write a
> new macro, so I appreciate that I'd be allowed to do so.
>
> Closures are IMO more useful for me to use, hence a reason to use
> Lisp instead of PHP for some tasks. I also rather like
> ext:run-program which is in CMUCL. The interactive debug pagkage
> with in-context REPloop is *essential*, in Lisp but missing from
> all other languages I've used.
I agree that closures are more useful than macros for application
programmers (although macros are needed for low-level support code
such as your LOOP that the application-programmer uses). Closures
can't be implemented in ANS-Forth though, and there is no plan for
including them in Forth-200x. If I write my own Forth, it will
certainly have closures as a main feature, but this will also make it
non-standard.
I'm dubious of your reference-count idea being done in Forth, but I do
think that closures are possible and worthwhile. That alone would be a
huge step forward --- maybe even salable for actual money!
I'll have to get back to you on this after giving it some more
thought.
Good analogy about walking the plank blind-folded, though! That
reminds me of the "peril-sensitive sunglasses" described in
"Hitchhiker's Guide to the Galaxy" --- they would get increasingly
dark corresponding to how much peril that you were in --- on the
assumption that when people know how much trouble they are in, they
more often make the situation worse rather than better, so it is best
if they remain blissfully ignorant. :-)
> > > > I don't know of any Forth implementation of unlimited-size integers.
> > > "This looks like a job for Superman."
> > > (This looks like a good project for any Forth expert, as you claim to be.)
> > Maybe, but that sounds like an effort to turn Forth into yet
> > another desktop-computer language.
>
> But one with a *very* small footprint that ran very fast.
I don't really get what unlimited-size integers are useful for. They
prevent overflow from happening. Isn't it possible though, for the
programmer to figure out ahead of time how big his integers have to be
so that they don't overflow, and just use fixed-size integers that are
large enough? Forth does have mixed-precision arithmetic, so the
entire arithmetic sequence doesn't have to be done at a high precision
just because one intermediate value requires a high precisions --- the
precision used can fluctuate up and down as necessary to obtain fast
speed while yet not overflowing.
> > I don't know enough about Lisp yet to follow your reference-count
> > idea.
>
> What I said about my reference-count idea had nothing to do with
> Lisp specifically.
Well, I get the *idea* of reference-count, and I agree that explicitly
freeing nodes is a major hassle. I just don't know how this can be
done in Forth, which is an untyped language. All of this seems to be
getting a long ways away from what Forth is normally used for.
Have you looked at Factor? It does this reference-count business
already, and it is similar to Forth in that it uses a parameter stack.
From what you are describing, it really sounds like you are trying to
reinvent Factor.
I tried programming in Factor but didn't much like it. It used
quotations (closures) for manipulating data on the stack, rather than
use the stack-manipulation words (NIP, TUCK, etc.) that I am familiar
with from Forth. Also, I didn't understand a lot of the concepts, and
the documentation was mostly a reference that assumed the programmer
already knew the concepts. To a large extent, the reason why I am now
learning CL is because there are beau-coup books available to help me
learn the concepts. Maybe after I learn CL and the associated
concepts, I will give Factor another try. You obviously know the
concepts though, so you should be able to learn Factor --- they do
have a friendly and helpful mailing-list group.
I really think Slava Pestov has already tackled all of the ideas that
you are thinking about, so you should familiarize yourself with his
work even if you end up writing your own system. Slava once told me
that he thought Factor could run on a processor as small as the
ColdFire, which is a medium-sized processor comparable to what you are
talking about (8M of memory). I doubt that CL could run on something
like that. I had asked him about Factor running on the eZ80, and he
said that one was too small.
For me though, something like the ColdFire is pretty big --- I am
interested in 16-bit processors such as the PIC24 --- I'm not really
the best person for you to try to get interested in your reference-
count garbage-collection idea. I still think that, for me anyway, it
is best to use Forth for micro-controllers and Lisp for desktop
computers, and not try to have a one-size-fits-all language.
> > This would only be interesting if it were done on a Forth-engine
> > (a processor that is designed to run Forth, such as the MiniForth
> > that I wrote the development system for). It might be easier to
> > build a Forth-engine than a Lisp-engine, although I don't know
> > enough about processor design to comment on this.
>
> I have no money to buy anything like that, nor space to put it if
> you give me free beta-test version to play with, so I'll pass on
> further discussion of that otherwise fine idea.
Testra is a *very* rinky-dink outfit. The boss, John Hart, is also
more than a little bit eccentric. If you get him excited about the
idea, you may be able to get Testra to do the work for free on the
basis that they will sell the hardware when you actually have
customers ready to pay, so you don't have to put any money up
yourself. The downside is that Testra would own the hardware design,
but the upside is that there would actually be some hardware, which is
more than you've got now. It is all about approaching them in the
right way, and catching them when they aren't doing anything else at
the time (this happens quite often for them, which is why I don't work
there anymore). :-)
I'm still pretty dubious that Lisp-in-Forth would be worthwhile
without a custom processor.
> > My boss at Testra (which developed the MiniForth processor) told
> > me that some Lispers once talked to him about developing a Lisp
> > processor, but nothing ever came of it.
>
> Google: "Lisp Machine"
> Circa 1989 Symbolics Inc. made them.
I know about the Lisp Machine, but I don't know if these were the same
people who approached Testra. It is the same time period though.
Mark Wooding
> I don't really get what unlimited-size integers are useful for. They
> prevent overflow from happening. Isn't it possible though, for the
> programmer to figure out ahead of time how big his integers have to be
> so that they don't overflow, and just use fixed-size integers that are
> large enough?
It's possible to do this, but not statically. Suppose you have to write
a program which accepts an integer n as input and outputs the nth
Fibonacci number F(n) as output. Suppose you know that the input is
bounded above by 2^32.
As a closed form, F(n) = 1/sqrt(5) (phi^n - phibar^n), where phi is the
golden ratio (1 + sqrt(5)/2 and phibar is its conjugate (1 - sqrt(n))/2.
This doesn't lend itself to precise calculation, but it does let us
estimate the size of the result. Then F(n) < 1/sqrt(5) phi^n; so,
taking binary logarithms, lg F(n) < n lg phi - 1/2 lg 5 < 7/10 n. This
isn't looking so good for n around 2^32. I guess we could compute the
size of the result dynamically, but it's hard to see why that would be
an improvement on having the bignum implementation work out how much
space to allocate itself.
> Forth does have mixed-precision arithmetic, so the entire arithmetic
> sequence doesn't have to be done at a high precision just because one
> intermediate value requires a high precisions --- the precision used
> can fluctuate up and down as necessary to obtain fast speed while yet
> not overflowing.
I thought that Forth only provided words for single and double precision
integer arithmetic, and not for anything bigger.
> Well, I get the *idea* of reference-count, and I agree that explicitly
> freeing nodes is a major hassle. I just don't know how this can be
> done in Forth, which is an untyped language. All of this seems to be
> getting a long ways away from what Forth is normally used for.
I agree. I like Forth (though I've not played with it very much); it's
probably the lowest level language I know of that has what I'd think of
as being adequate abstraction capabilities. And I've given some thought
as to how to make a Forth with dynamic typing and garbage collection --
the things which (to my mind) make working in Lisp even more enjoyable
-- and they simply don't fit. Forth's basic capabilities are tied quite
closely to its simple memory model; introducing dynamic types and
garbage collection complicates the memory model so much that you've
basically lost the Forthness. You'd have been better off starting with
PostScript.
-- [mdw]
Hugh Aguilar
Forth has mixed-precision words, such as */ the scalar ( a b c -- n )
that calculates (a*b)/c, with the intermediate value being double
precision. Similarly, we have M*/ ( da b c -- dn ) in which da and dn
are double-precision, and the intermediate value is triple precision.
Going the other way, we have words to divide a double-precision by a
single-precision to obtain a single-precision quotient and remainder.
There are more. There are weird gaps though. We don't have a word for
dividing a double-precision by another double-precision --- I lobbied
for this with the Forth-200x committee, but was ignored as usual. In
my novice package I provide this, but it is slow because it is written
in Forth rather than in assembly-language. I didn't write it --- I got
most of my integer arithmetic code form Nathaniel Grossman's famous
article in the Sept/Oct-1984 "Forth Dimensions." This article provided
a continued-fraction program that is used for calculating rational
approximations of floating-point constants for use by */ and M/*. For
example, here are some I calculated for pi:
macro: pi* ( s -- s-result ) \ signed single-precision
1068966896 340262731 */ ;
macro: upi* ( u -- u-result ) \ unsigned single-precision
3618458675 1151791169 u*/ ;
macro: dpi* ( d -- d-result ) \ signed double-precision
1068966896 340262731 m*/ ;
macro: udpi* ( ud -- ud-result ) \ unsigned double-precision
3083975227 1963319607 ut*/ d2* ;
Most math, including what you described regarding Fibonacci sequences,
is above my head. For the most part, I would expect that unlimited-
size integers would only be used in desktop computer programs. Forth
is primarily used in micro-controllers. We are mostly dealing with 16-
bit data (because that is the precision of ADC and DAC ports), so we
may have to use double-precision intermediate values, or maybe even
triple-precision in some cases. I can't really imagine any use for
unlimited-size integers though. Also, we generally avoid using code
that has a widely varying execution time on a micro-controller,
because the applications are real-time and we have to be careful not
to overrun the time allotment, or chaos will result --- that pretty
much precludes anything fancy like unlimited-precision arithmetic.
> > Well, I get the *idea* of reference-count, and I agree that explicitly
> > freeing nodes is a major hassle. I just don't know how this can be
> > done in Forth, which is an untyped language. All of this seems to be
> > getting a long ways away from what Forth is normally used for.
>
> I agree. I like Forth (though I've not played with it very much); it's
> probably the lowest level language I know of that has what I'd think of
> as being adequate abstraction capabilities.
What do you mean by "abstraction capabilities?"
> And I've given some thought
> as to how to make a Forth with dynamic typing and garbage collection --
> the things which (to my mind) make working in Lisp even more enjoyable
> -- and they simply don't fit. Forth's basic capabilities are tied quite
> closely to its simple memory model; introducing dynamic types and
> garbage collection complicates the memory model so much that you've
> basically lost the Forthness. You'd have been better off starting with
> PostScript.
I've only written one PostScript program in my life, and I learned
PostScript specifically for this (and I stopped reading as soon as I
learned enough for my program). This was the slide-rule program; the
PostScript was generated by a Forth program. I originally wrote the
program to generate gcode for a CNC milling machine (and I still think
this is reasonable for onesy-twosy manufacture), but then I found out
(from Don Lancaster) about photo-lithography, that can be used for
mass-production, so I upgraded to generate PostScript. My first CL
program will most likely be a port of the slide-rule program (although
I may drop the gcode and add SVG, along with a GUI emulator).
I didn't much like PostScript because it wasn't as close to Forth as I
expected. There were no immediate words. There weren't even basic
stack-manipulation words. All in all, it looked like something that
could be generated by another program, but not something that I would
want to program in manually. I got the impression that the people who
designed PostScript were enamored to Forth because it was easy to
implement, but didn't have very much practical experience with Forth.
Some people (Don Lancaster) like PostScript though, so maybe I would
too if I learned more.
As I told Robert Maas, I would use Factor if I wanted a Forth-like
language (with a parameter stack) that had dynamic-OOP and garbage-
collection --- or I would just use CL for desktop programming (which
is what I'm doing). Factor has drifted so far from Forth now, that
there isn't that much attraction for me anymore --- I don't think it
would be any easier to port Forth code to Factor than to CL, so I
might as well go with CL.
Tim Bradshaw
> I don't really get what unlimited-size integers are useful for. They
> prevent overflow from happening. Isn't it possible though, for the
> programmer to figure out ahead of time how big his integers have to be
> so that they don't overflow, and just use fixed-size integers that are
> large enough?
If you want to write an algebra system, for instance you need to be
able to do correct arithmetic, and this means you don't want some
arbitrary point at which the system just gives up and (if you're lucky)
throws an error or (if you're not) just silently returns the wrong
answer. This means you don't want integers of limited precision, and
you also want division to give the right answer: 1/2 is not 0, 1, 2, or
some stupid machine-limited "float" type which will then never compare
properly with anything else, it's 1/2. sqrt(-1) is not an error, it's
i. It's pretty easy to show that you can't know from the statement of
even quite simple problems how complex the solution will be, how
complex the intermediate working required to get to the solution (which
is very often hugely larger than the solution) will be, or in fact
whether there is a solution at all. So it is definitely not safe to
decide that you'll never see large integers or ratios of them, because
you will.
Hugh Aguilar
> you also want division to give the right answer: 1/2 is not 0, 1, 2, or
> some stupid machine-limited "float" type which will then never compare
> properly with anything else, it's 1/2.
In my novice package I do provide a ratio type, with a double-
precision numerator and single-precision denominator. It reduces
fractions to their simplest term.
I had to use a single-precision denominator because ANS-Forth doesn't
provide a double/double division.
It can overflow, but it does solve the problem of repeating binaries
in floats, so it is a step in the right direction. I borrowed the idea
of a ratio data-type from Factor, although I think other languages
have it as well.
Albert van der Horst
Hugh Aguilar <hughag...@yahoo.com> wrote:
<SNIP>
>I didn't much like PostScript because it wasn't as close to Forth as I
>expected. There were no immediate words. There weren't even basic
>stack-manipulation words. All in all, it looked like something that
>could be generated by another program, but not something that I would
>want to program in manually. I got the impression that the people who
>designed PostScript were enamored to Forth because it was easy to
>implement, but didn't have very much practical experience with Forth.
>Some people (Don Lancaster) like PostScript though, so maybe I would
>too if I learned more.
If by stack manipulation words you mean ``DUP DROP SWAP ROLL ''
they are called `` dup pop exch roll '' in PostScript.
[Not many people will read this, but I couldn't let this pass. ]
Groetjes Albert
Robert Maas, http://tinyurl.com/uh3t
> From: Hugh Aguilar <hughaguila...@yahoo.com>
> Actually, + just adds the top two datums on the parameter stack
> --- to print the top datum you use a dot.
Ooops, yes. I get so used to Lisp automatically printing the result
of each REP-loop (i.e. REP not just RE), and it's been so many
years since I tried to program anything in Forth, that I forgot
that Forth doesn't show you the result unless and until you dot it.
> The + and . correspond to Lisp's + and PRINT pretty much exactly
Yup.
> (except that Forth uses a stack and Lisp uses a list).
Conceptually, i.e. ignoring the details of low-level
implementation, they are essentially the same. That is if you are
writing an application program, translating from one language to
the other, Forth's and Lisp's + are directly corresponding, either
translates to the other (in the case where Lisp's + is applied to
exactly two paramters. Lisp's + is more general, applying to
however many parameters you give it, but that can't be done in
Forth because Forth doesn't use parens, so there's no way for the +
word to know how many additional paramters are supposed to be
eaten, so it is fixed to eat exactly two).
Older Lisps had a function PLUS2 which was the twp-arg case, and
PLUS which was a macro that expanded to nested calls to PLUS2,
whereupon PLUS2 would be an exact functional equivalent to Forth's
+ word.
> > =A0 Conceptually you have a list (3 5 7) and want to apply 1+ to each
> > =A0 =A0element of that list, collecting the results into a new list..
> In my list.4th package, I have a word called EACH that applies a
> function (called a "toucher") to each element of list.
Ah, good, you're catching on to the proper conceptual jargon for
what we are talking about, *apply*ing a function to each element of
a list.
> I also have some macros EACH[ ... ]EACH that allow the touching
> code to be put inline, rather than made into a function.
Rather than a *word* I presume you mean.
Of course conceptually it's a function.
Now the MAPCAR function in Lisp not only applies the function to
each element in the list, but it collects the corresponding
return-value-from-function into a new list. Does your EACH
word/function do that? Does your EACH[ ... ]EACH likewise build a
new list of the return values?
> This code can generate a new list, or it can modify the existing
> list in place.
Oops, I should have read ahead before asking. Amended question:
What determines whether EACH generates new list, or modify the old
list, or neither? Is there a global configuration flag that is set
to affect how EACH works?
> > At the application-programmer level, I agree. But Forth would be a
> > nifty way to implement a high-level language on a medium-small
> > desktop computer, such as my Macintosh Performa 600 with only 8MB
> > RAM, or a medium-large portable device with a similar amount of
> > RAM.
> I'm still dubious that the result would be more efficient or simpler
> than a traditional approach.
That main reason for implementing Lisp on top of Forth is *not* to
create a version of Lisp that is faster than versions coded
directly in C. Rather the reason is to make easier for people like
me to do the process of implementing Lisp, so that per the Chinese
proverb a thousand flowers can bloom of various people like me
experimenting with each of our various ideas how to design a
storage-management system for list processing. I expect it'd take
just a couple months to implement the essential parts of Lisp using
Forth, but a year or so trying to code it from scratch in C.
> I really have to learn more about Lisp before I comment further though.
As I said before, if you are doing any sort of processing linked
lists, then conceptually you already know enough about list
processing to understand my discussions of reference count. You
don't really need to know *anything* about Lisp per se to
understand that there is a function for building a cell from two
given pointers, and functions to extract one or the other pointer
from such a 2-cell. You don't even need to know that the
constructor for 2-cells is called CONS and the extractors are
called CAR and CDR, although you knowing that allows me to use that
jargon in my abstract discussion rather than calling these
functions Make2PartCell and ExtractFirstPart and ExtractSecondPart
respectively. A paragraph that mentionned CONS/CAR/CDR many times
would be virtually illegible with those long names instead of the
short Lisp jargon names.
> I'm still trying to figure out how to implement Forth
> efficiently, so Lisp-in-Forth is definitely beyond me at this time.
But Forth is already implemented on my Mac and lots of other
machines. Why do you have to *implement* Forth, rather than just
use it, build on top of it? Are the existing implementations not
efficient enough in your opinion?
> I agree that closures are more useful than macros for application
> programmers (although macros are needed for low-level support code
> such as your LOOP that the application-programmer uses).
I wrote+posted an essay sometime in the past five years about the
sequential steps in developing a methologody for solving a specific
class of problems. It went something like this:
- Re-invent the wheel by re-solving the problem each time you
encounter another instance of the problem.
- "Design Pattern" - Copy-and-paste a template that reminds you how
you solved the problem before, and then substitute the
non-boilerplate parts of that pattern, to manually customize the
problem-solution.
- "Function" - Write general code that takes parameters and uses
them to solve the instance of the problem, but the syntax of
this function call might be sorta user-unfriendly.
- "Macro" - Write a utilty that takes as input the variable parts
and automatically merges them with the boilerplate to yield the
customized instance of the class of solutions. Now the syntax is
much more user-friendly, but still restricted to the general
syntax of the language, i.e. s-expressions.
- "Reader Macro" - Define one of the otherwise unused
(syntactically disallowed) characters to be a dispatch character
to invoke a special syntax to follow it, such as #(2 3 5 7) to
represent a vector of first four primes. Now you have notation
that isn't s-expressions, although the pieces within it must be
atoms or s-expressions.
- "Application-Specific Language" - Add a parser for your special
syntax that translates to the instance. Now you can use *any*
syntax you want, no longer even vaguely similar to s-expressions
if you choose. For example, you could have a DOM parser for
COBOL or Java or public-transit schedules or HTML or tables of
connections for circuit boards, then the resultant parse-tree
can be compiled or interpreted.
> Closures can't be implemented in ANS-Forth though,
Why not?? I'm not as sure of this as I'm sure I could do reference
count storage management, but a couple years ago I believe I
figured out a way to implement closures by the obvious technique of
an association list for bindings, but *two* (2) different such
association lists, one for global/special bindings, and one for
lexical bindings. The trick is that when you descend into nested
forms, you keep both lists of bindings, and push a new binding onto
the appropriate bindings list, but when you call a function you
re-bind the lexical binding list to NIL but keep the special
binding list unchanged across the call. When you return from a
function, you restore the old lexical binding list to what it was
just before the function call. When you create a lexical closure,
you encapsulate the lexical-binding list in the closure-function,
so that when you call that closure the lexical-binding list is
initialized to that encapsulated binding list rather than to NIL.
I think that's all you need to do to make it work. (For non-local
returns such as THROW -> CATCH and sorta-nonlocal returns such as
RETURN-FROM -> BLOCK, you need to unwind the stack, popping items
of the appropriate stack, and restoring the old lexical binding
list whenever you cross a function-call boundary which happens only
with non-local returns not with RETURN-FROM.)
Now that I believe I have a way to implement list-processing, with
reference-count storage management, within Forth, and McCarthy
showed in 1959 that it's possible to write programs using nested
lists and then to emulate such a program by simply calling EVAL on
it, using a association list to hold all current special bindings
as the emulator runs, and combining that with the previous
paragraph showing how to implement closures correctly within an
interpretor, just by using two instead of one association list for
two kinds of bindings, I believe that allows interpreted closures
to be implemented within Forth.
> I'm dubious of your reference-count idea being done in Forth,
What alternative do you have in Forth? After your program builds
linked-list structure, and is done with it, what does your program do?
- It never is recycled, just uses more and more memory until you run out?
- Application programmer must *manually* code a "free" call at the
point where it'll be needed, just like when programming in C?
- What else other than reference count or mark-and-sweep GC??
> Good analogy about walking the plank blind-folded, though! That
> reminds me of the "peril-sensitive sunglasses" described in
> "Hitchhiker's Guide to the Galaxy" --- they would get
> increasingly dark corresponding to how much peril that you were
> in --- on the assumption that when people know how much trouble
> they are in, they more often make the situation worse rather than
> better, so it is best if they remain blissfully ignorant. :-)
IMO that's a horrible attitude. Imagine if automobiles were
designed so that whenever they started to skid on ice or snow, or
whenever you hit the brakes hard, or whenever the CHECK ENGINE or
FUEL LOW light goes on, the windshield would automatically turn
black so you can't see which way your car is going?
IMO it's better to teach student drivers how to react in
emergencies, using driving simulators of course instead of live
automobiles until after the student has learned. I believe airline
pilots do this sort of thing in training simulators. Imagine if
instead, airline pilots had their instruments go dark and their
windshield go opaque whenever the plane's computer detected a
problem??
> I don't really get what unlimited-size integers are useful for.
> They prevent overflow from happening. Isn't it possible though,
> for the programmer to figure out ahead of time how big his
> integers have to be so that they don't overflow, and just use
> fixed-size integers that are large enough?
One of the important lessons of both mathematics and software is
that it's often easier to solve a problem in general than for a
specific value of a parameter. In this case, it's easier to write a
library to do arbitrary precision arithmetic, than to write a set
of different-precision arithmetics, each library tuned to one
particular size of numbers. For example, for public-key
cryptosystem I currently use 210-digit (697-bit) integers as
modulus and exponents and remainders. And as temporaries during
the process of modular multiplication, I have to deal with
420-digit (1394-bit) integers. It would be a pain if I had to find
a special-purpose library for dealing with those two specific
sizes, unlikely anybody had ever invented such a library before, so
I'd need to write my own library, which would take years to get
right, instead of just using the arbitrary length big-integers
present in Lisp. Does Forth support multiplication of two 697-bit
integers to yield a 1394-bit integer, and dividing a 1394-bit
integer by a 697-bit integer to yield a 697-bit remainder?
> Forth does have mixed-precision arithmetic, so the entire
> arithmetic sequence doesn't have to be done at a high precision
> just because one intermediate value requires a high precisions
> --- the precision used can fluctuate up and down as necessary to
> obtain fast speed while yet not overflowing.
Does Forth support the multiplication and division I specified
in the previous paragraph?
> > > I don't know enough about Lisp yet to follow your reference-count
> > > idea.
> > What I said about my reference-count idea had nothing to do with
> > Lisp specifically.
> Well, I get the *idea* of reference-count, and I agree that
> explicitly freeing nodes is a major hassle. I just don't know how
> this can be done in Forth, which is an untyped language. All of
> this seems to be getting a long ways away from what Forth is
> normally used for.
Forth is a general purpose language. It can be used for *new*
things it wasn't normally used for earlier. Right?
Machine language is untyped. You have memory addresses, and if you
just look at a random block of memory you can't really be sure how
the data in that block of memory is supposed to be interpreted. And
yet, using machine language, it's possible to implement Lisp, which
has data restricted to specific formats to allow automatic
type-testing at runtime. You do exactly the same thing when
implementing Lisp using Forth. You write "constructor" words for
each of the various types of atomic data you want it to be able to
construct. You write "constructor" words for each type of container
you want it to be able to construct. You write accessors for each
of the parts of each of the types of containers. You write a
type-tester that looks at memory starting with the first byte of an
atomic datum or a container, in particular looks at tag bits at the
start of the object, and returns a code telling what type that
object is. You code your polymorphic functions to accept a pointer
as (each) parameter, pass that pointer to the type-tester function,
and depending on the return value dispatch to various special-type
code. For example, PRINT reads different amounts of memory and
interprets what it sees differently depending on what type of data
is there.
As a starter, define two types of atomic data:
- 30-bit integers, with high-order tag bits of 00 for positive and
11 for 2's-complement negative.
- Short USASCII strings of text, where first byte has tag bits 01
followed by a 6-bit character-count followed by that many
consecutive bytes.
Define one type of container:
- 2cell (i.e. "CONS" cell), where first byte is exactly 10000000 in
binary, then immediately follows the two pointers.
Use the null string, instead of a special NIL atom, to mark the
CDR-end of a linked list. Thus a linked-list of the first four
primes would print using dotted notation as:
(2 . (3 . (5 . (7 . ""))))
> Have you looked at Factor?
"Factor" is such a common word in mathematics and English that I
wouldn't know how to find whatever you're talking about. But no I
probably haven't chanced upon what you're talking about. URL please
for something that primarily describes what it's all about?
Google search: [Factor] First match is http://en.wikipedia.org/wiki/Factor
which lists many meanings, including:
In computer science and information technology:
* Factor (programming language), a concatenative stack-oriented
programming language
http://en.wikipedia.org/wiki/Factor_(programming_language)
Is that what you are referring to? I'm actually proposing only a
set of Forth words that manage list-processing with reference
count, *not* a whole new language (syntax). But if I wanted to play
with it, this seems to be the download I'd need for FreeBSD:
http://builds.factorcode.org/release?os=freebsd&cpu=x86.64
But they don't have any version at all that run on my Mac, so it
totally defeats my purpose of having something on my Mac in which I
could play with implementing list processing.
> It does this reference-count business already, and it is similar
> to Forth in that it uses a parameter stack. From what you are
> describing, it really sounds like you are trying to reinvent
> Factor.
No, but perhaps something vaguely like it that can be installed
within Pocket Forth on Macintosh System 7.5.5.
> You obviously know the concepts though, so you should be able to
> learn Factor
Except that it doesn't run on my Mac so it's of no use to me.
> I really think Slava Pestov has already tackled all of the ideas
> that you are thinking about,
No. He hand-codes reference-count within C++, whereas I want to
implement reference-count within Forth instead.
> Slava once told me that he thought Factor could run on a
> processor as small as the ColdFire, which is a medium-sized
> processor comparable to what you are talking about (8M of memory).
Unfortunately he hasn't bothered to build it for 68030 CPU with no
floating-point unit and with ROM version 67C.
> I still think that, for me anyway, it is best to use Forth for
> micro-controllers and Lisp for desktop computers, and not try to
> have a one-size-fits-all language.
Unfortunately there's no free version of Lisp that works properly
on my Mac, and I can't afford to pay $400 for Macintosh Allegro
Common Lisp version 1.3.2. (I had 1.2.2 which ran fine on my
Macintosh Plus, but when I tried to run it on my Mac Performa it
froze the machine as soon as it started.)
Robert Maas, http://tinyurl.com/uh3t
> ... I've given some thought as to how to make a Forth with
> dynamic typing and garbage collection -- the things which (to my
> mind) make working in Lisp even more enjoyable -- and they simply
> don't fit. Forth's basic capabilities are tied quite closely to
> its simple memory model; introducing dynamic types and garbage
> collection complicates the memory model so much that you've
> basically lost the Forthness. You'd have been better off starting
> with PostScript.
Pocket Forth is a free Forth interactive-interpretor that runs fine
on my Macintosh "Performa 600" (68030-CPU) System 7.5.5.
Is there a free Postscript interactive-interpretor that runs on the
same machine+system? If not, then Postscript isn't even an option
for me here.
Robert Maas, http://tinyurl.com/uh3t
> >Maybe you could write one for me and install it on your server and
> >show it to me so that I can add it to my collection? Or if you know
> >where to find an already-installed Forth on FreeBSD, you could tell
> >me where to find it here, and then you could coach me towards
> >writing my own CGI/Forth demo.
> Already installed
What's the URL of your demo so that I can try it?
> ... Are you happy with one binary in the path and a library
> sources in the current directory? "Installation" is sooo
> "unsimple".
If I'm just clicking on a URL to your demo, none of that matter.
If I'm going to copy your demo to my FreeBSD account and try to get
it running here, ugh, pain, but maybe worth it.
> There are simple Forth on unices.
> lina for linux is only 28 kbyte.
> You can build it on linux:
No I can't. I have no access to any linux that has any way to
connect to the net to download lina. (I have a RedHat Linux laptop
whose modem stopped working several years ago, and there's nobody
in Sunnyvale who knows Linux who is willing to help me diagnose the
modem problem, where it refuses to go on-hook because it says it's
already on-hook, and I don't know whether it's a lock file that is
wedged or a bug in the OS or the modem itself burned out.)
> Didn't you try apropos Forth ?
Trying it now:
> apropos Forth
Forth: nothing appropriate
> apropos forth
forth: nothing appropriate
> apropos lisp
cmucl(1) - CMU Common Lisp
lisp(1) - CMU Common Lisp programming environment
> apropos Python
python(1) - an interpreted, interactive, object-oriented programming language
> whereis python
python: /usr/local/bin/python /usr/local/man/man1/python.1.gz /usr/ports/lang/python
Andrew Haley
>
> I agree. I like Forth (though I've not played with it very much); it's
> probably the lowest level language I know of that has what I'd think of
> as being adequate abstraction capabilities. And I've given some thought
> as to how to make a Forth with dynamic typing and garbage collection --
> the things which (to my mind) make working in Lisp even more enjoyable
> -- and they simply don't fit. Forth's basic capabilities are tied quite
> closely to its simple memory model; introducing dynamic types and
> garbage collection complicates the memory model so much that you've
> basically lost the Forthness.
I don't think that's actually true: as an example of how you might do
it, HP's System RPL is pretty close. There is a paper in the Journal
of Forth Application And Research from 1988 that explains the
low-level details of how it was done. It's very Forth.
Garbage collection should be pretty easy, though. A conservative GC
can scan the stack and the dictionary, and this is pretty
straightforward to implement.
Andrew.
Doug Hoffman
>> From: m...@distorted.org.uk (Mark Wooding)
>> ... I've given some thought as to how to make a Forth with
>> dynamic typing and garbage collection -- the things which (to my
>> mind) make working in Lisp even more enjoyable -- and they simply
>> don't fit. Forth's basic capabilities are tied quite closely to
>> its simple memory model; introducing dynamic types and garbage
>> collection complicates the memory model so much that you've
>> basically lost the Forthness. You'd have been better off starting
>> with PostScript.
>
> Pocket Forth is a free Forth interactive-interpretor that runs fine
> on my Macintosh "Performa 600" (68030-CPU) System 7.5.5.
Mops is another free Forth that will run fine on your Mac. Mops has a
very complete dynamic OOP system built in (including multiple
inheritance). It may also have garbage collection (the later version
for OS X definitely has gc, can't remember if the 680x0 version does).
-Doug
Albert van der Horst
Robert Maas, http://tinyurl.com/uh3t <seeWeb...@rem.intarweb.org> wrote:
>> >Maybe you could write one for me and install it on your server and
>> >show it to me so that I can add it to my collection? Or if you know
>> >where to find an already-installed Forth on FreeBSD, you could tell
>> >me where to find it here, and then you could coach me towards
>> >writing my own CGI/Forth demo.
>> Already installed
>
>What's the URL of your demo so that I can try it?
I'm reluctant to publish it here, but you can get it if you
e-mail me.
I can reveal the source of the script though:
-------------------8<-------------------
#!/bin/lina5 -s
"<HTML> <BODY> <PRE> Hello World </PRE> </BODY> </HTML>" TYPE CR
-------------------8<-------------------
>
>> ... Are you happy with one binary in the path and a library
>> sources in the current directory? "Installation" is sooo
>> "unsimple".
>
>If I'm just clicking on a URL to your demo, none of that matter.
>If I'm going to copy your demo to my FreeBSD account and try to get
>it running here, ugh, pain, but maybe worth it.
>
>> There are simple Forth on unices.
>> lina for linux is only 28 kbyte.
>> You can build it on linux:
>
>No I can't. I have no access to any linux that has any way to
>connect to the net to download lina. (I have a RedHat Linux laptop
>whose modem stopped working several years ago, and there's nobody
>in Sunnyvale who knows Linux who is willing to help me diagnose the
>modem problem, where it refuses to go on-hook because it says it's
>already on-hook, and I don't know whether it's a lock file that is
>wedged or a bug in the OS or the modem itself burned out.)
I told you how to build it in order to show how simple that is,
not because there is any need to do it. Sorry for the confusion.
If you don't have a linux machine: don't panic!
There are other ways to access the Internet.
Get access to a Windows machine. (Don't tell me that your mother
has no Windows machine to e-mail her grand children.)
So here is the step by step download version:
Surf to http://home.hccnet.nl/a.w.m.van.der.horst/lina.html
The first link is an archive, download it.
Put the file on your BSD machine.
A>tar xfz lina-4.0.6.tar.gz
A>cd lina-4.0.6
<Optionally study the pdf, browse the html,
or print the postscript manual>
A>
A>lina
<welcome message>
You can now try out some well-known Forth commands:
WORDS
1 300 INDEX
1 2 + .
Instructions are not complete without an "uninstall".
A> rm -r lina-4.0.6*
Enjoy.
Groetjes Albert
Mark Wooding
> On Nov 24, 12:25 pm, m...@distorted.org.uk (Mark Wooding) wrote:
> > I like Forth (though I've not played with it very much); it's
> > probably the lowest level language I know of that has what I'd think
> > of as being adequate abstraction capabilities.
>
> What do you mean by "abstraction capabilities?"
An abstraction mechanism lets you capture the essence of a `pattern',
capture its essence, and then invoke it, explaining only what's unusual
about this particular instance. A function is a common kind of
abstraction, but functions can only abstract over patterns of
computations of values. Making more kinds of things be first-class
values extends the reach of functional abstraction, but there are
limits: e.g., functional arguments usually have to be decorated in some
way to make it clear that their contents aren't to be evaluated
immediately, and the weight of this notation can become prohibitive.
Forth's words are an obvious example of an abstraction mechanism.
`Ordinary' words (I forget the Forth technical term), which just append
execution semantics to a definition in progress, are Forth's analogue to
conventional functions (more or less). You can get a fair way with
these kinds of words, but the limitations would become apparent to
advanced users, at least. But Forth doesn't stop there: immediate words
which combine compile- and execution-time semantics can be used to
produce very powerful effects, and build convenient new languages out of
very primitive parts. (You know all this. I'm writing it anyway, (a)
for the Lisp users' benefit, and (b) as a familiar example of a powerful
abstraction tool.)
Forth, as is used in real life, itself is (or at least can be) such a
language, built from some very simple memory-management tools: I think I
really started to understand where Forth was coming from by reading the
source code to a simple Forth implementation written in i386 assembler.
It seemed to me at the time that the character of Forth arises as a
combination of the powerful abstraction of immediate words, the openness
of the compilation and execution processes, and the simplicity of the
communication mechanisms (the various stacks and the ALLOT memory
space), all of which fit together beautifully to produce an extremely
capable language from almost nothing at all.
> > And I've given some thought as to how to make a Forth with dynamic
> > typing and garbage collection -- the things which (to my mind) make
> > working in Lisp even more enjoyable -- and they simply don't fit.
> > Forth's basic capabilities are tied quite closely to its simple
> > memory model; introducing dynamic types and garbage collection
> > complicates the memory model so much that you've basically lost the
> > Forthness. You'd have been better off starting with PostScript.
>
> I didn't much like PostScript because it wasn't as close to Forth as I
> expected. There were no immediate words. There weren't even basic
> stack-manipulation words. All in all, it looked like something that
> could be generated by another program, but not something that I would
> want to program in manually.
I mentioned it as a (presumably) familiar example of a stack-based
concatenative language with a Lisp-like memory model, rather than as a
glowing recommendation; I failed to make this clear, so I'm sorry about
that. My point was really that such things are rather alien to the way
Forth constructs definitions and similar, and that these mechanisms are
fundamental to Forth's character -- so much so that to change them means
that you don't really have Forth any more.
> As I told Robert Maas, I would use Factor if I wanted a Forth-like
> language (with a parameter stack) that had dynamic-OOP and garbage-
> collection --- or I would just use CL for desktop programming (which
> is what I'm doing).
Others have also mentioned Factor, which looks like a better attempt.
I've started reading the documentation, but don't have anything coherent
to say about it yet except to thank you and others for the pointer.
> Factor has drifted so far from Forth now, that there isn't that much
> attraction for me anymore --- I don't think it would be any easier to
> port Forth code to Factor than to CL, so I might as well go with CL.
This looks to be in line with my speculation above.
It's probably not clear: I /want/ to be wrong. I'd dearly like to be
able to capture the Forthness of Forth in a richer world of dynamic
objects. And it may be that Factor is the right answer; it certainly
seems like it's worth a look. My own deliberations reached the
conclusion that the two were incompatible in a fairly fundamental way;
maybe I was mistaken, and maybe Factor is the solution I was looking
for.
But I also like Common Lisp, and I certainly wouldn't wish to discourage
anyone from trying or using it.
-- [mdw]
Paul Rubin
predominantly a Lisp discussion.
2. You can't really use reference counting for Lisp GC, because of the
possibility of cyclic lists. You need a tracing garbage collector.
3. Lisp is really quite easy to implement if you just want a simple
interpreter without the libraries and creature comforts of Common Lisp.
I wrote one in C in a couple of weeks a long time ago, that was embedded
in a commercial product and proved to be quite usable.
4. CLISP (a small Common Lisp implementation that's been around for a
while) should run fine on 68030-class hardware. I don't know if there
is a Mac port, but you could always do one.
5. Similarly, gforth should run fine on that class of hardware.
6. Traditional Forth doesn't have bignums. Mixed-precision arithmetic
means single and double precision, basically.
7. Why on earth can't you get a more modern computer? You can probably
scrounge a fairly powerful x86 box from a garbage can and run your
favorite Linux distro on it.
Rob Warnock
+---------------
| Pocket Forth is a free Forth interactive-interpretor that runs fine
| on my Macintosh "Performa 600" (68030-CPU) System 7.5.5.
|
| Is there a free Postscript interactive-interpretor that runs on the
| same machine+system?
Ghostscript, maybe?
http://pages.cs.wisc.edu/~ghost/
When you run it with no args, you can type raw Postscript
into its stdin...
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Robert Maas, http://tinyurl.com/uh3t
> cat >hello.frt
> : hello ." hello world " ;
> ^D
." seems to be an immediate word that scans input and prints it on
the fly. If you wanted instead to separately:
- Scan input to make string in the heap, and just put the pointer on the stack.
- *then* print via top of stack.
what would be the code? I'll take a wild guess:
: hello " hello world " . ;
How close is that to correct?
Robert Maas, http://tinyurl.com/uh3t
> >> ... You'd have been better off starting with PostScript.
(question where to find PostScript that runs on Macintosh)
> > Pocket Forth is a free Forth interactive-interpretor that runs fine
> > on my Macintosh "Performa 600" (68030-CPU) System 7.5.5.
> Mops is another free Forth that will run fine on your Mac.
How will that help me use PostScript instead of Forth??
I already have Pocket Forth. I don't need another Forth for my Mac.
If you want me to switch to PostScript on my Mac, then where is a
PostScript that runs on my Mac??