Path: nntp.gmd.de!news.ruhr-uni-bochum.de!news-koe1.dfn.de!news-fra1.dfn.de!news-kar1.dfn.de!newsfeed.nacamar.de!news-peer.sprintlink.net!news.sprintlink.net!Sprint!cpk-news-hub1.bbnplanet.com!news.bbnplanet.com!nntp2.dejanews.com!nnrp2.dejanews.com!not-for-mail From: oleg@pobox.com Newsgroups: comp.lang.scheme Subject: LAND*: an AND with local bindings Date: Sun, 22 Feb 1998 15:53:52 -0600 Organization: Deja News - The Leader in Internet Discussion Lines: 176 Message-ID: <6cq6vd$isk$1@nnrp2.dejanews.com> Reply-To: oleg@pobox.com NNTP-Posting-Host: postnews.dejanews.com Summary: proposing a LAND* ::= LET* + AND Keywords: binding, special form, macro, denotation, Scheme, programming with guards X-Article-Creation-Date: Sun Feb 22 21:53:52 1998 GMT X-Http-User-Agent: Mozilla/4.04 (Macintosh; I; PPC, Nav) Like an ordinary AND, a LAND* special form evaluates its arguments - expressions - one after another in order till the first one that yields #f. Unlike AND, however, a non-#f result of one expressions can be bound to a fresh variable and used in the subsequent expressions. - Motivation - Sample applications - Generalizing cond: LAND* vs => - LAND* and programming with guards - Implementation issues - Challenges of validating special forms (writing test cases) - Annotated syntax of LAND* - Denotational specification of LAND* semantics When an ordinary AND is formed of _proper_ boolean expressions: (AND E1 E2 ...) expression E2, if it gets to be evaluated, knows that E1 has returned non-#f. Moreover, E2 knows exactly what the result of E1 was - #t - so E2 can use this knowledge to its advantage. If E1 however is an _extended_ boolean expression, E2 can no longer tell which particular non-#f value E1 has returned. Chances are it took a lot of work to evaluate E1, and the produced result (a number, a vector, a string, etc) may be of value to E2. Alas, the AND form merely checks that the result is not an #f, and throws it away. If E2 needs it, it has to compute that value again. This proposed LAND* special form lets constituent expressions get hold of the results of already evaluated expressions, without re-doing their work. Sample applications: The following piece of code (from my treap package) (let ((new-root (node:dispatch-on-key root key ...))) (if new-root (set! root new-root))) could be elegantly re-written as (land* ((new-root (node:dispatch-on-key root key ...))) (set! root new-root)) A very common application of land* is looking up a value associated with a given key in an assoc list, returning #f in case of a look-up failure: ; The standard implementation (define (look-up key alist) (let ((found-assoc (assq key alist))) (and found-assoc (cdr found-assoc)))) ; A more elegant solution (define (look-up key alist) (cdr (or (assq key alist) '(#f . #f)))) ; An implementation which is just as graceful as the latter ; and just as efficient as the former. In fact, it expands ; _precisely_ into it (define (look-up key alist) (land* ((x (assq key alist))) (cdr x))) Generalized cond: (or (land* (bindings-cond1) body1) (land* (bindings-cond2) body2) (begin else-clause)) Unlike => (cond's send), LAND* applies beyond cond. LAND* can also be used to generalize cond, as => is limited to sending of only a single value; LAND* allows as many bindings as necessary (which are performed in sequence) (or (land* ((c (read-char)) ((not (eof-object? c)))) (string-set! some-str i c) (++! i)) (begin (do-process-eof))) Another concept LAND* is reminiscent of is programming with guards: a LAND* form can be considered a sequence of _guarded_ expressions. In a regular program, forms may produce results, bind them to variables and let other forms use these results. LAND* differs in that it checks to make sure that every produced result "makes sense" (that is, not an #f). The first "failure" triggers the guard and aborts the rest of the sequence (which presumably would not make any sense to execute anyway). Appendices A and B below show a formal syntax and denotational semantics of the LAND* form being proposed. BTW, if one has a Scheme interpreter written in Prolog/ML/Haskell, he can implement that semantics right away. In Scheme, it is trivial to code LAND* using "define-syntax". Alas, Gambit does not have this facility. Thus LAND* is implemented as a macro, which converts a LAND* expression into a "tree" of AND and LET expressions. For example, (LAND* ((my-list (compute-list)) ((not (null? my-list)))) (do-something my-list)) is transformed into (and (let ((my-list (compute-list))) (and my-list (not (null? my-list)) (begin (do-something my-list))))) I must admit the LAND* macro is written in a pathetic anti-functional style. The excuse I have is that the macro's goal is a syntactic transformation of source code, that is, performing a re-writing. IMHO, rewriting kind of suggests mutilation. The implementation and the validation code are available from http://pobox.com/~oleg/ftp/Scheme/vland.scm The validation code verifies not only that everything works as expected, but also that LAND* finds syntax errors where expected. Note validating a special form is a bit more challenging than a regular procedure. It's certainly more involved than it looks in the following snippet: (expect (land* ((x 1)) ) 1) (must-be-a-syntax-error (land* ( #f (x 1))) ) (expect (land* ( (#f) (x 1)) ) #f) It's especially tricky to trap a _syntax_ error where it is expected, recover and continue with other test cases. It goes without saying that 'expect' and 'must-be-a-syntax-error' must be special forms; Moreover, they are special forms of _the higher order_, as you can see from their implementation (see the reference above). See also http://pobox.com/~oleg/ftp/Scheme/ for the definition of my standard "prelude" that is used during the validation process. I'd appreciate comments, questions and suggestions. Appendix A. Syntax and informal semantics LAND* (CLAWS) BODY where CLAWS is a list of expressions or bindings: CLAWS ::= '() | (cons CLAW CLAWS) CLAW ::= (VARIABLE EXPRESSION) | (EXPRESSION) | BOUND-VARIABLE The CLAWS are evaluated in the strict left-to-right order. For each CLAW, the EXPRESSION part is evaluated first (or BOUND-VARIABLE is looked up). If the result is #f, LAND* immediately returns #f, thus disregarding the rest of the CLAWS and the BODY. If the EXPRESSION evaluates to non-#f, and the CLAW is of the form (VARIABLE EXPRESSION) the EXPRESSION's value is bound to a freshly made VARIABLE. The VARIABLE is available for _the rest_ of the CLAWS, and the BODY. As usual, all VARIABLEs must be unique (like in let*). Thus LAND* is a sort of cross-breed between LET* and AND. Appendix B. Formal (denotational) semantics Eval[ (LAND* (CLAW1 ...) BODY), Env] = EvalClaw[ CLAW1, Env ] andalso Eval[ (LAND* ( ...) BODY), ExtClawEnv[ CLAW1, Env]] Eval[ (LAND* (CLAW) ), Env] = EvalClaw[ CLAW, Env ] Eval[ (LAND* () FORM1 ...), Env] = Eval[ (BEGIN FORM1 ...), Env ] Eval[ (LAND* () ), Env] = #t EvalClaw[ BOUND-VARIABLE, Env ] = Eval[ BOUND-VARIABLE, Env ] EvalClaw[ (EXPRESSION), Env ] = Eval[ EXPRESSION, Env ] EvalClaw[ (VARIABLE EXPRESSION), Env ] = Eval[ EXPRESSION, Env ] ExtClawEnv[ BOUND-VARIABLE, Env ] = Env ExtClawEnv[ (EXPRESSION), Env ] = EnvAfterEval[ EXPRESSION, Env ] ExtClawEnv[ (VARIABLE EXPRESSION), Env ] = ExtendEnv[ EnvAfterEval[ EXPRESSION, Env ], VARIABLE boundto Eval[ EXPRESSION, Env ]] -----== Posted via Deja News, The Leader in Internet Discussion ==----- http://www.dejanews.com/ Now offering spam-free web-based newsreading