ScarLang

This project contains a minimal functional programming language called ScarLang, implemented in C++. ScarLang is just a funky name I thought of while listening to the best game soundtrack of all time, 東方紅魔郷 〜 the Embodiment of Scarlet Devil.

Runtime system (C)

The runtime system is implemented in C. Gcc statically links to it for the final executable. This runtime system is a minimal virtual machine for the SCRLAM abstract machine.

Grammar

Prog         = { TopDecl Seperator }
TopDecl      = FunctionDecl | Comment | DataDecl
DataDecl     = "data" Identifier "=" Constructor { "|" Constructor }
Constructor  = Identifier { Identifier }
Comment      = "--" { anyCharExceptNewline } "\n"
               | "--[" { anyChar } "]--"
FunctionDecl = Identifier { Identifier } "=" Expr
               (* supports curried functions: f x y = ... *)
               
Expr         = LetExpr
               | IfExpr
               | LambdaExpr
               | CaseExpr
               | InfixExpr  (* implicitally defines function application and atomics *)

LetExpr      = "let" FunctionDecl { Seperator FunctionDecl } "in" Expr
IfExpr       = "if" Expr "then" Expr "else" Expr
LambdaExpr   = LambdaKw { Identifier } "->" Expr
LambdaKw     = "\" | "laevatein"

CaseExpr     = "case" Expr "of" { Pattern "->" Expr }
InfixExpr    = AppExpr { BinaryOp AppExpr }
AppExpr      = AtomicExpr { AtomicExpr }
                (* function application by juxtaposition *)

AtomicExpr   = Identifier
               | Literal
               | Pack{Num, Num} (* Constructor *)
               | "(" Expr ")"

(* Might be out of scope, so initially will only support simple constructor patterns *)
Pattern      = Identifier
               | Literal
               | "_" 
               | Constructor { Pattern }

Literal      = num | String
Num          = digit { digit } [ "." digit { digit } ]
String       = "\"" { anyCharExceptQuote } "\""
Identifier   = letter { letter | digit | "_" }
Seperator    = "\n" | ";" | EOF
BinaryOp     = ArithmeticOp | ComparisonOp | LogicalOp | CustomOp
ArithmeticOp = "+" | "-" | "*" | "/" | "%" | "^" | "^^" | "**"
ComparisonOp = "==" | "!=" | "<" | ">" | "<=" | ">="
LogicalOp    = "&&" | "||"
CustomOp     = "$" | "!!" | "."  (* function application, get element at index, function composition *)

Note that not all features of this grammar may be implemented in the initial version of ScarLang, but this serves as a roadmap for future development. Maybe guards and where clauses will be supported in the future.

Operator precedence and associativity (from highest to lowest):

Precedence	Operators	Description	Associativity
9	f x	Function application	Left
8	.	Function composition	Right
8	!!	Get Element at Index	Left
7	^ ^^ **	Exponentiation	Right
6	* / %		Left
5	+ -		Left
4	++ :	List concatenation	Right
3	== != < > <= >=	Comparison	Non-associative
2	&&	Logical AND	Right
1	||	Logical OR	Right
0	$		Right
Pretty much the same precedence as Haskell, except monadic operators like >>= and >> and functor operators like <*> and <$> are not included in ScarLang.
There is no explicit operator for negation; instead, it is defined as a function: negate x.

Notes and limitations

Currently, there is no elaboration phase. This means that it is possible to write incorrect code, compile it (without error), but when executing it, it will produce undefined results. For example, the following code will compile without error, but will produce undefined results when executed:

main = add 1 2 3

This is because add is a function that takes two arguments, but in this case, it is being called with three arguments. The compiler does not check for this, and simply treats add 1 2 3 as the application of the function add to the arguments 1, 2, and 3, and asumes that the arity of add is 3, which is not the case.

There is also a severe lack of desugaring. If I ever have time, I will add proper code sugar to the language (which the grammar allows for). The priority of this project has been compiling a lazy language to machine code.

ScarLang is supposed to be statically typed (similar to Haskell), but currently there is no type inference or type checking implemented. This means that it is possible to write code that is not type safe, and the compiler will not catch it. The compiler assumes you write type safe code, and will produce undefined results if you do not.

For now, the abstract machine does not support garbage collection, nor does it optimize arithmetic using a V-stack. This may be implemented later, but for the purpose of this research it would add a lot of complexity.

Proper support for characters (and strings through proper support for lists) is also not implemented, but may be added in the future. A majority of list support is code sugar, and as stated before, there is a severe lack of desugaring in the current implementation of ScarLang, so this is not a priority at the moment.