LambdaScript - a Functional Programming Language Inspired by OCaml and Haskell

Foreword

Hello, and thank you for taking the time to look at LambdaScript. After about a year of working on LambdaScript, I have decided to start from scratch write a new, more reliable, and efficient interpreter for a new language - LambdaScript 2. This new language is based on the same principles as LambdaScript, but with a more robust implementation in TypeScript, rather than OCaml.

Working on LambdaScript has been an incredible learning experience for me, and I hope to make LambdaScript 2 even better. I hope you enjoy looking at LambdaScript/LambdaScript 2 as much as I enjoyed working on it!

-Alex

Table of Contents

1. Overview
2. Example Usages
3. Installation
4. Usage
5. Testing
6. Code Documentation

Overview

LambdaScript is a statically-typed functional programming language designed to make it easy to write elegant and expressive code. It features a powerful type system underpinned by kinds, which allows for higher-order arithmetic on types.

It also features a type inference engine similar to the Hindley-Milner algorithm, which can infer the types of most expressions, so you don't have to write them out.

Semantics

• To view the rigerously-defined semantics for LambdaScript, please refer to https://github.com/LambdaAK/LambdaScript/blob/main/documentation/LambdaScript.pdf

• Note that they are currently outdated, and have not yet been updated to reflect the new syntax and features.

Examples

Basic Types

input

17

output

Int: 17

input

true

output

Bool: true

input

"hello world!"

output

String: hello world!

input

()

output

Unit: ()

Compound Types

input

[]

output

[a]: []

input

1 :: 2 :: 3 :: 4 :: 5 :: []

output

[Int]: [1, 2, 3, 4, 5]

input

[1, 2, 3, 4, 5]

output

[Int]: [1, 2, 3, 4, 5]

input

(1, true)

output

(Int, Bool): (1, true)

input

\ x -> x

output

a -> a: function

input

\ x -> x + 1

output

Int -> Int: function

Let Expressions

input

let x = 1 in
let y = 2 in
x + y

output

Int: 3

input

let f x y z = x (y + z) in f

output

f : (Int -> a) -> Int -> Int -> a = function

Ternary Expressions

input

if true then 1 else 2

output

Int: 1

Switch Expressions

input

switch [] =>
  | [] -> true
  | _ :: _ -> false
end

output

Bool: true

input

switch [1, 2] =>
  | [] -> true
  | _ :: _ -> false
end

output

Bool: false

input

type IntList =
  | Nil
  | Cons (Int, IntList)
 
let rec length l =
  switch l =>
  | Nil -> 0
  | Cons (_, t) -> 1 + length t
  end
 

output

length : IntList -> Int = function

Higher Order Functions

input

let rec map f arr =
  switch arr =>
    | [] -> []
    | h :: t -> f h :: map f t
  end

output

(a -> b) -> [a] -> [b]: function

input

map (\ x -> x * x) [1, 2, 3, 4, 5]

output

[Int]: [1, 4, 9, 16, 25]

input

let rec filter f arr =
  switch arr =>
    | [] -> []
    | h :: t ->
      if f h then h :: filter t
      else filter t
    end

output

(a -> Bool) -> [a] -> [a]: function

input

let rec reduce_left op arr acc =
  switch arr =>
  | [] -> acc
  | h :: t -> reduce_left op t (op acc h)
  end

output

(a -> b -> a) -> [b] -> a -> a: function

input

let rec reduce_right op arr acc =
  switch arr =>
  | [] -> acc
  | h :: t -> op h (reduce_right op t acc)
  end

output

(a -> b -> b) -> [a] -> b -> b: function

Algebraic Data Types

input

type IntPair = (Int, Int)

output

type IntPair : (Int, Int)

input

type IntList =
  | Nil
  | Cons (Int, IntList)

output

type IntList : Nil | Cons (Int, IntList)

input

type IntBT =
  | Leaf
  | Node (Int, IntBT, IntBT)

output

type IntBT : Leaf | Node (Int, IntBT, IntBT)

input

type IntOpt =
  | None
  | Some (Int

output

type IntOpt : None | Some (Int)

Polymorphic Algebraic Data Types

input

type Option a = | None | Some (a)

output

Option : * -> *

input

type List a = | Nil | Cons (a, List a)

output

List : * -> *

input

type Either a b = | Left (a) | Right (b)

output

Either : * -> * -> *

input

type AssocList key val = [(key, val)]

output

AssocList : * -> * -> *

input

     type App a b = a b
     

output

     App : (* -> *) -> * -> *
     

input

type App2 a b c d e = e (b c a) d

output

* -> (* -> * -> *) -> * -> * -> (* -> * -> *) -> *

Installation

Prerequisites

• OCaml 5.0.0 or higher
• Dune

Building

• To clone the project, run the following command:

git clone https://github.com/LambdaAK/LambdaScript

• Then, cd into the project directory and run the following command:

make

Usage

• You can run the REPL by running the following command:

make repl

• You can execute a LambdaScript file by running the following command:

dune exec ./bin/interpreter.exe <filename>

Testing

Testing Overview

There are currently around 450 unit tests in the test directory. In order to achieve greater exhaustiveness, I implemented a mechanism taking pre-built unit tests and generating new ones by applying random transformatios to them. This allows for a much greater number of tests to be generated, and thus a greater degree of confidence in the correctness of the implementation. With this, the 450 unit tests can be expanded to around 13,000 unit tests.

Running Tests

To run the unit tests, run the following command:

make test

• To use the random test generator, set the modify_tests variable in test/test.ml to true and follow the instructions above.

• To run tests with coverage, run the following command:

make bisect

Documentation

• To generate the code documentation, run the following command:

make doc

• To view the code documentation, run the following command

make opendoc