Index: Home     | What Is Izumi | Misc Links   | Random Thoughts | Too Much To Read | The Rant Vault | Quotes
Dev:   Projects | Ideas For Dev | Nerdkill | Rig | Hint

$Id: MiniHint.izu,v 1.6 2005/11/05 21:55:57 ralf Exp $

0. Deprecated Project Notice

20050122 Warning: This project is indefinitely put on hold.

1. Introduction

1.1. Goal

20041221

There is no goal yet. The project is not formaly specified yet. This page exists only because I needed a place to write down some notes. So please read the notes below if you wish but don't expect too much. The whole thing may never happen, or it may swing in totally different direction.

1.2. Description

1.3. Milestones

20041221

Milestones are not available yet.

2. Plan

2.1. Initial prototype

To be done (by decreasing priority):

2004MMDD [1.N] Section: Desc

Finished (by decreasing date):

20041106 [1.F] Test: Switching from CSTools to Coco/R C#
20041024 [1.F] Test: Compiling CSTools
20041024 [1.F] Test: Skeleton Project

2.2. Milestone 1

2.3. Milestone 2

3. Notes

(Notes are given in chronological order.)

The main objective is to write down a tentative grammar for CocoR. The parser will generate an abstract tree, directly suitable for executation by a stack machine.

The main lines of the language are:

• As close as possible to classical syntaxes such as Java and JavaScript
• Line ending serve as implicit statement separators (will be cumbersome later)
• As few specific symbols as possible, namely parenthesis and dash should be enough.
• Named functions first. Anonymous functions will come later.
• Functions should be able to take either typed or untyped arguments. Start with untyped.
• Implicit blocks after a keyword are terminated by "end" keyword (aka if, etc.)

Classic parsers that generate compilers process one full syntactic unit, such as one C# file for example. I can start with this but it is not the ultimate goal and will be annoying later. What I want ultimately is have a line-oriented IDE for a PDA. Edit one line and process it on the fly, generating its tree.

It is actually easier than it seems to handle that. If the parser does not have to deal with a complete unit, it merely needs to process input as a list of statements. Once the abstract tree is built, a quick analysis can determine if the unit is valid -- the same that would need to happen at runtime anyway.

It thus then becomes possible to process full units or to have an IDE process a single line statement and maintain the tree.

One way to deal with this is to keep a tokenized version of the line in the IDE. Think Basic editors that reformat on the fly and indicate errors at the same time the line is typed. This is often annoying when editing though if the editor reformats the line or pops up error messages -- on the other hand it can be done without disturbing the user. Also the tokenized version of a line may need to maintain information about white spaces.

A simpler approach is just to store the line as text and only provide an auto-indentation facility. Aside the text line the corresponding abstract tree must be stored (or at least a pointer onto the main tree.) and if possible each identifier in the tree must retain token information (at least the column at which the token started so that errors can be pointed out -- line information can be inferred and needs not be stored.)

So the parser definition may look something like this:

Program = { statement line } .

Statement = declaration | instruction .

Declaration = module | class | function | var .

Instruction = expression | if | while | for | return | end . 

Module = "module" namespace .

Class = "class" ident .

Namespace = ident { "." Ident } .

Function = "function" ident [ params ] .

Params = Weak "-" { [type] name } .

Var = Weak "var" namespace [ ident ] "=" expression .

	// Semantic: ident is optional if namespace has no dot. It becomes the ident.

List = "(" [ expr | { , } ] { , expr { , } } ")" .

Expression = arith | new | fun.

Arith = (same order and functionnality than JavaScript)
	// Operands: + - * / % mod and or xor (logical) & | ^ (bits) << >> ! ~

New = "new" namespace [ list ] .

Fun = "fun" [ params ] "-" block .

	// Semantic: this is an anonymous function. Note the confusion about line separators.

If = "if" expression line block

Block = { statement line } "end"

While = "while" expression line block 

For = "for" expression [ "-" expression [ "-" expression ] ] line block .
Return = "return" expression .
Literal = string | number | boolean .
Number = integer | double | hexa .
Boolean = "true" or "false" .

Now there are a couple of problems here:

• The anonymous function cannot be all declared on one line and at the same time use line terminators to delimit inner statemetns. It would be cumbersome to force the user to have to split a simple function into several lines because that's what the grammar requires when it could have been so simple as being elegantly expressed as one-liner.
• Ideally the new expression should accept an expression and not a namespace as second argument. Ideally I'd like to be able to write a function that returns a class name to be instantiated by new.

The grammar of course does a poor job at explaining semantics and overall behavior.

Ideally the ultimate goal is to have something that is prototype-based and that allows supple redefinitions are runtime. The language should be weakly typed, that is types can be ommited and infered or explicitly described. Yet for a first milestone, that's too much.

So the basic behavior could be something like that:

• Milestone 1:
• A simple procedural language.
• No anonymous functions.
• No class redefinition and overloading at runtime.
• Intrisinc operations for basic operations.
• No operator overloading.
• A basic stack-based interpreter.
• Following Milestones, as it comes:
• Everything is a function.
• Scoping.
• Operator overloading.
• Anonymous functions.
• Manipulation of partial functions and class objects.
• Lazy evaluation.
• Closure.
• Stream oriented execution.

Note that there are not too many specifics at that point. The idea is to start with something simple -- let's say common. Things that are easy to add, such as operator overloading, will be done next.

