ParselTongue 0.1

Chapter 0: Introduction and Motivation

This document is an informative specification of the ParselTongue programming language at version 0.1. ParselTongue's implementation is the normative language definition, but this document strives to document its functionality in accurate detail.

Chapter 1: Syntax

This section presents the syntax of ParselTongue, which defines the expression forms used for evaluation. Examples are given for each kind of expression.

An expression is one of:

• number

  42
  

  Note: ParselTongue implementations may fail to parse negative numbers. This dubious design choice will be revisited in later versions of the language.

• string

  "Are you having fun yet?"
  

• true

  true
  

• false

  false
  

• expression ; expression ;

  5; "another expression";
  

• if (expression) then expression else expression

  if true then 
      "passed" 
  else 
      "failed"
  

• for (expression; expression; expression) { expression }

  defvar x = 0 in {  
      for(x = 0; <(x,5); x++) {
          print(x);
          print("\n");
      };
      print("Another print statement!");
  }
  # You cannot include another expression here
  

• while (expression) { expression }

  while(true) {
      print("infinite loops are bad for the environment!");
  }
  

• lambda (identifier ...) { expression }

  (lambda(x) { x })(4)
  

• expression(expression, ...)

  myFunction(1, 2, 3)
  

• deffun identifier(identifier, ...) expression in expression

  deffun not(b) if b then false else true in {
      if (true) then
          print(not(true))
      else
          5
  }
  
  
  # multiple deffuns and defvars can appear in a row, but the final body
  # must be enclosed in {}
  defvar x = 0 in
  deffun inc() x++ in
  deffun dec() x-- in {
    inc(); dec(); dec(); inc();
  }
  

• defvar identifier = expression in expression

  # You can also nest deffuns and defvars
  deffun not(b) if b then false else true in
      defvar x = 0 in {
          if ==(x, 0) then
              print("Passed")
          else
              print("Failed")
          ;
          x;
    }
  

• { identifier : expression, ... }

  {
      prop1: 'a property',
      prop2: 'another property'
  }
  

• expression@identifier(expression, ...)

  # @ provides an object as an implicit argument
  defvar o = {f:lambda(self) { self.x }, x:3} in { o@f() }
  

• expression@[expression](expression, ...)

  defvar o = {fg:lambda(self) { self.x }, x:3} in { o@[+("f", "g")]() }
  

• left-hand-side

  see below

• left-hand-side = expression

  o = 3
  o.x = 3
  o[+("baz", "x")] = 22
  

• left-hand-side += expression

• left-hand-side -= expression

  o += 3
  o.x -= 5
  o[+("foo", "bar")] += "hello"
  

• identifier++
• identifier--
• ++identifier

• --identifier

• op(expression, ...)

  print("This will go to standard out")
  <(4, 5)
  ==(5, 5)
  

A left-hand-side is one of:

• identifier
• expression[expression]
• expression.identifier

An op is one of:

< > + - == print

You can also comment an entire line by starting it with "#";

Whitespace is not significant.

Chapter 2: Values, Answers, and Output

There are several types of values that a ParselTongue program might evaluate to. These are written in boldface to distinguish them from expressions.

A value is one of:

• number, corresponding to Racket numbers
• string, corresponding to finite sequences of Unicode characters
• true
• false
• {string : value, ...} (an object with strings for field names and values for all fields)
• lambda^environment (identifier, ...) { expression } (a function paired with the environment it was evaluated in)

A ParselTongue program may also terminate its computation and signal an error, which is a valid program result, but not a value. An error is always associated with a string value:

An error is: error(string)

Collectively, errors and values are referred to as answers.

Chapter 3: Evaluating Expressions

When evaluating expressions, there is always a current environment, and for each program, there is a single store. The environment maps identifiers to locations, and the store maps locations to values.

Sometimes, evaluating an expression results in an error. If evaluating an expression ever results in an error, the entire evaluation stops with that error as the result. Thus, we write that sub-expressions evaluate to values, rather than answers, because if they had evaluated to an error, computation would have stopped already.

Evaluating the Number Expression

The expression number evaluates to the result of performing the string->number Racket function call on number.

Evaluating the String Expression

The expression string evaluates to the string value string.

Evaluating the True Expression

The expression true evaluates to the value true.

Evaluating the False Expression

The expression false evaluates to the value false.

Evaluating the Sequence Expression

To evaluate expression₁;expression₂ ;:

1. Evaluate expression₁ to a value v.
2. Evaluate expression₂ and yield its result.

Evaluating the If Expression

