HDTenEightyP/NetNews huggingface dataset:
From: pardo@cs.washington.edu (David Keppel)
Subject: GC across address spaces (WAS: Adding garbage collection to C++)
Reply-To: pardo@cs.washington.edu (David Keppel)
Organization: Computer Science & Engineering, U. of Washington, Seattle
Date: Wed, 19 Aug 1992 00:09:51 GMT
Keywords: C, GC, parallel

>bill@amber.ssd.csd.harris.com (Bill Leonard) writes:
>>[How to garbage collect multi-threaded programs where some pointers to
>> shared memory are kept in per-thread private storage]

tmb@idiap.ch writes:
>[You don't need "garbage collection only if specifically asked for.
> Just retain a pointer to the object in the address space of A.
> In fact, you can encapsulate this behavior nicely inside your "send"
> procedure.]

One of the big reasons for using GC is that it frees the programmer from
managing object lifetimes explicitly.  Some parallel programming
practicioners say (I think correctly) that figuring out lifetimes is, in
general, substantially harder with parallelism than without.

Explicitly retaining a pointer will solve the problem but defeats one of
the reasons for having GC in the first place.  Now the programmer of
address space A must decide when address space B has finished with the
memory and the pointer in A can be destroyed.  Some of the mental overhead
can be masked by various protocols, but the pointer still comes at the
programmer's expense.

