From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Ian Price Newsgroups: gmane.lisp.guile.user Subject: Re: prompts: any example ? Date: Sat, 03 Mar 2012 08:08:08 +0000 Message-ID: <878vjiayzb.fsf@Kagami.home> References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1330762643 17672 80.91.229.3 (3 Mar 2012 08:17:23 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sat, 3 Mar 2012 08:17:23 +0000 (UTC) Cc: guile-user@gnu.org To: Catonano Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sat Mar 03 09:17:23 2012 Return-path: Envelope-to: guile-user@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 1S3k9a-0004l7-KD for guile-user@m.gmane.org; Sat, 03 Mar 2012 09:17:22 +0100 Original-Received: from localhost ([::1]:58125 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S3k9Z-0005iQ-MB for guile-user@m.gmane.org; Sat, 03 Mar 2012 03:17:21 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:39050) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S3k9U-0005iJ-HY for guile-user@gnu.org; Sat, 03 Mar 2012 03:17:18 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1S3k9R-0004lJ-Sl for guile-user@gnu.org; Sat, 03 Mar 2012 03:17:16 -0500 Original-Received: from mail-wi0-f169.google.com ([209.85.212.169]:64950) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1S3k9R-0004l1-GI for guile-user@gnu.org; Sat, 03 Mar 2012 03:17:13 -0500 Original-Received: by wibhi20 with SMTP id hi20so1392605wib.0 for ; Sat, 03 Mar 2012 00:17:11 -0800 (PST) Received-SPF: pass (google.com: domain of ianprice90@googlemail.com designates 10.180.80.40 as permitted sender) client-ip=10.180.80.40; Authentication-Results: mr.google.com; spf=pass (google.com: domain of ianprice90@googlemail.com designates 10.180.80.40 as permitted sender) smtp.mail=ianprice90@googlemail.com; dkim=pass header.i=ianprice90@googlemail.com Original-Received: from mr.google.com ([10.180.80.40]) by 10.180.80.40 with SMTP id o8mr2626580wix.10.1330762631082 (num_hops = 1); Sat, 03 Mar 2012 00:17:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type:content-transfer-encoding; bh=52bwz+XWMivohiGDDgixE/LJojcULexN+o/LTw7+GuA=; b=LSlyfk32Pg7sLNPqFokZkLBNhqxXlXivcHJKjl3OCswVm40XqXbdw03eJGhv6rdai9 f7rSEK++D+4+1VBn46lczeVJZ+JTgV5BOc0Q4OjK9BeDTs8+hXEngUzhv96nSNu57uil JrPNaAWBxS9e7d//HYLLWOf+cs/oJFi4R6v7MdlsPppRXcQa5MQPAn5lLHbnKyXNw0ln iks6Z44E3dnVZzBpIhkC71rcjaLfNACLqD1gX9e8aclImH4ruWehfJ/or5PvWpph5mBk KSPR7OZ6VrW6/UZUwPgNXa3SiEl7xMiVYL8EKR1orJFundoe3iv2mrr17gdy6JyK5txQ mDdg== Original-Received: by 10.180.80.40 with SMTP id o8mr2067946wix.10.1330762630905; Sat, 03 Mar 2012 00:17:10 -0800 (PST) Original-Received: from Kagami.home (host86-174-97-88.range86-174.btcentralplus.com. [86.174.97.88]) by mx.google.com with ESMTPS id v4sm23547697wiy.9.2012.03.03.00.17.07 (version=TLSv1/SSLv3 cipher=OTHER); Sat, 03 Mar 2012 00:17:09 -0800 (PST) In-Reply-To: (catonano@gmail.com's message of "Mon, 27 Feb 2012 22:32:07 +0100") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 209.85.212.169 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.user:9316 Archived-At: Catonano writes: > as in the subject > > I'm trying to get acquainted with this prompts thing. Can anyone indicate= an example of use to me that is particuraly meaningful or expressive ? What guile calls prompts and aborts, are generally found under the heading of 'delimited continuations'. These are primitive control operators that can be used to implement more complicated kinds of control, such as backtracking, exceptions, generators,etc. Generators tend to be a good starting point, as they have proven themselves to be very useful in practice, and many programmers are familiar with them. So we will take that as our example. Say we want to be able to write a generator for the natural numbers, then in python the way we would write this is >>> def naturals(): ... x =3D 0 ... while True: ... yield x ... x +=3D 1 ...=20 >>> gen =3D naturals() >>> gen >>> next(gen) 0 >>> next(gen) 1 >>> next(gen) 2 >>> next(gen) 3 and so on. We might like to write something similar in scheme (only without mixing up generators and functions like python does :P ). Our hypothetical ideal syntax will be (define naturals (generator (let loop ((x 0)) (yield x) (loop (1+ x))))) but for now, we'll go for the more modest (make-generator (lambda (yield) ...)) and leave the syntactic sugar for later. So, we need to write a function make-generator, of one argument (a procedure taking a yield procedure), that returns a generator object. When we call 'next' on this generator object, it will run the procedure until it either comes to a 'yield' or it finishes normally. When it comes to a yield, it isn't enough to just stop the computation, as we need to be able to continue it again when we want more values. This suggests we need a "continuable abort". Which is what the procedure 'abort-to-prompt' provides. We also need to be specify where to abort to (i.e. the place where next was called), which is what 'call-with-prompt' gives us. So our first draft version of a generator becomes. ;; make-generator calls proc with a procedure that aborts the generator ;; continuably with the specified value=20 (define (make-generator proc) (lambda () ;; we don't want generator to start immediately (proc (lambda (escape-val) ;; prompts are tagged so we know which kind of prompt we are ;; aborting to (abort-to-prompt 'generator-prompt escape-val))))) (define (next generator) (call-with-prompt 'generator-prompt (lambda () ;; run generator (generator)) (lambda (resume val) ;; just return val val))) but hang on, we don't have a way to associate resume procedure with the gen= erator. To do this, we create a generator object, with a mutable resume field. Which next will update when the generator returns. (import (rnrs records syntactic)) ; my preferred record macro YMMV (define-record-type (generator make-raw-generator generator?) (fields (mutable next))) now we update our 'make-generator' and 'next-generator' procedures to take into account these generator objects. (define (make-generator proc) (make-raw-generator (lambda () (proc (lambda (escape-val) (abort-to-prompt 'generator-prompt escape-val)))))) (define (next generator) (call-with-prompt 'generator-prompt (lambda () (let ((next (generator-next generator))) (next))) (lambda (resume val) (generator-next-set! generator resume) val))) Now we can define our natural number generator. (define naturals (make-generator (lambda (yield) (let loop ((i 0)) (yield i) (loop (1+ i)))))) and test it out scheme@(guile=E2=88=92user)> naturals $8 =3D # scheme@(guile=E2=88=92user)> (next naturals) $9 =3D 0 scheme@(guile=E2=88=92user)> (next naturals) $10 =3D 1 scheme@(guile=E2=88=92user)> (next naturals) $11 =3D 2 scheme@(guile=E2=88=92user)> (next naturals) $12 =3D 3 This generator implementation can be improved still further. Currently, it behaves strangely if the procedure terminates (define bug-gen (make-generator (lambda (yield) (yield 'first) (yield 'second) (yield 'third) 'final))) scheme@(guile=E2=88=92user)> (next bug-gen) $17 =3D first scheme@(guile=E2=88=92user)> (next bug-gen) $18 =3D second scheme@(guile=E2=88=92user)> (next bug-gen) $19 =3D third scheme@(guile=E2=88=92user)> (next bug-gen) $20 =3D final scheme@(guile=E2=88=92user)> (next bug-gen) $21 =3D final scheme@(guile=E2=88=92user)> (next bug-gen) $22 =3D final we'd like it to return an end-of-generator object in this case, so we don't keep doing redundant computation. (define-record-type end-of-generator) So, if the generator returns normally, i.e. it doesn't abort, then we modify the generator to indicate it is finished. And we take this into account in 'next'. (define-record-type (generator make-raw-generator generator?) (fields (mutable finished?) (mutable next))) (define (make-generator proc) (make-raw-generator #f (lambda () (proc (lambda (escape-val) (abort-to-prompt 'generator-prompt escape-val)))))) (define (next generator) (if (generator-finished? generator) (make-end-of-generator) (call-with-prompt 'generator-prompt (lambda () (let ((next (generator-next generator))) (call-with-values next (lambda args (generator-finished?-set! generator #t) (apply values args))))) (lambda (resume val) (generator-next-set! generator resume) val)))) Now we don't do extra work when the generator is finished scheme@(guile=E2=88=92user)> (define bug-gen (make-generator (lambda (yield) (yield 'first) (yield 'second) (yield 'third) 'final))) scheme@(guile=E2=88=92user)> (next bug-gen) $32 =3D first scheme@(guile=E2=88=92user)> (next bug-gen) $33 =3D second scheme@(guile=E2=88=92user)> (next bug-gen) $34 =3D third scheme@(guile=E2=88=92user)> (next bug-gen) $35 =3D final scheme@(guile=E2=88=92user)> (next bug-gen) $36 =3D # scheme@(guile=E2=88=92user)> (next bug-gen) $37 =3D # Finally, some syntactic sugar instead of using make-generator (define-syntax-parameter yield (lambda (stx) (syntax-violation 'yield "yield used outside of a generator form" stx))) (define-syntax-rule (generator body rest ...) (make-generator (lambda (yield*) (syntax-parameterize ((yield (syntax-rules () ((yield val) (yield* val))))) body rest ...)))) Now, we can just write (define naturals (generator (let loop ((x 0)) (yield x) (loop (1+ x))))) instead of (define naturals (make-generator (lambda (yield) (let loop ((x 0)) (yield x) (loop (1+ x)))))) Some conclusions =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Firstly, I apologise for the style, this was, with minor editing, how it came to mind. Second, perhaps this should be packaged up so that I don't keep reinventing it every time someone wants an example of continuations in practice. And thirdly, below are some gists for other examples including (sigh) a previously written generator example (though it uses shift/reset). I hope this has been useful. Defining your own control structures is something you will need to, and probably should do, only rarely. You'll generally know when that is since you will be trying to do something crazy, or having to write in a convoluted programming style. https://gist.github.com/1548531 - monadic reflection https://gist.github.com/1381107 - continuations for web programming https://gist.github.com/1381091 - simple generators. --=20 Ian Price "Programming is like pinball. The reward for doing it well is the opportunity to do it again" - from "The Wizardy Compiled"