Home > Community > Blogs > Custom IC Design > skill for the skilled the partial predicate problem

 Login with a Cadence account. Not a member yet? Create a permanent login account to make interactions with Cadence more conveniennt. Register | Membership benefits
 Get email delivery of the Custom IC Design blog (individual posts).

## Email

Recipients email * (separate multiple addresses with commas)

Message *

 Send yourself a copy

## Subscribe

Intro copy of the newsletter section here, some intro copy of the newsletter. Instruction of how to subscribe to this newsletter.

First Name *

Last Name *

Email *

Company / Institution *

 Send Yourself A Copy

# SKILL for the Skilled: The Partial Predicate Problem

Comments(2)The partial predicate problem describes the type of problem encountered when a function needs to usually return a computed value, but also may need to return a special value indicating that the computation failed. Specifically, the problem arises if the caller cannot distinguish this special value from a successfully calculated value. In this posting of SKILL for the Skilled, we look at several ways to attach this problem in SKILL.

#### Approach 1: Returning nil to indicate failure

A very common way a SKILL function indicates to its caller that it failed to do what was requested is to return `nil`. For example, the SKILL function `nthelem` returns the Nth element of a given list, given an integer N. If the list has less than N elements, it returns `nil`. For example `(nthelem 2 '(10 20 30))` returns `20`, but `(nthelem 4 '(10 20 30))` returns `nil`.

A limitation of this approach is that `(nthelem 2 '(t nil t))` also returns `nil`, because `nil` is the second element. The caller can only trust `nil` to be the failure case if he knows that `nil` is not an element of the list.

Here is an implementation of a `find` function which returns the first element of a given list which matches a given predicate. Note that this example (and most of the examples in this article) only work in Scheme/Skill++ mode.

```(defun find_A (predicate data)
(car (exists x data
(predicate x))))
```

Here are some examples of how it works.

```(find_A oddp '(2 4 5 6 7 9))
==> 5

(find_A stringp '(this is 1 "list" of stuff))
==> "list"

(find_A numberp '(this is a list of symbols))
==> nil

(find_A listp '(t t t nil t t))
==> nil
```

Notice that the `find_A` function returns `nil` in two cases:

• if there is no element in the given list which matches the predicate
• if `nil` is explicitly in the given list and matches the predicate
Thus if `find_A` returns `nil` you don't know whether it found something or not.

#### Approach 2: Returning a given default value on failure

The following implementation of `find_B` attempts to settle the ambiguity by allowing the caller to specify the return value on the so-called failure case.
```(defun find_B (predicate data @key default)
(let ((tail (exists x data
(predicate x))))
(if tail
(car tail)
default)))

(find_B stringp '(this is 1 "list" of stuff) ?default 'notfound)
==> "list"

(find_B listp '(t t t nil t t) ?default 'notfound)
==> nil

(find_B numberp '(this is a list of symbols) ?default 'notfound)
==> notfound
```

A disadvantage of this case is that the caller might find it clumsy at the call-site to provide a value which the given function call would otherwise never return.

#### Approach 3: Wrapping the return value on success

