BrainPad Language Implementation

Since the GHI post was the inspiration for this little vacation project I thought I would share my progress and challenges here. I did not want to pollute the original BrainPad post with my posts, just because at this point this is still just a .NET core project until

  1. I get a better understanding of what BrainPad supports
  2. I actually get a BrainPad to play with

The language supports the following

  • Recursion
  • Passing functions as arguments - useful for callbacks (think interrupt handlers)

From a design perspective, I decided to generate an an AST (abstract syntax tree) during the parsing stage rather than directly executing the code from the source.

Using an AST makes things quite flexible, once you have compiled the AST you can do a few cool things

  1. Write a tree walker that can do a few simple code optimizations (I will implement some constant folding and dead code elimination as an example)
  2. Write a tree walker that executes directly from the AST. The advantage is that all the parsing, variable and function calls have been resolved so executing from the AST does not require any further scanning of the code to find function entry points etc.
  3. You could write a tree walker that generates code. This code could be some form of intermediate code that is cheap to execute or it could generate native code for the target system.

The current implementation has a simple tree executor back end.

For the curious, I started documenting what I have in the language so far using a syntax loosely based on EBNF. I have not documented everything yet, but what is documented is implemented.

Language Structure

<stmt>      := <vardecl>
                | <assignment>
                | <funcdecl>
                | <funccall>
                | <return>
                | <if>
                | <while>
                | <for>
                | <break>

<stmtblock> := '{' <stmt>* '}'

<vardecl>   := 'var' <ident> '=' <expr>
<assignment>:= <ident> '=' <expr>
<funcdecl>  := 'func' <ident>'('<params>')' <stmtblock>
<params>    := <ident> [',' <ident>]*
<funccall>  := <ident>'(' <args> ')'
<args>      := <expr> [',' <expr>]*
<return>    := 'return' <expr>
<if>        := 'if' <expr> <stmtblock> [<else>]
<else>      := 'else' [<if> | <stmtblock>]
<while>     := 'while' <expr> <stmtblock>
<for>       := 'for' [<vardecl> | <assignment>] ';'
                    [<expr>] ';'
                    [<expr>] <stmtblock>
<break>     := 'break'

<expr>      := <relexpr> [<logicalop> <relexpr>]*
<relexpr>   := <addexpr> [<relop> <addexpr>]*
<addexpr>   := <multexpr> [<addop> <multexpr>]*
<multexpr>  := <factor> [<mulop> <factor>]*
<factor>    := '(' <expr> ')'
                | <number>
                | <string> [<indexer>]
                | <funccall> [<indexer>]
                | <ident> [<indexer>]
<indexer>   := '['<expr>']'

<logicalop> := 'and' | 'or'
<relop>     := '==' | '<>' | '<' | '<=' | '>' | '>='
<addop>     := '+' | '-'
<mulop>     := '*' | '/' | '%'

## Builtin Functions

print(<args>)
println(<args>)

len(string)
left(string, count)
right(string, count)
mid(string, index, count)

abs(value)
sqrt(value)
sin(radians)
cos(radians)
tan(radians)
asin(radians)
acos(radians)
atan(radians)
atan2(y, x)
2 Likes

I have made the repository public. The code is still quite rough, and I will be committing frequently so I might be breaking things along the way. For testing I implemented a makeshift REPL and the ability to execute a file by passing it on the command line.

1 Like

That is great. I haven’t looked at it yet but will very soon.

There has been some code cleanup especially with regard to the distinction between statement and expression AST nodes. I was initially considering making everything an expression but ultimately decided against it so I made that decision more explicit in the AST.

I have also added a simple (very simple) optimizer, it is still very rudimentary but it does a few interesting things

  1. Constant folding
  2. Simple algebraic simplifications
x + 0 => x
0 + x => x
x - 0 => x
0 - x => -x
x * 0 => 0
0 * x => 0
0 / x => 0
x / 1 => x
x * 1 => x
  1. Function call optimization

I have a few other interesting optimizations in mind, something that can quite easily be done already is very basic dead code elimination.

It is interesting how often I need to stop myself using things like generics etc. I am trying to use things that I remember were not available in .NETMF which I assume is similar for TinyCLR.

1 Like

From the examples folder, here is a little program that prints the primes below 100

//*****************************************************************************
// isPrime tests the primality of a number
// Algorithm from: https://en.wikipedia.org/wiki/Primality_test
func isPrime(n) {
    if n <= 3 {
        return n > 1
    }

    if n % 2 == 0 or n % 3 == 0 {
        return 0
    }

    var i = 5
    while i*i <= n {
        if n % i == 0 or n % (i + 2) == 0 {
            return 0
        }
        i = i + 6
    }
    return 1
}

var primes = 0
for var i = 0; i < 100; i=i+1 {
    if isPrime(i) {
        print(i, ", ")
        primes = primes + 1
    }
}
println()
println("Found ", primes, " prime numbers")

Are you sure about this one ? :wink:

I presume that it’s a power display issue and not your code.

:slight_smile: that was a typo, I updated it, thanks

So this keep getting better, thanks top-level-statements. A student (adult + children) will start with BP Language to write code with no decorator… then move to decorators… then move to VS and use top-level-statements and then finally move to OO coding.