To evaluate if (expression₁) then expression₂ else expression₃:

1. Evaluate expression₁ to a value v.
2. If v is the value false, then evaluate expression₃ and yield its result.
3. Otherwise, evaluate expression₂ and yield its result.

Evaluating the For Expression

To evaluate for (init; test; update) { body }:

1. Evaluate init to an value v.
2. Evaluate test to a value v2.
3. If v2 is false, the yield v as the result of the whole expression.
4. Otherwise
   1. Evaluate body to a value v3.
   2. Evaluate update to a value v4.
   3. Evaluate test to a value v5.
   4. If v5 is the value false, then yield v3 as the result of the whole expression.
   5. Otherwise, go to sub-step 4.1 above and repeat.

Evaluating the While Expression

To evaluate while (test) { body }:

1. Evaluate test to a value v.
2. If v is the value false, then yield false as the result of the whole expression
3. Otherwise
   1. Evaluate body to a value v2.
   2. Evaluate test to a value v3.
   3. If v3 is the value false, then yield v2 as the result of the whole expression.
   4. Otherwise, go to sub-step 3.1 above and repeat.

Evaluating the Lambda Expression

To evaluate lambda (identifier ...) { body }:

1. Let env be the current environment.
2. Yield the value lambda^env (identifier ...) { body }

Evaluating the Application Expression

To evaluate func(expr₁, ..., expr_n):

1. Evaluate func to a value v
2. Yield the result of evaluating Apply(v, expr₁, ..., expr_n)

Evaluating the Comparative Operators

To evaluate op(expr₁, expr₂), when op is < or >:

1. Evaluate expr₁ to a value v₁.
2. Evaluate expr₂ to a value v₂.
3. If both v₁ or v₂ are numbers, then perform the Racket op operation on v₁ and v₂ (this always yields either true or false).
4. Otherwise, yield error(S), where S is the concatenation of the strings "Bad arguments for <:\n", Pretty(v₁), "\n" and Pretty(v₂).

Evaluating the Addition Operator

The addition operator + behaves differently depending on whether it is applied to numbers or strings. To evaluate the expression +(expr₁, ..., expr_n), for n > 0:

1. Evaluate expr₁, ..., expr_n to a list of values v₁, ..., v_n, starting with expr₁, from left to right.
2. If all of v₁, ..., v_n are numbers, then yield the result of applying the Racket + operation to v₁, ..., v_n
3. If all of v₁, ..., v_n are strings, then yield the result of applying the Racket string-append operation to v₁, ..., v_n
4. Otherwise, yield error("Bad arguments to +")

Evaluating the Subtraction Operation

To evaluate the expression -(expr₁, ..., expr_n), for n > 0:

1. Evaluate expr₁, ..., expr_n to a list of values v₁, ..., v_n, starting with expr₁, from left to right.
2. If n is 1 and v₁ is a number, then yield v₁.
3. Otherwise, if all of v₁, ..., v_n are numbers, then yield the result of applying the Racket - operation to v₁, ..., v_n
4. Otherwise, yield error("Bad arguments to -")

Evaluating the == Operation

To evaluate the expression ==(expr₁, expr₂):

1. Evaluate expr₁ to a value v₁.
2. Evaluate expr₂ to a value v₂.
3. Yield the result of applying Equal(v₁, v₁)

Evaluating the Print Operator

To evaluate the expression print(expr):

1. Evaluate expr to a value v.
2. Output Pretty(v)

Evaluating erroneous operator patterns

To evaluate the expression op():

1. Yield error("Empty list for prim op")

To evaluate the expression op(expr₁, ..., expr_n), with n > 2 and op one of < > ==:

1. Yield error("Bad primop")

To evaluate the expression print(expr₁, ..., expr_n), with n > 1:

1. Yield error("Bad primop")

Evaluating the Deffun Expression

To evaluate the expression deffun identifier(identifier₁, ...) expression₁ in expression₂:

1. Let store be the current store.
2. Let location be a new location not in store.
3. Let env be the current environment.
4. Let env' be the result of applying AddBinding(env, identifier, location)
5. Let v be lambda^env'(identifier₁, ...) expression₁
6. Let store' be the result of applying UpdateStore(store, location, v).
7. Set the current store to store'
8. Set the current environment to env'
9. Yield the result of evaluating expression₂
10. Set the current environment back to env

Evaluating the Defvar Expression

To evaluate the expression defvar identifier = expression₁ in expression₂:

1. Evaluate expression₁ to a value v.
2. Let store be the current store.
3. Let location be a new location not in store.
4. Let env be the current environment.
5. Let env' be the result of applying AddBinding(env, identifier, location)
6. Let store' be the result of applying UpdateStore(store, location, v).
7. Set the current store to store'
8. Set the current environment to env'
9. Yield the result of evaluating expression₂
10. Set the current environment back to env

Evaluating the Object Expression

To evaluate the expression {identifier:expression,...}:

1. If more than one of the identifiers in (identifier, ...) are identical, then yield error("Multiply-defined fields").
2. Otherwise:
   1. Evaluate all the expressions from left to right, to a sequence of values v, ...
   2. Yield the value {"identifier" : v, ...}

Evaluating the Dotted Object Lookup Expression

To evaluate the expression expression.identifier:

1. Evaluate expression to a value v.
2. Yield the result of applying Lookup(v, "identifier")

Evaluating the Bracket Object Lookup Expression

To evaluate the expression expression_obj[expression_fld]:

1. Evaluate expression_obj to a value v_o.
2. Evaluate expression_fld to a value v_f.
3. Yield the result of applying Lookup(v_o, v_f)

Evaluating the Dotted Method Expression

To evaluate the expression expression@identifier(expression₁,...):

1. Evaluate expression to a value v.
2. Let v_f be the result of evaluating Lookup(v, "identifier")
3. Yield the result of applying Apply(v_f, v, expression₁, ...)

Evaluating the Bracket Method Expression

To evaluate the expression expression@[expression_fld](expression₁, ...):

1. Evaluate expression_obj to a value v_o.
2. Evaluate expression_fld to a value v_f.
3. Let v_f be the result of evaluating Lookup(v, "identifier")
4. Yield the result of applying Apply(v_f, v, expression₁, ...)

Evaluating the Variable Assignment Expression

To evaluate the expression identifier = expression:

1. Evaluate expression to a value v
2. Let location be the mapping of identifier in the current environment
3. Let store' be the result of applying UpdateStore(store, location, v)
4. Set the current store to store'

Evaluating the Dotted Object Assignment Expression

To evaluate the expression expression_obj.identifier = expression_new

1. Evaluate expression_obj to a value v_obj
2. Evaluate expression_new to a value v_new
3. Yield the result of applying UpdateObject(v_obj, "identifier", v_new)

Evaluating the Bracket Object Assignment Expression

To evaluate the expression expression_obj[expression_fld] = expression_new

1. Evaluate expression_obj to a value v_obj
2. Evaluate expression_fld to a value v_fld
3. Evaluate expression_new to a value v_new
4. Yield the result of applying UpdateObject(v_obj, v_fld, v_new)

Evaluating the Variable Assignment Operator Expression

To evaluate the expression identifier op= expression, where op is either + or -:

1. Evaluate expression to a value v
2. Let location be the mapping for identifier in the current environment
3. Let v_now be the current value of the mapping for location in the current store
4. Let v_new be the result of applying Combine(op, v_now, v)
5. Let store' be the result of applying UpdateStore(store, location, v_new)
6. Set the current store to be store'
7. Yield v_new

Evaluating the Dotted Assignment Operator Expression

To evaluate the expression expression_obj.identifier op= expression, where op is + or -:

1. Evaluate expression_obj to a value v_o
2. Let v_f be the result of applying Lookup(v_o, "identifier")
3. Evaluate expression to a value v
4. Let v_new be the result of applying Combine(op, v_f, v)
5. Yield the result of applying UpdateObject(v_o, "identifier", v_new)

Evaluating the Bracket Assignment Operator Expression

To evaluate the expression expression_obj[expression_fld] op= expression

1. Evaluate expression_obj to a value v_o
2. Evaluate expression_fld to a value v_fld
3. Evaluate expression to a value v
4. Let v_f be the result of applying Lookup(v_o, v_fld)
5. Let v_new be the result of applying Combine(op, v_f, v)
6. Yield the result of applying UpdateObject(v_o, v_fld, v_new)

Evaluating the Post-Increment Operator Expression

To evaluate the expression identifier++:

1. Let location be the mapping of identifier in the current environment
2. Let v be the mapping of location in the current store
3. Let v' be the result of applying Combine(+, 1 v)
4. Let store' be the result of UpdateStore(location, v')
5. Yield v

Evaluating the Pre-Increment Operator Expression

To evaluate the expression ++identifier:

1. Let location be the mapping of identifier in the current environment
2. Let v be the mapping of location in the current store
3. Let v' be the result of applying Combine(+, 1 v)
4. Let store' be the result of UpdateStore(location, v')
5. Yield v'

