HDTenEightyP/NetNews huggingface dataset:
From: mw@ki.fht-mannheim.de (Marc Wachowitz)
Newsgroups: comp.compilers
Subject: Re: Adding garbage collection to C++
Keywords: C, GC
Date: 13 Aug 92 11:40:23 GMT
Reply-To: mw@ki.fht-mannheim.de (Marc Wachowitz)
Organization: Fachhochschule fuer Technik Mannheim

Thomas M. Breuel <tmb@arolla.idiap.ch> wrote:
: As far as I can tell, ANSI-C and C++ are both fully garbage collectable
: within the current language standard.

At least you would have to be very careful when the programmer copies the
value of the last pointer to some heap object to some memory region (e.g.
an unsigned char[]) and changes the order of the array elements, then
destroys the pointer.  No more live reference is detectable by the
collector, but the programmer may copy back the pointer value (again
changing the byte order) and ... :-) I guess such manipulations would be
possible with the current standard.

: More precisely, I believe that you could compile ANSI-C to portable and
: idiomatic CommonLisp (the main difficulty is pointers to automatic
: variables).

I'm not sure whether C would allow changing addresses; if not, you'd have
to translate them into something else if your Lisp implementation uses a
moving collector, which is quite likely. This is surely possible, but
hardly very efficient - so why not use Lisp in the first place, with
better performance :-)
--
Marc Wachowitz
mw@gandalf.ki.fht-mannheim.de, 75742@novell1.rz.fht-mannheim.de
[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.  This sort of thing
makes it hard to find all the live data. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: kumar@ra.csc.ti.com (Sundeep Kumar)
Newsgroups: comp.compilers
Subject: Generating LALR(1) Grammar from an arbitrary CFG.
Keywords: LALR, theory, question
Date: 20 Aug 92 03:35:01 GMT
Reply-To: kumar@ra.csc.ti.com (Sundeep Kumar)
Organization: Compilers Central

Is there a utility that accepts an abitrary CFG and either gives an
equivalent LALR(1) grammar or decides that the CFG has no equivalent
LALR(1) grammar ? Is this problem in general, solvable ?

--sundeep Kumar
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: John R. Levine <compilers-request@iecc.cambridge.ma.us>
Subject: comp.compilers now available by e-mail from LISTSERV
Reply-To: John R. Levine <compilers-request@iecc.cambridge.ma.us>
Organization: Compilers Central
Date: Thu, 13 Aug 1992 03:01:23 GMT
Keywords: administrivia

Jim McIntosh at the American University has kindly setup a LISTSERV
gateway to comp.compilers called COMPIL-L.  This lets people who don't get
usenet receive the newsgroup via electronic mail.  All articles posted to
comp.compilers are mailed to the mailing list when they arrive at A.U.,
usually a few minutes after I post them.  Any mail sent to COMPIL-L will
be forwarded here for moderation just like any other incoming compilers
message.

To subscribe a person should send e-mail to listserv@american.edu with one
line in the mail message (not in the subject!)  That line should read:

                        SUBSCRIBE COMPIL-L full_name
for example:
                        SUBSCRIBE COMPIL-L Ima Hacker

To get off the list the subscriber should send e-mail to the same address
with the message:       SIGNOFF COMPIL-L

If you have problems getting on or off the list, please contact me, not
Jim.  In particular, if you want to add or delete a mail alias other than
your own personal mail address, you have to ask me to do it.

Regards,
John Levine, comp.compilers moderator
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Subject: Re: Adding garbage collection to C++
Reply-To: tmb@arolla.idiap.ch (Thomas M. Breuel)
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)
Date: Tue, 18 Aug 1992 17:18:07 GMT
Keywords: GC, parallel

In article <92-08-093@comp.compilers> tmb@idiap.ch writes:

   You don't need a language extension, nor do you need "garbage
   collection only [to] happen if [you] specifically ask for it". Simply
   retain a pointer to the object in the address space of A. In fact, you
   can encapsulate this behavior nicely inside your "send" procedure.

The moderator replies:

   [So how do you ever collect storage that's ever been shared between two
   threads?  In fairness, this isn't unique to C -- it'd be a problem in any
   situation where you have a shared heap with unshared pointers. -John]

