[M3devel] gcc 4.5.0?

[Mika Nystrom]

In Modula-3 you can pass a nested function in a function call.  It can
be quite useful but it's broken in PM3 so I never use it.

I've been meaning to write an optimistic Scheme compiler that uses tricks
with nested functions passed like that to allocate closures on demand...

(With nested functions, you can essentially set up a mechanism to jump
back up the stack, of course by doubling the recursion depth, and that
you could use to copy the stack into heap memory... something like that)

    Mika

Jay K writes:
>
>Of course. I tried to read it as a teenager and got stuck on the automata s=
>tuff.
>=20
>=20
>Wirth isn't 100% clear to me.
> He describes my two schemes.
> I think he throws out the second as an unimportant optimization.
> He criticizes the first as inefficient=2C granted.
> What I don't get is the static link in addition to the dynamic link.
> Perhaps I have not accounted for recursion.
>=20
>=20
>Oh..I see..he is allowing to take the address of a nested function.
>I didn't account for that.
>I still don't understand all the arrow he draws for the static link=2C but
>I do see that my scheme doesn't suffice.
>Taking the address of a nested function..doesn't seem like a good idea.
>Maybe I'm too C-minded.
>=20
>=20
>My prototypical favorite Scheme example is:
>=20
>=20
>(define (make-adder x)
>   (define (add y) (+ x y))
>   add)
>=20
>=20
>(define add2 (make-adder 2))
>(add2 3) =3D> 5
>=20
>=20
>but Modula-3 doesn't allow for that anyway..
>=20
>Still=2C we make "closures": tuple{-1=2C function pointer=2C frame pointer}
>before calling a pointer=2C we check if it points to -1=2C and if so
>we call function pointer with frame pointer as the link.
>=20
>=20
>And then I guess=2C you might have something like this?
>=20
>=20
>=20
>int F1(int a=2C int b=2C int (*F)())
>{
>  int F2()
>  {
>    return a + b=3B
>  }
>=20
>  if (F !=3D NULL)
>   return F()=3B
>=20
>  return F1(a - 1=2C b - 1=2C &F2)=3B
>=20
>}
>=20
>=20
>F(1=2C 2=2C NULL) =3D> 3
>=20
>=20
>Though that doesn't demonstrate the generality perhaps.
>=20
>=20
>Taking the address of a nested function seems dubious.
>=20
>=20
>My "favorite" bit of Schema:
>=20
>(define (make-adder x)
>   (define (add y) (+ x y))
>   add)
>=20
>=20
>(define add2 (make-adder 2))
>=20
>(add2 3) =3D> 3
>=20
>=20
>But we don't allow that sort of thing -- frames are always stack allocated.
>=20
>=20
>=20
> - Jay
>
>
>----------------------------------------
>> To: jay.krell at cornell.edu
>> Date: Thu=2C 20 May 2010 23:45:22 -0700
>> From: mika at async.async.caltech.edu
>> CC: m3devel at elegosoft.com
>> Subject: Re: [M3devel] gcc 4.5.0?
>>
>> The Dragon Book is
>>
>> Aho=2C Sethi=2C Ullman. Compilers: Principles=2C Techniques=2C and Tools.
>> Addison-Wesley=2C 1988. Chapter 7=2C esp. Sec. 7.4.
>>
>> Mika
>>
>> Jay K writes:
>>>
>>>Thanks for the reference!
>>>=3D20
>>>search for "Good Ideas=3D2C Through the Looking Glass"
>>>finds it right away: "http://www.cs.inf.ethz.ch/~wirth/Articles/GoodIdeas=
>_o=3D
>>>rigFig.pdf"
>>>(I don't need to provide the link really.)
>>>=3D20
>>> - Jay
>>>
>>>----------------------------------------
>>>> To: jay.krell at cornell.edu
>>>> Date: Thu=3D2C 20 May 2010 22:37:56 -0700
>>>> From: mika at async.async.caltech.edu
>>>> CC: m3devel at elegosoft.com
>>>> Subject: Re: [M3devel] gcc 4.5.0?
>>>>
>>>>
>>>> As I recall it the "Dragon Book" has a whole section on this topic of
>>>> nested functions in Pascal. Including Dijkstra's "display". I'm not
>>>> an expert=3D2C just remember reading it. Wirth also talks about it in h=
>is
>>>> "Good Ideas=3D2C Through the Looking Glass" (where he says the display
>>>> might be a pessimization).
>>>>
>>>> Mika
>>>>
>>>> Jay K writes:
>>>>>
>>>>>Maybe we can/should transform into one of the forms I show and dispense=
> w=3D
>>>it=3D3D
>>>>>h any gcc support?
>>>>>At the cost of losing some "easy" optimization..of nested functions?
>>>>> "easy" as in=3D3D2C occurs even without -O2=3D3D2C but might occur wit=
>h -O2?
>>>>>=3D3D20
>>>>>=3D3D20
>>>>>I know what you mean -- NT386 passes the static link in ecx.
>>>>>This is "ok" because in C++ the "this" pointer is passed in ecx.
>>>>>=3D3D20
>>>>>=3D3D20
>>>>>Passing it as "just" another parameter might be less efficient=3D3D2C b=
>ut o=3D
>>>k?
>>>>> And really=3D3D2C it'd only be less efficient on one architecture -- 3=
>2bit=3D
>>> x8=3D3D
>>>>>6.
>>>>> And maybe not all x86s -- depending on if some ABIs have a register ba=
>se=3D
>>>d=3D3D
>>>>> calling convention.
>>>>>=3D3D20
>>>>>=3D3D20
>>>>>We don't need any actual ABI-compatibility with anything here=3D3D2C do=
> we?
>>>>>=3D3D20
>>>>>=3D3D20
>>>>> - Jay
>>>>>
>>>>>
>>>>>----------------------------------------
>>>>>> From: hosking at cs.purdue.edu
>>>>>> Date: Thu=3D3D2C 20 May 2010 22:22:46 -0400
>>>>>> To: jay.krell at cornell.edu
>>>>>> CC: m3devel at elegosoft.com
>>>>>> Subject: Re: [M3devel] gcc 4.5.0?
>>>>>>
>>>>>> That is the standard formulation=3D3D2C but different architectures h=
>ave =3D
>>>diff=3D3D
>>>>>erent optimised forms (passing static link in a register=3D3D2C etc.). =
>In a=3D
>>>ny c=3D3D
>>>>>ase=3D3D2C gcc has its own weird way of doing things=3D3D2C which we mo=
>stly u=3D
>>>se=3D3D2C =3D3D
>>>>>but from which we need a little extra support (hence the small amount o=
>f =3D
>>>sp=3D3D
>>>>>ecial tailoring).
>>>>>>
>>>>>> On 20 May 2010=3D3D2C at 21:43=3D3D2C Jay K wrote:
>>>>>>
>>>>>>>
>>>>>>> Wierd. To me the model to follow is almost obvious. It should be obv=
>io=3D
>>>us=3D3D
>>>>> to everyone and implemented the way I have in mind. :)
>>>>>>>
>>>>>>>
>>>>>>> The static link is an extra parameter.
>>>>>>> And=3D3D2C as such=3D3D2C also an extra local variable.
>>>>>>> You only need one.
>>>>>>> Each nesting level would follow another chain.
>>>>>>> Or you can pass each nesting level as an extra parameter.
>>>>>>> Or you can optimize and pass locals/parameters separately.
>>>>>>> But there is an obvious straightforward non-optimized form. ?
>>>>>>>
>>>>>>>
>>>>>>> Here=3D3D2C I worked it through:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Why doesn't it just look something like this:
>>>>>>>
>>>>>>>
>>>>>>> nested:
>>>>>>>
>>>>>>> void F1(int a=3D3D2C int b)
>>>>>>> {
>>>>>>> int c =3D3D3D a + b=3D3D3B
>>>>>>>
>>>>>>> int f2()
>>>>>>> {
>>>>>>> int d =3D3D3D a + b=3D3D3B
>>>>>>>
>>>>>>> int f3()
>>>>>>> {
>>>>>>> return d + a + c=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>> return a + c + f3()=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>> return f2()=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>> not nested:
>>>>>>>
>>>>>>>
>>>>>>> typedef struct {
>>>>>>> /* locals */
>>>>>>> int d=3D3D3B
>>>>>>> void* x86_frame_pointer=3D3D3B
>>>>>>> void* x86_return_address=3D3D3B
>>>>>>> /* parameters */
>>>>>>> f1_frame_t* f1=3D3D3B
>>>>>>> } f2_frame_t=3D3D3B
>>>>>>>
>>>>>>>
>>>>>>> typedef struct {
>>>>>>> /* locals */
>>>>>>> int c=3D3D3B
>>>>>>> void* x86_frame_pointer=3D3D3B
>>>>>>> void* x86_return_address=3D3D3B
>>>>>>> /* parameters */
>>>>>>> int a=3D3D3B
>>>>>>> int b=3D3D3B
>>>>>>> } f1_frame_t=3D3D3B
>>>>>>>
>>>>>>>
>>>>>>> int f3(f2_frame_t* f2)
>>>>>>> {
>>>>>>> return f2->d + f2->f1->a + f2->f1->c=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> int f2(f1_frame_t* f1)
>>>>>>> {
>>>>>>> int d =3D3D3D f1->a + f1->b=3D3D3B
>>>>>>> return f1->a + f1->c + f3((f2_frame_t*)&d)=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> int F1(int a=3D3D2C int b)
>>>>>>> {
>>>>>>> int c =3D3D3D a + b=3D3D3B
>>>>>>> return f2((f1_frame_t*)&c)=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> or=3D3D2C alernatively=3D3D2C almost the same=3D3D2C pass each chain=
> as anot=3D
>>>her para=3D3D
>>>>>meter:
>>>>>>>
>>>>>>>
>>>>>>> typedef struct {
>>>>>>> /* locals */
>>>>>>> int d=3D3D3B
>>>>>>> void* x86_frame_pointer=3D3D3B
>>>>>>> void* x86_return_address=3D3D3B
>>>>>>> /* parameters */
>>>>>>> } f2_frame_t=3D3D3B
>>>>>>>
>>>>>>>
>>>>>>> typedef struct {
>>>>>>> /* locals */
>>>>>>> int c=3D3D3B
>>>>>>> void* x86_frame_pointer=3D3D3B
>>>>>>> void* x86_return_address=3D3D3B
>>>>>>> /* parameters */
>>>>>>> int a=3D3D3B
>>>>>>> int b=3D3D3B
>>>>>>> } f1_frame_t=3D3D3B
>>>>>>>
>>>>>>>
>>>>>>> int f3(f2_frame_t* f2=3D3D2C f1_frame_t* f1)
>>>>>>> {
>>>>>>> return f2->d + f1->a + f1->c=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> int f2(f1_frame_t* f1)
>>>>>>> {
>>>>>>> int d =3D3D3D f1->a + f1->b=3D3D3B
>>>>>>> return f1->a + f1->c + f3((f2_frame_t*)&d=3D3D2C f1)=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> int F1(int a=3D3D2C int b)
>>>>>>> {
>>>>>>> int c =3D3D3D a + b=3D3D3B
>>>>>>> return f2((f1_frame_t*)&c)=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> This should be easily adapted to any function call convention/sequen=
>ce=3D
>>>.
>>>>>>> e.g. even if parameters are passed in registers.
>>>>>>>
>>>>>>>
>>>>>>> And for that matter=3D3D2C why don't we just transform it to be like=
> thi=3D
>>>s?
>>>>>>> With the goal of reducing/eliminating gcc patches?
>>>>>>>
>>>>>>>
>>>>>>> Am I missing something?
>>>>>>>
>>>>>>>
>>>>>>> This form doesn't work?
>>>>>>>
>>>>>>>
>>>>>>> Isn't reasonably simple?
>>>>>>>
>>>>>>>
>>>>>>> Granted it might not be optimal. But it depends.
>>>>>>> You know=3D3D2C you can copy in the local/parameter values=3D3D2C bu=
>t then=3D
>>> you h=3D3D
>>>>>ave
>>>>>>> to copy them out too. You can do analysis to show they aren't change=
>d=3D
>>>=3D3D2C
>>>>>>> in which case no need to copy them out.
>>>>>>> Similarly you can pass the parameters as separate parameters=3D3D2C =
>by a=3D
>>>ddre=3D3D
>>>>>ss
>>>>>>> if they are ever changed.
>>>>>>>
>>>>>>>
>>>>>>> A portable transform couldn't depend on adjacency of locals and para=
>me=3D
>>>te=3D3D
>>>>>rs.
>>>>>>> It would have to either copy the parameters into the frame_t=3D3D2C =
>or t=3D
>>>heir=3D3D
>>>>> addresses.
>>>>>>>
>>>>>>>
>>>>>>> A portable form couldn't get the frame by taking the address of a "i=
>nd=3D
>>>iv=3D3D
>>>>>idual" local.
>>>>>>>
>>>>>>>
>>>>>>> Here is portable form:
>>>>>>>
>>>>>>>
>>>>>>> typedef struct {
>>>>>>> int d=3D3D3B
>>>>>>> f1_frame_t* f1=3D3D3B
>>>>>>> } f2_frame_t=3D3D3B
>>>>>>>
>>>>>>> typedef struct {
>>>>>>> int a=3D3D3B
>>>>>>> int b=3D3D3B
>>>>>>> int c=3D3D3B
>>>>>>> } f1_frame_t=3D3D3B
>>>>>>>
>>>>>>>
>>>>>>> int f3(f2_frame_t* f2)
>>>>>>> {
>>>>>>> return f2->d + f2->f1->a + f2->f1->c=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>> int f2(f1_frame_t* f1)
>>>>>>> {
>>>>>>> f2_frame_t f=3D3D3B
>>>>>>> f.f1 =3D3D3D f1=3D3D3B
>>>>>>> f.d =3D3D3D f1->a + f1->b=3D3D3B
>>>>>>> return f1->a + f1->c + f3(&f)=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> int F1(int a=3D3D2C int b)
>>>>>>> {
>>>>>>> f1_frame_t f=3D3D3B
>>>>>>> f.a =3D3D3D a=3D3D3B
>>>>>>> f.b =3D3D3D b=3D3D3B
>>>>>>> f.c =3D3D3D a + b=3D3D3B
>>>>>>> return f2(&f)=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> or:
>>>>>>>
>>>>>>>
>>>>>>> typedef struct {
>>>>>>> int d=3D3D3B
>>>>>>> } f2_frame_t=3D3D3B
>>>>>>>
>>>>>>>
>>>>>>> typedef struct {
>>>>>>> int a=3D3D3B
>>>>>>> int b=3D3D3B
>>>>>>> int c=3D3D3B
>>>>>>> } f1_frame_t=3D3D3B
>>>>>>>
>>>>>>>
>>>>>>> int f3(f2_frame_t* f2=3D3D2C f1_frame_t* f1)
>>>>>>> {
>>>>>>> return f2->d + f1->a + f1->c=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> int f2(f1_frame_t* f1)
>>>>>>> {
>>>>>>> f2_frame_t f=3D3D3B
>>>>>>> f.d =3D3D3D f1->a + f1->b=3D3D3B
>>>>>>> return f1->a + f1->c + f3(&f=3D3D2C f1)=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> int F1(int a=3D3D2C int b)
>>>>>>> {
>>>>>>> f1_frame_t f=3D3D3B
>>>>>>> f.a =3D3D3D a=3D3D3B
>>>>>>> f.b =3D3D3D b=3D3D3B
>>>>>>> f.c =3D3D3D a + b=3D3D3B
>>>>>>> return f2(&f)=3D3D3B
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> - Jay
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> ----------------------------------------
>>>>>>>> Date: Thu=3D3D2C 20 May 2010 12:12:00 -0500
>>>>>>>> From: rodney_bates at lcwb.coop
>>>>>>>> To: m3devel at elegosoft.com
>>>>>>>> Subject: Re: [M3devel] gcc 4.5.0?
>>>>>>>>
>>>>>>>> gcc even extends C with nested functions=3D3D2C and the support is =
>ther=3D
>>>e fo=3D3D
>>>>>r that. We use it too.
>>>>>>>>
>>>>>>>> Beware: The runtime model is=3D3D2C IMO=3D3D2C bizarre. Definitely =
>counte=3D
>>>rintui=3D3D
>>>>>tive and unlike anything
>>>>>>>> you will ever see elsewhere. There are two static links. One is use=
>d =3D
>>>fo=3D3D
>>>>>r the first step
>>>>>>>> in following a static chain and points to the expected place in the=
> t=3D
>>>ar=3D3D
>>>>>get frame. The other
>>>>>>>> is used of subsequent steps in chain-following=3D3D2C and points to=
> som=3D
>>>ewhe=3D3D
>>>>>re inside the target
>>>>>>>> frame that is dependent on the target procedure. It's the beginning=
> o=3D
>>>f =3D3D
>>>>>a subrecord where
>>>>>>>> all the nonlocally-referenced variables are collected. The second s=
>ta=3D
>>>ti=3D3D
>>>>>c link is also
>>>>>>>> located in there. All the nonlocally-referenced variables and param=
>et=3D
>>>er=3D3D
>>>>>s are duplicated
>>>>>>>> in there too.
>>>>>>>>
>>>>>>>> I'm not sure I remembered these details exactly right. Maybe both l=
>in=3D
>>>ks=3D3D
>>>>> point to the
>>>>>>>> subrecord=3D3D2C but one is located at a traditional procedure-inde=
>pend=3D
>>>ent=3D3D
>>>>>=3D3D2C fixed location
>>>>>>>> in the frame=3D3D2C while the second is located in the subrecord. A=
>lso=3D
>>>=3D3D2C s=3D3D
>>>>>ometimes the first
>>>>>>>> static link value is kept in a register and never stored.
>>>>>>>>
>>>>>>>> What this all apparently accomplishes is simplifying an "insanely c=
>om=3D
>>>pl=3D3D
>>>>>icated" _compile-time_
>>>>>>>> scheme that=3D3D2C I believe came from interaction between nested p=
>roce=3D
>>>dure=3D3D
>>>>>s and inlining them.
>>>>>>>>
>>>>>>>> But it's at the cost of what I would call an insanely complicated _=
>ru=3D
>>>nt=3D3D
>>>>>ime_ scheme.
>>>>>>>>
>>>>>>>> It undermined m3gdb's handling of static links=3D3D2C and I don't t=
>hink=3D
>>> it'=3D3D
>>>>>s possible to fix
>>>>>>>> with the current design of emitting debug info very early. The loca=
>ti=3D
>>>on=3D3D
>>>>>s and target
>>>>>>>> offsets of these things aren't know until later=3D3D2C and m3gdb re=
>ally=3D
>>> nee=3D3D
>>>>>ds to know them.
>>>>>>>>
>>>>>>>>
>>>>>>>> Jay K wrote:
>>>>>>>>> What I meant regarding "static chain" was more like "does gcc alre=
>ad=3D
>>>y =3D3D
>>>>>have support that we can use".
>>>>>>>>> Don't any of the other languages need it already?
>>>>>>>>> Ada? Pascal? Maybe the nested C function support?
>>>>>>>>>
>>>>>>>>> - Jay
>>>>>>>>>
>>>>>> =3D3D =3D 		 	   		  =