The Artima Developer Community
Sponsored Link

Weblogs Forum
Macros and Domain Specific Languages

13 replies on 1 page. Most recent reply: Jul 15, 2006 1:03 PM by Christopher Diggins

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 13 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Macros and Domain Specific Languages (View in Weblogs)
Posted: Jul 9, 2006 12:19 PM
Reply to this message Reply
Summary
A macro pre-processor which works as a type-aware pattern matcher can be used to transform language X into another language Y. In other words you could create a domain specific language from another language.
Advertisement
Many macro languages, like the C pre-processor (CPP), involve dumb token replacement using a pseudo-function syntax, but this is extremely limited. The desired use of a pre-processor is often to modify the syntax and semantics of a language, but rarely is it type-aware. This severely limits is usefulness. The C++ template system on the other hand is also a powerful macro system, which is type-aware but can't work with tokens. The two systems clearly need to be married.

The next logical step in creating a better macro language would be to eliminate the function syntax, and use pattern matching syntax. A macro can be more effective if it matches patterns in the source code (with or without types) and rewrites them as desired.

For example consider if "add" was a function primitive in a post-fix language:

  42 13 add_int
  4.2 1.3 add_float
Now say that like most sane individuals, you prefer infix notation. Let's introduce a macro system which works using pattern transforms:
  transform { x:int + y:int } => { x y add_int }
  transform { x:float + y:float } => { x y add_float }
Now you can write two infix expression in your postfix language:
  42 + 13
  4.2 + 1.3
So this has essentially allowed you to redefine the syntax for your postfix language to create a new infix language, which may be more appropriate for the problem at hand.


Alexandre Tachard

Posts: 3
Nickname: alextp
Registered: Nov, 2005

Re: Macros and Domain Specific Languages Posted: Jul 9, 2006 6:25 PM
Reply to this message Reply
Interesting.
I wonder if you can apply this technique to nested patterns, and their ilk, even if only to determine left or right associativity of some operators. If so, I'd definitely like to program in a language that allowed this.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Macros and Domain Specific Languages Posted: Jul 9, 2006 8:42 PM
Reply to this message Reply
You may be interested in:

Eelco Visser, "Program Transformation with Stratego/XT Rules, Strategies, Tools, and Systems in Stratego/XT 0.9", Domain-Specific Program Generation, Lecture Notes in Computer Science, Volume 3016, Springer-Verlag, 2004.

http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-2004/2004-011.pdf

It could be ideal to implement arbitrary language to CAT

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: Macros and Domain Specific Languages Posted: Jul 10, 2006 8:09 AM
Reply to this message Reply
This is cool, but the example isn't too useful if you don't have named variables ;-).

Do you have ideas on how to handle procedures like this one:

f = [23] ["foo"] if

This function is Bool -> Int | String. Do you have types like Int | String? Or do you generate a compiler error for these kinds of procedures?

Are you going to add polymorphism / multimethods to Cat? So you could have a procedure int+ and string+, and a generic +:

1 2 + => 3
"1" "2" + => "12"

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Macros and Domain Specific Languages Posted: Jul 10, 2006 11:12 AM
Reply to this message Reply
> This is cool, but the example isn't too useful if you
> don't have named variables ;-).

The plan is to have named pattern matching terms, but not named variable or arguments.

> Do you have ideas on how to handle procedures like this
> one:
>
> f = [23] ["foo"] if
>
> This function is Bool -> Int | String. Do you have types
> like Int | String? Or do you generate a compiler error for
> these kinds of procedures?

I would like to support (Int | String) as a type.

> Are you going to add polymorphism / multimethods to Cat?

Yes, this is under development right now, and it'll look something like:


def + : (int int) -> (int) { add_int }
def + : (float float) -> (float) { add_float }
def + : (string string) -> (string) { cat_string }

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Macros and Domain Specific Languages Posted: Jul 10, 2006 11:16 AM
Reply to this message Reply
> Interesting.
> I wonder if you can apply this technique to nested
> patterns, and their ilk, even if only to determine left or
> right associativity of some operators.

I hope you will.

> If so, I'd
> definitely like to program in a language that allowed this.

