Skip to content
/ terp Public

A functional programming language with lisp syntax and ML semantics that runs on the BEAM

License

Notifications You must be signed in to change notification settings

smpoulsen/terp

Repository files navigation

Terp

terp is a toy language that falls somewhere between an ML and a lisp.

Currently implemented:

Additional examples can be found in the examples directory.

Usage

Installation/Prerequisites

To try terp, you must have Elixir and Erlang installed. If you don’t already have them installed, the asdf version manager is a good way to do so (or see the installation guide at elixir-lang.org). If you’re using asdf, there is a .tool-versions file in the root of the project; running asdf install will install the proper versions of Elixir and Erlang.

With those installed, run mix deps.get in the root directory to install additional dependencies.

REPL

The quickest way to try terp is via the Read-Eval-Print-Loop (REPL). The repl is started by running* iex -S mix terp.repl at the command line from the project root.

In the REPL you can evaluate expressions, import modules, and type check expressions.

media/repl_demo.gif

*The REPL can also be started with just mix terp.repl. If stared like this, there is not any scrollback or history. By using iex -S mix terp.repl, the IEx shell provides those features while still running the terp REPL.

File evaluation

There’s a mix task (mix terp.run $FILENAME) to evaluate a file:

For example, with a file named test.tp (terp files must end in .tp) that contains the following code:

(defn identity (x) x)

(defn square (x)
    (* x x))

(square (identity 2))

Running mix terp.run test.tp evaluates the file:

$ mix terp.run test.tp
4

Language Features

Comments

Comments are single-line and begin with ;;:

;; A comment
(+ 5 1)
;; 6

Variable binding

Variables are bound using let:

(let x 5)

(let identity
    (lambda (x) x))

(identity x)
;; 5

Local variables can be bound with let-values:

(let-values
    ([x 5]
     [y 3])
  (+ x y))
;; 8

(defn plusOne (x)
  (let-values
      ([y 1])
    (+ x y)))
(plusOne 5)
;; 6

Conditionals

if expressions must include a value for both the true and false case (an if and an else).

(if #t 5 10)
;; 5

(let x 5)
(if (equal? x 5)
    (* x x)
    0)
;; 25

cond can be used to test multiple possible conditions without chaining if/elses: cond takes conditions and their outcomes should their case be true; the last condition should be a default.

(let sound
    (lambda (animal)
      (cond
       [(equal? animal "cow") "moo"]
       [(equal? animal "cat") "meow"]
       [(equal? animal "dog") "bark"]
       [#t "zzz"]
       )))

(sound "dog")
;; "bark"

Function definition

Functions are defined using lambda; they can be bound to a name with let.

The arguments must be wrapped in parens. The body of the function can be bare if it does not have to be evaluated (e.g. returns a single value). Otherwise, the body must be parenthesized as well.

;; An anonymous identity function.
;; It returns the value it receives.
(lambda (x) x)

;; Defining a named function:
(let double
    (lambda (x)
      (* 2 x)))
(double 5)
;; 10

(let square
    (lambda (x)
      (* x x)))
(square 5)
;; 25

Multi-argument functions:

(((lambda (x)
    (lambda (y)
      (+ x y))) 5 ) 3)
;; 8

((lambda (x y)
   (+ x y)) 5 3)
;; 8

Functions are automatically curried when defined. This allows for easy partial application of multi-argument functions:

;; add is a function that takes two arguments.
;;   Currying turns it into a series of functions
;;   that each takes a single argument.
(let add
    (lambda (x y)
      (+ x y)))

;; We can define a new function, add_five, that partially
;; applies add to the value 5:
(let add_five
    (add 5))

;; evaluating add_five with 3 binds the last argument in
;; add, and the function is fully evaluated:
(add_five 3)
;; 8

Functions can also be defined using defn; this is syntactic sugar for let/lambda definition:

(defn add (x y)
  (+ x y))

Recursive functions

Recursive functions are defined with letrec. The base case(s) and recursive case(s) must be provided or the function will not terminate.

(letrec factorial
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (factorial (- n 1))))))

(factorial 5)
;; 120

Recursive functions can also be defined using defrec; this is syntactic sugar for letrec/lambda:

(defrec factorial (n)
    (if (equal? n 0)
        1
        (* n (factorial (- n 1)))))

(factorial 5)
;; 120

