Loading

metaprograms.inc

  1. ; file:     metaprograms.inc
  2. ; purpose:  experimental, not for production
  3. ; ----------------------------------------------------------------------------------------------------------
  4.  
  5. ; some experiments with metaprograms written in nasm macro language using assembler symbols, just as a proof of concept
  6. ; compile with listing and see some results in listing file. there is no use of linking nor running that, of course
  7. ; -nasm metaprograms.inc -l metaprograms.lst
  8.  
  9. ; an original fibonacci table generator copied from nasm manual, an inspiration:
  10. %if 0
  11. fibonacci:
  12.   %assign i 0
  13.   %assign j 1
  14.   %rep 100
  15.     %if j > 65535
  16.       %exitrep
  17.     %endif
  18.     dw j
  19.     %assign k j+i
  20.     %assign i j
  21.     %assign j k
  22.   %endrep
  23.  
  24. fib_number equ ($−fibonacci)/2
  25. %endif
  26.  
  27. ; well, that was just some ordinary code generator. however, we can do more abstract work with this mechanic
  28.  
  29. ; a metaprogramming debug value tracer :) for tracing metaprogram values into listing file, just comes handy sometimes
  30. %define debug   db
  31.  
  32. ; a factorial metaprogram written in nasm's macro language, in a style of metaprograms written in c++ templates
  33. ; does only a symbolic computation at assembly time, emits no code, only symbols, declares it's own type/class
  34.  
  35. %macro  factorial   2
  36. ; macro parameters:
  37. ; 1     new symbol name of a computation
  38. ; 2 input argument, a numeric value
  39.  
  40. ; %1: is an assembly symbol for "place", where the computation is performed (symbolic name of a computation is bound to location)
  41. ; computation returns %1.result value which is technically a local symbol .result of %1 symbol in assembly,
  42. ; and it's semantic for us is cleanly 'a result of computation named %1'. A dark side of anonymous lambda computations...
  43.  
  44. %defstr %1.type "numeric"
  45. %defstr %1.input "numeric"
  46. %defstr %1.class "computation"
  47.  
  48. %1:
  49. %assign fact %2
  50. %assign i %2-1
  51. %assign k i
  52.   %rep k
  53.     %assign fact i*fact
  54.     %assign i i-1
  55. %endrep
  56.  
  57. .result equ fact
  58.  
  59. %endmacro
  60.  
  61. ; invocation and usage in code:
  62. ; here, some computation is done
  63.     factorial f,6 ; 2*3*4*5*6 = 0x2d0
  64. ; now, a return value can be used back in source:
  65.     dq  f.result ; "display" a result D0 02 00 00 00 00 00 00 in listing file
  66.  
  67. ; This could be generalized into folds, even factorial is just one of possible folds on binary multiplication
  68. ; We need to reinvent symbolic functors with apply to generalize that. Since it's elementary operation is equ evaluator,
  69. ; these functors can accept symbols and constants and scalar expressions of them. Scalar in assembler's terminology, of course.
  70.  
  71. ; In the sense of Math theory, we are inside a category of assembler's critical expressions with all that, and both assembly
  72. ; symbols and their values are related with an "equ" morphism representing monadic bind (which adds symbol to assembler's symbol
  73. ; table, symbol table is a monad and I believe it is provable :).
  74. ; Perhaps some theoretic properties could be derived on them. They are quite weak.
  75. ; However, preprocessor variables with %assign did a real breakthrough on this in factorial example above.
  76. ; They are also critical-limited scalar values, and cannot accept relocatable symbols, but we have already invented
  77. ; a "type conversion" from scalar to relocatable symbol with the ".result equ" local symbolic construct
  78. ; So now it seems would be possible to write a full calculator on assembler's context stack as a metaprogram, later
  79.  
  80. ; example of meta predicate, tests if a name is present in list of names
  81. ; we use that as pure register (or [register]) detector in code generators to distinguish from symbol references and indirects
  82.  
  83. %macro is_member 3+
  84. ; 1 meta computation id
  85. ; 2 input, some name
  86. ; 3 list of possible names to select from
  87.  
  88. %defstr %%input %2
  89. %%1:
  90. %rep %0-2
  91.   %ifidni %%input,%3
  92.     %define %%found
  93.   %endif
  94. %endrep
  95. %ifdef %%found
  96. .result equ 1
  97. %else
  98. .result equ 0
  99. %endif
  100. %endmacro
  101.  
  102. ; with this kind of logic predicates, it could be possible to write some unification on symbolic types at compile time,
  103. ; (just like prolog does or c++ templates do with type unification)
  104.  
  105. ; --------------
  106. ; another experiment: preliminary attempt to construct an expression compiler as metaprogram
  107.  
  108. %macro PLUS 3
  109. %defstr %1.type "numeric"
  110. %defstr %1.input "numeric numeric"
  111. %defstr %1.class "computation"
  112.  
  113. %1:
  114. .result equ (%2+%3)
  115. %endmacro
  116.  
  117.     PLUS    a,2,3
  118.     dq  a.result
  119.  
  120. %macro MULT 3
  121. %defstr %1.type "numeric"
  122. %defstr %1.input "numeric numeric"
  123. %defstr %1.class "computation"
  124.  
  125. %1:
  126. .result equ (%2*%3)
  127. %endmacro
  128.  
  129.     MULT    b,2,3
  130.     dq  b.result
  131.  
  132. ; an apply functor for binary
  133. %macro APPLY 4
  134. %defstr %1.type "functor"
  135. %define %1.input "operator value value"
  136. %defstr %1.class "computation"
  137.  
  138. %1:
  139. .first equ %3
  140. .second equ %4
  141.   %2 %1.compute,%1.first,%1.second
  142. %1.result equ (%1.compute.result)
  143. %endmacro
  144.  
  145. ; now, we can even compose such computations into expressions:
  146.     APPLY   c,PLUS,3,4
  147.     APPLY   d,MULT,2,c.result
  148.     dq  d.result
  149.  
  150. ; more, we can overload apply for unary and even ternary when needed. here's apply unary
  151. %macro APPLY 3
  152. %defstr %1.type "functor"
  153. %define %1.input "operator value"
  154. %defstr %1.class "computation"
  155.  
  156. %1:
  157. .first equ %3
  158.   %2 %1.compute,%1.first
  159. %1.result equ (%1.compute.result)
  160. %endmacro
  161.  
  162. ; some exemplary unary operator
  163. %macro NEGATIVE 2
  164. %defstr %1.type "numeric"
  165. %defstr %1.input "numeric"
  166. %defstr %1.class "computation"
  167.  
  168. %1:
  169. .result equ (-%2)
  170. %endmacro
  171.  
  172. ; let's check unary aplication
  173.     APPLY   x,NEGATIVE,c.result
  174.     dq  x.result
  175.  
  176. ; another unary operator, this time a practical one in 64bit assembly, a curried ADD
  177. %macro ADD8 2
  178. %defstr %1.type "numeric"
  179. %defstr %1.input "numeric"
  180. %defstr %1.class "computation"
  181.  
  182. %1:
  183. .result equ (%2+8)
  184. %endmacro
  185.  
  186. ; now, we can try to invent haskell-like currying of any meta binary to meta unary. it's just a partial apply on metas
  187. ; however, perhaps a result shall evaluate to a macro invocation, not a symbol value. I am not sure, now.
  188. ; let's begin with all curried ADD functions generator
  189.  
  190. %macro _ADDX 1
  191.   %define ADD%1.argument %1
  192.   %macro ADD%1 2
  193.   %%ADD.%1:
  194.   .result equ (%2+ADD%1.argument)
  195.   %endmacro
  196. %endmacro
  197.  
  198. ; now, _ADDX serves as a meta generator for curried ADD macros (it is a real metafunction in our macroprogram)
  199.  
  200. %if 0 ; its still a little broken here...
  201.     ; declare functors
  202.     _ADDX 3
  203.     _ADDX 6
  204.     ; perform some computation with them
  205.     APPLY some_cool_curried,ADD3,1
  206.     APPLY other_curried,ADD6,some_cool_curried.result
  207.  
  208.     dq  other_curried.result
  209. %endif
  210.  
  211. %macro CURRY 3
  212. %defstr %1.type "functor"
  213. %define %1.input "operator numeric"
  214. %defstr %1.class "computation"
  215.  
  216. %1:
  217. ; I AM WORKING THINKING JUST HERE...
  218. ; The ideas are, from an example just above, to
  219. ; 1. generate a curried functor from a passed functor macro name
  220. ; 2a. apply it to metavalue
  221. ; 2b. generate a wrapper macro
  222.  
  223. %endmacro
  224.  
  225. ; We could also invent a generic fold based on APPLY
  226.  
  227. ; Another already working trick
  228. ; variable and greedy macro arguments are a good candidate for effortless cons list implementation
  229. ; lets try a folding loop on numbers list first, just for a comparision. every loop is just a special case of fold, either
  230.  
  231. %macro SUM 3-*
  232. ; sum all numbers from %2 up
  233.  
  234. %defstr %1.type "numeric"
  235. %defstr %1.input "numlist"
  236. %defstr %1.class "computation"
  237.  
  238. %1:
  239. %assign accumulator %2
  240. %assign j %0-2
  241. %rep j
  242.   %rotate 1
  243.   %assign i accumulator
  244.   %assign accumulator i+%2
  245. %endrep
  246. .result equ accumulator
  247. %endmacro
  248.  
  249.     SUM s0,1,2,3,4,5,6
  250.     dq  s0.result   ; 1+2+3+4+5+6 = 21 = 0x15
  251.  
  252. ; a little test of symbol mix and computation composition
  253. seno    equ 3
  254. slama   equ 7
  255. trava   equ 9
  256. listi   equ 2
  257.  
  258.     SUM s1,1,2,seno,3,slama,3,trava,0,listi,f.result
  259.     dq  s1.result
  260.  
  261. ; now, lets try something on list of symbols. first, a trivial sum
  262. %macro SUMSIZES 2-*
  263. ; we expect a size of a <symbol> is an "attribute" predeclared as a symbol in conforming syntax as <symbol>.size
  264. ; such pairs can be defined via structured declarators we invented long ago. (They replace a weak and not-so-practical-as-could-be
  265. ; legacy struct/endstruct assembly construct without intrinsic support)
  266. ; 1 symbolic name of this computation
  267. ; 2+    list of symbols, at least one
  268.  
  269. %1:
  270. %assign i %0-1
  271. %assign accumulator 0
  272. %rep i
  273.   %rotate 1
  274.   %assign accumulator accumulator + %1.size  
  275. %endrep
  276.  
  277. .result equ accumulator
  278. %endmacro
  279.  
  280. ; example of usage:
  281. first:
  282. .size   equ 3
  283. second:
  284. .size   equ 4
  285. third:
  286. .size   equ (f.result)
  287.  
  288.     SUMSIZES ls,first,second,third
  289.     dq  ls.result
  290.  
  291. ; now, a little bit generalized sum, sums on any "dot member" of all symbols, like above
  292. %macro SUMMEMBERS 3-*
  293. ; 1 symbolic name of this computation
  294. ; 2 member id, same to all symbols
  295. ; 3+    list of symbols, at least one
  296.  
  297. %1:
  298. %assign i %0-2
  299. %assign accumulator 0
  300. %define %%member .%2
  301. %rep i    
  302.   %assign accumulator accumulator + %3 %+ %%member
  303.   %rotate 1
  304. %endrep
  305.  
  306. .result equ accumulator
  307. %endmacro
  308.  
  309.     ; same as above, sums ".size" members of symbols from list
  310.     SUMMEMBERS  ms,size,first,second,third
  311.     dq  ms.result
  312.  
  313. ; And this is already quite useful, since nasm is not a multipass assembler, it cannot bloat up structures and needs critical
  314. ; expressions for every storage reservation and location control
  315. ; So this SUMMEMBERS fold above is quite handy to predict table sizes from future of pending assembly by
  316. ; summing sizes of structures or data passed to declarators
  317.  
  318. ; let's go deeper. generalize to list fold of APPLY any binary operator. numerics, a concept proof only for today
  319.  
  320. %macro FOLDAPPLY 5-*
  321. ; 1 symbolic name of this computation
  322. ; 2 memeber id
  323. ; 3 operator macro name
  324. ; 4 initial value for fold
  325. ; 5+    list of symbols, at least one
  326.  
  327. %1:
  328. %assign i %0-5
  329. %assign accumulator %4
  330. %define %%member .%2
  331. %rep i
  332.   %define %%applied foldapply %+ i
  333.   APPLY %1.%%applied,%3,accumulator,%5 %+ %%member
  334.   %assign accumulator %1.%%applied.result
  335.   %undef %%applied
  336.   %rotate 1
  337. %endrep
  338.  
  339. %1.result equ accumulator
  340.  
  341. %endmacro
  342.  
  343. %if 0 ; this is also borked
  344.     ; FOLDAPPLY z,size,PLUS,0,first,second,third
  345.     dq  z.result
  346. %endif
  347.  
  348. ; TODO: with this style of coding, invent an evaluator for context expressions (and I mean assembly stack contexts, which nasm
  349. ; already has, so we could reimplement an ancient UNIVAC Structured Macro Assembler in NASM macro language at the full strength
  350. ; of it's equivalence to Algol or Pascal expression syntax (or C, in today's ideology, it's just the same language still).
  351.  
  352. ; We would need no more compilers, then.
  353.  
  354. ; But the big question behind all this effort above remains:
  355. ; Is it possible to implement a Haskell-like language in assembler's preprocessor?
  356.