headers
John Carter | 1 Nov 2004 02:46
Picon

Re: [stack] Some notes on stack effect inference


On Thu, 28 Oct 2004, Slava Pestov wrote:

> http://www.jroller.com/page/slava/20041028#type_inference

Ah, I see you fairly rapidly hit that brick wall that all the
concatenative languages I have seen so far hit....

Conditional Stack Effects.

How do you infer past an "if" statement.

The "then" branch can do arbitarily nastily different things to the
stack compare to the "else" branch. So what is the 'net stack effect?

It gets really messy.

Yet compare that to more traditional lambda calculus / call / function
environment.

All stack effects get rolled up and undone as soon as you as you hit
return. Much simpler to analyze. A Lambda calcalus _always_ has a
simply functional mapping of [input1, input2, input3,...] => [single
output value]

Is this a hard trade off? Stack languages are easier than lambda
calculus to analyze in that argument binding is not present, but
harder to analyze the the return values.

One fix may be a stack language where the compiler enforces that
(Continue reading)

Permalink | Reply | 15 comments |
headers
Slava Pestov | 1 Nov 2004 03:11

[stack] Factor interpreter in Factor


Hi everybody,

I have implemented a reflective Factor interpreter in Factor, along with 
a basic trace and stepper tool. This code should work with Factor 0.67.

---->8-------------

USE: vectors
USE: namespaces
USE: logic
USE: kernel
USE: combinators
USE: lists
USE: words
USE: stack
USE: errors
USE: continuations
USE: strings
USE: prettyprint
USE: stdio

! A Factor interpreter written in Factor. Used by compiler for
! partial evaluation, also for trace and step.

! Meta-stacks
SYMBOL: meta-rs
: >R meta-rs get vector-push ;
: R> meta-rs get vector-pop ;
SYMBOL: meta-ds
(Continue reading)

Permalink | Reply | 0 comments |
headers
William Tanksley, Jr | 1 Nov 2004 17:57
Picon

Re: [stack] Some notes on stack effect inference


On Mon, 01 Nov 2004 14:46:45 +1300 (NZDT), John Carter
<john.carter <at> tait.co.nz> wrote:
> Ah, I see you fairly rapidly hit that brick wall that all the
> concatenative languages I have seen so far hit....
> Conditional Stack Effects.
> How do you infer past an "if" statement.

Yup, that's a problem. Loops are possibly worse.

The solution is to have two new anonymous types: iterated and
conditional. The "iterated" type encloses a single stack signature and
indicates that it could be repeated any number of times; the
"conditional" type encloses two stack signatures, and indicates that
either one may be valid at runtime.

Then, depending on the strength of your type inference engine, you can
allow those types to propagate to various levels. The easiest choice,
of course, is to provide no support for them; this means that all
loops must be balanced, and all IFs must have the same type effect as
their THENs. The next easiest choice is to not allow those types to be
returned from functions; this means that every word must clean up its
own mess.

If you allow more than this, I don't know of a static solution; to the
best of my knowledge, you need to provide runtime facilities. But this
makes sense, because the problem at hand IS a dynamic stack.

-Billy
(Continue reading)

Permalink | Reply | 2 comments |
headers
sa | 1 Nov 2004 19:06

Re: [stack] Some notes on stack effect inference


John Carter <john.carter <at> tait.co.nz> wrote on 10/31/2004 08:46:45 PM:

[:]

>
> One fix may be a stack language where the compiler enforces that
> the stack effect of the "then" branch must be exactly the same as the
> "else" branch.
>

as some of you know, i've been advocating the project of integrating
vector programming techniques into the concatenative language framework.
in the ideal world, we never loop.  computation is just the flow of data
through array primitives.

over the years, APLers have accumulated hundreds, if not thousands of
techniques for just this purpose.  some of these results are wonderfully
counterintuitive.

here is a simple example.

given a string y of space-delimited words and an integer x, cut y into
a list of strings [ .. z .. ] where the count of each z is less than or
equal to x, and every word in y is wholly contained in just one z.

  wrap[20;"this is a string consisting of words separated by blanks"]
