List comprehensions
On 01/05/2016 02:42 AM, doug moen wrote:
The reason for the * operator in OpenSCAD2 is that I unified the "statement"
and "expression" syntax to the maximum extent possible. The prefix * operator
already exists in OpenSCAD at the statement level, and I made it available
in expression syntax for consistency.
Right, that makes sense. If it does not help regarding an easier move to
OpenSCAD2, I guess we can skip this for now. Otherwise it should be easy
to add (I hope bison agrees here ;-).
[ f(1), for (a = [2:4]) f(a), for (b = [4:-1:2]) f(b), f(1), ]
{ g(1); for (a = [2:4]) g(a); for (b = [4:-1:2]) g(b); g(1); }
Notice how the 2 lines above are structurally the same, and in OpenSCAD2
the 'for' operator has the same semantics in both cases. The first is a
list expression, the second is a "statement" (in OpenSCAD) or an "object
expression" (in OpenSCAD2). Note that the trailing , in the list expression
is optional in OpenSCAD, and I hope to make the trailing ; optional in the
object expression in OpenSCAD2.
Yep, and the first expression now works with the patch I'm working on:
function f(x) = x * x;
echo([ f(1), for (a = [2:4]) f(a), for (b = [4:-1:2]) f(b), f(1), ]);
// ECHO: [1, 4, 9, 16, 16, 9, 4, 1]
Yes, the 'each' operator is verbose. I tried using an operator character, &,
in a previous draft, but it didn't get a very positive response from Marius,
because it doesn't look like anything familiar.
I just stated that in comparison to the syntax nophead asked about and for
that specific case.
In general, I think using "each" looks much better, especially when using
with functions. First I did not see what it's supposed to do, but after
implementing it, it became clear it's basically the unwrap operator :-).
echo([ each f(x) ]);
ciao,
Torsten.
tp3 wrote
Still, it might be possible. Do you have a specific use-case where that
would help. It's more compact than the matching recursive function,
but also looks a bit scary :).
Not on top of my head now. But I recall that in early python, some guy found
a secret
internal buffer, allowing python to do that :
[ i==1 and 1 or _1[i] // this line is the same as i==1?1:_1[i] in
openscad's code
for i in range(1,5)
]
The secret internal buffer is _1, which won't work in later python versions.
I made use of that _1 quite a lot and enjoying it very much.
In deed it can be achieved using recursion. But recursion in general is much
harder to read, as can be seen from this example.
$ Runsun Pan, PhD
$ libs:
doctest ,
faces ( git ),
offline doc ( git ),
runscad.py( 1 , 2 , git ),
synwrite( 1 , 2 );
$ tips:
hash( 1 , 2 ),
sweep ,
var( 1 , 2 ),
lerp ,
animGif ,
precision( 1 , 2 ),
xl-control
--
View this message in context: http://forum.openscad.org/List-comprehensions-tp15321p15496.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I think that this "secret internal buffer" syntax is obscure and hard to
figure out. It's not obvious it has a lot of use cases.
But I agree, recursive functions are a pain to write, and there is high
level syntax that is easier to write and which can replace the use of
recursive functions in some common cases. The list comprehension syntax is
a popular example of this.
I'm going to introduce another 'generator' operator for use in list
comprehensions. This operator is easy to understand, very powerful, and can
be used in place of recursive functions in many cases.
It is basically a direct rip-off of the C 'for' statement. If you know C,
the meaning should be obvious. I'll give examples.
[for (i=1; i <= 4; i=i+1) i]
=> [1,2,3,4]
[for (i=2; i <= 10; i=i+2) i]
=> [2,4,6,8,10]
[for (i=1,n=1; i <= 4; i=i+1, n=(n+i)*i) n]
=> [1, 6, 27, 124]
// Look, it's Runsun's magic sequence!
sort(x) = [for (L=x; L!=[]; m=min(L), L=[for (i=L) if (i > m) i]) m];
// non-recursive sort algorithm
If anybody reading this is a Haskell/functional programmer, then you might
recognize that this 'for' operator is actually a generalized anamorphism,
like 'unfold' but with more convenient syntax.
On 4 January 2016 at 20:35, runsun runsun@gmail.com wrote:
Any thought of accessing the item(s) generated (still in the buffer), in
the
middle of looping, before the loop is completed ?
Something like:
[ for(i=[1:4])
if(i==1) 1
else ((@-1)+i)*i
]
=> [ 1
, (1+2)*2 // = 6
, (6+3)*3 // = 27
, (27+4)*4 // = 124
]
=> [ 1,6,27,124 ]
$ Runsun Pan, PhD
$ libs:
doctest ,
faces ( git ),
offline doc ( git ),
runscad.py( 1 , 2 , git ),
synwrite( 1 , 2 );
$ tips:
hash( 1 , 2 ),
sweep ,
var( 1 , 2 ),
lerp ,
animGif ,
precision( 1 , 2 ),
xl-control
--
View this message in context:
http://forum.openscad.org/List-comprehensions-tp15321p15491.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 01/05/2016 05:20 AM, doug moen wrote:
I'm going to introduce another 'generator' operator for use in list
comprehensions. This operator is easy to understand, very powerful,
and can be used in place of recursive functions in many cases.
It is basically a direct rip-off of the C 'for' statement. If you
know C, the meaning should be obvious. I'll give examples.
[for (i=1; i <= 4; i=i+1) i]
=> [1,2,3,4]
Ah, nice, that's much more obvious than a magic variable. So
this would introduce a special case where variable reassignment
is possible.
Some observations for discussions after implementing this :-)...
[for (i=1,n=1; i <= 4; i=i+1, n=(n+i)*i) n]
=> [1, 6, 27, 124]
// Look, it's Runsun's magic sequence!
To make this work, we need to handle at least the 3rd part as
sequential assignment as let() does. Probably we also want this
for the 1st part, so it's both consistent and allows an initializer
list like "i = 1, n = i + 1".
The 2nd expression would be simply a boolean, so nothing special
there.
sort(x) = [for (L=x; L!=[]; m=min(L), L=[for (i=L) if (i > m) i]) m];
// non-recursive sort algorithm
This gives "undefined variable m" with my implementation as the
first iteration does not have m set yet. I think that's correct
as the generator expression is evaluated before the iterator
expression.
ciao,
Torsten.
Looks like a step too far (backwards) towards C++ to me.
On 5 January 2016 at 19:33, Torsten Paul Torsten.Paul@gmx.de wrote:
On 01/05/2016 05:20 AM, doug moen wrote:
I'm going to introduce another 'generator' operator for use in list
comprehensions. This operator is easy to understand, very powerful,
and can be used in place of recursive functions in many cases.
It is basically a direct rip-off of the C 'for' statement. If you
know C, the meaning should be obvious. I'll give examples.
[for (i=1; i <= 4; i=i+1) i]
=> [1,2,3,4]
Ah, nice, that's much more obvious than a magic variable. So
this would introduce a special case where variable reassignment
is possible.
Some observations for discussions after implementing this :-)...
[for (i=1,n=1; i <= 4; i=i+1, n=(n+i)*i) n]
=> [1, 6, 27, 124]
// Look, it's Runsun's magic sequence!
To make this work, we need to handle at least the 3rd part as
sequential assignment as let() does. Probably we also want this
for the 1st part, so it's both consistent and allows an initializer
list like "i = 1, n = i + 1".
The 2nd expression would be simply a boolean, so nothing special
there.
sort(x) = [for (L=x; L!=[]; m=min(L), L=[for (i=L) if (i > m) i]) m];
// non-recursive sort algorithm
This gives "undefined variable m" with my implementation as the
first iteration does not have m set yet. I think that's correct
as the generator expression is evaluated before the iterator
expression.
ciao,
Torsten.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 01/05/2016 08:41 PM, nop head wrote:
Looks like a step too far (backwards) towards C++ to me.
There are certainly some concerns about this. Introducing reassignment
in that special case is probably something that can cause some
confusion. Also with the future plan of unification of modules and
functions, this could lead to problems (need for serialized evaluation?).
So I pushed the other extensions separately, so we could have those
soon and still decide what to do with that c-style for expression...
ciao,
Torsten.
doug.moen wrote
[for (i=1,n=1; i <= 4;
i=i+1, n=(n+i)*i
) n]
=> [1, 6, 27, 124]
// Look, it's Runsun's magic sequence!
If i=i+1 and n=(n+i)*i are to be in the same scope, I would say this should
have given:
[ i=1,n=1 => next i = 2, next n= (n+2)*2= 4
, i=2,n=4 => next i = 3, next n= (4+3)*3= 21
, i=3,n=21 => next i = 4, next n= (21+4)*4= 100
, i=4,n=100 => next i=5, next n = (100+5)*5= 525
]
=> [4,21,100,525]
At least that's the way I think it is, following my coding instinct.
I think it's much harder to use and read than my version :)
Besides, my version allows users to grab any items that's already generated,
not just the last one. For example, this one adds the last two items of the
internal buffer (I introduce a @ as the buffer):
[ for(i=[1:4])
if (i==1) i
else if ( i==2) @[-1]
else (@[-1] + @[-2] )*i
]
=> [ 1
, 1*2 = 2
, (1+2)*3 = 9
, (2+9)*4 = 44
]
=> [ 1, 2, 9, 44 ]
This version adds all items previously generated, then * i :
[ for(i=[1:4]) sum(@) * i ]
=> [ 1, 2, 9, 48 ]
From my limited understanding, in terms of development, the only thing need
to work out is to define a special variable @.
$ Runsun Pan, PhD
$ libs:
doctest ,
faces ( git ),
offline doc ( git ),
runscad.py( 1 , 2 , git ),
synwrite( 1 , 2 );
$ tips:
hash( 1 , 2 ),
sweep ,
var( 1 , 2 ),
lerp ,
animGif ,
precision( 1 , 2 ),
xl-control
--
View this message in context: http://forum.openscad.org/List-comprehensions-tp15321p15506.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
@doug, I see your logic now:
[ i=1,n=1 => i=1, n= 1
, i=2,n=1 => next i= 2, next n = (1+2)*2 = 6
, i=3,n=6 => next i= 3, next n= (6+3)*3= 27
, i=4,n=27=> next i= 4, next n= (27+4)*4= 124
]
=> [1, 6, 27, 124]
Pls scratch that part of my comment.
$ Runsun Pan, PhD
$ libs:
doctest ,
faces ( git ),
offline doc ( git ),
runscad.py( 1 , 2 , git ),
synwrite( 1 , 2 );
$ tips:
hash( 1 , 2 ),
sweep ,
var( 1 , 2 ),
lerp ,
animGif ,
precision( 1 , 2 ),
xl-control
--
View this message in context: http://forum.openscad.org/List-comprehensions-tp15321p15507.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I wonder if you all are familiar with the Lisp loop macro.
IMHO its the best loop control system I have every used.
Rather than go for a C style of loop I'd rather see a more lisp and python
kind of control.
I refer you to these three short pages for examples and explanation.
- http://cl-cookbook.sourceforge.net/loop.html
- http://www.ai.sri.com/pkarp/loop.html
-
http://www.gigamonkeys.com/book/loop-for-black-belts.html
Here is the BNF form with all possible keywords (too many ):
E.g. (in LISP)
list_of_random_values = [...]
a = (loop for i in list_of_random_values
counting (evenp i) into evens
counting (oddp i) into odds
summing i into total
maximizing i into max
minimizing i into min
finally (return (list min max total evens odds)))
This would be modified a little for use in list comprehensions to imply the
return of a list and to eliminate the loop keyword. So it must start with a
for.
Likewise the do argument indicates the following will be the return values
(in LISP this would actually use "collect" instead of "do" as the keyword).
Actually "collect" might be clearer as that is what the list comprehension
does. I have used "do" below
To deal with initial values and internal variables there are such things as
with, initially, and finally.
In LISP the loop macro expands to the core lisp code which is actually
executed. This expansion is documented so you can see how to do it in
another language - but OpenSCAD's existing let statement (from lisp
initially) pretty much handles all cases we might need below.
Currently in openSCAD (as a list comprehension) a syntax example is:
- [ for (i=[0:10], j=[0:1]) let (a= [i, i*i]) a[j] ]
In openSCAD the syntax might look like : (I haven't worked out the ;
placement. using newlines)
-
Return same as input
[for [a b] in [[1 2] [3 4] [5 6]]
do [a b] ] -
Return just first part
[for [a b] in [[1 2] [3 4] [5 6]]
do a ]
You can see why "collect" might be clearer replacement for "do" but longer. -
Create pairs
[for x = [1:5]
for y = ["A","B","C","D","E"]
do [x y] ]
giving [[1 A] [2 B] [3 C] [4 D] [5 E]] -
Increment a second variable by using from. The end of the loop will be
defined by prior for definitions
[for x = [1:5]
for y from 10
do [x y] ]
giving [[1 10] [2 11] [3 12] [4 13] [5 14]] -
Early termination using while or until
[for x in [1,2,3,4,5,6]
while prime(x)
do [ x, x*x] ]
until can be used instead of while for a negative test -
Nested loops - here using extended from syntax but could just use existing
range like x=[1:4]
[for x from 1 to 4
[for y from 1 to x
collect y] ]
gives: [[1] [1 2] [1 2 3] [1 2 3 4]] -
using with statement (just add to implicit let() ) it leaves the variable
alone during the loop
[for x =[1,2,3,4,5,6]
with start = 12
while prime(x)
do [ x, x*start] ] -
"initially" is evaluated after the for and with statements define
variables but before the loop begins.
[for x =[3,4,5,6,7,8]
with start = 12
initially factor = startx
while prime(x)
do [ x, xstart+factor] ] -
using finally to return a single value after iterating over a large amount
of data
[for x=[1:100]
for y = (* x x)
until (y >= 729)
finally [x, (y == 729)] ]
returns a single pair with second value true if x*x == 729 else false
I.e. the internal list is created and just before returning the finally
clause is evaluated and returned instead. -
using conditionals within the loop (as an operator, not a regular if
statement)
[for x below 10
if odd(x)
collect x into odds
else
collect x into evens
finally [odds, evens] ]
gives [[1 3 5 7 9] [0 2 4 6 8]]
Thoughts ?
--
View this message in context: http://forum.openscad.org/List-comprehensions-tp15321p15508.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Torsten wrote: "There are certainly some concerns about this. Introducing
reassignment in that special case is probably something that can cause some
confusion."
It's not reassignment. There's a full explanation below.
nophead wrote: "Looks like a step too far (backwards) towards C++ to me."
Since Javascript also contains the for (..;..;..) operator, you could also
say it's a step too far towards Javascript.
Anyway, that's deliberate, and I will explain. OpenSCAD is a pure
functional language that has the syntax of C (and Javascript), which are
procedural languages. It's a weird design decision which threw me for a
loop when I first encountered it. But I see the logic. Javascript is the
world's most popular language, so giving OpenSCAD C-like syntax is maybe a
way of lowering the barrier to learning and using it.
In the functional programming community, there's this idea that explicit
recursion is the "goto" of functional programming, and that we should be
providing higher level "structured" programming constructs that make it
easier to write code without resorting to recursive functions. Back in the
1970's, there was a successful campaign to banish the "goto" in favour of
high level control structures like if..then..else.., for.., while.. and
switch.. What are the equivalent high level control structures that replace
the use of recursion?
Part of the answer is list comprehension syntax, and that has been a very
successful addition to OpenSCAD.
Beyond this, functional programming theorists have identified a number of
commonly occurring patterns of recursion, and designed high level control
structures that encapsulate these recursive patterns.
One of these patterns is called "anamorphism", and the corresponding
functional control structure is called "unfold". The functions that Torsten
wrote to generate Runsun's sequence are anamorphisms. They could be
rewritten using "unfold", but the problem is that "unfold" in Haskell has a
complex and hard to use interface. So I don't want that interface in
OpenSCAD.
When I tried to design a better interface, I discovered that the new
interface was structurally the same as a C for loop. Since OpenSCAD is
designed to be a pure functional language with C syntax, it was obvious we
should just use C for loop syntax, rather than invent something new.
Here's how it works:
[ for ( a=inita,b=initb,... ; condition ; a=nexta,b=nextb,... ) expr ]
is equivalent to:
function f(a,b,...) =
condition
? concat([expr], f(nexta,nextb,...))
: [ ];
f(inita,initb,...)
(Or you could convert this to tail recursion, like in Torsten's code.)
In other words, this really is functional programming. The
a=nexta,b=nextb,... section specifies the arguments that are passed to the
recursive call to f. It is not reassignment.
For example,
[for (i=1; i <= 4; i=i+1) i]
is equivalent to:
function f(i) =
i <= 4
? concat([i], f(i=i+1))
: [];
echo(f(i=1));
Note that i=i+1 occurs in the expansion. It isn't reassignment!
And I think the design must have achieved it's goal: Torsten liked it
enough to do a trial implementation.
On 5 January 2016 at 14:41, nop head nop.head@gmail.com wrote:
Looks like a step too far (backwards) towards C++ to me.
On 5 January 2016 at 19:33, Torsten Paul Torsten.Paul@gmx.de wrote:
On 01/05/2016 05:20 AM, doug moen wrote:
I'm going to introduce another 'generator' operator for use in list
comprehensions. This operator is easy to understand, very powerful,
and can be used in place of recursive functions in many cases.
It is basically a direct rip-off of the C 'for' statement. If you
know C, the meaning should be obvious. I'll give examples.
[for (i=1; i <= 4; i=i+1) i]
=> [1,2,3,4]
Ah, nice, that's much more obvious than a magic variable. So
this would introduce a special case where variable reassignment
is possible.
Some observations for discussions after implementing this :-)...
[for (i=1,n=1; i <= 4; i=i+1, n=(n+i)*i) n]
=> [1, 6, 27, 124]
// Look, it's Runsun's magic sequence!
To make this work, we need to handle at least the 3rd part as
sequential assignment as let() does. Probably we also want this
for the 1st part, so it's both consistent and allows an initializer
list like "i = 1, n = i + 1".
The 2nd expression would be simply a boolean, so nothing special
there.
sort(x) = [for (L=x; L!=[]; m=min(L), L=[for (i=L) if (i > m) i]) m];
// non-recursive sort algorithm
This gives "undefined variable m" with my implementation as the
first iteration does not have m set yet. I think that's correct
as the generator expression is evaluated before the iterator
expression.
ciao,
Torsten.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org