From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: Better generator and iterator support in guile w.r.t. speed Date: Tue, 05 Mar 2013 17:57:36 +0100 Message-ID: <4559439.WT9qmlgVD5@warperdoze> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7Bit X-Trace: ger.gmane.org 1362502673 23297 80.91.229.3 (5 Mar 2013 16:57:53 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 5 Mar 2013 16:57:53 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Mar 05 17:58:15 2013 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UCvBu-0003HX-LI for guile-devel@m.gmane.org; Tue, 05 Mar 2013 17:58:14 +0100 Original-Received: from localhost ([::1]:51650 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UCvBY-00076H-W0 for guile-devel@m.gmane.org; Tue, 05 Mar 2013 11:57:52 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:56100) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UCvBR-00075V-JE for guile-devel@gnu.org; Tue, 05 Mar 2013 11:57:48 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UCvBP-00052X-TF for guile-devel@gnu.org; Tue, 05 Mar 2013 11:57:45 -0500 Original-Received: from mail-la0-x22d.google.com ([2a00:1450:4010:c03::22d]:46338) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UCvBP-00051r-LT for guile-devel@gnu.org; Tue, 05 Mar 2013 11:57:43 -0500 Original-Received: by mail-la0-f45.google.com with SMTP id er20so6463395lab.32 for ; Tue, 05 Mar 2013 08:57:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:from:to:subject:date:message-id:user-agent:mime-version :content-transfer-encoding:content-type; bh=MAL6FRMescUikc5gNN3rhTIqvaEwGqKKeGDNgob/JDA=; b=WGxnwlDqbW2y3vdFLAuQhD4coDfccAcd87rcWI/wFCNtsVZDUD8Qnz3AcFQ9sjnoJZ sgMF352WJvmnL9t+gBiVRtmLazUJeQQFOh7YyJkBSUwke4iG4q+nSFF5b5n2gOSEZ30v 3KHKL2h6/BT3funV86n35AhtM3ISdJFBMeOzhEWrxCR9gzAjJu+kZOPC9xB72bTWVEf8 iWBBZRz8pW43okNNmjoCvXcAcK5KEnGJToBat4A2WGl3MQfO3bRvLVKOxqe1ybPLnWV/ /AZdgA2lhDKXxSWK8l+ZtZ//8hkmf7t4k7VBVb63JAxY0EXM4C2/8x0xPKTmLGRsMvoC t/Dw== X-Received: by 10.152.113.164 with SMTP id iz4mr22158691lab.50.1362502662069; Tue, 05 Mar 2013 08:57:42 -0800 (PST) Original-Received: from warperdoze.localnet (1-1-1-39a.veo.vs.bostream.se. [82.182.254.46]) by mx.google.com with ESMTPS id l1sm8786130lbn.8.2013.03.05.08.57.39 (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 05 Mar 2013 08:57:40 -0800 (PST) User-Agent: KMail/4.9.4 (Linux/3.5.0-25-generic; KDE/4.9.4; x86_64; ; ) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:4010:c03::22d X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:15860 Archived-At: Hi guilers! Inspired by wingo's recent blogage on wingolog in combination with my portings of racket and cl loop frameworks, I did some thinking about generators. Especially inlining. 1. Can we make stubs like this inlinable (iterate (generator g (iterate (for x in l-i-s-t) (when (even? x) (yield (f x))))) (collect (+ (next g) (next g)))) A generator would be somthing like (define-syntax-rule (generator _thunk) (lambda () (let ((thunk (lambda () (_thunk) (finish)))) (call-with-prompt tag thunk (lambda (k . l) (set! thunk k) (apply values l)))))) (define-syntax-rules (yield x) (abort-to-prompt tag x)) With this kind of generator, as wingo says, we will get what we want but slowly. Might matter sometimes and not somtimes. What we would have liked here is some way of noticing that the liveness of "tag" is somewhat lexical and cannot be hidden in f. With that information a compiler would be able to inline code quite efficiently and make extensive use of gotos. How? Let's see how finish is working (define-syntax-parameter finish) (define-syntax-rule (iterate c ...) (syntax-parametrize ((finish (syntax-rules () ((_ x) (apport-to-prompt tag2 x))))) (call-with-prompt (lambda () loop code) (lambda _ final code)))) This whole setup would then be identified to something like (seqence loop: (with-frame g (generator thunk) code ...) finish: finish-code) To make the compilation to glil simple we mean by with-frame that we can setup a stack area where we can inline the thunk code and then a call to g like (next g) == (g) we can identify that 1. if (g) returns it will be from the abort clause in the prompt because the next part will jump to the finish part in the section which is below the generator frame and then it's possible to mark that stack space void. 2 The usage of the continuation is that we overwrite the same stack space with continuos versions of k's e.g. this is a characterizatin that we can keep the stack as a storage for this continuation. 3 with-frame is not recursive in g e.g. g is not visible inside thunk 4 So we should be able to make this work with intelligent usage of gotos. No, (f x) will be a problem because that we cannot know how much stack-space that function is needing. 5 What is interesting with the rtl format is that function applications are setuped at the end of the stack frame. This means that imersion of a generator is pretty simple using gotos and for rtl we would be able to manage quite general iterators and inline them with quite simple means. My conclusion is that for wip-rtl we should really start working on a prompt ideom that is lexical. But is it general enough. probably, but if you If you consider the main use case to be inlinable code, then you would need to consider the following tree-il extension (lexical-rec-prompts (name thunk abort-lam) ...) where name ... is visible inside the thunk's and abort's sections. Of cause not all versions of this code will be possible to manage without long-jumps and old pompt like features. (to note, CL's tagbody seams to be a very similar notion) Am I out in the blue or do you agree? Cheers Stefan.