functions

[Uno]

Lisp isn't really a functional language. Although there's some wiggle
room in the definition, a functional language generally means one based
upon the mathematical notion of a function, i.e. a mapping from arguments
to results.

Such a definition doesn't have any notion of side effects or of mutable
state. The result is determined solely by the arguments, and a function
call whose return value isn't used is essentially a no-op.

In such a language, you can't write functions such as rand(), time(),
getc() etc which return different results for the same arguments. Although
it's legal for a function to have no arguments or to return no result
(technically, the argument or result would be a 0-tuple), there's no
point. A function with no arguments may as well be a constant, and a
function which returns no result may as well not be called.

"Impure" functional languages may include features which violate this rule
(e.g. for I/O). Such a language would still be considered "functional" if
it doesn't rely upon such features unnecessarily.

Alright, well I appreciate Malcolm's comment.

Tja.

 

[Peter Nilsson]

"%z"

ITYM "%zu"

[It would be nice if the standard explicitly said %zd
worked for ptrdiff_t.]

I think removal of implicit int was necessary for the
language, although the lack of required prototypes is
still an issue IMO.

Flexible array members, va_copy, long long and even
support for last enums to have a comma have been useful
for me.

I could argue that extended identifiers is a positive.
Even though every implementation I use can cope with more
than 6 characters of precision, most if not all of my
programs would be UB without that.

 

[Uno]

In order for that to mean anything,
you have to know how "xstdio.h" defines:
FILE
_Next
_Wend
_Fwprep
_Mode
_MLBF
_MNBF
_Buf
fflush

Like this:

/* xstdio.h internal header */
#include <stdarg.h>
#include <stdio.h>
/* bits for _Mode in FILE */
#define _MOPENR 0x1
#define _MOPENW 0x2
#define _MOPENA 0x4
#define _MTRUNC 0x8
#define _MCREAT 0x10
#define _MBIN 0x20
#define _MALBUF 0x40
#define _MALFIL 0x80
#define _MEOF 0x100
#define _MERR 0x200
#define _MLBF 0x400
#define _MNBF 0x800
#define _MREAD 0x1000
#define _MWRITE 0x2000
/* codes for _Printf and _Scanf */
#define _FSP 0x01
#define _FPL 0x02
#define _FMI 0x04
#define _FNO 0x08
#define _FZE 0x10
#define _WMAX 999
#define _WANT (EOF-1)
/* macros for _Scanf */
#define FMAX 512 /* widest supported field */
#define GET(px) (++(px)->nchar, (*(px)->pfn)((px)->arg, _WANT))
#define GETN(px) (0 <= --(px)->nget ? GET(px) : _WANT)
#define UNGET(px, ch) \
(--(px)->nchar, (*(px)->pfn)((px)->arg, ch))
#define UNGETN(px, ch) {if ((ch) != _WANT) UNGET(px, ch); }
/* type definitions */
typedef struct {
union {
long li;
long double ld;
} v;
char *s;
int n0, nz0, n1, nz1, n2, nz2, prec, width;
size_t nchar;
unsigned int flags;
char qual;
} _Pft;
typedef struct {
int (*pfn)(void *, int);
void *arg;
va_list ap;
const char *s;
int nchar, nget, width;
char noconv, qual, stored;
} _Sft;
/* declarations */
FILE *_Foprep(const char *, const char *, FILE *);
int _Fopen(const char *, unsigned int, const char *);
int _Frprep(FILE *);
int _Ftmpnam(char *, int);
int _Fwprep(FILE *);
void _Genld(_Pft *, char, char *, short, short);
int _Getfld(_Sft *);
int _Getfloat(_Sft *);
int _Getint(_Sft *);
void _Ldtob(_Pft *, char);
void _Litob(_Pft *, char);
int _Printf(void *(*)(void *, const char *, size_t),
void *, const char *, va_list);
void _Putfld(_Pft *, va_list *, char, char *);
int _Scanf(int (*)(void *, int),
void *, const char *, va_list);

??

 

[Nick Keighley]

On Jun 20, 5:37 pm, (e-mail address removed) (Richard Harter) wrote:


I'm not a Lisp programmer.

it might be a good idea to look up the definitions of terms before you
pontificate abou them... You can write Lisp in a functional style but
you don't have to. Proper functional programming langauges don't allow
values to be modified (mutated). They don't usually have assignment
and the only side effects are i/o. You can write Lisp like this but a
lot of Lisp isn't like this.

