function application in lisp, confusing error messages

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

function application in lisp, confusing error messages

Postby >-) » Fri Jul 18, 2014 2:24 pm UTC

Code: Select all

(defun repeat (f x n)
   (if (> n 0)
      (x)
      (repeat f (f x) (- n 1))))

(defun foo (z) (+ z 1))


i'm trying to repeatedly apply a function.

Code: Select all

>(repeat 'foo 4 0)
*** - EVAL: undefined function F


but foo is defined:

Code: Select all

> #' foo
#<FUNCTION FOO (Z) (DECLARE (SYSTEM::IN-DEFUN FOO)) (BLOCK FOO (+ Z 1))>


so removed the quote thing

Code: Select all

>(repeat foo 4 0)
*** - SYSTEM::READ-EVAL-PRINT: variable FOO has no value


i tried a different set of numbers

Code: Select all

>(repeat 'foo 4 3)
*** - EVAL: undefined function X


wait what. x isn't even supposed to be a function. unless (f x) returns a function. but foo only returns integers

this is in GNU CLISP 2.49

have i made a simple mistake somewhere? i don't get it.

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: function application in lisp, confusing error messages

Postby Nyktos » Fri Jul 18, 2014 5:06 pm UTC

There are a couple of issues here. Lisp is weird.

First of all, "(x)" is Lisp syntax for what would be "x()" elsewhere; in other words, you are indeed trying to call x.

Secondly, you're running one of the more bizarre and confusing features of Lisp, namely the fact that it has separate namespaces for functions and variables – and functions which are passed as arguments fall into the latter. You can't call the f argument using "(f x)", you have to use "(funcall f x)".

Finally, neither of the two things you've tried is the correct way to pass a function as an argument. You've seen that simply typing "(repeat foo 4 0)" doesn't work (because of the namespace issue), but quoting foo is going to pass a symbol, not the function either. The correct way to pass a function in the function namespace is to use the #' operator; i.e. "(repeat #'foo 4 0)".

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: function application in lisp, confusing error messages

Postby >-) » Fri Jul 18, 2014 10:47 pm UTC

thanks for the help.

somehow, funcall feels kind of crude and inelegant.

----
this is a bit off topic but i figured it was better than starting a new thread.

i've been trying church numerals and arithmetic. it worked up until i tried exponentials. i understand the concept behind the exponentiation function:
https://en.wikipedia.org/wiki/Church_en ... h_numerals
which is n repeatedly applies m to f, and function applications multiply, resulting in m*m*m... = m^n applications of f to x

but i can't seem to get it to work. this is my implementation.

i need currying; found this on some site. seems to work

Code: Select all

(defun curry (function &rest args)
    (lambda (&rest more-args)
      (apply function (append args more-args))))


converts number to church representation and back

Code: Select all

(defun church (n)
   (labels
      ((repeat (f x n)
         (if (<= n 0)
            x
            (repeat f (funcall f x) (- n 1)))))
      (lambda (f x) (repeat f x n))))


(defun unchurch (n)
   (funcall n (lambda (x) (+ 1 x)) 0))


some numbers to work with

Code: Select all

(defparameter zero (church 0))
(defparameter one (church 1))
(defparameter two (church 2))
(defparameter three (church 3))


these two work, so i'm pretty sure my implementation is done right

Code: Select all

(defun cadd (n m)
   (lambda (f x)
      (funcall m f (funcall n f x))))

(defun cmul (n m)
   (lambda (f x)
      (funcall n (lambda (x) (funcall m f x)) x)))


my attempts at exponentiation:
just like the wikipedia page right? https://en.wikipedia.org/wiki/Church_en ... h_numerals

Code: Select all

(defun cexp0 (m n)
   (curry n m))

ok maybe i'll have then call f and x afterwards as shown under the function definition column of the table

Code: Select all

(defun cexp1 (m n)
   (lambda (f x)
      (funcall (curry n m) f x)))


i figured that m also needed to be curried

Code: Select all

(defun cexp2 (m n)
   (lambda (f x)
      (funcall (curry n (curry m)) f x)))


tried calling f first, then x, even though it shouldn't make a difference.

Code: Select all

(defun cexp3 (m n)
   (lambda (f x)
      (funcall (funcall (curry n (curry m)) f) x)))


fed n two arguments and removed the curry

Code: Select all

(defun cexp4 (m n)
   (lambda (f x)
      (funcall (funcall n m f) x)))


curried m because it was only getting a singular f as a argument and m takes two

Code: Select all

(defun cexp5 (m n)
   (lambda (f x)
      (funcall (funcall n (curry m) f) x)))


i'm applying m to f, without giving f an argument, so i tried currying f too

Code: Select all

(defun cexp6 (m n)
   (lambda (f x)
      (funcall (funcall n (curry m) (curry f)) x)))


put n and m in the same ( ) to emulate wikipedia's (n m)

Code: Select all

(defun cexp7 (m n)
   (lambda (f x)
      (funcall (funcall (curry n m) (curry f)) x)))


took out the funcall in the hopes that something would work

Code: Select all

(defun cexp8 (m n)
   (lambda (f x)
      (funcall (curry n m) (curry f) x)))


i gave up at this point and just tried sticking it all together

Code: Select all

(defun cexp9 (m n)
   (lambda (f x)
      (funcall n m f x)))


none of these work. i always an error message about either too few arguments or too many to some lambda. if i stare hard enough, i can sometimes figure out what's missing an argument, but i can't seem to come up with an implementation that fits. can anyone offer some advice?

jareds
Posts: 436
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: function application in lisp, confusing error messages

Postby jareds » Sat Jul 19, 2014 1:03 am UTC

>-) wrote:somehow, funcall feels kind of crude and inelegant.

