Rewrite this script by designing an interpreter in racket

Question

The original script is like this:

#lang racket
(for ([i (in-range 3)])
    (for ([j (in-range 9)])
      (display "X"))
     (display "\n"))

(for ([i (in-range 6)])
  (for ([j (in-range 3)])
    (display " "))
  (for ([j (in-range 3)])
    (display "X"))
  (for ([j (in-range 3)])
    (display " "))
  (display "\n"))

(for ([i (in-range 3)])
    (for ([j (in-range 9)])
      (display "X"))
     (display "\n"))

The output is:

XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
   XXX   
   XXX   
   XXX   
   XXX   
   XXX   
   XXX   
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX

I'm wondering whether I can rewrite this using a DSL like this:

(define a
  "3 9 X
6 3 b 3 X 3 b
3 9 X")

And then:

(interpret a)

to draw this graph.

Does anyone know what is the best way to do that?

Answer 1

To attack problems like this, first describe a data type that captures the operations you want in your DSL, rather than concentrating on surface syntax. Once you've got the data type in hand, you should have a much easier time with the problem.

From a first glance, it looks like we can design 3 fundamental forms in your language:

1. Strings
2. Repetition
3. Sequencing

We can represent this disjoint class with primitive strings and structures. Let's call this class as a whole a 'pexpr', for "printable expr". In code:

;; An pexpr is one of the following:
;;   * a primitive string,
;;   * a seq, or
;;   * a repeat
(struct seq (bodies) #:transparent)    ;; bodies is a list of pexpr
(struct repeat (n body) #:transparent) ;; n is a number, body is a pexpr

It might help to make some helper functions as abbreviations since "seq" and "repeat" are themselves a bit long-winded.

;; For convenience, we define some abbreviations s and r for seq and repeat,
;; respectively.
(define (s . bodies)
  (seq bodies))
(define (r n . bodies)
  (repeat n (seq bodies)))

Your example "I" string can be written as this:

(define an-example
  (s
   (r 3 (r 9 "X") "\n")
   (r 6 (r 3 " ") (r 3 "X") "\n")
   (r 3 (r 9 "X") "\n")))

Note that this encoding has an explicit representation for newlines which, from the surface syntax alone, is implicit. It then becomes the job of a parser to take lines in your surface syntax and turning them into pexprs, but that shouldn't be too difficult. Hopefully. :)

Anyway, the interpret function, then, becomes a matter of filling in the details for a template like this:

(define (interpret pexpr)
  (match pexpr
    [(? string?)
     ...]
    [(struct seq (bodies))
     ...]
    [(struct repeat (n body))
     ...]))

where the '...'s should be easy to fill in.

This approach to these kinds of problems is one described by How to Design Programs and Programming Languages: Application and Interpretation. I'd recommend looking at them: they're good stuff.

Answer 2

Sure, that looks doable. It's a parsing problem, mostly. I would break it up like this. Each of your input lines specifies a block of output lines. Figure out a good way of representing that, in Racket. Make some examples, to make sure it covers what you want it to cover. Next, I would probably write the function that renders one of these blocks. Mostly, I'd do that one first so that I could have the satisfaction of seeing output. Then, I would write a function that took a list of these block specifications and output them all. Then, I would write a function that parses a single line of input. It looks like you can split these lines using whitespace (e.g., using "regexp-split"), and then process these lists using an ad-hoc parser. This is the part I think I'd be most likely to get wrong, and I'd write a bunch of test cases before coding it up. Finally, you need a function that calls this parser on each line of input, and then ships the resulting block specifications off to the display function.