Another common way is to return a wrapped value. I.e., don't return the value found/computed, but rather return a list whose first element is that computed value. The SKILL member function does just this. `(member 5 '(1 2 3 4))` returns `nil` because the given list does not contain `5`; whereas `(member 3 '(1 2 3 4)` returns a list `(3 4)`. Thus the only time `member` returns `nil` is when it didn't find the value being sought.

Another function which uses this approach is `errset`, which returns `nil` if the given form to evaluated triggered an error. Otherwise, `errset` returns a singleton list whose first (and only) element is the value calculated. Thus `(errset 6/4)` returns `(3)`, while `(errset 6/0)` returns nil.

An obvious advantage of this wrapping approach is that the failure condition can always be distinguished from the success case. A disadvantage is that the caller who wants to use the calculated value must unwrap the value with an additional call to `car`, probably after testing whether the value is `nil`.

Here is an implementation of `find_C` which wraps its return value. It only returns `nil` if no element of the list matches the predicate. But the caller must call `car` to unwrap the value.

```(defun find_C (predicate data)
(let ((tail (exists x data
(predicate x))))
(when tail
(ncons (car tail)))))

(find_C stringp '(this is 1 "list" of stuff) ?default 'notfound)
==> ("list")

(find_C listp '(t t t nil t t) ?default 'notfound)
==> (nil)

(find_C numberp '(this is a list of symbols) ?default 'notfound)
==> nil
```

Another disadvantage of this approach is that `find_C` always allocates memory if it successfully finds what its looking for.

#### Approach 4: Continuation passing

Still another way to solve this problem in SKILL++ is by passing a continuation. This involves organizing your code a bit differently, but in the end allows a lot of flexibility. The idea is to pass an extra argument which is itself a function to call with the computed value if successful.
```(defun find_D (predicate data @key (if_found (lambda (x) x)))
(let ((tail (exists x data
(predicate x))))
(when tail
(if_found (car tail)))))
```
The `find_D` function searches the given list for an element matching the condition. If successful, calls the given function, `if_found` and returns the value it returns. Otherwise it omits calling the `if_found` and simply returns `nil`.

#### Continuation passing is a generalization

As you can see from the examples below, the function `find_D` is actually a generalization of `find_A`, `find_B`, and `find_C`.

These examples work like `find_A`.

```(find_D stringp '(this is 1 "list" of stuff))
==> "list"

(find_D listp '(t t t nil t t))
==> nil

(find_D numberp '(this is a list of symbols))
==> nil
```
These examples work like `find_B`.
```(find_D stringp '(this is 1 "list" of stuff) ?if_found (lambda (x) 'notfound))
==> "list"

(find_D listp '(t t t nil t t) ?if_found (lambda (x) 'notfound))
==> notfound

(find_D numberp '(this is a list of symbols) ?if_found (lambda (x) 'notfound))
==> notfound
```
These examples work like `find_C`.
```(find_D stringp '(this is 1 "list" of stuff) ?if_found ncons)
==> ("list")

(find_D listp '(t t t nil t t) ?if_found ncons)
==> (nil)

(find_D numberp '(this is a list of symbols) ?if_found ncons)
==> nil
```

An initial reaction of this type of coding might be that it looks more complicated. But in fact, it is often less complicated when you actually try to use it. Why is this? It is because the code at the call-site usually needs to (1) do something with the calculated value. In addition, there must be program logic, to (2) test whether the value corresponds to the success case or the failure case.

The way `find_D` is intended to be used, the code for case (1) goes inside the function being passed as the `?if_found` argument, and the code for case (2) is already inside the `find_D` implementation. This is shown in the following examples.

#### Example using continuation passing

Assume we have a function, `is_metal_shape?`, which figures out whether a given shape is on a metal layer, presumably by looking at the layer name of the shape and looking in the tech file to see whether that layer has "metal" function. Here is an example of how to use `find_B` and `find_D` to add such a shape to a particular db-group.

```(let ((shape (find_B is_metal_shape? cv~>shapes
?default 'notfound))
(unless (shape == 'notfound)
```

Notice that the call to `find_D` is actually simpler.

```(find_D is_metal_shape? cv~>shapes
?if_found (lambda (shape)
```

This approach has certain advantages over all the alternatives shown above. The most obvious advantage is that there is no ambiguity at the call-site. The caller does not have to tend with the failure condition. In fact it is the function `find_D` itself which knows whether the sought element was found and deals with it appropriately.

#### Handling the found and not-found cases separately

One might also write a version of function `find_D` with an additional `if_not_found` keyword argument to handle the other case that the call-site wants to do something different if such an element is not found--for example to trigger an error.
```(defun find_E (predicate data @key
(if_found (lambda (x) x))
(if_not_found (lambda (_x) nil)))
(let ((tail (exists x data
(predicate x))))
(if tail
(if_found (car tail))
(if_not_found))))
```

#### Summary

In the above paragraphs, we saw several common ways of dealing with the so-called partial predicate problem in SKILL.
• Return nil to indicate failure
• Return a given default value to indicate failure
• Wrap the return value
• Pass a continuation to call on success.

In general continuation passing can indeed be very complicated, but there are certainly cases such as the example shown here, where the style is simple to use and eliminates complexity from your code with no added overhead.

Jim Newton

By Haitham Gad on December 3, 2013
find_C can also be viewed as returning a monadic value (in Haskell terminology). I think it's the best approach for a statically-typed language that supports pattern matching. For a dynamically-typed language (like SKILL), I usually use approach 1 whenever I can i.e. when I know that nil cannot represent any success scenarios.

By Team SKILL on December 4, 2013
Hi Haitham, thanks for your comment.  Yes, I also think approach one is the most common. I've heard case 1 referred to also as nil-punning.

Kind regards

Jim