Wolin - a minimal Kotlin-like language compiler for 65xx

[qus]

Since I got my WIFI modem for C64 I wanted to write a program, or as would my son say an "app" that would synchronize my C64 uIEC clock (and maybe even CIA clock or TI variable) with modem's internal clock (it gets it from NTP). I'm not really into assembler coding, you know - it's like drilling a tunnel with a spoon when we have these huge monster drills, but I digress... I don't like C either, it doesn't have objects, not to mention functional programming or any other feature that makes coding FUN. And it's not suited for C64 programming anyway... So... what's there for me? There's SLANG and Atalan. SLANG seems to be just some kind of super-macro-assembler on top of macro-assembler, it's nice, but quirky. I do love how Atalan works, but unfortunately it was abandoned by its author. I tried to fix it, but it's written in some messy C, damn it!

So, no more options... unless... I write my own compiler! I never wrote any and had no idea how hard it could be. And guess what? It's not so hard! All you need is ANTLR4, a grammar of some nice existing modern language (like Kotlin) and the knowledge that 65xx has not three, but 250-something usable registers (thanks 6502.org!)

So it's been a lazy week, and I was able to compile this piece of code into 6510 (see attached assembler.s):

Code: Select all

package pl.qus.wolin

fun sillySum(arg1: Word, arg2: Word): Word {
    throw 12345
    return arg1+arg2
}

fun main() {
    var b: Word = 0
    var sumError: Word = 0xcafd

    try {
        b=sillySum(4,2)
    } catch (ex: Word) {
        b=sumError
    }

    b++
}

