Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //// You'll need MBase [1] to run this example. This is essentially a Lisp loaded with
- //// all the bells and whistles one need to write compilers (i.e., macros) easily.
- ////
- //// This is a demonstration of how to use the Language-Oriented Programming approach
- //// in an unusual case of a very simple problem domain: recognising Morse code.
- ////
- //// Here, a convenient syntax is defined first, to encode the Morse table naturally,
- //// and then a macro is defined to back this syntax with a trie-based implementation.
- //// With a dedicated syntax for this macro we're automatically getting syntax highlighting
- //// and it just looks nicer than S-expressions or whatever.
- ////
- //// An advantage of this approach is that each step is very simple, while not being
- //// short in terms of number of lines, it is more readable and more maintainable than
- //// a function-based solution.
- ////
- //// Compilation pipeline is following:
- //// parsing: defmorse macro
- //// -> 'ds_to_trie': trie IR
- //// -> for each trie node, 'mchoice' -> Lisp code
- //// -> 'defmorse' macro: wrap the top node into a lambda
- ////
- //// [1] https://github.com/combinatorylogic/mbase
- //// Define a syntax extension for the Morse code definition.
- // Macro expansion is deferred to later
- syntax in expr, start: ' "." morse [mcode]:ds ";" '
- + { mcode := slist<[mdef]>:ds => ds;
- mdef := "|"? [ident]:dst slist<[dd]>:dds "|"? => p(dds, dst);
- dd := { "." => `dot } / { "-" => `dash }; }
- { return 'lisp'('defmorse'(ds)) }
- ----------- // hint a compiler to flush the definitions
- //// Define an intermediate trie language structure
- ast trie { expr = ch(expr:l, expr:r, ident:ret) // choice node
- | t(ident:ret); // terminal node
- }
- //// Convert a flat Morse defs list into a trie
- // This is the most complex part of this implementation, but
- // an equally complex code is needed for any non-macro recogniser anyway.
- //
- // The same trie intermediate language code can later be reused for the other
- // macros, it is fairly generic.
- function ds_to_trie(ds) {
- // Utility function: add a terminal to a trie
- update(t, dst) = visit:trie(expr:t) { once expr {
- ch -> mk:node(ret = dst)
- | t -> mk:node(ret = dst)}};
- // Utility function: make a new choice node if needed
- prep(t) = visit:trie(expr:t) { once expr {
- ch -> node
- | t -> 'ch'('t'([]), 't'([]), ret)}};
- // Rewrite a binary trie with a single new entry
- rewrite(trie, p) = {
- <p(dds,dst)> = p;
- do loop(d = dds, t = trie) {
- if(not(d)) update(t, dst) // Insert a terminal node
- else visit:trie(expr: t) { // Walk the choice nodes, creating new nodes if needed
- once expr { ch -> {match car(d) with
- 'dot' -> mk:node(l=loop(cdr(d),prep(l))) // dots to the left
- | 'dash' -> mk:node(r=loop(cdr(d),prep(r)))} // dashes to the right
- | t -> loop(d, prep(node)) // Make a dummy node and repeat
- }}}};
- // Iteratively rewrite a trie for all the pairs
- foldl(rewrite, 't'([]), ds)}
- //// Generate a Lisp code
- function mchoice(arg, nxt, l, r, ret) {
- varg = 'var'(arg);
- // Build a single trie entry if statement
- `if( \varg\ ) {
- \nxt\ = cdr( \varg\ );
- if (car( \varg\ ) == 0) \l\ else \r\
- } else return \ret\ ` }
- //// The actual macro
- macro defmorse(ds) {
- trie = ds_to_trie(ds); // Generate a trie IR first
- ltrief = // Compile it to Lisp
- visit:trie(expr: trie) {
- deep expr(arg) {
- ch -> symbols(nxt) { mchoice(arg,nxt,l(nxt),
- r(nxt),'vquote'(ret)) }
- | t -> {vret = 'vquote'(ret); `return \vret\`}}};
- // Make an unrolled trie function with a default argument name
- 'fun'(['arg0'],
- pfront_expr(ltrief('arg0')))}
- //// Now, use the previously defined language. In a production scenario
- // the language definiton is better be moved to another source file.
- define morse =
- .morse | A .- B -... C -.-. D -.. E . F ..-. G --. H .... I .. |
- | J .--- K -.- L .-.. M -- N -. O --- P .--. Q --.- R .-. |
- | S ... T - U ..- V ...- W .-- X -..- Y -.-- Z --.. |;
- //// Test it. Morse codes are represented as lists of zeros (.) and ones (-).
- // The backend macro can be easily retargeted to understand any other representation.
- iter m in #'((0 0 0)
- (0 0 0 0)
- (0 0)
- (1))
- do writeline(morse(m))
- /////////
Advertisement
Add Comment
Please, Sign In to add comment