The Latte programming language

Latte is an imperative language, almost a subset of Java and can be easily translated to it.

This description is intentionally imprecise and example-based; refining the specification is part of the task. A grammar of the base language is available in the BNFC format.

Test program tarball:

lattests121017.tgz z 17.10.2012, MD5:49ca5702ca9795fb8f33d52b0b3c6fc3

Example: Hello world

// Hello world 

int main () {
  printString("hello world") ;
  return 0 ;
}

Example: print even numbers below 10

// print even numbers below 10

int main () {
  int i ;
  i = 0 ;
  while (i < 10){
    if (i % 2 == 0) printInt(i) ; 
    i++ ;
  }
  printInt(i) ;
  return 0 ;
}

Example: factorial in two ways

int main () {
  printInt(fact(7)) ;
  printInt(factr(7)) ;
  return 0 ;
}

// iterative
int fact (int n) {
  int i,r ;
  i = 1 ;
  r = 1 ;
  while (i < n+1) {
    r = r * i ;
    i++ ;
  }
  return r ;
}

// recursive
int factr (int n) {
  if (n < 2) 
    return 1 ;
  else 
    return (n * factr(n-1)) ; 
}

Program structure

A Latte program is a sequence of function definitions. A function definition has a value type, a name, an argument list, and a body consisting of statements.

Names in function definitions must be different.

One function must have the name main. Its value type must be int and its argument list empty: 

  int main () { ... } ;

All functions should return a value of their value type. Void functions without return statements are allowed.

Functions can be mutually recursive, i.e. call each other. 

Program.   Program ::= [TopDef] ;
FnDef.	   TopDef ::= Type Ident "(" [Arg] ")" Block ;
separator nonempty TopDef "" ;
Arg. 	   Arg ::= Type Ident;
separator  Arg "," ;

Statements

Statements: empty,sequence,if,while,return as in C/Java. We also consider statements: assignment, postincrementation, postdecrementation (in the base version only variables are l-values).

Variable declarations can occur at any point in a block, however each variable must be declared before it is used. If a declaration has no initializer, declared variable is to be initialized with a default value (0 for int, "" for string, false for bool).

Variables declared in a block statement are not usable outside the block. They overshadow variables that come from outside. Otherwise, a variable can only be declared once in the same block. 

Block.     Block ::= "{" [Stmt] "}" ;
separator  Stmt "" ;
Empty.     Stmt ::= ";" ;
BStmt.     Stmt ::= Block ;
Decl.      Stmt ::= Type [Item] ";" ;
NoInit.    Item ::= Ident ;
Init.      Item ::= Ident "=" Expr ;
separator nonempty Item "," ;
Ass.       Stmt ::= Ident "=" Expr  ";" ;
Incr.      Stmt ::= Ident "++"  ";" ;
Decr.      Stmt ::= Ident "--"  ";" ;
Ret.       Stmt ::= "return" Expr ";" ;
VRet.      Stmt ::= "return" ";" ;
Cond.      Stmt ::= "if" "(" Expr ")" Stmt  ;
CondElse.  Stmt ::= "if" "(" Expr ")" Stmt "else" Stmt  ;
While.     Stmt ::= "while" "(" Expr ")" Stmt ;
SExp.      Stmt ::= Expr  ";" ;

Types

Types int,boolean,void as in Java; string corresponds to Java String. There are no conversions between types. Introducing implicit type conversions will be treated as an error, rather than a language extension.

For context analysis it may be helpful to interoduce function types internally. 

Int.       Type ::= "int" ;
Str.       Type ::= "string" ;
Bool.      Type ::= "boolean" ;
Void.      Type ::= "void" ;
internal   Fun. Type ::= Type "(" [Type] ")" ;
separator  Type "," ;

Expressions

A subset of Java expressions: 
EVar.      Expr6 ::= Ident ;
ELitInt.   Expr6 ::= Integer ;
ELitTrue.  Expr6 ::= "true" ;
ELitFalse. Expr6 ::= "false" ;
EApp.      Expr6 ::= Ident "(" [Expr] ")" ;
EString.   Expr6 ::= String ;
Neg.       Expr5 ::= "-" Expr6 ;
Not.       Expr5 ::= "!" Expr6 ;
EMul.      Expr4 ::= Expr4 MulOp Expr5 ;
EAdd.      Expr3 ::= Expr3 AddOp Expr4 ;
ERel.      Expr2 ::= Expr2 RelOp Expr3 ;
EAnd.      Expr1 ::= Expr2 "&&" Expr1 ;
EOr.       Expr ::= Expr1 "||" Expr ;

Logical expressions have value of type boolean and are computed lazily (the second argument is not evaluated if the first determines the value of the whole).

Strings

Strings similarly to Java, i.e. variables of type string contain a reference to a heap allocated string of characters.

Strings can occur as: literals, values of variables, function arguments and results.

Strings can be arguments of a predefined function printString

Strings can be concatenated using the operator +; the result is a new string.

Predefined functions

The following predefined functions are available: 
void printInt(int)
void printString(string)
void error()
int readInt()
string readString()

error prints out runtime error and halts the program.

readString reads one line of input and returns it as a string.

Function arguments

All arguments are passed by value (note that strings are represented as references,also passed by value). Within the function, arguments are treated as local variables, i.e. assignments to them are allowed.

Latte and Java

Core Latte can be easily translated to Java by wrapping all functions in a class as public static methods. The main method has to be given another type signature. Translating nested blocks (and some of the extensions) may require some thought.

Extensions

Note: credit for extensions is only given in the stage III (LLVM/x86 backend).

Arrays and for-loops

Arrays as in Java, i.e. variables of an array type contain a reference to a heap-allocated array. Arrays are created explicitly, using the operator new. Arrays have a predefined attribute length (e.g. a.length)

Array declaration examples


  int[] a;
  string[] b;
Arrays can (but need not) be created at declaration time: 

  a = new int[20];
  int[] c = new int[30];
Functions can be passed arrays as arguments and yield them as results: 

int[] sum (int[] a, int[] b) {
  int[] res = new int [a.length];
  int i = 0;

  while (i < a.length) {
    res[i] = a[i] + b[i];
    i++;
  }
  return res;
}

Within the scope of this extension, a simple version of the foreach should be implemented: 


    for (int x : a) 
     printInt(x);
Tests for this extension can be found in extensions/arrays1.

Structures

A basic form of objects, with attributes only (no methods or inheritance). Variables of structure types contain reference to heap allocated objects. Assignment is reference assignment; similarly structures can be used as arguments and results are allowed and to be understood as passing refernces (this refers also to other object extensions). 


class list {
  int elem;
  list next;
}

int main() {
  printInt(length(fromTo(1,50)));
  printInt(length2(fromTo(1,100)));
}

int head (list xs) {
  return xs . elem;
}
 
list cons (int x, list xs) {
  list n;
  n = new list;
  n.elem = x;
  n.next = xs;
  return n;
}

int length (list xs) {
  if (xs==(list)null)
    return 0;
  else
    return 1 + length (xs.next);
}

list fromTo (int m, int n) {
  if (m>n)
    return (list)null;
  else 
    return cons (m,fromTo (m+1,n));
}

int length2 (list xs) {
  int res = 0;
  while (xs != (list)null) {
    res++;
    xs = xs.next;
  }
  return res;
}
Tests for this extension can be found in extensions/struct.

Objects

Classes and objects, with methods and single inheritance (without method override).

Sample class: 


  int main () {
  Counter c;
  c = new Counter;
  c.incr();
  c.incr();
  c.incr();
  int x = c.value();
  printInt(x);
  return 0;
}

class Counter {
  int val;

  void incr () {val++; return;}
  int value () {return val;}
}

Inheritance example: 


class Point2 {
  int x;
  int y;

  void move (int dx, int dy) {
     x = x + dx;
     y = y + dy;
  }

  int getX () { return x; }

  int getY () { return y; }
}

class Point3 extends Point2 {
  int z;

  void moveZ (int dz) {
    z = z + dz;
  }

  int getZ () { return z; }
}

class Point4 extends Point3 {
  int w;

  void moveW (int dw) {
    w = w + dw;
  }

  int getW () { return w; }
}

int main () {
  Point2 p = new Point3;
  Point3 q = new Point3;
  Point4 r = new Point4;

  q.move(2,4);
  q.moveZ(7);
  p = q;

  p.move(3,5);
 
  r.move(1,3);
  r.moveZ(6);
  r.moveW(2);

  printInt(p.getX());  
  printInt(p.getY());  
  printInt(q.getZ());  
  printInt(r.getW());
  return 0;
}
Tests for this extension can be found in extensions/objects1.

Virtual methods

The limitation of the previous extension, forbidding method override, makes real OO programming impossible. Hence, this extension should implement method override, treating all methods as virtual (as in Smalltalk).

Example: 


  class Node {
  Shape elem;
  Node next;

  void setElem(Shape c) { elem = c; }

  void setNext(Node n) { next = n; }

  Shape getElem() { return elem; }

  Node getNext() { return next; }
}

class Stack {
  Node head;

  void push(Shape c) {
    Node newHead = new Node;
    newHead.setElem(c);
    newHead.setNext(head);
    head = newHead;
  }

  boolean isEmpty() {
    return head==(Node)null;
  }

  Shape top() {
    return head.getElem();
  }

  void pop() {
    head = head.getNext();
  }
}

class Shape {
  void tell () {
    printString("I'm a shape");
  }

  void tellAgain() {
     printString("I'm just a shape");
  }
}

class Rectangle extends Shape {
  void tellAgain() {
    printString("I'm really a rectangle");
  }
}

class Circle extends Shape {
  void tellAgain() {
    printString("I'm really a circle");
  }
}

class Square extends Rectangle {
  void tellAgain() {
    printString("I'm really a square");
  }
}

int main() {
  Stack stk = new Stack;
  Shape s = new Shape;
  stk.push(s);
  s = new Rectangle;
  stk.push(s);
  s = new Square;
  stk.push(s);
  s = new Circle;
  stk.push(s);
  while (!stk.isEmpty()) {
    s = stk.top();
    s.tell();
    s.tellAgain();
    stk.pop();
  }
  return 0;
}

Garbage collection

This extension does not change syntax (or to some extent, semantics) of the language, but enhances memory management by releasing unreachable strings. It's enough to implement a simple, reference counting collector.