Skip to content

Fhree is a small strongly typed functional language, it is interpreted and it implements the big-step operational semantics.

License

Notifications You must be signed in to change notification settings

marcoantoniocorallo/Fhree

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

45 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Note: This repo is no longer updated. Trustee is an extension of Fhree, revised and improved.


Fhree

Fhree is a reference implementation of a small strongly and statically typed functional language, it is interpreted and it implements the big-step operational semantics.

It is the result of some excercises for the Languages, Compilers and Interpreters course @ UniPi, and it's an extension of the FUN language shown by Prof. Galletta during the lectures.

The language is strongly inspired by OCaml, with some syntactical differences and simplifications.

The name Fhree is a word pun derived from the original language's name FUN.

Fun probably states for "Functional", but it can also mean "having fun", so the word pun would be "Fun for fun", whose acronym is FFF $\rightarrow$ F3 $\rightarrow$ F Three $\rightarrow$ F(h)ree.


Syntax

Unlike in OCaml, there are no free variables. So there is no let construct but only let-in.

let x = 5 in x

There is a shorthand for this, by means of ;:

let x = 5;

For (also recursive) functions there is a construct let-fun similar to the OCaml's let-rec.

let fun fact n = 
    if n = 0 then 1
    else n * fact (n - 1)
in fact 5

In order to have a strong type system, functions declaration make use of mandatory type annotations.

let fun fact ( n : int ) : int = 
    if n = 0 then 1
    else n * fact (n - 1)
in fact 5

Functions can be used also without declaration, this allows to have both lambdas and recursive lambdas:

5 |> (
    fun fact ( n : int ) : int = 
        if n = 0 then 1
        else n * fact (n - 1)
)
"anon-fun" |> lambda (s : string) : string -> " with annotation"

Type annotations are available also in every other construct, but optionally.


Data Types

Fhree provides the most common data types: integers, floats, chars, booleans and strings.

Furthermore, it provides homogeneous lists of values and heterogeneous tuples.

Type Literal examples Operators Meaning
int -5, 0, 42 + - * / % Arithmetic operations on ints
float 0.15, .0002,0.1e-22, +. -. *. /. Arithmetic operations on floats
string "Hello World" ^ Concatenation of strings
boolean true, false && ||
tuple ('a', 0, "hi!"),(0,1) proj t i Projection of the i-th element of t
list [2, 4, 6, 8], [], ["Hello!"] hd l 
tl
e::l
is_empty l
Get the first element of l
Get l without the first element
Add e in head of l
Tests if l is empty

Comments

There are both C/Java-like single-line comments and OCaml-like multi-line nested comments

// this is a comment

(* also
    (* this *) 
is a comment *)

Values

Expressible and denotable values are

  • integers

  • booleans

  • characters

  • floats

  • strings

  • function closures

  • tuples of values

  • list of values


I/O

There are IO directives for each data type. The format for the type T is get_T/print_T.

IO functions are still expressions, and thus evaluation returns a value. In particular, print functions are evaluated to the special value Unit.

let fun fact(n : int) : int = 
  let _ = print_int n in    // sequencing
  if n = 0 then 
    1
  else
    n * fact (n - 1)
in get_int () |> fact

Control Flow Analysis

In addition to the type analysis, Fhree does a step of control-flow-analysis, using a fix-point algorithm. The result of the analysis of a file f is writed into a file f.cfa.

The CFA is skipped by default (option --no-cfa), as you can read in the usage message.

There is also an option to do only the CFA, using Fhree as an analyzer.


Requirements

Fhree is developed using OCaml and some OCaml tools for generating lexer and parser. For building the project, you must have these tools installed in your environment.

  • OCaml and opam: follow the official instruction for you platform

  • Menhir once you have installed opam, just run opam install menhir


Usage

To build Fhree just move in the directory and run make.

After that, you can run the interpreter of the language ./Fhree with the following options.

Usage: Fhree [--no-cfa | --cfa | --all] filename
Options:
 --no-cfa
    default option: executes only the program, without analyzing the control-flow;
 --cfa
    executes only the control-flow analyzer, without executing the program;
 --all
    does a control-flow-analysis of the code and prints the result into filename.cfa
    then executes the program;

Design choices:

  • An empty program is still a correct program (with Unit value).
  • There is a single sequencing expression, that is let ... in.
  • The language requires type annotation for function parameter and return type.
  • The construct Proj t i takes a tuple and an integer literal! That's motivated by the static type checking.
  • IO primitives are "native" functions, that is: closure preloaded into the environment and defined by means of an AST node that can be instantied only by invokations to these functions.
  • At the moment, Proj on tuples and list operators are not functions! They are simple expressions, and then they cannot be used as higher-order functions or passed in pipe. Again, that's motivated by the static type checking. This will be updated with the future introduction of generics.

To Do:

  • Hexadecimal integers

  • Global Declarations

  • Unification algorithm for removing the mandatory type annotation in fun definitions

  • Another unification algorithm for an implementation of pattern matching

  • REPL

  • Code generation for a simple compilation

  • Generics

  • Uncurried functions definitions

    Multiple-argument function definition are now available! They make use of currying: they are parsed and converted in the corresponding curried - single-argument - functions: a function f

    fun f (a : t1) (b : t2) (c :t3) : tf = body;;

    is internally converted into

    fun f (a : t1) : (t2 -> t3 -> tf) -> 
        lambda (b : t2) : (t3 -> tf) -> 
            lambda (c : t3) : tf -> body

About

Fhree is a small strongly typed functional language, it is interpreted and it implements the big-step operational semantics.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages