The accumulator problem that Graham writes about is a silly problem. It
is designed to show how Lisp shines in one particular area. There are
quite a few things that a language requires to be able to write that
problem to his specifications. Each language typically has a "catch"
program that shows extremes. Take a look at quicksort in Haskell. Or
the washing machine example on Forth, Inc.'s website.
My two favorite languages to program in are Forth and Lisp. Both are
wonderful languages. Neither could replace the other in what they do
best (I would never think of using another language for embedded
programming other than Forth). However, both languages are exception
for one shear fact: they are extensible. This cannot be stressed
enough.
IMHO, the "aha" moment with any language or concept happens when you
actually force yourself to use it. My "aha" moment with OOP occured
when I was a teenager writing my first MUD. I realized that a bag was a
container, and so is a room, and so is a living object... and a player
is a living object, and so is a monster.
With Lisp, I really had two "aha" moments -- both occurred during the
same project, but at different times. The project (which I hope to be
publishing on the web soon) was a regular expression parser. It started
out as a C in Lisp piece of code. But as I kept refining it, and
realizing what could really be done, it was absolutely amazing how
small and fast the code got. Extremely simple to understand, debug,
test -- I can't stress this enough.
An example of this was when I got to compiling the regular expression.
What turned out to be the simplest solution was to create functions at
runtime for each component of the expression, and then join them in a
list. To compare the regular expression to a stream, I just call each
function in the list one at a time with a stream, if all the functions
pass, then there was a match. Try doing that in C/C++.
What was an even bigger "aha" was when I wanted to add features to the
regular expression parser. What happens with a | symbol in a regular
expression? Well, just create a new list of functions (basically
another regular expression), and now join both compiled lists into a
list of 2 expressions. This was something that wasn't in my original
design spec to do, but I realized that it would only take about 5 lines
of code to add it.
My second "aha" with Lisp came when I really started using macros. I
had used them (mildly) throughout the regex parser, but they were just
1-2 line macros to simplify life. However, when the parser was done, I
needed to use it to create a FLEX like parser that could be used to
parse another language file. As it turns out, this macro ended up being
only 25 lines of code, and allowed me to write a function like so:
(setq token-parser
(regex:flex
(#/if|then/ (lambda (text)
(format t "KEYWORD: ~A~%" text)))
(#/\a\w*/ (lambda (text)
(format t "SYMBOL: ~A~%" text)))
(#/0x\x+/ (lambda (text)
(format t "HEX: ~A~%" text)))
(#/\d+/ (lambda (text)
(format t "DECIMAL: ~A~%" text)))
(#/("[^"]*")+/ (lambda (text)
(format t "STRING: ~A~%" text)))
(#/,/ (lambda (text)
(format t "COMMA~%")))
(#/\s+/ nil)))
This then creates a very large function for me that checks, in order,
each regular expression an parses the text. For example:
(FUNCALL token-parser "if x then print \"HI!\",10,0xff")
==> KEYWORD: if
SYMBOL: x
KEYWORD: then
SYMBOL: print
STRING: "HI!"
COMMA
DECIMAL: 10
COMMA
HEX: 0xff
T
The best advice is to use it. I'd ignore more "examples" that you see
in a book as propoganda. (Note: Paul Graham is an excellent writer and
I love Hackers and Painters). Since you seem to be an accomplished
programmer, take a real world problem you needed to solve and now solve
it using Lisp. Take advantage of high order functions and lists -- I
bet you'll be pleasantly suprised at how differently you will solve the
problem, and how much simpler the solution will be :)
Jeff
>>>>> On 18 Aug 2004 09:13:47 -0700, Jeff ("Jeff") writes:
Jeff> My two favorite languages to program in are Forth and Lisp. Both are
Jeff> wonderful languages. Neither could replace the other in what they do
Jeff> best (I would never think of using another language for embedded
Jeff> programming other than Forth).
I don't know Forth, but I know that people who program in it
certainly do seem to love it. Why do you think that Lisp is
unsuitable for embedded systems, in general, and in particular
in comparison to Forth? (Lisp has been successfully used for
embedded systems in the past, and many people nowadays seem to
be using Java for embedded systems. Most tiny embedded systems
that I've seen were written in assembler, and larger ones in C.)
I hope people don't turn this into a language flame war.
I am just curious about your experience with embedded systems
and Forth and Lisp.
Christopher C. Stacy wrote:
> >>>>> On 18 Aug 2004 09:13:47 -0700, Jeff ("Jeff") writes:
> Jeff> My two favorite languages to program in are Forth and Lisp.
> Both are Jeff> wonderful languages. Neither could replace the other
> in what they do Jeff> best (I would never think of using another
> language for embedded Jeff> programming other than Forth).
>
> I don't know Forth, but I know that people who program in it
> certainly do seem to love it. Why do you think that Lisp is
> unsuitable for embedded systems, in general, and in particular
> in comparison to Forth? (Lisp has been successfully used for
> embedded systems in the past, and many people nowadays seem to
> be using Java for embedded systems. Most tiny embedded systems
> that I've seen were written in assembler, and larger ones in C.)
>
> I hope people don't turn this into a language flame war.
> I am just curious about your experience with embedded systems
> and Forth and Lisp.
IMO, Forth is just unbeatable in embedded systems. I've never even
heard of Lisp being used in embedded devices (the closest I've come is
LispMe on the Palm). I would be interested in reading more about some
of these other systems. Are there any for the ARM7TDMI (my current
hobby processor of choice)?
Forth allows for unrestricted access to every part of the device. ROM,
RAM, I/O pins, interrupts, assembly code. It leaves a very small
footprint. And, like Lisp, is fully extensible. Given a processor data
sheet and minimal specs (for RAM, virtual registers, etc), I could sit
down and write a Forth system for device in under a day, complete with
assembler and most of the core ANSI functionality.
Many times, it is stated that Forth is nothing more than a macro
assembler on crack. I couldn't agree more. When I use it, I literally
feel just 1 step removed from the processor. And I not only put that
layer there myself, but whenever I need to, I can bypass it by creating
my own CODE (assembly) functions with little or no effort.
Lisp allows me to "hack together" a solution to a problem that isn't
100% defined. It let's me glob together lots of clay and slowly widdle
away at what I don't need at tack on what I really do (elegantly) until
the solution seems to reveal itself to me.
Forth is the opposite. When you are beginning from zero (and I mean
creating a boot image), and your problem is well defined, Forth allows
me to systematically break apart the problem until it is factored into
1-2 line functions that get reused everywhere. I truly believe that the
beauty of Forth is in its ability to make you aware of the fact that
all problems (no matter how complex) are really very, very simple
problems that just look complex when put together. If you solve the
tiny ones individually first, the full solution is quite simple as well.
I love Lisp. I wish I could use it 100% of the time at my work (which
does allow me to do some work in it, because of how productive I've
been with it in the past). But, I use Lisp when I don't care how a CONS
pair is put together "under the hood" or how many cycles it will take
to execute a FUNCALL. I use Forth when these things are important to
me. When every cycle and byte of RAM/ROM is important. Forth is so
beautiful in this regard, that I've used it to successfully program
machines from the Atari 2600 (using a 6502 and 16 /bytes/ of VRAM) all
the way up to a StrongARM.
Jeff
Marc Feeley at the University of Montreal is working on very small, almost
R4RS-compliant, Schemes (with tail recursion, continuations, threads, ...,
only small integers for numbers, no file I/O) that will fit into 3K ROM
on a PIC and run in a few score to a few hundred bytes of RAM. I think he
just finished PicoBIT, which is referenced in the first poster on his
web site at
http://www.iro.umontreal.ca/~feeley/
Brad Lucier
"Jeff" <···@nospam.insightbb.com> writes:
> IMO, Forth is just unbeatable in embedded systems. I've never even
> heard of Lisp being used in embedded devices (the closest I've come is
> LispMe on the Palm). I would be interested in reading more about some
> of these other systems. Are there any for the ARM7TDMI (my current
You may do a Google search for Movitz or ThinLisp. See also Frode
Vatvedt Fjeld's PIC microcontroller assembler.
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
On Thu, 19 Aug 2004 06:20:18 GMT, "Jeff" <···@nospam.insightbb.com>
wrote:
> I've never even heard of Lisp being used in embedded devices ...
Not Lisp ... however, Rick Kelsey and Jonathan Rees created a version
of Scheme (called Pre-Scheme) explicitly for use in low level system
and embedded programming. Rees and Bruce Donald wrote an earlier
paper about experiences programming robots in Scheme.
http://citeseer.ist.psu.edu/kelsey97prescheme.html
http://mumble.net/~jar/pubs/scheme-mobile-robots.ps
Both papers sort of conclude that a host high level features must be
sacrificed to effectively marry Scheme to hardware. It is likely that
many similar sacrifices would be necessary for Lisp.
George
--
for email reply remove "/" from address
George Neuner <·········@comcast.net> wrote:
+---------------
| "Jeff" <···@nospam.insightbb.com> wrote:
| > I've never even heard of Lisp being used in embedded devices ...
|
| Not Lisp ... however, Rick Kelsey and Jonathan Rees ... [Pre-Scheme]...
| Both papers sort of conclude that a host high level features must be
| sacrificed to effectively marry Scheme to hardware. It is likely that
| many similar sacrifices would be necessary for Lisp.
+---------------
At the extreme of that, one can always simply write an S-expr notation
assembler [look for references to "LAP" (Lisp Assembler Program) in
old Lisps], and then wrap arbitrarily-complex Lisp macros around that,
letting one get as close to the iron as one could wish. [I have used
that on a couple of projects.]
Also see Aubrey Jaffer's "Schlep" compiler for a subset of Scheme for
a similar approach, only targeting C instead of assembler:
<http://swiss.csail.mit.edu/~jaffer/Work/scm95-2>
<http://swiss.csail.mit.edu/~jaffer/Docupage/schlep.html>
<http://swiss.csail.mit.edu/~jaffer/Docupage/schlep.scm>
As he notes in the first URL above, he's been using the output of
Schlep in device drivers! ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
"Jeff" <···@nospam.insightbb.com> wrote in message news:<·······················@attbi_s51>...
> I've never even heard of Lisp being used in embedded devices
Lemonodor recently mentioned "L":
http://lemonodor.com/archives/000886.html
Also, IIRC a modified commercial Common Lisp with bounded-time garbage
collection was once used for telecom.
Manuel
> I don't know Forth, but I know that people who program in it
> certainly do seem to love it. Why do you think that Lisp is
> unsuitable for embedded systems, in general, and in particular
> in comparison to Forth? (Lisp has been successfully used for
> embedded systems in the past, and many people nowadays seem to
> be using Java for embedded systems. Most tiny embedded systems
> that I've seen were written in assembler, and larger ones in C.)
>
> I hope people don't turn this into a language flame war.
> I am just curious about your experience with embedded systems
> and Forth and Lisp.
This is a very interesting thread. I've used Forth for about
20 years now, and I'm just starting to get comfy with Lisp/Scheme.
In some ways, they are duals of each other. Where Forth is right
down to the metal and you tend to make small reusable functions, Lisp
is removed from the machine and you write small reusable functions.
I find the approach to the solutions to be similar, in that we tend
to factor the problem down into parts that look solvable on their
own, and then assemble the blocks until the entire probelm is solved.
I use the same techniques when programming in C or Tcl and it drives
my coworkers nuts, because Iuse an iterative approach instead of
BUFD (big up front design).
I've seen a few Schemes for small processors, but they tend to use
somewhere between 24 and 32K of code, which is 3-4 times the typical
Forth kernel footprint. But I'm busy browsing around looking for
clues that will help me build a small Scheme interpreter for a
micro.
Maybe a tethered model where the host does a lot of the heavy lifting
of managing symbol tables and the main REPL loop will help. I'm
going to let the probelm percolate for a few months and then go
at it in the cold Canadian winter....
Cheer, Ralph
rhempel wrote:
> I've seen a few Schemes for small processors, but they tend to use
> somewhere between 24 and 32K of code, which is 3-4 times the typical
> Forth kernel footprint. But I'm busy browsing around looking for
> clues that will help me build a small Scheme interpreter for a
> micro.
I think this article will appeal to you:
Danny Dubé. "BIT: A very compact Scheme system for embedded applications".
Scheme and Functional Programming 2000. September 2000.
--
Jens Axel Søgaard
Jens Axel S�gaard <······@soegaard.net> writes:
> rhempel wrote:
> > I've seen a few Schemes for small processors, but they tend to use
> > somewhere between 24 and 32K of code, which is 3-4 times the typical
> > Forth kernel footprint. But I'm busy browsing around looking for
> > clues that will help me build a small Scheme interpreter for a micro.
>
> I think this article will appeal to you:
>
> Danny Dub�. "BIT: A very compact Scheme system for embedded applications".
> Scheme and Functional Programming 2000. September 2000.
... and maybe this one too:
Feeley M., Dub� D. (2003), "PICBIT: a Scheme system for the PIC
microcontroller", Proceedings of the Scheme Workshop, Boston, MA,
United States, November 2003, pages 7-15.
You may find it on my web page:
http://w3.ift.ulaval.ca/~dadub100/
Danny Dub�
"Christopher C. Stacy" <······@news.dtpq.com> wrote in message
··················@news.dtpq.com...
> >>>>> On 18 Aug 2004 09:13:47 -0700, Jeff ("Jeff") writes:
> Jeff> My two favorite languages to program in are Forth and Lisp. Both
are
> Jeff> wonderful languages. Neither could replace the other in what they
do
> Jeff> best (I would never think of using another language for embedded
> Jeff> programming other than Forth).
>
> I don't know Forth, but I know that people who program in it
> certainly do seem to love it. Why do you think that Lisp is
> unsuitable for embedded systems, in general, and in particular
> in comparison to Forth? (Lisp has been successfully used for
> embedded systems in the past, and many people nowadays seem to
> be using Java for embedded systems. Most tiny embedded systems
> that I've seen were written in assembler, and larger ones in C.)
One of the things about Forth that makes it practical for smaller systems is
that while you can work at a reasonably high level, the system itself is
very low level, giving you fine control over placement of most everything.
Also, when all is said and done, the final system image tends to be quite
static (in that you know where everything is in the memory map, how big
things are, etc.).
Now there is nothing really that keeps someone from writing Lisp in a
similar way, relying on essentially manual memory layout, etc. But, we tend
to NOT do that routinely in Lisp, whereas Forth folks DO routinely do that.
Most modern programmers rarely even look at the memory map layout of the
machine they're using. I haven't in a long time, being a generic high level
applications programmer. Much in the same way, most Lisp programmers don't
worry about "those details" either.
But because of the static nature of typical Forth environs, the coders are
much more aware of the relationship that their program has to memory, and
how it is placed, etc.
A simple example is that Forth is typically even more static than C code.
While I'm sure there are routines similar to MALLOC in Forth, if you read
the basic literature on Forth, the concept of dynamically allocating (or,
more importantly, releasing) memory doesn't really exist. Any real dynamic
work is done on the stack, and everything else is statically allocated
within the dictionary.
So, in the end you have very fine control over where everything is yet still
have the ability to work at a reasonably high level of abstraction.
Obviously with larger and larger systems, this is less of a problem, and
even the phrase "embedded" today is talking about pretty large machines.
Regards,
Will Hartung
(·····@msoft.com)