develooper Front page | perl.perl5.porters | Postings from April 2008

Re: Make built-in list functions continuous

Thread Previous | Thread Next
Nicholas Clark
April 5, 2008 11:09
Re: Make built-in list functions continuous
Message ID:
On Tue, Apr 01, 2008 at 11:38:24PM -0400, wren argetlahm wrote:
> Nicholas Clark wrote:

> >Which gets tricky, because there isn't an AST in the perl 5 interpreter.
> >(As I understand it, and this is not my strong point) the tokeniser and
> >lexer spit out an optree directly, having already done some 
> >transformations.
> >Further necessary transformations are performed by the same functions as
> >are actually also performing some true optimisations (eg the ck_* functions
> >that "check" ops as they are built, and the peephole optimiser)
> >Constant folding is performed as the optree is assembled.
> That does make things tricky (though an optree *is* an AST, albeit less 
> malleable than standard intermediate ASTs). If the tokenizer/lexer is 
> already doing some transformations, then it should be possible to add in 
> a few more. That is, assuming they have a large enough window to see the 
> whole statement before spewing anything out. I've done some XS but I 
> haven't really looked into the interpreter itself.

Sadly not.

The grammar generates ops as soon as it can. For example

	|	expr WHILE expr
			{ $$ = newLOOPOP(OPf_PARENS, 1, scalar($3), $1); }

OP *
Perl_newLOGOP(pTHX_ I32 type, I32 flags, OP *first, OP *other)

so by this point the two 'expr's are already reduced to optrees. Expressions
are reduced to optrees as soon as possible, so 3 * 2 + 1 gets compiled like

$ ./perl -DT -e '$a = 3 * 2 + 1'
### <== '$'

### 1:LEX_NORMAL/XOPERATOR "= 3 * 2 + 1\n"
### Pending identifier '$a'
### <== WORD(opval=op_const) PV("a"\0)

### 1:LEX_NORMAL/XOPERATOR "= 3 * 2 + 1\n"
### <== ASSIGNOP(ival=op_null)

### 1:LEX_NORMAL/XTERM " 3 * 2 + 1\n"
### Saw number in " * 2 + 1\n"
### <== THING(opval=op_const) IV(3)

### 1:LEX_NORMAL/XOPERATOR " * 2 + 1\n"
### <== MULOP(ival=op_multiply)

### 1:LEX_NORMAL/XTERM " 2 + 1\n"
### Saw number in " + 1\n"
### <== THING(opval=op_const) IV(2)

### <== ADDOP(ival=op_add)

### 1:LEX_NORMAL/XTERM " 1\n"
### Saw number in "\n"
### <== THING(opval=op_const) IV(1)

### <== ';'

### Tokener got EOF
### <== EOF


and the 3 * 2 will be constant folded to 6 before the ADDOP is created.

> All of this is moot however, since we don't need to take the 
> continuation of arbitrary functions. I'm only advocating that we do it 

I don't think that we can take continuations of arbitrary functions, because
we can't transform this:

sub foo {
    local $something::somewhere::else = 3;

    ... # do stuff foreach @_


into something that re-sets up $something::somewhere::else to 3 on each entry
*for the general case* because $something::somewhere::else might be a tied
variable, and so capable of generating side effects on each assignment. Hence
for the general case, one still must only assign it exactly once, and restore
it exactly once, and have its value be unaltered once the function returns.

If we add implicit continuations, at the "do stuff" point, one provides an
object that permits execution to jump back within the dynamic scope of &foo
(as if it had never left), at which point to keep inside &foo consistent,
$something::somewhere::else has to be set back to 3, but that violates the
other constraint that $something::somewhere::else is only assigned to once.

(Fortunately Perl 6 doesn't have this level of pessimism, as variables can't
be tied unless they are explicitly marked as being tie-able. This allows
the compiler to optimise the general case. I don't think that Parrot has any
such constraint on "active" data, so I'm not sure if this will reduce its
scope for optimisations)

> for the built-in list functions. I'm guessing that the implementation of 
> `map`, `grep`, etc are just thin wrappers around foreach-loops and so we 
> can pretty easily construct the component functions, i.e. the rewrites 
> using foreach-loops basically captures it.

They are not. They each use their own pairs of operators.

> Fair enough. I knew the optree stuff was hairy, though I didn't expect 
> it to be quite that hairy. If there aren't any hooks to apply 

They are very hairy. :-(

> transformations prior to only having the opcodes, that severely limits 
> the options. For someone familiar with the Filter modules and familiar 
> enough with Perl to reinvent the grammars for the lexer/parser, that 
> could be another avenue for proof of concept and debugging.

Even PPI doesn't manage to provide a grammar for Perl 5.

Nicholas Clark

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About