Religious war: You are objectively correct, that is why Lisp-1's (single namespace Lisps) are the best.
>-) wrote:i've been trying church numerals and arithmetic. it worked up until i tried exponentials. [...] can anyone offer some advice?

Yes, write down your types when dealing with complex higher-order functions. In an MLish notation, your Church numerals have type:
'a church2 = (('a -> 'a) * 'a) -> 'a
as opposed to the traditional:
'a church1 = ('a -> 'a) -> 'a -> 'a

With traditional Church numerals, "(unchurch (n m))" works because "int church1" is "(int -> int) -> int -> int", which is the same as "(int -> int) -> (int -> int)", so an "int church1" can be passed to an "(int -> int) church1". Thus, n can take the type "(int -> int) church1" and m can take the type "int church1", and "(n m)" will have the type "(int -> int) -> (int -> int)", which is to say "int church1", which is the desired type to pass to unchurch.

In your case, say we have:

Code: Select all

(defun cexp (m n)
  (lambda (f x) EXP))

and we want to write a correctly typed EXP along the lines of "(((n m) f) x)". Let's say that f and x have types ('b -> 'b) and 'b, respectively. There's simply no way that we can pass m to n without converting it to a church1. Suppose we do so. Then, the simple "((n (church2->church1 m) f) x)" is properly typed:
(church2->church1 m) gets type ('b church1), i.e. (('b -> 'b) -> 'b -> 'b)
n gets type (('b -> 'b) church2)

This would be your cexp5, IF your "curry" were church2->church1, but it is not. church2->church1 does match the definition of currying in the sense of converting a function from a multiple-argument form to a curried form, but your "curry" is currying in the sense of partial application. In types:
Your curry (where X and Y are potentially multiple arguments):
(X * Y -> z) * X -> (Y -> z)
Conversion curry (of a two-argument function):
(x * y -> z) -> x -> y -> z
That is:

Code: Select all

(defun curry2 (f)
  (lambda (x)
    (lambda (y)
      (funcall f x y))))

Takes a two-argument f and returns a curried version, and your cexp5 will work with curry2.

(Note that a more general conversion curry function would be: (curryn n f) with type:
int * (x1 * ... xn -> y) -> x1 -> ... -> xn -> y
but we don't need to write that now.)

A more general piece of advice would be to try to understand more specifically what's going wrong before changing something. I don't get the impression that trying all those versions helped. If you either engaged in a type analysis or perhaps tried to learn your implementation's debugger, it might have helped. But I'm not familiar with GNU CLISP, so I can't give more specific advice in this regard.

>-)
Posts: 527
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: function application in lisp, confusing error messages

Postby >-) » Sat Jul 19, 2014 3:11 am UTC

oh, i see what i did wrong now.

thank you for the help, and i'll keep your advice in mind!

btw, would you be able to link me to a ml type notation guide? i did a few standard google searches but couldn't find anything substantial. particularly, what does that * operator do?

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: function application in lisp, confusing error messages

Postby EvanED » Sat Jul 19, 2014 4:11 am UTC

I don't know what ML guide to give you, but the * is a tuple: e.g. (4,5) is an instance of int*int, or (1,"foo") is int*string (or whatever ML names string types...).

So an curried function that you can call like ((f 1) 2) => 3 in Lisp notation would have type int -> int -> int, but the more traditional, uncurried form that you'd call as (f 1 2) => 3 would have type int * int -> int.

jareds
Posts: 436
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: function application in lisp, confusing error messages

Postby jareds » Sat Jul 19, 2014 4:25 am UTC

ML refers to a family of strongly-typed functional languages, the popular dialects of which are Standard ML (or SML) and OCaml (or Objective Caml). These should be readily searchable. But I'm not quickly finding anything that aren't general language tutorials, so I'll explain the key points.

(T * U * ...) is a product type, or tuple. For example, (7, "hi", false) has type (int * string * bool). (T -> U) is a function type. All functions take one argument and return one value, but functions that take multiple arguments can be expressed as taking one argument that is a tuple. For example, (string * int -> char). Using this notation for a language with native multi-argument functions, I was just referring to the language's native multi-argument functions.

Types can be parameterized by type variables. Type variables have names starting with an apostrophe, but you can see partway through I got lazy and stopped doing that. For example:
list-ref : 'a list * int -> 'a
means that, for any type 'a, list-ref takes an ('a list) (read: list of 'a) and an int, and returns a value of type 'a.

With notation like:
'a church1 = ('a -> 'a) -> 'a -> 'a
I was defining the type "church1 of 'a" as equivalent to the expression on the right.

It might "help" to read about Hindley-Milner (the basis for the type system in the ML family of languages) or type theory or something, but my advice about type analysis really just meant to do it on an ad hoc basis. I do think it is helpful to be able to jot down types for your functions, but you can do that informally using any notation that makes sense.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 4 guests