However from what I understand there are
also keywords in Lisp which input and output lists.

Lisp doesn't really have any keywords. Everything is a function.

The main
difference is that the lists themselves may be executable.

that isn't what makes Lisp (or anything else) a functional programming
language. There are librraries for C++ that support a functional
style.

So the
distinction between doing something and shuffling bits would still
hold. Lisp probably makes in more obvious that most code can be
written as functions, however.

it would help if you stayed with more standard terminology...

 

[Nick Keighley]

Alright, well I appreciate Malcolm's comment.

well if he's given you "food for thought" then good. But don't quote
him without doing some checking!

 

[Malcolm McLean]

it would help if you stayed with more standard terminology...

The terms "function" and "procedure" are used in many ways. They ahve
common English-language meanings, and the terms are used in various
programming languages with slightly different meanings. However in
English a "function" is a mapping of an input set to an output set,
whilst a "procedure" is a set of steps for doing something. These
meanings are sufficiently close to the ones I wish to express.

A function of a functional language that performs IO is not a function
in my terminology, it's a procedure. I'm aware that it may be termed a
function. A procedure that writes to a global variable is a function
and not a procedure in my terminology, which is a change from normal
usage, but captures something important.

 

[Keith Thompson]

The terms "function" and "procedure" are used in many ways. They ahve
common English-language meanings, and the terms are used in various
programming languages with slightly different meanings. However in
English a "function" is a mapping of an input set to an output set,
whilst a "procedure" is a set of steps for doing something. These
meanings are sufficiently close to the ones I wish to express.

A function of a functional language that performs IO is not a function
in my terminology, it's a procedure. I'm aware that it may be termed a
function. A procedure that writes to a global variable is a function
and not a procedure in my terminology, which is a change from normal
usage, but captures something important.

You're posting in a programming language forum, specifically a
C forum. C doesn't use the term "procedure", but a number of
other languages do (Pascal, Ada, etc.) -- and they use the terms
"function" and "procedure", fairly consistently, in a manner that's
inconsistent with the way you're using them.

Unless you want this to be a (boring) discussion about the meanings
of words, I recommend that you use terminology that we can agree on.
(I've suggested "pure function" for the distinction you're making.)

I agree that the distinction you're making is a valid one. What do
you want to say about it?

 

[Nobody]

A function of a functional language that performs IO is not a function
in my terminology, it's a procedure. I'm aware that it may be termed a
function. A procedure that writes to a global variable is a function
and not a procedure in my terminology, which is a change from normal
usage, but captures something important.

FWIW: in Haskell, both of these are functions in the mathematical sense
(as that's all that Haskell allows). Computations with side-effects
(whether I/O or mutable variables) are implemented as state transformers,
functions which accept the prior state as an argument and return the
updated state as part of the result.

However, the state itself is typically opaque, i.e. you can't obtain
instances of the state type. Instead, you have a set of primitive state
transformers which can be composed to create more complex programs. For
non-I/O transformers, a function is provided to "run" the transformer and
return the result. The only way to run an I/O transformer is to return it
from the "main" function.

The limited set of operations prevents the state from being "forked",
allowing it to be modified in-place (and allowing the primitive I/O
transformers to be implemented as calls to OS API functions).

 

[Tim Rentsch]

I'm not a Lisp programmer. However from what I understand there are
also keywords in Lisp which input and output lists. The main
difference is that the lists themselves may be executable. So the
distinction between doing something and shuffling bits would still
hold. Lisp probably makes in more obvious that most code can be
written as functions, however.

Lisp isn't really a functional language. [snip elaboration]

Of course Lisp is a functional programming language. Lisp
has evolved to include impure features such as 'setq', so
it's no longer a /pure/ functional language, but it's a
functional language nonetheless. In fact Lisp could be
called the canonical example of a functional programming
language, considering its place in the history of other
functional languages.

 

[Malcolm McLean]

Unless you want this to be a (boring) discussion about the meanings
of words, I recommend that you use terminology that we can agree on.
(I've suggested "pure function" for the distinction you're making.)

I agree that the distinction you're making is a valid one.  What do
you want to say about it?

"Pure functions", using the term a bit more broadly than normal

a) can be written portably, depending on nothing more than memory
allocation.
b) can be tested independent of hardware.
c) almost always can form the heart of the program.
d) may not call IO functions *.

