L2.cps_convert

  1from collections.abc import Callable, Sequence
  2from functools import partial
  3
  4from L1 import syntax as L1
  5
  6from L2 import syntax as L2
  7
  8
  9def cps_convert_term(
 10    term: L2.Term,
 11    m: Callable[[L1.Identifier], L1.Statement],
 12    fresh: Callable[[str], str],
 13) -> L1.Statement:
 14    _term = partial(cps_convert_term, fresh=fresh)
 15    _terms = partial(cps_convert_terms, fresh=fresh)
 16
 17    match term:
 18        case L2.Let(bindings=bindings, body=body):
 19            result = _term(body, m)
 20
 21            for name, value in reversed(bindings):
 22                result = _term(value, lambda value: L1.Copy(destination=name, source=value, then=result))
 23
 24            return result
 25
 26        case L2.Reference(name=name):
 27            return m(name)
 28
 29        case L2.Abstract(parameters=parameters, body=body):
 30            tmp = fresh("t")
 31            k = fresh("k")
 32            return L1.Abstract(
 33                destination=tmp,
 34                parameters=[*parameters, k],
 35                body=_term(body, lambda body: L1.Apply(target=k, arguments=[body])),
 36                then=m(tmp),
 37            )
 38
 39        case L2.Apply(target=target, arguments=arguments):
 40            k = fresh("k")
 41            tmp = fresh("t")
 42            return L1.Abstract(
 43                destination=k,
 44                parameters=[tmp],
 45                body=m(tmp),
 46                then=_term(
 47                    target,
 48                    lambda target: _terms(
 49                        arguments,
 50                        lambda arguments: L1.Apply(target=target, arguments=[*arguments, k]),
 51                    ),
 52                ),
 53            )
 54
 55        case L2.Immediate(value=value):
 56            tmp = fresh("t")
 57            return L1.Immediate(destination=tmp, value=value, then=m(tmp))
 58
 59        case L2.Primitive(operator=operator, left=left, right=right):
 60            tmp = fresh("t")
 61            return _term(
 62                left,
 63                lambda left: _term(
 64                    right,
 65                    lambda right: L1.Primitive(destination=tmp, operator=operator, left=left, right=right, then=m(tmp)),
 66                ),
 67            )
 68
 69        case L2.Branch(operator=operator, left=left, right=right, consequent=consequent, otherwise=otherwise):
 70            j = fresh("j")
 71            tmp = fresh("t")
 72            return L1.Abstract(
 73                destination=j,
 74                parameters=[tmp],
 75                body=m(tmp),
 76                then=_term(
 77                    left,
 78                    lambda left: _term(
 79                        right,
 80                        lambda right: L1.Branch(
 81                            operator=operator,
 82                            left=left,
 83                            right=right,
 84                            then=_term(consequent, lambda consequent: L1.Apply(target=j, arguments=[consequent])),
 85                            otherwise=_term(otherwise, lambda otherwise: L1.Apply(target=j, arguments=[otherwise])),
 86                        ),
 87                    ),
 88                ),
 89            )
 90
 91        case L2.Allocate(count=count):
 92            tmp = fresh("t")
 93            return L1.Allocate(destination=tmp, count=count, then=m(tmp))
 94
 95        case L2.Load(base=base, index=index):
 96            tmp = fresh("t")
 97            return _term(
 98                base,
 99                lambda base: L1.Load(destination=tmp, base=base, index=index, then=m(tmp)),
100            )
101
102        # Should double check this
103        case L2.Store(base=base, index=index, value=value):
104            tmp = fresh("t")
105            return _term(
106                base,
107                lambda base: _term(
108                    value,
109                    lambda value: L1.Store(
110                        base=base, index=index, value=value, then=L1.Immediate(destination=tmp, value=0, then=m(tmp))
111                    ),
112                ),
113            )
114
115        case L2.Begin(effects=effects, value=value):  # pragma: no branch
116            return _terms(
117                effects,
118                lambda effects: _term(
119                    value,
120                    lambda value: m(value),
121                ),
122            )
123
124
125def cps_convert_terms(
126    terms: Sequence[L2.Term],
127    k: Callable[[Sequence[L1.Identifier]], L1.Statement],
128    fresh: Callable[[str], str],
129) -> L1.Statement:
130    _term = partial(cps_convert_term, fresh=fresh)
131    _terms = partial(cps_convert_terms, fresh=fresh)
132
133    match terms:
134        case []:
135            return k([])
136
137        case [first, *rest]:
138            return _term(first, lambda first: _terms(rest, lambda rest: k([first, *rest])))
139
140        case _:  # pragma: no cover
141            raise ValueError(terms)
142
143
144def cps_convert_program(
145    program: L2.Program,
146    fresh: Callable[[str], str],
147) -> L1.Program:
148    _term = partial(cps_convert_term, fresh=fresh)
149
150    match program:
151        case L2.Program(parameters=parameters, body=body):  # pragma: no branch
152            return L1.Program(
153                parameters=parameters,
154                body=_term(body, lambda value: L1.Halt(value=value)),
155            )