docs/with_sympy.md

   1 # Symbolic Evaluation with SymPy
   2
   3
   4 ```python
   5 import sympy
   6
   7 from joy.joy import run
   8 from joy.library import UnaryBuiltinWrapper
   9 from joy.utils.pretty_print import TracePrinter
  10 from joy.utils.stack import list_to_stack
  11
  12 from notebook_preamble import D, J, V, define
  13 ```
  14
  15
  16 ```python
  17 sympy.init_printing()
  18 ```
  19
  20 ## [SypPy Symbols](http://docs.sympy.org/latest/modules/core.html#module-sympy.core.symbol)
  21
  22 The SymPy package provides a powerful and elegant ["thunk"](https://en.wikipedia.org/wiki/Thunk) object that can take the place of a numeric value in calculations and "record" the operations performed on it.
  23
  24 We can create some of these objects and put them on the Joy stack:
  25
  26
  27 ```python
  28 stack = list_to_stack(sympy.symbols('c a b'))
  29 ```
  30
  31 If we evaluate the `quadratic` program
  32
  33     over [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2
  34
  35 The [SypPy Symbols](http://docs.sympy.org/latest/modules/core.html#module-sympy.core.symbol) will become the symbolic expression of the math operations.  Unfortunately, the library `sqrt` function doesn't work with the SymPy objects:
  36
  37
  38 ```python
  39 viewer = TracePrinter()
  40 try:
  41     run('over [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2', stack, D, viewer.viewer)
  42 except Exception, e:
  43     print e
  44 viewer.print_()
  45 ```
  46
  47     can't convert expression to float
  48                                                 b a c . over [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2
  49                                               b a c a . [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2
  50     b a c a [[[neg] dupdip sqr 4] dipd * * - sqrt pm] . dip 2 * [/] cons app2
  51                                                 b a c . [[neg] dupdip sqr 4] dipd * * - sqrt pm a 2 * [/] cons app2
  52                            b a c [[neg] dupdip sqr 4] . dipd * * - sqrt pm a 2 * [/] cons app2
  53                                                     b . [neg] dupdip sqr 4 a c * * - sqrt pm a 2 * [/] cons app2
  54                                               b [neg] . dupdip sqr 4 a c * * - sqrt pm a 2 * [/] cons app2
  55                                                     b . neg b sqr 4 a c * * - sqrt pm a 2 * [/] cons app2
  56                                                    -b . b sqr 4 a c * * - sqrt pm a 2 * [/] cons app2
  57                                                  -b b . sqr 4 a c * * - sqrt pm a 2 * [/] cons app2
  58                                                  -b b . dup mul 4 a c * * - sqrt pm a 2 * [/] cons app2
  59                                                -b b b . mul 4 a c * * - sqrt pm a 2 * [/] cons app2
  60                                               -b b**2 . 4 a c * * - sqrt pm a 2 * [/] cons app2
  61                                             -b b**2 4 . a c * * - sqrt pm a 2 * [/] cons app2
  62                                           -b b**2 4 a . c * * - sqrt pm a 2 * [/] cons app2
  63                                         -b b**2 4 a c . * * - sqrt pm a 2 * [/] cons app2
  64                                         -b b**2 4 a*c . * - sqrt pm a 2 * [/] cons app2
  65                                         -b b**2 4*a*c . - sqrt pm a 2 * [/] cons app2
  66                                      -b -4*a*c + b**2 . sqrt pm a 2 * [/] cons app2
  67
  68
  69 We can pick out that first symbolic expression obect from the Joy stack:
  70
  71
  72 ```python
  73 S, E = viewer.history[-1]
  74 ```
  75
  76
  77 ```python
  78 q = S[0]
  79 q
  80 ```
  81
  82
  83
  84
  85 $$- 4 a c + b^{2}$$
  86
  87
  88
  89 The Python `math.sqrt()` function causes the "can't convert expression to float" exception but `sympy.sqrt()` does not:
  90
  91
  92 ```python
  93 sympy.sqrt(q)
  94 ```
  95
  96
  97
  98
  99 $$\sqrt{- 4 a c + b^{2}}$$
 100
 101
 102
 103 ## Use `sympy.sqrt`
 104 This is easy to fix.
 105
 106
 107 ```python
 108 D['sqrt'] = UnaryBuiltinWrapper(sympy.sqrt)
 109 ```
 110
 111 Now it works just fine.
 112
 113
 114 ```python
 115 (root1, (root2, _)) = run('over [[[neg] dupdip sqr 4] dipd * * - sqrt pm] dip 2 * [/] cons app2', stack, D)[0]
 116 ```
 117
 118
 119 ```python
 120 root1
 121 ```
 122
 123
 124
 125
 126 $$\frac{1}{2 a} \left(- b - \sqrt{- 4 a c + b^{2}}\right)$$
 127
 128
 129
 130
 131 ```python
 132 root2
 133 ```
 134
 135
 136
 137
 138 $$\frac{1}{2 a} \left(- b + \sqrt{- 4 a c + b^{2}}\right)$$
 139
 140
 141
 142 At some point I will probably make an optional library of Joy wrappers for SymPy functions, and either load it automatically if SymPy installation is available or have a CLI switch or something.  There's a huge amount of incredibly useful stuff and I don't see why Joy shouldn't expose another interface for using it.  (As an example, the symbolic expressions can be "lambdafied" into very fast versions, i.e. a function that takes `a`, `b`, and `c` and computes the value of the root using just low-level fast code, bypassing Joy and Python.  Also, Numpy, &c.)
 143
 144 ## Partial Evaluation
 145
 146 [Futamura projections](https://en.wikipedia.org/wiki/Futamura_projection)
 147
 148 Starting with the example from [Partial Computation of Programs](http://hdl.handle.net/2433/103401)
 149 by [Yoshihiko Futamura](http://fi.ftmr.info/) of a function to compute `u` to the `k`th power:
 150
 151
 152 ```python
 153 def F(u, k):
 154     z = 1
 155     while k != 0:
 156         if odd(k):
 157             z = z * u
 158         k = k / 2
 159         u = u * u
 160     return z
 161 ```
 162
 163 Partial evaluation with `k = 5`:
 164
 165
 166 ```python
 167 def F5(u):
 168     z = 1 * u
 169     u = u * u
 170     u = u * u
 171     z = z * u
 172     return z
 173 ```
 174
 175 Translate `F(u, k)` to Joy
 176
 177     u k 1                    # z = 1
 178         [pop] [Fw] while     # the while statement
 179         popopd               # discard u k, "return" z
 180
 181 What's Fw?
 182
 183
 184     u k z [pop odd] [Ft] [] ifte   # the if statement
 185           [2 //] dip               # k = k / 2  floordiv
 186           [sqr] dipd               # u = u * u
 187
 188           [[sqr] dip 2 //] dip     # We can merge last two lines.
 189
 190 Helper function Ft (to compute z = z * u).
 191
 192
 193        u k z Ft
 194     ---------------
 195        u k u*z
 196
 197
 198     Ft == [over] dip *
 199
 200 Putting it together:
 201
 202     Ft == [over] dip *
 203     Fb == [[sqr] dip 2 //] dip
 204     Fw == [pop odd] [Ft] [] ifte Fb
 205      F == 1 [pop] [Fw] while popopd
 206
 207
 208 ```python
 209 define('odd == 2 %')
 210 ```
 211
 212
 213 ```python
 214 define('Ft == [over] dip *')
 215 ```
 216
 217
 218 ```python
 219 define('Fb == [[sqr] dip 2 //] dip')
 220 ```
 221
 222
 223 ```python
 224 define('Fw == [pop odd] [Ft] [] ifte Fb')
 225 ```
 226
 227
 228 ```python
 229 define('F == 1 [pop] [Fw] while popopd')
 230 ```
 231
 232 Try it out:
 233
 234
 235 ```python
 236 J('2 5 F')
 237 ```
 238
 239     32
 240
 241
 242 In order to elide the tests let's define special versions of `while` and `ifte`:
 243
 244
 245 ```python
 246 from joy.joy import joy
 247 from joy.library import FunctionWrapper
 248 from joy.parser import Symbol
 249 from joy.utils.stack import concat
 250
 251
 252 S_while = Symbol('while')
 253
 254
 255 @FunctionWrapper
 256 def while_(S, expression, dictionary):
 257     '''[if] [body] while'''
 258     (body, (if_, stack)) = S
 259     if joy(stack, if_, dictionary)[0][0]:
 260         expression = concat(body, (if_, (body, (S_while, expression))))
 261     return stack, expression, dictionary
 262
 263
 264 @FunctionWrapper
 265 def ifte(stack, expression, dictionary):
 266     '''[if] [then] [else] ifte'''
 267     (else_, (then, (if_, stack))) = stack
 268     if_res = joy(stack, if_, dictionary)[0][0]
 269     quote = then if if_res else else_
 270     expression = concat(quote, expression)
 271     return (stack, expression, dictionary)
 272
 273
 274 D['ifte'] = ifte
 275 D['while'] = while_
 276 ```
 277
 278 And with a SymPy symbol for the `u` argument:
 279
 280
 281 ```python
 282 stack = list_to_stack([5, sympy.symbols('u')])
 283 viewer = TracePrinter()
 284 try:
 285     (result, _) = run('F', stack, D, viewer.viewer)[0]
 286 except Exception, e:
 287     print e
 288 viewer.print_()
 289 ```
 290
 291                              u 5 . F
 292                              u 5 . 1 [pop] [Fw] while popopd
 293                            u 5 1 . [pop] [Fw] while popopd
 294                      u 5 1 [pop] . [Fw] while popopd
 295                 u 5 1 [pop] [Fw] . while popopd
 296                            u 5 1 . Fw [pop] [Fw] while popopd
 297                            u 5 1 . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd
 298                  u 5 1 [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd
 299             u 5 1 [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd
 300          u 5 1 [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd
 301                            u 5 1 . Ft Fb [pop] [Fw] while popopd
 302                            u 5 1 . [over] dip * Fb [pop] [Fw] while popopd
 303                     u 5 1 [over] . dip * Fb [pop] [Fw] while popopd
 304                              u 5 . over 1 * Fb [pop] [Fw] while popopd
 305                            u 5 u . 1 * Fb [pop] [Fw] while popopd
 306                          u 5 u 1 . * Fb [pop] [Fw] while popopd
 307                            u 5 u . Fb [pop] [Fw] while popopd
 308                            u 5 u . [[sqr] dip 2 //] dip [pop] [Fw] while popopd
 309           u 5 u [[sqr] dip 2 //] . dip [pop] [Fw] while popopd
 310                              u 5 . [sqr] dip 2 // u [pop] [Fw] while popopd
 311                        u 5 [sqr] . dip 2 // u [pop] [Fw] while popopd
 312                                u . sqr 5 2 // u [pop] [Fw] while popopd
 313                                u . dup mul 5 2 // u [pop] [Fw] while popopd
 314                              u u . mul 5 2 // u [pop] [Fw] while popopd
 315                             u**2 . 5 2 // u [pop] [Fw] while popopd
 316                           u**2 5 . 2 // u [pop] [Fw] while popopd
 317                         u**2 5 2 . // u [pop] [Fw] while popopd
 318                           u**2 2 . u [pop] [Fw] while popopd
 319                         u**2 2 u . [pop] [Fw] while popopd
 320                   u**2 2 u [pop] . [Fw] while popopd
 321              u**2 2 u [pop] [Fw] . while popopd
 322                         u**2 2 u . Fw [pop] [Fw] while popopd
 323                         u**2 2 u . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd
 324               u**2 2 u [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd
 325          u**2 2 u [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd
 326       u**2 2 u [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd
 327                         u**2 2 u . Fb [pop] [Fw] while popopd
 328                         u**2 2 u . [[sqr] dip 2 //] dip [pop] [Fw] while popopd
 329        u**2 2 u [[sqr] dip 2 //] . dip [pop] [Fw] while popopd
 330                           u**2 2 . [sqr] dip 2 // u [pop] [Fw] while popopd
 331                     u**2 2 [sqr] . dip 2 // u [pop] [Fw] while popopd
 332                             u**2 . sqr 2 2 // u [pop] [Fw] while popopd
 333                             u**2 . dup mul 2 2 // u [pop] [Fw] while popopd
 334                        u**2 u**2 . mul 2 2 // u [pop] [Fw] while popopd
 335                             u**4 . 2 2 // u [pop] [Fw] while popopd
 336                           u**4 2 . 2 // u [pop] [Fw] while popopd
 337                         u**4 2 2 . // u [pop] [Fw] while popopd
 338                           u**4 1 . u [pop] [Fw] while popopd
 339                         u**4 1 u . [pop] [Fw] while popopd
 340                   u**4 1 u [pop] . [Fw] while popopd
 341              u**4 1 u [pop] [Fw] . while popopd
 342                         u**4 1 u . Fw [pop] [Fw] while popopd
 343                         u**4 1 u . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd
 344               u**4 1 u [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd
 345          u**4 1 u [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd
 346       u**4 1 u [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd
 347                         u**4 1 u . Ft Fb [pop] [Fw] while popopd
 348                         u**4 1 u . [over] dip * Fb [pop] [Fw] while popopd
 349                  u**4 1 u [over] . dip * Fb [pop] [Fw] while popopd
 350                           u**4 1 . over u * Fb [pop] [Fw] while popopd
 351                      u**4 1 u**4 . u * Fb [pop] [Fw] while popopd
 352                    u**4 1 u**4 u . * Fb [pop] [Fw] while popopd
 353                      u**4 1 u**5 . Fb [pop] [Fw] while popopd
 354                      u**4 1 u**5 . [[sqr] dip 2 //] dip [pop] [Fw] while popopd
 355     u**4 1 u**5 [[sqr] dip 2 //] . dip [pop] [Fw] while popopd
 356                           u**4 1 . [sqr] dip 2 // u**5 [pop] [Fw] while popopd
 357                     u**4 1 [sqr] . dip 2 // u**5 [pop] [Fw] while popopd
 358                             u**4 . sqr 1 2 // u**5 [pop] [Fw] while popopd
 359                             u**4 . dup mul 1 2 // u**5 [pop] [Fw] while popopd
 360                        u**4 u**4 . mul 1 2 // u**5 [pop] [Fw] while popopd
 361                             u**8 . 1 2 // u**5 [pop] [Fw] while popopd
 362                           u**8 1 . 2 // u**5 [pop] [Fw] while popopd
 363                         u**8 1 2 . // u**5 [pop] [Fw] while popopd
 364                           u**8 0 . u**5 [pop] [Fw] while popopd
 365                      u**8 0 u**5 . [pop] [Fw] while popopd
 366                u**8 0 u**5 [pop] . [Fw] while popopd
 367           u**8 0 u**5 [pop] [Fw] . while popopd
 368                      u**8 0 u**5 . popopd
 369                             u**5 .
 370
 371
 372
 373 ```python
 374 result
 375 ```
 376
 377
 378
 379
 380 $$u^{5}$$
 381
 382
 383
 384 Let's try partial evaluation by hand and use a "stronger" thunk.
 385
 386 Caret underscoring indicates terms that form thunks.  When an arg is unavailable for a computation we just postpone it until the arg becomes available and in the meantime treat the pending computation as one unit.
 387
 388                              u 5 . F
 389                              u 5 . 1 [pop] [Fw] while popopd
 390                            u 5 1 . [pop] [Fw] while popopd
 391                      u 5 1 [pop] . [Fw] while popopd
 392                 u 5 1 [pop] [Fw] . while popopd
 393                            u 5 1 . Fw [pop] [Fw] while popopd
 394                            u 5 1 . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd
 395                  u 5 1 [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd
 396             u 5 1 [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd
 397          u 5 1 [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd
 398                            u 5 1 . Ft Fb [pop] [Fw] while popopd
 399                            u 5 1 . [over] dip * Fb [pop] [Fw] while popopd
 400                     u 5 1 [over] . dip * Fb [pop] [Fw] while popopd
 401                              u 5 . over 1 * Fb [pop] [Fw] while popopd
 402                            u 5 u . 1 * Fb [pop] [Fw] while popopd
 403                          u 5 u 1 . * Fb [pop] [Fw] while popopd
 404                            u 5 u . Fb [pop] [Fw] while popopd
 405                            u 5 u . [[sqr] dip 2 //] dip [pop] [Fw] while popopd
 406           u 5 u [[sqr] dip 2 //] . dip [pop] [Fw] while popopd
 407                              u 5 . [sqr] dip 2 // u [pop] [Fw] while popopd
 408                        u 5 [sqr] . dip 2 // u [pop] [Fw] while popopd
 409                                u . sqr 5 2 // u [pop] [Fw] while popopd
 410                                u . dup mul 5 2 // u [pop] [Fw] while popopd
 411                          u dup * . 5 2 // u [pop] [Fw] while popopd
 412                          ^^^^^^^
 413
 414
 415              u dup * 2 u [pop] [Fw] . while popopd
 416                         u dup * 2 u . Fw [pop] [Fw] while popopd
 417                         u dup * 2 u . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd
 418               u dup * 2 u [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd
 419          u dup * 2 u [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd
 420       u dup * 2 u [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd
 421                         u dup * 2 u . Fb [pop] [Fw] while popopd
 422                         u dup * 2 u . [[sqr] dip 2 //] dip [pop] [Fw] while popopd
 423        u dup * 2 u [[sqr] dip 2 //] . dip [pop] [Fw] while popopd
 424                           u dup * 2 . [sqr] dip 2 // u [pop] [Fw] while popopd
 425                     u dup * 2 [sqr] . dip 2 // u [pop] [Fw] while popopd
 426                             u dup * . sqr 2 2 // u [pop] [Fw] while popopd
 427                             u dup * . dup mul 2 2 // u [pop] [Fw] while popopd
 428                       u dup * dup * . 2 2 // u [pop] [Fw] while popopd
 429                       ^^^^^^^^^^^^^
 430
 431
 432
 433
 434 w/ `K == u dup * dup *`
 435
 436                  K 1 u [pop] [Fw] . while popopd
 437                             K 1 u . Fw [pop] [Fw] while popopd
 438                             K 1 u . [pop odd] [Ft] [] ifte Fb [pop] [Fw] while popopd
 439                   K 1 u [pop odd] . [Ft] [] ifte Fb [pop] [Fw] while popopd
 440              K 1 u [pop odd] [Ft] . [] ifte Fb [pop] [Fw] while popopd
 441           K 1 u [pop odd] [Ft] [] . ifte Fb [pop] [Fw] while popopd
 442                             K 1 u . Ft Fb [pop] [Fw] while popopd
 443                             K 1 u . [over] dip * Fb [pop] [Fw] while popopd
 444                      K 1 u [over] . dip * Fb [pop] [Fw] while popopd
 445                               K 1 . over u * Fb [pop] [Fw] while popopd
 446                             K 1 K . u * Fb [pop] [Fw] while popopd
 447                           K 1 K u . * Fb [pop] [Fw] while popopd
 448                         K 1 K u * . Fb [pop] [Fw] while popopd
 449                             ^^^^^
 450
 451 w/ `L == K u *`
 452
 453                          K 1 L . Fb [pop] [Fw] while popopd
 454                          K 1 L . [[sqr] dip 2 //] dip [pop] [Fw] while popopd
 455         K 1 L [[sqr] dip 2 //] . dip [pop] [Fw] while popopd
 456                            K 1 . [sqr] dip 2 // L [pop] [Fw] while popopd
 457                      K 1 [sqr] . dip 2 // L [pop] [Fw] while popopd
 458                              K . sqr 1 2 // L [pop] [Fw] while popopd
 459                              K . dup mul 1 2 // L [pop] [Fw] while popopd
 460                            K K . mul 1 2 // L [pop] [Fw] while popopd
 461                          K K * . 1 2 // L [pop] [Fw] while popopd
 462                          ^^^^^
 463                          K K * . 1 2 // L [pop] [Fw] while popopd
 464                        K K * 1 . 2 // L [pop] [Fw] while popopd
 465                      K K * 1 2 . // L [pop] [Fw] while popopd
 466                        K K * 0 . L [pop] [Fw] while popopd
 467                      K K * 0 L . [pop] [Fw] while popopd
 468                K K * 0 L [pop] . [Fw] while popopd
 469           K K * 0 L [pop] [Fw] . while popopd
 470           ^^^^^
 471                      K K * 0 L . popopd
 472                              L .
 473
 474 So:
 475
 476     K == u dup * dup *
 477     L == K u *
 478
 479 Our result "thunk" would be:
 480
 481     u dup * dup * u *
 482
 483 Mechanically, you could do:
 484
 485     u      dup * dup *  u   *
 486     u u   [dup * dup *] dip *
 487     u dup [dup * dup *] dip *
 488
 489
 490     F5 == dup [dup * dup *] dip *
 491
 492 But we can swap the two arguments to the final `*` to get all mentions of `u` to the left:
 493
 494
 495     u u dup * dup * *
 496
 497
 498 Then de-duplicate "u":
 499
 500
 501     u dup dup * dup * *
 502
 503
 504 To arrive at a startlingly elegant form for F5:
 505
 506
 507     F5 == dup dup * dup * *
 508
 509
 510 ```python
 511 stack = list_to_stack([sympy.symbols('u')])
 512 viewer = TracePrinter()
 513 try:
 514     (result, _) = run('dup dup * dup * *', stack, D, viewer.viewer)[0]
 515 except Exception, e:
 516     print e
 517 viewer.print_()
 518 result
 519 ```
 520
 521               u . dup dup * dup * *
 522             u u . dup * dup * *
 523           u u u . * dup * *
 524          u u**2 . dup * *
 525     u u**2 u**2 . * *
 526          u u**4 . *
 527            u**5 .
 528
 529
 530
 531
 532
 533 $$u^{5}$$
 534
 535
 536
 537 I'm not sure how to implement these kinds of thunks.  I think you have to have support in the interpreter, or you have to modify all of the functions like `dup` to check for thunks in their inputs.
 538
 539 Working on the compiler, from this:
 540
 541     dup dup * dup * *
 542
 543 We can already generate:
 544
 545     ---------------------------------
 546     (a0, stack) = stack
 547     a1 = mul(a0, a0)
 548     a2 = mul(a1, a1)
 549     a3 = mul(a2, a0)
 550     stack = (a3, stack)
 551     ---------------------------------
 552
 553 This is pretty old stuff...  (E.g. from 1999, M. Anton Ertl [Compilation of Stack-Based Languages](http://www.complang.tuwien.ac.at/projects/rafts.html) he goes a lot further for Forth.)
 554
 555
 556 ```python
 557
 558 ```
 559
 560 ## "A Transformation Based Approach to Semantics-Directed Code Generation"
 561
 562 by Arthur Nunes-Harwitt
 563
 564 https://dl.acm.org/citation.cfm?doid=2635648.2635652
 565
 566
 567
 568
 569 ```python
 570 def m(x, y): return x * y
 571
 572 print m(2, 3)
 573 ```
 574
 575     6
 576
 577
 578
 579 ```python
 580 def m(x): return lambda y: x * y
 581
 582 print m(2)(3)
 583 ```
 584
 585     6
 586
 587
 588
 589 ```python
 590 def m(x): return "lambda y: %(x)s * y" % locals()
 591
 592 print m(2)
 593 print eval(m(2))(3)
 594 ```
 595
 596     lambda y: 2 * y
 597     6
 598
 599
 600 In Joy:
 601
 602     m == [*] cons
 603
 604     3 2 m i
 605     3 2 [*] cons i
 606     3 [2 *] i
 607     3 2 *
 608     6
 609
 610
 611
 612 ```python
 613 def p(n, b): # original
 614     return 1 if n == 0 else b * p(n - 1, b)
 615
 616
 617 def p(n): # curried
 618     return lambda b: 1 if n == 0 else b * p(n - 1, b)
 619
 620
 621 def p(n): # quoted
 622     return "lambda b: 1 if %(n)s == 0 else b * p(%(n)s - 1, b)"  % locals()
 623
 624
 625 print p(3)
 626 ```
 627
 628     lambda b: 1 if 3 == 0 else b * p(3 - 1, b)
 629
 630
 631 Original
 632
 633     p == [0 =] [popop 1] [-- over] [dip *] genrec
 634
 635     b n p
 636     b n [0 =] [popop 1] [-- over [p] dip *]
 637
 638     b n -- over [p] dip *
 639     b n-1  over [p] dip *
 640     b n-1 b [p] dip *
 641     b n-1 p b *
 642
 643
 644 curried, quoted
 645
 646                         n p
 647     ---------------------------------------------
 648        [[n 0 =] [pop 1] [dup n --] [*] genrec]
 649
 650
 651 ```python
 652 def p(n): # lambda lowered
 653     return (
 654         lambda b: 1
 655         if n == 0 else
 656         lambda b: b * p(n - 1, b)
 657         )
 658
 659
 660 def p(n): # lambda lowered quoted
 661     return (
 662         "lambda b: 1"
 663         if n == 0 else
 664         "lambda b: b * p(%(n)s - 1, b)"  % locals()
 665         )
 666
 667 print p(3)
 668 ```
 669
 670     lambda b: b * p(3 - 1, b)
 671
 672
 673
 674     p == [0 =] [[pop 1]] [ [-- [dup] dip p *] cons ]ifte
 675
 676
 677     3 p
 678     3 [-- [dup] dip p *] cons
 679     [3 -- [dup] dip p *]
 680
 681
 682
 683 ```python
 684 def p(n): # expression lifted
 685     if n == 0:
 686         return lambda b: 1
 687     f = p(n - 1)
 688     return lambda b: b * f(b)
 689
 690
 691 print p(3)(2)
 692 ```
 693
 694     8
 695
 696
 697
 698 ```python
 699 def p(n): # quoted
 700     if n == 0:
 701         return "lambda b: 1"
 702     f = p(n - 1)
 703     return "lambda b: b * (%(f)s)(b)"  % locals()
 704
 705 print p(3)
 706 print eval(p(3))(2)
 707 ```
 708
 709     lambda b: b * (lambda b: b * (lambda b: b * (lambda b: 1)(b))(b))(b)
 710     8
 711
 712
 713     p == [0 =] [pop [pop 1]] [-- p [dupdip *] cons] ifte
 714
 715
 716     3 p
 717     3 -- p [dupdip *] cons
 718     2    p [dupdip *] cons
 719     2 -- p [dupdip *] cons [dupdip *] cons
 720     1    p [dupdip *] cons [dupdip *] cons
 721     1 -- p [dupdip *] cons [dupdip *] cons [dupdip *] cons
 722     0    p [dupdip *] cons [dupdip *] cons [dupdip *] cons
 723     0 pop [pop 1] [dupdip *] cons [dupdip *] cons [dupdip *] cons
 724     [pop 1] [dupdip *] cons [dupdip *] cons [dupdip *] cons
 725     ...
 726     [[[[pop 1] dupdip *] dupdip *] dupdip *]
 727
 728
 729     2 [[[[pop 1] dupdip *] dupdip *] dupdip *] i
 730     2  [[[pop 1] dupdip *] dupdip *] dupdip *
 731     2   [[pop 1] dupdip *] dupdip *  2 *
 732     2    [pop 1] dupdip *  2      *  2 *
 733     2     pop 1  2      *  2      *  2 *
 734               1  2      *  2      *  2 *
 735
 736
 737
 738     p == [0 =] [pop [pop 1]] [--  p    [dupdip *] cons] ifte
 739     p == [0 =] [pop [pop 1]] [-- [p] i [dupdip *] cons] ifte
 740     p == [0 =] [pop [pop 1]] [--]   [i [dupdip *] cons] genrec
 741
 742
 743 ```python
 744 define('p == [0 =] [pop [pop 1]] [--] [i [dupdip *] cons] genrec')
 745 ```
 746
 747
 748 ```python
 749 J('3 p')
 750 ```
 751
 752     [[[[pop 1] dupdip *] dupdip *] dupdip *]
 753
 754
 755
 756 ```python
 757 V('2 [[[[pop 1] dupdip *] dupdip *] dupdip *] i')
 758 ```
 759
 760                                                . 2 [[[[pop 1] dupdip *] dupdip *] dupdip *] i
 761                                              2 . [[[[pop 1] dupdip *] dupdip *] dupdip *] i
 762     2 [[[[pop 1] dupdip *] dupdip *] dupdip *] . i
 763                                              2 . [[[pop 1] dupdip *] dupdip *] dupdip *
 764                2 [[[pop 1] dupdip *] dupdip *] . dupdip *
 765                                              2 . [[pop 1] dupdip *] dupdip * 2 *
 766                           2 [[pop 1] dupdip *] . dupdip * 2 *
 767                                              2 . [pop 1] dupdip * 2 * 2 *
 768                                      2 [pop 1] . dupdip * 2 * 2 *
 769                                              2 . pop 1 2 * 2 * 2 *
 770                                                . 1 2 * 2 * 2 *
 771                                              1 . 2 * 2 * 2 *
 772                                            1 2 . * 2 * 2 *
 773                                              2 . 2 * 2 *
 774                                            2 2 . * 2 *
 775                                              4 . 2 *
 776                                            4 2 . *
 777                                              8 .
 778
 779
 780
 781 ```python
 782 stack = list_to_stack([sympy.symbols('u')])
 783 (result, s) = run('p i', stack, D)[0]
 784 result
 785 ```
 786
 787 From this:
 788
 789     p == [0 =] [pop pop 1] [-- over] [dip *] genrec
 790
 791 To this:
 792
 793     p == [0 =] [pop [pop 1]] [--] [i [dupdip *] cons] genrec
 794
 795
 796
 797
 798 ## Try it with `F()`:
 799
 800
 801 ```python
 802 def odd(n): return n % 2
 803
 804
 805 def F(u, k):
 806     z = 1
 807     while k != 0:
 808         if odd(k):
 809             z = z * u
 810         k = k / 2
 811         u = u * u
 812     return z
 813
 814 F(2, 5)
 815 ```
 816
 817
 818 ```python
 819 def F(k):
 820     def _F(u, k=k):
 821         z = 1
 822         while k != 0:
 823             if odd(k):
 824                 z = z * u
 825             k = k / 2
 826             u = u * u
 827         return z
 828     return _F
 829
 830 F(5)(2)
 831 ```
 832
 833
 834 ```python
 835 def F(k):
 836     def _F(u, k=k):
 837         if k == 0:
 838             z = 1
 839         else:
 840             z = F(k / 2)(u)
 841             z *= z
 842             if odd(k):
 843                 z = z * u
 844         return z
 845     return _F
 846
 847 F(5)(2)
 848 ```
 849
 850
 851 ```python
 852 def F(k):
 853     if k == 0:
 854         z = lambda u: 1
 855     else:
 856         f = F(k / 2)
 857         def z(u):
 858             uu = f(u)
 859             uu *= uu
 860             return uu * u if odd(k) else uu
 861     return z
 862
 863 F(5)(2)
 864 ```
 865
 866
 867 ```python
 868 def F(k):
 869     if k == 0:
 870         z = lambda u: 1
 871     else:
 872         f = F(k / 2)
 873         if odd(k):
 874             z = lambda u: (lambda fu, u: fu * fu * u)(f(u), u)
 875         else:
 876             z = lambda u: (lambda fu, u: fu * fu)(f(u), u)
 877     return z
 878
 879 F(5)(2)
 880 ```
 881
 882
 883 ```python
 884 def F(k):
 885     if k == 0:
 886         z = "lambda u: 1"
 887     else:
 888         f = F(k / 2)
 889         if odd(k):
 890             z = "lambda u: (lambda fu, u: fu * fu * u)((%(f)s)(u), u)" % locals()
 891         else:
 892             z = "lambda u: (lambda fu, u: fu * fu)((%(f)s)(u), u)" % locals()
 893     return z
 894
 895 source = F(5)
 896 print source
 897 eval(source)(2)
 898 ```
 899
 900 Hmm...
 901
 902
 903 ```python
 904 for n in range(4):
 905     print F(n)
 906 ```
 907
 908
 909 ```python
 910 def F(k):
 911     if k == 0:
 912         z = "lambda u: 1"
 913     elif k == 1:
 914         z = "lambda u: u"
 915     else:
 916         f = F(k / 2)
 917         if odd(k):
 918             z = "lambda u: (lambda fu, u: fu * fu * u)((%(f)s)(u), u)" % locals()
 919         else:
 920             z = "lambda u: (lambda fu, u: fu * fu)((%(f)s)(u), u)" % locals()
 921     return z
 922
 923 source = F(5)
 924 print source
 925 eval(source)(2)
 926 ```
 927
 928
 929 ```python
 930 for n in range(4):
 931     print F(n)
 932 ```
 933
 934
 935 ```python
 936 def F(k):
 937     if k == 0:
 938         z = "lambda u: 1"
 939     elif k == 1:
 940         z = "lambda u: u"
 941     else:
 942         m = k / 2
 943         if odd(k):
 944             if m == 0:
 945                 z = "lambda u: 1"
 946             elif m == 1:
 947                 z = "lambda u: u * u * u"
 948             else:
 949                 z = "lambda u: (lambda fu, u: fu * fu * u)((%s)(u), u)" % F(m)
 950         else:
 951             if m == 0:
 952                 z = "lambda u: 1"
 953             elif m == 1:
 954                 z = "lambda u: u * u"
 955             else:
 956                 z = "lambda u: (lambda u: u * u)((%s)(u))" % F(m)
 957     return z
 958
 959 source = F(5)
 960 print source
 961 eval(source)(2)
 962 ```
 963
 964
 965 ```python
 966 def F(k):
 967     if k == 0:
 968         z = "lambda u: 1"
 969     elif k == 1:
 970         z = "lambda u: u"
 971     else:
 972         m = k / 2
 973         if m == 0:
 974             z = "lambda u: 1"
 975
 976         elif odd(k):
 977             if m == 1:
 978                 z = "lambda u: u * u * u"
 979             else:
 980                 z = "lambda u: (lambda fu, u: fu * fu * u)((%s)(u), u)" % F(m)
 981         else:
 982             if m == 1:
 983                 z = "lambda u: u * u"
 984             else:
 985                 z = "lambda u: (lambda u: u * u)((%s)(u))" % F(m)
 986     return z
 987
 988 source = F(5)
 989 print source
 990 eval(source)(2)
 991 ```
 992
 993
 994 ```python
 995 for n in range(7):
 996     source = F(n)
 997     print n, '%2i' % eval(source)(2), source
 998 ```
 999
1000 So that gets pretty good, eh?
1001
1002
1003 But looking back at the definition in Joy, it doesn't seem easy to directly apply this technique to Joy code:
1004
1005     Ft == [over] dip *
1006     Fb == [[sqr] dip 2 //] dip
1007     Fw == [pop odd] [Ft] [] ifte Fb
1008      F == 1 [pop] [Fw] while popopd
1009
1010
1011 But a direct translation of the Python code..?
1012
1013
1014     F == [
1015       [[0 =] [pop 1]]
1016       [[1 =] []]
1017       [_F.0]
1018       ] cond
1019
1020     _F.0 == dup 2 // [
1021       [[0 =]     [pop 1]]
1022       [[pop odd] _F.1]
1023       [_F.2]
1024       ] cond
1025
1026     _F.1 == [1 =] [pop [dup dup * *]] [popd F [dupdip over * *] cons] ifte
1027     _F.2 == [1 =] [pop [dup *]]       [popd F [i dup *]         cons] ifte
1028
1029
1030 Try it:
1031
1032     5 F
1033     5 [ [[0 =] [pop 1]] [[1 =] []] [_F.0] ] cond
1034     5 _F.0
1035     5 dup 2 // [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond
1036     5 5 2 //   [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond
1037
1038     5 2 [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond
1039     5 2 _F.1
1040     5 2 [1 =] [popop [dup dup * *]] [popd F [dupdip over * *] cons] ifte
1041     5 2                              popd F [dupdip over * *] cons
1042       2                                   F [dupdip over * *] cons
1043
1044     2 F [dupdip over * *] cons
1045
1046     2 F
1047     2 [ [[0 =] [pop 1]] [[1 =] []] [_F.0] ] cond
1048     2 _F.0
1049     2 dup 2 // [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond
1050     2 2 2 // [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond
1051     2 1 [ [[0 =] [pop 1]] [[pop odd] _F.1] [_F.2] ] cond
1052     2 1 _F.2
1053     2 1 [1 =] [popop [dup *]] [popd F [i dup *] cons] ifte
1054     2 1 popop [dup *]
1055     [dup *]
1056
1057
1058     2 F     [dupdip over * *] cons
1059     [dup *] [dupdip over * *] cons
1060     [[dup *] dupdip over * *]
1061
1062 And here it is in action:
1063
1064     2 [[dup *] dupdip over * *] i
1065     2  [dup *] dupdip over * *
1066     2   dup *  2      over * *
1067     2   2   *  2      over * *
1068     4          2      over * *
1069     4          2      4    * *
1070     4          8             *
1071     32
1072
1073
1074
1075 So, it works, but in this case the results of the partial evaluation are more elegant.
1076
1077
1078
1079
1080
1081
1082 ## Try it with `hylomorphism()`:
1083
1084
1085 ```python
1086 def hylomorphism(c, F, P, G):
1087     '''Return a hylomorphism function H.'''
1088
1089     def H(a):
1090         if P(a):
1091             result = c
1092         else:
1093             b, aa = G(a)
1094             result = F(b, H(aa))
1095         return result
1096
1097     return H
1098 ```
1099
1100 ### First, curry
1101
1102 With abuse of syntax:
1103
1104
1105 ```python
1106 def hylomorphism(c):
1107     return lambda F: lambda P: lambda G: lambda a: (
1108         if P(a):
1109             result = c
1110         else:
1111             b, aa = G(a)
1112             result = F(b)(H(aa))
1113         return result
1114     )
1115
1116 ```
1117
1118 ### lambda lowering
1119
1120
1121
1122 ```python
1123 def hylomorphism(c):
1124     def r(a):
1125         def rr(P):
1126             if P(a):
1127                 return lambda F: lambda G: c
1128             return lambda F: lambda G: (
1129                     b, aa = G(a)
1130                     return F(b)(H(aa))
1131                 )
1132         return rr
1133     return r
1134
1135
1136 ```
1137
1138 ### expression lifting
1139
1140
1141
1142 ```python
1143 def hylomorphism(c):
1144     def r(a):
1145         def rr(P):
1146             def rrr(G):
1147                 if P(a):
1148                     return lambda F: c
1149                 b, aa = G(a)
1150                 H = hylomorphism(c)(aa)(P)(G)
1151                 return lambda F: F(b)(H(F))
1152             return rrr
1153         return rr
1154     return r
1155
1156
1157 ```
1158
1159 ### quoted
1160
1161
1162
1163 ```python
1164 def hylomorphism(c):
1165     def r(a):
1166         def rr(P):
1167             def rrr(G):
1168                 if P(a):
1169                     return "lambda F: %s" % (c,)
1170                 b, aa = G(a)
1171                 H = hylomorphism(c)(aa)(P)(G)
1172                 return "lambda F: F(%(b)s)((%(H)s)(F))" % locals()
1173             return rrr
1174         return rr
1175     return r
1176
1177
1178 ```
1179
1180
1181 ```python
1182 hylomorphism(0)(3)(lambda n: n == 0)(lambda n: (n-1, n-1))
1183 ```
1184
1185
1186 ```python
1187 def F(a):
1188     def _F(b):
1189         print a, b
1190         return a + b
1191     return _F
1192
1193 ```
1194
1195
1196 ```python
1197 F(2)(3)
1198 ```
1199
1200
1201 ```python
1202 eval(hylomorphism(0)(5)(lambda n: n == 0)(lambda n: (n-1, n-1)))(F)
1203 ```
1204
1205
1206 ```python
1207 eval(hylomorphism([])(5)(lambda n: n == 0)(lambda n: (n-1, n-1)))(lambda a: lambda b: [a] + b)
1208 ```
1209
1210
1211 ```python
1212
1213 ```
1214
1215
1216 ```python
1217 hylomorphism(0)([1, 2, 3])(lambda n: not n)(lambda n: (n[0], n[1:]))
1218 ```
1219
1220
1221 ```python
1222 hylomorphism([])([1, 2, 3])(lambda n: not n)(lambda n: (n[1:], n[1:]))
1223 ```
1224
1225
1226 ```python
1227 eval(hylomorphism([])([1, 2, 3])(lambda n: not n)(lambda n: (n[1:], n[1:])))(lambda a: lambda b: [a] + b)
1228 ```
1229
1230
1231 ```python
1232
1233 ```
1234
1235
1236 ```python
1237
1238 ```
1239
1240
1241 ```python
1242
1243 ```
1244
1245
1246 ```python
1247 def hylomorphism(c):
1248     return lambda a: lambda P: (
1249         if P(a):
1250             result = lambda F: lambda G: c
1251         else:
1252             result = lambda F: lambda G: (
1253                 b, aa = G(a)
1254                 return F(b)(H(aa))
1255             )
1256         return result
1257     )
1258
1259 ```
1260
1261
1262 ```python
1263 def hylomorphism(c):
1264     return lambda a: (
1265         lambda F: lambda P: lambda G: c
1266         if P(a) else
1267         lambda F: lambda P: lambda G: (
1268             b, aa = G(a)
1269             return F(b)(H(aa))
1270         )
1271     )
1272
1273 ```
1274
1275
1276 ```python
1277 def hylomorphism(c):
1278     return lambda a: lambda G: (
1279         lambda F: lambda P: c
1280         if P(a) else
1281         b, aa = G(a)
1282         lambda F: lambda P: F(b)(H(aa))
1283     )
1284
1285 ```