k-infix

7.7

top ← prev up next →

k-infix

kefin

k-infix is a simple Haskell-like infix expression parser.

k-infix makes writing infix expressions in Racket easy. It’s extensible as one can add operators freely. k-infix supports prefix, postfix, and binary operators. Left and right -associativity are also supported.

1 Quick start

To get started we require the library and use $ to write expressions.

> (require k-infix)
> ($ 1 + 2)
3
> ($ 1 + 2 / (3 * 4))
7/6
> ($ 2 ^ 3 ^ 4)
2417851639229258349412352

The default expression parser handles arbitrary functions.

> (define (my-fn x y) (+ x (exp y)))
> ($ my-fn 1 2 + 3)
11.38905609893065

Note that to use arbitrary expressions as function arguments, you must surround them by parentheses.

> ($ my-fn (1/2 + 1/2) 2)
8.38905609893065

Otherwise, the operator will break the function application.

> ($ my-fn 1/2 + 1/2 2)
my-fn: arity mismatch;
the expected number of arguments does not match the given
number
  expected: 2
  given: 1
  arguments...:
   1/2

Arbitrary types are supported. Here, booleans.

> ($ 1 + 2 >= 3 and (5 + 2) / 2 < 5)
#t

Use ~ to escape parsing.

> ($ ~(if + 1 2) - 3)
-2

2 Custom parse rules

We can add our own parse rules using define-$+, this generates a new parser. For example, let’s make sqrt a unary prefix operator.

> (require k-infix/define)
> (define-$+ $1 (sqrt 200 left -100))
> ($1 sqrt sqrt 16)
2

An operator entry ((sqrt 200 left -100)) is of the form (id precedence associativity unary-precedence maybe-description).

In the default context where sqrt is a function and not an operator, evaluation would fail because it parses the above expression to (sqrt sqrt 16).

> ($ sqrt sqrt 16)
sqrt: arity mismatch;
the expected number of arguments does not match the given
number
  expected: 1
  given: 2
  arguments...:
   #<procedure:sqrt>
   16

The binary precedence is 200, this means that it will bind very strongly to whatever is to its right.

> ($1 sqrt 8 * 2)
5.656854249492381
> (* (sqrt 8) 2)
5.656854249492381

If we want multiplication take precedence we need to turn the binary precedence down to be lower than multiplication (100):

> (define-$+ $2 (sqrt 99 left -100))
> ($2 sqrt 8 * 2)
4
> (sqrt (* 8 2))
4

When it comes to unary postfix operators the second precedence is important. It specifies how strong the operator’s affinity is to be binary. For instance.

> (define-$+ $3 (! 99 left -100) (sqrt 99 left -100))
; -100, really does not like to be binary
> (define (! n) (if (positive? n) (* n (! (sub1 n))) 1))
> ($3 8 ! + sqrt 2)
40321.41421356237

In this example, once + was seen, ! was demoted to a unary postfix operator, then, once sqrt was seen, + was kept a binary operator, since sqrt has a lower postfix precedence.

We can augment the example by investigating unary precedences among themselves.

> (define-$+ $ (! 99 left -100) (sqrt 99 left -100))
> ($ sqrt 16 !)
24

From this we see that sqrt binds more tightly if the precedences are equal. What if we increase the precedence of !?

> (define-$+ $ (! 100 left -100) (sqrt 99 left -100))
> ($ sqrt 16 !)
4574143.623455652

Now that we have defined the precedence we want, we may want to combine more rules, however, we don’t want to keep re-specifying these rules. What we can do is combine parsers.

> (module other racket
     (provide meta-parser)
     (require k-infix/define)
     (define-$+ meta-parser (! 100 left -100) (sqrt 99 left -100)))
