From: Michael Groeneweg
Subject: writing a search-algorithm in (X)Emacs-Lisp
Date:
Message-ID: <8t7r38$efi$1@riker.addcom.de>
Hello Newsgroup,
I have a problem: I need to implement a search-algorithm in Lisp (called
Boyer-Moore, if s.o. wants to know). Searching a text should be quite simple
for (X)Emacs I thougt, so I wanted to program it in Emacs-Lisp. I started
several times now, but don't come to an end. Can s.o. tell me how to start.
Should I first learn using XEmacs in all details or is there a way to start
off programming instantly? Maybe I should first start learning Common
Lisp... I'm really confused. Is there a good (maybe german) tutorial on
s.th. like this? A good book might also be helpful...
Help me! PLEASE!
begin 666 Michael Groeneweg.vcf
M0D5'24XZ5D-!4D0-"E9%4E-)3TXZ,BXQ#0I..D=R;V5N97=E9SM-:6-H865L
M#0I&3CI-:6-H865L($=R;V5N97=E9PT*5$5,.TA/344[5D])0T4Z*# T.3(Q
M*2 V(#$W(#4S#0I414P[0T5,3#M63TE#13HH,#$W,··@.3DU(·@W(#DU#0I!
M1%([2$]-13H[.TMO9V=E=V5G(#<[16UD96X[3FEE9&5R<V%C:'-E;CLR-C<R
M,SM$975T<V-H;&%N9 T*3$%"14P[2$]-13M%3D-/1$E.1SU154]4140M4%))
M3E1!0DQ%.DMO9V=E=V5G(#<],$0],··········@3FEE9&5R<V%C:'-E;B R
M-C<R,STP1#TP041E=71S8VAL86YD#0I8+5=!0BU'14Y$15(Z,@T*55),.FAT
M=' Z+R]W=W<N1W)O96YE=V5G+F1E#0I"1$%9.C$Y-S,Q,3$X#0I%34%)3#M0
M4D5&.TE.5$523D54.DUI8VAA96Q 1W)O96YE=V5G+F1E#0I2158Z,C P,#$P
7,C54,C,T,····@T*14Y$.E9#05)$#0H`
`
end
From: Christian Nyb�
Subject: Re: writing a search-algorithm in (X)Emacs-Lisp
Date:
Message-ID: <87bsw8bfyz.fsf@siteloft.no>
"Michael Groeneweg" <·······@Groeneweg.de> writes:
> I have a problem: I need to implement a search-algorithm in Lisp
> (called Boyer-Moore, if s.o. wants to know).
Make sure you don't look at
<URL:http://www.cs.utexas.edu/users/boyer/ftp/nqthm/> before you have
a working implementation, then.
> Searching a text should be quite simple for (X)Emacs I thougt, so I
> wanted to program it in Emacs-Lisp. I started several times now, but
> don't come to an end. Can s.o. tell me how to start.
For a nice intro to emacs-lisp programming, see
<URL:http://www.delorie.com/gnu/docs/emacs-lisp-intro/>
These days, emacs-lisp is mostly (I hope) used to extend the emacs
environment. It's a quite outdated dialect of lisp. Unless you want
your program to be a truly integrated part of emacs, it's preferrable
to write in Common Lisp instead.
> Should I first learn using XEmacs in all details
I don't think that's neccessary. Do C-h t, or even C-u C-h t German
RET to learn the basics of XEmacs. (C-h t means hold control, type h,
let go of control, type t)
> or is there a way to start off programming instantly? Maybe I should
> first start learning Common Lisp... I'm really confused. Is there a
> good (maybe german) tutorial on s.th. like this? A good book might
> also be helpful... Help me! PLEASE!
Download the free Trial version of Allegro Common Lisp from
www.franz.com. I see that you post from a Windows box - if you opt
for the Windows version, I suggest that you stay away from the
Integrated Development Environment of Allegro until you desire to add
GUI functionality to you app.
Once you've unpacked Allegro, see the directory xeli in Allegro's home
directory. It has instructions on how to set up the connection
between XEmacs and Allegro.
See the website www.alu.org for listings of books on Common Lisp.
have fun,
--
chr
Two books to start with:
ANSI Common Lisp by Grahm
Structure and Interpetation of Computer Programs by ?
Both are supposed to be the best books for starting out. In fact most
undergrad CS courses use them. I suggest using a interactive lisp
interpeter and not xemacs.
Don't expect instant Lisp programming. It's not like C and will take
some time and guts to get good with.
Good luck.
>>>>> "Michael" == Michael Groeneweg <·······@Groeneweg.de> writes:
Michael> Hello Newsgroup, I have a problem: I need to implement a
Michael> search-algorithm in Lisp (called Boyer-Moore, if
Michael> s.o. wants to know). Searching a text should be quite
Michael> simple for (X)Emacs I thougt, so I wanted to program it
Michael> in Emacs-Lisp. I started several times now, but don't
Michael> come to an end. Can s.o. tell me how to start. Should I
Michael> first learn using XEmacs in all details or is there a way
Michael> to start off programming instantly? Maybe I should first
Michael> start learning Common Lisp... I'm really confused. Is
Michael> there a good (maybe german) tutorial on s.th. like this?
Michael> A good book might also be helpful... Help me! PLEASE!
--
.. Nick Papadonis
From: Norbert Koch
Subject: Re: writing a search-algorithm in (X)Emacs-Lisp
Date:
Message-ID: <vzhf60axpf.fsf@lamia.LF.net>
Nick Papadonis <········@yahoo.com> wrote:
> undergrad CS courses use them. I suggest using a interactive lisp
> interpeter and not xemacs.
? XEmacs is an interactive LISP interpreter.
norbert
--
Hey!! Let's watch the' ELEVATOR go UP and DOWN at th' HILTON HOTEL!!
In article <··············@turing.dynodns.net>, Nick Papadonis
<········@yahoo.com> wrote:
> Two books to start with:
>
> ANSI Common Lisp by Grahm
> Structure and Interpetation of Computer Programs by ?
>
> Both are supposed to be the best books for starting out. In fact most
> undergrad CS courses use them. I suggest using a interactive lisp
> interpeter and not xemacs.
>
> Don't expect instant Lisp programming. It's not like C and will take
> some time and guts to get good with.
>
> Good luck.
>
> >>>>> "Michael" == Michael Groeneweg <·······@Groeneweg.de> writes:
>
> Michael> Hello Newsgroup, I have a problem: I need to implement a
> Michael> search-algorithm in Lisp (called Boyer-Moore, if
> Michael> s.o. wants to know). Searching a text should be quite
> Michael> simple for (X)Emacs I thougt, so I wanted to program it
> Michael> in Emacs-Lisp. I started several times now, but don't
> Michael> come to an end. Can s.o. tell me how to start. Should I
> Michael> first learn using XEmacs in all details or is there a way
> Michael> to start off programming instantly? Maybe I should first
> Michael> start learning Common Lisp... I'm really confused. Is
> Michael> there a good (maybe german) tutorial on s.th. like this?
> Michael> A good book might also be helpful... Help me! PLEASE!
If he'd had Macintosh Common Lisp this would help:
(ed 'bm-find-string-in-files)
;-)
--
Rainer Joswig, Hamburg, Germany
Email: ·············@corporate-world.lisp.de
Web: http://corporate-world.lisp.de/
Nick Papadonis <········@yahoo.com> writes:
> Structure and Interpetation of Computer Programs by ?
By Harold Abelson and Gerald Jay Sussman with Julie Sussman.
Sam
From: Erik Naggum
Subject: Re: writing a search-algorithm in (X)Emacs-Lisp
Date:
Message-ID: <3181529242535671@naggum.net>
* "Michael Groeneweg" <·······@Groeneweg.de>
| I have a problem: I need to implement a search-algorithm in Lisp
| (called Boyer-Moore, if s.o. wants to know). Searching a text
| should be quite simple for (X)Emacs I thougt, so I wanted to program
| it in Emacs-Lisp.
The search algorithm in Emacs Lisp (please note the smaller number
of hyphens in English compared to German) is already an adaptation
of Boyer-Moore, both for string and regular expression searches, but
it is naturally more efficient with string searches. (BTW, someone,
somebody, something, etc, are not abbreviated in English, either.)
#:Erik
--
I agree with everything you say, but I would
attack to death your right to say it.
-- Tom Stoppard
From: Reini Urban
Subject: Re: writing a search-algorithm in (X)Emacs-Lisp
Date:
Message-ID: <39fad50f.2418536932@judy>
Michael Groeneweg wrote:
>I have a problem: I need to implement a search-algorithm in Lisp (called
>Boyer-Moore, if s.o. wants to know). Searching a text should be quite simple
>for (X)Emacs I thougt, so I wanted to program it in Emacs-Lisp. I started
>several times now, but don't come to an end. Can s.o. tell me how to start.
>Should I first learn using XEmacs in all details or is there a way to start
>off programming instantly? Maybe I should first start learning Common
>Lisp... I'm really confused. Is there a good (maybe german) tutorial on
>s.th. like this? A good book might also be helpful...
>Help me! PLEASE!
searching is fast enough in emacs.
but just for tutorial purposes:
A colleague implemented boyer-moore string search in autolisp, which has
no strings as vectors, for the stdlib. so it is straightforward to
convert that to elisp. substr is a slow subseq for strings, vector-like
access (aref) would be much faster.
also the shift table is here a dotted pair list, a simple vector would
be better.
http://xarch.tu-graz.ac.at/autocad/stdlib/contrib/boyer-moore-search.lsp
;;; Returns first position of match in str or nil
;;; case-sensitive, no regex, plain substring, first index = 1
;;; Boyer-Moore method by Serge Pashkov, faster than old strpos below
;;; Lisp translation of Modula-2 program from the book
;;; "Algorithms and data structure", N.Wirth, Prentice-Hall, Inc. 1986
;;; see contrib/boyer-moore.lsp for benchmarks and samples
(defun STD-STRPOS (match s / m n i d p c mc mm1)
(setq m (strlen match)
n (strlen s))
(if (<= 1 m n)
(progn
(setq mc (substr match m 1) mm1 (1- m))
(setq d nil i 0)
;; build table of shifts d
(while (< (setq i (1+ i)) m)
(setq d (cons (cons (substr match i 1) (- m i)) d)))
;; search match within string
(setq i m)
(while (<= 1 i n)
(setq i (if (or (/= (setq c (substr s i 1)) mc)
(/= (substr s (- i mm1) m) match))
(+ i (if (setq p (assoc c d)) (cdr p) m))
(- mm1 i)))) ;negative value for ending
;; return position or nil
(if (< i 0) (- i)))))
--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html