Safe HaskellNone

Chi

Description

A wrapper module that exports the generated abstract syntax of χ as well as some definitions that may be useful when testing χ code or interpreters.

Synopsis

The abstract syntax of χ

module AbsChi

Parsing and pretty-printing

parse ∷ String → Exp #

Tries to parse a χ program. If parsing fails, then an exception is raised.

prettyExp → String #

Pretty-prints a χ program.

An example

addExp #

A χ program for addition of natural numbers.

Conversions

fromNatural ∷ Natural → Exp #

Converts a Haskell natural number to its χ representation.

toNaturalExp → Maybe Natural #

Tries to convert the given χ expression to a natural number.

data Code a #

Encoding monad.

Instances

Instances details
Monad Code # 
Instance details

Defined in Chi

Methods

(>>=)Code a → (a → Code b) → Code b

(>>)Code a → Code b → Code b

return ∷ a → Code a

Functor Code # 
Instance details

Defined in Chi

Methods

fmap ∷ (a → b) → Code a → Code b

(<$) ∷ a → Code b → Code a

Applicative Code # 
Instance details

Defined in Chi

Methods

pure ∷ a → Code a

(<*>)Code (a → b) → Code a → Code b

liftA2 ∷ (a → b → c) → Code a → Code b → Code c

(*>)Code a → Code b → Code b

(<*)Code a → Code b → Code a

data Decode a #

Decoding monad.

Instances

Instances details
Monad Decode # 
Instance details

Defined in Chi

Methods

(>>=)Decode a → (a → Decode b) → Decode b

(>>)Decode a → Decode b → Decode b

return ∷ a → Decode a

Functor Decode # 
Instance details

Defined in Chi

Methods

fmap ∷ (a → b) → Decode a → Decode b

(<$) ∷ a → Decode b → Decode a

Applicative Decode # 
Instance details

Defined in Chi

Methods

pure ∷ a → Decode a

(<*>)Decode (a → b) → Decode a → Decode b

liftA2 ∷ (a → b → c) → Decode a → Decode b → Decode c

(*>)Decode a → Decode b → Decode b

(<*)Decode a → Decode b → Decode a

Alternative Decode # 
Instance details

Defined in Chi

Methods

emptyDecode a

(<|>)Decode a → Decode a → Decode a

someDecode a → Decode [a]

manyDecode a → Decode [a]

runCodeCode a → a #

Runs a coder.

Note that coding might not give consistent results if you invoke runCode multiple times. For instance, the following code will return False:

  runCode (code (parse "Suc(Zero())"))
    ==
  runCode (do
    code (parse "Zero()")
    code (parse "Suc(Zero())"))

runDecodeDecode a → Maybe a #

Runs a decoder. Note that decoders can fail.

asDecoderCode a → Decode a #

Turns a coder into a decoder.

Example usage:

  do e <- asDecoder (code e)
     decode (eval (Apply selfInterpreter e))

codeExpCode Exp #

Encodes expressions.

decodeExpDecode Exp #

Decodes expressions.

codeVarVariableCode Exp #

Encodes variables.

codeConConstructorCode Exp #

Encodes constructors.

decodeVarExpDecode Variable #

Decodes variables.

decodeConExpDecode Constructor #

Decodes constructors.

internalCodeCode Exp #

An internal implementation of coding.

Example usage:

  runCode $ do
    ic <- internalCode
    ce <- code e
    return (eval (Apply ic ce))

Free and bound variables

freeExp → HashSet Variable #

The term's free variables.

boundExp → HashSet Variable #

Bound variables that actually occur bound in the term (not in a binder). For λx.x a singleton set containing x is returned, but for λx.Nil() the empty set is returned.

closed ∷ Gen Exp #

A QuickCheck generator for closed terms.

Functions that can be used to run internal substitution functions and self-interpreters

runInternalSubstitution #

Arguments

∷ (ExpExp)

Evaluation.

Exp

Internal substitution.

Variable

The variable.

Exp

The closed expression that should be substituted for the variable (not in coded form).

Exp

The possibly open expression in which the closed expression should be substituted for the variable (not in coded form).

→ Maybe Exp 

Tries to compute the value of the given internal substitution function applied to the given arguments.

If the application terminates, and the result can be decoded, then this result is returned.

Example usage:

  runInternalSubstitution eval internalSubst
    (Variable "plus") add (parse "plus")

runSelfInterpreter #

Arguments

∷ (ExpExp)

An implementation of evaluation.

Exp

The self-interpreter.

Exp

The program to be evaluated (not in coded form).

→ [Exp]

The program's arguments (not in coded form).

→ Maybe Exp 

Uses a self-interpreter to evaluate a program applied to some arguments.