Scoping in the first prototype will be standard: intrinsic functions, modules, classes, functions and blocks, in that order. Every intrinsinc things are going to be stored in the global Hint namespace.

There should be a default mechanism to access the host functionnality. Since the prototype will be coded in C#, it makes sense to provide access to the .Net Framework, that is:

• Classes from the framework can be instantiated, for example by accessing then thru a global DotNet namespace (aka DotNet.System.IO.Path...)
• Arguments must be matched accordingly. That is the basic data types used by Hint will be the ones from the CLR (string, int, etc.)

Note that I haven't introduced the notion of a "using" or "import" statement yet in the grammar. I'll see as it goes.

Execution will be done by a standard stack-based interpreter. Ideally some elements of lazy evaluation and closures could be used in the implementation of the interpreter.

The interpreter will directly act on the tree generated by the parser. One possible data structure for this tree:

• Node interface
• Literal: a terminal, such as a string or integer.
• FCall: operand, arguments (nodes)

To be continued.

Defining the syntax and parsing it is only one part of defining the language. Since the language is going to be interpreted, the other obvious important part is the definition of the interpreter, or more exactly the way it will work which will influence how the language is used.

Things I rougthly have in mind:

• Stack based machine.
• Directly uses the tree generated by the parser as instruction list.
• Pro: Easy to implement, no need to convert to byte code and interpret that byte code. No new byte code and binary format needed.
• Cons: Requires more memory than a nicely packed array of bytes.
• Solution: Simply start with the node tree, eventually simply find a way to dump the node tree as bytes -- some kind of serialization mechanism that does not involve deserializing, i.e. the interpreter could use both.
• Treat every data type as an object.
• It would be easier to start with a number of integral data types, such as integer, floats, doubles and strings.
• OTOH sooner or later I will need boxing mechanisms. Boxing is expensive yet more convenient.
• Bottom line: it is more elegant to treat all data types the same way, yet it is more efficient to be able to deal with integers and such directly.
• The ideal future direction is to have objects defined with slots. Some slots will be reserved named, such as _type, _parent (for inheritance)

and _prototype.

• It would be convenient to use this mechanism since the very beginning even if I don't expose it. Integral parts could thus be described as-is in the node tree and as pseudo-objects on the stack with optimizations to deal with them.
• Treat every instruction as a generic function call.
• This is somehow linked to the previous topic and the idea of operator overloading.
• Same as before, I could start with a generic treatment and then add some specific optimizations for operations on integral data types.

I was struggling on how to implement the parser. Defining the grammar is not difficult (although there are still some details that are sketchy to say the less) yet I wanted to start implementing it and I couldn't find what I wanted:

• A classic parser that parses one full "compilation unit", i.e. one full source for a given class.
• A parser I can include in the test IDE and which would be line-oriented.

Let me explain the latter one: to test the language I want a minimal PocketPC editor. It's actually more an IDE in the sense that I want something similar to the old Basic editors where each line is tokenized on the fly. So rather than write a "full parser" then later a tokenizer for the IDE I'd rather write something that can parse one single line of the program. The problem when I do that is that I can't get a grammar that validates a full source file.

It just struck me I was wrong. I can get both with a trick.

A full source file must contain:

• One module definition (a block "module .... end").
• At least one class definition (a block "class ... end") within that module.
• A class definition contains functions and variables definitions.
• Statements can only appear within a function definition.

So what I just need is one grammar which first production can be either one statement or one module. Then it is a semantic error to parse one single statement when parsing a single source line.

The output of the parsing will be the abstract execution tree.

This has the advantage that I can do "partial recompilation" on the fly in the IDE but just parsing those lines that have been edited and merging the resulting tree where needed. This implies the IDE must keep track of which source lines produced which sub-tree. When processing a full file, the parser will need to keep that information around for the IDE to use.

Here's a stupid idea: implement this in Python rather than C#. Let's see:

• Performances will be pathetic. Python is interpreted and although the interpreters are quite good, it's still interpreted. C#/CLR may not be the fastest choice either but it's still better speed-wise. Speed is not an issue at all right now yet as soon as I want this to do something useful it will become one.
• That would imply using win32gui (i.e. low Win32 calls) to build any kind of UI rather than using the .Net Windows.Form classes.

So overall it's a poor choice although on some other level it is an interesting one. From an academic point of view let's say.

Speaking of Python, why not using its "identation defines block" way?

On another unrelated note, the syntax should be as flexible as possible:

• Using lex/yacc or even Coco/R is a mistake.
• I can get away with the lexer part by splitting on whitespace and using regexps to identify lexems.
• The grammar should not be hardcoded. It should be encoded using embedded rules that can be overriden later. Same for keywords. This was the original Hint idea and is still what makes more sense for me.
• There's still a need to provide an easy way to perform "local" parsing (of a line) versus unit parsing (for a whole unit file.)

Site License

This work is licensed by Raphaël Moll under a Creative Commons License.

Options

Color Theme:	Gray  | Blue  | Black | Sand  | Khaki  | Egg  | None

Web ralf.alfray.com

Display Izumi & PHP Credits

Stats

502 accesses, 1 access from 38.107.179.209
Visited 8 times by Google, last 2012/03/16 10:44
Visited 12 times by Yahoo!, last 2011/10/14 05:41
Visited 1 times by MSN, last 2011/05/28 02:04

< Generated in 0.47 seconds the 05/20/2012, 07:15 AM by Izumi 1.1.4 >