Repository: ergoplatform/sigma-rust (language: rust)

Issue:
Function definition (def) eval and serialization



Discussion / hints:

Fix patch:
diff --git a/.github/workflows/android.yml b/.github/workflows/android.yml
index ddbc74fc7..ce9c5330b 100644
--- a/.github/workflows/android.yml
+++ b/.github/workflows/android.yml
@@ -29,5 +29,6 @@ jobs:
         uses: reactivecircus/android-emulator-runner@v2
         with:
           api-level: 29
+          ndk: 21.3.6528147 
           script: cd ./bindings/ergo-lib-jni && ./gradlew connectedCheck
 
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
index e980650f8..b41513132 100644
--- a/.github/workflows/ci.yml
+++ b/.github/workflows/ci.yml
@@ -94,17 +94,17 @@ jobs:
         uses: actions-rs/tarpaulin@master
         with:
           args: '-v --out Lcov --exclude-files bindings/*'
-      - name: Upload coverage report to Codecov
-        if: matrix.os == 'ubuntu-latest'
-        uses: codecov/codecov-action@v1
-        with:
-          fail_ci_if_error: true
-      # - name: Push code coverage results to coveralls.io
-      #   if: matrix.os == 'ubuntu-latest' && github.event_name == 'pull_request'
-      #   uses: coverallsapp/github-action@master
+      # - name: Upload coverage report to Codecov
+      #   if: matrix.os == 'ubuntu-latest'
+      #   uses: codecov/codecov-action@v1
       #   with:
-      #     github-token: ${{ secrets.GITHUB_TOKEN }}
-      #     path-to-lcov: ./lcov.info
+      #     fail_ci_if_error: true
+      - name: Push code coverage results to coveralls.io
+        if: matrix.os == 'ubuntu-latest' 
+        uses: coverallsapp/github-action@master
+        with:
+          github-token: ${{ secrets.GITHUB_TOKEN }}
+          path-to-lcov: ./lcov.info
         
   doc-links:
     name: Intra-documentation links
