Comparison Lisp <--> Beta
A. The BETA language
1. Has an incredible symmetry between data and executable program code.
Much better than Lisp. Syntax is such that execution goes strictly
from left to right, except for loops.
2. Lexically scoped, but a module system ("fragment" system) permits
to put parts of a program into separate files - effectively splitting
interface and implementation.
3. Multiple values, but symmetrically for both input (function arguments)
and output (function return values). A program can be viewed as moving
data around between black boxes.
4. PROGN, LET, Lisp closures, list objects, defstruct objects, CLOS instances
all correspond to "pattern"s.
5. Symmetry data/code provides automatically for different kinds of
inheritance:
outer level inner level
----------- -----------
code code local function definitions
data code local variables
code data ??
data data defstruct :include
6. "Part objects" cover the issues
- local functions with lexical scope,
- defstruct :include,
- defclass subclassing, but only single inheritance.
7. The ":<" token makes up
- generic classes (not present in Lisp, you would have to use
a DEFCLASS in a non-null lexical environment),
- generic functions,
- &key parameters for functions.
8. The "::<" token specifies
- subclassing,
- methods for generic functions,
- keyword arguments for functions.
9. CALL-NEXT-METHOD goes the other way around: the most general method
determines the general behaviour, the most specific method only
plays the role of a fixup.
10. Compile-time typing where possible, run-time tying where necessary.
For example, you can put functions into plain lists or into lists
of functions. The latter saves some run-time checks. Of course,
general lists and lists of functions share the same definitions for
insert, delete etc.
11. Concurrency, i.e. deterministic parallelism. (Would make
WITH-PACKAGE-ITERATOR and WITH-HASH-TABLE-ITERATOR obsolete in CL.)
12. No multiple inheritance.
No generic functions with more than one dispatching argument.
The macro system is pretty much limited, violates lexical scoping,
therefore error prone to use.
B. The Mjolner BETA implementation
1. It is as easy to generate machine code for Beta programs than for Lisp.
2. Generates standalone executables. Hello-world is just 100 KB on Linux.
3. Automatic garbage collection (generational, scavenging).
4. Speed:
consing up 1000 closures into a list
Mjolner 0.049 sec
CLISP 0.064 sec
GCL 0.168 sec
some integer array hacking
C 4.2 sec
Mjolner 111 sec
GCL 288 sec
CLISP 415 sec
(All timings on a 486/33.)
5. Libraries for all kinds of container classes, streams, processes,
exceptions, X11, Motif.
C. The grains of salt:
1. The syntax is orthogonal, but you have to get used to it.
2. Unhygienic macros ("super patterns").
3. No nested comments.
4. Need a dictionary for the words "pattern", "part object", "virtual pattern".
For more information about BETA, look into the comp.lang.beta newsgroup.
Disclaimer: I have no relation with Mjolner Informatics, except that they gave
me a copy of their Mjolner compiler for free.
Bruno Haible
hai...@ma2s2.mathematik.uni-karlsruhe.de
> 4. PROGN, LET, Lisp closures, list objects, defstruct objects, CLOS instances
> all correspond to "pattern"s.
So what are these "patterns" anyway? It sounds as if they are very
close if not identical to lisp closures. After all, can't each of the
above lisp stuff can be implemented as sugar for closures.
rodrigo vanegas
r...@cs.brown.edu
Bruno> Since a new language called BETA is gaining attention, which
Bruno> has some features Lisp is proud of, I attempt a comparison
Bruno> between Beta and Lisp.
I understand that this group is dedicated for BETA but if
subject says "Comparison: Beta - Lisp". I didn't find too much
comparison, I found mostly list of features that are common in
both languges. It would be nice if somebody posted real
comparison, as atleast only thing I know about Beta is that it
has "pattern"s.
Petri
--
--------------------------------------------------------------------------
Petri Virkkula | Internet: Petri.V...@hut.fi
JMT 11 E 125 | X.400 : /G=Petri/S=Virkkula/O=hut/ADMD=fumail/C=fi/
02150 Espoo | Voice : +358 0 455 1277
FINLAND |
--------------------------------------------------------------------------
You're basically pretty much correct. A pattern is essentially the
same thing as a closure, the primary difference being that a pattern
is static. Essentially, a pattern is a uniform code construct which
will be instantiated into a closure at runtime.
To make a jump backwards to the initial comparison idea, the key
conceptual difference between Beta and Lisp is that Beta is very
static: patterns are static entities which are compiled into
programs. At runtime, a pattern is instantiated into an "object"
which, depending on how it's used, may be a value or a procedure, or
any combination thereof (just like a closure, because it IS a
closure).
The important differences come about because of three things:
<1> Static typing - in Beta, the types of variables are always declared
statically. Programs in Beta is very static, which makes it very
different from the dynamic nature of lisp programming.
<2> Single inheritance- the Beta object model uses only single inheritance.
The designers decided that rather than try to work out a system for
resolving the confusion caused by MI (namespace collisions, repeated
inheritance, etc.), it was better to do without it. I don't necessarily
agree with them, but it did result in keeping Beta simple.
<3> Virtual patterns - the object model is rather different. Instead of
the CLOS model where a child method overrides a parent method, Beta
uses the Simula model, where the child extends the parent method. The
parent implementation of a method contains calls to inner, which are
dynamically bound to the correct extension for the actual child type.
Going further, since everything (functions, procedures, methods, values)
is just a pattern, the virtual pattern idea can be applied to *any*
method at all. This results in a *very* interesting program model,
where you can write any procedure to be dynamically extensible. This can
actually be used to write lambda expressions! It's quite elegant...
<MC>
--
|| Mark Craig Chu-Carroll: <MC> || "I'm not dumb,
|| CIS Grad, U of Delaware || I just have a command of thoroughly
|| PGP key available by finger || useless information."
|| car...@cis.udel.edu || -Calvin
You're basically pretty much correct. A pattern is essentially the
same thing as a closure, the primary difference being that a pattern
is static. Essentially, a pattern is a uniform code construct which
will be instantiated into a closure at runtime.
OK, so let's equate a pattern with a lambda expression which is
instantiated into a closure at runtime.
To make a jump backwards to the initial comparison idea, the key
conceptual difference between Beta and Lisp is that Beta is very
static: patterns are static entities which are compiled into
programs.
And lambda expressions are static entities which are compiled into
functions.
The important differences come about because of three things:
<1> Static typing - in Beta, the types of variables are always declared
statically. Programs in Beta is very static, which makes it very
different from the dynamic nature of lisp programming.
Agreed, although it wouldn't take much of a stretch to imagine a lisp
which required type declarations. Admittedly, most lisp users would
hate that.
<2> Single inheritance- the Beta object model uses only single inheritance.
The designers decided that rather than try to work out a system for
resolving the confusion caused by MI (namespace collisions, repeated
inheritance, etc.), it was better to do without it. I don't necessarily
agree with them, but it did result in keeping Beta simple.
But it looked to me like the object system that Beta uses is one based
on closures. That sort of object system has been used in lisp and has
the same sort of single inheritance. For the same matter, I assume
that one could build a CLOS type multiple inheritance object system
in Beta which did not use closures in such a direct way.
<3> Virtual patterns - the object model is rather different. Instead of
the CLOS model where a child method overrides a parent method, Beta
uses the Simula model, where the child extends the parent method. The
parent implementation of a method contains calls to inner, which are
dynamically bound to the correct extension for the actual child type.
See my last comment.
Going further, since everything (functions, procedures, methods, values)
is just a pattern, the virtual pattern idea can be applied to *any*
method at all. This results in a *very* interesting program model,
where you can write any procedure to be dynamically extensible. This can
actually be used to write lambda expressions! It's quite elegant...
Could you give an example here which doesn't look like a closure. I
guess I'm looking for something which would not have a straightforward
translation into lisp. If there's something new here I'd really like
to know.
-Mark
--
Mark Friedman
NASA-Ames Research Center
MS 269-2
Moffett Field, CA 94035-1000
vmail: (415) 604-0573
email: bo...@ptolemy.arc.nasa.gov
: ...
: some integer array hacking
: C 4.2 sec
: Mjolner 111 sec
: GCL 288 sec
: CLISP 415 sec
: (All timings on a 486/33.)
: ...
Are these numbers right? I've seriously used GCL and CLISP myself and
had some arguments with a "true believer Lisper" who thought "Lisp _does_
compete reasonably with C for numeric stuff", but I never bothered to do
the timing tests, and always assumed it wasn't this bad. Is it, really?
Also, I was interested in Beta until one minute ago, because of this.
Are there intrinsic reasons for this that will prevent it from ever
improving?
- Lenny Gray -
> Bruno Haible (hai...@ma2s2.mathematik.uni-karlsruhe.de) wrote:
>
> : ...
> : some integer array hacking
> : C 4.2 sec
> : Mjolner 111 sec
> : GCL 288 sec
> : CLISP 415 sec
> : (All timings on a 486/33.)
> : ...
Ouch!
> Are these numbers right? I've seriously used GCL and CLISP myself and
> had some arguments with a "true believer Lisper" who thought "Lisp _does_
> compete reasonably with C for numeric stuff", but I never bothered to do
> the timing tests, and always assumed it wasn't this bad. Is it, really?
I don't know what Bruno's "some integer array hacking" program does,
but the performance ratios shown do not reflect my personal experience.
For example, here's a very simple "some integer array hacking" program
I wrote for the occasion:
/* siah.c - some integer array hacking in C */
void main(void)
{
int a[10000], i, j;
for (j=0; j<1000; j++)
for (i=0; i<10000; i++)
a[i] = i*4;
}
(* siah.bet - some integer array hacking in BETA *)
ORIGIN '~beta/basiclib/v1.4/betaenv'
--program:descriptor--
(#
a: [10000]@integer;
do
(for j:1000 repeat
(for i:a.range repeat i*4 -> a[i] for);
for);
#)
And here's the run-times (486/66; BETA compiler v5.0(1); gcc v2.5.8):
BETA 4.41
gcc 3.10
gcc -O6 1.24
In this case, the ratio between BETA and unoptimized C was 1.4, while
the ratio between BETA and optimized C was 3.6.
Bear in mind that the BETA compiler does not currently perform nearly
as much optimization as gcc does. Also, the code generated by the BETA
compiler contained an index check (which could have been removed, had
the optimizer been smarter) at each assignment, while the C code
obviously did not.
> Also, I was interested in Beta until one minute ago, because of this.
Hopefully, your interest has been reawakened.
/Jacob Seligmann
------------------------------------------------------------------------
Mjolner Informatics ApS Phone: (+45) 86 20 20 00 ext. 2754
Science Park Aarhus Direct: (+45) 86 20 20 11 - 2754
Gustav Wieds Vej 10 Fax: (+45) 86 20 12 22
DK-8000 Aarhus C, Denmark Email: jac...@mjolner.dk
------------------------------------------------------------------------
BETA is better
------------------------------------------------------------------------
From the point of view of a Lisp programmer, a pattern consists of
* a specification of variables (call them "variables" or "closure variables"
or "slots"), and
* a piece of code which is executed after the storage for the variables has
been allocated (call it "initialization method" or simply "program").
But that's only one of many aspects of patterns...
Bruno Haible
hai...@ma2s2.mathematik.uni-karlsruhe.de
>> So what are these "patterns" anyway? It sounds as if they are very
>> close if not identical to lisp closures. After all, can't each of the
>> above lisp stuff can be implemented as sugar for closures.
> From the point of view of a Lisp programmer, a pattern consists of
>
> * a specification of variables (call them "variables" or "closure variables"
> or "slots"), and
>
> * a piece of code which is executed after the storage for the variables has
> been allocated (call it "initialization method" or simply "program").
Ok, so consider the following:
(lambda (x y) (print "whatever...") (funcall x y))
This lambda abstraction, which evaluates to a closure, has "a
specification of variables", X and Y, and "a piece of code which is
executed after the storage for the variables has been allocated", the
PRINT followed by the FUNCALL.
I don't see any difference yet...
> But that's only one of many aspects of patterns...
Why is it that every explanation of patterns i've come across so far
always includes a "more to come" disclaimer at the end?! I'm
beginning to wonder if these so called "patterns" can be defined at
all!
rodrigo "tired of playing detective" vanegas
r...@cs.brown.edu
With the important extension that it is not only possible to declare
x will be of type A,
but also
x will belong to some fixed subtype of type A.
This makes it possible to have generic container classes.
> Programs in Beta is very static, which makes it very
> different from the dynamic nature of lisp programming.
I don't agree here. This depends on your programming style. You can
perfectly embed Lambda Calculus into Beta.
Bruno Haible
hai...@ma2s2.mathematik.uni-karlsruhe.de
Yep, that's pretty much it.
] The important differences come about because of three things:
]
] <1] Static typing - in Beta, the types of variables are always declared
] statically. Programs in Beta is very static, which makes it very
] different from the dynamic nature of lisp programming.
]
]Agreed, although it wouldn't take much of a stretch to imagine a lisp
]which required type declarations. Admittedly, most lisp users would
]hate that.
]
] <2] Single inheritance- the Beta object model uses only single inheritance.
] The designers decided that rather than try to work out a system for
] resolving the confusion caused by MI (namespace collisions, repeated
] inheritance, etc.), it was better to do without it. I don't necessarily
] agree with them, but it did result in keeping Beta simple.
]
]But it looked to me like the object system that Beta uses is one based
]on closures. That sort of object system has been used in lisp and has
]the same sort of single inheritance. For the same matter, I assume
]that one could build a CLOS type multiple inheritance object system
]in Beta which did not use closures in such a direct way.
Again, you're pretty much right. It's *very* similar to closure based
object systems. It reminds me quite a lot of a closure based object
system I implemented for Scheme as an undergrad.
] <3] Virtual patterns - the object model is rather different. Instead of
] the CLOS model where a child method overrides a parent method, Beta
] uses the Simula model, where the child extends the parent method. The
] parent implementation of a method contains calls to inner, which are
] dynamically bound to the correct extension for the actual child type.
]
]See my last comment.
]
] Going further, since everything (functions, procedures, methods, values)
] is just a pattern, the virtual pattern idea can be applied to *any*
] method at all. This results in a *very* interesting program model,
] where you can write any procedure to be dynamically extensible. This can
] actually be used to write lambda expressions! It's quite elegant...
]
]Could you give an example here which doesn't look like a closure. I
]guess I'm looking for something which would not have a straightforward
]translation into lisp. If there's something new here I'd really like
]to know.
No, I can't give an example which doesn't look like a closure, because
as I've said, the comparison to closures is pretty damned exact. The
differences that I've pointed out are primarily differences in
programming style that wind up in common programs.
Programming styles in Beta do end up being somewhat different than
styles in Lisp, primarily because of the factors I've mentioned
above. The Beta idioms could be used to implement the programming
styles used by most commonlisp people; and the commonlisp idioms could
be used to implement the beta style. It's not a semantic difference,
just a stylistic one.
<MC>
--
|| Mark Craig Chu-Carroll: <MC> || "A libertarian is just a republican
|| CIS Grad, U of Delaware || who takes drugs"
|| PGP Key Available, by finger || - Bob Black
|| car...@cis.udel.edu ||
>A. The BETA language
>
>1. Has an incredible symmetry between data and executable program code.
> Much better than Lisp.
This is useless without some details. All I know is that you think
Beta has an "incredible symmetry".
Most of the rest of the message has the same problem.
>2. Lexically scoped, but a module system ("fragment" system) permits
> to put parts of a program into separate files - effectively splitting
> interface and implementation.
Virtually every Lisp in the universe lets you put parts of the
program in separate files. So what exactly is the issue here?
>7. The ":<" token makes up
> - generic classes (not present in Lisp, you would have to use
> a DEFCLASS in a non-null lexical environment),
So in fact what you mean is *Common* Lisp, not Lisp.
>9. CALL-NEXT-METHOD goes the other way around: the most general method
> determines the general behaviour, the most specific method only
> plays the role of a fixup.
Again more is needed.
>11. Concurrency, i.e. deterministic parallelism. (Would make
> WITH-PACKAGE-ITERATOR and WITH-HASH-TABLE-ITERATOR obsolete in CL.)
I think you are confused about the nature and role of these
iterators. But perhaps not. It's impossible to tell from
the little you say.
>4. Speed:
> consing up 1000 closures into a list
> Mjolner 0.049 sec
> CLISP 0.064 sec
> GCL 0.168 sec
> some integer array hacking
> C 4.2 sec
> Mjolner 111 sec
> GCL 288 sec
> CLISP 415 sec
> (All timings on a 486/33.)
It's necessary to see the code. What declarations did you use
in Common Lisp? Also, try a faster Common Lisp.
I don't think so. If their compiler did more optimizations, the Mjolner
timings certainly would be much closer to the C timings.
Bruno Haible
hai...@ma2s2.mathematik.uni-karlsruhe.de
If their compiler did more optimizations, the Mjolner
timings certainly would be much closer to the C timings.
Contrast with the strategy of the Sather group: their compiler started
out by doing better than C++ on some microbenchmarks. That's what it
takes to win supporters in real life.
> Lenny Gray (lenn...@netcom.com) wrote:
>
> > Bruno Haible (hai...@ma2s2.mathematik.uni-karlsruhe.de) wrote:
> >
> > > some integer array hacking
> > > C 4.2 sec
> > > Mjolner 111 sec
> > > GCL 288 sec
> > > CLISP 415 sec
>
> > Are these numbers right? I've seriously used GCL and CLISP myself and
> > had some arguments with a "true believer Lisper" who thought "Lisp _does_
> > compete reasonably with C for numeric stuff", but I never bothered to do
> > the timing tests, and always assumed it wasn't this bad. Is it, really?
>
> I don't know what Bruno's "some integer array hacking" program does [...]
Mr. Bruno Haible was friendly enough to send me the C and LISP programs
used. Unfortunately, he had deleted the BETA program, so I had to do
the port from scratch. All three programs are listed at the end of this
post. The benchmark is the program run with n=9.
[As you can see below, the C implementation uses a lot of tricks I did
not care or was unable to use in the BETA port: in-lining (#define's),
hard-wired variable liveliness information (loads of blocks with local
variables, making the code very hard to read), code generation hints
(register ...), array pointers (*d++ = *s++), unstructured gotos, etc.]
Here's my results (486/66; BETA compiler v5.0(2); gcc v2.5.8):
gcc -O6 -fomit-frame-pointer 2.08
BETA -no-range-check 11.00
[Actually, the compiler currently do not have a -no-range-check option.
The BETA figure was obtained by removing all boundl-instructions from
the code by hand, and reassembling; this is the only way I could
achieve a fair comparison.]
As you can see, the ratio between state-of-the-art optimized C and BETA
was 5.3, not 26.4 as above.
> > Also, I was interested in Beta until one minute ago, because of this.
> > Are there intrinsic reasons for this that will prevent it from ever
> > improving?
I looked at the generated code, and it seems that the increase in
execution time can be attributed to two factors:
(1) The BETA code allocates its variables on the heap, while the C
code uses registers almost exclusively.
(2) The BETA code performs a regular lookup calculation at each array
access, while the C code simply increases a dedicated register
during the linear sweep.
With a little bit of effort, there is absolutely no reason why the BETA
compiler should not be able to perform the variable liveliness analysis
itself (although currently it does not, and therefore pays the heavy
price of using heap space instead of registers). Also, the linear array
sweeps are simple enough that the compiler could recognize them and
avoid the index calculations (again, it currently does not, and
therefore pays the price at each lookup).
"Some integer array hacking"-type programs are *exactly* what highly
sophisticated C compilers excel at, but there are no intrinsic reasons
why the BETA compiler should not to be able to produce comparable code.
We're constantly working on it...
Sincerely,
/Jacob Seligmann
------------------------------------------------------------------------
Mjolner Informatics ApS Phone: (+45) 86 20 20 00 ext. 2754
Science Park Aarhus Direct: (+45) 86 20 20 11 - 2754
Gustav Wieds Vej 10 Fax: (+45) 86 20 12 22
DK-8000 Aarhus C, Denmark Email: jac...@mjolner.dk
------------------------------------------------------------------------
BETA is better
------------------------------------------------------------------------
============================== fannkuch.c ==============================
/* Programm zur Simulation des Pfannkuchenspiels */
/* Bruno Haible 10.06.1990 */
#include <stdio.h>
#define PermLength 100
#define PermCopy(Source,Dest,n) \
{register int h = n; register int *s = Source; register int *d = Dest; \
while (h) {*d++ = *s++; h--;}; \
}
void main()
{ int n;
int Perm[PermLength];
int Perm1[PermLength];
int Zaehl[PermLength];
int PermMax[PermLength];
int BishMax; /* bisheriges Maximum aller Spiegelungsanzahlen */
printf("n = ?");
scanf("%d",&n); if (!((n>0)&&(n<=PermLength))) goto Ende;
BishMax=-1;
/* Erzeugung aller Permutationen */
/* Erzeuge die Permutationen nach dem Algorithmus:
PERM1[0..n-1] := (0,...,n-1]
t:=n
# if t=1 then standardroutine, goto $
Z_hl[t-1]:=t
t:=t-1, goto #
$ if t<n then goto &, if t=n then fertig.
& rotiere PERM1[0..t], dec Z_hl[t], if >0 then goto #
t:=t+1, goto $
*/
{ register int i;
for (i=0; i<n; i++) { Perm1[i]=i; };
};
{ register int t;
t=n;
Kreuz: if (t==1) goto standardroutine;
Zaehl[t-1]=t;
t=t-1; goto Kreuz; /* rekursiver Aufruf */
Dollar: /* R_cksprung aus dem rekursiven Aufruf */
if (t==n) goto Fertig;
/* Rotieren: Perm1[0] <- Perm1[1] <- ... <- Perm1[n-1] <- Perm1[0] */
{ register int Perm0; register int i;
Perm0=Perm1[0];
for (i=0; i<t; i++) {Perm1[i]=Perm1[i+1];};
Perm1[t]=Perm0;
};
if (--Zaehl[t]) goto Kreuz;
t=t+1; goto Dollar;
standardroutine:
PermCopy(Perm1,Perm,n); /* Perm := Perm1 */
{ int Spiegelungsanzahl;
Spiegelungsanzahl=0;
{ unsigned int k;
while (!((k=Perm[0]) == 0))
{/* Spiegle Perm[0..k] */
unsigned int k2=(k+1)/2;
register int *up = &Perm[0]; register int *down = &Perm[k];
{ register int i;
i=k2; while (i) {int h; h=*up; *up++=*down; *down--=h; i--;};
}
Spiegelungsanzahl++;
};
};
if (Spiegelungsanzahl>BishMax)
{BishMax=Spiegelungsanzahl; PermCopy(Perm1,PermMax,n);};
}
goto Dollar;
}
Fertig: printf("Das Maximum betrug %d.\n bei ",BishMax);
{register unsigned int i;
printf("(");
for (i=0; i<n; i++)
{if (i>0) printf(" ");
printf("%d",PermMax[i]+1);
};
printf(")");
};
printf("\n");
Ende: ;
}
============================= fannkuch.lsp =============================
(defun fannkuch (&optional (n (progn
(format *query-io* "n = ?")
(parse-integer (read-line *query-io*))
) ) )
(unless (and (> n 0) (<= n 100)) (return-from fannkuch))
(let ((n n))
(declare (fixnum n))
(let ((perm (make-array n :element-type 'fixnum))
(perm1 (make-array n :element-type 'fixnum))
(zaehl (make-array n :element-type 'fixnum))
(permmax (make-array n :element-type 'fixnum))
(bishmax -1))
(declare (type (simple-array fixnum (*)) perm perm1 zaehl permmax))
(declare (fixnum bishmax))
(dotimes (i n) (setf (svref perm1 i) i))
(prog ((\t n))
(declare (fixnum \t))
Kreuz
(when (= \t 1) (go standardroutine))
(setf (svref zaehl (- \t 1)) \t)
(decf \t)
(go Kreuz)
Dollar
(when (= \t n) (go fertig))
(let ((perm0 (svref perm1 0)))
(dotimes (i \t) (setf (svref perm1 i) (svref perm1 (+ i 1))))
(setf (svref perm1 \t) perm0)
)
(when (plusp (decf (svref zaehl \t))) (go Kreuz))
(incf \t)
(go Dollar)
standardroutine
(dotimes (i n) (setf (svref perm i) (svref perm1 i)))
(let ((Spiegelungsanzahl 0) (k 0))
(declare (fixnum Spiegelungsanzahl k))
(loop
(when (= (setq k (svref perm 0)) 0) (return))
(let ((k2 (ceiling k 2)))
(declare (fixnum k2))
(dotimes (i k2) (rotatef (svref perm i) (svref perm (- k i))))
)
(incf Spiegelungsanzahl)
)
(when (> Spiegelungsanzahl bishmax)
(setq bishmax Spiegelungsanzahl)
(dotimes (i n) (setf (svref permmax i) (svref perm1 i)))
) )
(go Dollar)
fertig
)
(format t "Das Maximum betrug ~D.~% bei " bishmax)
(format t "(")
(dotimes (i n)
(when (> i 0) (format t " "))
(format t "~D" (+ (svref permmax i) 1))
)
(format t ")")
(terpri)
(values)
) ) )
============================= fannkuch.bet =============================
ORIGIN '~beta/basiclib/v1.4/betaenv'
--program:descriptor--
(#
PermLength: (# exit 100 #);
Perm, Perm1, PermMax, Zaehl: [PermLength]@integer;
h, i, k, n, t, up, down, BishMax, Spiegelungsanzahl: @integer;
do
'n = ?' -> putText;
getInt -> n;
(if (n < 1) or (n > PermLength) then stop if);
-1 -> BishMax;
(for i:n repeat i-1 -> Perm1[i] for);
n -> t;
again:
(#
do (for i:t repeat i -> Zaehl[i] for); 1 -> t;
(for i:n repeat Perm1[i] -> Perm[i] for);
0 -> Spiegelungsanzahl;
while1:
(#
do (if Perm[1]->k // 0 then leave while1 if);
1 -> up; k+1 -> down; down/2 -> i;
while2:
(#
do (if i // 0 then leave while2 if);
Perm[up] -> h; Perm[down] -> Perm[up]; h -> Perm[down];
up+1 -> up; down-1 -> down; i-1 -> i;
restart while2;
#);
Spiegelungsanzahl+1 -> Spiegelungsanzahl;
restart while1;
#);
(if Spiegelungsanzahl > BishMax then
Spiegelungsanzahl -> BishMax;
(for i:n repeat Perm1[i] -> PermMax[i] for)
if);
while3:
(#
do (if t // n then leave while3 if);
Perm1[1] -> h;
(for i:t repeat Perm1[i+1] -> Perm1[i] for);
h -> Perm1[t+1];
(if (Zaehl[t+1]-1 -> Zaehl[t+1]) <> 0 then restart again if);
t+1 -> t;
restart while3;
#);
#);
'Das Maximum betrug ' -> putText;
BishMax -> putInt;
'.\n bei (' -> putText;
(for i:n repeat
(if i > 1 then ' ' -> put if);
PermMax[i]+1 -> putInt;
for);
')' -> putLine;
#)
========================================================================
There was a Prolog a while back that did better than C for some
numeric stuff. Did this win wupporters? Nooooooooooo...
It's a necessary but not sufficient condition. Sather and C are both in
the algol vein; crossover is easy. Prolog is utterly different than C;
performance is almost the least of one's worries.
| [As you can see below, the C implementation uses a lot of tricks I did
| not care or was unable to use in the BETA port: in-lining (#define's),
| hard-wired variable liveliness information (loads of blocks with local
| variables, making the code very hard to read), code generation hints
| (register ...), array pointers (*d++ = *s++), unstructured gotos, etc.]
this is not benchmarking execution speeds of C or LISP or anything. this
is benchmarking a programmer's willingness to write assembly language and
to see how well his assembly language coding style fits various languages.
I'll bet gcc -O6 does a better job on reasonably-written C than it does on
this spaghetti code. I mean, writing your own version of memcpy because
you think memcpy won't be fast enough is rather pathetic when there are
CPU's out that have block move instruction idioms and good compilers that
open-code them when calls to memcpy are requested.
to paraphrase Richard Stallman from a response to a bug report for Emacs
with a horribly convoluted fix:
Unfortunately, the code you wrote looks like the intermediate stage of
scheme compilation, and it's too hard for me to read. I can't even
figure out what [it] does.
and what's this about a semicolon _after_ the closing brace in blocks?
such things worry me when I read other people's C code, because it tells me
that they don't really program in C, but translate from something else into
C. that's the feeling I got from the LISP code, too. is this really a
good way to compare languages? I think not.
are there any good ways to compare _languages_? I think programmer time
spent and number of compilation runs required to solve a particular problem
is a better indication. then, later, we can benchmark the compilers.
I don't use LISP because of its outstanding speed, anyway. I use it
because _I_ am faster in LISP than in anything else I know well enough to
compare to. two days of my time translates to the cost of a CPU upgrade to
my clients. so what if it runs five times slower and takes 100 instead of
20 milliseconds? with the upgraded CPU it'll only take 3 times more time,
and if I need to come back to enhance the functionality, they can buy an
even _faster_ CPU. we're not talking about more than constant factors in
difference between these benchmarks here, right?
BETA and LISP probably have a lot to tell us about optimal program design
in their respective mind-sets and a comparison of their relative strengths
and idiomatic expressiveness would be instructive. onwards, folks!
#<Erik>
--
Microsoft is not the answer. Microsoft is the question. NO is the answer.
> > [Description of C spaghetti code deleted]
>
> this is not benchmarking execution speeds of C or LISP or anything. this
> is benchmarking a programmer's willingness to write assembly language and
> to see how well his assembly language coding style fits various languages.
I couldn't agree more! I was simply answering to a post which could be
misinterpreted as saying that BETA is inherent 25 times slower than C.
This did not reflect my personal impression, so I retrieved the C
benchmark program from the original poster, did a simple rewrite in
BETA, gained a factor 5, and posted this result along with the programs
used for you all to verify.
That is, I did not write the spaghetti code in the first place, neither
do I feel this is the way to program in BETA, or C, or LISP, or
whatever.
> are there any good ways to compare _languages_? I think programmer time
> spent and number of compilation runs required to solve a particular problem
> is a better indication. then, later, we can benchmark the compilers.
Again, I agree, as long as your programs are not orders of magnitude
slower than what is achievable, and as long as there are no inherent
barriers in the language design to ever achieving better performance.
> BETA and LISP probably have a lot to tell us about optimal program design
> in their respective mind-sets and a comparison of their relative strengths
> and idiomatic expressiveness would be instructive. onwards, folks!
Actually I was quite surprised to see a BETA-LISP comparison thread in
the first place. Sure, BETA strongly supports a functional programming
paradigm, but it is still an object-oriented language at heart - it
never ceases to amaze me just how versatile and expressive the BETA
pattern concept is! Keep the comparisons coming.
Cheers,
I'd say it's neither.
Jeff> In article <SCHWARTZ.94...@roke.cse.psu.edu>
Jeff> schw...@roke.cse.psu.edu (Scott Schwartz) writes:
>> je...@aiai.ed.ac.uk (Jeff Dalton) writes: There was a Prolog a while
>> back that did better than C for some numeric stuff. Did this win
>> wupporters? Nooooooooooo...
>>
>> It's a necessary but not sufficient condition.
Jeff> I'd say it's neither.
Are we about to open the `C vs. Lisp' thread again, with BETA on the
side?
(for those puzzled: this has been a raging debate for the last couple
of months in comp.lang.lisp)
------------------------------------------------------------------------------
Christian Lynbech | Hit the philistines three times over the
office: R0.33 (phone: 3217) | head with the Elisp reference manual.
email: lyn...@daimi.aau.dk | - pet...@hal.com (Michael A. Petonic)
------------------------------------------------------------------------------
jac...@daimi.aau.dk (Jacob Seligmann) writes:
[...]
Here's my results (486/66; BETA compiler v5.0(2); gcc v2.5.8):
gcc -O6 -fomit-frame-pointer 2.08
BETA -no-range-check 11.00
[Actually, the compiler currently do not have a -no-range-check option.
The BETA figure was obtained by removing all boundl-instructions from
the code by hand, and reassembling; this is the only way I could
achieve a fair comparison.]
As you can see, the ratio between state-of-the-art optimized C and BETA
was 5.3, not 26.4 as above.
[...]
With a little bit of effort, there is absolutely no reason why the BETA
compiler should not be able to perform the variable liveliness analysis
itself (although currently it does not, and therefore pays the heavy
price of using heap space instead of registers). Also, the linear array
sweeps are simple enough that the compiler could recognize them and
avoid the index calculations (again, it currently does not, and
therefore pays the price at each lookup).
"Some integer array hacking"-type programs are *exactly* what highly
sophisticated C compilers excel at, but there are no intrinsic reasons
why the BETA compiler should not to be able to produce comparable code.
We're constantly working on it...
What Jacob's saying is
(a) Typical code written in c performs more than 5 times
better than code in his favourite language using available
implementations, and
(b) there's no reason why his favourite language couldn't be
implemented so it was competive.
What lisp (and beta) advocates seem to often ignore is that quality of
code generation really matters to most people.
Telling people that a factor of 5 difference in run-time doesn't
really matter doesn't encourage them to use your language. Neither
does telling them that *in principle* or *some day in the future*,
your language could be competitive.
Unless you have competitive ports to x86, Sparc, Alpha, DEC & SG Mips,
PA-RISC, and RS6k, few people are going to use a language. Not many
people are going to bother explaining that performance matters to
them, they're just going to ignore you when you try to tell them
otherwise.
Which is a pity, because competive compilers for sane languages like
beta and lisp are obviously feasible. Paul Wilson was proposing a
compiler for scheme+objects that would compete with C, CMU CL was
great (although it now seems to be largely unsupported) and the ETH
Oberon compilers are also wonderful (although the systems they're in
don't co-operate with the rest of the universe.)
At least Jacob's actually working on improving the beta
implementation. As far as I can tell, the usual lisp advocate response
to performance complaints is to either:
(a) deny there's a problem,
(b) say one day there won't be a problem, or
(c) suggest you write code that looks like FORTRAN and
manually weigh expression trees and other insanity.
Perhaps Gwydion or Paul Wilson's scheme+objects compiler will save the
world.
--
Matthew McDonald ma...@cs.uwa.edu.au
Nim's longest recorded utterance was the sixteen-sign declarative
pronouncement, "Give orange me give eat orange me eat orange give me
eat orange give me you."
> Jeff> I'd say it's neither.
>
> Are we about to open the `C vs. Lisp' thread again, with BETA on the
> side?
>
> (for those puzzled: this has been a raging debate for the last couple
> of months in comp.lang.lisp)
>
>
>
Howdy,
Sure let's open it up again ;-) But no really -- skip all this
talk of "realtime" this and that and concerns about competing with
Fortran on floating point. I'm still _VERY_ curious (concerned?)
about why Lisp isn't more popular in "the trenches". Go look at
Borland C++ compiler's output in large model (typical Windows app) -
not too slick. Now go run a typical Windows app (or Unix workstation
app for that matter). It pages like all get out when you open a
windows or switch to another task. Now go install a Windows
_personal utility app_ -- 40 meg disk footprint or more. We're
not talking big DB servers, just a nice word processor or
spreadsheet.
So why don't folks use Lisp to write this stuff? Blazing
speed,space,etc. aint that critical. What gives?
=============================================
Scott McLoughlin
Conscious Computing
=============================================
: What Jacob's saying is
: (a) Typical code written in c performs more than 5 times
^^^^^^^^^^^^^^^^^^^^^^^^^
A small correction: It should be the-state-of-the-art spaghetti code in c
: better than code in his favourite language using available
: implementations, and
Naresh
--
_______________________________________________________________________________
Naresh Sharma [N.Sh...@LR.TUDelft.NL] Herenpad 28 __|__
Faculty of Aerospace Engineering 2628 AG Delft \_______(_)_______/
T U Delft Optimists designed the aeroplane, ! ! !
Ph(Work) (+31)15-783992 pessimists designed the parachute!
Ph(Home) (+31)15-569636 Plan:Design Airplanes on Linux the best OS on Earth!
------------------------------PGP-KEY-AVAILABLE--------------------------------
So true !
The best example is probably Visual Basic, right ?
Stefan
> (a) Typical code written in c performs more than 5 times
> better than code in his favourite language using available
> implementations, and
This is exactly the sort of unsupportable generalization I was afraid
would result from the net publication of this so-called "benchmark."
(Not a reference to Jacob's post, but to the original.) Differences in
performance do not boil down to single numbers, nor any kind of simple
comparison for that matter.
>.... Telling people that a factor of 5 difference in run-time doesn't
> really matter doesn't encourage them to use your language.
Most of the time, a factor of five is negligible. In critical parts of
the code however, a factor of 1.05 may be important.
> .... As far as I can tell, the usual lisp advocate response
> to performance complaints is to either:
> (a) deny there's a problem,
> (b) say one day there won't be a problem, or
> (c) suggest you write code that looks like FORTRAN and
> manually weigh expression trees and other insanity.
This is gross oversimplification. As a "lisp advocate," I consistently
maintain that if and when there is a performance problem, it can be dealt
with in the same way one deals with performance problems in any language.
There is not a generalized performance problem inherent in lisp.
> What Jacob's saying is
> (a) Typical code written in c performs more than 5 times
> better than code in his favourite language using available
> implementations, and
> (b) there's no reason why his favourite language couldn't be
> implemented so it was competive.
Again, I was merely answering to an earlier post which was
misinterpreted as saying that BETA was *inherently* 25 times or more
slower than C. I did so by using the original C program containing
tight loops with lots of pointer arithmetic to write an equivalent BETA
program which was "only" 5 times slower (thereby trying to show that
the factor or 25 was much too pessimistic), and finally explained the
difference in the code produced (thereby trying to show that the
slowdown was not a product of the language design, only its current
implementation).
> What lisp (and beta) advocates seem to often ignore is that quality of
> code generation really matters to most people.
>
> Telling people that a factor of 5 difference in run-time doesn't
> really matter doesn't encourage them to use your language. Neither
> does telling them that *in principle* or *some day in the future*,
> your language could be competitive.
We at Mjolner Informatics take the quality of the produced code
*extremely* seriously. There is no reason why we should not be able to
produce code comparable to C for the imperative portions of the
language, and we're constantly working on it.
Meanwhile, it is our practical experience that for real applications
(not dhrystone-type benchmarks) the quality of the code currently
produced is more than acceptable. Also, BETA provides an easy interface
to C; if 5% of your code is time-critical, you can therefore still
write it in your favorite procedural, optimized language, and use
BETA's modelling features and extensive libraries for the remaining 95%.
Cheers,
>The best example is probably Visual Basic, right ?
Well, unless you're Microsoft.
Where does a 500 pound gorilla sleep?
--
Har du kramat din varg idag?
I know this is about beta rather than lisp, but what Jacob is
saying about beta sounds a lot like what many people have been saying
about lisp.
...
What Jacob's saying is
(a) Typical code written in c performs more than 5 times
better than code in his favourite language using available
implementations, and
For Common Lisp (LispWorks and CMU, at least), the factor was 2, not
5. Moreover, I certainly disagree that this small numerical-analysis
benchmark is a typical C program. It's certainly not typical of, say,
telecommunications switching systems. Nevertheless, I agree that the
potential difference in efficiency of generated code between CL and
(the best) C compilers remains an obstacle to broadening CL's market.
Telling people that a factor of 5 difference in run-time doesn't
really matter doesn't encourage them to use your language. Neither
does telling them that *in principle* or *some day in the future*,
your language could be competitive.
I agree that "in principle" is a weak argument; "can be fixed by the
vendor within n months/years" is a somewhat better argument (if
true!).
Unless you have competitive ports to x86, Sparc, Alpha, DEC & SG Mips,
PA-RISC, and RS6k, few people are going to use a language. Not many
Common Lisp has all these.
At least Jacob's actually working on improving the beta
implementation. As far as I can tell, the usual lisp advocate response
to performance complaints is to either:
(a) deny there's a problem,
I don't deny the existence of a problem.
(b) say one day there won't be a problem, or
I think a concerted effort by vendors could substantially solve the
problem--i.e., make the best Common Lisp compilers generate code
substantially competitive with the code generated by the best C
compilers--within a reasonably short time period (perhaps 1-2 years).
Presumably, this will occur only if/when CL users raise its priority
above that of other new features and quality improvements.
(c) suggest you write code that looks like FORTRAN and
manually weigh expression trees and other insanity.
Ideally, code should "look like" the abstract solution to the problem
at hand. If the problem is numerical analysis, then shuffling vector
elements is precisely the =correct= abstraction of the
solution--mathematician have no abstraction higher-level than that.
If you want to say that the ideal compiler would deduce all datatypes
so that explicit type declarations would be unnecessary, I agree; but
I don't see how you can hold this lack of type inferencing against
Common Lisp when C does no such thing either.
--
Lawrence G. Mayka
AT&T Bell Laboratories
l...@ieain.att.com
Standard disclaimer.
Which is exactly right. It's necessary to know why the code is
slower and whether it can be fixed (and how hard it would be to
fix it) before you can reach conclusions about the _language_.
>> What lisp (and beta) advocates seem to often ignore is that quality of
>> code generation really matters to most people.
Who's done that? I haven't noticed it. But then I'm not on the
lookout for such things.
>> Telling people that a factor of 5 difference in run-time doesn't
>> really matter doesn't encourage them to use your language. Neither
>> does telling them that *in principle* or *some day in the future*,
>> your language could be competitive.
So? Let's settle first what's true. What people decide to do with
that information is then up to them.
[More reasonable stuff from Jacob Seligmann omitted.]
-- jeff
Many people? Like who, for instance?
I hope we don't add a misleading "Lisp advocate" stereotype
to the already misleading "Lisp" stereotype.
>Which is a pity, because competive compilers for sane languages like
>beta and lisp are obviously feasible. Paul Wilson was proposing a
>compiler for scheme+objects that would compete with C, CMU CL was
>great (although it now seems to be largely unsupported) and the ETH
>Oberon compilers are also wonderful (although the systems they're in
>don't co-operate with the rest of the universe.)
So you're actually on the same side as the Lisp advocates (modulo
your misleading characterization of them).
>At least Jacob's actually working on improving the beta
>implementation.
That's a rather unfair complaint. I have to work, and I'm
not employed these days to improve Lisp implementation. A
number of other Lisp "advocates" are in a similar position.
>As far as I can tell, the usual lisp advocate response
>to performance complaints is to either:
> (a) deny there's a problem,
Who has done that? There are a number of obvious problems, in
addition to any non-obvious ones. For instance, Lucid CL is too
large for me to use it for my work if I try to run it on the machine
on my desk.
> (b) say one day there won't be a problem, or
Who says that? Since no one knows what will happen in the
future, how can anyone say there won't be a problem one day?
> (c) suggest you write code that looks like FORTRAN and
> manually weigh expression trees and other insanity.
Who said anything about writing code that looks like FORTRAN?
The only thing close to that I can recall was in the "data bloat"
thread where it was pointed out that you could pack data by using
parallel arrays (rather than structs) as in FORTRAN. The code
still wouldn't have to look like FORTRAN. Nor does declaration-
filled Common Lisp look like FORTRAN.
(I have seen Lisp code that looked like FORTRAN, BTW. Imagine
lots of PROGs and GOs. But not for many years.)
-- jeff
> Out there in the real world, there are n (where n > 20, probably)
> people sitting in front of a Windows box for every one person sitting
> in front of a real computer. So if you write a program in Visual
> BASIC, you'll be able to sell it. You won't be able to maintain it, of
> course, but that's the customer's problem.
>
> If you write a program in a real language for a real computer, *unless
> you can port it to Windows (or windows NT, or Windows 95, or whatever
> other dreck Bill Gates decides to unload on the uneducated next)* you
> are not going to sell it. I know. I set up a company in 1988 to
> develop knowledge engineering tools. I said to myself 'the PC isn't
> powerful enough to do what I want to do, so I'll develop tools for
> real computers'. There were other mistakes I made, but I think it was
> that one that cost me the company...
Howdy,
Exactly. I suspect that N is much > 20 if you don't count
bank machines ;-) Now, how do we get the "real languages" in use
on not so real Windows boxes? What exactly _is_ the "political
economy" of commercial dynamic language implementations.
We've got a $49 "Personal Eiffel". Is anyone out there
working in a "Personal Lisp" or "Personal Scheme" or "Personal
Dylan" or "Personal ML"???? If not -- Why Not? Were all the
venture capitalists "burned" in the 80's AI hyped up binge? Do
the implementors have a comfy niche with Govt contracts and
research grants, so why bother? Are these languages so hard
to implement (well) that the economics simply won't bear a
low cost implementation (with CL it's imaginable!) to price
conscious consumers? Is the marketing channel blocked by
MS and Borland and Watcom and a few others, so product just
can't get out the door?
Anyway, with FrameMaker selling cheap on PC's and
Interleaf coming to a Windows box near you and Intergraph
running on NT and ... All the $$ workstation software is
(1) coming to PC's and then fairly quickly thereafter
(2) dropping in price. What about languages? If not,
why not?
ps. Sorry to hear about your company.
> I hope we don't add a misleading "Lisp advocate" stereotype
> to the already misleading "Lisp" stereotype.
Is that a reference to the thread about a newsgroup for Lisp advocacy?
I'm not sure, but this looks like you've misunderstood the issue,
which was about the need, or not, for a comp.lang.lisp.advocacy
newsgroup, and not the nature and/or worth of Lisp advocacy, which
is another matter. My point was merely that at the moment, there's
no choice, except to add such advocacy threads to a killfile, which
is not ideal.
I hope I've misunderstood your comment, in which case I apologise.
However, I'm not aware of any stereotype being the problem. Perhaps
you're refering to some other thread, perhaps in another newsgroup,
but I don't know. So I'll just add that _my_ thread (the one I started)
was about the location of such advocacy threads, bot about their
worth. I'd like to have a choice about what I read, which is a purely
personal thing.
It just happens that we see these threads in comp.lang.lisp, and I'm
not aware of a Lisp newsgroup that might cover the same subjects but
without the advocacy threads. If you can suggest one, then I'll happily
leave comp.lang.lisp and go and read it.
Meanwhile, I've been enjoying this particular thread, as I felt it
had some interesting things to say about implementation and design
of languages. I hadn't thought of it in the same way as "C vs Lisp"
threads. Should I?
As I said above, if I've misunderstood your comment, then I'm sorry.
I wish well with your Lisp advocacy, whether I read it or not. If
I've ever suggested or implied that you _shouldn't_ advocate Lisp,
then I'm sorry for that, too. It could only have been because of
an misunderstanding. I've seen some extreme advocacy of Pascal
vs C, and itwas ugly. That rather colours my feelings! I didn't
mean to imply that you were included in that group of advocates,
as I've always found your posts worth reading.
The comp.lang.visual newsgroup is in need of another kind of advocacy,
simply because so many users of VB and VC++ have yet to discover the
wider world of "visual" programming that Microsoft have yet to support.
That goes way beyond "X vs Y" debates, and into the power of marketing
over the power (or lack of it) of other media, such as UseNet. You
can read the comp.lang.visual FAQ for the details, if you want to
know more about that problem. It'll explain why some people believe
that c.l.v should become a moderated newsgroup.
I'm glad that Lisp hasn't reached that point, and I hope that it
never will. After all, the name Lisp still refers to Lisp, and not
a Microsoft product that looks nothing like Lisp. Ouch.
Well, ok. That's my c.l.v advocacy over with for today. ;-)
> (I have seen Lisp code that looked like FORTRAN, BTW. Imagine
> lots of PROGs and GOs. But not for many years.)
Yeah, me too. I used to write Basic code like that. Then I switched
to Forth, and never used an exlicit GOTO again. Now I just write
compilers and macros that can do it for me. ;-)
Martin Rodgers
--
Future generations are relying on us
It's a world we've made - Incubus
We're living on a knife edge, looking for the ground -- Hawkwind
I thought my article was reasonably clear in context. Maybe not.
Anyway, I was responding to an article that said such things as "the
usual lisp advocate response".
>I hope I've misunderstood your comment, in which case I apologise.
>However, I'm not aware of any stereotype being the problem. Perhaps
>you're refering to some other thread, perhaps in another newsgroup,
>but I don't know.
Why not assume I'm talking about something in *this* thread,
namely: Comparison: Beta - Lisp?
-- jeff
> I thought my article was reasonably clear in context. Maybe not.
> Anyway, I was responding to an article that said such things as "the
> usual lisp advocate response".
I'm still not sure what that means. Was it a reference to the advocacy
thread or not? It's a question that asks for a yes or no.
> Why not assume I'm talking about something in *this* thread,
> namely: Comparison: Beta - Lisp?
I am assuming that, but it doesn't make the "advocacy" reference
unambigous. Perhaps that's coz I see so many ways of interpreting
people's comments. I don't see _this_ thread as one about advocacy.
It appears to me to be about Lisp and Beta, but I don't recall seeing
anyone trying to "advocate" the use of one language or another.
That could be coz I don't see all comparison threads as advocacy
threads. It's possible that I missed that aspect, or I just didn't
consider it stong enough in this thread.
I didn't intend it as a reference to the advocacy thread. I can't
say for the article I was responding to. If it's important, I may
be able to find it. But we should probably take it to e-mail.
-- jeff