Guest User

Morse macro

a guest
Nov 12th, 2015
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.58 KB | None | 0 0
  1. //// You'll need MBase [1] to run this example. This is essentially a Lisp loaded with
  2. //// all the bells and whistles one need to write compilers (i.e., macros) easily.
  3. ////
  4. //// This is a demonstration of how to use the Language-Oriented Programming approach
  5. //// in an unusual case of a very simple problem domain: recognising Morse code.
  6. ////
  7. //// Here, a convenient syntax is defined first, to encode the Morse table naturally,
  8. //// and then a macro is defined to back this syntax with a trie-based implementation.
  9. //// With a dedicated syntax for this macro we're automatically getting syntax highlighting
  10. //// and it just looks nicer than S-expressions or whatever.
  11. ////
  12. //// An advantage of this approach is that each step is very simple, while not being
  13. //// short in terms of number of lines, it is more readable and more maintainable than
  14. //// a function-based solution.
  15. ////
  16. //// Compilation pipeline is following:
  17. //// parsing: defmorse macro
  18. //// -> 'ds_to_trie': trie IR
  19. //// -> for each trie node, 'mchoice' -> Lisp code
  20. //// -> 'defmorse' macro: wrap the top node into a lambda
  21. ////
  22. //// [1] https://github.com/combinatorylogic/mbase
  23.  
  24.  
  25. //// Define a syntax extension for the Morse code definition.
  26. // Macro expansion is deferred to later
  27. syntax in expr, start: ' "." morse [mcode]:ds ";" '
  28. + { mcode := slist<[mdef]>:ds => ds;
  29. mdef := "|"? [ident]:dst slist<[dd]>:dds "|"? => p(dds, dst);
  30. dd := { "." => `dot } / { "-" => `dash }; }
  31. { return 'lisp'('defmorse'(ds)) }
  32.  
  33. ----------- // hint a compiler to flush the definitions
  34.  
  35. //// Define an intermediate trie language structure
  36. ast trie { expr = ch(expr:l, expr:r, ident:ret) // choice node
  37. | t(ident:ret); // terminal node
  38. }
  39.  
  40. //// Convert a flat Morse defs list into a trie
  41. // This is the most complex part of this implementation, but
  42. // an equally complex code is needed for any non-macro recogniser anyway.
  43. //
  44. // The same trie intermediate language code can later be reused for the other
  45. // macros, it is fairly generic.
  46.  
  47. function ds_to_trie(ds) {
  48. // Utility function: add a terminal to a trie
  49. update(t, dst) = visit:trie(expr:t) { once expr {
  50. ch -> mk:node(ret = dst)
  51. | t -> mk:node(ret = dst)}};
  52.  
  53. // Utility function: make a new choice node if needed
  54. prep(t) = visit:trie(expr:t) { once expr {
  55. ch -> node
  56. | t -> 'ch'('t'([]), 't'([]), ret)}};
  57.  
  58. // Rewrite a binary trie with a single new entry
  59. rewrite(trie, p) = {
  60. <p(dds,dst)> = p;
  61. do loop(d = dds, t = trie) {
  62. if(not(d)) update(t, dst) // Insert a terminal node
  63. else visit:trie(expr: t) { // Walk the choice nodes, creating new nodes if needed
  64. once expr { ch -> {match car(d) with
  65. 'dot' -> mk:node(l=loop(cdr(d),prep(l))) // dots to the left
  66. | 'dash' -> mk:node(r=loop(cdr(d),prep(r)))} // dashes to the right
  67. | t -> loop(d, prep(node)) // Make a dummy node and repeat
  68. }}}};
  69.  
  70. // Iteratively rewrite a trie for all the pairs
  71. foldl(rewrite, 't'([]), ds)}
  72.  
  73. //// Generate a Lisp code
  74. function mchoice(arg, nxt, l, r, ret) {
  75. varg = 'var'(arg);
  76. // Build a single trie entry if statement
  77. `if( \varg\ ) {
  78. \nxt\ = cdr( \varg\ );
  79. if (car( \varg\ ) == 0) \l\ else \r\
  80. } else return \ret\ ` }
  81.  
  82. //// The actual macro
  83. macro defmorse(ds) {
  84. trie = ds_to_trie(ds); // Generate a trie IR first
  85. ltrief = // Compile it to Lisp
  86. visit:trie(expr: trie) {
  87. deep expr(arg) {
  88. ch -> symbols(nxt) { mchoice(arg,nxt,l(nxt),
  89. r(nxt),'vquote'(ret)) }
  90. | t -> {vret = 'vquote'(ret); `return \vret\`}}};
  91. // Make an unrolled trie function with a default argument name
  92. 'fun'(['arg0'],
  93. pfront_expr(ltrief('arg0')))}
  94.  
  95.  
  96. //// Now, use the previously defined language. In a production scenario
  97. // the language definiton is better be moved to another source file.
  98. define morse =
  99. .morse | A .- B -... C -.-. D -.. E . F ..-. G --. H .... I .. |
  100. | J .--- K -.- L .-.. M -- N -. O --- P .--. Q --.- R .-. |
  101. | S ... T - U ..- V ...- W .-- X -..- Y -.-- Z --.. |;
  102.  
  103. //// Test it. Morse codes are represented as lists of zeros (.) and ones (-).
  104. // The backend macro can be easily retargeted to understand any other representation.
  105. iter m in #'((0 0 0)
  106. (0 0 0 0)
  107. (0 0)
  108. (1))
  109. do writeline(morse(m))
  110.  
  111.  
  112. /////////
Advertisement
Add Comment
Please, Sign In to add comment