*. except indirectly, really d should read 'may not depend on IO
functions'.

"IO functions"
a) are hardware dependent
b) can't be tested independently of the hardware.
c) in practice are more vulnerable than pure functions to hardware
failure.
d) can call pure functions.

So if we adopt the convention of giving IO functions a special
namespace, eg capitalising the initial letter, we've separated the
program out into two portions, the portable, logic processing portion,
and the non-portable, hardware manipulation portion.

 

[Nobody]

Yes and no. Functional languages and functional progamming is
quite different from procedural languages and procedural
programming. The differences flow from that distinction.

I'm not a Lisp programmer. However from what I understand there are
also keywords in Lisp which input and output lists. The main
difference is that the lists themselves may be executable. So the
distinction between doing something and shuffling bits would still
hold. Lisp probably makes in more obvious that most code can be
written as functions, however.

Lisp isn't really a functional language. [snip elaboration]

Of course Lisp is a functional programming language. Lisp
has evolved to include impure features such as 'setq',

setq has been present since the earliest implementations; e.g. LISP-1
(1960):

http://history.siam.org/sup/Fox_1960_LISP.pdf

(page 136).

so
it's no longer a /pure/ functional language, but it's a
functional language nonetheless. In fact Lisp could be
called the canonical example of a functional programming
language, considering its place in the history of other
functional languages.

It's more functional than Fortran, which was the only other high-level
language around at that time. For a long time, it was the "most
functional" language. But it's far more impure than any modern functional
language (ML, Haskell, Hope, Miranda, ...), both in terms of the
availability of non-functional features, and the extent to which they are
used in real-world Lisp code.

So what would you consider the factors which determine whether a language
is "functional" or not? I.e. what separates an impure functional language
from an imperative language?

Functions as values (lambda forms)? Both Python and JavaScript have those,
but I wouldn't consider them to be functional languages. Apart from
anything else, the lack of tail-call optimisation effectively
prohibits writing substantial code in a functional style.

 

[Uno]

On the implementation that I happen to be using,
there is a putc macro and it happens to be defined this way:

#define putc(X, Y) \
(--(Y)->_cnt >= 0 ? 0xff & (*(Y)->_ptr++ = (char)(X)) :
_flsbuf((X),(Y)))

You don't think that _cnt is the same for your implementation?

I don't know what
_cnt
_ptr
_flsbuf
are.

Anyway, I wrote my toy library mostly to learn
the standard libary. Delving into the meanings of
_cnt
_ptr
_flsbuf
wouldn't have helped my understanding of the standard library,
so I considered putc to be as primitive as I wanted to get.

I would be surprised if Plauger's putc
were very different from his fputc.

What does his putc look like. /* That's not Yiddish */

My expectations get blown all the time with this material:

/* putc function */
#include "xstdio.h"

int (putc)(int c, FILE *str)
{ /* put character to stream */
return (fputc(c, str));
}

stdio.h is one of the harder ones, to be sure.

I've heard it said that one has arrived in C when he can use the
standard library effectively. Do you think it realistic that I could
replicate your toy library?

 

[Nick Keighley]

On Mon, 21 Jun 2010 22:34:07 -0700, Tim Rentsch wrote:

Yes and no.  Functional languages and functional progamming is
quite different from procedural languages and procedural
programming.  The differences flow from that distinction.  
I'm not a Lisp programmer. However from what I understand there are
also keywords in Lisp which input and output lists. The main
difference is that the lists themselves may be executable. So the
distinction between doing something and shuffling bits would still
hold. Lisp probably makes in more obvious that most code can be
written as functions, however.
Lisp isn't really a functional language.  [snip elaboration]

Of course Lisp is a functional programming language.  Lisp
has evolved to include impure features such as 'setq',

setq has been present since the earliest implementations; e.g. LISP-1
(1960):

       http://history.siam.org/sup/Fox_1960_LISP.pdf

(page 136).

so
it's no longer a /pure/ functional language, but it's a
functional language nonetheless.  In fact Lisp could be
called the canonical example of a functional programming
language, considering its place in the history of other
functional languages.

It's more functional than Fortran, which was the only other high-level
language around at that time.

Algol-60. In fact weren't there precursors to Algol-60 (Algol-58?
Algol-W?). But then Algol-60 weren't functional either.

 

[Bart van Ingen Schenau]

q1) Is the C standard library a compendium of the necessary functions?

No. The C standard library consists of (among other things) a
collection of functions that:
a) are impossible to write in portable C (e.g. fopen, fputc)
b) are hard to write an efficient & correct implementation for in
standard C (e.g. sin, cos)
c) have been around for a long time and were considered useful enough
for inclusion in the standard.

The functions of the standard library are hardly ever used all in the
same project. Some projects use one subset of the functions, while
other projects use another subset.
And more often than not, the standard library does NOT contain a
necessary function for some project.

The standard library does not try to cover everything, but instead
contains just a common subset of features that are available.

Bart v Ingen Schenau

 

[Nobody]

No. The C standard library consists of (among other things) a
collection of functions that:

b) are hard to write an efficient & correct implementation for in
standard C (e.g. sin, cos)

Provided that you have a sufficiently large integer type, a correct C
implementation of the trig functions shouldn't be significantly less
efficient than an assembler implementation. Obviously, it will be less
efficient than using a built-in CPU instruction if one exists.

The biggest problem with implementing floating point primitives in
portable C is the lack of a guarantee of a sufficiently large integer
type, coupled with the lack of support for multi-word operations (i.e. no
access to the carry and overflow flags).

 

[Tim Rentsch]

Yes and no. Functional languages and functional progamming is
quite different from procedural languages and procedural
programming. The differences flow from that distinction.

I'm not a Lisp programmer. However from what I understand there are
also keywords in Lisp which input and output lists. The main
difference is that the lists themselves may be executable. So the
distinction between doing something and shuffling bits would still
hold. Lisp probably makes in more obvious that most code can be
written as functions, however.

Lisp isn't really a functional language. [snip elaboration]

Of course Lisp is a functional programming language. Lisp
has evolved to include impure features such as 'setq',

setq has been present since the earliest implementations; e.g. LISP-1
(1960):

http://history.siam.org/sup/Fox_1960_LISP.pdf

(page 136).

My understanding is that Lisp as originally formulated in 1958
didn't have setq. This view is reinforced by the structure
of the supplied document, eg, 'The Program Feature' is relegated
to section 4.5; functions like setq are almost just footnotes.

It's more functional than Fortran, which was the only other high-level
language around at that time. For a long time, it was the "most
functional" language.
Right.

But it's far more impure than any modern functional
language (ML, Haskell, Hope, Miranda, ...), both in terms of the
availability of non-functional features, and the extent to which they are
used in real-world Lisp code.

I tend to agree, although obviously languages that don't
have non-functional features don't use those features,
so the two differentiations are somewhat circular.

So what would you consider the factors which determine whether a language
is "functional" or not? I.e. what separates an impure functional language
from an imperative language?

1. Functions are first-class values (including being able to
produce new functions dynamically).

2. The community that uses the language follows a style that
is predominantly functional.

Functions as values (lambda forms)? Both Python and JavaScript have those,
but I wouldn't consider them to be functional languages.

Both Python and JavaScript started as primarily imperative languages.
Even if they both had function values from day one (which I
don't think they did, but I'm certainly not an expert on the
history of either language), I believe they were put in as minor
elements, not as essential elements.

Apart from
anything else, the lack of tail-call optimisation effectively
prohibits writing substantial code in a functional style.

These kinds of QOI issues are a red herring, I think. For example,
I'm pretty sure early Lisp's didn't have tail call optimization, but
that doesn't change whether Lisp is a functional language. How can
the language be used, how is it expected to be used, how is it
actually used? If a language can (easily) be used in a functional
style, if it is expected to be used in a predominatly functional
style, if it is used in a predominantly functional style, then I
think it's fair to call if a functional language. By this measure
Lisp is less functional than some other languages like ML, Haskell,
etc, but certainly is more functional than any FORTRAN/Algol
derived language (and I think it's fair to include both Python
and JavaScript in that category).

 

[Tim Rentsch]

On Mon, 21 Jun 2010 22:34:07 -0700, Tim Rentsch wrote:

Yes and no. Functional languages and functional progamming is
quite different from procedural languages and procedural
programming. The differences flow from that distinction.

I'm not a Lisp programmer. However from what I understand there are
also keywords in Lisp which input and output lists. The main
difference is that the lists themselves may be executable. So the
distinction between doing something and shuffling bits would still
hold. Lisp probably makes in more obvious that most code can be
written as functions, however.

Lisp isn't really a functional language. [snip elaboration]

