Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
Current time: March 28, 2024, 7:43 am

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Arithmetic Expression Compiler
#1
Arithmetic Expression Compiler
So, I'd like to share my first steps in designing programming languages. As some of you know, for the last 11 months or so, I've been developing a program called Arithmetic Expression Compiler. It's written mostly in JavaScript and it converts directives from my own programming language (at first just arithmetic expressions) to FlatAssembler-compatible and i486-compatible (let's pretend it's i486-compatible, I haven't bothered to actually test it on anything else than my 12-year-old PC with 1Ghz Celeron processor) assembly. Recently, using the Duktape framework, I extended it to be able to not just compile single directives, but entire simple programs written in files.
So, here is one of the first programs I've written in the first programming language I've made myself:
Code:
;Advanced example: implementing the permutation algorithm.
AsmStart
    debug=0
    macro pushIntToStack x
    {
        sub esp,4
        fld dword [x]
        fistp dword [esp]
    }
    macro pushPointerToStack x
    {
        sub esp,4
        lea ebx,[x]
        mov [esp],ebx
    }
    macro pushStringToStack x
    {
        sub esp,4
        mov dword [esp],x
    }
    format PE console
    entry start

    include 'win32a.inc'

    section '.text' code executable
    start:
    jmp enterNumber$
        enterNumber db "Enter a whole number (1 - 1'000'000).",10,0
    enterNumber$:
    pushStringToStack enterNumber
    call [printf]
    pushPointerToStack original
    jmp floatSign$
        floatSign db "%f",0
    floatSign$:
    pushStringToStack floatSign
    call [scanf]
    jmp permutationString$
        permutationString db "The permutations of its digits are:",10,0
    permutationString$:
    pushStringToStack permutationString
    call [printf]
AsmEnd
numberOfDigits:=0
i:=0
While i<10
    countDigits[i]:=0
    i:=i+1
EndWhile
While original>0
    numberOfDigits:= numberOfDigits + 1
    lastDigit:= mod( original , 10 )
    countDigits[ lastDigit ]:=countDigits( lastDigit ) + 1
    original:= (original - lastDigit) / 10
EndWhile
AsmStart
    if debug=1
AsmEnd
        i:=0
        While i<10
            subscript:=4*i
            AsmStart
                fld dword [subscript]
                fistp dword [subscript]
                mov ebx,[subscript]
                pushIntToStack (countDigits+ebx)
                pushStringToStack integerSign
                call [printf]
            AsmEnd
            i:=i+1
        EndWhile
        AsmStart
            pushStringToStack newLineString
            call [printf]
        AsmEnd
AsmStart
end if
AsmEnd
topOfMyStack:=1
myStack[(numberOfDigits+1)]:=0
While topOfMyStack>0
    currentNumberOfDigits:=myStack ( topOfMyStack * ( numberOfDigits + 1 ) )
    i:=0
    While i<currentNumberOfDigits
        currentNumber(i):=myStack ( topOfMyStack * ( numberOfDigits + 1 ) + ( i + 1 ) )
        i:=i+1
    EndWhile
    AsmStart
        if debug=1
    AsmEnd
            i:=0
            While i<currentNumberOfDigits
                subscript:=i*4
                AsmStart
                    fld dword [subscript]
                    fistp dword [subscript]
                    mov ebx,[subscript]
                    pushIntToStack (currentNumber+ebx)
                    pushStringToStack integerSign
                    call [printf]
                AsmEnd
                i:=i+1
            EndWhile
            AsmStart
                pushStringToStack newLineString
                call [printf]
            AsmEnd
    AsmStart
        end if
    AsmEnd
    topOfMyStack:=topOfMyStack-1
    If currentNumberOfDigits=numberOfDigits
        i:=0
        While i<numberOfDigits
            subscript:=i*4
            AsmStart
                fld dword [subscript]
                fistp dword [subscript]
                mov ebx,[subscript]
                pushIntToStack (currentNumber+ebx)
                pushStringToStack integerSign
                call [printf]
            AsmEnd
            i:=i+1
        EndWhile
        AsmStart
            pushStringToStack newLineString
            call [printf]
        AsmEnd
    Else
        i:=0
        While i<10
            counter:=0
            j:=0
            While j<currentNumberOfDigits
                If currentNumber(j)=i
                    counter:=counter+1
                EndIf
                j:=j+1
            EndWhile
            If counter<countDigits(i)
                topOfMyStack:=topOfMyStack+1
                myStack(topOfMyStack*(numberOfDigits+1)):=currentNumberOfDigits+1
                j:=0
                While j<currentNumberOfDigits
                    myStack(topOfMyStack*(numberOfDigits+1)+(j+1)):=currentNumber(j)
                    j:=j+1
                EndWhile
                myStack (topOfMyStack * (numberOfDigits + 1) + (j + 1) ) := i
            EndIf
            i:=i+1
        EndWhile
    EndIf
