Doing mini-languages in CL
Greg Menke
I've been toying with the idea of using CL to build a mini-language to
generate code to run on a microcontroller, but I think what I really
want is a language that is pretty much Lisp. Perhaps something on the
order of Xlisp, so I can keep the very handy language structure- but
specifically simplified and limited features.
This is making me think of how I would avoid trying to redefine the
Lisp operators themselves- which doesn't sound like the right
approach. I also think it might be the wrong approach to create a set
of functions that parallel the CL functions but with for example, a
leading underscore to avoid clashing. Since I'd be implementing a
"mini-Lisp" within Lisp, I'd like to keep the same symbol names where
I can.
Lacking a better idea, I might try the 2nd approach, but I was hoping
for a nicer way if someone has one.
Thanks,
Gregm
Christophe Rhodes
Well, what I think you're meant to do is to write a
microcontroller:generate-code function that is analogous to
cl:compile, and use that function to generate code for the target.
The details of the code generation depend slightly on what runtime
services you expect to find there -- do you have a C library? Are you
aiming to build a Lisp core? Your generate-code function will have to
know (effectively) how to "link" with what's there -- if there's
nothing there at all, then you have to provide everything yourself.
In other words, you should look to build a compiler for your target
platform as an application to live inside your host Lisp. For
examples of this in the wild, see SBCL and Movitz, where for those the
mini-language in question is Common Lisp :-)
Cheers,
Christophe
[ So just in case that last bit is confusing: Movitz and SBCL have the
additional constraint of wanting to generate a runtime library from
the same sources that built the application; they do this by running
their application compiler over the compiler sources. This is
probably not going to be the case in your situation, so some of the
confusion will disappear. ]
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
Will Hartung
"Greg Menke" <gregm...@toadmail.com> wrote in message
news:m31xp1t...@europa.pienet...
>
> I've been toying with the idea of using CL to build a mini-language to
> generate code to run on a microcontroller, but I think what I really
> want is a language that is pretty much Lisp. Perhaps something on the
> order of Xlisp, so I can keep the very handy language structure- but
> specifically simplified and limited features.
>
> This is making me think of how I would avoid trying to redefine the
> Lisp operators themselves- which doesn't sound like the right
> approach. I also think it might be the wrong approach to create a set
> of functions that parallel the CL functions but with for example, a
> leading underscore to avoid clashing. Since I'd be implementing a
> "mini-Lisp" within Lisp, I'd like to keep the same symbol names where
> I can.
It sort of depends on what you're trying to do.
If all you want is to write a compiler for a "Lisp inspired" mini-language,
then the two primary things to leverage of CL are the Reader and Symbols.
I think it was Thomas Burdick who mentioned this a little while ago, but I
forget the thread.
But, anyway, what you do is simply leverage the property lists of Symbols to
place the code relevant to compiling (or even executing) your forms. Then,
you can use the Reader to be your lexer, and away you go.
It's really pretty easy.
By doing it this way, you essentially overload any symbols that overlap in
your space and with CL, thus instead of a classic Lisp-2, you make it a
Lisp-N.
Hopefully someone will chime in with the relevant post, I couldn't find it.
Regards,
Will Hartung
(wi...@msoft.com)
Greg Menke
> Greg Menke <gregm...@toadmail.com> writes:
>
> > I've been toying with the idea of using CL to build a mini-language to
> > generate code to run on a microcontroller, but I think what I really
> > want is a language that is pretty much Lisp. Perhaps something on the
> > order of Xlisp, so I can keep the very handy language structure- but
> > specifically simplified and limited features.
> >
> > This is making me think of how I would avoid trying to redefine the
> > Lisp operators themselves- which doesn't sound like the right
> > approach. I also think it might be the wrong approach to create a set
> > of functions that parallel the CL functions but with for example, a
> > leading underscore to avoid clashing. Since I'd be implementing a
> > "mini-Lisp" within Lisp, I'd like to keep the same symbol names where
> > I can.
> >
> > Lacking a better idea, I might try the 2nd approach, but I was hoping
> > for a nicer way if someone has one.
>
> Well, what I think you're meant to do is to write a
> microcontroller:generate-code function that is analogous to
> cl:compile, and use that function to generate code for the target.
> The details of the code generation depend slightly on what runtime
> services you expect to find there -- do you have a C library? Are you
> aiming to build a Lisp core? Your generate-code function will have to
> know (effectively) how to "link" with what's there -- if there's
> nothing there at all, then you have to provide everything yourself.
I was on the mini-language kick in an effort to maybe use CL macros at
the mini-language "source" level to do stuff. Given I'd be trying to
use mini-language functions whose names are the same as normal CL
functions, I wanted to somehow avoid conflicts. My requirements are
simple enough that a very basic runtime environment will suffice- a
single stack that houses all variables from "global" all the way down,
no gc. Sort of a "Lisp without the Lisp", but with the same syntax if
you will.
> In other words, you should look to build a compiler for your target
> platform as an application to live inside your host Lisp. For
> examples of this in the wild, see SBCL and Movitz, where for those the
> mini-language in question is Common Lisp :-)
The application is a little 8 bit ucontroller, I have some ROM
functions for fp and basic tty support, but thats about it. I was
thinking of a very minimal Lisp. Basically I want the program
structure, 8/16 bit ints, fp and a basic set of stuff for playing
around with numbers, characters and bits- perhaps strings. Something
like loop would be very handy- which is why I was wanting to use
macros. Since I can control the ABI, I can go right to assembler-
which is key since this is a very small target.
Gregm
Marc Battyani
"Greg Menke" <gregm...@toadmail.com> wrote
>
> The application is a little 8 bit ucontroller, I have some ROM
> functions for fp and basic tty support, but thats about it. I was
> thinking of a very minimal Lisp. Basically I want the program
> structure, 8/16 bit ints, fp and a basic set of stuff for playing
> around with numbers, characters and bits- perhaps strings. Something
> like loop would be very handy- which is why I was wanting to use
> macros. Since I can control the ABI, I can go right to assembler-
> which is key since this is a very small target.
That's interesting.
Can you tell us which 甥ontroller you will target ?
Marc
Raymond Wiker
>
> The application is a little 8 bit ucontroller, I have some ROM
> functions for fp and basic tty support, but thats about it. I was
> thinking of a very minimal Lisp. Basically I want the program
> structure, 8/16 bit ints, fp and a basic set of stuff for playing
> around with numbers, characters and bits- perhaps strings. Something
> like loop would be very handy- which is why I was wanting to use
> macros. Since I can control the ABI, I can go right to assembler-
> which is key since this is a very small target.
Maybe Henry Baker's "Comfy" paper could be of interest?
--
Raymond Wiker Mail: Raymon...@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
Duane Rettig
Will Hartung had the right idea at the highest level, and that is
to create a new namespace. How you do that is up to you. The most
trivial way to do it is to use the package system to create a namespace
that doesn't use CL directly. Another approach is to use properties on
the names to which you want to give target-definitions, as Will suggested.
If the language is not extensible (and even if it is, sometimes) you can
use a table via either an array or a hash-table to create your own
namespace - all operations on the targeted namespace would go through that
table.
--
Duane Rettig du...@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Adam Warner
> Given I'd be trying to use mini-language functions whose names are the
> same as normal CL functions, I wanted to somehow avoid conflicts.
You can use another package and only import those Common Lisp symbols that
you want to be the same. Here's an example where I'm only redefining +:
(defpackage #:mini
(:use)
#.`(:import-from :cl
,@(let (list)
(do-external-symbols (symbol :cl)
(unless (eq symbol '+) (push symbol list)))
list)))
(in-package mini)
(defun + (&rest args)
(apply #'concatenate 'string args))
While you are in the MINI package everything works like your mini language:
* (in-package mini)
#<The MINI package, 980/1574 internal, 0/2 external>
* (length (+ "abc" "def"))
6
Regards,
Adam
Marco Antoniotti
(defpackage "MINI" (:use "CL")
(:shadow "+")
...
)
Cheers
marco
Adam Warner
> Ahem....
>
> (defpackage "MINI" (:use "CL")
> (:shadow "+")
> ...
> )
>
> Cheers
>
> marco
Eek! Unfortunately even using Common Lisp isn't always enough to stop me
reinventing it, poorly.
Thanks Marco.
Regards,
Adam
Greg Menke
8052 (the one with rom'ed Basic) w/ 32K ram. The output of the
mini-language would be assembly- the assembler I have for it is
reasonable, I'm quite happy to defer all the instruction coding and
address fixup grunt work to it.
Gregm
Tim Bradshaw
> This is making me think of how I would avoid trying to redefine the
> Lisp operators themselves- which doesn't sound like the right
> approach. I also think it might be the wrong approach to create a set
> of functions that parallel the CL functions but with for example, a
> leading underscore to avoid clashing. Since I'd be implementing a
> "mini-Lisp" within Lisp, I'd like to keep the same symbol names where
> I can.
Well, ultimately what you're going to be doing, I think, is taking
some form and compiling it to produce code that will run on your
minicontroller. So it doesn't really matter if some of the names you
use clash with CL names, because you obviously won't be calling the CL
functions or anything, since they run on the wrong machine altogether.
So, for instance, you could keep the information you need to compile
code for this little machine in a hashtable or something, and at some
point your compiler would say (gethash 'car *code-table*) or
something, and use the resulting object.
But I may be confused.
--tim
Thomas F. Burdick
> "Greg Menke" <gregm...@toadmail.com> wrote in message
> news:m31xp1t...@europa.pienet...
> >
> > I've been toying with the idea of using CL to build a mini-language to
> > generate code to run on a microcontroller, but I think what I really
> > want is a language that is pretty much Lisp. Perhaps something on the
> > order of Xlisp, so I can keep the very handy language structure- but
> > specifically simplified and limited features.
> >
> > This is making me think of how I would avoid trying to redefine the
> > Lisp operators themselves- which doesn't sound like the right
> > approach. I also think it might be the wrong approach to create a set
> > of functions that parallel the CL functions but with for example, a
> > leading underscore to avoid clashing. Since I'd be implementing a
> > "mini-Lisp" within Lisp, I'd like to keep the same symbol names where
> > I can.
>
> It sort of depends on what you're trying to do.
>
> If all you want is to write a compiler for a "Lisp inspired" mini-language,
> then the two primary things to leverage of CL are the Reader and Symbols.
>
> I think it was Thomas Burdick who mentioned this a little while ago, but I
> forget the thread.
You're probably thinking of this thread, which I was about to point him to:
http://groups.google.com/groups?threadm=xcvad3ycvuw.fsf%40famine.OCF.Berkeley.EDU
If it makes sense, I'd implement both the cross-compiler, and an
interpreter. If you keep your Lisp dialect's namespaces seperate from
Common Lisp's, it makes everything much easier, with no need to play
games with the package system just to acheive namespacing.
A naive cross-compiler is pretty easy. Just design a very low-level
pico-Lisp, which consists of special forms and primitive functions
that you'll need to build on top of. Write a compiler for that
language. Add macroexpansion to your compiler, and build your
mini-Lisp up using functions and macros. You should probably design
your compiler's handling of primitive functions to be extensible, so
you can write Lisp functions in assember, when you later discover the
need.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Will Hartung
> 8052 (the one with rom'ed Basic) w/ 32K ram. The output of the
> mini-language would be assembly- the assembler I have for it is
> reasonable, I'm quite happy to defer all the instruction coding and
> address fixup grunt work to it.
So, simply put the goal is to write a pure compiler, not an emulator or a
simulator or anything like that. Rather, you put in "GregLisp", and out come
8052 Assembly to be assembled, hexified, downloaded, burnt, plugged in and
tested just like any other bit of 8052 Assembly.
If your primary goal in using CL is mostly for its macro facility, I would
stop right there.
When you write your own compiler, as long as you have the ability to call
(greg-compile sexpr), you basically have a macro facility built in to your
own system, rather than having to "fight" wil CLs.
Your compiler will already take S-exprs, but there's nothing that says those
S-exprs have to come solely from source code for the microcontroller. You
can easily do something like this:
(defun compile-when (form)
;; (when expr form) == (if expr form)
(let ((expr (second form))
(body (third form)))
(gregs-compiler (list 'if expr form))))
(defun compile-if (form)
;; (if expr then-body else-body)
;; convert to (cond (expr then-body)
;; (t else-body))
(let* ((expr (second form))
(then-body (third form))
(else-body (fourth form))
(rewrite-form (list 'cond (list expr then-body))))
(when else-body
(setf rewrite-form (append rewrite-form (list (list 't else-body)))))
(gregs-compiler rewrite-form)))
(I'll leave compiling the COND statement as an exercise for the reader).
But, basically, while these are certainly not macros in the classic CL
sense, they essentially take an input S-Expr and transform it into something
else, and then feeds it into your compiler.
For my simple compiler, this was my "gregs-compiler":
(defun compile-to-rsl (form)
(cond
((or (numberp form) (stringp form)) (format nil "~W" form))
((symbolp form) (variable-to-rsl form))
((consp form) (function-to-rsl form))
(t (errorf "Don't know what this is! ~A ~A" form (type-of form)))))
To compile a function:
(defun function-to-rsl (form)
(if (not (car form))
(error "Empty list passed to function-to-rsl!")
(let* ((func-name (car form))
(func-code (gethash func-name *functions*)))
(when (not func-code)
(errorf "Function not defined ~A ~A" func-name form))
(funcall func-code (cdr form)))))
I stored the respective function compilers in a hash table (craftily named
*functions*).
If you rely on Symbols and property lists (something I didn't think about
being more in Java mode that Lisp mode), then you associate the compiler
function directly with the symbol rather than building up a table like I
did. Whatever floats your boat.
But for basic stuff, using S-exprs, it's really pretty darn easy to work it
all out.
My compiler was pretty simple, pretty limited and relied on nice people like
me feeding it good code, but when you can essentially create your parse tree
on the fly and feed it back into the compiler itself, things get pretty easy
pretty darn fast, and you find you won't necessarily need macros. Now, if
you want macros in your mini-language, that's a different animal entirely.
Luck.
Regards,
Will Hartung
(wi...@msoft.com)
Kaz Kylheku
> I've been toying with the idea of using CL to build a mini-language to
> generate code to run on a microcontroller, but I think what I really
> want is a language that is pretty much Lisp. Perhaps something on the
> order of Xlisp, so I can keep the very handy language structure- but
> specifically simplified and limited features.
Could ThinLisp satisfy your requirements?
Will Hartung
"Thomas F. Burdick" <t...@famine.OCF.Berkeley.EDU> wrote in message
news:xcv1xp1...@famine.OCF.Berkeley.EDU...
> A naive cross-compiler is pretty easy. Just design a very low-level
> pico-Lisp, which consists of special forms and primitive functions
> that you'll need to build on top of. Write a compiler for that
> language. Add macroexpansion to your compiler, and build your
> mini-Lisp up using functions and macros. You should probably design
> your compiler's handling of primitive functions to be extensible, so
> you can write Lisp functions in assember, when you later discover the
> need.
This is really important, because you think Lisp compiler (or Scheme
compilers, or whatever), and you hunt down the systems, look at the HUGE
sources and go "Oh. My. God. I wanted something SIMPLE!".
The trick is that while the larger systems with sophisticated code
generators can be and are complicated, at the higher level, many of these
ARE quite simple.
Once you start down the path on your compiler and get the basic forms
working (simple expresions, simple loop and conditionals, functions) you'll
find that everything else layers on top of that framework pretty readily.
These other systems are difficult because they've already accumulated all of
this stuff, so the simplicity gets buried.
You'll find that your 100-200 line compiler is doing AMAZING things, then
try some other parts and go "Oh, woe, that's really gross code..." and
pretty soon you're optimizing stuff.
But since it's all incremental, the development can be really efficient.
Being able to type (gregs-compiler '(+ 1 1)) in the Listener and see what
you get is a remarkable productivity tool.
So, mostly don't be afraid of something like this by looking at others code
and panicing. It need not be that bad.
Start small, think big, take one bite of the elephant at a time. Since you
don't have to worry so much about grammars and such, adding special forms
and such is easy, and other interesting things you can punt to the Reader
(#xFF for free! Woo hoo!).
Regards,
Will Hartung
(wi...@msoft.com)
Thomas F. Burdick
I agree with everything Will said here, and just want to add:
> You'll find that your 100-200 line compiler is doing AMAZING things, then
> try some other parts and go "Oh, woe, that's really gross code..." and
> pretty soon you're optimizing stuff.
>
> But since it's all incremental, the development can be really efficient.
I highly recommend using some sort of constraints system like Cells or
KR. Common Lisp is already a great compiler toolkit, and a simple
one-way constraints system adds a lot of value. You can keep stuff
organized a lot more easily (or at least I could) if you add your
optimizations as declarative rules.
> Start small, think big, take one bite of the elephant at a time. Since you
> don't have to worry so much about grammars and such, adding special forms
> and such is easy, and other interesting things you can punt to the Reader
> (#xFF for free! Woo hoo!).
Looking through comp.compilers can be depressing sometimes: how much
time and effort do people spend parsing and lexing?!?! Lisp really
makes it easier to skip to the good stuff.
Greg Menke
I'm not looking for a native Lisp on the processor, just a handy way
of building a Lisp-like language that compiles to native, plain-old
static machine code on the target. This is pretty much just a way to
avoid using the built-in Basic- I need only to equal its convienence.
Since CL is so pretty darn cool, I thought I'd try actually using it
to do the nasty parsing and fiddling that compilers have to do rather
than homebrewing Yet Another Stupid Broken Parser for yet another
C-like language.
Gregm
Greg Menke
> "Greg Menke" <gregm...@toadmail.com> wrote in message
> news:m3oes5g...@europa.pienet...
>
> > 8052 (the one with rom'ed Basic) w/ 32K ram. The output of the
> > mini-language would be assembly- the assembler I have for it is
> > reasonable, I'm quite happy to defer all the instruction coding and
> > address fixup grunt work to it.
>
> So, simply put the goal is to write a pure compiler, not an emulator or a
> simulator or anything like that. Rather, you put in "GregLisp", and out come
> 8052 Assembly to be assembled, hexified, downloaded, burnt, plugged in and
> tested just like any other bit of 8052 Assembly.
Thats it in a nutshell. From that perspective, my question was how to
arrange the symbol names for the functions "GregLisp" implements.
> If your primary goal in using CL is mostly for its macro facility, I would
> stop right there.
I was more hoping to leverage the reader, with the ability to use
macros as something thats potentially useful- but which I probably
don't understand how to arrange at the moment.
> When you write your own compiler, as long as you have the ability to call
> (greg-compile sexpr), you basically have a macro facility built in to your
> own system, rather than having to "fight" wil CLs.
>
> Your compiler will already take S-exprs, but there's nothing that says those
> S-exprs have to come solely from source code for the microcontroller. You
> can easily do something like this:
<snip sample code, Thanks!>
> I stored the respective function compilers in a hash table (craftily named
> *functions*).
>
> If you rely on Symbols and property lists (something I didn't think about
> being more in Java mode that Lisp mode), then you associate the compiler
> function directly with the symbol rather than building up a table like I
> did. Whatever floats your boat.
I get the impression that figuring this out will be a good education
for me on how Lisp handles symbols.
> But for basic stuff, using S-exprs, it's really pretty darn easy to work it
> all out.
Thats what I was going for.
> My compiler was pretty simple, pretty limited and relied on nice people like
> me feeding it good code, but when you can essentially create your parse tree
> on the fly and feed it back into the compiler itself, things get pretty easy
> pretty darn fast, and you find you won't necessarily need macros. Now, if
> you want macros in your mini-language, that's a different animal entirely.
>
> Luck.
>
> Regards,
>
> Will Hartung
> (wi...@msoft.com)
Thanks! I think those are the hints I needed- next I'll see if I can
do something.
Gregm
Frode Vatvedt Fjeld
> 8052 (the one with rom'ed Basic) w/ 32K ram. The output of the
> mini-language would be assembly- the assembler I have for it is
> reasonable, I'm quite happy to defer all the instruction coding and
> address fixup grunt work to it.
I started programming something like this a while ago for PIC
microcontrollers. It's not much (mostly an assembler, I think) but you
might want to have a look at it, at
<URL:http://www.cs.uit.no/~frodef/sw/picl.lisp>
--
Frode Vatvedt Fjeld
Will Hartung
> "Will Hartung" <wi...@msoft.com> writes:
> > So, simply put the goal is to write a pure compiler, not an emulator or
a
> > simulator or anything like that. Rather, you put in "GregLisp", and out
come
> > 8052 Assembly to be assembled, hexified, downloaded, burnt, plugged in
and
> > tested just like any other bit of 8052 Assembly.
>
> Thats it in a nutshell. From that perspective, my question was how to
> arrange the symbol names for the functions "GregLisp" implements.
>
>
> > If your primary goal in using CL is mostly for its macro facility, I
would
> > stop right there.
>
> I was more hoping to leverage the reader, with the ability to use
> macros as something thats potentially useful- but which I probably
> don't understand how to arrange at the moment.
Yeah, I think the detail to note is that the Macro facility is a Compiler
attribute, not a Reader attribute. The reader doesn't do macro expansion,
the compiler does. Grokking that detail early helps set expectations. So,
simply put you may well be able to leverage CL macros in building your
compiler, but the language your compiler will be compiling will probably not
be able to directly leverage CL macros (but could well have its own).
Hmm..
Actually you could do something sick like this in your compiler:
(defun greg-compiler (form)
(cond
((consp form) (compile-function-or-macro form))
...)))
(defun compile-function-or-macro (form)
(let ((macro-symbol (first form)))
(cond ((eq macro-symbol 'defmacro (eval form))) ;; defining a new macro,
let CL do the work
((macro-function macro-symbol) (greg-compiler (macroexpand form)))
;; compile the expanded form
(t (compile-function form))))) ;; something I can actually
understand.
This let's you use the stock CL defmacro facility on your s-exprs, but the
real problem is that you'll end up "polluting" the namespace of your CL
image with macros for your language. You'll probably have other package
issues and potential conflicts, but you can work through those I'm
bettering. So, in that sense, you're using the CL macros as sort of a crude
"pre-processor". But shrewd package management can keep that from being a
horrible issue, and it gives your language macros "for free". And you
thought getting #xFF was cool!
> > If you rely on Symbols and property lists (something I didn't think
about
> > being more in Java mode that Lisp mode), then you associate the compiler
> > function directly with the symbol rather than building up a table like I
> > did. Whatever floats your boat.
>
> I get the impression that figuring this out will be a good education
> for me on how Lisp handles symbols.
Symbols are one of those anachronisms of CL. They're amazingly powerful
objects that were overloaded and used for "everything" back in the day. When
folks think that CL doesn't have any data structures of note, it's because a
lot of stuff was done with Symbols and their properties (and lists).
But when you come to CL from other lanaguages, and look for things like
hashtables et al, you then overlook Symbols and all they provide simply
because other lanaguages don't have anything like them. They're just Yet
Another tool that CL provides to be leveraged as appropriate and its always
good to at least know what tools are IN the toolbox, if not necessarily
knowing exactly how to USE them.
Regards,
Will Hartung
(wi...@msoft.com)
Will Hartung
> I highly recommend using some sort of constraints system like Cells or
> KR. Common Lisp is already a great compiler toolkit, and a simple
> one-way constraints system adds a lot of value. You can keep stuff
> organized a lot more easily (or at least I could) if you add your
> optimizations as declarative rules.
What is KR? I admit to not having spent much time looking at Cells.
Regards,
Will Hartung
(wi...@msoft.com)
Raymond Wiker
"Knowledge Representation" (I think), a prototype-based object
system used in and bundled with) Garnet.
Thomas F. Burdick
> "Will Hartung" <wi...@msoft.com> writes:
>
> > "Thomas F. Burdick" <t...@famine.OCF.Berkeley.EDU> wrote in message
> > news:xcvvfmd...@famine.OCF.Berkeley.EDU...
> >
> >> I highly recommend using some sort of constraints system like Cells or
> >> KR. Common Lisp is already a great compiler toolkit, and a simple
> >> one-way constraints system adds a lot of value. You can keep stuff
> >> organized a lot more easily (or at least I could) if you add your
> >> optimizations as declarative rules.
> >
> > What is KR? I admit to not having spent much time looking at Cells.
>
> "Knowledge Representation" (I think), a prototype-based object
> system used in and bundled with) Garnet.
It's a prototype-inheritance object system with one-way lazy
constraints. You can pull it out of Garnet and use it on its own,
too.
Thomas F. Burdick
I find it easier to just have your own macro system in parallel with
CL's. If you don't need MACROLET, it's very easy:
(defun expand-defmacro (form)
(destructuring-bind (name ll &rest body)
(let ((whole (gensym)))
`(eval-when (compile)
(setf (get ',name 'macro-function)
(lambda (,whole)
(destructuring-bind ,destructuring-ll (cdr ,whole)
,@body)))
',name))))
(setf (get 'defmacro 'macro-function) #'expand-defmacro)
(defun my-macroexpand-1 (form)
(let ((macrofun (get (car form) 'macro-function)))
(if (functionp macrofun)
(values (funcall macrofun form) t)
(values form nil))))
(defun my-macroexpand (form)
(loop with expanded = nil
for (form this-expanded) = (multiple-value-list (my-macroexpand-1 form))
when this-expanded do (setf expanded t)
while this-expanded
finally (return (values form expanded))))
Now, as long as your compiler knows how to process EVAL-WHEN (COMPILE),
and passes its body to CL:EVAL, you're all set up. Just have the
compiler call MY-MACROEXPAND on any form before compiling it. Viola`,
macros that are written in Common Lisp that operate upon your
mini-lisp dialect. Now you can implement LET! :-)
jan
> Actually you could do something sick like this in your compiler:
>
> (defun greg-compiler (form)
> (cond
> ((consp form) (compile-function-or-macro form))
> ...)))
>
> (defun compile-function-or-macro (form)
> (let ((macro-symbol (first form)))
> (cond ((eq macro-symbol 'defmacro (eval form))) ;; defining a new macro,
> let CL do the work
> ((macro-function macro-symbol) (greg-compiler (macroexpand form)))
> ;; compile the expanded form
> (t (compile-function form))))) ;; something I can actually
> understand.
That's similar to what I do except I use macroexpand-1 because some
macros are easier to deal with at intermediate stages of expansion.
Using this approach on cmucl, once you have IF, you get COND, WHEN and
UNLESS for free, but an even bigger win is getting LOOP for the price
of LET and TAGBODY.
--
jan
Greg Menke
I think everyone's help in this thread is sinking in a little. I
spent some time last night working with macroexpand and I'm starting
to see what you're getting at. The 3 package approach mentioned
previously is increasingly looking like the way to divide up the
design. I'm still not sure about using hash tables or CL symbols for
the compiler, so thats where I'm going next I guess.
Its also starting to look as if I'll be doing the instruction coding
myself anyway. But thats not all bad because my 8051 assembler is a
dos program, I'd rather have a portable compiler since the development
host & console is an Ultra 2.
Thanks everyone,
Gregm
Peter Seibel
Well, since it was more fun than trying to write about pathnames (for
my book) inspired by this thread I spent a chunk of yesterday playing
around with writing a compiler for a made up "machine". While there
are plenty of improvements to be made to this code (such as generating
an intermediate form that is suitable to feeding to a peephole
optimizer) it might give you a few ideas. And I'm sure if it has any
really *bad* ideas in it, someone else will be kind enough to point
them out.
The language is slightly lispy with lexical variables and tagbody (on
top of which I build a few higher level constructs such as DOTIMES).
However the only kind of values are numbers with 0 treated as false
and everything else 1. And since I was pretending to be developing a
compiler for an extremely simply chip, I assumed that the compiler
would emit a single executable from a bunch of functions with a known
entry point.
The way this compiler is implemented, the language can be extended by
writing macros using normal CL:DEFMACRO. However unlike normal CL
macros the target language is MINI not CL. Which means the macros can
use all of CL to compute their expansion but after all macros are
expanded the code must be built only of MINI special operators and
primitive functions.
-Peter
(defpackage :mini-compiler
(:documentation "The package our compiler runs in.")
(:use :cl))
(defpackage :mini
(:documentation "The package where we define the MINI language."
(:use))
(in-package :mini-compiler)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; We are building a compiler for a made up stack machine. The
;; primitive operations of this machine are as follows:
;;
;; NOP -- do nothing.
;; LOAD register -- load the value from a register onto the stack
;; STORE register -- store the top of the stack into a register
;; PUSH value -- push a literal number onto the stack
;; POP -- pop the top of the stack
;; ADD -- pop the top two items off the stack and push their sum.
;; SUBTRACT -- pop the top two items off the stack and push their difference.
;; MULTIPLY -- pop the top two items off the stack and push their product.
;; DIVIDE -- pop the top two items off the stack and push their quotient.
;; EQUAL -- pop the top two items and push 0 if they are different.
;; GREATER_THAN -- pop the top two items and push 0 unless the first is greater than the second
;; LESS_THAN -- pop the top two items and push 0 unless the first is less than the second
;; NOT_LESS_THAN -- pop the top two items and push 0 if the first is less than the second
;; NOT_GREATER_THAN -- pop the top two items and push 0 if the first is greater than the second
;; COMPLEMENT -- pop the top of the stack and push 1 if it is 0 and 0 otherwise.
;; PRINT -- pop the top of the stack and print its value.
;; BRANCH_ON_ZERO address -- pop the top of the stack and branch to address if it is zero
;; GO address -- unconditionally jump to the given address
;; CALL address -- call a function. Jumps to the address after saving the current *pc* on a stack.
;; RETURN -- return from a function to the addressed popped of the call stack.
;; EXIT -- exit the program.
(defvar *compiler-output* *standard-output*)
(defvar *compiler-trace-output* *trace-output*)
(defvar *trace-compiler* nil)
(defvar *pc* 0)
(defvar *available-registers*)
(defvar *functions*)
(defvar *tagbody-labels* ())
(defvar *variable-bindings* ())
(defvar *measuring* nil)
(defmacro define-special-operator (symbol lambda-list &body body)
"Define a special operator. This macro defines a function that is
responsible for compiling a call to the special operator named by `symbol'.
The rest of the list representing the special operator call will be passed
to this function and destructured with `lambda-list'."
`(progn
(defun ,symbol (&rest args)
(destructuring-bind ,lambda-list args
,@body))
(setf (get ',symbol 'mini-compiler) 'special-operator)))
(defmacro define-primitive (symbol &body body)
"Define a primitive function that will be encoded inline. The body
is responsible for emitting appropriate operations to implement the
desired functionality. Defines a function of no arguments named
`symbol' that will emit those codes. The arguments to the function
can be assumed to be on the stack."
`(progn
(defun ,symbol () ,@body)
(setf (get ',symbol 'mini-compiler) 'primitive))))
(defun mini-special-operator-p (symbol)
"Is the given symbol the name of a MINI special operator?"
(eql (get symbol 'mini-compiler) 'special-operator))
(defun mini-primitive-p (symbol)
"Is the given symbol the name of a MINI primitive function?"
(eql (get symbol 'mini-compiler) 'primitive))
(defun compile-mini-file (input &optional (output (make-pathname :type "masm" :defaults input)))
(with-open-file (*compiler-output* output :direction :output :if-exists :supersede)
(compile-program
(let ((*package* (find-package :mini)))
(with-open-file (in input)
(format *compiler-output* "~&;; Compiled from ~a~%" (truename in))
(loop for fn = (read in nil nil) while fn collect fn))))
(truename *compiler-output*)))
(defun compile-program (program &key (entry-point 'mini::main))
"Compile a program represented as a list of MINI::DEFUN's. The entry point is a name of a function."
(let* ((header-length (let ((*measuring* t) (*pc* 0)) (emit-program-header nil) *pc*))
(*available-registers* (loop for i from 0 below 256 collect i))
(*functions* (allocate-functions program header-length))
(*pc* 0))
(emit-program-header entry-point)
(loop for function in program do (compile-expr function))))
(defun compile-expr (code)
"Compile a single s-expression of our mini-language."
(/log "~&~:[Compiling~;Measuring~] ~s~%" *measuring* code)
(typecase code
(null)
(number (emit "PUSH ~d" code))
(symbol (emit "LOAD ~a" (find-register code)))
(cons (compile-cons code)))
t)
(defun measure (expr)
"Measure the length of the code that will be emitted for a given expression
without actually emitting any code"
(let ((*measuring* t)
(*pc* 0))
(compile-expr expr)
*pc*))
(defun compile-cons (code)
"As in common lisp there are three ways to evaluate a cons: as a
macro call, as a special operator call, or as a function call."
(destructuring-bind (first &rest rest) code
(unless (symbolp first) (error "Expected symbol, got ~S" first))
(cond
((macro-function first)
(compile-expr (expand-macro code)))
((mini-special-operator-p first)
(apply first rest))
(t (compile-function-call first rest)))))
(defun expand-macro (code)
"Note that we get to use the CL macro mechanism here. This is huge!"
(/log "~&Macro expanding ~s~%" code)
(macroexpand code))
(defun compile-function-call (function args)
"Compile the code that will evaluate the function's arguments. Then the function
itself is either a primitive in which case we emit the code that impements it by
calling the appropriate generator function or it is not in which case we use the
CALL instruction to call it by name."
(loop for expr in args do (compile-expr expr))
(if (mini-primitive-p function)
(funcall function)
(emit "CALL ~d" (function-address function))))
(defun emit-program-header (entry-point)
(emit "CALL ~d" (function-address entry-point))
(emit "EXIT"))
(defun allocate-functions (program *pc*)
"Measure the size of all the functions in the program so we know their address
before we try to compile them."
(loop for function in program
for size = (measure function)
collect (cons (extract-function-name function) *pc*)
do (incf *pc* size)))
(defun extract-function-name (function)
(assert (eql (first function) 'mini::defun))
(second function))
(defun function-address (name)
(unless *measuring*
(let ((cons (assoc name *functions*)))
(unless cons (error "No function named ~a" name))
(cdr cons))))
(defun emit (format &rest args)
"Emit 'instructions' for our mythical machine. If we are only measuring then we
don't actually emit."
(when (not *measuring*) (actually-emit format args))
(incf *pc* (1+ (length args))))
(defun actually-emit (format args)
"This is where we actually emit 'instructions'. For demonstration purposes we'll
just print some pseudo assembly. This could emit machine code or whatever. At this
point we leave lisp behind."
(fresh-line *compiler-output*)
(format *compiler-output* "~3d: " *pc*)
(apply #'format *compiler-output* format args)
(terpri *compiler-output*))
(defun /log (format &rest args)
(when *trace-compiler*
(fresh-line)
(apply #'format *compiler-trace* format args)
(fresh-line)))
(defun //log (format &rest args)
(let ((*trace-compiler* t))
(apply #'/log format args)))
(defun toggle-trace () (setf *trace-compiler* (not *trace-compiler*)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; Now we are ready to define the MINI language using
;;;; define-primitive, define-special-operator and macros.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Primitives. These map directly to the particular ops supported by
;;; our target machine.
(define-primitive mini::+ (emit "ADD"))
(define-primitive mini::- (emit "SUBTRACT"))
(define-primitive mini::* (emit "MULTIPLY"))
(define-primitive mini::/ (emit "DIVIDE"))
(define-primitive mini::= (emit "EQUAL"))
(define-primitive mini::> (emit "GREATER_THAN"))
(define-primitive mini::< (emit "LESS_THAN"))
(define-primitive mini::>= (emit "NOT_LESS_THAN"))
(define-primitive mini::<= (emit "NOT_GREATER_THAN"))
(define-primitive mini::not (emit "COMPLEMENT"))
(define-primitive mini::print (emit "PRINT"))
(define-primitive mini::%peek)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Special operators. These implement basic control constructs that
;;; can't be implemented as macros, usually because they need to use
;;; machine level ops that are not exposed as primitives. As in Common
;;; Lisp, they provide building blocks for higher level macros.
;;
;; MINI:PROGN -- like CL:PROGN except no multiple values.
;;
(define-special-operator mini::progn (&rest body)
(loop for (expr . rest) on body do
(compile-expr expr)
(when rest (emit "POP"))))
;;
;; MINI:IF -- like CL:IF
;;
(define-special-operator mini::if (test then &optional else)
(compile-expr test)
(let ((then-length (measure then)))
(emit "BRANCH_ON_ZERO ~d" (+ 2 *pc* then-length)))
(compile-expr then)
(when else
(emit "GO ~d" (+ 2 *pc* (measure else)))
(compile-expr else)))
;;
;; MINI:LET -- like CL:LET except variables default to the numeric value 0.
;;
(define-special-operator mini::let ((&rest bindings) &body body)
(/log "~&Allocating registers for ~S~%" bindings)
(let* ((*variable-bindings* *variable-bindings*)
(bindings (normalize-bindings-list bindings))
(vars (mapcar #'first bindings))
(values (mapcar #'second bindings))
(registers (mapcar #'allocate-register vars)))
(loop for var in vars
for value in values
do (mini::set var value)
(emit "POP"))
(loop for (expr . rest) on body do
(compile-expr expr)
(when rest (emit "POP")))
(loop for r in registers do (deallocate-register r)))))
(defun normalize-bindings-list (vars)
(loop for v in vars when (symbolp v) collect (list v 0) else collect v))
(defun allocate-register (var)
(unless *measuring*
(/log "Allocating register for ~S" var)
(unless (symbolp var) (error "Variable name must be a symbol."))
(let ((register (pop *available-registers*)))
(unless register (error "Out of registers."))
(setf *variable-bindings* (acons var register *variable-bindings*))
register)))
(defun find-register (var)
(unless *measuring*
(/log "Finding register for ~S in ~S" var *variable-bindings*)
(let ((binding (assoc var *variable-bindings*)))
(unless binding (error "No binding for ~s in ~s" var *variable-bindings*))
(format nil "R~d" (cdr binding)))))
(defun deallocate-register (register)
(unless *measuring*
(push register *available-registers*)))
;;
;; MINI:TAGBODY -- similar to CL:TAGBODY. The immediate elements of
;; the tagbody are either symbols which interpreted as labels or
;; expressions to be evaluated. The labels can be jumped to with
;; MINI:GO.
;;
(define-special-operator mini::tagbody (&rest body)
(let ((*tagbody-labels* *tagbody-labels*))
(/log "~&Finding labels in tagbody~%")
(let ((*measuring* t) (*pc* *pc*))
(loop for expr in body
do (/log "~&Saw: ~s~%" expr)
when (symbolp expr) do (note-label expr)
else do (compile-expr expr)))
(/log "~&Found labels: ~s~%" *tagbody-labels*)
(loop for expr in body
unless (symbolp expr) do (compile-expr expr))))
;;
;; MINI:GO -- Jump to the given label in the most narrowly scoped
;; enclosing TAGBODY.
;;
(define-special-operator mini::go (label)
(emit "GO ~d" (find-go-target label)))
(defun note-label (label)
(/log "~&>> Noting label ~a at ~d~%" label *pc*)
(setf *tagbody-labels* (acons label *pc* *tagbody-labels*)))
(defun find-go-target (label)
(/log "~:[F~;Skipping f~]inding target for ~s in ~s~%" *measuring* label *tagbody-labels*)
(unless *measuring*
(unless (symbolp label) (error "Argument to GO must be a symbol."))
(let ((label-target (assoc label *tagbody-labels*)))
(unless label-target (error "No target ~S in ~S" label *tagbody-labels*))
(cdr label-target))))
;;
;; MINI:RETURN -- used to return from a function (not a block as in CL)
;;
(define-special-operator mini::return (&body body)
(loop for expr in body do (compile-expr expr))
(emit "RETURN"))
;;
;; MINI:SET -- simple assignment. Assigns a value (evaluated) to a named variable.
;;
(define-special-operator mini::set (var value)
(compile-expr value)
(emit "STORE ~a" (find-register var)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Other language constructs. Once we've got our primitives and
;;; special operators, we can define new language constructs with
;;; regular CL macros. However note while we can use all of CL in the
;;; definition of the macro, the code it expands into must be pure
;;; MINI--i.e. MINI special operators and primitives or macros that
;;; will eventually expand into such. Thus we can't use things like
;;; LOOP directly in MINI unless we write one ourselves because it
;;; expands into a bunch of calls to CL primitives, not MINI
;;; primitives.
(defmacro mini::defun (name (&rest params) &body body)
"A MINI defun is fairly primitive compared to a CL:DEFUN. Since a
MINI program is compiled to a single executable with static linkage
between functions, we don't need to associate the code of a function
with its name; that happens in ALLOCATE-FUNCTIONS."
(declare (ignore name))
`(mini::return
(mini::let
,(loop for p in params collect `(,p (mini::%peek)))
,@body)))
(defmacro mini::dotimes ((var count) &body body)
(let ((start-label (gensym "START"))
(end-label (gensym "END")))
`(mini::tagbody
,start-label
(mini::if (mini::= ,var ,count) (mini::go ,end-label))
,@body
(mini::set ,var (mini::+ 1 ,var))
(mini::go ,start-label)
,end-label)))
(defmacro mini::when (test &rest body)
`(mini::if ,test (mini::progn ,@body)))
(defmacro mini::unless (test &rest body)
`(mini::if (mini::not ,test) (mini::progn ,@body)))
(defmacro mini::cond (&rest clauses)
(when clauses
`(mini::if ,(caar clauses)
(mini::progn ,@(cdar clauses))
(mini::cond ,@(cdr clauses)))))
--
Peter Seibel pe...@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Kenny Tilton
Peter Seibel wrote:
> Well, since it was more fun than trying to write about pathnames (for
> my book) ...
Brave man! Well, you got me over the LOOP hurdle, can't wait.
kenny
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
Will Hartung
"Peter Seibel" <pe...@javamonkey.com> wrote in message
news:m3wu6ry...@javamonkey.com...
> Well, since it was more fun than trying to write about pathnames (for
> my book) inspired by this thread I spent a chunk of yesterday playing
> around with writing a compiler for a made up "machine". While there
> are plenty of improvements to be made to this code (such as generating
> an intermediate form that is suitable to feeding to a peephole
> optimizer) it might give you a few ideas. And I'm sure if it has any
> really *bad* ideas in it, someone else will be kind enough to point
> them out.
Heh, you beat me to it. I was going to play with this this weekend.
You cheated with a "fake" computer :-).
What I really like about this is what it represents symbolically. In the
past we bantered about ways to get a really nice split-string function, with
folks bantering back and forth make subtle adjustments. I'm sure that
happens in other forums as well.
Then there was that recent thread where the yahoo came in looking for SSE
support and I crassly suggested that perhaps a simple modification to
Cormans assembler would actually give him exactly what he asked for, to
which I got a tirade about how he was a professional, time is money, don't
fix others tools, etc. He scoffed when it was suggested that it wouldn't be
a big deal to add that functionality to Cormans CL.
Now, we have Peter who took the time to hack out a mini compiler for a
simple S-Expr based language which in reality shares with Lisp little more
than the ASCII character set.
But the fact that he was able to punch this out in a short time, and share
it with the community, it goes to show the capabilities of this environment,
and the bright side of this community.
Now I want to go over to c.l.c++ and see how many compilers have been posted
there in the past few months.
Greg, take this stone axe of a compiler, grok how the rock is grafted to the
stick with steamed sinew, then toss it away, find your own rock, your own
stick and build your own from the ground up. It's probably worth the
investment to actually start from scratch than try and reshape this into
what you want.
Regards,
Will Hartung
(wi...@msoft.com)
Duane Rettig
> Well, since it was more fun than trying to write about pathnames (for
> my book) inspired by this thread I spent a chunk of yesterday playing
> around with writing a compiler for a made up "machine".
Excellent. Where will you put it in your book? (it _has_ to go into
your book!)
> While there
> are plenty of improvements to be made to this code (such as generating
> an intermediate form that is suitable to feeding to a peephole
> optimizer) it might give you a few ideas. And I'm sure if it has any
> really *bad* ideas in it, someone else will be kind enough to point
> them out.
I don't have time to analyze thoroughly, but it looks like you have
the basics. I like that you recognize the power of carrying
macroexpand through. Perhaps someday expand-macro will also be
able to analyze its lexical environment, as well. It's easy enough
to write Lisp in Lisp; it gets a little harder as your target language
gets less and less lisp-like.
Thomas F. Burdick
> Peter Seibel <pe...@javamonkey.com> writes:
>
> > Well, since it was more fun than trying to write about pathnames (for
> > my book) inspired by this thread I spent a chunk of yesterday playing
> > around with writing a compiler for a made up "machine".
>
> Excellent. Where will you put it in your book? (it _has_ to go into
> your book!)
I'm with Duane here, this is great! Writing little compilers is one
of Lisp's traditional strenghts, but it's missing from a lot of recent
Lisp books. With microcontrollers nowadays looking like computers
from the '70s, a compiler definately has a place in a Practical Lisp
book. < 400 LOC!
Peter Seibel
> Duane Rettig <du...@franz.com> writes:
>
> > Peter Seibel <pe...@javamonkey.com> writes:
> >
> > > Well, since it was more fun than trying to write about pathnames (for
> > > my book) inspired by this thread I spent a chunk of yesterday playing
> > > around with writing a compiler for a made up "machine".
> >
> > Excellent. Where will you put it in your book? (it _has_ to go into
> > your book!)
>
> I'm with Duane here, this is great! Writing little compilers is one
> of Lisp's traditional strenghts, but it's missing from a lot of recent
> Lisp books. With microcontrollers nowadays looking like computers
> from the '70s, a compiler definately has a place in a Practical Lisp
> book. < 400 LOC!
Thanks. Does anyone have any recommendations of a good actual chip to
target? It would be cooler to present an actual compiler for a real
architecture but I don't want to get bogged down in explaining all the
ins and outs of a particular CPU. Since I'm not already familiar with
any instruction sets other than the Java VM's, a reasonable metric of
whether an architecture might be good for my purposes is, is there
architecture/instruction-set documentation available on the web that I
can download and then grok in a few hours.
I've considered targeting the JVM (though the rest of the gorp around
dealing with class files is a bit of a hassle). Other candidates are
MIX or MMIX which have the obvious advantage of being designed for
pedagogy.
-Peter
P.S. [Thomas, sorry for the dup in your mailbox, I meant to post but
hit reply instead.]
Greg Menke
A 6502 would be nice & simple. The 8052 is also pretty simple, but
has some annoying properties with make for wordy assembly- there are
fancied up variants which reduce the annoyance. But I'd go for the
6502, because then you could run it on an Atari 800- nice fp and
console right there, and with a little fiddling, it could be made to
boot directly over a serial port from your development host. The
various PIC's are quite popular but have a dreadful assembly- at least
the 16x variants. Ugly-nasty.
Gregm
Jens Axel Søgaard
> Thanks. Does anyone have any recommendations of a good actual chip to
> target? It would be cooler to present an actual compiler for a real
> architecture but I don't want to get bogged down in explaining all the
> ins and outs of a particular CPU.
The good old Z80? Nowadays it is found in Texas TI83 calculator.
--
Jens Axel Søgaard,
slightly nostalgic since the Z80 also was in his first computer a ZX81
Brian Downing
Greg Menke <gregm...@toadmail.com> wrote:
> A 6502 would be nice & simple. The 8052 is also pretty simple, but
> has some annoying properties with make for wordy assembly- there are
> fancied up variants which reduce the annoyance. But I'd go for the
> 6502, because then you could run it on an Atari 800- nice fp and
> console right there, and with a little fiddling, it could be made to
> boot directly over a serial port from your development host.
Bonus points if you can find a 6502 (or other) machine that has had its
ROMs available publicly, so one could legally download an emulator to
try out examples from the book without actually owning one of the
machines.
That would be one hell of a practical example! "Here's a working
compiler for a real architecture, and here's how to try out the results
on your computer."
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Greg Menke
This is exactly the kind of language implementation I'm thinking of.
I'm groveling around cooking up an ABI that will support the the
amount of Lisp-ness I want. No strings, gc, conses, closures, structs
or sequences to begin with, but it'll start with strongly typed
8,16,32 bit ints, fp, and chars and the usual pile of functions to
fiddle with them. First I'll walk, then run, then rule. ;)
Gregm
Will Hartung
> t...@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Thanks. Does anyone have any recommendations of a good actual chip to
> target? It would be cooler to present an actual compiler for a real
> architecture but I don't want to get bogged down in explaining all the
> ins and outs of a particular CPU. Since I'm not already familiar with
> any instruction sets other than the Java VM's, a reasonable metric of
> whether an architecture might be good for my purposes is, is there
> architecture/instruction-set documentation available on the web that I
> can download and then grok in a few hours.
Seriously, you should consider something bone simple like the 8086 .COM
model running DOS.
I think most every person with a computer can actually try out your code and
you can write Interesting Programs and readily test them. Simple DOS
interrupts for basic console I/O.
Using the classic "tiny" memory model, the 8086 is basically a high end Z80.
Set all of the segment registers to 0, assume the 64K memory block, a MS-DOS
COM file is a binary image loaded at I think #x0100 (it may load at 0, and
just have execution start at #x0100..I forget).
There's nothing that says you have to leverage the entire instruction set.
Lots of resources, minimal set up, several popular assemblers. Just treat it
as an 8-Bit computer and go on your merry way. It also helps that 95% of the
machines on the planet today can run the compiled code directly.
Regards,
Will Hartung
(wi...@msoft.com)
Erann Gat
<pe...@javamonkey.com> wrote:
> t...@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > Duane Rettig <du...@franz.com> writes:
> >
> > > Peter Seibel <pe...@javamonkey.com> writes:
> > >
> > > > Well, since it was more fun than trying to write about pathnames (for
> > > > my book) inspired by this thread I spent a chunk of yesterday playing
> > > > around with writing a compiler for a made up "machine".
> > >
> > > Excellent. Where will you put it in your book? (it _has_ to go into
> > > your book!)
> >
> > I'm with Duane here, this is great! Writing little compilers is one
> > of Lisp's traditional strenghts, but it's missing from a lot of recent
> > Lisp books. With microcontrollers nowadays looking like computers
> > from the '70s, a compiler definately has a place in a Practical Lisp
> > book. < 400 LOC!
>
> Thanks. Does anyone have any recommendations of a good actual chip to
> target?
I like the 6811. See http://www.newmicros.com/
You can also target the host processor to do e.g. inline floating point
computations. See
http://vorlon.cwru.edu/~beer/Software/FPC-PPC/FPC-PPC-DOC-0.1.txt for an
example.
E.
Bruce Stephens
[...]
> I've considered targeting the JVM (though the rest of the gorp
> around dealing with class files is a bit of a hassle). Other
> candidates are MIX or MMIX which have the obvious advantage of being
> designed for pedagogy.
parrot seems like another potentially useful one. Probably similar to
JVM, in that it might actually be useful (MIX and MMIX probably
wouldn't be), but might be too messy as an example (presumably MIX and
MMIX are clean).
[...]
Greg Menke
Its easy enough to run an Atari emulator, a bit of googling will find
it. The roms are easy to find, the trickiest being the rom Basic as I
recall- which wouldn't be needed for this example. The rom bios can
boot from a floppy, which can be rigged as an appropriately formatted
file on the emulator host PC- though this sort of thing is more or
less Windows only IIRC.
Gregm
Edi Weitz
> Bonus points if you can find a 6502 (or other) machine that has had
> its ROMs available publicly, so one could legally download an
> emulator to try out examples from the book without actually owning
> one of the machines.
I suspect they're hard to find (if you insist on "legal") although I'd
love to see the Apple II (my first computer) as the target machine.
(M)MIX probably is the way to go because legal emulators exist. Plus
there are books about it and support websites. Knuth's page
<http://www-cs-faculty.stanford.edu/~knuth/mmix-news.html>
even says that there's official gcc support for MMIX... :)
> That would be one hell of a practical example! "Here's a working
> compiler for a real architecture, and here's how to try out the
> results on your computer."
Yep! That'd be great. Go Peter!!!
Edi.
Brett Gibson
wrote:
> Thanks. Does anyone have any recommendations of a good actual chip to
> target? It would be cooler to present an actual compiler for a real
> architecture but I don't want to get bogged down in explaining all the
> ins and outs of a particular CPU. Since I'm not already familiar with
> any instruction sets other than the Java VM's, a reasonable metric of
> whether an architecture might be good for my purposes is, is there
> architecture/instruction-set documentation available on the web that I
> can download and then grok in a few hours.
<Unlurk>
I suggest the ARM processors: they have the benefit of having a RISC
design with a clean instruction set that isn't too difficult to learn
for someone not versed in assembler. Also, they are found in a large
proportion of modern hand-held devices.
Brett
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Tim Lavoie
> Thanks. Does anyone have any recommendations of a good actual chip to
> target? It would be cooler to present an actual compiler for a real
> architecture but I don't want to get bogged down in explaining all the
> ins and outs of a particular CPU. Since I'm not already familiar with
> any instruction sets other than the Java VM's, a reasonable metric of
> whether an architecture might be good for my purposes is, is there
> architecture/instruction-set documentation available on the web that I
> can download and then grok in a few hours.
Henry Baker's COMFY compiler targeted 6502 using Emacs Lisp to compile
a mini language, so it's an interesting read regardless of what you
target. The 6-page paper includes the compiler source. :)
http://portal.acm.org/citation.cfm?id=270947&jmp=cit&dl=GUIDE&dl=ACM
On the other hand, compiling to Java class files would be really neat,
and widely available for people to play with.
Kenny Tilton
Tim Lavoie wrote:
> Peter Seibel <pe...@javamonkey.com> wrote in message news:<m3u11uw...@javamonkey.com>...
>
>
>>Thanks. Does anyone have any recommendations of a good actual chip to
>>target?
> Henry Baker's COMFY compiler targeted 6502...
6502 is my vote, too, perhaps only because that is the only chip I have
programmed. Two registers, three addressing modes, Boom!, yer done.
> On the other hand, compiling to Java class files would be...
..good for Lava, the sequel to PL?
kt
Thomas F. Burdick
Having poked around a little bit, it looks like there's a bunch of
good stuff, including emulators and assemblers/disassemblers for the
6502 at (gasp) www.6502.org. It's probably a good bet that your
readers will be more software inclined than hardware inclined, and the
6502 has the advantage that even horrible EEs like yours truly can
make functioning stuff with it. With their MINI->6502 compiler,
they'd be only a trip to the electronics store from having a working
implementation of the cofee pot control protocol.
jan
[snip: Peter's compiler]
I had a couple problems running your compiler, firstly there were
parenthesis mismatches. I assume this was due to image/source
differences and not because you typed the whole thing into your mail
editor untested ;-)
Also, when compiled (on CMUCL) it corrupted &key argument
handling. Loading the source file works fine. Fixing this is left as
an exercise for the writer.
Anyway, to the point, here's where I would do things a little
differently.
(defpackage :mini
(:documentation "The package where we define the MINI language.")
(:use)
(:import-from :cl "WHEN" "UNLESS" "COND"))
(defun compile-cons (code)
"As in common lisp there are three ways to evaluate a cons: as a
macro call, as a special operator call, or as a function call."
(destructuring-bind (first &rest rest) code
(unless (symbolp first) (error "Expected symbol, got ~S" first))
(let ((first (find-symbol (symbol-name first) :mini)))
(cond
((macro-function first)
(compile-expr (expand-macro code)))
((mini-special-operator-p first)
(apply first rest))
(t (compile-function-call first rest))))))
(defun expand-macro (code)
"Note that we get to use the CL macro mechanism here. This is huge!"
(/log "~&Macro expanding ~s~%" code)
(macroexpand-1 code))
Now we don't need to reimplement WHEN, UNLESS and COND. On CMUCL we
can't remove DOTIMES yet because we need BLOCK, RETURN-FROM and PSETQ
as primitives first. Although implementing these is more work than
just implementing DOTIMES directly, once done we get LOOP for free.
(dotimes (n 5)
(print n)) macroexpands to =>
(BLOCK NIL
(LET ((N 0))
(DECLARE (TYPE (INTEGER 0 10) N))
(TAGBODY
(GO #:G3008)
#:G3007
(PRINT N)
(PSETQ N (1+ N))
#:G3008
(UNLESS (>= N 10) (GO #:G3007))
(RETURN-FROM NIL (PROGN NIL)))))
(loop for x from 27
repeat 5
do (print x)) macroexpands to =>
(BLOCK NIL
(LET ((X 27))
(DECLARE (TYPE NUMBER X))
(LET ((#:G3012 32))
(DECLARE (TYPE REAL #:G3012))
(TAGBODY
ANSI-LOOP::NEXT-LOOP
(IF
(MINUSP
(LET* ((#:G3013 (- #:G3012 1)))
(SETQ #:G3012 #:G3013)))
(PROGN NIL (GO ANSI-LOOP::END-LOOP))
NIL)
(PRINT X)
(SETQ X (1+ X))
(GO ANSI-LOOP::NEXT-LOOP)
ANSI-LOOP::END-LOOP))))
--
jan
Rob Warnock
+---------------
| Greg, take this stone axe of a compiler, grok how the rock is grafted to the
| stick with steamed sinew, then toss it away, find your own rock, your own
| stick and build your own from the ground up. It's probably worth the
| investment to actually start from scratch than try and reshape this into
| what you want.
It's probably also worth looking at the chapters on compiling in
Norvig's "PAIP", both the byte-code and compiling-to-C sections.
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Kalle Olavi Niemitalo
> 6502 is my vote, too, perhaps only because that is the only chip I
> have programmed. Two registers, three addressing modes, Boom!, yer
> done.
Surely there are more.
http://www.obelisk.demon.co.uk/6502/addressing.html
I was analyzing some 6502 code a few weeks ago, to work around
misfeatures in a C64 game. Found several jump tables there,
apparently for dynamically loaded blocks of code.
Kenny Tilton
Kalle Olavi Niemitalo wrote:
> Kenny Tilton <kti...@nyc.rr.com> writes:
>
>
>>6502 is my vote, too, perhaps only because that is the only chip I
>>have programmed. Two registers, three addressing modes, Boom!, yer
>>done.
>
>
> Surely there are more.
> http://www.obelisk.demon.co.uk/6502/addressing.html
>
I was thinking of the interesting ones: zero-page, indexed indirect, and
indirect indexed. That link calls "load accumulator" an addressing mode,
and identifies an indirect addressing mode used only by the jump
instruction. The absolute modes would be a yawn to implement as well
(not that my favorite three are that hard.)
Marco Antoniotti
Doing the JVM is a great idea. However, for a real life CPU I would
target the ARM instruction set. My times with the EE crowd are in the
past, but a lot of people (meaning HW vendors) were licensing ARM cores
for their products. Things may have changed and this is nothing more
than an anecdote, but it may help you making up your mind.
Cheers
--
Marco
Marc Battyani
"Peter Seibel" <pe...@javamonkey.com> wrote
>
> Thanks. Does anyone have any recommendations of a good actual chip to
> target? It would be cooler to present an actual compiler for a real
> architecture but I don't want to get bogged down in explaining all the
> ins and outs of a particular CPU. Since I'm not already familiar with
> any instruction sets other than the Java VM's, a reasonable metric of
> whether an architecture might be good for my purposes is, is there
> architecture/instruction-set documentation available on the web that I
> can download and then grok in a few hours.
>
> I've considered targeting the JVM (though the rest of the gorp around
> dealing with class files is a bit of a hassle). Other candidates are
> MIX or MMIX which have the obvious advantage of being designed for
> pedagogy.
I vote for a modern, compiler friendly, cheap ($5) 16 bits micro-controller
architecture: The MSP430 (Texas Instrument)
There are lots of docs on the TI web site and the parts are readily available
at www.digikey.com for instance.
If you are interested, I even can give you a schematics and PCB design.
Marc
Peter Seibel
> Peter Seibel <pe...@javamonkey.com> writes:
>
> [snip: Peter's compiler]
>
> I had a couple problems running your compiler, firstly there were
> parenthesis mismatches. I assume this was due to image/source
> differences and not because you typed the whole thing into your mail
> editor untested ;-)
Actually I tapped it out in morse code using the space bar. But my
morse is a bit rusty. ;-)
> Also, when compiled (on CMUCL) it corrupted &key argument handling.
> Loading the source file works fine. Fixing this is left as an
> exercise for the writer.
Strange.
So I'm not sure I get this--aside from the fact that we don't know for
certain (i.e. the standard doesn't say) what WHEN, UNLESS, and COND
expand into, even if we assume they expand into the obvious use of IF
and PROGN, they expand into uses of CL:IF and CL:PROGN. So you'd have
to change more than you've show here. In theory you could hang stuff
off the plists of CL symbols but you couldn't use my technique of
defining a function on the symbol that generates the code because you
can't redefine functions in the CL package. But even if you did make
those changes, consider what would happen if you were running in a
Common Lisp that for implemented IF, WHEN, UNLESS, and COND as macros
that expand to some implementation-dependent primitive. There's no way
for the MINI compiler to know how to compile that primitive.
Or am I missing something?
-Peter
Peter Seibel
> In article <m3u11ue...@europa.pienet>,
> Greg Menke <gregm...@toadmail.com> wrote:
> > A 6502 would be nice & simple. The 8052 is also pretty simple, but
> > has some annoying properties with make for wordy assembly- there are
> > fancied up variants which reduce the annoyance. But I'd go for the
> > 6502, because then you could run it on an Atari 800- nice fp and
> > console right there, and with a little fiddling, it could be made to
> > boot directly over a serial port from your development host.
>
> Bonus points if you can find a 6502 (or other) machine that has had its
> ROMs available publicly, so one could legally download an emulator to
> try out examples from the book without actually owning one of the
> machines.
Okay, so I did some poking around and am beginning to wrap my head
around this. But some things are still fuzzy. Let me see if I've got
this straight. To start at the beginning:
- Since the 6205 is just a CPU in real life (i.e. hardware) it needs
to be embedded into an actual computer that provides I/O etc.
- All these computers, e.g. the Atari 2600, have their own scheme of
mapping memory to i/o devices, etc.
- And actual computers built on the 6205 have had their "OS" in ROM
that was part of the computer.
- Additionally systems like the Atari loaded new software (the
games) via ROM cartridges.
Assuming that's basically right, I'm trying to understand how these
various parts map onto software emulators.
- Presumably it doesn't make much sense to have a generic 6205
emulator any more thna it makes sense to have just a CPU with no
motherboard, etc.
- It does make sense to have an emulator for a complete system like
the Atari 2600 (e.g. Stella[1]).
- A complete system emulator presumably includes the OS ROM or
facsimile thereof.
- An emulator for an actual system knows how to load and run a file
that contains the literal data (i.e. code) contained on a ROM game
cartgridge. On other systems these ROMs might include things like
BASIC.
For my purposes, I don't actually need any of the game ROM's since I'm
going to be writing a compiler that generates the code that I want to
run. (Which is good, because those ROMs are only legally available to
folks who actually own the cartridge.)
If *that's* all correct, then it seems that if I actually want to
write a compiler that generates code that someone can run on an
emulator, I need to not only pick a particular CPU to target but also
a complete system for which there are emulators available.
And presumably writing a compiler that generates "executables" for
such an emulator is a bit more work than just generating 6205
instructions. But has the advantage that you can actually do something
with the code you generate.
If all *that* is correct, does anyone have a good recomendation for a
good emulator to target--ideally something that runs on Linux, OS X,
and Windows and is free (as in beer) and easy to install.
Or if I'm looking at this the wrong way, maybe someone can clear up my
confusion. Thanks.
-Peter
[1] <http://stella.sourceforge.net/>
Bulent Murtezaoglu
PS> recomendation for a good emulator to target--ideally something
PS> that runs on Linux, OS X, and Windows and is free (as in beer)
PS> and easy to install.
I'd look into Palm emulators and/or fancy telephone emulators. Or maybe
you could target something like the PIC and bundle an evaluation version
of a cross platform lisp (LW covers all three OSs with the same graphical
toolkit) along with a little PIC simulator written in Lisp showing little
lights etc. connected to the little chip. If people want real hardware
PIC kits can be cheap. Or maybe an ARM9 but I don't know if the ARM
simulator is (still?) free.
PS> Or if I'm looking at this the wrong way, maybe someone can
PS> clear up my confusion. Thanks.
I like this idea but I don't know if it is a good idea for you to do
this. There are a lot of things that can frustrate your reader (esp.
several years after the publication) and you probably don't want to
get "I can't get the simulator to work on my machine, you suck" kind
of e-mail. Doing everything including the simulator in Lisp would
help with that though (that's partly why I dreamt that option up).
cheers,
BM
Paul Wallich
> Brian Downing <see-si...@lavos.net> writes:
>
>
>>In article <m3u11ue...@europa.pienet>,
>>Greg Menke <gregm...@toadmail.com> wrote:
>>
>>>A 6502 would be nice & simple. The 8052 is also pretty simple, but
>>>has some annoying properties with make for wordy assembly- there are
>>>fancied up variants which reduce the annoyance. But I'd go for the
>>>6502, because then you could run it on an Atari 800- nice fp and
>>>console right there, and with a little fiddling, it could be made to
>>>boot directly over a serial port from your development host.
>>
>>Bonus points if you can find a 6502 (or other) machine that has had its
>>ROMs available publicly, so one could legally download an emulator to
>>try out examples from the book without actually owning one of the
>>machines.
>
>
> Okay, so I did some poking around and am beginning to wrap my head
> around this. But some things are still fuzzy. Let me see if I've got
> this straight. To start at the beginning:
>
> - Since the 6205 is just a CPU in real life (i.e. hardware) it needs
> to be embedded into an actual computer that provides I/O etc.
Just for nitpicking: 6502 (someone else no doubt has a 6205), which is
actually the base of a family including the 6510 (with extra
instructons) and 6507(?) (with some onboard ram and limited address lines)
> - All these computers, e.g. the Atari 2600, have their own scheme of
> mapping memory to i/o devices, etc.
> - And actual computers built on the 6205 have had their "OS" in ROM
> that was part of the computer.
>
> - Additionally systems like the Atari loaded new software (the
> games) via ROM cartridges.
They didn't really load software via ROMs -- the ROM simply supplied
data at XXXX-YYYY of the address space.
I think you may be looking at things a little bit wrong here. First,
some emulators, in addition to showing simulated screen output, also
show what's going on under the hood. So you can have programs that "do"
things just by altering memory locations & so forth. (And, of course, a
lot of what happens in games is just a matter of twiddling particular
memory locations)
Second, insofar as there is a rudimentary OS/library on these old
machines, what you want is a linker rather than a monolithic compiler
targeted to a single system.
On the one hand, this means that your initial version will probably only
be able to do relatively simple I/O things (keyboard input, character
output to screen). On the other hand, if you write the code
transparently it will be obvious to a reader how to extend it for any
given system being emulated, and that will be a fun and easy project to
get them hooked.
paul
Christopher C. Stacy
what you're talking about here. But I wanted to say this, in case
it's relevent. If you're going to implement a subset Lisp compiler
as a teaching example, be sure to strongly highlight: the fact that
it's not anything like a complete Common Lisp, people don't normally
program in this subset, and that the performance of real implementations
of Lisp is based on advanced techniques not represented here.
Otherwise, clueless idiots will conclude and cite and try to use it
as if it were a real CL implementation, and people will believe them,
and we'll never dig out of their misinformation.
You probably already realize this, but I couldn't contain myself.
Marc Battyani
"Peter Seibel" <pe...@javamonkey.com> wrote
>
> If *that's* all correct, then it seems that if I actually want to
> write a compiler that generates code that someone can run on an
> emulator, I need to not only pick a particular CPU to target but also
> a complete system for which there are emulators available.
The microcontroller I mentioned in another post (MSP430) has an emulator and
even a gcc cross compiler toolchain (hosted on SF). So you just have to emit
object code compatible with these to have it working.
And it's a microcontroller so this mean it's self contained with
CPU,RAM,FLASH,I/O, timers, A/D, PWM, UART, etc.
So I still think it's a much better choice than some old design like the
6502.
Marc
Jens Axel Søgaard
> If all *that* is correct, does anyone have a good recomendation for a
> good emulator to target--ideally something that runs on Linux, OS X,
> and Windows and is free (as in beer) and easy to install.
Since this book is going to be read for many years, the current solution
where you have made an emulator for your own simple assembler language
is actually more likely to stand to test of time than choosing some
arbitrary processor.
The coolness factor is of course higher, when people can see their
code run at an actual piece of hardware, but since most people will
end up using the emulator, it really doesn't matter whether it is an
emulator for an ad hoc language or an real one.
A compromise would be to include an emulator written in CL for a subset
of an actual machine language. This might be easier to do than one
might think.
At the 1996 Scheme Compiler Workshop they wrote a compiler
targeting a Sparc. To ease testing they included a small Sparc
emulutor.
The emulator:
<http://www.cs.indiana.edu/eip/compile/emu.ss>
(run it in ChezPetite)
The greater picture:
<http://www.cs.indiana.edu/eip/compile/>
--
Jens Axel Søgaard
Greg Menke
Its not a teaching tool- its a tool to write software to run in a
gizmo. I'm faced with writing code for this processor again, and I
don't want to re-open old wounds trying to get something written using
the built-in Basic. A mini-pseudo-lisp gives vastly improved syntax
and a lot of features the rom basic doesn't have. It'll probably be
lots faster too. It is not intended to be a large part of CL, or
comprehensive in any particular way, its more of a pain reduction
tool. I think anyone who's dealt with maintaining programs written in
8052 Basic would jump at anything whatsoever that provides an
alternative. Its not as bad as the Basic in the Parallax Stamp- but
its still pretty bad.
Gregm
jan
The change I made to COMPILE-CONS handles this:
(let ((first (find-symbol (symbol-name first) :mini)))
eg. It will see CL:IF and convert it to MINI:IF.
> But even if you did make those changes, consider what would happen
> if you were running in a Common Lisp that for implemented IF, WHEN,
> UNLESS, and COND as macros that expand to some implementation
> dependent primitive. There's no way for the MINI compiler to know
> how to compile that primitive.
Yes, the code is not strictly portable, but neither are threads and
that hasn't stopped anybody. Also note that the other change I made to
your code was changing macroexpand to macroexpand-1 which allows
COMPILE-CONS to stop further expansion if it sees a primitive it
recognises. This may give enough independence from the CL
implementation's design choices to be able to choose a set of MINI
primitives that could make this fairly portable (I haven't tried yet
though).
--
jan
Paolo Amoroso
> I'd look into Palm emulators and/or fancy telephone emulators. Or maybe
Palm emulators need ROMs, which are legally available only to
registered developers, or can be downloaded from an actual Palm OS
device.
Paolo
--
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Rob Warnock
+---------------| > ... If you're going to implement a subset Lisp compiler
| > as a teaching example, be sure to strongly highlight: the fact that
| > it's not anything like a complete Common Lisp, people don't normally
|
| ... A mini-pseudo-lisp gives vastly improved syntax and a lot of
| features the rom basic doesn't have. ... It is not intended to be
| a large part of CL, or comprehensive in any particular way, its more
| of a pain reduction tool.
In that case, you might want to piggyback on a classical acronym from
the old days: LAP, for Lisp Assembly Program. You can call your compiler
"LAP with some convenience Lisp macros", if you want to be really safe. ;-}
-Rob
p.s. I've been musing off & on for some time about a "LAP-C"
[double pun intended], which would be an S-expr representation
of C source that would allow "convenience Lisp macros" for doing
all the neat compile-time stuff that "#define" is so terrible at.
Does anyone know of any past projects along those lines...?
Note: I am quite familiar with Aubrey Jaffer's "Schlep", a simple
Scheme-subset to C transliterator, but it uses a kind of Hungarian
mangling of symbols [though with suffixes instead of the more common
prefixes] to convey type information to the C output, and for some
time now I've felt that a CL-subset to C transliterator would be more
perspicuous, since one could use normal CL declaration syntax to capture
the type info instead of Hungarian. [A couple of years ago I hacked
on "Schlep" for a while trying to add CL declaration syntax, and got
bogged down. But that was before I started programming in anger in CL...
Hmmm... Maybe now...]
In any case, those interested in Lispy mini-languages for hardware work
might find it interesting to read the following:
<URL:http://swiss.csail.mit.edu/~jaffer/Work/>
<URL:http://swiss.csail.mit.edu/~jaffer/Work/scm95-1>
<URL:http://swiss.csail.mit.edu/~jaffer/Work/scm95-2>
<URL:http://swissnet.ai.mit.edu/~jaffer/Docupage/schlep.html>
<URL:http://swissnet.ai.mit.edu/~jaffer/Docupage/schlep.scm>
Older version:
<URL:http://swissnet.ai.mit.edu/ftpdir/users/jaffer/schlep.scm>
Greg Menke
I think you should call the language "Dance", so then it'd be LAP Dance.
Gregm
Michael Livshin
> rp...@rpw3.org (Rob Warnock) writes:
>
>> p.s. I've been musing off & on for some time about a "LAP-C"
>> [double pun intended], which would be an S-expr representation
>> of C source that would allow "convenience Lisp macros" for doing
>> all the neat compile-time stuff that "#define" is so terrible at.
>> Does anyone know of any past projects along those lines...?
>
> I think you should call the language "Dance", so then it'd be LAP
> Dance.
I've also been thinking about such a thing (because I really need it),
but so far the only aspect I've actually had the time/gumption to
produce is the name: MaCkerel.
I'll get me coat,
--m
--
Tools that are no good require more skill.
Jens Axel Søgaard
>>>p.s. I've been musing off & on for some time about a "LAP-C"
>>>[double pun intended], which would be an S-expr representation
>>>of C source that would allow "convenience Lisp macros" for doing
>>>all the neat compile-time stuff that "#define" is so terrible at.
>>>Does anyone know of any past projects along those lines...?
Do you know PreScheme?
<ftp://ftp.ccs.neu.edu/pub/people/wand/vlisp/lasc/prescheme.ps.gz>
Source can be found in the distribution of Scheme48.
--
Jens Axel Søgaard
Jens Axel Søgaard
> Do you know PreScheme?
>
> <ftp://ftp.ccs.neu.edu/pub/people/wand/vlisp/lasc/prescheme.ps.gz>
I meant to give this link:
<http://mumble.net/~kelsey/papers/prescheme.ps.gz>
--
Jens Axel Søgaard
Rob Warnock
+---------------
Yes, of course. But the last time I looked at it [which I admit was
quite some time ago] it seemed pretty closely targeted to generating
code for the Scheme48 VM. Do you know of anyone who has successfully
used it for some other target?
-Rob
Thomas Lindgren
> "Will Hartung" <wi...@msoft.com> writes:
>
> I agree with everything Will said here, and just want to add:
>
> > You'll find that your 100-200 line compiler is doing AMAZING things, then
> > try some other parts and go "Oh, woe, that's really gross code..." and
> > pretty soon you're optimizing stuff.
> >
> > But since it's all incremental, the development can be really efficient.
>
> I highly recommend using some sort of constraints system like Cells or
> KR. Common Lisp is already a great compiler toolkit, and a simple
> one-way constraints system adds a lot of value. You can keep stuff
> organized a lot more easily (or at least I could) if you add your
> optimizations as declarative rules.
This sounds interesting. Please expand. (My personal experience was in
encoding how to optimize various operations given type
information. This ended up as a kind of decision-tree interpreter, but
wasn't really satisfactory.)
Best,
Thomas
--
Thomas Lindgren
"It's becoming popular? It must be in decline." -- Isaiah Berlin
Jens Axel Søgaard
> Jens Axel Søgaard <use...@jasoegaard.dk> wrote:
> | Do you know PreScheme?
> | <ftp://ftp.ccs.neu.edu/pub/people/wand/vlisp/lasc/prescheme.ps.gz>
> | Source can be found in the distribution of Scheme48.
> +---------------
> Yes, of course. But the last time I looked at it [which I admit was
> quite some time ago] it seemed pretty closely targeted to generating
> code for the Scheme48 VM. Do you know of anyone who has successfully
> used it for some other target?
I am told Vlisp and Scheme48 were seperate projects both using Prescheme.
Unfortunately that's all I know.
--
Jens Axel Søgaard
Cameron MacKinnon
> Jens Axel Søgaard <use...@jasoegaard.dk> wrote:
> | Do you know PreScheme?
> | <ftp://ftp.ccs.neu.edu/pub/people/wand/vlisp/lasc/prescheme.ps.gz>
> | Source can be found in the distribution of Scheme48.
>
> quite some time ago] it seemed pretty closely targeted to generating
> code for the Scheme48 VM. Do you know of anyone who has successfully
> used it for some other target?
It's a good paper in this context. There's also
http://citeseer.nj.nec.com/kelsey89realistic.html
The same author expands on techniques to build a compiler with multiple
front ends. The example in the paper transforms Pascal to MC68020 assembly.
--
Cameron MacKinnon
Toronto, Canada
Luke J Crook
> In article <m3u11ue...@europa.pienet>,
> Greg Menke <gregm...@toadmail.com> wrote:
>
>>A 6502 would be nice & simple. The 8052 is also pretty simple, but
>>has some annoying properties with make for wordy assembly- there are
>>fancied up variants which reduce the annoyance. But I'd go for the
>>6502, because then you could run it on an Atari 800- nice fp and
>>console right there, and with a little fiddling, it could be made to
>>boot directly over a serial port from your development host.
>
>
> Bonus points if you can find a 6502 (or other) machine that has had its
> ROMs available publicly, so one could legally download an emulator to
> try out examples from the book without actually owning one of the
> machines.
You could always target this machine (when it is released). ARM + Z80 +
6502.
-Luke
Brian Mastenbrook
<pe...@javamonkey.com> wrote:
> If all *that* is correct, does anyone have a good recomendation for a
> good emulator to target--ideally something that runs on Linux, OS X,
> and Windows and is free (as in beer) and easy to install.
Perhaps you can look at SIMH, which has emulators for a huge number of
systems (including VAX, which runs NetBSD!).
http://simh.trailing-edge.com .
--
Brian Mastenbrook
http://www.cs.indiana.edu/~bmastenb/
Rob Warnock
+---------------
| Peter Seibel <pe...@javamonkey.com> wrote:
| > If all *that* is correct, does anyone have a good recomendation for a
| > good emulator to target--ideally something that runs on Linux, OS X,
| > and Windows and is free (as in beer) and easy to install.
|
| Perhaps you can look at SIMH, which has emulators for a huge number of
| systems (including VAX, which runs NetBSD!).
| http://simh.trailing-edge.com .
SIMH also contains an emulator for the KS-10 (DECsystem-2020) flavor
of the PDP-10/-20 family, which is capable of running [selected versions]
of the actual classic operating systems -- TOPS-10, TOPS-20, and even ITS!
In fact, since it includes an emulation of a DZ11 multi-line terminal
multiplexor implemented as a Telnet daemon, there are even a few
multi-user TOPS-10 systems running in emulation out there on the net!
Ironically, using an 800 MHz P3, it runs ~10x a real KS10! ;-} ;-}
Anyway, I mention this because the PDP-10 instruction set is interesting
[simple, clean, 16-register machine, with instructions constructed
in a mostly-orthogonal way -- my favorite-ever machine architecture
to code in assembler!], and is historically interesting as well [see
<URL:http://www.lispworks.com/reference/HyperSpec/Body/f_ldb.htm> and
<URL:http://www.lispworks.com/reference/HyperSpec/Body/f_dpb.htm>].
Personally, I think that the PDP-10 instruction set is a far better
ISA to use for tutorials than, say, MIX. Also, it support both stack-
oriented subroutines *and* fully-optimized tail calls. ;-} ;-}
I'm not kidding, actually: there was a standard convention of using the
"PJSRT" macro -- which just expanded into a JRST (unconditional jump) --
whenever the last two instructions of a subroutine would have been
"PUSHJ P,somewhere" immediately followed by "POPJ P,0". And it was
very common for assembly-language programmers to provide curried
versions of functions, with entry points that set up the constant
arg(s) and then PJRST'd (or, where convenient, fell into) to the
fully-general function. E.g., if EXPT computes register T0 raised
to the register T1 power, then:
quarto: movei t1,4 ; call with arg in t0
pjrst expt ; (cheaper than two skips)
cube: movei t1,3 ; call with arg in t0
skipa
square: movei t1,2 ; (ditto)
expt: ...
...raise t0 to t1 power...
...
popj p,0
Christopher C. Stacy
Rob> Brian Mastenbrook <NObmast...@cs.indiana.edu> wrote:
Rob> +---------------
Rob> | Peter Seibel <pe...@javamonkey.com> wrote:
Rob> | > If all *that* is correct, does anyone have a good recomendation for a
Rob> | > good emulator to target
Rob> |
Rob> | Perhaps you can look at SIMH, which has emulators
Rob> +---------------
Rob> Anyway, I mention this because the PDP-10 instruction set
By the way, the PDP-10 instruction set was specifically designed to be
a good LISP machine. For starters, every memory location is a CONS cell,
and the basic memory access instructions are the CAR and CDR instructions,
Other features include the addressing modes and multiple stacks.
(It doesn't include built-in data type checking like the Lisp Machine
architectures; that wasn't clearly part of the Lisp model in 1964/67).
Of course, there are already lots of Lisp implementations for the PDP-10.