<div dir="ltr"><div><div><div><div><div>I posted a few questions about Racket macros a few days ago, and received many interesting suggestions Neil Van Dyke. Danny Yoo posted a link to a very interesting blog/book, which was of great help:<br>
<br> <a href="http://www.greghendershott.com/fear-of-macros/" target="_blank">http://www.greghendershott.com/fear-of-macros/</a><br><br>I also received programs from Robby Findler, Sean Kanaley, Marco Maggio, etc. Since the feedback was so usefull, I decided to ask for more. In fewer words, I am posting a small program here, and I would like to receive suggestion on improvements. I wrote a macro that converts infix expressions to the Cambridge prefix notation. Here are a few examples on how to use it:<br>
<br>#lang racket<br><br>(require "infix.rkt")<br><br>(define (fibonacci n)<br> (if (hp n<2) 1<br> (hp fibonacci:(n - 1)+fibonacci:(n - 2))))<br><br>(define (app xs ys)<br> (if (null? xs) ys<br> [hp car:xs cons app:(cdr:xs& ys)]))<br>
<br></div>One can use the macro on the REPL:<br><br>Welcome DrRacket, version 6.0 [3m].<br>Language: racket [costumized]; memory limit: 256 MB.<br>> (hp 'lily cons 'rose cons 'orchid cons ())<br>'(lily rose orchid)<br>
> (hp "Rose" cons "Lily" cons "Orchid" cons ())<br>'("Rose" "Lily" "Orchid")<br>> (hp 3 (4+5) 6)<br>162<br>> (hp 3*(4+5)*6)<br>162<br>> (define (area r) (hp pi r r))<br>
> (area 10)<br>314.1592653589793<br>> _<br><br></div>My program has many flaws. I hope to receive a corrected version. For instance, I don't think that writing the expression into a string in order to tokenize it is a good idea. I guess there is a better solution in Racket. I also believe that one can use syntax-case to get some error handling. In any case, here is the hp-macro:<br>
<br>#lang racket ;; File: infix.rkt<br>(require (for-syntax racket))<br><br></div>;; Function calls are written thus: expt:(2&3)<br></div>;; The arguments are separated by &, since the macro does not<br></div>;; accept commas. A call fn:(a&b&c&d) is read thus: (&(& (& a b) c)d)<br>
;; (flat '(&(& (& a b) c)d)) => (a b c d)<br><div><div><div>(define-for-syntax (flat xs)<br> (match xs ['() '()]<br> [(list-rest '& a b) (append (flat a) b)]<br> [_ (list xs)]))<br>
<br></div><div>;; (w op) produces the precedence of op. For instance,<br></div><div>;; (w '*) produces the precedence of *, whici is 5.<br></div><div>;; right associative operators have negative precedence.<br></div><div>
(define-for-syntax (w s) (case s <br> [(&) 0] [(or) 1] [(and) 2]<br> [(< = > <= >=) 3]<br> [(cons) -3] [(:) -7]<br> [(+ -) 4] [(* /) 5] [(^) 6] <br> [else 9]))<br><br></div><div>;; Multiplication can be achieved by * or by juxtaposition.<br>
</div><div>;; (times? x) checks juxtaposition<br></div><div>(define-for-syntax (times? x) (or (pair? x) (= (w x ) 9)))<br><br></div><div>;; e contains the infix expression, that will be consumed by the algorithm<br></div>
<div>;; o contains the operator stack<br></div><div>;; a builds the prefix expression.<br></div><div>;; I found this algorithm in an old Lisp book, by Winston and Horn<br></div><div>(define-for-syntax (pri e o a)<br> (define (p? ox) <br>
((if (< (w ox) 0) >= >) (abs (w (car e))) (abs (w ox))))<br> (match/values (values e o a)<br> [('() '() (cons x _)) x]<br> [[(cons (? times?) _) _ _ ] (pri (cons '* e) o a)]<br>
[[ (list-rest x y es) (or '() (cons (? p?) _)) _] <br> (pri es (cons x o) `(,(pre y) ,@a))]<br> [[_ (cons ': ops) (list-rest (cons '& _) y args)]<br> (pri e ops `((,y ,@(flat (car a))) ,@args))]<br>
[[_ (cons ': orest) (list-rest ax ay arest)]<br> (pri e orest `((,ay ,ax) ,@arest))]<br> [[_ (cons ox orest) (list-rest ax ay arest)]<br> (pri e orest `( (,ox ,ay ,ax) ,@arest))]))<br><br></div>
<div>;; if x is not pair?, (pre x) produces x<br></div><div>;; if x is a quoted expression, (pre x) produces x<br></div><div>;; otherwise, (pre x) calls (pri (cdr x) '() (pre (car x)) )<br></div><div>;; to produce the prefix notation.<br>
</div><div>(define-for-syntax (pre x)<br> (cond [ (not (pair? x)) x]<br> [ (equal? (car x) 'quote) x]<br> [else (pri (cdr x) '() (list (pre (car x))))]))<br><br></div><div>;; (tokenize xpr) has a misleading name. <br>
</div><div>;; In fact, it reads an sexpr representation of the infix expression.<br></div><div>;; For instance, if xpr= '("3" "*" "(" "4" "+" "5" ")" "*" "6"),<br>
</div><div>;; (tokenize xpr) produces '(3 * (4 + 5) * 6);<br></div><div>;; the list of string tokes is saved in s, that is destructively<br></div><div>;; updated by the algorithm. I wrote an error handling version,<br>
</div><div>;; but I decided to leave this kind of complication out of the<br></div><div>;; algorithm.</div><div>(define-for-syntax (tokenize xpr) (let [(s '())]<br> (define (rdit) (match s<br> [ '() (error "Unexpected end of input")]<br>
[ (list-rest "'" y resto) <br> (list 'quote (rdit))]<br> [ (cons (and head (regexp #rx"^\"")) tail) (set! s tail)<br> (substring head 1 (- (string-length head) 1))]<br>
[ (list-rest "(" ")" tail) (set! s tail) (list 'quote '())]<br> [ (cons "(" tail) (set! s tail)<br> (rdlist (~a s #:max-width 30))]<br> [ (cons ")" _)(error "Unmatched `)'")] <br>
[ (cons "#f" tail) (set! s tail) '#f]<br> [ (cons "#t" tail) (set! s tail) '#t]<br> [ (cons (and head (? string->number)) tail) (set! s tail) <br> (string->number head)]<br>
[ (cons head tail) (set! s tail) (string->symbol head)] )) <br><br></div><div>;; Here one reads the tail of the sexpr. <br></div><div>(define (rdlist callee)<br> (match s ['() (error "Unexpected end of list")]<br>
[(cons ")" tail) (set! s tail) '()]<br> [_ (cons (rdit) (rdlist callee))] ))<br> <br></div><div> ;; below, one tokenizes xpr, and calls (rdit)<br></div><div> (set! s (separate xpr)) (rdit)))<br>
<br></div><div>;; regexpr to tokenize x<br></div><div>(define-for-syntax (separate x) (regexp-match* <br> (regexp (string-append "\"[^\"]+\"|#t|#f|[a-z]+->[a-z]+"<br> "|-?[0-9]+\\.?[0-9]*e-?[0-9]+"<br>
"|[a-z?A-Z~-]+[0-9-]*"<br> "|-?[0-9]+\\.?[0-9]*|;[a-z]+/?[a-z]*"<br> "|<=|>=|[][()'&;*:<>=+/^-]")) x))<br><br></div><div>;; Below you will find two things that I don't like in<br>
</div><div>;; this solution. Since I don't want mandatory white space<br></div><div>;; around tokens, I write the infix expression into a string.<br></div><div>;; Then I tokenize the string, and read it back as an<br>
</div><div>;; sexpr. For instance, let us assume that one enters<br></div><div>;; (hp 3*4+5*6). There is no spaces around the operators.<br></div><div>;; The hp macro writes everything into a string: xpr= "3*4+5*6";<br>
</div><div>;; (tokenize xpr) reads this string back as an sexpr: (3 * 4 + 5 * 6).<br></div><div>;; (pre (tokenize xpr)) puts the expression into the prefix form.<br></div><div>(define-for-syntax (tkn stx) (with-output-to-string (lambda()<br>
(write (cdr (syntax->datum stx))) )))<br><br>(define-syntax (hp stx)<br> (datum->syntax stx (pre (tokenize (tkn stx)) )))<br><br>(provide hp)<br><br><div>;; Here is what I hope to get from the list members:<br>
</div><div>;; 1) A way to avoid writing the expression into a string<br></div><div>;; before tokenizing it. I am not sure whether this is<br></div><div>;; possible. By the way, I would like to have a macro<br></div>
<div>;; solution, like the one Mark Kantrowitz wrote for Lisp.<br></div><div>;; This means that I don't want to create a #lang infix,<br></div><div>;; or something like that.<br>;;<br></div><div>;; 2) I also want to avoid datum->syntax, since this is<br>
</div><div>;; the general recommendation in this user list.<br></div><div>;; I believe that it is quite easy to use syntax case,<br></div><div>;; since the algorithm is based on matching subexpressions.<br><br>
</div><div>;; Sorry for this long posting.<br><br></div></div></div></div></div>