Search code examples
lisppie-lang

When is a list a list, and when is a list an application?

I am trying to learn a bit of type theory. This is being taught using a dialect of lisp the author wrote called pie.

Let's say we have defined some function f that takes a single argument of type A and produces an output of type B and I have some a that is of type A.

If I try to type the expression:

(f a)

I can't decide between two possible outcomes:

  1. It's a list whose first element is some A->B and whose second element is some A
  2. It's something of type B ... because it's an application

When is a list a list, and when is it an application? What if i wanted lists of functions, how would this work, what's to stop the list being interpreted as an application?

Solution

  • The expression (f a) is a form with f as the first identifier and a as the second. This can never be a list unless f is syntax* (macro).

    Thus f gets evaluated to some object which is applied with the evaluated a as argument. If f evaluates to anything else than a function object you'll get an error since it cannot be applied.

    You can create literal lists with quote. eg. (quote (f a)) or the syntax abbreviation '(f a) applies the syntax quote which evaluates it's argument as data. eg. a list with two symbols, f and a.

    You can create lists dynamically with cons. eg. (cons 'f (cons 'a '())) creates a new list (f a) and (list 'f 'a) is a function that makes a chain of cons with the arguments as elements.

    If you wanted to create a list of two functions you can do (cons + (cons - '())) or (list + -) and they are not getting applied because they have no parentheses around them. If you were to do (list (+) (-)) they both get applied with zero arguments and the list results in being (0 0). Note that + and - are just variables here that get evaluated to function objects. You can create new function objects with lambda eg. (lambda (arg) (* arg arg)) is an implementaion of square. They need to be evaluated to become functions so you cannot put them in literals. Eg. '((lambda (arg) (* arg arg)) +) will become a list with the first element being a list with symbol lambda and the second the symbol +. None have anything to do with functions.