Jump to content
  • Advertisement
Sign in to follow this  
Daerax

Metaprogramming and Number Paramerterized Types

This topic is 3726 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So this is just me wanting to talk about my experiences relating to the thread title. Feel free to share yours. In my opinion one of the reasons C++ still exists is because it has been extended using templates to useful directions beyond what the authors could ever have hoped. Quite nice behaviour I did not intend was one can add 2 vectors of type Vec(n, double) and Vec(n, int) but cannot take their dot product. Notice one knows before compiling that a vector was indexed out of bounds. This is thanks to the russian group who have done a visual studio integration that does some really nice intellisense. I recently stumbled upon the paper on Number Parameterized Types for Haskell. In there different methods are talked about which let one emulate some of the attributes of dependent types - where some invariants can be checked statically at compile time to eliminate a certain classes of errors. Looking at it, I decided such a thing would be quite useful to me so I decided to implement it on the .NET framework. Which is currently where I live thanks to all the tools and libraries. Luckily as well, my language of choice on there is Nemerle so I was able to implement it more cleanly and flexibly than found in the paper. The whole method involves encoding the required numbers into type constructors. The core of the code is in creating a bunch of empty union types. Specifying an interface and then implementing each digit as structs matching the interface which can then be used to instantiate arbitrary classes.
    public variant D7
        | D7    
    public variant D8    
        | D8    
    public variant D9 
        | D9
   ...    
/***************************************************************************/   
    public interface Digit['a]
        ToNumber() : int

    public struct d0 : Digit[D0]
        public ToNumber() : int
            0
    public struct d1 : Digit[D1]
        public ToNumber() : int
            1
  ....

Defining a vector class: Vector ['a, 'b, 'vtype] constructor( args : Digit['a] * Digit['b], init: vtype) .... Then one can go: def (v, v2) = (Vector(d0(), d2(), 0), Vector(d0(), d3(), 0) ; And get a compile time error when you try to add both of them. I then decided to clean it up and make it more general. Note that to allow arbitrary precision simply allow the digit union or variant types to take a data constructor. I do not know if this is how hardcore schemers and lispers view the world but I originally intended to write a seperate set of macros and then write a library using them but then realized that the macros and the library belonged in the same package, it did not make sense separating them and only making the library visible. What I realized I was doing was language oriented programming. For example on .NET I cannot create a polymorphic type which also contained mathematical operators since there is no Number Interface (why there is no Add(a ,b) I am unsure). To get around this I decided to create the operators as macros, since the types of the vectors will be fixed and known within the body of the functions where the usage occurs. Nemerle allows one to do metaprogramming in the same language and uses quasiquotations of nemerle code to deconstruct and construct syntax trees so one need not write obtuse code messing with the syntax tree. Thus for example I could write:
macro @<.>(a, b) { acquire type of a and b. Use simple 9 line helper function to convert to integer. 

Compare sizes. If mismatch throw compile error. 
Else Quote: 
         <[
            def size = $vector1.Size.Upperbound;
            def arr1 = $vector1.getArrayRep();
            def arr2 = $vector2.getArrayRep();
            def zero = arr1[0] - arr1[0];
            def dotp = $[arr1 * arr2 | i in $[0 .. size-1]].FoldLeft(zero, (i,j)=> i + j);]>
. The computation is staged and only those values which are not known at compile time are deferred. To cut a long story short I wrote a bunch of macros with little effort that made using number paramertized types as part of the language simple. Then wrote a natural number package (you can add and multiply the numbers and know results before runtime) using them. Which were then used for the vectors. Vectors dimensions can only be constructed using a natural number. Although one can say def v = vec 5 this is just shorthand for def v = Vector(0, Naturals(d0(d5()))). Code of which is :
 def p = Helper.IntToTypeCons(sz);
            <[Vector(0, Naturals($p)) ]>;}
. Anyways being able to drop down and write plugins to the compiler to make it more suit your needs when the language or framework is not expressive enough to tackle your domain is nice I feel. The only downside is being careful not to introduce too many new keywords and weird syntaxes. Although to the end user the macros not extended with new syntax are in fact indistinguishable from normal functions.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Daerax
The whole method involves encoding the required numbers into type constructors. The core of the code is in creating a bunch of empty union types. Specifying an interface and then implementing each digit as structs matching the interface which can then be used to instantiate arbitrary classes.


Interesting if you can specify your domain. Not so helpful if I walk along and decide to create a vector in 37-space, now does it? Unless I am reading it wrong...

But a very neat trick. I love reading how people bend and twist code.

Share this post


Link to post
Share on other sites
Quote:
Original post by visage
Quote:
Original post by Daerax
The whole method involves encoding the required numbers into type constructors. The core of the code is in creating a bunch of empty union types. Specifying an interface and then implementing each digit as structs matching the interface which can then be used to instantiate arbitrary classes.


Interesting if you can specify your domain. Not so helpful if I walk along and decide to create a vector in 37-space, now does it? Unless I am reading it wrong...

But a very neat trick. I love reading how people bend and twist code.


Heh I described it wrong. What I meant was that I created 9 different datatypes (enums, variants, data, whatever) to represent each digit. I then created an interface Digit['a] And then created struct digit0 : Digit[D0] ... for all 9 digits. Then the vector constructor will have : this(typearg : Digits['a], seed : int) ...

If you wanted to create a vector in 37 space whose elements are doubles that is simple. Just go def v = vec 37 seed 0.0. This get translated by the macro to Vector(0.0, Naturals(d3(d7(0)))) where the zero is used to terminate (could be anything though: "", 99, etc.). The "type arguments" can be as large as you want. Even as big as One Million. This is after the variants have been changed to take data constructors.
public variant['a] D9 
| D9 {next : 'a}
. However if you know that you will never go over four digits then the variants need not be extended as above. The constructor of the vecotor would then become this(typearg : Digits['a] * Digits['b] * Digits['c] * Digits['d], seed : int) and the above macro would have translated to: Vector(0.0, Naturals(d0(), d0(), d3(), d7()) )

No need to specify the domain else in my opinion would be pretty useless. The idea for this came from here.

[Edited by - Daerax on July 9, 2008 11:37:10 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!