Crafting an interpreter in PureBasic

Just starting out? Need help? Post your questions and find answers here.
Thorium
Addict
Addict
Posts: 1268
Joined: Sat Aug 15, 2009 6:59 pm

Re: Crafting an interpreter in PureBasic

Post by Thorium »

Rinzwind wrote:Most just want a convenient way to structure data and its behaviour.
Thats the biggest flaw of OOP. Data and code should not belong together. It may be easier for a human to think about an object which encapsulated the code and data it operates on. But it's fundamentally not how the computer works. You got code, which operates on data. The abstraction layer of combining them together just decreases your performance and for me personally is harder to understand than writing code which operates on data, which exists independently from the code.
And that OOP performance is a real world problem is proven by the "new" approaches taken to increase performance of games, they call it data driven programming, which breaks away from the concept of combining data and code into objects. It's also used to drastically increase browser performance as traditionally everything in browser coding is an object.
Rinzwind wrote: which can be immensely useful to simplify coding.
In my experience this "simplification" in coding is just an illusion. I agree it's easier to handle multiple instances of things. However it's also not particularly hard or much work to implement it with the procedural style. In the end you just tade some coding simplifications for performance and more problems down the line. You spend much more time on the origanization of your objects, which for me defeats the purpose of a abstraction layer, which OOP is supposed to be. Abstract parts of coding for convenience. However that convenience is very shallow and bites you back later when your biggest worry is how to organize your object classes and how they should communicate with each other. You start to add code in just to handle how objects interact with each other, that need to interact. In the real world you never have a perfect hirarchy where your flow just trickles down a tree, but that is what OOP wants you to have. If you start to use cross references and manager objects, you realize your code isnt actually more reusable as procedural code as you got a ton of dependencies between objects.

That said, i am not against optional additions which enable easier use of OOP. However it's not required at all in my opinion.
User avatar
mk-soft
Addict
Addict
Posts: 3191
Joined: Fri May 12, 2006 6:51 pm
Location: Germany

Re: Crafting an interpreter in PureBasic

Post by mk-soft »

As you can guess, I have been very busy with OOP, because I needed to know how OOP works internally for a project (out of interest and later in application).
Otherwise I wouldn't have been able to access COM objects with Purebasic.

To program object-oriented with Purebasic, you have to do everything yourself that other compilers do for you. First I wrote a pre-compiler, after that only via macros (see OOP-BaseClass).

Even if it makes sense for certain tasks to implement them as OOP, it is actually a disaster for the processing in the programme.

