Goose  Check-in [dd70f4c696]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Sema: terms can now be wrapped along with a callback to be invoked by Substitute().
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: dd70f4c6960fc18f846a28acff4c596931ae6f63ab49870bbed302cf699ecce1
User & Date: achavasse 2019-03-17 15:54:13.514
Context
2019-03-17
20:56
Sema: terms can now be wrapped along with a post processing function. This is similar to the substitute call back, but it is invoked after the best unification solution has been chosen. check-in: 396ab349c6 user: achavasse tags: trunk
15:54
Sema: terms can now be wrapped along with a callback to be invoked by Substitute(). check-in: dd70f4c696 user: achavasse tags: trunk
11:49
Added a way to quote an expression so that its content is ignored during unification, and used it for function signatures. check-in: 68eda7b3fe user: achavasse tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to bs/builtins/types/func/invoke.cpp.
︙︙
20
21
22
23
24
25
26




27
28
29
30
31
32
33
34
35
36
37
38


                auto callPat = TVEC( args.val(), sema::MkHole( "_"_sid ) );

                for( auto&& [s, uc] : Unify( sig, callPat, uc ) )
                {
                    if( uc.numUnknownValues() )
                        continue;





                    if( !bestSol || uc.score() > bestUC->score() )
                    {
                        bestUC = uc;
                        bestSol = s;
                        ambiguous = false;
                        continue;
                    }

                    if( uc.score() < bestUC->score() )
                        continue;









>
>
>
>




|








20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


                auto callPat = TVEC( args.val(), sema::MkHole( "_"_sid ) );

                for( auto&& [s, uc] : Unify( sig, callPat, uc ) )
                {
                    if( uc.numUnknownValues() )
                        continue;

                    auto ssol = Substitute( s, uc );
                    if( !ssol )
                        continue;

                    if( !bestSol || uc.score() > bestUC->score() )
                    {
                        bestUC = uc;
                        bestSol = ssol;
                        ambiguous = false;
                        continue;
                    }

                    if( uc.score() < bestUC->score() )
                        continue;
︙︙
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

                    cout << "function arguments mismatch.\n";
                    return nullopt;
                }

                return invoke( c, callee, *bestSol, *bestUC );
            }

            optional< Value > invoke( const Context& c, const Value& callee, const Term& uniSol, UnificationContext& uc ) const final
            {
                const auto& env = c.env();

                if( !IsBuiltinFunc( callee ) )
                    PerformLazyFuncParsing( env, callee );

                auto unifiedCallPat = Substitute( uniSol, uc );
                auto callDecomp = Decompose( unifiedCallPat,
                    Vec(
                        SubTerm(),  // args
                        SubTerm()   // return type
                    )
                );









|






<








56
57
58
59
60
61
62
63
64
65
66
67
68
69

70
71
72
73
74
75
76

                    cout << "function arguments mismatch.\n";
                    return nullopt;
                }

                return invoke( c, callee, *bestSol, *bestUC );
            }

            optional< Value > invoke( const Context& c, const Value& callee, const Term& unifiedCallPat, UnificationContext& uc ) const final
            {
                const auto& env = c.env();

                if( !IsBuiltinFunc( callee ) )
                    PerformLazyFuncParsing( env, callee );


                auto callDecomp = Decompose( unifiedCallPat,
                    Vec(
                        SubTerm(),  // args
                        SubTerm()   // return type
                    )
                );
︙︙
Changes to bs/builtins/types/overloadset/invoke.cpp.
︙︙
23
24
25
26
27
28
29




30
31
32
33
34
35
36
37
38
39
40
41


                auto rtPat = sema::MkHole( "_"_sid );

                for( auto&& [s,ovl,uc] : pOvlSet->unify( args.val(), rtPat, uc ) )
                {
                    if( uc.numUnknownValues() )
                        continue;





                    if( !bestSol || uc.score() > bestUC->score() )
                    {
                        bestUC = uc;
                        bestSol = s;
                        bestOvl = ovl;
                        ambiguous = false;
                        continue;
                    }

                    if( uc.score() < bestUC->score() )
                        continue;








>
>
>
>




|








23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


                auto rtPat = sema::MkHole( "_"_sid );

                for( auto&& [s,ovl,uc] : pOvlSet->unify( args.val(), rtPat, uc ) )
                {
                    if( uc.numUnknownValues() )
                        continue;

                    auto ssol = Substitute( s, uc );
                    if( !ssol )
                        continue;

                    if( !bestSol || uc.score() > bestUC->score() )
                    {
                        bestUC = uc;
                        bestSol = ssol;
                        bestOvl = ovl;
                        ambiguous = false;
                        continue;
                    }

                    if( uc.score() < bestUC->score() )
                        continue;
︙︙
Changes to bs/builtins/types/template/invoke.cpp.
︙︙
24
25
26
27
28
29
30




31
32
33
34
35
36
37
38
39
40
41
42


                auto callPat = TVEC( args.val(), sema::MkHole( "_"_sid ) );

                for( auto&& [s, uc] : Unify( tf->signature(), callPat, uc ) )
                {
                    if( uc.numUnknownValues() )
                        continue;





                    if( !bestSol || uc.score() > bestUC->score() )
                    {
                        bestUC = uc;
                        bestSol = s;
                        ambiguous = false;
                        continue;
                    }

                    if( uc.score() < bestUC->score() )
                        continue;









>
>
>
>




|








24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


                auto callPat = TVEC( args.val(), sema::MkHole( "_"_sid ) );

                for( auto&& [s, uc] : Unify( tf->signature(), callPat, uc ) )
                {
                    if( uc.numUnknownValues() )
                        continue;

                    auto ssol = Substitute( s, uc );
                    if( !ssol )
                        continue;

                    if( !bestSol || uc.score() > bestUC->score() )
                    {
                        bestUC = uc;
                        bestSol = ssol;
                        ambiguous = false;
                        continue;
                    }

                    if( uc.score() < bestUC->score() )
                        continue;
︙︙
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

                    cout << "template function arguments mismatch.\n";
                    return nullopt;
                }

                return invoke( c, callee, *bestSol, *bestUC );
            }

            optional< Value > invoke( const Context& c, const Value& callee, const Term& uniSol, UnificationContext& uc ) const final
            {
                auto tf = FromValue< TFunc >( callee );
                assert( tf );

                auto unifiedCallPat = Substitute( uniSol, uc );
                auto callDecomp = Decompose( unifiedCallPat,
                    Vec(
                        SubTerm(),  // args
                        SubTerm()   // return type
                    )
                );









|




<








60
61
62
63
64
65
66
67
68
69
70
71

72
73
74
75
76
77
78

                    cout << "template function arguments mismatch.\n";
                    return nullopt;
                }

                return invoke( c, callee, *bestSol, *bestUC );
            }

            optional< Value > invoke( const Context& c, const Value& callee, const Term& unifiedCallPat, UnificationContext& uc ) const final
            {
                auto tf = FromValue< TFunc >( callee );
                assert( tf );


                auto callDecomp = Decompose( unifiedCallPat,
                    Vec(
                        SubTerm(),  // args
                        SubTerm()   // return type
                    )
                );
︙︙
Changes to bs/builtins/types/template/rules.cpp.
︙︙
103
104
105
106
107
108
109


110
111
112
113
114
115
116
117
118
119
120
121

            if( varIndex == UnificationContext::InvalidIndex )
                return;

            auto capturedValue = uc.getValue( varIndex );
            assert( capturedValue );

            auto valueToStore = Substitute( *capturedValue, uc );



            auto captureIdentity = AppendToVectorTerm( c.identity(),
                TERM( "$$"_sid ), TERM( tvar->name() ) );

            c.env()->storeValue( captureIdentity, ANYTERM( c ), valueToStore );

            // If the same TVar was present multiple time in the
            // function's signature, its setup will be called multiple time, so
            // to make sure we only store it once, erase the variable's name from
            // the unification context.
            uc.eraseLHSName( tvar->name() );
        }








>
>




|








103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

            if( varIndex == UnificationContext::InvalidIndex )
                return;

            auto capturedValue = uc.getValue( varIndex );
            assert( capturedValue );

            auto valueToStore = Substitute( *capturedValue, uc );
            if( !valueToStore )
                return;

            auto captureIdentity = AppendToVectorTerm( c.identity(),
                TERM( "$$"_sid ), TERM( tvar->name() ) );

            c.env()->storeValue( captureIdentity, ANYTERM( c ), *valueToStore );

            // If the same TVar was present multiple time in the
            // function's signature, its setup will be called multiple time, so
            // to make sure we only store it once, erase the variable's name from
            // the unification context.
            uc.eraseLHSName( tvar->name() );
        }
︙︙
Changes to bs/sema/CMakeLists.txt. 
1
2

3
4
5
6
7
8
9
10

11
12
13
14
15
16
17

add_library( empathy-sema
    env.cpp


    hole.cpp
    uni-context.cpp
    uni-ruleset.cpp
    uni-basicrules.cpp
    uni-holes.cpp
    uni-3way.cpp
    uni-quote.cpp

    unify.cpp
    substitute.cpp

    inv-ruleset.cpp
    invocation.cpp

    tpl-ruleset.cpp



>








>








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

add_library( empathy-sema
    env.cpp
    callback.cpp

    hole.cpp
    uni-context.cpp
    uni-ruleset.cpp
    uni-basicrules.cpp
    uni-holes.cpp
    uni-3way.cpp
    uni-quote.cpp
    uni-callback.cpp
    unify.cpp
    substitute.cpp

    inv-ruleset.cpp
    invocation.cpp

    tpl-ruleset.cpp
︙︙
Added bs/sema/callback.cpp. 


























































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include "sema.h"

namespace empathy::sema
{
    Term WrapWithCallback( const Term& t, Callback&& cb )
    {
        return TVEC( TSID( callback ),
            TERM( static_pointer_cast< void >( make_shared< Callback >( move( cb ) ) ) ),
            t );
    }

    optional< pair< Term, ptr< Callback > > > UnwrapCallback( const Term& cbt )
    {
        auto result = Decompose( cbt,
            Vec(
                Lit( "callback"_sid ),
                Val< ptr< void > >(),
                SubTerm()
            )
        );

        if( !result )
            return nullopt;

        auto&& [pCB, t] = *result;
        return make_pair( t, static_pointer_cast< Callback >( pCB ) );
    }
}
Added bs/sema/callback.h. 






























>
>
>
>
>
>
>
>
>
>
>
>
>
>

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#ifndef EMPATHY_SEMA_CALLBACK_H
#define EMPATHY_SEMA_CALLBACK_H

namespace empathy::sema
{
    using Callback = function< optional< Term  > ( const Term& t ) >;

    extern Term WrapWithCallback( const Term& t, Callback&& cb );
    extern optional< pair< Term, ptr< Callback > > > UnwrapCallback( const Term& cbt );

    extern void SetupCallbackUnificationRules( UnificationRuleSet& ruleSet );
}

#endif
Changes to bs/sema/inv-ruleset.h. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#ifndef EMPATHY_SEMA_INV_RULESET_H
#define EMPATHY_SEMA_INV_RULESET_H

namespace empathy::sema
{
    class InvocationRule
    {
        public:
            virtual ~InvocationRule() {}

            virtual optional< Value > resolveInvocation( const Context& c, const Value& callee, const Value& args ) const = 0;

            virtual optional< Value > invoke( const Context& c, const Value& callee, const Term& uniSol, UnificationContext& uc ) const
            {
                return nullopt;
            }

            virtual optional< Term > getSignature( const Value& callee ) const
            {
                return nullopt;













|








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#ifndef EMPATHY_SEMA_INV_RULESET_H
#define EMPATHY_SEMA_INV_RULESET_H

namespace empathy::sema
{
    class InvocationRule
    {
        public:
            virtual ~InvocationRule() {}

            virtual optional< Value > resolveInvocation( const Context& c, const Value& callee, const Value& args ) const = 0;

            virtual optional< Value > invoke( const Context& c, const Value& callee, const Term& unifiedCallPat, UnificationContext& uc ) const
            {
                return nullopt;
            }

            virtual optional< Term > getSignature( const Value& callee ) const
            {
                return nullopt;
︙︙
Changes to bs/sema/sema.h.
︙︙
9
10
11
12
13
14
15

16
17
18
19
20
21
22

{
    using namespace util;
    using namespace ir;
}

#include "context.h"
#include "env.h"


#include "hole.h"
#include "uni-score.h"
#include "uni-context.h"
#include "unify.h"
#include "uni-ruleset.h"
#include "uni-basicrules.h"








>








9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

{
    using namespace util;
    using namespace ir;
}

#include "context.h"
#include "env.h"
#include "callback.h"

#include "hole.h"
#include "uni-score.h"
#include "uni-context.h"
#include "unify.h"
#include "uni-ruleset.h"
#include "uni-basicrules.h"
︙︙
Changes to bs/sema/substitute.cpp. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25









26
27
28
29
30
31
32
33
34



35
36
37
38
39
40
41

#include "sema.h"

namespace empathy::sema
{
    Term Substitute( const Term& src, const UnificationContext& context )
    {
        if( !holds_alternative< pvec >( src.content() ) )
            return src;

        auto optHole = HoleFromIRExpr( src );
        if( optHole )
        {
            const auto& hole = *optHole;

            // We only substitute indexed holes. If we encounter a named hole,
            // output it as is.
            if( !holds_alternative< uint32_t >( hole ) )
                return src;

            const auto& optVal = context.getValue( get< uint32_t >( hole ) );
            if( !optVal )
                return src;

            return Substitute( *optVal, context );
        }










        const auto& vec = *get< pvec >( src.content() );
        immer::vector< Term > outputTerms;
        auto vt = outputTerms.transient();
        bool faulty = false;

        for( auto&& t : vec.terms() )
        {
            auto newT = Substitute( t, context );



            faulty = faulty || newT.isFaulty();
            vt.push_back( move( newT ) );
        }

        return Term( src.location(), make_shared< Vector >( vt.persistent(), faulty ) );
    }
}





|




|
<














>
>
>
>
>
>
>
>
>









>
>
>
|
|






1
2
3
4
5
6
7
8
9
10

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include "sema.h"

namespace empathy::sema
{
    optional< Term > Substitute( const Term& src, const UnificationContext& context )
    {
        if( !holds_alternative< pvec >( src.content() ) )
            return src;

        if( auto optHole = HoleFromIRExpr( src ) )

        {
            const auto& hole = *optHole;

            // We only substitute indexed holes. If we encounter a named hole,
            // output it as is.
            if( !holds_alternative< uint32_t >( hole ) )
                return src;

            const auto& optVal = context.getValue( get< uint32_t >( hole ) );
            if( !optVal )
                return src;

            return Substitute( *optVal, context );
        }

        if( auto optCB = UnwrapCallback( src ) )
        {
            auto val = Substitute( optCB->first, context );
            if( !val )
                return nullopt;

            return ( *optCB->second )( *val );
        }

        const auto& vec = *get< pvec >( src.content() );
        immer::vector< Term > outputTerms;
        auto vt = outputTerms.transient();
        bool faulty = false;

        for( auto&& t : vec.terms() )
        {
            auto newT = Substitute( t, context );
            if( !newT )
                return nullopt;

            faulty = faulty || newT->isFaulty();
            vt.push_back( move( *newT ) );
        }

        return Term( src.location(), make_shared< Vector >( vt.persistent(), faulty ) );
    }
}
Changes to bs/sema/substitute.h. 
1
2
3
4
5
6
7
8
9

#ifndef EMPATHY_SEMA_SUBSTITUTE_H
#define EMPATHY_SEMA_SUBSTITUTE_H

namespace empathy::sema
{
    extern Term Substitute( const Term& src, const UnificationContext& context );
}

#endif






|




1
2
3
4
5
6
7
8
9

#ifndef EMPATHY_SEMA_SUBSTITUTE_H
#define EMPATHY_SEMA_SUBSTITUTE_H

namespace empathy::sema
{
    extern optional< Term > Substitute( const Term& src, const UnificationContext& context );
}

#endif
Changes to bs/sema/tests/unify-holes.cpp.
︙︙
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


        auto&& [e,c] = *it;

        REQUIRE( c.numUnknownValues() == 0 );
        REQUIRE( c.score() == expectedScore );

        auto sol = Substitute( e, c );
        REQUIRE( sol == expectedSolution );

        ++it;
        REQUIRE( it == g.end() );
    }

    void CheckForNoSolution( const Term& lhs, const Term& rhs )
    {








|








23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


        auto&& [e,c] = *it;

        REQUIRE( c.numUnknownValues() == 0 );
        REQUIRE( c.score() == expectedScore );

        auto sol = Substitute( e, c );
        REQUIRE( *sol == expectedSolution );

        ++it;
        REQUIRE( it == g.end() );
    }

    void CheckForNoSolution( const Term& lhs, const Term& rhs )
    {
︙︙
Changes to bs/sema/tests/utrie-unify.cpp.
︙︙
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


        for( auto&& [v,content,c] : trie->unify( vec, context ) )
        {
            if( c.numUnknownValues() )
                continue;

            auto sol = Substitute( TERM( make_shared< Vector >( v ) ), c );
            solutions.emplace_back( sol, content, c.score() );
        }

        sort( solutions.begin(), solutions.end(), []( auto&& a, auto&& b )
        {
            return get< 1 >( a ) < get< 1 >( b );
        } );









|








18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


        for( auto&& [v,content,c] : trie->unify( vec, context ) )
        {
            if( c.numUnknownValues() )
                continue;

            auto sol = Substitute( TERM( make_shared< Vector >( v ) ), c );
            solutions.emplace_back( *sol, content, c.score() );
        }

        sort( solutions.begin(), solutions.end(), []( auto&& a, auto&& b )
        {
            return get< 1 >( a ) < get< 1 >( b );
        } );
︙︙
Added bs/sema/uni-callback.cpp. 


































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include "sema.h"

namespace empathy::sema
{
    // When encountering a callback wrapper during unification, strip it away
    // and unify the content. The wrapper will be put back by the inner unification
    // rule.
    void SetupCallbackUnificationRules( UnificationRuleSet& ruleSet )
    {
        ruleSet.addHalfUnificationRule( TVEC( TSID( callback ), ANYTERM( cb ), ANYTERM( t ) ),
            []( const Term& lhs, UnificationContext& c ) -> UniGen
            {
                auto unwrap = UnwrapCallback( lhs );
                if( !unwrap )
                    co_return;
                auto&& [t,cb] = *unwrap;

                co_yield { t, c };
            } );

        ruleSet.addSymRule( TVEC( TSID( quote ), ANYTERM( t ) ), ANYTERM( rhs ),
            []( const Term& lhs, const Term& rhs, UnificationContext& c ) -> UniGen
            {
                auto unwrap = UnwrapCallback( lhs );
                if( !unwrap )
                    co_return;
                auto&& [t,cb] = *unwrap;

                co_yield Unify( t, rhs, c );
            }  );
    }
}
Changes to bs/sema/uni-quote.h. 
1
2
3
4
5




6
7
8
9
10
11
12

#ifndef EMPATHY_SEMA_UNI_QUOTE_H
#define EMPATHY_SEMA_UNI_QUOTE_H

namespace empathy::sema
{




    extern Term Quote( const Term& t );
    extern optional< Term > Unquote( const Term& t );

    extern void SetupQuoteUnificationRules( UnificationRuleSet& ruleSet );
}

#endif






>
>
>
>








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#ifndef EMPATHY_SEMA_UNI_QUOTE_H
#define EMPATHY_SEMA_UNI_QUOTE_H

namespace empathy::sema
{
    // Expressions can be quoted so that they aren't recursed into during
    // unification. This allows to carry unification patterns around (like function
    // signatures) without them causing an unification failure because their holes remain
    // unresolved.
    extern Term Quote( const Term& t );
    extern optional< Term > Unquote( const Term& t );

    extern void SetupQuoteUnificationRules( UnificationRuleSet& ruleSet );
}

#endif
Changes to bs/sema/uni-ruleset.cpp. 
1
2
3
4
5
6
7
8

9
10
11
12
13
14
15

#include "sema.h"

using namespace empathy;
using namespace empathy::sema;

UnificationRuleSet::UnificationRuleSet()
{
    SetupBasicUnificationRules( *this );

    SetupHoleUnificationRules( *this );
    Setup3WayUnificationRules( *this );
    SetupQuoteUnificationRules( *this );
}

void UnificationRuleSet::addSymRule( const Term& pat, UniFunc f )
{









>








1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include "sema.h"

using namespace empathy;
using namespace empathy::sema;

UnificationRuleSet::UnificationRuleSet()
{
    SetupBasicUnificationRules( *this );
    SetupCallbackUnificationRules( *this );
    SetupHoleUnificationRules( *this );
    Setup3WayUnificationRules( *this );
    SetupQuoteUnificationRules( *this );
}

void UnificationRuleSet::addSymRule( const Term& pat, UniFunc f )
{
︙︙
Fossil 2.26 [1205ec86cb] 2025-04-30 16:57:32
This page was generated in about 0.023s