Decoy

Work in progress

Decoy is a simple functional language with a syntax derived from R5RS Scheme and semantics derived from R5RS Scheme.

But it's not Scheme. Thus the name!

I'm not normally a fan of "extended subset" languages like this, but Decoy is best thought of as a DSL for pure state-transformation functions (such as so-called "reducers") that reuses a well-understood syntax instead of making up yet another one. In that light it's not so bad.

For details of the language, see the Decoy Language Definition.

Quick Start

Decoy has a reference interpreter, which is written in Lua 5.3.

• Make sure Lua 5.3 is installed
• Clone this repo
• Change directory to the repo's root directory
• Run ./test.sh to run the test suite.
• Run ./bin/decoy eval eg/foo.scm to evaluate a Decoy module.
• Run ./bin/decoy compile eg/foo.scm to compile a Decoy module to JavaScript.

Design Considerations

Having pure functions that transform a system state (plus possibly some input parameters) into a "next" system state (plus possibly some output events) is a really spiffy way to define and implement things like programming languages and user interfaces.

In programming languages they call this small-step operational semantics. In web development they call these functions reducers. It's not limited to these two ideas; there are a number of other variations on this theme out there.

I wanted a language for writing these state-transformation functions in.

The language needn't innovate very much, and being based on an established language will make it easier to pick up and encourage "transferrable skills". (Thus the significant Scheme borrowings.)

Since the functions themselves are pure (have no side effects), the language should enforce that. (Thus, no set!.)

It should also be simple to implement, and straightforward to compile to (and otherwise interoperate with) other more conventional languages such as JavaScript. (Thus, a simplified and adjusted type system, and no burden of implementing tail recursion on a target platform that doesn't support it naturally.)

Comparison to Other Languages

Decoy is not Scheme

Lots of things are missing:

• Cons cells aren't mutable
• There's no tail recursion
• There's no vectors
• There's no numeric tower
• There's no quote or quasiquote notation
• There's no character or boolean constants
• There's no macros
• define can only be used at top-level
• There's no call-with-current-continuation or dynamic-wind
• There's no ports
• There's no support for SRFIs
• My word, there's not even a standard environment loaded by default!

All the same, once you get over that last point and import an R5RS-like environment at the top of your source file, the set of programs that are both R5RS Scheme programs and Decoy programs ought to be fairly large.

Some things are added:

• A module system of sorts
• Some standard libraries, supplied as modules in this system

Relation to Pixley

Pixley is a much earlier project by the same author to define a minimal subset of Scheme in which a self-interpreter could be written. While Decoy has some similarities to Pixley, Decoy is generally a richer language, in which there are more data types (such as numbers), more standard procedures (such as list), and a module system. There are also no plans to implement a Decoy interpreter in Decoy.

Relation to Robin

Robin is an earlier project by the same author.

It shares some of the same ideals about not having a comprehensive "standard" environment by default, instead providing multiple small libraries that can be explicitly imported individually, or in a single larger aggregate.

More TBW.

TODO

Reconceptualizing

• stdenv can be replaced by r5rsish. r5rsish should import and re-export a number of constituent modules, e.g. cons, arith, string, etc.
• The Decoy parser need not parse program into Cons lists. It can parse them into AST structures instead. This will require classes for ADT nodes which are special forms like Define and ImportFrom, and these will still require lists in them, but those lists can be Lua tables.

Modules

• Test modules that import modules (r5rsish)
• Test that circular imports don't loop
• Include only those symbols that are used when compiling an import
• How does a module import a symbol and re-export (or not re-export) it?

Forms

Needs tests

• (string-ref string k) procedure
• map -- library procedure
• list-ref -- library procedure

In Scheme

• append -- library procedure
• (string-length string) procedure
• (string<? string1 string2) library procedure
• (string>? string1 string2) library procedure
• (string<=? string1 string2) library procedure
• (string>=? string1 string2) library procedure

Equality

• = -- procedure; this only works on numbers
• (string=? string1 string2) library procedure
• equal? - in Scheme this works on cons cells and many other types of things. We will need to take that into account somehow. Perhaps it only appears in r5rsish and the individual libraries will expose list-equal? and such.

Not in Scheme

Have these in some library, just don't have them in r5rsish

• fold
• assert -- this is in Chicken by default too -- note this is a macro
• error

Aspirational

• Interned strings and modules? Hash-consing, even?
• Tracebacks, or at least line/column, or at least "in function..."
• Module path should be like LUA_PATH with the patterns