6
$\begingroup$

I'm reading this and I'm having a hard time understanding lazy patterns; in particular I'm baffled with the server-client toy problem and why there is a 'problem' of matching "...too early".

The reason I'm asking this here is because I can understand some Mathematica and it's the only context I can use in order to approach the topic of pattern matching in Haskell.

I can understand the distinction between a Mathematica function that Hold's it's arguments and one that doesn't.

Is that a proper analogy to use?

Can anybody provide a brief explainer in case the two functionalities are similar?

Obviously I'll appreciate any hint, nudge, source in the right direction although I'd prefer something relatively concise and if possible relevant to how pattern-matching works in Mathematica.


Here is the code snippet adapted from the cited tutorial. The issue revolves around the absence or presence of ~ in the definition of client below:

-- Haskell code

import Prelude hiding (init)

reqs                      = client init resps
resps                     = server reqs

client init ~(resp:resps) = init : client (next resp) resps

server      (req:reqs)    = process req : server reqs

init                      = 0
next resp                 = resp
process req               = req+1

main = print (take 10 reqs)

-- prints: [0,1,2,3,4,5,6,7,8,9]
$\endgroup$
12
$\begingroup$

Most of the issue here is related to subtle evaluation and pattern-matching features in Haskell that have no analog in Wolfram Language (WL). The ~ operator has no real equivalent within WL. Nevertheless, the issues can be approximated in WL and such approximation will indeed make judicious use of Hold attributes to induce lazy evaluation semantics.

The crux of the matter is that the linked set of function definitions are mutually recursive. The order in which those recursions are resolved are critically important to avoid runaway calculation. A pattern like (resp:resps) as it appears in client requires the matched argument to be evaluated down to the depth of the first list cell ("cons") prior to evaluating the body of client. But the cons cell in question is produced within the body of client itself. So we get into an infinite regress trying to produce the result.

By changing the pattern to ~resp:resps, the pattern-matching process becomes non-strict and notionally moves the problematic argument cons evaluation over into the body of client after the first result cons cell has been generated.

Details

The question concerns the use of the lazy pattern ~(resp:resps) in the definition of client in the following Haskell code (which has been simplified from the tutorial linked in the question):

-- Haskell code

reqs = client 0 (server reqs)

client init ~(resp:resps) = init : client resp resps
server (req:reqs) = req+1 : server reqs

take 10 reqs
-- returns: [0,1,2,3,4,5,6,7,8,9]

This main thing to note is that the function reqs is not only self-recursive, but it also links the functions client and server together into a mutually recursive dependency. Furthermore, the return values of all of these functions are infinite in length. This setup is useful when used in a non-strict ("lazy evaluating") language like Haskell. If we naively translate this into WL, we get:

(* does not work! *)
ClearAll[reqs, client, server]

reqs[] := client[0, server[reqs[]]]

client[init_, {resp_, resps___}] := Prepend[init, client[resp, resps]]
server[{req_, reqs___}] := Prepend[req+1, server[{reqs}]]

Take[10, reqs[]]

(* $RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of server[reqs[]]. *)

WL has no analog to the systemic lazy evaluation present in Haskell. So any emulation of it is going to be messy. But let us try anyway. There is a definition of some lazy operators at the bottom of this post, notably lazy. We can use these operators to define infinite self-recursive functions and control the depth of strict evaluation. For example:

primes[n_:1] := lazy[Prime[n], primes[n+1]]

primes[] // take[10] // Normal
(* {2, 3, 5, 7, 11, 13, 17, 19, 23, 29} *)

We will now use them to adjust the naive example to have lazy evaluation behaviour:

ClearAll[reqs, client, server]
SetAttributes[{client, server}, HoldAll]

reqs[] := client[0, server[reqs[]]]

client[init_, resps_] := lazy[init, lazy[first[resps], rest[resps]]]
server[reqs_] := lazy[first[reqs]+1, server[rest[reqs]]]

While these definitions do not match Haskell's thunk-based evaluation process exactly, it is close enough for our purposes. It gives the same answer:

reqs[] // take[10] // Normal
(* {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} *)

We are now into a position to discuss the original questions.

Why is there are problem matching "too early"?

In Haskell, most expressions are evaluated non-strictly. But in the case the pattern-matching, some patterns are partially evaluated in strict fashion before evaluating the function body. (resp:resps) is one such pattern. In order to match this pattern, the expression being matched must be evaluated enough to know that it is a non-empty list. That entails evaluating to reach the first cons cell but the elements themselves can remain unevaluated.