Evaluating the Post-Decrement Operator Expression

To evaluate the expression identifier--:

1. Let location be the mapping of identifier in the current environment
2. Let v be the mapping of location in the current store
3. Let v' be the result of applying Combine(-, 1 v)
4. Let store' be the result of UpdateStore(location, v')
5. Yield v

Evaluating the Pre-Decrement Operator Expression

To evaluate the expression --identifier:

1. Let location be the mapping of identifier in the current environment
2. Let v be the mapping of location in the current store
3. Let v' be the result of applying Combine(-, 1 v)
4. Let store' be the result of UpdateStore(location, v')
5. Yield v'

Metafunctions

Combine(op, value₁, value₂)

1. If both v₁ and v₂ are numbers, yield the result of applying the Racket op operation to them
2. If both v₁v₂ are strings, and op is +, yield the result of applying the Racket string-append operation to them
3. For any other combination of values and operators, yield error("Bad primop")

Apply(value, expr₁, ..., expr_n)

1. If value is not of the form lambda^env (identifier₁, ..., identifier_m) { body }, then yield error(S), where S is the string "Not a function: " concatenated with the result of Pretty(value)
2. Otherwise:
   1. Evaluate expr₁, ..., expr_n to a sequence of values v₁, ..., v_n starting with expr₁ and going from left to right.
   2. If n does not equal m (e.g. the argument list is a different length than the list of argument names), yield error("Application failed with arity mismatch").
   3. Otherwise:
      1. Let env' be a copy of env.
      2. Let store' be a copy of store.
      3. Create n new locations, l₁, ..., l_n, that don't exist in the store.
      4. From left to right, for i from 1 to n in the identifier list, let env' be the result of applying the metafunction AddBinding(env', identifier_i, l_i).
      5. From left to right, for i from 1 to n in the location list, let store' be the result of applying the metafunction UpdateStore(store', l_i, v_i).
      6. Set the current environment to env'.
      7. Set the current store to store'
      8. Evaluate body to a value v.
      9. Set the current environment back to env
      10. Yield v as the result of the entire expression.

Lookup(v_o, v_f)

1. If v_f is not a string, yield error(S), where S is the string "Non-string in field update: " concatenated with the result of Pretty(v_f).
2. If v_o is not an object, yield error(S), where S is the string "Non-object in field lookup: " concatenated with the result of Pretty(v_o).
3. If v_o does not have a field named v_f, yield error(S), where S is the string "Field not found: " concatenated with v_f.
4. Otherwise, yield the value of the field named v_f in v_o.

UpdateObject(v_obj, v_f, v_new)

1. If v_f is not a string, yield error(S), where S is the string "Non-string in field update: " concatenated with the result of Pretty(v_f).
2. If v_obj is not an object, yield error(S), where S is the string "Non-object in field update: " concatenated with the result of Pretty(v_obj).
3. Otherwise:
   1. If v_o does not have a field named v_f, yield a new object with all the fields of v_obj, plus a new field that maps v_f to v_new.
   2. Otherwise, yield a new object with the value of the field v_f replaced with value v_new.

Equal(value₁, value₂)

• Equal(string, string) = true for identical strings
• Equal(number, number) = true for identical numbers
• Equal(true, true) = true
• Equal(false, false) = true
• Equal({string₁ : value₁, ...}, {string₂ : value₂, ...}) = true when the same strings are in the sequences {string₁, ...}, and {string₂, ...} (in the same order), and when Equal(value₁, value₂) ... for all the values, in order. (At each position, the values are pairwise equal)
• Equal( lambda^{environment₁} (identifier₁, ...) { expression₁ }, lambda^{environment₂} (identifier₂, ...) { expression₂ } ) = true when the environments map the same identifiers to Equal values, and when expression₁ is the same as expression₂
• Equal(v₁, v₂) = false in all other cases

AddBinding(env, identifier, location)

If env has a mapping for identifier, replace the mapping with one from identifier to location. Otherwise, add a mapping to env from identifier to location. Return the resulting env.

UpdateStore(store, location, value)

If store has a mapping for location, replace the mapping with one from location to value. Otherwise, add a mapping to store from location to value. Return the resulting store.

Pretty(v)

Pretty(v) provides a string value that describes the value v provided as an argument. It yields the following results:

• Pretty(string) = string
• Pretty(number) = Racket's number->string applied to number
• Pretty(true) = "true"
• Pretty(false) = "false"
• Pretty({string : value, ...}) = "object"
• Pretty(lambda^environment (identifier, ...) { expression }) = "function"