Programming Thread

Started by the-pi-guy, Mar 13, 2016, 10:39 PM

previous topic - next topic

0 Members and 1 Guest are viewing this topic.

Go Down

the-pi-guy

So we are learning about strictly functional programming.

Where absolutely everything is done using functions.

So there's nothing like a+b, instead, it's add(a,b)

And most things are done using recursion.

Legend

So we are learning about strictly functional programming.

Where absolutely everything is done using functions.

So there's nothing like a+b, instead, it's add(a,b)

And most things are done using recursion.
Does that change things really?

I know in C# a+b calls a function anyway.

the-pi-guy

Does that change things really?

I know in C# a+b calls a function anyway.
Not in that case, but pure functional programming languages don't have for or while loops.

You have to do loops like this:

loop(i, limit){
if(lessThan(i,limit)){
   loop(add(1,i),limit)
}
}

the-pi-guy

So I spent way too much time trying to install a portal virtual machine. But it kept giving an error and the internet wasn't much help.  

Finally gave up.  Installed the regular version.  

After all that I spent a while trying to figure out the syntax for this program.  

Around midnight I was getting prepared to give up and finally some of the test cases were passing.  

Spent about an hour fixing them pretty easily.  Except two were giving bizarre errors that still don't make sense.  I ended up doing something weird.  

1-(2+3) was returning -22, which makes no sense.  However you look at it.  

Then I added 1*1-(2*1+3*1) and suddenly it was parsing correctly.  

I am wondering if JavaScript was taking the numbers as some weird encoded value.  But oh well.  I am done.

Legend

So I spent way too much time trying to install a portal virtual machine. But it kept giving an error and the internet wasn't much help.  

Finally gave up.  Installed the regular version.  

After all that I spent a while trying to figure out the syntax for this program.  

Around midnight I was getting prepared to give up and finally some of the test cases were passing.  

Spent about an hour fixing them pretty easily.  Except two were giving bizarre errors that still don't make sense.  I ended up doing something weird.  

1-(2+3) was returning -22, which makes no sense.  However you look at it.  

Then I added 1*1-(2*1+3*1) and suddenly it was parsing correctly.  

I am wondering if JavaScript was taking the numbers as some weird encoded value.  But oh well.  I am done.
Haha yeah 2 and 3 must have been interpreted as strings so adding them produced 23. Multiplying by 1 forced javascript to think of them as numbers.

the-pi-guy

Haha yeah 2 and 3 must have been interpreted as strings so adding them produced 23. Multiplying by 1 forced javascript to think of them as numbers.
With how tired I was, I somehow still knew what was happening, but not really why.

Now that I'm rested, it's pretty obvious that's what was happening.  

the-pi-guy

The structure of a compiler:


Phase 1:  Lexical Analyzer: converts a file into tokens.  

This part of the compiler basically figures out where the keywords are.  Basically it goes through the file character by character, usually discarding the white space.  It's what figures out if "IF" identifies something or if it's the start of an if statement for example.  

Spoiler for A typical set of tokens that might be matched up::
<br>-ID<br>-DOUBLE<br>-INT<br>-IF<br>-THEN<br>-ELSE<br>-WHILE<br>-FOR<br>-SWITCH<br>-CASE<br>-STATEMENTS <br>--PRINT STATEMENT<br>--ASSIGNMENT STATEMENT<br>-LPAREN<br>-RPAREN<br>-MULT <br>-DIV<br>-PLUS<br>-MINUS<br>-MOD <br>


Phase 2:  Syntax Analyzer: converts list of tokens into a parse tree

The syntax analyzer matches up a string in a grammar to figure out how to build the parse tree.  

A simple grammar:
S -> S + S | S - S | T
T -> T * T  | T / T | U
U -> (S) | NUMBER
NUMBER -> (0-9)+

This grammar generates all expressions like 7+4*3, 1+2*3/4, etc.

But this grammar has a problem, it is ambiguous.  For each of the strings above, there are multiple different ways to build a parse tree that matches.
Leftmostderivations jaredwf.png

This means that the expressions like 1-4+3 could be interpreted different ways.
The compiler could run it like 1-(4+3) or (1-4)+3
We could get 0 or -6 in this case.  

So ambiguous grammars are bad, because they can lead to those kinds of problems.
For the simple expressions like these, we need something that does:
-Precedence (multiplying comes before adding)
This is done by having operations with higher precedence lower in the grammar.
-Associativity (whether a-b-c is interpreted as a-(b-c) or (a-b)-c )
This is done by matching each left associative operation with a left recursive production and same with the right.  This looks like:
A -> A * B | B / A
B -> NUMBER

In this example, multiplication is left associative, and division is right associative.  So in the division example a/b/c/d, the compiler would solve c/d first.

Phase 3: Semantic Analyzer

This phase does things like type checking.  You'll basically run through the parse tree and make sure that the types match.

Phase 4:  Intermediate code generation

This phase goes through the parse tree to build the code.

This part can be pretty tricky.  You want to do things like building a symbol table to keep track of where a variable gets used and to keep track of scope.  
Have to be able to access the symbol table to know whether you're in the local variable space for x.  

If your compiling into assembly, you'll need to keep track of what memory locations are used for what variables, as well as what variables are in what registers.
An expression like  
a = a + b;
int c = a + b;
might have to become something like (in more like psuedocode):
load register1, a
load register2, b
add register1, register1, register2
store a
add register3, register1, register2
store c

Phase 1,2 and 4 are essentially the minimum of what a compiler needs.  

A good compiler is also going to have phases for code optimization, and final code generation.

A fancy compiler can have some pretty sophisticated processes for code optimization.  

Some things that can be done include looking at the exit condition for a function.  I recall seeing that gcc will actually simplify the following code:

function square(int x){
int i = 0;
  while(i<x*x){
i++;
}
return i;
}

into the following:

function square(int x){
return x*x;
}

I don't know if that's actually what the example was, but it was something like that.

Legend

I know every single thing online always says "never make your own game engine," but I'm getting really excited about starting mine. The primary goal is to make an engine for my 4D game but ideally I'd use this engine for all my games going forward. A few things I'd like

Good alt version support. Unity is great at making a game run on multiple systems but it still has lots and lots of things that only work by making separate projects for each SKU. I'd like my engine to have a system where SKUs are easy to define and automatically handled. (as an extreme example, a demo would exist in the same project as the full game instead of being forked off)

Decent scalability. I realised that I tend to make niche games that can be really exciting for people that don't consider themselves video game players. It would be smart to make an engine that can run on older computers. It doesn't need to look good, but it should be able to run smoothly.

High precision. Doubles and longs should be used on most things. First of all I just like them, secondly I tend to use complex geometry where imprecision adds up, thirdly suspend/resume mean that games can run for weeks without being reset, and fourthly I'd love to make a space game one day.

Splitscreen/local multiplayer support. Goes without saying.

Rock solid frame rates. The actual act of rendering should be safe to perform at any time. Essentially the camera and critical components are guaranteed to update every frame but other things can be skipped as needed. Basically asynchronous timewarp but built into the game and available even in 2D. The game should have a steady framerate but this is a safety net.

the-pi-guy

-Trying to install an IDE
-Won't install, due to build problems
-can't find any help because every google result is about the IDE not building a program, and not the other way around....  

darkknightkryta

So we are learning about strictly functional programming.

Where absolutely everything is done using functions.

So there's nothing like a+b, instead, it's add(a,b)

And most things are done using recursion.
Dr. Racket?

the-pi-guy


darkknightkryta

We are using JavaScript.  
Oh.  The University of Waterloo here created a language that sounds exactly as you described.  

the-pi-guy

Oh.  The University of Waterloo here created a language that sounds exactly as you described.  
It's not that the language doesn't do other things, we just aren't allowed to do those things...  

darkknightkryta

It's not that the language doesn't do other things, we just aren't allowed to do those things...  
That sounds excessive. "I'm going to force my way of programming on my students and teach nothing practical".  Unless this is some weird data structure class.

the-pi-guy

Mar 23, 2019, 06:23 PM Last Edit: Mar 23, 2019, 06:26 PM by the-pi-guy
That sounds excessive. "I'm going to force my way of programming on my students and teach nothing practical".  Unless this is some weird data structure class.
It's just the functional programming part of the course.  We are just required to make all our functions in the form of functional programs, so we arent allowed to use non-functional programming techniques.  

I know every single thing online always says "never make your own game engine," but I'm getting really excited about starting mine. The primary goal is to make an engine for my 4D game but ideally I'd use this engine for all my games going forward. A few things I'd like

Good alt version support. Unity is great at making a game run on multiple systems but it still has lots and lots of things that only work by making separate projects for each SKU. I'd like my engine to have a system where SKUs are easy to define and automatically handled. (as an extreme example, a demo would exist in the same project as the full game instead of being forked off)

Decent scalability. I realised that I tend to make niche games that can be really exciting for people that don't consider themselves video game players. It would be smart to make an engine that can run on older computers. It doesn't need to look good, but it should be able to run smoothly.

High precision. Doubles and longs should be used on most things. First of all I just like them, secondly I tend to use complex geometry where imprecision adds up, thirdly suspend/resume mean that games can run for weeks without being reset, and fourthly I'd love to make a space game one day.

Splitscreen/local multiplayer support. Goes without saying.

Rock solid frame rates. The actual act of rendering should be safe to perform at any time. Essentially the camera and critical components are guaranteed to update every frame but other things can be skipped as needed. Basically asynchronous timewarp but built into the game and available even in 2D. The game should have a steady framerate but this is a safety net.

How's it going?

Go Up