================== Expressions in Toy ================== Toy expressions are written and used pretty much like Lisp expressions, but they can also be modelled in a system using only unary application. This document first introduces the Lisp-like way of thinking about them, since it is the way you'll think about them in practice, and probably the way of thinking about them that makes for more efficient implementations. It then shows how that model corresponds to the unary function model. In the first model, a Toy expression is either a symbol or a call. A call applies a function (an expression) to zero or more arguments (also expressions). Calls are written as (fn arg1 arg2 ...) This implies that 'x' is a different expression from '(x)', and both of them are different from '((x))', and so on. Lists are written as [el1, el2, el3]. That's syntactic sugar, but let's treat it as primitive just for now. Definitions are written as (= pattern replacement). For example: (= (c:if c:true then else) then) (= (c:if c:false then else) else) (= my:if c:if) (= ((c:foo fn x) y z) (fn z x y)) A function can have definitions with different arities: (= (c:bar) c:blah) (= (c:bar x) c:bar) (= (c:bar x y) c:baz) There are also varargic functions, defined by putting an '*' before the last argument of the function. For example, (= (c:baz fn *xs) (c:map fn xs)) If you call this as (c:foo fn a b c), 'xs' will be bound to the list [a, b, c]. The above declaration applies to all calls of 'c:foo' with one or more parameters. You can use the '*' syntax when calling a function as well as when declaring one. The call (fn arg1 arg2 *args) is like writing (apply fn (list arg1 arg2 . args)) in Lisp, or fn(arg1, arg2, *args) in Python [yup, the syntax is inspired by that]. Note that if you call a function with a *-argument, this may call declarations with different arities depending on the length of the list passed in through the *-argument. For example, consider the call (c:bar *args) with the definition of 'c:bar' from above. If 'args' is an empty list, the first definition will be used; if 'args' is a one-element list, the second definition will be used; two-element list, third definition; if there are any more elements, none of the definitions will match and we'll get an error. I don't know whether you're still with me so far. I hope so, but if not, please ask until I have come up with a clear explanation :-) However, there's one subtlety: The objects passed in through the * syntax do not have to be lists, and the implementation must handle this. Let's say that we have a call (my:foo x *y) and 'y' is not a list. No declarations without * parameters will match, but if you have a declarations (= (my:foo fn *o) (fn o)) then the above evaluates to '(x y)', even if y is not a list. If, instead, you have a declaration (= (my:foo *a) (my:bar a)) then the correct semantics are still that it matches, passing as 'a' a "list" whose tail is the non-list object 'y' from the call. Similarly, when you have (= (my:foo fn *o) (fn o)) then calling (my:foo *arg), where arg is a cons object whose tail is a non-list, then the declaration should match, binding 'o' to the non-list. However, we might allow implementations that don't support lists whose tail isn't a list; such an implementation obviously wouldn't have to support these cases. Now, for the unary functions model. In this model, expressions are either symbols or applications; since we're using '(fn x y)' syntax for the Lisp-like model, let's write unary applications as 'fn @ arg', where the @ operator associates to the left. We'll also need parantheses... let's use angle brackets. So < @ > = > Now we introduce two constants, l:cons and c:nil, and use them to represent lists. [] translates to c:nil, obviously. [x] translates to, l:cons @ x @ c:nil [x,y] translates to, l:cons @ x @ We now model a Lisp-like application (fn arg1 arg2 arg3) as, fn @ [arg1, arg2, arg3] A call without arguments, '(fn)', thus becomes fn @ [] and '((fn))' becomes fn @ [] @ [] and '((fn x) y z)' becomes, fn @ [x] @ [y, z] It remains to explain the vararg calls. They translate to calls whose argument list's tail is the vararg argument; for example, '(fn x *y)' becomes, fn @ and '(fn x y *z)' becomes fn @ > whereas '(fn x y z)', without the syntactic sugar, is fn @ >> This translation is the same for the lhs and the rhs of a '=' definition. Conversely, this implies that you can write in the concrete language as (fn *arg) and fn @ x @ y @ z as (((fn *x) *y) *z) If this makes it clear, great. If not, please ask and help me to improve this document. :-)