spec

Informal specification

This is based off of section 2 of Plotkin's paper, entitled "2. The programming language, PCF".

Plotkin's paper doesn't provide a concrete syntax, so we make one up.

Additionally, we add two builtins to the language, which is allowed by section 2:

• let: for ease of writing code. It's sugar for abstracting and applying, and not polymorphic.

• polymorphic if/then/else: because having only two monomorphic if/then/else constructs (one that returns Bool and one that returns Nat) would be sad.

Examples are provided at ./spec/examples.md.

They're also available in JSON form for building test suites.

Writing your own

Your implementation should take PCF on STDIN and then do one of three things:

1. Exit with exit code 2 if the syntax is invalid.

2. Exit with exit code 3 if the program doesn't typecheck.

3. Print the evaluated input to STDOUT otherwise.

A few notes:

• You can write anything to STDERR you want.

• The only output that must be formatted a particular way is booleans and natural numbers. They must be followed by a single newline.

  For example:

  true
  

  Or:

  123
  

  If given a program that evaluates to anything else (like a lambda) you can print it however you want.

If you start on your own implementation definitely let me know. Once you're ready I'll mention it here.

Testing your implementation

The test-cases come in JSON form so you can hook them into your test suite. This way you get the standard tests, but in the interface you expect.

There's also an executable provideds for testing your implementation, though the output isn't very pretty.

Run it via:

stack install
acme-pcf-test <your-implementation>

Example output:

# Parse tests
+ var <passed>
+ lam <passed>
+ app <passed>
+ app2 <passed>
<etc>

# Typecheck tests
+ bool-literal <passed>
+ is-zero <passed>
+ app-not-function <passed>

# Evaluation tests
+ lam <passed>
+ app <passed>
+ let <passed>
<etc>

Note on the examples

They're generated by the Haskell code, so if you make a PR don't change them by hand.