EndWhile
AsmStart
invoke system,_pause
invoke exit,0

_pause db "PAUSE",0
integerSign db "%d",0
newLineString db 10,0

section '.rdata' readable writable
original dd ?
result dd ?
lastDigit dd ?
numberOfDigits dd ?
countDigits dd 11 dup(?)
subscript dd ?
myStack dd 1000 dup(?)
topOfMyStack dd ?
counter dd ?
i dd ?
currentNumber dd 11 dup(?)
currentNumberOfDigits dd ?
j dd ?


section '.idata' data readable import
library msvcrt,'msvcrt.dll'
import msvcrt,printf,'printf',system,'system',exit,'exit',scanf,'scanf'
AsmEnd
You can download the source code of my compiler there, there is a link there to a ZIP-archive containing the source code and instructions on how to compile it using CLANG or GCC (000webhost doesn't allow me to host executable files):
http://flatassembler.000webhostapp.com/compiler.html
I've designed this programming language to be as easy to integrate with Assembly as possible. The Assembly code C compilers have to produce (trying to declare variables themselves, trying to declare functions themselves...) has to be almost completely rewritten if you are targeting a different assembly language compiler or a different operating system.
However, the solution I've made may be even worse than the problem. The programs written in that programming language are completely non-portable. Also, since my compiler tries to make as few assumptions as possible, it produces way inferior Assembly code than any decent C-compiler would. However, it seems to make no perceptible difference on a what's now a 12-year-old computer (the Assembly code a JavaScript JIT-compiler produces is probably even less optimal). Also, because of the design of my programming language, it often happens that a compiler doesn't catch an error such as using an undeclared variable and outputs syntactically invalid Assembly.
I am also dreaming about making a compiled LISP-like language in which you could write arithmetic expressions in both S-expressions and infix-expressions, but be able to use only S-expressions elsewhere (since they come very handy in string and array-manipulation). However, I probably won't have time for that in foreseeable future.
#2
RE: Arithmetic Expression Compiler
This is so far out of my wheelhouse that I couldn't comment intelligently on it.

I could recommend an area that is pretty open for development, and where assembly compilation still matters-- scripting old / small processors for use in robotics. I was surprised to find a 68B09E chip in an Arduino-based electronics shop. Well, that used to be a high-power CPU that was used in the Radio Shack Color Computer II.

The programming is mostly done in C or C++, but it seems to me you could make custom libraries. Also, the hardware costs for Arduino projects are often just $10-$20 USD.
#3
RE: Arithmetic Expression Compiler
(January 2, 2019 at 3:01 am)FlatAssembler Wrote: So, I'd like to share my first steps in designing programming languages. As some of you know, for the last 11 months or so, I've been developing a program called Arithmetic Expression Compiler. It's written mostly in JavaScript and it converts directives from my own programming language (at first just arithmetic expressions) to FlatAssembler-compatible and i486-compatible (let's pretend it's i486-compatible, I haven't bothered to actually test it on anything else than my 12-year-old PC with 1Ghz Celeron processor) assembly. Recently, using the Duktape framework, I extended it to be able to not just compile single directives, but entire simple programs written in files.
So, here is one of the first programs I've written in the first programming language I've made myself:
Code:
;Advanced example: implementing the permutation algorithm.
AsmStart
    debug=0
macro pushIntToStack x
{
sub esp,4
fld dword [x]
fistp dword [esp]
}
macro pushPointerToStack x
{
sub esp,4
lea ebx,[x]
mov [esp],ebx
}
macro pushStringToStack x
{
sub esp,4
mov dword [esp],x
}
format PE console
entry start

include 'win32a.inc'