("this is a string "
 "consisting of "
 "words separated by "
(Continue reading)

Permalink | Reply | 1 comment |
headers
sa | 1 Nov 2004 19:55

Re: [stack] Some notes on stack effect inference


k:

  wrap:{(b -1_(-1+b _binl x+b:0,1+&" "=y)\0)_ y,:" "}

XY:

  ; wrap [' , dup] dip swap ' = &: 1 + 0 ,.
         dup [+] dip swap [dup] dip _binl
         -1 + 0 swap .v! -1 _.  <at>  _. ;

'wrap' requires nine (!) stack shuffle words:  three dips,
three dups, and three swaps.

using pattern-notation, we can eliminate them all:

  ; wrap  { [s w] s ' , ' = &: 1 + 0 ,. s w wrap. } ;
  ; wrap. { [b s w] 0 b b w + _binl -1 + .v! -1 _. b  <at> . s _ } ;

------------------------ Yahoo! Groups Sponsor --------------------~--> 
$9.95 domain names from Yahoo!. Register anything.
http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/saFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/
(Continue reading)

Permalink | Reply | 0 comments |
headers
sa | 5 Nov 2004 19:05

[stack] finding joined line-segments


An entertaining problem which appeared on comp.lang.functional the
other day:

http://groups.google.com/groups?hl=en&lr=&selm=1099278642.163792.174710%40z14g2000cwz.googlegroups.com&rnum=1

a k solution, which i'll probably post tonight:

http://www.nsl.com/papers/lines.htm

howzabout one in joy, or factor?

------------------------ Yahoo! Groups Sponsor --------------------~--> 
$9.95 domain names from Yahoo!. Register anything.
http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/saFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> To unsubscribe from this group, send an email to:
    concatenative-unsubscribe <at> yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
(Continue reading)

Permalink | Reply | 1 comment |
headers
Slava Pestov | 7 Nov 2004 04:54

[stack] More stack effect work


Hi everybody,

I have posted some more (incomplete for now) stack algebra results, as 
well as a detailed description of an actual stack effect inference 
algorithm that works with recursive words at 
http://www.jroller.com/page/slava/.

The code can be found in CVS:

http://cvs.sourceforge.net/viewcvs.py/factor/Factor/Factor/library/tools/inference.factor?view=markup

It is reasonably complete, however it has some limitations:

- While simple recursive words can have their stack effects inferred, 
recursive combinators (like each, map, and so on) do not.

- Only a small set of primitives has their stack effects specified.

Neither of these is unfixable, and the next iteration of the code will 
solve them.

The next steps I want to take with this is proving the two conjectures 
about generalized recursive stack effects, finishing the inference 
algorithm, then extending the model to infer types.

Slava

------------------------ Yahoo! Groups Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Paul-V Khuong | 7 Nov 2004 20:16
Picon
Favicon

Re: [stack] More stack effect work


> Message: 1         
>    Date: Sat, 06 Nov 2004 22:54:40 -0500
>    From: Slava Pestov <slava <at> jedit.org>
> Subject: More stack effect work
> 
> Hi everybody,
> 
> I have posted some more (incomplete for now) stack
> algebra results, as 
> well as a detailed description of an actual stack
> effect inference 
> algorithm that works with recursive words at 
> http://www.jroller.com/page/slava/.
[...]
> It is reasonably complete, however it has some
> limitations:
> 
> - While simple recursive words can have their stack
> effects inferred, 
> recursive combinators (like each, map, and so on) do
> not.
> 
> - Only a small set of primitives has their stack
> effects specified.
> 
> Neither of these is unfixable, and the next
> iteration of the code will 
> solve them.
[...]
(Continue reading)

Permalink | Reply | 0 comments |
headers
phimvt | 8 Nov 2004 05:29
Picon
Picon

Re: [stack] Some notes on stack effect inference


On Mon, 1 Nov 2004, John Carter wrote:

[..]

> Conditional Stack Effects.
> 
> How do you infer past an "if" statement.
> 
> The "then" branch can do arbitarily nastily different things to the
> stack compare to the "else" branch. So what is the 'net stack effect?
> 
> It gets really messy.

But the same kind of problems arise with lists in other languages.

First, take homogeneous lists such as lists of integers, [11 22 33]
or [100 200 300 400]. There will be a possible program which, 
expressed procedurally, says: if the first item in the list is
less than 20, then delete it from the list else leave it. Or in
Joy:  test1 == [first 20 <] [rest] [] ifte. Or in a Lisp-like lambda
calculus language: (define test1(L) (if (< (car L) 20) (cdr L) (L))
So, if the type checker keeps track of the length of lists, then any
such branching function requires the checker to handle exactly the
same "problem" (if indeed it is a problem) as you mentioned. As far
as I know, strongly typed functional languages would not see it as
a problem at all, they treat the type simply as "list-of-integer"
and do not bother about the length.

In languages where lists can be heterogenous one might have the lists
(Continue reading)

Permalink | Reply | 9 comments |
headers
sa | 8 Nov 2004 17:40

Re: [stack] finding joined line-segments


i found a completely non-iterative solution to this problem on the drive
into work this morning.

see the revisions to the paper below.  (it's evil)

sa <at> dfa.com wrote on 11/05/2004 01:05:46 PM:

>
>
>
>
>
>
> An entertaining problem which appeared on comp.lang.functional the
> other day:
>
>
http://groups.google.com/groups?hl=en&lr=&selm=1099278642.163792.174710%40z14g2000cwz.googlegroups.com&rnum=1

>
> a k solution, which i'll probably post tonight:
>
> http://www.nsl.com/papers/lines.htm
>
> howzabout one in joy, or factor?
>
>
>
>
(Continue reading)

Permalink | Reply | 0 comments |

Gmane