If the self-interpreter terminates, and the result can be decoded, then this result is returned.

Example usage:

  do n <- runSelfInterpreter eval selfInterpreter add
            [fromNatural 2, fromNatural 2]
     toNatural n

Some testing procedures

testEvaluation ∷ (ExpExp) → IO Bool #

Tests whether a purported implementation of evaluation can evaluate addition of two natural numbers (add) correctly.

The test is, of course, incomplete.

testMultiplication #

Arguments

∷ (ExpExp)

Evaluation.

Exp

Multiplication. The program should take two natural numbers as input and produce a natural number as its result.

→ IO Bool 

Tests whether a purported implementation of evaluation and a purported implementation of multiplication of two natural numbers are correct.

The test is, of course, incomplete.

testSubstitution ∷ (VariableExpExpExp) → IO Bool #

Tests a purported implementation of substitution.

The substitution operation takes three arguments, x, e and e', where e is closed, and should substitute e for every free occurrence of x in e'.

The test is designed for substitution operations that are implemented exactly like in the χ specification. In particular, the substitution operation should not rename any bound variables.

The test is, of course, incomplete.

testInternalSubstitutionWith #

Arguments

∷ (ExpExp)

Evaluation.

→ (VariableExpExpExp)

Substitution.

Exp

Internal substitution.

Variable

The variable.

Exp

The closed expression that should be substituted for the variable (not in coded form).

Exp

The possibly open expression in which the closed expression should be substituted for the variable (not in coded form).

→ Bool 

Tests if the result of the given internal substitution function matches that of the given substitution function for given inputs.

Note that no result is returned if some program crashes or fails to terminate.

Example usage:

  testInternalSubstitutionWith eval subst internalSubst
    (Variable "plus") add (parse "plus")

testInternalSubstitution #

Arguments

∷ (ExpExp)

Evaluation.

→ (VariableExpExpExp)

Substitution.

Exp

Internal substitution.

→ IO Bool 

Tests whether an implementation of internal substitution matches an implementation of substitution.

The test is, of course, incomplete.

testSelfInterpreterWith #

Arguments

∷ (ExpExp)

Evaluation.

Exp

The self-interpreter.

Exp

The program to be evaluated (not in coded form).

→ [Exp]

The arguments (not in coded form).

→ Bool 

Tests if the result of the given self-interpreter matches that of the given evaluator for a program applied to some arguments.

Note that no result is returned if some program crashes or fails to terminate.

Example usage:

  testSelfInterpreterWith eval selfInterpreter add
    [fromNatural 2, fromNatural 2]

testSelfInterpreter #

Arguments

∷ (ExpExp)

Evaluation.

Exp

The self-interpreter.

→ IO Bool 

Tests whether a purported implementation of evaluation and a purported self-interpreter are correctly implemented.

The test is, of course, incomplete.

testTuringMachineInterpreter #

Arguments

∷ (ExpExp)

Evaluation.

Exp

The Turing machine interpreter.

→ IO Bool 

Tests whether a purported implementation of evaluation and a purported Turing machine interpreter are correctly implemented. The Turing machine interpreter should satisfy the specification given in Assignment 6.

The test is, of course, incomplete.

Orphan instances

Generic Br # 
Instance details

Associated Types

type Rep Br ∷ Type → Type

Methods

fromBr → Rep Br x

to ∷ Rep Br x → Br

Generic Exp # 
Instance details

Associated Types

type Rep Exp ∷ Type → Type

Methods

fromExp → Rep Exp x

to ∷ Rep Exp x → Exp

Generic Variable # 
Instance details

Associated Types

type Rep Variable ∷ Type → Type

Methods

fromVariable → Rep Variable x

to ∷ Rep Variable x → Variable

Generic Constructor # 
Instance details

Associated Types

type Rep Constructor ∷ Type → Type

Methods

fromConstructor → Rep Constructor x

to ∷ Rep Constructor x → Constructor

Hashable Variable # 
Instance details

Methods

hashWithSalt ∷ Int → Variable → Int

hashVariable → Int

Hashable Constructor # 
Instance details

Methods

hashWithSalt ∷ Int → Constructor → Int

hashConstructor → Int

Arbitrary Br #

A QuickCheck generator for branches.

Instance details

Methods

arbitrary ∷ Gen Br

shrinkBr → [Br]

Arbitrary Exp #

A QuickCheck generator for terms.

Instance details

Methods

arbitrary ∷ Gen Exp

shrinkExp → [Exp]

Arbitrary Variable #

A QuickCheck generator for (a small number of) variables.

Instance details

Methods

arbitrary ∷ Gen Variable

shrinkVariable → [Variable]

Arbitrary Constructor #

A QuickCheck generator for (a small number of) constructors.

Instance details