section '.text' code executable
start:
jmp enterNumber$
enterNumber db "Enter a whole number (1 - 1'000'000).",10,0
enterNumber$:
pushStringToStack enterNumber
call [printf]
pushPointerToStack original
jmp floatSign$
floatSign db "%f",0
floatSign$:
pushStringToStack floatSign
call [scanf]
jmp permutationString$
permutationString db "The permutations of its digits are:",10,0
permutationString$:
pushStringToStack permutationString
call [printf]
AsmEnd
numberOfDigits:=0
i:=0
While i<10
countDigits[i]:=0
i:=i+1
EndWhile
While original>0
numberOfDigits:= numberOfDigits + 1
lastDigit:= mod( original , 10 )
countDigits[ lastDigit ]:=countDigits( lastDigit ) + 1
original:= (original - lastDigit) / 10
EndWhile
AsmStart
if debug=1
AsmEnd
i:=0
While i<10
subscript:=4*i
AsmStart
fld dword [subscript]
fistp dword [subscript]
mov ebx,[subscript]
pushIntToStack (countDigits+ebx)
pushStringToStack integerSign
call [printf]
AsmEnd
i:=i+1
EndWhile
AsmStart
pushStringToStack newLineString
call [printf]
AsmEnd
AsmStart
end if
AsmEnd
topOfMyStack:=1
myStack[(numberOfDigits+1)]:=0
While topOfMyStack>0
currentNumberOfDigits:=myStack ( topOfMyStack * ( numberOfDigits + 1 ) )
i:=0
While i<currentNumberOfDigits
currentNumber(i):=myStack ( topOfMyStack * ( numberOfDigits + 1 ) + ( i + 1 ) )
i:=i+1
EndWhile
AsmStart
if debug=1
AsmEnd
i:=0
While i<currentNumberOfDigits
subscript:=i*4
AsmStart
fld dword [subscript]
fistp dword [subscript]
mov ebx,[subscript]
pushIntToStack (currentNumber+ebx)
pushStringToStack integerSign
call [printf]
AsmEnd
i:=i+1
EndWhile
AsmStart
pushStringToStack newLineString
call [printf]
AsmEnd
AsmStart
end if
AsmEnd
topOfMyStack:=topOfMyStack-1
If currentNumberOfDigits=numberOfDigits
i:=0
While i<numberOfDigits
subscript:=i*4
AsmStart
fld dword [subscript]
fistp dword [subscript]
mov ebx,[subscript]
pushIntToStack (currentNumber+ebx)
pushStringToStack integerSign
call [printf]
AsmEnd
i:=i+1
EndWhile
AsmStart
pushStringToStack newLineString
call [printf]
AsmEnd
Else
i:=0
While i<10
counter:=0
j:=0
While j<currentNumberOfDigits
If currentNumber(j)=i
counter:=counter+1
EndIf
j:=j+1
EndWhile
If counter<countDigits(i)
topOfMyStack:=topOfMyStack+1
myStack(topOfMyStack*(numberOfDigits+1)):=currentNumberOfDigits+1
j:=0
While j<currentNumberOfDigits
myStack(topOfMyStack*(numberOfDigits+1)+(j+1)):=currentNumber(j)
j:=j+1
EndWhile
myStack (topOfMyStack * (numberOfDigits + 1) + (j + 1) ) := i
EndIf
i:=i+1
EndWhile
EndIf
EndWhile
AsmStart
invoke system,_pause
invoke exit,0

_pause db "PAUSE",0
integerSign db "%d",0
newLineString db 10,0

section '.rdata' readable writable
original dd ?
result dd ?
lastDigit dd ?
numberOfDigits dd ?
countDigits dd 11 dup(?)
subscript dd ?
myStack dd 1000 dup(?)
topOfMyStack dd ?
counter dd ?
i dd ?
currentNumber dd 11 dup(?)
currentNumberOfDigits dd ?
j dd ?


