Path: ...!3.eu.feeder.erje.net!feeder.erje.net!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.prolog
Subject: Re: How Scryer Prolog became the disgrace of Computer Science (Was:
 Is Scryer Prologs failure measurable?)
Date: Tue, 13 Aug 2024 15:49:32 +0200
Message-ID: <v9fo9b$166p1$2@solani.org>
References: <v8gc6e$l44p$1@solani.org> <v952rb$10h3e$1@solani.org>
 <v9fo70$166p1$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 13 Aug 2024 13:49:31 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="1252129"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
Cancel-Lock: sha1:YHG+7zRkaXtAatJ0OCgm7MSUu7c=
In-Reply-To: <v9fo70$166p1$1@solani.org>
X-User-ID: eJwFwYEBwCAIA7CXUGid5wCV/09YAudinyAYGIwvv1UoyU0JVmpa+8UR77eN5jItJttj74+PPXW7B3jT+QNoyxZ3
Bytes: 2613
Lines: 43

The time complexity of a look ahead
parser with one word token look ahead and
one character look ahead, and Prolog code

that is optimized towards clauses that
use first argument indexing, you can view
it as a kind of table driven parser with

push down, althought its Prolog, should be only
O(N+M), where N=number of characters and M=number of
words. It has linear complexity and not

something else. In 1965 Donald Knuth proposed
LR(k) parser, which are bottom up, but the idea
here is LL(k) parser, which are top down.

Both parsing algorithms run in linear time.

Mild Shock schrieb:
> I can make a case of such a comparison,
> DCG pipe dream versus proper look-ahead:
> 
> /* Scryer Prolog 0.9.4-135 */
> ?- time((between(1,1000,_), data(X), json_chars(Y,X,[]), fail; true)).
>     % CPU time: 0.283s, 2_506_022 inferences
>     true.
> 
> /* SWI-Prolog 9.3.8 */
> ?- time((between(1,1000,_), data(X), atom_json_term(X,Y,[]), fail; true)).
> % 44,998 inferences, 0.016 CPU in 0.006 seconds (281% CPU, 2879872 Lips)
> true.
> 
> I think the speed difference of a factor
> 20x is not because of native float parsing.
> The example doesn’t have much float:
> 
> data("{                                   \"a\":123 }").
> 
> So whats the bug in the DCG parser by
> Scryer Prolog? Why does the parser written by
> Jan W. not have the same defect?
> 
> Why does the number of inferences differ so much?