summaryrefslogtreecommitdiff
path: root/dhall
diff options
context:
space:
mode:
authorNadrieril Feneanar2020-01-31 20:22:09 +0000
committerGitHub2020-01-31 20:22:09 +0000
commit72a6fef65bb3d34be1f501a1f6de66fb8a54fa04 (patch)
tree033314a3e3254e8fcf1154d1570a720b058db4d9 /dhall
parent140b5d5ab24795a4053f7e5bdcd8b2343e35558e (diff)
parent0c0e7d4db15abf709fafc0c9b9db4d377ea3c158 (diff)
Rewrite normalization and typechecking with environments (#126)
Rewrite normalization and typechecking with environments
Diffstat (limited to 'dhall')
-rw-r--r--dhall/Cargo.toml2
-rw-r--r--dhall/build.rs8
l---------dhall/src/dhall.abnf1
-rw-r--r--dhall/src/error/mod.rs126
-rw-r--r--dhall/src/lib.rs241
-rw-r--r--dhall/src/semantics/builtins.rs540
-rw-r--r--dhall/src/semantics/core/context.rs144
-rw-r--r--dhall/src/semantics/core/mod.rs3
-rw-r--r--dhall/src/semantics/core/value.rs591
-rw-r--r--dhall/src/semantics/core/var.rs295
-rw-r--r--dhall/src/semantics/mod.rs11
-rw-r--r--dhall/src/semantics/nze/env.rs76
-rw-r--r--dhall/src/semantics/nze/lazy.rs64
-rw-r--r--dhall/src/semantics/nze/mod.rs9
-rw-r--r--dhall/src/semantics/nze/normalize.rs421
-rw-r--r--dhall/src/semantics/nze/value.rs656
-rw-r--r--dhall/src/semantics/nze/var.rs36
-rw-r--r--dhall/src/semantics/parse.rs (renamed from dhall/src/semantics/phase/parse.rs)4
-rw-r--r--dhall/src/semantics/phase/mod.rs259
-rw-r--r--dhall/src/semantics/phase/normalize.rs791
-rw-r--r--dhall/src/semantics/phase/typecheck.rs838
-rw-r--r--dhall/src/semantics/resolve.rs (renamed from dhall/src/semantics/phase/resolve.rs)2
-rw-r--r--dhall/src/semantics/tck/env.rs124
-rw-r--r--dhall/src/semantics/tck/mod.rs6
-rw-r--r--dhall/src/semantics/tck/tyexpr.rs137
-rw-r--r--dhall/src/semantics/tck/typecheck.rs611
-rw-r--r--dhall/src/semantics/to_expr.rs105
-rw-r--r--dhall/src/syntax/ast/expr.rs84
-rw-r--r--dhall/src/syntax/ast/visitor.rs42
-rw-r--r--dhall/src/syntax/binary/decode.rs2
l---------dhall/src/syntax/text/dhall.abnf1
-rw-r--r--dhall/src/syntax/text/dhall.pest.visibility (renamed from dhall/src/dhall.pest.visibility)0
-rw-r--r--dhall/src/syntax/text/parser.rs4
-rw-r--r--dhall/src/syntax/text/printer.rs2
-rw-r--r--dhall/src/tests.rs23
-rw-r--r--dhall/tests/type-errors/hurkensParadox.txt9
-rw-r--r--dhall/tests/type-errors/mixedUnions.txt2
-rw-r--r--dhall/tests/type-errors/unit/AnnotationRecordWrongFieldName.txt2
-rw-r--r--dhall/tests/type-errors/unit/AnnotationRecordWrongFieldType.txt2
-rw-r--r--dhall/tests/type-errors/unit/AssertAlphaTrap.txt7
-rw-r--r--dhall/tests/type-errors/unit/AssertDoubleZeros.txt2
-rw-r--r--dhall/tests/type-errors/unit/AssertTriviallyFalse.txt2
-rw-r--r--dhall/tests/type-errors/unit/EquivalenceNotSameType.txt2
-rw-r--r--dhall/tests/type-errors/unit/EquivalenceNotTerms.txt2
-rw-r--r--dhall/tests/type-errors/unit/FunctionApplicationArgumentNotMatch.txt14
-rw-r--r--dhall/tests/type-errors/unit/FunctionApplicationIsNotFunction.txt7
-rw-r--r--dhall/tests/type-errors/unit/FunctionArgumentTypeNotAType.txt7
-rw-r--r--dhall/tests/type-errors/unit/FunctionTypeArgumentTypeNotAType.txt7
-rw-r--r--dhall/tests/type-errors/unit/IfBranchesNotMatch.txt2
-rw-r--r--dhall/tests/type-errors/unit/IfBranchesNotType.txt2
-rw-r--r--dhall/tests/type-errors/unit/IfNotBool.txt2
-rw-r--r--dhall/tests/type-errors/unit/LetWithWrongAnnotation.txt2
-rw-r--r--dhall/tests/type-errors/unit/ListLiteralEmptyNotType.txt14
-rw-r--r--dhall/tests/type-errors/unit/ListLiteralNotType.txt2
-rw-r--r--dhall/tests/type-errors/unit/ListLiteralTypesNotMatch.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeAlternativeHasNoHandler.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeAnnotationNotType.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeEmptyWithoutAnnotation.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeHandlerFreeVar.txt1
-rw-r--r--dhall/tests/type-errors/unit/MergeHandlerNotFunction.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeHandlerNotInUnion.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeHandlerNotMatchAlternativeType.txt14
-rw-r--r--dhall/tests/type-errors/unit/MergeLhsNotRecord.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeMissingHandler1.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeMissingHandler2.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeRhsNotUnion.txt2
-rw-r--r--dhall/tests/type-errors/unit/MergeUnusedHandler.txt2
-rw-r--r--dhall/tests/type-errors/unit/NaturalSubtractNotNatural.txt14
-rw-r--r--dhall/tests/type-errors/unit/OperatorAndNotBool.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorEqualNotBool.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorListConcatenateLhsNotList.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorListConcatenateListsNotMatch.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorListConcatenateNotListsButMatch.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorListConcatenateRhsNotList.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorNotEqualNotBool.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorOrNotBool.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorPlusNotNatural.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorTextConcatenateLhsNotText.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorTextConcatenateRhsNotText.txt2
-rw-r--r--dhall/tests/type-errors/unit/OperatorTimesNotNatural.txt2
-rw-r--r--dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxAbsent.txt2
-rw-r--r--dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxPresent.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecordSelectionEmpty.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecordSelectionNotPresent.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecordSelectionNotRecord.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecordSelectionTypeNotUnionType.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecordTypeValueMember.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecursiveRecordMergeLhsNotRecord.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecursiveRecordMergeOverlapping.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecursiveRecordMergeRhsNotRecord.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecursiveRecordTypeMergeLhsNotRecordType.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecursiveRecordTypeMergeOverlapping.txt2
-rw-r--r--dhall/tests/type-errors/unit/RecursiveRecordTypeMergeRhsNotRecordType.txt2
-rw-r--r--dhall/tests/type-errors/unit/RightBiasedRecordMergeLhsNotRecord.txt2
-rw-r--r--dhall/tests/type-errors/unit/RightBiasedRecordMergeRhsNotRecord.txt2
-rw-r--r--dhall/tests/type-errors/unit/SomeNotType.txt2
-rw-r--r--dhall/tests/type-errors/unit/TextLiteralInterpolateNotText.txt2
-rw-r--r--dhall/tests/type-errors/unit/TypeAnnotationWrong.txt2
-rw-r--r--dhall/tests/type-errors/unit/UnionConstructorFieldNotPresent.txt2
-rw-r--r--dhall/tests/type-errors/unit/UnionDeprecatedConstructorsKeyword.txt7
-rw-r--r--dhall/tests/type-errors/unit/UnionTypeMixedKinds.txt2
-rw-r--r--dhall/tests/type-errors/unit/UnionTypeMixedKinds2.txt2
-rw-r--r--dhall/tests/type-errors/unit/UnionTypeMixedKinds3.txt2
-rw-r--r--dhall/tests/type-errors/unit/UnionTypeNotType.txt2
-rw-r--r--dhall/tests/type-errors/unit/VariableFree.txt7
105 files changed, 3131 insertions, 3352 deletions
diff --git a/dhall/Cargo.toml b/dhall/Cargo.toml
index b795898..2fbfb23 100644
--- a/dhall/Cargo.toml
+++ b/dhall/Cargo.toml
@@ -13,13 +13,13 @@ build = "build.rs"
itertools = "0.8.0"
hex = "0.3.2"
lazy_static = "1.4.0"
+ once_cell = "1.3.1"
percent-encoding = "2.1.0"
pest = "2.1"
pest_consume = "1.0"
serde = "1.0"
serde_cbor = "0.9.0"
smallvec = "1.0.0"
-take_mut = "0.2.2"
[dev-dependencies]
pretty_assertions = "0.6.1"
diff --git a/dhall/build.rs b/dhall/build.rs
index c95a26d..8992f22 100644
--- a/dhall/build.rs
+++ b/dhall/build.rs
@@ -339,6 +339,8 @@ fn generate_tests() -> std::io::Result<()> {
|| path == "unit/CompletionWithWrongDefaultType"
|| path == "unit/CompletionWithWrongFieldName"
|| path == "unit/CompletionWithWrongOverridenType"
+ // TODO: enable free variable checking
+ || path == "unit/MergeHandlerFreeVar"
}),
input_type: FileType::Text,
output_type: None,
@@ -367,6 +369,8 @@ fn generate_tests() -> std::io::Result<()> {
|| path == "unit/CompletionWithWrongDefaultType"
|| path == "unit/CompletionWithWrongFieldName"
|| path == "unit/CompletionWithWrongOverridenType"
+ // TODO: enable free variable checking
+ || path == "unit/MergeHandlerFreeVar"
}),
input_type: FileType::Text,
output_type: None,
@@ -383,8 +387,8 @@ fn generate_tests() -> std::io::Result<()> {
fn convert_abnf_to_pest() -> std::io::Result<()> {
let out_dir = env::var("OUT_DIR").unwrap();
- let abnf_path = "src/dhall.abnf";
- let visibility_path = "src/dhall.pest.visibility";
+ let abnf_path = "src/syntax/text/dhall.abnf";
+ let visibility_path = "src/syntax/text/dhall.pest.visibility";
let grammar_path = Path::new(&out_dir).join("dhall.pest");
println!("cargo:rerun-if-changed={}", abnf_path);
println!("cargo:rerun-if-changed={}", visibility_path);
diff --git a/dhall/src/dhall.abnf b/dhall/src/dhall.abnf
deleted file mode 120000
index ce13b8e..0000000
--- a/dhall/src/dhall.abnf
+++ /dev/null
@@ -1 +0,0 @@
-../../dhall-lang/standard/dhall.abnf \ No newline at end of file
diff --git a/dhall/src/error/mod.rs b/dhall/src/error/mod.rs
index 6e7be64..4df018d 100644
--- a/dhall/src/error/mod.rs
+++ b/dhall/src/error/mod.rs
@@ -1,10 +1,9 @@
use std::io::Error as IOError;
-use crate::semantics::core::context::TypecheckContext;
-use crate::semantics::core::value::Value;
-use crate::semantics::phase::resolve::ImportStack;
-use crate::semantics::phase::NormalizedExpr;
-use crate::syntax::{BinOp, Import, Label, ParseError, Span};
+use crate::semantics::resolve::ImportStack;
+use crate::semantics::Value;
+use crate::syntax::{Import, ParseError};
+use crate::NormalizedExpr;
pub type Result<T> = std::result::Result<T, Error>;
@@ -37,65 +36,59 @@ pub enum EncodeError {
CBORError(serde_cbor::error::Error),
}
-/// A structured type error that includes context
+/// A structured type error
#[derive(Debug)]
pub struct TypeError {
message: TypeMessage,
- context: TypecheckContext,
}
/// The specific type error
#[derive(Debug)]
pub(crate) enum TypeMessage {
- UnboundVariable(Span),
+ // UnboundVariable(Span),
InvalidInputType(Value),
InvalidOutputType(Value),
- NotAFunction(Value),
- TypeMismatch(Value, Value, Value),
- AnnotMismatch(Value, Value),
- InvalidListElement(usize, Value, Value),
- InvalidListType(Value),
- InvalidOptionalType(Value),
- InvalidPredicate(Value),
- IfBranchMismatch(Value, Value),
- IfBranchMustBeTerm(bool, Value),
- InvalidFieldType(Label, Value),
- NotARecord(Label, Value),
- MustCombineRecord(Value),
- MissingRecordField(Label, Value),
- MissingUnionField(Label, Value),
- BinOpTypeMismatch(BinOp, Value),
- InvalidTextInterpolation(Value),
- Merge1ArgMustBeRecord(Value),
- Merge2ArgMustBeUnionOrOptional(Value),
- MergeEmptyNeedsAnnotation,
- MergeHandlerMissingVariant(Label),
- MergeVariantMissingHandler(Label),
- MergeAnnotMismatch,
- MergeHandlerTypeMismatch,
- MergeHandlerReturnTypeMustNotBeDependent,
- ProjectionMustBeRecord,
- ProjectionMissingEntry,
- ProjectionDuplicateField,
+ // NotAFunction(Value),
+ // TypeMismatch(Value, Value, Value),
+ // AnnotMismatch(Value, Value),
+ // InvalidListElement(usize, Value, Value),
+ // InvalidListType(Value),
+ // InvalidOptionalType(Value),
+ // InvalidPredicate(Value),
+ // IfBranchMismatch(Value, Value),
+ // IfBranchMustBeTerm(bool, Value),
+ // InvalidFieldType(Label, Value),
+ // NotARecord(Label, Value),
+ // MustCombineRecord(Value),
+ // MissingRecordField(Label, Value),
+ // MissingUnionField(Label, Value),
+ // BinOpTypeMismatch(BinOp, Value),
+ // InvalidTextInterpolation(Value),
+ // Merge1ArgMustBeRecord(Value),
+ // Merge2ArgMustBeUnionOrOptional(Value),
+ // MergeEmptyNeedsAnnotation,
+ // MergeHandlerMissingVariant(Label),
+ // MergeVariantMissingHandler(Label),
+ // MergeAnnotMismatch,
+ // MergeHandlerTypeMismatch,
+ // MergeHandlerReturnTypeMustNotBeDependent,
+ // ProjectionMustBeRecord,
+ // ProjectionMissingEntry,
+ // ProjectionDuplicateField,
Sort,
- RecordTypeDuplicateField,
- RecordTypeMergeRequiresRecordType(Value),
- UnionTypeDuplicateField,
- EquivalenceArgumentMustBeTerm(bool, Value),
- EquivalenceTypeMismatch(Value, Value),
- AssertMismatch(Value, Value),
- AssertMustTakeEquivalence,
+ // RecordTypeDuplicateField,
+ // RecordTypeMergeRequiresRecordType(Value),
+ // UnionTypeDuplicateField,
+ // EquivalenceArgumentMustBeTerm(bool, Value),
+ // EquivalenceTypeMismatch(Value, Value),
+ // AssertMismatch(Value, Value),
+ // AssertMustTakeEquivalence,
+ Custom(String),
}
impl TypeError {
- pub(crate) fn new(
- context: &TypecheckContext,
- message: TypeMessage,
- ) -> Self {
- TypeError {
- context: context.clone(),
- message,
- }
+ pub(crate) fn new(message: TypeMessage) -> Self {
+ TypeError { message }
}
}
@@ -103,28 +96,29 @@ impl std::fmt::Display for TypeError {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
use TypeMessage::*;
let msg = match &self.message {
- UnboundVariable(span) => span.error("Type error: Unbound variable"),
+ // UnboundVariable(var) => var.error("Type error: Unbound variable"),
InvalidInputType(v) => {
v.span().error("Type error: Invalid function input")
}
InvalidOutputType(v) => {
v.span().error("Type error: Invalid function output")
}
- NotAFunction(v) => v.span().error("Type error: Not a function"),
- TypeMismatch(x, y, z) => {
- x.span()
- .error("Type error: Wrong type of function argument")
- + "\n"
- + &z.span().error(format!(
- "This argument has type {:?}",
- z.get_type().unwrap()
- ))
- + "\n"
- + &y.span().error(format!(
- "But the function expected an argument of type {:?}",
- y
- ))
- }
+ // NotAFunction(v) => v.span().error("Type error: Not a function"),
+ // TypeMismatch(x, y, z) => {
+ // x.span()
+ // .error("Type error: Wrong type of function argument")
+ // + "\n"
+ // + &z.span().error(format!(
+ // "This argument has type {:?}",
+ // z.get_type().unwrap()
+ // ))
+ // + "\n"
+ // + &y.span().error(format!(
+ // "But the function expected an argument of type {:?}",
+ // y
+ // ))
+ // }
+ Custom(s) => format!("Type error: Unhandled error: {}", s),
_ => format!("Type error: Unhandled error: {:?}", self.message),
};
write!(f, "{}", msg)
diff --git a/dhall/src/lib.rs b/dhall/src/lib.rs
index 62a1b27..dbf1fc0 100644
--- a/dhall/src/lib.rs
+++ b/dhall/src/lib.rs
@@ -16,3 +16,244 @@ mod tests;
pub mod error;
pub mod semantics;
pub mod syntax;
+
+use std::fmt::Display;
+use std::path::Path;
+
+use crate::error::{EncodeError, Error, ImportError, TypeError};
+use crate::semantics::parse;
+use crate::semantics::resolve;
+use crate::semantics::resolve::ImportRoot;
+use crate::semantics::{typecheck, typecheck_with, TyExpr, Value, ValueKind};
+use crate::syntax::binary;
+use crate::syntax::{Builtin, Const, Expr};
+
+pub type ParsedExpr = Expr<Normalized>;
+pub type DecodedExpr = Expr<Normalized>;
+pub type ResolvedExpr = Expr<Normalized>;
+pub type NormalizedExpr = Expr<Normalized>;
+
+#[derive(Debug, Clone)]
+pub struct Parsed(ParsedExpr, ImportRoot);
+
+/// An expression where all imports have been resolved
+///
+/// Invariant: there must be no `Import` nodes or `ImportAlt` operations left.
+#[derive(Debug, Clone)]
+pub struct Resolved(ResolvedExpr);
+
+/// A typed expression
+#[derive(Debug, Clone)]
+pub struct Typed(TyExpr);
+
+/// A normalized expression.
+///
+/// Invariant: the contained Typed expression must be in normal form,
+#[derive(Debug, Clone)]
+pub struct Normalized(Value);
+
+/// Controls conversion from `Value` to `Expr`
+#[derive(Copy, Clone)]
+pub(crate) struct ToExprOptions {
+ /// Whether to convert all variables to `_`
+ pub(crate) alpha: bool,
+ /// Whether to normalize before converting
+ pub(crate) normalize: bool,
+}
+
+impl Parsed {
+ pub fn parse_file(f: &Path) -> Result<Parsed, Error> {
+ parse::parse_file(f)
+ }
+ pub fn parse_str(s: &str) -> Result<Parsed, Error> {
+ parse::parse_str(s)
+ }
+ pub fn parse_binary_file(f: &Path) -> Result<Parsed, Error> {
+ parse::parse_binary_file(f)
+ }
+ pub fn parse_binary(data: &[u8]) -> Result<Parsed, Error> {
+ parse::parse_binary(data)
+ }
+
+ pub fn resolve(self) -> Result<Resolved, ImportError> {
+ resolve::resolve(self)
+ }
+ pub fn skip_resolve(self) -> Result<Resolved, ImportError> {
+ resolve::skip_resolve_expr(self)
+ }
+
+ pub fn encode(&self) -> Result<Vec<u8>, EncodeError> {
+ binary::encode(&self.0)
+ }
+
+ /// Converts a value back to the corresponding AST expression.
+ pub fn to_expr(&self) -> ParsedExpr {
+ self.0.clone()
+ }
+}
+
+impl Resolved {
+ pub fn typecheck(&self) -> Result<Typed, TypeError> {
+ Ok(Typed(typecheck(&self.0)?))
+ }
+ pub fn typecheck_with(self, ty: &Normalized) -> Result<Typed, TypeError> {
+ Ok(Typed(typecheck_with(&self.0, ty.to_expr())?))
+ }
+ /// Converts a value back to the corresponding AST expression.
+ pub fn to_expr(&self) -> ResolvedExpr {
+ self.0.clone()
+ }
+}
+
+impl Typed {
+ /// Reduce an expression to its normal form, performing beta reduction
+ pub fn normalize(&self) -> Normalized {
+ Normalized(self.0.rec_eval_closed_expr())
+ }
+
+ /// Converts a value back to the corresponding AST expression.
+ fn to_expr(&self) -> ResolvedExpr {
+ self.0.to_expr(ToExprOptions {
+ alpha: false,
+ normalize: false,
+ })
+ }
+
+ pub(crate) fn get_type(&self) -> Result<Normalized, TypeError> {
+ Ok(Normalized(self.0.get_type()?))
+ }
+}
+
+impl Normalized {
+ pub fn encode(&self) -> Result<Vec<u8>, EncodeError> {
+ binary::encode(&self.to_expr())
+ }
+
+ /// Converts a value back to the corresponding AST expression.
+ pub fn to_expr(&self) -> NormalizedExpr {
+ self.0.to_expr(ToExprOptions {
+ alpha: false,
+ normalize: false,
+ })
+ }
+ /// Converts a value back to the corresponding AST expression, alpha-normalizing in the process.
+ pub(crate) fn to_expr_alpha(&self) -> NormalizedExpr {
+ self.0.to_expr(ToExprOptions {
+ alpha: true,
+ normalize: false,
+ })
+ }
+ pub(crate) fn to_value(&self) -> Value {
+ self.0.clone()
+ }
+ pub(crate) fn into_value(self) -> Value {
+ self.0
+ }
+
+ pub(crate) fn from_const(c: Const) -> Self {
+ Normalized(Value::from_const(c))
+ }
+ pub(crate) fn from_kind_and_type(v: ValueKind, t: Normalized) -> Self {
+ Normalized(Value::from_kind_and_type(v, t.into_value()))
+ }
+ pub(crate) fn from_value(th: Value) -> Self {
+ Normalized(th)
+ }
+ pub(crate) fn const_type() -> Self {
+ Normalized::from_const(Const::Type)
+ }
+
+ pub fn make_builtin_type(b: Builtin) -> Self {
+ Normalized::from_value(Value::from_builtin(b))
+ }
+ pub fn make_optional_type(t: Normalized) -> Self {
+ Normalized::from_value(
+ Value::from_builtin(Builtin::Optional).app(t.to_value()),
+ )
+ }
+ pub fn make_list_type(t: Normalized) -> Self {
+ Normalized::from_value(
+ Value::from_builtin(Builtin::List).app(t.to_value()),
+ )
+ }
+ pub fn make_record_type(
+ kts: impl Iterator<Item = (String, Normalized)>,
+ ) -> Self {
+ Normalized::from_kind_and_type(
+ ValueKind::RecordType(
+ kts.map(|(k, t)| (k.into(), t.into_value())).collect(),
+ ),
+ Normalized::const_type(),
+ )
+ }
+ pub fn make_union_type(
+ kts: impl Iterator<Item = (String, Option<Normalized>)>,
+ ) -> Self {
+ Normalized::from_kind_and_type(
+ ValueKind::UnionType(
+ kts.map(|(k, t)| (k.into(), t.map(|t| t.into_value())))
+ .collect(),
+ ),
+ Normalized::const_type(),
+ )
+ }
+}
+
+macro_rules! derive_traits_for_wrapper_struct {
+ ($ty:ident) => {
+ impl std::cmp::PartialEq for $ty {
+ fn eq(&self, other: &Self) -> bool {
+ self.0 == other.0
+ }
+ }
+
+ impl std::cmp::Eq for $ty {}
+
+ impl std::fmt::Display for $ty {
+ fn fmt(
+ &self,
+ f: &mut std::fmt::Formatter,
+ ) -> Result<(), std::fmt::Error> {
+ self.0.fmt(f)
+ }
+ }
+ };
+}
+
+derive_traits_for_wrapper_struct!(Parsed);
+derive_traits_for_wrapper_struct!(Resolved);
+
+impl std::hash::Hash for Normalized {
+ fn hash<H>(&self, state: &mut H)
+ where
+ H: std::hash::Hasher,
+ {
+ if let Ok(vec) = self.encode() {
+ vec.hash(state)
+ }
+ }
+}
+
+impl Eq for Typed {}
+impl PartialEq for Typed {
+ fn eq(&self, other: &Self) -> bool {
+ self.normalize() == other.normalize()
+ }
+}
+impl Display for Typed {
+ fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+ self.to_expr().fmt(f)
+ }
+}
+
+impl Eq for Normalized {}
+impl PartialEq for Normalized {
+ fn eq(&self, other: &Self) -> bool {
+ self.0 == other.0
+ }
+}
+impl Display for Normalized {
+ fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+ self.to_expr().fmt(f)
+ }
+}
diff --git a/dhall/src/semantics/builtins.rs b/dhall/src/semantics/builtins.rs
new file mode 100644
index 0000000..c20fb77
--- /dev/null
+++ b/dhall/src/semantics/builtins.rs
@@ -0,0 +1,540 @@
+use crate::semantics::{
+ self, typecheck, NzEnv, TyExpr, TyExprKind, Value, ValueKind, VarEnv,
+};
+use crate::syntax::map::DupTreeMap;
+use crate::syntax::Const::Type;
+use crate::syntax::{
+ BinOp, Builtin, Const, Expr, ExprKind, InterpolatedText,
+ InterpolatedTextContents, Label, NaiveDouble, Span, UnspannedExpr, V,
+};
+use crate::Normalized;
+use std::collections::HashMap;
+use std::convert::TryInto;
+
+/// A partially applied builtin.
+/// Invariant: the evaluation of the given args must not be able to progress further
+#[derive(Debug, Clone)]
+pub(crate) struct BuiltinClosure<Value> {
+ pub env: NzEnv,
+ pub b: Builtin,
+ /// Arguments applied to the closure so far.
+ pub args: Vec<Value>,
+ /// Keeps the types of the partial applications around to be able to convert back to TyExpr.
+ /// If the args so far are `x_1`, ..., `x_n`, this contains the types of `b`, `b x1`, ...,
+ /// `b x_1 x_2 ... x_(n-1)`.
+ pub types: Vec<Value>,
+}
+
+impl BuiltinClosure<Value> {
+ pub fn new(b: Builtin, env: NzEnv) -> Self {
+ BuiltinClosure {
+ env,
+ b,
+ args: Vec::new(),
+ types: Vec::new(),
+ }
+ }
+
+ pub fn apply(&self, a: Value, f_ty: Value, ret_ty: &Value) -> ValueKind {
+ use std::iter::once;
+ let args = self.args.iter().cloned().chain(once(a.clone())).collect();
+ let types = self.types.iter().cloned().chain(once(f_ty)).collect();
+ apply_builtin(self.b, args, ret_ty, types, self.env.clone())
+ }
+ /// This doesn't break the invariant because we already checked that the appropriate arguments
+ /// did not normalize to something that allows evaluation to proceed.
+ pub fn normalize(&self) {
+ for x in self.args.iter() {
+ x.normalize();
+ }
+ }
+ pub fn to_tyexprkind(&self, venv: VarEnv) -> TyExprKind {
+ TyExprKind::Expr(self.args.iter().zip(self.types.iter()).fold(
+ ExprKind::Builtin(self.b),
+ |acc, (v, ty)| {
+ ExprKind::App(
+ TyExpr::new(
+ TyExprKind::Expr(acc),
+ Some(ty.clone()),
+ Span::Artificial,
+ ),
+ v.to_tyexpr(venv),
+ )
+ },
+ ))
+ }
+}
+
+pub(crate) fn rc<E>(x: UnspannedExpr<E>) -> Expr<E> {
+ Expr::new(x, Span::Artificial)
+}
+
+// Ad-hoc macro to help construct the types of builtins
+macro_rules! make_type {
+ (Type) => { rc(ExprKind::Const(Const::Type)) };
+ (Bool) => { rc(ExprKind::Builtin(Builtin::Bool)) };
+ (Natural) => { rc(ExprKind::Builtin(Builtin::Natural)) };
+ (Integer) => { rc(ExprKind::Builtin(Builtin::Integer)) };
+ (Double) => { rc(ExprKind::Builtin(Builtin::Double)) };
+ (Text) => { rc(ExprKind::Builtin(Builtin::Text)) };
+ ($var:ident) => {
+ rc(ExprKind::Var(V(stringify!($var).into(), 0)))
+ };
+ (Optional $ty:ident) => {
+ rc(ExprKind::App(
+ rc(ExprKind::Builtin(Builtin::Optional)),
+ make_type!($ty)
+ ))
+ };
+ (List $($rest:tt)*) => {
+ rc(ExprKind::App(
+ rc(ExprKind::Builtin(Builtin::List)),
+ make_type!($($rest)*)
+ ))
+ };
+ ({ $($label:ident : $ty:ident),* }) => {{
+ let mut kts = DupTreeMap::new();
+ $(
+ kts.insert(
+ Label::from(stringify!($label)),
+ make_type!($ty),
+ );
+ )*
+ rc(ExprKind::RecordType(kts))
+ }};
+ ($ty:ident -> $($rest:tt)*) => {
+ rc(ExprKind::Pi(
+ "_".into(),
+ make_type!($ty),
+ make_type!($($rest)*)
+ ))
+ };
+ (($($arg:tt)*) -> $($rest:tt)*) => {
+ rc(ExprKind::Pi(
+ "_".into(),
+ make_type!($($arg)*),
+ make_type!($($rest)*)
+ ))
+ };
+ (forall ($var:ident : $($ty:tt)*) -> $($rest:tt)*) => {
+ rc(ExprKind::Pi(
+ stringify!($var).into(),
+ make_type!($($ty)*),
+ make_type!($($rest)*)
+ ))
+ };
+}
+
+pub(crate) fn type_of_builtin<E>(b: Builtin) -> Expr<E> {
+ use Builtin::*;
+ match b {
+ Bool | Natural | Integer | Double | Text => make_type!(Type),
+ List | Optional => make_type!(
+ Type -> Type
+ ),
+
+ NaturalFold => make_type!(
+ Natural ->
+ forall (natural: Type) ->
+ forall (succ: natural -> natural) ->
+ forall (zero: natural) ->
+ natural
+ ),
+ NaturalBuild => make_type!(
+ (forall (natural: Type) ->
+ forall (succ: natural -> natural) ->
+ forall (zero: natural) ->
+ natural) ->
+ Natural
+ ),
+ NaturalIsZero | NaturalEven | NaturalOdd => make_type!(
+ Natural -> Bool
+ ),
+ NaturalToInteger => make_type!(Natural -> Integer),
+ NaturalShow => make_type!(Natural -> Text),
+ NaturalSubtract => make_type!(Natural -> Natural -> Natural),
+
+ IntegerToDouble => make_type!(Integer -> Double),
+ IntegerShow => make_type!(Integer -> Text),
+ IntegerNegate => make_type!(Integer -> Integer),
+ IntegerClamp => make_type!(Integer -> Natural),
+
+ DoubleShow => make_type!(Double -> Text),
+ TextShow => make_type!(Text -> Text),
+
+ ListBuild => make_type!(
+ forall (a: Type) ->
+ (forall (list: Type) ->
+ forall (cons: a -> list -> list) ->
+ forall (nil: list) ->
+ list) ->
+ List a
+ ),
+ ListFold => make_type!(
+ forall (a: Type) ->
+ (List a) ->
+ forall (list: Type) ->
+ forall (cons: a -> list -> list) ->
+ forall (nil: list) ->
+ list
+ ),
+ ListLength => make_type!(forall (a: Type) -> (List a) -> Natural),
+ ListHead | ListLast => {
+ make_type!(forall (a: Type) -> (List a) -> Optional a)
+ }
+ ListIndexed => make_type!(
+ forall (a: Type) ->
+ (List a) ->
+ List { index: Natural, value: a }
+ ),
+ ListReverse => make_type!(
+ forall (a: Type) -> (List a) -> List a
+ ),
+
+ OptionalBuild => make_type!(
+ forall (a: Type) ->
+ (forall (optional: Type) ->
+ forall (just: a -> optional) ->
+ forall (nothing: optional) ->
+ optional) ->
+ Optional a
+ ),
+ OptionalFold => make_type!(
+ forall (a: Type) ->
+ (Optional a) ->
+ forall (optional: Type) ->
+ forall (just: a -> optional) ->
+ forall (nothing: optional) ->
+ optional
+ ),
+ OptionalNone => make_type!(
+ forall (A: Type) -> Optional A
+ ),
+ }
+}
+
+// Ad-hoc macro to help construct closures
+macro_rules! make_closure {
+ (var($var:ident)) => {{
+ rc(ExprKind::Var(V(
+ Label::from(stringify!($var)).into(),
+ 0
+ )))
+ }};
+ (λ($var:tt : $($ty:tt)*) -> $($body:tt)*) => {{
+ let var = Label::from(stringify!($var));
+ let ty = make_closure!($($ty)*);
+ let body = make_closure!($($body)*);
+ rc(ExprKind::Lam(var, ty, body))
+ }};
+ (Type) => {
+ rc(ExprKind::Const(Type))
+ };
+ (Natural) => {
+ rc(ExprKind::Builtin(Builtin::Natural))
+ };
+ (List $($ty:tt)*) => {{
+ let ty = make_closure!($($ty)*);
+ rc(ExprKind::App(
+ rc(ExprKind::Builtin(Builtin::List)),
+ ty
+ ))
+ }};
+ (Some($($v:tt)*)) => {
+ rc(ExprKind::SomeLit(
+ make_closure!($($v)*)
+ ))
+ };
+ (1 + $($v:tt)*) => {
+ rc(ExprKind::BinOp(
+ BinOp::NaturalPlus,
+ make_closure!($($v)*),
+ rc(ExprKind::NaturalLit(1))
+ ))
+ };
+ ([ $($head:tt)* ] # $($tail:tt)*) => {{
+ let head = make_closure!($($head)*);
+ let tail = make_closure!($($tail)*);
+ rc(ExprKind::BinOp(
+ BinOp::ListAppend,
+ rc(ExprKind::NEListLit(vec![head])),
+ tail,
+ ))
+ }};
+}
+
+#[allow(clippy::cognitive_complexity)]
+fn apply_builtin(
+ b: Builtin,
+ args: Vec<Value>,
+ ty: &Value,
+ types: Vec<Value>,
+ env: NzEnv,
+) -> ValueKind {
+ use Builtin::*;
+ use ValueKind::*;
+
+ // Small helper enum
+ enum Ret {
+ ValueKind(ValueKind),
+ Value(Value),
+ DoneAsIs,
+ }
+ let make_closure = |e| typecheck(&e).unwrap().eval(&env);
+
+ let ret = match (b, args.as_slice()) {
+ (OptionalNone, [t]) => Ret::ValueKind(EmptyOptionalLit(t.clone())),
+ (NaturalIsZero, [n]) => match &*n.kind() {
+ NaturalLit(n) => Ret::ValueKind(BoolLit(*n == 0)),
+ _ => Ret::DoneAsIs,
+ },
+ (NaturalEven, [n]) => match &*n.kind() {
+ NaturalLit(n) => Ret::ValueKind(BoolLit(*n % 2 == 0)),
+ _ => Ret::DoneAsIs,
+ },
+ (NaturalOdd, [n]) => match &*n.kind() {
+ NaturalLit(n) => Ret::ValueKind(BoolLit(*n % 2 != 0)),
+ _ => Ret::DoneAsIs,
+ },
+ (NaturalToInteger, [n]) => match &*n.kind() {
+ NaturalLit(n) => Ret::ValueKind(IntegerLit(*n as isize)),
+ _ => Ret::DoneAsIs,
+ },
+ (NaturalShow, [n]) => match &*n.kind() {
+ NaturalLit(n) => Ret::ValueKind(TextLit(
+ semantics::TextLit::from_text(n.to_string()),
+ )),
+ _ => Ret::DoneAsIs,
+ },
+ (NaturalSubtract, [a, b]) => match (&*a.kind(), &*b.kind()) {
+ (NaturalLit(a), NaturalLit(b)) => {
+ Ret::ValueKind(NaturalLit(if b > a { b - a } else { 0 }))
+ }
+ (NaturalLit(0), _) => Ret::Value(b.clone()),
+ (_, NaturalLit(0)) => Ret::ValueKind(NaturalLit(0)),
+ _ if a == b => Ret::ValueKind(NaturalLit(0)),
+ _ => Ret::DoneAsIs,
+ },
+ (IntegerShow, [n]) => match &*n.kind() {
+ IntegerLit(n) => {
+ let s = if *n < 0 {
+ n.to_string()
+ } else {
+ format!("+{}", n)
+ };
+ Ret::ValueKind(TextLit(semantics::TextLit::from_text(s)))
+ }
+ _ => Ret::DoneAsIs,
+ },
+ (IntegerToDouble, [n]) => match &*n.kind() {
+ IntegerLit(n) => {
+ Ret::ValueKind(DoubleLit(NaiveDouble::from(*n as f64)))
+ }
+ _ => Ret::DoneAsIs,
+ },
+ (IntegerNegate, [n]) => match &*n.kind() {
+ IntegerLit(n) => Ret::ValueKind(IntegerLit(-n)),
+ _ => Ret::DoneAsIs,
+ },
+ (IntegerClamp, [n]) => match &*n.kind() {
+ IntegerLit(n) => {
+ Ret::ValueKind(NaturalLit((*n).try_into().unwrap_or(0)))
+ }
+ _ => Ret::DoneAsIs,
+ },
+ (DoubleShow, [n]) => match &*n.kind() {
+ DoubleLit(n) => Ret::ValueKind(TextLit(
+ semantics::TextLit::from_text(n.to_string()),
+ )),
+ _ => Ret::DoneAsIs,
+ },
+ (TextShow, [v]) => match &*v.kind() {
+ TextLit(tlit) => {
+ if let Some(s) = tlit.as_text() {
+ // Printing InterpolatedText takes care of all the escaping
+ let txt: InterpolatedText<Normalized> =
+ std::iter::once(InterpolatedTextContents::Text(s))
+ .collect();
+ let s = txt.to_string();
+ Ret::ValueKind(TextLit(semantics::TextLit::from_text(s)))
+ } else {
+ Ret::DoneAsIs
+ }
+ }
+ _ => Ret::DoneAsIs,
+ },
+ (ListLength, [_, l]) => match &*l.kind() {
+ EmptyListLit(_) => Ret::ValueKind(NaturalLit(0)),
+ NEListLit(xs) => Ret::ValueKind(NaturalLit(xs.len())),
+ _ => Ret::DoneAsIs,
+ },
+ (ListHead, [_, l]) => match &*l.kind() {
+ EmptyListLit(n) => Ret::ValueKind(EmptyOptionalLit(n.clone())),
+ NEListLit(xs) => {
+ Ret::ValueKind(NEOptionalLit(xs.iter().next().unwrap().clone()))
+ }
+ _ => Ret::DoneAsIs,
+ },
+ (ListLast, [_, l]) => match &*l.kind() {
+ EmptyListLit(n) => Ret::ValueKind(EmptyOptionalLit(n.clone())),
+ NEListLit(xs) => Ret::ValueKind(NEOptionalLit(
+ xs.iter().rev().next().unwrap().clone(),
+ )),
+ _ => Ret::DoneAsIs,
+ },
+ (ListReverse, [_, l]) => match &*l.kind() {
+ EmptyListLit(n) => Ret::ValueKind(EmptyListLit(n.clone())),
+ NEListLit(xs) => {
+ Ret::ValueKind(NEListLit(xs.iter().rev().cloned().collect()))
+ }
+ _ => Ret::DoneAsIs,
+ },
+ (ListIndexed, [_, l]) => {
+ let l_whnf = l.kind();
+ match &*l_whnf {
+ EmptyListLit(_) | NEListLit(_) => {
+ // Extract the type of the list elements
+ let t = match &*l_whnf {
+ EmptyListLit(t) => t.clone(),
+ NEListLit(xs) => xs[0].get_type_not_sort(),
+ _ => unreachable!(),
+ };
+
+ // Construct the returned record type: { index: Natural, value: t }
+ let mut kts = HashMap::new();
+ kts.insert("index".into(), Value::from_builtin(Natural));
+ kts.insert("value".into(), t.clone());
+ let t = Value::from_kind_and_type(
+ RecordType(kts),
+ Value::from_const(Type),
+ );
+
+ // Construct the new list, with added indices
+ let list = match &*l_whnf {
+ EmptyListLit(_) => EmptyListLit(t),
+ NEListLit(xs) => NEListLit(
+ xs.iter()
+ .enumerate()
+ .map(|(i, e)| {
+ let mut kvs = HashMap::new();
+ kvs.insert(
+ "index".into(),
+ Value::from_kind_and_type(
+ NaturalLit(i),
+ Value::from_builtin(
+ Builtin::Natural,
+ ),
+ ),
+ );
+ kvs.insert("value".into(), e.clone());
+ Value::from_kind_and_type(
+ RecordLit(kvs),
+ t.clone(),
+ )
+ })
+ .collect(),
+ ),
+ _ => unreachable!(),
+ };
+ Ret::ValueKind(list)
+ }
+ _ => Ret::DoneAsIs,
+ }
+ }
+ (ListBuild, [t, f]) => {
+ let list_t = Value::from_builtin(List).app(t.clone());
+ Ret::Value(
+ f.app(list_t.clone())
+ .app(
+ make_closure(make_closure!(
+ λ(T : Type) ->
+ λ(a : var(T)) ->
+ λ(as : List var(T)) ->
+ [ var(a) ] # var(as)
+ ))
+ .app(t.clone()),
+ )
+ .app(EmptyListLit(t.clone()).into_value_with_type(list_t)),
+ )
+ }
+ (ListFold, [_, l, _, cons, nil]) => match &*l.kind() {
+ EmptyListLit(_) => Ret::Value(nil.clone()),
+ NEListLit(xs) => {
+ let mut v = nil.clone();
+ for x in xs.iter().cloned().rev() {
+ v = cons.app(x).app(v);
+ }
+ Ret::Value(v)
+ }
+ _ => Ret::DoneAsIs,
+ },
+ (OptionalBuild, [t, f]) => {
+ let optional_t = Value::from_builtin(Optional).app(t.clone());
+ Ret::Value(
+ f.app(optional_t.clone())
+ .app(
+ make_closure(make_closure!(
+ λ(T : Type) ->
+ λ(a : var(T)) ->
+ Some(var(a))
+ ))
+ .app(t.clone()),
+ )
+ .app(
+ EmptyOptionalLit(t.clone())
+ .into_value_with_type(optional_t),
+ ),
+ )
+ }
+ (OptionalFold, [_, v, _, just, nothing]) => match &*v.kind() {
+ EmptyOptionalLit(_) => Ret::Value(nothing.clone()),
+ NEOptionalLit(x) => Ret::Value(just.app(x.clone())),
+ _ => Ret::DoneAsIs,
+ },
+ (NaturalBuild, [f]) => Ret::Value(
+ f.app(Value::from_builtin(Natural))
+ .app(make_closure(make_closure!(
+ λ(x : Natural) ->
+ 1 + var(x)
+ )))
+ .app(
+ NaturalLit(0)
+ .into_value_with_type(Value::from_builtin(Natural)),
+ ),
+ ),
+
+ (NaturalFold, [n, t, succ, zero]) => match &*n.kind() {
+ NaturalLit(0) => Ret::Value(zero.clone()),
+ NaturalLit(n) => {
+ let fold = Value::from_builtin(NaturalFold)
+ .app(
+ NaturalLit(n - 1)
+ .into_value_with_type(Value::from_builtin(Natural)),
+ )
+ .app(t.clone())
+ .app(succ.clone())
+ .app(zero.clone());
+ Ret::Value(succ.app(fold))
+ }
+ _ => Ret::DoneAsIs,
+ },
+ _ => Ret::DoneAsIs,
+ };
+ match ret {
+ Ret::ValueKind(v) => v,
+ Ret::Value(v) => v.to_whnf_check_type(ty),
+ Ret::DoneAsIs => AppliedBuiltin(BuiltinClosure {
+ b,
+ args,
+ types,
+ env,
+ }),
+ }
+}
+
+impl<Value: std::cmp::PartialEq> std::cmp::PartialEq for BuiltinClosure<Value> {
+ fn eq(&self, other: &Self) -> bool {
+ self.b == other.b && self.args == other.args
+ }
+}
+impl<Value: std::cmp::Eq> std::cmp::Eq for BuiltinClosure<Value> {}
diff --git a/dhall/src/semantics/core/context.rs b/dhall/src/semantics/core/context.rs
deleted file mode 100644
index f755f72..0000000
--- a/dhall/src/semantics/core/context.rs
+++ /dev/null
@@ -1,144 +0,0 @@
-use std::collections::HashMap;
-use std::rc::Rc;
-
-use crate::error::TypeError;
-use crate::semantics::core::value::Value;
-use crate::semantics::core::value::ValueKind;
-use crate::semantics::core::var::{AlphaVar, Shift, Subst};
-use crate::syntax::{Label, V};
-
-#[derive(Debug, Clone)]
-enum CtxItem {
- Kept(AlphaVar, Value),
- Replaced(Value),
-}
-
-#[derive(Debug, Clone)]
-pub(crate) struct TypecheckContext(Rc<Vec<(Label, CtxItem)>>);
-
-impl TypecheckContext {
- pub fn new() -> Self {
- TypecheckContext(Rc::new(Vec::new()))
- }
- pub fn insert_type(&self, x: &Label, t: Value) -> Self {
- let mut vec = self.0.as_ref().clone();
- vec.push((x.clone(), CtxItem::Kept(x.into(), t.under_binder(x))));
- TypecheckContext(Rc::new(vec))
- }
- pub fn insert_value(&self, x: &Label, e: Value) -> Result<Self, TypeError> {
- let mut vec = self.0.as_ref().clone();
- vec.push((x.clone(), CtxItem::Replaced(e)));
- Ok(TypecheckContext(Rc::new(vec)))
- }
- pub fn lookup(&self, var: &V<Label>) -> Option<Value> {
- let mut var = var.clone();
- let mut shift_map: HashMap<Label, _> = HashMap::new();
- for (l, i) in self.0.iter().rev() {
- match var.over_binder(l) {
- None => {
- let i = i.under_multiple_binders(&shift_map);
- return Some(match i {
- CtxItem::Kept(newvar, t) => {
- Value::from_kind_and_type(ValueKind::Var(newvar), t)
- }
- CtxItem::Replaced(v) => v,
- });
- }
- Some(newvar) => var = newvar,
- };
- if let CtxItem::Kept(_, _) = i {
- *shift_map.entry(l.clone()).or_insert(0) += 1;
- }
- }
- // Unbound variable
- None
- }
- /// Given a var that makes sense in the current context, map the given function in such a way
- /// that the passed variable always makes sense in the context of the passed item.
- /// Once we pass the variable definition, the variable doesn't make sense anymore so we just
- /// copy the remaining items.
- fn do_with_var<E>(
- &self,
- var: &AlphaVar,
- mut f: impl FnMut(&AlphaVar, &CtxItem) -> Result<CtxItem, E>,
- ) -> Result<Self, E> {
- let mut vec = Vec::new();
- vec.reserve(self.0.len());
- let mut var = var.clone();
- let mut iter = self.0.iter().rev();
- for (l, i) in iter.by_ref() {
- vec.push((l.clone(), f(&var, i)?));
- if let CtxItem::Kept(_, _) = i {
- match var.over_binder(l) {
- None => break,
- Some(newvar) => var = newvar,
- };
- }
- }
- for (l, i) in iter {
- vec.push((l.clone(), (*i).clone()));
- }
- vec.reverse();
- Ok(TypecheckContext(Rc::new(vec)))
- }
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- if delta < 0 {
- Some(self.do_with_var(var, |var, i| Ok(i.shift(delta, &var)?))?)
- } else {
- Some(TypecheckContext(Rc::new(
- self.0
- .iter()
- .map(|(l, i)| Ok((l.clone(), i.shift(delta, &var)?)))
- .collect::<Result<_, _>>()?,
- )))
- }
- }
- fn subst_shift(&self, var: &AlphaVar, val: &Value) -> Self {
- self.do_with_var(var, |var, i| Ok::<_, !>(i.subst_shift(&var, val)))
- .unwrap()
- }
-}
-
-impl Shift for CtxItem {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(match self {
- CtxItem::Kept(v, t) => {
- CtxItem::Kept(v.shift(delta, var)?, t.shift(delta, var)?)
- }
- CtxItem::Replaced(e) => CtxItem::Replaced(e.shift(delta, var)?),
- })
- }
-}
-
-impl Shift for TypecheckContext {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- self.shift(delta, var)
- }
-}
-
-impl Subst<Value> for CtxItem {
- fn subst_shift(&self, var: &AlphaVar, val: &Value) -> Self {
- match self {
- CtxItem::Replaced(e) => CtxItem::Replaced(e.subst_shift(var, val)),
- CtxItem::Kept(v, t) => match v.shift(-1, var) {
- None => CtxItem::Replaced(val.clone()),
- Some(newvar) => CtxItem::Kept(newvar, t.subst_shift(var, val)),
- },
- }
- }
-}
-
-impl Subst<Value> for TypecheckContext {
- fn subst_shift(&self, var: &AlphaVar, val: &Value) -> Self {
- self.subst_shift(var, val)
- }
-}
-
-/// Don't count contexts when comparing stuff.
-/// This is dirty but needed.
-impl PartialEq for TypecheckContext {
- fn eq(&self, _: &Self) -> bool {
- true
- }
-}
-impl Eq for TypecheckContext {}
diff --git a/dhall/src/semantics/core/mod.rs b/dhall/src/semantics/core/mod.rs
deleted file mode 100644
index 90d74ea..0000000
--- a/dhall/src/semantics/core/mod.rs
+++ /dev/null
@@ -1,3 +0,0 @@
-pub mod context;
-pub mod value;
-pub mod var;
diff --git a/dhall/src/semantics/core/value.rs b/dhall/src/semantics/core/value.rs
deleted file mode 100644
index 6fa00ac..0000000
--- a/dhall/src/semantics/core/value.rs
+++ /dev/null
@@ -1,591 +0,0 @@
-use std::cell::{Ref, RefCell, RefMut};
-use std::collections::HashMap;
-use std::rc::Rc;
-
-use crate::error::{TypeError, TypeMessage};
-use crate::semantics::core::context::TypecheckContext;
-use crate::semantics::core::var::{AlphaLabel, AlphaVar, Shift, Subst};
-use crate::semantics::phase::normalize::{apply_any, normalize_whnf};
-use crate::semantics::phase::typecheck::{builtin_to_value, const_to_value};
-use crate::semantics::phase::{Normalized, NormalizedExpr, Typed};
-use crate::semantics::to_expr;
-use crate::syntax::{
- Builtin, Const, ExprKind, Integer, InterpolatedTextContents, Label,
- NaiveDouble, Natural, Span,
-};
-
-use self::Form::{Unevaled, NF, WHNF};
-
-/// Stores a possibly unevaluated value. Gets (partially) normalized on-demand, sharing computation
-/// automatically. Uses a RefCell to share computation.
-/// Can optionally store a type from typechecking to preserve type information.
-/// If you compare for equality two `Value`s in WHNF, then equality will be up to alpha-equivalence
-/// (renaming of bound variables) and beta-equivalence (normalization). It will recursively
-/// normalize as needed.
-#[derive(Clone)]
-pub(crate) struct Value(Rc<RefCell<ValueInternal>>);
-
-/// Invariant: if `form` is `WHNF`, `value` must be in Weak Head Normal Form
-/// Invariant: if `form` is `NF`, `value` must be fully normalized
-#[derive(Debug)]
-struct ValueInternal {
- form: Form,
- kind: ValueKind,
- /// This is None if and only if `value` is `Sort` (which doesn't have a type)
- ty: Option<Value>,
- span: Span,
-}
-
-#[derive(Debug, Clone, Copy)]
-pub(crate) enum Form {
- /// No constraints; expression may not be normalized at all.
- Unevaled,
- /// Weak Head Normal Form, i.e. normalized up to the first constructor, but subexpressions may
- /// not be normalized. This means that the first constructor of the contained ValueKind is the first
- /// constructor of the final Normal Form (NF).
- WHNF,
- /// Normal Form, i.e. completely normalized.
- /// When all the Values in a ValueKind are at least in WHNF, and recursively so, then the
- /// ValueKind is in NF. This is because WHNF ensures that we have the first constructor of the NF; so
- /// if we have the first constructor of the NF at all levels, we actually have the NF.
- NF,
-}
-
-#[derive(Debug, Clone, PartialEq, Eq)]
-pub(crate) enum ValueKind {
- /// Closures
- Lam(AlphaLabel, Value, Value),
- Pi(AlphaLabel, Value, Value),
- // Invariant: in whnf, the evaluation must not be able to progress further.
- AppliedBuiltin(Builtin, Vec<Value>),
-
- Var(AlphaVar),
- Const(Const),
- BoolLit(bool),
- NaturalLit(Natural),
- IntegerLit(Integer),
- DoubleLit(NaiveDouble),
- EmptyOptionalLit(Value),
- NEOptionalLit(Value),
- // EmptyListLit(t) means `[] : List t`, not `[] : t`
- EmptyListLit(Value),
- NEListLit(Vec<Value>),
- RecordType(HashMap<Label, Value>),
- RecordLit(HashMap<Label, Value>),
- UnionType(HashMap<Label, Option<Value>>),
- UnionConstructor(Label, HashMap<Label, Option<Value>>),
- UnionLit(Label, Value, HashMap<Label, Option<Value>>),
- // Invariant: in whnf, this must not contain interpolations that are themselves TextLits, and
- // contiguous text values must be merged.
- TextLit(Vec<InterpolatedTextContents<Value>>),
- Equivalence(Value, Value),
- // Invariant: in whnf, this must not contain a value captured by one of the variants above.
- PartialExpr(ExprKind<Value, Normalized>),
-}
-
-impl Value {
- fn new(kind: ValueKind, form: Form, ty: Value, span: Span) -> Value {
- ValueInternal {
- form,
- kind,
- ty: Some(ty),
- span,
- }
- .into_value()
- }
- pub(crate) fn const_sort() -> Value {
- ValueInternal {
- form: NF,
- kind: ValueKind::Const(Const::Sort),
- ty: None,
- span: Span::Artificial,
- }
- .into_value()
- }
- pub(crate) fn from_kind_and_type(v: ValueKind, t: Value) -> Value {
- Value::new(v, Unevaled, t, Span::Artificial)
- }
- pub(crate) fn from_kind_and_type_and_span(
- v: ValueKind,
- t: Value,
- span: Span,
- ) -> Value {
- Value::new(v, Unevaled, t, span)
- }
- pub(crate) fn from_kind_and_type_whnf(v: ValueKind, t: Value) -> Value {
- Value::new(v, WHNF, t, Span::Artificial)
- }
- pub(crate) fn from_const(c: Const) -> Self {
- const_to_value(c)
- }
- pub(crate) fn from_builtin(b: Builtin) -> Self {
- builtin_to_value(b)
- }
- pub(crate) fn with_span(self, span: Span) -> Self {
- self.as_internal_mut().span = span;
- self
- }
-
- pub(crate) fn as_const(&self) -> Option<Const> {
- match &*self.as_whnf() {
- ValueKind::Const(c) => Some(*c),
- _ => None,
- }
- }
- pub(crate) fn span(&self) -> Span {
- self.as_internal().span.clone()
- }
-
- fn as_internal(&self) -> Ref<ValueInternal> {
- self.0.borrow()
- }
- fn as_internal_mut(&self) -> RefMut<ValueInternal> {
- self.0.borrow_mut()
- }
- /// WARNING: The returned ValueKind may be entirely unnormalized, in particular it may just be an
- /// unevaled PartialExpr. You probably want to use `as_whnf`.
- pub(crate) fn as_kind(&self) -> Ref<ValueKind> {
- Ref::map(self.as_internal(), ValueInternal::as_kind)
- }
- /// This is what you want if you want to pattern-match on the value.
- /// WARNING: drop this ref before normalizing the same value or you will run into BorrowMut
- /// panics.
- pub(crate) fn as_whnf(&self) -> Ref<ValueKind> {
- self.normalize_whnf();
- self.as_kind()
- }
-
- /// Converts a value back to the corresponding AST expression.
- pub(crate) fn to_expr(
- &self,
- opts: to_expr::ToExprOptions,
- ) -> NormalizedExpr {
- to_expr::value_to_expr(self, opts)
- }
- pub(crate) fn to_whnf_ignore_type(&self) -> ValueKind {
- self.as_whnf().clone()
- }
- /// Before discarding type information, check that it matches the expected return type.
- pub(crate) fn to_whnf_check_type(&self, ty: &Value) -> ValueKind {
- self.check_type(ty);
- self.to_whnf_ignore_type()
- }
- pub(crate) fn into_typed(self) -> Typed {
- Typed::from_value(self)
- }
-
- /// Mutates the contents. If no one else shares this, this avoids a RefCell lock.
- fn mutate_internal(&mut self, f: impl FnOnce(&mut ValueInternal)) {
- match Rc::get_mut(&mut self.0) {
- // Mutate directly if sole owner
- Some(refcell) => f(RefCell::get_mut(refcell)),
- // Otherwise mutate through the refcell
- None => f(&mut self.as_internal_mut()),
- }
- }
- /// Normalizes contents to normal form; faster than `normalize_nf` if
- /// no one else shares this.
- pub(crate) fn normalize_mut(&mut self) {
- self.mutate_internal(|vint| vint.normalize_nf())
- }
-
- pub(crate) fn normalize_whnf(&self) {
- let borrow = self.as_internal();
- match borrow.form {
- Unevaled => {
- drop(borrow);
- self.as_internal_mut().normalize_whnf();
- }
- // Already at least in WHNF
- WHNF | NF => {}
- }
- }
- pub(crate) fn normalize_nf(&self) {
- self.as_internal_mut().normalize_nf();
- }
-
- pub(crate) fn app(&self, v: Value) -> Value {
- let body_t = match &*self.get_type_not_sort().as_whnf() {
- ValueKind::Pi(x, t, e) => {
- v.check_type(t);
- e.subst_shift(&x.into(), &v)
- }
- _ => unreachable!("Internal type error"),
- };
- Value::from_kind_and_type_whnf(
- apply_any(self.clone(), v, &body_t),
- body_t,
- )
- }
-
- /// In debug mode, panic if the provided type doesn't match the value's type.
- /// Otherwise does nothing.
- pub(crate) fn check_type(&self, ty: &Value) {
- debug_assert_eq!(
- Some(ty),
- self.get_type().ok().as_ref(),
- "Internal type error"
- );
- }
- pub(crate) fn get_type(&self) -> Result<Value, TypeError> {
- Ok(self.as_internal().get_type()?.clone())
- }
- /// When we know the value isn't `Sort`, this gets the type directly
- pub(crate) fn get_type_not_sort(&self) -> Value {
- self.get_type()
- .expect("Internal type error: value is `Sort` but shouldn't be")
- }
-}
-
-impl ValueInternal {
- fn into_value(self) -> Value {
- Value(Rc::new(RefCell::new(self)))
- }
- fn as_kind(&self) -> &ValueKind {
- &self.kind
- }
-
- fn normalize_whnf(&mut self) {
- take_mut::take_or_recover(
- self,
- // Dummy value in case the other closure panics
- || ValueInternal {
- form: Unevaled,
- kind: ValueKind::Const(Const::Type),
- ty: None,
- span: Span::Artificial,
- },
- |vint| match (&vint.form, &vint.ty) {
- (Unevaled, Some(ty)) => ValueInternal {
- form: WHNF,
- kind: normalize_whnf(vint.kind, &ty),
- ty: vint.ty,
- span: vint.span,
- },
- // `value` is `Sort`
- (Unevaled, None) => ValueInternal {
- form: NF,
- kind: ValueKind::Const(Const::Sort),
- ty: None,
- span: vint.span,
- },
- // Already in WHNF
- (WHNF, _) | (NF, _) => vint,
- },
- )
- }
- fn normalize_nf(&mut self) {
- match self.form {
- Unevaled => {
- self.normalize_whnf();
- self.normalize_nf();
- }
- WHNF => {
- self.kind.normalize_mut();
- self.form = NF;
- }
- // Already in NF
- NF => {}
- }
- }
-
- fn get_type(&self) -> Result<&Value, TypeError> {
- match &self.ty {
- Some(t) => Ok(t),
- None => {
- Err(TypeError::new(&TypecheckContext::new(), TypeMessage::Sort))
- }
- }
- }
-}
-
-impl ValueKind {
- pub(crate) fn into_value_with_type(self, t: Value) -> Value {
- Value::from_kind_and_type(self, t)
- }
-
- /// Converts a value back to the corresponding AST expression.
- pub(crate) fn to_expr(
- &self,
- opts: to_expr::ToExprOptions,
- ) -> NormalizedExpr {
- to_expr::kind_to_expr(self, opts)
- }
-
- pub(crate) fn normalize_mut(&mut self) {
- match self {
- ValueKind::Var(_)
- | ValueKind::Const(_)
- | ValueKind::BoolLit(_)
- | ValueKind::NaturalLit(_)
- | ValueKind::IntegerLit(_)
- | ValueKind::DoubleLit(_) => {}
-
- ValueKind::EmptyOptionalLit(tth) | ValueKind::EmptyListLit(tth) => {
- tth.normalize_mut();
- }
-
- ValueKind::NEOptionalLit(th) => {
- th.normalize_mut();
- }
- ValueKind::Lam(_, t, e) => {
- t.normalize_mut();
- e.normalize_mut();
- }
- ValueKind::Pi(_, t, e) => {
- t.normalize_mut();
- e.normalize_mut();
- }
- ValueKind::AppliedBuiltin(_, args) => {
- for x in args.iter_mut() {
- x.normalize_mut();
- }
- }
- ValueKind::NEListLit(elts) => {
- for x in elts.iter_mut() {
- x.normalize_mut();
- }
- }
- ValueKind::RecordLit(kvs) => {
- for x in kvs.values_mut() {
- x.normalize_mut();
- }
- }
- ValueKind::RecordType(kvs) => {
- for x in kvs.values_mut() {
- x.normalize_mut();
- }
- }
- ValueKind::UnionType(kts) | ValueKind::UnionConstructor(_, kts) => {
- for x in kts.values_mut().flat_map(|opt| opt) {
- x.normalize_mut();
- }
- }
- ValueKind::UnionLit(_, v, kts) => {
- v.normalize_mut();
- for x in kts.values_mut().flat_map(|opt| opt) {
- x.normalize_mut();
- }
- }
- ValueKind::TextLit(elts) => {
- for x in elts.iter_mut() {
- x.map_mut(Value::normalize_mut);
- }
- }
- ValueKind::Equivalence(x, y) => {
- x.normalize_mut();
- y.normalize_mut();
- }
- ValueKind::PartialExpr(e) => {
- e.map_mut(Value::normalize_mut);
- }
- }
- }
-
- pub(crate) fn from_builtin(b: Builtin) -> ValueKind {
- ValueKind::AppliedBuiltin(b, vec![])
- }
-}
-
-impl Shift for Value {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(Value(self.0.shift(delta, var)?))
- }
-}
-
-impl Shift for ValueInternal {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(ValueInternal {
- form: self.form,
- kind: self.kind.shift(delta, var)?,
- ty: self.ty.shift(delta, var)?,
- span: self.span.clone(),
- })
- }
-}
-
-impl Shift for ValueKind {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(match self {
- ValueKind::Lam(x, t, e) => ValueKind::Lam(
- x.clone(),
- t.shift(delta, var)?,
- e.shift(delta, &var.under_binder(x))?,
- ),
- ValueKind::AppliedBuiltin(b, args) => {
- ValueKind::AppliedBuiltin(*b, args.shift(delta, var)?)
- }
- ValueKind::Pi(x, t, e) => ValueKind::Pi(
- x.clone(),
- t.shift(delta, var)?,
- e.shift(delta, &var.under_binder(x))?,
- ),
- ValueKind::Var(v) => ValueKind::Var(v.shift(delta, var)?),
- ValueKind::Const(c) => ValueKind::Const(*c),
- ValueKind::BoolLit(b) => ValueKind::BoolLit(*b),
- ValueKind::NaturalLit(n) => ValueKind::NaturalLit(*n),
- ValueKind::IntegerLit(n) => ValueKind::IntegerLit(*n),
- ValueKind::DoubleLit(n) => ValueKind::DoubleLit(*n),
- ValueKind::EmptyOptionalLit(tth) => {
- ValueKind::EmptyOptionalLit(tth.shift(delta, var)?)
- }
- ValueKind::NEOptionalLit(th) => {
- ValueKind::NEOptionalLit(th.shift(delta, var)?)
- }
- ValueKind::EmptyListLit(tth) => {
- ValueKind::EmptyListLit(tth.shift(delta, var)?)
- }
- ValueKind::NEListLit(elts) => {
- ValueKind::NEListLit(elts.shift(delta, var)?)
- }
- ValueKind::RecordLit(kvs) => {
- ValueKind::RecordLit(kvs.shift(delta, var)?)
- }
- ValueKind::RecordType(kvs) => {
- ValueKind::RecordType(kvs.shift(delta, var)?)
- }
- ValueKind::UnionType(kts) => {
- ValueKind::UnionType(kts.shift(delta, var)?)
- }
- ValueKind::UnionConstructor(x, kts) => {
- ValueKind::UnionConstructor(x.clone(), kts.shift(delta, var)?)
- }
- ValueKind::UnionLit(x, v, kts) => ValueKind::UnionLit(
- x.clone(),
- v.shift(delta, var)?,
- kts.shift(delta, var)?,
- ),
- ValueKind::TextLit(elts) => {
- ValueKind::TextLit(elts.shift(delta, var)?)
- }
- ValueKind::Equivalence(x, y) => ValueKind::Equivalence(
- x.shift(delta, var)?,
- y.shift(delta, var)?,
- ),
- ValueKind::PartialExpr(e) => {
- ValueKind::PartialExpr(e.shift(delta, var)?)
- }
- })
- }
-}
-
-impl Subst<Value> for Value {
- fn subst_shift(&self, var: &AlphaVar, val: &Value) -> Self {
- match &*self.as_kind() {
- // If the var matches, we can just reuse the provided value instead of copying it.
- // We also check that the types match, if in debug mode.
- ValueKind::Var(v) if v == var => {
- if let Ok(self_ty) = self.get_type() {
- val.check_type(&self_ty.subst_shift(var, val));
- }
- val.clone()
- }
- _ => Value(self.0.subst_shift(var, val)),
- }
- }
-}
-
-impl Subst<Value> for ValueInternal {
- fn subst_shift(&self, var: &AlphaVar, val: &Value) -> Self {
- ValueInternal {
- // The resulting value may not stay in wnhf after substitution
- form: Unevaled,
- kind: self.kind.subst_shift(var, val),
- ty: self.ty.subst_shift(var, val),
- span: self.span.clone(),
- }
- }
-}
-
-impl Subst<Value> for ValueKind {
- fn subst_shift(&self, var: &AlphaVar, val: &Value) -> Self {
- match self {
- ValueKind::AppliedBuiltin(b, args) => {
- ValueKind::AppliedBuiltin(*b, args.subst_shift(var, val))
- }
- ValueKind::PartialExpr(e) => {
- ValueKind::PartialExpr(e.subst_shift(var, val))
- }
- ValueKind::TextLit(elts) => {
- ValueKind::TextLit(elts.subst_shift(var, val))
- }
- ValueKind::Lam(x, t, e) => ValueKind::Lam(
- x.clone(),
- t.subst_shift(var, val),
- e.subst_shift(&var.under_binder(x), &val.under_binder(x)),
- ),
- ValueKind::Pi(x, t, e) => ValueKind::Pi(
- x.clone(),
- t.subst_shift(var, val),
- e.subst_shift(&var.under_binder(x), &val.under_binder(x)),
- ),
- ValueKind::Var(v) if v == var => val.to_whnf_ignore_type(),
- ValueKind::Var(v) => ValueKind::Var(v.shift(-1, var).unwrap()),
- ValueKind::Const(c) => ValueKind::Const(*c),
- ValueKind::BoolLit(b) => ValueKind::BoolLit(*b),
- ValueKind::NaturalLit(n) => ValueKind::NaturalLit(*n),
- ValueKind::IntegerLit(n) => ValueKind::IntegerLit(*n),
- ValueKind::DoubleLit(n) => ValueKind::DoubleLit(*n),
- ValueKind::EmptyOptionalLit(tth) => {
- ValueKind::EmptyOptionalLit(tth.subst_shift(var, val))
- }
- ValueKind::NEOptionalLit(th) => {
- ValueKind::NEOptionalLit(th.subst_shift(var, val))
- }
- ValueKind::EmptyListLit(tth) => {
- ValueKind::EmptyListLit(tth.subst_shift(var, val))
- }
- ValueKind::NEListLit(elts) => {
- ValueKind::NEListLit(elts.subst_shift(var, val))
- }
- ValueKind::RecordLit(kvs) => {
- ValueKind::RecordLit(kvs.subst_shift(var, val))
- }
- ValueKind::RecordType(kvs) => {
- ValueKind::RecordType(kvs.subst_shift(var, val))
- }
- ValueKind::UnionType(kts) => {
- ValueKind::UnionType(kts.subst_shift(var, val))
- }
- ValueKind::UnionConstructor(x, kts) => ValueKind::UnionConstructor(
- x.clone(),
- kts.subst_shift(var, val),
- ),
- ValueKind::UnionLit(x, v, kts) => ValueKind::UnionLit(
- x.clone(),
- v.subst_shift(var, val),
- kts.subst_shift(var, val),
- ),
- ValueKind::Equivalence(x, y) => ValueKind::Equivalence(
- x.subst_shift(var, val),
- y.subst_shift(var, val),
- ),
- }
- }
-}
-
-// TODO: use Rc comparison to shortcut on identical pointers
-impl std::cmp::PartialEq for Value {
- fn eq(&self, other: &Self) -> bool {
- *self.as_whnf() == *other.as_whnf()
- }
-}
-impl std::cmp::Eq for Value {}
-
-impl std::fmt::Debug for Value {
- fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- let vint: &ValueInternal = &self.as_internal();
- if let ValueKind::Const(c) = &vint.kind {
- write!(fmt, "{:?}", c)
- } else {
- let mut x = fmt.debug_struct(&format!("Value@{:?}", &vint.form));
- x.field("value", &vint.kind);
- if let Some(ty) = vint.ty.as_ref() {
- x.field("type", &ty);
- } else {
- x.field("type", &None::<()>);
- }
- x.finish()
- }
- }
-}
diff --git a/dhall/src/semantics/core/var.rs b/dhall/src/semantics/core/var.rs
deleted file mode 100644
index 1548713..0000000
--- a/dhall/src/semantics/core/var.rs
+++ /dev/null
@@ -1,295 +0,0 @@
-use std::collections::HashMap;
-
-use crate::syntax::{ExprKind, InterpolatedTextContents, Label, V};
-
-/// Stores a pair of variables: a normal one and one
-/// that corresponds to the alpha-normalized version of the first one.
-/// Equality is up to alpha-equivalence (compares on the second one only).
-#[derive(Clone, Eq)]
-pub struct AlphaVar {
- normal: V<Label>,
- alpha: V<()>,
-}
-
-// Exactly like a Label, but equality returns always true.
-// This is so that ValueKind equality is exactly alpha-equivalence.
-#[derive(Clone, Eq)]
-pub struct AlphaLabel(Label);
-
-pub(crate) trait Shift: Sized {
- // Shift an expression to move it around binders without changing the meaning of its free
- // variables. Shift by 1 to move an expression under a binder. Shift by -1 to extract an
- // expression from under a binder, if the expression does not refer to that bound variable.
- // Returns None if delta was negative and the variable was free in the expression.
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self>;
-
- fn over_binder<T>(&self, x: T) -> Option<Self>
- where
- T: Into<AlphaVar>,
- {
- self.shift(-1, &x.into())
- }
-
- fn under_binder<T>(&self, x: T) -> Self
- where
- T: Into<AlphaVar>,
- {
- // Can't fail since delta is positive
- self.shift(1, &x.into()).unwrap()
- }
-
- fn under_multiple_binders(&self, shift_map: &HashMap<Label, usize>) -> Self
- where
- Self: Clone,
- {
- let mut v = self.clone();
- for (x, n) in shift_map {
- v = v.shift(*n as isize, &x.into()).unwrap();
- }
- v
- }
-}
-
-pub(crate) trait Subst<S> {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self;
-}
-
-impl AlphaVar {
- pub(crate) fn to_var(&self, alpha: bool) -> V<Label> {
- if alpha {
- V("_".into(), self.alpha.1)
- } else {
- self.normal.clone()
- }
- }
- pub(crate) fn from_var_and_alpha(normal: V<Label>, alpha: usize) -> Self {
- AlphaVar {
- normal,
- alpha: V((), alpha),
- }
- }
-}
-
-impl AlphaLabel {
- pub(crate) fn to_label_maybe_alpha(&self, alpha: bool) -> Label {
- if alpha {
- "_".into()
- } else {
- self.to_label()
- }
- }
- pub(crate) fn to_label(&self) -> Label {
- self.clone().into()
- }
-}
-
-impl Shift for AlphaVar {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(AlphaVar {
- normal: self.normal.shift(delta, &var.normal)?,
- alpha: self.alpha.shift(delta, &var.alpha)?,
- })
- }
-}
-
-/// Equality up to alpha-equivalence
-impl std::cmp::PartialEq for AlphaVar {
- fn eq(&self, other: &Self) -> bool {
- self.alpha == other.alpha
- }
-}
-impl std::cmp::PartialEq for AlphaLabel {
- fn eq(&self, _other: &Self) -> bool {
- true
- }
-}
-
-impl std::fmt::Debug for AlphaVar {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- write!(f, "AlphaVar({}, {})", self.normal, self.alpha.1)
- }
-}
-
-impl std::fmt::Debug for AlphaLabel {
- fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
- write!(f, "AlphaLabel({})", &self.0)
- }
-}
-
-impl From<Label> for AlphaVar {
- fn from(x: Label) -> AlphaVar {
- AlphaVar {
- normal: V(x, 0),
- alpha: V((), 0),
- }
- }
-}
-impl<'a> From<&'a Label> for AlphaVar {
- fn from(x: &'a Label) -> AlphaVar {
- x.clone().into()
- }
-}
-impl From<AlphaLabel> for AlphaVar {
- fn from(x: AlphaLabel) -> AlphaVar {
- let l: Label = x.into();
- l.into()
- }
-}
-impl<'a> From<&'a AlphaLabel> for AlphaVar {
- fn from(x: &'a AlphaLabel) -> AlphaVar {
- x.clone().into()
- }
-}
-
-impl From<Label> for AlphaLabel {
- fn from(x: Label) -> AlphaLabel {
- AlphaLabel(x)
- }
-}
-impl From<AlphaLabel> for Label {
- fn from(x: AlphaLabel) -> Label {
- x.0
- }
-}
-impl Shift for () {
- fn shift(&self, _delta: isize, _var: &AlphaVar) -> Option<Self> {
- Some(())
- }
-}
-
-impl<A: Shift, B: Shift> Shift for (A, B) {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some((self.0.shift(delta, var)?, self.1.shift(delta, var)?))
- }
-}
-
-impl<T: Shift> Shift for Option<T> {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(match self {
- None => None,
- Some(x) => Some(x.shift(delta, var)?),
- })
- }
-}
-
-impl<T: Shift> Shift for Box<T> {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(Box::new(self.as_ref().shift(delta, var)?))
- }
-}
-
-impl<T: Shift> Shift for std::rc::Rc<T> {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(std::rc::Rc::new(self.as_ref().shift(delta, var)?))
- }
-}
-
-impl<T: Shift> Shift for std::cell::RefCell<T> {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(std::cell::RefCell::new(self.borrow().shift(delta, var)?))
- }
-}
-
-impl<T: Shift, E: Clone> Shift for ExprKind<T, E> {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(self.traverse_ref_with_special_handling_of_binders(
- |v| Ok(v.shift(delta, var)?),
- |x, v| Ok(v.shift(delta, &var.under_binder(x))?),
- )?)
- }
-}
-
-impl<T: Shift> Shift for Vec<T> {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(
- self.iter()
- .map(|v| Ok(v.shift(delta, var)?))
- .collect::<Result<_, _>>()?,
- )
- }
-}
-
-impl<K, T: Shift> Shift for HashMap<K, T>
-where
- K: Clone + std::hash::Hash + Eq,
-{
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(
- self.iter()
- .map(|(k, v)| Ok((k.clone(), v.shift(delta, var)?)))
- .collect::<Result<_, _>>()?,
- )
- }
-}
-
-impl<T: Shift> Shift for InterpolatedTextContents<T> {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(self.traverse_ref(|x| Ok(x.shift(delta, var)?))?)
- }
-}
-
-impl<S> Subst<S> for () {
- fn subst_shift(&self, _var: &AlphaVar, _val: &S) -> Self {}
-}
-
-impl<S, A: Subst<S>, B: Subst<S>> Subst<S> for (A, B) {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- (self.0.subst_shift(var, val), self.1.subst_shift(var, val))
- }
-}
-
-impl<S, T: Subst<S>> Subst<S> for Option<T> {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- self.as_ref().map(|x| x.subst_shift(var, val))
- }
-}
-
-impl<S, T: Subst<S>> Subst<S> for Box<T> {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- Box::new(self.as_ref().subst_shift(var, val))
- }
-}
-
-impl<S, T: Subst<S>> Subst<S> for std::rc::Rc<T> {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- std::rc::Rc::new(self.as_ref().subst_shift(var, val))
- }
-}
-
-impl<S, T: Subst<S>> Subst<S> for std::cell::RefCell<T> {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- std::cell::RefCell::new(self.borrow().subst_shift(var, val))
- }
-}
-
-impl<S: Shift, T: Subst<S>, E: Clone> Subst<S> for ExprKind<T, E> {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- self.map_ref_with_special_handling_of_binders(
- |v| v.subst_shift(var, val),
- |x, v| v.subst_shift(&var.under_binder(x), &val.under_binder(x)),
- )
- }
-}
-
-impl<S, T: Subst<S>> Subst<S> for Vec<T> {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- self.iter().map(|v| v.subst_shift(var, val)).collect()
- }
-}
-
-impl<S, T: Subst<S>> Subst<S> for InterpolatedTextContents<T> {
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- self.map_ref(|x| x.subst_shift(var, val))
- }
-}
-
-impl<S, K, T: Subst<S>> Subst<S> for HashMap<K, T>
-where
- K: Clone + std::hash::Hash + Eq,
-{
- fn subst_shift(&self, var: &AlphaVar, val: &S) -> Self {
- self.iter()
- .map(|(k, v)| (k.clone(), v.subst_shift(var, val)))
- .collect()
- }
-}
diff --git a/dhall/src/semantics/mod.rs b/dhall/src/semantics/mod.rs
index 1eeef86..98fdf5a 100644
--- a/dhall/src/semantics/mod.rs
+++ b/dhall/src/semantics/mod.rs
@@ -1,3 +1,8 @@
-pub mod core;
-pub mod phase;
-pub mod to_expr;
+pub mod builtins;
+pub mod nze;
+pub mod parse;
+pub mod resolve;
+pub mod tck;
+pub(crate) use self::builtins::*;
+pub(crate) use self::nze::*;
+pub(crate) use self::tck::*;
diff --git a/dhall/src/semantics/nze/env.rs b/dhall/src/semantics/nze/env.rs
new file mode 100644
index 0000000..0b22a8b
--- /dev/null
+++ b/dhall/src/semantics/nze/env.rs
@@ -0,0 +1,76 @@
+use crate::semantics::{AlphaVar, Value, ValueKind};
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub(crate) enum NzVar {
+ /// Reverse-debruijn index: counts number of binders from the bottom of the stack.
+ Bound(usize),
+ /// Fake fresh variable generated for expression equality checking.
+ Fresh(usize),
+}
+
+#[derive(Debug, Clone)]
+enum NzEnvItem {
+ // Variable is bound with given type
+ Kept(Value),
+ // Variable has been replaced by corresponding value
+ Replaced(Value),
+}
+
+#[derive(Debug, Clone)]
+pub(crate) struct NzEnv {
+ items: Vec<NzEnvItem>,
+}
+
+impl NzVar {
+ pub fn new(idx: usize) -> Self {
+ NzVar::Bound(idx)
+ }
+ pub fn fresh() -> Self {
+ use std::sync::atomic::{AtomicUsize, Ordering};
+ // Global counter to ensure uniqueness of the generated id.
+ static FRESH_VAR_COUNTER: AtomicUsize = AtomicUsize::new(0);
+ let id = FRESH_VAR_COUNTER.fetch_add(1, Ordering::SeqCst);
+ NzVar::Fresh(id)
+ }
+ /// Get index of bound variable.
+ /// Panics on a fresh variable.
+ pub fn idx(&self) -> usize {
+ match self {
+ NzVar::Bound(i) => *i,
+ NzVar::Fresh(_) => panic!(
+ "Trying to use a fresh variable outside of equality checking"
+ ),
+ }
+ }
+}
+
+impl NzEnv {
+ pub fn new() -> Self {
+ NzEnv { items: Vec::new() }
+ }
+
+ pub fn insert_type(&self, t: Value) -> Self {
+ let mut env = self.clone();
+ env.items.push(NzEnvItem::Kept(t));
+ env
+ }
+ pub fn insert_value(&self, e: Value) -> Self {
+ let mut env = self.clone();
+ env.items.push(NzEnvItem::Replaced(e));
+ env
+ }
+ pub fn lookup_val(&self, var: &AlphaVar) -> ValueKind {
+ let idx = self.items.len() - 1 - var.idx();
+ match &self.items[idx] {
+ NzEnvItem::Kept(_) => ValueKind::Var(NzVar::new(idx)),
+ NzEnvItem::Replaced(x) => x.kind().clone(),
+ }
+ }
+ pub fn lookup_ty(&self, var: &AlphaVar) -> Value {
+ let idx = self.items.len() - 1 - var.idx();
+ match &self.items[idx] {
+ NzEnvItem::Kept(ty) => ty.clone(),
+ NzEnvItem::Replaced(x) => x.get_type().unwrap(),
+ }
+ }
+}
diff --git a/dhall/src/semantics/nze/lazy.rs b/dhall/src/semantics/nze/lazy.rs
new file mode 100644
index 0000000..d361313
--- /dev/null
+++ b/dhall/src/semantics/nze/lazy.rs
@@ -0,0 +1,64 @@
+use once_cell::unsync::OnceCell;
+use std::cell::Cell;
+use std::fmt::Debug;
+use std::ops::Deref;
+
+pub trait Eval<Tgt> {
+ fn eval(self) -> Tgt;
+}
+
+/// A value which is initialized from a `Src` on the first access.
+pub struct Lazy<Src, Tgt> {
+ /// Exactly one of `src` of `tgt` must be set at a given time.
+ /// Once `src` is unset and `tgt` is set, we never go back.
+ src: Cell<Option<Src>>,
+ tgt: OnceCell<Tgt>,
+}
+
+impl<Src, Tgt> Lazy<Src, Tgt>
+where
+ Src: Eval<Tgt>,
+{
+ /// Creates a new lazy value with the given initializing value.
+ pub fn new(src: Src) -> Self {
+ Lazy {
+ src: Cell::new(Some(src)),
+ tgt: OnceCell::new(),
+ }
+ }
+ /// Creates a new lazy value with the given already-initialized value.
+ pub fn new_completed(tgt: Tgt) -> Self {
+ let lazy = Lazy {
+ src: Cell::new(None),
+ tgt: OnceCell::new(),
+ };
+ let _ = lazy.tgt.set(tgt);
+ lazy
+ }
+}
+
+impl<Src, Tgt> Deref for Lazy<Src, Tgt>
+where
+ Src: Eval<Tgt>,
+{
+ type Target = Tgt;
+ fn deref(&self) -> &Self::Target {
+ self.tgt.get_or_init(|| {
+ let src = self.src.take().unwrap();
+ src.eval()
+ })
+ }
+}
+
+impl<Src, Tgt> Debug for Lazy<Src, Tgt>
+where
+ Tgt: Debug,
+{
+ fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ if let Some(tgt) = self.tgt.get() {
+ fmt.debug_tuple("Lazy@Init").field(tgt).finish()
+ } else {
+ fmt.debug_tuple("Lazy@Uninit").finish()
+ }
+ }
+}
diff --git a/dhall/src/semantics/nze/mod.rs b/dhall/src/semantics/nze/mod.rs
new file mode 100644
index 0000000..2c8d907
--- /dev/null
+++ b/dhall/src/semantics/nze/mod.rs
@@ -0,0 +1,9 @@
+pub mod env;
+pub mod lazy;
+pub mod normalize;
+pub mod value;
+pub mod var;
+pub(crate) use env::*;
+pub(crate) use normalize::*;
+pub(crate) use value::*;
+pub(crate) use var::*;
diff --git a/dhall/src/semantics/nze/normalize.rs b/dhall/src/semantics/nze/normalize.rs
new file mode 100644
index 0000000..e9d140b
--- /dev/null
+++ b/dhall/src/semantics/nze/normalize.rs
@@ -0,0 +1,421 @@
+use std::collections::HashMap;
+
+use crate::semantics::NzEnv;
+use crate::semantics::{
+ Binder, BuiltinClosure, Closure, TextLit, TyExpr, TyExprKind, Value,
+ ValueKind,
+};
+use crate::syntax::{
+ BinOp, Builtin, Const, ExprKind, InterpolatedTextContents,
+};
+use crate::Normalized;
+
+pub(crate) fn apply_any(f: Value, a: Value, ty: &Value) -> ValueKind {
+ match f.kind() {
+ ValueKind::LamClosure { closure, .. } => {
+ closure.apply(a).to_whnf_check_type(ty)
+ }
+ ValueKind::AppliedBuiltin(closure) => {
+ closure.apply(a, f.get_type().unwrap(), ty)
+ }
+ ValueKind::UnionConstructor(l, kts, uniont) => ValueKind::UnionLit(
+ l.clone(),
+ a,
+ kts.clone(),
+ uniont.clone(),
+ f.get_type().unwrap(),
+ ),
+ _ => ValueKind::PartialExpr(ExprKind::App(f, a)),
+ }
+}
+
+pub(crate) fn squash_textlit(
+ elts: impl Iterator<Item = InterpolatedTextContents<Value>>,
+) -> Vec<InterpolatedTextContents<Value>> {
+ use std::mem::replace;
+ use InterpolatedTextContents::{Expr, Text};
+
+ fn inner(
+ elts: impl Iterator<Item = InterpolatedTextContents<Value>>,
+ crnt_str: &mut String,
+ ret: &mut Vec<InterpolatedTextContents<Value>>,
+ ) {
+ for contents in elts {
+ match contents {
+ Text(s) => crnt_str.push_str(&s),
+ Expr(e) => match e.kind() {
+ ValueKind::TextLit(elts2) => {
+ inner(elts2.iter().cloned(), crnt_str, ret)
+ }
+ _ => {
+ if !crnt_str.is_empty() {
+ ret.push(Text(replace(crnt_str, String::new())))
+ }
+ ret.push(Expr(e.clone()))
+ }
+ },
+ }
+ }
+ }
+
+ let mut crnt_str = String::new();
+ let mut ret = Vec::new();
+ inner(elts, &mut crnt_str, &mut ret);
+ if !crnt_str.is_empty() {
+ ret.push(Text(replace(&mut crnt_str, String::new())))
+ }
+ ret
+}
+
+pub(crate) fn merge_maps<K, V, F, Err>(
+ map1: &HashMap<K, V>,
+ map2: &HashMap<K, V>,
+ mut f: F,
+) -> Result<HashMap<K, V>, Err>
+where
+ F: FnMut(&K, &V, &V) -> Result<V, Err>,
+ K: std::hash::Hash + Eq + Clone,
+ V: Clone,
+{
+ let mut kvs = HashMap::new();
+ for (x, v2) in map2 {
+ let newv = if let Some(v1) = map1.get(x) {
+ f(x, v1, v2)?
+ } else {
+ v2.clone()
+ };
+ kvs.insert(x.clone(), newv);
+ }
+ for (x, v1) in map1 {
+ // Insert only if key not already present
+ kvs.entry(x.clone()).or_insert_with(|| v1.clone());
+ }
+ Ok(kvs)
+}
+
+// Small helper enum to avoid repetition
+enum Ret<'a> {
+ ValueKind(ValueKind),
+ Value(Value),
+ ValueRef(&'a Value),
+ Expr(ExprKind<Value, Normalized>),
+}
+
+fn apply_binop<'a>(
+ o: BinOp,
+ x: &'a Value,
+ y: &'a Value,
+ ty: &Value,
+) -> Option<Ret<'a>> {
+ use BinOp::{
+ BoolAnd, BoolEQ, BoolNE, BoolOr, Equivalence, ListAppend, NaturalPlus,
+ NaturalTimes, RecursiveRecordMerge, RecursiveRecordTypeMerge,
+ RightBiasedRecordMerge, TextAppend,
+ };
+ use ValueKind::{
+ BoolLit, EmptyListLit, NEListLit, NaturalLit, RecordLit, RecordType,
+ };
+ Some(match (o, x.kind(), y.kind()) {
+ (BoolAnd, BoolLit(true), _) => Ret::ValueRef(y),
+ (BoolAnd, _, BoolLit(true)) => Ret::ValueRef(x),
+ (BoolAnd, BoolLit(false), _) => Ret::ValueKind(BoolLit(false)),
+ (BoolAnd, _, BoolLit(false)) => Ret::ValueKind(BoolLit(false)),
+ (BoolAnd, _, _) if x == y => Ret::ValueRef(x),
+ (BoolOr, BoolLit(true), _) => Ret::ValueKind(BoolLit(true)),
+ (BoolOr, _, BoolLit(true)) => Ret::ValueKind(BoolLit(true)),
+ (BoolOr, BoolLit(false), _) => Ret::ValueRef(y),
+ (BoolOr, _, BoolLit(false)) => Ret::ValueRef(x),
+ (BoolOr, _, _) if x == y => Ret::ValueRef(x),
+ (BoolEQ, BoolLit(true), _) => Ret::ValueRef(y),
+ (BoolEQ, _, BoolLit(true)) => Ret::ValueRef(x),
+ (BoolEQ, BoolLit(x), BoolLit(y)) => Ret::ValueKind(BoolLit(x == y)),
+ (BoolEQ, _, _) if x == y => Ret::ValueKind(BoolLit(true)),
+ (BoolNE, BoolLit(false), _) => Ret::ValueRef(y),
+ (BoolNE, _, BoolLit(false)) => Ret::ValueRef(x),
+ (BoolNE, BoolLit(x), BoolLit(y)) => Ret::ValueKind(BoolLit(x != y)),
+ (BoolNE, _, _) if x == y => Ret::ValueKind(BoolLit(false)),
+
+ (NaturalPlus, NaturalLit(0), _) => Ret::ValueRef(y),
+ (NaturalPlus, _, NaturalLit(0)) => Ret::ValueRef(x),
+ (NaturalPlus, NaturalLit(x), NaturalLit(y)) => {
+ Ret::ValueKind(NaturalLit(x + y))
+ }
+ (NaturalTimes, NaturalLit(0), _) => Ret::ValueKind(NaturalLit(0)),
+ (NaturalTimes, _, NaturalLit(0)) => Ret::ValueKind(NaturalLit(0)),
+ (NaturalTimes, NaturalLit(1), _) => Ret::ValueRef(y),
+ (NaturalTimes, _, NaturalLit(1)) => Ret::ValueRef(x),
+ (NaturalTimes, NaturalLit(x), NaturalLit(y)) => {
+ Ret::ValueKind(NaturalLit(x * y))
+ }
+
+ (ListAppend, EmptyListLit(_), _) => Ret::ValueRef(y),
+ (ListAppend, _, EmptyListLit(_)) => Ret::ValueRef(x),
+ (ListAppend, NEListLit(xs), NEListLit(ys)) => Ret::ValueKind(
+ NEListLit(xs.iter().chain(ys.iter()).cloned().collect()),
+ ),
+
+ (TextAppend, ValueKind::TextLit(x), _) if x.is_empty() => {
+ Ret::ValueRef(y)
+ }
+ (TextAppend, _, ValueKind::TextLit(y)) if y.is_empty() => {
+ Ret::ValueRef(x)
+ }
+ (TextAppend, ValueKind::TextLit(x), ValueKind::TextLit(y)) => {
+ Ret::ValueKind(ValueKind::TextLit(x.concat(y)))
+ }
+ (TextAppend, ValueKind::TextLit(x), _) => Ret::ValueKind(
+ ValueKind::TextLit(x.concat(&TextLit::interpolate(y.clone()))),
+ ),
+ (TextAppend, _, ValueKind::TextLit(y)) => Ret::ValueKind(
+ ValueKind::TextLit(TextLit::interpolate(x.clone()).concat(y)),
+ ),
+
+ (RightBiasedRecordMerge, _, RecordLit(kvs)) if kvs.is_empty() => {
+ Ret::ValueRef(x)
+ }
+ (RightBiasedRecordMerge, RecordLit(kvs), _) if kvs.is_empty() => {
+ Ret::ValueRef(y)
+ }
+ (RightBiasedRecordMerge, RecordLit(kvs1), RecordLit(kvs2)) => {
+ let mut kvs = kvs2.clone();
+ for (x, v) in kvs1 {
+ // Insert only if key not already present
+ kvs.entry(x.clone()).or_insert_with(|| v.clone());
+ }
+ Ret::ValueKind(RecordLit(kvs))
+ }
+
+ (RecursiveRecordMerge, _, RecordLit(kvs)) if kvs.is_empty() => {
+ Ret::ValueRef(x)
+ }
+ (RecursiveRecordMerge, RecordLit(kvs), _) if kvs.is_empty() => {
+ Ret::ValueRef(y)
+ }
+ (RecursiveRecordMerge, RecordLit(kvs1), RecordLit(kvs2)) => {
+ let kts = match ty.kind() {
+ RecordType(kts) => kts,
+ _ => unreachable!("Internal type error"),
+ };
+ let kvs = merge_maps::<_, _, _, !>(kvs1, kvs2, |k, v1, v2| {
+ Ok(Value::from_partial_expr(
+ ExprKind::BinOp(
+ RecursiveRecordMerge,
+ v1.clone(),
+ v2.clone(),
+ ),
+ kts.get(k).expect("Internal type error").clone(),
+ ))
+ })?;
+ Ret::ValueKind(RecordLit(kvs))
+ }
+
+ (RecursiveRecordTypeMerge, RecordType(kts_x), RecordType(kts_y)) => {
+ let kts = merge_maps::<_, _, _, !>(
+ kts_x,
+ kts_y,
+ // If the Label exists for both records, then we hit the recursive case.
+ |_, l: &Value, r: &Value| {
+ Ok(Value::from_partial_expr(
+ ExprKind::BinOp(
+ RecursiveRecordTypeMerge,
+ l.clone(),
+ r.clone(),
+ ),
+ ty.clone(),
+ ))
+ },
+ )?;
+ Ret::ValueKind(RecordType(kts))
+ }
+
+ (Equivalence, _, _) => {
+ Ret::ValueKind(ValueKind::Equivalence(x.clone(), y.clone()))
+ }
+
+ _ => return None,
+ })
+}
+
+pub(crate) fn normalize_one_layer(
+ expr: ExprKind<Value, Normalized>,
+ ty: &Value,
+ env: &NzEnv,
+) -> ValueKind {
+ use ValueKind::{
+ BoolLit, DoubleLit, EmptyOptionalLit, IntegerLit, NEListLit,
+ NEOptionalLit, NaturalLit, RecordLit, RecordType, UnionConstructor,
+ UnionLit, UnionType,
+ };
+
+ let ret = match expr {
+ ExprKind::Import(_) => unreachable!(
+ "There should remain no imports in a resolved expression"
+ ),
+ // Those cases have already been completely handled in the typechecking phase (using
+ // `RetWhole`), so they won't appear here.
+ ExprKind::Lam(..)
+ | ExprKind::Pi(..)
+ | ExprKind::Let(..)
+ | ExprKind::Embed(_)
+ | ExprKind::Var(_) => {
+ unreachable!("This case should have been handled in typecheck")
+ }
+ ExprKind::Annot(x, _) => Ret::Value(x),
+ ExprKind::Const(c) => Ret::Value(Value::from_const(c)),
+ ExprKind::Builtin(b) => Ret::Value(Value::from_builtin_env(b, env)),
+ ExprKind::Assert(_) => Ret::Expr(expr),
+ ExprKind::App(v, a) => Ret::Value(v.app(a)),
+ ExprKind::BoolLit(b) => Ret::ValueKind(BoolLit(b)),
+ ExprKind::NaturalLit(n) => Ret::ValueKind(NaturalLit(n)),
+ ExprKind::IntegerLit(n) => Ret::ValueKind(IntegerLit(n)),
+ ExprKind::DoubleLit(n) => Ret::ValueKind(DoubleLit(n)),
+ ExprKind::SomeLit(e) => Ret::ValueKind(NEOptionalLit(e)),
+ ExprKind::EmptyListLit(t) => {
+ let arg = match &*t.kind() {
+ ValueKind::AppliedBuiltin(BuiltinClosure {
+ b: Builtin::List,
+ args,
+ ..
+ }) if args.len() == 1 => args[0].clone(),
+ _ => panic!("internal type error"),
+ };
+ Ret::ValueKind(ValueKind::EmptyListLit(arg))
+ }
+ ExprKind::NEListLit(elts) => {
+ Ret::ValueKind(NEListLit(elts.into_iter().collect()))
+ }
+ ExprKind::RecordLit(kvs) => {
+ Ret::ValueKind(RecordLit(kvs.into_iter().collect()))
+ }
+ ExprKind::RecordType(kvs) => {
+ Ret::ValueKind(RecordType(kvs.into_iter().collect()))
+ }
+ ExprKind::UnionType(kvs) => {
+ Ret::ValueKind(UnionType(kvs.into_iter().collect()))
+ }
+ ExprKind::TextLit(elts) => {
+ let tlit = TextLit::new(elts.into_iter());
+ // Simplify bare interpolation
+ if let Some(v) = tlit.as_single_expr() {
+ Ret::Value(v.clone())
+ } else {
+ Ret::ValueKind(ValueKind::TextLit(tlit))
+ }
+ }
+ ExprKind::BoolIf(ref b, ref e1, ref e2) => {
+ match b.kind() {
+ BoolLit(true) => Ret::ValueRef(e1),
+ BoolLit(false) => Ret::ValueRef(e2),
+ _ => {
+ match (e1.kind(), e2.kind()) {
+ // Simplify `if b then True else False`
+ (BoolLit(true), BoolLit(false)) => Ret::ValueRef(b),
+ _ if e1 == e2 => Ret::ValueRef(e1),
+ _ => Ret::Expr(expr),
+ }
+ }
+ }
+ }
+ ExprKind::BinOp(o, ref x, ref y) => match apply_binop(o, x, y, ty) {
+ Some(ret) => ret,
+ None => Ret::Expr(expr),
+ },
+
+ ExprKind::Projection(_, ref ls) if ls.is_empty() => {
+ Ret::ValueKind(RecordLit(HashMap::new()))
+ }
+ ExprKind::Projection(ref v, ref ls) => match v.kind() {
+ RecordLit(kvs) => Ret::ValueKind(RecordLit(
+ ls.iter()
+ .filter_map(|l| kvs.get(l).map(|x| (l.clone(), x.clone())))
+ .collect(),
+ )),
+ _ => Ret::Expr(expr),
+ },
+ ExprKind::Field(ref v, ref l) => match v.kind() {
+ RecordLit(kvs) => match kvs.get(l) {
+ Some(r) => Ret::Value(r.clone()),
+ None => Ret::Expr(expr),
+ },
+ UnionType(kts) => Ret::ValueKind(UnionConstructor(
+ l.clone(),
+ kts.clone(),
+ v.get_type().unwrap(),
+ )),
+ _ => Ret::Expr(expr),
+ },
+ ExprKind::ProjectionByExpr(_, _) => {
+ unimplemented!("selection by expression")
+ }
+ ExprKind::Completion(_, _) => unimplemented!("record completion"),
+
+ ExprKind::Merge(ref handlers, ref variant, _) => {
+ match handlers.kind() {
+ RecordLit(kvs) => match variant.kind() {
+ UnionConstructor(l, _, _) => match kvs.get(l) {
+ Some(h) => Ret::Value(h.clone()),
+ None => Ret::Expr(expr),
+ },
+ UnionLit(l, v, _, _, _) => match kvs.get(l) {
+ Some(h) => Ret::Value(h.app(v.clone())),
+ None => Ret::Expr(expr),
+ },
+ EmptyOptionalLit(_) => match kvs.get(&"None".into()) {
+ Some(h) => Ret::Value(h.clone()),
+ None => Ret::Expr(expr),
+ },
+ NEOptionalLit(v) => match kvs.get(&"Some".into()) {
+ Some(h) => Ret::Value(h.app(v.clone())),
+ None => Ret::Expr(expr),
+ },
+ _ => Ret::Expr(expr),
+ },
+ _ => Ret::Expr(expr),
+ }
+ }
+ ExprKind::ToMap(_, _) => unimplemented!("toMap"),
+ };
+
+ match ret {
+ Ret::ValueKind(v) => v,
+ Ret::Value(v) => v.to_whnf_check_type(ty),
+ Ret::ValueRef(v) => v.to_whnf_check_type(ty),
+ Ret::Expr(expr) => ValueKind::PartialExpr(expr),
+ }
+}
+
+/// Normalize a TyExpr into WHNF
+pub(crate) fn normalize_tyexpr_whnf(tye: &TyExpr, env: &NzEnv) -> ValueKind {
+ match tye.kind() {
+ TyExprKind::Var(var) => env.lookup_val(var),
+ TyExprKind::Expr(ExprKind::Lam(binder, annot, body)) => {
+ let annot = annot.eval(env);
+ ValueKind::LamClosure {
+ binder: Binder::new(binder.clone()),
+ annot: annot.clone(),
+ closure: Closure::new(annot, env, body.clone()),
+ }
+ }
+ TyExprKind::Expr(ExprKind::Pi(binder, annot, body)) => {
+ let annot = annot.eval(env);
+ let closure = Closure::new(annot.clone(), env, body.clone());
+ ValueKind::PiClosure {
+ binder: Binder::new(binder.clone()),
+ annot,
+ closure,
+ }
+ }
+ TyExprKind::Expr(ExprKind::Let(_, None, val, body)) => {
+ let val = val.eval(env);
+ body.eval(&env.insert_value(val)).kind().clone()
+ }
+ TyExprKind::Expr(e) => {
+ let ty = match tye.get_type() {
+ Ok(ty) => ty,
+ Err(_) => return ValueKind::Const(Const::Sort),
+ };
+ let e = e.map_ref(|tye| tye.eval(env));
+ normalize_one_layer(e, &ty, env)
+ }
+ }
+}
diff --git a/dhall/src/semantics/nze/value.rs b/dhall/src/semantics/nze/value.rs
new file mode 100644
index 0000000..ae06942
--- /dev/null
+++ b/dhall/src/semantics/nze/value.rs
@@ -0,0 +1,656 @@
+use std::collections::HashMap;
+use std::rc::Rc;
+
+use crate::error::{TypeError, TypeMessage};
+use crate::semantics::nze::lazy;
+use crate::semantics::Binder;
+use crate::semantics::{
+ apply_any, normalize_one_layer, normalize_tyexpr_whnf, squash_textlit,
+};
+use crate::semantics::{type_of_builtin, typecheck, TyExpr, TyExprKind};
+use crate::semantics::{BuiltinClosure, NzEnv, NzVar, VarEnv};
+use crate::syntax::{
+ BinOp, Builtin, Const, ExprKind, Integer, InterpolatedTextContents, Label,
+ NaiveDouble, Natural, Span,
+};
+use crate::{Normalized, NormalizedExpr, ToExprOptions};
+
+/// Stores a possibly unevaluated value. Gets (partially) normalized on-demand, sharing computation
+/// automatically. Uses a Rc<RefCell> to share computation.
+/// If you compare for equality two `Value`s, then equality will be up to alpha-equivalence
+/// (renaming of bound variables) and beta-equivalence (normalization). It will recursively
+/// normalize as needed.
+#[derive(Clone)]
+pub(crate) struct Value(Rc<ValueInternal>);
+
+#[derive(Debug)]
+struct ValueInternal {
+ kind: lazy::Lazy<Thunk, ValueKind>,
+ /// This is None if and only if `form` is `Sort` (which doesn't have a type)
+ ty: Option<Value>,
+ span: Span,
+}
+
+/// An unevaluated subexpression
+#[derive(Debug, Clone)]
+pub(crate) enum Thunk {
+ /// A completely unnormalized expression.
+ Thunk { env: NzEnv, body: TyExpr },
+ /// A partially normalized expression that may need to go through `normalize_one_layer`.
+ PartialExpr {
+ env: NzEnv,
+ expr: ExprKind<Value, Normalized>,
+ ty: Value,
+ },
+}
+
+/// An unevaluated subexpression that takes an argument.
+#[derive(Debug, Clone)]
+pub(crate) enum Closure {
+ /// Normal closure
+ Closure {
+ arg_ty: Value,
+ env: NzEnv,
+ body: TyExpr,
+ },
+ /// Closure that ignores the argument passed
+ ConstantClosure { body: Value },
+}
+
+/// A text literal with interpolations.
+// Invariant: this must not contain interpolations that are themselves TextLits, and contiguous
+// text values must be merged.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub(crate) struct TextLit(Vec<InterpolatedTextContents<Value>>);
+
+/// This represents a value in Weak Head Normal Form (WHNF). This means that the value is
+/// normalized up to the first constructor, but subexpressions may not be fully normalized.
+/// When all the Values in a ValueKind are in WHNF, and recursively so, then the ValueKind is in
+/// Normal Form (NF). This is because WHNF ensures that we have the first constructor of the NF; so
+/// if we have the first constructor of the NF at all levels, we actually have the NF.
+/// In particular, this means that once we get a `ValueKind`, it can be considered immutable, and
+/// we only need to recursively normalize its sub-`Value`s to get to the NF.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub(crate) enum ValueKind {
+ /// Closures
+ LamClosure {
+ binder: Binder,
+ annot: Value,
+ closure: Closure,
+ },
+ PiClosure {
+ binder: Binder,
+ annot: Value,
+ closure: Closure,
+ },
+ AppliedBuiltin(BuiltinClosure<Value>),
+
+ Var(NzVar),
+ Const(Const),
+ BoolLit(bool),
+ NaturalLit(Natural),
+ IntegerLit(Integer),
+ DoubleLit(NaiveDouble),
+ EmptyOptionalLit(Value),
+ NEOptionalLit(Value),
+ // EmptyListLit(t) means `[] : List t`, not `[] : t`
+ EmptyListLit(Value),
+ NEListLit(Vec<Value>),
+ RecordType(HashMap<Label, Value>),
+ RecordLit(HashMap<Label, Value>),
+ UnionType(HashMap<Label, Option<Value>>),
+ // Also keep the type of the uniontype around
+ UnionConstructor(Label, HashMap<Label, Option<Value>>, Value),
+ // Also keep the type of the uniontype and the constructor around
+ UnionLit(Label, Value, HashMap<Label, Option<Value>>, Value, Value),
+ TextLit(TextLit),
+ Equivalence(Value, Value),
+ /// Invariant: evaluation must not be able to progress with `normalize_one_layer`?
+ PartialExpr(ExprKind<Value, Normalized>),
+}
+
+impl Value {
+ pub(crate) fn const_sort() -> Value {
+ ValueInternal::from_whnf(
+ ValueKind::Const(Const::Sort),
+ None,
+ Span::Artificial,
+ )
+ .into_value()
+ }
+ /// Construct a Value from a completely unnormalized expression.
+ pub(crate) fn new_thunk(env: &NzEnv, tye: TyExpr) -> Value {
+ ValueInternal::from_thunk(
+ Thunk::new(env, tye.clone()),
+ tye.get_type().ok(),
+ tye.span().clone(),
+ )
+ .into_value()
+ }
+ /// Construct a Value from a partially normalized expression that's not in WHNF.
+ pub(crate) fn from_partial_expr(
+ e: ExprKind<Value, Normalized>,
+ ty: Value,
+ ) -> Value {
+ // TODO: env
+ let env = NzEnv::new();
+ ValueInternal::from_thunk(
+ Thunk::from_partial_expr(env, e, ty.clone()),
+ Some(ty),
+ Span::Artificial,
+ )
+ .into_value()
+ }
+ /// Make a Value from a ValueKind
+ pub(crate) fn from_kind_and_type(v: ValueKind, t: Value) -> Value {
+ ValueInternal::from_whnf(v, Some(t), Span::Artificial).into_value()
+ }
+ pub(crate) fn from_const(c: Const) -> Self {
+ let v = ValueKind::Const(c);
+ match c {
+ Const::Type => {
+ Value::from_kind_and_type(v, Value::from_const(Const::Kind))
+ }
+ Const::Kind => {
+ Value::from_kind_and_type(v, Value::from_const(Const::Sort))
+ }
+ Const::Sort => Value::const_sort(),
+ }
+ }
+ pub(crate) fn from_builtin(b: Builtin) -> Self {
+ Self::from_builtin_env(b, &NzEnv::new())
+ }
+ pub(crate) fn from_builtin_env(b: Builtin, env: &NzEnv) -> Self {
+ Value::from_kind_and_type(
+ ValueKind::from_builtin_env(b, env.clone()),
+ typecheck(&type_of_builtin(b)).unwrap().eval_closed_expr(),
+ )
+ }
+
+ pub(crate) fn as_const(&self) -> Option<Const> {
+ match &*self.kind() {
+ ValueKind::Const(c) => Some(*c),
+ _ => None,
+ }
+ }
+ pub(crate) fn span(&self) -> Span {
+ self.0.span.clone()
+ }
+
+ /// This is what you want if you want to pattern-match on the value.
+ /// WARNING: drop this ref before normalizing the same value or you will run into BorrowMut
+ /// panics.
+ pub(crate) fn kind(&self) -> &ValueKind {
+ self.0.kind()
+ }
+
+ /// Converts a value back to the corresponding AST expression.
+ pub(crate) fn to_expr(&self, opts: ToExprOptions) -> NormalizedExpr {
+ if opts.normalize {
+ self.normalize();
+ }
+
+ self.to_tyexpr_noenv().to_expr(opts)
+ }
+ pub(crate) fn to_whnf_ignore_type(&self) -> ValueKind {
+ self.kind().clone()
+ }
+ /// Before discarding type information, check that it matches the expected return type.
+ pub(crate) fn to_whnf_check_type(&self, ty: &Value) -> ValueKind {
+ self.check_type(ty);
+ self.to_whnf_ignore_type()
+ }
+
+ /// Normalizes contents to normal form; faster than `normalize` if
+ /// no one else shares this.
+ pub(crate) fn normalize_mut(&mut self) {
+ match Rc::get_mut(&mut self.0) {
+ // Mutate directly if sole owner
+ Some(vint) => vint.normalize_mut(),
+ // Otherwise mutate through the refcell
+ None => self.normalize(),
+ }
+ }
+ pub(crate) fn normalize(&self) {
+ self.0.normalize()
+ }
+
+ pub(crate) fn app(&self, v: Value) -> Value {
+ let body_t = match &*self.get_type_not_sort().kind() {
+ ValueKind::PiClosure { annot, closure, .. } => {
+ v.check_type(annot);
+ closure.apply(v.clone())
+ }
+ _ => unreachable!("Internal type error"),
+ };
+ Value::from_kind_and_type(apply_any(self.clone(), v, &body_t), body_t)
+ }
+
+ /// In debug mode, panic if the provided type doesn't match the value's type.
+ /// Otherwise does nothing.
+ pub(crate) fn check_type(&self, _ty: &Value) {
+ // TODO: reenable
+ // debug_assert_eq!(
+ // Some(ty),
+ // self.get_type().ok().as_ref(),
+ // "Internal type error"
+ // );
+ }
+ pub(crate) fn get_type(&self) -> Result<Value, TypeError> {
+ Ok(self.0.get_type()?.clone())
+ }
+ /// When we know the value isn't `Sort`, this gets the type directly
+ pub(crate) fn get_type_not_sort(&self) -> Value {
+ self.get_type()
+ .expect("Internal type error: value is `Sort` but shouldn't be")
+ }
+
+ pub fn to_tyexpr(&self, venv: VarEnv) -> TyExpr {
+ let map_uniontype = |kts: &HashMap<Label, Option<Value>>| {
+ ExprKind::UnionType(
+ kts.iter()
+ .map(|(k, v)| {
+ (k.clone(), v.as_ref().map(|v| v.to_tyexpr(venv)))
+ })
+ .collect(),
+ )
+ };
+
+ let tye = match &*self.kind() {
+ ValueKind::Var(v) => TyExprKind::Var(venv.lookup(v)),
+ ValueKind::AppliedBuiltin(closure) => closure.to_tyexprkind(venv),
+ self_kind => TyExprKind::Expr(match self_kind {
+ ValueKind::Var(..) | ValueKind::AppliedBuiltin(..) => {
+ unreachable!()
+ }
+ ValueKind::LamClosure {
+ binder,
+ annot,
+ closure,
+ } => ExprKind::Lam(
+ binder.to_label(),
+ annot.to_tyexpr(venv),
+ closure.to_tyexpr(venv),
+ ),
+ ValueKind::PiClosure {
+ binder,
+ annot,
+ closure,
+ } => ExprKind::Pi(
+ binder.to_label(),
+ annot.to_tyexpr(venv),
+ closure.to_tyexpr(venv),
+ ),
+ ValueKind::Const(c) => ExprKind::Const(*c),
+ ValueKind::BoolLit(b) => ExprKind::BoolLit(*b),
+ ValueKind::NaturalLit(n) => ExprKind::NaturalLit(*n),
+ ValueKind::IntegerLit(n) => ExprKind::IntegerLit(*n),
+ ValueKind::DoubleLit(n) => ExprKind::DoubleLit(*n),
+ ValueKind::EmptyOptionalLit(n) => ExprKind::App(
+ Value::from_builtin(Builtin::OptionalNone).to_tyexpr(venv),
+ n.to_tyexpr(venv),
+ ),
+ ValueKind::NEOptionalLit(n) => {
+ ExprKind::SomeLit(n.to_tyexpr(venv))
+ }
+ ValueKind::EmptyListLit(n) => {
+ ExprKind::EmptyListLit(TyExpr::new(
+ TyExprKind::Expr(ExprKind::App(
+ Value::from_builtin(Builtin::List).to_tyexpr(venv),
+ n.to_tyexpr(venv),
+ )),
+ Some(Value::from_const(Const::Type)),
+ Span::Artificial,
+ ))
+ }
+ ValueKind::NEListLit(elts) => ExprKind::NEListLit(
+ elts.iter().map(|v| v.to_tyexpr(venv)).collect(),
+ ),
+ ValueKind::TextLit(elts) => ExprKind::TextLit(
+ elts.iter()
+ .map(|t| t.map_ref(|v| v.to_tyexpr(venv)))
+ .collect(),
+ ),
+ ValueKind::RecordLit(kvs) => ExprKind::RecordLit(
+ kvs.iter()
+ .map(|(k, v)| (k.clone(), v.to_tyexpr(venv)))
+ .collect(),
+ ),
+ ValueKind::RecordType(kts) => ExprKind::RecordType(
+ kts.iter()
+ .map(|(k, v)| (k.clone(), v.to_tyexpr(venv)))
+ .collect(),
+ ),
+ ValueKind::UnionType(kts) => map_uniontype(kts),
+ ValueKind::UnionConstructor(l, kts, t) => ExprKind::Field(
+ TyExpr::new(
+ TyExprKind::Expr(map_uniontype(kts)),
+ Some(t.clone()),
+ Span::Artificial,
+ ),
+ l.clone(),
+ ),
+ ValueKind::UnionLit(l, v, kts, uniont, ctort) => ExprKind::App(
+ TyExpr::new(
+ TyExprKind::Expr(ExprKind::Field(
+ TyExpr::new(
+ TyExprKind::Expr(map_uniontype(kts)),
+ Some(uniont.clone()),
+ Span::Artificial,
+ ),
+ l.clone(),
+ )),
+ Some(ctort.clone()),
+ Span::Artificial,
+ ),
+ v.to_tyexpr(venv),
+ ),
+ ValueKind::Equivalence(x, y) => ExprKind::BinOp(
+ BinOp::Equivalence,
+ x.to_tyexpr(venv),
+ y.to_tyexpr(venv),
+ ),
+ ValueKind::PartialExpr(e) => e.map_ref(|v| v.to_tyexpr(venv)),
+ }),
+ };
+
+ TyExpr::new(tye, self.0.ty.clone(), self.0.span.clone())
+ }
+ pub fn to_tyexpr_noenv(&self) -> TyExpr {
+ self.to_tyexpr(VarEnv::new())
+ }
+}
+
+impl ValueInternal {
+ fn from_whnf(k: ValueKind, ty: Option<Value>, span: Span) -> Self {
+ ValueInternal {
+ kind: lazy::Lazy::new_completed(k),
+ ty,
+ span,
+ }
+ }
+ fn from_thunk(th: Thunk, ty: Option<Value>, span: Span) -> Self {
+ ValueInternal {
+ kind: lazy::Lazy::new(th),
+ ty,
+ span,
+ }
+ }
+ fn into_value(self) -> Value {
+ Value(Rc::new(self))
+ }
+
+ fn kind(&self) -> &ValueKind {
+ &self.kind
+ }
+ fn normalize(&self) {
+ self.kind().normalize();
+ }
+ // TODO: deprecated
+ fn normalize_mut(&mut self) {
+ self.normalize();
+ }
+
+ fn get_type(&self) -> Result<&Value, TypeError> {
+ match &self.ty {
+ Some(t) => Ok(t),
+ None => Err(TypeError::new(TypeMessage::Sort)),
+ }
+ }
+}
+
+impl ValueKind {
+ pub(crate) fn into_value_with_type(self, t: Value) -> Value {
+ Value::from_kind_and_type(self, t)
+ }
+
+ pub(crate) fn normalize(&self) {
+ match self {
+ ValueKind::Var(..)
+ | ValueKind::Const(_)
+ | ValueKind::BoolLit(_)
+ | ValueKind::NaturalLit(_)
+ | ValueKind::IntegerLit(_)
+ | ValueKind::DoubleLit(_) => {}
+
+ ValueKind::EmptyOptionalLit(tth) | ValueKind::EmptyListLit(tth) => {
+ tth.normalize();
+ }
+
+ ValueKind::NEOptionalLit(th) => {
+ th.normalize();
+ }
+ ValueKind::LamClosure { annot, closure, .. }
+ | ValueKind::PiClosure { annot, closure, .. } => {
+ annot.normalize();
+ closure.normalize();
+ }
+ ValueKind::AppliedBuiltin(closure) => closure.normalize(),
+ ValueKind::NEListLit(elts) => {
+ for x in elts.iter() {
+ x.normalize();
+ }
+ }
+ ValueKind::RecordLit(kvs) => {
+ for x in kvs.values() {
+ x.normalize();
+ }
+ }
+ ValueKind::RecordType(kvs) => {
+ for x in kvs.values() {
+ x.normalize();
+ }
+ }
+ ValueKind::UnionType(kts)
+ | ValueKind::UnionConstructor(_, kts, _) => {
+ for x in kts.values().flat_map(|opt| opt) {
+ x.normalize();
+ }
+ }
+ ValueKind::UnionLit(_, v, kts, _, _) => {
+ v.normalize();
+ for x in kts.values().flat_map(|opt| opt) {
+ x.normalize();
+ }
+ }
+ ValueKind::TextLit(tlit) => tlit.normalize(),
+ ValueKind::Equivalence(x, y) => {
+ x.normalize();
+ y.normalize();
+ }
+ ValueKind::PartialExpr(e) => {
+ e.map_ref(Value::normalize);
+ }
+ }
+ }
+
+ pub(crate) fn from_builtin(b: Builtin) -> ValueKind {
+ ValueKind::from_builtin_env(b, NzEnv::new())
+ }
+ pub(crate) fn from_builtin_env(b: Builtin, env: NzEnv) -> ValueKind {
+ ValueKind::AppliedBuiltin(BuiltinClosure::new(b, env))
+ }
+}
+
+impl Thunk {
+ pub fn new(env: &NzEnv, body: TyExpr) -> Self {
+ Thunk::Thunk {
+ env: env.clone(),
+ body,
+ }
+ }
+ pub fn from_partial_expr(
+ env: NzEnv,
+ expr: ExprKind<Value, Normalized>,
+ ty: Value,
+ ) -> Self {
+ Thunk::PartialExpr { env, expr, ty }
+ }
+ pub fn eval(self) -> ValueKind {
+ match self {
+ Thunk::Thunk { env, body } => normalize_tyexpr_whnf(&body, &env),
+ Thunk::PartialExpr { env, expr, ty } => {
+ normalize_one_layer(expr, &ty, &env)
+ }
+ }
+ }
+}
+
+impl Closure {
+ pub fn new(arg_ty: Value, env: &NzEnv, body: TyExpr) -> Self {
+ Closure::Closure {
+ arg_ty,
+ env: env.clone(),
+ body,
+ }
+ }
+ /// New closure that ignores its argument
+ pub fn new_constant(body: Value) -> Self {
+ Closure::ConstantClosure { body }
+ }
+
+ pub fn apply(&self, val: Value) -> Value {
+ match self {
+ Closure::Closure { env, body, .. } => {
+ body.eval(&env.insert_value(val))
+ }
+ Closure::ConstantClosure { body, .. } => body.clone(),
+ }
+ }
+ fn apply_var(&self, var: NzVar) -> Value {
+ match self {
+ Closure::Closure { arg_ty, .. } => {
+ let val = Value::from_kind_and_type(
+ ValueKind::Var(var),
+ arg_ty.clone(),
+ );
+ self.apply(val)
+ }
+ Closure::ConstantClosure { body, .. } => body.clone(),
+ }
+ }
+
+ // TODO: somehow normalize the body. Might require to pass an env.
+ pub fn normalize(&self) {}
+ /// Convert this closure to a TyExpr
+ pub fn to_tyexpr(&self, venv: VarEnv) -> TyExpr {
+ self.apply_var(NzVar::new(venv.size()))
+ .to_tyexpr(venv.insert())
+ }
+ /// If the closure variable is free in the closure, return Err. Otherwise, return the value
+ /// with that free variable remove.
+ pub fn remove_binder(&self) -> Result<Value, ()> {
+ match self {
+ Closure::Closure { .. } => {
+ let v = NzVar::fresh();
+ // TODO: handle case where variable is used in closure
+ // TODO: return information about where the variable is used
+ Ok(self.apply_var(v))
+ }
+ Closure::ConstantClosure { body, .. } => Ok(body.clone()),
+ }
+ }
+}
+
+impl TextLit {
+ pub fn new(
+ elts: impl Iterator<Item = InterpolatedTextContents<Value>>,
+ ) -> Self {
+ TextLit(squash_textlit(elts))
+ }
+ pub fn interpolate(v: Value) -> TextLit {
+ TextLit(vec![InterpolatedTextContents::Expr(v)])
+ }
+ pub fn from_text(s: String) -> TextLit {
+ TextLit(vec![InterpolatedTextContents::Text(s)])
+ }
+
+ pub fn concat(&self, other: &TextLit) -> TextLit {
+ TextLit::new(self.iter().chain(other.iter()).cloned())
+ }
+ pub fn is_empty(&self) -> bool {
+ self.0.is_empty()
+ }
+ /// If the literal consists of only one interpolation and not text, return the interpolated
+ /// value.
+ pub fn as_single_expr(&self) -> Option<&Value> {
+ use InterpolatedTextContents::Expr;
+ if let [Expr(v)] = self.0.as_slice() {
+ Some(v)
+ } else {
+ None
+ }
+ }
+ /// If there are no interpolations, return the corresponding text value.
+ pub fn as_text(&self) -> Option<String> {
+ use InterpolatedTextContents::Text;
+ if self.is_empty() {
+ Some(String::new())
+ } else if let [Text(s)] = self.0.as_slice() {
+ Some(s.clone())
+ } else {
+ None
+ }
+ }
+ pub fn iter(
+ &self,
+ ) -> impl Iterator<Item = &InterpolatedTextContents<Value>> {
+ self.0.iter()
+ }
+ /// Normalize the contained values. This does not break the invariant because we have already
+ /// ensured that no contained values normalize to a TextLit.
+ pub fn normalize(&self) {
+ for x in self.0.iter() {
+ x.map_ref(Value::normalize);
+ }
+ }
+}
+
+impl lazy::Eval<ValueKind> for Thunk {
+ fn eval(self) -> ValueKind {
+ self.eval()
+ }
+}
+
+/// Compare two values for equality modulo alpha/beta-equivalence.
+impl std::cmp::PartialEq for Value {
+ fn eq(&self, other: &Self) -> bool {
+ Rc::ptr_eq(&self.0, &other.0) || self.kind() == other.kind()
+ }
+}
+impl std::cmp::Eq for Value {}
+
+impl std::cmp::PartialEq for Thunk {
+ fn eq(&self, _other: &Self) -> bool {
+ unreachable!(
+ "Trying to compare thunks but we should only compare WHNFs"
+ )
+ }
+}
+impl std::cmp::Eq for Thunk {}
+
+impl std::cmp::PartialEq for Closure {
+ fn eq(&self, other: &Self) -> bool {
+ let v = NzVar::fresh();
+ self.apply_var(v) == other.apply_var(v)
+ }
+}
+impl std::cmp::Eq for Closure {}
+
+impl std::fmt::Debug for Value {
+ fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ let vint: &ValueInternal = &self.0;
+ let kind = vint.kind();
+ if let ValueKind::Const(c) = kind {
+ return write!(fmt, "{:?}", c);
+ }
+ let mut x = fmt.debug_struct(&format!("Value@WHNF"));
+ x.field("kind", kind);
+ if let Some(ty) = vint.ty.as_ref() {
+ x.field("type", &ty);
+ } else {
+ x.field("type", &None::<()>);
+ }
+ x.finish()
+ }
+}
diff --git a/dhall/src/semantics/nze/var.rs b/dhall/src/semantics/nze/var.rs
new file mode 100644
index 0000000..264b81d
--- /dev/null
+++ b/dhall/src/semantics/nze/var.rs
@@ -0,0 +1,36 @@
+use crate::syntax::Label;
+
+// Exactly like a Label, but equality returns always true.
+// This is so that ValueKind equality is exactly alpha-equivalence.
+#[derive(Clone, Eq)]
+pub struct Binder {
+ name: Label,
+}
+
+impl Binder {
+ pub(crate) fn new(name: Label) -> Self {
+ Binder { name }
+ }
+ pub(crate) fn to_label(&self) -> Label {
+ self.clone().into()
+ }
+}
+
+/// Equality up to alpha-equivalence
+impl std::cmp::PartialEq for Binder {
+ fn eq(&self, _other: &Self) -> bool {
+ true
+ }
+}
+
+impl std::fmt::Debug for Binder {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "Binder({})", &self.name)
+ }
+}
+
+impl From<Binder> for Label {
+ fn from(x: Binder) -> Label {
+ x.name
+ }
+}
diff --git a/dhall/src/semantics/phase/parse.rs b/dhall/src/semantics/parse.rs
index 00db422..ee35536 100644
--- a/dhall/src/semantics/phase/parse.rs
+++ b/dhall/src/semantics/parse.rs
@@ -3,10 +3,10 @@ use std::io::Read;
use std::path::Path;
use crate::error::Error;
-use crate::semantics::phase::resolve::ImportRoot;
-use crate::semantics::phase::Parsed;
+use crate::semantics::resolve::ImportRoot;
use crate::syntax::binary;
use crate::syntax::parse_expr;
+use crate::Parsed;
pub(crate) fn parse_file(f: &Path) -> Result<Parsed, Error> {
let mut buffer = String::new();
diff --git a/dhall/src/semantics/phase/mod.rs b/dhall/src/semantics/phase/mod.rs
deleted file mode 100644
index 5332eb3..0000000
--- a/dhall/src/semantics/phase/mod.rs
+++ /dev/null
@@ -1,259 +0,0 @@
-use std::fmt::Display;
-use std::path::Path;
-
-use crate::error::{EncodeError, Error, ImportError, TypeError};
-use crate::semantics::core::value::Value;
-use crate::semantics::core::value::ValueKind;
-use crate::semantics::core::var::{AlphaVar, Shift, Subst};
-use crate::semantics::to_expr::ToExprOptions;
-use crate::syntax::binary;
-use crate::syntax::{Builtin, Const, Expr};
-use resolve::ImportRoot;
-
-pub(crate) mod normalize;
-pub(crate) mod parse;
-pub(crate) mod resolve;
-pub(crate) mod typecheck;
-
-pub type ParsedExpr = Expr<Normalized>;
-pub type DecodedExpr = Expr<Normalized>;
-pub type ResolvedExpr = Expr<Normalized>;
-pub type NormalizedExpr = Expr<Normalized>;
-
-#[derive(Debug, Clone)]
-pub struct Parsed(ParsedExpr, ImportRoot);
-
-/// An expression where all imports have been resolved
-///
-/// Invariant: there must be no `Import` nodes or `ImportAlt` operations left.
-#[derive(Debug, Clone)]
-pub struct Resolved(ResolvedExpr);
-
-/// A typed expression
-#[derive(Debug, Clone)]
-pub struct Typed(Value);
-
-/// A normalized expression.
-///
-/// Invariant: the contained Typed expression must be in normal form,
-#[derive(Debug, Clone)]
-pub struct Normalized(Typed);
-
-impl Parsed {
- pub fn parse_file(f: &Path) -> Result<Parsed, Error> {
- parse::parse_file(f)
- }
- pub fn parse_str(s: &str) -> Result<Parsed, Error> {
- parse::parse_str(s)
- }
- pub fn parse_binary_file(f: &Path) -> Result<Parsed, Error> {
- parse::parse_binary_file(f)
- }
- pub fn parse_binary(data: &[u8]) -> Result<Parsed, Error> {
- parse::parse_binary(data)
- }
-
- pub fn resolve(self) -> Result<Resolved, ImportError> {
- resolve::resolve(self)
- }
- pub fn skip_resolve(self) -> Result<Resolved, ImportError> {
- resolve::skip_resolve_expr(self)
- }
-
- pub fn encode(&self) -> Result<Vec<u8>, EncodeError> {
- binary::encode(&self.0)
- }
-
- /// Converts a value back to the corresponding AST expression.
- pub fn to_expr(&self) -> ParsedExpr {
- self.0.clone()
- }
-}
-
-impl Resolved {
- pub fn typecheck(self) -> Result<Typed, TypeError> {
- Ok(typecheck::typecheck(self.0)?.into_typed())
- }
- pub fn typecheck_with(self, ty: &Typed) -> Result<Typed, TypeError> {
- Ok(typecheck::typecheck_with(self.0, ty.normalize_to_expr())?
- .into_typed())
- }
- /// Converts a value back to the corresponding AST expression.
- pub fn to_expr(&self) -> ResolvedExpr {
- self.0.clone()
- }
-}
-
-impl Typed {
- /// Reduce an expression to its normal form, performing beta reduction
- pub fn normalize(mut self) -> Normalized {
- self.normalize_mut();
- Normalized(self)
- }
-
- pub(crate) fn from_const(c: Const) -> Self {
- Typed(Value::from_const(c))
- }
- pub(crate) fn from_kind_and_type(v: ValueKind, t: Typed) -> Self {
- Typed(Value::from_kind_and_type(v, t.into_value()))
- }
- pub(crate) fn from_value(th: Value) -> Self {
- Typed(th)
- }
- pub(crate) fn const_type() -> Self {
- Typed::from_const(Const::Type)
- }
-
- /// Converts a value back to the corresponding AST expression.
- pub fn to_expr(&self) -> ResolvedExpr {
- self.0.to_expr(ToExprOptions {
- alpha: false,
- normalize: false,
- })
- }
- /// Converts a value back to the corresponding AST expression, beta-normalizing in the process.
- pub fn normalize_to_expr(&self) -> NormalizedExpr {
- self.0.to_expr(ToExprOptions {
- alpha: false,
- normalize: true,
- })
- }
- /// Converts a value back to the corresponding AST expression, (alpha,beta)-normalizing in the
- /// process.
- pub(crate) fn normalize_to_expr_alpha(&self) -> NormalizedExpr {
- self.0.to_expr(ToExprOptions {
- alpha: true,
- normalize: true,
- })
- }
- pub(crate) fn to_value(&self) -> Value {
- self.0.clone()
- }
- pub(crate) fn into_value(self) -> Value {
- self.0
- }
-
- pub(crate) fn normalize_mut(&mut self) {
- self.0.normalize_mut()
- }
-
- pub(crate) fn get_type(&self) -> Result<Typed, TypeError> {
- Ok(self.0.get_type()?.into_typed())
- }
-
- pub fn make_builtin_type(b: Builtin) -> Self {
- Typed::from_value(Value::from_builtin(b))
- }
- pub fn make_optional_type(t: Typed) -> Self {
- Typed::from_value(
- Value::from_builtin(Builtin::Optional).app(t.to_value()),
- )
- }
- pub fn make_list_type(t: Typed) -> Self {
- Typed::from_value(Value::from_builtin(Builtin::List).app(t.to_value()))
- }
- pub fn make_record_type(
- kts: impl Iterator<Item = (String, Typed)>,
- ) -> Self {
- Typed::from_kind_and_type(
- ValueKind::RecordType(
- kts.map(|(k, t)| (k.into(), t.into_value())).collect(),
- ),
- Typed::const_type(),
- )
- }
- pub fn make_union_type(
- kts: impl Iterator<Item = (String, Option<Typed>)>,
- ) -> Self {
- Typed::from_kind_and_type(
- ValueKind::UnionType(
- kts.map(|(k, t)| (k.into(), t.map(|t| t.into_value())))
- .collect(),
- ),
- Typed::const_type(),
- )
- }
-}
-
-impl Normalized {
- pub fn encode(&self) -> Result<Vec<u8>, EncodeError> {
- binary::encode(&self.to_expr())
- }
-
- pub(crate) fn to_expr(&self) -> NormalizedExpr {
- self.0.normalize_to_expr()
- }
- pub(crate) fn to_expr_alpha(&self) -> NormalizedExpr {
- self.0.normalize_to_expr_alpha()
- }
- pub(crate) fn into_typed(self) -> Typed {
- self.0
- }
-}
-
-impl Shift for Typed {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(Typed(self.0.shift(delta, var)?))
- }
-}
-
-impl Shift for Normalized {
- fn shift(&self, delta: isize, var: &AlphaVar) -> Option<Self> {
- Some(Normalized(self.0.shift(delta, var)?))
- }
-}
-
-impl Subst<Value> for Typed {
- fn subst_shift(&self, var: &AlphaVar, val: &Value) -> Self {
- Typed(self.0.subst_shift(var, val))
- }
-}
-
-macro_rules! derive_traits_for_wrapper_struct {
- ($ty:ident) => {
- impl std::cmp::PartialEq for $ty {
- fn eq(&self, other: &Self) -> bool {
- self.0 == other.0
- }
- }
-
- impl std::cmp::Eq for $ty {}
-
- impl std::fmt::Display for $ty {
- fn fmt(
- &self,
- f: &mut std::fmt::Formatter,
- ) -> Result<(), std::fmt::Error> {
- self.0.fmt(f)
- }
- }
- };
-}
-
-derive_traits_for_wrapper_struct!(Parsed);
-derive_traits_for_wrapper_struct!(Resolved);
-derive_traits_for_wrapper_struct!(Normalized);
-
-impl std::hash::Hash for Normalized {
- fn hash<H>(&self, state: &mut H)
- where
- H: std::hash::Hasher,
- {
- if let Ok(vec) = self.encode() {
- vec.hash(state)
- }
- }
-}
-
-impl Eq for Typed {}
-impl PartialEq for Typed {
- fn eq(&self, other: &Self) -> bool {
- self.0 == other.0
- }
-}
-
-impl Display for Typed {
- fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
- self.to_expr().fmt(f)
- }
-}
diff --git a/dhall/src/semantics/phase/normalize.rs b/dhall/src/semantics/phase/normalize.rs
deleted file mode 100644
index bf0c626..0000000
--- a/dhall/src/semantics/phase/normalize.rs
+++ /dev/null
@@ -1,791 +0,0 @@
-use std::collections::HashMap;
-use std::convert::TryInto;
-
-use crate::semantics::core::value::Value;
-use crate::semantics::core::value::ValueKind;
-use crate::semantics::core::var::{AlphaLabel, AlphaVar, Shift, Subst};
-use crate::semantics::phase::Normalized;
-use crate::syntax;
-use crate::syntax::Const::Type;
-use crate::syntax::{
- BinOp, Builtin, ExprKind, InterpolatedText, InterpolatedTextContents,
- Label, NaiveDouble,
-};
-
-// Ad-hoc macro to help construct closures
-macro_rules! make_closure {
- (#$var:ident) => { $var.clone() };
- (var($var:ident, $n:expr, $($ty:tt)*)) => {{
- let var = AlphaVar::from_var_and_alpha(
- Label::from(stringify!($var)).into(),
- $n
- );
- ValueKind::Var(var)
- .into_value_with_type(make_closure!($($ty)*))
- }};
- // Warning: assumes that $ty, as a dhall value, has type `Type`
- (λ($var:tt : $($ty:tt)*) -> $($body:tt)*) => {{
- let var: AlphaLabel = Label::from(stringify!($var)).into();
- let ty = make_closure!($($ty)*);
- let body = make_closure!($($body)*);
- let body_ty = body.get_type_not_sort();
- let lam_ty = ValueKind::Pi(var.clone(), ty.clone(), body_ty)
- .into_value_with_type(Value::from_const(Type));
- ValueKind::Lam(var, ty, body).into_value_with_type(lam_ty)
- }};
- (Natural) => {
- Value::from_builtin(Builtin::Natural)
- };
- (List $($rest:tt)*) => {
- Value::from_builtin(Builtin::List)
- .app(make_closure!($($rest)*))
- };
- (Some($($rest:tt)*)) => {{
- let v = make_closure!($($rest)*);
- let v_type = v.get_type_not_sort();
- let opt_v_type = Value::from_builtin(Builtin::Optional).app(v_type);
- ValueKind::NEOptionalLit(v).into_value_with_type(opt_v_type)
- }};
- (1 + $($rest:tt)*) => {
- ValueKind::PartialExpr(ExprKind::BinOp(
- syntax::BinOp::NaturalPlus,
- make_closure!($($rest)*),
- Value::from_kind_and_type(
- ValueKind::NaturalLit(1),
- make_closure!(Natural)
- ),
- )).into_value_with_type(
- make_closure!(Natural)
- )
- };
- ([ $($head:tt)* ] # $($tail:tt)*) => {{
- let head = make_closure!($($head)*);
- let tail = make_closure!($($tail)*);
- let list_type = tail.get_type_not_sort();
- ValueKind::PartialExpr(ExprKind::BinOp(
- syntax::BinOp::ListAppend,
- ValueKind::NEListLit(vec![head])
- .into_value_with_type(list_type.clone()),
- tail,
- )).into_value_with_type(list_type)
- }};
-}
-
-#[allow(clippy::cognitive_complexity)]
-pub(crate) fn apply_builtin(
- b: Builtin,
- args: Vec<Value>,
- ty: &Value,
-) -> ValueKind {
- use syntax::Builtin::*;
- use ValueKind::*;
-
- // Small helper enum
- enum Ret<'a> {
- ValueKind(ValueKind),
- Value(Value),
- // For applications that can return a function, it's important to keep the remaining
- // arguments to apply them to the resulting function.
- ValueWithRemainingArgs(&'a [Value], Value),
- DoneAsIs,
- }
-
- let ret = match (b, args.as_slice()) {
- (OptionalNone, [t]) => Ret::ValueKind(EmptyOptionalLit(t.clone())),
- (NaturalIsZero, [n]) => match &*n.as_whnf() {
- NaturalLit(n) => Ret::ValueKind(BoolLit(*n == 0)),
- _ => Ret::DoneAsIs,
- },
- (NaturalEven, [n]) => match &*n.as_whnf() {
- NaturalLit(n) => Ret::ValueKind(BoolLit(*n % 2 == 0)),
- _ => Ret::DoneAsIs,
- },
- (NaturalOdd, [n]) => match &*n.as_whnf() {
- NaturalLit(n) => Ret::ValueKind(BoolLit(*n % 2 != 0)),
- _ => Ret::DoneAsIs,
- },
- (NaturalToInteger, [n]) => match &*n.as_whnf() {
- NaturalLit(n) => Ret::ValueKind(IntegerLit(*n as isize)),
- _ => Ret::DoneAsIs,
- },
- (NaturalShow, [n]) => {
- match &*n.as_whnf() {
- NaturalLit(n) => Ret::ValueKind(TextLit(vec![
- InterpolatedTextContents::Text(n.to_string()),
- ])),
- _ => Ret::DoneAsIs,
- }
- }
- (NaturalSubtract, [a, b]) => match (&*a.as_whnf(), &*b.as_whnf()) {
- (NaturalLit(a), NaturalLit(b)) => {
- Ret::ValueKind(NaturalLit(if b > a { b - a } else { 0 }))
- }
- (NaturalLit(0), _) => Ret::Value(b.clone()),
- (_, NaturalLit(0)) => Ret::ValueKind(NaturalLit(0)),
- _ if a == b => Ret::ValueKind(NaturalLit(0)),
- _ => Ret::DoneAsIs,
- },
- (IntegerShow, [n]) => match &*n.as_whnf() {
- IntegerLit(n) => {
- let s = if *n < 0 {
- n.to_string()
- } else {
- format!("+{}", n)
- };
- Ret::ValueKind(TextLit(vec![InterpolatedTextContents::Text(s)]))
- }
- _ => Ret::DoneAsIs,
- },
- (IntegerToDouble, [n]) => match &*n.as_whnf() {
- IntegerLit(n) => {
- Ret::ValueKind(DoubleLit(NaiveDouble::from(*n as f64)))
- }
- _ => Ret::DoneAsIs,
- },
- (IntegerNegate, [n]) => match &*n.as_whnf() {
- IntegerLit(n) => Ret::ValueKind(IntegerLit(-n)),
- _ => Ret::DoneAsIs,
- },
- (IntegerClamp, [n]) => match &*n.as_whnf() {
- IntegerLit(n) => {
- Ret::ValueKind(NaturalLit((*n).try_into().unwrap_or(0)))
- }
- _ => Ret::DoneAsIs,
- },
- (DoubleShow, [n]) => {
- match &*n.as_whnf() {
- DoubleLit(n) => Ret::ValueKind(TextLit(vec![
- InterpolatedTextContents::Text(n.to_string()),
- ])),
- _ => Ret::DoneAsIs,
- }
- }
- (TextShow, [v]) => match &*v.as_whnf() {
- TextLit(elts) => {
- match elts.as_slice() {
- // Empty string literal.
- [] => {
- // Printing InterpolatedText takes care of all the escaping
- let txt: InterpolatedText<Normalized> =
- std::iter::empty().collect();
- let s = txt.to_string();
- Ret::ValueKind(TextLit(vec![
- InterpolatedTextContents::Text(s),
- ]))
- }
- // If there are no interpolations (invariants ensure that when there are no
- // interpolations, there is a single Text item) in the literal.
- [InterpolatedTextContents::Text(s)] => {
- // Printing InterpolatedText takes care of all the escaping
- let txt: InterpolatedText<Normalized> =
- std::iter::once(InterpolatedTextContents::Text(
- s.clone(),
- ))
- .collect();
- let s = txt.to_string();
- Ret::ValueKind(TextLit(vec![
- InterpolatedTextContents::Text(s),
- ]))
- }
- _ => Ret::DoneAsIs,
- }
- }
- _ => Ret::DoneAsIs,
- },
- (ListLength, [_, l]) => match &*l.as_whnf() {
- EmptyListLit(_) => Ret::ValueKind(NaturalLit(0)),
- NEListLit(xs) => Ret::ValueKind(NaturalLit(xs.len())),
- _ => Ret::DoneAsIs,
- },
- (ListHead, [_, l]) => match &*l.as_whnf() {
- EmptyListLit(n) => Ret::ValueKind(EmptyOptionalLit(n.clone())),
- NEListLit(xs) => {
- Ret::ValueKind(NEOptionalLit(xs.iter().next().unwrap().clone()))
- }
- _ => Ret::DoneAsIs,
- },
- (ListLast, [_, l]) => match &*l.as_whnf() {
- EmptyListLit(n) => Ret::ValueKind(EmptyOptionalLit(n.clone())),
- NEListLit(xs) => Ret::ValueKind(NEOptionalLit(
- xs.iter().rev().next().unwrap().clone(),
- )),
- _ => Ret::DoneAsIs,
- },
- (ListReverse, [_, l]) => match &*l.as_whnf() {
- EmptyListLit(n) => Ret::ValueKind(EmptyListLit(n.clone())),
- NEListLit(xs) => {
- Ret::ValueKind(NEListLit(xs.iter().rev().cloned().collect()))
- }
- _ => Ret::DoneAsIs,
- },
- (ListIndexed, [_, l]) => {
- let l_whnf = l.as_whnf();
- match &*l_whnf {
- EmptyListLit(_) | NEListLit(_) => {
- // Extract the type of the list elements
- let t = match &*l_whnf {
- EmptyListLit(t) => t.clone(),
- NEListLit(xs) => xs[0].get_type_not_sort(),
- _ => unreachable!(),
- };
-
- // Construct the returned record type: { index: Natural, value: t }
- let mut kts = HashMap::new();
- kts.insert("index".into(), Value::from_builtin(Natural));
- kts.insert("value".into(), t.clone());
- let t = Value::from_kind_and_type(
- RecordType(kts),
- Value::from_const(Type),
- );
-
- // Construct the new list, with added indices
- let list = match &*l_whnf {
- EmptyListLit(_) => EmptyListLit(t),
- NEListLit(xs) => NEListLit(
- xs.iter()
- .enumerate()
- .map(|(i, e)| {
- let mut kvs = HashMap::new();
- kvs.insert(
- "index".into(),
- Value::from_kind_and_type(
- NaturalLit(i),
- Value::from_builtin(
- Builtin::Natural,
- ),
- ),
- );
- kvs.insert("value".into(), e.clone());
- Value::from_kind_and_type(
- RecordLit(kvs),
- t.clone(),
- )
- })
- .collect(),
- ),
- _ => unreachable!(),
- };
- Ret::ValueKind(list)
- }
- _ => Ret::DoneAsIs,
- }
- }
- (ListBuild, [t, f]) => {
- let list_t = Value::from_builtin(List).app(t.clone());
- Ret::Value(
- f.app(list_t.clone())
- .app({
- // Move `t` under new variables
- let t1 = t.under_binder(Label::from("a"));
- let t2 = t1.under_binder(Label::from("as"));
- make_closure!(
- λ(a : #t) ->
- λ(as : List #t1) ->
- [ var(a, 1, #t2) ] # var(as, 0, List #t2)
- )
- })
- .app(EmptyListLit(t.clone()).into_value_with_type(list_t)),
- )
- }
- (ListFold, [_, l, _, cons, nil, r @ ..]) => match &*l.as_whnf() {
- EmptyListLit(_) => Ret::ValueWithRemainingArgs(r, nil.clone()),
- NEListLit(xs) => {
- let mut v = nil.clone();
- for x in xs.iter().cloned().rev() {
- v = cons.app(x).app(v);
- }
- Ret::ValueWithRemainingArgs(r, v)
- }
- _ => Ret::DoneAsIs,
- },
- (OptionalBuild, [t, f]) => {
- let optional_t = Value::from_builtin(Optional).app(t.clone());
- Ret::Value(
- f.app(optional_t.clone())
- .app({
- let t1 = t.under_binder(Label::from("a"));
- make_closure!(λ(a: #t) -> Some(var(a, 0, #t1)))
- })
- .app(
- EmptyOptionalLit(t.clone())
- .into_value_with_type(optional_t),
- ),
- )
- }
- (OptionalFold, [_, v, _, just, nothing, r @ ..]) => match &*v.as_whnf()
- {
- EmptyOptionalLit(_) => {
- Ret::ValueWithRemainingArgs(r, nothing.clone())
- }
- NEOptionalLit(x) => {
- Ret::ValueWithRemainingArgs(r, just.app(x.clone()))
- }
- _ => Ret::DoneAsIs,
- },
- (NaturalBuild, [f]) => Ret::Value(
- f.app(Value::from_builtin(Natural))
- .app(make_closure!(
- λ(x : Natural) -> 1 + var(x, 0, Natural)
- ))
- .app(
- NaturalLit(0)
- .into_value_with_type(Value::from_builtin(Natural)),
- ),
- ),
-
- (NaturalFold, [n, t, succ, zero, r @ ..]) => match &*n.as_whnf() {
- NaturalLit(0) => Ret::ValueWithRemainingArgs(r, zero.clone()),
- NaturalLit(n) => {
- let fold = Value::from_builtin(NaturalFold)
- .app(
- NaturalLit(n - 1)
- .into_value_with_type(Value::from_builtin(Natural)),
- )
- .app(t.clone())
- .app(succ.clone())
- .app(zero.clone());
- Ret::ValueWithRemainingArgs(r, succ.app(fold))
- }
- _ => Ret::DoneAsIs,
- },
- _ => Ret::DoneAsIs,
- };
- match ret {
- Ret::ValueKind(v) => v,
- Ret::Value(v) => v.to_whnf_check_type(ty),
- Ret::ValueWithRemainingArgs(unconsumed_args, mut v) => {
- let n_consumed_args = args.len() - unconsumed_args.len();
- for x in args.into_iter().skip(n_consumed_args) {
- v = v.app(x);
- }
- v.to_whnf_check_type(ty)
- }
- Ret::DoneAsIs => AppliedBuiltin(b, args),
- }
-}
-
-pub(crate) fn apply_any(f: Value, a: Value, ty: &Value) -> ValueKind {
- let f_borrow = f.as_whnf();
- match &*f_borrow {
- ValueKind::Lam(x, _, e) => {
- e.subst_shift(&x.into(), &a).to_whnf_check_type(ty)
- }
- ValueKind::AppliedBuiltin(b, args) => {
- use std::iter::once;
- let args = args.iter().cloned().chain(once(a.clone())).collect();
- apply_builtin(*b, args, ty)
- }
- ValueKind::UnionConstructor(l, kts) => {
- ValueKind::UnionLit(l.clone(), a, kts.clone())
- }
- _ => {
- drop(f_borrow);
- ValueKind::PartialExpr(ExprKind::App(f, a))
- }
- }
-}
-
-pub(crate) fn squash_textlit(
- elts: impl Iterator<Item = InterpolatedTextContents<Value>>,
-) -> Vec<InterpolatedTextContents<Value>> {
- use std::mem::replace;
- use InterpolatedTextContents::{Expr, Text};
-
- fn inner(
- elts: impl Iterator<Item = InterpolatedTextContents<Value>>,
- crnt_str: &mut String,
- ret: &mut Vec<InterpolatedTextContents<Value>>,
- ) {
- for contents in elts {
- match contents {
- Text(s) => crnt_str.push_str(&s),
- Expr(e) => {
- let e_borrow = e.as_whnf();
- match &*e_borrow {
- ValueKind::TextLit(elts2) => {
- inner(elts2.iter().cloned(), crnt_str, ret)
- }
- _ => {
- drop(e_borrow);
- if !crnt_str.is_empty() {
- ret.push(Text(replace(crnt_str, String::new())))
- }
- ret.push(Expr(e.clone()))
- }
- }
- }
- }
- }
- }
-
- let mut crnt_str = String::new();
- let mut ret = Vec::new();
- inner(elts, &mut crnt_str, &mut ret);
- if !crnt_str.is_empty() {
- ret.push(Text(replace(&mut crnt_str, String::new())))
- }
- ret
-}
-
-pub(crate) fn merge_maps<K, V, F, Err>(
- map1: &HashMap<K, V>,
- map2: &HashMap<K, V>,
- mut f: F,
-) -> Result<HashMap<K, V>, Err>
-where
- F: FnMut(&K, &V, &V) -> Result<V, Err>,
- K: std::hash::Hash + Eq + Clone,
- V: Clone,
-{
- let mut kvs = HashMap::new();
- for (x, v2) in map2 {
- let newv = if let Some(v1) = map1.get(x) {
- f(x, v1, v2)?
- } else {
- v2.clone()
- };
- kvs.insert(x.clone(), newv);
- }
- for (x, v1) in map1 {
- // Insert only if key not already present
- kvs.entry(x.clone()).or_insert_with(|| v1.clone());
- }
- Ok(kvs)
-}
-
-// Small helper enum to avoid repetition
-enum Ret<'a> {
- ValueKind(ValueKind),
- Value(Value),
- ValueRef(&'a Value),
- Expr(ExprKind<Value, Normalized>),
-}
-
-fn apply_binop<'a>(
- o: BinOp,
- x: &'a Value,
- y: &'a Value,
- ty: &Value,
-) -> Option<Ret<'a>> {
- use BinOp::{
- BoolAnd, BoolEQ, BoolNE, BoolOr, Equivalence, ListAppend, NaturalPlus,
- NaturalTimes, RecursiveRecordMerge, RecursiveRecordTypeMerge,
- RightBiasedRecordMerge, TextAppend,
- };
- use ValueKind::{
- BoolLit, EmptyListLit, NEListLit, NaturalLit, RecordLit, RecordType,
- TextLit,
- };
- let x_borrow = x.as_whnf();
- let y_borrow = y.as_whnf();
- Some(match (o, &*x_borrow, &*y_borrow) {
- (BoolAnd, BoolLit(true), _) => Ret::ValueRef(y),
- (BoolAnd, _, BoolLit(true)) => Ret::ValueRef(x),
- (BoolAnd, BoolLit(false), _) => Ret::ValueKind(BoolLit(false)),
- (BoolAnd, _, BoolLit(false)) => Ret::ValueKind(BoolLit(false)),
- (BoolAnd, _, _) if x == y => Ret::ValueRef(x),
- (BoolOr, BoolLit(true), _) => Ret::ValueKind(BoolLit(true)),
- (BoolOr, _, BoolLit(true)) => Ret::ValueKind(BoolLit(true)),
- (BoolOr, BoolLit(false), _) => Ret::ValueRef(y),
- (BoolOr, _, BoolLit(false)) => Ret::ValueRef(x),
- (BoolOr, _, _) if x == y => Ret::ValueRef(x),
- (BoolEQ, BoolLit(true), _) => Ret::ValueRef(y),
- (BoolEQ, _, BoolLit(true)) => Ret::ValueRef(x),
- (BoolEQ, BoolLit(x), BoolLit(y)) => Ret::ValueKind(BoolLit(x == y)),
- (BoolEQ, _, _) if x == y => Ret::ValueKind(BoolLit(true)),
- (BoolNE, BoolLit(false), _) => Ret::ValueRef(y),
- (BoolNE, _, BoolLit(false)) => Ret::ValueRef(x),
- (BoolNE, BoolLit(x), BoolLit(y)) => Ret::ValueKind(BoolLit(x != y)),
- (BoolNE, _, _) if x == y => Ret::ValueKind(BoolLit(false)),
-
- (NaturalPlus, NaturalLit(0), _) => Ret::ValueRef(y),
- (NaturalPlus, _, NaturalLit(0)) => Ret::ValueRef(x),
- (NaturalPlus, NaturalLit(x), NaturalLit(y)) => {
- Ret::ValueKind(NaturalLit(x + y))
- }
- (NaturalTimes, NaturalLit(0), _) => Ret::ValueKind(NaturalLit(0)),
- (NaturalTimes, _, NaturalLit(0)) => Ret::ValueKind(NaturalLit(0)),
- (NaturalTimes, NaturalLit(1), _) => Ret::ValueRef(y),
- (NaturalTimes, _, NaturalLit(1)) => Ret::ValueRef(x),
- (NaturalTimes, NaturalLit(x), NaturalLit(y)) => {
- Ret::ValueKind(NaturalLit(x * y))
- }
-
- (ListAppend, EmptyListLit(_), _) => Ret::ValueRef(y),
- (ListAppend, _, EmptyListLit(_)) => Ret::ValueRef(x),
- (ListAppend, NEListLit(xs), NEListLit(ys)) => Ret::ValueKind(
- NEListLit(xs.iter().chain(ys.iter()).cloned().collect()),
- ),
-
- (TextAppend, TextLit(x), _) if x.is_empty() => Ret::ValueRef(y),
- (TextAppend, _, TextLit(y)) if y.is_empty() => Ret::ValueRef(x),
- (TextAppend, TextLit(x), TextLit(y)) => Ret::ValueKind(TextLit(
- squash_textlit(x.iter().chain(y.iter()).cloned()),
- )),
- (TextAppend, TextLit(x), _) => {
- use std::iter::once;
- let y = InterpolatedTextContents::Expr(y.clone());
- Ret::ValueKind(TextLit(squash_textlit(
- x.iter().cloned().chain(once(y)),
- )))
- }
- (TextAppend, _, TextLit(y)) => {
- use std::iter::once;
- let x = InterpolatedTextContents::Expr(x.clone());
- Ret::ValueKind(TextLit(squash_textlit(
- once(x).chain(y.iter().cloned()),
- )))
- }
-
- (RightBiasedRecordMerge, _, RecordLit(kvs)) if kvs.is_empty() => {
- Ret::ValueRef(x)
- }
- (RightBiasedRecordMerge, RecordLit(kvs), _) if kvs.is_empty() => {
- Ret::ValueRef(y)
- }
- (RightBiasedRecordMerge, RecordLit(kvs1), RecordLit(kvs2)) => {
- let mut kvs = kvs2.clone();
- for (x, v) in kvs1 {
- // Insert only if key not already present
- kvs.entry(x.clone()).or_insert_with(|| v.clone());
- }
- Ret::ValueKind(RecordLit(kvs))
- }
-
- (RecursiveRecordMerge, _, RecordLit(kvs)) if kvs.is_empty() => {
- Ret::ValueRef(x)
- }
- (RecursiveRecordMerge, RecordLit(kvs), _) if kvs.is_empty() => {
- Ret::ValueRef(y)
- }
- (RecursiveRecordMerge, RecordLit(kvs1), RecordLit(kvs2)) => {
- let ty_borrow = ty.as_whnf();
- let kts = match &*ty_borrow {
- RecordType(kts) => kts,
- _ => unreachable!("Internal type error"),
- };
- let kvs = merge_maps::<_, _, _, !>(kvs1, kvs2, |k, v1, v2| {
- Ok(Value::from_kind_and_type(
- ValueKind::PartialExpr(ExprKind::BinOp(
- RecursiveRecordMerge,
- v1.clone(),
- v2.clone(),
- )),
- kts.get(k).expect("Internal type error").clone(),
- ))
- })?;
- Ret::ValueKind(RecordLit(kvs))
- }
-
- (RecursiveRecordTypeMerge, _, _) | (Equivalence, _, _) => {
- unreachable!("This case should have been handled in typecheck")
- }
-
- _ => return None,
- })
-}
-
-pub(crate) fn normalize_one_layer(
- expr: ExprKind<Value, Normalized>,
- ty: &Value,
-) -> ValueKind {
- use ValueKind::{
- AppliedBuiltin, BoolLit, DoubleLit, EmptyListLit, EmptyOptionalLit,
- IntegerLit, NEListLit, NEOptionalLit, NaturalLit, RecordLit, TextLit,
- UnionConstructor, UnionLit, UnionType,
- };
-
- let ret = match expr {
- ExprKind::Import(_) => unreachable!(
- "There should remain no imports in a resolved expression"
- ),
- // Those cases have already been completely handled in the typechecking phase (using
- // `RetWhole`), so they won't appear here.
- ExprKind::Lam(_, _, _)
- | ExprKind::Pi(_, _, _)
- | ExprKind::Let(_, _, _, _)
- | ExprKind::Embed(_)
- | ExprKind::Const(_)
- | ExprKind::Builtin(_)
- | ExprKind::Var(_)
- | ExprKind::Annot(_, _)
- | ExprKind::RecordType(_)
- | ExprKind::UnionType(_) => {
- unreachable!("This case should have been handled in typecheck")
- }
- ExprKind::Assert(_) => Ret::Expr(expr),
- ExprKind::App(v, a) => Ret::Value(v.app(a)),
- ExprKind::BoolLit(b) => Ret::ValueKind(BoolLit(b)),
- ExprKind::NaturalLit(n) => Ret::ValueKind(NaturalLit(n)),
- ExprKind::IntegerLit(n) => Ret::ValueKind(IntegerLit(n)),
- ExprKind::DoubleLit(n) => Ret::ValueKind(DoubleLit(n)),
- ExprKind::SomeLit(e) => Ret::ValueKind(NEOptionalLit(e)),
- ExprKind::EmptyListLit(ref t) => {
- // Check if the type is of the form `List x`
- let t_borrow = t.as_whnf();
- match &*t_borrow {
- AppliedBuiltin(Builtin::List, args) if args.len() == 1 => {
- Ret::ValueKind(EmptyListLit(args[0].clone()))
- }
- _ => {
- drop(t_borrow);
- Ret::Expr(expr)
- }
- }
- }
- ExprKind::NEListLit(elts) => {
- Ret::ValueKind(NEListLit(elts.into_iter().collect()))
- }
- ExprKind::RecordLit(kvs) => {
- Ret::ValueKind(RecordLit(kvs.into_iter().collect()))
- }
- ExprKind::TextLit(elts) => {
- use InterpolatedTextContents::Expr;
- let elts: Vec<_> = squash_textlit(elts.into_iter());
- // Simplify bare interpolation
- if let [Expr(th)] = elts.as_slice() {
- Ret::Value(th.clone())
- } else {
- Ret::ValueKind(TextLit(elts))
- }
- }
- ExprKind::BoolIf(ref b, ref e1, ref e2) => {
- let b_borrow = b.as_whnf();
- match &*b_borrow {
- BoolLit(true) => Ret::ValueRef(e1),
- BoolLit(false) => Ret::ValueRef(e2),
- _ => {
- let e1_borrow = e1.as_whnf();
- let e2_borrow = e2.as_whnf();
- match (&*e1_borrow, &*e2_borrow) {
- // Simplify `if b then True else False`
- (BoolLit(true), BoolLit(false)) => Ret::ValueRef(b),
- _ if e1 == e2 => Ret::ValueRef(e1),
- _ => {
- drop(b_borrow);
- drop(e1_borrow);
- drop(e2_borrow);
- Ret::Expr(expr)
- }
- }
- }
- }
- }
- ExprKind::BinOp(o, ref x, ref y) => match apply_binop(o, x, y, ty) {
- Some(ret) => ret,
- None => Ret::Expr(expr),
- },
-
- ExprKind::Projection(_, ref ls) if ls.is_empty() => {
- Ret::ValueKind(RecordLit(HashMap::new()))
- }
- ExprKind::Projection(ref v, ref ls) => {
- let v_borrow = v.as_whnf();
- match &*v_borrow {
- RecordLit(kvs) => Ret::ValueKind(RecordLit(
- ls.iter()
- .filter_map(|l| {
- kvs.get(l).map(|x| (l.clone(), x.clone()))
- })
- .collect(),
- )),
- _ => {
- drop(v_borrow);
- Ret::Expr(expr)
- }
- }
- }
- ExprKind::Field(ref v, ref l) => {
- let v_borrow = v.as_whnf();
- match &*v_borrow {
- RecordLit(kvs) => match kvs.get(l) {
- Some(r) => Ret::Value(r.clone()),
- None => {
- drop(v_borrow);
- Ret::Expr(expr)
- }
- },
- UnionType(kts) => {
- Ret::ValueKind(UnionConstructor(l.clone(), kts.clone()))
- }
- _ => {
- drop(v_borrow);
- Ret::Expr(expr)
- }
- }
- }
- ExprKind::ProjectionByExpr(_, _) => {
- unimplemented!("selection by expression")
- }
- ExprKind::Completion(_, _) => unimplemented!("record completion"),
-
- ExprKind::Merge(ref handlers, ref variant, _) => {
- let handlers_borrow = handlers.as_whnf();
- let variant_borrow = variant.as_whnf();
- match (&*handlers_borrow, &*variant_borrow) {
- (RecordLit(kvs), UnionConstructor(l, _)) => match kvs.get(l) {
- Some(h) => Ret::Value(h.clone()),
- None => {
- drop(handlers_borrow);
- drop(variant_borrow);
- Ret::Expr(expr)
- }
- },
- (RecordLit(kvs), UnionLit(l, v, _)) => match kvs.get(l) {
- Some(h) => Ret::Value(h.app(v.clone())),
- None => {
- drop(handlers_borrow);
- drop(variant_borrow);
- Ret::Expr(expr)
- }
- },
- (RecordLit(kvs), EmptyOptionalLit(_)) => {
- match kvs.get(&"None".into()) {
- Some(h) => Ret::Value(h.clone()),
- None => {
- drop(handlers_borrow);
- drop(variant_borrow);
- Ret::Expr(expr)
- }
- }
- }
- (RecordLit(kvs), NEOptionalLit(v)) => {
- match kvs.get(&"Some".into()) {
- Some(h) => Ret::Value(h.app(v.clone())),
- None => {
- drop(handlers_borrow);
- drop(variant_borrow);
- Ret::Expr(expr)
- }
- }
- }
- _ => {
- drop(handlers_borrow);
- drop(variant_borrow);
- Ret::Expr(expr)
- }
- }
- }
- ExprKind::ToMap(_, _) => unimplemented!("toMap"),
- };
-
- match ret {
- Ret::ValueKind(v) => v,
- Ret::Value(v) => v.to_whnf_check_type(ty),
- Ret::ValueRef(v) => v.to_whnf_check_type(ty),
- Ret::Expr(expr) => ValueKind::PartialExpr(expr),
- }
-}
-
-/// Normalize a ValueKind into WHNF
-pub(crate) fn normalize_whnf(v: ValueKind, ty: &Value) -> ValueKind {
- match v {
- ValueKind::AppliedBuiltin(b, args) => apply_builtin(b, args, ty),
- ValueKind::PartialExpr(e) => normalize_one_layer(e, ty),
- ValueKind::TextLit(elts) => {
- ValueKind::TextLit(squash_textlit(elts.into_iter()))
- }
- // All other cases are already in WHNF
- v => v,
- }
-}
diff --git a/dhall/src/semantics/phase/typecheck.rs b/dhall/src/semantics/phase/typecheck.rs
deleted file mode 100644
index 3960146..0000000
--- a/dhall/src/semantics/phase/typecheck.rs
+++ /dev/null
@@ -1,838 +0,0 @@
-use std::borrow::Cow;
-use std::cmp::max;
-use std::collections::HashMap;
-
-use crate::error::{TypeError, TypeMessage};
-use crate::semantics::core::context::TypecheckContext;
-use crate::semantics::core::value::Value;
-use crate::semantics::core::value::ValueKind;
-use crate::semantics::core::var::{Shift, Subst};
-use crate::semantics::phase::normalize::merge_maps;
-use crate::semantics::phase::Normalized;
-use crate::syntax;
-use crate::syntax::{
- Builtin, Const, Expr, ExprKind, InterpolatedTextContents, Label, Span,
- UnspannedExpr,
-};
-
-fn tck_pi_type(
- ctx: &TypecheckContext,
- x: Label,
- tx: Value,
- te: Value,
-) -> Result<Value, TypeError> {
- use TypeMessage::*;
- let ctx2 = ctx.insert_type(&x, tx.clone());
-
- let ka = match tx.get_type()?.as_const() {
- Some(k) => k,
- _ => return Err(TypeError::new(ctx, InvalidInputType(tx))),
- };
-
- let kb = match te.get_type()?.as_const() {
- Some(k) => k,
- _ => {
- return Err(TypeError::new(
- &ctx2,
- InvalidOutputType(te.get_type()?),
- ))
- }
- };
-
- let k = function_check(ka, kb);
-
- Ok(Value::from_kind_and_type(
- ValueKind::Pi(x.into(), tx, te),
- Value::from_const(k),
- ))
-}
-
-fn tck_record_type(
- ctx: &TypecheckContext,
- kts: impl IntoIterator<Item = Result<(Label, Value), TypeError>>,
-) -> Result<Value, TypeError> {
- use std::collections::hash_map::Entry;
- use TypeMessage::*;
- let mut new_kts = HashMap::new();
- // An empty record type has type Type
- let mut k = Const::Type;
- for e in kts {
- let (x, t) = e?;
- // Construct the union of the contained `Const`s
- match t.get_type()?.as_const() {
- Some(k2) => k = max(k, k2),
- None => return Err(TypeError::new(ctx, InvalidFieldType(x, t))),
- }
- // Check for duplicated entries
- let entry = new_kts.entry(x);
- match &entry {
- Entry::Occupied(_) => {
- return Err(TypeError::new(ctx, RecordTypeDuplicateField))
- }
- Entry::Vacant(_) => entry.or_insert_with(|| t),
- };
- }
-
- Ok(Value::from_kind_and_type(
- ValueKind::RecordType(new_kts),
- Value::from_const(k),
- ))
-}
-
-fn tck_union_type<Iter>(
- ctx: &TypecheckContext,
- kts: Iter,
-) -> Result<Value, TypeError>
-where
- Iter: IntoIterator<Item = Result<(Label, Option<Value>), TypeError>>,
-{
- use std::collections::hash_map::Entry;
- use TypeMessage::*;
- let mut new_kts = HashMap::new();
- // Check that all types are the same const
- let mut k = None;
- for e in kts {
- let (x, t) = e?;
- if let Some(t) = &t {
- match (k, t.get_type()?.as_const()) {
- (None, Some(k2)) => k = Some(k2),
- (Some(k1), Some(k2)) if k1 == k2 => {}
- _ => {
- return Err(TypeError::new(
- ctx,
- InvalidFieldType(x, t.clone()),
- ))
- }
- }
- }
- let entry = new_kts.entry(x);
- match &entry {
- Entry::Occupied(_) => {
- return Err(TypeError::new(ctx, UnionTypeDuplicateField))
- }
- Entry::Vacant(_) => entry.or_insert_with(|| t),
- };
- }
-
- // An empty union type has type Type;
- // an union type with only unary variants also has type Type
- let k = k.unwrap_or(Const::Type);
-
- Ok(Value::from_kind_and_type(
- ValueKind::UnionType(new_kts),
- Value::from_const(k),
- ))
-}
-
-fn function_check(a: Const, b: Const) -> Const {
- if b == Const::Type {
- Const::Type
- } else {
- max(a, b)
- }
-}
-
-pub(crate) fn const_to_value(c: Const) -> Value {
- let v = ValueKind::Const(c);
- match c {
- Const::Type => {
- Value::from_kind_and_type(v, const_to_value(Const::Kind))
- }
- Const::Kind => {
- Value::from_kind_and_type(v, const_to_value(Const::Sort))
- }
- Const::Sort => Value::const_sort(),
- }
-}
-
-pub fn rc<E>(x: UnspannedExpr<E>) -> Expr<E> {
- Expr::new(x, Span::Artificial)
-}
-
-// Ad-hoc macro to help construct the types of builtins
-macro_rules! make_type {
- (Type) => { ExprKind::Const(Const::Type) };
- (Bool) => { ExprKind::Builtin(Builtin::Bool) };
- (Natural) => { ExprKind::Builtin(Builtin::Natural) };
- (Integer) => { ExprKind::Builtin(Builtin::Integer) };
- (Double) => { ExprKind::Builtin(Builtin::Double) };
- (Text) => { ExprKind::Builtin(Builtin::Text) };
- ($var:ident) => {
- ExprKind::Var(syntax::V(stringify!($var).into(), 0))
- };
- (Optional $ty:ident) => {
- ExprKind::App(
- rc(ExprKind::Builtin(Builtin::Optional)),
- rc(make_type!($ty))
- )
- };
- (List $($rest:tt)*) => {
- ExprKind::App(
- rc(ExprKind::Builtin(Builtin::List)),
- rc(make_type!($($rest)*))
- )
- };
- ({ $($label:ident : $ty:ident),* }) => {{
- let mut kts = syntax::map::DupTreeMap::new();
- $(
- kts.insert(
- Label::from(stringify!($label)),
- rc(make_type!($ty)),
- );
- )*
- ExprKind::RecordType(kts)
- }};
- ($ty:ident -> $($rest:tt)*) => {
- ExprKind::Pi(
- "_".into(),
- rc(make_type!($ty)),
- rc(make_type!($($rest)*))
- )
- };
- (($($arg:tt)*) -> $($rest:tt)*) => {
- ExprKind::Pi(
- "_".into(),
- rc(make_type!($($arg)*)),
- rc(make_type!($($rest)*))
- )
- };
- (forall ($var:ident : $($ty:tt)*) -> $($rest:tt)*) => {
- ExprKind::Pi(
- stringify!($var).into(),
- rc(make_type!($($ty)*)),
- rc(make_type!($($rest)*))
- )
- };
-}
-
-fn type_of_builtin<E>(b: Builtin) -> Expr<E> {
- use syntax::Builtin::*;
- rc(match b {
- Bool | Natural | Integer | Double | Text => make_type!(Type),
- List | Optional => make_type!(
- Type -> Type
- ),
-
- NaturalFold => make_type!(
- Natural ->
- forall (natural: Type) ->
- forall (succ: natural -> natural) ->
- forall (zero: natural) ->
- natural
- ),
- NaturalBuild => make_type!(
- (forall (natural: Type) ->
- forall (succ: natural -> natural) ->
- forall (zero: natural) ->
- natural) ->
- Natural
- ),
- NaturalIsZero | NaturalEven | NaturalOdd => make_type!(
- Natural -> Bool
- ),
- NaturalToInteger => make_type!(Natural -> Integer),
- NaturalShow => make_type!(Natural -> Text),
- NaturalSubtract => make_type!(Natural -> Natural -> Natural),
-
- IntegerToDouble => make_type!(Integer -> Double),
- IntegerShow => make_type!(Integer -> Text),
- IntegerNegate => make_type!(Integer -> Integer),
- IntegerClamp => make_type!(Integer -> Natural),
-
- DoubleShow => make_type!(Double -> Text),
- TextShow => make_type!(Text -> Text),
-
- ListBuild => make_type!(
- forall (a: Type) ->
- (forall (list: Type) ->
- forall (cons: a -> list -> list) ->
- forall (nil: list) ->
- list) ->
- List a
- ),
- ListFold => make_type!(
- forall (a: Type) ->
- (List a) ->
- forall (list: Type) ->
- forall (cons: a -> list -> list) ->
- forall (nil: list) ->
- list
- ),
- ListLength => make_type!(forall (a: Type) -> (List a) -> Natural),
- ListHead | ListLast => {
- make_type!(forall (a: Type) -> (List a) -> Optional a)
- }
- ListIndexed => make_type!(
- forall (a: Type) ->
- (List a) ->
- List { index: Natural, value: a }
- ),
- ListReverse => make_type!(
- forall (a: Type) -> (List a) -> List a
- ),
-
- OptionalBuild => make_type!(
- forall (a: Type) ->
- (forall (optional: Type) ->
- forall (just: a -> optional) ->
- forall (nothing: optional) ->
- optional) ->
- Optional a
- ),
- OptionalFold => make_type!(
- forall (a: Type) ->
- (Optional a) ->
- forall (optional: Type) ->
- forall (just: a -> optional) ->
- forall (nothing: optional) ->
- optional
- ),
- OptionalNone => make_type!(
- forall (A: Type) -> Optional A
- ),
- })
-}
-
-pub(crate) fn builtin_to_value(b: Builtin) -> Value {
- let ctx = TypecheckContext::new();
- Value::from_kind_and_type(
- ValueKind::from_builtin(b),
- type_with(&ctx, type_of_builtin(b)).unwrap(),
- )
-}
-
-/// Type-check an expression and return the expression alongside its type if type-checking
-/// succeeded, or an error if type-checking failed.
-/// Some normalization is done while typechecking, so the returned expression might be partially
-/// normalized as well.
-fn type_with(
- ctx: &TypecheckContext,
- e: Expr<Normalized>,
-) -> Result<Value, TypeError> {
- use syntax::ExprKind::{Annot, Embed, Lam, Let, Pi, Var};
- let span = e.span();
-
- Ok(match e.as_ref() {
- Lam(var, annot, body) => {
- let annot = type_with(ctx, annot.clone())?;
- annot.normalize_nf();
- let ctx2 = ctx.insert_type(var, annot.clone());
- let body = type_with(&ctx2, body.clone())?;
- let body_type = body.get_type()?;
- Value::from_kind_and_type(
- ValueKind::Lam(var.clone().into(), annot.clone(), body),
- tck_pi_type(ctx, var.clone(), annot, body_type)?,
- )
- }
- Pi(x, ta, tb) => {
- let ta = type_with(ctx, ta.clone())?;
- let ctx2 = ctx.insert_type(x, ta.clone());
- let tb = type_with(&ctx2, tb.clone())?;
- return tck_pi_type(ctx, x.clone(), ta, tb);
- }
- Let(x, t, v, e) => {
- let v = if let Some(t) = t {
- t.rewrap(Annot(v.clone(), t.clone()))
- } else {
- v.clone()
- };
-
- let v = type_with(ctx, v)?;
- return type_with(&ctx.insert_value(x, v.clone())?, e.clone());
- }
- Embed(p) => p.clone().into_typed().into_value(),
- Var(var) => match ctx.lookup(&var) {
- Some(typed) => typed.clone(),
- None => {
- return Err(TypeError::new(
- ctx,
- TypeMessage::UnboundVariable(span),
- ))
- }
- },
- e => {
- // Typecheck recursively all subexpressions
- let expr = e.traverse_ref_with_special_handling_of_binders(
- |e| type_with(ctx, e.clone()),
- |_, _| unreachable!(),
- )?;
- type_last_layer(ctx, expr, span)?
- }
- })
-}
-
-/// When all sub-expressions have been typed, check the remaining toplevel
-/// layer.
-fn type_last_layer(
- ctx: &TypecheckContext,
- e: ExprKind<Value, Normalized>,
- span: Span,
-) -> Result<Value, TypeError> {
- use syntax::BinOp::*;
- use syntax::Builtin::*;
- use syntax::Const::Type;
- use syntax::ExprKind::*;
- use TypeMessage::*;
- let mkerr = |msg: TypeMessage| Err(TypeError::new(ctx, msg));
-
- /// Intermediary return type
- enum Ret {
- /// Returns the contained value as is
- RetWhole(Value),
- /// Returns the input expression `e` with the contained value as its type
- RetTypeOnly(Value),
- }
- use Ret::*;
-
- let ret = match &e {
- Import(_) => unreachable!(
- "There should remain no imports in a resolved expression"
- ),
- Lam(_, _, _) | Pi(_, _, _) | Let(_, _, _, _) | Embed(_) | Var(_) => {
- unreachable!()
- }
- App(f, a) => {
- let tf = f.get_type()?;
- let tf_borrow = tf.as_whnf();
- let (x, tx, tb) = match &*tf_borrow {
- ValueKind::Pi(x, tx, tb) => (x, tx, tb),
- _ => return mkerr(NotAFunction(f.clone())),
- };
- if &a.get_type()? != tx {
- return mkerr(TypeMismatch(f.clone(), tx.clone(), a.clone()));
- }
-
- let ret = tb.subst_shift(&x.into(), a);
- ret.normalize_nf();
- RetTypeOnly(ret)
- }
- Annot(x, t) => {
- if &x.get_type()? != t {
- return mkerr(AnnotMismatch(x.clone(), t.clone()));
- }
- RetWhole(x.clone())
- }
- Assert(t) => {
- match &*t.as_whnf() {
- ValueKind::Equivalence(x, y) if x == y => {}
- ValueKind::Equivalence(x, y) => {
- return mkerr(AssertMismatch(x.clone(), y.clone()))
- }
- _ => return mkerr(AssertMustTakeEquivalence),
- }
- RetTypeOnly(t.clone())
- }
- BoolIf(x, y, z) => {
- if *x.get_type()?.as_whnf() != ValueKind::from_builtin(Bool) {
- return mkerr(InvalidPredicate(x.clone()));
- }
-
- if y.get_type()?.get_type()?.as_const() != Some(Type) {
- return mkerr(IfBranchMustBeTerm(true, y.clone()));
- }
-
- if z.get_type()?.get_type()?.as_const() != Some(Type) {
- return mkerr(IfBranchMustBeTerm(false, z.clone()));
- }
-
- if y.get_type()? != z.get_type()? {
- return mkerr(IfBranchMismatch(y.clone(), z.clone()));
- }
-
- RetTypeOnly(y.get_type()?)
- }
- EmptyListLit(t) => {
- match &*t.as_whnf() {
- ValueKind::AppliedBuiltin(syntax::Builtin::List, args)
- if args.len() == 1 => {}
- _ => return mkerr(InvalidListType(t.clone())),
- }
- RetTypeOnly(t.clone())
- }
- NEListLit(xs) => {
- let mut iter = xs.iter().enumerate();
- let (_, x) = iter.next().unwrap();
- for (i, y) in iter {
- if x.get_type()? != y.get_type()? {
- return mkerr(InvalidListElement(
- i,
- x.get_type()?,
- y.clone(),
- ));
- }
- }
- let t = x.get_type()?;
- if t.get_type()?.as_const() != Some(Type) {
- return mkerr(InvalidListType(t));
- }
-
- RetTypeOnly(Value::from_builtin(syntax::Builtin::List).app(t))
- }
- SomeLit(x) => {
- let t = x.get_type()?;
- if t.get_type()?.as_const() != Some(Type) {
- return mkerr(InvalidOptionalType(t));
- }
-
- RetTypeOnly(Value::from_builtin(syntax::Builtin::Optional).app(t))
- }
- RecordType(kts) => RetWhole(tck_record_type(
- ctx,
- kts.iter().map(|(x, t)| Ok((x.clone(), t.clone()))),
- )?),
- UnionType(kts) => RetWhole(tck_union_type(
- ctx,
- kts.iter().map(|(x, t)| Ok((x.clone(), t.clone()))),
- )?),
- RecordLit(kvs) => RetTypeOnly(tck_record_type(
- ctx,
- kvs.iter().map(|(x, v)| Ok((x.clone(), v.get_type()?))),
- )?),
- Field(r, x) => {
- match &*r.get_type()?.as_whnf() {
- ValueKind::RecordType(kts) => match kts.get(&x) {
- Some(tth) => {
- RetTypeOnly(tth.clone())
- },
- None => return mkerr(MissingRecordField(x.clone(),
- r.clone())),
- },
- // TODO: branch here only when r.get_type() is a Const
- _ => {
- match &*r.as_whnf() {
- ValueKind::UnionType(kts) => match kts.get(&x) {
- // Constructor has type T -> < x: T, ... >
- Some(Some(t)) => {
- RetTypeOnly(
- tck_pi_type(
- ctx,
- x.clone(),
- t.clone(),
- r.under_binder(x),
- )?
- )
- },
- Some(None) => {
- RetTypeOnly(r.clone())
- },
- None => {
- return mkerr(MissingUnionField(
- x.clone(),
- r.clone(),
- ))
- },
- },
- _ => {
- return mkerr(NotARecord(
- x.clone(),
- r.clone()
- ))
- },
- }
- }
- // _ => mkerr(NotARecord(
- // x,
- // r?,
- // )),
- }
- }
- Const(c) => RetWhole(const_to_value(*c)),
- Builtin(b) => RetWhole(builtin_to_value(*b)),
- BoolLit(_) => RetTypeOnly(builtin_to_value(Bool)),
- NaturalLit(_) => RetTypeOnly(builtin_to_value(Natural)),
- IntegerLit(_) => RetTypeOnly(builtin_to_value(Integer)),
- DoubleLit(_) => RetTypeOnly(builtin_to_value(Double)),
- TextLit(interpolated) => {
- let text_type = builtin_to_value(Text);
- for contents in interpolated.iter() {
- use InterpolatedTextContents::Expr;
- if let Expr(x) = contents {
- if x.get_type()? != text_type {
- return mkerr(InvalidTextInterpolation(x.clone()));
- }
- }
- }
- RetTypeOnly(text_type)
- }
- BinOp(RightBiasedRecordMerge, l, r) => {
- let l_type = l.get_type()?;
- let r_type = r.get_type()?;
-
- // Extract the LHS record type
- let l_type_borrow = l_type.as_whnf();
- let kts_x = match &*l_type_borrow {
- ValueKind::RecordType(kts) => kts,
- _ => return mkerr(MustCombineRecord(l.clone())),
- };
-
- // Extract the RHS record type
- let r_type_borrow = r_type.as_whnf();
- let kts_y = match &*r_type_borrow {
- ValueKind::RecordType(kts) => kts,
- _ => return mkerr(MustCombineRecord(r.clone())),
- };
-
- // Union the two records, prefering
- // the values found in the RHS.
- let kts = merge_maps::<_, _, _, !>(kts_x, kts_y, |_, _, r_t| {
- Ok(r_t.clone())
- })?;
-
- // Construct the final record type from the union
- RetTypeOnly(tck_record_type(
- ctx,
- kts.into_iter().map(|(x, v)| Ok((x.clone(), v))),
- )?)
- }
- BinOp(RecursiveRecordMerge, l, r) => RetTypeOnly(type_last_layer(
- ctx,
- ExprKind::BinOp(
- RecursiveRecordTypeMerge,
- l.get_type()?,
- r.get_type()?,
- ),
- Span::Artificial,
- )?),
- BinOp(RecursiveRecordTypeMerge, l, r) => {
- // Extract the LHS record type
- let borrow_l = l.as_whnf();
- let kts_x = match &*borrow_l {
- ValueKind::RecordType(kts) => kts,
- _ => {
- return mkerr(RecordTypeMergeRequiresRecordType(l.clone()))
- }
- };
-
- // Extract the RHS record type
- let borrow_r = r.as_whnf();
- let kts_y = match &*borrow_r {
- ValueKind::RecordType(kts) => kts,
- _ => {
- return mkerr(RecordTypeMergeRequiresRecordType(r.clone()))
- }
- };
-
- // Ensure that the records combine without a type error
- let kts = merge_maps(
- kts_x,
- kts_y,
- // If the Label exists for both records, then we hit the recursive case.
- |_, l: &Value, r: &Value| {
- type_last_layer(
- ctx,
- ExprKind::BinOp(
- RecursiveRecordTypeMerge,
- l.clone(),
- r.clone(),
- ),
- Span::Artificial,
- )
- },
- )?;
-
- RetWhole(tck_record_type(ctx, kts.into_iter().map(Ok))?)
- }
- BinOp(o @ ListAppend, l, r) => {
- match &*l.get_type()?.as_whnf() {
- ValueKind::AppliedBuiltin(List, _) => {}
- _ => return mkerr(BinOpTypeMismatch(*o, l.clone())),
- }
-
- if l.get_type()? != r.get_type()? {
- return mkerr(BinOpTypeMismatch(*o, r.clone()));
- }
-
- RetTypeOnly(l.get_type()?)
- }
- BinOp(Equivalence, l, r) => {
- if l.get_type()?.get_type()?.as_const() != Some(Type) {
- return mkerr(EquivalenceArgumentMustBeTerm(true, l.clone()));
- }
- if r.get_type()?.get_type()?.as_const() != Some(Type) {
- return mkerr(EquivalenceArgumentMustBeTerm(false, r.clone()));
- }
-
- if l.get_type()? != r.get_type()? {
- return mkerr(EquivalenceTypeMismatch(r.clone(), l.clone()));
- }
-
- RetWhole(Value::from_kind_and_type(
- ValueKind::Equivalence(l.clone(), r.clone()),
- Value::from_const(Type),
- ))
- }
- BinOp(o, l, r) => {
- let t = builtin_to_value(match o {
- BoolAnd => Bool,
- BoolOr => Bool,
- BoolEQ => Bool,
- BoolNE => Bool,
- NaturalPlus => Natural,
- NaturalTimes => Natural,
- TextAppend => Text,
- ListAppend => unreachable!(),
- RightBiasedRecordMerge => unreachable!(),
- RecursiveRecordMerge => unreachable!(),
- RecursiveRecordTypeMerge => unreachable!(),
- ImportAlt => unreachable!("There should remain no import alternatives in a resolved expression"),
- Equivalence => unreachable!(),
- });
-
- if l.get_type()? != t {
- return mkerr(BinOpTypeMismatch(*o, l.clone()));
- }
-
- if r.get_type()? != t {
- return mkerr(BinOpTypeMismatch(*o, r.clone()));
- }
-
- RetTypeOnly(t)
- }
- Merge(record, union, type_annot) => {
- let record_type = record.get_type()?;
- let record_borrow = record_type.as_whnf();
- let handlers = match &*record_borrow {
- ValueKind::RecordType(kts) => kts,
- _ => return mkerr(Merge1ArgMustBeRecord(record.clone())),
- };
-
- let union_type = union.get_type()?;
- let union_borrow = union_type.as_whnf();
- let variants = match &*union_borrow {
- ValueKind::UnionType(kts) => Cow::Borrowed(kts),
- ValueKind::AppliedBuiltin(syntax::Builtin::Optional, args)
- if args.len() == 1 =>
- {
- let ty = &args[0];
- let mut kts = HashMap::new();
- kts.insert("None".into(), None);
- kts.insert("Some".into(), Some(ty.clone()));
- Cow::Owned(kts)
- }
- _ => {
- return mkerr(Merge2ArgMustBeUnionOrOptional(union.clone()))
- }
- };
-
- let mut inferred_type = None;
- for (x, handler_type) in handlers {
- let handler_return_type =
- match variants.get(x) {
- // Union alternative with type
- Some(Some(variant_type)) => {
- let handler_type_borrow = handler_type.as_whnf();
- let (x, tx, tb) = match &*handler_type_borrow {
- ValueKind::Pi(x, tx, tb) => (x, tx, tb),
- _ => {
- return mkerr(NotAFunction(
- handler_type.clone(),
- ))
- }
- };
-
- if variant_type != tx {
- return mkerr(TypeMismatch(
- handler_type.clone(),
- tx.clone(),
- variant_type.clone(),
- ));
- }
-
- // Extract `tb` from under the `x` binder. Fails is `x` was free in `tb`.
- match tb.over_binder(x) {
- Some(x) => x,
- None => return mkerr(
- MergeHandlerReturnTypeMustNotBeDependent,
- ),
- }
- }
- // Union alternative without type
- Some(None) => handler_type.clone(),
- None => {
- return mkerr(MergeHandlerMissingVariant(x.clone()))
- }
- };
- match &inferred_type {
- None => inferred_type = Some(handler_return_type),
- Some(t) => {
- if t != &handler_return_type {
- return mkerr(MergeHandlerTypeMismatch);
- }
- }
- }
- }
- for x in variants.keys() {
- if !handlers.contains_key(x) {
- return mkerr(MergeVariantMissingHandler(x.clone()));
- }
- }
-
- match (inferred_type, type_annot.as_ref()) {
- (Some(t1), Some(t2)) => {
- if &t1 != t2 {
- return mkerr(MergeAnnotMismatch);
- }
- RetTypeOnly(t1)
- }
- (Some(t), None) => RetTypeOnly(t),
- (None, Some(t)) => RetTypeOnly(t.clone()),
- (None, None) => return mkerr(MergeEmptyNeedsAnnotation),
- }
- }
- ToMap(_, _) => unimplemented!("toMap"),
- Projection(record, labels) => {
- let record_type = record.get_type()?;
- let record_type_borrow = record_type.as_whnf();
- let kts = match &*record_type_borrow {
- ValueKind::RecordType(kts) => kts,
- _ => return mkerr(ProjectionMustBeRecord),
- };
-
- let mut new_kts = HashMap::new();
- for l in labels {
- match kts.get(l) {
- None => return mkerr(ProjectionMissingEntry),
- Some(t) => {
- use std::collections::hash_map::Entry;
- match new_kts.entry(l.clone()) {
- Entry::Occupied(_) => {
- return mkerr(ProjectionDuplicateField)
- }
- Entry::Vacant(e) => e.insert(t.clone()),
- }
- }
- };
- }
-
- RetTypeOnly(Value::from_kind_and_type(
- ValueKind::RecordType(new_kts),
- record_type.get_type()?,
- ))
- }
- ProjectionByExpr(_, _) => unimplemented!("selection by expression"),
- Completion(_, _) => unimplemented!("record completion"),
- };
-
- Ok(match ret {
- RetTypeOnly(typ) => Value::from_kind_and_type_and_span(
- ValueKind::PartialExpr(e),
- typ,
- span,
- ),
- RetWhole(v) => v.with_span(span),
- })
-}
-
-/// `type_of` is the same as `type_with` with an empty context, meaning that the
-/// expression must be closed (i.e. no free variables), otherwise type-checking
-/// will fail.
-pub(crate) fn typecheck(e: Expr<Normalized>) -> Result<Value, TypeError> {
- type_with(&TypecheckContext::new(), e)
-}
-
-pub(crate) fn typecheck_with(
- expr: Expr<Normalized>,
- ty: Expr<Normalized>,
-) -> Result<Value, TypeError> {
- typecheck(expr.rewrap(ExprKind::Annot(expr.clone(), ty)))
-}
diff --git a/dhall/src/semantics/phase/resolve.rs b/dhall/src/semantics/resolve.rs
index cc4a024..3acf114 100644
--- a/dhall/src/semantics/phase/resolve.rs
+++ b/dhall/src/semantics/resolve.rs
@@ -2,9 +2,9 @@ use std::collections::HashMap;
use std::path::{Path, PathBuf};
use crate::error::{Error, ImportError};
-use crate::semantics::phase::{Normalized, NormalizedExpr, Parsed, Resolved};
use crate::syntax;
use crate::syntax::{FilePath, ImportLocation, URL};
+use crate::{Normalized, NormalizedExpr, Parsed, Resolved};
type Import = syntax::Import<NormalizedExpr>;
diff --git a/dhall/src/semantics/tck/env.rs b/dhall/src/semantics/tck/env.rs
new file mode 100644
index 0000000..812ca7a
--- /dev/null
+++ b/dhall/src/semantics/tck/env.rs
@@ -0,0 +1,124 @@
+use crate::semantics::{AlphaVar, NzEnv, NzVar, TyExprKind, Type, Value};
+use crate::syntax::{Label, V};
+
+/// Environment for indexing variables.
+#[derive(Debug, Clone, Copy)]
+pub(crate) struct VarEnv {
+ size: usize,
+}
+
+/// Environment for resolving names.
+#[derive(Debug, Clone)]
+pub(crate) struct NameEnv {
+ names: Vec<Label>,
+}
+
+/// Environment for typing expressions.
+#[derive(Debug, Clone)]
+pub(crate) struct TyEnv {
+ names: NameEnv,
+ items: NzEnv,
+}
+
+impl VarEnv {
+ pub fn new() -> Self {
+ VarEnv { size: 0 }
+ }
+ pub fn size(&self) -> usize {
+ self.size
+ }
+ pub fn insert(&self) -> Self {
+ VarEnv {
+ size: self.size + 1,
+ }
+ }
+ pub fn lookup(&self, var: &NzVar) -> AlphaVar {
+ self.lookup_fallible(var).unwrap()
+ }
+ pub fn lookup_fallible(&self, var: &NzVar) -> Option<AlphaVar> {
+ let idx = self.size.checked_sub(var.idx() + 1)?;
+ Some(AlphaVar::new(idx))
+ }
+}
+
+impl NameEnv {
+ pub fn new() -> Self {
+ NameEnv { names: Vec::new() }
+ }
+ pub fn as_varenv(&self) -> VarEnv {
+ VarEnv {
+ size: self.names.len(),
+ }
+ }
+
+ pub fn insert(&self, x: &Label) -> Self {
+ let mut env = self.clone();
+ env.insert_mut(x);
+ env
+ }
+ pub fn insert_mut(&mut self, x: &Label) {
+ self.names.push(x.clone())
+ }
+ pub fn remove_mut(&mut self) {
+ self.names.pop();
+ }
+
+ pub fn unlabel_var(&self, var: &V) -> Option<AlphaVar> {
+ let V(name, idx) = var;
+ let (idx, _) = self
+ .names
+ .iter()
+ .rev()
+ .enumerate()
+ .filter(|(_, n)| *n == name)
+ .nth(*idx)?;
+ Some(AlphaVar::new(idx))
+ }
+ pub fn label_var(&self, var: &AlphaVar) -> V {
+ let name = &self.names[self.names.len() - 1 - var.idx()];
+ let idx = self
+ .names
+ .iter()
+ .rev()
+ .take(var.idx())
+ .filter(|n| *n == name)
+ .count();
+ V(name.clone(), idx)
+ }
+}
+
+impl TyEnv {
+ pub fn new() -> Self {
+ TyEnv {
+ names: NameEnv::new(),
+ items: NzEnv::new(),
+ }
+ }
+ pub fn as_varenv(&self) -> VarEnv {
+ self.names.as_varenv()
+ }
+ pub fn as_nzenv(&self) -> &NzEnv {
+ &self.items
+ }
+ pub fn as_nameenv(&self) -> &NameEnv {
+ &self.names
+ }
+
+ pub fn insert_type(&self, x: &Label, t: Type) -> Self {
+ TyEnv {
+ names: self.names.insert(x),
+ items: self.items.insert_type(t),
+ }
+ }
+ pub fn insert_value(&self, x: &Label, e: Value) -> Self {
+ TyEnv {
+ names: self.names.insert(x),
+ items: self.items.insert_value(e),
+ }
+ }
+ pub fn lookup(&self, var: &V) -> Option<(TyExprKind, Type)> {
+ let var = self.names.unlabel_var(var)?;
+ let ty = self.items.lookup_ty(&var);
+ Some((TyExprKind::Var(var), ty))
+ }
+}
diff --git a/dhall/src/semantics/tck/mod.rs b/dhall/src/semantics/tck/mod.rs
new file mode 100644
index 0000000..1df2a48
--- /dev/null
+++ b/dhall/src/semantics/tck/mod.rs
@@ -0,0 +1,6 @@
+pub mod env;
+pub mod tyexpr;
+pub mod typecheck;
+pub(crate) use env::*;
+pub(crate) use tyexpr::*;
+pub(crate) use typecheck::*;
diff --git a/dhall/src/semantics/tck/tyexpr.rs b/dhall/src/semantics/tck/tyexpr.rs
new file mode 100644
index 0000000..1a048f9
--- /dev/null
+++ b/dhall/src/semantics/tck/tyexpr.rs
@@ -0,0 +1,137 @@
+use crate::error::{TypeError, TypeMessage};
+use crate::semantics::{rc, NameEnv, NzEnv, TyEnv, Value};
+use crate::syntax::{ExprKind, Span, V};
+use crate::Normalized;
+use crate::{NormalizedExpr, ToExprOptions};
+
+pub(crate) type Type = Value;
+
+/// Stores an alpha-normalized variable.
+#[derive(Debug, Clone, Copy)]
+pub struct AlphaVar {
+ idx: usize,
+}
+
+#[derive(Debug, Clone)]
+pub(crate) enum TyExprKind {
+ Var(AlphaVar),
+ // Forbidden ExprKind variants: Var, Import, Embed
+ Expr(ExprKind<TyExpr, Normalized>),
+}
+
+// An expression with inferred types at every node and resolved variables.
+#[derive(Clone)]
+pub(crate) struct TyExpr {
+ kind: Box<TyExprKind>,
+ ty: Option<Type>,
+ span: Span,
+}
+
+impl AlphaVar {
+ pub(crate) fn new(idx: usize) -> Self {
+ AlphaVar { idx }
+ }
+ pub(crate) fn idx(&self) -> usize {
+ self.idx
+ }
+}
+
+impl TyExpr {
+ pub fn new(kind: TyExprKind, ty: Option<Type>, span: Span) -> Self {
+ TyExpr {
+ kind: Box::new(kind),
+ ty,
+ span,
+ }
+ }
+
+ pub fn kind(&self) -> &TyExprKind {
+ &*self.kind
+ }
+ pub fn span(&self) -> &Span {
+ &self.span
+ }
+ pub fn get_type(&self) -> Result<Type, TypeError> {
+ match &self.ty {
+ Some(t) => Ok(t.clone()),
+ None => Err(TypeError::new(TypeMessage::Sort)),
+ }
+ }
+
+ /// Converts a value back to the corresponding AST expression.
+ pub fn to_expr(&self, opts: ToExprOptions) -> NormalizedExpr {
+ tyexpr_to_expr(self, opts, &mut NameEnv::new())
+ }
+ pub fn to_expr_tyenv(&self, env: &TyEnv) -> NormalizedExpr {
+ let opts = ToExprOptions {
+ normalize: true,
+ alpha: false,
+ };
+ let mut env = env.as_nameenv().clone();
+ tyexpr_to_expr(self, opts, &mut env)
+ }
+
+ /// Eval the TyExpr. It will actually get evaluated only as needed on demand.
+ pub fn eval(&self, env: &NzEnv) -> Value {
+ Value::new_thunk(env, self.clone())
+ }
+ /// Eval a closed TyExpr (i.e. without free variables). It will actually get evaluated only as
+ /// needed on demand.
+ pub fn eval_closed_expr(&self) -> Value {
+ self.eval(&NzEnv::new())
+ }
+ /// Eval a closed TyExpr fully and recursively;
+ pub fn rec_eval_closed_expr(&self) -> Value {
+ let mut val = self.eval_closed_expr();
+ val.normalize_mut();
+ val
+ }
+}
+
+fn tyexpr_to_expr<'a>(
+ tyexpr: &'a TyExpr,
+ opts: ToExprOptions,
+ env: &mut NameEnv,
+) -> NormalizedExpr {
+ rc(match tyexpr.kind() {
+ TyExprKind::Var(v) if opts.alpha => {
+ ExprKind::Var(V("_".into(), v.idx()))
+ }
+ TyExprKind::Var(v) => ExprKind::Var(env.label_var(v)),
+ TyExprKind::Expr(e) => {
+ let e = e.map_ref_maybe_binder(|l, tye| {
+ if let Some(l) = l {
+ env.insert_mut(l);
+ }
+ let e = tyexpr_to_expr(tye, opts, env);
+ if let Some(_) = l {
+ env.remove_mut();
+ }
+ e
+ });
+
+ match e {
+ ExprKind::Lam(_, t, e) if opts.alpha => {
+ ExprKind::Lam("_".into(), t, e)
+ }
+ ExprKind::Pi(_, t, e) if opts.alpha => {
+ ExprKind::Pi("_".into(), t, e)
+ }
+ e => e,
+ }
+ }
+ })
+}
+
+impl std::fmt::Debug for TyExpr {
+ fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ let mut x = fmt.debug_struct("TyExpr");
+ x.field("kind", self.kind());
+ if let Some(ty) = self.ty.as_ref() {
+ x.field("type", &ty);
+ } else {
+ x.field("type", &None::<()>);
+ }
+ x.finish()
+ }
+}
diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs
new file mode 100644
index 0000000..20076cd
--- /dev/null
+++ b/dhall/src/semantics/tck/typecheck.rs
@@ -0,0 +1,611 @@
+use std::borrow::Cow;
+use std::cmp::max;
+use std::collections::HashMap;
+
+use crate::error::{TypeError, TypeMessage};
+use crate::semantics::merge_maps;
+use crate::semantics::{
+ type_of_builtin, Binder, BuiltinClosure, Closure, TyEnv, TyExpr,
+ TyExprKind, Type, Value, ValueKind,
+};
+use crate::syntax::{
+ BinOp, Builtin, Const, Expr, ExprKind, InterpolatedTextContents, Span,
+};
+use crate::Normalized;
+
+fn type_of_recordtype<'a>(
+ tys: impl Iterator<Item = Cow<'a, TyExpr>>,
+) -> Result<Type, TypeError> {
+ // An empty record type has type Type
+ let mut k = Const::Type;
+ for t in tys {
+ match t.get_type()?.as_const() {
+ Some(c) => k = max(k, c),
+ None => return mkerr("InvalidFieldType"),
+ }
+ }
+ Ok(Value::from_const(k))
+}
+
+fn function_check(a: Const, b: Const) -> Const {
+ if b == Const::Type {
+ Const::Type
+ } else {
+ max(a, b)
+ }
+}
+
+fn type_of_function(src: Type, tgt: Type) -> Result<Type, TypeError> {
+ let ks = match src.as_const() {
+ Some(k) => k,
+ _ => return Err(TypeError::new(TypeMessage::InvalidInputType(src))),
+ };
+ let kt = match tgt.as_const() {
+ Some(k) => k,
+ _ => return Err(TypeError::new(TypeMessage::InvalidOutputType(tgt))),
+ };
+
+ Ok(Value::from_const(function_check(ks, kt)))
+}
+
+fn mkerr<T, S: ToString>(x: S) -> Result<T, TypeError> {
+ Err(TypeError::new(TypeMessage::Custom(x.to_string())))
+}
+
+/// When all sub-expressions have been typed, check the remaining toplevel
+/// layer.
+fn type_one_layer(
+ env: &TyEnv,
+ kind: &ExprKind<TyExpr, Normalized>,
+) -> Result<Type, TypeError> {
+ Ok(match kind {
+ ExprKind::Import(..) => unreachable!(
+ "There should remain no imports in a resolved expression"
+ ),
+ ExprKind::Var(..)
+ | ExprKind::Lam(..)
+ | ExprKind::Pi(..)
+ | ExprKind::Let(..)
+ | ExprKind::Const(Const::Sort)
+ | ExprKind::Embed(..) => unreachable!(), // Handled in type_with
+
+ ExprKind::Const(Const::Type) => Value::from_const(Const::Kind),
+ ExprKind::Const(Const::Kind) => Value::from_const(Const::Sort),
+ ExprKind::Builtin(b) => {
+ let t_expr = type_of_builtin(*b);
+ let t_tyexpr = type_with(env, &t_expr)?;
+ t_tyexpr.eval(env.as_nzenv())
+ }
+ ExprKind::BoolLit(_) => Value::from_builtin(Builtin::Bool),
+ ExprKind::NaturalLit(_) => Value::from_builtin(Builtin::Natural),
+ ExprKind::IntegerLit(_) => Value::from_builtin(Builtin::Integer),
+ ExprKind::DoubleLit(_) => Value::from_builtin(Builtin::Double),
+ ExprKind::TextLit(interpolated) => {
+ let text_type = Value::from_builtin(Builtin::Text);
+ for contents in interpolated.iter() {
+ use InterpolatedTextContents::Expr;
+ if let Expr(x) = contents {
+ if x.get_type()? != text_type {
+ return mkerr("InvalidTextInterpolation");
+ }
+ }
+ }
+ text_type
+ }
+ ExprKind::EmptyListLit(t) => {
+ let t = t.eval(env.as_nzenv());
+ match &*t.kind() {
+ ValueKind::AppliedBuiltin(BuiltinClosure {
+ b: Builtin::List,
+ args,
+ ..
+ }) if args.len() == 1 => {}
+ _ => return mkerr("InvalidListType"),
+ };
+ t
+ }
+ ExprKind::NEListLit(xs) => {
+ let mut iter = xs.iter();
+ let x = iter.next().unwrap();
+ for y in iter {
+ if x.get_type()? != y.get_type()? {
+ return mkerr("InvalidListElement");
+ }
+ }
+ let t = x.get_type()?;
+ if t.get_type()?.as_const() != Some(Const::Type) {
+ return mkerr("InvalidListType");
+ }
+
+ Value::from_builtin(Builtin::List).app(t)
+ }
+ ExprKind::SomeLit(x) => {
+ let t = x.get_type()?;
+ if t.get_type()?.as_const() != Some(Const::Type) {
+ return mkerr("InvalidOptionalType");
+ }
+
+ Value::from_builtin(Builtin::Optional).app(t)
+ }
+ ExprKind::RecordLit(kvs) => {
+ use std::collections::hash_map::Entry;
+ let mut kts = HashMap::new();
+ for (x, v) in kvs {
+ // Check for duplicated entries
+ match kts.entry(x.clone()) {
+ Entry::Occupied(_) => {
+ return mkerr("RecordTypeDuplicateField")
+ }
+ Entry::Vacant(e) => e.insert(v.get_type()?),
+ };
+ }
+
+ let ty = type_of_recordtype(
+ kts.iter()
+ .map(|(_, t)| Cow::Owned(t.to_tyexpr(env.as_varenv()))),
+ )?;
+ Value::from_kind_and_type(ValueKind::RecordType(kts), ty)
+ }
+ ExprKind::RecordType(kts) => {
+ use std::collections::hash_map::Entry;
+ let mut seen_fields = HashMap::new();
+ for (x, _) in kts {
+ // Check for duplicated entries
+ match seen_fields.entry(x.clone()) {
+ Entry::Occupied(_) => {
+ return mkerr("RecordTypeDuplicateField")
+ }
+ Entry::Vacant(e) => e.insert(()),
+ };
+ }
+
+ type_of_recordtype(kts.iter().map(|(_, t)| Cow::Borrowed(t)))?
+ }
+ ExprKind::UnionType(kts) => {
+ use std::collections::hash_map::Entry;
+ let mut seen_fields = HashMap::new();
+ // Check that all types are the same const
+ let mut k = None;
+ for (x, t) in kts {
+ if let Some(t) = t {
+ match (k, t.get_type()?.as_const()) {
+ (None, Some(k2)) => k = Some(k2),
+ (Some(k1), Some(k2)) if k1 == k2 => {}
+ _ => return mkerr("InvalidFieldType"),
+ }
+ }
+ match seen_fields.entry(x) {
+ Entry::Occupied(_) => {
+ return mkerr("UnionTypeDuplicateField")
+ }
+ Entry::Vacant(e) => e.insert(()),
+ };
+ }
+
+ // An empty union type has type Type;
+ // an union type with only unary variants also has type Type
+ let k = k.unwrap_or(Const::Type);
+
+ Value::from_const(k)
+ }
+ ExprKind::Field(scrut, x) => {
+ match &*scrut.get_type()?.kind() {
+ ValueKind::RecordType(kts) => match kts.get(&x) {
+ Some(tth) => tth.clone(),
+ None => return mkerr("MissingRecordField"),
+ },
+ // TODO: branch here only when scrut.get_type() is a Const
+ _ => {
+ let scrut_nf = scrut.eval(env.as_nzenv());
+ match scrut_nf.kind() {
+ ValueKind::UnionType(kts) => match kts.get(x) {
+ // Constructor has type T -> < x: T, ... >
+ Some(Some(ty)) => {
+ let pi_ty = type_of_function(
+ ty.get_type()?,
+ scrut.get_type()?,
+ )?;
+ Value::from_kind_and_type(
+ ValueKind::PiClosure {
+ binder: Binder::new(x.clone()),
+ annot: ty.clone(),
+ closure: Closure::new_constant(
+ scrut_nf,
+ ),
+ },
+ pi_ty,
+ )
+ }
+ Some(None) => scrut_nf,
+ None => return mkerr("MissingUnionField"),
+ },
+ _ => return mkerr("NotARecord"),
+ }
+ } // _ => mkerr("NotARecord"),
+ }
+ }
+ ExprKind::Annot(x, t) => {
+ let t = t.eval(env.as_nzenv());
+ let x_ty = x.get_type()?;
+ if x_ty != t {
+ return mkerr(format!(
+ "annot mismatch: ({} : {}) : {}",
+ x.to_expr_tyenv(env),
+ x_ty.to_tyexpr(env.as_varenv()).to_expr_tyenv(env),
+ t.to_tyexpr(env.as_varenv()).to_expr_tyenv(env)
+ ));
+ // return mkerr(format!(
+ // "annot mismatch: {} != {}",
+ // x_ty.to_tyexpr(env.as_varenv()).to_expr_tyenv(env),
+ // t.to_tyexpr(env.as_varenv()).to_expr_tyenv(env)
+ // ));
+ // return mkerr(format!("annot mismatch: {:#?} : {:#?}", x, t,));
+ }
+ x_ty
+ }
+ ExprKind::Assert(t) => {
+ let t = t.eval(env.as_nzenv());
+ match &*t.kind() {
+ ValueKind::Equivalence(x, y) if x == y => {}
+ ValueKind::Equivalence(..) => return mkerr("AssertMismatch"),
+ _ => return mkerr("AssertMustTakeEquivalence"),
+ }
+ t
+ }
+ ExprKind::App(f, arg) => {
+ match f.get_type()?.kind() {
+ ValueKind::PiClosure { annot, closure, .. } => {
+ if arg.get_type()? != *annot {
+ // return mkerr(format!("function annot mismatch"));
+ return mkerr(format!(
+ "function annot mismatch: ({} : {}) : {}",
+ arg.to_expr_tyenv(env),
+ arg.get_type()?
+ .to_tyexpr(env.as_varenv())
+ .to_expr_tyenv(env),
+ annot.to_tyexpr(env.as_varenv()).to_expr_tyenv(env),
+ ));
+ }
+
+ let arg_nf = arg.eval(env.as_nzenv());
+ closure.apply(arg_nf)
+ }
+ _ => return mkerr(format!("apply to not Pi")),
+ }
+ }
+ ExprKind::BoolIf(x, y, z) => {
+ if *x.get_type()?.kind() != ValueKind::from_builtin(Builtin::Bool) {
+ return mkerr("InvalidPredicate");
+ }
+ if y.get_type()?.get_type()?.as_const() != Some(Const::Type) {
+ return mkerr("IfBranchMustBeTerm");
+ }
+ if z.get_type()?.get_type()?.as_const() != Some(Const::Type) {
+ return mkerr("IfBranchMustBeTerm");
+ }
+ if y.get_type()? != z.get_type()? {
+ return mkerr("IfBranchMismatch");
+ }
+
+ y.get_type()?
+ }
+ ExprKind::BinOp(BinOp::RightBiasedRecordMerge, x, y) => {
+ let x_type = x.get_type()?;
+ let y_type = y.get_type()?;
+
+ // Extract the LHS record type
+ let kts_x = match x_type.kind() {
+ ValueKind::RecordType(kts) => kts,
+ _ => return mkerr("MustCombineRecord"),
+ };
+ // Extract the RHS record type
+ let kts_y = match y_type.kind() {
+ ValueKind::RecordType(kts) => kts,
+ _ => return mkerr("MustCombineRecord"),
+ };
+
+ // Union the two records, prefering
+ // the values found in the RHS.
+ let kts = merge_maps::<_, _, _, !>(kts_x, kts_y, |_, _, r_t| {
+ Ok(r_t.clone())
+ })?;
+
+ // Construct the final record type
+ let ty = type_of_recordtype(
+ kts.iter()
+ .map(|(_, t)| Cow::Owned(t.to_tyexpr(env.as_varenv()))),
+ )?;
+ Value::from_kind_and_type(ValueKind::RecordType(kts), ty)
+ }
+ ExprKind::BinOp(BinOp::RecursiveRecordMerge, x, y) => {
+ let ekind = ExprKind::BinOp(
+ BinOp::RecursiveRecordTypeMerge,
+ x.get_type()?.to_tyexpr(env.as_varenv()),
+ y.get_type()?.to_tyexpr(env.as_varenv()),
+ );
+ let ty = type_one_layer(env, &ekind)?;
+ TyExpr::new(TyExprKind::Expr(ekind), Some(ty), Span::Artificial)
+ .eval(env.as_nzenv())
+ }
+ ExprKind::BinOp(BinOp::RecursiveRecordTypeMerge, x, y) => {
+ let x_val = x.eval(env.as_nzenv());
+ let y_val = y.eval(env.as_nzenv());
+ let kts_x = match x_val.kind() {
+ ValueKind::RecordType(kts) => kts,
+ _ => return mkerr("RecordTypeMergeRequiresRecordType"),
+ };
+ let kts_y = match y_val.kind() {
+ ValueKind::RecordType(kts) => kts,
+ _ => return mkerr("RecordTypeMergeRequiresRecordType"),
+ };
+ for (k, tx) in kts_x {
+ if let Some(ty) = kts_y.get(k) {
+ type_one_layer(
+ env,
+ &ExprKind::BinOp(
+ BinOp::RecursiveRecordTypeMerge,
+ tx.to_tyexpr(env.as_varenv()),
+ ty.to_tyexpr(env.as_varenv()),
+ ),
+ )?;
+ }
+ }
+
+ // A RecordType's type is always a const
+ let xk = x.get_type()?.as_const().unwrap();
+ let yk = y.get_type()?.as_const().unwrap();
+ Value::from_const(max(xk, yk))
+ }
+ ExprKind::BinOp(BinOp::ListAppend, l, r) => {
+ let l_ty = l.get_type()?;
+ match &*l_ty.kind() {
+ ValueKind::AppliedBuiltin(BuiltinClosure {
+ b: Builtin::List,
+ ..
+ }) => {}
+ _ => return mkerr("BinOpTypeMismatch"),
+ }
+
+ if l_ty != r.get_type()? {
+ return mkerr("BinOpTypeMismatch");
+ }
+
+ l_ty
+ }
+ ExprKind::BinOp(BinOp::Equivalence, l, r) => {
+ if l.get_type()? != r.get_type()? {
+ return mkerr("EquivalenceTypeMismatch");
+ }
+ if l.get_type()?.get_type()?.as_const() != Some(Const::Type) {
+ return mkerr("EquivalenceArgumentsMustBeTerms");
+ }
+
+ Value::from_const(Const::Type)
+ }
+ ExprKind::BinOp(o, l, r) => {
+ let t = Value::from_builtin(match o {
+ BinOp::BoolAnd
+ | BinOp::BoolOr
+ | BinOp::BoolEQ
+ | BinOp::BoolNE => Builtin::Bool,
+ BinOp::NaturalPlus | BinOp::NaturalTimes => Builtin::Natural,
+ BinOp::TextAppend => Builtin::Text,
+ BinOp::ListAppend
+ | BinOp::RightBiasedRecordMerge
+ | BinOp::RecursiveRecordMerge
+ | BinOp::RecursiveRecordTypeMerge
+ | BinOp::Equivalence => unreachable!(),
+ BinOp::ImportAlt => unreachable!("ImportAlt leftover in tck"),
+ });
+
+ if l.get_type()? != t {
+ return mkerr("BinOpTypeMismatch");
+ }
+
+ if r.get_type()? != t {
+ return mkerr("BinOpTypeMismatch");
+ }
+
+ t
+ }
+ ExprKind::Merge(record, union, type_annot) => {
+ let record_type = record.get_type()?;
+ let handlers = match record_type.kind() {
+ ValueKind::RecordType(kts) => kts,
+ _ => return mkerr("Merge1ArgMustBeRecord"),
+ };
+
+ let union_type = union.get_type()?;
+ let variants = match union_type.kind() {
+ ValueKind::UnionType(kts) => Cow::Borrowed(kts),
+ ValueKind::AppliedBuiltin(BuiltinClosure {
+ b: Builtin::Optional,
+ args,
+ ..
+ }) if args.len() == 1 => {
+ let ty = &args[0];
+ let mut kts = HashMap::new();
+ kts.insert("None".into(), None);
+ kts.insert("Some".into(), Some(ty.clone()));
+ Cow::Owned(kts)
+ }
+ _ => return mkerr("Merge2ArgMustBeUnionOrOptional"),
+ };
+
+ let mut inferred_type = None;
+ for (x, handler_type) in handlers {
+ let handler_return_type = match variants.get(x) {
+ // Union alternative with type
+ Some(Some(variant_type)) => match handler_type.kind() {
+ ValueKind::PiClosure { closure, annot, .. } => {
+ if variant_type != annot {
+ return mkerr("MergeHandlerTypeMismatch");
+ }
+
+ closure.remove_binder().or_else(|()| {
+ mkerr("MergeReturnTypeIsDependent")
+ })?
+ }
+ _ => return mkerr("NotAFunction"),
+ },
+ // Union alternative without type
+ Some(None) => handler_type.clone(),
+ None => return mkerr("MergeHandlerMissingVariant"),
+ };
+ match &inferred_type {
+ None => inferred_type = Some(handler_return_type),
+ Some(t) => {
+ if t != &handler_return_type {
+ return mkerr("MergeHandlerTypeMismatch");
+ }
+ }
+ }
+ }
+ for x in variants.keys() {
+ if !handlers.contains_key(x) {
+ return mkerr("MergeVariantMissingHandler");
+ }
+ }
+
+ let type_annot =
+ type_annot.as_ref().map(|t| t.eval(env.as_nzenv()));
+ match (inferred_type, type_annot) {
+ (Some(t1), Some(t2)) => {
+ if t1 != t2 {
+ return mkerr("MergeAnnotMismatch");
+ }
+ t1
+ }
+ (Some(t), None) => t,
+ (None, Some(t)) => t,
+ (None, None) => return mkerr("MergeEmptyNeedsAnnotation"),
+ }
+ }
+ ExprKind::ToMap(_, _) => unimplemented!("toMap"),
+ ExprKind::Projection(record, labels) => {
+ let record_type = record.get_type()?;
+ let kts = match record_type.kind() {
+ ValueKind::RecordType(kts) => kts,
+ _ => return mkerr("ProjectionMustBeRecord"),
+ };
+
+ let mut new_kts = HashMap::new();
+ for l in labels {
+ match kts.get(l) {
+ None => return mkerr("ProjectionMissingEntry"),
+ Some(t) => {
+ use std::collections::hash_map::Entry;
+ match new_kts.entry(l.clone()) {
+ Entry::Occupied(_) => {
+ return mkerr("ProjectionDuplicateField")
+ }
+ Entry::Vacant(e) => e.insert(t.clone()),
+ }
+ }
+ };
+ }
+
+ Value::from_kind_and_type(
+ ValueKind::RecordType(new_kts),
+ record_type.get_type()?,
+ )
+ }
+ ExprKind::ProjectionByExpr(_, _) => {
+ unimplemented!("selection by expression")
+ }
+ ExprKind::Completion(_, _) => unimplemented!("record completion"),
+ })
+}
+
+/// `type_with` typechecks an expressio in the provided environment.
+pub(crate) fn type_with(
+ env: &TyEnv,
+ expr: &Expr<Normalized>,
+) -> Result<TyExpr, TypeError> {
+ let (tyekind, ty) = match expr.as_ref() {
+ ExprKind::Var(var) => match env.lookup(&var) {
+ Some((k, ty)) => (k, Some(ty)),
+ None => return mkerr("unbound variable"),
+ },
+ ExprKind::Lam(binder, annot, body) => {
+ let annot = type_with(env, annot)?;
+ let annot_nf = annot.eval(env.as_nzenv());
+ let body_env = env.insert_type(&binder, annot_nf.clone());
+ let body = type_with(&body_env, body)?;
+ let body_ty = body.get_type()?;
+ let ty = TyExpr::new(
+ TyExprKind::Expr(ExprKind::Pi(
+ binder.clone(),
+ annot.clone(),
+ body_ty.to_tyexpr(body_env.as_varenv()),
+ )),
+ Some(type_of_function(annot.get_type()?, body_ty.get_type()?)?),
+ Span::Artificial,
+ );
+ let ty = ty.eval(env.as_nzenv());
+ (
+ TyExprKind::Expr(ExprKind::Lam(binder.clone(), annot, body)),
+ Some(ty),
+ )
+ }
+ ExprKind::Pi(binder, annot, body) => {
+ let annot = type_with(env, annot)?;
+ let annot_nf = annot.eval(env.as_nzenv());
+ let body =
+ type_with(&env.insert_type(binder, annot_nf.clone()), body)?;
+ let ty = type_of_function(annot.get_type()?, body.get_type()?)?;
+ (
+ TyExprKind::Expr(ExprKind::Pi(binder.clone(), annot, body)),
+ Some(ty),
+ )
+ }
+ ExprKind::Let(binder, annot, val, body) => {
+ let val = if let Some(t) = annot {
+ t.rewrap(ExprKind::Annot(val.clone(), t.clone()))
+ } else {
+ val.clone()
+ };
+
+ let val = type_with(env, &val)?;
+ let val_nf = val.eval(&env.as_nzenv());
+ let body = type_with(&env.insert_value(&binder, val_nf), body)?;
+ let body_ty = body.get_type().ok();
+ (
+ TyExprKind::Expr(ExprKind::Let(
+ binder.clone(),
+ None,
+ val,
+ body,
+ )),
+ body_ty,
+ )
+ }
+ ExprKind::Const(Const::Sort) => {
+ (TyExprKind::Expr(ExprKind::Const(Const::Sort)), None)
+ }
+ ExprKind::Embed(p) => {
+ return Ok(p.clone().into_value().to_tyexpr_noenv())
+ }
+ ekind => {
+ let ekind = ekind.traverse_ref(|e| type_with(env, e))?;
+ let ty = type_one_layer(env, &ekind)?;
+ (TyExprKind::Expr(ekind), Some(ty))
+ }
+ };
+
+ Ok(TyExpr::new(tyekind, ty, expr.span()))
+}
+
+/// Typecheck an expression and return the expression annotated with types if type-checking
+/// succeeded, or an error if type-checking failed.
+pub(crate) fn typecheck(e: &Expr<Normalized>) -> Result<TyExpr, TypeError> {
+ type_with(&TyEnv::new(), e)
+}
+
+/// Like `typecheck`, but additionally checks that the expression's type matches the provided type.
+pub(crate) fn typecheck_with(
+ expr: &Expr<Normalized>,
+ ty: Expr<Normalized>,
+) -> Result<TyExpr, TypeError> {
+ typecheck(&expr.rewrap(ExprKind::Annot(expr.clone(), ty)))
+}
diff --git a/dhall/src/semantics/to_expr.rs b/dhall/src/semantics/to_expr.rs
deleted file mode 100644
index b21fb29..0000000
--- a/dhall/src/semantics/to_expr.rs
+++ /dev/null
@@ -1,105 +0,0 @@
-use crate::semantics::core::value::Value;
-use crate::semantics::core::value::ValueKind;
-use crate::semantics::phase::typecheck::rc;
-use crate::semantics::phase::NormalizedExpr;
-use crate::syntax;
-use crate::syntax::{Builtin, ExprKind};
-
-#[derive(Copy, Clone)]
-/// Controls conversion from `Value` to `Expr`
-pub(crate) struct ToExprOptions {
- /// Whether to convert all variables to `_`
- pub(crate) alpha: bool,
- /// Whether to normalize before converting
- pub(crate) normalize: bool,
-}
-
-/// Converts a value back to the corresponding AST expression.
-pub(crate) fn value_to_expr(
- val: &Value,
- opts: ToExprOptions,
-) -> NormalizedExpr {
- if opts.normalize {
- val.normalize_whnf();
- }
- val.as_kind().to_expr(opts)
-}
-
-/// Converts a value back to the corresponding AST expression.
-pub(crate) fn kind_to_expr(
- kind: &ValueKind,
- opts: ToExprOptions,
-) -> NormalizedExpr {
- match kind {
- ValueKind::Lam(x, t, e) => rc(ExprKind::Lam(
- x.to_label_maybe_alpha(opts.alpha),
- t.to_expr(opts),
- e.to_expr(opts),
- )),
- ValueKind::AppliedBuiltin(b, args) => args
- .iter()
- .map(|v| v.to_expr(opts))
- .fold(rc(ExprKind::Builtin(*b)), |acc, v| {
- rc(ExprKind::App(acc, v))
- }),
- ValueKind::Pi(x, t, e) => rc(ExprKind::Pi(
- x.to_label_maybe_alpha(opts.alpha),
- t.to_expr(opts),
- e.to_expr(opts),
- )),
- ValueKind::Var(v) => rc(ExprKind::Var(v.to_var(opts.alpha))),
- ValueKind::Const(c) => rc(ExprKind::Const(*c)),
- ValueKind::BoolLit(b) => rc(ExprKind::BoolLit(*b)),
- ValueKind::NaturalLit(n) => rc(ExprKind::NaturalLit(*n)),
- ValueKind::IntegerLit(n) => rc(ExprKind::IntegerLit(*n)),
- ValueKind::DoubleLit(n) => rc(ExprKind::DoubleLit(*n)),
- ValueKind::EmptyOptionalLit(n) => rc(ExprKind::App(
- rc(ExprKind::Builtin(Builtin::OptionalNone)),
- n.to_expr(opts),
- )),
- ValueKind::NEOptionalLit(n) => rc(ExprKind::SomeLit(n.to_expr(opts))),
- ValueKind::EmptyListLit(n) => {
- rc(ExprKind::EmptyListLit(rc(ExprKind::App(
- rc(ExprKind::Builtin(Builtin::List)),
- n.to_expr(opts),
- ))))
- }
- ValueKind::NEListLit(elts) => rc(ExprKind::NEListLit(
- elts.iter().map(|n| n.to_expr(opts)).collect(),
- )),
- ValueKind::RecordLit(kvs) => rc(ExprKind::RecordLit(
- kvs.iter()
- .map(|(k, v)| (k.clone(), v.to_expr(opts)))
- .collect(),
- )),
- ValueKind::RecordType(kts) => rc(ExprKind::RecordType(
- kts.iter()
- .map(|(k, v)| (k.clone(), v.to_expr(opts)))
- .collect(),
- )),
- ValueKind::UnionType(kts) => rc(ExprKind::UnionType(
- kts.iter()
- .map(|(k, v)| (k.clone(), v.as_ref().map(|v| v.to_expr(opts))))
- .collect(),
- )),
- ValueKind::UnionConstructor(l, kts) => rc(ExprKind::Field(
- ValueKind::UnionType(kts.clone()).to_expr(opts),
- l.clone(),
- )),
- ValueKind::UnionLit(l, v, kts) => rc(ExprKind::App(
- ValueKind::UnionConstructor(l.clone(), kts.clone()).to_expr(opts),
- v.to_expr(opts),
- )),
- ValueKind::TextLit(elts) => rc(ExprKind::TextLit(
- elts.iter()
- .map(|contents| contents.map_ref(|e| e.to_expr(opts)))
- .collect(),
- )),
- ValueKind::Equivalence(x, y) => rc(ExprKind::BinOp(
- syntax::BinOp::Equivalence,
- x.to_expr(opts),
- y.to_expr(opts),
- )),
- ValueKind::PartialExpr(e) => rc(e.map_ref(|v| v.to_expr(opts))),
- }
-}
diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 68cb524..28a0aee 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -24,7 +24,7 @@ pub enum Const {
/// The `Int` field is a DeBruijn index.
/// See dhall-lang/standard/semantics.md for details
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
-pub struct V<Label>(pub Label, pub usize);
+pub struct V(pub Label, pub usize);
// Definition order must match precedence order for
// pretty-printing to work correctly
@@ -112,7 +112,7 @@ pub enum ExprKind<SubExpr, Embed> {
Const(Const),
/// `x`
/// `x@n`
- Var(V<Label>),
+ Var(V),
/// `λ(x : A) -> b`
Lam(Label, SubExpr, SubExpr),
/// `A -> B`
@@ -174,29 +174,38 @@ pub enum ExprKind<SubExpr, Embed> {
}
impl<SE, E> ExprKind<SE, E> {
+ pub fn traverse_ref_maybe_binder<'a, SE2, Err>(
+ &'a self,
+ visit: impl FnMut(Option<&'a Label>, &'a SE) -> Result<SE2, Err>,
+ ) -> Result<ExprKind<SE2, E>, Err>
+ where
+ E: Clone,
+ {
+ visitor::TraverseRefMaybeBinderVisitor(visit).visit(self)
+ }
+
pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>(
&'a self,
- visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
- visit_under_binder: impl FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>,
+ mut visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
+ mut visit_under_binder: impl FnMut(&'a Label, &'a SE) -> Result<SE2, Err>,
) -> Result<ExprKind<SE2, E>, Err>
where
E: Clone,
{
- visitor::TraverseRefWithBindersVisitor {
- visit_subexpr,
- visit_under_binder,
- }
- .visit(self)
+ self.traverse_ref_maybe_binder(|l, x| match l {
+ None => visit_subexpr(x),
+ Some(l) => visit_under_binder(l, x),
+ })
}
- fn traverse_ref<'a, SE2, Err>(
+ pub(crate) fn traverse_ref<'a, SE2, Err>(
&'a self,
- visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
+ mut visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
) -> Result<ExprKind<SE2, E>, Err>
where
E: Clone,
{
- visitor::TraverseRefVisitor { visit_subexpr }.visit(self)
+ self.traverse_ref_maybe_binder(|_, e| visit_subexpr(e))
}
fn traverse_mut<'a, Err>(
@@ -206,6 +215,16 @@ impl<SE, E> ExprKind<SE, E> {
visitor::TraverseMutVisitor { visit_subexpr }.visit(self)
}
+ pub fn map_ref_maybe_binder<'a, SE2>(
+ &'a self,
+ mut map: impl FnMut(Option<&'a Label>, &'a SE) -> SE2,
+ ) -> ExprKind<SE2, E>
+ where
+ E: Clone,
+ {
+ trivial_result(self.traverse_ref_maybe_binder(|l, x| Ok(map(l, x))))
+ }
+
pub fn map_ref_with_special_handling_of_binders<'a, SE2>(
&'a self,
mut map_subexpr: impl FnMut(&'a SE) -> SE2,
@@ -214,10 +233,10 @@ impl<SE, E> ExprKind<SE, E> {
where
E: Clone,
{
- trivial_result(self.traverse_ref_with_special_handling_of_binders(
- |x| Ok(map_subexpr(x)),
- |l, x| Ok(map_under_binder(l, x)),
- ))
+ self.map_ref_maybe_binder(|l, x| match l {
+ None => map_subexpr(x),
+ Some(l) => map_under_binder(l, x),
+ })
}
pub fn map_ref<'a, SE2>(
@@ -227,7 +246,7 @@ impl<SE, E> ExprKind<SE, E> {
where
E: Clone,
{
- trivial_result(self.traverse_ref(|x| Ok(map_subexpr(x))))
+ self.map_ref_maybe_binder(|_, e| map_subexpr(e))
}
pub fn map_mut<'a>(&'a mut self, mut map_subexpr: impl FnMut(&'a mut SE)) {
@@ -295,22 +314,6 @@ impl<E> Expr<E> {
}
}
-impl<Label: PartialEq + Clone> V<Label> {
- pub fn shift(&self, delta: isize, var: &V<Label>) -> Option<Self> {
- let V(x, n) = var;
- let V(y, m) = self;
- Some(if x == y && n <= m {
- V(y.clone(), add_ui(*m, delta)?)
- } else {
- V(y.clone(), *m)
- })
- }
-
- pub fn over_binder(&self, x: &Label) -> Option<Self> {
- self.shift(-1, &V(x.clone(), 0))
- }
-}
-
pub fn trivial_result<T>(x: Result<T, !>) -> T {
match x {
Ok(x) => x,
@@ -318,16 +321,6 @@ pub fn trivial_result<T>(x: Result<T, !>) -> T {
}
}
-/// Add an isize to an usize
-/// Returns `None` on over/underflow
-fn add_ui(u: usize, i: isize) -> Option<usize> {
- Some(if i < 0 {
- u.checked_sub(i.checked_neg()? as usize)?
- } else {
- u.checked_add(i as usize)?
- })
-}
-
impl PartialEq for NaiveDouble {
fn eq(&self, other: &Self) -> bool {
self.0.to_bits() == other.0.to_bits()
@@ -357,9 +350,8 @@ impl From<NaiveDouble> for f64 {
}
}
-/// This is only for the specific `Label` type, not generic
-impl From<Label> for V<Label> {
- fn from(x: Label) -> V<Label> {
+impl From<Label> for V {
+ fn from(x: Label) -> V {
V(x, 0)
}
}
diff --git a/dhall/src/syntax/ast/visitor.rs b/dhall/src/syntax/ast/visitor.rs
index 424048b..6a1ce7d 100644
--- a/dhall/src/syntax/ast/visitor.rs
+++ b/dhall/src/syntax/ast/visitor.rs
@@ -1,6 +1,7 @@
-use crate::syntax::*;
use std::iter::FromIterator;
+use crate::syntax::*;
+
/// A visitor trait that can be used to traverse `ExprKind`s. We need this pattern so that Rust lets
/// us have as much mutability as we can.
/// For example, `traverse_ref_with_special_handling_of_binders` cannot be made using only
@@ -295,51 +296,26 @@ where
Ok(())
}
-pub struct TraverseRefWithBindersVisitor<F1, F2> {
- pub visit_subexpr: F1,
- pub visit_under_binder: F2,
-}
+pub struct TraverseRefMaybeBinderVisitor<F>(pub F);
-impl<'a, SE, E, SE2, Err, F1, F2> ExprKindVisitor<'a, SE, SE2, E, E>
- for TraverseRefWithBindersVisitor<F1, F2>
+impl<'a, SE, E, SE2, Err, F> ExprKindVisitor<'a, SE, SE2, E, E>
+ for TraverseRefMaybeBinderVisitor<F>
where
SE: 'a,
E: 'a + Clone,
- F1: FnMut(&'a SE) -> Result<SE2, Err>,
- F2: FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>,
+ F: FnMut(Option<&'a Label>, &'a SE) -> Result<SE2, Err>,
{
type Error = Err;
fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> {
- (self.visit_subexpr)(subexpr)
+ (self.0)(None, subexpr)
}
fn visit_subexpr_under_binder(
- self,
+ mut self,
label: &'a Label,
subexpr: &'a SE,
) -> Result<SE2, Self::Error> {
- (self.visit_under_binder)(label, subexpr)
- }
- fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> {
- Ok(embed.clone())
- }
-}
-
-pub struct TraverseRefVisitor<F1> {
- pub visit_subexpr: F1,
-}
-
-impl<'a, SE, E, SE2, Err, F1> ExprKindVisitor<'a, SE, SE2, E, E>
- for TraverseRefVisitor<F1>
-where
- SE: 'a,
- E: 'a + Clone,
- F1: FnMut(&'a SE) -> Result<SE2, Err>,
-{
- type Error = Err;
-
- fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> {
- (self.visit_subexpr)(subexpr)
+ (self.0)(Some(label), subexpr)
}
fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> {
Ok(embed.clone())
diff --git a/dhall/src/syntax/binary/decode.rs b/dhall/src/syntax/binary/decode.rs
index c18deb5..52b699c 100644
--- a/dhall/src/syntax/binary/decode.rs
+++ b/dhall/src/syntax/binary/decode.rs
@@ -3,13 +3,13 @@ use serde_cbor::value::value as cbor;
use std::iter::FromIterator;
use crate::error::DecodeError;
-use crate::semantics::phase::DecodedExpr;
use crate::syntax;
use crate::syntax::{
Expr, ExprKind, FilePath, FilePrefix, Hash, ImportLocation, ImportMode,
Integer, InterpolatedText, Label, Natural, Scheme, Span, UnspannedExpr,
URL, V,
};
+use crate::DecodedExpr;
pub(crate) fn decode(data: &[u8]) -> Result<DecodedExpr, DecodeError> {
match serde_cbor::de::from_slice(data) {
diff --git a/dhall/src/syntax/text/dhall.abnf b/dhall/src/syntax/text/dhall.abnf
new file mode 120000
index 0000000..4a95034
--- /dev/null
+++ b/dhall/src/syntax/text/dhall.abnf
@@ -0,0 +1 @@
+../../../../dhall-lang/standard/dhall.abnf \ No newline at end of file
diff --git a/dhall/src/dhall.pest.visibility b/dhall/src/syntax/text/dhall.pest.visibility
index 03a000b..03a000b 100644
--- a/dhall/src/dhall.pest.visibility
+++ b/dhall/src/syntax/text/dhall.pest.visibility
diff --git a/dhall/src/syntax/text/parser.rs b/dhall/src/syntax/text/parser.rs
index ef1471f..2ec63e2 100644
--- a/dhall/src/syntax/text/parser.rs
+++ b/dhall/src/syntax/text/parser.rs
@@ -5,7 +5,6 @@ use std::rc::Rc;
use pest_consume::{match_nodes, Parser};
-use crate::semantics::phase::Normalized;
use crate::syntax;
use crate::syntax::map::{DupTreeMap, DupTreeSet};
use crate::syntax::ExprKind::*;
@@ -14,6 +13,7 @@ use crate::syntax::{
InterpolatedText, InterpolatedTextContents, Label, NaiveDouble, Natural,
Scheme, Span, UnspannedExpr, URL, V,
};
+use crate::Normalized;
// This file consumes the parse tree generated by pest and turns it into
// our own AST. All those custom macros should eventually moved into
@@ -422,7 +422,7 @@ impl DhallParser {
))
}
- fn variable(input: ParseInput) -> ParseResult<V<Label>> {
+ fn variable(input: ParseInput) -> ParseResult<V> {
Ok(match_nodes!(input.into_children();
[label(l), natural_literal(idx)] => V(l, idx),
[label(l)] => V(l, 0),
diff --git a/dhall/src/syntax/text/printer.rs b/dhall/src/syntax/text/printer.rs
index 96f4c2a..06dd70f 100644
--- a/dhall/src/syntax/text/printer.rs
+++ b/dhall/src/syntax/text/printer.rs
@@ -496,7 +496,7 @@ impl Display for Scheme {
}
}
-impl<Label: Display> Display for V<Label> {
+impl Display for V {
fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
let V(x, n) = self;
x.fmt(f)?;
diff --git a/dhall/src/tests.rs b/dhall/src/tests.rs
index f1648cf..8216243 100644
--- a/dhall/src/tests.rs
+++ b/dhall/src/tests.rs
@@ -48,7 +48,7 @@ use std::io::{Read, Write};
use std::path::PathBuf;
use crate::error::{Error, Result};
-use crate::semantics::phase::Parsed;
+use crate::Parsed;
#[allow(dead_code)]
#[derive(Clone)]
@@ -165,20 +165,17 @@ pub fn run_test(test: Test<'_>) -> Result<()> {
assert_eq_display!(ty, expected);
}
TypeInferenceFailure(file_path) => {
- let mut res =
- parse_file_str(&file_path)?.skip_resolve()?.typecheck();
+ let res = parse_file_str(&file_path)?.skip_resolve()?.typecheck();
if let Ok(e) = &res {
// If e did typecheck, check that get_type fails
- res = e.get_type();
+ e.get_type().unwrap_err();
}
- res.unwrap_err();
}
// Checks the output of the type error against a text file. If the text file doesn't exist,
// we instead write to it the output we got. This makes it easy to update those files: just
// `rm -r dhall/tests/type-errors` and run the tests again.
TypeError(file_path) => {
- let mut res =
- parse_file_str(&file_path)?.skip_resolve()?.typecheck();
+ let res = parse_file_str(&file_path)?.skip_resolve()?.typecheck();
let file_path = PathBuf::from(file_path);
let error_file_path = file_path
.strip_prefix("../dhall-lang/tests/type-inference/failure/")
@@ -186,11 +183,13 @@ pub fn run_test(test: Test<'_>) -> Result<()> {
let error_file_path =
PathBuf::from("tests/type-errors/").join(error_file_path);
let error_file_path = error_file_path.with_extension("txt");
- if let Ok(e) = &res {
- // If e did typecheck, check that get_type fails
- res = e.get_type();
- }
- let err: Error = res.unwrap_err().into();
+ let err: Error = match res {
+ Ok(e) => {
+ // If e did typecheck, check that get_type fails
+ e.get_type().unwrap_err().into()
+ }
+ Err(e) => e.into(),
+ };
if error_file_path.is_file() {
let expected_msg = std::fs::read_to_string(error_file_path)?;
diff --git a/dhall/tests/type-errors/hurkensParadox.txt b/dhall/tests/type-errors/hurkensParadox.txt
index 870388d..4dfdcf5 100644
--- a/dhall/tests/type-errors/hurkensParadox.txt
+++ b/dhall/tests/type-errors/hurkensParadox.txt
@@ -1,8 +1 @@
-[unknown location] Type error: Wrong type of function argument
-[unknown location] This argument has type Sort
- --> 5:21
- |
-5 | in let pow = λ(X : Kind) → X → Type␊
- | ^--^
- |
- = But the function expected an argument of type Kind
+Type error: Unhandled error: function annot mismatch: (U : Sort) : Kind
diff --git a/dhall/tests/type-errors/mixedUnions.txt b/dhall/tests/type-errors/mixedUnions.txt
index 30fcdf8..fd4de70 100644
--- a/dhall/tests/type-errors/mixedUnions.txt
+++ b/dhall/tests/type-errors/mixedUnions.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidFieldType(Label("Right"), Type)
+Type error: Unhandled error: InvalidFieldType
diff --git a/dhall/tests/type-errors/unit/AnnotationRecordWrongFieldName.txt b/dhall/tests/type-errors/unit/AnnotationRecordWrongFieldName.txt
index e15da48..946b296 100644
--- a/dhall/tests/type-errors/unit/AnnotationRecordWrongFieldName.txt
+++ b/dhall/tests/type-errors/unit/AnnotationRecordWrongFieldName.txt
@@ -1 +1 @@
-Type error: Unhandled error: AnnotMismatch(Value@Unevaled { value: PartialExpr(RecordLit(DupTreeMap { map: {Label("x"): [Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@Unevaled { value: AppliedBuiltin(Natural, []), type: Type } }]}, size: 1 })), type: Value@WHNF { value: RecordType({Label("x"): Value@Unevaled { value: AppliedBuiltin(Natural, []), type: Type }}), type: Type } }, Value@WHNF { value: RecordType({Label("y"): Value@Unevaled { value: AppliedBuiltin(Natural, []), type: Type }}), type: Type })
+Type error: Unhandled error: annot mismatch: ({ x = 1 } : { x : Natural }) : { y : Natural }
diff --git a/dhall/tests/type-errors/unit/AnnotationRecordWrongFieldType.txt b/dhall/tests/type-errors/unit/AnnotationRecordWrongFieldType.txt
index 16b2d83..89817db 100644
--- a/dhall/tests/type-errors/unit/AnnotationRecordWrongFieldType.txt
+++ b/dhall/tests/type-errors/unit/AnnotationRecordWrongFieldType.txt
@@ -1 +1 @@
-Type error: Unhandled error: AnnotMismatch(Value@Unevaled { value: PartialExpr(RecordLit(DupTreeMap { map: {Label("x"): [Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } }]}, size: 1 })), type: Value@WHNF { value: RecordType({Label("x"): Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type }}), type: Type } }, Value@WHNF { value: RecordType({Label("x"): Value@WHNF { value: AppliedBuiltin(Text, []), type: Type }}), type: Type })
+Type error: Unhandled error: annot mismatch: ({ x = 1 } : { x : Natural }) : { x : Text }
diff --git a/dhall/tests/type-errors/unit/AssertAlphaTrap.txt b/dhall/tests/type-errors/unit/AssertAlphaTrap.txt
index 2969c18..87cf48e 100644
--- a/dhall/tests/type-errors/unit/AssertAlphaTrap.txt
+++ b/dhall/tests/type-errors/unit/AssertAlphaTrap.txt
@@ -1,6 +1 @@
- --> 1:47
- |
-1 | assert : (\(_: Bool) -> _) === (\(x: Bool) -> _)␊
- | ^
- |
- = Type error: Unbound variable
+Type error: Unhandled error: unbound variable
diff --git a/dhall/tests/type-errors/unit/AssertDoubleZeros.txt b/dhall/tests/type-errors/unit/AssertDoubleZeros.txt
index d9df5c7..d8627ba 100644
--- a/dhall/tests/type-errors/unit/AssertDoubleZeros.txt
+++ b/dhall/tests/type-errors/unit/AssertDoubleZeros.txt
@@ -1 +1 @@
-Type error: Unhandled error: AssertMismatch(Value@WHNF { value: DoubleLit(NaiveDouble(-0.0)), type: Value@WHNF { value: AppliedBuiltin(Double, []), type: Type } }, Value@WHNF { value: DoubleLit(NaiveDouble(0.0)), type: Value@WHNF { value: AppliedBuiltin(Double, []), type: Type } })
+Type error: Unhandled error: AssertMismatch
diff --git a/dhall/tests/type-errors/unit/AssertTriviallyFalse.txt b/dhall/tests/type-errors/unit/AssertTriviallyFalse.txt
index c7bbf8d..d8627ba 100644
--- a/dhall/tests/type-errors/unit/AssertTriviallyFalse.txt
+++ b/dhall/tests/type-errors/unit/AssertTriviallyFalse.txt
@@ -1 +1 @@
-Type error: Unhandled error: AssertMismatch(Value@WHNF { value: NaturalLit(1), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } }, Value@WHNF { value: NaturalLit(2), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: AssertMismatch
diff --git a/dhall/tests/type-errors/unit/EquivalenceNotSameType.txt b/dhall/tests/type-errors/unit/EquivalenceNotSameType.txt
index 4dbe2ad..89749e9 100644
--- a/dhall/tests/type-errors/unit/EquivalenceNotSameType.txt
+++ b/dhall/tests/type-errors/unit/EquivalenceNotSameType.txt
@@ -1 +1 @@
-Type error: Unhandled error: EquivalenceTypeMismatch(Value@Unevaled { value: PartialExpr(BoolLit(false)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } }, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: EquivalenceTypeMismatch
diff --git a/dhall/tests/type-errors/unit/EquivalenceNotTerms.txt b/dhall/tests/type-errors/unit/EquivalenceNotTerms.txt
index dbce067..de11e28 100644
--- a/dhall/tests/type-errors/unit/EquivalenceNotTerms.txt
+++ b/dhall/tests/type-errors/unit/EquivalenceNotTerms.txt
@@ -1 +1 @@
-Type error: Unhandled error: EquivalenceArgumentMustBeTerm(true, Value@Unevaled { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: EquivalenceArgumentsMustBeTerms
diff --git a/dhall/tests/type-errors/unit/FunctionApplicationArgumentNotMatch.txt b/dhall/tests/type-errors/unit/FunctionApplicationArgumentNotMatch.txt
index 3bb1492..8d101c3 100644
--- a/dhall/tests/type-errors/unit/FunctionApplicationArgumentNotMatch.txt
+++ b/dhall/tests/type-errors/unit/FunctionApplicationArgumentNotMatch.txt
@@ -1,13 +1 @@
-[unknown location] Type error: Wrong type of function argument
- --> 1:22
- |
-1 | (λ(_ : Natural) → _) True␊
- | ^--^
- |
- = This argument has type Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type }
- --> 1:8
- |
-1 | (λ(_ : Natural) → _) True␊
- | ^-----^
- |
- = But the function expected an argument of type Value@NF { value: AppliedBuiltin(Natural, []), type: Type }
+Type error: Unhandled error: function annot mismatch: (True : Bool) : Natural
diff --git a/dhall/tests/type-errors/unit/FunctionApplicationIsNotFunction.txt b/dhall/tests/type-errors/unit/FunctionApplicationIsNotFunction.txt
index 062f9de..a72e120 100644
--- a/dhall/tests/type-errors/unit/FunctionApplicationIsNotFunction.txt
+++ b/dhall/tests/type-errors/unit/FunctionApplicationIsNotFunction.txt
@@ -1,6 +1 @@
- --> 1:1
- |
-1 | True True␊
- | ^--^
- |
- = Type error: Not a function
+Type error: Unhandled error: apply to not Pi
diff --git a/dhall/tests/type-errors/unit/FunctionArgumentTypeNotAType.txt b/dhall/tests/type-errors/unit/FunctionArgumentTypeNotAType.txt
index 9e43c33..a13fb3a 100644
--- a/dhall/tests/type-errors/unit/FunctionArgumentTypeNotAType.txt
+++ b/dhall/tests/type-errors/unit/FunctionArgumentTypeNotAType.txt
@@ -1,6 +1 @@
- --> 1:7
- |
-1 | λ(_ : 1) → _␊
- | ^
- |
- = Type error: Invalid function input
+[unknown location] Type error: Invalid function input
diff --git a/dhall/tests/type-errors/unit/FunctionTypeArgumentTypeNotAType.txt b/dhall/tests/type-errors/unit/FunctionTypeArgumentTypeNotAType.txt
index dd2e758..a13fb3a 100644
--- a/dhall/tests/type-errors/unit/FunctionTypeArgumentTypeNotAType.txt
+++ b/dhall/tests/type-errors/unit/FunctionTypeArgumentTypeNotAType.txt
@@ -1,6 +1 @@
- --> 1:1
- |
-1 | 2 → _␊
- | ^
- |
- = Type error: Invalid function input
+[unknown location] Type error: Invalid function input
diff --git a/dhall/tests/type-errors/unit/IfBranchesNotMatch.txt b/dhall/tests/type-errors/unit/IfBranchesNotMatch.txt
index 262e54f..6b1dcdd 100644
--- a/dhall/tests/type-errors/unit/IfBranchesNotMatch.txt
+++ b/dhall/tests/type-errors/unit/IfBranchesNotMatch.txt
@@ -1 +1 @@
-Type error: Unhandled error: IfBranchMismatch(Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } }, Value@Unevaled { value: PartialExpr(TextLit(InterpolatedText { head: "", tail: [] })), type: Value@WHNF { value: AppliedBuiltin(Text, []), type: Type } })
+Type error: Unhandled error: IfBranchMismatch
diff --git a/dhall/tests/type-errors/unit/IfBranchesNotType.txt b/dhall/tests/type-errors/unit/IfBranchesNotType.txt
index 8ef3a40..06039a7 100644
--- a/dhall/tests/type-errors/unit/IfBranchesNotType.txt
+++ b/dhall/tests/type-errors/unit/IfBranchesNotType.txt
@@ -1 +1 @@
-Type error: Unhandled error: IfBranchMustBeTerm(true, Type)
+Type error: Unhandled error: IfBranchMustBeTerm
diff --git a/dhall/tests/type-errors/unit/IfNotBool.txt b/dhall/tests/type-errors/unit/IfNotBool.txt
index 64c0465..b2d200c 100644
--- a/dhall/tests/type-errors/unit/IfNotBool.txt
+++ b/dhall/tests/type-errors/unit/IfNotBool.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidPredicate(Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: InvalidPredicate
diff --git a/dhall/tests/type-errors/unit/LetWithWrongAnnotation.txt b/dhall/tests/type-errors/unit/LetWithWrongAnnotation.txt
index 0862162..cae4fea 100644
--- a/dhall/tests/type-errors/unit/LetWithWrongAnnotation.txt
+++ b/dhall/tests/type-errors/unit/LetWithWrongAnnotation.txt
@@ -1 +1 @@
-Type error: Unhandled error: AnnotMismatch(Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } }, Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type })
+Type error: Unhandled error: annot mismatch: (True : Bool) : Natural
diff --git a/dhall/tests/type-errors/unit/ListLiteralEmptyNotType.txt b/dhall/tests/type-errors/unit/ListLiteralEmptyNotType.txt
index e075521..070e461 100644
--- a/dhall/tests/type-errors/unit/ListLiteralEmptyNotType.txt
+++ b/dhall/tests/type-errors/unit/ListLiteralEmptyNotType.txt
@@ -1,13 +1 @@
- --> 1:6
- |
-1 | [] : List Type␊
- | ^--^
- |
- = Type error: Wrong type of function argument
- --> 1:11
- |
-1 | [] : List Type␊
- | ^--^
- |
- = This argument has type Kind
-[unknown location] But the function expected an argument of type Type
+Type error: Unhandled error: function annot mismatch: (Type : Kind) : Type
diff --git a/dhall/tests/type-errors/unit/ListLiteralNotType.txt b/dhall/tests/type-errors/unit/ListLiteralNotType.txt
index 99b95a3..3937453 100644
--- a/dhall/tests/type-errors/unit/ListLiteralNotType.txt
+++ b/dhall/tests/type-errors/unit/ListLiteralNotType.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidListType(Type)
+Type error: Unhandled error: InvalidListType
diff --git a/dhall/tests/type-errors/unit/ListLiteralTypesNotMatch.txt b/dhall/tests/type-errors/unit/ListLiteralTypesNotMatch.txt
index 7916dbb..a64cf67 100644
--- a/dhall/tests/type-errors/unit/ListLiteralTypesNotMatch.txt
+++ b/dhall/tests/type-errors/unit/ListLiteralTypesNotMatch.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidListElement(1, Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type }, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: InvalidListElement
diff --git a/dhall/tests/type-errors/unit/MergeAlternativeHasNoHandler.txt b/dhall/tests/type-errors/unit/MergeAlternativeHasNoHandler.txt
index d4e9024..711d77d 100644
--- a/dhall/tests/type-errors/unit/MergeAlternativeHasNoHandler.txt
+++ b/dhall/tests/type-errors/unit/MergeAlternativeHasNoHandler.txt
@@ -1 +1 @@
-Type error: Unhandled error: MergeVariantMissingHandler(Label("x"))
+Type error: Unhandled error: MergeVariantMissingHandler
diff --git a/dhall/tests/type-errors/unit/MergeAnnotationNotType.txt b/dhall/tests/type-errors/unit/MergeAnnotationNotType.txt
index 7da5cb9..4c72653 100644
--- a/dhall/tests/type-errors/unit/MergeAnnotationNotType.txt
+++ b/dhall/tests/type-errors/unit/MergeAnnotationNotType.txt
@@ -1 +1 @@
-Type error: Unhandled error: Merge2ArgMustBeUnionOrOptional(Value@Unevaled { value: UnionType({}), type: Type })
+Type error: Unhandled error: Merge2ArgMustBeUnionOrOptional
diff --git a/dhall/tests/type-errors/unit/MergeEmptyWithoutAnnotation.txt b/dhall/tests/type-errors/unit/MergeEmptyWithoutAnnotation.txt
index 7da5cb9..4c72653 100644
--- a/dhall/tests/type-errors/unit/MergeEmptyWithoutAnnotation.txt
+++ b/dhall/tests/type-errors/unit/MergeEmptyWithoutAnnotation.txt
@@ -1 +1 @@
-Type error: Unhandled error: Merge2ArgMustBeUnionOrOptional(Value@Unevaled { value: UnionType({}), type: Type })
+Type error: Unhandled error: Merge2ArgMustBeUnionOrOptional
diff --git a/dhall/tests/type-errors/unit/MergeHandlerFreeVar.txt b/dhall/tests/type-errors/unit/MergeHandlerFreeVar.txt
deleted file mode 100644
index de9e256..0000000
--- a/dhall/tests/type-errors/unit/MergeHandlerFreeVar.txt
+++ /dev/null
@@ -1 +0,0 @@
-Type error: Unhandled error: MergeHandlerReturnTypeMustNotBeDependent
diff --git a/dhall/tests/type-errors/unit/MergeHandlerNotFunction.txt b/dhall/tests/type-errors/unit/MergeHandlerNotFunction.txt
index c5ed223..f1cdf92 100644
--- a/dhall/tests/type-errors/unit/MergeHandlerNotFunction.txt
+++ b/dhall/tests/type-errors/unit/MergeHandlerNotFunction.txt
@@ -1 +1 @@
-[unknown location] Type error: Not a function
+Type error: Unhandled error: NotAFunction
diff --git a/dhall/tests/type-errors/unit/MergeHandlerNotInUnion.txt b/dhall/tests/type-errors/unit/MergeHandlerNotInUnion.txt
index 7da5cb9..4c72653 100644
--- a/dhall/tests/type-errors/unit/MergeHandlerNotInUnion.txt
+++ b/dhall/tests/type-errors/unit/MergeHandlerNotInUnion.txt
@@ -1 +1 @@
-Type error: Unhandled error: Merge2ArgMustBeUnionOrOptional(Value@Unevaled { value: UnionType({}), type: Type })
+Type error: Unhandled error: Merge2ArgMustBeUnionOrOptional
diff --git a/dhall/tests/type-errors/unit/MergeHandlerNotMatchAlternativeType.txt b/dhall/tests/type-errors/unit/MergeHandlerNotMatchAlternativeType.txt
index ae36eef..8b729a4 100644
--- a/dhall/tests/type-errors/unit/MergeHandlerNotMatchAlternativeType.txt
+++ b/dhall/tests/type-errors/unit/MergeHandlerNotMatchAlternativeType.txt
@@ -1,13 +1 @@
-[unknown location] Type error: Wrong type of function argument
- --> 1:38
- |
-1 | merge { x = λ(_ : Bool) → _ } (< x : Natural >.x 1)␊
- | ^-----^
- |
- = This argument has type Type
- --> 1:19
- |
-1 | merge { x = λ(_ : Bool) → _ } (< x : Natural >.x 1)␊
- | ^--^
- |
- = But the function expected an argument of type Value@NF { value: AppliedBuiltin(Bool, []), type: Type }
+Type error: Unhandled error: MergeHandlerTypeMismatch
diff --git a/dhall/tests/type-errors/unit/MergeLhsNotRecord.txt b/dhall/tests/type-errors/unit/MergeLhsNotRecord.txt
index da600de..d151710 100644
--- a/dhall/tests/type-errors/unit/MergeLhsNotRecord.txt
+++ b/dhall/tests/type-errors/unit/MergeLhsNotRecord.txt
@@ -1 +1 @@
-Type error: Unhandled error: Merge1ArgMustBeRecord(Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: Merge1ArgMustBeRecord
diff --git a/dhall/tests/type-errors/unit/MergeMissingHandler1.txt b/dhall/tests/type-errors/unit/MergeMissingHandler1.txt
index d4e9024..711d77d 100644
--- a/dhall/tests/type-errors/unit/MergeMissingHandler1.txt
+++ b/dhall/tests/type-errors/unit/MergeMissingHandler1.txt
@@ -1 +1 @@
-Type error: Unhandled error: MergeVariantMissingHandler(Label("x"))
+Type error: Unhandled error: MergeVariantMissingHandler
diff --git a/dhall/tests/type-errors/unit/MergeMissingHandler2.txt b/dhall/tests/type-errors/unit/MergeMissingHandler2.txt
index d583de7..711d77d 100644
--- a/dhall/tests/type-errors/unit/MergeMissingHandler2.txt
+++ b/dhall/tests/type-errors/unit/MergeMissingHandler2.txt
@@ -1 +1 @@
-Type error: Unhandled error: MergeVariantMissingHandler(Label("y"))
+Type error: Unhandled error: MergeVariantMissingHandler
diff --git a/dhall/tests/type-errors/unit/MergeRhsNotUnion.txt b/dhall/tests/type-errors/unit/MergeRhsNotUnion.txt
index db93650..4c72653 100644
--- a/dhall/tests/type-errors/unit/MergeRhsNotUnion.txt
+++ b/dhall/tests/type-errors/unit/MergeRhsNotUnion.txt
@@ -1 +1 @@
-Type error: Unhandled error: Merge2ArgMustBeUnionOrOptional(Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: Merge2ArgMustBeUnionOrOptional
diff --git a/dhall/tests/type-errors/unit/MergeUnusedHandler.txt b/dhall/tests/type-errors/unit/MergeUnusedHandler.txt
index b7eefdd..a429b89 100644
--- a/dhall/tests/type-errors/unit/MergeUnusedHandler.txt
+++ b/dhall/tests/type-errors/unit/MergeUnusedHandler.txt
@@ -1 +1 @@
-Type error: Unhandled error: MergeHandlerMissingVariant(Label("y"))
+Type error: Unhandled error: MergeHandlerMissingVariant
diff --git a/dhall/tests/type-errors/unit/NaturalSubtractNotNatural.txt b/dhall/tests/type-errors/unit/NaturalSubtractNotNatural.txt
index 02a9c45..8d101c3 100644
--- a/dhall/tests/type-errors/unit/NaturalSubtractNotNatural.txt
+++ b/dhall/tests/type-errors/unit/NaturalSubtractNotNatural.txt
@@ -1,13 +1 @@
- --> 1:1
- |
-1 | Natural/subtract True True␊
- | ^--------------^
- |
- = Type error: Wrong type of function argument
- --> 1:18
- |
-1 | Natural/subtract True True␊
- | ^--^
- |
- = This argument has type Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type }
-[unknown location] But the function expected an argument of type Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type }
+Type error: Unhandled error: function annot mismatch: (True : Bool) : Natural
diff --git a/dhall/tests/type-errors/unit/OperatorAndNotBool.txt b/dhall/tests/type-errors/unit/OperatorAndNotBool.txt
index a4346f2..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorAndNotBool.txt
+++ b/dhall/tests/type-errors/unit/OperatorAndNotBool.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(BoolAnd, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorEqualNotBool.txt b/dhall/tests/type-errors/unit/OperatorEqualNotBool.txt
index 57f9095..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorEqualNotBool.txt
+++ b/dhall/tests/type-errors/unit/OperatorEqualNotBool.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(BoolEQ, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorListConcatenateLhsNotList.txt b/dhall/tests/type-errors/unit/OperatorListConcatenateLhsNotList.txt
index 2bcb4fc..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorListConcatenateLhsNotList.txt
+++ b/dhall/tests/type-errors/unit/OperatorListConcatenateLhsNotList.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(ListAppend, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorListConcatenateListsNotMatch.txt b/dhall/tests/type-errors/unit/OperatorListConcatenateListsNotMatch.txt
index e314702..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorListConcatenateListsNotMatch.txt
+++ b/dhall/tests/type-errors/unit/OperatorListConcatenateListsNotMatch.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(ListAppend, Value@Unevaled { value: PartialExpr(NEListLit([Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } }])), type: Value@WHNF { value: AppliedBuiltin(List, [Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type }]), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorListConcatenateNotListsButMatch.txt b/dhall/tests/type-errors/unit/OperatorListConcatenateNotListsButMatch.txt
index 2bcb4fc..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorListConcatenateNotListsButMatch.txt
+++ b/dhall/tests/type-errors/unit/OperatorListConcatenateNotListsButMatch.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(ListAppend, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorListConcatenateRhsNotList.txt b/dhall/tests/type-errors/unit/OperatorListConcatenateRhsNotList.txt
index 2bcb4fc..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorListConcatenateRhsNotList.txt
+++ b/dhall/tests/type-errors/unit/OperatorListConcatenateRhsNotList.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(ListAppend, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorNotEqualNotBool.txt b/dhall/tests/type-errors/unit/OperatorNotEqualNotBool.txt
index 32b3549..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorNotEqualNotBool.txt
+++ b/dhall/tests/type-errors/unit/OperatorNotEqualNotBool.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(BoolNE, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorOrNotBool.txt b/dhall/tests/type-errors/unit/OperatorOrNotBool.txt
index f91bd83..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorOrNotBool.txt
+++ b/dhall/tests/type-errors/unit/OperatorOrNotBool.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(BoolOr, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorPlusNotNatural.txt b/dhall/tests/type-errors/unit/OperatorPlusNotNatural.txt
index 9194f3a..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorPlusNotNatural.txt
+++ b/dhall/tests/type-errors/unit/OperatorPlusNotNatural.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(NaturalPlus, Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorTextConcatenateLhsNotText.txt b/dhall/tests/type-errors/unit/OperatorTextConcatenateLhsNotText.txt
index e67e9e5..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorTextConcatenateLhsNotText.txt
+++ b/dhall/tests/type-errors/unit/OperatorTextConcatenateLhsNotText.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(TextAppend, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorTextConcatenateRhsNotText.txt b/dhall/tests/type-errors/unit/OperatorTextConcatenateRhsNotText.txt
index e67e9e5..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorTextConcatenateRhsNotText.txt
+++ b/dhall/tests/type-errors/unit/OperatorTextConcatenateRhsNotText.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(TextAppend, Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OperatorTimesNotNatural.txt b/dhall/tests/type-errors/unit/OperatorTimesNotNatural.txt
index 8146ba9..9f10587 100644
--- a/dhall/tests/type-errors/unit/OperatorTimesNotNatural.txt
+++ b/dhall/tests/type-errors/unit/OperatorTimesNotNatural.txt
@@ -1 +1 @@
-Type error: Unhandled error: BinOpTypeMismatch(NaturalTimes, Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: BinOpTypeMismatch
diff --git a/dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxAbsent.txt b/dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxAbsent.txt
index c319c81..3937453 100644
--- a/dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxAbsent.txt
+++ b/dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxAbsent.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidListType(Value@WHNF { value: AppliedBuiltin(Optional, [Value@Unevaled { value: AppliedBuiltin(Bool, []), type: Type }]), type: Type })
+Type error: Unhandled error: InvalidListType
diff --git a/dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxPresent.txt b/dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxPresent.txt
index 99df27c..91d7fb0 100644
--- a/dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxPresent.txt
+++ b/dhall/tests/type-errors/unit/OptionalDeprecatedSyntaxPresent.txt
@@ -1 +1 @@
-Type error: Unhandled error: AnnotMismatch(Value@Unevaled { value: PartialExpr(NEListLit([Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@Unevaled { value: AppliedBuiltin(Natural, []), type: Type } }])), type: Value@WHNF { value: AppliedBuiltin(List, [Value@Unevaled { value: AppliedBuiltin(Natural, []), type: Type }]), type: Type } }, Value@WHNF { value: AppliedBuiltin(Optional, [Value@Unevaled { value: AppliedBuiltin(Natural, []), type: Type }]), type: Type })
+Type error: Unhandled error: annot mismatch: ([1] : List Natural) : Optional Natural
diff --git a/dhall/tests/type-errors/unit/RecordSelectionEmpty.txt b/dhall/tests/type-errors/unit/RecordSelectionEmpty.txt
index 1770faa..ea48374 100644
--- a/dhall/tests/type-errors/unit/RecordSelectionEmpty.txt
+++ b/dhall/tests/type-errors/unit/RecordSelectionEmpty.txt
@@ -1 +1 @@
-Type error: Unhandled error: MissingRecordField(Label("x"), Value@Unevaled { value: PartialExpr(RecordLit(DupTreeMap { map: {}, size: 0 })), type: Value@WHNF { value: RecordType({}), type: Type } })
+Type error: Unhandled error: MissingRecordField
diff --git a/dhall/tests/type-errors/unit/RecordSelectionNotPresent.txt b/dhall/tests/type-errors/unit/RecordSelectionNotPresent.txt
index 9211e05..ea48374 100644
--- a/dhall/tests/type-errors/unit/RecordSelectionNotPresent.txt
+++ b/dhall/tests/type-errors/unit/RecordSelectionNotPresent.txt
@@ -1 +1 @@
-Type error: Unhandled error: MissingRecordField(Label("x"), Value@Unevaled { value: PartialExpr(RecordLit(DupTreeMap { map: {Label("y"): [Value@Unevaled { value: PartialExpr(RecordLit(DupTreeMap { map: {}, size: 0 })), type: Value@Unevaled { value: RecordType({}), type: Type } }]}, size: 1 })), type: Value@WHNF { value: RecordType({Label("y"): Value@Unevaled { value: RecordType({}), type: Type }}), type: Type } })
+Type error: Unhandled error: MissingRecordField
diff --git a/dhall/tests/type-errors/unit/RecordSelectionNotRecord.txt b/dhall/tests/type-errors/unit/RecordSelectionNotRecord.txt
index 27db6a2..35d604f 100644
--- a/dhall/tests/type-errors/unit/RecordSelectionNotRecord.txt
+++ b/dhall/tests/type-errors/unit/RecordSelectionNotRecord.txt
@@ -1 +1 @@
-Type error: Unhandled error: NotARecord(Label("x"), Value@WHNF { value: BoolLit(true), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: NotARecord
diff --git a/dhall/tests/type-errors/unit/RecordSelectionTypeNotUnionType.txt b/dhall/tests/type-errors/unit/RecordSelectionTypeNotUnionType.txt
index 36c8e28..35d604f 100644
--- a/dhall/tests/type-errors/unit/RecordSelectionTypeNotUnionType.txt
+++ b/dhall/tests/type-errors/unit/RecordSelectionTypeNotUnionType.txt
@@ -1 +1 @@
-Type error: Unhandled error: NotARecord(Label("x"), Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: NotARecord
diff --git a/dhall/tests/type-errors/unit/RecordTypeValueMember.txt b/dhall/tests/type-errors/unit/RecordTypeValueMember.txt
index 72d4316..fd4de70 100644
--- a/dhall/tests/type-errors/unit/RecordTypeValueMember.txt
+++ b/dhall/tests/type-errors/unit/RecordTypeValueMember.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidFieldType(Label("x"), Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: InvalidFieldType
diff --git a/dhall/tests/type-errors/unit/RecursiveRecordMergeLhsNotRecord.txt b/dhall/tests/type-errors/unit/RecursiveRecordMergeLhsNotRecord.txt
index 42cdf65..7fd03d3 100644
--- a/dhall/tests/type-errors/unit/RecursiveRecordMergeLhsNotRecord.txt
+++ b/dhall/tests/type-errors/unit/RecursiveRecordMergeLhsNotRecord.txt
@@ -1 +1 @@
-Type error: Unhandled error: RecordTypeMergeRequiresRecordType(Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: RecordTypeMergeRequiresRecordType
diff --git a/dhall/tests/type-errors/unit/RecursiveRecordMergeOverlapping.txt b/dhall/tests/type-errors/unit/RecursiveRecordMergeOverlapping.txt
index 42cdf65..7fd03d3 100644
--- a/dhall/tests/type-errors/unit/RecursiveRecordMergeOverlapping.txt
+++ b/dhall/tests/type-errors/unit/RecursiveRecordMergeOverlapping.txt
@@ -1 +1 @@
-Type error: Unhandled error: RecordTypeMergeRequiresRecordType(Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: RecordTypeMergeRequiresRecordType
diff --git a/dhall/tests/type-errors/unit/RecursiveRecordMergeRhsNotRecord.txt b/dhall/tests/type-errors/unit/RecursiveRecordMergeRhsNotRecord.txt
index 42cdf65..7fd03d3 100644
--- a/dhall/tests/type-errors/unit/RecursiveRecordMergeRhsNotRecord.txt
+++ b/dhall/tests/type-errors/unit/RecursiveRecordMergeRhsNotRecord.txt
@@ -1 +1 @@
-Type error: Unhandled error: RecordTypeMergeRequiresRecordType(Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: RecordTypeMergeRequiresRecordType
diff --git a/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeLhsNotRecordType.txt b/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeLhsNotRecordType.txt
index 42cdf65..7fd03d3 100644
--- a/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeLhsNotRecordType.txt
+++ b/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeLhsNotRecordType.txt
@@ -1 +1 @@
-Type error: Unhandled error: RecordTypeMergeRequiresRecordType(Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: RecordTypeMergeRequiresRecordType
diff --git a/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeOverlapping.txt b/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeOverlapping.txt
index 42cdf65..7fd03d3 100644
--- a/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeOverlapping.txt
+++ b/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeOverlapping.txt
@@ -1 +1 @@
-Type error: Unhandled error: RecordTypeMergeRequiresRecordType(Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: RecordTypeMergeRequiresRecordType
diff --git a/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeRhsNotRecordType.txt b/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeRhsNotRecordType.txt
index 42cdf65..7fd03d3 100644
--- a/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeRhsNotRecordType.txt
+++ b/dhall/tests/type-errors/unit/RecursiveRecordTypeMergeRhsNotRecordType.txt
@@ -1 +1 @@
-Type error: Unhandled error: RecordTypeMergeRequiresRecordType(Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: RecordTypeMergeRequiresRecordType
diff --git a/dhall/tests/type-errors/unit/RightBiasedRecordMergeLhsNotRecord.txt b/dhall/tests/type-errors/unit/RightBiasedRecordMergeLhsNotRecord.txt
index 9a2913b..42600a4 100644
--- a/dhall/tests/type-errors/unit/RightBiasedRecordMergeLhsNotRecord.txt
+++ b/dhall/tests/type-errors/unit/RightBiasedRecordMergeLhsNotRecord.txt
@@ -1 +1 @@
-Type error: Unhandled error: MustCombineRecord(Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: MustCombineRecord
diff --git a/dhall/tests/type-errors/unit/RightBiasedRecordMergeRhsNotRecord.txt b/dhall/tests/type-errors/unit/RightBiasedRecordMergeRhsNotRecord.txt
index 9a2913b..42600a4 100644
--- a/dhall/tests/type-errors/unit/RightBiasedRecordMergeRhsNotRecord.txt
+++ b/dhall/tests/type-errors/unit/RightBiasedRecordMergeRhsNotRecord.txt
@@ -1 +1 @@
-Type error: Unhandled error: MustCombineRecord(Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: MustCombineRecord
diff --git a/dhall/tests/type-errors/unit/SomeNotType.txt b/dhall/tests/type-errors/unit/SomeNotType.txt
index 43581a0..63fec72 100644
--- a/dhall/tests/type-errors/unit/SomeNotType.txt
+++ b/dhall/tests/type-errors/unit/SomeNotType.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidOptionalType(Type)
+Type error: Unhandled error: InvalidOptionalType
diff --git a/dhall/tests/type-errors/unit/TextLiteralInterpolateNotText.txt b/dhall/tests/type-errors/unit/TextLiteralInterpolateNotText.txt
index ba2aecd..f1a77d9 100644
--- a/dhall/tests/type-errors/unit/TextLiteralInterpolateNotText.txt
+++ b/dhall/tests/type-errors/unit/TextLiteralInterpolateNotText.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidTextInterpolation(Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } })
+Type error: Unhandled error: InvalidTextInterpolation
diff --git a/dhall/tests/type-errors/unit/TypeAnnotationWrong.txt b/dhall/tests/type-errors/unit/TypeAnnotationWrong.txt
index 77ff57f..52fc94d 100644
--- a/dhall/tests/type-errors/unit/TypeAnnotationWrong.txt
+++ b/dhall/tests/type-errors/unit/TypeAnnotationWrong.txt
@@ -1 +1 @@
-Type error: Unhandled error: AnnotMismatch(Value@Unevaled { value: PartialExpr(NaturalLit(1)), type: Value@WHNF { value: AppliedBuiltin(Natural, []), type: Type } }, Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: annot mismatch: (1 : Natural) : Bool
diff --git a/dhall/tests/type-errors/unit/UnionConstructorFieldNotPresent.txt b/dhall/tests/type-errors/unit/UnionConstructorFieldNotPresent.txt
index 7b2e610..f88cb57 100644
--- a/dhall/tests/type-errors/unit/UnionConstructorFieldNotPresent.txt
+++ b/dhall/tests/type-errors/unit/UnionConstructorFieldNotPresent.txt
@@ -1 +1 @@
-Type error: Unhandled error: MissingUnionField(Label("y"), Value@WHNF { value: UnionType({Label("x"): Some(Value@Unevaled { value: AppliedBuiltin(Bool, []), type: Type })}), type: Type })
+Type error: Unhandled error: MissingUnionField
diff --git a/dhall/tests/type-errors/unit/UnionDeprecatedConstructorsKeyword.txt b/dhall/tests/type-errors/unit/UnionDeprecatedConstructorsKeyword.txt
index 9cc0c19..87cf48e 100644
--- a/dhall/tests/type-errors/unit/UnionDeprecatedConstructorsKeyword.txt
+++ b/dhall/tests/type-errors/unit/UnionDeprecatedConstructorsKeyword.txt
@@ -1,6 +1 @@
- --> 1:1
- |
-1 | constructors < Left : Natural | Right : Bool >␊
- | ^----------^
- |
- = Type error: Unbound variable
+Type error: Unhandled error: unbound variable
diff --git a/dhall/tests/type-errors/unit/UnionTypeMixedKinds.txt b/dhall/tests/type-errors/unit/UnionTypeMixedKinds.txt
index 07604ba..fd4de70 100644
--- a/dhall/tests/type-errors/unit/UnionTypeMixedKinds.txt
+++ b/dhall/tests/type-errors/unit/UnionTypeMixedKinds.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidFieldType(Label("y"), Type)
+Type error: Unhandled error: InvalidFieldType
diff --git a/dhall/tests/type-errors/unit/UnionTypeMixedKinds2.txt b/dhall/tests/type-errors/unit/UnionTypeMixedKinds2.txt
index 07604ba..fd4de70 100644
--- a/dhall/tests/type-errors/unit/UnionTypeMixedKinds2.txt
+++ b/dhall/tests/type-errors/unit/UnionTypeMixedKinds2.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidFieldType(Label("y"), Type)
+Type error: Unhandled error: InvalidFieldType
diff --git a/dhall/tests/type-errors/unit/UnionTypeMixedKinds3.txt b/dhall/tests/type-errors/unit/UnionTypeMixedKinds3.txt
index 83fc426..fd4de70 100644
--- a/dhall/tests/type-errors/unit/UnionTypeMixedKinds3.txt
+++ b/dhall/tests/type-errors/unit/UnionTypeMixedKinds3.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidFieldType(Label("y"), Value@Unevaled { value: AppliedBuiltin(Bool, []), type: Type })
+Type error: Unhandled error: InvalidFieldType
diff --git a/dhall/tests/type-errors/unit/UnionTypeNotType.txt b/dhall/tests/type-errors/unit/UnionTypeNotType.txt
index 72d4316..fd4de70 100644
--- a/dhall/tests/type-errors/unit/UnionTypeNotType.txt
+++ b/dhall/tests/type-errors/unit/UnionTypeNotType.txt
@@ -1 +1 @@
-Type error: Unhandled error: InvalidFieldType(Label("x"), Value@Unevaled { value: PartialExpr(BoolLit(true)), type: Value@WHNF { value: AppliedBuiltin(Bool, []), type: Type } })
+Type error: Unhandled error: InvalidFieldType
diff --git a/dhall/tests/type-errors/unit/VariableFree.txt b/dhall/tests/type-errors/unit/VariableFree.txt
index a46aac0..87cf48e 100644
--- a/dhall/tests/type-errors/unit/VariableFree.txt
+++ b/dhall/tests/type-errors/unit/VariableFree.txt
@@ -1,6 +1 @@
- --> 1:1
- |
-1 | x␊
- | ^
- |
- = Type error: Unbound variable
+Type error: Unhandled error: unbound variable