Loading

metaprograms.inc

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