Thanks for the encouragement.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Macros and Domain Specific Languages Posted: Jul 10, 2006 11:17 AM
Reply to this message Reply
> You may be interested in:
>
> Eelco Visser, "Program Transformation with Stratego/XT
> Rules, Strategies, Tools, and Systems in Stratego/XT 0.9",
> Domain-Specific Program Generation, Lecture Notes in
> Computer Science, Volume 3016, Springer-Verlag, 2004.
>
> http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-2004/2004-01
> 1.pdf
>
> It could be ideal to implement arbitrary language to CAT

Thanks a lot for the paper!

Emil Cristian Alexandrescu

Posts: 13
Nickname: mkcoos
Registered: Jul, 2006

Re: Macros and Domain Specific Languages Posted: Jul 11, 2006 8:17 AM
Reply to this message Reply
That "macro pre-processor which works as a type-aware pattern matcher" is equivalent with a typed functional language.

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: Macros and Domain Specific Languages Posted: Jul 13, 2006 4:15 PM
Reply to this message Reply
> That "macro pre-processor which works as a type-aware
> pattern matcher" is equivalent with a typed functional
> language.

Could you explain that?

Alexandre Tachard

Posts: 3
Nickname: alextp
Registered: Nov, 2005

Re: Macros and Domain Specific Languages Posted: Jul 13, 2006 4:55 PM
Reply to this message Reply
> > That "macro pre-processor which works as a type-aware
> > pattern matcher" is equivalent with a typed functional
> > language.
>
> Could you explain that?


"typed functional language" == pattern matching on types + recursion == "macro pre-processor which works as a type-aware pattern matcher"
The same way, C++ templates can be seen as some sort of functional language (although not a very good one for general-purpose programming)

Emil Cristian Alexandrescu

Posts: 13
Nickname: mkcoos
Registered: Jul, 2006

Re: Macros and Domain Specific Languages Posted: Jul 13, 2006 5:06 PM
Reply to this message Reply
Alexandre provided the right answer for me.
Thancks, Alexander!

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: Macros and Domain Specific Languages Posted: Jul 14, 2006 6:00 AM
Reply to this message Reply
I still don't understand it...with Cat's macro preprocessor you can transform [f] map [g] map => [f g] map. How would you do that in a typed functional language?

Emil Cristian Alexandrescu

Posts: 13
Nickname: mkcoos
Registered: Jul, 2006

Re: Macros and Domain Specific Languages Posted: Jul 15, 2006 2:28 AM
Reply to this message Reply
Cat is unfinished yet. This is why I can't provide a Cat example. Instead I'll make my point in a fictive typed functional language with reverse polish notation - for staying as consistent with Cat as I can.

Consider "green" and "pass" as types. Therefore "GREEN" and "PASS" must be considerred as those types' instances accordingly.

Let [GREEN PASS]map be [GREEN]map [PASS]map by deffinition.

Red from the left-side to the right, the deffinition is an EXPANSSION rule. It can be applied whenever the programmer used "[GREEN PASS]map" explicitely. In this case it works just like a macro

Red from the right-side to the left, the deffinition is a CONTRACTION rule. It can be applied only in case the compiler finds "[GREEN]map [PASS]map" within the code. In this case this is compiling technique, not a macro expanssion.

In a typed language, one can define
[SNAIL BROWN]map
[GOOD COLD]map
differently, without the risk of confussion; typed languages can allow overloading. This can lead to different expanssion-contraction rules for any combination between arguments' types.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Macros and Domain Specific Languages Posted: Jul 15, 2006 1:03 PM
Reply to this message Reply
> > That "macro pre-processor which works as a type-aware
> > pattern matcher" is equivalent with a typed functional
> > language.
>
> Could you explain that?

Most term rewriting languages, which match patterns and rewrite them, are by their very nature a declarative programming language. Like XSLT for example. You can write loops, conditionals, etc.

However, whether the Cat macro pre-processor is technically a functional language, I don't think so yet, since it lacks the facilities to pass or return functions.

For those interested, the macro language has been broken away from Cat as a separate language, which I am calling "Catnip" for the time being.

I found that it cluttered up the Cat language definition to have the transforms as part of the language proper.

Flat View: This topic has 13 replies on 1 page
Topic: Macros and Domain Specific Languages Previous Topic   Next Topic Topic: Post-JIT Compilation (Compiling at the last possible moment)


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us