The technique of ``keeping a pointer'' to prevent GC is good.  So is
promoting storage from gc'able to non-gc'able.  Ideally, you keep a
uniform programming model and the underlying implementation is optimized.
In practice, you probably keep a uniform programming model but the
implementors of libraries, stubs, etc., are forced to worry about the
performance issues and choose implementations accordingly.

  ;-D on  ( Sharing memory with every process that's shared it )  Pardo
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: henry@zoo.toronto.edu (Henry Spencer)
Subject: Re: Adding garbage collection to C++
Reply-To: henry@zoo.toronto.edu (Henry Spencer)
Organization: U of Toronto Zoology
Date: Fri, 14 Aug 1992 21:29:17 GMT
Keywords: C, GC

our moderator writes:
>[It is my impression that an ANSI C program is allowed to copy a pointer to
>a long and later back to a pointer of the same type...

Yes, but it doesn't promise what you'll get.  Many older definitions of C
promised that you could convert a pointer to a suitably-large integer
(long isn't necessarily large enough!) and then back again unchanged.
Some of the ANSI C drafts also promised that.  The final standard does
not.

Don't feel bad about overlooking this, Dennis Ritchie missed it too...
which is why even revised K&R2 gets this wrong.  (Unless there's been a
chance for another revision recently; Dennis does know about this.)
-- 
Henry Spencer @ U of Toronto Zoology, henry@zoo.toronto.edu  utzoo!henry
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: grover@brahmand.Eng.Sun.COM (Vinod Grover)
Newsgroups: comp.compilers
Subject: Re: Code Generation by Coagulation?
Keywords: code, optimize, bibliography
Date: 13 Aug 92 05:46:51 GMT
Reply-To: grover@brahmand.Eng.Sun.COM (Vinod Grover)
Organization: Sun Microsystems, Mt. View, Ca.

jeremy@sw.oz.au (Jeremy Fitzhardinge) writes:
>I've been looking through the paper "Code Generation by Coagualtion" by
>Michael Karr, published in 1984.  ...

There was a followup quite recently. Look at:

"CCG: A Prototype Coagulating Code Generator", W.G. Morris, 
ACM Conference on Programming Language Design and Implementation,
June 1991.

-- Vinod Grover
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: sasghm@unx.sas.com (Gary Merrill)
Newsgroups: comp.compilers
Subject: Re: Two-pass C compilers
Keywords: C, design
Date: 17 Aug 92 17:14:59 GMT
Reply-To: Gary Merrill <sasghm@unx.sas.com>
Organization: Compilers Central

As posed, this question is a pseudo-question and is unanswerable.  The
answer hinges on what we mean by "pass".  As John has pointed out, the
"classical" meaning of pass (as applied to assemblers) pertains to the
number of times the *source* is read.  With high- level languages, the
concept of pass becomes a bit more murky, and even in the best texts there
is confusion.

For example, in _The_Theory_and_Practice_of_Compiler_Writing_, Tremblay
and Sorenson first define "separate pass" as meaning "examine the entire
source program".  Yet two paragraphs later they conflate "phase" and
"pass" (using both terms) in such assertions as

	[T]he optimization phase may require that several
        passes of the source program (or its intermediate
        form) be made.

and then

	[T]he optimization phase is often spread throughout
	the other pases of the compilation process ...

I find this second statement especially puzzling, but it is clear that
they intend to extend the idea of "pass" to include the processing of an
intermediate representation.

If we employ this broader notion of "pass", then every C compiler known to
me is multi-pass.  Whether the intermediate representation is in a file on
the disk, in memory, or on my notepad is irrelevant.  (Note that
frequently the intermediate representation is not textual in nature, but
is a binary representation of a tree or a set of quadruples.  In fact,
there may be *several* intermediate representations, depending upon how
much and what kind of optimization is desired.)  But if we employ the
narrower (classical) notion of "pass", then every C compiler known to me
is single pass since I know of none (there *may* be some, but I can't
imagine why) that read the original source more than once.  Even those
compilers that first generate a file of tokenized input (at least the old
Whitesmith's compiler used to do this) are single pass since they read the
original source only once.

---
Gary H. Merrill  [Principal Systems Developer, C Compiler Development]
SAS Institute Inc. / SAS Campus Dr. / Cary, NC  27513 / (919) 677-8000
sasghm@theseus.unx.sas.com ... !mcnc!sas!sasghm
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: pakstas@idt.unit.no (Algirdas Pakstas)
Newsgroups: comp.compilers
Subject: Re: A Non-LALR(1) Parser Generator
Keywords: parse, bibliography, LALR
Date: 17 Aug 92 17:11:21 GMT
Reply-To: pakstas@idt.unit.no (Algirdas Pakstas)
Organization: Div. of CS & Telematics, Norwegian Institute of Technology

bromage@mullauna.cs.mu.oz.au (Andrew Bromage) writes:
|[re Pager's work on parser generators]

Also, D Pager's approach was used in parser constructor called LALR,
which is stored in DECUS library (written in MACRO-11 under RSX-11):

@misc(LALR,
     title="{LALR(1)} parser constructor to translate computer languages",
     note="DECUS Program Library, N11-312")

and in GDT_PC (Grammar Debugging Tool and Parser Constructor) developed by
Dept. of Software Engineering for Distributed Computer Systems of the
Institute of Math. & Informatics, Vilnius, Lithuania:

@inproceedings(Pakshtas-88,
	author="Pakshtas, A.", 
	title="Design and debugging of user-friendly interfaces for
               the DCCS software development system",
	booktitle="Proc. 6th Intern. Conf. on Systems Engineering,
                   Coventry, England, 13-15 Sept. 1988",
        year=1988,
        month=sep,
        pages="876--883")

@inproceedings(Pakshtas-89f,
        author="Pak{\v{s}}tas, Algirdas and R. Meidut{\.{e}} 
                and G. Stradalov",
        title="A Software System for Parser Constructing with
               Full-Screen Debugging Facilities",
        booktitle="System Sciences X, Inter. Conf. on Systems
                   Sciences",
        address="Wroclaw, Poland",
        year=1989,
        month=sep,
        pages=145,
        note="(Abstr. of Papers)")

@book(BOOK2-91,
     author="Pak{\v{s}}tas, Algirdas and Zolotariov, Nicolay",
     title="Syntax-oriented Components of Distributed Systems:
            Development and Debugging Tools on the Basis of
            Formal Descriptions",
     publisher="Nauka",
     address="Moscow",
     year=1991,
     note="280p. (in Russian)")

@techreport(Pakshtas-92d,
        author="Pak{\v{s}}tas, Algirdas and Stradalov, Georgij",
        title="{On Grammar Splitting/Debugging and Parser Table Linking
         Technique and Tools}",
        institution="The Norwegian Institute of Technology",
        address="N-7034, Trondheim, Norway",
        year=1992,
        type="EPOS paper",
        number=21,
        note="17p.",
        month=feb)

-- Algirdas Pakstas
_______________________________________________________________
Algirdas.Pakstas@idt.unit.no                  NTH IDT
Ph.: +47-7-594485                             N-7034, Trondheim
FAX: +47-7-594466                             Norway
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: Hao-yang Wang <hywang@apple.com>
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Reply-To: Hao-yang Wang <hywang@apple.com>
Organization: Compilers Central
Date: Wed, 12 Aug 1992 18:20:55 GMT
Keywords: Basic, C, performance

1. The "ON ERROR GOTO..." statement, as well as other "ON ... GOTO..."
statements, is not easy to implement in a compiled environment.

2. To support the strings in BASIC, we need (a) a heap, (b) some garbage
collecting or reference counting technique.  These will introduce some
overhead in memory management.

These language features are not unique to BASIC.  And we can see that the
implementations of any languages with these features can hardly beat the
implementations of C in execution efficiency.

Hao-yang Wang
Pai Technology, Inc
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.lang.basic
From: maniattb@cs.rpi.edu (Bill Maniatty)
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Reply-To: maniattb@cs.rpi.edu (Bill Maniatty)
Organization: Compilers Central
Date: Wed, 12 Aug 1992 20:48:27 GMT
Keywords: Basic, C, performance

Glenn_Johansson@f313.n203.z2.fidonet.cd.chalmers.se writes:
|> 2. Why is the basic compilers creating a slower product than the C
|> compilers?

Slower in what sense, rate of compilation, or the run time speed of
executables generated.  C requires more than one pass for compilation, and
therefore compiles slower than Basic.  Basic is much easier to compile and
interpret than C (recall in the beginning of the PC movement Basic was the
first higher level language for many machines, Altair, Commodore, Apple,
IBM).  The address space for a Basic interpreter/compiler is much smaller
than for C.

C is a more accurate representation of the underlying hardware, and it is
possible for the programmer to take advantage of that knowledge.  Basic is
not a stack oriented language and cannot take advantage of the hardware
stack the same way that 'C' can.  The C programmer has access to low level
(by that I mean close to the hardware) operations.  C supports bit map
management, pointers, compile time constant folding, the register
qualifier etc.

Also since Basic is not suitable for implementation of large projects and
system software, much less work goes into optimization.

Basic programmers just don't have the same tools at their disposal.

Bill
-- 
|	maniattb@cs.rpi.edu - in real life Bill Maniatty
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Subject: Re: Adding garbage collection to C++
Reply-To: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Organization: MAXTAL P/L C/- University Computing Centre, Sydney
Date: Thu, 20 Aug 1992 23:41:50 GMT
Keywords: C, GC, parallel

>[How do you garbage collect multi-threaded programs where some pointers to
>shared memory are kept in per-thread private storage]

	Clearly you have to GC at the level of sharing. If A and B share
storage, you have to make the collector scan the stacks of both A and B.
So the collector needs to be implemented in the Operating system.

	Perhaps simply retaining a pointer in the address space of A works
for threads, but it doesnt work for systems like Windows, where you 'give
away' the pointer to the OS. There IS no stack or local address space
between callbacks into you're program, so there is nowhere to retain that
pointer.

-- 
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: pardo@cs.washington.edu (David Keppel)
Subject: Re: Adding garbage collection to C++
Reply-To: pardo@cs.washington.edu (David Keppel)
Organization: Computer Science & Engineering, U. of Washington, Seattle
Date: Sat, 15 Aug 1992 22:04:59 GMT
Keywords: C++, GC, parallel

bill@amber.ssd.csd.harris.com (Bill Leonard) writes:
>[Garbage collection across multiple processes is hard ...]

But not impossible:

AUTHOR = "John Hughes",
TITLE = "A Distributed Garbage Collection Algorithm",
BOOKTITLE = "Functional Programming Languages and Computer
Architecture",
YEAR = 1985, PAGES = {256--272}

%T STRUCTURING DISTRIBUTED APPLICATIONS AS FRAGMENTED OBJECTS
%A Mesaac Makpangou
%A Yvon Gourhant
%A Jean-Pierre Le Narzul
%A Marc Shapiro
%R Rapport de Recherche INRIA 1404
%D February 1991
%X nelly@sor.inria.fr, anonymous FTP nuri.inria.fr [128.93.1.26]

%T Robust, Distributed References and Accylic Garbage Colelction
%A Marc Shapiro
%A Peter Dickman
%A David Plainfosse
%J Symposium on Principles of Distributed Computing
%C Vancouver, Canada
%D August 1992
%X marc.shapiro@inria.fr

%A Barbara Liskov
%A Rivka Ladin
%T Higly-Available Distributed Services and Fault-Tolerant Distributed
Garbage Collection
%J Proceedings of the 5th Symposium on the Principles of Distributed
Computing
%P 29-39
%D August 1986
%C Vancouver, Canada
%X rivka@crl.dec.com

>[Thus I advocate GC can be turned on or off.]

To my mind, being able to turn it on or off is a good idea, even when
decide that distributed gc is possible.  You do need to have a tight
definition on the language & system behavior when it is turned off.

	;-D on  ( This idea is GARBAGE ... collection  )  Pardo
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1416 comp.lang.c:12583
From: mcrware!adam@uunet.UU.NET (Adam Goldberg)
Newsgroups: comp.compilers,comp.lang.c
Subject: Re: Two-pass C compilers
Keywords: C
Date: 19 Aug 92 14:31:04 GMT
Reply-To: mcrware!adam@uunet.UU.NET (Adam Goldberg)
Organization: Microware Systems Corp., Des Moines, Iowa

behrenss@Informatik.TU-Muenchen.DE (Soenke Behrens) writes:
>Hmmm ... beat me if I something silly, but: Is there any way around
>a two-pass compiler? (Or even more passes)

>First pass: Reading in the source, preprocessing it, building a symbol table.
>Second pass: Generate p-Code
>Third pass: Optimize p-Code (Note: Do not mix with 2nd pass or you are
>in deep trouble)
>Fourth pass: Generate native code in linkable object file

Perhaps I'm dense, but...

Is the 'First Pass' (as defined by Soenke) the preprocessor?  Even if it
is, there's no great trick (seems to me) to preprocess, build a symbol
table and output unoptimized p-Code all in the first pass through the
source.  At that point, you've got p-Code (which is essentially an
internal data representation of the source) to optimize, translate into
assembler and assemble.  I would call this 1 pass for the following
reasons:

 o The source code is read ONCE only.
 o Take as many passes though the p-Code as you want; the p-Code is 
   (essentially) an internal representation of the partially compiled
   source.  Chomp on that N times, and you're still only playing with
   internal data--hence, you have a 1 pass compiler, not a N+1 pass
   compiler.
 o The assembly output is again only an internal representation.
   Assembling it is translating internal representation(s) into output.
   Not a separate pass.


-- 
Adam G.
adamg@microware.com, or ...!uunet!mcrware!adamg
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: hisgen@src.dec.com (Andy Hisgen)
Newsgroups: comp.compilers
Subject: Re: Large-space GC
Keywords: GC, storage, design
Date: 20 Aug 92 22:07:18 GMT
Reply-To: hisgen@src.dec.com (Andy Hisgen)
Organization: Compilers Central

In the 70's, someone at MIT, I believe Peter Bishop, did a PhD
dissertation on Garbage Collection in Very Large Address Spaces.  My
recollection is a little hazy, but persistent and long-lived storage was a
major issue.  I believe his work is closest to your suggestion of "Keep
summary info for a segment, where the summary info says what other
segments have pointers in to the segment and what other segments are
pointed to by the segment." (But don't take my word for it).

Andy Hisgen
hisgen@src.dec.com
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.lang.c
From: maniattb@cs.rpi.edu (Bill Maniatty)
Subject: Two-pass C compilers
Reply-To: maniattb@cs.rpi.edu (Bill Maniatty)
Organization: Compilers Central
Date: Sat, 15 Aug 1992 20:45:24 GMT
Keywords: C
Re: Why is compiled basic slower than C? (Basic is the future)

|> C requires more than one pass for compilation, and
|> therefore compiles slower than Basic.

	Some of the wise guys (I mean friends) in my office challenged my
assertion that C requires more than one pass to compile.  I'm of the
impression that C compilers use more than one pass.  Since they challenged
me, I get to make up the rules of this contest which are:
	1). Ansi 'C' is the grammar.
	2). If we skip optimization, is there any construct in C that would
	require multiple passes, and if not how do we avoid many passes?
	3). How about if we perform optimization (specify the optimizations
		please), can it be done in 1 pass?
	4). Are there any one pass C compilers out there. (That is C done with
		2+ pass compilers for purely historical reasons?)

