Generics - Is this possible?

[Andreas Leitgeb]

Here's a solution that I just worked out for my own use:
public class IteratorToIterable<T> implements Iterable<T> {
[...]
}

final Iterator<String> itStr= Arrays.asList("1","2","3").iterator();
for (String s:
new Iterable<String>() {
public Iterator<String> iterator() { return itStr; }
}
)
{
System.out.println(s);
}

Perhaps less elegant, but shorter

 

[Arne Vajhøj]

How about it? Are you suggesting that Java doesn't have the equivalent?

goto is a reserved word in Java, but is not and never will be
implemented.

Arne

 

[Andreas Leitgeb]

Here's a solution that I just worked out for my own use:
public class IteratorToIterable<T> implements Iterable<T> { [...] }
Andreas Leitgeb wrote:
[anonymous Iterable-subclass whose .iterator() returns the iterator]

[ misses the point, that we were starting from iterator, not iterable ]

I'm sure the itStr declaration was just a way of getting into that
situation, and Andreas would not use such an indirect approach to
iterate over an array.

100% correct.

Perhaps I did miss it, or perhaps I made a larger point about how the lack of
an Iterable may be much less of a problem in practice.

I offer a different example:

for (String s: new Iterable<String>() {
public Iterator<String> iterator() { return new Scanner(System.in); }
}) {
System.out.println(s);
}

Scanner is an Iterator<String>, but not an Iterable.

 

[Andreas Leitgeb]

I've yet to meet a language that absolutely prohibits what it "considers"
dangerous coding practices (inasmuch as a programming language considers
anything ).

I do think, that in Java the dangerous coding pracise of
pointer-arithmetics is really really prohibited

 

[Andreas Leitgeb]

How about it? Are you suggesting that Java doesn't have the equivalent?

The real pendant for goto would be a switch wrapped in an endless loop.

Do you have an example of code that uses "goto" that you could not
accomplish in any other way?

If you see forward jumps as structured "if", and backwards-jumps
as structured loops, then there can easily exist some mixture that
doesn't really map to a proper nesting of structured elements.
like jump into the middle of a loop, or jumping from one loop
to another or even from one subroutine to another.

I don't know if there are any theories about what spaghetti-code
can be structurized, and what (if any) not, or if there even exist
algorithms for this transformation.

 

[Daniel Pitts]

Hi,

I'm looking at the signature for something like a 'map' function.

For List it may be something like:

List<B> map(List<A> a, UnaryFunction<A, B> f)

But, I want I'd rather it not be List specific, so I was after
something like:

T<B> map(T<A> a UnaryFunction<A, B> f)

But, the compiler doesn't like this

Any ideas on how or whether this is possible?

Thanks,
Levi

How about this:

public static <A, B, T extends Collection<B>> T map(Iterable<A> source,
T dest, UnaryFunction<A, B> f) {
for (A a: source) {
dest.add(f.call(a));
}
return dest;
}

Example usage:

Set<Foo> foos = map(inputCollection, new HashSet<Foo>(), myFunction);

 

[Andreas Leitgeb]

In other words, for those who missed my point, the premise that we have to
start from an Iterator, not an Iterable, is itself of little significance
because in such situations it will be more feasible to recast the problem
to a more easily solved one.

Can you explain me, how to do the recast, when starting from a Scanner?

Since those situations, where we do start with an Iterable are trivial,
it's not very interesting to deal with those in this thread.
Your point seems to be, that the situation "start with an iterator"
doesn't ever happen in practise, and the Iterable's iterator() call
is always just preceding the currently focussed snippet of code.

But there's also Scanner and there may be other Iterator-subclasses,
for iterating ressources that can be iterated only once. So starting
with an Iterator (and not an Iterable) is not just an artifical problem.

You obviously avoided to comment on the Scanner-example that I added
to my previous posting.

 

[Andreas Leitgeb]

