[00:00.000 --> 00:16.240] Hi, I'm Wilberd. This talk is on self-conscious reflexive interpreters, and is joint work [00:16.240 --> 00:25.480] with Nada Amin. The talk is largely inspired by John Doyle's 1978 MIT PhD thesis proposal [00:25.480 --> 00:31.120] entitled Reflexive Interpreters, but also incorporates ideas from John McCarthy, Marvin [00:31.120 --> 00:38.400] Minsky, and Doug Lenit. It's very much work in progress. I hope you'll bear that in mind [00:38.400 --> 00:47.280] as you listen to the talk. However, we're hoping that ideas in this talk will encourage [00:47.280 --> 00:56.200] you to explore some of the space and ideas of reflexive or self-conscious interpreters, [00:56.200 --> 01:07.520] which both Nada and I find very intriguing and inspiring. So, in 1959, John McCarthy, [01:07.520 --> 01:15.120] who is known for many things, including being the originator of the list programming language, [01:15.120 --> 01:20.080] wrote a paper called Programs with Common Sense. This is one of the early papers in [01:20.080 --> 01:26.560] our symbolic artificial intelligence, or artificial intelligence in general, and he proposes this [01:26.560 --> 01:37.680] idea of writing a problem solver that can learn from its experience and also accept advice [01:37.680 --> 01:44.760] from an external entity and communicate with an external entity. So, he calls this software [01:45.400 --> 01:51.080] an advice taker, or the advice taker. So, when I talk about advice taker, I'm talking about the [01:51.080 --> 01:57.480] software he envisions in this 1959 paper, Programs with Common Sense. And in particular, [01:58.360 --> 02:05.080] his notion of common sense is far beyond what you see in almost any piece of software today, [02:05.960 --> 02:13.160] maybe with large language models very recently, you could argue that there's some common sense, [02:13.160 --> 02:20.360] even that's, I think, highly debatable. However, interacting with a compiler, or a text editor, [02:21.000 --> 02:29.400] or word processor, or things like that, I think there's really no common sense in those programs, [02:29.400 --> 02:40.680] even many decades after this original proposal. McCarthy describes this notion of a advice taker, [02:41.480 --> 02:49.480] and he proposes features of the advice taker that he thinks would be critical for building something. [02:51.160 --> 02:56.040] So, for example, all the behaviors of the system have to be representable [02:56.040 --> 03:00.920] in the system itself. So, this is a system that to some extent understands its own [03:00.920 --> 03:09.560] capabilities and behaviors. And also, the system has to be extensible in a simple way. [03:11.240 --> 03:17.560] And the system has to be able to improve its behavior. [03:19.480 --> 03:28.040] And there are other features of this program that McCarthy considers important. And then in the paper, [03:28.040 --> 03:35.240] he talks about different ways you could describe such a system using imperative or declarative [03:36.040 --> 03:41.320] sentences or language. And he also talks about how you might go about constructing [03:41.320 --> 03:47.640] an advice taker. It's important to understand that in 1959, John McCarthy hadn't attempted to [03:47.640 --> 03:54.920] create such a system. This is basically a white paper describing how you might go about building [03:54.920 --> 04:01.560] a system, or what the design might look like, or what the desired features of such a system would be. [04:02.360 --> 04:08.120] But he certainly hadn't implemented anything like advice taker at this point. [04:09.320 --> 04:14.280] And as far as I can tell, no one has succeeded in building something like advice taker today. [04:16.280 --> 04:21.560] He talks about the main features, representing expressions in the computer and so forth. [04:22.360 --> 04:28.440] When you read this paper, it is from 1959. So, it's fairly early on in the history of computing, [04:29.400 --> 04:38.600] at least as we see it in 2023. But you can see a kernel of an idea here. So, for example, [04:39.400 --> 04:45.720] he has this notion of an immediate deduction routine. So, if you're familiar with Kahneman's [04:45.720 --> 04:51.480] idea of system one and system two thinking, McCarthy in this paper proposes something very [04:51.480 --> 04:57.640] similar where there's fast thinking and slow thinking. You can have slow thinking that's [04:57.640 --> 05:03.080] more reflective or introspective. And you can have fast thinking, which is sort of automatic [05:03.080 --> 05:11.240] thinking. And so, part of the idea in this paper is that a smart system or common sense system, [05:11.240 --> 05:17.800] like the advice taker, would have access to what we might now call solvers. For example, [05:17.800 --> 05:23.080] SAT solvers, SMT solvers, things like that, or program synthesis tools or whatever, that [05:23.880 --> 05:30.760] for solving particular problems might be fast, but in some sense at a global level, [05:30.760 --> 05:39.320] aren't very introspective, not very smart. So, this overall software, which is supposed to [05:39.320 --> 05:48.200] display intelligent behavior, would be capable of using these lower level solvers in an intelligent [05:48.200 --> 05:56.200] way because the overall system would understand what the different solvers are good for and have [05:56.200 --> 06:03.720] some at least, you know, rough notion of how long it takes a solver to run, if it's going to finish [06:03.720 --> 06:10.600] roughly, things like that, what sort of resource usages it might have, and also what resources [06:10.600 --> 06:16.040] the overall system, the overall advice taker has available to it. For example, how much memory, [06:16.040 --> 06:22.440] how much RAM, how much nowadays flash drive space, you know, how much CPU horsepower, [06:22.440 --> 06:27.240] you know, is it running on a parallel supercomputer, is it running on a pocket calculator, so forth. [06:27.960 --> 06:35.800] So, the overall advice taker would be built in this kind of layered fashion, where there'd [06:35.800 --> 06:43.000] actually be a hierarchy of reasoning tasks and problem solving tasks going all the way down [06:43.000 --> 06:50.040] to calling out to these solvers, which probably can't be introspected into. So, in other words, [06:50.040 --> 06:55.880] the overall advice taker program can't look into these solvers necessarily to understand exactly [06:55.880 --> 07:02.200] how they're working, but it has some high level description of how they work or can learn over [07:02.200 --> 07:12.120] time through observation how they work. And the paper also presents a language here, [07:12.840 --> 07:19.320] logic based language basically for, you know, describing how a system might reason about [07:19.320 --> 07:26.280] going to the airport, for example, that kind of thing. Now, I'll say that I find this paper [07:26.280 --> 07:37.880] very inspiring. However, when read today, the paper can seem a little goofy or anachronistic, [07:37.880 --> 07:44.120] I guess, something like that, old fashioned. Part of the idea, part of the reason for that, [07:44.120 --> 07:51.720] I think, is that this example is not very inspiring. And I don't know where this came from. I don't [07:51.720 --> 07:58.520] think this is the greatest use of logic ever. And McCarthy later did a lot of work on frames and [08:00.040 --> 08:03.960] you know, logics where you could talk about what's changing and so forth, [08:05.400 --> 08:11.080] having to do with the frame problem, and these sorts of things. And you can maybe see some of [08:11.080 --> 08:17.240] his early reasoning, or thinking about these problems in this logical description. However, [08:18.120 --> 08:25.000] I don't think it's a particularly exciting example. And so a modern reader may read this [08:25.000 --> 08:30.520] example and think there's nothing really here. But I would encourage you if you read this paper [08:31.320 --> 08:39.080] to think a bit in terms of what McCarthy was trying to accomplish, not in terms of his encoding, [08:39.080 --> 08:44.120] or that particular logic he was using. Instead, you know, focus at the level of [08:44.680 --> 08:52.840] these five facets of a system, or his overall design where you'd have a fast system that you [08:52.840 --> 09:00.040] can't introspect into. And then you'd have high level, you know, a system that could represent [09:00.040 --> 09:05.480] aspects of itself and its behavior. So I think that's the important part of this paper, understanding [09:05.480 --> 09:11.400] that. One thing I found interesting about this paper also, which is definitely different from [09:11.400 --> 09:18.760] how most papers work today, is that at the very end, there's a description of when McCarthy [09:19.400 --> 09:26.920] presented the paper. And he's catching a little flak here from one of the pioneers of [09:26.920 --> 09:35.640] natural language processing, who says Dr. McCarthy's paper belongs in a journal of half-baked ideas. [09:35.640 --> 09:40.520] And part of this, I think, was because McCarthy hadn't even attempted to implement this. You know, [09:40.520 --> 09:45.720] if you think about the computing resources available in 1959, this is a pretty optimistic [09:47.560 --> 09:52.360] you know, system, or the idea that he could build a system, or anyone could build a system like this [09:52.360 --> 09:58.920] in 1959 was pretty amazing given that, you know, they were still basically waiting for [09:58.920 --> 10:04.920] transistorized computers and all that. But anyway, this paper, I think, if read [10:05.480 --> 10:13.000] by a modern reader focusing on the intent of McCarthy and the high level of concepts, [10:13.000 --> 10:20.920] is still inspiring today. And I think it's also true that, as McCarthy points out, computer programs [10:20.920 --> 10:26.920] don't have common sense. And the programs I use day in, day out, don't really learn from me. I can't [10:26.920 --> 10:31.800] converse with them and have a conversation. You know, McCarthy wanted to be able to use [10:32.760 --> 10:38.840] some sort of natural language processing, or maybe stylized language to converse with the program, [10:38.840 --> 10:44.520] and have the program be able to communicate its internal state, or aspects of its internal state, [10:47.560 --> 10:51.880] to an outside advisor, which would have been a human, I think, in McCarthy's day, [10:51.880 --> 10:57.960] but now potentially could be another program. And so he's got a lot of interesting ideas here. [10:58.760 --> 11:05.240] And, you know, I felt his frustration with the state of software, or reading this, [11:05.240 --> 11:11.880] and I feel that same frustration today, which I think is probably one reason why people get [11:11.880 --> 11:18.680] so excited by signing like chat GPT, which does appear to maybe have some common sense, [11:18.680 --> 11:21.720] or to be able to have a conversation with a user. [11:22.440 --> 11:31.320] So, this is a foundational paper in the history of artificial intelligence. It's full of interesting [11:31.320 --> 11:39.000] ideas, if you read it, I think, with the right mindset. And I think we haven't made that much [11:39.000 --> 11:48.600] progress even today on what McCarthy was proposing in 1959. So part of what Nada and I are trying to [11:48.760 --> 11:55.320] figure out is, well, why don't programs today have common sense in the way McCarthy was talking [11:55.320 --> 12:03.000] about? Why can't a program determine when it's stuck and ask for help, or have a human or other [12:03.000 --> 12:08.840] external agent, you know, provide heuristics, something like that. McCarthy wanted one of [12:08.840 --> 12:14.920] these problem-solving advice takers to be able to learn how to become good at a new domain, [12:15.480 --> 12:22.600] such as playing chess, let's say, by, you know, asking questions when it got stuck, [12:22.600 --> 12:28.680] getting advice from an entity that's more skilled than it was, with the idea that they [12:28.680 --> 12:34.680] can improve over time from its experience. Now, of course, today we have programs that [12:34.680 --> 12:40.920] play Go and chess and board games like that extremely well. And there's been a lot of work [12:41.560 --> 12:46.920] on reinforcement learning, and there's the work on alpha zero and so forth. However, [12:46.920 --> 12:54.520] if you think about the staggering amount of computation required to create, you know, [12:54.520 --> 12:59.880] superhuman play with one of those systems, I think that's not at all in the spirit of [12:59.880 --> 13:04.600] what McCarthy had in mind. McCarthy, I think, was talking about how humans learn and the idea [13:04.600 --> 13:09.080] that for humans learning how to play chess, someone more experienced can sit there and [13:09.480 --> 13:19.480] watch and give pithy advice. And a beginner can learn in real time with relatively limited [13:19.480 --> 13:23.960] communication and bandwidth and without, you know, playing against themselves 100 billion [13:23.960 --> 13:30.520] times or whatever happens with these reinforcement learning systems. There's a sort of relatively [13:30.520 --> 13:36.520] small amount of computation in some sense. Now, I'm not saying that the brain isn't very complicated [13:36.840 --> 13:41.960] and doesn't do all sorts of things we don't understand. I'm not saying the brain isn't [13:41.960 --> 13:47.400] capable of lots of computation, but in terms of symbolic manipulation and things like that, [13:47.400 --> 13:54.200] we know our brains are relatively limited. So certainly human beginner doesn't learn how to [13:54.200 --> 14:02.200] play chess the same way that alpha zero would. And the human learning some skill with an expert [14:02.200 --> 14:06.840] setting next to them to guide them learns in a different way. And that's really what McCarthy [14:06.840 --> 14:12.120] is talking about. And so that's what Nata and I are interested in exploring. You know, could we, [14:12.120 --> 14:18.680] now computers or millions of times more capable, try to take another crack at building one of [14:18.680 --> 14:27.480] these systems. Now, another person who was very interested in building this sort of system was [14:27.480 --> 14:37.560] John Doyle. And so John Doyle was studying at MIT in the late 70s. And he was working with Jerry [14:37.560 --> 14:44.680] Sussman. And, you know, this was an era where he had Marvin Minsky and Sussman and this very strong [14:45.320 --> 14:54.200] AI lab that was, you know, interested in things like, you know, scheme programming, the scheme [14:54.200 --> 15:02.840] programming language, you know, came out of this environment. And also symbolic representation, [15:02.840 --> 15:09.560] how do you represent information? And also things like metacircular interpreters. So here's an area [15:09.560 --> 15:16.200] where you're seeing a combination of programming languages and ideas about programming languages [15:16.200 --> 15:22.520] and interpreters and metacircular interpreters, but also connected to symbolic artificial [15:22.520 --> 15:27.720] intelligence. And it doesn't actually have to be symbolic. You could have neural networks [15:27.720 --> 15:32.360] helping out, you could have machine learning or reinforcement learning, things like that, [15:32.360 --> 15:38.760] that interact with the symbolic systems. But there is some notion of a symbolic system inside of, [15:38.760 --> 15:44.760] of what we're talking about here with Doyle and McCarthy. Whether that be functional programming [15:44.760 --> 15:49.000] based or imperative programming based or logic programming based, there's still some sort of [15:49.000 --> 15:54.680] symbolic information and some notion of explainability, which turns out to be important in these [15:54.680 --> 16:03.400] ideas. In case Doyle was interested in this idea of a self conscious, metacircular interpreter. [16:04.360 --> 16:10.120] So the idea that you could have a problem solver, you could, you know, sort of take a crack at [16:10.120 --> 16:16.440] building McCarthy's advice taker, if you had a metacircular interpreter that was augmented with [16:16.440 --> 16:21.320] information about the programming language, it can interpret and its own code and so forth, [16:21.320 --> 16:28.440] and could reason about that. So, and also part of this is that, you know, the system has to [16:29.400 --> 16:35.480] be able to control itself and try to deal with this exponentially growing search base that [16:35.480 --> 16:42.200] comes up over and over again, when you're doing reasoning. So MacArthur, sorry, Doyle [16:42.520 --> 16:48.360] proposes a whole bunch of interesting ideas. And this is linked to a bunch of work that was going [16:48.360 --> 16:54.680] on at MIT lab at that time by, you know, people like Guy Steele and Drew McDermott and so forth, [16:54.680 --> 17:01.800] in addition to Minsky and Sussman and so forth, you know, a whole bunch of other people. I won't [17:01.800 --> 17:08.760] get into all of them, but I definitely recommend reading these AI memos from that time period [17:08.840 --> 17:13.000] and things like the Amor interpreter. Lots of very interesting papers back then. [17:14.280 --> 17:19.640] And McCarthy, sorry, Doyle talks about, you know, the language you might have and [17:20.280 --> 17:26.920] it gives examples of reasoning and compilation efficiency turns out to be a major idea. Once [17:26.920 --> 17:36.440] again, I think if you read this thesis proposal, which is from around 1979, 1980, it's important to [17:36.520 --> 17:44.520] keep in mind the intention and where Doyle was trying to go instead of, you know, overly criticizing [17:44.520 --> 17:51.400] specific examples that maybe aren't very exciting today. Okay, so I think it's important to keep [17:51.400 --> 18:01.400] in mind what he was trying to accomplish. And he wrote a PhD thesis, you know, on related ideas, [18:01.400 --> 18:08.600] a model for deliberation action and introspection, which was published as a AI tech report number 581. [18:10.280 --> 18:21.880] So those are really interesting ideas to me. Doyle also talked about what he called a truth [18:21.880 --> 18:27.400] maintenance system, which later probably should be called a belief maintenance system. But he [18:27.400 --> 18:34.840] proposed this architecture, which I think was largely inspired by work by Sussman and other [18:34.840 --> 18:41.240] people, but more formalized in a particular architecture, this truth maintenance systems [18:41.240 --> 18:51.000] or TMSs. And this paper, this AI memo 521 is full of interesting ideas, including things like [18:51.640 --> 18:59.000] arguing truth maintenance systems that could, you know, argue in front of other truth maintenance [18:59.000 --> 19:05.560] systems, and other truth maintenance systems observing the arguments between two TMSs could [19:05.560 --> 19:10.600] update their own beliefs. So these, these were systems that could update their own beliefs over [19:10.600 --> 19:17.880] time. And there are all sorts of interesting work here, including default logics and things like [19:17.880 --> 19:24.680] that. And, and one of the things that came out of the work on TMSs was this book, Building Problem [19:24.680 --> 19:32.920] Solvers, by Ken Forbes and Johan DeClerre. And this is basically a book on AI patterns and how [19:32.920 --> 19:37.960] they can be AI programming patterns and how they can be applied to various problems. But it talks [19:37.960 --> 19:43.400] about things like the different types of truth maintenance systems. An early piece of work that's [19:43.400 --> 19:53.560] related is, you know, Jerry Sussman's a computational model skill acquisition where he tries to [19:53.560 --> 20:03.640] understand how a program could learn some complex domain like a human could. And, and so this was [20:04.280 --> 20:12.200] really foundational to a lot of the work that came later by people like Doyle. So this was also [20:12.200 --> 20:18.680] very interesting. This is describing his hacker system. So the hacker system, and you can, I think [20:18.680 --> 20:23.400] if you look at the hacker system, you can see something like a TMS inside of it. But this hacker [20:23.400 --> 20:30.200] system could learn basically how to program or learn how to debug programs and things like that. [20:30.200 --> 20:37.080] And so this was an early attempt to, you know, try to deal with problem solving domain having to do [20:37.080 --> 20:43.720] with software development or programming. That was similar in some sense to McCarthy's advice [20:43.720 --> 20:50.680] taker, although as far as I know, there wasn't this notion of, of interaction in the same way [20:50.680 --> 20:58.120] that McCarthy had talked about. So you could see something like the TMS is coming out of this [20:58.520 --> 21:08.680] hacker approach. Another piece of work that came out of the MIT AI lab around that time [21:08.680 --> 21:15.960] was this notion of a Lisp programmers apprentice by Charles Rich and Howie Shrobe. And there was [21:15.960 --> 21:21.320] actually a book that was published by ACM Press on the programmers apprentice project which ran [21:22.200 --> 21:31.480] for, for quite a while at MIT. And the idea was to build a system that could learn the needs of a [21:31.480 --> 21:39.000] software engineer over time. And this, this was an extremely ambitious project at the time [21:39.000 --> 21:46.360] when it started in the 70s, included things like natural language processing and voice [21:46.360 --> 21:52.520] recognition and, and so forth. And different types of program synthesis at the architectural [21:52.520 --> 21:59.880] level, not just at the synthesis at the level of individual functions. So that was also, you know, [21:59.880 --> 22:08.440] an interesting set of ideas that that were going around. Okay, so the last set of ideas I'll talk [22:08.440 --> 22:17.240] about that I think are in this vein, we're from Doug Lennett, who worked on several important [22:17.240 --> 22:24.920] programs. And one was called AM. This is like an automated mathematician. And there was another one [22:25.800 --> 22:32.360] called Eurisco. And here's Eurisco, a plan, a program that learns new heuristics and domain [22:32.360 --> 22:40.120] concepts. And this is part three of that series. And you can find these papers, the nature of [22:40.120 --> 22:48.280] heuristics, so this heuristic based theory formation. Okay, so here's number two. And, [22:49.080 --> 22:53.880] you know, as followed up by this paper, why AM and Eurisco appear to work. [22:54.760 --> 23:05.080] And this is also a very interesting line of reasoning. And so you have this idea of heuristic [23:05.080 --> 23:11.480] guided systems, systems that can invent their own heuristics, and so forth. And you can see that [23:12.040 --> 23:21.320] all of these systems, along with the work by, say, you know, Minsky on Society of Mine, [23:22.280 --> 23:29.480] are similar in that they go to a certain notion of intelligence, which is the ability to get [23:29.480 --> 23:37.240] unstuck, the ability to either ask for help, or to recognize when a system is stuck, or to be able [23:37.240 --> 23:43.160] to use heuristics to get unstuck, or even to use meta heuristics to develop new heuristics to get [23:43.160 --> 23:48.200] stuck, or to use meta meta heuristics to develop meta heuristics to develop meta meta, you know, [23:48.200 --> 23:54.680] develop heuristics to get unstuck, that sort of thing. So, you know, that that is, I think, [23:54.680 --> 24:00.520] core at understanding all of this work, you know, the notion of intelligence, which has to do with [24:00.520 --> 24:10.680] getting unstuck. Now, I could talk a lot more about these ideas, but I would like to change gears [24:10.680 --> 24:18.040] into what Nada and I have been exploring. And, you know, so we've decided, we want to try to [24:18.040 --> 24:25.640] understand why something like AdviceTaker doesn't seem to exist today, at least to our knowledge. [24:25.640 --> 24:31.480] There have been projects, there are projects like the SOAR project, that's OAR, and other projects [24:31.480 --> 24:36.680] have been running a long time for, you know, symbolic AI type things. But as far as I know, [24:36.680 --> 24:45.000] there isn't anything I think that McCarthy would recognize as his AdviceTaker. And so, [24:45.000 --> 24:51.960] the question we have is, why is that? Is it because the basic idea is fundamentally flawed? Is it [24:51.960 --> 24:56.920] because the idea is not well defined enough, and you couldn't tell if it had been built or not? [24:57.640 --> 25:02.840] Is it because that there's some fundamental limitation, like there's some notion of [25:02.840 --> 25:09.880] self-introspection or self-consciousness that we can't describe or runs into the halting problem [25:09.880 --> 25:16.200] or something like that? Or is it just because, you know, people have abandoned that idea? You know, [25:16.200 --> 25:24.360] it's been, let's see, 60 years, plus since that paper was proposed, computers are millions of times [25:24.920 --> 25:28.280] faster, you know, in terms of memory usage and so forth. [25:28.760 --> 25:35.880] Our memory availability, and there's been lots of progress in algorithms and programming languages [25:35.880 --> 25:43.400] and solvers and large language models and so forth. So, maybe it's possible today to try to build [25:43.400 --> 25:49.800] something like AdviceTaker, or at least if it's not, to try to understand maybe why that's not [25:49.800 --> 25:55.160] possible. Now, of course, it could be that the reason AdviceTaker hasn't been built is that it [25:55.160 --> 26:00.280] would take, you know, maybe a thousand people, you know, 20 years to build it. So, that might be [26:00.280 --> 26:08.280] possible. Or it may be that, you know, something could be built today using off-the-shelf components [26:08.280 --> 26:13.560] or the solvers we have and things like that. Combining those things that already exist in the [26:13.560 --> 26:19.960] creative way, maybe that would be possible for a small number of people to make a lot of progress. [26:20.040 --> 26:25.320] So, we're not sure. So, we want to explore, and we want to explore by trying to build things and [26:25.320 --> 26:32.200] figuring out what we find hard, what we find easy, and with nothing else, you know, no other [26:32.200 --> 26:38.040] objective, at least we hope that by exploring this space, we will encounter interesting things we [26:38.040 --> 26:46.920] want to explore more, even if we can't build something like AdviceTaker. Now, the line of [26:47.000 --> 26:52.360] research that I'm starting from has to do with this language called mini-canron that I've been [26:52.360 --> 27:00.680] working on with many people, including Nada and Dan Friedman, Oleg Kostrov, Michael Ballantyne, [27:00.680 --> 27:06.200] Rick Rosenblatt, many, many others. I can't name everyone. But a whole bunch of people have worked [27:06.200 --> 27:16.200] on this language, going back to Dan Friedman's original implementation of it. And this is a [27:16.200 --> 27:22.440] mini-canron has basically turned into a constraint logic language, a pure constraint logic language, [27:22.440 --> 27:29.480] for doing things like writing interpreters, type inferences, parsers, as pure relations. And that [27:29.480 --> 27:36.200] allows you to do types of program synthesis. So, one of the things that came out of that was this [27:36.200 --> 27:44.760] paper, Unified Approach to Solving Seven Programming Problems, where we show how by writing an [27:44.760 --> 27:50.120] interpreter for a subset of scheme as a pure relation, and then combining that with constraint [27:50.120 --> 27:57.080] solving and a special type of search, Oleg Kostrov came up with, it's possible to solve various [27:57.080 --> 28:03.720] program synthesis problems in a unified way. And another thing that came out of this is a [28:03.720 --> 28:11.960] barlerman, this barlerman tool. And so with barlerman, we can do little synthesis problems. [28:11.960 --> 28:19.800] So, for example, here I want to maybe define append in scheme. So, I can say append of the [28:19.800 --> 28:26.040] empty list to the empty list is the empty list. All right, so I'm giving you an example. And then [28:26.040 --> 28:31.640] the system is going to try to fill in basically a template where comma a, comma b, and comma c [28:32.280 --> 28:40.200] are holes or logic variables with no value associated with them, representing holes. And [28:40.840 --> 28:47.400] then, in this case, the, this is the constant function that always returns the empty list has [28:47.400 --> 28:54.680] been synthesized, which is correct, but not very interesting. So, we can try, say, what happens [28:54.680 --> 29:01.960] if we append the list cat to list dog, we should get back the list cat dog. And now, [29:03.240 --> 29:06.600] barlerman has to do a little more work and tries to come up with something a little more [29:06.600 --> 29:12.680] complicated, but it still is missing the recursion. So, we can try doing one more call. So, let's do [29:13.480 --> 29:26.680] how about ABC to DE to get ABCDE. And hopefully, barlerman will be able to synthesize the recursion. [29:27.720 --> 29:31.880] In any case, you can see that we're doing a type of example directed synthesis. [29:32.840 --> 29:39.800] And, you know, under the hood, barlerman uses constraint solving, unification, things like that, [29:39.800 --> 29:50.440] also has type constraints with numbers and, and symbols, and does a, a type of complete interleaving [29:50.440 --> 30:00.040] search. And sometimes barlerman gets stuck. You know, so barlerman is not an example of smart [30:00.120 --> 30:07.000] software, we're in, in the McCarthy notion. Barlerman will often get stuck. However, [30:08.120 --> 30:14.600] in certain cases, at least when there's enough context filled in, barlerman can be relatively [30:14.600 --> 30:19.000] fast. So, right now, it's taking barlerman a while. So, let's just fill in a little more [30:20.520 --> 30:26.760] of the template here. So, I'll, I'll say that we're defying a function called a pen, which takes [30:26.760 --> 30:34.120] two arguments, call them L and S, see if this speeds it up any. And, you know, a human can look [30:34.120 --> 30:39.960] at these examples and figure out things like the name of the function should be append. A human [30:39.960 --> 30:47.480] could also look at the fact that all three of these examples include two arguments. Now, in this [30:47.480 --> 30:52.120] case, they're both lists, although append in general and scheme, the second argument doesn't [30:52.120 --> 30:59.320] have to be a list, but that might help. Another thing we can give is a help, it's help if we want [30:59.320 --> 31:09.160] to is, you know, we might say, hey, because this appears to be a recursive function, we maybe can [31:09.160 --> 31:16.200] give it a barlerman a little more help like that and say that, well, since we have a list [31:16.840 --> 31:22.200] in the first position, we're going to guess that we're going to check if the list is empty. [31:22.920 --> 31:32.280] Otherwise, we're going to do one of two recursive calls. So, that might help. [31:39.640 --> 31:44.280] Might need more help. [31:47.160 --> 31:48.520] How much help does it need? [31:51.800 --> 31:52.360] Let's see. [31:55.400 --> 32:02.520] Okay. So, in this case, it figured it out. I think the fact that I'm recording a video right now [32:02.520 --> 32:07.320] is slowing down the the processor enough that we're using enough memory that [32:08.360 --> 32:13.080] the barlomens having a little more trouble than usual. There are some tricks we can use [32:13.160 --> 32:18.680] to give barlerman hints. But you could see part of it was I was able to fill out [32:19.720 --> 32:26.760] some of the structure. So, I could guess, you know, even a beginning scheme programmer, [32:26.760 --> 32:32.200] we would teach certain heuristics to. So, for example, all right, given these examples, [32:32.200 --> 32:37.400] well, we know we're defining a function called append, we can guess at least that the function [32:37.400 --> 32:42.920] takes two arguments. It might take more than two arguments, or it might take a variable number of [32:42.920 --> 32:48.120] arguments. You know, so maybe it takes zero or more arguments. In fact, the full scheme append [32:49.000 --> 32:54.120] can take any number of lists. In this case, we could do a two argument [32:55.560 --> 33:03.560] synthesis. And if we guess that append should be recursive because we have lists of different [33:03.560 --> 33:10.120] lengths, then if we also guess that we're recurring on the first argument, then we can [33:10.120 --> 33:14.040] probably figure out a lot of the structure of the program automatically. And then we might also [33:14.040 --> 33:20.120] be able to figure out things like, well, maybe we don't know what the base case is. And so, [33:20.120 --> 33:24.680] in this case, it's still still can synthesize the program, even not knowing what the base case is. [33:25.640 --> 33:30.040] So, we could, you know, create a little bit of a skeleton of a program, [33:31.880 --> 33:37.560] just from looking at these examples and following a few heuristics. And then Barleman, [33:37.560 --> 33:44.760] even though it's dealing with this exponential search, could get enough of a hint that it [33:44.760 --> 33:51.000] can finish synthesizing the rest of the program. Okay, so that's an example of how Barleman, [33:51.080 --> 33:57.800] which isn't very smart, could be called from a smarter program that can do introspection on [33:57.800 --> 34:04.200] the examples. And the smarter program could then provide a template or skeleton or sketch [34:04.200 --> 34:09.240] of the program to be synthesized based on what it observes from things like the tests or [34:10.280 --> 34:15.080] some sort of specification provided maybe by human or by another computer program. [34:15.960 --> 34:23.560] So, this idea of using Barleman basically as an external solver is part of what we're trying [34:23.560 --> 34:34.840] to explore as well. I should also mention that the software that we're developing [34:35.800 --> 34:42.520] might also benefit from some of the ideas in Chris Hansen and Jerry Sussman's software [34:42.520 --> 34:50.440] designed for flexibility. And this book is, in some ways, the intellectual successor to [34:50.440 --> 34:57.160] structure an interpretation of computer programs by Abelson and Sussman, but can also be thought of [34:57.160 --> 35:06.440] as lessons taken from artificial intelligence programming out of MIT and in the corporate [35:06.440 --> 35:15.480] world as well, distilled so you can use them in various other software projects. And Jerry Sussman [35:15.480 --> 35:23.000] gave a nice talk in 2022 at the Scheme Workshop, which is available on YouTube, where he talks about [35:23.000 --> 35:28.760] one of these patterns, which is called layering, where you can add things like meta information [35:28.760 --> 35:37.000] you want to keep track to in an intelligent piece of software through this layering technique. So, [35:37.000 --> 35:50.920] that's worth looking at. Okay, so let's look at BAT, which is the Barleman advice taker. [35:51.720 --> 35:59.720] Now, BAT itself, even though if we ever release it, we're probably going to release it under an MIT [35:59.720 --> 36:05.800] license. This BAT project, the Barleman advice taker that Nada and I are working on, has not yet [36:05.800 --> 36:11.720] been released, and we're not sure if or when we will release it. Right now, it's in very early [36:11.720 --> 36:18.040] stages, and we're just exploring some of the ideas that I've been talking about. And I'll walk you [36:18.840 --> 36:25.640] through some of the code and some of the examples to see where we're trying to go. But it is the case [36:25.640 --> 36:33.320] that we're still very early in the development of the software, and it's quite messy. A number of [36:33.320 --> 36:39.480] the files here need to be removed or cleaned up. We need to have documentation and more tests and [36:39.480 --> 36:45.400] things like that. And so, it'll just be a while before we'd be in a position where we want to [36:45.480 --> 36:51.960] release it, and we'd also want it to be more capable. But the other part, the other reason, [36:51.960 --> 36:59.000] at least I'm hesitant to release it right now, is that the ideas and the papers that I've been [36:59.000 --> 37:07.960] showing, those ideas have existed for a long time, and anyone who's smart and creative and [37:07.960 --> 37:13.800] thinks hard about those ideas and is inspired by them, could use their own approach to try to [37:13.800 --> 37:19.720] build something like AdviceTaker or build something like what Doyle was envisioning with a [37:19.720 --> 37:27.720] metacircular reflexive interpreter. And so, the fact that we're building something that uses scheme, [37:27.720 --> 37:35.400] shea scheme, mini-canron, barlerman, you know, scheme interpreter written as a relation and [37:35.400 --> 37:40.360] mini-canron and all those sorts of things, that doesn't mean that that's the only way to approach [37:40.360 --> 37:45.080] what McCarthy was thinking of or Doyle was thinking of. That doesn't mean that we're on the right [37:45.080 --> 37:52.680] track at all. In fact, we could be totally on the wrong track. So, I'm a little hesitant to release [37:52.680 --> 37:58.600] what we have just because, you know, people might just decide that they want to play around with [37:58.600 --> 38:06.360] this and use it, and that this is a starting point for exploration rather than looking at the problem [38:07.240 --> 38:12.200] you know, fresh and reading those papers and just thinking really hard and then using the [38:12.200 --> 38:18.760] techniques that maybe you're familiar with. So, you know, it may be just better for people who [38:18.760 --> 38:23.800] are interested in this area to work independently a little bit and then we could exchange notes or [38:23.800 --> 38:31.800] things like that, maybe hold a workshop or something to talk about ideas. Whereas, you know, just sharing [38:31.800 --> 38:41.480] code may actually not be beneficial. And so, anyway, if you have thoughts on that, let me know. [38:42.600 --> 38:49.960] I think it is a little double edge to share this code right now, given that I don't think we really [38:49.960 --> 38:55.000] understand the special sauce that be required yet. And so, if you start from this code, you may be [38:55.000 --> 39:04.360] heading down the wrong path. Okay. So, I am going to load bat and chase game. [39:08.840 --> 39:15.720] All right. Okay, so that seemed to be running some tests. [39:18.920 --> 39:23.560] Okay, you can see it's applying heuristics and it's calling barlament and things like that. [39:24.520 --> 39:33.000] Okay, so let's just look at this bat software a little bit. And maybe talk about the organization [39:33.000 --> 39:39.480] of the software. So, the current version of that. So, bat stands for barlament advice taker. So, the [39:39.480 --> 39:45.720] idea, the original idea was that we were going to build an advice taker program that was oriented [39:45.720 --> 39:53.160] around barlament, which was the program I just showed you. Now, barlament is not very smart. [39:53.160 --> 40:00.840] Okay, it's not capable of recognizing when it's stuck. It doesn't know anything about its resource [40:00.840 --> 40:08.200] utilization. It can't ask for help. It can't explain its own internal state. So, you could think of [40:08.200 --> 40:15.720] barlament in a sense as a opaque solver that might be called by an introspective system. [40:16.440 --> 40:21.400] Other solvers that might be called from an introspective system would be things like [40:21.400 --> 40:28.840] SAT solvers or SMT solvers, maybe something like Z3, or maybe a solver written using answer set [40:28.840 --> 40:35.960] programming, or maybe something neural based, reinforcement learning based, statistics based, [40:35.960 --> 40:40.040] as long as the answer, you know, could be verified in the end or the system [40:40.040 --> 40:46.120] could reason about its confidence in the answer. So, you have this idea of a solver, [40:46.120 --> 40:52.920] something that's fast, but not introspective, that can be called from the advice taking program. [40:52.920 --> 40:58.600] So, bat is the advice taking program, and barlament is one solver that it could use, [40:58.600 --> 41:04.760] and over time we may add additional solvers. McCarthy also had the idea of a problem domain [41:04.760 --> 41:10.920] because advice taker is supposed to be a problem solver with common sense. That means that you're [41:10.920 --> 41:17.880] trying to solve problems in some domain, whether that being playing a good game of chess or trying [41:17.880 --> 41:24.760] to write a program or whatever, there has to be some problem domain or maybe an advice taker [41:24.760 --> 41:31.880] could handle multiple problem domains. Even all the way back to McCarthy in 1959, [41:32.760 --> 41:39.960] McCarthy was looking at generating programs as a problem domain. John Doyle also looked [41:39.960 --> 41:47.240] at this domain. In fact, many of the people in this area of AI, you'll see, looking at those [41:47.240 --> 41:53.960] papers I showed you, they look at programming, reasoning about programs, generating programs, [41:53.960 --> 41:59.960] fixing or repairing programs as a problem domain. And I think that's natural for two reasons. One is [42:00.600 --> 42:07.160] anyone who's exploring these areas probably is a pretty good programmer or at least has had to go [42:07.160 --> 42:13.560] through the process of learning how to program and knows either how to teach programming or how to [42:13.560 --> 42:20.840] learn about programming has gone through that experience. And also, the other reason is that [42:20.840 --> 42:27.400] because the advice taker itself is a program, in this case, bat is written in Scheme and [42:27.400 --> 42:33.560] mini-canon, if you could build a system that can reason about software and that generate software, [42:33.560 --> 42:40.920] repair software, then there's at least the potential of applying the advice taker to itself [42:40.920 --> 42:48.360] and therefore having the system improve itself. And so I think this is at the heart of Doyle's idea [42:48.360 --> 42:55.720] of this introspective, you know, or reflexive, meta-circular interpreter is that the interpreter [42:55.720 --> 43:02.280] for some problem-solving domain could understand its own code, at least to some extent, have access [43:02.280 --> 43:09.560] to its own code, maybe know semantics of its own code. So you can imagine maybe a problem-solving [43:09.560 --> 43:16.920] interpreter that had access to its own operational semantics for its own interpreter or denotational [43:16.920 --> 43:23.880] semantics or axiomatic semantics, things like that. Formal representations of itself or that [43:23.960 --> 43:29.400] could do abstract interpretation of programs that can interpret things like that. [43:30.360 --> 43:37.080] So that would be an example of an interpreter that had access to some smarts about its own [43:37.080 --> 43:44.280] behavior or capabilities. In addition, you could also have the system have access to [43:44.920 --> 43:50.600] information about the hardware it's running on, how much memory it has available, the processors, [43:50.600 --> 43:56.680] things like that. And furthermore, you could have this information organized in a way, [43:58.680 --> 44:04.280] along with other information about the problem domain. So if the problem domain is about chess, [44:04.280 --> 44:11.000] maybe their concepts related to playing chess. And one way to organize this information is in [44:11.000 --> 44:19.960] an ontology, which is often represented as a tree or a graph or a forest, often trees or forests [44:20.040 --> 44:26.840] of information. So hierarchical information, you can think of this often as sort of an object-oriented [44:26.840 --> 44:32.280] type thing where you have parent-child relationships. And so you can represent all [44:32.280 --> 44:39.560] sorts of information, including heuristics and meta heuristics in an ontology. So in BAT, we have [44:39.560 --> 44:47.320] this idea of an ontology. So we have concepts. And you can see here we have a syntax rules macro. [44:48.040 --> 44:55.560] And we have instances of concepts. So we have a concept in fields. And so we have a notion of an [44:55.560 --> 45:03.160] instance and the types of instance and so forth. And so here are a bunch of helpers. And because we [45:03.160 --> 45:10.840] want to be reflective or as meta-circular as possible, the notion of a concept is itself a [45:10.840 --> 45:16.440] concept. The notion of an ontology is also a concept or an instance is also a concept. So [45:16.440 --> 45:22.040] this is a little small talky in a way, if you want to think of it that way. We also have the [45:22.040 --> 45:31.080] notion of a solver. So we have various types of solvers. And we have the notion of history [45:31.080 --> 45:38.760] and the delta or change between two different states and things like that. So we have a whole [45:38.760 --> 45:48.040] bunch of different concepts here. If I go down here and look at, so initially we had an empty list [45:48.040 --> 45:54.120] of concepts. If I have the system list, the concepts that currently knows about, you can see [45:54.120 --> 46:00.040] that there is information about things like tail position, or I shouldn't say information, but [46:00.040 --> 46:04.280] concepts like things like tail position, which is a grammatical property of software. [46:04.360 --> 46:15.080] And also there are concepts like advice or the fact that there's a user or BAT itself. So BAT [46:15.080 --> 46:23.960] has a concept referring to itself and also has explicit notions of history using a Blackboard [46:23.960 --> 46:31.160] architecture, which I won't get into what a Blackboard architecture is, but that was a traditional [46:31.160 --> 46:38.520] style 1980s AI system approach where you could write different things to memory and that would [46:38.520 --> 46:46.680] trigger certain types of actions. But also notions of resources and things like for the [46:46.680 --> 46:52.120] arity of a function, whether or not the function is variadic and take any number of arguments, [46:52.120 --> 46:59.320] or maybe it's fixed, fixed arity, and we know exactly how many arguments, or maybe it's fixed [46:59.320 --> 47:04.040] arity with at least a certain number of arguments, but we don't know what those are and things like [47:04.040 --> 47:11.080] that. And so the notion of arity itself, the notion of a program template or a sketch, the notion [47:11.080 --> 47:18.120] of variables and expressions. So we're getting into things like, you know, notions of the programming [47:18.120 --> 47:25.000] language that are represented, and the notion of a synthesis problem or a synthesis solution. [47:25.800 --> 47:30.200] You know, all of these sorts of things, including heuristics and meta heuristics, [47:30.760 --> 47:36.680] are important to be able to represent in the system. So those are ideas or concepts represented [47:36.680 --> 47:43.240] in an ontology. And the important part, the most important part is that the system can represent [47:43.240 --> 47:48.760] things about itself. It has a representation of itself as representation of a user or a conversation, [47:49.320 --> 47:58.360] those sorts of things. In addition to an ontology, there's also a notion of communication [47:58.360 --> 48:06.920] between the advice taker and a user or an external entity. So currently, we have sort of [48:08.200 --> 48:12.280] a high level sketch of how we might imagine a conversation. We don't have a working [48:12.360 --> 48:20.760] implementation yet. But you can see some examples of what the conversation with BAT may be. If BAT [48:20.760 --> 48:26.440] gets stuck, you know, trying to synthesize something like factorial, there may be a suggestion to try [48:26.440 --> 48:34.280] to do something like use an accumulator. And so synthesize an accumulator called factorial [48:34.280 --> 48:40.120] AC. And then, you know, there may be a sketch there that the system is able to come up with. [48:40.120 --> 48:45.160] And then you can imagine this sort of conversation going backwards and forwards between [48:45.960 --> 48:52.280] some entity and external entity in BAT itself. So, you know, at this point, we're still trying to [48:52.280 --> 49:00.200] figure out how we would represent that communication. In McCarthy's advice taker paper, he talks about [49:00.200 --> 49:04.600] sort of a stylized language that could be used. And we're definitely figuring that one out. [49:05.400 --> 49:09.320] We also have the notion of an erity. So that was sort of the first thing we wanted to do, [49:09.320 --> 49:17.160] similar to when I tried to, for Barleman, figure out what the erity is for the append function. [49:17.160 --> 49:23.560] That turns out to speed up the Barleman synthesis quite a lot, usually. So you can see that we have, [49:25.800 --> 49:33.400] in this case, the notion of trying to append, to synthesize append. And we have heuristics that [49:33.400 --> 49:42.520] have to do with erity. So here, we have a notion of guessing erity. And then, we have various [49:42.520 --> 49:49.080] helpers to try to help, you know, help us with this notion of guessing the erity of a function. [49:50.360 --> 49:56.360] But you can see here is a heuristic, you know, fine erity sketch from input output examples. [49:56.360 --> 50:03.640] And so here you can see we have an instance in our, our ontology. So we have a heuristic in the [50:03.640 --> 50:10.200] name of the heuristic and when it's applicable and how do you apply it and so forth. There also [50:10.200 --> 50:20.440] is a heuristic having to do with Barleman itself. So, you know, there is a Barleman heuristic. [50:21.160 --> 50:28.920] So you can actually see that, you know, if, if it's possible to invoke Barleman, [50:28.920 --> 50:33.960] that is a heuristic that's available to the Barleman advice taker. So that's one of the [50:33.960 --> 50:40.520] heuristics. And, and we have code here to transform problems into something that Barleman can handle. [50:41.960 --> 50:48.280] So, let's see what else. Engines are something that we're not currently using, but that's a [50:48.280 --> 50:56.760] way to deal with timeouts. Let's see, we have append examples here. So we have input output [50:56.760 --> 51:02.200] examples. So these are, you know, similar to what I was showing with Barleman. And then we [51:02.200 --> 51:08.680] have more sophisticated examples where we might have notions of logic variables or holes, even [51:08.680 --> 51:15.160] in the input output examples themselves, and so forth. And you can see that there are different [51:15.160 --> 51:22.440] types of sketches that might be guessed. And in fact, we can also do things like, you know, [51:22.440 --> 51:28.440] have, have the system, if the system guesses that the base case is not recursive, we can use a minicanrin [51:28.440 --> 51:38.040] absento constraint saying that the name append can't appear in the body of the base case, [51:38.040 --> 51:41.160] if we think that there's a base case. And, and also there's no Lebrecht, [51:42.120 --> 51:48.360] no recursive definitions in the base case. So we can use some of the constraints in minicanrin and [51:48.360 --> 51:55.960] Barleman to enforce certain notions like the idea that we have a base case. And, you know, [51:55.960 --> 52:01.480] we can imagine sort of the internal state of Barleman, how it would work through [52:02.360 --> 52:06.920] different aspects of this program as it's trying to interpret it. And part of the idea is to be [52:07.000 --> 52:12.840] able to simulate what a student learning how to program in a language like scheme might think. [52:13.480 --> 52:20.680] And so there, there are heuristics that we teach to beginning pre scheme programmers, [52:20.680 --> 52:26.360] like if Dan Friedman always teaches, if you write a recursive function and there's no question [52:26.360 --> 52:32.520] asked about a certain argument, like is it null or a pair, then that argument will be passed in [52:32.520 --> 52:38.520] any recursions without being changed. So that would be an example of a heuristic that we could add to [52:38.520 --> 52:49.320] that. Let's see. We also have information like, you know, tail recursion, which we're still working [52:49.320 --> 52:56.840] on. But we have some heuristics with tail recursion that we're working on as well. And then we have [52:56.840 --> 53:03.720] some code that can take one of our templates and turn it into a mini can run example that Barleman [53:03.720 --> 53:12.600] can handle. And we've also, we also have been exploring notions of types that we can, that we [53:12.600 --> 53:25.240] might find useful in the future. And I think, yeah, yeah, so we also have some notes and, [53:25.240 --> 53:32.360] and motivating examples that we care about. And so high level questions that we have are, [53:32.360 --> 53:38.680] what are the sorts of things that we want to, to have a system like that be able to reason [53:38.680 --> 53:44.360] about explicitly, and what information needs or what concepts have to go in the ontology, [53:44.360 --> 53:48.760] like what does that need to know about itself, what does that need to know about potential [53:48.760 --> 53:57.240] resource usage, how is that going to communicate with external entities concisely and represent [53:57.240 --> 54:03.080] concisely its own internal state, and also know when it's stuck or recognize when it's stuck and [54:03.080 --> 54:09.800] ask for heuristics or meta heuristics and have that conversation. So those are things that we're, [54:09.800 --> 54:15.640] we're thinking about. If you find this interesting and you'd like to talk to us, you know, please [54:15.640 --> 54:24.280] drop me an email. And maybe we can do a call. And I also encourage you to try hacking on something [54:24.280 --> 54:30.840] like, like advice taker yourself, I think it's a very interesting set of problems. And a minimum, [54:30.840 --> 54:34.760] I think it's worth reading these papers and trying to understand where a lot of these, [54:35.880 --> 54:43.320] you know, 1980s, late 70s systems were headed towards. And, you know, it was worth rethinking [54:43.640 --> 54:50.600] in modern day, whether or not we could take another shot at it. And if you also think that, [54:50.600 --> 54:56.520] well, everything now is neural, or machine learning, you just remember that neural networks [54:56.520 --> 55:01.160] had multiple times where they were in vogue and then went out of vogue and so forth. So, [55:01.160 --> 55:06.920] you know, maybe time that symbolic systems or at least neuro symbolic combinations of systems [55:07.800 --> 55:13.800] are revisited in the spirit of things like advice taker and McCarthy and Doyle and Minsky [55:13.800 --> 55:21.160] and Sussman and so forth. Thank you very much.