This is just FANTASTIC!! Working with hundreds of students, I wish I had this for the last 5 years!!! NO BLOCKS, no scratch, no makecode, PLEASE

// 1
Print "BrainPad"

// 2
Print("BrainPad");

// 3 - Start using VisualStudio with top-line statements
using GHIElectronics.TinyCLR.BrainPad
BrainPad.Print("BrainPad");

// 4 - Use VS like a pro
using GHIElectronics.TinyCLR.BrainPad
class Program{
    static void Main(){
        BrainPad.Print("BrainPad");
    }
}
1 Like

IMHO, the key to better teaching of programming is not the syntax of a language but to build a programming “mindset”.

I have taught many programming courses, and have seen the students understand the syntax of a language, and understand how loops work, but when it comes time to build a program they struggle where to start.

Eliminating brackets will be of little help if the student is unable to “think like a programmer”

How do we teach students to think like a programmer? My wife might think this is a disservice to society.:slight_smile:

2 Likes

I disagree very much. I have also spent a lot of time trying. There are people, like you, are born to code. The goal here is to give a below-average person a chance by making the first few steps easier to take. “Public static void” has no coding value whatsoever. I want to teach you what a variable is first, without introducing any other “ignore these for now”.

Trying to teach, I have quickly learned that I have forgotten how much I know and how much I have to teach.

Here is an example

x=5
Print x+1

How is easy is there code above? I have had many instances where a student expected it to show x+1 or show 5+1. Now take that average student and add “public static”, add main, add using…etc and they will be completely lost and MOST IMPORTANTLY they would lose interest.

In summary, people that really want to code do not need us, they have Google and YouTube. We are doing this for everyone else.

By the way, happy holidays to you and everyone else.

2 Likes

I would tend to agree with Gus, here.

My feeling is that nowadays we learn a programming language and not how to become a programmer.

I would then try to start at the same point as it all started some years ago with ZX81, Oric and others : a very simple basic without any curlicue and as simple as it can be.

Granted, we may have to add some special instructions for graphics, I/Os or special devices, but the foundation would be/should be a very simple language, so that we only have to think on the algorithm and not the language arcanas.

3 Likes

Who are you agreeing with, Gus or Me?

I believe Gus is targeting those who have a natural talent for programming, and is trying to ease the entry into that world.

I believe everyone should have an exposure to programming, in order to better understand the technological world around us. That is my reason for teaching “think like a programmer”.

Actually, agreement is not necessary, We are both right. :slight_smile:

3 Likes

Agreement not necessary but still, I say that I do agree with you as well (on both of your posts).

That said, and regardless of arguments from everyone, I think that programming is not something anybody could learn, regardless of the language used.
Programming needs some abilities or skills that may be missing to some people. I would say the same for painting, philosophy or music.

But sometimes, those abilities may already exist and would be revealed by a very easy learning curve.
Perhaps that it’s what everybody here is already saying ? :wink:

3 Likes

I think the sentiment is the same across the board, there is a need for an environment with a lower barrier to entry for the beginner.

I do think that the language should forgo line numbers and “GOTO/GOSUB/RETURN” in favor of functions, as long as the language supports top-level statements. That way, functions can be taught incrementally, and the cognitive overhead is not much more than understanding “GOSUB/RETURN”.

As functions are introduced, the student can still assume global variables, as they would with “GOSUB/RETURN” and then progress to understanding function arguments, return values and scoping.

As for curly braces, I do not have a strong opinion here, the only reason the current interpreter uses curly braces is because they require fewer tokens and therefore less code to parse assuming explicit statement block termination using something like “END WHILE”, “END IF”, “END FOR” etc. but easy enough to change.

Ideally, I believe we should avoid the need to introduce semi-colons :slight_smile:

I know Gus did not want arrays, but arrays open so many more options I just could not resist :).

Array elements can be any type, including other arrays, so you can create jagged arrays as well.

I wanted to try an experiment with some syntax around arrays and allow the ‘+’ operator append to the array either at the beginning or at the end.

For example

// Create an array with 2 items
var fruit = ["apples", "oranges"]
println(fruit)

// Add an item to the end of the array
fruit = fruit + "bananas"
println(fruit)

// Add an item to the beginning of the array
fruit ="peaches" + fruit 
println(fruit)

// Show elements of the array
println(fruit[2])           
println(left(fruit, 2))     
println(right(fruit, 2)) 
println(mid(fruit, 1, 2))
println("We have ", len(fruit), " types of fruit")

The output from the above is

[apples,oranges]
[apples,oranges,bananas]
[peaches,apples,oranges,bananas]
oranges
[peaches,apples]
[oranges,bananas]
[apples,oranges]
We have 4 types of fruit
4 Likes

Is it
We have 4 pieces of fruit
Or is it
We have 4 types of fruit

:thinking:

1 Like

That is great to have. My thinking is if a user is at a point where they need arrays then they should switch to C#. I could be wrong here so I am happy to see arrays.

I am going to use the excuse that I did this at 3am… mmm, maybe I should go review the code I wrote as well, but it seemed awesome at the time :slight_smile:

And by the magic of the internet all errors are erased :slight_smile:

Bwhahahhaha :rofl: