Language Specification (Spring 2025) - stchang/450lang GitHub Wiki

This page contains the #lang 450lang programming language specification for Spring 2025.

Much of it is written in terms of Data Definitions, as in lectures and assignments. Some semantics will be described with the syntax when it is easier to do so.

The input syntax is s-expression data and is presented here as such, but the language allows programmers to write code without the leading "quote".

• A Program is a List<TopLevelForm>
  • Represents what the programmer writes, which can be either an Expression, or a (variant of) bind/rec that associates a variable with an Expression.
• A TopLevelForm is either a:
  • `(bind/rec ,Var ,Expr)
    • This top-level bind/rec does not have a "body"; instead the introduced variable has global scope analogous to Racket's define.
  • Expression
• An Expression (Expr) is one of:
  • Atom, which is one of:
    • Number
    • String
    • 'TRUE!
    • 'FALSE!
    • mt
      • Represents the empty list
  • Variable (Var), which is a Symbol
  • `(bind [,Var ,Expr] ,Expr)
    • defines a variable that is visible in the second Expr
  • `(bind/rec [,Var ,Expr] ,Expr)
    • defines a recursive variable that is visible in both the first and second Exprs
  • `(lm ,List<Var> ,Expr)
    • a user-defined "lambda" function
  • `(iffy ,Expr ,Expr ,Expr)
    • conditional that follows JS "truthy" (and "falsy") semantics
  • `(∧ ,Expr ...)
    • short-circuiting logical "and" (so it can't be a function), analogous to Racket's and
    • accepts any number of arguments
    • symbol is unicode "wedge", written with \wedge + ctrl-\ in DrRacket
  • `(∨ ,Expr ...)
    • short-circuiting logical "or" (so it can't be a function), analogous to Racket's or
    • accepts any number of arguments
    • symbol is unicode "vee", written with \vee + ctrl-\ in DrRacket
  • (cons Expr List<Expr)
    • a function call, where the function may either be a "built-in" Racket function, or a user-defined lm "lambda"

The Expression data definition is analogous to Program in previous assignments, when we did not have "top-level" definitions

450lang semantics borrows ideas from many other programming languages.

• "arithmetic" operations like "plus", "times", and others follows JS coercion semantics (according to repljs.com) and the behavior differs depending on the type(s) of the input(s). They may also produce NaN with some types of inputs.
• The iffy conditional test follows JavaScript "truthy" and "falsy" semantics.
• The ~= equality operator follows JS "loose" equality
• lm behaves like Racket's lambda
• bind behaves like (a singular version of) Racket's let
• bind/rec behaves like (a singular version of) Racket's letrec

When run, 450lang programs produce Results, many of which are borrowed from Racket.

• A Result is one of:
  • (Racket) Number
  • (Racket) String
  • (Racket) Boolean
  • (Racket) List
  • NaN
  • A FnResult is one of:
    • Racket function
    • (lm-result List<Symbol> AST Env)
  • ErrorResult
    • UNDEF-ERR
      • An "undefined" error should occur when trying to use an undefined variable.
    • NOT-FN-ERR
      • A "not fn" error should occur if attempting to call a non-function.
    • ARITY-ERR
      • An "arity" error should occur if attempting to call a function with the wrong number of arguments. Note that many functions in the initial environment are "variable arity", which means they accept any number of arguments, and thus should not generate this error. But user-defined lm functions must be given the exact number of requirement arguments when called.
    • CIRCULAR-ERR
      • A "circular" error occurs when using bind/rec incorrectly (e.g., without a base case).

Note that an environment is a runtime data structure that contains in-scope bindings (though programmers do not have direct access to it). Formally:

• An Environment (Env) is a List<(list Var EnvVal)>
• An EnvVal is either:
  • Result
  • Box<Result>
  • The second case is needed by bind/rec to define recursive functions.

A programming language with no "built in" functions, i.e., an empty initial environment, is not very useful.

• As mentioned, +, ×, and other arithmetic primitive operations follow JS coercion semantics. When given lists, + appends lists together when all the arguments are lists. Further, when given a mix of lists and strings, the list elements are converted to strings and then "joined" together with commas (test it for yourself in JS!). For other non-number arguments, arithmetic functions follow the JS semantics at repljs.com and may produce NaN.

In addition to the primitives from previous assignments (+, ×, ~=), here are other primitives in the INIT-ENV initial environment (note that the added some most of the following primitives directly correspond to a Racket function and its behavior; unless otherwise indicated, they do not follow JS semantics; when it's not obvious, we indicate the Racket function it’s associated with):

• list functions and constants: 1st, 2nd, rst, mt (i.e., "empty"), cns (i.e., "cons"), li (i.e., "list")
• comparison: <=, <, >, >=
• boolean: ¬ (negation)
  • symbol is unicode "neg", written with \neg + ctrl-\ in DrRacket
  • results in true for JS "falsy" values, and false otherwise
• arithmetic: abs, -- (i.e., "sub1"), ++ (i.e., "add1") (the last two perform JS coercions in the same manner as their - and + counterparts)

450lang includes some testing forms that are mapped to rackunit, that enable writing tests and examples.

• A chk= primitive, mapped to check-equal? from rackunit is available.
• in addition there's chk, which is mapped to check-true and chknot which is analogous to check-false
• The language includes some error predicates to further help with testing
  • UNDEF-ERR?
  • NOT-FN-ERR?
  • ARITY-ERR?
  • CIRCULAR-ERR?
  • NaN?