An update

It’s high time for an update!

Most of the fundamentals have been implemented. Development has been proceeding slowly because I’ve been wrestling with a challenging problem: how should arrays, structures, and other such data types be passed to—and returned from—subroutines in a clean and consistent way? I think that, ideally, we should be able to write code that looks a bit like this:

person.name$ = "Foo Barbaz"
person.dob.year = 1983
person.dob.month = 10
person.dob.day = 5

printDetails (person)   // how should the contents of "person" be passed?

sub printDetails (p)
   print p.name$ + " was born on " \
            + str$ (p.dob.year) + "/" \
            + str$ (p.dob.month) + "/" \
            + str$ (p.dob.day) + "."
end sub

I think I’ve finally figured out how to solve this problem in an elegant way. I plan to implement tables (which are pretty much equivalent to associative arrays) that will be able to contain values (real numbers, character strings, and—importantly—references to other tables) identified by arbitrary keys (integers and character strings). To ensure that tables can be used as structures, a.b will be treated as syntactic sugar for a("b") and subroutines will be able to take references to tables as arguments (for instance, test (a)).

For maximum speed, I plan to implement tables using a composite structure containing both an array part (for values identified by integer keys within a particular range) and a crit-bit trie part (for values identified by any other keys), but the underlying implementation will be abstracted and hidden at the user level.

Seventh development version

I’ve finally managed to implement subroutines! I expected this task to be the greatest obstacle to development progress, and it didn’t turn out to be so bad after all—indeed, structures (and modules) are looking more daunting now. A bit of polishing still remains: local variables are implemented, but static variables aren’t yet; subroutines can’t take either array or scalar references as parameters, nor can they return references to arrays or scalars; and I’m sure there are plenty of bugs that I haven’t managed to iron out yet.

If you can, please download (tar.gz, zip) and test the seventh development version, and report any bugs that you find! Thanks in advance. :-)

What’s new?

  • Subroutines:
    hello ("Tom")
    
    sub hello (name$)
       print "Hello, " + name$ + "!"
    end sub
  • Local variables:
    a = 1
    print a
    test ()
    print a
    
    sub test ()
       print a
       local a = 2
       print a
    end sub
  • A FREE command:
    dim array[100]
    array[50] = 1
    free array
  • Multiple assignments per line:
    a = 1, b = 2, c = 3
  • And a few other little things.

Here are a couple of really rough benchmarks.

// subroutine calling
for call = 1 to 1000000
   test (1, 2, 3)
   test (call, call + 1, call + 2)
next

sub test (a, b, c)
   return a + b + c
end sub

(On my machine: 3.965 seconds in Yabasic 2.763, 0.530 seconds in Yabasic 3.)

// recursive subroutine

test (100000)

sub test (a)
   if a test (a - 1)
end sub

(On my machine: 0.206 seconds in Yabasic 2.763, 0.022 seconds in Yabasic 3.)

Yet another development version

Here’s a new development release! If you can, please download it (tar.gz, zip), compile it, and test it. This version features arrays (currently with square brackets, just to ease the process of implementing functions—don’t panic!) and various other improvements. It’s entirely memory-clean, and—dare I say it—pretty fast. ;-)
Read more »

Another development version

I’ve been continuing to experiment with the register-based virtual machine model I told you folks about earlier. Here’s an updated development version of Yabasic: tar.gz, zip. I repeat, it’s a development version. (You’ll get a few compile-time warnings: don’t worry about them, everything will be cleaned up in the end.) Things are coming along nicely; last night and this morning, for instance, I implemented IF statements, FOR loops, INPUT, and several functions. The basics are pretty much done—arrays/structures, subroutines, modules, and a few more complicated functions are all that remain to be completed, really.

I’m really excited about two things. The first is that this version of Yabasic is completely memory-clean: that means there are no memory leaks, and all memory is freed before the interpreter exits. The second is that this version is remarkably fast in comparison to, say, Yabasic 2.763. For example, the following loop:

for a = 1 to 10000000
next

takes 1.5 seconds to execute in Yabasic 2.763 and around 0.4 seconds to execute in this experimental version. That’s a pretty decent increase in speed, if I do say so myself. ;-) In pretty much every other benchmark that I’ve done, this version—with its register-based virtual machine model—has outperformed Yabasic 2.763 substantially, and I think it’s looking very promising.