.... that would leave $cafe in b variable (spoiler: if initializing variables was working - it isn't yet).

So how does it work? First it translates Wolin code to intermediate virtual machine assembler that has the following syntax:

Code: Select all

mnemonic destination[type] = arg1[type], arg2[type]

So for example "b++" becomes:

Code: Select all

add pl.qus.wolin.test.main..b[word] = pl.qus.wolin.test.main..b[word], #1[byte]

And then there's "template" file that describes how each "mnemonic type = type,type" combination gets translated into 6510 asm, by matching some patterns:

Code: Select all

add ?dest[word] = ?src[word], #?val[byte] -> """
    clc
    lda {src}
    adc #{val}
    sta {dest}
    lda {src}+1
    adc #0
    sta {dest}+1
"""

which in this case becomes:

Code: Select all

    clc
    lda pl.qus.wolin.test.main..b
    adc #1
    sta pl.qus.wolin.test.main..b
    lda pl.qus.wolin.test.main..b+1
    adc #0
    sta pl.qus.wolin.test.main..b+1

It does this line by line and lo and behold! - Kotlin code translated to 65xx assembler!

Of course it's only very beginning and a tiny fraction of what real Kotlin can do. I'm learnig a lot while coding it. Next thing will probably be a look into OO and functional... just because nobody tried it yet and because "65xx is not designed for OO".

Some technical info:

- CPU stack is used only for jsring and temporary register storage

- There's ZP-based "program stack" used for evaluating exproessions (and gee - it really makes everything so simple!)

- There are two non ZP stacks: one for function calls and function local variables (so recurrence is possible) and second for exception handling

- Variables can be fixed to a location like "var background: Ubyte^53281" and even to single bit at some location (for boolean variables)

I'll try to share some more experience if I continue coding this assembler. Feel free to share your ideas/knowledge!

[BigEd]

Welcome and thanks for sharing - hope to see further developments!

[whartung]

Nice! Clever, qus.

[qus]

Of course there's still need for an optimizer as you can see i.e. in pieces like:

Code: Select all

inx
inx
dex
dex

But I wanted to show you some more cool things that I can easily get with pattern matching.

1. some trivial optimizations:

Code: Select all

div SP(?d)[byte] = SP(?dzielna)[byte], #2 -> """   ror {d},x"""
div SP(?d)[byte] = SP(?dzielna)[byte], #4 -> """
    ror {d},x
    ror {d},x"""
div SP(?d)[byte] = SP(?dzielna)[byte], #8 -> """
    ror {d},x
    ror {d},x
    ror {d},x"""

2. supporting a new primitive type doesn't require any change to compiler code! (ok, besides telling the compiler that "float" takes 4 bytes - but that's really all it needs to know)

Code: Select all

add SP(?dest)[float] = SP(?first)[float], SP(?second)[float] -> """   jsr fadd_with_stack"""

[qus]

As for progress I am now able to compile this:

Code: Select all

package pl.qus.wolin
/*
import c64.kernal

const val urzadzenie: ubyte = 8

fun setLfs^0xffba(lfn: ubyte^r.a, dev: ubyte^r.x, channel: ubyte^r.y)
fun setNam^0xffbd(len: ubyte^r.a, name: word^r.xy)
*/

var tlo: ubyte^53281
var b: uword = 0

fun testFunction(arg1: uword, arg2: uword): uword {
    return arg1+arg2
}


fun testThrow(arg1: uword, arg2: uword) {
    throw 12345
}

fun testCatch() {
    try {
        testThrow(4,2)
    } catch (ex: word) {
        b=0xcafd
    }
}

fun testIf() {
    if(tlo == 2)
        b = 50000
    else if(tlo == 3)
        b = 50001
    else
        tlo++
}

fun testIncrement() {
    tlo++	
}

fun main() {
    var pi: float

    //pi = 3.14


    //setLfs(1, urzadzenie, 1)
    //setNam(razyDwa(2),"dupa")
}

[qus]

Update: added loops:

Code: Select all

fun testWhile1() {
        do {
            tlo++
        } while (tlo==10)
}

fun testWhile2() {
        while(tlo==10) {
            tlo++
        }
}

Compiles to:

Code: Select all

pl.qus.wolin.test.testWhile1:
  dex
__wolin_lab_doWhileBody_4:
  dex
  inc 53281
  inx
  dex
    lda 53281
    sta 0,x
  dex
  lda #10
  sta 0,x
    lda #1// rowne
    sta 2,x
    lda 1,x
    cmp 0,x
    beq __wolin_eq_label_2
    lda #0 // jednak rozne
    sta 2,x
__wolin_eq_label_2:
  inx
  inx
    lda 0,x
    cmp #1
    beq __wolin_lab_doWhileBody_4
  inx
  rts

pl.qus.wolin.test.testWhile2:
  dex
__wolin_lab_whileCondition_5:
  dex
    lda 53281
    sta 0,x
  dex
  lda #10
  sta 0,x
    lda #1// rowne
    sta 2,x
    lda 1,x
    cmp 0,x
    beq __wolin_eq_label_3
    lda #0 // jednak rozne
    sta 2,x
__wolin_eq_label_3:
  inx
  inx
    lda 0,x
    cmp #1
    bne __wolin_lab_afterWhileBody_5
  dex
  inc 53281
  inx
  jmp __wolin_lab_whileCondition_5
__wolin_lab_afterWhileBody_5:
  inx
  rts

[qus]

So it appears implementing lambdas is also pretty straightforward. After all they're just functions...

Now I can compile this:

Code: Select all

var suma: (ubyte, ubyte)->ubyte

...

fun testFunctionVar() {
    suma = { a, b -> a+b }
    tlo = suma(5,6)
}

[qus]

This is a simple lambda test in Wolin

Code: Select all

package pl.qus.wolin

var tlo: ubyte^53281

var b: uword //= 0 - inicjalizacja w obrębie pliku powoduje empty stack exception!

var suma: (ubyte, ubyte)->ubyte

fun testFunctionVar(x: ubyte, y: ubyte) {

    suma = {
        a: ubyte, b: ubyte ->
        a+b
    }
    tlo = suma(x,y)

}


fun main() {
    testFunctionVar(2,3)
}

and this is resulting code (of course - unoptimized!):

Code: Select all

; setupSPE=155[ubyte],53247[uword]


; prepare exception stack
__wolin_spe = 155 ; exception stack ptr
__wolin_spe_top = 53247 ; exception stack top
    lda #<__wolin_spe_top ; set exception stack top
    sta __wolin_spe
    lda #>__wolin_spe_top
    sta __wolin_spe+1

; setupEXPTR=178[ubyte]


__wolin_exception_ptr = 178 ; pointer to exception object on throw


; setupCATCH=253[ubyte]


__wolin_spe_zp_vector = 253


; setupSPF=251[ubyte],40959[uword]


; prepare function stack
__wolin_spf = 251 ; function stack ptr
__wolin_spf_top = 40959 ; function stack top
    lda #<__wolin_spf_top ; set function stack top
    sta __wolin_spf
    lda #>__wolin_spf_top
    sta __wolin_spf+1

; setupSP=142[ubyte]


; prepare program stack
__wolin_sp_top = 142 ; program stack top
    ldx #__wolin_sp_top ; set program stack top

; goto__wolin_pl_qus_wolin_test_main[adr]

  jmp __wolin_pl_qus_wolin_test_main

; label__wolin_pl_qus_wolin_test_testFunctionVar

__wolin_pl_qus_wolin_test_testFunctionVar:

; allocSP<r.temp1>,#2


    dex
    dex

; letSP(0)<r.temp1>[ptr]=__wolin_lambda_function_0[adr]


    lda #<__wolin_lambda_function_0
    sta 0,x
    lda #>__wolin_lambda_function_0
    sta 0+1,x

; let__wolin_pl_qus_wolin_test_suma<pl.qus.wolin.test.suma>[ptr]=SP(0)<r.temp1>[ptr]


    lda 0,x
    sta __wolin_pl_qus_wolin_test_suma
    lda 0+1,x
    sta __wolin_pl_qus_wolin_test_suma,x

; freeSP<r.temp1>,#2


    inx
    inx

; allocSP<r.temp4>,#1

  dex

; allocSPF,#3


  clc
  lda __wolin_spf
  sbc #3
  sta __wolin_spf
  lda __wolin_spf+1
  sbc #0
  sta __wolin_spf+1

; allocSP<r.temp5>,#1

  dex

; letSP(0)<r.temp5>[ubyte]=SPF(4)<pl.qus.wolin.test.testFunctionVar.x>[ubyte]


    ldy #4
    lda (__wolin_spf),y
    sta 0,x


; letSPF(1)[ubyte]=SP(0)<r.temp5>[ubyte]


  lda 0,x
  ldy #1
  sta (__wolin_spf),y

; freeSP<r.temp5>,#1

  inx

; allocSP<r.temp6>,#1

  dex

; letSP(0)<r.temp6>[ubyte]=SPF(3)<pl.qus.wolin.test.testFunctionVar.y>[ubyte]


    ldy #3
    lda (__wolin_spf),y
    sta 0,x


; letSPF(0)[ubyte]=SP(0)<r.temp6>[ubyte]


  lda 0,x
  ldy #0
  sta (__wolin_spf),y

; freeSP<r.temp6>,#1

  inx

; call__wolin_pl_qus_wolin_test_suma[ptr]


    lda #<__wolin_pl_qus_wolin_test_suma
    sta __wolin_indirect_jsr+1
    lda #>__wolin_pl_qus_wolin_test_suma
    sta __wolin_indirect_jsr+2
    jsr __wolin_indirect_jsr

; letSP(0)<r.temp4>[ubyte]=SPF(0)<lambdaReturn>[ubyte]


    ldy #0
    lda (__wolin_spf),y
    sta 0,x


; freeSPF<lambdaReturn>,#1

  clc
  lda __wolin_spf
  adc #1
  sta __wolin_spf
  lda __wolin_spf+1
  adc #0
  sta __wolin_spf+1

; let53281[ubyte]=SP(0)<r.temp4>[ubyte]


    lda 0,x
    sta 53281


; freeSP<r.temp4>,#1

  inx

; freeSPF,#2

  clc
  lda __wolin_spf
  adc #2
  sta __wolin_spf
  lda __wolin_spf+1
  adc #0
  sta __wolin_spf+1

; ret

  rts

; label__wolin_pl_qus_wolin_test_main

__wolin_pl_qus_wolin_test_main:

; allocSPF,#2


  clc
  lda __wolin_spf
  sbc #2
  sta __wolin_spf
  lda __wolin_spf+1
  sbc #0
  sta __wolin_spf+1

; allocSP<r.temp8>,#1

  dex

; letSP(0)<r.temp8>[ubyte]=#2[ubyte]


  lda #2
  sta 0,x

; letSPF(1)[ubyte]=SP(0)<r.temp8>[ubyte]


  lda 0,x
  ldy #1
  sta (__wolin_spf),y

; freeSP<r.temp8>,#1

  inx

; allocSP<r.temp9>,#1

  dex

; letSP(0)<r.temp9>[ubyte]=#3[ubyte]


  lda #3
  sta 0,x

; letSPF(0)[ubyte]=SP(0)<r.temp9>[ubyte]


  lda 0,x
  ldy #0
  sta (__wolin_spf),y

; freeSP<r.temp9>,#1

  inx

; call__wolin_pl_qus_wolin_test_testFunctionVar[adr]

  jsr __wolin_pl_qus_wolin_test_testFunctionVar

; letSP(0)<r.temp7>[unit]=SPF(0)<pl.qus.wolin.test.testFunctionVar.returnValue>[unit]

 

; freeSPF<pl.qus.wolin.test.testFunctionVar.returnValue>,#0

 

; ret

  rts

; label__wolin_lambda_function_0

__wolin_lambda_function_0:

; allocSP<r.temp10>,#1

  dex

; letSP(0)<r.temp10>[ubyte]=SPF(1)<pl.qus.wolin.test.lambda_function_0.a>[ubyte]


    ldy #1
    lda (__wolin_spf),y
    sta 0,x


; allocSP<r.temp11>,#1

  dex

; letSP(0)<r.temp11>[ubyte]=SPF(0)<pl.qus.wolin.test.lambda_function_0.b>[ubyte]


    ldy #0
    lda (__wolin_spf),y
    sta 0,x


; addSP(1)<r.temp10>[ubyte]=SP(1)<r.temp10>[ubyte],SP(0)<r.temp11>[ubyte]


    clc
    lda 1,x
    adc 0,x
    sta 1,x

; freeSP<r.temp11>,#1

  inx

; letSPF(2)<lambdaReturn>[ubyte]=SP(0)<r.temp10>[ubyte]


  lda 0,x
  ldy #2
  sta (__wolin_spf),y

; freeSP<r.temp10>,#1

  inx

; freeSPF,#2

  clc
  lda __wolin_spf
  adc #2
  sta __wolin_spf
  lda __wolin_spf+1
  adc #0
  sta __wolin_spf+1

; ret

  rts

; label__wolin_indirect_jsr

__wolin_indirect_jsr:

; goto65535[adr]

  jmp 65535

; label__wolin_pl_qus_wolin_test_suma

__wolin_pl_qus_wolin_test_suma:

; alloc#2,0

  .word 0

; label__wolin_pl_qus_wolin_test_b

__wolin_pl_qus_wolin_test_b:

; alloc#2,0

  .word 0

[qus]

Finally a test on an emulator. I've found some bugs in template code, fixed them and now I have this, which changes background color to reddish via lambda call (using the same Wolin source, as post above)

Code: Select all

__wolin_spf = 251 ; function stack ptr
__wolin_spf_top = 40959 ; function stack top
    lda #<__wolin_spf_top ; set function stack top
    sta __wolin_spf
    lda #>__wolin_spf_top
    sta __wolin_spf+1
__wolin_sp_top = 142 ; program stack top
    ldx #__wolin_sp_top ; set program stack top
  jmp __wolin_pl_qus_wolin_test_main
__wolin_pl_qus_wolin_test_testFunctionVar:

    dex
    dex

    lda #<__wolin_lambda_function_0
    sta 0,x
    lda #>__wolin_lambda_function_0
    sta 0+1,x

    lda 0,x
    sta __wolin_pl_qus_wolin_test_suma
    lda 0+1,x
    sta __wolin_pl_qus_wolin_test_suma+1

    inx
    inx
  dex

  clc
  lda __wolin_spf
  sbc #3
  sta __wolin_spf
  lda __wolin_spf+1
  sbc #0
  sta __wolin_spf+1
  dex

    ldy #4
    lda (__wolin_spf),y
    sta 0,x

  lda 0,x
  ldy #1
  sta (__wolin_spf),y

    ldy #3
    lda (__wolin_spf),y
    sta 0,x

  lda 0,x
  ldy #0
  sta (__wolin_spf),y
  inx

    lda __wolin_pl_qus_wolin_test_suma
    sta __wolin_indirect_jsr+1
    lda __wolin_pl_qus_wolin_test_suma+1
    sta __wolin_indirect_jsr+2
    jsr __wolin_indirect_jsr

    ldy #0
    lda (__wolin_spf),y
    sta 0,x

  clc
  lda __wolin_spf
  adc #1
  sta __wolin_spf
  lda __wolin_spf+1
  adc #0
  sta __wolin_spf+1

    lda 0,x
    sta 53281

  inx
  clc
  lda __wolin_spf
  adc #2
  sta __wolin_spf
  lda __wolin_spf+1
  adc #0
  sta __wolin_spf+1
  rts

__wolin_pl_qus_wolin_test_main:
  clc
  lda __wolin_spf
  sbc #2
  sta __wolin_spf
  lda __wolin_spf+1
  sbc #0
  sta __wolin_spf+1
  dex

  lda #2
  sta 0,x
  lda 0,x
  ldy #1
  sta (__wolin_spf),y
  lda #3
  sta 0,x

  lda 0,x
  ldy #0
  sta (__wolin_spf),y
  inx
  jsr __wolin_pl_qus_wolin_test_testFunctionVar
  rts

__wolin_lambda_function_0:
  dex

    ldy #1
    lda (__wolin_spf),y
    sta 0,x

  dex

    ldy #0
    lda (__wolin_spf),y
    sta 0,x

    clc
    lda 1,x
    adc 0,x
    sta 1,x
  inx

  lda 0,x
  ldy #2
  sta (__wolin_spf),y
  inx
  clc
  lda __wolin_spf
  adc #2
  sta __wolin_spf
  lda __wolin_spf+1
  adc #0
  sta __wolin_spf+1
  rts

__wolin_indirect_jsr:
  jmp 65535
__wolin_pl_qus_wolin_test_suma:
  .word 0
__wolin_pl_qus_wolin_test_b:
  .word 0

[qus]

Now for some optimizations. This is not coded yet, but going from this code:

Code: Select all

label lambda_function_0

alloc SP<r.temp12>, #1 // for statement a+b
let SP(0)<r.temp12>[ubyte] = SPF(1)<pl.qus.wolin.test.lambda_function_0.a>[ubyte] // simple id from var
alloc SP<r.temp13>, #1 // for right side
let SP(0)<r.temp13>[ubyte] = SPF(0)<pl.qus.wolin.test.lambda_function_0.b>[ubyte] // simple id from var
add SP(1)<r.temp12>[ubyte] = SP(1)<r.temp12>[ubyte], SP(0)<r.temp13>[ubyte] // two sides
free SP<r.temp13>, #1 // for right side, type =ubyte
let SPF(2)<lambdaReturn>[ubyte] = SP(0)<r.temp12>[ubyte] // LAMBDA return assignment
free SP<r.temp12>, #1 // for statement a+b, type = ubyte
free SPF, #2 // free fn arguments and locals for lambda_function_0

ret

to this (equivalent) code of the lambda function used above:

Code: Select all

label lambda_function_0

add SPF(2)<lambdaReturn>[ubyte] = SPF(1)<pl.qus.wolin.test.lambda_function_0.a>[ubyte], **SPF(0)<pl.qus.wolin.test.lambda_function_0.b>[ubyte]** // two sides
free SPF, #2 // free fn arguments and locals for lambda_function_0

ret

would require 4 atomic steps.

[qus]

Small update: implemented minimal type inference, so the lambda function can now be expressed just as:

Code: Select all

    suma = { a, b -> a+b }

(as we know the type of variable suma from its declaration)

Bigger update - I'm not really sure why someone claimed "6502 wasn't designed for OO" So far implementing object oriented seems pretty straightforward too... Unless I encounter some pitfall later...

[GARTHWILSON]

qus wrote:

Bigger update - I'm not really sure why someone claimed "6502 wasn't designed for OO" So far implementing object oriented seems pretty straightforward too... Unless I encounter some pitfall later...

You might be interested in this topic, which does, despite the name, have some '02 content:
Object Oriented Dispatch on 65816

[qus]

Thanks!

EDIT: This was some fun read. But first time I've stumbled across someone questioning utility of OO, I got back to OP, expecting it being posted in late 80s-early 90s, yet I was shocked that somone really wrote it in... erm... 2005?!

[qus]

So, some of my insights into objects. Obvoiusly object field operations will be the slowest.

Let's for example take this simple class:

Code: Select all

class Dupa {
	val a: ubyte
	val b: ubyte

    fun jakasFunkcja(): Dupa {
        tlo = a+b
        return this
    }
}

as a and b in jakasFunkcja are variables in some instance of this object, they need to be dereferenced at their current memory address unknown at compilation time

Fortunately class functions get one intinsic parameter "this" as argument 0. So if I need to fetch class field for current operation like here:

Code: Select all

letSP(0)<__wolin_reg1>[ubyte]=HEAP(1)<pl.qus.wolin.pl.qus.wolin.test.Dupa.a>[ubyte]

I do it like this:

Code: Select all

    ldy #0 ; as first argument to this function is "this" (the object)...
    lda (__wolin_spf),y
    sta __wolin_this_ptr
    iny
    lda (__wolin_spf),y
    sta __wolin_this_ptr+1; i'll store it on ZP to dereference class variables from there

    ldy #1 ; a is #1 on HEAP, fetch it
    lda (__wolin_this_ptr),y
    sta 0,x ; store it on operations stack

That is of course a long operation, but I have no other ideas on implementation. Also - this limits data space of each object instance to 255, obviously. It should be enough for everyone, though

[qus]

Update: implemented object constructors. All I'm missing now is memory manager for allocating class instance space (and I really hope I can write it in Wolin, not in assembler!)

So with following code:

Code: Select all

class Dupa {
	val a: ubyte
	val b: ubyte

    fun jakasFunkcja(): Dupa {
        tlo = a+b
        return this
    }
}

var dupa: Dupa

fun main() {
    dupa = Dupa()
}

function main just allocates ("new" in C++) instance of the class and constructs it. So each class gets a constructor, in this case it looks like this:

Code: Select all

// ****************************************
// konstruktor: fun pl.qus.wolin.test.Dupa():pl.qus.wolin.test.Dupa
// ****************************************
label __wolin_pl_qus_wolin_test_Dupa

alloc SP<__wolin_reg0>, #2 // for returning this
alloc SPF, #2 // prepare stack for calling AllocMem function (right now just return value, but later on I need to add memory size augument, obviously!)
call __wolin_alloc_mem[adr] // calls alloc mem function that returns pointer to newly allocated data
let SP(0)<__wolin_reg0>[ptr] = SPF(0)<returnValue>[ptr] // get returned pointer to temp reg
let SPF(0)<pl.qus.wolin.pl.qus.wolin.test.Dupa.returnValue>[ptr] = SP(0)<__wolin_reg0>[ptr] // put this pointer in consturctor's return value
free SPF <ptr>, #2 // free stack used to call allocMem
free SP<__wolin_reg0>, #2 // free temp reg
ret

which translates to this:

Code: Select all

__wolin_pl_qus_wolin_test_Dupa:

; allocSP<__wolin_reg0>,#2


    dex
    dex

; allocSPF,#2


  clc
  lda __wolin_spf
  sbc #2
  sta __wolin_spf
  lda __wolin_spf+1
  sbc #0
  sta __wolin_spf+1

; call__wolin_alloc_mem[adr]

  jsr __wolin_alloc_mem

; letSP(0)<__wolin_reg0>[ptr]=SPF(0)<returnValue>[ptr]


     ldy #0
     lda (__wolin_spf),y
     sta 0,x
     iny
     lda (__wolin_spf),y
     sta 0+1,x

; letSPF(0)<pl.qus.wolin.pl.qus.wolin.test.Dupa.returnValue>[ptr]=SP(0)<__wolin_reg0>[ptr]


    ldy #0
    lda 0,x
    sta (__wolin_spf),y
    iny
    lda 0+1,x
    sta (__wolin_spf),y

; freeSPF<ptr>,#2

  clc
  lda __wolin_spf
  adc #2
  sta __wolin_spf
  lda __wolin_spf+1
  adc #0
  sta __wolin_spf+1

; freeSP<__wolin_reg0>,#2


    inx
    inx

    rts