Well, inasmuch as in theory, two languages that are both "Turing-complete"
should be able to implement identical algorithms, whether there's a
well-defined mapping process or not it should be obvious that you can
always come up with an equivalent.

Using turing-completeness for argumentation does not answer this problem.

Even if we assumed some "unlimited Java", the one existing implementation
(or even the nicest of all them) might just be an interpreter for the
verbatim original implementation.

Turing completeness of any structured target language is no proof that
a structured pendant exists for each spaghetti code.

 

[lstephen]

How about this:

public static <A, B, T extends Collection<B>> T map(Iterable<A> source,
T dest, UnaryFunction<A, B> f) {
for (A a: source) {
dest.add(f.call(a));
}
return dest;

}

Example usage:

Set<Foo> foos = map(inputCollection, new HashSet<Foo>(), myFunction);

I agree that this covers the common case. But, I was looking for a way
to improve this in two ways.

1. the 'map' concept can be applied to other, non-collection, types
(e.g., Haskell's Maybe type)
2. I wanted to express the restriction that the type passed in was
what came back (e.g., If a Set was passed in, a Set would be returned)

Note that there would be more than one implementation of map around,
so the general type would only appear in the interface.

Thanks,
Levi

 

[Andreas Leitgeb]

Why not?

Because we argue with two different meanings of "structured".
(Sorry I didn't notice that before - would have saved us some
iterations already)

Yours seems to be such that since Java has no goto, every legal
Java program is automatically "structured".

My definition of "structured" is a bit stricter, and would
exclude certain practices, like the one shown in this snippet:

int step=10;
while (step>0) {
switch (step) {
case 10: if (blah()) { step=30; continue; }
case 20: if (foo()) { step=0; break; }
case 30: if (snarf()) { step=10; continue; }
case 40: step=30; continue;
}
}
While it's legal Java code(-excerpt), it's not "structured"
according to my own humpty dumpty definition ;-)

I've looked at "http://en.wikipedia.org/wiki/Structured_programming"
but wasn't able to make out any sharp definition. The sample I
provided probably fits well to the "State machines" paragraph.
Quote: " It is possible to structure these systems by making each
state-change a separate subprogram..."
This could be interpreted, that such state-machine code is not yet
structured.

If there is some other "official" definition of "structured" that
supports your point, then, well, then you've won 10 points for
a correct statement, even though one of no use, due to my
(as it now appears) inexact question.

I'm interested, what others consider "structured" to mean.

 

[Andreas Leitgeb]

For a long time, when I used C professionally, I used to look for excuses to
use 'goto' in my code, just for grins and giggles.

Since C/C++ do not have labelled loops like Java, an excuse for a use
for goto is not all that hard to find there. My C++ code contains some
gotos, and were I to convert it to Java, I could change most of them
to: "break thatOuterLoop;"

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Patricia Shanahan schreef:
| Logan Shaw wrote:
| ...
|> Is there a reason why an enhanced for loop couldn't be built to use
|> either
|> an Iterator or an Iterable?
|>
|> There are cases when we have a priori that an Iterator object exists.
|> For example, some API returns an Iterator. (There are other legit uses.)
|> In those cases, it would nice to be able to use the object at hand.
| ...
|
| Here's a solution that I just worked out for my own use:
|
| import java.util.Iterator;
|
| /**
| * Iterable whose iterator() method returns a
| * specified Iterator.
| * @param <T> The base type of the Iterator and Iterable.
| */
| public class IteratorToIterable<T> implements Iterable<T> {
| private Iterator<T> base;
| /**
| * Create an Iterable whose iterator method returns base.
| * @param base
| */
| public IteratorToIterable(Iterator<T> base){
| this.base = base;
| }
| /**
| * Get the Iterator passed to the constructor. The Iterator
| * should be used only once.
| */
| public Iterator<T> iterator() {
| return base;
| }
| }

I would add

public static <T> Iterable<T> toIterable(Iterator<T> base) {
~ return new IteratorToIterable<T>(base);
}

