I've implemented a Lindenmayer System generator, with postscript output.
A L-System is a fractal, which can be used to describe plants. The
program implements the commands described here:
http://www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html
Some example outputs (converted to PDF, because it is shorter)
http://www.frank-buss.de/tmp/bush.pdf
http://www.frank-buss.de/tmp/snow.pdf
http://www.frank-buss.de/tmp/dragon.pdf
The code is below. But it is too slow. I think it is the function
"starts-with" and the string handling, perhaps it could be faster with
lists, because then the substitute step could be implemented faster.
How can I profile the program? I know the "time"-macro, but would be
nice to have an utility, which writes for every function or every line
the time after program termination.
And it would be nice to test new rules interactive, without the need to
produce a postscript file, first. Is this possible with LTK or some other
GUI interface?
Another idea: Enhancing it to 3D output and color, like this program:
http://home.wanadoo.nl/laurens.lapre/lparser.htm
(defun starts-with (string search start)
"Returns true, if the string 'search' is at 'start' in 'string'."
(let ((string-len (length string))
(search-len (length search)))
(if (> (+ start search-len) string-len)
nil
(equal (subseq string start (+ start search-len)) search))))
(defun search-longest (rules string start)
"Returns the successor and predecessor length, if a predecessor
is found in 'string' at 'start'. Returns the longest match."
(let ((found-successor nil)
(found-predecessor-length 0))
(loop for (predecessor . successor) in rules do
(when (starts-with string predecessor start)
(let ((predecessor-length (length predecessor)))
(when (>= predecessor-length found-predecessor-length)
(setq found-predecessor-length predecessor-length)
(setq found-successor successor)))))
(values found-successor found-predecessor-length)))
(defun apply-rules (rules axiom)
"Returns the next iteration, starting with the string in 'axiom'."
(let ((result ""))
(loop for i from 0 to (1- (length axiom)) do
(multiple-value-bind (successor predecessor-length)
(search-longest rules axiom i)
(if successor
(progn
(setq result (concatenate 'string result successor))
(setq i (1- (+ i predecessor-length))))
(progn
(setq result (concatenate 'string result (subseq axiom i (1+ i))))))))
result))
(defun l-system (rules axiom depth)
"Returns 'depth' iterations, starting with 'axiom' and applying the 'rules'."
(let ((result axiom))
(loop repeat depth do
(setq result (apply-rules rules result)))
result))
(defun forward (point len angle)
"Returns a new point by starting from 'point' and adding the polar coordinates 'len' and 'angles'."
(let ((x (car point))
(y (cdr point))
(rad (* (/ (coerce pi 'single-float) 180.0) angle)))
(cons (+ x (* (sin rad) len)) (+ y (* (cos rad) len)))))
(defun do-l-system (commands len angle fun)
"Calls 'fun x0 y0 x1 y1' for every command in the 'commands' string."
(let ((point-stack '())
(angle-stack '())
(current-point '(0e0 . 0e0))
(current-angle 0e0))
(loop for i from 0 to (1- (length commands)) do
(let ((command (elt commands i)))
(cond ((eq command #\f)
(setq current-point (forward current-point len current-angle)))
((eq command #\F)
(let ((next-point (forward current-point len current-angle)))
(funcall fun (car current-point) (cdr current-point) (car next-point) (cdr next-point))
(setq current-point next-point)))
((eq command #\+)
(setq current-angle (+ current-angle angle)))
((eq command #\-)
(setq current-angle (- current-angle angle)))
((eq command #\[)
(push current-point point-stack)
(push current-angle angle-stack))
((eq command #\])
(setq current-point (pop point-stack))
(setq current-angle (pop angle-stack))))))))
(defun postscript-l-system (rules axiom angle depth)
"Calculates and prints a Lindenmayer System as postscript."
(format t "500 500 scale~%")
(format t ".1 .1 translate~%")
(format t "0 setlinewidth~%")
(let ((commands (l-system rules axiom depth))
(min-x 1e30)
(min-y 1e30)
(max-x -1e30)
(max-y -1e30))
(do-l-system commands 1 angle
(lambda (x0 y0 x1 y1)
(when (< x0 min-x) (setq min-x x0))
(when (< y0 min-y) (setq min-y y0))
(when (< x1 min-x) (setq min-x x1))
(when (< y1 min-y) (setq min-y y1))
(when (> x0 max-x) (setq max-x x0))
(when (> y0 max-y) (setq max-y y0))
(when (> x1 max-x) (setq max-x x1))
(when (> y1 max-y) (setq max-y y1))))
(let* ((len (float (/ (max (- max-y min-y) (- max-x min-x)))))
(min-x (* min-x len))
(min-y (* min-y len)))
(do-l-system commands len angle
(lambda (x0 y0 x1 y1)
(format t "~D ~D moveto ~D ~D lineto~%" (- x0 min-x) (- y0 min-y) (- x1 min-x) (- y1 min-y))))))
(format t "stroke~%")
(format t "showpage~%"))
;;; dragon, needs some minutes to calculate with depth 16
; (postscript-l-system '(("FL"."FL+FR+") ("FR"."-FL-FR")) "FL" 90 16)
;;; snowflake
; (postscript-l-system '(("F"."F+F--F+F")) "F--F--F" 60 7)
;;; bush
; (postscript-l-system '(("F"."FF-[-F+F+F]+[+F-F-F]")) "+F" 23 5)
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> [...]
> The code is below. But it is too slow. I think it is the function
> "starts-with" and the string handling, perhaps it could be faster with
> lists, because then the substitute step could be implemented faster.
> [...]
> (defun starts-with (string search start)
> "Returns true, if the string 'search' is at 'start' in 'string'."
> (let ((string-len (length string))
> (search-len (length search)))
> (if (> (+ start search-len) string-len)
> nil
> (equal (subseq string start (+ start search-len)) search))))
Use STRING= or STRING-EQUAL, they both take start and end arguments
for each string.
---Vassil.
--
Vassil Nikolov <········@poboxes.com>
Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.
In article <············@newsreader3.netcologne.de>,
Frank Buss <··@frank-buss.de> wrote:
> I've implemented a Lindenmayer System generator, with postscript output.
> A L-System is a fractal, which can be used to describe plants. The
> program implements the commands described here:
>
> http://www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html
>
> Some example outputs (converted to PDF, because it is shorter)
>
> http://www.frank-buss.de/tmp/bush.pdf
> http://www.frank-buss.de/tmp/snow.pdf
> http://www.frank-buss.de/tmp/dragon.pdf
>
> The code is below. But it is too slow. I think it is the function
> "starts-with" and the string handling, perhaps it could be faster with
> lists, because then the substitute step could be implemented faster.
>
> How can I profile the program? I know the "time"-macro, but would be
> nice to have an utility, which writes for every function or every line
> the time after program termination.
>
> And it would be nice to test new rules interactive, without the need to
> produce a postscript file, first. Is this possible with LTK or some other
> GUI interface?
Can't say I did much. ;-)
(in-package "CLIM-USER")
(defun clim-l-system (rules axiom angle depth &optional (stream *standard-output*))
(with-room-for-graphics (stream)
(with-scaling (stream 500 500)
(let ((commands (l-system rules axiom depth))
(min-x 1e30)
(min-y 1e30)
(max-x -1e30)
(max-y -1e30))
(do-l-system commands 1 angle
(lambda (x0 y0 x1 y1)
(when (< x0 min-x) (setq min-x x0))
(when (< y0 min-y) (setq min-y y0))
(when (< x1 min-x) (setq min-x x1))
(when (< y1 min-y) (setq min-y y1))
(when (> x0 max-x) (setq max-x x0))
(when (> y0 max-y) (setq max-y y0))
(when (> x1 max-x) (setq max-x x1))
(when (> y1 max-y) (setq max-y y1))))
(let* ((len (float (/ (max (- max-y min-y) (- max-x min-x)))))
(min-x (* min-x len))
(min-y (* min-y len)))
(do-l-system commands len angle
(lambda (x0 y0 x1 y1)
(draw-line* stream (- x0 min-x) (- y0 min-y) (- x1 min-x) (- y1 min-y)))))))))
http://lispm.dyndns.org/lisp/pics/lindenmayer.jpg
Rainer Joswig <······@lisp.de> wrote:
> (in-package "CLIM-USER")
CLIM looks interesting, I like the integration with text and graphic output
in the command window, but if I want to develop applications with native
look-and-feel, can I use it for this purpose? Has it advanced controls,
like the ones you find in Java Swing, like JTable, JTree, JTabbedPane,
JToolBar and standard dialogs, like JColorChooser, JFileChooser and
JOptionPane?
On the LispWorks site they say it is primarily for legacy support and you
should use CAPI:
http://www.lispworks.com/products/clim.html
Of course, they want to sell their product, but if CAPI is a good library,
maybe I'll use it.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> Rainer Joswig <······@lisp.de> wrote:
>
>> (in-package "CLIM-USER")
>
> CLIM looks interesting, I like the integration with text and graphic output
> in the command window, but if I want to develop applications with native
> look-and-feel, can I use it for this purpose?
Yes. That is the whole point of gadgets.
http://www.stud.uni-karlsruhe.de/~unk6/clim-spec/30-1.html
> Has it advanced controls,
> like the ones you find in Java Swing, like JTable, JTree, JTabbedPane,
> JToolBar and standard dialogs, like JColorChooser, JFileChooser and
> JOptionPane?
The whole system is much more abstract than that. You have tables,
graphs (any type, not just trees), and you can present commands in a
pane. Tabbed panes aren't standard that I know of, but they should be
easy to implement (preference dialogs never were that complicated at
that time: you'd probably have something more like emacs's customize).
Dialogs are really implemented as dialogs in CLIM. You do an
ACCEPTING-VALUES and write the code as a dialog with the user. If the
look-and-feel wants to, it can have all the acceptors in one pane and
let you enter them in any order.
> On the LispWorks site they say it is primarily for legacy support and you
> should use CAPI:
>
> http://www.lispworks.com/products/clim.html
>
> Of course, they want to sell their product, but if CAPI is a good library,
> maybe I'll use it.
I was under the impression that LW's CLIM used CAPI under the hood as a
toolkit.
I don't know that CAPI tries to offer all that CLIM does, and it's not a
portable standard or abstract over different types of interface devices afaik.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Frank Buss <··@frank-buss.de> wrote in message news:<············@newsreader3.netcologne.de>...
> Rainer Joswig <······@lisp.de> wrote:
>
> > (in-package "CLIM-USER")
>
> CLIM looks interesting, I like the integration with text and graphic output
> in the command window,
Yeah, but what you saw is just a only a tiny bit of what would be
possible with the Listener (like making everything of the graphic
mouse sensitive, adding commands to draw the graphics, ...).
> but if I want to develop applications with native
> look-and-feel, can I use it for this purpose? Has it advanced controls,
> like the ones you find in Java Swing, like JTable, JTree, JTabbedPane,
> JToolBar and standard dialogs, like JColorChooser, JFileChooser and
> JOptionPane?
CLIM is supposed to be to sit on top of a native GUI library. So you
have some support to use native gadgets. Since CLIM
has been defined, GUIs have changed and thus CLIM lacks support
for some newer stuff.
> On the LispWorks site they say it is primarily for legacy support and you
> should use CAPI:
>
> http://www.lispworks.com/products/clim.html
>
> Of course, they want to sell their product, but if CAPI is a good library,
> maybe I'll use it.
LispWorks wants you to use CAPI. CAPI may support some newer GUI
facilities (though it also lacks a SOME) and
it is also cross-platform (like CLIM) on Windows, X11/Motif and Mac OS / Aqua.
CAPI is the supported GUI library for LispWorks - and only for LispWorks
(if we forget about Liquid CL for a moment).
Since the closed-source CLIM implementation itself was kind of dead
end (though vendors - Xanalys, Franz and Digitool - still support
it kind of), a new implementation of CLIM (McCLIM) is in the works.
It currently runs on X11 and a new backend of Mac OS X / Cocoa is
under development. It is still (pre-) Alpha, but some applications
are already possible with it - it currently lacks a native Windows
backend. I guess it will take another two to three years to improve it,
but that is surely a fun project for everybody interested in
libraries for graphical user interfaces.
http://clim.mikemac.com/ and http://mcclim.cliki.net/index
Frank Buss <··@frank-buss.de> wrote in message news:<············@newsreader3.netcologne.de>...
> Rainer Joswig <······@lisp.de> wrote:
>
> > (in-package "CLIM-USER")
>
> CLIM looks interesting,
Another notable CLIM feature is the capability to create
Postscript from CLIM drawing commands:
(defun postscript-clim-l-system (rules axiom angle depth &optional
(file "/tmp/test.ps"))
(with-open-file (file-stream file :direction :output)
(with-output-to-postscript-stream (stream file-stream)
(clim-l-system rules axiom angle depth stream))))
This makes it possible to use all the nice high-level drawing
commands from Lisp and either display it on screen or
generate Postscript from the same code.
Frank Buss <··@frank-buss.de> writes:
> CLIM looks interesting, I like the integration with text and graphic output
> in the command window, but if I want to develop applications with native
> look-and-feel, can I use it for this purpose? Has it advanced controls,
> like the ones you find in Java Swing, like JTable, JTree, JTabbedPane,
Others in this thread have already answered most of your questions.
Let me just add that I have seen CLIM code for creating something
similar to a tree gadget (caveat: I'm not familiar with JTree).
> JToolBar and standard dialogs, like JColorChooser, JFileChooser and
> JOptionPane?
CLIM provides standard dialogs for file selection and user
notification.
> On the LispWorks site they say it is primarily for legacy support and you
> should use CAPI:
The attitude of vendors may be changed by the interests and requests
of customers.
I personally like the ideas behind CLIM. As for its perceived
vintage/legacy status, I think it is a living testimony of some of the
best software ideas from the Lisp Machines.
CLIM makes it still possible to experiment with those ideas now, on
current hardware, and build on them. Thanks to McCLIM, many Lispers
who use Unix/Mac OS X have the opportunity of being exposed to such
ideas.
I'm doing my best to spread the voice about CLIM. This is one of the
main motivations for the blog I have started recently:
Lisp Propulsion Laboratory log
http://www.paoloamoroso.it/log
Paolo
--
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Recommended Common Lisp libraries/tools (Google for info on each):
- ASDF/ASDF-INSTALL: system building/installation
- CL-PPCRE: regular expressions
- UFFI: Foreign Function Interface
What is the lisp you are using. There are nice profilers in allegro and
lispworks.
There is also metering in clocc that should do what you wan't.
The concatenate part in apply rules looks like the bottleneck, this copies
the results string again and again.
salud2
Karsten
"Frank Buss" <··@frank-buss.de> wrote in message
·················@newsreader3.netcologne.de...
> How can I profile the program? I know the "time"-macro, but would be
> nice to have an utility, which writes for every function or every line
> the time after program termination.
"Karsten Poeck" <························@wanadoo.es> wrote:
> What is the lisp you are using. There are nice profilers in allegro
> and lispworks.
I'm using CLISP, but perhaps I'll buy LispWorks. I've tried both and they
are both powerful, but I like the IDE of LispWorks more and there are no
licence costs for standalone redistributables, which I need for my
customers.
> There is also metering in clocc that should do what you wan't.
nice collection, thanks, I've bookmarked it.
> The concatenate part in apply rules looks like the bottleneck, this
> copies the results string again and again.
yes, this was the bottleneck, I've changed it to MAKE-STRING for every
iteration and REPLACE within the iteration. Now the Dragon Curve is
calculated in 16 seconds instead of 15 minutes!
The new code, with some more examples:
http://www.frank-buss.de/tmp/lsystem.lisp.txt
BTW: Did you know, that the Penrose Tiling can be implemented with an L-
System? A bit offtopic: is there a nice rule for hexagonal and square
tilings, which doubles the size for each iteration?
http://www.frank-buss.de/tmp/penrose.png
I think the LTK solution is nice, too, but I've found another easy
solution by simply redirecting the output to a file and calling
ghostview, which is available for windows, too.
Of course, I didn't know l-lisp, which is much better than my program :-)
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
(message (Hello 'Frank)
(you :wrote :on '(Sun, 29 Aug 2004 01:53:56 +0000 (UTC)))
(
FB> Another idea: Enhancing it to 3D output and color, like this
FB> program:
FB> http://home.wanadoo.nl/laurens.lapre/lparser.htm
by the way, have you seen l-lisp?
http://www.ii.uib.no/~knute/lsystems/llisp.html
it works under cmucl, can render using opengl and has very advanced rules..
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
(prin1 "Jane dates only Lisp programmers"))