close

Вход

Забыли?

вход по аккаунту

?

Compile Time Abstraction Techniques for the D Programming

код для вставкиСкачать
Compile Time Abstraction
Techniques for the D
Programming Language
Benjamin Shropshire
Abstraction
•What
•Why
•When
•How
What & Why
• What:
Isolation of lower level complexity
– Distillation of Intent
– Removal of redundancy
• Why:
Saving Time
– Programming time
– Maintenance time
– User time
Benjamin Shropshire
3
When to use Abstractions?
• Let the computer do what it is good at.
• Abstract where abstraction is a good fit
Benjamin Shropshire
4
When to Not use Abstractions?
• If the abstraction doesn't fit, don't force it.
• Beware of premature optimizations.
– Code speed
– Coding speed
– Test optimizations.
Benjamin Shropshire
5
Compile time processing
•Nesting Templates
•Chained Recursion
•Nested Tuples
Nesting Templates
template Remove(R...)
{
// 0 based indices of the
Define two lists
// Tuple parts to remove
two templates
template From(A...)
{
// the tuple to remove stuff from
static if(A.length != 0)
{
// test if last item in A is to be removed
static if(isIn!(A.length-1, R))
{
alias From!(A[0..$-1]) From;
}
else
{
alias T!(From!(A[0..$-1]), A[$-1]) From;
}
}
else
{
alias T!() From;
}
}
}
Benjamin Shropshire
using
7
Nesting Templates
• Multiple Tuples
• Useful naming
Remove!(1,3,5).From!(ubyte,byte,ushort,short,uint,int)
// same as
T!(ubyte,ushort,uint)
Benjamin Shropshire
8
Chained Recursion
template SetOfAction()
{
alias .Loop!(Effect).Range Range;
alias .Loop!(Effect).Drop Drop;
alias Effect End;
}
template Range(int start, int stop)
{
alias range!(start, stop) Effect;
mixin SetOfAction!();
}
template Loop(L...)
{
template Range(int start, int stop)
{
alias T!(L,range!(start, stop)) Effect;
mixin SetOfAction!();
}
template Drop(A...)
{
alias drop!(A).from!(L) Effect;
mixin SetOfAction!();
}
}
Benjamin Shropshire
Starting point
Introduce alias to
nested templates
Nested templates that
do something and
then also use mixin
9
Chained Recursion
• Object Oriented style design
• Domain Specific Languages
• Closer to what is wanted
Range!(1,5).
Range!(7,8).
Range!(80,90).
Drop!(
Range!(83,87).End
).End
T!(1,2,3,4,5,7,8,80,81,82,88,89,90)
Benjamin Shropshire
10
Nested Tuples
Template For(T...)
{
struct Ues(A...)
{
static alias T Type;
static alias V value
}
}
Alias tuples inside of strut
alias For!(int, float).Use!(5, 3.1415) map;
foreach(I,T; map.Type)
{
writef(“%s\n”, cast(T)map.Value[I]);
}
Benjamin Shropshire
11
Nested Tuples
•
Use structs
–
–
Alias in templates don’t work
foreach works well on types
Benjamin Shropshire
12
All Together Now
•Compile Time Parsing
•Compile Time Parser Generation
Compile Time Parsing
• Reading Data
• Building tree
Benjamin Shropshire
14
Compile Time Parsing
/// B ::= DB | D ;
struct B(char[] str)
{
private alias D!(str) d;
static if(d.match)
{
static const bool match = true;
alias B!(d.rem) b;
static if(b.match)
{
static alias T!(d,b. Content) Content;
static const char[] rem = b.rem;
}
else
{
static alias T!(d) Content;
static const char[] rem = d.rem;
}
}
else
static const bool match = false;
}
Benjamin Shropshire
Attempt to parse D
Attempt to parse B
Build tuple of D’s
Record unused input
15
Compile Time Parsing
/// A ::= BCA | B ;
struct A(char[] str)
{
private alias B!(str) b;
static if(b.match)
{
static const bool match = true;
private alias C!(b.rem) c;
static if(c.match)
{
private alias A!(c.rem) a;
static if(a.match)
{
static alias T!(b,a.Content) Content;
static const char[] rem = a.rem;
}
else
{
static alias T!(b) Content;
static const char[] rem = b.rem;
}
}
else
{
static alias T!(b) Content;
static const char[] rem = b.rem;
}
}
else
static const bool match = false;
}
Benjamin Shropshire
Found BCA
Found BC failed on A, so parsing only B
Found B failed on C, so parsing only B
Failed on B, so failing
16
Compile Time Parsing
alias A!("DDCDDCDDDCDC") pattern;
foreach(i,T;pattern.cont)
{
writef("Start B # %d\n",i);
foreach(j,U;T.cont)
writef(" D # %d\n",j);
writef("Stop B # %d\n",i);
}
writef("remaining %s\n",pattern.rem);
/* output
Start B # 0
D # 0
D # 1
Stop B # 0
Start B # 1
D # 0
D # 1
Stop B # 1
Start B # 2
D # 0
D # 1
D # 2
Stop B # 2
Start B # 3
D # 0
Stop B # 3
remaining C
*/
Benjamin Shropshire
17
Compile Time Parser Generation
• Parse grammar
• Select production to instance
• Try each disjunction
– Try each part
• Recurs to other productions
• Record checkpoints
• Backtrack through checkpoints on failure
Benjamin Shropshire
18
Compile Time Parser Generation
Grammar(char[] grammar)
{
alias ParseGrammar(grammar) parsedGrammar;
ParseRule(rule)(tokens)
{
alias parsedGrammar.Get(rule) thisRule;
checkpoint = tokens.position;
options: foreach(option; thisRule)
{
tokens.position = checkpoint
foreach(index, clause; option)
{
ret[index] = ParseRule!(clause)(tokens);
if(ret[index].failed)
continue options;
}
return Action!(option.Action)(ret);
}
}
}
Benjamin Shropshire
19
Compile Time Abstraction Techniques for the D
Programming Language
Benjamin Shropshire
Special Thanks to:
•
•
Dr. Robert Hiromoto
Michael Hewitt
•
•
•
Dr. David Buehler
Dr. Geoffrey Shropshire
Eric Hewitt
Benjamin Shropshire
20
Документ
Категория
Презентации
Просмотров
1
Размер файла
114 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа