Decoy Language Definition

Work in progress

This document contains a description of the Decoy language. Along with the reference interpreter, it attempts to define the Decoy language prescriptively.

Many of the language features are demonstrated by example code that can be run as an automated test. However these demonstrations cannot provide an exhaustive definition of the expected behaviour.

Grammar

This is how the parser understands the program text:

Module ::= {Expr}.
Expr   ::= "(" {Expr} ")"
         | Symbol
         | StrLit
         | NumLit
         .

The output of this parsing is a list of "S-expressions", which are isomorphic to (a subset of) the values manipulated by a Decoy program at runtime.

On another conceptual level, these S-expressions are interpreted as a number as "special forms" that have a role in evaluation:

• (bind name expr expr)
• (lambda (name ...) expr)
• (if expr expr expr)
• (expr ...)
• identifier

Some "special forms" may only appear at the top level of a program source file, i.e. a module, and not inside another expression:

• (import-from name (name ...))
• (define name expr)

In addition, there are forms which get expanded ("desugared") into one or more of the above forms:

• (let* ((name expr) ...) expr) desugars to a series of binds
• (cond (expr expr) ... (else expr)) desugars to a series of ifs

Modules

The set of defines within a module defines the set of identifiers, and their associated meanings, that the module exposes to the rest of the world (i.e. other modules). A set of identifiers along with their associated meanings is called an environment.

An environment is available to the module when it is processed. It is evaluated within this environment.

This environment for a module consists of an optional "prelude" environment supplied by the implementation, extended with the environments of all external modules that are imported using import-from forms within the module.

Although an implementation of Decoy may provide a prelude environment, as a convenience, for the processing of modules, it must also provide an option to provide no prelude at all (or equivalently, an empty prelude.)

It is important to note that modules may be implemented in languages other that Decoy. There are several considerations here, that we will endeavour to write down in some form here one day.

NOTE: Modules are provided for their semantics. It is understood that an "implementation module" written in language X will be used when the code is compiled to X. But the module defines the semantics. More on this later.

Standard Environment

There is also a standard environment containing symbols which are mainly bound to functions. This is a work in progress, but includes

• (equal? expr)
• artithmetic operators: + - * /
• comparison operators: > >= < <=
• boolean operators: and or not

These may be considered to have been implicitly imported from a prelude module (whose implementation is in something other than Decoy itself, i.e. whose symbols are bound to builtin functions).

Evaluation of Decoy Expressions

-> Functionality "Interpret Decoy Program" is implemented by shell command
-> "./bin/decoy eval -I lib/ -m stdenv %(test-body-file)"

-> Functionality "Interpret Decoy Program" is implemented by shell command
-> "./bin/decoy compile -I lib/ -m stdenv %(test-body-file) > out.mjs && node out.mjs"

Constructing and Manipulating Data

-> Tests for functionality "Interpret Decoy Program"

Strings

String literals evaluate to literally that string.

"hello"
===> "hello"

Numbers

123
===> 123

Arithmetic

(* 2 (+ 3 4))
===> 14

(+ 2.4 0)
===> 2.4

(let* ((a 2.0) (b 2.5)) (/ b a))
===> 1.25

Negative numbers

(+ -2 -4.1)
===> -6.1

Yet - by itself is parsed as a symbol. And refers to the subtraction operation.

(- 17 9)
===> 8

Comparison

(> 2 1)
===> #t

(> 2 2)
===> #f

(>= 2 1)
===> #t

(>= 2 2)
===> #t

(< 2 3)
===> #t

(< 2 2)
===> #f

(<= 2 3)
===> #t

(<= 2 2)
===> #t

Boolean operators

Note, unlike Scheme, these are not guaranteed to be short-circuiting.

(and (< 2 2) (<= 2 3))
===> #f

(and (<= 2 2) (<= 2 3) (<= 2 4))
===> #t

(and)
===> #t

(or (< 2 2) (<= 2 3))
===> #t

(or (< 2 2) (<= 2 3) (< 2 1))
===> #t

(or)
===> #f

(not (or))
===> #t

not takes exactly 1 argument.

(not)
???>

Binding to Names

let* lets you bind identifiers to values. An identifier can be bound to a symbol.

(let* ((a "hello")) a)
===> "hello"

let* can appear in the binding expression in a let*.

(let* ((a (let* ((b "c")) b))) a)
===> "c"

let* can bind a symbol to a function value.

(let* ((a (lambda (x y) y)))
      (a "foo" "bar"))
===> "bar"

Bindings established in a binding in a let* can be seen in subsequent bindings in the same let*.

(let* ((a "hello") (b (equal? a "hello"))) b)
===> #t

Shadowing happens.

(let* ((a "hello")) (let* ((a "goodbye")) a))
===> "goodbye"

let* can have an empty list of bindings.

(let* () "hi")
===> "hi"

Despite its use in negation, names can begin with -.

(let* ((-- 17) (--- 9)) (- -- ---))
===> 8

Predicates and Decision-making

cond can be used to compare values. equal? works on strings.

(cond
  ((equal? "a" "a") "true")
  (else "false"))
===> "true"

(cond
  ((equal? "a" "b") "true")
  (else "false"))
===> "false"

if.

(if (equal? "a" "a") "true" "false")
===> "true"

(if (equal? "a" "b") "true" "false")
===> "false"

All non-booleans are considered true. This at least coincides with what Chicken tells me.

(if 1 "true" "false")
===> "true"

(if 0 "true" "false")
===> "true"

(if "hey" "true" "false")
===> "true"

(if "" "true" "false")
===> "true"

cond works.

(let* ((true (equal? "a" "a")))
  (cond (true "hi") (else "lo")))
===> "hi"

(let* ((true (equal? "a" "a"))
       (false (equal? "a" "b")))
  (cond (false "hi") (true "med") (else "lo")))
===> "med"

(let* ((true (equal? "a" "a"))
       (false (equal? "a" "b")))
  (cond (false "hi") (false "med") (else "lo")))
===> "lo"

cond can have zero tests before the else.

(cond (else "woo"))
===> "woo"

Functions

You can define functions with lambda. Technically, they are anonymous. But they can only be applied if they are in "A-normal form", that is, if they are bound to a name.

(let*
  ((z (lambda (a) a) ))
  (z "whee"))
===> "whee"

Bindings in force when a function is defined will still be in force when the function is applied, even if they are not lexically in scope.

(let*
  ((bear (let*
      ((a 100)
       (f (lambda (x) (- x a))))
    f)))
  (bear 250))
===> 150

You can call a function with a bound name as its argument.

(let* ((interpret
        (lambda (program)
          (let* ((interpreter 1000))
            (+ interpreter program))))
       (myjunk 33))
  (interpret myjunk))
===> 1033

Functions can take functions.

(let*
  ((apply (lambda (x) (x 65))))
  (apply (lambda (r) (+ r 100))))
===> 165

Functions can return functions.

(let*
  ((mk (lambda (x) (lambda (y) (+ y x))))
   (mk2 (mk 99)))
  (mk2 100))
===> 199

Standard Environment

Trigonometric functions

(let* ((round (lambda (x)
  (/ (floor (* 1000000 x)) 1000000))))
    (round (sin 6.0)))
===> -0.279416

(let* ((round (lambda (x)
  (/ (floor (* 1000000 x)) 1000000))))
    (round (cos 6.0)))
===> 0.96017

Other math

(abs 5)
===> 5

(abs -5)
===> 5

(abs 0)
===> 0

(ceiling 5.5)
===> 6

(ceiling 5.0)
===> 5

(ceiling -5.5)
===> -5

(floor 5.5)
===> 5

(floor 5.0)
===> 5

(floor -5.5)
===> -6