Hi,

Edit: I forgot to mention that if you know any existing Lisp implementation for 6502 I am also interested to have a look at it for ideas, although I'm quite convinced I need to write my own to get what I really want.

I used to program C64 in assembly back in the '90s, writing a few intros and utils, and played C64 games several hours a day as a child.

I'd like to implement a simple Lisp, something similar to Scheme dialect, for my C64 and (maybe later) to my non-existing custom-built 65c816 board. C64 is the only 65xx hardware I have ATM so the first version will be for that anyway. As you might know, Lisp is a dynamically typed language, which poses some problems for implementing it efficiently and I could use some optimization ideas. I try to explain my design thoughts so that you will understand them even if you have not implemented Lisp yourself (if you have no idea what it is try http://schemers.org/ ).

I have thought of having a 24-bit general datatype, where first 16 bits represent either an integer (or true/false/end-of-list etc. values) or a pointer. The last byte is a type tag that tells how to interpret the first 16 bits (00=16-bit integer,01=cons cell, 02=pointer to vector, 03=truth value, 04=end-of-list, 05=pointer to rational number, 06=pointer to string.. ..) I would, in addition to this dynamic typing scheme, have functions for 8- and 16-bit operations as an optimization:


The numeric tower would include arbitrarily sized rationals in addition to 16-bit integers, but not floating point numbers as rationals can be used instead, as many people in this forum have pointed out (thank you!).

Garbage collection would be done by scanning ZP and stack (and global variables located elsewhere) for Lisp values, marking pointers in heap and then deallocating any values in heap that are not referenced by anything. Note that the gc does not have to know whether some address in f.e. stack is really a Lisp word or a subroutine return address, because in the worst case some memory that could be freed is retained and I can live with that, since it will happen unfrequently in practice.

The system would of course have both an interpreter (quite easy) and an optimizing compiler (much harder but should be doable). The interpreter is always included in the runtime system, because Lisp code can be created and executed by other Lisp procedures and interpreter is very useful for debugging anyway, when you have debugged some piece of code you just compile it so it will run faster.

Natural choice for an implementation language would be to write this system in Lisp. However 64k of memory (and lack of compiler in the first version) will make this rather difficult, so bulk of the code will be written in 6502 assembler and some parts of the runtime system will maybe be written in Lisp. With 65c816 situation would be different, but as I am more familiar with software than hardware design I will first use existing hardware.

Some words about the compiler: I hope I'm able to fit in in the system, so that I could compile functions one at a time, when I want to do so, without resorting to a PC. I have a general idea: first the compiler does some high-level optimizations on the source code-resembling intermediate representation, then it will lower the code for a Forth-like stack machine, do some peephole optimizations and then (at last ) compile it to machine code. With so few a registers, stack machine will be probably be the best intermediate representation, in my opinion anyway. Any thoughts on this?

Hi moonshine
Ian Piumarta wrote a minimal LISP interpreter called LYSP which he says compiles down to 21K of x86 code. (It's written in C)

It might be worth a look at his implementation, even if you're more inclined to re-implement than to port. I'm sure you're right that re-implementation will be a better learning experience.

But then, you want a compiler, not an interpreter...

I found some other pointers to small LISPs here and here but again I think most won't be compiling to machine code.

Cheers
Ed

Thanks for your comments! I will first do just a simple interpreter, as I have read some papers on Lisp optimization, as well as the Dragon Book (Compilers: Principles, Techniques and tools) and the compiler is going to take some time and effort if done right. Probably it is best not to try too much initially, and improve it later. Also after my first post I started to wonder how to efficiently compile procedure calls when some of the calls may actually invoke the interpreter, and this problem is still unresolved.

Ah, the Dragon book - I should study that some time.

For implementation ideas you might be interested to read jonesforth, which comes recommended as a self-explaining small Forth in one file of assembly. It has been ported to PPC too, and also has inspired another small lisp

Another connection: a friend of mine is implementing a Scheme: I think he started from the stack-based model found in this paper which he runs on a VM inspired by jonesforth.

Some interesting links and info on 8-bit lisp/scheme here

http://www.ip9.org/munro/skimp/

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

great link!

Edit: it's a scheme for z80, archived at http://web.archive.org/web/201001311519 ... nro/skimp/

Thanks again for these links, I'm going to read them now. Actually R. Kent Dygwig's paper is the one I referred to when I said I've read a paper about Lisp optimization I think I will read it once more though. I'm going to use a stack-based approach. There is one other paper I know of, http://www.gnu.org/software/guile/manua ... ation.html . Unfortunately as any kind of data alignment cannot be guaranteed on 6502, the idea of using low-order bits of a word as type tags cannot be used, but it is an interesting read anyway.

Because 6510 (on a C64) has so few registers, I think I will compile stack (byte)code quite directly to machine code, using some of ZP as a temporary parameter stack, A/X for temporaries and ZP+Y for indexing. I think this approach has been used before in other compilers. The language itself will be pretty much like Scheme, without explicit continuations or hygienic macros. Some kind of macros must be supported for implementing the language itself though.

Offtopic: I haven't been coding for a C64 for ages, it seems I have forgot nearly everything except the opcodes and writing to display memory Also I'll probably have to make a cable between my two C64's to be able to cross-assemble. I really want to use C64 as a development system, not just for running programs assembled on my PC, but not having to keep assembler in memory at the same time or constantly reloading it from disk. And I could use the cable later for this program as well. I suppose in this forum you people really understand what's the difference, instead of thinking I'm insane.

I can't claim to know anything about Lisp; but think of ZP as being 256 processor registers, usable as pointers, indirects, variables, etc.. Each can be accessed in 3 clocks. A lot of processors can't do anything at all in 3 clocks. Forth uses part of ZP for the normal data stack, with X serving as the pointer, and can fairly easily do non-preëmptive multitasking on a 6502 with minimal task-switching overhead.

The original McCarthy Lisps also lacked space for tag bits. To achieve a comparable effect, McCarthy used designated regions of memory instead. E.g., memory from X0 to X1 contained only cons-cells, Y0 to Y1 contained only symbols, Z0 to Z1 only activation frames, and so on.

That way, a function like (cons? x) would return T if X0 <= x < X1, and nil otherwise. (sym? x) would return T if Y0 <= x < Y1. I think you get the idea. The advantage is obvious: no need for tagging; the disadvantage is equally obvious -- performance hit in trying to determine the kind of pointer.



I encourage you to study Forth. Forth, as you perhaps already know, exposes a dual-stack architecture directly to the coder. No garbage collection, no variadic functions, no data types of any kind, etc. It's just you, the machine, and your imagination.

Despite these seeming limitations, Forth code is known to run astonishingly fast -- often far faster than, say, C, which takes a severe performance hit on the 6502 because its concrete architecture is so radically different from C's virtual machine architecture. Indeed, if you squint hard enough, you can get the 6502 to behave as a respectable (though certainly not the fastest possible) stack architecture.

The reason you should study Forth is not for the language; you're already intent on using Lisp, and that's fine (I like Lisp too! In fact, I would like to hear updates on your progress, especially w.r.t. the 65816 implementation). Instead, you should study how Forth compiles. I particularly encourage the use of subroutine-threading, which is a technique as old as Fortran (and thus, predates even Forth and Lisp!), which makes a lot of sense on 8-bit CPUs. If memory is at a real premium for your application, direct- or indirect-threading (first used with Forth, IIRC) may make more sense.

As it is much faster to make a 8-bit tag compare than two 16-bit pointer compares, I think I'll go with 24-bit general datatype at this point, although it will waste some memory I think there will be plenty of it left for data. I have studied Forth a bit, and have more extensively studied some other stack machines. It is probably easiest to compile Lisp to some kind of Forth-like representation and then execute the resulting code or compile it to ML with some kind of peephole optimizations. A reader and an interpreter is higher priority at the moment though. The compiler should probably be written in Lisp, then I could use it to compile itself.

I will use Commodore KERNAL for I/O and stuff (uses up $d000-$ffff), so that would leave 52kB for my own use, I think that is enough when used properly. My assembler is located at $8000 but I will be able to cross-compile from one C64 to another using a custom cable if that becomes a problem at some point. I've been doing a multimedia presentation (usually called a demo or an intro) for C64 with some friends lately, simply because it's 15 years since I programmed 6502 and I found it easier to start with something I was more familiar with back in the days. Currently it is a scrolltext and a music player, and as a whole it should fit in 4k decrunched so it shouldn't take too much time to make unless I'm very lazy for some reason I have done some math routines (again, to refresh my memory) like 16-bit mul/div not used in the intro though. I suppose I will code this Lisp system when I get bored with the intro and vice versa. I would need to find suitable hardware and a different assembler to support 65c816, but doing that would be a very neat hack IMO. And I'd like to have a homebuilt 65c816 computer with a Lisp system anyway..

While I agree tag comparison is easier (equality and/or bit-masks), you can get by with only comparing the high bytes of a pointer. You still have to do range checking though.



A bit of a shameless plug, but, I maintain the 65816 emulator called "lib65816". Although I haven't worked on it in a while, I'm also writing an emulator for a computer I hope to build myself one day (the Kestrel-2). Documentation could be a whole lot better (as in, documentation could actually exist at all), but, at least I'm here to answer any questions if this interests you any.

As far as concrete hardware, there's not much of a choice available: Apple IIgs, SuperNES, or SuperCPU for Commodore 64 or 128. I cannot think of any computer available today that uses the 65816, so you're pretty limited to either home-built or used equipment.

There are simple circuits to place a 65816 into a 6502 system, if all you want is the opcodes, not the speed or the memory. The next step is to add the memory, which isn't too difficult. Increasing the speed beyond the host speed is where it gets interesting - that's what I'm doing at present, with a friend. We found we need a fair number of 74 series to do the job, so the next step is to put all the glue into a CPLD.

The nice thing about tackling the problem as an upgrade to existing hardware is that you have a working platform to start from. We're using the Beeb. It means we had a wider choice than the machines you listed. The SuperCPU is the same idea, but they had a more aggressive spec than we did (and they wanted to sell in volume, so they had to impress)

Another subproject we might yet tackle is to use the Beeb's TUBE interface, and hang the 65816 onto that, as a second processor. But the TUBE is not a trivial interface.

The nice thing about a fresh start is that you don't have a host clock to worry about.

I've still not found any good documentation on what the TUBE interface actually was. Can you provide an executive summary?

One idea I've had for retrofitting a 65816 CPU into a Commodore computer was to adapt the Kestrel-1 computer I'd built to serve as an 8MHz 65816-based single-board computer that couples with the C64 via the cartridge port as a slave peripheral. I'd use $DE00-$DEFF (I think that was one of the open memory holes) as a 256-byte window into the 65816's memory space. A VIA (located elsewhere in I/O space) would then be used by the C64 to drive the 65816's DMA interface.

Inter-processor communication would occur by writing messages in previously agreed upon memory locations and triggering interrupts.

The TUBE is a 40-way connector, every alternate wire is ground (or power), then you have the data bus, the 7 bottom address bits, four control signals and a clock. On the parasite side, there was a ULA (you can buy them from sprow) which contains a set of FIFOs. The parasite performs OS calls by posting into the appropriate FIFO, so can do asynchronous calls - for example, to output a sound.

There's some hardware detail in the TUBE service manual

One can take the idea and map it down to a much simpler 8-bit port, or a pair of them - here's a 6809 example

OK, so the TUBE is more or less what I was thinking of for the Commodore 64 interface then -- essentially a message passing, high-speed, point-to-point network link (kind of like an ATM PHY interface).