From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: Re: Background info abot the unfyication tool Date: Fri, 21 May 2010 12:50:59 +0200 Message-ID: References: <201005181942.01466.stefan.tampe@spray.se> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1274441876 27313 80.91.229.12 (21 May 2010 11:37:56 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 21 May 2010 11:37:56 +0000 (UTC) Cc: guile-devel@gnu.org To: stefan Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri May 21 13:37:55 2010 connect(): No such file or directory Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1OFQY6-0005kT-Gv for guile-devel@m.gmane.org; Fri, 21 May 2010 13:37:54 +0200 Original-Received: from localhost ([127.0.0.1]:52117 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OFQY5-0007km-PU for guile-devel@m.gmane.org; Fri, 21 May 2010 07:37:53 -0400 Original-Received: from [140.186.70.92] (port=55943 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OFQXy-0007hK-Re for guile-devel@gnu.org; Fri, 21 May 2010 07:37:49 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OFQXp-0001Jk-MO for guile-devel@gnu.org; Fri, 21 May 2010 07:37:45 -0400 Original-Received: from a-pb-sasl-quonix.pobox.com ([208.72.237.25]:54704 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1OFQXo-0001Jb-RI for guile-devel@gnu.org; Fri, 21 May 2010 07:37:37 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 67845B5A30; Fri, 21 May 2010 07:37:36 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; s=sasl; bh=j44uFysLodu0DTleF66zQDeu2LA=; b=rUfz36 5wdP8kS4fIYlLPnEk1qyzlZJMgsFnAM2sc8JAq1pfaQcshObbmcjG2bY89/QRF2F pK5aej4YKlNC2shOG9x+gR6eC+Xy2YfK6C6mfxg+aELxuz/Zlhl6ySks53yEqmKk 8hwNcMcfdOpDDKhnWkxNxB3X1GQUnjrYoLDvo= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type; q=dns; s=sasl; b=noKoqacAuafFy7EC2jRpp198PMEANifO P05h4nRDmE9dGBj1BSiheDNtl8R28EB4J1vomabV/PHitDrxOfDo5RZ4kzLy2xM2 Zd7FMxMOTmWmb0yio2ITQORyMkHKz2SmSii4iMHn7XZzJR8t68JPVjE1kKwoO+ug EtwI0vuzQFo= Original-Received: from a-pb-sasl-quonix. (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 542EDB5A2F; Fri, 21 May 2010 07:37:35 -0400 (EDT) Original-Received: from unquote (unknown [81.39.169.91]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTPSA id 55872B5A2E; Fri, 21 May 2010 07:37:32 -0400 (EDT) In-Reply-To: <201005181942.01466.stefan.tampe@spray.se> (stefan's message of "Tue, 18 May 2010 19:42:01 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.92 (gnu/linux) X-Pobox-Relay-ID: 403BFC9C-64CD-11DF-B122-D033EE7EF46B-02397024!a-pb-sasl-quonix.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:10338 Archived-At: Hi Stefan, Thanks for this writeup, it was very interesting. I don't come from the logic programming world, so it was great to hear your thoughts and see your code. It's clear that you've thought a lot about these problems :) It's very cool that you were able to come in an hack up performant solutions. Rock on! Though, with my maintainer hat on, I have to be a bit more cautious :) The set of instructions in Guile's VM has been chosen to be appropriate to Guile's flavor of Scheme, and for Elisp. We could add prolog-type instructions, yes -- but I would like to avoid it if I can :-) As you know, the speed of an algorithm depends first of all on how much it conses, and secondly on the number of instructions that it executes. So with these considerations in mind, and with the caveat of my ignorance of logic programming, let's consider your examples :) On Tue 18 May 2010 19:42, stefan writes: > Backtracking. Guile supports backtracking natively, using escape-only prompts. So in your example, having used (ice-9 control): > > (let ((X (var!)) > (Y (var!)) > (L (var!))) (let ((frame-nr (make-prompt-tag))) (% (if ( Q [K a Y L]) ... (abort frame-nr)) (lambda (unused-cont) (if ( Q [X Y]) ... ...)))))) Also do you need to actually make variables at runtime? Might binding them to fresh values or whatever be done at expansion time, and expanded into the source? > so, variables are allocated on a stack On Guile's stack, yes. > and when new bindings is done the old values is saved on an > undo-array. If you need to produce side effects to undo something, use dynamic-wind; if you just need dynamic scoping, e.g. for detecting cycles, use with-fluids; and if you don't need to produce effects, the lexical scoping combined with the abort should serve your purposes. > 3. REF - need to quickly tell if the data is a reference to another > object!! Interesting. This reminds me of kanren; have you seen it? Perhaps that is an ignorant reference, though. > The cool thing though is that we can fix this, > basically we mark all arrows (-> a b) that has been visited via a special > hashmap kind of datastructure Use with-fluids for that hashmap, if it can be implemented functionally. This would cons, though. It is true that currently scheme-only solutions will be slower than yours, though I suspect that your previous numbers were based on some implementation misunderstandings. For example, pmatch from (system base pmatch) is a straightforward matcher that generates all-inlined code (without closures, I mean). Check the compilation output of (lambda (x) (pmatch x ((a _) 'a) (b c) 'b)), for example. Granted you can see from that output that we don't inline (in the copy-propagation sense) as much as we should, and our basic block ordering is really suboptimal -- but I'd like to focus on those more general algorithms so that all of Guile will benefit, and eventually we produce nice tight code. Let us know how it goes with prompt and abort :) I don't have a link on hand, but a few months ago I wrote about prompt and abort on my web log, with links to papers. Cheers, A -- http://wingolog.org/