> (begin-for-syntax (require 'other))
> (define-$+ $ #:parsers (meta-parser) (I 120 left -100))
> (define I identity)
> ($ sqrt I 16 !)
4574143.623455652

Combining define-$ forms of the parser is cumbersome because the definition is always one phase too low to be used in the next define-$. The next section will show you how to keep every parser on the same phase using a non-define form.

3 Lower level parsing

k-infix provides low-level parser-generator ’primitives’. These are found in k-infix/custom, and their result is a function taking a syntax object as input.

> (require k-infix/custom)
> ($+ (sqrt 100 left -100))
#<procedure:...te/primitive.rkt:10:2>

The primitives are $* and $+, both are analogous to define-$* and define-$+ respectively except that they do not define the parser one +1 phase.

> (define $ ($+ (sqrt 100 left -100)))
> ($ #'(1 + sqrt 2))
#<syntax (+ 1 (sqrt 2))>

Combining parsers is easy using the #:parser directive as a first argument followed by a list of parsers. The parsers are merged in order, with conflicts resolved by prioritizing the last parser.

> (define $1 ($* (sqrt 200 left -100)))
> (define $2 ($* (I 200 left -100)))
> (define $3 ($* (+ 100 left 0)))
> (define $ ($* #:parsers ($1 $2 $3)))
> ($ #'(1 I + sqrt 2))
#<syntax (+ (I 1) (sqrt 2))>

One can also add rules whilst adding parsers.

> (define $ ($* #:parsers ($) (- 100 left 0)))
> ($ #'(1 I + sqrt 2 - 3))
#<syntax (- (+ (I 1) (sqrt 2)) 3)>

4 Reference

(require k-infix)

package: k-infix

syntax
($ item ...)

item = infix-expr
| ~ (expr)

infix-expr = or
| and
| bior
| bxor
| band
| =
| !=
| >=
| <=
| >
| <
| <=>
| <<
| >>
| +
| -
| *
| /
| %
| ^
| not
| bnot

Parse an infix expression. If no item is provided, the parser returns its operator table. An expression preceded by literal ~ will not be parsed.

value
bior : procedure?
value
bxor : procedure?
value
band : procedure?
value
<< : procedure?
value
>> : procedure?
value
% : procedure?
value
^ : procedure?
value
bnot : procedure?

Operator aliases for bitwise-ior, bitwise-xor, bitwise-and, arithmetic-shift (left) arithmetic-shift (right), modulo, expt, and bitwise-not respectively.

procedure
(!= x y) → boolean?
x : number?
y : number

Inequality test. Equivalent to (lambda (x y) (not (= x y)))

procedure
(<=> x y) → exact-integer?
x : number?
y : number?

Three-way numeric comparator. Returns 1 if x > y, 0 if x = y, -1 if x < y.

4.1 Define forms

(require k-infix/define)

package: k-infix

syntax
(define-$* name parse-lookup-entry ...)

name = id

parse-lookup-entry = (id prec associativity maybe-postfix-prec)

prec = exact-integer?

associativity = left
| right

maybe-postfix-prec = exact-integer?

Defines a parser with the given name and parse-lookup-entry unified with the default-parse-table as its lookup table.

prec is the precedence of the operator. The higher this is the tigher it binds to the surrounding expressions.

associativity is the associativity of the operator. Left-associativity means that the operator will nest left as (+ (+ (+ 1 2) 3) 4). Right-associativity nests right (^ (^ (^ 3 4) 2) 1).

maybe-postfix-prec determines the precedence in unary disputs. A unary dispute is where we have v1 op1 op2 v2, where v1 v2 are values and op1 op2 are operators. The operator with the highest postfix-prec will become binary, the other unary.

syntax
(define-$+ name parse-lookup-entry ...)

name = id

parse-lookup-entry = (id prec associativity maybe-postfix-prec)

prec = exact-integer?

associativity = left
| right

maybe-postfix-prec =
| exact-integer?

The same as define-$* but merges the lookup table with the default lookup table from $.

4.2 Custom forms

(require k-infix/custom)

package: k-infix

syntax
($* parse-lookup-entry ...)
($* #:parsers (parser ...) parse-lookup-entry ...)

name = id

parsers = expr

parse-lookup-entry = (id prec associativity maybe-postfix-prec)

prec = exact-integer?

associativity = left
| right

maybe-postfix-prec =
| exact-integer?

Creates a new parser using the parse lookup table. The second form merges previous parsers. Parse rules are overwritten by those that are defined last.

syntax
($+ parse-lookup-entry ...)
($+ #:parsers (parser ...) parse-lookup-entry ...)

name = id

parsers = expr

parse-lookup-entry = (id prec associativity maybe-postfix-prec)

prec = exact-integer?

associativity = left
| right

maybe-postfix-prec =
| exact-integer?

Same as $* but merges in the default parse table.

4.3 Default parser rules

Here are all operators, their precedence, and associativity respectively.

Examples:

> (require k-infix racket/pretty)
> (pretty-write ($))
#hash((!= . (50 left 50 "inequality comparison"))
      (% . (100 left 100 "modulo"))
      (* . (100 left 100 "multiplication"))
      (+ . (90 left 100 "addition"))
      (- . (90 left 100 "subtraction"))
      (/ . (100 left 100 "division"))
      (< . (60 left 60 "less-than comparison"))
      (<< . (80 left 80 "left binary shift"))
      (<= . (60 left 60 "less-than or equal comparison"))
      (<=> . (70 left 70 "three-way comparison"))
      (= . (50 left 50 "equality comparison"))
      (> . (60 left 60 "greater-than comparison"))
      (>= . (60 left 60 "greater-than or equal comparison"))
      (>> . (80 left 80 "right binary shift"))
      (^ . (110 right 110 "power"))
      (and . (10 left 10 "boolean and"))
      (band . (40 left 40 "bitwise and"))
      (bior . (20 left 20 "bitwise ior"))
      (bnot . (110 right 110 "bitwise not"))
      (bxor . (30 left 30 "bitwise xor"))
      (not . (110 right 110 "boolean not"))
      (or . (0 left 0 "boolean or")))

5 Examples

Here are some more examples to get you started.

5.1 Coin flipping

Suppose you have N coins and K flips. You can flip an arbitrary coin. All coins start face-down, and a flip has a 50% chance of change the coin to face-up. If a coin is face-up, you can take have it.

What is the expected value of (N K) coins and flips given that you waste any remaining flips on a single coin once all coins are flipped?

> (require k-infix memoize)
> (define/memo (x n k)
    (match* (n k)
      [(_ 0) 0]
      [(0 k) ($ 1/2 * x 0 (k - 1) + 1/2 * (-1 + x 1 (k - 1)))]
      [(n k) ($ 1/2 * (1 + x (n - 1) (k - 1)) + 1/2 * x n (k - 1))]))
> (x 1 1)
1/2
> (x 2 1)
1/2
> (x 2 2)
1
> (x 2 3)
5/4
> (exact->inexact (x 50 250))
49.5

top ← prev up next →

1	Quick start
2	Custom parse rules
3	Lower level parsing
4	Reference
5	Examples