Path: utzoo!attcan!uunet!lll-winken!ames!ig!bionet!agate!ucbvax!decwrl!labrea!russell!pereira
From: pereira@russell.STANFORD.EDU (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Inline expansion versus threaded code
Summary: additional details
Keywords: paging threaded code
Message-ID: <8544@russell.STANFORD.EDU>
Date: 16 Apr 89 05:09:15 GMT
References: <1635@kulcs.kulcs.uucp> <8489@russell.STANFORD.EDU> <1399@murtoa.cs.mu.oz.au>
Sender: pereira@russell.Stanford.EDU (Fernando Pereira)
Reply-To: pereira@russell.UUCP (Fernando Pereira)
Organization: Center for the Study of Language and Information, Stanford U.
Lines: 21

A few additional details prompted by Lee's comments.

My figures for native vs. threaded code came from comparing Quintus
Prolog with two commercial native code compilers for Prolog two years
ago, and from discussions with Richard O'Keefe about Prolog
compilation. Native code compilation techniques may have improved
since then.

The problem of access to rules is more complicated in parsers that
do not use the rules directly but instead use some kind of parsing
tables derived from the rules. Usually, the tables are much larger
than the original rule set.

The question of whether parallelism will be useful for parsing is also
rather tricky. To ensure termination and avoid an exponential
proliferation of analyses, most parsers these days use dynamic
programming techniques to merge parsing configurations. As a
consequence, parsing alternatives are no longer independent, leading
to subtle synchronization problems in parallel systems. Sigh...

-- Fernando Pereira