Of course Lisp is a functional programming language. Lisp
has evolved to include impure features such as 'setq',

setq has been present since the earliest implementations; e.g. LISP-1
(1960):

http://history.siam.org/sup/Fox_1960_LISP.pdf

(page 136).

so
it's no longer a /pure/ functional language, but it's a
functional language nonetheless. In fact Lisp could be
called the canonical example of a functional programming
language, considering its place in the history of other
functional languages.

It's more functional than Fortran, which was the only other high-level
language around at that time.

Algol-60. In fact weren't there precursors to Algol-60 (Algol-58?
Algol-W?). But then Algol-60 weren't functional either.

Lisp predates Algol-60. Lisp was approximately contemporaneous
with Algol-58, or IAL as it was originally called. (Algol-W was
definitely after Algol-60, not sure by how much.) Both Lisp and
Algol-60 existed on paper for a reasonable period of time before
being implemented, however I'm fairly sure implementations of
Lisp predate implementations of any Algol. (IAL spun off Jovial
(or perhaps more accurately Jovial was spun out following IAL),
I'm not sure when, and I'm not sure when Jovial was implemented
either. So Jovial is another possible contender.) All this
just from memory, so feel free to take with a grain -- or even
two! -- of salt...

 

[Keith Thompson]

Provided that you have a sufficiently large integer type, a correct C
implementation of the trig functions shouldn't be significantly less
efficient than an assembler implementation. Obviously, it will be less
efficient than using a built-in CPU instruction if one exists.

[...]

A CPU instruction that implements, say, the sin function is likely to
be faster than a software implementation, but by no means certain.
There have been complex CPU instructions that actually turned out
to be slower than their software equivalents. (I think the VAX
"evaluate polynomial" instruction was an example of this.)

 

[Nick Keighley]

These kinds of QOI issues are a red herring, I think.  For example,
I'm pretty sure early Lisp's didn't have tail call optimization, but
that doesn't change whether Lisp is a functional language.  

some C compilers implement tail call optimisation

<snip>

 

[Nobody]

1. Functions are first-class values (including being able to
produce new functions dynamically).

2. The community that uses the language follows a style that
is predominantly functional.

Lisp certainly satisfies the former (although so do a lot of
modern languages to some degree). I guess I can't really speak with
authority about the latter.

The Lisp dialect with which I have most familiarity is Emacs Lisp. That
tends to be used in a rather non-functional way, but that's probably
inevitable given the context (i.e. the main purpose of Lisp code is to
modify the editing state in response to user commands).

From what I've seen of other Lisp usage, updating variables on each pass
through a loop seems more common than "reduce", but that isn't really a
statistically-sigificant sample.

Both Python and JavaScript started as primarily imperative languages.
Even if they both had function values from day one (which I
don't think they did, but I'm certainly not an expert on the
history of either language), I believe they were put in as minor
elements, not as essential elements.

I don't know about Python; JavaScript had functions as values from day
one. It's far more widely-used than "lambda" in Python, if only
to define prototype (class) members, i.e.:

MyClass.foo = function(arg) { ... }

or:
MyClass.prototype = {
foo : function(arg) { ... }
}

The more traditional syntax:

function foo(arg) {...}

only works for simple names.

But in spite of all that, I don't think that you can really call
JavaScript a functional language. It certainly doesn't satisfy your
second criterion above.

These kinds of QOI issues are a red herring, I think. For example,
I'm pretty sure early Lisp's didn't have tail call optimization, but
that doesn't change whether Lisp is a functional language. How can
the language be used, how is it expected to be used, how is it
actually used?

If you don't have tail-call optimisation, you don't really have much
choice but to use iteration instead of recursion. IOW, it can't be used,
isn't expected to be used, and won't be used in a functional style.

[I can agree with you about the "doesn't change whether Lisp is a
functional language", albeit from the opposite side.]

For me, "functional" means that "function" has the mathematical meaning,
rather than "procedure which returns a value". An "impure" functional
language is one with strict semantics (e.g. ML); anything more impure than
that is an imperative language, with or without functions-as-values.

gcc's __attribute__((pure)) indicates the mathematical notion of a
function: no side effects, result depends only on the arguments (albeit
with strict semantics, obviously). glibc uses this for e.g. strlen,
strcmp, etc, although not for the math functions as these are affected by
the fenv.h stuff and can set the exception flags. gcc will use this
attribute to eliminate unnecessary calls.