Here’s a (rather inefficient) program that finds prime numbers:

limit = 10000

for number = 2 to limit
   prime = true
   for check = 2 to int (sqrt (number))
      if not (number mod check) then
         prime = false
      endif
   next

   if prime then
      print number
   endif
next

Have fun, and please report any bugs that you find! :-D

“Registers” vs. stacks

Many interpreters use an internal stack to keep track of values. For example,

print "Hello, " + "world!"

would typically be represented internally as

cPushString "Hello, "
cPushString "world!"
cConcatenate
cPrint

This is pretty self-explanatory: the string “Hello, ” is pushed onto the interpreter’s stack, followed by the string “world!”; then the two strings are popped off the stack, concatenated (joined together), and the result is pushed back onto the stack; and, finally, the value at the top of the stack is output.

This would be all well and good if pushing onto and popping off the stack were cheap operations. And, with a good stack implementation, they are remarkably cheap. But the number of pushes and pops in an average program tends to be high, with the unfortunate consequence that stack overhead is quite noticeable.

There is another less commonly used model that involves using virtual fixed registers to record values internally. Under a register-based implementation, we might re-write the program above as

cStoreString r1 "Hello, "
cStoreString r2 "world!"
cConcatenate r3 r1 r2
cPrint r3

This stores the string “Hello, ” in register 1, stores the string “world!” in register 2, and then concatenates the strings in registers 1 and 2, storing the result in register 3, which is then outputted. In this model, there is no stack overhead, because the interpreter already knows exactly where to store values.

Yesterday I wrote an experimental version of Yabasic—a very experimental version—that uses a virtual register machine rather than a virtual stack machine. As an unusual twist, commands are registers, so we have

1 cConstantString "Hello, "
2 cConstantString "world!"
3 cConcatenate 1 2
4 cPrint 3

The results are pretty promising. On my computer,

a = 0

while (a < 10000000)
   a = a + 1
wend

runs in around 0.4 seconds under the new implementation. Under Yabasic 2.9.16, the same program takes around 0.9 seconds to run. Under Yabasic 2.763, the program runs in about 1.1 seconds.

And, you know, it really wasn’t all that hard to make the register-based version of Yabasic. It’s still really incomplete at the moment, but so far there’s been very little of the fiddling I was afraid of.

Check it out: Yabasic-3-experimental2.

Yabasic 3 progress update

Yabasic 3 development is now underway! Pedro will be implementing the abstract syntax tree, Jacob will be working on the symbol management routines (that will handle variables and subroutines), and I’ll be focusing on the parser, lexer, and the backbone of the interpreter. Because there are now three people working on Yabasic 3, we plan to use a Git version control repository hosted on GitHub—there’s already some code up there, but it’s not functional yet.

Personally, I hope to get a substantial amount of work done on Yabasic in the next week or so; we’ll see whether that works out or not. ;-) Thanks to all you Yabasic users out there for your patience!

Here’s to Yabasic 3…

Variables in Yabasic 3

Variables can identify two types of values: real numbers (no suffix appended to variable name) and character strings (“$” suffix appended).

Variables in action:

pi = 3.1416
name$ = "Bob"

Scalars

Scalars are variables that can hold only one value:

town$ = "Tinyville"
population = 100

Scalars need not be declared prior to use, but note that an error will be reported if a program tries to access a scalar variable that has not previously been assigned a value.

Arrays

Arrays are variables that can hold more than one value:

town$ (1) = "Randomville"
population (1) = 30000
town$ (2) = "Somewhereton"
population (2) = 20000

Arrays can have any number of dimensions.

The position of an element in an array is specified using indices. Given an index n, an upper bound b, and assuming that n and b are both members of the set of integers, 0 must be less than or equal to n, and n in turn must be less than or equal to b.

Arrays need not be declared prior to use, but note that an error will be reported if a program tries to access an array element that has not previously been assigned a value.

Structures and user-defined types

User-defined types (UDTs) are “templates” for structures. They can be built out of scalars, arrays, and structures.

Structures can be explicitly created:

struct some_structure
   some_component
end struct

or made from UDTs:

type some_type
   some_component
end type

struct some_structure_1 as some_type
struct some_structure_2 as some_type

For example:

type crate
   name$
   apples
   oranges
   pears
end type

struct crate (2) as crate

crate (1).name$ = "CR001"
crate (1).apples = 30
crate (1).oranges = 50
crate (1).pears = 40

crate (2).name$ = "CR002"
crate (2).apples = 40
crate (2).oranges = 25
crate (2).pears = 50

Subroutine arguments/parameters

Arguments passed to subroutines are stored in variable parameters:

v (1) = 3
values (1, 2, v ())

sub values (a, b, c ())
   print a, b, c (1)   // output will be "1 2 3"
   return
end sub

Each argument must correspond to a variable parameter, and vice-versa; an error will be reported if too many or too few arguments are passed to a subroutine.

By default, scalar arguments are passed “by value”, and arrays are passed “by reference”; however, the keywords byval and byref can be used to override this:

a = 2
print a   // output will be "2"

assign (a, 7)
print a   // output will be "7"

sub assign (byref scalar, byval value)
   scalar = 7
   return
end sub

Structures can be passed as subroutine arguments:

crate.apples = 30
crate.oranges = 50
crate.pears = 40
count_fruit (crate)

sub count_fruit (crate)
   print crate.apples, "apples"     // output will be "30 apples"
   print crate.oranges, "oranges"   // output will be "50 oranges"
   print crate.pears, "pears"       // output will be "40 pears"
   return
end sub

Global, local, and static variables

(Note: For the purpose of clarification, and in light of some flaws in my own thinking, I have edited this section multiple times.)

By default, variables are “global”; that is, they can be accessed both from within the main program body and from inside subroutines.

Variables inside subroutines can be declared “local”. A local variable can only be accessed from inside its own subroutine; also, a local variable, if one exists, will be always used within a subroutine in preference to a global variable of the same name. For example:

a = 1
print example_1 (), a   // will print "2 2"

a = 1
print example_2 (), a   // will print "2 1"

sub example_1 ()
   a = 2   // changes the value of the global "a"

   return a
end sub

sub example_2 ()
   local a

   a = 2   // changes the value of the local "a", not that of the global "a"

   return a
end sub

By default, a local variable will lose its value when its subroutine returns. A “static” variable is a special form of local variable that keeps its value when the subroutine that it is in returns. For example:

increment_values ()   // output will be "1 2"
increment_values ()   // output will be "2 3"

sub increment_values ()
   static a = 1, b = 2, c () = { 1 }

   print a, b

   return
end sub

Static variables must be assigned an initial value.

Variables in Yabasic 3 (some preliminary ideas, version two)

Working on the basis that it is prudent to release early and often, here’s version two.

A few notes…

  • In light of some of the feedback I’ve received, I think it would be confusing if variables were allowed to “change types” mid-program, so I’ve updated the presentation accordingly.
  • If we kept the “$” suffix for character string variable names, associative arrays might be a little ugly (assuming we use them to implement records): would oranges.name$ become oranges$ ("name") or oranges ("name$")? This isn’t too big an issue, though.
  • I would suggest that both “plain” and “associative” arrays work in the same way from a user’s point of view, but it might be a good idea to detect the difference and represent them differently internally, thus maximising speed?

Thanks to everyone who’s provided feedback so far. Please forgive me if I do not respond to it immediately; I’m very busy, and keeping track of so many posts is hard enough as it is! ;-) But keep the comments and suggestions coming, folks!

Variables in Yabasic 3 (some preliminary ideas)

Hello all!

I’ve been working on some preliminary ideas for variables in Yabasic 3. Here’s a presentation that outlines what I have in mind.

Comments, questions, and suggestions are welcome!

Thanks, Tom.

Welcome, Jacob!

I’m delighted to announce that Jacob Nielsen will be joining us in our endeavour to re-write Yabasic in C++. At this stage, he will probably focus primarily on implementing the symbol-handling class, which will manage variables (including scalars and arrays) and subroutines (to a degree). The symbol-handling class will be one of Yabasic’s core components, and I’m very pleased that we have someone competent (unlike myself) to work on it.

So, Jacob, welcome! It’s great to have you on board.