That's less a language problem and more a "political" problem.

In the threaded case (lightweight) processes, there is generally no
problem (except for the implementor), since the GC knows about threads
(examples are Lucid CommonLisp and Parc's PCR).

In the shared memory case, a GC (in particular, a conservative GC) will be
happy to scan the stack/heap of the other process for potential references
to its own data. It helps, of course, if the valid addresses in each
process' address space are non-overlapping...

If processes can't easily examine each other's memory, in particular, if
there is a slow network connection between the two processes, you may want
to use other kinds of mechanism. For example, when process 1 sends a
reference to an object in process 1's address space to process 2, process
1 may promise to keep that data alive until process 2 tells process 1 that
it's OK to get rid of it. To automate reclamation inside process 2,
process 2 can put the reference to the object in process 1 into an object
with some GC finalization procedure; the finalization procedure informs
process 1 that the object is no longer needed.

This kind of protocol is actually already used routinely. For example,
X resources held by languages with garbage collection are often freed
explicitly by GC finalization.

This may sound as if the presence of GC complicates threading, shared
memory, or network communications. I think that impression is false.

As I said in my posting quoted above, you can always and trivially disable
GC for some object by holding on to a pointer to it; this gets you back to
the non-GC case. But if you do have GC in your language, it turns out that
you have a variety of mechanisms (some of which are given above) at your
disposal to make it work even across process and network mechanisms, which
I find is a plus, not a minus.

					Thomas.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: scott@bbx.basis.com (Scott Amspoker)
Newsgroups: comp.compilers
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Keywords: Basic, performance
Date: 13 Aug 92 15:41:07 GMT
Reply-To: scott@bbx.basis.com (Scott Amspoker)
Organization: BASIS International, Ltd., Albuquerque NM USA

jch@rdg.dec.com (John Haxby) writes:
>Glenn_Johansson@f313.n203.z2.fidonet.cd.chalmers.se writes:
>|> [How much slower is compiled Basic than C, and why?]
>
>There has been a lot of work put into optimizing C compilers: the efforts
>of FSF, Sun and MIPSCO to mention but three.  There hasn't been a great
>deal of work put into optimizing BASIC compilers, at least not that I know
>of.
>
>There seems to be a more general problem though: compilers of high-level
>languages tends to produce optimal machine code, whereas compilers of
>low-level languages tend to produce sub-optimal machine code.

We market a business-oriented BASIC-style language called BBx.  It is
interpreted.  Although it is quite different from Microsoft BASIC there
are still common qualities of any BASIC dialect.

A few years ago there was some discussion about producing a compiler for
it.  We found several reasons why a compiler would not be a great idea.
The main reason is that the runtime dynamics of BASIC don't translate well
to a compiled environment.  The most important aspects are dynamic
string/array management and dynamic flow control involving error/exception
handling.  The latter is especially hard to optimize.

A C programmer tends to approach these things with a more "static" frame
of mind resorting to a dynamic model only if it is really necessary (and
knowing there will be a performance hit).  Furthermore, BASIC normally
performs lots of runtime checks such as array subscripts and ranges.
Granted, a BASIC compiler could allow the option of turning these checks
off but I'm assuming a proper semantical translation.

Since our product is used primarily for business data processing
applications which spend most of their time performing file and user i/o,
the need for a compiler isn't as critical.  Indeed we have been known to
beat some compiled languages in file-oriented benchmarks.

I just don't think interpreted languages compile well.  If they do then
they really aren't exploiting the special strengths of interpretation.
You end up with the worst of both worlds.
-- 
Scott Amspoker
Basis International, Albuquerque, NM
scott@bbx.basis.com
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: John R. Levine <compilers-request@iecc.cambridge.ma.us>
Subject: Should I post help wanted messages?
Reply-To: John R. Levine <compilers-request@iecc.cambridge.ma.us>
Organization: Compilers Central
Date: Sat, 15 Aug 1992 00:16:23 GMT
Keywords: administrivia, question

Over the years, I have never posted "help wanted" or "position available"
messages in comp.compilers on the theory that there is a perfectly good
group, misc.jobs.offered, intended for them.

I've been getting more such messages than I used to, one or two per week,
so I wonder whether I should reconsider my policy.  As an alternative, I
might post one digest message per week containing the help wanted messages
that arrived during the week.  Would people prefer this?  Send me a note
and let me know.  If I don't get a lot of support for change, I'll leave
things as they are.

Regards,
John Levine, johnl@iecc.cambridge.ma.us, {spdcc|ima|world}!iecc!johnl

PS: I have no sympathy at all for the theory advanced by some people that
they don't want to use misc.jobs.offered because anyone who reads it must
be a total loser.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: masayosh@eclipse.cs.Colorado.EDU (Masayoshi Ishikawa)
Subject: Re: Eli compiler construction system - version 3.3.1
Reply-To: masayosh@eclipse.cs.Colorado.EDU (Masayoshi Ishikawa)
Organization: University of Colorado at Boulder
Date: Fri, 21 Aug 1992 00:09:12 GMT
Keywords: tools, FTP

> Version 3.3.1 of the Eli compiler construction system is now available
> either on magnetic tape or via anonymous ftp (ftp.cs.colorado.edu,
> 128.138.243.151, pub/cs/distribs/eli).  ...

Patch files to run Eli compiler construction system version 3.3.2 on
NeXT NS2.1 is also available via anonymous ftp (ftp.cs.colorado.edu,
128.138.243.151, pub/cs/distribs/eli/NeXT).
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
Newsgroups: comp.compilers
Subject: Re: A Non-LALR(1) Parser Generator
Keywords: LR(1)
Date: 20 Aug 92 07:03:13 GMT
Reply-To: bromage@mullauna.cs.mu.OZ.AU (Andrew Bromage)
Organization: Computer Science, University of Melbourne, Australia

ejy@hrmsc.att.com (Eugene Yurek) writes:

>Charlie Wetherell originally wrote LR along with Shannon for some
>government entity they were either employed for or were working on a
>contract for, so, consequently, the entire source is in the public domain.

Does anybody know if LR is sitting on a server somewhere?

>This generator is not easy to use compared to YACC.  You cannot provide
>semantic actions within the grammar.  They must be handled in a separate
>source file, and manually tied back to the productions in the BNF (yuk!!).
>Basically, I'm saying that LR works well, however, its not that easy to
>use (though this is a subjective observation on my part). And as I said
>above, you're going to need a Fortran compiler, and some patience to use
>it.  It is, however, the only LR(1) parser generator that I've ever come
>across (please, no flames!!!).

Even if it is useless from practical point of view, it would be very
interesting to have a look at the source code. Apparently, also, LR had
excellent output options, since the emphasis, I think, was to accept a
very large class of grammars. Because of this, you could get from LR just
about any diagnostic about your grammar that you could ever hope for.

Since my original article, I have been told this description of the first
of Pager's algorithms:

	"Two items with the same lookahead symbol and different
	cores should not be put together in a merged state unless
	there are already two items in one of the states with those
	cores and a common lookahead."

If anybody can make head or tail of this description, they're welcome to
it.

His second algorithm ("strong compatibility") will merge _all_ item sets
which can be merged without introducing a shift-reduce conflict into the
parser, but is apparently computationally expensive. So here's a challenge
for programmers out there: write a parser generator, which has the same
conflict resolving capabilities as YACC, but will parse LR(1) grammars. By
the way, parsers created must be of a reasonable size - i.e. some item set
merging must take place.

While I'm on the subject of parser generators, I heard about an LALR
parser generator written in Sasl the other day. Does anybody know about
this?  

Also, have any other parser generators ever been written for LR(1)
grammars (or any other superset of LALR(1) grammars for that matter)?  I
know about some algorithms for parsing all context-free grammars, but they
are all either parallel or run in cubic time...

bromage@mullauna.cs.mu.oz.au
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: buehlman@iwf.mabp.ethz.ch (Buehlmann Thomas)
Newsgroups: comp.compilers
Subject: Re: constant folding at parse time
Keywords: parse, attribute
Date: 21 Aug 92 11:51:46 GMT
Article-I.D.: comp.92-08-134
Reply-To: buehlman@iwf.mabp.ethz.ch (Buehlmann Thomas)
Organization: Swiss Federal Institute of Technology (ETH), Zurich, CH

twpierce@amhux1.amherst.EDU (Tim Pierce) writes:

>The discussion about constant folding has intrigued me a little bit, and
>I've been a little stumped figuring out how I would implement this in the
>general case.  Writing code into mknode() to fold the addition or
>multiplication of two nodes with constant value makes sense to me, for
>example.  But what about an expression such as "4 + y + 4"?  As I see it,
>a shift-reduce parser following the rule

>expr -> expr + expr
>      | CONST
>      | ID

Watch out, this optimization may be inherently unsafe since you change the
semantical meaning between the optimized version and the non-optimized
version in such a way that different results may be produced. Just two
short examples:

1) x/12 * 12
You may reduce this to x, but what happens, if x is not divisible by 12?
In this case you obviously got a clash between the mathematical meaning of
the expression and the 'procedural' meaning the programmer wanted to
achieve.

2) assume the maximal size of int be 16!
12 + x + 5
depending on x and the implementation you might get different results,
maybe even the compiler complains while folding the constants. However the
writer might have known that x is always strictly less than -1!
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: nickh@CS.CMU.EDU (Nick Haines)
Subject: TDF (ANDF) information
Reply-To: nickh@CS.CMU.EDU (Nick Haines)
Organization: School of Computer Science, Carnegie Mellon University
Date: Tue, 18 Aug 1992 22:47:11 GMT
Originator: nickh@VOILA.VENARI.CS.CMU.EDU
Keywords: UNCOL

After the last time TDF (the OSF's chosen ANDF) was discussed here, I dug
out an old email contact address and sent off for the newer information
pack. This comes as 3 (soon to be 4) documents:

- TDF Specification (56pp)
- TDF Facts and Figures (9pp, gives comparative benchmarks)
- TDF and portability (14pp)
- Introductory Guide to TDF (available soon)

You too can be the proud owner of this stuff by contacting:

	Dr Nic E Peeling
	Defence Research Agency
	RSRE
	St Andrews Road
	Great Malvern
	Worcestershire
	U.K.
	WR14 3PS

	Tel: +44 684 895314
	Fax: +44 684 894303
	Internet: peeling%hermes.mod.uk@relay.mod.uk
	Janet: peeling@uk.mod.hermes

TDF is an Architecture Neutral Distribution Format (ANDF). It's similar to
a machine-independent intermediate representation in a compiler. The idea
is that software vendors can sell a single shrink-wrapped ANDF version
(made by a `producer', similar to a compiler front-end) of their stuff and
anyone with an ANDF `installer' (back end) on their machine can buy it and
run it. It's a bit like UNCOL in the breadth of its aims but seems to
actually work....

Only a subset of TDF was chosen by the OSF for its ANDF. This subset is
sufficient for ANSI C, but TDF as a whole was designed to support (at
least) FORTRAN, COBOL, C++, Ada, ML, and LISP also.

DRAE have the following TDF items:

- ANSI C producer
- MIPS, VAX, i386, SPARC, and 68k installers
- ANDF to ANDF optimizer
- ANDF pretty-printer.
- ANDF linker

They are working on these items:

- C++ producer
- Transputer installer
- extensions to TDF to support parallelism

and you can be sure that producers for other languages are in the works
(through collaboration with other bodies, to make an informed guess).

From "TDF Facts and Figures" (which gives runtime/compile-time/ filesize
benchmarks comparing TDF compilers with other compilers) I've distilled
these runtime benchmarks. On these machines:

Platform	OS		Native Compiler

VAXStation 3100	Ultrix 4.2	GCC 1.37.1
DECStation 5100 Ultrix 4.1	CC -O2 and CC -O3
Dell 486	SCO UNIX	GCC 1.37.1 -O
SPARCStation 2	SunOS 4.1.1	CC -O3
HP 9000/425T	HP-UX 7.05	CC -O

they got these runtime results for these parts of SPEC (values greater
than 1 show TDF better than native compiler):

	eqntott	espresso gcc	xlisp

VAX	1.02	0.98	 0.90	1.03
MIPS	0.99	0.95	 1.01	0.95
MIPS*	0.91	0.91	 	0.98
486	1.01	1.02	 0.90	1.08
SPARC	1.15	1.00	 0.81	0.97
68k	1.29	0.83	 0.90	0.90

(* the -O3 level on CC does multi-file optimizations. The corresponding
level of optimization (tcc -M) was used for the TDF compiler in this
instance but not in any of the other tests. The gcc benchmark does not run
correctly with CC -O3, so this was omitted).

Nick Haines nickh@cs.cmu.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: pdg@crosfield.co.uk (paul goffin)
Newsgroups: comp.compilers
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Keywords: Basic, C, performance
Date: 19 Aug 92 12:57:28 GMT
Reply-To: pdg@crosfield.co.uk (paul goffin)
Organization: Crosfield Electronics, Hemel Hempstead, United Kingdom.

Glenn_Johansson@f313.n203.z2.fidonet.cd.chalmers.se writes:
>1. How much slower is compiled modern basic than compiled modern C?

Are you sure it is?

>2. Why is the basic compilers creating a slower product than the C
>compilers?
[stuff deleted]
>   e. Other (?)

Because C is pretty trendy at the moment and so most of the effort in
improving compilers is going into C.  Compiled BASIC has never been very
trendy.

I've usually found a good FORTRAN compiler to be better than any C
compiler.  That's not because FORTRAN is 'better' than C, it's just
because a lot of people were once interested in making FORTRAN programs
run very fast, so they spent the money to sort the compilers out.

Paul
-- 
+ Paul Goffin +  Crosfield Electronics Ltd. U.K.  +44 442 230000x3357 +
[Fortran is easier to optimize than C, mostly because it doesn't allow a lot
of the aliasing possible in C. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: bromage@mullauna.cs.mu.oz.au (Andrew Bromage)
Newsgroups: comp.compilers
Subject: Re: A Non-LALR(1) Parser Generator
Keywords: parse, bibliography
Date: 17 Aug 92 01:04:02 GMT
Reply-To: bromage@mullauna.cs.mu.oz.au (Andrew Bromage)
Organization: Computer Science, University of Melbourne, Australia

dan%npt1@uunet.UU.NET (Dan White) writes:
>   Do you know of any parser generators that will generate parsers for
>languages that are not LALR(1)? Specifically, I want to generate a parser
>for a language called CMS-2.

D Pager has produced a few algorithms which may be of some use. They are
designed to handle LR(1) grammars (a proper superset of LALR(1)), but
produce parsers of realistic size. He does this by merging sets (as in the
standard LALR construction algorithm), but using a different criterion
than equality of cores.

The references are:
Pager, "A practical general method for constructing LR(k) parsers", Acta
Informatica, 7, pp 249-268, 1977.

Pager, "The lane tracing algorithm for constructing LR(k) parsers",
Information Science, 12, pp 19-42, 1977.

The first (ie simpler) algorithm was used in a parser compiler called
"LR", the availability of which I know nothing about.

It was reviewed in:
Wetherell and Shannon, "LR - automatic parser generator and LR(1) parser",
IEEE Transactions on Software Engineering, SE-7, pp 274-278, 1981.

>[A common approach is to twist the syntax around until it's LALR, either by
>accepting a superset of the legal language and throwing out the bad cases
>semantically, or else by using lexical feedback kludges to guide the parser,
>typically by passing up special tokens from the lexer. -John]

This is a really bad hack, and should be avoided. I know it's common
practice, but I don't believe that it's particularly marvellous.

A nice approach was used in Gofer, where operator precedences are
redefinable from the source. The way this was fixed was to store
expressions as a linked list and writing another parser to handle these
expressions. It's a bit like the LL and operator precedence parsers of
yesteryear. I think that the moral of the story is to only use other
techniques when the LR approach genuinely fails, and not before.

bromage@mullauna.cs.mu.oz.au
-- 
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