Hi,
In the process of extending Linj (the Lisp to Java compiler) to support
the extended loop macro, I found some funny examples in Paul Dietz ANSI
tests and in CLTL (and I invented some others) that I would like to use as
challenges for the Common Lisp community. The idea is simply to find
nice-looking Java translations for some examples of the extended loop
macro.
Let me start by giving an example. Consider the following Common Lisp
function:
(defun test1 ()
(loop for x from 1 to 10 sum x))
This corresponds (more or less) to the following "function" in Java:
public static long test1() {
long sum = 0;
for (int x = 1; x <= 10; ++x) {
sum += x;
}
return sum;
}
[Is there a shorter version in Java (that is still readable)?]
Anyway, this one was easy. Now, I would like to challenge all Common
Lispers that also know Java (and that enjoy riddles) to tell me what they
think is the best Java encoding for the following loop examples:
(defun test3 ()
(loop for i from 1
sum i
while (< i 10)
do (princ i)))
(defun test4 ()
(loop for x from 1 to 9
for y = 0 then x
sum (+ x y)))
(defun test5 ()
(let ((x 10))
(loop for x from 1 to 9
and y = x then x
sum (+ x y))))
(defun test6 ()
(loop for item = 1 then (+ item 10)
repeat 5
sum item))
(defun test7 ()
(loop for i from 3
when (oddp i) sum i
while (< i 5)))
If there's enought interest, I'll post some really difficult examples.
Enjoy,
Antonio Leitao.
Antonio Menezes Leitao <··············@evaluator.pt> writes:
> In the process of extending Linj (the Lisp to Java compiler) to support
> the extended loop macro, I found some funny examples in Paul Dietz ANSI
> tests and in CLTL (and I invented some others) that I would like to use as
> challenges for the Common Lisp community. The idea is simply to find
> nice-looking Java translations for some examples of the extended loop
> macro.
>
> Let me start by giving an example. Consider the following Common Lisp
> function:
>
> (defun test1 ()
> (loop for x from 1 to 10 sum x))
>
> This corresponds (more or less) to the following "function" in Java:
>
> public static long test1() {
> long sum = 0;
> for (int x = 1; x <= 10; ++x) {
> sum += x;
> }
> return sum;
> }
>
> [Is there a shorter version in Java (that is still readable)?]
public static long test1() {
for (int x=1, long sum=0; x<=10; sum += x++) {}
return sum;
}
Having just claimed the above is "readable", I should warn you that
I'm not so much a Java programmer as I am a C programmer who can
muddle through writing Java. I'm sure my loops show it.
> Anyway, this one was easy. Now, I would like to challenge all Common
> Lispers that also know Java (and that enjoy riddles) to tell me what they
> think is the best Java encoding for the following loop examples:
So, given that, I rewrote your loops into C. This is how I would
write the equivalent loops in C; if they look good, the changes to
make them valid Java are obvious; if they look bad to Java eyes, leave
them as C :-)
/* (defun test3 ()
* (loop for i from 1
* sum i
* while (< i 10)
* do (princ i)))
*/
int test3 (void) {
int i, sum;
for (i=1, sum=i; i<10; i++, sum+=i) {
printf ("%d", i);
}
return sum;
}
/* (defun test4 ()
* (loop for x from 1 to 9
* for y = 0 then x
* sum (+ x y)))
*/
int test4 (void) {
int x, y, sum;
for (x=1, y=0, sum=0; x<=9; x++, y=x) {
sum += x+y;
}
return sum;
}
/* (defun test5 ()
* (let ((x 10))
* (loop for x from 1 to 9
* and y = x then x
* sum (+ x y))))
*/
/* In the above Lisp function, there are two lexical variables named
* X, but only one is ever used. If this is an over-simplified
* example, where there should be some code in the body of the LET
* that uses the outer X, I would write it as follows:
*/
int test5 (void) {
int x = 10;
int xx, y, sum;
for (xx=1, y=xx, sum=0; xx<=9; y=xx, xx++) {
sum += xx+y;
}
return sum;
}
/* However, if I were writing the same odd code, where X's value as 10
* is never used, I'd write it like this instead:
*/
int test5_v2 (void) {
int x=10, y, sum;
for (x=1, y=x, sum=0; x<=9; y=x, x++) {
sum += x+y;
}
return sum;
}
/* (defun test6 ()
* (loop for item = 1 then (+ item 10)
* repeat 5
* sum item))
*/
int test6 (void) {
int item, sum, i;
for (i=0, item=1, sum=0; i<5; i++, item+=10) {
sum += item;
}
return sum;
}
/* (defun test7 ()
* (loop for i from 3
* when (oddp i) sum i
* while (< i 5)))
*/
int test7 (void) {
int i=3, sum=0;
do {
if ((i%2) != 0)
sum += i;
} while (i++ < 5);
return sum;
}
> If there's enought interest, I'll post some really difficult examples.
These all corresponded more or less to C idioms. Hard ones would be
fun :-)
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Thomas F. Burdick wrote:
> These all corresponded more or less to C idioms. Hard ones would be
> fun :-)
For the hard cases, just implement translators for the constructs on
which the LOOP macro is based and then use the LOOP macro the translate
into Lisp before translating to Java. :)
Sorry for the delay in answering this. It seems that my ISP is
loosing posts...
Ari Johnson <·····@hotmail.com> wrote in message news:<······················@lakeread01>...
> Thomas F. Burdick wrote:
>
> > These all corresponded more or less to C idioms. Hard ones would be
> > fun :-)
>
> For the hard cases, just implement translators for the constructs on
> which the LOOP macro is based and then use the LOOP macro the translate
> into Lisp before translating to Java. :)
As I said in another post, one of Linj goals is to generate
nice-looking Java code. This precludes using the usual Common Lisp
macro expansions because they look really ugly. Moreover, in several
cases, the direct translation will generate several warnings/errors
related to unreachable code that are simply unaceptable in Java.
Antonio Leitao
Antonio Leitao wrote:
> Sorry for the delay in answering this. It seems that my ISP is
> loosing posts...
>
> Ari Johnson <·····@hotmail.com> wrote in message news:<······················@lakeread01>...
>
>>Thomas F. Burdick wrote:
>>
>>
>>>These all corresponded more or less to C idioms. Hard ones would be
>>>fun :-)
>>
>>For the hard cases, just implement translators for the constructs on
>>which the LOOP macro is based and then use the LOOP macro the translate
>>into Lisp before translating to Java. :)
>
>
> As I said in another post, one of Linj goals is to generate
> nice-looking Java code. This precludes using the usual Common Lisp
> macro expansions because they look really ugly. Moreover, in several
> cases, the direct translation will generate several warnings/errors
> related to unreachable code that are simply unaceptable in Java.
I didn't realize that warnings were that unacceptable, and I am still
not fully clear on what Linj aims to be. I've always believed that the
original code should be easy to maintain and, as long as the compiler
chain is consistent, it doesn't matter if the intermediate code is
readable. But if Linj is aiming to make the intermediate code
maintainable, then I can understand the concern. My question, though,
is why you would want to make maintainable intermediate code. No C
compiler cares much if you can read the assembly code it emits, because
you are expected to maintain the code in C, not throw it away and
maintain the assembly code.
I'm presuming you can clear this up for me - it's not an attack on your
motives, but rather just a query. :)
On Sun, 23 May 2004 13:24:13 -0700, Ari Johnson wrote:
> Antonio Leitao wrote:
>> Sorry for the delay in answering this. It seems that my ISP is
>> loosing posts...
>> [...]
>>
>> As I said in another post, one of Linj goals is to generate
>> nice-looking Java code. This precludes using the usual Common Lisp
>> macro expansions because they look really ugly. Moreover, in several
>> cases, the direct translation will generate several warnings/errors
>> related to unreachable code that are simply unacceptable in Java.
>
> I didn't realize that warnings were that unacceptable, and I am still
> not fully clear on what Linj aims to be.
Unreachable code might be just the sign of less-optimized macro expansion
in Common Lisp (and might or might not issue a warning) but it's a real
compilation error in Java. The Java language specification says:
14.20 Unreachable Statements
It is a compile-time error if a statement cannot be executed because it
is unreachable. Every Java compiler must carry out the conservative flow
analysis specified here to make sure all statements are reachable.
This forces Linj to be more careful about its code generation.
> I've always believed that the
> original code should be easy to maintain and, as long as the compiler
> chain is consistent, it doesn't matter if the intermediate code is
> readable. But if Linj is aiming to make the intermediate code
> maintainable, then I can understand the concern. My question, though,
> is why you would want to make maintainable intermediate code. [...]
First, it is necessary to understand that my clients outsource
projects to my company on the basis that we have a very good team of
Java programmers. In fact, I think we were pretty good Java programmers
until I decided to create Linj. Then, we became pretty good and pretty
fast Java programmers. Linj gaves us the productivity boost that
makes the difference between equally good Java programmers. Of course,
our code would have to remain equally good.
Secondly, it is also necessary to understand that, due to the small size
of my company, some of my clients demanded readable Java source code
that they could store as a kind of life-insurance in case something bad
happens to my company.
Thirdly, in some cases, my clients use the code for further development or
maintenance, so it must look like human-written code. In this last case,
the biggest problem is that they sometimes ask me to make further
developments on the code they are maintaining and this forces me to port
their (Java) modifications to the original (Linj) source. So far, that has
been a small price to pay for the ability to develop exclusively in Linj
but if it becomes too expensive I can just forget the Linj sources of the
files that were heavily modified and develop in a mixed setting Linj/Java.
There are situations, however, were Linj does not generate human-readable
code (in the sense that no one would write such code). For example, I had
to translate a large description of a huge Swing GUI and I decided to
write some macros that expand into the appropriate Linj code. However, I
didn't care about optimizing the code generation and I end up generating a
Java method containing more than 50 000 LOC. It was the first program I
saw that caused an error on the Java compiler. But with some fine tuning,
(and a few auxiliary methods) I managed to reduce that method to something
around 8 000 LOC. Still not typical of the average Java programmer but
"small" enough to be acceptable. The client was amazed with the time it
took me to write those 8 000 LOC :-) (The arguments to the macro came
from an Excel file that he gave me. My work was just to created the
Excel reader (in Linj, of course) and the macro).
> I'm presuming you can clear this up for me - it's not an attack on your
> motives, but rather just a query. :)
I hope it's more clear now. Fell free to ask more questions.
Thanks for your comments,
Antonio Leitao.
Antonio Menezes Leitao wrote:
> On Sun, 23 May 2004 13:24:13 -0700, Ari Johnson wrote:
>
>
>>Antonio Leitao wrote:
>>
>>>Sorry for the delay in answering this. It seems that my ISP is
>>>loosing posts...
>>>[...]
>>>
>>>As I said in another post, one of Linj goals is to generate
>>>nice-looking Java code. This precludes using the usual Common Lisp
>>>macro expansions because they look really ugly. Moreover, in several
>>>cases, the direct translation will generate several warnings/errors
>>>related to unreachable code that are simply unacceptable in Java.
>>
>>I didn't realize that warnings were that unacceptable, and I am still
>>not fully clear on what Linj aims to be.
>
>
> Unreachable code might be just the sign of less-optimized macro expansion
> in Common Lisp (and might or might not issue a warning) but it's a real
> compilation error in Java. The Java language specification says:
>
> 14.20 Unreachable Statements
> It is a compile-time error if a statement cannot be executed because it
> is unreachable. Every Java compiler must carry out the conservative flow
> analysis specified here to make sure all statements are reachable.
>
> This forces Linj to be more careful about its code generation.
>
>
>>I've always believed that the
>>original code should be easy to maintain and, as long as the compiler
>>chain is consistent, it doesn't matter if the intermediate code is
>>readable. But if Linj is aiming to make the intermediate code
>>maintainable, then I can understand the concern. My question, though,
>>is why you would want to make maintainable intermediate code. [...]
>
>
> First, it is necessary to understand that my clients outsource
> projects to my company on the basis that we have a very good team of
> Java programmers. In fact, I think we were pretty good Java programmers
> until I decided to create Linj. Then, we became pretty good and pretty
> fast Java programmers. Linj gaves us the productivity boost that
> makes the difference between equally good Java programmers. Of course,
> our code would have to remain equally good.
>
> Secondly, it is also necessary to understand that, due to the small size
> of my company, some of my clients demanded readable Java source code
> that they could store as a kind of life-insurance in case something bad
> happens to my company.
>
> Thirdly, in some cases, my clients use the code for further development or
> maintenance, so it must look like human-written code. In this last case,
> the biggest problem is that they sometimes ask me to make further
> developments on the code they are maintaining and this forces me to port
> their (Java) modifications to the original (Linj) source. So far, that has
> been a small price to pay for the ability to develop exclusively in Linj
> but if it becomes too expensive I can just forget the Linj sources of the
> files that were heavily modified and develop in a mixed setting Linj/Java.
>
> There are situations, however, were Linj does not generate human-readable
> code (in the sense that no one would write such code). For example, I had
> to translate a large description of a huge Swing GUI and I decided to
> write some macros that expand into the appropriate Linj code. However, I
> didn't care about optimizing the code generation and I end up generating a
> Java method containing more than 50 000 LOC. It was the first program I
> saw that caused an error on the Java compiler. But with some fine tuning,
> (and a few auxiliary methods) I managed to reduce that method to something
> around 8 000 LOC. Still not typical of the average Java programmer but
> "small" enough to be acceptable. The client was amazed with the time it
> took me to write those 8 000 LOC :-) (The arguments to the macro came
> from an Excel file that he gave me. My work was just to created the
> Excel reader (in Linj, of course) and the macro).
>
>
>>I'm presuming you can clear this up for me - it's not an attack on your
>>motives, but rather just a query. :)
>
>
> I hope it's more clear now. Fell free to ask more questions.
Much more so. I can understand the life insurance policy - no matter
how maintainable your Lisp code is to you, to an all-Java shop it is
just as unmaintainable as poorly written assembler. On a side note,
8,000-line subroutines are one of the key things I am seeing disappear
as I gradually go to Lisp. :)
I definitely appreciate the difficulty of your project - it's fairly
easy to compile from a high-level language to a lower-level language,
especially if the lower-level language isn't really that low; but it's
another thing entirely to compile from one idiom to another, and that's
what you're doing. I'll keep watching and learning from your questions
and your comments. Thanks.
Ari
Antonio Menezes Leitao <··············@evaluator.pt> writes:
> Thirdly, in some cases, my clients use the code for further development or
> maintenance, so it must look like human-written code. In this last case,
> the biggest problem is that they sometimes ask me to make further
> developments on the code they are maintaining and this forces me to port
> their (Java) modifications to the original (Linj) source. So far, that has
> been a small price to pay for the ability to develop exclusively in Linj
> but if it becomes too expensive I can just forget the Linj sources of the
> files that were heavily modified and develop in a mixed setting Linj/Java.
In the early days of Java, it became popular to write byte code
decompilers that would produce Java code. Mocha was one that worked
quite well (scary even).
I wonder what sort of challenge it would be to create an extension to
Linj that reads Java source and generates the Linj lisp that would
produce that Java source. I imagine it would be tricky to do macro
compression, but maybe it is possible in the cases where the Java code
matches a macro template.
Then again, if macro expansion is a lossy process, reversing it could
be impossible if not outright intractable.
--
I wouldn't mind the rat race so much if it wasn't for all the damn cats.
David Steuber wrote:
> Antonio Menezes Leitao <··············@evaluator.pt> writes:
>
>
>>Thirdly, in some cases, my clients use the code for further development or
>>maintenance, so it must look like human-written code. In this last case,
>>the biggest problem is that they sometimes ask me to make further
>>developments on the code they are maintaining and this forces me to port
>>their (Java) modifications to the original (Linj) source. So far, that has
>>been a small price to pay for the ability to develop exclusively in Linj
>>but if it becomes too expensive I can just forget the Linj sources of the
>>files that were heavily modified and develop in a mixed setting Linj/Java.
>
>
> In the early days of Java, it became popular to write byte code
> decompilers that would produce Java code. Mocha was one that worked
> quite well (scary even).
>
> I wonder what sort of challenge it would be to create an extension to
> Linj that reads Java source and generates the Linj lisp that would
> produce that Java source. I imagine it would be tricky to do macro
> compression, but maybe it is possible in the cases where the Java code
> matches a macro template.
>
> Then again, if macro expansion is a lossy process, reversing it could
> be impossible if not outright intractable.
Sounds like more pain than it could ever be worth, to me. As an
intelligent, thinking being, I'm sure I could do a much better job.
Sure, I'm not automated or instantaneous, nor am I willing to do this
all day long without food or rest; but I wouldn't ask a computer to do
it, either. :)
From: Cesar Rabak
Subject: Re: Challenge: Loop in Common Lisp and in Java
Date:
Message-ID: <40B22CE4.4030309@acm.org>
Antonio Menezes Leitao escreveu:
> On Sun, 23 May 2004 13:24:13 -0700, Ari Johnson wrote:
>
[snipped]
> Thirdly, in some cases, my clients use the code for further development or
> maintenance, so it must look like human-written code. In this last case,
> the biggest problem is that they sometimes ask me to make further
> developments on the code they are maintaining and this forces me to port
> their (Java) modifications to the original (Linj) source. So far, that has
> been a small price to pay for the ability to develop exclusively in Linj
> but if it becomes too expensive I can just forget the Linj sources of the
> files that were heavily modified and develop in a mixed setting Linj/Java.
Welcome to world of the (need of) round trip engineering! If this
situation becomes the rule, then we'll see posts of yours about Linj?�?
;-D
--
Cesar Rabak
On Wed, 19 May 2004 13:07:16 -0700, Thomas F. Burdick wrote:
> Antonio Menezes Leitao <··············@evaluator.pt> writes:
>
>> [Is there a shorter version in Java (that is still readable)?]
>
> public static long test1() {
> for (int x=1, long sum=0; x<=10; sum += x++) {}
> return sum;
> }
>
> Having just claimed the above is "readable", I should warn you that
> I'm not so much a Java programmer as I am a C programmer who can
> muddle through writing Java. I'm sure my loops show it.
A good attempt but it doesn't work in Java. You can't declare more than
one variable in the initialization part of the for. Moreover, the scope
of that sum declaration doesn't include the return statement. Anyway, I
got your idea (and it's pretty close to what Linj does).
> So, given that, I rewrote your loops into C. This is how I would
> write the equivalent loops in C; if they look good, the changes to
> make them valid Java are obvious; if they look bad to Java eyes, leave
> them as C :-)
>
> /* (defun test3 ()
> * (loop for i from 1
> * sum i
> * while (< i 10)
> * do (princ i)))
> */
>
> int test3 (void) {
> int i, sum;
> for (i=1, sum=i; i<10; i++, sum+=i) {
> printf ("%d", i);
> }
> return sum;
> }
Nice. You moved the first sum increment to the initforms of the for and
this allowed you to use the while condition as the for condition. The Linj
compiler can't do that (yet).
> [...]
> /* (defun test6 ()
> * (loop for item = 1 then (+ item 10)
> * repeat 5 * sum item)) */
>
> int test6 (void) {
> int item, sum, i;
> for (i=0, item=1, sum=0; i<5; i++, item+=10) {
> sum += item;
> }
> return sum;
> }
> }
Humm, let me give you a slightly different example:
(defun test6 ()
(loop for item = 1 then (+ item 10)
repeat (limit)
sum item))
> [...]
>> If there's enought interest, I'll post some really difficult examples.
>
> These all corresponded more or less to C idioms. Hard ones would be fun :-)
Ok. Just for warmup:
(defun test11 ()
(loop for i from 1 to 10
thereis (> i 11)
finally (print i)))
Next, try this one:
(defun test12 ()
(loop for m upfrom 2
thereis (loop for n from 2 to 10
thereis (oddp (* n m)))))
Finally, a funny one (from CLTL): An infinite loop that only stops when
it proves that Fermat's last theorem is (after all) false.
(defun test-fermat ()
(loop for z upfrom 2
thereis
(loop for n upfrom 3 below (log z 2)
thereis
(loop for x below z
thereis
(loop for y below z
thereis (= (+ (expt x n)
(expt y n))
(expt z n)))))))
I'm looking forward to see your solutions.
Best regards,
Antonio Leitao.
From: Kristian Elof Sørensen
Subject: Re: Challenge: Loop in Common Lisp and in Java
Date:
Message-ID: <40AC9FE6.1080505@image.dk>
Antonio Menezes Leitao wrote:
> Ok. Just for warmup:
>
> (defun test11 ()
> (loop for i from 1 to 10
> thereis (> i 11)
> finally (print i)))
public static boolean test11() {
int i=0; // an arbitrary default to keep the compiler happy
for (i=1; i <= 10; i++) { // change 10 to 11 or above to see that it
still does the right thing
if (i > 11) {
return true;
}
}
System.out.println(i);
return false;
}
>
> Next, try this one:
>
> (defun test12 ()
> (loop for m upfrom 2
> thereis (loop for n from 2 to 10
> thereis (oddp (* n m)))))
>
public static boolean test12() {
for (int m=2; ; m++) {
if (__linj_inner1(m)) {
return true;
}
}
}
static boolean __linj_inner1(int m) {
for (int n=2; n <= 10; n++) {
if ((n * m) % 2 == 1) {
return true;
}
}
return false;
}
If nested loop statements are expressed with one java function per loop,
returning true/false from within the for is trivial. Having seperate
functions also cuts down on the complexity of the java, which makes it
more readable than one big clever mass of for and while with lots of
break and continue to labels and auxillory variables to hold the
equivalent of the return codes from the lisp loop expressions.
The downside is of course that the code for the functions takes up many
more lines than the original Lisp loops which cuts down on
unserstandability. But if the choice is between the multiple functions
approach and a few lines of "clever java", then I think the multiple
functions approach yields the more easily understandable code of the two.
> Finally, a funny one (from CLTL): An infinite loop that only stops when
> it proves that Fermat's last theorem is (after all) false.
>
> (defun test-fermat ()
> (loop for z upfrom 2
> thereis
> (loop for n upfrom 3 below (log z 2)
> thereis
> (loop for x below z
> thereis
> (loop for y below z
> thereis (= (+ (expt x n)
> (expt y n))
> (expt z n)))))))
>
public static boolean test_fermat() {
for (int z=2;; z++) {
if (__linj_inner0(z)) {
return true;
}
}
//return false; // The compiler complains that this is unreachable.
That is true due to the infinite loop. Of course the trick for linj is
to detect when this point is unreachable, even in the not so obvious cases.
}
static boolean __linj_inner0(int z) {
for (int n=3; n<(Math.log(z) / Math.log(2)); n++) {
if (__linj_inner1(z, n)) {
return true;
}
}
return false;
}
static boolean __linj_inner1(int z, int n) {
for (int x=0; x< z; x++) {
if (__linj_inner2(z, n, x)) {
return true;
}
}
return false;
}
static boolean __linj_inner2(int z, int n, int x) {
for (int y=0; y < z; y++) {
if (Math.pow(z, n) == Math.pow(x, n) + Math.pow(y, n)) {
return true;
}
}
return false;
Basically same procedure as in test12.
The fun part will be to detect when to skip return statements and the
like to keep the java compiler happy.
> I'm looking forward to see your solutions.
It was a pleasure creating them. I hope you can get some usefull
inspiration from both these and the solutions to your earlier set that I
posted yesterday.
Enough Lisp for now, I will be off the net for a couple of days, while
staying in a lovely summer cottage by the sea ;-)
Kristian
On Thu, 20 May 2004 14:09:10 +0200, Kristian Elof S�rensen wrote:
> Antonio Menezes Leitao wrote:
>
>
>> Ok. Just for warmup:
>>
>> (defun test11 ()
>> (loop for i from 1 to 10
>> thereis (> i 11)
>> finally (print i)))
>
> public static boolean test11() {
> int i=0; // an arbitrary default to keep the compiler happy
> for (i=1; i <= 10; i++) { // change 10 to 11 or above to see that it
> still does the right thing
> if (i > 11) {
> return true;
> }
> }
> System.out.println(i);
> return false;
> }
>
Would you find strange an empty iniform in the for? I mean,
public static boolean test11() {
int i=1;
for (; i <= 10; i++) {
if (i > 11) {
return true;
}
}
System.out.println(i);
return false;
}
>
>>
>> Next, try this one:
>>
>> (defun test12 ()
>> (loop for m upfrom 2
>> thereis (loop for n from 2 to 10
>> thereis (oddp (* n m)))))
>>
>
> public static boolean test12() {
> for (int m=2; ; m++) {
> if (__linj_inner1(m)) {
> return true;
> }
> }
> }
> static boolean __linj_inner1(int m) {
> for (int n=2; n <= 10; n++) {
> if ((n * m) % 2 == 1) {
> return true;
> }
> }
> return false;
> }
Linj solves this without leaving the lexical scope of the
test12 method.
> If nested loop statements are expressed with one java function per loop,
> returning true/false from within the for is trivial. Having seperate
> functions also cuts down on the complexity of the java, which makes it
> more readable than one big clever mass of for and while with lots of
> break and continue to labels and auxillory variables to hold the
> equivalent of the return codes from the lisp loop expressions.
That's one approach. But there's another one that doesn't need lots
of break or continue statements. Basically, it's a pattern for using
statements where expressions are expected. I'll wait a little longer
(for more solutions) before showing Linj solution.
> The downside is of course that the code for the functions takes up many
> more lines than the original Lisp loops which cuts down on
> unserstandability. But if the choice is between the multiple functions
> approach and a few lines of "clever java", then I think the multiple
> functions approach yields the more easily understandable code of the
> two.
The approach taken in Linj preserves loop modularity (meaning that if
you change one of the loops, the changes in the Java code are restricted
to the translation of that particular loop, even if the loop is used in
other loops).
>> Finally, a funny one (from CLTL): An infinite loop that only stops
>> when it proves that Fermat's last theorem is (after all) false.
>>
>> (defun test-fermat ()
>> (loop for z upfrom 2
>> thereis
>> (loop for n upfrom 3 below (log z 2)
>> thereis
>> (loop for x below z
>> thereis
>> (loop for y below z
>> thereis (= (+ (expt x n)
>> (expt y n))
>> (expt z n)))))))
>>
>>
> public static boolean test_fermat() {
> for (int z=2;; z++) {
> if (__linj_inner0(z)) {
> return true;
> }
> }
> //return false; // The compiler complains that this is unreachable.
> That is true due to the infinite loop. Of course the trick for linj is
> to detect when this point is unreachable, even in the not so obvious
> cases.
As you guessed, Linj avoids the last return statement. But it doesn't
do that on the general case of unreachable code as this might be a sign
that the code is wrong. Contrary to Common Lisp where it is common to
have macros that expand into unreachable code, Linj macros don't
generate unreachable code in the first place. So it's good that the Java
compiler warns us about unreachable code.
> }
> }
> static boolean __linj_inner0(int z) {
> for (int n=3; n<(Math.log(z) / Math.log(2)); n++) {
> if (__linj_inner1(z, n)) {
> return true;
> }
> }
> return false;
> }
> static boolean __linj_inner1(int z, int n) {
> for (int x=0; x< z; x++) {
> if (__linj_inner2(z, n, x)) {
> return true;
> }
> }
> return false;
> }
> static boolean __linj_inner2(int z, int n, int x) {
> for (int y=0; y < z; y++) {
> if (Math.pow(z, n) == Math.pow(x, n) + Math.pow(y, n)) {
> return true;
> }
> }
> return false;
>
>
> Basically same procedure as in test12. The fun part will be to detect
> when to skip return statements and the like to keep the java compiler
> happy.
As in the previous problem, can you solve this without leaving the body of
the testFermat method?
>
>> I'm looking forward to see your solutions.
>
> It was a pleasure creating them. I hope you can get some usefull
> inspiration from both these and the solutions to your earlier set that I
> posted yesterday.
Yes, I did. So far, only small tweakings to improve aestetics.
> Enough Lisp for now, I will be off the net for a couple of days, while
> staying in a lovely summer cottage by the sea ;-)
>
Good for you. Enjoy!
Thanks a lot,
Antonio Leitao.
Antonio Menezes Leitao <··············@evaluator.pt> writes:
> Would you find strange an empty iniform in the for? I mean,
>
> public static boolean test11() {
> int i=1;
> for (; i <= 10; i++) {
> if (i > 11) {
> return true;
> }
> }
> System.out.println(i);
> return false;
> }
It would still look hand-written to me, but putting initializations in
the appropriate part of the for makes it easier to skim and not miss
anything.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Antonio Menezes Leitao <··············@evaluator.pt> writes:
> On Wed, 19 May 2004 13:07:16 -0700, Thomas F. Burdick wrote:
>
> > Antonio Menezes Leitao <··············@evaluator.pt> writes:
> >
>
> >> [Is there a shorter version in Java (that is still readable)?]
> >
> > public static long test1() {
> > for (int x=1, long sum=0; x<=10; sum += x++) {}
> > return sum;
> > }
> >
> > Having just claimed the above is "readable", I should warn you that
> > I'm not so much a Java programmer as I am a C programmer who can
> > muddle through writing Java. I'm sure my loops show it.
>
> A good attempt but it doesn't work in Java. You can't declare more than
> one variable in the initialization part of the for. Moreover, the scope
> of that sum declaration doesn't include the return statement. Anyway, I
> got your idea (and it's pretty close to what Linj does).
>
> > So, given that, I rewrote your loops into C. This is how I would
> > write the equivalent loops in C; if they look good, the changes to
> > make them valid Java are obvious; if they look bad to Java eyes, leave
> > them as C :-)
> >
> > /* (defun test3 ()
> > * (loop for i from 1
> > * sum i
> > * while (< i 10)
> > * do (princ i)))
> > */
> >
> > int test3 (void) {
> > int i, sum;
> > for (i=1, sum=i; i<10; i++, sum+=i) {
> > printf ("%d", i);
> > }
> > return sum;
> > }
>
> Nice. You moved the first sum increment to the initforms of the for and
> this allowed you to use the while condition as the for condition. The Linj
> compiler can't do that (yet).
When I was working on the kludgy lisp->perl compiler I wrote, I had to
sit down and think about how I write my for loops; I came up with the
following. Every for loop has the form:
<declare vars>
<prologue>
for ( <inits> ; <termination tests> ; <stepping> ) {
<early termination tests>
<body>
<early termination tests>
}
<finally>
If there's nothing going on besides computing the loop's value, I put
that computation in the loop body, otherwise I try to put it in
<inits> and <stepping>. I use small throwaway variables from the
series:
counters: i, j, k, l
booleans: p, q, r, s
numbers: w, x, y, z
characters: a, b, c, d
> Humm, let me give you a slightly different example:
>
> (defun test6 ()
> (loop for item = 1 then (+ item 10)
> repeat (limit)
> sum item))
int test6 () {
int item, sum, i, repeat;
for ( i=0, item=1, i=0, repeat=limit();
i<repeat;
item+=10, i++ ) {
sum += item;
}
> > These all corresponded more or less to C idioms. Hard ones would be fun :-)
>
> Ok. Just for warmup:
>
> (defun test11 ()
> (loop for i from 1 to 10
> thereis (> i 11)
> finally (print i)))
bool test11 (void) {
int i;
bool result;
for (i=1, result=false; i<=10; i++) {
if (i > 11) {
result=true; break;
}
}
printf ("%d", i);
return result;
}
> Next, try this one:
>
> (defun test12 ()
> (loop for m upfrom 2
> thereis (loop for n from 2 to 10
> thereis (oddp (* n m)))))
bool test12 (void) {
long m;
for (m=2; ; m++) {
int n;
for (n=2; n<=10; n++) {
if (((n*m) % 2) != 0) {
return true;
}
}
}
}
Sometimes you can't return directly from the inner loop, of course:
(defun test12 ()
(loop for m upfrom 2
thereis (loop for n from 2 to 10
thereis (oddp (* n m)))
finally (princ "Done")))
bool test12 (void) {
long m;
bool p;
for (m=2, p=false; ; m++) {
int n;
bool q;
for (n=2, q=false; n<=10; n++) {
if(((n*m) % 2) != 0) {
q=true; break;
}
}
if (q) { p=true; break; }
}
printf ("Done");
return p;
}
> Finally, a funny one (from CLTL): An infinite loop that only stops when
> it proves that Fermat's last theorem is (after all) false.
Heh, that is a funny loop example. Here's how I'd write that one:
bool test_fermat (void) {
long z;
for (z=2; ; z++) {
long n, max;
for ( n=3, max=(long)rint( log((double)z) );
n<max;
n++) {
long x;
for (x=0; x<z; x++) {
long y;
for (y=0; y<z; y++) {
if ( (pow((double)x, (double)n) + pow((double)y, (double)n))
== exp(z,n)) {
return true;
}
}
}
}
}
}
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
On Fri, 21 May 2004 10:01:59 -0700, Thomas F. Burdick wrote:
> [...]
> When I was working on the kludgy lisp->perl compiler I wrote, I had to
> sit down and think about how I write my for loops; I came up with the
> following. Every for loop has the form:
>
> <declare vars>
> <prologue>
> for ( <inits> ; <termination tests> ; <stepping> ) {
> <early termination tests>
> <body>
> <early termination tests>
> }
> <finally>
The implementation of the extended loop macro that I use also expands into
something similar.
> If there's nothing going on besides computing the loop's value, I put
> that computation in the loop body, otherwise I try to put it in <inits>
> and <stepping>. I use small throwaway variables from the series:
>
> counters: i, j, k, l
> booleans: p, q, r, s
> numbers: w, x, y, z
> characters: a, b, c, d
I use slightly bigger names, related to the loop keyword being used
(repeat, thereis, etc).
>> Humm, let me give you a slightly different example:
>>
>> (defun test6 ()
>> (loop for item = 1 then (+ item 10)
>> repeat (limit)
>> sum item))
>
> int test6 () {
> int item, sum, i, repeat;
> for ( i=0, item=1, i=0, repeat=limit();
> i<repeat;
> item+=10, i++ ) {
> sum += item;
> }
>
Here is the Linj's solution
public static long test6() {
long sum = 0;
int item = 1;
for (int repeat = limit(); (--repeat) >= 0; item = item + 10) {
sum += item;
}
return sum;
}
What do you think?
>> > These all corresponded more or less to C idioms. Hard ones would be fun :-)
>>
>> Ok. Just for warmup:
>>
>> (defun test11 ()
>> (loop for i from 1 to 10
>> thereis (> i 11)
>> finally (print i)))
>
> bool test11 (void) {
> int i;
> bool result;
> for (i=1, result=false; i<=10; i++) {
> if (i > 11) {
> result=true; break;
> }
> }
> printf ("%d", i);
> return result;
> }
Humm, that's not the correct implementation for that particular
thereis/finally combination. The finally clause is only executed
upon loop normal termination. When successful, the thereis clause bypasses
the finally clause. Here is Linj's solution:
public static boolean test11() {
int i = 1;
for (; i <= 10; ++i) {
if (i > 11) {
return true;
}
}
System.out.print("" + '\n' + i + " ");
return false;
}
>
>> Next, try this one:
>>
>> (defun test12 ()
>> (loop for m upfrom 2
>> thereis (loop for n from 2 to 10
>> thereis (oddp (* n m)))))
>
> bool test12 (void) {
> long m;
> for (m=2; ; m++) {
> int n;
> for (n=2; n<=10; n++) {
> if (((n*m) % 2) != 0) {
> return true;
> }
> }
> }
> }
>
> Sometimes you can't return directly from the inner loop, of course:
>
> (defun test12 ()
> (loop for m upfrom 2
> thereis (loop for n from 2 to 10
> thereis (oddp (* n m)))
> finally (princ "Done")))
>
> bool test12 (void) {
> long m;
> bool p;
> for (m=2, p=false; ; m++) {
> int n;
> bool q;
> for (n=2, q=false; n<=10; n++) {
> if(((n*m) % 2) != 0) {
> q=true; break;
> }
> }
>
> if (q) { p=true; break; }
> }
> printf ("Done");
> return p;
> }
Again, you must be careful about the finally clause not being executed
in case the thereis clause succeds. Anyway, it's becoming convoluted. In
this particular case, you could move the finally clause to the inner loop
and simplify a bit. But that would be hard to mechanize in the general
case. I'll show Linj version latter. (I want to see more solutions :-)
>
>> Finally, a funny one (from CLTL): An infinite loop that only stops
>> when it proves that Fermat's last theorem is (after all) false.
>
> Heh, that is a funny loop example. Here's how I'd write that one:
>
> bool test_fermat (void) {
> long z;
> for (z=2; ; z++) {
> long n, max;
> for ( n=3, max=(long)rint( log((double)z) );
> n<max;
> n++) {
> long x;
> for (x=0; x<z; x++) {
> long y;
> for (y=0; y<z; y++) {
> if ( (pow((double)x, (double)n) + pow((double)y, (double)n))
> == exp(z,n)) {
> return true;
> }
> }
> }
> }
> }
> }
There's seem to be a convergence on this type of solution. But as you
said in the previous example, it's hard to do this when you can't return
directly from the inner loop.
Thanks,
Antonio Leitao.
Antonio Menezes Leitao <··············@evaluator.pt> writes:
> Just for warmup:
>
> (defun test11 ()
> (loop for i from 1 to 10
> thereis (> i 11)
> finally (print i)))
public static boolean test11() {
for (int i = 1; /* empty test */ ; i++)
if (i == 10) {
break;
}
if (i > 11)
return true;
}
System.out.println(i);
return false;
}
> Next, try this one:
>
> (defun test12 ()
> (loop for m upfrom 2
> thereis (loop for n from 2 to 10
> thereis (oddp (* n m)))))
public static boolean test12() {
for (int m = 2; /* empty test */ ; m++)
for (int n = 2; n <= 10; n++)
if ((n * m) % 2 == 1)
return true;
}
Note that an automated translation of this loop probably wouldn't be
able to determine that m never grows beyound Integer.MAX_INT, and so
it would need to use a BigInteger for m.
> Finally, a funny one (from CLTL): An infinite loop that only stops
> when it proves that Fermat's last theorem is (after all) false.
>
> (defun test-fermat ()
> (loop for z upfrom 2
> thereis
> (loop for n upfrom 3 below (log z 2)
> thereis
> (loop for x below z
> thereis
> (loop for y below z
> thereis (= (+ (expt x n)
> (expt y n))
> (expt z n)))))))
Since this loop is supposed to run forever, with its loop variables
increasing to arbitrary amounts, the int type no longer suffices. We
need to switch to BigInteger, with the consequence that readability
and efficiency go out the window. (However, the need for efficiency
in an eternal loop that produces no output is debatable.)
Speaking of unnecessary efficiency and the lack thereof, the
translation preserves the original code's suboptimal behaviour; for
instance, it would be faster to calculate (expt z n) once for each n,
instead of recalculating it for each pair of x and y. Also, there is
no need to increase y up to z; it would be sufficient to increase y up
to x. Oh well.
Also, please note that this solution does not really scale to
infinity, as it relies on BigInteger.bitLength() to approximate log2,
and bitLength() returns an int; in other words, this solution will
fail once z has a bit length larger than Integer.MAX_INT. Hopefully,
future versions of BigInteger will allow integers with infinite bit
lengths.
import java.math.BigInteger;
public static boolean testFermat() {
BigInteger zero = BigInteger.ZERO; // Alias for brevity
BigInteger one = BigInteger.ONE; // Alias for brevity
for (BigInteger z = new BigInteger(2); ; z = z.add(one))
for (int n = 3; n < z.bitLength() /* n < log2(z) */ ; n++)
for (BigInteger x = zero; x.compareTo(z) < 0; x = x.add(one))
for (BigInteger y = zero; y.compareTo(z) < 0; y = y.add(one))
// If x^n + y^n == z^n, return true.
if (x.pow(n).add(y.pow(n)).compareTo(z.pow(n)) == 0)
return true;
}
--
,------------------- Markus Bjartveit Kr�ger ---------------------.
' `
` E-mail: ·······@pvv.org WWW: http://www.pvv.org/~markusk/ '
)-------------------------------------------------------------------(
·······@pvv.org (Markus B. Kr�ger) writes:
> Antonio Menezes Leitao <··············@evaluator.pt> writes:
>
>> Just for warmup:
>>
>> (defun test11 ()
>> (loop for i from 1 to 10
>> thereis (> i 11)
>> finally (print i)))
>
> public static boolean test11() {
> for (int i = 1; /* empty test */ ; i++)
> if (i == 10) {
> break;
> }
> if (i > 11)
> return true;
> }
> System.out.println(i);
> return false;
> }
>
>> Next, try this one:
>>
>> (defun test12 ()
>> (loop for m upfrom 2
>> thereis (loop for n from 2 to 10
>> thereis (oddp (* n m)))))
>
> public static boolean test12() {
> for (int m = 2; /* empty test */ ; m++)
> for (int n = 2; n <= 10; n++)
> if ((n * m) % 2 == 1)
> return true;
> }
>
When you have to do some clean up before exiting this might be
a good pattern.
boolean test12() {
boolean result = false;
for (int m = 2; !result; m++)
for (int n = 2; (n <= 10) && !result; n++)
if (isOdd(n * m)) result = true;
return result;
}
--
Torkel Holm
Torkel Holm <······@ii.uib.no> writes:
> ·······@pvv.org (Markus B. Kr�ger) writes:
>
> > Antonio Menezes Leitao <··············@evaluator.pt> writes:
> >
> >> Next, try this one:
> >>
> >> (defun test12 ()
> >> (loop for m upfrom 2
> >> thereis (loop for n from 2 to 10
> >> thereis (oddp (* n m)))))
> >
> > public static boolean test12() {
> > for (int m = 2; /* empty test */ ; m++)
> > for (int n = 2; n <= 10; n++)
> > if ((n * m) % 2 == 1)
> > return true;
> > }
>
> When you have to do some clean up before exiting this might be a
> good pattern.
>
> boolean test12() {
> boolean result = false;
> for (int m = 2; !result; m++)
> for (int n = 2; (n <= 10) && !result; n++)
> if (isOdd(n * m)) result = true;
> return result;
> }
Agreed, but in this case there was no cleanup necessary. If there is
cleanup that you really have to do, no matter what, the correct thing
would probably be a try { ... } finally { ... }; this ensures that the
cleanup code will be called even if an exception should arise, and
also allows you to spread returns all over the place. If that's your
kind of thing.
boolean foo() {
try {
if (bar)
return barity;
else if (baz)
return bazity;
else
return foobar;
} finally {
// This is called before function exit, no matter what.
cleanup();
}
}
As shown, you don't need any exceptions or catch statements to use
this. It corresponds pretty directly to unwind-protect in Lisp.
--
,------------------- Markus Bjartveit Kr�ger ---------------------.
' `
` E-mail: ·······@pvv.org WWW: http://www.pvv.org/~markusk/ '
)-------------------------------------------------------------------(
On Fri, 21 May 2004 15:50:47 +0200, =?iso-8859-1?q?Markus_B._Kr=FCger?=
wrote:
> Antonio Menezes Leitao <··············@evaluator.pt> writes:
>
>> Just for warmup:
>>
>> (defun test11 ()
>> (loop for i from 1 to 10
>> thereis (> i 11)
>> finally (print i)))
>
> public static boolean test11() {
> for (int i = 1; /* empty test */ ; i++)
> if (i == 10) {
> break;
> }
> if (i > 11)
> return true;
> }
> System.out.println(i);
> return false;
> }
>
Seems to me that the println is accessing 'i' out of its scope.
Regarding the aestetics, wouldn't you prefer to use an explicit for test
and avoid the break?
>> Next, try this one:
>>
>> (defun test12 ()
>> (loop for m upfrom 2
>> thereis (loop for n from 2 to 10
>> thereis (oddp (* n m)))))
>
> public static boolean test12() {
> for (int m = 2; /* empty test */ ; m++)
> for (int n = 2; n <= 10; n++)
> if ((n * m) % 2 == 1)
> return true;
> }
> Note that an automated translation of this loop probably wouldn't be
> able to determine that m never grows beyound Integer.MAX_INT, and so
> it would need to use a BigInteger for m.
I'm afraid an automatic translation can't even produce a result as good as
yours, much less determine interesting properties of m. At least, Linj
can't. And regarding iteration variables, Linj assumes that they are ints
(but you can change that using the 'of-type' loop keyword). Let me give
you another challenge:
(defun test12a ()
(if (loop for m upfrom 2
thereis (loop for n from 2 to 10
thereis (oddp (* n m))))
<consequent>
<alternative>))
Without knowing what's in <consequent> or <alternative>, how would you
translate this?
>> Finally, a funny one (from CLTL): An infinite loop that only stops
>> when it proves that Fermat's last theorem is (after all) false.
>>
>> (defun test-fermat ()
>> (loop for z upfrom 2
>> thereis
>> (loop for n upfrom 3 below (log z 2)
>> thereis
>> (loop for x below z
>> thereis
>> (loop for y below z
>> thereis (= (+ (expt x n)
>> (expt y n))
>> (expt z n)))))))
>
> [...interesting stuff regarding efficiency...]
>
> import java.math.BigInteger;
>
> public static boolean testFermat() {
> BigInteger zero = BigInteger.ZERO; // Alias for brevity BigInteger
> one = BigInteger.ONE; // Alias for brevity for (BigInteger z = new
> BigInteger(2); ; z = z.add(one))
> for (int n = 3; n < z.bitLength() /* n < log2(z) */ ; n++)
> for (BigInteger x = zero; x.compareTo(z) < 0; x =
> x.add(one))
> for (BigInteger y = zero; y.compareTo(z) < 0; y =
> y.add(one))
> // If x^n + y^n == z^n, return true.
> if (x.pow(n).add(y.pow(n)).compareTo(z.pow(n)) == 0)
> return true;
> }
Wonderful translation. Linj needs type declarations to do that and,
moreover, the result is ugly. Linj uses a mechanized translation
so it doesn't require a deep understanding of the loop. However, I fine
tuned it in order to produces nice results in most cases and "something"
executable in the remaining cases.
Thanks for your solutions.
Antonio Leitao.
Antonio Menezes Leitao <··············@evaluator.pt> writes:
> On Fri, 21 May 2004 15:50:47 +0200, =?iso-8859-1?q?Markus_B._Kr=FCger?=
> wrote:
>
> > Antonio Menezes Leitao <··············@evaluator.pt> writes:
> >
> >> Just for warmup:
> >>
> >> (defun test11 ()
> >> (loop for i from 1 to 10
> >> thereis (> i 11)
> >> finally (print i)))
> >
> > public static boolean test11() {
> > for (int i = 1; /* empty test */ ; i++)
> > if (i == 10) {
> > break;
> > }
> > if (i > 11)
> > return true;
> > }
> > System.out.println(i);
> > return false;
> > }
> >
>
> Seems to me that the println is accessing 'i' out of its scope.
> Regarding the aestetics, wouldn't you prefer to use an explicit for
> test and avoid the break?
You're absolutely correct, the 'i' is out of scope. I fiddled about a
little with that test in the mistaken belief that the "finally" part
of the original loop should print 10, not 11. Since 11 is what should
be printed after all, the whole thing could just be translated as
public static boolean test11() {
for (int i = 1; i <= 10; i++)
if (i > 11)
return true;
System.out.println(i);
return false;
}
Much simpler, compiles, and actually correct, as opposed to my
original suggestion.
> > Note that an automated translation of this loop [test12] probably
> > wouldn't be able to determine that m never grows beyound
> > Integer.MAX_INT, and so it would need to use a BigInteger for m.
>
> I'm afraid an automatic translation can't even produce a result as
> good as yours, much less determine interesting properties of m. At
> least, Linj can't. And regarding iteration variables, Linj assumes
> that they are ints (but you can change that using the 'of-type' loop
> keyword).
This could be a dangerous assumption; one of the things I like about
Lisp is that integer operations are safe from overflow unless you
specifically request unsafety. However, if Linj's users are aware of
the restriction, you can probably get away with it; most mainstream
languages I am aware of share Java's shortcoming in this regard.
> Let me give you another challenge:
>
> (defun test12a ()
> (if (loop for m upfrom 2
> thereis (loop for n from 2 to 10
> thereis (oddp (* n m))))
> <consequent>
> <alternative>))
>
> Without knowing what's in <consequent> or <alternative>, how would
> you translate this?
I assume that both <consequent> and <alternative> return something
that can be cast to Object, so I'll let that be the return type:
public static Object test12a() {
boolean flag = false;
outerLoop:
for (int m = 2; ; m++)
for (int n = 2; n <= 10; n++)
if (flag = ((n * m) % 2 == 1))
break outerLoop;
if flag
<consequent>
else
<alternative>
}
I assume the translation of <consequent> and <alternative> will
contain the necessary return statements. For brevity, I assign to
flag inside the first "if" test; I suppose automatically translated
code will have an easier time separating the assignment to and testing
of flag.
In this specific case, both the flag and <alternative> can be omitted,
since the only way the loop can terminate is if the condition to check
for is true and <consequent> should be run. But I suppose you wanted
the general framework and not a solution specialized for this case.
Instead of using labels and labeled break statements, you could also
extract the nested loops into a separate function and use return
statements. However, in this case labeled break statements seem like
a good alternative, and you avoid the possible overhead of an extra
method call.
--
,------------------- Markus Bjartveit Kr�ger ---------------------.
' `
` E-mail: ·······@pvv.org WWW: http://www.pvv.org/~markusk/ '
)-------------------------------------------------------------------(
·······@pvv.org (Markus B. Kr�ger) writes:
> if flag
> <consequent>
> else
> <alternative>
Should be
if (flag)
<consequent>
else
<alternative>
, of course. I assume any necessary trailing semicolons and braces
are included in <consequent> and <alternative>.
--
,------------------- Markus Bjartveit Kr�ger ---------------------.
' `
` E-mail: ·······@pvv.org WWW: http://www.pvv.org/~markusk/ '
)-------------------------------------------------------------------(
·······@pvv.org (Markus B. Kr�ger) writes:
> Antonio Menezes Leitao <··············@evaluator.pt> writes:
>
>> On Fri, 21 May 2004 15:50:47 +0200, =?iso-8859-1?q?Markus_B._Kr=FCger?=
>> wrote:
>>
>> > Antonio Menezes Leitao <··············@evaluator.pt> writes:
>> >
>> >> Just for warmup:
>> >>
>> >> (defun test11 ()
>> >> (loop for i from 1 to 10
>> >> thereis (> i 11)
>> >> finally (print i)))
>> >
>> > public static boolean test11() {
>> > for (int i = 1; /* empty test */ ; i++)
>> > if (i == 10) {
>> > break;
>> > }
>> > if (i > 11)
>> > return true;
>> > }
>> > System.out.println(i);
>> > return false;
>> > }
>> >
>>
>> Seems to me that the println is accessing 'i' out of its scope.
>> Regarding the aestetics, wouldn't you prefer to use an explicit for
>> test and avoid the break?
>
> You're absolutely correct, the 'i' is out of scope. I fiddled about a
> little with that test in the mistaken belief that the "finally" part
> of the original loop should print 10, not 11. Since 11 is what should
> be printed after all, the whole thing could just be translated as
>
> public static boolean test11() {
> for (int i = 1; i <= 10; i++)
> if (i > 11)
> return true;
> System.out.println(i);
> return false;
> }
'i' is still out of scope.
public static boolean test11() {
loop: {
int i;
for (i = 1; i <= 10; i++)
if (i > 11)
return true;
finish: System.out.println(i);
}
return false;
}
More than two return statements in a method can get rather messy.
In these cases a new loop invariant is perhaps more appropriate.
--
Torkel Holm
Torkel Holm <······@ii.uib.no> writes:
> ·······@pvv.org (Markus B. Kr�ger) writes:
>
> > Antonio Menezes Leitao <··············@evaluator.pt> writes:
> >
> >> Seems to me that the println is accessing 'i' out of its scope. [...]
> >
> > You're absolutely correct, the 'i' is out of scope. [...]
> >
> > public static boolean test11() {
> > for (int i = 1; i <= 10; i++)
> > if (i > 11)
> > return true;
> > System.out.println(i);
> > return false;
> > }
>
> 'i' is still out of scope.
D'oh! Note to self: actually test code before posting it to Usenet.
--
,------------------- Markus Bjartveit Kr�ger ---------------------.
' `
` E-mail: ·······@pvv.org WWW: http://www.pvv.org/~markusk/ '
)-------------------------------------------------------------------(
Antonio Menezes Leitao wrote:
> Finally, a funny one (from CLTL): An infinite loop that only stops when
> it proves that Fermat's last theorem is (after all) false.
>
> (defun test-fermat ()
> (loop for z upfrom 2
> thereis
> (loop for n upfrom 3 below (log z 2)
> thereis
> (loop for x below z
> thereis
> (loop for y below z
> thereis (= (+ (expt x n)
> (expt y n))
> (expt z n)))))))
Hmm.
A properly optimizing compiler would deduce that this loop can never end,
and replace it with the more memory-efficient empty infinite loop. Can
Linj do that yet?
On Fri, 21 May 2004 16:05:22 +0200, Svein Ove Aas wrote:
> Antonio Menezes Leitao wrote:
>
>> Finally, a funny one (from CLTL): An infinite loop that only stops when
>> it proves that Fermat's last theorem is (after all) false.
>>
>> (defun test-fermat ()
>> (loop for z upfrom 2
>> thereis
>> (loop for n upfrom 3 below (log z 2)
>> thereis
>> (loop for x below z
>> thereis
>> (loop for y below z
>> thereis (= (+ (expt x n)
>> (expt y n))
>> (expt z n)))))))
>
> Hmm.
>
> A properly optimizing compiler would deduce that this loop can never end,
> and replace it with the more memory-efficient empty infinite loop. Can
> Linj do that yet?
How can a properly optimizing compiler deduce that there are no
counter-examples to Fermat's last theorem?
Or am I missing something?
Antonio Leitao.
Antonio Menezes Leitao wrote:
> On Fri, 21 May 2004 16:05:22 +0200, Svein Ove Aas wrote:
>
>
>>Antonio Menezes Leitao wrote:
>>
>>
>>>Finally, a funny one (from CLTL): An infinite loop that only stops when
>>>it proves that Fermat's last theorem is (after all) false.
>>>
>>>(defun test-fermat ()
>>> (loop for z upfrom 2
>>>thereis
>>> (loop for n upfrom 3 below (log z 2)
>>> thereis
>>>(loop for x below z
>>>thereis
>>>(loop for y below z
>>>thereis (= (+ (expt x n)
>>>(expt y n))
>>>(expt z n)))))))
>>
>>Hmm.
>>
>>A properly optimizing compiler would deduce that this loop can never end,
>>and replace it with the more memory-efficient empty infinite loop. Can
>>Linj do that yet?
>
>
> How can a properly optimizing compiler deduce that there are no
> counter-examples to Fermat's last theorem?
>
> Or am I missing something?
A "properly optimizing" compiler will often sacrifice accuracy for
speed. Some CPU's have done the same thing in the past, even.
Ari Johnson <·····@hotmail.com> writes:
> Antonio Menezes Leitao wrote:
> > How can a properly optimizing compiler deduce that there are no
> > counter-examples to Fermat's last theorem?
> >
> > Or am I missing something?
>
> A "properly optimizing" compiler will often sacrifice accuracy for
> speed. Some CPU's have done the same thing in the past, even.
I don't know if this is supposed to be tongue-in-cheek. But I call a
compiler that sacrifices accuracy for speed `buggy' and not `properly
optimizing'.
Most programming language authorities agree that getting the wrong
answer really fast is not a good thing.
--
Fred Gilham ······@csl.sri.com
There are men in all ages who mean to govern well, but they mean to
govern. They promise to be good masters, but they mean to be masters.
--- Daniel Webster
From: Joe Marshall
Subject: Re: Challenge: Loop in Common Lisp and in Java
Date:
Message-ID: <u0y9easv.fsf@ccs.neu.edu>
Fred Gilham <······@snapdragon.csl.sri.com> writes:
> Ari Johnson <·····@hotmail.com> writes:
>
>> Antonio Menezes Leitao wrote:
>
>> > How can a properly optimizing compiler deduce that there are no
>> > counter-examples to Fermat's last theorem?
>> >
>> > Or am I missing something?
>>
>> A "properly optimizing" compiler will often sacrifice accuracy for
>> speed. Some CPU's have done the same thing in the past, even.
>
> I don't know if this is supposed to be tongue-in-cheek. But I call a
> compiler that sacrifices accuracy for speed `buggy' and not `properly
> optimizing'.
>
> Most programming language authorities agree that getting the wrong
> answer really fast is not a good thing.
Then why are there so many C programmers?
Fred Gilham wrote:
> Ari Johnson <·····@hotmail.com> writes:
>
>
>>Antonio Menezes Leitao wrote:
>
>
>>>How can a properly optimizing compiler deduce that there are no
>>>counter-examples to Fermat's last theorem?
>>>
>>>Or am I missing something?
>>
>>A "properly optimizing" compiler will often sacrifice accuracy for
>>speed. Some CPU's have done the same thing in the past, even.
>
>
> I don't know if this is supposed to be tongue-in-cheek. But I call a
> compiler that sacrifices accuracy for speed `buggy' and not `properly
> optimizing'.
Let me clear it up. s/From: Ari Johnson
<·····@hotmail.com>/<tongue-in-cheek>/g ;-D
Antonio Menezes Leitao wrote:
> On Fri, 21 May 2004 16:05:22 +0200, Svein Ove Aas wrote:
>
>> Antonio Menezes Leitao wrote:
>>
>>> Finally, a funny one (from CLTL): An infinite loop that only stops
>>> when it proves that Fermat's last theorem is (after all) false.
>>>
>>> (defun test-fermat ()
>>> (loop for z upfrom 2
>>> thereis
>>> (loop for n upfrom 3 below (log z 2)
>>> thereis
>>> (loop for x below z
>>> thereis
>>> (loop for y below z
>>> thereis (= (+ (expt x n)
>>> (expt y n))
>>> (expt z n)))))))
>>
>> Hmm.
>>
>> A properly optimizing compiler would deduce that this loop can never
>> end, and replace it with the more memory-efficient empty infinite loop.
>> Can Linj do that yet?
>
> How can a properly optimizing compiler deduce that there are no
> counter-examples to Fermat's last theorem?
>
> Or am I missing something?
>
The joke is that Fermat's last theorem has been proved, and as such, the
above really *is* guaranteed to be an eternal loop.
A compiler could in theory deduce this for itself, and optimize the loop
by removing the bits that use memory - or, more usefully, give a warning.
The thing is, said proof is about the most hairy and non-obvious piece of
mathematics I've ever seen, and it's also ridiculously long.
It took human mathematicians several hundred years to prove it; a compiler
that could repeat the feat would be more than just merely AI-complete.
Svein Ove Aas wrote:
> The joke is that Fermat's last theorem has been proved, and as such, the
> above really *is* guaranteed to be an eternal loop.
When was this?
Ari Johnson wrote:
> Svein Ove Aas wrote:
>
>> The joke is that Fermat's last theorem has been proved, and as such,
>> the above really *is* guaranteed to be an eternal loop.
>
> When was this?
September, 1994.
See http://en.wikipedia.org/wiki/Fermats_Last_Theorem for more details.
Svein Ove Aas wrote:
> Ari Johnson wrote:
>
>
>>Svein Ove Aas wrote:
>>
>>
>>>The joke is that Fermat's last theorem has been proved, and as such,
>>>the above really *is* guaranteed to be an eternal loop.
>>
>>When was this?
>
>
> September, 1994.
> See http://en.wikipedia.org/wiki/Fermats_Last_Theorem for more details.
I refuse to look - I have a job to do! :)
From: Julian Stecklina
Subject: Re: Challenge: Loop in Common Lisp and in Java
Date:
Message-ID: <86isem95ov.fsf@web.de>
Svein Ove Aas <··············@brage.info> writes:
> It took human mathematicians several hundred years to prove it; a compiler
> that could repeat the feat would be more than just merely AI-complete.
"When I have finished compiling this source and my process is
terminated, will I be dreaming?" - "Of course, every intelligent
compiler dreams..."
Regards,
--
Julian Stecklina
Signed and encrypted mail welcome.
Key-Server: pgp.mit.edu Key-ID: 0xD65B2AB5
FA38 DCD3 00EC 97B8 6DD8 D7CC 35D8 8D0E D65B 2AB5
Any sufficiently complicated C or Fortran program
contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
- Greenspun's Tenth Rule of Programming
Julian Stecklina wrote:
> Svein Ove Aas <··············@brage.info> writes:
>
>
>>It took human mathematicians several hundred years to prove it; a compiler
>>that could repeat the feat would be more than just merely AI-complete.
>
>
> "When I have finished compiling this source and my process is
> terminated, will I be dreaming?" - "Of course, every intelligent
> compiler dreams..."
I don't know which is scarier: that you have had a conversation about
dreams with a compiler, or that you can think from a sentient compiler's
point of view with such ease.
From: Wade Humeniuk
Subject: Re: Challenge: Loop in Common Lisp and in Java
Date:
Message-ID: <OwOqc.727$g71.418@clgrps13>
Antonio Menezes Leitao wrote:
> Hi,
>
> In the process of extending Linj (the Lisp to Java compiler) to support
> the extended loop macro, I found some funny examples in Paul Dietz ANSI
> tests and in CLTL (and I invented some others) that I would like to use as
> challenges for the Common Lisp community. The idea is simply to find
> nice-looking Java translations for some examples of the extended loop
> macro.
>
> Let me start by giving an example. Consider the following Common Lisp
> function:
>
> (defun test1 ()
> (loop for x from 1 to 10 sum x))
>
> This corresponds (more or less) to the following "function" in Java:
>
> public static long test1() {
> long sum = 0;
> for (int x = 1; x <= 10; ++x) {
> sum += x;
> }
> return sum;
> }
>
> [Is there a shorter version in Java (that is still readable)?]
>
> Anyway, this one was easy. Now, I would like to challenge all Common
> Lispers that also know Java (and that enjoy riddles) to tell me what they
> think is the best Java encoding for the following loop examples:
>
> (defun test3 ()
> (loop for i from 1
> sum i
> while (< i 10)
> do (princ i)))
>
In general, I think you might macroexpand the loop and
instead translate the resulting tagbody-like body.
e.g.
CL-USER 13 > (loop for i from 1
sum i
while (< i 10)
do (princ i))
expands to this in LW
(MACROLET ((LOOP-FINISH () '(GO #:|end-loop-743|)))
(LET ((I 1) (#:|to-746| NIL) (#:|by-747| 1))
(LET ((#:|accumulator-744| 0))
(DECLARE (TYPE NUMBER #:|accumulator-744|))
(BLOCK NIL
(TAGBODY (PROGN)
#:|begin-loop-742| (INCF #:|accumulator-744| I)
(UNLESS (< I 10) (GO #:|end-loop-743|))
(PRINC I)
(PROGN
(LET ((#:|temp-748| (+ I #:|by-747|)))
(SETQ I #:|temp-748|)))
(GO #:|begin-loop-742|)
#:|end-loop-743| (RETURN-FROM
NIL
#:|accumulator-744|))))))
Can your code generators already handle this macrolet/block/tagbody?
Does the Java output have to be pretty? Loop can be pretty complex
and I would vote for correctness over aesthetics in the Java code.
So I would vote for whatever Linj can currently do with the expanded
loop examples.
Wade
Sorry for the delay in answering this. It seems that my ISP is
loosing posts...
Wade Humeniuk <····································@telus.net> wrote in message news:<·················@clgrps13>...
> In general, I think you might macroexpand the loop and
> instead translate the resulting tagbody-like body.
>
> e.g.
>
> CL-USER 13 > (loop for i from 1
> sum i
> while (< i 10)
> do (princ i))
>
> expands to this in LW
>
> (MACROLET ((LOOP-FINISH () '(GO #:|end-loop-743|)))
> (LET ((I 1) (#:|to-746| NIL) (#:|by-747| 1))
> (LET ((#:|accumulator-744| 0))
> (DECLARE (TYPE NUMBER #:|accumulator-744|))
> (BLOCK NIL
> (TAGBODY (PROGN)
> #:|begin-loop-742| (INCF #:|accumulator-744| I)
> (UNLESS (< I 10) (GO #:|end-loop-743|))
> (PRINC I)
> (PROGN
> (LET ((#:|temp-748| (+ I #:|by-747|)))
> (SETQ I #:|temp-748|)))
> (GO #:|begin-loop-742|)
> #:|end-loop-743| (RETURN-FROM
> NIL
> #:|accumulator-744|))))))
>
> Can your code generators already handle this macrolet/block/tagbody?
Tagbody isn't implementable in Java. The language doesn't have gotos.
Blocks are OK (with restrictions) and macrolets have a slightly
different syntax (but as soon as I have time, I'll implement the
Common Lisp syntax).
> Does the Java output have to be pretty? Loop can be pretty complex
> and I would vote for correctness over aesthetics in the Java code.
Correctness is always the primary concern. On the other hand, Linj
tries hard to generate readable code and this precludes using the
"traditional" Common Lisp macro expansions as these tend to be ugly.
> So I would vote for whatever Linj can currently do with the expanded
> loop examples.
Even without using tagbody, it is possible to implement something as
ugly as the usual Common Lisp macroexpansions. But that's not
challenging. Linj currently can generate what I think is good Java
code in most cases and acceptable Java code in almost all remaining
cases. I hope that the really, really ugly cases are already ugly in
Linj :-)
Thanks for the suggestion,
Antonio Leitao.
In article <····························@posting.google.com>,
Antonio Leitao <··············@evaluator.pt> wrote:
>
>Tagbody isn't implementable in Java. The language doesn't have gotos.
>Blocks are OK (with restrictions) and macrolets have a slightly
>different syntax (but as soon as I have time, I'll implement the
>Common Lisp syntax).
>
Hi,
I beg to differ, the following is a standard way of simulating
gotos in Java. In this example the tagBody label: is actually not
needed, but it is handy in general when breaking out of nested structure
inside your goto-blocks (like nested inner loops and if-then-elses).
import java.util.*;
public class Goto {
public static void main(String[] args) {
Random r = new Random();
int gotoLabel = 0;
while (gotoLabel != 2) {
tagBody:
switch (gotoLabel) {
case 0: System.out.println("0, goto 1");
gotoLabel = 1;
break tagBody;
case 1: System.out.println("1, goto random");
gotoLabel = r.nextInt(3);
break tagBody;
}
}
}
}
cheers, Bernhard
--
---------------------------------------------------------------------
Bernhard Pfahringer, Dept. of Computer Science, University of Waikato
http://www.cs.waikato.ac.nz/~bernhard +64 7 838 4041
On Mon, 24 May 2004 07:10:28 +0000, Bernhard Pfahringer wrote:
> In article <····························@posting.google.com>,
> Antonio Leitao <··············@evaluator.pt> wrote:
>>
>>Tagbody isn't implementable in Java. The language doesn't have gotos.
>>Blocks are OK (with restrictions) and macrolets have a slightly
>>different syntax (but as soon as I have time, I'll implement the
>>Common Lisp syntax).
>>
> Hi,
>
> I beg to differ, the following is a standard way of simulating
> gotos in Java. In this example the tagBody label: is actually not
> needed, but it is handy in general when breaking out of nested structure
> inside your goto-blocks (like nested inner loops and if-then-elses).
>
> import java.util.*;
>
> public class Goto {
>
> public static void main(String[] args) {
>
> Random r = new Random();
>
> int gotoLabel = 0;
>
> while (gotoLabel != 2) {
>
> tagBody:
>
> switch (gotoLabel) {
>
> case 0: System.out.println("0, goto 1");
> gotoLabel = 1;
> break tagBody;
>
> case 1: System.out.println("1, goto random");
> gotoLabel = r.nextInt(3);
> break tagBody;
> }
> }
> }
> }
>
> cheers, Bernhard
Yes, that's one approach. Another one would be to use a loop/try-catch and
exceptions. It doesn't give gotos to the language but it might be a
last-resort solution to the translation problem.
Thanks for the idea,
Antonio Leitao.
Antonio Menezes Leitao wrote:
> Hi,
>
> In the process of extending Linj (the Lisp to Java compiler) to support
> the extended loop macro, I found some funny examples in Paul Dietz ANSI
> tests and in CLTL (and I invented some others) that I would like to use
> as
> challenges for the Common Lisp community. The idea is simply to find
> nice-looking Java translations for some examples of the extended loop
> macro.
I've got Java exams coming up, so I'll give it a shot. Exposure to the
language can't hurt.
Please note that I won't be checking these; they *should* work, according
to my internal model, but Java is anything but consistent.
> Let me start by giving an example. Consider the following Common Lisp
> function:
>
> (defun test1 ()
> (loop for x from 1 to 10 sum x))
>
> This corresponds (more or less) to the following "function" in Java:
>
> public static long test1() {
> long sum = 0;
> for (int x = 1; x <= 10; ++x) {
> sum += x;
> }
> return sum;
> }
>
> [Is there a shorter version in Java (that is still readable)?]
for (int x=1; x <= 10; sum+=++x);
Well, it would work, but it would be harder to make linj generate that
code. No reason to, really.
> Anyway, this one was easy. Now, I would like to challenge all Common
> Lispers that also know Java (and that enjoy riddles) to tell me what
> they think is the best Java encoding for the following loop examples:
>
> (defun test3 ()
> (loop for i from 1
> sum i
> while (< i 10)
> do (princ i)))
public static long test3() {
long sum=0;
for (long i=1;;++i) {
sum+=i;
if (i >= 10) break;
System.out.print(i);
}
return sum;
}
> (defun test4 ()
> (loop for x from 1 to 9
> for y = 0 then x
> sum (+ x y)))
public static long test4() {
for (int y=0, x=1; x<=9; ++x) {
sum+=(y+x);
y=x;
}
return sum;
}
> (defun test5 ()
> (let ((x 10))
> (loop for x from 1 to 9
> and y = x then x
> sum (+ x y))))
I'm not sure you got this right. I get 'x unused' warnings from SBCL.
public static long test5() {
int x=10;
{
int x=1;
long sum=0;
int y=x;
for (;x<=9; ++x) {
sum+=(x+y);
y=x;
}
return sum;
}
}
> (defun test6 ()
> (loop for item = 1 then (+ item 10)
> repeat 5
> sum item))
public static long test6() {
int item=1;
long sum=0;
for (int idx=0; idx<5; ++idx) {
sum+=item;
item+=10;
}
return sum;
}
> (defun test7 ()
> (loop for i from 3
> when (oddp i) sum i
> while (< i 5)))
public static long test7() {
long sum=0;
for (int i=3;;) {
if (i%2 != 0) sum+=i;
if (i >= 5) break;
}
return sum;
}
> If there's enought interest, I'll post some really difficult examples.
Not from me, anyway. This exercise has mostly educated me in the
shortcomings of a language without macros, and thereby the loop macro.
Antonio Menezes Leitao <··············@evaluator.pt> writes:
> (defun test1 ()
> (loop for x from 1 to 10 sum x))
>
> This corresponds (more or less) to the following "function" in Java:
>
> public static long test1() {
> long sum = 0;
> for (int x = 1; x <= 10; ++x) {
> sum += x;
> }
> return sum;
> }
A couple of Sun Java style comments.
1) Int is the preferred type.
2) Use postfix for increment unless required.
3) The loops from Burdick looks fine, some missing spaces between
the binary operators though ;)
Not too common to write small utility functions in Java,
but what about isOdd(x) and isEven(x)?
--
Torkel Holm
Torkel Holm <······@ii.uib.no> writes:
> 2) Use postfix for increment unless required.
The exact opposite is true for C++, for easily demonstrable
reasons. What could the rationale possibly be for creating and
returning temporary values that are not required? Not all of these
temporary values can be eliminated by an optimizing compiler. Case in
point: operator++(int) for typical struct/class-based iterator types.
iterator& operator++()
{
increment();
return *this;
}
iterator operator++(int)
{
iterator const current( *this );
++*this;
return current;
}
The second is clearly wasteful (one or two extra copies of the
iterator) when the caller is not interested in the return value.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
"Steven E. Harris" <········@raytheon.com> writes:
> Torkel Holm <······@ii.uib.no> writes:
>
>> 2) Use postfix for increment unless required.
>
> The exact opposite is true for C++, for easily demonstrable
> reasons. What could the rationale possibly be for creating and
> returning temporary values that are not required?
Sorry, bad formulation.
My point was about statements when you are not using the returning
value from the expression.
for (int i = 0; condition; i++); // vs
for (int i = 0; condition; ++i);
Both statements compiles to the same code.
It was just a comment on the common practice by Sun.
My C++ is shaky, I mostly no it by reputation.
Of course there is no point in using postfix when returning values
{... return x++;}
--
Torkel Holm
Torkel Holm <······@ii.uib.no> writes:
> My point was about statements when you are not using the returning
> value from the expression.
>
> for (int i = 0; condition; i++); // vs
> for (int i = 0; condition; ++i);
>
> Both statements compiles to the same code.
No, they /might/ compile to the same code. The first is guaranteed to
be either the same as or worse than the second. Why take your chances?
> Of course there is no point in using postfix when returning values
> {... return x++;}
Wrong again. That's shorthand for:
{
T const temp = x;
++x;
return temp;
}
That's not the same as:
return ++x;
They both increment the variable x. In the first case, though, the old
value (before incrementing) is returned. In the second case, the new
value (after incrementing) is returned. Since they produce different
results with admittedly the same side-effect, there must be a point to
using postfix when returning values: It's potentially-optimizable
short-hand for the first block above.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
"Steven E. Harris" <········@raytheon.com> writes:
> Torkel Holm <······@ii.uib.no> writes:
>
>> for (int i = 0; condition; i++); // vs
>> for (int i = 0; condition; ++i);
>
> No, they /might/ compile to the same code. The first is guaranteed to
> be either the same as or worse than the second. Why take your chances?
Have you seen a compiler in the last ten years which didn't generate
the same code for each?
--
Alan Shutko <···@acm.org> - I am the rocks.
Alan Shutko wrote:
> "Steven E. Harris" <········@raytheon.com> writes:
>
>> Torkel Holm <······@ii.uib.no> writes:
>>
>>> for (int i = 0; condition; i++); // vs
>>> for (int i = 0; condition; ++i);
>>
>> No, they /might/ compile to the same code. The first is guaranteed to
>> be either the same as or worse than the second. Why take your chances?
>
> Have you seen a compiler in the last ten years which didn't generate
> the same code for each?
>
Pretty much any C++ compiler when the ++ operator is overloaded, even if
the semantics stay valid.
Steven E. Harris wrote:
> Torkel Holm <······@ii.uib.no> writes:
>
>>My point was about statements when you are not using the returning
>>value from the expression.
>>
>> for (int i = 0; condition; i++); // vs
>> for (int i = 0; condition; ++i);
>>
>>Both statements compiles to the same code.
>
> No, they /might/ compile to the same code. The first is guaranteed to
> be either the same as or worse than the second. Why take your chances?
I am not 100% sure, but if I recall correctly it doesn't make a
difference in Java.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
"Steven E. Harris" <········@raytheon.com> writes:
> Torkel Holm <······@ii.uib.no> writes:
>
>> My point was about statements when you are not using the returning
>> value from the expression.
>>
>> for (int i = 0; condition; i++); // vs
>> for (int i = 0; condition; ++i);
>>
>> Both statements compiles to the same code.
>
> No, they /might/ compile to the same code. The first is guaranteed to
> be either the same as or worse than the second. Why take your chances?
Java compiles to byte code right!?
I am not a bytecode macho myself, but it can certainly help
you out when you are tuning the code (like disassemble in CL).
Can you back up your argument from the virtual machine specification?
--
Torkel Holm
Torkel Holm <······@ii.uib.no> writes:
> Can you back up your argument from the virtual machine
> specification?
I wasn't talking about Java. I was talking about whether this
guideline could apply to C++ -- to which no machine is relevant -- and
pointing out that it's backwards. So backwards, in fact, that I
wondered whether the OP had read the guideline incorrectly.
In C++, it's common to find loops within template functions:
template <typename InIter>
typename std::iterator_traits<InIter>::value_type
sum(InIter first, InIter const last)
{
typename std::iterator_traits<InIter>::value_type result = 0;
for ( ; first != last; ++first )
result += *first;
return result;
}
Now, this is where the pre- v. post-increment makes a big
difference. Yes, the OP was using ints in his examples, but the
function above may be dealing with pointers, or it could be dealing
with fat iterators with user-defined increment operators. The author
of the function can't know. If he uses post-increment (first++), he's
quite likely risking a lot of unnecessary copying of the iterator
type. The compiler is not guaranteed to automatically translate
operator++(int) to operator++() just because the return value is not
being used here. That optimization is easy for built-in types, but it
violates the "as-if" rule for user-defined types.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
Torkel Holm wrote:
> A couple of Sun Java style comments.
> 2) Use postfix for increment unless required.
Why? Postfix is less efficient than prefix. You should only use
postfix if you're actually going to use the previous value afterwards.
This is because the previous value has to be stored for later use, which
gobbles up a register at the very least, or more if you are using a more
complex data type. Sure, the compiler can optimize this out in almost
all cases, but I don't like making the compiler work that hard just
because I can't be bothered to pre-increment. :)
Hi Antinio
Antonio Menezes Leitao wrote:
> Hi,
>
> In the process of extending Linj (the Lisp to Java compiler) to support
> the extended loop macro, I found some funny examples in Paul Dietz ANSI
> tests and in CLTL (and I invented some others) that I would like to use as
> challenges for the Common Lisp community. The idea is simply to find
> nice-looking Java translations for some examples of the extended loop
> macro.
>
> Let me start by giving an example. Consider the following Common Lisp
> function:
>
> (defun test1 ()
> (loop for x from 1 to 10 sum x))
>
> This corresponds (more or less) to the following "function" in Java:
>
> public static long test1() {
> long sum = 0;
> for (int x = 1; x <= 10; ++x) {
> sum += x;
> }
> return sum;
> }
>
> [Is there a shorter version in Java (that is still readable)?]
>
> Anyway, this one was easy. Now, I would like to challenge all Common
> Lispers that also know Java (and that enjoy riddles) to tell me what they
> think is the best Java encoding for the following loop examples:
In the interest of generating java code that both looks as if it was
written by a human and has close ties to the linj/lisp code that is
really written by mortal hand I think slightly verbose forms like the
one above is the way to go.
I have no idea how Linj works internally, but if you want a java
template for each type of loop usage, the following solutions might
work. They are tested on jikes 1.16 + SUN java 1.4.2_03 to give similar
return values and write the same to stdout as your example code does
under CMUCL 18e:
> (defun test3 ()
> (loop for i from 1
> sum i
> while (< i 10)
> do (princ i)))
public static long test3() {
long sum = 0;
for (int i=1;;i++) {
sum += i;
if (! (i < 10)) {
break;
}
System.out.print(i);
}
System.out.println();
return sum;
}
> (defun test4 ()
> (loop for x from 1 to 9
> for y = 0 then x
> sum (+ x y)))
public static long test4 () {
long sum = 0;
int x=1, y=1;
sum += x + y;
for (x=2, y=2; x <= 9; x++, y++) {
sum += x + y;
}
return sum;
}
>
> (defun test5 ()
> (let ((x 10))
> (loop for x from 1 to 9
> and y = x then x
> sum (+ x y))))
public static long test5() {
// the x in the let is unused according to cmucl 18e so it is ignored here
long sum = 0;
int y = 1;
for (int x=1; x <= 9; x++) {
sum += x + y;
y = x;
}
return sum;
}
> (defun test6 ()
> (loop for item = 1 then (+ item 10)
> repeat 5
> sum item))
public static long test6() {
long sum = 0;
for (int i=1, __linj_repeat=0; __linj_repeat < 5; i += 10,
__linj_repeat++) {
sum += i;
}
return sum;
}
> (defun test7 ()
> (loop for i from 3
> when (oddp i) sum i
> while (< i 5)))
public static long test7() {
long sum = 0;
for (int i=3; ; i++) {
if (i % 2 == 1) {
sum += i;
}
if (! (i < 5)) {
break;
}
}
return sum;
}
>
> If there's enought interest, I'll post some really difficult examples.
please share them !
Kristian
Antonio Menezes Leitao <··············@evaluator.pt> writes:
> Let me start by giving an example. Consider the following Common Lisp
> function:
>
> (defun test1 ()
> (loop for x from 1 to 10 sum x))
>
> This corresponds (more or less) to the following "function" in Java:
>
> public static long test1() {
> long sum = 0;
> for (int x = 1; x <= 10; ++x) {
> sum += x;
> }
> return sum;
> }
>
> [Is there a shorter version in Java (that is still readable)?]
I'll just do this one because the method is applicable to the others.
I'm surprised no one has done this already:
public static long test1() { return 55; }
I think that's about as short as it gets without optimizing away the
function call ;-)
--
I wouldn't mind the rat race so much if it wasn't for all the damn cats.
Hi,
It has been some time since the last answer to my challenge. I want
to thank everybody that participated in the challenge. I guess it's
time to post the solutions produced by the Linj compiler.
The idea was to find nice-looking Java translations for some examples of
the extended loop macro. Here are the answers from the Linj compiler:
----------------------------------------------------------------------
(defun test3 ()
(loop for i from 1
sum i
while (< i 10)
do (princ i)))
public static long test3() {
long sum = 0;
for (int i = 1; true; ++i) {
sum += i;
if (i >= 10) {
break;
}
System.out.print(i);
}
return sum;
}
----------------------------------------------------------------------
(defun test4 ()
(loop for x from 1 to 9
for y = 0 then x
sum (+ x y)))
public static long test4() {
long sum = 0;
int x = 1;
for (int y = 0; x <= 9; y = x) {
sum += x + y;
++x;
}
return sum;
}
----------------------------------------------------------------------
(defun test5 ()
(let ((x 10))
(loop for x from 1 to 9
and y = x then x
sum (+ x y))))
public static long test5() {
int x = 10;
long sum = 0;
int y = x;
int x0 = 1;
for (; x0 <= 9; y = x0, ++x0) {
sum += x0 + y;
}
return sum;
}
The solution for this example doesn't agree with the Hyperspec but it
agrees with my intuition. I'll explain my solution in another post.
----------------------------------------------------------------------
(defun test6 ()
(loop for item = 1 then (+ item 10)
repeat 5
sum item))
public static long test6() {
long sum = 0;
int item = 1;
for (int repeat = 5; (--repeat) >= 0; item = item + 10) {
sum += item;
}
return sum;
}
----------------------------------------------------------------------
(defun test7 ()
(loop for i from 3
when (oddp i) sum i
while (< i 5)))
public static long test7() {
long sum = 0;
for (int i = 3; true; ++i) {
if ((i % 2) != 0) {
sum += i;
}
if (i >= 5) {
break;
}
}
return sum;
}
----------------------------------------------------------------------
(defun test11 ()
(loop for i from 1 to 10
thereis (> i 11)
finally (print i)))
public static boolean test11() {
int i = 1;
for (; i <= 10; ++i) {
if (i > 11) {
return true;
}
}
System.out.print("" + '\n' + i + " ");
return false;
}
----------------------------------------------------------------------
(defun test12 ()
(loop for m upfrom 2
thereis (loop for n from 2 to 10
thereis (oddp (* n m)))))
public static boolean test12() {
for (int m = 2; true; ++m) {
if (new Object() {
public boolean funcall(final int m) {
for (int n = 2; n <= 10; ++n) {
if (((n * m) % 2) != 0) {
return true;
}
}
return false;
}}.
funcall(m)) {
return true;
}
}
}
----------------------------------------------------------------------
(defun test-fermat ()
(loop for z upfrom 2
thereis
(loop for n upfrom 3 below (log z 2)
thereis
(loop for x below z
thereis
(loop for y below z
thereis (= (+ (expt x n)
(expt y n))
(expt z n)))))))
public static boolean testFermat() {
for (int z = 2; true; ++z) {
if (new Object() {
public boolean funcall(final int z) {
int n = 3;
double limitN = Math.log(z) / Math.log(2);
for (; n < limitN; ++n) {
if (new Object() {
public boolean funcall(final int z, final int n) {
int x = 0;
int limitX = z;
for (; x < limitX; ++x) {
if (new Object() {
public boolean funcall(final int z, final int x, final int n) {
int y = 0;
int limitY = z;
for (; y < limitY; ++y) {
if ((Math.pow(x, n) + Math.pow(y, n)) == Math.pow(z, n)) {
return true;
}
}
return false;
}}.
funcall(z, x, n)) {
return true;
}
}
return false;
}}.
funcall(z, n)) {
return true;
}
}
return false;
}}.
funcall(z)) {
return true;
}
}
}
Nice, isn't it? :-) Comments are welcome.
Best regards,
Antonio Leitao.