1. request memory, 2. allocate virtual table, 3. call construtor, 5. make object ready. 6. object no longer needed, 7. call destructor, 8. delete memory, 9. lock object call. (Can't PB, Only one gabage managment).

It gets worse when objects are chained (mine do not inherit).
Result = Object.SubObject(Paran).Object.Value
You can imagine that at every point an object is created -> object create -> value <- object release <- object release is executed.
I do not consider this to be optimised.

But I think you can also use OOP sensibly in certain cases, but not for everything.

Many use COMatePlus to access existing objects, which is not necessarily bad. But since it uses the late binding, this programming technique is internally very time-consuming, since the parameters always have to be packed together first, the object method ID is queried from the name and then the function is called via the Invoke method using the ID. Then the parameters and the method are separated again internally by Invoke and the function is called.

Maybe think about working with early binding. This means calling the methods of the object directly via the description of the interface. For many objects, the interfaces for early binding are already declared in Purebasic. See PB tool structures and interfaces.

Thanks DeepL.com :wink:
My Projects ThreadToGUI / OOP-BaseClass / OOP-BaseClassDispatch / EventDesigner V3
PB v3.30 / v5.70 - OS Mac Mini OSX 10.xx - VM Window Pro / Linux Ubuntu
Downloads on my Webspace
User avatar
TheAutomator
User
User
Posts: 94
Joined: Tue Dec 01, 2020 8:33 pm

Re: Crafting an interpreter in PureBasic

Post by TheAutomator »

interesting stuff @Olli!
purebasic is all about coding it yourself isn't it?

also about the OOP thing:

functional languages are handy for most stuff, but if you need to go abstract it's a little harder.. like for making an ast in this example. :)
User avatar
Tenaja
Addict
Addict
Posts: 1829
Joined: Tue Nov 09, 2010 10:15 pm

Re: Crafting an interpreter in PureBasic

Post by Tenaja »

TheAutomator wrote:interesting stuff @Olli!
purebasic is all about coding it yourself isn't it?

also about the OOP thing:

functional languages are handy for most stuff, but if you need to go abstract it's a little harder.. like for making an ast in this example. :)
Have you tried one of the code pastes on the forum? I know there are C libraries that can be converted, too, and they resemble some of the options presented.
https://stackoverflow.com/questions/203 ... of-lists-c

It doesn't matter a whole lot if it's native or not, a solution is a solution. Most languages have a disadvantage...heck, C doesn't even have any type of lists native. (But there are numerous solutions available--even Rosetta Code has them.) I guess you just have to decide if a function call is too much effort to disqualify PB from your project.
User avatar
TheAutomator
User
User
Posts: 94
Joined: Tue Dec 01, 2020 8:33 pm

Re: Crafting an interpreter in PureBasic

Post by TheAutomator »

actually, it DOES matter, because if something that basic isn't build in and it requires you to reinvent the wheel (on a memory management scale), for experienced users a lot can go wrong. messing with memory and not knowing what you're doing makes it a lot harder for users like me who didn't have a masters diploma on computer science..

purebasic is not free, I'm trying to decide if the learning curve for something as basic as making a list is gonna be worth it or not. it feels a bit like having a wonderful car in front of you, it's driving superb, has a nice layout, doesn't use a lot of fuel ... BUT if you want airbags, well you have to build that part of the car yourself :p

i love the language, but i think it can be a little bit more user friendly when it comes to stuff al lot of other programming languages have:

variants
oop
dynamic nested lists

build in.

this is just my opinion and i know there are different opinions going around here so here is what I'm going to do..

I'm going to research about the more low level stuff like memory and pointers (partially did that already),
try my best to figure out how to write functions that do what i need and (important) fully understand what they do.
examine the examples you guys kindly wrote for me as a reference,
show what i got so far by posting updates here (for anyone interested),
and hopefully have a nice little interpreter by the end :)

before i start with the nested list functions and such, do any of you guys think this is a good way of building an interpreter inside of a functional language? or are there different approaches (not talking about compilers or assembly stuff) that would be better if you don't work with oop?

that last question comes from the idea that interpreters always work with some kind of AST and recursion, the shunting yard algorithm was my first approach but that's another story, not a fan of that algorithm for making an interpreter.
User avatar
Tenaja
Addict
Addict
Posts: 1829
Joined: Tue Nov 09, 2010 10:15 pm

Re: Crafting an interpreter in PureBasic

Post by Tenaja »

Reinvent the wheel? You've been given several examples, both in PB and in C. It's more like updating the text on the sidewall of the wheel.
User avatar
Tenaja
Addict
Addict
Posts: 1829
Joined: Tue Nov 09, 2010 10:15 pm

Re: Crafting an interpreter in PureBasic

Post by Tenaja »

TheAutomator wrote: before i start with the nested list functions and such, do any of you guys think this is a good way of building an interpreter inside of a functional language? or are there different approaches (not talking about compilers or assembly stuff) that would be better if you don't work with oop?

that last question comes from the idea that interpreters always work with some kind of AST and recursion, the shunting yard algorithm was my first approach but that's another story, not a fan of that algorithm for making an interpreter.
I wrote a fully functional compiler without nested lists--not just a toy compiler to prove I could do it, but one that was used for product. I used a flat list, but organized it to allow walking the tree for optimization with every bit of functionality that nested lists could provide. I started it before PB had the Module feature, so the first functioning versions didn't even have that, much less all the oop stuff you've mentioned.

If you've learned oop and "need" it for a complex project, then I'm sure PB's limitations may feel stifling. Most people who have their heart set on oop either implement one (be it a shared one or self-written), or they move on. You just have to decide how critical it is for you. I think FreeBasic and Oxygen Basic both have classes (I think), but I've never used either, and their forums are not very active.