(this is a pattern much seen in Jakarta Commons)
and then

| public static void main(String[] args) {
| Iterator<Integer> it = getIterator();
| for(Integer i: toIterable(it) ){
| System.out.println(i);
| }
| }

with a proper static import.

One could even just put that method somewhere in the class where one
wants to use it.

H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4-svn0 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iD4DBQFIDGwEe+7xMGD3itQRAkgEAJ9httlWOlSauKtrNvoXi5edXjtB8ACXUNF5
GnELu8MWNBn1IYW71SD7hg==
=jpMA
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Patricia Shanahan schreef:
| Logan Shaw wrote:
| ...
|> Is there a reason why an enhanced for loop couldn't be built to use
|> either
|> an Iterator or an Iterable?
|>
|> There are cases when we have a priori that an Iterator object exists.
|> For example, some API returns an Iterator. (There are other legit uses.)
|> In those cases, it would nice to be able to use the object at hand.
| ...
|
| Here's a solution that I just worked out for my own use:
|
| import java.util.Iterator;
|
| /**
| * Iterable whose iterator() method returns a
| * specified Iterator.
| * @param <T> The base type of the Iterator and Iterable.
| */
| public class IteratorToIterable<T> implements Iterable<T> {
| private Iterator<T> base;
| /**
| * Create an Iterable whose iterator method returns base.
| * @param base
| */
| public IteratorToIterable(Iterator<T> base){
| this.base = base;
| }
| /**
| * Get the Iterator passed to the constructor. The Iterator
| * should be used only once.
| */
| public Iterator<T> iterator() {
| return base;
| }
| }
|
| The intended use of this class is:
|
| public static void main(String[] args) {
| Iterator<Integer> it = getIterator();
| for(Integer i: new IteratorToIterable<Integer>(it) ){
| System.out.println(i);
| }
| }