In order to obtain the first element, we must evaluate the client expression enough to obtain that element. That means we must evaluate the expression init : client..., where : is the constructor functions of the first list cell (cons). But... we have just said that the pattern (resp:resps) must be evaluated before we get to the : function. That drives a call to server which then calls back to reqs which is back to client... and we are stuck in an infinite evaluation cycle.

The Haskell operator ~ converts a strict pattern into a non-strict one. Operationally, it internally changes the definition of client from this:

-- Haskell code
client init (resp:resps) = init : client resp resps

to this:

-- Haskell code
client init resps = init : client (head resps) (tail resps)

Note how the destructuring of the input list resps is now done in the body of the definition instead of proactively in the argument pattern-matching stage.

Also note we had quietly performed this code transformation when we wrote our WL emulation of the Haskell example. This is because WL lacks any similar sort of rewriting operator so we had to do it manually. But we can still demonstrate the problem in our code if we change the working definition of client from:

client[init_, resps_] := lazy[init, lazy[first[resps], rest[resps]]]

to the broken version:

client[init_, resps_] /; first[resps] != Null :=
  lazy[init, lazy[first[resps], rest[resps]]]

By introducing a pattern condition on the argument resps, we have forced its evaluation prior to the evaluation of the body. It is now "too soon":

reqs[] // take[10] // Normal

(* $RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of first[server[reqs[]]]!=Null. *)

Again, the details of both the pattern and body evaluations in the WL code differ in considerable detail from the Haskell analogs, but they are close enough to demonstrate the principles under which the issue occurs.

Is Haskell's ~ equivalent to Hold?

Sort of. Not really. They both share the attribute that they indicate that an expression is not to be evaluated right away. But Haskell's ~ operator also performs a logical code transformation on the containing definition to enable certain classes of partial lazy evaluation unique to Haskell. In WL, evaluation is generally all or nothing. If we wish to emulate partial resolution of deferred evaluations, we will have to write it ourselves. Consider, for example, the discussion in How do I evaluate only one step of an expression?.


Appendix - Lazy Operator Definitions

The following lazy-evaluation functions are extremely limited in scope, not to mention horribly inefficient. Nevertheless, they will suffice for the purposes of this response.

ClearAll[lazy, first, rest, take]

SetAttributes[lazy, HoldAll]
lazy[x_] := lazy[Nothing, x]

first[lazy[f_, _]] := f

rest[lazy[_, r_]] := r

take[n_][l_] :=
  lazy[If[n <= 0, Nothing, first[l]], If[n <= 0, lazy[], take[n-1][rest[l]]]]

Normal[l_lazy] ^:=
  Module[{ll = l, f}, NestWhileList[(f=first[ll];ll=rest[ll];f)&, Null, # =!= Nothing&]][[2;;-1]]

Bonus Quiz

The ability to predict the output of the following (slightly evil) Haskell example demonstrates that the first steps have been taken off the path of procedural thinking and into Haskell's non-strict world of pattern-matching and equational reasoning:

-- Haskell code

notimperative x =
  let (a,b) = (x+1,c+1)
      (c,d) = (d+1,a+1)
  in (a,b,c,d)

notimperative 0

Spoiler

no, i'm not giving it away that easily :)
Uncompress["1:eJxTTMoPCuZkYGDQMNQx0THWMdIEACG4A0A=", HoldAllComplete]

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I'm not trying to offend anyone or anything but if I could afford it I would be really happy to pay for an answer like this; amazing $\endgroup$ – yosimitsu kodanuri Jan 25 at 15:12
  • $\begingroup$ +1 for the quiz! =) $\endgroup$ – Henrik Schumacher Jan 29 at 9:59
  • $\begingroup$ I think I can pretend I understand how to obtain the result but not really;notimperative 0 binds x with 0; in turn (a,b) gets bound to (1,c+1) and (c,d) to (d+1,2); next, c becomes 3; finally, b becomes 4? $\endgroup$ – yosimitsu kodanuri Jan 30 at 20:27
  • 1
    $\begingroup$ I think you have it. As an exercise, you might want to repeat your analysis without resorting to using the argument value 0. That is, derive a simpler expression that remains a function of x. I think it is sometimes fruitful to take on the mindset that Haskell expressions compute functions rather than data. That mindset also makes discussions about things like monads and category theory slightly less incomprehensible :) $\endgroup$ – WReach Feb 1 at 16:50
  • $\begingroup$ Oh don't get me started on 'incomprehensible'; I stumble in the dark all the time but it is beautiful nonsense, nonetheless. I can't help but thank you for the suggestion and the great answer. $\endgroup$ – yosimitsu kodanuri Feb 1 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.