source: project/gazette/src/issues/5.wiki @ 20533

Last change on this file since 20533 was 20533, checked in by Alex Shinn, 9 years ago

adding chicken talk

File size: 7.3 KB
Line 
1((title . "Issue 5")
2 (authors "Alex Shinn")
3 (date . 1285489159))
4
5== 0. Introduction
6
7Welcome to issue 5 of the Chicken Gazette!  We're tentatively
8switching the Gazette publication to Monday this week, to give people
9something to read after coming back from the weekend.
10
11== 1. The Hatching Farm - New Eggs & The Egg Repository
12
13This week
14[[http://wiki.call-cc.org/users/mario-domenech-goulart|Mario Domenech Goulart]]
15released a new egg called
16[[http://wiki.call-cc.org/eggref/4/accents-substitute|accents-substitute]]
17to replaced accented Latin characters with either HTML entities or their
18non-accented ASCII equivalents, for when you need to work with ASCII-only
19text.
20
21[[http://wiki.call-cc.org/users/ivan-raikov|Ivan Raikov]]
22has been busy, and in addition to many egg updates has released
23a new egg called [[http://wiki.call-cc.org/egg/cis|cis]]
24(compact integer sets) as a possible alternate to last week's featured egg
25[[http://wiki.call-cc.org/egg/iset|iset]].  It's less efficient
26in terms of time and space, but has a simpler implementation for
27when performance doesn't matter.
28
29Our fearless leader [[http://wiki.call-cc.org/users/felix-winkelmann|Felix]]
30also added a new egg [[http://wiki.call-cc.org/eggref/4/system|system]],
31inspired by the CL defsystem macro.  {{system}} lets you define groups
32of files and their dependencies which can be loaded or compiled, and
33even re-loaded or compiled keeping track of modified files.  Use it
34as a {{make}} alternative in your .setup files, or for rapid development
35in the repl!
36
37== 2. The Core - Bleeding Edge Development
38
39
40
41== 3. Chicken Talk
42
43The exciting news on the mailing list this week was a
44[[http://lists.nongnu.org/archive/html/chicken-users/2010-09/msg00074.html|performance boost]]
45mentioned by [[http://wiki.call-cc.org/users/mario-domenech-goulart|Mario Domenech Goulart]]
46where the [[http://wiki.call-cc.org/eggref/4/awful|awful]]
47web framework ran a benchmark almost 7x faster.  This is
48likely due to a new GC improvement by Felix.
49
50Taylor Venable [[http://lists.nongnu.org/archive/html/chicken-users/2010-09/msg00068.html|brought up an issue]]
51in the new [[http://wiki.call-cc.org/eggref/4/coops|coops]]
52object system involving class redefinition and {{define-method}}
53on a generic not first provided with {{define-generic}}.
54It turns out Chicken will do an implicit {{define-generic}} for
55you as a convenience, but it's probably best to define each
56generic once explicitly.  Also be aware that redefining a
57class will create a completely new class which instances of
58the old class will not belong to.
59
60Richard Hollos [[http://lists.nongnu.org/archive/html/chicken-users/2010-09/msg00066.html|reported an error]]
61compiling on AMD64 Linux, which turned out to be just a chicken and
62egg problem.
63
64Markus Klotzbuecher [[http://lists.nongnu.org/archive/html/chicken-users/2010-09/msg00075.html|provided a patch]]
65for the {{cairo}} egg, showing activity in the graphical
66library front.
67
68Finally Felix just
69[[http://lists.nongnu.org/archive/html/chicken-users/2010-09/msg00083.html|announced]]
70[[http://wiki.call-cc.org/eggref/4/coops|coops]] version 1.0!
71If you've been using {{tinyclos}}, give {{coops}} a try.
72
73== 4. Omelette Recipes - Tips and Tricks
74
75We've got a wide variety of options for parsing in Chicken, from the
76built-in {{read}} and extensions thereon, to regular expressions, to a
77plethora of both specific and general purpose parsing libraries.  This
78week, I want to take a look at one of the general purpose libraries,
79[[http://wiki.call-cc.org/egg/packrat|the packrat egg]] by Tony
80Garnock-Jones.
81
82A packrat parser is a parser for Parsing Expression Grammars (PEGs),
83which is essentially a recursive decent parser with backtracking plus
84memoization to promise a linear time parse.  They look similar to
85Context Free Grammars (CFGs), but are unambiguous by virtue of being
86ordered - the leftmost matching rule is always chosen.  PEGs also
87allow {{and}} and {{not}} rules, which allow them to parse languages
88that can't be described by CFGs.
89
90The
91[[http://bugs.call-cc.org/export/20226/release/4/packrat/doc/packrat.pdf|documentation for packrat]]
92is not too user-friendly, and among other things doesn't include any
93examples of parsing from actual text.  This is because {{packrat}} is
94written to work over abstract streams of tokens, not just text, but
95text is usually what people want to work with when looking at parsers.
96So we'll start by writing a version of the expression parser example
97to work on text.
98
99<enscript highlight="scheme">
100  ;; Start with the base textual generator from the documentation:
101  (define (generator filename port)
102    (let ((ateof #f)
103          (pos (top-parse-position filename)))
104      (lambda ()
105        (if ateof
106            (values pos #f)
107            (let ((x (read-char port)))
108              (if (eof-object? x)
109                  (begin
110                    (set! ateof #t)
111                    (values pos #f))
112                  (let ((old-pos pos))
113                    (set! pos (update-parse-position pos x))
114                    (values old-pos (cons x x)))))))))
115
116  ;; Now define a character-oriented version of the expression parser:
117  (define expr-parser
118    (packrat-parser expr
119      (expr ((a <- mulexp '#\+ b <- mulexp) (+ a b)) ((a <- mulexp) a))
120      (mulexp ((a <- simple '#\* b <- simple) (* a b)) ((a <- simple) a))
121      (simple ((a <- num) a) (('#\( a <- expr '#\)) a))
122      (num ((a <- digits) (string->number (list->string a))))
123      (digits ((a <- digit b <- digits) (cons a b)) ((a <- digit) (list a)))
124      (digit ((a <- '#\0) a) ((a <- '#\1) a) ((a <- '#\2) a)
125             ((a <- '#\3) a) ((a <- '#\4) a) ((a <- '#\5) a)
126             ((a <- '#\6) a) ((a <- '#\7) a) ((a <- '#\8) a)
127             ((a <- '#\9) a))))
128
129  ;; ... and a utility function to parse from strings or ports,
130  ;; and return the semantic results on success or #f on failure:
131  (define (expr-parse x)
132    (let ((g (base-generator->results
133              (generator #f (if (string? x) (open-input-string x) x)))))
134      (let ((res (expr-parser g)))
135        (and (parse-result-successful? res)
136             (parse-result-semantic-value res)))))
137
138  ;; Some examples:
139  (expr-parse "2") => 2
140  (expr-parse "2+2") => 4
141  (expr-parse "2+2*7") => 16
142  (expr-parse "(2+2)*7") => 28
143  (expr-parse "3*4+5*6") => 42
144</enscript>
145
146As you can see, writing the grammar is very natural.  We've chosen to
147compute the values directly in the actions, but could also return them
148as s-expressions, e.g. using {{`(+ ,a ,b)}} to get an AST to work
149with.
150
151The egg is still rather primitive, and is missing some useful features
152such as charsets (which would simplify our "digit" rule greatly), and
153arbitrary predicates, but is definitely something that can be built
154on.  For similar efforts you can search for Scheme "parser
155combinators," which often refer to the same thing without the
156memoization.  A parser combinator project worth checking out is Taylor
157Campbell's [[http://mumble.net/~campbell/darcs/parscheme/|parscheme]].
158
159== 5. About the Chicken Gazette
160
161The Gazette is produced weekly by a volunteer from the Chicken
162community. The latest issue can be found at
163[[http://gazette.call-cc.org]] or you can follow it in your feed
164reader at [[http://gazette.call-cc.org/feed.atom]]. If you'd like to
165write an issue,
166[[http://bugs.call-cc.org/browser/gazette/README.txt|check out the instructions]]
167and come and find us in #chicken on Freenode!
Note: See TracBrowser for help on using the repository browser.