I am trying to implement a text file reader. For my application I need
the reader to be fast. I believe that a hand coded lexer might give me
the speed I need.
In C I would implement something like this:
switch (ch)
case 'A': ...
case 'B': ...
default: ...
I tried doing this is lisp with tagbody and an array of
labels:
(tagbody
(go (elt ch tbl))
A
...
B
...
default
...)
But it appears that go does not eval its arguments.
I know about the "case" macro in lisp, but the hyperspec
says that "Each of the normal-clauses is then considered in turn."
Does this mean that the lisp case macro is required to check
each destination key sequentially? Am I going in the wrong direction?
-Ram
On Aug 19, 12:05 am, ·······@gmail.com wrote:
> I am trying to implement a text file reader. For my application I need
> the reader to be fast. I believe that a hand coded lexer might give me
> the speed I need.
Why not just use READ ?
Let it do the scanning/lexing for you. If you need different syntax
you can usually adjust the readtable** so that it works well. (I have
one mucked up so much it returns tokens for java like syntax!)
Anyway, you can try to roll your own, but for the time savings in
programming and speed, I bet you'll have a hard time beating READ.
(If it were me, I'd probably try that first.) For example:
(cl:defpackage #:parser
(:export #:parse))
(in-package #:parser)
(defun a ()
(pprint "saw a"))
(defun b ()
(pprint "saw b"))
(defun foobar ()
(pprint "saw foobar"))
(defun parse (stream)
(let ((*package* (find-package '#:parser)))
(do ((sym (read stream nil stream)
(read stream nil stream)))
((eq sym stream))
(funcall (symbol-function sym)))))
CL-USER> (parser::parse (make-string-input-stream "b a foobar a"))
"saw b"
"saw a"
"saw foobar"
"saw a"
NIL
(yes under the hood there is some kind of hashing from string name to
the symbol table - but read in most implementations is pretty
efficient)
** Let's say it's comma delimited symbols you need to parse (a problem
I just had), you can trivially change the readtable to turn them into
spaces:
(defvar *comma-to-space-readtable*
(let ((*readtable* (copy-readtable nil)))
(set-syntax-from-char #\, #\Space)
*readtable*))
Now you can just bind over *readtable* in parse to change it to the
*comma-to-space-readtable* and change how READ behaves.
Kevin
In article <··············@maple.ramandgita.com>, ·······@gmail.com
wrote:
> I am trying to implement a text file reader. For my application I need
> the reader to be fast. I believe that a hand coded lexer might give me
> the speed I need.
>
> In C I would implement something like this:
>
> switch (ch)
> case 'A': ...
> case 'B': ...
> default: ...
>
> I tried doing this is lisp with tagbody and an array of
> labels:
>
> (tagbody
> (go (elt ch tbl))
> A
> ...
> B
> ...
> default
> ...)
>
> But it appears that go does not eval its arguments.
>
> I know about the "case" macro in lisp, but the hyperspec
> says that "Each of the normal-clauses is then considered in turn."
>
> Does this mean that the lisp case macro is required to check
> each destination key sequentially? Am I going in the wrong direction?
CASE is a macro. You can expand it and see what the implementation
does. Usually I would expect that it expands into
some form that uses COND.
It could be that some clever implementation would
optimize it for some cases, but I have no idea which would do it.
You would need to ask the implementor(s) or macroexpand (or
even disassemble) the code.
the typical Lisp way would do something like this:
(funcall (aref table (char-code (read-char))) ...)
Where the table is an array of functions.
Isn't that fast enough?
>
> -Ram
--
http://lispm.dyndns.org/
·······@gmail.com writes:
> I am trying to implement a text file reader. For my application I need
> the reader to be fast. I believe that a hand coded lexer might give me
> the speed I need.
>
> In C I would implement something like this:
>
> switch (ch)
> case 'A': ...
> case 'B': ...
> default: ...
Notice that C compilers can and do generate successive tests,
depending on the set of constants, and the optimization level.
So if you don't care what code is generated in C, why do you care in
Lisp? Just use CASE and trust the compiler writers.
> I tried doing this is lisp with tagbody and an array of
> labels:
>
> (tagbody
> (go (elt ch tbl))
> A
> ...
> B
> ...
> default
> ...)
>
> But it appears that go does not eval its arguments.
>
> I know about the "case" macro in lisp, but the hyperspec
> says that "Each of the normal-clauses is then considered in turn."
>
> Does this mean that the lisp case macro is required to check
> each destination key sequentially? Am I going in the wrong direction?
This looks good enough a table for me:
C/USER[154]> (disassemble (compile nil (lambda (x) (declare (type character x)) (case x ((#\0 #\1 #\2 #\3) 'digit) ((#\a #\b #\c #\d) 'letter) (otherwise 'unknown)))))
Disassembly of function NIL
(CONST 0) = #S(HASH-TABLE :TEST EXT:STABLEHASH-EQ (#\d . 4) (#\c . 4) (#\b . 4) (#\a . 4) (#\3 . 1) (#\2 . 1) (#\1 . 1) (#\0 . 1))
(CONST 1) = DIGIT
(CONST 2) = LETTER
(CONST 3) = UNKNOWN
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
11 byte-code instructions:
0 (LOAD 1)
1 (JMPHASH 0 L10 #1=L4 #1# #1# #1# #2=L7 #2# #2# #2#)
4 L4
4 (CONST 1) ; DIGIT
5 (SKIP&RET 2)
7 L7
7 (CONST 2) ; LETTER
8 (SKIP&RET 2)
10 L10
10 (CONST 3) ; UNKNOWN
11 (SKIP&RET 2)
NIL
Otherwise, if you happen to use an implementation that doesn't do
that, well, why don't you just do what you say you want to do?
C/USER[159]> (disassemble
(compile nil
(lambda (x)
(declare (fixnum x))
(if (<= 0 x 3)
(funcall (aref #.(vector (lambda () 'zero) (lambda () 'one) (lambda () 'two)) x))
(funcall (lambda () 'out-of-bounds))))))
Disassembly of function NIL
(CONST 0) = 0
(CONST 1) = 3
(CONST 2) = #(#<FUNCTION :LAMBDA NIL 'ZERO> #<FUNCTION :LAMBDA NIL 'ONE> #<FUNCTION :LAMBDA NIL 'TWO>)
(CONST 3) = OUT-OF-BOUNDS
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
12 byte-code instructions:
0 (CONST&PUSH 0) ; 0
1 (LOAD&PUSH 2)
2 (CONST&PUSH 1) ; 3
3 (CALLSR&JMPIF 2 49 L10) ; <=
7 (CONST 3) ; OUT-OF-BOUNDS
8 (SKIP&RET 2)
10 L10
10 (CONST&PUSH 2) ; #(# # #)
11 (LOAD&PUSH 2)
12 (CALLSR&PUSH 1 1) ; AREF
15 (FUNCALL 0)
17 (SKIP&RET 2)
NIL
C/USER[160]>
--
__Pascal Bourguignon__
···@informatimago.com (Pascal J. Bourguignon) writes:
>
> Otherwise, if you happen to use an implementation that doesn't do
> that, well, why don't you just do what you say you want to do?
>
>
> C/USER[159]> (disassemble
> (compile nil
> (lambda (x)
> (declare (fixnum x))
> (if (<= 0 x 3)
> (funcall (aref #.(vector (lambda () 'zero) (lambda () 'one) (lambda () 'two)) x))
> (funcall (lambda () 'out-of-bounds))))))
>
Thank you! It never occurred to me to have an array of functions! This will
work just fine for me.
-Ram
In article <··············@maple.ramandgita.com>, ····@sonic.net wrote:
> Thank you! It never occurred to me to have an array of functions! This will
> work just fine for me.
Interesting. When I saw your subject line, I assumed you were asking
about an array of functions. That's what "table-based control flow"
sounds like to me.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***