If I was wrong, I apologize for misleading anyone, but if I'm correct then
in their face! :-)

Bill
-- 
maniattb@cs.rpi.edu - in real life Bill Maniatty
[Depends on what you mean by pass.  Most C compilers I know turn C into
assembler and only read the source once.  Whether you think of the
assembler as a second pass is a matter of semantics.  Some compilers, e.g.
Turbo C, go directly from C to object code, again only reading the source
once.  In this regard I can't see any way that C differs from Basic or
Fortran, both of which are about equally easy or hard to process in one
pass.  PL/I is a little harder to do in one pass since you're allowed to
declare variables after you use them.  -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: dbenn@leven.appcomp.utas.edu.au (David Benn)
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Reply-To: dbenn@leven.appcomp.utas.edu.au (David Benn)
Organization: University of Tasmania at Launceston
Date: Sat, 15 Aug 1992 03:00:47 GMT
Keywords: Basic, performance

In the discussion about BASIC compilers thus far, a recurring theme seems
to have emerged, namely the problem of managing BASIC's run-time dynamics.

I have been writing a compiler based loosely on AmigaBASIC - a Microsoft
derivative - for the best part of a year now, and have naturally had to
deal with these kind of issues. Re: strings memory allocation, I have
compromised. Strings in ACE have a default length of 1K. Small, I know.
However, the programmer can optionally declare a variable of any type
including strings. The only non-optional declarations are for arrays. With
strings, the programmer can specify smaller (say 100 bytes or less) or
larger strings (limited only by available memory). For many applications,
1K is ample. Indeed, 512 bytes is often enough, and I may yet reduce the
default to that. I know that many of you are thinking, "geez what a waste
of memory." I concede that it is not by any means optimal, but it does
avoid having to worry about garbage collection. More importantly, it works
quite well!

By the way, if you are interested, I hope to have ACE in the PD sometime
in the next few months. It has everything from simple BASIC stuff to
structures, pointers, turtle graphics, powerful sound and wave statements,
case...end case etc. 

Regards...
-- 
dbenn@leven.appcomp.utas.edu.au
David Benn - Applied Computing, University of Tasmania at Launceston.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: locks@cs.sun.ac.za (Graeme Lockley)
Newsgroups: comp.compilers
Subject: L-attribute grammars VS a more general class
Keywords: attribute, question
Date: 20 Aug 92 14:35:42 GMT
Reply-To: locks@cs.sun.ac.za (Graeme Lockley)
Organization: Compilers Central

This is a problem which has kept me thinking for a while now.

   The attribute grammar community can be roughly divided into two camps.
The first camp believe that L-attribute grammars are not only simple, but
are powerful enough to specify real programming languages. The second camp
refute this by expending a lot of resources towards building attribute
evaluators for the larger classes; pseudo-circular, non-circular, ordered
AG to name the most popular.

   My question is:
     Can languages that require identifiers be defined before use, be 
     specified more compactly and/or clearly using the larger than
     L-attribute grammars?

  Should this be the case, then most modern languages (don't take the term
`modern' too literaly) can be specified using L-attribute grammars. The
languages I have in mind being Modula-2, K&R C and ANSI C (granted, the
PIM definition of Modula-2 does not allow the FORWARD keyword, although
most of the Modula-2 compilers require the FORWARD definition if a
procedure is used before being defined).

   I don't want to start a language or attribute grammar war; I am
primarily intrested in the benefits of using a general class of attribute
grammar above L-attribute grammar for the languages in question. A REAL
example accompanying each response would be greatly appreciated.

   Please don't respond to the net but post to my e-mail address. Should
anybody request for a summary, I'll post.

Graeme Lockley
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.