Scheme/Racket: idiomatic infix math evaluator

Question

Inspired by xkcd and a couple of praising blog posts, I decided to try out Lisp. It seemed that the best-supported dialect was Racket, itself a variant of Scheme, so I went with that and wrote an infix mathematical expression parser to get familiar with the basic concepts.

That was a mind-bending experience considering I never did functional programming. Not having mutable variables (or not using them, anyways) and having to use recursion instead of loops was a little hard for my imperative mind.

Anyways, I came up with this. My goal was to parse infix mathematical expressions with correct precedence and parentheses. It supports additions, subtractions, multiplications and divisions. It works, but it's probably full of hints that I'm new at this, and I would like to know which parts could have been made more idiomatic.

#lang racket

;; usage: (reduce (tokenize))

;; tokenizing function
(define (tokenize)
  (define (-tokenize-operator first)
    (cond
      ([equal? first #\+] (list + (read-char)))
      ([equal? first #\-] (list - (read-char)))
      ([equal? first #\*] (list * (read-char)))
      ([equal? first #\/] (list / (read-char)))))

  (define (-tokenize-number first)
    (define (--char->number char)
      (let ([ascii-zero (char->integer #\0)])
        (- (char->integer char) ascii-zero)))

    (define (--read-number initial)
      (let ([char (read-char)])
        (if (char-numeric? char)
            (--read-number (+ (--char->number char) (* initial 10)))
            (list initial char))))

    (if (char-numeric? first)
        (--read-number (--char->number first))
        '()))

  (define (-tokenize-openparen first)
    (if (equal? first #\()
        (list #\( (read-char))
        '()))

  (define (-tokenize first endchar)
    (if (equal? first endchar)
        '()
        (let ([operator (-tokenize-operator first)]
              [number (-tokenize-number first)]
              [openparen (-tokenize-openparen first)])
          (cond
            ([pair? operator] (cons (car operator) (-tokenize (cadr operator) endchar)))
            ([pair? number] (cons (car number) (-tokenize (cadr number) endchar)))
            ([pair? openparen] (list (-tokenize (cadr openparen) #\))))
            (else (tokenize))))))

  (let ([first (read-char)])
    (-tokenize first #\newline)))

;; parsing and evaluation function
(define (reduce tokens)
  (define (-operator-priority op)
    (cond
      ([ormap (lambda (p) (equal? p op)) (list + -)] 1)
      ([ormap (lambda (p) (equal? p op)) (list * /)] 2)))

  (define (-rvalue list max-priority)
    (define (--lower-parentheses parenthesed-expression next-tokens)
          (let ([paren-result (car (-rvalue parenthesed-expression 0))])
            (-rvalue (cons paren-result next-tokens) max-priority)))

    (define (--reduce-rvalue lvalue next-tokens)
      (let* ([operator (car next-tokens)]
             [priority (-operator-priority operator)]
             [then (cdr next-tokens)])
        (if (> priority max-priority)
            (let* ([rvalue (-rvalue then priority)]
                   [value (operator lvalue (car rvalue))])
              (-rvalue (cons value (cdr rvalue)) max-priority))
            list)))

    (let ([lvalue (car list)]
          [next-tokens (cdr list)])
      (if (pair? lvalue)
          (--lower-parentheses lvalue next-tokens)
          (if (pair? next-tokens)
              (--reduce-rvalue lvalue next-tokens)
              list))))

  (car (-rvalue tokens 0)))

Thanks!

Answer 1

Here are my review comments on the tokeniser:

1. It's unusual to prefix symbols with -. The indentation should be enough to tell you the "nesting level" of the inner functions, without having to put -s in front.

2. Your inner -tokenize could be hoisted into a named let, so that your tokenize function looked like this (I will make other changes to the function later, but for now I try to keep as close to your original code as possible):

   (define (tokenize)
     ;; other internal definitions
   
     (let recur ([first (read-char)]
                 [endchar #\newline])
       (if (equal? first endchar)
           '()
           (let ([operator (-tokenize-operator first)]
                 [number (-tokenize-number first)]
                 [openparen (-tokenize-openparen first)])
             (cond
               ([pair? operator] (cons (car operator) (recur (cadr operator) endchar)))
               ([pair? number] (cons (car number) (recur (cadr number) endchar)))
               ([pair? openparen] (list (recur (cadr openparen) #\))))
               (else (recur (read-char) #\newline)))))))
   

3. Character comparisons can use eqv? instead of equal?. Not really a biggie, but usually I reserve equal? for deep comparisons.

4. Use #f for false/null values, not '(). In Scheme, #f is the only false value there is; '() is a true value (like everything else). Though, instead of all those different tokenising helpers, and calling them all and then only using one of the return values, it would be nicer to test directly in the cond.

5. Instead of all the repeated (read-char)s, you might consider using a port stream instead. Create one using sequence->stream, then you can call stream-first and stream-rest on it.

With all that in mind, I'd write the tokeniser like so:

(define (tokenize [port (current-input-port)])
  (let recur ([str (sequence->stream (in-input-port-chars port))])
    (cond [(stream-empty? str) '()]
          [(char-numeric? (stream-first str))
           (let loop [(str str)
                      (digits '())]
             (if (and (not (stream-empty? str))
                      (char-numeric? (stream-first str)))
                 (loop (stream-rest str) (cons (stream-first str) digits))
                 (cons (string->number (list->string (reverse digits)))
                       (recur str))))]
          [(char-whitespace? (stream-first str))
           (recur (stream-rest str))]
          [else (cons (stream-first str) (recur (stream-rest str)))])))

(Comments on the evaluator to come later.)