source: proto/s2k/trunk/demo/grep/grep.py @ 4053

Last change on this file since 4053 was 3748, checked in by ksherdy, 6 years ago

Removed import statements from compilable.

File size: 4.9 KB
Line 
1#
2# grep - A very simple example to demonstrate 'fixed-string' grep with parallel bit streams.
3#
4#        This prototypes demonstrates a compilable prototype with
5#        minimal reliance on complementary hand-written template code.
6#        In addition, this examples draws attention to missing features in the Pablo
7#        language which prevent the elimination of hand-written templates.
8#
9# Ken Herdy
10# July 29, 2013
11#
12# grep program flow
13#
14# StreamInput' -> Transpose' -> ClassifyBytes -> Match -> MatchLines -> FilterMatchLines -> StreamOutput'
15#                                                                 
16# grep -c program flow
17#
18# ... MatchLines -> CountLines -> StreamOutput''
19#
20# grep | wc -l program flow
21#
22# ... StreamOutput' -> Transpose' -> MatchLF -> PopCount -> StreamOutPut''
23#   
24# ' marks denote missing functionality which prevents
25# the direct compilation of Pablo code to C/C++ code
26#
27# Observations:
28#
29# 1) Both sequential and bit parallel computations are performed.
30#   
31#    Examples include:
32#       
33#          a) sequential iteration over the matches and line feed streams in the 'Match' routine
34#          b) sequential and/or parall_matchedel output of marked lines in the 'CompressLines' / 'WriteLines' routine   
35#
36# 2) Creation of spans are problematic at the start of an input data stream.
37#
38#    A solution approach to this problem is to:
39#               
40#    a) formalize the meaning of the expressions of the language as expressions
41#    operating on sequences (streams) of 2^k bit data items both preceded and
42#    succeeded by an unbounded number of 2^k with zero value items.
43#
44#    b) define the 'line starts' stream as line_starts = ~Adv(0) ^ ~0
45#               
46# 3) Options such as -c represent separate branches in the underlying stream graph.
47#
48# 4) Support of pipes and filter type applications requires subgraph
49#    composition but only a single transposition step.
50#    As in SPL a composite program structure could support
51#    UNIX-style pipe and filters archicture for
52#    parall_matchedel bit stream apps,
53#    e.g. composite { graph { /* program flow */ } }
54#
55class Basis_bits():
56        bit_0 = 0
57        bit_1 = 0
58        bit_2 = 0
59        bit_3 = 0
60        bit_4 = 0
61        bit_5 = 0
62        bit_6 = 0
63        bit_7 = 0
64
65class Lex():
66        a  = 0
67        p  = 0
68        l  = 0
69        e  = 0
70        LF = 0
71
72class Output():
73        match_follows   = 0
74        lines                   = 0
75        line_starts             = 0
76        line_ends               = 0
77       
78def ClassifyBytes(basis_bits, lex): 
79        temp1 = (basis_bits.bit_1 &~ basis_bits.bit_0)
80        temp2 = (basis_bits.bit_2 &~ basis_bits.bit_3)
81        temp3 = (temp1 & temp2)
82        temp4 = (basis_bits.bit_4 | basis_bits.bit_5)
83        temp5 = (basis_bits.bit_7 &~ basis_bits.bit_6)
84        temp6 = (temp5 &~ temp4)
85        lex.a = (temp3 & temp6)
86        temp7 = (basis_bits.bit_2 & basis_bits.bit_3)
87        temp8 = (temp1 & temp7)
88        temp9 = (basis_bits.bit_6 | basis_bits.bit_7)
89        temp10 = (temp4 | temp9)
90        lex.p = (temp8 &~ temp10)
91        temp11 = (basis_bits.bit_4 & basis_bits.bit_5)
92        temp12 = (temp11 &~ temp9)
93        lex.l = (temp3 & temp12)
94        temp13 = (basis_bits.bit_5 &~ basis_bits.bit_4)
95        temp14 = (temp13 & temp5)
96        lex.e = (temp3 & temp14)
97        temp15 = (basis_bits.bit_0 | basis_bits.bit_1)
98        temp16 = (basis_bits.bit_2 | basis_bits.bit_3)
99        temp17 = (temp15 | temp16)
100        temp18 = (basis_bits.bit_4 &~ basis_bits.bit_5)
101        temp19 = (basis_bits.bit_6 &~ basis_bits.bit_7)
102        temp20 = (temp18 & temp19)
103        lex.LF = (temp20 &~ temp17)
104       
105def Match(lex, output):
106    # Mark _follows.
107        cursor = pablo.Advance(lex.a)
108        cursor = pablo.Advance(cursor & lex.p)
109        cursor = pablo.Advance(cursor & lex.p)
110        cursor = pablo.Advance(cursor & lex.l)
111        cursor = pablo.Advance(cursor & lex.e)
112        output.match_follows = cursor
113
114def MatchLines(lex, output):
115       
116        all_line_starts   = pablo.ScanToFirst(~lex.LF) | (pablo.Advance(lex.LF) &~ lex.LF)
117        all_line_ends     = lex.LF
118
119        last_line_start   = pablo.ScanToFirst(all_line_starts) 
120        cursor            = last_line_start
121
122        while(pablo.inFile(cursor)):
123               
124                if(cursor & all_line_starts):
125                        last_line_start = cursor
126                       
127                if(cursor & output.match_follows):
128                        cursor = pablo.ScanTo(cursor, lex.LF)
129                        output.lines |= pablo.InclusiveSpan(last_line_start, cursor) # LF | match
130               
131                cursor = pablo.AdvanceThenScanTo(cursor, all_line_starts | output.match_follows)
132
133        output.line_starts = output.lines & all_line_starts
134        output.line_ends   = pablo.ScanTo(output.line_starts, output.lines & all_line_ends)
135
136###
137### <-- Demo only for now.
138###
139### def FilterMatchLines(data, output):
140###     output.byte_data = pablo.filter_bytes(data, ~(pablo.Advance(output.lines) | output.lines))
141        # output.byte_data = pablo.filter_bytes(data, ~output.lines) # a line has a LF
142
143
144### def CountLines(lex, output):
145        # return pablo.PopCount(pablo.MatchStar(output.lines, ~lex.LF) & lex.LF)
146###     return pablo.PopCount(pablo.Advance(output.lines) & lex.LF)
147        # return pablo.PopCount(output.lines & lex.LF) # a line has a LF
148
149# write out template considers end positions
150
151def Main(basis_bits, lex, output):
152        Transpose(byte_data, basis_bits)
153        ClassifyBytes(basis_bits, lex)
154        Match(lex, output)
155        MatchLines(lex, output)
156
157    ### FilterMatchLines(data, output)
158    ### WriteStreamOutput(Output)
159
160        ### if(options.count):
161        ### CountLines(lex, output))
162               
Note: See TracBrowser for help on using the repository browser.