diff --git a/README.md b/README.md
index 30d8ae908..0573a864d 100644
--- a/README.md
+++ b/README.md
@@ -1,4 +1,4 @@
-[![codecov](https://codecov.io/gh/ergoplatform/sigma-rust/branch/develop/graph/badge.svg?token=W1ITCGM9ZP)](https://codecov.io/gh/ergoplatform/sigma-rust)
+[![Coverage Status](https://coveralls.io/repos/github/ergoplatform/sigma-rust/badge.svg)](https://coveralls.io/github/ergoplatform/sigma-rust)
 
 Rust implementation of [ErgoScript](https://github.com/ScorexFoundation/sigmastate-interpreter) cryptocurrency scripting language. 
 
diff --git a/bindings/ergo-lib-jni/build.gradle b/bindings/ergo-lib-jni/build.gradle
index 60d759868..fde3de188 100644
--- a/bindings/ergo-lib-jni/build.gradle
+++ b/bindings/ergo-lib-jni/build.gradle
@@ -78,7 +78,7 @@ android {
             proguardFiles getDefaultProguardFile("proguard-android-optimize.txt"), "proguard-rules.pro"
         }
     }
-    
+
     compileOptions {
         sourceCompatibility JavaVersion.VERSION_1_8
         targetCompatibility JavaVersion.VERSION_1_8
diff --git a/ergo-lib/CHANGELOG.md b/ergo-lib/CHANGELOG.md
index 2f3ed4799..bf28bd6b4 100644
--- a/ergo-lib/CHANGELOG.md
+++ b/ergo-lib/CHANGELOG.md
@@ -6,6 +6,10 @@ and this project adheres to [Semantic Versioning](http://semver.org/).
 
 <!-- next-header -->
 ## [Unreleased] - ReleaseDate
+
+### Added 
+- `BlockValue`, `ValDef`, `ValUse`, `FuncValue`, `Apply` IR nodes evaluation and serialization [#171](https://github.com/ergoplatform/sigma-rust/pull/171);
+
 ## [0.4.3] - 2021-01-15
 
 ### Added 
diff --git a/ergo-lib/README.md b/ergo-lib/README.md
index c7405e507..afe43ea1d 100644
--- a/ergo-lib/README.md
+++ b/ergo-lib/README.md
@@ -15,6 +15,7 @@
 - `Context` properties (`dataInputs`);
 - Value types with serialization for most of them(types and values);
 - `EQ`(`==`), `NEQ`(`!=`);
+- `BlockValue`, `ValDef`, `ValUse`, `FuncValue`, `Apply`;
 
 ## Usage 
 ## Crate features
diff --git a/ergo-lib/src/ast.rs b/ergo-lib/src/ast.rs
index 8950d3aff..8d85f22dd 100644
--- a/ergo-lib/src/ast.rs
+++ b/ergo-lib/src/ast.rs
@@ -1,14 +1,19 @@
 //! AST for ErgoTree
 
+pub(crate) mod apply;
 pub(crate) mod bin_op;
+pub(crate) mod block;
 pub(crate) mod coll_fold;
 pub(crate) mod expr;
 pub(crate) mod extract_reg_as;
+pub(crate) mod func_value;
 pub(crate) mod global_vars;
 pub(crate) mod method_call;
 pub(crate) mod option_get;
 pub(crate) mod predef_func;
 pub(crate) mod property_call;
+pub(crate) mod val_def;
+pub(crate) mod val_use;
 
 pub mod constant;
 pub mod value;
diff --git a/ergo-lib/src/ast/apply.rs b/ergo-lib/src/ast/apply.rs
new file mode 100644
index 000000000..8a5e6fd5d
--- /dev/null
+++ b/ergo-lib/src/ast/apply.rs
@@ -0,0 +1,180 @@
+use std::io;
+
+use crate::eval::env::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
+use crate::serialization::sigma_byte_reader::SigmaByteRead;
+use crate::serialization::sigma_byte_writer::SigmaByteWrite;
+use crate::serialization::SerializationError;
+use crate::serialization::SigmaSerializable;
+use crate::types::stype::SType;
+
+use super::expr::Expr;
+use super::expr::InvalidArgumentError;
+use super::val_def::ValId;
+use super::value::Value;
+
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct Apply {
+    func: Expr,
+    args: Vec<Expr>,
+}
+
+impl Apply {
+    pub fn new(func: Expr, args: Vec<Expr>) -> Result<Self, InvalidArgumentError> {
+        let func = match func.tpe() {
+            SType::SColl(_) => Ok(func),
+            SType::SFunc(sfunc) => {
+                let arg_types: Vec<SType> = args.iter().map(|a| a.tpe()).collect();
+                if sfunc.t_dom != arg_types {
+                    Err(InvalidArgumentError(format!(
+                        "Expected args: {0:?}, got: {1:?}",
+                        sfunc.t_dom, args
+                    )))
+                } else {
+                    Ok(func)
+                }
+            }
+            _ => Err(InvalidArgumentError(format!(
+                "unexpected Apply::func: {0:?}",
+                func.tpe(),
+            ))),
+        }?;
+        Ok(Apply { func, args })
+    }
+
+    pub fn tpe(&self) -> SType {
+        match self.func.tpe() {
+            SType::SColl(_) => todo!(),
+            SType::SFunc(f) => f.t_range,
+            _ => panic!("unexpected Apply::func: {0:?}", self.func.tpe()),
+        }
+    }
+}
+
+impl Evaluable for Apply {
+    fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        let func_v = self.func.eval(env, ctx)?;
+        let args_v_res: Result<Vec<Value>, EvalError> =
+            self.args.iter().map(|arg| arg.eval(env, ctx)).collect();
+        let args_v = args_v_res?;
+        match func_v {
+            Value::FuncValue(fv) => {
+                let arg_ids: Vec<ValId> = fv.args().iter().map(|a| a.idx).collect();
+                let mut cur_env = env.clone();
+                arg_ids.iter().zip(args_v).for_each(|(idx, arg_v)| {
+                    cur_env.insert(*idx, arg_v);
+                });
+                fv.body().eval(&cur_env, ctx)
+            }
+            _ => Err(EvalError::UnexpectedValue(format!(
+                "expected func_v to be Value::FuncValue got: {0:?}",
+                func_v
+            ))),
+        }
+    }
+}
+
+impl SigmaSerializable for Apply {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), io::Error> {
+        self.func.sigma_serialize(w)?;
+        self.args.sigma_serialize(w)
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let func = Expr::sigma_parse(r)?;
+        let args = Vec::<Expr>::sigma_parse(r)?;
+        Ok(Apply::new(func, args)?)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use std::rc::Rc;
+
+    use crate::ast::bin_op::BinOp;
+    use crate::ast::bin_op::LogicOp;
+    use crate::ast::block::BlockValue;
+    use crate::ast::func_value::*;
+    use crate::ast::val_def::ValDef;
+    use crate::ast::val_use::ValUse;
+    use crate::eval::context::Context;
+    use crate::eval::tests::eval_out;
+    use crate::serialization::sigma_serialize_roundtrip;
+    use crate::test_util::force_any_val;
+    use crate::types::stype::SType;
+
+    use super::*;
+
+    use proptest::collection::vec;
+    use proptest::prelude::*;
+
+    impl Arbitrary for Apply {
+        type Strategy = BoxedStrategy<Self>;
+        type Parameters = ();
+
+        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
+            (any::<Expr>(), vec(any::<Expr>(), 1..10))
+                .prop_map(|(body, args)| {
+                    let func = Box::new(FuncValue::new(
+                        args.iter()
+                            .enumerate()
+                            .map(|(idx, arg)| FuncArg {
+                                idx: (idx as u32).into(),
+                                tpe: arg.tpe(),
+                            })
+                            .collect(),
+                        body,
+                    ))
+                    .into();
+                    Self { func, args }
+                })
+                .boxed()
+        }
+    }
+
+    proptest! {
+
+        #[test]
+        fn ser_roundtrip(v in any::<Apply>()) {
+            prop_assert_eq![sigma_serialize_roundtrip(&v), v];
+        }
+    }
+
+    #[test]
+    fn eval_user_defined_func_call() {
+        let arg = Expr::Const(Box::new(1i32.into()));
+        let bin_op = Expr::BinOp(Box::new(BinOp {
+            kind: LogicOp::Eq.into(),
+            left: Expr::ValUse(Box::new(ValUse {
+                val_id: 1.into(),
+                tpe: SType::SInt,
+            })),
+            right: Expr::ValUse(Box::new(ValUse {
+                val_id: 2.into(),
+                tpe: SType::SInt,
+            })),
+        }));
+        let body = Expr::BlockValue(Box::new(BlockValue {
+            items: vec![ValDef {
+                id: 2.into(),
+                rhs: Expr::Const(Box::new(1i32.into())),
+            }],
+            result: bin_op,
+        }));
+        let apply: Expr = Box::new(Apply {
+            func: Expr::FuncValue(Box::new(FuncValue::new(
+                vec![FuncArg {
+                    idx: 1.into(),
+                    tpe: SType::SInt,
+                }],
+                body,
+            ))),
+            args: vec![arg],
+        })
+        .into();
+        let ctx = Rc::new(force_any_val::<Context>());
+        assert!(eval_out::<bool>(&apply, ctx));
+    }
+}
diff --git a/ergo-lib/src/ast/bin_op.rs b/ergo-lib/src/ast/bin_op.rs
index 15c14b68e..2d3568bd5 100644
--- a/ergo-lib/src/ast/bin_op.rs
+++ b/ergo-lib/src/ast/bin_op.rs
@@ -3,11 +3,12 @@
 use eval::costs::Costs;
 
 use crate::eval;
-use crate::eval::Env;
+use crate::eval::env::Env;
 use crate::eval::EvalContext;
 use crate::eval::EvalError;
 use crate::eval::Evaluable;
 use crate::serialization::op_code::OpCode;
+use crate::types::stype::SType;
 
 use super::expr::Expr;
 use super::value::Value;
@@ -79,6 +80,12 @@ impl BinOp {
     pub fn op_code(&self) -> OpCode {
         self.kind.into()
     }
+
+    pub fn tpe(&self) -> SType {
+        match self.kind {
+            BinOpKind::Logic(_) => SType::SBoolean,
+        }
+    }
 }
 
 impl Evaluable for BinOp {
diff --git a/ergo-lib/src/ast/block.rs b/ergo-lib/src/ast/block.rs
new file mode 100644
index 000000000..3831b96b5
--- /dev/null
+++ b/ergo-lib/src/ast/block.rs
@@ -0,0 +1,94 @@
+use std::io;
+
+use crate::eval::env::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
+use crate::serialization::op_code::OpCode;
+use crate::serialization::sigma_byte_reader::SigmaByteRead;
+use crate::serialization::sigma_byte_writer::SigmaByteWrite;
+use crate::serialization::SerializationError;
+use crate::serialization::SigmaSerializable;
+use crate::types::stype::SType;
+
+use super::expr::Expr;
+use super::val_def::ValDef;
+use super::value::Value;
+
+/** The order of ValDefs in the block is used to assign ids to ValUse(id) nodes
+ * For all i: items(i).id == {number of ValDefs preceded in a graph} with respect to topological order.
+ * Specific topological order doesn't really matter, what is important is to preserve semantic linkage
+ * between ValUse(id) and ValDef with the corresponding id.
+ * This convention allow to valid serializing ids because we always serializing and deserializing
+ * in a fixed well defined order.
+ */
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct BlockValue {
+    pub items: Vec<ValDef>,
+    pub result: Expr,
+}
+
+impl BlockValue {
+    pub fn tpe(&self) -> SType {
+        self.result.tpe()
+    }
+
+    pub fn op_code(&self) -> OpCode {
+        OpCode::BLOCK_VALUE
+    }
+}
+
+impl Evaluable for BlockValue {
+    fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        let mut cur_env = env.clone();
+        for i in self.items.iter() {
+            let v: Value = i.rhs.eval(&cur_env, ctx)?;
+            cur_env.insert(i.id, v);
+        }
+        self.result.eval(&cur_env, ctx)
+    }
+}
+
+impl SigmaSerializable for BlockValue {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), io::Error> {
+        self.items.sigma_serialize(w)?;
+        self.result.sigma_serialize(w)
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let items = Vec::<ValDef>::sigma_parse(r)?;
+        let result = Expr::sigma_parse(r)?;
+        Ok(BlockValue { items, result })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::ast::block::BlockValue;
+    use crate::ast::expr::Expr;
+    use crate::ast::val_def::ValDef;
+    use crate::serialization::sigma_serialize_roundtrip;
+
+    use proptest::collection::vec;
+    use proptest::prelude::*;
+
+    impl Arbitrary for BlockValue {
+        type Strategy = BoxedStrategy<Self>;
+        type Parameters = ();
+
+        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
+            (any::<Expr>(), vec(any::<ValDef>(), 0..10))
+                .prop_map(|(result, items)| Self { items, result })
+                .boxed()
+        }
+    }
+
+    proptest! {
+
+        #[test]
+        fn ser_roundtrip(block in any::<BlockValue>()) {
+            let e = Expr::BlockValue(block.into());
+            prop_assert_eq![sigma_serialize_roundtrip(&e), e];
+        }
+    }
+}
diff --git a/ergo-lib/src/ast/coll_fold.rs b/ergo-lib/src/ast/coll_fold.rs
index d37c54073..699c0fa25 100644
--- a/ergo-lib/src/ast/coll_fold.rs
+++ b/ergo-lib/src/ast/coll_fold.rs
@@ -1,9 +1,19 @@
+use crate::eval::env::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
 use crate::serialization::sigma_byte_reader::SigmaByteRead;
 use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SerializationError;
 use crate::serialization::SigmaSerializable;
+use crate::types::stype::SType;
+use crate::types::stype::TupleItems;
 
 use super::expr::Expr;
+use super::value::Coll::NonPrimitive;
+use super::value::Coll::Primitive;
+use super::value::CollPrim;
+use super::value::Value;
 
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub struct Fold {
@@ -15,6 +25,12 @@ pub struct Fold {
     fold_op: Expr,
 }
 
+impl Fold {
+    pub fn tpe(&self) -> SType {
+        self.zero.tpe()
+    }
+}
+
 impl SigmaSerializable for Fold {
     fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), std::io::Error> {
         self.input.sigma_serialize(w)?;
@@ -33,3 +49,44 @@ impl SigmaSerializable for Fold {
         })
     }
 }
+
+impl Evaluable for Fold {
+    fn eval(&self, env: &Env, ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        let input_v = self.input.eval(env, ctx)?;
+        let zero_v = self.zero.eval(env, ctx)?;
+        let fold_op_v = self.fold_op.eval(env, ctx)?;
+        let input_v_clone = input_v.clone();
+        let mut fold_op_call = |arg: Value| match &fold_op_v {
+            Value::FuncValue(func_value) => {
+                let func_arg = func_value
+                    .args()
+                    .first()
+                    .ok_or_else(|| EvalError::NotFound("empty argument for fold op".to_string()))?;
+                let env1 = env.clone().extend(func_arg.idx, arg);
+                func_value.body().eval(&env1, ctx)
+            }
+            _ => Err(EvalError::UnexpectedValue(format!(
+                "expected fold_op to be Value::FuncValue got: {0:?}",
+                input_v_clone
+            ))),
+        };
+        match input_v {
+            Value::Coll(coll) => match *coll {
+                Primitive(CollPrim::CollByte(coll_byte)) => {
+                    coll_byte.iter().try_fold(zero_v, |acc, byte| {
+                        let tup_arg = Value::Tup(TupleItems::pair(acc, Value::Byte(*byte)));
+                        fold_op_call(tup_arg)
+                    })
+                }
+                NonPrimitive { elem_tpe: _, v } => v.iter().try_fold(zero_v, |acc, item| {
+                    let tup_arg = Value::Tup(TupleItems::pair(acc, item.clone()));
+                    fold_op_call(tup_arg)
+                }),
+            },
+            _ => Err(EvalError::UnexpectedValue(format!(
+                "expected Fold input to be Value::Coll, got: {0:?}",
+                input_v
+            ))),
+        }
+    }
+}
diff --git a/ergo-lib/src/ast/expr.rs b/ergo-lib/src/ast/expr.rs
index 3db61961e..6fe7e5479 100644
--- a/ergo-lib/src/ast/expr.rs
+++ b/ergo-lib/src/ast/expr.rs
@@ -1,18 +1,22 @@
-use core::fmt;
-
 use crate::serialization::op_code::OpCode;
+use crate::types::scontext::SContext;
 use crate::types::stype::SType;
 
+use super::apply::Apply;
 use super::bin_op::BinOp;
+use super::block::BlockValue;
 use super::coll_fold::Fold;
 use super::constant::Constant;
 use super::constant::ConstantPlaceholder;
 use super::extract_reg_as::ExtractRegisterAs;
+use super::func_value::FuncValue;
 use super::global_vars::GlobalVars;
 use super::method_call::MethodCall;
 use super::option_get::OptionGet;
 use super::predef_func::PredefFunc;
 use super::property_call::PropertyCall;
+use super::val_def::ValDef;
+use super::val_use::ValUse;
 
 extern crate derive_more;
 use derive_more::From;
@@ -26,22 +30,32 @@ pub enum Expr {
     ConstPlaceholder(Box<ConstantPlaceholder>),
     /// Predefined functions (global)
     PredefFunc(Box<PredefFunc>),
-    /// Collection fold op
-    Fold(Box<Fold>),
     Context,
     // Global(Global),
     /// Predefined global variables
     GlobalVars(Box<GlobalVars>),
+    /// Function definition
+    FuncValue(Box<FuncValue>),
+    /// Function application
+    Apply(Box<Apply>),
     /// Method call
     MethodCall(Box<MethodCall>),
     /// Property call
     ProperyCall(Box<PropertyCall>),
+    /// Block (statements, followed by an expression)
+    BlockValue(Box<BlockValue>),
+    /// let-bound expression
+    ValDef(Box<ValDef>),
+    /// Reference to ValDef
+    ValUse(Box<ValUse>),
     /// Binary operation
     BinOp(Box<BinOp>),
     /// Option get method
     OptionGet(Box<OptionGet>),
     /// Extract register's value (box.RX properties)
     ExtractRegisterAs(Box<ExtractRegisterAs>),
+    /// Collection fold op
+    Fold(Box<Fold>),
 }
 
 impl Expr {
@@ -57,24 +71,40 @@ impl Expr {
             Expr::OptionGet(v) => v.op_code(),
             Expr::ExtractRegisterAs(v) => v.op_code(),
             Expr::BinOp(op) => op.op_code(),
-            _ => todo!("{0:?}", self),
+            Expr::BlockValue(op) => op.op_code(),
+            Expr::ValUse(op) => op.op_code(),
+            Expr::FuncValue(op) => op.op_code(),
+            Expr::ValDef(op) => op.op_code(),
+            _ => todo!("not yet implemented opcode for {0:?}", self),
         }
     }
 
     /// Type of the expression
-    pub fn tpe(&self) -> &SType {
+    pub fn tpe(&self) -> SType {
         match self {
-            Expr::Const(c) => &c.tpe,
-            _ => todo!(),
+            Expr::Const(v) => v.tpe.clone(),
+            Expr::ConstPlaceholder(v) => v.tpe.clone(),
+            Expr::PredefFunc(v) => v.tpe(),
+            Expr::Context => SType::SContext(SContext()),
+            Expr::GlobalVars(v) => v.tpe(),
+            Expr::FuncValue(v) => v.tpe(),
+            Expr::Apply(v) => v.tpe(),
+            Expr::MethodCall(v) => v.tpe(),
+            Expr::ProperyCall(v) => v.tpe(),
+            Expr::BlockValue(v) => v.tpe(),
+            Expr::ValDef(v) => v.tpe(),
+            Expr::ValUse(v) => v.tpe.clone(),
+            Expr::BinOp(v) => v.tpe(),
+            Expr::OptionGet(v) => v.tpe(),
+            Expr::ExtractRegisterAs(v) => v.tpe.clone(),
+            Expr::Fold(v) => v.tpe(),
         }
     }
 }
 
-impl fmt::Display for Expr {
-    fn fmt(&self, _: &mut fmt::Formatter<'_>) -> fmt::Result {
-        todo!()
-    }
-}
+/// Unexpected argument on node construction (i.e non-Option input in OptionGet)
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct InvalidArgumentError(pub String);
 
 #[cfg(test)]
 pub mod tests {
diff --git a/ergo-lib/src/ast/extract_reg_as.rs b/ergo-lib/src/ast/extract_reg_as.rs
index 8afbac31b..aa7ea9178 100644
--- a/ergo-lib/src/ast/extract_reg_as.rs
+++ b/ergo-lib/src/ast/extract_reg_as.rs
@@ -1,6 +1,6 @@
 use crate::chain::ergo_box::ErgoBox;
 use crate::chain::ergo_box::RegisterId;
-use crate::eval::Env;
+use crate::eval::env::Env;
 use crate::eval::EvalContext;
 use crate::eval::EvalError;
 use crate::eval::Evaluable;
@@ -83,10 +83,7 @@ mod tests {
             tpe: SType::SOption(SType::SLong.into()),
         })
         .into();
-        let option_get_expr: Expr = Box::new(OptionGet {
-            input: get_reg_expr,
-        })
-        .into();
+        let option_get_expr: Expr = Box::new(OptionGet::new(get_reg_expr).unwrap()).into();
         let ctx = Rc::new(force_any_val::<Context>());
         let v = eval_out::<i64>(&option_get_expr, ctx.clone());
         assert_eq!(v, ctx.self_box.value.as_i64());
diff --git a/ergo-lib/src/ast/func_value.rs b/ergo-lib/src/ast/func_value.rs
new file mode 100644
index 000000000..a466e636f
--- /dev/null
+++ b/ergo-lib/src/ast/func_value.rs
@@ -0,0 +1,128 @@
+use std::io;
+
+use crate::eval::env::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
+use crate::serialization::op_code::OpCode;
+use crate::serialization::sigma_byte_reader::SigmaByteRead;
+use crate::serialization::sigma_byte_writer::SigmaByteWrite;
+use crate::serialization::SerializationError;
+use crate::serialization::SigmaSerializable;
+use crate::types::sfunc::SFunc;
+use crate::types::stype::SType;
+
+use super::expr::Expr;
+use super::val_def::ValId;
+use super::value::Value;
+
+#[cfg(test)]
+use proptest_derive::Arbitrary;
+
+#[derive(PartialEq, Eq, Debug, Clone)]
+#[cfg_attr(test, derive(Arbitrary))]
+pub struct FuncArg {
+    pub idx: ValId,
+    pub tpe: SType,
+}
+
+impl SigmaSerializable for FuncArg {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), io::Error> {
+        self.idx.sigma_serialize(w)?;
+        self.tpe.sigma_serialize(w)
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let idx = ValId::sigma_parse(r)?;
+        let tpe = SType::sigma_parse(r)?;
+        Ok(FuncArg { idx, tpe })
+    }
+}
+
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct FuncValue {
+    args: Vec<FuncArg>,
+    body: Expr,
+    tpe: SType,
+}
+
+impl FuncValue {
+    pub fn new(args: Vec<FuncArg>, body: Expr) -> Self {
+        let t_dom = args.iter().map(|fa| fa.tpe.clone()).collect();
+        let t_range = body.tpe();
+        let tpe = SType::SFunc(Box::new(SFunc {
+            t_dom,
+            t_range,
+            tpe_params: vec![],
+        }));
+        FuncValue { args, body, tpe }
+    }
+
+    pub fn args(&self) -> &[FuncArg] {
+        self.args.as_ref()
+    }
+
+    pub fn body(&self) -> &Expr {
+        &self.body
+    }
+
+    pub fn tpe(&self) -> SType {
+        self.tpe.clone()
+    }
+
+    pub fn op_code(&self) -> OpCode {
+        OpCode::FUNC_VALUE
+    }
+}
+
+impl Evaluable for FuncValue {
+    fn eval(&self, _env: &Env, _ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        Ok(Value::FuncValue(Box::new(self.clone())))
+    }
+}
+
+impl SigmaSerializable for FuncValue {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), io::Error> {
+        self.args.sigma_serialize(w)?;
+        self.body.sigma_serialize(w)
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let args = Vec::<FuncArg>::sigma_parse(r)?;
+        args.iter()
+            .for_each(|a| r.val_def_type_store().insert(a.idx, a.tpe.clone()));
+        let body = Expr::sigma_parse(r)?;
+        Ok(FuncValue::new(args, body))
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::ast::expr::Expr;
+    use crate::serialization::sigma_serialize_roundtrip;
+
+    use proptest::collection::vec;
+    use proptest::prelude::*;
+
+    use super::*;
+
+    impl Arbitrary for FuncValue {
+        type Strategy = BoxedStrategy<Self>;
+        type Parameters = ();
+
+        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
+            (any::<Expr>(), vec(any::<FuncArg>(), 1..10))
+                .prop_map(|(body, args)| Self::new(args, body))
+                .boxed()
+        }
+    }
+
+    proptest! {
+
+        #[test]
+        fn ser_roundtrip(func_value in any::<FuncValue>()) {
+            let e = Expr::FuncValue(func_value.into());
+            prop_assert_eq![sigma_serialize_roundtrip(&e), e];
+        }
+    }
+}
diff --git a/ergo-lib/src/ast/global_vars.rs b/ergo-lib/src/ast/global_vars.rs
index 3d9cf5295..b68b7f4b4 100644
--- a/ergo-lib/src/ast/global_vars.rs
+++ b/ergo-lib/src/ast/global_vars.rs
@@ -1,4 +1,5 @@
 use crate::serialization::op_code::OpCode;
+use crate::types::stype::SType;
 
 #[derive(PartialEq, Eq, Debug, Clone)]
 /// Predefined global variables
@@ -22,6 +23,15 @@ impl GlobalVars {
             GlobalVars::Height => OpCode::HEIGHT,
         }
     }