I had some classes (Combinators, see
http://mindprod.com/jgloss/combination.html) which were iterators and
wanted to use them like this as well. I ended up having them implement
both Iterator<T> and Iterable<T>, with the iterator() function just
{return this;}. Not very elegant, but works as expected. I do remember
somebody had some valid remarks against that practice though,
particularly multiple iterations are a problem.

H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4-svn0 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iD8DBQFIDG4me+7xMGD3itQRArFnAJ0WM6Uwa84QrOE5l8nJdY/AWHg2sQCeO27g
/eHR6veCu8CBwndouc6xUww=
=1I0b
-----END PGP SIGNATURE-----

 

[Andreas Leitgeb]

Why does it matter what the exact definition of "structured" is? Using
your definition doesn't change the point I made.

My original question was, if any spaghetti code could be converted to
structured code, to which you argued somehow like, that since Java was
turing complete, a "structured"/goto-free program exists for every
machine-implementable algorithm, thus also for one already implemented
in spaghetti code. So far so good. But this conclusion doesn't
*necessarily* remain valid, if I "arbitrarily" restrict my set of
"acceptable" Java programs.
I don't remember exactly, how to prove turing-completeness. I vaguely
remember, that one needs to be able to code some abstract building blocks.
Maybe these building blocks can be also coded in (my type of) structured
code, and any combination/chaining of these building blocks also needs to
be "inside" that restricted set of acceptable programs. Perhaps it is,
then you'd be right afterall. It just isn't yet obvious to me.

 

[Daniel Pitts]

I agree that this covers the common case. But, I was looking for a way
to improve this in two ways.

1. the 'map' concept can be applied to other, non-collection, types
(e.g., Haskell's Maybe type)
2. I wanted to express the restriction that the type passed in was
what came back (e.g., If a Set was passed in, a Set would be returned)

Note that there would be more than one implementation of map around,
so the general type would only appear in the interface.

Thanks,
Levi

Why restrict that the type-in is the type-out? The method I suggested
allows the caller to specify the type-out. Maybe you want to convert a
List to a Set while applying this mapping, or visa versa.

 

[Patricia Shanahan]

Andreas Leitgeb wrote:
....

I don't remember exactly, how to prove turing-completeness. I vaguely
remember, that one needs to be able to code some abstract building blocks.
Maybe these building blocks can be also coded in (my type of) structured
code, and any combination/chaining of these building blocks also needs to
be "inside" that restricted set of acceptable programs. Perhaps it is,
then you'd be right afterall. It just isn't yet obvious to me.

The main building blocks for emulating a TM are:

1. Conditional code execution. To remove this capability from Java, you
would have to do without "if", and anything else that can be used to
execute code conditionally based on a data value, such as "for",
"while", and "switch".

2. An array, or similar structure, with read and write access to a
"current" element, and ability to select the predecessor or successor of
the "current" element to be a the next "current" element. To remove that
capability from Java you would have to do without arrays, anything
implementing java.util.List, and java.io.RandomAccessFile.

3. Some means to execute code repeatedly, such as "for" or "while".

There are several independently developed concepts of algorithmic
computation that were shown, very early in the history of computer
science, to be equivalent. See
http://en.wikipedia.org/wiki/Church-Turing_thesis

Beyond that, given the equivalence of those models, and their
equivalence with the model represented by each general purpose
programming language ever developed, it appears that there is something
real and important about Turing-completeness. A language is unlikely to
be useful as a general purpose programming language without being
Turing-complete.

Of course, all this ignores the fact that any real computer is a finite
state automaton because there is a finite amount of material in the
accessible universe that could be used to build memory for it. It is
usually more useful to treat memory as unbounded.

Patricia

 

[Andreas Leitgeb]

My only point is that the lack of a "goto" statement isn't really a
problem.
[...]
No offense, but given your arbitrary limitation on what Java
implementations you'd consider acceptable,...

Now we're at the point I was two steps before:
Yes, it *does* depend on the definition of "structured"
(and I didn't claim that mine was any more correct than
anyone else's. I just described it informally).

If you arbitrarily say that the equivalent without a "goto"
must not be ugly,

I didn't really *say* it. I effectively *asked* if all implementable
algorithms are also implementable without resorting to state-machine
emulation. Maybe the answer is no. Turing-completenesss does not
answer my question, because I can't say, if this limitation of mine
to allow only "nice" code is still turing complete. (this is of course
an equivalent question to my original one).

If it was, then all dirty-hack-code could be rewritten for "nice",
if it isn't, then hackers have an everlasting excuse to *sometimes*
write ugly code

I find the question still interesting, but I understand, if no one
else does. So, unless there's a new insight to this, I suggest
we make an end-of-subthread now.

 

[Andreas Leitgeb]

Sorry...I didn't realize that was what you were asking. It's not how I
read the question you posed.

I now reread my sub-thread-starter posting, and admit, that
what I claimed there originally, was indeed correctly addressed
with your Turing argument. Only later did I exclude the
"while-switch" anti-sample.

I don't think you can conclude that there's a justification for
spaghetti code.

Spaghetti code wrapped/emulated in Java is still spaghetti code.

Unless we can prove, that "nice" Java is also Turing complete, it *is*
a justification, because using spaghetti code *may* be inevitable.

(In most of the practical cases, judged from experience, a "nice"
alternative does exist - for apt definitions of "practical" at
least

 

[Andreas Leitgeb]

But very structured spaghetti code.

haha, good joke

 

[Andreas Leitgeb]

But very structured spaghetti code.

I'd like to apologize for the other one of my followups on your
posting. - You may not have followed my whole discussion with
Pete.

If that's the case, and you're interested, then look at the code-sample in:
Message-ID: <[email protected]>
or:
http://groups.google.com/group/comp.lang.java.programmer/msg/f1845edf8ece4b0f

If you consider that to be "very structured spaghetti code",
then accept my laughter. If you think Java-code of that type
can generally be un-spaghettified, you're welcome to join in
and share your recipes.