section '.idata' data readable import
library msvcrt,'msvcrt.dll'
import msvcrt,printf,'printf',system,'system',exit,'exit',scanf,'scanf'
AsmEnd
You can download the source code of my compiler there, there is a link there to a ZIP-archive containing the source code and instructions on how to compile it using CLANG or GCC (000webhost doesn't allow me to host executable files):
http://flatassembler.000webhostapp.com/compiler.html
I've designed this programming language to be as easy to integrate with Assembly as possible. The Assembly code C compilers have to produce (trying to declare variables themselves, trying to declare functions themselves...) has to be almost completely rewritten if you are targeting a different assembly language compiler or a different operating system.
However, the solution I've made may be even worse than the problem. The programs written in that programming language are completely non-portable. Also, since my compiler tries to make as few assumptions as possible, it produces way inferior Assembly code than any decent C-compiler would. However, it seems to make no perceptible difference on a what's now a 12-year-old computer (the Assembly code a JavaScript JIT-compiler produces is probably even less optimal). Also, because of the design of my programming language, it often happens that a compiler doesn't catch an error such as using an undeclared variable and outputs syntactically invalid Assembly.
I am also dreaming about making a compiled LISP-like language in which you could write arithmetic expressions in both S-expressions and infix-expressions, but be able to use only S-expressions elsewhere (since they come very handy in string and array-manipulation). However, I probably won't have time for that in foreseeable future.

You would probably benefit from some formal education.
[Image: extraordinarywoo-sig.jpg]
#4
RE: Arithmetic Expression Compiler
Quote:This is so far out of my wheelhouse that I couldn't comment intelligently on it.
Well, that's kind of how I feel when you talk about how Chrome is the only good browser because it is the only one that allows the users to publish voice-recordings to your website - I have no idea what you are talking about.
Quote:scripting old / small processors for use in robotics
Well, you know, the compiler algorithm I've made kind of breaks for ARM processors, it assumes the existence of a stack inside the processor (like the FPU stack in x86).
I mean, yeah, I suppose I could arrange the 15 general purpose registers (or even just a portion of them) in a stack and then "push" and "pop" the values using the macros (a decent assembly-language compiler, assuming such exists for ARM, would allow me to do that). The obvious problem with that is that it would lead to unreasonably large executables (but I don't think performance would be a problem, since ARM processors are known to move values between registers a lot faster than Intel or AMD processors).
Very few assembly-language compilers (I assume none of those available for ARM) would allow me to make statements such as:
Code:
mov [result],3.141592f
However, if I am using the Duktape framework, that actually wouldn't matter much because I could just invoke a C function from JavaScript that would do pointer aliasing to give me hexadecimal IEEE 754 code (and both x86 and ARM support little-endian). So, I could easily output something like:
Code:
mov r0,0x40490fd0 ;3.141592
mov [result],r0
The biggest problem is that ARM, being a RISC processor architecture, doesn't have anything like the x86 "fsin". That would lead to very different kinds of problems than what I had to solve when making an app that outputs x86 assembly (which has those instructions, but they often change the FPU stack in a counter-intuitive way). I could solve those problems by, for instance, making a complicated macro that would calculate trigonometric functions using factorials (assuming that can be done without corrupting the "processor stack", I am not sure if that's possible). Calculating logarithms and exponents will probably be just as problematic in ARM assembly as it is in x86 assembly.
Or, unless I am working on bare metal, I could simply temporarily "store" the stack somewhere in memory, request the kernel to do the complicated calculations for me, and then reload the stack into the processor registers. But, if I want to be consistent, I'd have to do that very often since, if I quickly look up online, the ARM assembly doesn't even have the equivalent of "fprem" (which I used quite often in my compiler).
Those are just the problems I can think of right now.
Quote:You would probably benefit from some formal education.
Why exactly? What do you think I am doing wrong that a formal education would help with?
#5
RE: Arithmetic Expression Compiler
(January 3, 2019 at 4:47 am)FlatAssembler Wrote:
Quote:You would probably benefit from some formal education.
Why exactly? What do you think I am doing wrong that a formal education would help with?

Because a lot of the issues that you grapple with, and productive approaches for confronting them, are covered in formal education. In short, you are doing things the hard way. There's some value in that, I'm sure, but if your real goal is to learn, a formal education would do you much better than wandering alone in the wilderness. Other people have walked the path and can teach you based on their experience. By doing it alone, you're foregoing the benefit of their experience and their work.
[Image: extraordinarywoo-sig.jpg]
#6
RE: Arithmetic Expression Compiler
I don't think I am doing it the hard way, I think it's that x86 assembly and especially ARM assembly just aren't easy compilation targets.
The x86 Assembly language doesn't appear to follow the principle of least surprise at all. ARM assembly is said to be significantly more consistent, but that comes at a price of not having useful directives (such as the basic trigonometric functions, basic logarithmic and exponential functions, basic cyclometric functions...) built in. If you target those, you need to spend hours and hours debugging the assembly (and perhaps the easiest way to do that is to repeatedly call C functions such as "printf" from assembly code, which is itself very error prone) instead of implementing new features to your compiler.
That's why almost every compiler collection has its own byte code (GIMPLE in GCC, LLVM IR in CLANG...), which is intended to be easier to compile to than assembly, but it's still supposed to be easy to translate into any particular assembly. WebAssembly is also designed to be extremely easy to compile into.

By the way, what do you guys here think, what is the best compiler for C if you are just targeting the common Windows on Intel architecture? I think it's by far the Tiny C Compiler. It compiles the entire Duktape in an imperceptible amount of time on my 12-year-old laptop, while GCC takes more than 10 seconds to do the same. It's said that TCC produces inferior assembly code than GCC does, but, for the Duktape-based compiler I've made, the difference is imperceptible. I value being able to quickly modify my C program when debugging it more than being able to produce assembly optimized for the super-modern 64-bit processors (which my 12-year-old laptop can't execute anyway).

BTW, let me be clear, I am not planning to continue developing it. I've made it just in case somebody asks me "Do you know anything about how the compilers work?", that I can shut them up by saying "Sure, I've made one! From scratch, in JavaScript. For my own simple programming language that compiles into Assembly.".
#7
RE: Arithmetic Expression Compiler
FA, I have to say simply that you are on a different path than I am. There's real value in getting under the hood and playing with these little details. Whether you can convert that into a professorship or a paying job some day, I can't say.

I don't believe anyone here is going to be able to comment intelligently on this kind of project, though I've done some of the kind of thing you're talking about in the past. When I was a kid, I used assembly to rewrite parts of computer OS, and that was really a lot of fun for me. But now, I'm more interested in leveraging technologies to bring functionality to users.

In short, you're talking over my head now, so without seeming rude, I'm not going to answer any more posts unless they are about things that fall within my current interests and areas of expertise.
#8
RE: Arithmetic Expression Compiler
Well, yes, what I am doing is said to be very specialized. But, from my standpoint, most of the things programmers do are very specialized. I've heard of SVG only after five years of studying programming, for example. And, though I've heard of CSS before, only after five years of studying programming is that I got familiar with its basic syntax.
And making a website on which people can publish voice recordings is also quite a specialized action, isn't it?
#9
RE: Arithmetic Expression Compiler
(January 9, 2019 at 5:08 am)FlatAssembler Wrote: Well, yes, what I am doing is said to be very specialized. But, from my standpoint, most of the things programmers do are very specialized. I've heard of SVG only after five years of studying programming, for example. And, though I've heard of CSS before, only after five years of studying programming is that I got familiar with its basic syntax.
And making a website on which people can publish voice recordings is also quite a specialized action, isn't it?

Yes, no doubt.  Without being arrogant, I'd say that because I program for language instruction, I'm likely to know how to do things that few other programmers, even good ones, know how to do.  Specializing in one or two things, there would be a million programmers who are much better than I am.  I'm okay at web programming, but many are much better.  I'm okay with making complex database structures, but millions are better.  I'm okay at working with Javascript interfaces with Android browsers, but thousands are better.  I'm okay at music composition, 3D character animation, audio sound manipulation, and maybe a dozen other skills, but millions are better.

However, I doubt many are better than I am at integrating several skills from that list in a solo project.  That's why though I run a small business, none of the big super-chain businesses in my market can reproduce any of the projects I'm working on-- they'd have to hire large teams of specialists, have a project head, and spend many tens of thousands of dollars to do what I can do in a couple free weekends.  And even if they found those specialists, whose vision would they use even to determine what their project should DO, unless at least some of them have also taught English for 20 years?

Your interests in assembly compilation and web programming have already put you on a unique path, and that's not to be underestimated.  I wasn't joking when I mentioned robotics programming.  Many of the chips used in robotics are very old.  For example, you can buy a 6809 chip for a couple dollars that used to be the flagship CPU of home computers 30 years ago.  Most people use C libraries for programming such devices. . . but if you could compile custom assembly code for them, you could multiply their efficiency by maybe 10x. This would allow the use of very low-cost parts for controlling drones, for example, instead of more expensive more high power parts running inefficient code.

Look at it this way-- I know a lot of things about various aspects of programming, but I would never even TRY to write a compiler.  If a company was ever looking for a web programmer who could compile functions on the fly, I'd be disqualified.  And that's what I meant with my comment to you-- not that I'm turning my back on you, but that your unique interests make me unqualified to speak intelligently on much of what you're trying to do.
#10
RE: Arithmetic Expression Compiler
Eff compilers. I got an A in Compiler Design and I never want to see anything about it again.
"There remain four irreducible objections to religious faith: that it wholly misrepresents the origins of man and the cosmos, that because of this original error it manages to combine the maximum servility with the maximum of solipsism, that it is both the result and the cause of dangerous sexual repression, and that it is ultimately grounded on wish-thinking." ~Christopher Hitchens, god is not Great

PM me your email address to join the Slack chat! I'll give you a taco(or five) if you join! --->There's an app and everything!<---



Possibly Related Threads...
Thread Author Replies Views Last Post
  Compiler Theory FlatAssembler 5 986 October 27, 2020 at 10:48 am
Last Post: Angrboda



Users browsing this thread: 1 Guest(s)