If you'd like a great tutorial to make it more simple, search for Crenshaw's Let's Build a Compiler. He has one chapter dedicated to interpreters, but it should be enough to apply it to the rest of the compiler.
User avatar
TheAutomator
User
User
Posts: 94
Joined: Tue Dec 01, 2020 8:33 pm

Re: Crafting an interpreter in PureBasic

Post by TheAutomator »

Tenaja wrote:Reinvent the wheel? You've been given several examples, both in PB and in C. It's more like updating the text on the sidewall of the wheel.
yeah, that's what you guys did here? reinvent functions to make lists that already exist in other languages..
but like i said, diving into it ;)

re: "Crenshaw's Let's Build a Compiler"
cool, let me have a look!

do you still have the source code of your interpreter? would like to see (if you did that) how you made function code blocks an arrays work :)
User avatar
Tenaja
Addict
Addict
Posts: 1829
Joined: Tue Nov 09, 2010 10:15 pm

Re: Crafting an interpreter in PureBasic

Post by Tenaja »

Crenshaw covers those topics nicely. I'm not permitted to share mine.

Trond here on the forum also converted Crenshaw to pb... Don't have a link, but there might be one of you search the forum. He does nice work, but unfortunately he's intermittent here.
User avatar
blueb
Addict
Addict
Posts: 922
Joined: Sat Apr 26, 2003 2:15 pm
Location: Cuernavaca, Mexico

Re: Crafting an interpreter in PureBasic

Post by blueb »

Tenaja wrote: Trond here on the forum also converted Crenshaw to pb... Don't have a link, but there might be one of you search the forum. He does nice work, but unfortunately he's intermittent here.
found it :mrgreen:

https://pbtut.blogspot.com/2009/08/base.html
- It was too lonely at the top.

Current Machine: Win 10 Pro 64-bit, AMD Ryzen 9 5900X, 64 gigs ram, Geforce GTX 1660 Ti w/6 gigs ram
User avatar
TheAutomator
User
User
Posts: 94
Joined: Tue Dec 01, 2020 8:33 pm

Re: Crafting an interpreter in PureBasic

Post by TheAutomator »

https://pbtut.blogspot.com/2009/08/base.html

ehm.. he's building a compiler using assembly, that's not at all what i'm trying to do.
User avatar
Tenaja
Addict
Addict
Posts: 1829
Joined: Tue Nov 09, 2010 10:15 pm

Re: Crafting an interpreter in PureBasic

Post by Tenaja »

TheAutomator wrote:https://pbtut.blogspot.com/2009/08/base.html

ehm.. he's building a compiler using assembly, that's not at all what i'm trying to do.
If you are trying to build an AST, then it is almost exactly what he did. The only difference is he saved the asm to a text file instead of to an AST memory block. Read Crenshaw's chapter on interpreters, and you will see that only one step varies.
User avatar
Tenaja
Addict
Addict
Posts: 1829
Joined: Tue Nov 09, 2010 10:15 pm

Re: Crafting an interpreter in PureBasic

Post by Tenaja »

I have not studied interpreters as much as I have studied compilers (I frequently skipped those chapters), so take this with a grain of salt. However, after thinking on it, it seems to me there may be two primary ways to craft an interpreter. The first is the 80's way where you scan line by line, and when you jump, you scan from the top until you find the target. I'm not sure an AST makes sense in this case, unless you keep a Map or List of all line numbers with jumps and their targets, so you can skip the "scan from top" step, and instead, reference your List or Map. Either way, this is likely the simplest, which is why it was so popular on the 6502. An AST just adds complexity.

What seems to be more common now is a 2-step process, starting with turning the code into bytecode. We all know Java does it (they call it a compile step), but so does Lua (the script language), and even Python (the "interpreted" language) does it:
https://opensource.com/article/18/4/int ... n-bytecode
http://www.jucs.org/jucs_11_7/the_imple ... iredo.html
With a two-step system like this, you need the compiler (sometimes called an interpreter) to generate the bytecode, and then the "virtual machine" that runs it. In this case, the generation of the bytecode is exactly like an asm compiler from a mechanical standpoint--I don't know about Lua, but Java and Python even save the "compiled" file. Depending on the needs of the system, I'd likely do this, because I could convert my compiler by only changing the emitter. But then I'd have to write the "virtual machine" to run it.

You have talked about generating an AST. In this context, that is essentially a bytecode--the second method. If you are going to "execute" your ast, then read the Crenshaw docs with the mindset that you are emitting bytecode...which is a fancy name for either machine code or assembly language for your virtual machine. However, instead of emitting the literal text "Push Var1", you will emit the bytecode for Push, then your var (either a pointer to it or a Map to it, or something like that). And, whether your Emit destination is into a file or into memory (i.e. into a List) is a trivial difference in the grand scheme.

In a nutshell, read Crenshaw's article--every chapter.
Olli
Enthusiast
Enthusiast
Posts: 421
Joined: Wed May 27, 2020 12:26 pm

Re: Crafting an interpreter in PureBasic

Post by Olli »

interesting stuff @Olli!
purebasic is all about coding it yourself isn't it?
Thank you, but I do not understand what you wonder... I was coding this for a homemade protected mode on a 80286, 22 years ago. You have all the rights, without problems... :-)

I prefer say you that structures in PB are not to be used dynamically. They are here to help the coder, that is sure, but no more. No dynamical including/excluding.

Why ? Because, the dynamical use is there :

Code: Select all

Structure Mem
   Dta.I[0]
EndStructure
Zero is generic here. What it means Dta[0] is the first integer, Dta[1] (yes : 1) is the second integer, Dta[2], the third one, etc... Until the end of the memory block, allocated with AllocateMemory(). It is dynamic, but limited to the field "Dta".

You can try, or ask anybody to check if I do a mistake but, I do not think you can store two generic fields like this

Code: Select all

Structure Fails
   I.I[0]
   S.S[0]
EndStructure
The reason is simple : all this is converted during the compiling.

Alternative :

Code: Select all

Structure StringTable
   S.S[0]
EndStructure

Structure IntegerTable
   I.I[0]
EndStructure

Structure DynamicData
   *S
   *I
EndStructure

Code: Select all

#is = Sizeof(Integer)

*M = AllocateMemory(#is * 100)
*DD.DynamicData = *M
*DD\S = *M + SizeOf(DynamicData)
*DD\I = *M + 50 * #is
*ST.StringTable = *DD\S
*IS.IntegerTable = *DD\I
Ok...

Here you have 2 integers for store 2 heap starts,
48 integers for store integers heap, and
50 integers for store strings heap.

All is absolutely dynamical :

* you can reallocate the 100 integers to 1000, 200, 10, x or y integers.
* you can move the several pointors (or heap starts) respecting the limits.

Note that read/write example is not mentionned, just indexing

Code: Select all

; string write example
*ST\S[5] = "Hello" ; (6th string is stored with "Hello")
Thank you Google search
User avatar
TheAutomator
User
User
Posts: 94
Joined: Tue Dec 01, 2020 8:33 pm

Re: Crafting an interpreter in PureBasic

Post by TheAutomator »

To come back to @Tenaja's idea to use some sort of bytecode.
well i just read the 2 articles about that and the use of labels is very interesting for nesting code!

the blogspot link seems to use recursive calls to functions to write bytecode.
I didn't know at first it was possible to get a tree structure plus recursive calls to functions back out of a list of instructions that way.

the way i used to build an ast if i couldn't use oop is this way:

Code: Select all

read tokens to token_stack{}
define AST_LIST{}

for each token in token_stack:
	push statement() to AST_LIST
until end of token_stack

call execute(AST_LIST)

func statement()
	define STATEMENT_LIST{}
	if token = "exit"
		push "exit" to STATEMENT_LIST
		next token
	if token = "if"
		push "if-statement" to STATEMENT_LIST
		next token
		push "boolean value" to STATEMENT_LIST
		next token
		push statement() to STATEMENT_LIST
		expect "end"
		next token
	if ...
	return STATEMENT_LIST{}
end

func execute(sub_list{})
	for each item in AST_LIST
		if item(1) = "if-statemen" and item(2) = "true"
		execute(item(3))
		if ...
	next
end
That's why nested lists appeal so much to me, when they are build you can just recursively traverse them,
you can also store whole function blocks in a separate map with a name and call them at will throughout your program.

for me that's the most easy and direct way, and this all in memory! :D
no bytecode, no saving to files, no assembly :)
Post Reply