[q_eng_anon]

this is interesting - thanks for your response.

I'm having a hard time understanding the program you supplied though, the subsequent description did not really help (probs more my fault than your own). I certainly understand the visitor pattern (and have had a sneaky suspicion it is important) but the lambda calculus, not so much.

What type of syntax is the program you supplied in - is it more of a pseudocode or an actual formal language?

thanks for the search keywords - definitely helped - if you have a favorite textbook/arxiv reference/author on this stuff, those would be greatly appreciated as well.

[cardiffspaceman]

The syntax is concise definition of named values where the values are all anonymous functions.

True = (lambda (t f) (t))

-- Let True be the function that takes two parameters t and f and returns the first, t. --

False = (lambda (t f) (f))

-- Let False be the function that takes two parameters t and f and returns the second, f. --

If = (lambda (b tr fa) (b tr fa))

-- Let If be the function that takes three parameters, and applies the first parameter b to the second and third parameters. --

Notice that if the parameter b is the True value above, 'b tr fa' will return 'tr'. If 'b' is False, 'b tr fa' will return 'fa'

  (lambda (x)
    (If x
        (lambda () (display "It was true!"))
        (lambda () (display "It was false!"))))

So it follows that this will pass either "It was true!" or "It was false!" to 'display', waving aside all the stuff you have to define that makes 'display' and STRINGS work as you'd expect.

This is where it becomes clear that you need a lazy system for this to make sense. In an eager system all three of the parameters to 'If' are evaluated and then their values are substituted into the body of 'If'. In a lazy system the expressions for the values are substituted for the parameters in the body, so only the parameter 'b' and one of the other parameters will be evaluated.

When I play around with functional languages I would just write

  True t f = t
  False t f = f
  If b tr fa = b tr fa
  ShowIt x = If x (display "It was true!") (display "It was false!")

You could also write this in (I think this is) Scheme:

  (define True (t f) (t))
  (define False(t f) (f))
  (define If (b tr fa) (b tr fa))
  (define ShowIt (x) (If (x (display "It was true!") (display "It was false!"))))

Except that Scheme isn't usually lazy.

[tonyg]

Yes, this is right except that the language as written is eager Scheme. You don't need a lazy system. The second and third arguments to If are nullary procedures. Their effects are delayed until invoked by whichever of True or False is supplied. Scheme's notation for invoking a nullary procedure -- `(t)`, vs `t` which just refers to the procedure -- doesn't help matters here :-)

[tonyg]

The syntax is close to Scheme and with small changes will run in a Scheme interpreter. For example, here's a session at the REPL of Racket:

  ~$ racket
  Welcome to Racket v7.2.0.6.
  > (define True (lambda (t f) (t)))
  > (define False (lambda (t f) (f)))
  > (define If (lambda (b tr fa) (b tr fa)))
  > (define P (lambda (x)
                (If x
                    (lambda () (display "It was true!"))
                    (lambda () (display "It was false!")))))
  > (P True)
  It was true!
  > (P False)
  It was false!
  > 

Seen differently, it's also close to the mathematical notation of the lambda calculus.

To learn about the lambda calculus, check out chapter 5 of "Types and Programming Languages", Benjamin C. Pierce, MIT Press 2002. You might also get something out of "Semantics Engineering with PLT Redex", Felleisen, Findler & Flatt, MIT Press 2009.

[tonyg]

Oh, see also https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin... for a quick overview of Church and Scott encodings. (Ignore the stuff about Mogensen-Scott. Also, you'll need to have played around with lambda calculus a bit for this stuff to make sense. This kind of thing might be helpful: https://jacksongl.github.io/files/demo/lambda/index.htm)