Module system

Modules can be imported in to other modules to make their functions/defined expressions available. Modules must specify the functions that they export (via provide) or they cannot be used in other modules.

To import a module use (require ...), where ... is a sequence of module names, at the top of the file. Module names are derived from their file-path relative to the project root directory (e.g. a file at “.examples/factorial.tp” has the module name examples/factorial).

(require examples/factorial
         examples/identity)

(factorial (identity 10))

With examples/factorial and examples/identity defined as in the examples directory.

To use functions from an imported module, the module that is imported must explicitly export functions it wants to make available externally. The syntax is (provide ...) where ... is a sequence of function names.

;; Module only exports factorial; identity is private.

(provide factorial)

(letrec factorial
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (factorial (- n 1))))))

(let identity
    (lambda (x) x))

Type system

Terp implements Hindley-Milner type inference.

Expressions are type checked prior to evaluation. If an expression fails the type check, it won’t be evaluated. To see the inferred type for an expression in the REPL, prefix it with :t or :type.

A type environment is maintained during evaluation and REPL sessions; this environment remembers the types for functions and variables.

Binding a simple variable:

media/repl_simple_env.gif

Binding and using a recursive, higher-order function: media/repl_type_env.png

Higher kinded types

Higher kinded types (types parameterized by another type) are defined using data:

(data (Maybe a) [Just a] [Nothing])

This defines a type, Maybe, that is parameterized by another type (represented by the type variable a). Concrete examples could be Maybe Int or Maybe String. Using Maybe Int as an example, values of the Maybe Int type can be either Just Int or Nothing. This can be used to work with values that can potentially be non-existent.

Defining a type with data also defines constructor functions for the value constructors of the type (Just and Nothing in this example).

Pattern matching

match allows you to pattern match against the value constructors for a type. In this example, Maybe is a type with the value constructors Just and Nothing. With match, you can write a function that takes a value of type Maybe and nicely handles values that are either Just or Nothing:

(data (Maybe a) [Just a] [Nothing])

(type maybePlusFive (-> [Maybe Int] [Maybe Int]))
(defn maybePlusFive (x)
  (match (x)
    [(Just y) (Just (+ 5 y))]
    [(Nothing) (Nothing)]))

(maybePlusFive (Just 5))
;; Just 10
(maybePlusFive (Nothing))
;; Nothing

Elixir/Erlang interop

Elixir and Erlang functions can be used by prefixing them with a :, e.g:

;; Using Elixir functions directly:
(:Enum.map '(1 2 3 4 5) (lambda (x) (* x x)))
;; '(1 4 9 16 25)

;; Calling Elixir's uppercase function:
(:String.upcase "asdf")
;; "ASDF"

;; Calling Erlang's uppercase function:
(:string.uppercase "asdf")
;; "ASDF"

;; Writing and using a function that uses an Elixir function:
(defn square (xs)
  (:Enum.map xs (lambda (x) (* x x))))
(square '(1 2 3 4 5))
;; '(1 4 9 16 25)

Caveats

There are currently a few important things to keep in mind:

  1. This is not yet thoroughly tested. There’s a large surface area to test to make sure everything works as expected.
  2. Type inference does not work for Elixir/Erlang functions. When writing functions that use Elixir/Erlang functions, type annotations should be provided for used functions. See ./examples/elixir_interop.tp for examples/details.
  3. The full module and function names must be provided.
  4. Elixir and Erlang functions aren’t curried.

Test utilities

There’s a mix task (mix terp.test [$FILENAME | $DIRECTORY]) to find and run tests in the given file(s)/directories.

Test files must end in _test.tp or they will not be run.

If a directory is provided to mix terp.test, its subdirectories are recursively checked for files to test.

prelude/test.tp exports the functions test, assert, and refute. See the documentation in prelude/test/runner.tp for more information.

(type test (-> String (-> Bool Bool)))

(type assert (-> Bool Bool))

(type refute (-> Bool Bool))

Running tests

A symbol [✓ | x] and the name provided to test are printed to the console; they are color coded green/red based on pass/fail respectively.

The time spent running tests and a count of total tests and total failures are also printed.

media/test_run.png

Error messages

To help with debugging, error messages try to be as informative as possible: media/error_messages.png

About

A functional programming language with lisp syntax and ML semantics that runs on the BEAM

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published