CODEWITHSUNDEEP
racket
JRR
JRR

Reputation: 6152

matching on AST in Racket

I'd like to write a function that matches on different syntax of the input argument, e.g.,

(define (foo e) 
  (match e
    [int (print "int")]
    [(and _ _) (printf "and")])
)

such that I can call it with:

(foo 1) --> prints "int"
(foo (and #t #f)) --> prints "and"

but that doesn't seem to work. What did I do wrong?

Upvotes: 0

Views: 490

Answers (3)

law-of-fives
law-of-fives

Reputation: 643

There is not a short yet complete response to this.

The first thing is, you cannot do this with a procedure. There are predicates you can use to determine if something is a number, like number?, but you can't catch syntax like and with this.

But the really, really, really important point is that you can't catch anything like this: by the time foo sees e, the expander has already expanded any syntax and evaluated the expression. That is, for instance, (and #t (+ 3 4)) has been converted into an expression like (if #t (+ 3 4) #f) and this expression is already evaluated by the time you see e inside the procedure, in which case e is just 7. In Racket, arguments to procedures are evaluated before the procedure is called. This means, roughly, all syntax transformers are applied, and the resulting expanded expression is evaluated, and then the procedure is called on the resulting value.

If you only care about tinkering with s-expressions, you can quote the argument and play with the resulting list. (quote (and 2 3) will give you a list containing the symbol 'and and not the syntax, so this probably isn't what you want. I mention it for some completeness.

The way to manage your question in Racket is to use macros. Again, the problem is that expressions passed as arguments to a procedure are already evaluated by the time the procedure is called, so you have to work at the level of define-syntax in order to catch expressions before they're expanded and evaluated. That is, to solve your specific problem you need something like a procedure which takes some syntax as an argument and gives back syntax:

#lang racket/base
(require (for-syntax racket/base syntax/parse))

(define-syntax (foo stx)
  (syntax-parse stx
    #:literals (and)
    [(_ i:number)
     (syntax (displayln "int"))]
    [(_ (and a b))
     (syntax (displayln "and"))]))

This procedure takes some syntax and produces some other syntax. The syntax argument stx (which could be named anything, it's just convention) must match a clause or else it is a syntax error. When you define syntax, you are essentially making a new programming language and this is a new construct in that language. If it matches, such as the case (and #t #f), it will replace the syntax #'(foo (and #t #f)) with something like #'(displayln "and"). It won't actually display "and" until this is evaluated.

To get started on macros see the Racket Guide or the Racket Reference.

Upvotes: 2

John Clements
John Clements

Reputation: 17203

To add just a bit to the excellent answer from law-of-fives, the feature I think you're looking for were called "FEXPR"s in Lisp. A FEXPR was a procedure that received the syntax of the arguments, rather than their values.

Several people pointed out the problems with FEXPRs, though (cf Wand, "The Theory of Fexprs is Trivial"); specifically, they make compilers very very unhappy. Instead, we now have Racket's macro system, which manages to combine expressiveness with a clear boundary between compile-time and run-time execution.

Upvotes: 0

soegaard
soegaard

Reputation: 31147

The problem is that the match pattern int matches everything.

> (match 42
      [int  "foo"]
      [_    "bar"])
"foo"

If you want to match the symbol int you need to write 'int

> (match 'int
      ['int  "foo"]
      [_     "bar"])
"foo"
> (match 42
      ['int  "foo"]
      [_     "bar"])
"bar"

Also note that in you example: (foo (and #t #f)) the arguments of the functions call are evaluated before the function is called. That is, first (and #t #f) is evaluated with #f as result. Then foo is callled: (foo #f).

If you want to call foo with a list-and-symbols representation the expression, then use: (foo '(and #t #f)).

Upvotes: 0

Related Questions