+
+    pub fn tpe(&self) -> SType {
+        match self {
+            GlobalVars::Inputs => SType::SColl(Box::new(SType::SBox)),
+            GlobalVars::Outputs => SType::SColl(Box::new(SType::SBox)),
+            GlobalVars::Height => SType::SInt,
+            GlobalVars::SelfBox => SType::SBox,
+        }
+    }
 }
 
 #[cfg(test)]
diff --git a/ergo-lib/src/ast/method_call.rs b/ergo-lib/src/ast/method_call.rs
index 956a2863e..4077355fa 100644
--- a/ergo-lib/src/ast/method_call.rs
+++ b/ergo-lib/src/ast/method_call.rs
@@ -12,8 +12,11 @@ pub struct MethodCall {
 }
 
 impl MethodCall {
-    pub fn tpe(&self) -> &SType {
-        self.method.tpe()
+    pub fn tpe(&self) -> SType {
+        match self.method.tpe() {
+            SType::SFunc(sfunc) => sfunc.t_range.clone(),
+            tpe => tpe.clone(),
+        }
     }
 
     pub fn op_code(&self) -> OpCode {
diff --git a/ergo-lib/src/ast/option_get.rs b/ergo-lib/src/ast/option_get.rs
index 3a1cbc800..d389c6d1a 100644
--- a/ergo-lib/src/ast/option_get.rs
+++ b/ergo-lib/src/ast/option_get.rs
@@ -1,6 +1,7 @@
 use super::expr::Expr;
+use super::expr::InvalidArgumentError;
 use crate::ast::value::Value;
-use crate::eval::Env;
+use crate::eval::env::Env;
 use crate::eval::EvalContext;
 use crate::eval::EvalError;
 use crate::eval::Evaluable;
@@ -9,16 +10,37 @@ use crate::serialization::sigma_byte_reader::SigmaByteRead;
 use crate::serialization::sigma_byte_writer::SigmaByteWrite;
 use crate::serialization::SerializationError;
 use crate::serialization::SigmaSerializable;
+use crate::types::stype::SType;
 
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub struct OptionGet {
-    pub input: Expr,
+    input: Expr,
 }
 
 impl OptionGet {
+    pub fn new(input: Expr) -> Result<Self, InvalidArgumentError> {
+        match input.tpe() {
+            SType::SOption(_) => Ok(OptionGet { input }),
+            _ => Err(InvalidArgumentError(format!(
+                "expected OptionGet::input type to be SOption, got: {0:?}",
+                input.tpe(),
+            ))),
+        }
+    }
+
     pub fn op_code(&self) -> OpCode {
         OpCode::OPTION_GET
     }
+
+    pub fn tpe(&self) -> SType {
+        match self.input.tpe() {
+            SType::SOption(o) => *o,
+            _ => panic!(
+                "expected OptionGet::input type to be SOption, got: {0:?}",
+                self.input.tpe()
+            ),
+        }
+    }
 }
 
 impl Evaluable for OptionGet {
@@ -42,9 +64,7 @@ impl SigmaSerializable for OptionGet {
     }
 
     fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
-        Ok(OptionGet {
-            input: Expr::sigma_parse(r)?,
-        })
+        Ok(OptionGet::new(Expr::sigma_parse(r)?)?)
     }
 }
 
@@ -83,8 +103,14 @@ mod tests {
 
     #[test]
     fn ser_roundtrip() {
+        let get_reg_expr: Expr = Box::new(ExtractRegisterAs {
+            input: Box::new(GlobalVars::SelfBox).into(),
+            register_id: RegisterId::R0,
+            tpe: SType::SOption(SType::SLong.into()),
+        })
+        .into();
         let e: Expr = Box::new(OptionGet {
-            input: Expr::Context,
+            input: get_reg_expr,
         })
         .into();
         assert_eq![sigma_serialize_roundtrip(&e), e];
diff --git a/ergo-lib/src/ast/predef_func.rs b/ergo-lib/src/ast/predef_func.rs
index c1dad77dc..4c8617e65 100644
--- a/ergo-lib/src/ast/predef_func.rs
+++ b/ergo-lib/src/ast/predef_func.rs
@@ -1,3 +1,5 @@
+use crate::types::stype::SType;
+
 use super::expr::Expr;
 
 #[derive(PartialEq, Eq, Debug, Clone)]
@@ -9,3 +11,11 @@ pub enum PredefFunc {
         input: Box<Expr>,
     },
 }
+
+impl PredefFunc {
+    pub fn tpe(&self) -> SType {
+        match self {
+            PredefFunc::Sha256 { input: _ } => todo!(),
+        }
+    }
+}
diff --git a/ergo-lib/src/ast/property_call.rs b/ergo-lib/src/ast/property_call.rs
index 32fa06e0c..02a5a88a7 100644
--- a/ergo-lib/src/ast/property_call.rs
+++ b/ergo-lib/src/ast/property_call.rs
@@ -11,8 +11,8 @@ pub struct PropertyCall {
 }
 
 impl PropertyCall {
-    pub fn tpe(&self) -> &SType {
-        self.method.tpe()
+    pub fn tpe(&self) -> SType {
+        self.method.tpe().clone()
     }
 
     pub fn op_code(&self) -> OpCode {
diff --git a/ergo-lib/src/ast/val_def.rs b/ergo-lib/src/ast/val_def.rs
new file mode 100644
index 000000000..297bd1462
--- /dev/null
+++ b/ergo-lib/src/ast/val_def.rs
@@ -0,0 +1,84 @@
+use std::io::Error;
+
+use crate::serialization::op_code::OpCode;
+use crate::serialization::sigma_byte_reader::SigmaByteRead;
+use crate::serialization::sigma_byte_writer::SigmaByteWrite;
+use crate::serialization::SerializationError;
+use crate::serialization::SigmaSerializable;
+use crate::types::stype::SType;
+
+use super::expr::Expr;
+
+extern crate derive_more;
+use derive_more::From;
+
+#[cfg(test)]
+use proptest_derive::Arbitrary;
+
+#[derive(PartialEq, Eq, Hash, Debug, Clone, Copy, From)]
+#[cfg_attr(test, derive(Arbitrary))]
+pub struct ValId(u32);
+
+impl SigmaSerializable for ValId {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), Error> {
+        w.put_u32(self.0)
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let id = r.get_u32()?;
+        Ok(ValId(id))
+    }
+}
+
+/** IR node for let-bound expressions `let x = rhs` which is ValDef.
+ * These nodes are used to represent ErgoTrees after common sub-expression elimination.
+ * This representation is more compact in serialized form.
+ * @param id unique identifier of the variable in the current scope. */
+#[derive(PartialEq, Eq, Debug, Clone)]
+#[cfg_attr(test, derive(Arbitrary))]
+pub struct ValDef {
+    pub id: ValId,
+    pub rhs: Expr,
+}
+
+impl ValDef {
+    pub fn tpe(&self) -> SType {
+        self.rhs.tpe()
+    }
+
+    pub fn op_code(&self) -> OpCode {
+        OpCode::VAL_DEF
+    }
+}
+
+impl SigmaSerializable for ValDef {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), Error> {
+        self.id.sigma_serialize(w)?;
+        self.rhs.sigma_serialize(w)
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let id = ValId::sigma_parse(r)?;
+        let rhs = Expr::sigma_parse(r)?;
+        r.val_def_type_store().insert(id, rhs.tpe());
+        Ok(ValDef { id, rhs })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::serialization::sigma_serialize_roundtrip;
+
+    use super::*;
+
+    use proptest::prelude::*;
+
+    proptest! {
+
+        #[test]
+        fn ser_roundtrip(v in any::<ValDef>()) {
+            let e = Expr::ValDef(v.into());
+            prop_assert_eq![sigma_serialize_roundtrip(&e), e];
+        }
+    }
+}
diff --git a/ergo-lib/src/ast/val_use.rs b/ergo-lib/src/ast/val_use.rs
new file mode 100644
index 000000000..8d357d2e3
--- /dev/null
+++ b/ergo-lib/src/ast/val_use.rs
@@ -0,0 +1,89 @@
+use std::io;
+
+use crate::eval::env::Env;
+use crate::eval::EvalContext;
+use crate::eval::EvalError;
+use crate::eval::Evaluable;
+use crate::serialization::op_code::OpCode;
+use crate::serialization::sigma_byte_reader::SigmaByteRead;
+use crate::serialization::sigma_byte_writer::SigmaByteWrite;
+use crate::serialization::SerializationError;
+use crate::serialization::SigmaSerializable;
+use crate::types::stype::SType;
+
+use super::val_def::ValId;
+use super::value::Value;
+
+/** Special node which represents a reference to ValDef in was introduced as result of CSE. */
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct ValUse {
+    pub val_id: ValId,
+    pub tpe: SType,
+}
+
+impl ValUse {
+    pub fn op_code(&self) -> OpCode {
+        OpCode::VAL_USE
+    }
+}
+
+impl Evaluable for ValUse {
+    fn eval(&self, env: &Env, _ctx: &mut EvalContext) -> Result<Value, EvalError> {
+        env.get(self.val_id).cloned().ok_or_else(|| {
+            EvalError::NotFound(format!("no value in env for id: {0:?}", self.val_id))
+        })
+    }
+}
+
+impl SigmaSerializable for ValUse {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), io::Error> {
+        self.val_id.sigma_serialize(w)
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let val_id = ValId::sigma_parse(r)?;
+        let tpe = r
+            .val_def_type_store()
+            .get(&val_id)
+            .ok_or(SerializationError::ValDefIdNotFound(val_id))?
+            .clone();
+        Ok(ValUse { val_id, tpe })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::ast::block::BlockValue;
+    use crate::ast::expr::Expr;
+    use crate::ast::func_value::FuncArg;
+    use crate::ast::func_value::FuncValue;
+    use crate::ast::val_def::ValDef;
+    use crate::serialization::sigma_serialize_roundtrip;
+
+    use super::*;
+
+    use proptest::prelude::*;
+
+    proptest! {
+
+        #[test]
+        fn ser_roundtrip_block_value(v in any::<ValDef>()) {
+            // ValDef should put the type into the ValDefStore for ValUse to read
+            let block = Expr::BlockValue(Box::new(BlockValue {
+                items: vec![v.clone()],
+                result: Box::new(ValUse{ val_id: v.id, tpe: v.tpe() }).into(),
+            }));
+            prop_assert_eq![sigma_serialize_roundtrip(&block), block];
+        }
+
+        #[test]
+        fn ser_roundtrip_func_value(v in any::<FuncArg>()) {
+            let body = Box::new(ValUse{ val_id: v.idx, tpe: v.tpe.clone() }).into();
+            let func = Expr::FuncValue(Box::new(
+                    FuncValue::new(vec![v], body)
+                    ));
+            prop_assert_eq![sigma_serialize_roundtrip(&func), func];
+        }
+
+    }
+}
diff --git a/ergo-lib/src/ast/value.rs b/ergo-lib/src/ast/value.rs
index deb419e7e..abc4ecc13 100644
--- a/ergo-lib/src/ast/value.rs
+++ b/ergo-lib/src/ast/value.rs
@@ -19,6 +19,7 @@ use crate::types::stype::TupleItems;
 
 use super::constant::TryExtractFrom;
 use super::constant::TryExtractFromError;
+use super::func_value::FuncValue;
 
 #[derive(PartialEq, Eq, Debug, Clone)]
 /// Collection for primitive values (i.e byte array)
@@ -60,7 +61,7 @@ impl Coll {
     }
 }
 
-/// Constant value
+/// Runtime value
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub enum Value {
     /// Boolean
@@ -91,6 +92,8 @@ pub enum Value {
     Context(Rc<Context>),
     /// Optional value
     Opt(Box<Option<Value>>),
+    /// lambda
+    FuncValue(Box<FuncValue>),
 }
 
 impl Value {
diff --git a/ergo-lib/src/eval.rs b/ergo-lib/src/eval.rs
index 36e5e7720..7db378af4 100644
--- a/ergo-lib/src/eval.rs
+++ b/ergo-lib/src/eval.rs
@@ -12,25 +12,17 @@ use thiserror::Error;
 
 use self::context::Context;
 use self::cost_accum::CostError;
+use self::env::Env;
 
 pub(crate) mod context;
 pub(crate) mod cost_accum;
 pub(crate) mod costs;
+pub(crate) mod env;
 pub(crate) mod expr;
 pub(crate) mod global_vars;
 pub(crate) mod method_call;
 pub(crate) mod property_call;
 
-/// Environment for the interpreter
-pub struct Env();
-
-impl Env {
-    /// Empty environment
-    pub fn empty() -> Env {
-        Env()
-    }
-}
-
 /// Interpreter errors
 #[derive(Error, PartialEq, Eq, Debug, Clone)]
 pub enum EvalError {
@@ -52,6 +44,9 @@ pub enum EvalError {
     /// Register id out of bounds
     #[error("{0:?}")]
     RegisterIdOutOfBounds(#[from] RegisterIdOutOfBounds),
+    /// Unexpected value
+    #[error("unexpected value: {0:?}")]
+    UnexpectedValue(String),
 }
 
 /// Result of expression reduction procedure (see `reduce_to_crypto`).
@@ -112,11 +107,12 @@ pub trait Evaluable {
 pub mod tests {
 
     use crate::ast::constant::TryExtractFrom;
+    use crate::ast::constant::TryExtractInto;
 
+    use super::env::Env;
     use super::*;
 
     pub fn eval_out<T: TryExtractFrom<Value>>(expr: &Expr, ctx: Rc<Context>) -> T {
-        use crate::ast::constant::TryExtractInto;
         let cost_accum = CostAccumulator::new(0, None);
         let mut ectx = EvalContext::new(ctx, cost_accum);
         expr.eval(&Env::empty(), &mut ectx)
diff --git a/ergo-lib/src/eval/env.rs b/ergo-lib/src/eval/env.rs
new file mode 100644
index 000000000..78accbc9a
--- /dev/null
+++ b/ergo-lib/src/eval/env.rs
@@ -0,0 +1,35 @@
+use std::collections::HashMap;
+
+use crate::ast::val_def::ValId;
+use crate::ast::value::Value;
+
+/// Environment for the interpreter
+#[derive(PartialEq, Eq, Debug, Clone)]
+pub struct Env {
+    store: HashMap<ValId, Value>,
+}
+
+impl Env {
+    /// Empty environment
+    pub fn empty() -> Env {
+        Env {
+            store: HashMap::new(),
+        }
+    }
+
+    /// Extend this environment (create new) with added element
+    pub fn extend(&self, idx: ValId, v: Value) -> Env {
+        let mut new_store = self.store.clone();
+        new_store.insert(idx, v);
+        Env { store: new_store }
+    }
+
+    pub fn insert(&mut self, idx: ValId, v: Value) {
+        self.store.insert(idx, v);
+    }
+
+    /// Get an element
+    pub fn get(&self, idx: ValId) -> Option<&Value> {
+        self.store.get(&idx)
+    }
+}
diff --git a/ergo-lib/src/eval/expr.rs b/ergo-lib/src/eval/expr.rs
index d664d405d..a610842c0 100644
--- a/ergo-lib/src/eval/expr.rs
+++ b/ergo-lib/src/eval/expr.rs
@@ -20,8 +20,12 @@ impl Evaluable for Expr {
             Expr::BinOp(op) => op.eval(env, ctx),
             Expr::Context => Ok(Value::Context(ctx.ctx.clone())),
             Expr::OptionGet(v) => v.eval(env, ctx),
+            Expr::Apply(op) => op.eval(env, ctx),
+            Expr::FuncValue(op) => op.eval(env, ctx),
+            Expr::ValUse(op) => op.eval(env, ctx),
+            Expr::BlockValue(op) => op.eval(env, ctx),
             _ => Err(EvalError::UnexpectedExpr(format!(
-                "Don't know how to eval Expr: {}",
+                "Don't know how to eval Expr: {0:?}",
                 self
             ))),
         }
diff --git a/ergo-lib/src/eval/method_call.rs b/ergo-lib/src/eval/method_call.rs
index f10eb5b2c..c5d4a4afd 100644
--- a/ergo-lib/src/eval/method_call.rs
+++ b/ergo-lib/src/eval/method_call.rs
@@ -38,7 +38,7 @@ mod tests {
             args: vec![Box::new(Constant::from(0i8)).into()],
         })
         .into();
-        let option_get_expr: Expr = Box::new(OptionGet { input: mc }).into();
+        let option_get_expr: Expr = Box::new(OptionGet::new(mc).unwrap()).into();
         let ctx = Rc::new(force_any_val::<Context>());
         assert_eq!(
             eval_out::<i64>(&option_get_expr, ctx.clone()),
diff --git a/ergo-lib/src/serialization.rs b/ergo-lib/src/serialization.rs
index 23a2b9c2d..5dfa8f989 100644
--- a/ergo-lib/src/serialization.rs
+++ b/ergo-lib/src/serialization.rs
@@ -9,6 +9,7 @@ mod global_vars;
 mod method_call;
 mod property_call;
 mod sigmaboolean;
+mod val_def_type_store;
 
 pub(crate) mod constant_store;
 pub(crate) mod ergo_box;
diff --git a/ergo-lib/src/serialization/data.rs b/ergo-lib/src/serialization/data.rs
index d1b46a99a..e0b5bc6fa 100644
--- a/ergo-lib/src/serialization/data.rs
+++ b/ergo-lib/src/serialization/data.rs
@@ -44,8 +44,8 @@ impl DataSerializer {
             Value::Tup(items) => items
                 .iter()
                 .try_for_each(|i| DataSerializer::sigma_serialize(i, w)),
-            Value::Opt(_) => panic!(), // unsupported, see https://github.com/ScorexFoundation/sigmastate-interpreter/issues/659
-            Value::Context(_) => todo!(), // TODO: throw error? it should not be here
+            Value::Opt(_) => panic!("Option is not yet supported"), // unsupported, see https://github.com/ScorexFoundation/sigmastate-interpreter/issues/659
+            _ => panic!("serialization is not supported for value: {0:?}", c),
         }
     }
 
diff --git a/ergo-lib/src/serialization/expr.rs b/ergo-lib/src/serialization/expr.rs
index 8144fec9b..7198d315a 100644
--- a/ergo-lib/src/serialization/expr.rs
+++ b/ergo-lib/src/serialization/expr.rs
@@ -2,15 +2,19 @@ use super::bin_op::bin_op_sigma_parse;
 use super::bin_op::bin_op_sigma_serialize;
 use super::{op_code::OpCode, sigma_byte_writer::SigmaByteWrite};
 use crate::ast::bin_op::LogicOp;
+use crate::ast::block::BlockValue;
 use crate::ast::coll_fold::Fold;
 use crate::ast::constant::Constant;
 use crate::ast::constant::ConstantPlaceholder;
 use crate::ast::expr::Expr;
 use crate::ast::extract_reg_as::ExtractRegisterAs;
+use crate::ast::func_value::FuncValue;
 use crate::ast::global_vars::GlobalVars;
 use crate::ast::method_call::MethodCall;
 use crate::ast::option_get::OptionGet;
 use crate::ast::property_call::PropertyCall;
+use crate::ast::val_def::ValDef;
+use crate::ast::val_use::ValUse;
 use crate::serialization::{
     sigma_byte_reader::SigmaByteRead, SerializationError, SigmaSerializable,
 };
@@ -41,6 +45,10 @@ impl SigmaSerializable for Expr {
                     Expr::OptionGet(v) => v.sigma_serialize(w),
                     Expr::ExtractRegisterAs(v) => v.sigma_serialize(w),
                     Expr::BinOp(op) => bin_op_sigma_serialize(op, w),
+                    Expr::BlockValue(op) => op.sigma_serialize(w),
+                    Expr::ValUse(op) => op.sigma_serialize(w),
+                    Expr::ValDef(op) => op.sigma_serialize(w),
+                    Expr::FuncValue(op) => op.sigma_serialize(w),
                     _ => panic!(format!("don't know how to serialize {:?}", expr)),
                 }
             }
@@ -89,6 +97,10 @@ impl SigmaSerializable for Expr {
                 }
                 OpCode::EQ => Ok(bin_op_sigma_parse(LogicOp::Eq.into(), r)?),
                 OpCode::NEQ => Ok(bin_op_sigma_parse(LogicOp::NEq.into(), r)?),
+                OpCode::BLOCK_VALUE => Ok(Expr::BlockValue(BlockValue::sigma_parse(r)?.into())),
+                OpCode::FUNC_VALUE => Ok(Expr::FuncValue(FuncValue::sigma_parse(r)?.into())),
+                OpCode::VAL_DEF => Ok(Expr::ValDef(ValDef::sigma_parse(r)?.into())),
+                OpCode::VAL_USE => Ok(Expr::ValUse(ValUse::sigma_parse(r)?.into())),
                 o => Err(SerializationError::NotImplementedOpCode(o.value())),
             }
         }
diff --git a/ergo-lib/src/serialization/method_call.rs b/ergo-lib/src/serialization/method_call.rs
index a8c634d04..094434b98 100644
--- a/ergo-lib/src/serialization/method_call.rs
+++ b/ergo-lib/src/serialization/method_call.rs
@@ -16,8 +16,7 @@ impl SigmaSerializable for MethodCall {
         self.method.obj_type.type_id().sigma_serialize(w)?;
         self.method.method_id().sigma_serialize(w)?;
         self.obj.sigma_serialize(w)?;
-        w.put_u32(self.args.len() as u32)?;
-        self.args.iter().try_for_each(|a| a.sigma_serialize(w))?;
+        self.args.sigma_serialize(w)?;
         Ok(())
     }
 
@@ -25,16 +24,9 @@ impl SigmaSerializable for MethodCall {
         let type_id = TypeId::sigma_parse(r)?;
         let method_id = MethodId::sigma_parse(r)?;
         let obj = Expr::sigma_parse(r)?;
-        let args_count = r.get_u32()?;
-        let mut args = Vec::with_capacity(args_count as usize);
-        for _ in 0..args_count {
-            args.push(Expr::sigma_parse(r)?);
-        }
-        Ok(MethodCall {
-            obj,
-            method: SMethod::from_ids(type_id, method_id),
-            args,
-        })
+        let args = Vec::<Expr>::sigma_parse(r)?;
+        let method = SMethod::from_ids(type_id, method_id);
+        Ok(MethodCall { obj, method, args })
     }
 }
 
diff --git a/ergo-lib/src/serialization/op_code.rs b/ergo-lib/src/serialization/op_code.rs
index b374e0a90..d882140b5 100644
--- a/ergo-lib/src/serialization/op_code.rs
+++ b/ergo-lib/src/serialization/op_code.rs
@@ -18,6 +18,7 @@ impl OpCode {
     pub const LAST_DATA_TYPE: OpCode = OpCode(111);
     pub const LAST_CONSTANT_CODE: OpCode = OpCode(Self::LAST_DATA_TYPE.value() + 1);
 
+    pub const VAL_USE: OpCode = Self::new_op_code(2);
     pub const CONSTANT_PLACEHOLDER: OpCode = Self::new_op_code(3);
 
     pub const EQ: OpCode = Self::new_op_code(35);
@@ -35,6 +36,9 @@ impl OpCode {
 
     pub const PROVE_DLOG: OpCode = Self::new_op_code(93);
 
+    pub const VAL_DEF: OpCode = Self::new_op_code(102);
+    pub const BLOCK_VALUE: OpCode = Self::new_op_code(104);
+    pub const FUNC_VALUE: OpCode = Self::new_op_code(105);
     pub const PROPERTY_CALL: OpCode = Self::new_op_code(107);
     pub const METHOD_CALL: OpCode = Self::new_op_code(108);
 
diff --git a/ergo-lib/src/serialization/serializable.rs b/ergo-lib/src/serialization/serializable.rs
index 0b83bcdb8..848221054 100644
--- a/ergo-lib/src/serialization/serializable.rs
+++ b/ergo-lib/src/serialization/serializable.rs
@@ -1,4 +1,7 @@
 //! Serialization of Ergo types
+use crate::ast::expr::InvalidArgumentError;
+use crate::ast::val_def::ValId;
+
 use super::{
     constant_store::ConstantStore,
     sigma_byte_reader::{SigmaByteRead, SigmaByteReader},
@@ -42,6 +45,12 @@ pub enum SerializationError {
     /// Tuple items out of bounds
     #[error("Tuple items out of bounds: {0}")]
     TupleItemsOutOfBounds(usize),
+    /// ValDef type for a given index not found in ValDefTypeStore store
+    #[error("ValDef type for an index {0:?} not found in ValDefTypeStore store")]
+    ValDefIdNotFound(ValId),
+    /// Invalid argument on node creation
+    #[error("Invalid argument: {0:?}")]
+    InvalidArgument(InvalidArgumentError),
 }
 
 impl From<vlq_encode::VlqEncodingError> for SerializationError {
@@ -56,6 +65,12 @@ impl From<io::Error> for SerializationError {
     }
 }
 
+impl From<InvalidArgumentError> for SerializationError {
+    fn from(e: InvalidArgumentError) -> Self {
+        SerializationError::InvalidArgument(e)
+    }
+}
+
 /// Consensus-critical serialization for Ergo
 pub trait SigmaSerializable: Sized {
     /// Write `self` to the given `writer`.
@@ -91,6 +106,22 @@ pub trait SigmaSerializable: Sized {
     }
 }
 
+impl<T: SigmaSerializable> SigmaSerializable for Vec<T> {
+    fn sigma_serialize<W: SigmaByteWrite>(&self, w: &mut W) -> Result<(), io::Error> {
+        w.put_u32(self.len() as u32)?;
+        self.iter().try_for_each(|i| i.sigma_serialize(w))
+    }
+
+    fn sigma_parse<R: SigmaByteRead>(r: &mut R) -> Result<Self, SerializationError> {
+        let items_count = r.get_u32()?;
+        let mut items = Vec::with_capacity(items_count as usize);
+        for _ in 0..items_count {
+            items.push(T::sigma_parse(r)?);
+        }
+        Ok(items)
+    }
+}
+
 /// serialization roundtrip
 #[cfg(test)]
 pub fn sigma_serialize_roundtrip<T: SigmaSerializable>(v: &T) -> T {
diff --git a/ergo-lib/src/serialization/sigma_byte_reader.rs b/ergo-lib/src/serialization/sigma_byte_reader.rs
index e1b7addd7..00d2b1299 100644
--- a/ergo-lib/src/serialization/sigma_byte_reader.rs
+++ b/ergo-lib/src/serialization/sigma_byte_reader.rs
@@ -1,5 +1,6 @@
 //! Sigma byte stream writer
 use super::constant_store::ConstantStore;
+use super::val_def_type_store::ValDefTypeStore;
 use sigma_ser::{peekable_reader::Peekable, vlq_encode::ReadSigmaVlqExt};
 use std::io::Read;
 
@@ -8,6 +9,7 @@ pub struct SigmaByteReader<R> {
     inner: R,
     constant_store: ConstantStore,
     substitute_placeholders: bool,
+    val_def_type_store: ValDefTypeStore,
 }
 
 impl<R: Peekable> SigmaByteReader<R> {
@@ -17,6 +19,7 @@ impl<R: Peekable> SigmaByteReader<R> {
             inner: pr,
             constant_store,
             substitute_placeholders: false,
+            val_def_type_store: ValDefTypeStore::new(),
         }
     }
 
@@ -30,6 +33,7 @@ impl<R: Peekable> SigmaByteReader<R> {
             inner: pr,
             constant_store,
             substitute_placeholders: true,
+            val_def_type_store: ValDefTypeStore::new(),
         }
     }
 }
@@ -44,6 +48,9 @@ pub trait SigmaByteRead: ReadSigmaVlqExt {
 
     /// Set new constant store
     fn set_constant_store(&mut self, constant_store: ConstantStore);
+
+    /// ValDef types store (resolves tpe on ValUse parsing)
+    fn val_def_type_store(&mut self) -> &mut ValDefTypeStore;
 }
 
 impl<R: Peekable> Read for SigmaByteReader<R> {
@@ -70,4 +77,8 @@ impl<R: ReadSigmaVlqExt> SigmaByteRead for SigmaByteReader<R> {
     fn set_constant_store(&mut self, constant_store: ConstantStore) {
         self.constant_store = constant_store;
     }
+
+    fn val_def_type_store(&mut self) -> &mut ValDefTypeStore {
+        &mut self.val_def_type_store
+    }
 }
diff --git a/ergo-lib/src/serialization/val_def_type_store.rs b/ergo-lib/src/serialization/val_def_type_store.rs
new file mode 100644
index 000000000..743402129
--- /dev/null
+++ b/ergo-lib/src/serialization/val_def_type_store.rs
@@ -0,0 +1,26 @@
+use std::collections::HashMap;
+
+use crate::ast::val_def::ValId;
+use crate::types::stype::SType;
+
+pub struct ValDefTypeStore(HashMap<ValId, SType>);
+
+impl ValDefTypeStore {
+    pub fn new() -> Self {
+        ValDefTypeStore(HashMap::new())
+    }
+
+    pub fn insert(&mut self, id: ValId, tpe: SType) {
+        self.0.insert(id, tpe);
+    }
+
+    pub fn get(&self, id: &ValId) -> Option<&SType> {
+        self.0.get(id)
+    }
+}
+
+impl Default for ValDefTypeStore {
+    fn default() -> Self {
+        ValDefTypeStore::new()
+    }
+}
diff --git a/ergo-lib/src/sigma_protocol/prover.rs b/ergo-lib/src/sigma_protocol/prover.rs
index 2787cb0a4..6a0601e8f 100644
--- a/ergo-lib/src/sigma_protocol/prover.rs
+++ b/ergo-lib/src/sigma_protocol/prover.rs
@@ -19,7 +19,8 @@ use super::{
 };
 use crate::ergo_tree::{ErgoTree, ErgoTreeParsingError};
 use crate::eval::context::Context;
-use crate::eval::{Env, EvalError, Evaluator};
+use crate::eval::env::Env;
+use crate::eval::{EvalError, Evaluator};
 use thiserror::Error;
 
 /// Prover errors
diff --git a/ergo-lib/src/sigma_protocol/verifier.rs b/ergo-lib/src/sigma_protocol/verifier.rs
index eef3209a8..f3cfaa8d4 100644
--- a/ergo-lib/src/sigma_protocol/verifier.rs
+++ b/ergo-lib/src/sigma_protocol/verifier.rs
@@ -12,7 +12,8 @@ use super::{
 };
 use crate::ergo_tree::{ErgoTree, ErgoTreeParsingError};
 use crate::eval::context::Context;
-use crate::eval::{Env, EvalError, Evaluator};
+use crate::eval::env::Env;
+use crate::eval::{EvalError, Evaluator};
 use dlog_protocol::FirstDlogProverMessage;
 
 /// Errors on proof verification
diff --git a/ergo-lib/src/types/sfunc.rs b/ergo-lib/src/types/sfunc.rs
index 7a1c0b570..53bafa264 100644
--- a/ergo-lib/src/types/sfunc.rs
+++ b/ergo-lib/src/types/sfunc.rs
@@ -3,7 +3,10 @@ use super::stype_param::STypeParam;
 
 #[derive(PartialEq, Eq, Debug, Clone)]
 pub struct SFunc {
+    /// Function parameter types
     pub t_dom: Vec<SType>,
+    /// Result type
     pub t_range: SType,
+    /// Type parameters if the function is generic
     pub tpe_params: Vec<STypeParam>,
 }
diff --git a/ergo-lib/src/types/stype.rs b/ergo-lib/src/types/stype.rs
index 6732a863a..cf627e380 100644
--- a/ergo-lib/src/types/stype.rs
+++ b/ergo-lib/src/types/stype.rs
@@ -98,6 +98,11 @@ impl<T> TupleItems<T> {
     //     self.0
     // }
 
+    /// Create a pair
+    pub fn pair(t1: T, t2: T) -> TupleItems<T> {
+        TupleItems(vec![t1, t2])
+    }
+
     /// Get the length (quantity)
     pub fn len(&self) -> usize {
         self.0.len()
diff --git a/ergo-lib/src/wallet/signing.rs b/ergo-lib/src/wallet/signing.rs
index 1216b8dd5..0d3191bec 100644
--- a/ergo-lib/src/wallet/signing.rs
+++ b/ergo-lib/src/wallet/signing.rs
@@ -5,13 +5,13 @@ use std::rc::Rc;
 use crate::chain::transaction::Input;
 use crate::eval::context::Context;
 use crate::eval::context::ContextError;
+use crate::eval::env::Env;
 use crate::{
     chain::{
         ergo_box::ErgoBox,
         ergo_state_context::ErgoStateContext,
         transaction::{unsigned::UnsignedTransaction, Transaction},
     },
-    eval::Env,
     sigma_protocol::prover::{Prover, ProverError},
 };
 


Test patch: