I tried to learn continuations yesterday. This led me to a tutorial on composable continuations in schemewiki.org. It explains things nicely, but what really intrigues me is something completely different: rainbow parentheses on mouse hovering.
This post, of course, explains how I managed to get it on my website!
Hacking schemewiki.org #
Since I do not know how to implement this feature, the first step is obvious: take a look at the source code in schemewiki.org. For (+ 1 (+ 3 (+ 2 4)))
, here’s the result:
http://community.schemewiki.org?composable-continuations-tutorial
... <span class="paren">(<a href="http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_idx_278" class="scheme-documentation">+a> 1 <span class="paren">(<a href="http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_idx_278" class="scheme-documentation">+a> 3 <span class="paren">(<a href="http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_idx_278" class="scheme-documentation">+a> 2 4)span>)span>)span> ... |
Something is going on with the class paren
… Perhaps they use JavaScript to add the rainbow? But I searched for js
in the source code and found nothing…
If it’s not JavaScript, then perhaps CSS? I saw at the top of the file…
http://community.schemewiki.org/css/default.css
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
... /* The paren stuff */ /* Top level */ PRE.scheme > SPAN.paren:hover { background-color: #FFCFCF } /* Paren level 1 */ PRE.scheme > SPAN.paren > SPAN.paren:hover { background-color: #CFFFCF } /* Paren level 2 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #CFCFFF } /* Paren level 3 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #CFFFFF } /* Paren level 4 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #FFCFFF } /* Paren level 5 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #FFFFCF } /* Paren level 6 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #B4E1EA } /* Paren level 7 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #BDEAB4 } /* Paren level 8 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #EAD4B4 } /* Paren level 9 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #F4D0EC } /* Paren level 10 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #D0D9F4 } /* Paren level 11 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #FFCFCF } /* Paren level 12 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #CFFFCF } /* Paren level 13 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #CFCFFF } /* Paren level 14 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #CFFFFF } /* Paren level 15 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #FFCFFF } /* Paren level 16 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #FFFFCF } /* Paren level 17 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #BDEAB4 } /* Paren level 18 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #EAD4B4 } /* Paren level 19 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #F4D0EC } /* Paren level 20 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #D0D9F4 } /* Paren level 21 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #FFCFCF } /* Paren level 22 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #CFFFCF } /* Paren level 23 */ PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:hover { background-color: #CFFFCF } PRE.scheme > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren > SPAN.paren:before { content: "{{23 levels of indentation?! Yiakes!}}" } /* extend here if more nestings are needed */ ... |
Mystery solved!
Integration with Pygments #
This rainbow trick requires that matching parentheses are grouped together in a span
. The obvious method to achieve this is to use the read
function to transform string into an S-Expression, thereby grouping matching parentheses together. However, one complication is that I also use Pygments for syntax highlight. It’s not clear how to integrate all of these together. Let’s explore a couple of options:
- If we group parentheses first by using
read
, the output would be an S-expression. Pygments, which expects a string as an input, won’t be able to function. That means we need to manually highlight syntax… which seems really difficult. - If we use Pygments first, the output would be an X-expression representing an HTML DOM tree.
read
, which expects a string as an input, won’t be able to function. That means we need to manually extract and parse code from the tree. This is not trivial at all. For instance, it’s not clear how to distinguish between an actual left parenthesis and a left parenthesis as a string.
However, one cool feature of Pygments is that it does not only do a syntax highlight but also acts as a lexer. Here’s an output example from Pygments:
'(div ((class "highlight")) (table ((class "sourcetable")) (tbody (tr (td ((class "linenos")) (div ((class "linenodiv")) (pre " 1n 2n 3n 4n 5n..."))) (td ((class "code")) (div ((class "source")) (pre (span) (span ((class "kn")) "#lang ") (span ((class "nn")) "racket") "nn" (span ((class "p")) "(") (span ((class "k")) "define-syntax-rule") " " (span ((class "p")) "(") (span ((class "n")) "def") " " (span ((class "n")) "whatever") " " (span ((class "k")) "...") (span ((class "p")) ")") " " (span ((class "p")) "(") (span ((class "k")) "define") " " (span ((class "n")) "whatever") " " (span ((class "k")) "...") (span ((class "p")) "))") "n" (span ((class "p")) "(") (span ((class "k")) "define-syntax-rule") " " ...) ...) ...) ...) ...) ...) ...) |
Notice that all parentheses are tagged with the class p
properly, so the second approach looks really promising. But while this blob of data contains what we want, it’s not exactly a stream of tokens. To extract that out, we use a straightforward pattern matching:
(match (highlight my-code-str) [`(div ((class "highlight")) (table ((class "sourcetable")) (tbody (tr (td ((class "linenos")) (div ((class "linenodiv")) (pre ,linenos))) (td ((class "code")) (div ((class "source")) (pre ,things-in-pre ...)) "n")))) "n") `(div ((class "highlight")) (table ((class "sourcetable")) (tbody (tr (td ((class "linenos")) (div ((class "linenodiv")) (pre ,linenos))) (td ((class "code")) (div ((class "source")) (pre ((class "scheme")) ,@(parenthesize things-in-pre))) "n")))) "n")]) ; add class scheme to pre to make CSS works |
What we need to do next is to write a function parenthesize
to match (span ((class "p")) "(")
with (span ((class "p")) ")")
. Note however that right now adjacent parentheses are grouped together, like (span ((class "p")) "))")
. Therefore, we need to first normalize them by splitting them to multiple tokens: (span ((class "p")) ")")
and (span ((class "p")) ")")
.
After normalization, we now need to do the real work which is to parse and group matching parentheses together. There are obvious and efficient algorithms to do this, but I’ve heard that Racket’s pattern matching is pretty powerful, so let’s try that. The idea is to find an innermost matching parentheses and group them one at a time, then repeat until there is no more matching parentheses left.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
(define left-paren '(span ((class "p")) "(")) (define right-paren '(span ((class "p")) ")")) (define not-paren? (negate (curryr member (list left-paren right-paren)))) (define (iter lst) (match lst [(list prefix-tok ... (== left-paren) (? not-paren? inside) ... (== right-paren) suffix-tok ...) (iter (append prefix-tok (list `(span ([class "paren"]) ,left-paren ,@inside ,right-paren)) suffix-tok))] [_ lst])) |
And finally define parenthesize
:
And holy cow, it works! Pretty quickly, too. The exact time complexity is unclear since I do not exactly know how Racket’s magical pattern matching works. Note that the matching patterns are not static data, so the compiler would not be able to exploit this much. We can assume that the compiler will generate a dumb code to try to match things. Finding an innermost matching parentheses definitely takes at least linear time, and we repeat it until there’s no more matching parentheses. That is, the algorithm would be at least quadratic. Since the code in my blog would be at most 500 lines long, that’s pretty chill.
But we can improve this and make it linear time. There are several ways to do it. I came up with a stack-based solution, and Justin seems to like it:
This algorithm also tolerates mismatched parentheses (but not mismatch type). This is great because it’s possible that I will just copy and paste only a par